Recent experimental research has revealed that the link conditions in realistic wireless networks vary significantly from the ideal disk model, and a substantial percentage of links are asymmetric. Many existing geographic routing protocols fail to consider asymmetric links during neighbor discovery and thus discount a significant number of potentially stable routes with good one-way reliability. This chapter provides a detailed overview of a number of location-aware routing protocols that explicitly use asymmetric links in routing to obtain efficient and shorter (low latency) routes. An asymmetric link routing protocol, called Asymmetric Geographic Forwarding (A-GF) is discussed in detail. A-GF discovers asymmetric links in the network, evaluates them for stability (e.g., based on mobility), and uses them to improve the routing efficiency.
TopIntroduction
Routing in mobile ad-hoc and sensor networks typically assumes that wireless links are bidirectional, i.e., wireless devices have identical transmission ranges. However, some recent empirical studies (Ganesan, Estrin, Woo, Culler, Krishnamachari & Wicker, 2002; Woo, Tong & Culler, 2003; Zamalloa & Krishnamachari, 2007; Zhao & Govidan, 2003) show that approximately 5-15% of the links in a low-power wireless network are asymmetric, and an increasing distance between nodes also increases the likelihood of an asymmetric link. This trend is further exacerbated by the increasing use of power management techniques that may cause the nodes in a network to operate at different transmission ranges. Link asymmetry is also caused by node mobility, heterogeneous radio technologies, and irregularities in radio ranges and path and packet loss patterns. Based on these observations, it is expected that link asymmetry will become more common in future wireless ad-hoc and sensor networks.
With increasing use of Global Positioning System (GPS) and many other (possibly less accurate but more resource-efficient) localization schemes, Geographic Forwarding (GF) is becoming an attractive choice for widely scalable routing in wireless ad-hoc and sensor networks. GF incurs very low overhead since no prior route discovery is required before forwarding the data packets. Many existing GF protocols are designed under the assumption of symmetric wireless links. That is, whenever a node receives a beacon packet from another node, it considers that node as its neighbor as it assumes the link is bi-directionally reachable. Such an assumption may not be realistic for practical wireless ad-hoc and sensor networks, since wireless links are often asymmetric. In Figure 1, node A discovers its neighbors B, C, and D by receiving beacons from them, which means that node A is within the wireless transmission ranges of all three nodes. Both node C and node D are also within the wireless transmission range of node A, so both the links A↔C and A↔D are symmetric. However, node B is outside node A's wireless transmission range and therefore, there is an asymmetric link B→A between these two nodes. Note that while all wireless links are to some extent asymmetric (i.e., the signal strength being stronger in one direction than the other but the wireless link still being connected in both directions), A-GF focuses on maximally asymmetric links (perfect connectivity one direction, zero in the other), as shown in Figure 1.
Figure 1. Concept of asymmetric links
Some geographic routing protocols (Couto, Aguayo, Bicket & Morris, 2003; Zhou, He, Krishnamurthy & Stankovic, 2004) detect asymmetric links and explicitly ignore them while making routing decisions. Eliminating asymmetric links discounts a substantial number of potentially stable routes with good one-way reliability and may lead to (1) routes that are longer than necessary and (2) no routes at all if there is not at least one fully symmetric path between the sender and receiver (Marina & Das, 2002; Sang, Arora & Zhang, 2007). Therefore, it is difficult to achieve high network connectivity, high data transmission rates, and low transmission latencies if the network has many asymmetric links. Furthermore, some recent empirical studies (Chen, Hao, Zhang, Chan & Ananda, 2009; Ganesan, Estrin, Woo, Culler, Krishnamachari & Wicker, 2002) show that asymmetric links tend to span longer distances than symmetric links. As a result, inclusion of asymmetric links in routing decisions can further improve the network performance. On the other hand, in a highly mobile setting, communications among mobile nodes may only be temporary and short-lived. For example, while the wireless connection between two cars driving in the same direction on a highway may last for a long time, the connection between cars driving in opposite directions will break very quickly. Therefore, it may be necessary to not only identify the presence of an asymmetric link, but to also measure or predict the time-varying quality or stability of such a link.