Adaptive Online Estimation of Temporal Connectivity in Dynamic Wireless Networks

Most applications involving large-scale wireless networks need to know the connectivity of the network topology. Conventional approaches largely ignore the temporal aspects of node-to-node connectivity, and perform an offline analysis. In this paper, we characterize the temporal connectivity in a mobile wireless network, in a decentralized manner. We present Path Detect, a distributed algorithm that combines local broadcast with distributed consensus to achieve a spatial-temporal view of network connectivity. Additionally, the information gathered by Path Detect allows for the distributed computation of temporal efficiency, a metric that has until now only been computed centrally. Path Detect is adaptive, and can therefore track connectivity changes in real-time. We evaluate Path Detect under diverse test-cases featuring node and wireless link failures, and mobility patterns. Through these evaluations, we show that the comparison of Path Detect against the ground truth observation shows less than 10% relative error in estimation of temporal efficiency for most cases. Additionally, we also present our results of evaluating Path Detect on a real-wold network, showing that it is an attractive choice for real-world implementations.