Design And Implementation Of Adaptive Routing Algorithm In Mobile Delay Network

The objective of the architecture for Delay Tolerant Network (DTNs) is to support the networking between nodes under the circumstance with intermittent connectivity, high end-to-end latency and high transmission error ratio. Due to the mobility of nodes, there usually does not exist an end-to-end connected path. Therefore, nodes in DTNs communicate in a hop by hop "store-carry-forward" manner. In recent years, research on DTNs mainly focused on routing protocols, and thus it becomes a hot topic in DTNs that how to make a correct and efficient routing strategy adaptively. The main contribution of this thesis are focused on three aspects:(1) Movement pattern-aware relay node group selection algorithm. We propose a Movement Pattern-Aware optimal Routing (MPAR) for SDTNs, by choosing the optimal relay node(s) set for each message. Concretely, the movement pattern of a group of node(s) can be extracted from the movement records of nodes.the routing problem is formally defined as a NP-Complete combinatorial optimization problem. We also demonstrate the difficulty for an online algorithm to solve the routing problem.(2) Message transmit profit based optimal schedule algorithm. We try to improve the routing performance by resorting to an efficient data item selection mechanism that takes the bandwidth and connection duration time into consideration. A specific data item selection mechanism for a probability-based routing is devised, which is formally defined as an optimal decision-making problem and solved by the dynamic programming technique.(3) Hop count based heuristic distance vector protocol, we propose a hop count based heuristic routing protocol by utilizing the information carried by the peripatetic packets in the network. A heuristic function is defined to help in making the routing decision. We formally define a custom operation for square matrices so as to transform the heuristic value calculation into matrix manipulation.The reasonability and reliability of the work in this thesis has been proved by the simula-tion. It can be seen from the results that all the three proposed algorithms outperform current ones.The work in this thesis can be extended thus applied to some real network scenarios, e.g. Vehicular Ad Hoc Network (VANET) and Mobile Social Network (MSN). Therefore, the work possesses theoretical and practical significance.