A Computationally Efficient Connectivity Measure for Random Graphs

This paper investigates the global-connectivity assessment of a sensor network subject to random communications. The investigation exploits the corresponding expected communication graph and its associated weighted vertex connectivity (WVC). Computing the WVC measure for such networks is an NP-hard problem. This situation led to the development of an approximate WVC (AWVC) measure, which has its own shortcomings. This paper introduces an improved approximate weighted vertex connectivity (IAWVC) measure with a polynomial- time implementation. The new connectivity measure does not have the shortcomings of the AWVC measure and, under some conditions, matches the WVC measure. Simulation results show the efficiency of the IAWVC computation and its effectiveness in approximating the WVC measure.