Ph.D Thesis

Ph.D StudentKapchits Boris
SubjectOn the Optimization of Wake-Up Frequencies in Sensor
DepartmentDepartment of Computer Science
Supervisor PROF. Reuven Cohen
Full Thesis textFull thesis text - English Version


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.