Asymmetric Geographic Forwarding: Exploiting Link Asymmetry in Location Aware Routing

Asymmetric Geographic Forwarding: Exploiting Link Asymmetry in Location Aware Routing

Pramita Mitra (University of Notre Dame, USA) and Christian Poellabauer (University of Notre Dame, USA)
DOI: 10.4018/jertcs.2011100104
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Geographic Forwarding (GF) algorithms typically employ a neighbor discovery method to maintain a neighborhood table that works well only if all wireless links are symmetric. 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. Existing GF algorithms fail to consider asymmetric links in neighbor discovery and thus discount a significant number of potentially stable routes with good one-way reliability. This paper introduces Asymmetric Geographic Forwarding (A-GF), which discovers asymmetric links in the network, evaluates them for stability (e.g., based on mobility), and uses them to obtain more efficient and shorter routes. A-GF also successfully identifies transient asymmetric links and ignores them to further improve the routing efficiency. Comparisons of A-GF to the original GF algorithm and another related symmetric routing algorithm indicate a decrease in hop count (and therefore latency) and an increase in successful route establishments, with only a small increase in overhead.
Article Preview

Introduction

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 2 Issues (2018): 1 Released, 1 Forthcoming
Volume 8: 2 Issues (2017)
Volume 7: 2 Issues (2016)
Volume 6: 2 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing