A New Measure of Wireless Network Connectivity

Despite intensive research in the area of network connectivity, there is an important category of problems that remain unsolved: how to characterize and measure the quality of connectivity of a wireless network which has a realistic number of nodes, not necessarily large enough to warrant the use of asymptotic analysis, and which has unreliable connections, reflecting the inherent unreliability of wireless communications? The quality of connectivity measures how easily and reliably a packet sent by a node can reach another node. It complements the use of capacity to measure the quality of a network in saturated traffic scenarios and provides an intuitive measure of the quality of (end-to-end) network connections. In this paper, we introduce a probabilistic connectivity matrix as a tool to measure the quality of network connectivity. Some interesting properties of the probabilistic connectivity matrix and their connections to the quality of connectivity are demonstrated. We demonstrate that the largest magnitude eigenvalue of the probabilistic connectivity matrix, which is positive, can serve as a good measure of the quality of network connectivity. We provide a flooding algorithm whereby the nodes repeatedly flood the network with packets, and by measuring just the number of packets a given node receives, the node is able to asymptotically estimate this largest eigenvalue.