Title: On pairwise connectivity of wireless multihop networks

Authors: Fangting Sun, Mark A. Shayman

Addresses: Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742, USA. ' Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742, USA

Abstract: This paper experimentally investigates the service availability of wireless multihop networks based on the following two metrics: Average Pairwise Connectivity (APC) and Pairwise Connected Ratio (PCR), where the former denotes the average number of node-disjoint paths per node pair and the latter is the fraction of node pairs that are pairwise connected. A theoretical upperbound are derived for APC, which can approximate the exact value very well. We also studied the fault tolerance and attack resilience and proposed a new resilience metric, α-ρ-resilience, where a network is α-ρ-resilient if at least a portion of nodes pairs remain connected as long as no more than p percentage nodes are removed. Three different node removal patterns are studied: random removal, selective removal and partition. The experimental studies show that wireless multihop networks are more sensitive to partition and selective removal attacks are a little bit more severe than random removal attacks.

Keywords: network connectivity; pairwise connectivity; fault tolerance; multihop wireless networks; random graph; security; service availability; removal attacks.

DOI: 10.1504/IJSN.2007.012823

International Journal of Security and Networks, 2007 Vol.2 No.1/2, pp.37 - 49

Published online: 16 Mar 2007 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article