Title :
A Benchmarking Algorithm to Determine Maximum Stability Data Gathering Trees for Wireless Mobile Sensor Networks
Author :
Meghanathan, Natarajan ; Mumford, Philip D.
Author_Institution :
Dept. of Comput. Sci., Jackson State Univ., Jackson, MS, USA
Abstract :
The high-level contribution of this paper is the design of a benchmarking algorithm to determine a sequence of the longest-living stable data gathering trees for wireless mobile sensor networks (MSNs) such that the number of tree discoveries is the theoretical global minimum. Referred to as the Max. Stability-DG algorithm, the algorithm assumes the availability of the complete knowledge of future topology changes, and operates according to a greedy strategy: Whenever a new data gathering tree is needed at time instant t, determine a spanning tree that will exist for the longest time since t and derive a data gathering tree by conducting a Breadth First Search on the spanning tree. We prove the correctness of the Max. Stability-DG algorithm that it indeed determines the sequence of longest living stable data gathering trees. Since the Max. Stability-DG trees are based on spanning trees covering the entire network of live sensor nodes, the average lifetime and the number of tree discoveries incurred for the Max. Stability-DG trees will serve respectively as the upper bound and lower bound for any network-wide communication topology determined using any other algorithm for mobile sensor networks.
Keywords :
mobile radio; telecommunication network topology; tree searching; trees (mathematics); wireless sensor networks; MSN; Max.Stability-DG algorithm; benchmarking algorithm; breadth first search; greedy strategy; longest-living stable data gathering tree; maximum stability data gathering tree; network-wide communication topology; sensor node; spanning tree; wireless mobile sensor network; Algorithm design and analysis; Complexity theory; Mobile communication; Mobile computing; Monitoring; Network topology; Topology; Algorithms; Data Gathering Trees; Maximum Stability; Mobile Sensor Networks; Simulations; Tree Lifetime;
Conference_Titel :
Information Technology: New Generations (ITNG), 2013 Tenth International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-0-7695-4967-5
DOI :
10.1109/ITNG.2013.83