Algorithms for local sensor synchronization

In a wireless sensor network (WSN), each sensor monitors environmental parameters, and reports its readings to a base station, possibly through other nodes. A sensor works in cycles, in each of which it stays active for a fixed duration, and then sleeps until the next cycle. The frequency of such cycles determines the portion of time that a sensor is active, and is the dominant factor on its battery life. The majority of existing work assumes globally synchronized WSN where all sensors have the same frequency. This leads to waste of battery power for applications that entail different accuracy of measurements, or environments where sensor readings have large variability. To overcome this problem, we propose LS, a query processing framework for locally synchronized WSN. We consider that each sensor n_i has a distinct sampling frequency f_i, which is determined by the application or environment requirements. The complication of LS is that n_i has to wake up with a network frequency F_if_i, in order to forward messages of other sensors. Our goal is to minimize the sum of F_i without delaying packet transmissions. Specifically, given a routing tree, we first present a dynamic programming algorithm that computes the optimal network frequency of each sensor; then, we develop a heuristic for finding the best tree topology, if this is not fixed in advance.