Neighborhood Overlap-based Stable Data Gathering Trees for Mobile Sensor Networks

Neighborhood Overlap-based Stable Data Gathering Trees for Mobile Sensor Networks

Natarajan Meghanathan (Jackson State University, Flowood, MS, USA)
DOI: 10.4018/IJWNBT.2016010101
OnDemand PDF Download:
No Current Special Offers


The hypothesis in this research is that the end nodes of a short distance link (the distance between the end nodes is significantly smaller than the transmission range per node) in a mobile sensor network (MSN) are more likely to share a significant fraction of their neighbors and such links are more likely to be stable. The author proposes to use Neighborhood Overlap (NOVER), a graph-theoretic metric used in complex network analysis, to effectively quantify the extent of shared neighborhood between the end nodes of a link and thereby the stability of the link. The author's claim is that links with larger NOVER score are more likely to be stable and could be preferred for inclusion while determining stable data gathering trees for MSNs. Through extensive simulations, the author shows that the NOVER-based DG trees are significantly more stable and energy-efficient compared to the DG trees determined using the predicted link expiration time (LET). Unlike the LET approach (currently the best known strategy), the NOVER-based approach could be applied without knowledge about the location and mobility of the nodes.
Article Preview

1. Introduction

Mobile Sensor Networks (MSNs) are an emerging category of wireless sensor networks in which the sensor nodes are considered to move independent of each other. MSNs could be used for applications in which an entire region (that is being monitored) could be effectively covered by letting the sensor nodes to move rather than be static. For example (Hull et al., 2006), the pollutant concentration in an area (like the downtown of a city) could be effectively measured by fixing the sensor nodes in mobile vehicles (like cars) that move through the area. For most of the applications of wireless sensor networks (including those of the MSNs), the data recorded by the sensor nodes is forwarded to a control center (called the sink) through one of several network-wide communication topologies like chains (Lindsey et al., 2002), clusters (Heinzelman et al., 2000), trees (Meghanathan, 2012b), connected dominating sets (Meghanathan, 2010a), etc. Among these communication topologies, the data gathering trees (DG trees) have been observed to be energy-efficient (Meghanathan, 2012a) as they comprise of the minimum number of links needed to span all the sensor nodes and there are no redundant transmissions. In the case of DG trees, the leaf nodes merely sense the data and transmit them to an upstream intermediate node that would in turn aggregate its own data with data received from all of its child nodes and forward the aggregated data to an upstream node that is on the path to the root node of the DG tree. For the rest of the paper, the terms 'node' and 'vertex', 'link' and 'edge', 'network' and 'graph', 'data gathering' and 'data aggregation', 'construction' and 'configuration' mean the same. These terms are used interchangeably unless stated.

MSNs inherit all the constraints of their static counterpart (like energy and memory-constrained sensor nodes as well as limited network bandwidth); mobility of the nodes is an additional constraint that needs to be handled. Due to node mobility, the network topology changes dynamically with time and any communication topology (like DG trees) that is setup among the sensor nodes needs to be frequently reconfigured. Significant amount of energy might be lost if network-wide broadcasts are frequently initiated for reconfiguring the communication topology in use. This motivates the need to determine stable communication topologies that could exist for a longer time.

Meghanathan (2012b) took the first step towards using DG trees for MSNs and proposed a distributed algorithm for determining stable DG trees in MSNs using the concept of predicted link expiration time (LET; Su & Gerla, 1999) that has been earlier successfully used for mobile ad hoc networks (Meghanathan 2012c; Meghanathan 2014a). Meghanathan (2015a) proposed a generic algorithm to determine maximum bottleneck link weight (MaxBLW)-based DG trees for static sensor networks: the bottleneck link weight for a path from a node to the root node of the DG tree is the minimum of the weights of the constituent links on the path and the MaxBLW-DG algorithm determines a DG tree in which the path from any node to the root node of the tree is the path with maximum value for the bottleneck link weight. In this paper, we explain a distributed version of the MaxBLW-DG algorithm to determine NOVER-based DG trees wherein the link weight is the link stability score (LSS) computed based on this strategy. For performance comparison purposes, we use the distributed version of the MaxBLW-DG tree algorithm to also determine the LET-based DG trees (Meghanathan, 2012b) wherein the weight of a link is its predicted LET.

Complete Article List

Search this Journal:
Open Access Articles
Volume 10: 2 Issues (2021): Forthcoming, Available for Pre-Order
Volume 9: 2 Issues (2020)
Volume 8: 2 Issues (2019)
Volume 7: 2 Issues (2018)
Volume 6: 2 Issues (2017)
Volume 5: 1 Issue (2016)
Volume 4: 3 Issues (2015)
Volume 3: 4 Issues (2014)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing