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

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

Natarajan Meghanathan, Philip Mumford
DOI: 10.4018/978-1-4666-5170-8.ch017
(Individual Chapters)
No Current Special Offers


The authors propose a graph intersection-based benchmarking algorithm to determine the sequence of longest-living stable data gathering trees for wireless mobile sensor networks whose topology changes dynamically with time due to the random movement of the sensor nodes. Referred to as the Maximum Stability-based Data Gathering (Max.Stable-DG) algorithm, the algorithm assumes the availability of complete knowledge of future topology changes and is based on the following greedy principle coupled with the idea of graph intersections: Whenever a new data gathering tree is required at time instant t corresponding to a round of data aggregation, choose the longest-living data gathering tree from time t. The above strategy is repeated for subsequent rounds over the lifetime of the sensor network to obtain the sequence of longest-living stable data gathering trees spanning all the live sensor nodes in the network such that the number of tree discoveries is the global minimum. In addition to theoretically proving the correctness of the Max.Stable-DG algorithm (that it yields the lower bound for the number of discoveries for any network-wide communication topology like spanning trees), the authors also conduct exhaustive simulations to evaluate the performance of the Max.Stable-DG trees and compare to that of the minimum-distance spanning tree-based data gathering trees with respect to metrics such as tree lifetime, delay per round, node lifetime and network lifetime, under both sufficient-energy and energy-constrained scenarios.
Chapter Preview


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(n2Tlogn) and O(n3Tlogn) when operated under sufficient-energy and energy-constrained scenarios respectively. The n2logn 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.

Key Terms in this Chapter

Mobile Sensor Network: A network of sensor nodes that move arbitrarily.

Algorithm: A sequence of steps to perform a particular task.

Data Gathering Tree: A communication topology that is used to aggregate data from all the sensor nodes towards a leader node that can further propagate the aggregated data to the sink.

Delay per Round: The number of timeslots incurred for the leader node to generate an aggregated data, collected from all the sensor nodes, propagated through the data gathering tree.

Network Lifetime: The time (number of rounds) of network disconnection due to the failure of one or more sensor nodes.

Node Lifetime: The time (number of rounds) of first node failure due to the exhaustion of battery charge at the sensor nodes.

Data aggregation: The process of combining data from multiple sensor nodes and generating a representative data of the same size as the data from the individual sensor nodes.

Round: During a round of data gathering, data gets aggregated starting from the leaf nodes of the tree and propagates all the way to the leader node. An intermediate node in the tree collects the aggregated data from its immediate child nodes and further aggregates with its own data before forwarding to its immediate parent node in the tree.

Tree Lifetime: The duration of existence of a data gathering tree.

Communication Topology: An arrangement of the nodes in the network that can be used to propagate data to the sink.

Stability: A characteristic of data gathering trees related to the duration of existence of the tree; the longer the duration of existence, the more stable is the data gathering tree.

Leader Node: The root node of the data gathering tree.

Complete Chapter List

Search this Book: