Energy Efficient Algorithms in Low-Energy Wireless Sensor Networks

Wireless sensor networks consist of small autonomous processors spatially distributed, typically with the goal of gathering physical data about the environment such as temperature, air pressure, and sound.

Sensor networks have a wide range of applications including military, health care monitoring, and environmental sensing.

Because sensors are typically battery powered, algorithms for sensor network models should not only seek to minimize runtime but also energy usage.

In extremely dense networks it may be inefficient for sensors to communicate with all neighboring sensors on a consistent basis, especially in mobile wireless sensor networks where the topology of the network is constantly changing.

Sensors conserve energy by going into a low-energy sleep state and for our algorithms sensors will be asleep for the vast majority of the total runtime.

Algorithms under these conditions face additional challenges because of the increased difficulty of coordinating between sensors.

Because of the spatial nature of sensor networks geometry problems are often of particular interest.

For example, to detect outliers data is often compared with the nearest neighboring sensors.

My work primarily is primarily in distributed algorithmic techniques that maximize network longevity. To overcome challenges coordinating divide and conquer algorithms in a single-hop setting I introduce breadth first recursion and use this technique to provide algorithms for sorting and the convex hull.

I then introduce a consolidation algorithms as a method using single-hop algorithms as building blocks for multi-hop algorithms. This technique is useful for computing all points k-nearest neighbors, the coverage boundary, and the Voronoi diagram.

I also analyze the problem of propagating data to a high energy base station. I provide analytical and empirical results which motivate the use of distributed algorithms on wireless sensor networks.