Article Preview
TopIntroduction
Routing in wireless 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. 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
Similar to geographic location based protocols, many reactive routing protocols for ad-hoc and sensor networks, such as Dynamic Source Routing (Johnson & Maltz, 1996) and Ad Hoc On Demand Vector Routing (Perkins, Belding-Rower, & Das, 2003), assume that all links in a network are symmetric and, therefore, they can fail to find routes when this assumption does not hold true. These routing protocols often rely on a two-phase communication process, where the same path is used to communicate between the sender and the receiver. If a single link on this path is asymmetric, the route establishment will fail. Even if route discovery succeeds, protocols that avoid or ignore asymmetric links in their route establishment will often discover routes that are longer than necessary, thereby affecting the end-to-end communication latencies experienced between sender and receiver.