Title: Maximum stability data gathering trees for mobile sensor networks

Authors: Natarajan Meghanathan; Philip D. Mumford

Addresses: Jackson State University, Mailbox 18839, 1400 John R. Lynch Street, Jackson, Mississippi, MS 39217, USA ' Sensors Directorate, Air Force Research Lab/RYW, Wright-Patterson Air Force Base, 2241 Avionics Circle, Dayton, Ohio, OH 45433, USA

Abstract: We describe a benchmarking algorithm (Max.Stability-DG algorithm) to determine the sequence of data gathering trees for maximum stability in mobile sensor networks such that the number of tree discoveries is the theoretical global minimum. The Max.Stability-DG algorithm assumes the availability of the complete knowledge of future topology changes and works based on a simple greedy principle: whenever a new data gathering tree is required at time instant t, we determine a spanning tree that exists for the longest time since t, transform the spanning tree to a rooted data gathering tree and use it until it exists. The whole procedure is repeated until the end of the session to obtain a sequence of longest-living stable data gathering trees. We prove the correctness of the Max.Stability-DG algorithm and also evaluate the performance of the Max.Stability-DG trees (compared to minimum-distance spanning tree-based data gathering trees) through extensive simulations under diverse operating conditions.

Keywords: maximum stability; data gathering trees; mobile sensor networks; tree lifetime; algorithms; simulation; mobile networks.

DOI: 10.1504/IJMNDI.2012.051972

International Journal of Mobile Network Design and Innovation, 2012 Vol.4 No.3, pp.164 - 178

Published online: 25 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article