The Heuristics

The first heuristic that we consider is used in [4,5]. It assumes that all links on a multi-hop wireless path interfere with each other. In a connected network, we can always construct a path that includes a given pair of links. In short, this heuristic assumes that any two links in the network interfere with each other. This is clearly a pessimistic model. The second heuristic [12] assumes that two links in the network interfere only if they share an endpoint. This is an optimistic heuristic. It is commonly known as the point interference model.

We do not expect either of these two heuristics to work well in our testbed. We include these in our study because they represent the two extreme ends of the approximations that have been used in the literature. Our measurements indeed show that these heuristics perform poorly.

The third heuristic [18,8] is more sophisticated. Consider two links $L_{AB}$ and $L_{CD}$. Let $d_{AB}$ be the distance between nodes $A$ and $B$. Similarly define $d_{CD}, d_{BC}$ and $d_{AD}$. The model says that $L_{AB}$ and $L_{CD}$ will interfere with each other if either $d_{BC} \leq K*d_{AB}$ or $d_{AD} \leq K*d_{CD}$. A commonly used value for $K$ is 2. Intuitively, the model says that if a node is receiving a transmission, a second transmitter can interfere with that reception only if it is sufficiently close. This model is generally paraphrased as interference range is twice the communication distance.

We term these three heuristics as $M1$, $M2$ and $M3$, respectively. These heuristics are ``binary''models, since they only predict whether a given pair links interfere with each other or not. They do not predict the actual $LIR$.

To see how these three models perform in our testbed, we compare their predictions for several pairs of links against experimentally measured $LIR$. The first step in this process is to select a set of links in the testbed to experiment with.