Complex Network Analysis-Based Graph Theoretic Metrics to Determine Stable Data Gathering Trees for Mobile Sensor Networks

摘要

The predicted link expiration time (LET)-based approach is currently the only promising approach to determine stable data gathering (DG) trees for mobile sensor networks, and the use of this approach requires the sensor nodes to be location and mobility aware (which is energy-draining on the nodes). The objective of this paper is to investigate the use of location and mobility-independent graph theoretic metrics (such as Neighborhood Overlap: NOVER, Bipartivity Index: BPI and Algebraic Connectivity: ALGC) that could be locally computed by each sensor node on the egocentric network of an edge to quantify the stability of the links. The egocentric network of an edge comprises 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 NOVER or a smaller BPI or a larger ALGC score should have its end nodes share a significant fraction of their neighbors and be a short distance link that is relatively more stable. Simulation results indicate that the DG trees determined based on the graph theoretic metrics are significantly more stable and energy-efficient compared to that of the LET-based DG trees.