Research On Routing Policy Based On The Graph Model For Delay Tolerant Networks

Compared with the traditional static networks, Delay Tolerant Networks(DTNs) have time-varying link capacity and dynamic topology, which makes it difficult for us to solve the routing problems directly with traditional static network theory in DTNs. Although the fundamental architecture has already existed, some basic theories and techniques for DTNs are not complete, such as the DTNs modeling, the maximum flow problem and the shortest routing problem. Therefore, research on modeling and routing policy in DTNs is still necessary according to its specific link characteristics.The contact between the nodes in DTNs is frequently interrupted, thus the link delay in DTNs includes the propagation delay, transmission delay and also the waiting time. The transmission delay of traffic is not only dependent on the capacity parameters of the link, but also related to the relationship between connectivity time interval series of two adjacent links, which cause the difficulty in computing the link delay. In this paper, we propose a cumulative traffic method to obtain the end-to-end delay of path based on the continuous time-aggregated graph in both single-hop and multi-hop scenario, considering traffic amount, transmission time and the relationship of connection interval series for adjacent two-hop link in network modeling. Based on this delay model, we optimize the conventional Earliest Delivery(ED) algorithm and further propose a shortest delay routing algorithm according to the continuous time-aggregated graph. Several simulation results are further presented to evaluate the proposed routing mechanism with the practical satellite DTN statistics, which is exported by Satellite Tool Kit software, so as to demonstrate the advantages of our proposed scheme in DTNs.Due to the intermittent link connectivity between nodes, there is no real-time end-to-end path in DTNs, thus it is impossible for us to solve the maximum flow problem with a direct application of augmenting path algorithm. In order to maximize the utility of network resources, acquire the upper limit of traffic amount with limited transceivers and obtain the optimal value of transceiver number, an algorithm is necessary which can reasonably schedule the transceivers, node buffer and link flow. In this paper, we propose a nonlinear programming model for maximum flow problem based on the time expanded graph, which effectively obtain the optimal routing mechanism, buffer allocation and transceiver schedule with multiple constraints taken into account, such as node buffer constraints, bounded link capacity and limited transceivers. Further, we employ the Linear Interactive and General Optimizer to solve this nonlinear programming model, and verify the performance of our algorithm in both maximum flow and convergence aspects.