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

Network Protocols and Algorithms

Philip Mumford²  Natarajan Meghanathan¹ 

[1] Jackson State University;Air Force Research Lab/RYWC

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

DOI  :  10.5296/npa.v5i4.4208

学科分类：计算机应用

来源: Macrothink Institute, Inc.

【 摘 要 】

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.

【 授权许可】

Unknown