Study On Reliable Multicast Based On Network Coding In Wireless Network

Varieties of wireless networks have become popular along with the development of communications technology, such as cellular network, wireless ad hoc network, etc. Recently the mobile host and handheld computers are becoming more popular and many network applications are promoted in wireless networks. Due to the poor quality of wireless channel and node mobility in wireless networks, data packets are often lost. However, most applications require reliable data transmission in wireless networks. Therefore, the reliable transmission of data packets in wireless networks is very important.In wireless networks, according to the feedback from receivers, a source knows the packets receivers already have and the lost packets at receivers. This dissertation studies how to encode and retransmit to ensure that the receivers recover the lost packets using network coding. For different scenarios, this dissertation studies different encoding and transmission scheduling schemes to optimize network performance, optimization objectives include minimizing the total number of retransmissions, minimizing the number of packets missing theire deadlines and so on. The main work and contributions are as follows:(1) Network coding based reliable retransmission algorithmThis dissertation studies network coding based realiable multicast in wireless network, the objective is to minimize the total number of retransmissions and proposes a graph model to model the network coding based retransmission problem. It is proved that the encoding strategy is equivalent to a minimum clique partition problem in the graph. To solve this problem efficiently, this dissertation proposes an approximation minimum clique partition algorithm with time complexity O(|E|) and proves its correctness, where |E| is the number of edges in the graph. For different packet loss ratios of wireless network, we compare the coding based retransmission strategy with traditional strategy in experiments. Simulation results show that fewer packets are retransmitted with network coding than with the conventional retransmission strategy.(2) Network coding based reliable multicast modelBased on the above work, we propose two models (Dynamic Multicast Retransmission Encoding, DMRE), (Cache-based Multicast Retransmission Encoding, CMRE) and the corresponding heuristic algorithms to further reduce the number of retransmissions. DMRE is a memoryless model which assumes that the receiviver does not cache the encoded retransmission packets for future use. DMRE model uses the continually updated information of each receiver to reduce the number of retransmissions. In DMRE, each retransmission decision is based on the latest packets requirements of the receiviers. CMRE model assumes that a receiver can cache all the received encoded retransmission packets and decode only when enough packets are received. Simulation results show that retransmission using DMRE is better than clique partition based encoding, and CMRE model performs better than DMRE model.(3) Broadcast scheduling based on network coding in time critical wireless networksConsidering the quality of service (QoS) such as the packet delay requirements in streaming media applications, this dissertation studies network coding based broadcast scheduling in a time-critical wireless network, the objective is minimizing the number of packets missing their deadlines. This dissertation presents a weighted graph model to describe the problem, and proves the network coding based broadcast scheduling problem in time-critical wireless networks with packets delay constraints is NP_hard. An integer programming method is proposed to solve the problem with small network size. According to the appropriate weight on vertex assigned in the model, usually the decreasing function of packet deadline, a maximum weighted clique based encoding algorithm is proposed to reduce the number of packets missing their deadlines. Also this dissertation analyzes how to set the vertex weight function to meet different application requirements in detail, which can be a reference for the design of the QoS aware network coding broadcast scheduling problem.