Research On Broadcast And Data Aggregation Algorithms In Wireless Ad Hoc Networks

With the rapid development of technology and the continuous improvement of hardware implementation in the 21st century, wireless ad hoc networks (WANETs) have the characteristics of easy deployment, flexible organization, scalability and strong robustness, and so on. Therefore WANETs have attracted lots of academic researchers'attention and have been widely applied to the areas of military and commerce. Broadcast and data aggregation are crucial operations in WANETs. Broadcast is to disseminate the data of nodes to the entire networks, and is widely used for transmitting routing control messages, important codes and latest security patches, and so on. This operation is an important factor for determining the performance of the networks. Data aggregation is first to aggregate the data of nodes using data aggregation functions, and then to deliver the aggregated data to the sink node. This operation is an important means of aggregating the nodes'data in WANETs, and thus is also an important factor for determining the performance of the networks.In some applications of WANETs, since nodes are powered by batteries, their energy is very limited. To conserve the energy, researchers propose several methods, such as using the network coding technology to decrease the number of transmissions of the nodes, and letting the nodes turn to sleep periodically in duty-cycled scenarios, and so on, where the duty cycle is the ratio of a node's active time to the whole scheduling time. This thesis focuses on these two energy-saving scenarios, investigates several optimization problems of broadcast and data aggregation in WANETs, and proposes several efficient solutions with the objective of improving the packet delivery ratio, the energy consumption and the delay. The main contributions of this thesis include the following four aspects.(1) It is an effective means to alleviate the impact of parallel transmissions on the performance of broadcast to apply network coding to broadcast algorithms. However, little work systematically analyzes the optimization of proposed network coding algorithms, and thus existing network coding algorithms are suboptimal. Hence, this thesis first proves that the optimizing problems of applying network coding to broadcast algorithms are NP-complete, and then puts forward a network coding algorithm called COMP. This network coding algorithm adopts the basic ideas of the greedy set packing algorithm and the greedy set cover algorithm to dig network coding opportunities as many as possible. Finally, COMP algorithm is applied to the existing broadcast algorithm. The results of simulation show that, COMP algorithm improves the performance of the existing broadcast algorithm, and its achieved performance improvement is greater than that of the existing network coding algorithm, especially in the scenarios where the network size is large, the maximum transmission range of the node is small and the number of sessions is large.(2) For the duty-cycled WANETs, this thesis studies the problem of collision-free minimum-latency broadcast scheduling, and aims to provide collision-free broadcast schedulings and to minimize the broadcast latency. This thesis proves that one-to-all and all-to-all duty-cycle-aware minimum-latency broadcast scheduling (DCA-MLBS) problems are NP-complete. For the one-to-all DCA-MLBS problem, this thesis proposes an approximation algorithm called OTAB. This algorithm builds a shortest path tree based on the communication latency between the nodes, uses this shortest path tree to layer and color the nodes, and to build the broadcast tree, and then schedules the broadcast layer by layer based on the colors of the parent nodes in the broadcast tree. Therefore this algorithm efficiently avoids the signal collision among the broadcast transmissions, and improves the broadcast latency. For the all-to-all DCA-MLBS problem under unit-size message model and unbounded-size message model, this thesis presents two approximation algorithms called UTB and UNB respectively. Both two algorithms contain two processes: all-to-one data gathering and one-to-all broadcast. This thesis proves that all the three algorithms provide correct and collision-free broadcast schedulings, and then gives the approximation ratios and time complexity of three algorithms through theorectical analysis, where the approximation ratio is the ratio of the approximation algorithm's broadcast latency to the optimal algorithm's broadcast latency. Moreover, this thesis proves that the total numbers of transmissions of three algorithms are at most constant times of the respective optimal algorithm's minimal total number of transmissions. The results of simulations show that, the broadcast latency and the total number of transmissions of OTAB algorithm are lower than those of the existing algorithm, and the broadcast latency and the total number of transmissions of UTB algorithm are more sensitive to the network configurations than those of UNB algorithm.(3) Besides signal collision, signal interference can also cause the failure of packet transmissions, and thus affects the performance of the networks. For the scenarios where the interference range of the node is larger than its transmission range, this thesis studies the problem of duty-cycle-aware interference-free broadcast scheduling (DCA-IFBS) with the aim of minimizing the broadcast latency, and proves the NP-completeness of both the one-to-all and all-to-all DCA-IFBS problems. For the one-to-all DCA-IFBS problem, this thesis proposes an approximation algorithm SIFBS, which schedules the broadcast directly from the source node. This algorithm uses a proper deployment of hexagons and a coloring method to color the nodes, layers the nodes based on the shortest path tree relating to the communication latency between the nodes, constructs the maximum independent sets, and then schedules the broadcast layer by layer based on the colors of the nodes in the maximum independent sets. Therefore SIFBS algorithm avoids the signal interference among the broadcast transmissions, and improves the broadcast latency. To improve the worst-case broadcast latency, this thesis proposes another approximation algorithm called TCABS. This algorithm uses the tree center node to assist the broadcast of the source node's message. For the all-to-all DCA-IFBS problem under unbounded-size message model, this thesis proposes an approximation algorithm called MILD. To schedule the broadcast, this algorithm contains two processes: a data gathering process and a broadcast process. This thesis proves that all the three algorithms provide correct and interference-free broadcast schedulings, and then gives the approximatioin ratios and the time complexity of three algorithms through theoretical analysis. Moreover, this thesis proves that the total numbers of transmissions of all the three algorithms are at most constant times of the respective optimal algorithm's minimal total number of transmissions. The results of simulations show that, SIFBS and TCABS outperforms the existing algorithm in terms of both the broadcast latency and the total number of transmissions, TCABS performs the best, and MILD algorithm outperforms one algorithm which randomly chooses one node to gather the data and broadcast.(4) For the duty-cycled WANETs, this thesis investigates how to provide a data aggregation scheduling with the minimum latency, such that the data of all the network nodes can be aggregated and transmitted fast to the sink node, and the transmissions are interference-free. This thesis proves that this problem is NP-complete, and proposes two approximation algorithms called SDAS and CDAS respectively. SDAS directly transmits the data of all the network nodes to the sink node. CDAS first transmits the data of all the network nodes to the network graph-theoretic center node, and then delivers the aggregated data from the network graph-theoretic center node to the sink node. This thesis proves that all the two algorithms provide correct and interference-free data aggregation schedulings, and then gives the approximatioin ratios, the maximum total numbers of transmissions and the time complexity of two algorithms through theoretical analysis. The results of simulations show that, the data aggregation latency of these two algorithms is significantly lower than the extended version of exiting algorithms. In addition, the data aggregation latency of CDAS algorithm is lower than that of SDAS algorithm except the scenarios where the transmission radius of a node is large.