Routing Algorithm Based On Network Coding For Wireless Networks

Nowadays, wireless network has been deep into every corner in our daily life, which influences and changes people’s way of life. In order to send data from one node to another node, wireless network needs routing protocol. The main function of the routing protocol is to find and maintain the transmitting path of data in networks, which plays a decisive role in information dissemination and sharing for wireless networks.Network coding is a new information technology emerged at the beginning of this century. It can greatly improve the network throughput and reliability. It changes the characteristic of receiving-forwarding of the traditional routing protocol, and makes the node have both receiving-forwarding and encoding functions. That is, it lets node encode several packets from different flows into a coded packet to be transmitted so that the number of packet transmissions is reduced, bandwidth utilization and the throughput of network are improved. The characteristic of network coding and the broadcasting nature of wireless channel inspire researchers to apply network coding in wireless network routing protocol so as to improve the routing throughput and lower delay.The mechanism in the network coding based routing for wireless network is quite different from that in the traditional routing. The difference mainly exists in that, in addition to consider the packet transmission rate, delay, throughput, packet loss rate, and other factors which the traditional routing protocols cover, of the optimal network coding scheme should be taken into account. In this dissertation, we study the algorithms based on network coding for wireless network using the broadcast nature of wireless links and investigate the coding-aware routing mechanism, which is different from traditional ones, and its key issues. We mainly focus on the influences of such factors as wireless link unreliability, limited energy and, bandwidth on network coding. In addition, we present the theoretical solutions and its applications. The main work and achievements are as follows:1) The low delay routing problem based on network coding is proposed. We present a coding gain aware low delay routing (CGAR), which is derived from the characteristic of network coding being able to improve network throughput and reduce data transmission delay. The main idea underlying CGAR is that, it lets the node separate data into two parts and one of the parts is transmited using available channel while the other is network coded with the packet from other flows and shares the channel occupied by these flows, improving bandwidth usage and the throughput and reducing data transmission delay. In this dissertation, via introducing coding graph, the problem of encoding the flows is changed into the one to find the least number of complete subgraph in a coding graph. In addition, the coding condition for the multiple flows in the coding graph to be coded is proved and the method of simplifying the coding graph is given. To remedy the problem that the flows with different data rates can not be coded directly, we code them using the method of split-flow and present the greedy algorithm to calculate network coding gain. CGAR takes the delay of transmitting one package as routing metric, which considers the impacts of coding opportunity, available channel, packet loss rate on delay. Simulation experiments show that CGAR has lower transmission delay compared with the DCAR and COPE, the two famous routing algorithms around the world.2) The energy-efficient routing based on network coding is investigated. In wireless network, lowering node transmitting power can reduce the energy consumption, but it possibly decreases link reliability and increases the link bit error rate as well as packet loss rate, which may increase the number of packet retransmissions and consume more energy. To solve this problem, we present an energy efficient routing algorithm based on network coding and power control for lossy networks (NCPCR). Noting that energy consumed by the node depends on its transmitting power and the number of data packet transmissions, the proposed NCPCR reduces transmitting power via power control and reduces transmission number by network coding, and it also balances them to reduce energy consumption as far as possible. NCPCR takes into account the decoding failure resulting from the failure of decoding node overhearing and computes the condition probability of decoding node overhearing the data transmitted by other nodes, and on this basis, the efficient coding condition for the coding node is presented. Simulation experiments show that NCPCR consumes less energy than DCAR and COPE.3) The routing with high throughput and reliability based on intra-flow and inter-flow network coding is studied. By making advantage of the propery that inter-flow network coding can improve the throughput of network and intra-flow network coding can improve reliability of network, we present an algorithm of intra-flow and inter-flow network coding based routing for wireless networks (I2NCR). First, I2NCR uses the improved inter-flow network coding scheme (INCS) to find a fixed routing with as much coding opportunity as possible, making higher throughput. Then, the intra-flow network coding and local opportunistic routing (LOR) is applied in the transmission of each hop. I2NCR can improve throughput while ensuring reliable transmissions of the data packets. INCS overcomes the problem of data retransmissions caused by the different loss rates among multiple links when coding packets are multicast, and it also reduces the number of packet transmissions so as to greatly improve network throughput. LOR reduces the number of retransmissions while guaranteeing the reliable transmission of the data packet using broadcast nature of the channel and letting the node with less expected transmission count (ETX) foreward data. Theoretic analysis and simulation experiments indicate that I2NCR has less number of packet transmissions and higher throughput than the traditional fixed routing and non-network coding routing.The proposed routing algorithms, including CGAR, NCPCR, and I2NCR, are significant in reducing packet delay, improving network throughput, and reducing energy consumption.