Edge Centrality Metrics to Quantify the Stability of Links for Mobile Sensor Networks

1. Introduction

Mobile sensor networks (MSNs) are a category of wireless sensor networks in which the sensor nodes could move independent of each other. The topology of MSNs changes dynamically with time and hence the communication topologies (like data gathering trees; Meghanathan, 2012) determined for such networks need to be frequently reconfigured. Not much work has been done so far to determine stable communication topologies for MSNs. To determine stable communication topologies in MSNs, it is imperative to quantify the stability of the links. The currently best known approach (Meghanathan, 2014) to quantify link stability has been borrowed from a related field called mobile ad hoc networks (MANETs; Abolhasan et al., 2004) and it is based on the notion of predicted link expiration time (LET, originally proposed by Su & Gerla, 1999 for MANETs). However, to predict the LET of a link, we need to know the location and mobility information of the end vertices of the link and in the case of MSNs, it would be too energy-draining for the sensor nodes to regularly detect their location and mobility information as well as to update their neighbors about the same.

The motivation for the research presented in this chapter is to investigate the use of graph theoretic measures (that would not require the location and mobility information of the nodes) borrowed from complex network analysis to quantify the stability of links in a MSN. In this pursuit, our hypothesis is that links whose end vertices are relatively closer to each other (i.e., have a significant fraction of their neighborhood shared) are more likely to be stable and vice-versa. We could thence use graph theoretic measures that could be used to quantify the extent of shared neighborhood between the end vertices of the edges and use the same as the link stability score (LSS): a measure of the edge weights for the algorithms to determine stable communication topologies. We restrict ourselves to data gathering trees (DG trees) as the communication topology of interest; however, the LSS scores determined based on the graph theoretic measures are independent of the communication topology.

The graph theoretic measures (as measures of edge centrality) used to quantify the extent of shared neighborhood of the end vertices of a link are: Neighborhood Overlap (NOVER)(Easley & Kleinberg, 2010), Bipartivity Index (BPI)(Estrada & Rodriguez-Velazquez, 2005) and Algebraic Connectivity (ALGC)(Fiedler, 1973). All these metrics have been so far used for complex network analysis involving social networks, biological networks, etc and have not been used for mobile sensor networks. Also, BPI and ALGC have been so far used only at the network level and not at the edge level (while NOVER, an edge level metric, has been primarily used for community detection). We capture the neighborhood of the end vertices of an edge u-v in the form of an egocentric network comprising of the end vertices and their neighbors (as nodes) and the links incident on the end vertices (as edges). We determine the NOVER, BPI and ALGC scores based on the egocentric edge networks. Simulation studies involving data gathering algorithms indicate edges with larger NOVER and ALGC scores as well as lower BPI scores are observed to be more stable. Hence, we assign the LSS score for an edge u-v to be as follows: (i) the NOVER score for the edge u-v, (ii) the complement of the BPI, BPI' = 1-BPI, of the egocentric network of the edge u-v, and (iii) the ALGC score for the egocentric network of the edge u-v.