Introduction

Multi-hop wireless networks have been a subject of much study. Most of the original work in this area was motivated by scenarios in which the nodes were highly mobile. Recently, interesting commercial applications of static multi-hop wireless networks have emerged. One example of such applications is ``community wireless networks'' [2,11]. Several companies [14,9] are field-testing wireless ``mesh'' networks to provide broadband Internet access.

Interference among wireless links significantly impacts the performance of static multi-hop wireless networks. Several researchers have studied this issue. The impact of interference on the capacity of wireless networks is studied in [8,10,12], while the impact on the performance of transport-level protocols is considered in [7,13,6]. The need for routing protocols to take link interference into account has been underscored in [4,5]. Information about link interference is also needed for optimal channel assignment [16].

Many of these studies build upon the knowledge of which links in the network interfere with each other. Yet, the problem of estimating the interference among links in a multi-hop wireless network has not been adequately addressed.

The problem of estimating link interference can be described informally as follows: given a set of wireless links, estimate whether (and by how much) their aggerate throughput will decrease when the links are all active simultaneously, compared to when they are active individually.

This is a challenging problem for several reasons. Accurate modeling of radio signal propagation is difficult since many environment and hardware-specific factors must be considered. Empirically testing every group of links for interference is not practical: a network with $n$ nodes can have $O(n^2)$ links, and even if we consider only pairwise interference, we may potentially have to test $O(n^4)$ pairs. The interference pattern could change due to environmental factors, so interference estimation is not a one-time task. Hence, it is important to do it efficiently.

Given these difficulties, some researchers simply assume that the information about which links in the network interfere with each other is known apriori [10]. Others assume that it can be approximated by using simple heuristics. One common heuristic states that the interference range equals a small multiple (typically, a factor of 2) of the communication distance [18,8].

In this paper, we study the phenomenon of interference among links in a 22-node IEEE 802.11 a/b/g based indoor wireless testbed. The paper makes two contributions. First, we show that the simple heuristics described in the previous literature fail to accurately predict the interference among links in our testbed. Second, we propose a simple, empirical estimation methodology to predict pairwise interference that requires only $O(n^2)$ measurement experiments. We show that the predictions made by our methodology match well with the observed pairwise interference among links in our testbed under a variety of conditions. Our methodology is useful for any wireless network where nodes use omni-directional antennas. We focus on omni-directional antennas since these are cheap and easy to deploy, and hence popular. Network architectures based on omni-directional antennas are quite common [17].

Paper outline: First, we formalize the notion of pairwise interference among wireless links. Next, we present a brief description of our testbed. We show that the simple heuristics used in previous work do not accurately model the interference in our testbed network. We next present our empirical methodology, and show that it accurately predicts pairwise link interference in our testbed. Finally, we summarize related work and present our conclusions.