Centralized and Distributed Algorithms for Stability-based Data Gathering in Mobile Sensor Networks

Due to the dynamic nature of the network topology in a mobile sensor network, a data gathering tree is likely to frequently break, necessitating the need for stable data gathering trees that can withstand node mobility for a reasonable amount of time. In this pursuit, we propose two algorithms: (1) a centralized algorithm that can return the sequence of longest-living stable data gathering trees such that the number of tree transitions (changes) is the global minimum; (2) a distributed algorithm that is based on the idea of finding a maximum spanning tree on a network graph whose edge weights are the predicted link expiration times (LET). While the centralized maximum stability-based data gathering (MAXS-DG) algorithm can be used to derive benchmarks for the optimal number of tree transitions (and thence the sequence of longest living stable data gathering trees) over the duration of a data gathering session, the distributed LET-based DG algorithm can be run across the sensor nodes in a network to find stable data gathering trees that have a longer lifetime bounded above by the MAXS-DG trees. In the simulations, we evaluate the tree lifetime, delay per round, node and network lifetime incurred with the MAXS-DG and LET-DG trees and observe a stability-delay tradeoff.