Font Size: a A A

Dominating Set Algorithms And Policies For Data Gathering In Wireless Sensor Networks

Posted on:2010-08-31Degree:DoctorType:Dissertation
Country:ChinaCandidate:R Y YuFull Text:PDF
GTID:1118360308978468Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Wireless sensor networks consist of a large number of sensor nodes, which are equipped with sensing, data processing, and communicating components. The sensor nodes collaborate together to monitor various phenomenons. Due to the low-power, low-cost, intelligent, distributed, and self-organized characteristics, wireless sensor networks have shown great potential in many fields, such as, military, environment, health, business, disaster forecast and relief.Wireless sensor networks are data-oriented, whose main task is data processing, including sensing, data gathering, transmission, compress, aggregation, and so on. Wireless sensor networks are usually densely deployed in a network area, and generate a great deal of data. Moreover, the data sensed by neighboring nodes is high correlated. These all impose great challenges on the design of data gathering algorithms.Since the sensor nodes are power-constrained, transferring large amounts of data definitely will shorten the lifetime of sensor networks. Therefore, the network performance on energy consumption and stability could be improved through the communication structure optimization or data redundancy removal.A virtual backbone plays an important role for the communication structure optimization. One of the frequently used techniques for virtual backbone construction is the dominating set. Many literatures proposed to use a connected dominating set as a virtual backbone in wirless networks, and designed various efficient algorithms. But few of them take special properties of sensor networks into consideration, such as data gathering, redundancy removal, etc.This dissertation focuses on the dominating set problems for efficient data gathering in wireless sensor networks.Because the tree structure is more appropriate for flooding, data gathering, and data aggregation in wireless sensor networks, this work first investigate the tree-based connected dominating set problem. The ordinary connected dominating set problems are based on connected networks. To extend the concept of connected dominating set into sparse sensor networks, and considering the data correlation as well, we propose the concepts of the virtual dominating set, the completedly virtual dominating set, and the correlation dominating set. Several efficient data gathering algorithms based on the extended dominating set concept are presented in this dissertation.Firstly, the energy-efficient dominating tree construction (EEDTC) algorithm is proposed to construct a dominating tree as a virtual backbone in wireless sensor networks. The EEDTC algorithm uses k-hop neighborhood information, and adjusting k will achieve different message complexity and time complexity for the algorithm. The EEDTC algorithm has good performance on energy consumption and energy balance of the network, and performs well under various traffic patterns in data gathering applications.Sencondly, for the purpose of gathering data from partially-connected sensor networks, with the help of virtual dominating sets, a grid-based mobile element scheduling (GBMES) algorithm is raised to schedule a mobile element (ME) periodically gathering data from the network. The GBMES algorithm has decent performance on reducing the traveling delay and data gathering delay of ME, which minimizes data loss due to the buffer overflow of sensor nodes.Thirdly, to efficiently gather data from spase sensor networks, two Voronoi diagram based algorithms are proposed, one is the Voronoi diagram based mobile collector scheduling algorithm (VDMCS), and the other is the multiplicatively weighted Voronoi diagram approach to energy-balancing data collection (MWVDC). Two algorithms both construct a completedly virtual dominating set using iterative virtual site insertion. The completedly virtual dominating set just covers all sensor nodes within a given transmission radius. Based on the completedly virtual dominating set, VDMCS constructs a shortest loop tour for the mobile collector (MC), while MWVDC constructs a loop tour for MC by compromising data gathering delay and energy consumption. Moreover, MWVDC is able to attain energy balance for the sensor network.Finally, an algorithm named the entropy evaluation for correlation dominating set construction (EECDS) is presented. The EECDS algorithm exploits the concept of the correlation domining set. It first determines the correlation between sensor nodes by evaluating the entropy of random variables, and then distributively generates a correlation graph. At last, the algorithm constructs a correlation dominating set using the information of the correlation graph. The EECDS algorithm is very efficient on reducing data redundancy in wireless sensor networks, and performs well on energy balance and scalability.
Keywords/Search Tags:Wireless sensor networks, Data gathering, Dominating set, Virtual dominating set, Correlation dominating set, Voronoi diagram, Information entropy, Differential entropy
PDF Full Text Request
Related items