Estimation of Link Interference in Static Multi-hop Wireless Networks


Jitendra Padhye$^\dag$, Sharad Agarwal$^\dag$, Venkata N. Padmanabhan$^\dag$, Lili Qiu$^\ddag$, Ananth Rao$^\S$, Brian Zill$^\dag$


$^\dag$Microsoft Research $^\ddag$University of Texas, Austin $^\S$University of California, Berkeley

We present a measurement-based study of interference among links in a static, IEEE 802.11, multi-hop wireless network. Interference is a key cause of performance degradation in such networks. To improve, or to even estimate the performance of these networks, one must have some knowledge of which links in the network interfere with one another, and to what extent. However, the problem of estimating the interference among links of a multi-hop wireless network is a challenging one. Accurate modeling of radio signal propagation is difficult since many environment and hardware-specific factors must be considered. Empirically testing every group of links is not practical: a network with $n$ nodes can have $O(n^2)$ links, and even if we consider only pairwise interference, we may have to potentially test $O(n^4)$ pairs. Given these difficulties, much of the previous work on wireless networks has assumed that information about interference in the network is either known, or that it can be approximated using simple heuristics. We test these heuristics in our testbed and find them to be inaccurate. We then propose a simple, empirical estimation methodology that can predict pairwise interference using only $O(n^2)$ measurements. Our methodology is applicable to any wireless network that uses omni-directional antennas. The predictions made by our methodology match well with the observed pairwise interference among links in our 22 node, 802.11-based testbed.