A Computationally Efficient Connectivity Measure for Random Graphs

PDF

Authors
  1. Mahboubi, H.
  2. Asadi, M.M.
  3. Aghdam, A.G.
  4. Blouin, S.
Corporate Authors
Defence Research and Development Canada, Atlantic Research Centre, Halifax NS (CAN)
Abstract
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.
Keywords
acoustic propagation;network connectivity;connectivity measure
Report Number
DRDC-RDDC-2016-P113 — External Literature
Date of publication
22 Nov 2016
Number of Pages
6
DSTKIM No
CA043342
CANDIS No
804651
Format(s):
Electronic Document(PDF)

Permanent link

Document 1 of 1

Date modified: