Research On Data Aggregation Scheduling Techniques In Wireless Sensor Networks

With rapid development of sensing techniques, embedded computing techniques andwireless communication techniques, wireless sensor networks with the advantage of lowcost and self-organization are widely applied in many fields, such as environmental mon-itoring, medical care and military defense. Wireless sensor network is a novel technologyfor acquiring and processing information. Thus, operations on the sensed data obtainedby wireless sensors are indispensable, and aggregation is one of the most fundamentaloperations, which is widely concerned by academia. In many wireless sensor network ap-plications, administrators or users usually submit an aggregate query on some of the phys-ical attributes of the sensed area. Then, the base station needs to aggregate the sensed datafrom all or a part of the nodes, and provide the aggregate result to the query user. In orderto eliminate the wireless interference during aggregation, aggregation scheduling problemaims in producing a collision-free schedule for the network, minimizing the aggregationtime at the same time. Thus, aggregation scheduling methods satisfy the query users withquick response by eliminating the interference and reducing the aggregation time. A wire-less sensor network is composed of a set of low-cost, low-power sensor nodes and theyorganize themselves to form an ad-hoc wireless network. Wireless sensor networks havethe following characteristics of limited node energy, limited communication capability,dynamic topology, etc. This brings some challenges for solving the aggregation schedul-ing problem in wireless sensor networks, e.g., how to design energy-efcient schedulingalgorithms, how to design scheduling algorithms for dynamic topology, how to increasethe data delivery rate. Facing the challenges, this thesis considers aggregation schedul-ing problem in wireless sensor networks from diferent aspects, and proposes diferentstrategies and algorithms. The research issues and results include the following.First, this thesis proposes a distributed aggregation scheduling algorithm for wirelesssensor networks. The previous aggregation scheduling algorithms are centralized withhigh aggregation time latency, which are not suitable for dynamic topologies. To solvethe problems above, this thesis proposes a two-phase distributed scheduling algorithm.The first phase of the algorithm distributively constructs an aggregation tree with a goodproperty, making use of maximal independent set, and divides the nodes into diferenttypes. In the second phase of the algorithm, sensor nodes first communicate with each other to obtain the local information and then generates the schedule with the obtainedinformation. The proposed algorithm is an approximation algorithm since the aggregationscheduling problem is proved NP-hard. Theoretical analysis show that the approximationratio of the algorithm is close to a constant number, which improves the aggregation timelatency. This thesis also proposes an adaptive strategy for our algorithm to handle thedynamic topologies, including adaptive tree maintenance and aggregation update.Second, this thesis proposes two aggregation scheduling algorithms for multi-sinksensor networks. There exist the problems of imbalanced load and energy cost in single-sink sensor networks. Deploying multiple sinks (base stations) with powerful computa-tion and communication capabilities helps alleviate the problems, thus multi-sink sensornetworks are widely concerned and applied. This thesis proposes two scheduling algo-rithms with two phases, which construct aggregation forests in the first phase and generateschedules in a bottom-up fashion. The diference between the two algorithms lies in theforest construction phase. The first algorithm takes advantages of Voronoi partitions andthe second algorithm constructs an aggregation forest with good properties using dominat-ing sets. This thesis shows the aggregation time of both algorithms and proves the secondalgorithm performs better. Simulation results show the efectiveness of the algorithms.Third, this thesis proposes an aggregation scheduling algorithm for duty-cycledwireless sensor networks. Considering the limited node energy in wireless sensor net-works, duty-cycled working style is adopted, i.e., a node works for a duration of timeduring a cycle and sleeps for the rest time of the cycle. The duty-cycled mechanism helpssave large amounts of energy, thus prolong the network lifetime, which has a wide ap-plication perspective. The proposed algorithm first constructs a layered structure of thenetwork and then schedules the working period. Theoretical analysis shows the approxi-mation ratio of the algorithm is close to a constant number, and simulation results showthe efectiveness of the algorithm.Finally, this thesis proposes a novel opportunistic aggregation scheduling mechanis-m for aggregation scheduling in wireless sensor networks. Existing scheduling algorithm-s do not consider the transmission failure during aggregation, thus are not applicable insensor networks with non-ideal link qualities. This thesis proposes a two-phase mech-anism based on the idea of opportunistic routing in order to increase the delivery rate.The proposed mechanism can be applied in any of the existing scheduling algorithms,which is a complementary for existing work on aggregation scheduling. The mechanismaugments the original schedule by adding opportunistic links with good link qualities in the first phase. Two strategies of opportunistic link selection are proposed in this thesis.The mechanism executes aggregation according to the augmented schedule in the secondphase. A new aggregation execution algorithm is proposed to handle the transmissionby the augmented schedule. Simulation results show that the opportunistic aggregationscheduling mechanism significantly increases the delivery rate, and verify the energy ef-ficiency of the mechanism.