Research On Distributed Broadcast Algorithm In Wireless Sensor Networks

Global broadcast is a fundamental problem in wireless sensor networks. The efficiency of global broadcast directly impacts the performance of many high level applications and protocols(e.g., route discovery). Global broadcast can be divided into the single-message broadcast and the multi-message broadcast according to the number of messages to be disseminated. In wireless sensor networks, wireless communications among network nodes have often been affected by some interference factors. Therefore, it is very important to adopt an underlying interference model in order to obtain an efficient network protocol. Recently, the physical interference model has been extensively used by protocol designers. The physical interference model is accordant with the practical situation in which the interference decreases gradually with the increasing of the distance between nodes. In addition, the global cumulative interference at a receiver node caused by all the simultaneously transmitting nodes in the network is taken into account. It is more realistic to design efficient distributed broadcast algorithms, since wireless sensor networks in the real world are more likely to be distributed systems. In order to implement grid partitioning on the network, the previous distributed deterministic single-message broadcast algorithms in the synchronous communication model assume that each node knows its coordinate in advance. Thus, the correctness and precision of the algorithms depends largely on the location accuracy of network nodes. And it will result in high cost and energy use to equip some or all of network nodes with GPS(i.e., Global Position System) devices. Moreover, the previous distributed multiple-message broadcast algorithms in the asynchronous communication model adopt the graph-based interference model instead of the more realistic physical interference model. For the reasons above, this thesis focuses on the design and analysis of distributed broadcast algorithms based on the physical interference model without relying on the coordinates of nodes. The main contributions are described as follows.(1) In the synchronous communication model, two distributed deterministic single-message broadcast algorithms are presented. The first broadcast algorithm called TEGB(i.e., the Time Efficient Global Broadcast algorithm) selects a Maximal Independent Set(MIS) for each network layer. Subsequently, multiple subsets of the MIS are carefully selected so as to allow the most concurrent transmissions. The theoretical analysis shows that TEGB has the time complexity of O(Dlogn), where n is the total number of nodes and D is the diameter of the network. Compared with the popular algorithm Det GenBroadcast proposed by Jurdzinski et al., TEGB has a logarithmic improvement in running time. Furthermore, the second broadcast algorithm named TBGB(i.e., the Tree-Based Global Broadcast algorithm) is designed to reduce the number of duplicated broadcast messages at each network layer. Specifically, TBGB can form a unidirectional spanning tree of the network. On the spanning tree, only the non-leaf nodes transmit the broadcast message. Therefore, the redundant broadcasts in the same layer are eliminated. The theoretical analysis shows that TBGB has the time complexity of O(DΔlogn), where Δ is the maximum node degree. Simulation results demonstrate the correctness of the above theoretical analysis.(2) In the asynchronous communication model, a distributed asynchronous multiple-message broadcast algorithm called DAMB(i.e., the Distributed Asynchronous Multiple-message Broadcast algorithm) is presented based on the generalized physical interference model. Based on a predefined transmission backbone, the algorithm DAMB solve the multiple-message broadcast with time cost of OckDn-+?+))]1(2([log τ, where n is the total number of nodes, D is the eccentricity of the sink node, k is the number of broadcast messages to be disseminated,τ is the time duration of a message transmission and c is a constant. The lower bound of all-to-all broadcast(i.e., k=n) capacity achieved by DAMB is ??))8/1(( Wc, where W is the channel bandwidth. What calls for special attention is that the algorithm DAMB is the first one to study the multi-message broadcast problem in large-scale asynchronous wireless sensor networks under the generalized physical interference model.