Link selection strategies based on network analysis to determine stable and energy-efficient data gathering trees for mobile sensor networks

We propose three different strategies for selecting links that could be part of stable data gathering (DG) trees for mobile sensor networks (MSNs). The proposed strategies are based on metrics (such as: Neighborhood Overlap, Bipartivity Index and Algebraic Connectivity) used in complex network analysis applied on the egocentric network of an edge: a graph comprising of the end nodes of the edge and their neighbors (as vertices) and links incident on the end nodes of the edge (as edges). We hypothesize that an edge whose egocentric network has a larger neighborhood overlap or a smaller bipartivity index or a larger value for algebraic connectivity should have its end nodes share a significant fraction of their neighbors and be a short distance link that is relatively more stable. Through extensive simulations, we show that each of the above three metrics of complex network analysis could be used to determine DG trees that are significantly more stable and energy-efficient compared to the currently best known strategy of using the predicted link expiration time (LET) to determine stable DG trees for MSNs. Also, unlike the LET approach, the proposed strategies could be applied without knowledge about the location and mobility of the nodes.