A Study On Network Coding-based Routing Algorithms For Delay Tolerant Networks

Delay tolerant networks (DTN) are a class of Mobile Ad Hoc Network in whichnodes are intermittently connected. The network works in poor environment and thelink often frequent interruption leading to a stable end-to-end path does not exist at alltimes. Therefore, the traditional routing algorithms cannot be applied to DTN. However,network coding can make the best use of network resource and increase robustness ofnetwork in demanding environment. So it can improve the performance of DTN byapplaying network coding to routing algorithms, and that becomes a significantdirection for research on routing algorithms of DTN.An overview of the conception, characteristics and the relevant theories on delaytolerant networks and network coding is given firstly in this thesis. Then, thecommunication mechanisms of the coding-based routing algorithm used in delaytolerant networks are focused on description. And do deep research on problems that thenumber of coding node is constrained and the bulk data transmission in DTN. On thisbasis, the specific work and the main contribution of this thesis are summarized asfollows:1. A high-efficiency and low-delay data transmission algorithm based on decodinganticipate (HLDA) is proposed to address the problems that large overhead and thedestination nodes wait a long time to decode in the routing algorithm of delay tolerantnetworks based on coding node constrained. The HLDA proposes a unicast and brocastmixing mechanism to decrease the overhead. By decreasing the coding coefficientmatrix interaction mechanism to further reduce overhead. And a new mechanism ofanticipating decoding by hub nodes is presented in HLDA, the coded packet which isthe most beneficial for decoding coded packet will be transmitted prior to thedestination node so that the destination node can obtain the original packets by decodingthe coded packets in time. Then, HLDA can decrease the end-to-end delay.The simulation platform is built with OPNET simulation software to compareHLDA to Hubcode (Hub-based forwarding using network coding) algorithm andEpidemic algorithm. Simulation results show that HLDA can reduce the overhead andaverage end-to-end delay as compared to the Hubcode algorithm and Epidemicalgorithm. 2. To solve the redundant overhead and the end-to-end delay which is affected bydon’t consider the remain survival time of coded packets to set the transmission priority,when the bulk data are segmented coding to transmit in the network, an efficient routingalgorithm for DTN based on dynamic segmented network coding (ERBNC) is proposed.By discarding the redundant ACK and coding packets in ACK transfer stage, andreducing the coding packet header fields, sets different priorities for coding packets tobe forwarded, ERBNC can reduce the network overhead as well as the end-to-end delayof data packets.The simulation is built with OPNET simulation software, and the ERBNCalgorithm’s performance is compared to DSNC (Dynamic Segmented Network Coding)algorithm and SNC (Segmented Network Coding) algorithm. Simulation results showthat, the performance of network overhead and the end-to-end delay of ERBNCalgorithm are improved.Finally, the full thesis is summarized and some further research directions ofrouting algorithms for delay tolerant networks are put forward.