Graph Intersection-Based Benchmarking Algorithm for Maximum Stability Data Gathering Trees in Wireless Mobile Sensor Networks

Introduction

A wireless sensor network is a network of sensor nodes that gather data about the deployed environment, intelligently process them and forward to a central control center called the sink that is typically located far away from the monitored network field. Traditionally, wireless sensor networks are considered to gather data for static environments, where mobility in any form - sensor nodes, users and the monitored phenomenon are totally ignored. Recently, with the prolific growth of embedded systems and ubiquitous computing technologies, wireless mobile sensor networks (WMSN) have been envisioned and successfully deployed for varied applications such as traffic monitoring, route planning, civil infrastructure monitoring, geo-imaging, etc. (Hull et al., 2006). A WMSN could be either a homogeneous or heterogeneous network of nodes (a general term used to refer sensor-equipped computers, mobile phones and vehicles) equipped with sensing capabilities like a camera sensor, microphone, GPS sensor, etc (Kansal et al., 2007). By leveraging the mobility of the sensor nodes, a WMSN could be used to monitor and collect data over a relatively larger region as well as use fewer sensor nodes for a given region, compared to static sensor networks.

A WMSN has constraints (limited battery charge, memory, processing capability, bandwidth and transmission range) similar to that of the static sensor networks. Two nodes that are outside the transmission range of each other cannot communicate directly. Though energy constraints are attributed for the limited transmission range of the sensor nodes, transmissions over a longer distance are likely to suffer from interference and collisions. Due to all of the above resource and operating constraints, it would not be a viable solution to require every sensor node to directly transmit their data to the sink over a longer distance. This necessitates the need for developing energy-efficient data gathering algorithms to determine communication topologies that can be used to effectively combine data collected at these sensor nodes and send only the aggregated data (that is a representative of the entire network) to the sink.

A majority of the data gathering algorithms available in the literature are meant for static sensor networks (networks with sensor nodes staying fixed at a particular location) with either a static sink (Lindsey et al., 2002; Heinzelman et al., 2000) or mobile sink (Srinivasan & Wu, 2008; Vlajic & Stevanovic, 2009). Tree-based communication topologies for data gathering have been observed (Meghanathan, 2012) to be the most energy-efficient (in terms of the number of link transmissions) for static sensor networks. However, in the presence of dynamic node mobility (like in a WMSN), tree-based communication topologies could require frequent reconfigurations. Hence, mobility brings in an additional dimension of constraint to a WMSN: we need algorithms to determine stable data gathering trees that can exist for a longer time and do not require frequent reconfigurations.

In this research, we address the problem of developing a benchmarking algorithm to determine the sequence of stable data gathering trees for mobile sensor networks such that the number of tree reconfigurations is the global minimum. In this pursuit, we present the Max.Stable-DG algorithm that operates according to the following greedy principle: Given the complete knowledge of future topology changes, whenever a data gathering tree is required at time instant t, the algorithm chooses the longest-living data gathering tree from t. This strategy is repeated over the duration of the data gathering session, resulting in the generation of a sequence of longest-living data gathering trees (DG-trees) called the Stable-Mobile-DG-Tree. If n is the number of nodes in the network and T is the number of rounds of data gathering, the worst-case run-time complexity of the Max.Stable-DG algorithm is O(n²Tlogn) and O(n³Tlogn) when operated under sufficient-energy and energy-constrained scenarios respectively. The n²logn factor in the above run-time complexity is the worst-case run-time complexity of the minimum-weight spanning tree algorithm, Prim’s algorithm (Cormen et al., 2009) used to determine the underlying spanning trees from which the data gathering trees are derived.