A High-Throughput Path Metric for Multi-Hop Wireless Routing

This paper describes and evaluates the routing metric that was ultimately used in RoofNet based on an office environment deployment. The metric assumes hop-by-hop acknowledgments and retransmissions for unicast traffic. For each hop, the expected number of transmissions required to successfully send a packet along that hop is computed based upon the success rate of broadcasted probes (assumed to not use retransmission) in both directions. The authors believe that this metric will tend to find higher bandwidth paths better than merely counting hops and lower the overall load on the network. The authors recognize that their scheme assumes that variable transmission power would not be very advantageous (which seems strange given that their radios can definitely vary their power). Their scheme also seems specialized for their (common in wireless networks of this sort) half-duplex environment where a forwarded transmission interferes with the original sender so ‘pipelining’ is not possible.

The authors evaluated their deployment with a 802.11b network deployed in offices in their lab. They measured the hop-by-hop loss rates and computing a baseline ‘best’ set of route throughputs (assuming that their model of interference along a multi-hop route based on loss rates was accurate). They compared these throughputs to actual throughputs obtained using (modified to avoid instabilities) DSDV and DSR with both the standard hop-count metric and with transmission count metric.

Not surprisingly, the authors observed improved performance with their metric. They identified some non-obvious sources of the improvement which could be used independently by DSDV and DSR: avoiding asymmetric routes (which can be done by ‘handshaking’ before considering a link usable) and usually avoiding routes that experience transmission errors (which DSR does when given link-layer feedback).

The authors also evaluated the accuracy of their link quality measurements. They found that significant bias was introduced by the packet sizes of their probes — larger packets were received significantly less often than smaller ones, but their metric assumed all packets were equal.