Multi-Hop Wireless Routing

In continuation of the multi-hop wireless discussion from previous posts, I'm discussing some salient points from two papers, A High-Throughput Path Metric for Multi-Hop Wireless Routing [ETX] and A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols [COMPARE].

Again, the motivation for researching routing policies for multi-hop wireless networks should be clear ... the problem changes drastically when you move away from the typical access point wireless communication (wireless communication is not more than one hop).   

The authors of [COMPARE] evaluated four different routing protocols based on three metrics: packet delivery ratio, routing overhead, and path optimality. Packet delivery ratio is exactly like what it sounds like and comparable to link loss ratios in [ETX] (which will be discussed shortly). Routing overhead is exactly what it sounds like as well. Path optimality is an interesting metric because it, as of this paper: "in the absence of congestion or other 'noise', path optimality measures the ability of the routing protocol to efficiently use network resources by selecting the shortest path from a source to a destination".

Before I divulge on the results of [COMPARE] I feel it is a fair time to motivate [ETX], whose premise was exactly: the most efficient paths through multi-hop networks may not always be the shortest ... i.e. shortest path is a bad metric for path optimality. The authors of [ETX] provide examples of such scenarios, but the crux of the problem comes down to the fact that not all wireless links are high-throughput and lossless. Rather, they again reinforce an important point: a single hop that delivers only 50% of packets might be less useful as two hops that each deliver 100% of packets.

In [COMPARE] the authors allude to the possible problems of shortest path optimality as "congestion or other 'noise'". It turns out, as was shown in [ETX], that there is a lot of lossy links ... a.k.a. links that suffer from a lot of 'noise' (interference, etc). In addition, many of these links are asymmetric. That is, sending packets one direction has a higher delivery ratio than the other direction. This is clearly an issue with respect to most wireless protocols because while data may only be sent in one direction, an ACK must be sent in the other direction. Ultimately the authors of [ETX] designed a new protocol called ETX (Expected Transmission Count) that is based on delivery ratios, asymmetry in the delivery ratios, and interference over longer routes.

A few more thoughts:

• The authors of [COMPARE] claim that wireless networks have a fundamental limitation to wired networks for sending broadcast packets due to the fact that there is no medium to reserve for all "nodes in proximity". Two thoughts here: (1) it seems like you could augment the RTS/CTS scheme to allow for a node to broadcast a message to all nodes that can hear the RTS/CTS; (2) the multi-hop wireless protocols of Roofnet don't use RTS/CTS either.
• The authors of [COMPARE] focused their studies on mobility and movement (which naturally changed the network topology) while the authors of [ETX] have a more subtle assumption that the wireless nodes are stationary (they at least assume this in Roofnet).
• DSR (dynamic source routing) seemed to be the best candidate for environments like those simulated in the [COMPARE] paper (highly mobile).