Ph.D Thesis | |

Ph.D Student | Kapchits Boris |
---|---|

Subject | On the Optimization of Wake-Up Frequencies in Sensor Networks |

Department | Department of Computer Science |

Supervisor | PROF. Reuven Cohen |

Full Thesis text |

This work addresses the tradeoff between efficient energy consumption and latency for the two most important tasks performed in a sensor network: packet routing and neighbor discovery. For the first task, we present an algorithm for maximizing the lifetime of a sensor network while guaranteeing an upper bound on the end-to-end delay. We prove that the proposed algorithm is optimal, and that it requires simple computing operations that can be implemented by simple devices. To the best of our knowledge, this is the first work to propose a sensor wake-up frequency that depends on the sensor's location in the routing paths. Using simulations, we show that the proposed algorithm significantly increases the lifetime of the network, while guaranteeing a maximum on the end-to-end delay.

We then extend this study to address a network with multiple gateways. Here we consider two sub-problems: the problem of constructing efficient routing trees and the problem of wake-up frequency assignment in a network with multiple routing trees. For the first problem we present an optimal algorithm and an approximation algorithm that achieves very close performance but can be more easily implemented. We prove that the second problem is NP-hard and propose a polynomial time approximation algorithm.

For the task of neighbor discovery,
we define a new concept, called ``ongoing neighbor discovery''. Although in
most sensor networks the nodes are static, the node connectivity is subject to
changes because of disruptions in wireless connectivity, transmission power
changes, or loss of synchronization between neighboring nodes. Hence, even after
a sensor is aware of its immediate neighbors, it must continuously maintain its
view, a process we call *continuous neighbor discovery*. In this work we
distinguish between neighbor discovery during sensor network initialization and
continuous neighbor discovery and focus on the latter task. We view continuous
neighbor discovery as a joint task of all the connected sensors. Each sensor
employs a simple protocol in a coordinate effort to reduce power consumption without
increasing the time required to detect hidden sensors.