Year

2012

Degree Name

Master of Philosophy

Department

School of Electrical, Computer and Telecommunications Engineering

Abstract

Wireless Sensor Networks (WSNs) are comprised of autonomous, self-organized sensors that collaborate to monitor surrounding conditions, such as temper- ature, motion, sound and vibration. The data collected by sensors are then forwarded to a base station or sink via multiple hops. A key challenge in WSNs is that sensor nodes are constrained by their physical size and battery capacity. As a result, they have limited energy, storage, processing speed, radio frequency (RF) bandwidth and transmission range. Consequently, the finite energy prob- lem has attracted the attention of a number of researchers given that it directly determines the lifetime, and hence, usability of a WSN.

In recent years, researchers have proposed to use energy harvesting technology to address the energy capacity constraint of sensor nodes. More specifically, sensor nodes are equipped with devices that are able to harvest energy from the ambient environment or human motion, and thereby, have the potential to operate perpetually. However, the energy-harvesting rate is time varying, and may not be sufficient to guarantee the required operating duty cycle. Hence, in order to ensure continuous operation, sensor nodes are required to maintain a low duty cycle.

In a WSN, each node operates in accordance to a given duty cycle and may wake and sleep synchronously or asynchronously. In this thesis, we assume nodes op- erate using an asynchronous duty cycle due to its simplicity and low signaling overheads as nodes are not required to be synchronized globally. However, low asynchronous duty cycle results in high sleep latency, which is the major contributor to end-to-end delays in WSNs. This is because the node with pack- ets to send has to wait until the next-hop neighbor wakes up. As a result, nodes experience varying end-to-end delays from the sink. Unfortunate,y this causes problems for applications such as software updates, which require a pre- determined delay bound. Thus, there is a need to reduce the sleep latency of some nodes to ensure the path from the sink falls below a given bound. How- ever, any developed solutions must also consider the available energy of each sensor node. That is, a solution must not unnecessarily increase the duty cycle of nodes as doing so consumes precious harvested energy.

In this thesis, the problem at hand is first formulated as a Binary Integer Pro- gram (BIP), which is then solved by the CPLEX Interactive Optimizer. Given that the problem is NP-hard, this thesis proposes and studies four centralized heuristic algorithms: Tabu, Domino, Edge and Reverse. In addition, it includes analysis on the correctness of Domino, Edge and Reverse; further, the time complexity of Tabu, Domino, Edge and Reverse is Ο (α x n2 x |Qi|),Ο(n + 2 x |U| x |P| + |U| x |P|2),Ο(n x |P|) and Ο(|Qi| x n2) respectively, where n is the number of nodes, |P| is the number of nodes in a given path, |U| is the number of paths with delay that exceeds the given bound, |Qi| is the number of slots in one period, and α is the number of iterations of the Tabu algorithm.

To evaluate the aforementioned algorithms, two sets of experiments are con- ducted. The first set compares BIP, Tabu, Domino, Edge and Reverse in networks with fewer than 80 nodes. These first set of experiments serve to compare the proposed algorithms against the optimal solution, which can only be obtained for small to moderate sized networks. Our the results show that, compared to BIP, the number of additional wake-up times generated by the centralized algorithms is 5%, 10%, 35% and 60% greater than BIP respectively. The second set evaluates the performance of Tabu, Domino, Edge and Reverse in networks with nodes ranging from 100 to 500 nodes. In these experiments, the following metrics are collected: number of nodes, degree, duty cycle and delay bound. The results show that for each algorithm, as the number of nodes increases, the number of extra slots required goes up as well. On the other hand, an increase in degree, duty cycle and delay bound will result in a decrease in the number of extra slots. Further, in experiments with more than 80 nodes, the average number of extra active slots activated by Domino, Edge and Reverse is within 13%, 110% and 375% greater than Tabu respectively.

Download

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.