Spatial Reusability-Aware Routing in Multi-Hop Wireless Networks

Abstract

Introduction

DUE to limited capacity of wireless communication media and lossy wireless links [30], it is extremely important to carefully select the route that can maximize the end-to-end throughput, especially in multi-hop wireless networks. In recent years, a large number of routing protocols ( etc.) have been proposed for multihop wireless networks. However, a fundamental problem with existing wireless routing protocols is that minimizing the overall number (or time) of transmissions to deliver a single packet from a source node to a destination node does not necessarily maximize the end-to-end throughput. A detailed example will be presented in Section 3.2 to show this observation. In this paper, we investigate two kinds of routing protocols, including single-path routing and anypath routing. The task of a single-path routing protocol is to select a cost minimizing path, along which the packets are delivered from the source node to the destination node. Recently, anypath routing (e.g., [2], [4]) appears as a novel routing technique exploiting the broadcast nature of wireless communication media to improve the end-to-end throughput. It aggregates the power of multiple relatively weak paths to
form a strong path, by welcoming any intermediate node who overhears the packet to participate in packet forwarding. Most of existing routing protocols, no matter singlepath routing protocols or anypath routing protocols, rely on link-quality aware routing metrics, such as link transmission count-based metrics (e.g., ETX [6] and EATX [32]) and link transmission time-based metrics (e.g., ETT [7] and EATT [13]). They simply select the (any)path that minimizes the overall transmission counts or transmission time for delivering a packet. However, an important property of the wireless communication media,which distinguishesit from traditional wired communication media, is the spatial reusability. Specifically, because wireless signals fade during propagation, two links are free of interference if they are far away enough, and thus can transmit at the same time on the same channel. To the best of our knowledge, most of the existingrouting protocols do not take spatial reusability of the wirelesscommunication mediainto account.Our examplein Section3.2willshow the improper usage of routing metrics by existing routing protocols, when spectrum spatial reusability is not considered. In thisprimerwork,wearguethatbycarefullyconsideringspatial reusability of the wireless communication media, we can tremendously improve the end-to-end throughput in multihop wireless networks (i.e., up to 5:3 throughput gain in single-path routing and up to 71:6 percent gain in anypath routingshownbyourevaluationresults). The detailed contributions of our work are as follows.

• To the best of our knowledge, we are the first to explicitly consider spatial reusability of the wireless communication media in routing, and design practical spatial reusability-aware single-path routing (SASR) and anypath routing (SAAR) protocols.
• We formulate the problem of spatial reusabilityaware single-path routing as a binary program, and propose two complementary categories of algorithms for path selection. While one category (SASR-MIN and SASR-FF) tends to exploit the best performance of the paths, the other category (SASR-MAX) evaluates the performance of the paths in the worst case.
• We further investigate the spectrum spatial reusability in anypath routing, and propose SAAR algorithm for participating node selection, cost calculation, and forwarding list determination.
• We have evaluated SASR algorithms and SAAR algorithm with different data rates in NS-2. The evaluation results show that our algorithms significantly improve the end-to-end throughput compared with existing ones. Specifically, for single-path routing, a throughput gain up to 5:3
  with a median of more than 60 percent is achieved in the case of single-flow, and an average gain of more than 20 percent is achieved with multiple flows; for anypath routing, a median gain of 13:2 percent and the maximum gain up to 71:6 percent can be realized. 

Related Work

In this Spatial Reusability-Aware Routing in Multi-Hop Wireless Networks section, we briefly review related works on metric design and protocol implementation. We also compare our work with those on joint routing problems, as well as other works considering reusability.

Routing Metrics There are a number of works on wireless routing metrics. For single-path routing, several link-quality aware metrics were proposed. RTT weighed the cost of single wireless link by the round trip delay of probe packets on it; ETX  assigned the link cost with its expected number of transmissions to successfully deliver a packet. Based on ETX, the authors designed ETOP metric considering links’ actual position on the path. In addition, incorporating the multi-rate ability, ETT took the expected transmission time of a link as its cost; and EMTT  extended the work to multicast. What’s more, provided some principles for routing metric design. There’re also metrics suitable for anypath routing. Chachulski et al. provided ETOXwhich considers opportunistic receptions at any forwarder.  the EATX metric was defined to reflect overall transmissions in any-path forwarding. Laufer et al. adopted EATX as the hyperlink cost, and defined the anypath cost composed of the hyperlink cost and the remaining cost. However, existing routing metrics tend to calculate path cost using some mechanism of lossless combination of link costs. For example, the ETX value of a path is the addition of each link’s ETX [6]. Similarly, Laufer calculated the anypath cost while considering all the forwarders’ costs . Besides, the guidelines , such as consistency, ignored the effect of reusability. Such lossless mechanism thus misses the opportunity of exploiting spectrum spatial reusability in wireless media.

Routing Protocols The earliest single-path routing protocols applied Dijkstra algorithm for route selection. When it comes to anypath routing, for example, ExOR appeared as a coordination mechanism between forwarders; MORE broke such coordination where all the forwarders worked according to their workload. Besides, MORE introduced network coding into anypath routing. On that basis, proposed the shortest anypath first (SAF) algorithm to determine the forwarders’ priorities, and proved its optimality; incorporated rate control and used a notion called credit to realize flow control; CodeOR  enabled concurrent transmissions of a window of segments; SOAR considered the problem of path divergence and rate limitation to efficiently support multiple flows; SourceSync  synchronized senders to achieve combined signals which lowers the packet error rate. Besides,  developed an optimization framework to exploit communication opportunities arising by chance; Hu et al.  proposed POR based on a per-packet feedback mechanism. Because the above routing protocols were designed based on existing transmission cost minimizing routing metrics, they cannot guarantee maximum end-to-end throughput when spatial reusability cannot be ignored. In addition, different from works  which should to some degree rely on synchronization between nodes, the throughput improvements of our algorithms in this work do not need MAC-layer coordination.

Other Related Works Some existing cross-layer approaches jointly consider routing and link scheduling . Zhang et al.  formulated joint routing and scheduling into an optimization problem, and solved the problem with a column generation method. Pan et al. dealt with the joint problem in cognitive radio networks considering the vacancy of licensed bands. Jones et al. implemented k-tuple network coding and proved throughput optimality of their policy. Although these works can provide good performance theoretically, they need centralized control to realize MAC-layer scheduling, and to eliminate transmission contention. The algorithms proposed in this work do not require any scheduling, and the SASR algorithms can be implemented in a distributed manner. Last but not least, there are also works aimed at exploiting spatial reusability. Specifically, the authorsconsidered the trade-off between spatial reuse and data rate, and proposed a decentralized power and rate control algorithm for higher network capacity. Zhai and Fang investigated the optimum carrier sensing range for throughput maximization. However, none of these works deal with the problem of route selection.

Implemantation

In this Spatial Reusability-Aware Routing in Multi-Hop Wireless Networks section, we discuss the important issues on the implementation of the proposed algorithms. First, similar manner as  can be used to create the interference profile at each node. It takes trials only with the same number of nodes in the network, during which a node senses no signal from an interference-free node. What’s more, to achieve lower complexity, the imperfect measurement-calibrated propagation model in [33] can also be adopted to generate conservative conflict graph. Second, the three SASR algorithms can be incorporated with existing single path routing protocols such as DSR in a distributed manner. Generally, in DSR, the source node sends route request for the destination. When the other nodes receive the route request, they will include their own addresses and forward the request. Then, the destination node calculates the path cost of the received route request, and piggybacks the route reply through the reverse path if necessary. To implement the SASR algorithms, each forwarder needs to add the interfering information into the route request. Specifically, on receiving a route request, a node checks all its previous forwarders, and adds one flag bit to the route request for each of them denoting whether the forwarder is interference-free. According to the flag bits in the received request, the destination node can build the non-interfering sets, and run the SASR algorithm to calculatethepathcost.Soexceptaddingflagbitsinroute request, the operations of a forwarder in the process of finding the route from the source to destination are the same as in the DSR protocol. The SASR algorithms are executed only at destination nodes.

Third, as most existing works on anypath routing SAAR is a central algorithm that calculates the path costs and forms the forwarder lists. It can be utilized to determine the workloads of the forwarders based on MORE 

Conclusion and Feature Work

In this Spatial Reusability-Aware Routing in Multi-Hop Wireless Networks paper, we have demonstrated that we can significantly improve the end-to-end throughput in multihop wireless networks, by carefully considering spatial reusability of the wireless communication media. We have presented two protocols, SASR and SAAR, for spatial reusability-aware single-path routing and anypath routing, respectively. We have also implemented our protocols, and compared them with existing routing protocols with the data rates of 11 Mbps and 54 Mbps. Evaluation results show that SASR and SAAR algorithms can achieve more significant end-to-end throughput gains under higher data rates.Forthe case of single-flow,SASR achieves a throughput gain of as high as 5.3× under 54 Mbps, while for SAAR, the maximum gain can reach 71.6%. Furthermore, in multi-flow case, SASR can also improve the per-flow average throughputs by more than 20%. Meanwhile, the tremendous throughput gains only require acceptable additional transmission overheads. The extra transmission overheads of route request are less than 10% in our evaluation. In 80% cases, the overall transmission counts are increased by no more than 2 with SASR, while for SAAR, most of the increments are below 1. As for the future work, one direction is to further explore opportunities to improve the performance of our routing algorithms by analyzing special underperforming cases identified in the evaluation. Another direction is to investigate inter-flow spatial reusability, and to optimize system-wide performance.