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

Natarajan Meghanathan, Philip Mumford

Abstract


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.


Keywords


Stability; Data Gathering Tree; Tree Lifetime; Link Expiration Time; Minimum Distance Spanning Trees; Simulations; Mobile Sensor Networks

Full Text:

PDF


DOI: http://dx.doi.org/10.5296/npa.v5i4.4208

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

To make sure that you can receive messages from us, please add the 'macrothink.org' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.

Copyright © Macrothink Institute ISSN 1943-3581