Research Of Network Coding-based Wireless Unicast And Multicast Scheduling Techniques

With the growing development of wireless technologies and wireless devices, the end users’wireless applications increase rapidly, including text message, audio and video applications, where the proportion of wireless video applications increases gradually, and thus cause growing demand for wireless bandwidth. Compared with wired network, wireless network has lower channel bandwidth, and cannot provide reliable and stable user service. A fundamental approach is to increase the capacity of wireless network, where network coding is considered as the most promising network technology recently. Network coding allows the intermediate nodes to process the data information, and thus increases the unicast and multicast throughput, reduces the transmission delay, decreases the transmission energy and improves network robustness in wireless network.We focus on network coding-based unicast and multicast scheduling techniques in wireless network. As for unicast, we discuss the performance of network coding with constrained overhearing buffers and overhearing management policies in wireless network. For reliable multicast, we analyze the multicast rate bound with two sources and introduce alternative scheduling algorithms which are based on random linear network coding. As for multicast where transmitted flows have strict per-packet delay bound, we propose a weighted debt based multicast retransimission scheduling algorithm. The main research work is as follows:(1) Wireless unicast network coding with constrained overhearing buffers.For wireless unicast applications based on opportunistic network coding, each node caches some packets in a buffer called overhearing buffer for decoding. Traditional FIFO-based (First In First Out) overhearing management policy for "X" coding structure is discussed, the impact of different queue scheduling algorithms and bandwidth allocation on system throughput are also analyzed. With finite overhearing buffers, theoretical result shows that throughput decreases rapidly as the buffer size decreases. Therefore, we propose a Best Effort-based overhearing management policy, which improves the probability of cached packets to be used for decoding, and thus increases the system throughput. Furthermore, to buffer less useless packets, we propose an overhearing management policy based on historical information, which could effectively decrease the impact of interfering flows on system throughput. (2) Random linear network coding based alternative scheduling algorithms with two sources.To lessen the impact of multicast member with the worst link quality on multicast rate in single source multicast, we analyze the multicast rate bound with two sources, and present static and dynamic alternative scheduling algorithms for two sources reliable multicast. Through transmitting encoded packets alternately, the presented algorithms exploit the link heterogeneity between multicast members and different sources. Compared with single source multicast, theoretical analysis and simulations show that both scheduling algorithms can effictively improve the multicast rate, thereby decrease expected time for completing transmission. Dynamic alternative scheduling algorithm acheives less expected transmission time by dynamically updating parameter.(3) Weighted debt based multicast retransimission scheduling algorithmIn the typical multicast model with single base station and multiple receivers, we focus on multicast flows with strict per-packet delay, where different receivers require different average throughput demands. We propose a weighted debt based multicast retransmission scheduling algorithm, the proposed algorithm collects the packet loss information and calculate the corresponding weighted debt for all receivers and the flows subscribed by the receiver after each transmission. We transform the problem of searching optimal encoded packet to weighted maximum clique problem, where the vertex weight is exactly the corresponding weighted debt. To solve the weighted maximum clique problem, we propose an approximation algorithm, where the algorithm encodes as many packets as possible on the premise of scheduling the vertex with maximum weighted debt. The simulation result shows that no matter in which scenes, the proposed weighted debt based multicast retransmission scheduling algorithm decreases the ratio of unfinished throughput demand, at the same time, the average throughput debt is lowest in all scheduling algorithms.