Survey on diversity-based routing in wireless mesh networks : Challenges and solutions
---
paper_title: Wireless mesh networks: a survey

paper_content:

Wireless mesh networks (WMNs) consist of mesh routers and mesh clients, where mesh routers have minimal mobility and form the backbone of WMNs. They provide network access for both mesh and conventional clients. The integration of WMNs with other networks such as the Internet, cellular, IEEE 802.11, IEEE 802.15, IEEE 802.16, sensor networks, etc., can be accomplished through the gateway and bridging functions in the mesh routers. Mesh clients can be either stationary or mobile, and can form a client mesh network among themselves and with mesh routers. WMNs are anticipated to resolve the limitations and to significantly improve the performance of ad hoc networks, wireless local area networks (WLANs), wireless personal area networks (WPANs), and wireless metropolitan area networks (WMANs). They are undergoing rapid progress and inspiring numerous deployments. WMNs will deliver wireless services for a large variety of applications in personal, local, campus, and metropolitan areas. Despite recent advances in wireless mesh networking, many research challenges remain in all protocol layers. This paper presents a detailed study on recent advances and open research issues in WMNs. System architectures and applications of WMNs are described, followed by discussing the critical factors influencing protocol design. Theoretical network capacity and the state-of-the-art protocols for WMNs are explored with an objective to point out a number of open research issues. Finally, testbeds, industrial practice, and current standard activities related to WMNs are highlighted.
---
paper_title: Joint MAC-aware routing and load balancing in mesh networks

paper_content:

Past approaches to routing in mesh networks either (i) do not account for the MAC-layer interactions between the links in a tractable manner, or (ii) are agnostic to load-balancing across gateways. Our answer to these problems is MaLB (MAC-aware and Load Balanced routing algorithm), a greedy, tractable, and distributed mesh routing algorithm. Since the underlying objective function has high combinatorial complexity, MaLB uses a greedy approach. MaLB finds an optimum routing forest (union of trees rooted at the gateways) by taking into account MAC-layer interaction between links, as well as optimum multi-hop association of mesh nodes to gateways. MaLB builds on top of ETP (Expected Through-Put), a recently proposed MAC-aware routing metric. We also propose a low complexity variant of MaLB called LB (Load Balanced routing algorithm) which performs load balancing in a MAC-agnostic manner. MaLB performs especially well in networks with skewed topologies that result from unplanned mesh network deployment, as well as in the presence of gateway failures. Simulations with an enhanced version of ns-2 show that MaLB results in up to 60% higher throughput than a shortest path algorithm with ETX (Expected Transmission Count). Furthermore, MaLB results in up to 30% improvement over the LB algorithm, as well as a shortest path algorithm with ETT (Expected Transmission Time).
---
paper_title: ExOR: opportunistic multi-hop routing for wireless networks

paper_content:

This paper describes ExOR,an integrated routing and MAC protocol that increases the throughput of large unicast transfers in multi-hop wireless networks. ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect which intermediate nodes actually received the transmission. This deferred choice gives each transmission multiple opportunities to make progress. As a result ExOR can use long radio links with high loss rates, which would be avoided by traditional routing. ExOR increases a connection's throughput while using no more network capacity than traditional routine.ExOR's design faces the following challenges. The nodes that receive each packet must agree on their identities and choose one forwarder.The agreement protocol must have low overhead, but must also be robust enough that it rarely forwards a packet zero times or more than once. Finally, ExOR must choose the forwarder with the lowest remaining cost to the ultimate destination.Measurements of an implementation on a 38-node 802.11b test-bed show that ExOR increases throughput for most node pairs when compared with traditional routing. For pairs between which traditional routing uses one or two hops, ExOR's robust acknowledgments prevent unnecessary retransmissions,increasing throughput by nearly 35%. For more distant pairs, ExOR takes advantage of the choice of forwarders to provide throughput gains of a factor of two to four.
---
paper_title: A Contention-Aware Routing Metric for Multi-Rate Multi-Radio Mesh Networks

paper_content:

We present a new routing metric for multi-rate multi-radio mesh networks, which takes into account both contention for the shared wireless channel and rate diversity in multi-radio multi-channel mesh networks. A key property of the proposed contention-aware transmission time (CATT) metric is that it is isotonic, hence can be applied to link-state routing protocols. We have implemented the CATT metric in the OLSR routing protocol, and evaluate it in a test-bed with mesh nodes each equipped with four radio interfaces. Our experiments show that the proposed routing metric significantly outperforms other metrics that have appeared in the literature, in a number of scenarios that correspond to different mesh network topologies.
---
paper_title: Load balancing in ad hoc networks: single-path routing vs. multi-path routing

paper_content:

Multi-path routing has been studied thoroughly in the context of wired networks. Ii has been shown that using multiple paths to route messages between any source-destination pair of nodes (instead of using a single path) balances the load more evenly throughout the network. The common belief is that the same is true for ad hoc networks, i.e., multi-path routing balances the load significantly better than single-path routing. We show that this is not necessarily the case. We introduce a new model for evaluating the load balance under multi-path routing, when the paths chosen are the first K shortest paths (for a pre-specified K). Using this model, we show that unless we use a very large number of paths (which is very costly and therefore infeasible) the load distribution is almost the same as single shortest path routing. This is in contrary to the previous existing results which assume that multi-path routing distributes the load uniformly.
---
paper_title: Great expectations: the value of spatial diversity in wireless networks

paper_content:

The effect of spatial diversity on the throughput and reliability of wireless networks is examined. Spatial diversity is realized through multiple independently fading transmit/receive antenna paths in single-user communication and through independently fading links in multiuser communication. Adopting spatial diversity as a central theme, we start by studying its information-theoretic foundations, then we illustrate its benefits across the physical (signal transmission/coding and receiver signal processing) and networking (resource allocation, routing, and applications) layers. Throughout the paper, we discuss engineering intuition and tradeoffs, emphasizing the strong interactions between the various network functionalities.
---
paper_title: Link-level measurements from an 802.11b mesh network

paper_content:

This paper analyzes the causes of packet loss in a 38-node urban multi-hop 802.11b network. The patterns and causes of loss are important in the design of routing and error-correction protocols, as well as in network planning.The paper makes the following observations. The distribution of inter-node loss rates is relatively uniform over the whole range of loss rates; there is no clear threshold separating "in range" and "out of range." Most links have relatively stable loss rates from one second to the next, though a small minority have very bursty losses at that time scale. Signal-to-noise ratio and distance have little predictive value for loss rate. The large number of links with intermediate loss rates is probably due to multi-path fading rather than attenuation or interference.The phenomena discussed here are all well-known. The contributions of this paper are an understanding of their relative importance, of how they interact, and of the implications for MAC and routing protocol design.
---
paper_title: Mesh networks: commodity multihop ad hoc networks

paper_content:

In spite of the massive efforts in researching and developing mobile ad hoc networks in the last decade, this type of network has not yet witnessed mass market deployment. The low commercial penetration of products based on ad hoc networking technology could be explained by noting that the ongoing research is mainly focused on implementing military or specialized civilian applications. On the other hand, users are interested in general-purpose applications where high bandwidth and open access to the Internet are consolidated and cheap commodities. To turn mobile ad hoc networks into a commodity, we should move to more pragmatic "opportunistic ad hoc networking" in which multihop ad hoc networks are not isolated self-configured networks, but rather emerge as a flexible and low-cost extension of wired infrastructure networks coexisting with them. Indeed, a new class of networks is emerging from this view: mesh networks. This article provides an overview of mesh networking technology. In particular, starting from commercial case studies we describe the core building blocks and distinct features on which wireless mesh networks should be based. We provide a survey of the current state of the art in off-the-shelf and proprietary solutions to build wireless mesh networks. Finally, we address the challenges of designing a high-performance, scalable, and cost-effective wireless mesh network.
---
paper_title: Routing in multi-radio, multi-hop wireless mesh networks

paper_content:

We present a new metric for routing in multi-radio, multi-hop wireless networks. We focus on wireless networks with stationary nodes, such as community wireless networks.The goal of the metric is to choose a high-throughput path between a source and a destination. Our metric assigns weights to individual links based on the Expected Transmission Time (ETT) of a packet over the link. The ETT is a function of the loss rate and the bandwidth of the link. The individual link weights are combined into a path metric called Weighted Cumulative ETT (WCETT) that explicitly accounts for the interference among links that use the same channel. The WCETT metric is incorporated into a routing protocol that we call Multi-Radio Link-Quality Source Routing.We studied the performance of our metric by implementing it in a wireless testbed consisting of 23 nodes, each equipped with two 802.11 wireless cards. We find that in a multi-radio environment, our metric significantly outperforms previously-proposed routing metrics by making judicious use of the second radio.
---
paper_title: a high-throughput path metric for multi-hop wireless routing

paper_content:

This paper presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29-node 802.11b test-bed demonstrate the poor performance of minimum hop-count, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer.
---
paper_title: Mobile Ad Hoc Networking: Imperatives and Challenges

paper_content:

A mobile ad hoc network (MANET), sometimes called a mobile mesh network, is a self- configuring network of mobile devices connected by wireless links. The Ad hoc networks are a new wireless networking paradigm for mobile hosts. Unlike traditional mobile wireless networks, ad hoc networks do not rely on any fixed infrastructure. Instead, hosts rely on each other to keep the network connected. It represent complex distributed systems that comprise wireless mobile nodes that can freely and dynamically self-organize into arbitrary and temporary, ''ad-hoc'' network topologies, allowing people and devices to seamlessly internetwork in areas with no pre-existing communication infrastructure. Ad hoc networking concept is not a new one, having been around in various forms for over 20 years. Traditionally, tactical networks have been the only communication networking application that followed the adhoc paradigm. Recently, the introduction of new technologies such as the Bluetooth, IEEE 802.11 and Hyperlan are helping enable eventual commercial MANET deployments outside the military domain. These recent evolutions have been generating a renewed and growing interest in the research and development of MANET.So,we would like to propose the challenges and imperativels that the MANET is facing.
---
paper_title: Trading structure for randomness in wireless opportunistic routing

paper_content:

Opportunistic routing is a recent technique that achieves high throughput in the face of lossy wireless links. The current opportunistic routing protocol, ExOR, ties the MAC with routing, imposing a strict schedule on routers' access to the medium. Although the scheduler delivers opportunistic gains, it misses some of the inherent features of the 802.11 MAC. For example, it prevents spatial reuse and thus may underutilize the wireless medium. It also eliminates the layering abstraction, making the protocol less amenable to extensions to alternate traffic types such as multicast. This paper presents MORE, a MAC-independent opportunistic routing protocol. MORE randomly mixes packets before forwarding them. This randomness ensures that routers that hear the same transmission do not forward the same packets. Thus, MORE needs no special scheduler to coordinate routers and can run directly on top of 802.11. Experimental results from a 20-node wireless testbed show that MORE's median unicast throughput is 22% higher than ExOR, and the gains rise to 45% over ExOR when there is a chance of spatial reuse. For multicast, MORE's gains increase with the number of destinations, and are 35-200% greater than ExOR.
---
paper_title: Measurement driven deployment of a two-tier urban mesh access network

paper_content:

Multihop wireless mesh networks can provide Internet access over a wide area with minimal infrastructure expenditure. In this work, we present a measurement driven deployment strategy and a data-driven model to study the impact of design and topology decisions on network-wide performance and cost. We perform extensive measurements in a two-tier urban scenario to characterize the propagation environment and correlate received signal strength with application layer throughput. We find that well-known estimates for pathloss produce either heavily overprovisioned networks resulting in an order of magnitude increase in cost for high pathloss estimates or completely disconnected networks for low pathloss estimates. Modeling throughput with wireless interface manufacturer specifications similarly results in severely underprovisioned networks. Further, we measure competing, multihop flow traffic matrices to empirically define achievable throughputs of fully backlogged, rate limited, and web-emulated traffic. We find that while fully backlogged flows produce starving nodes, rate-controlling flows to a fixed value yields fairness and high aggregate throughput. Likewise, transmission gaps occurring in statistically multiplexed web traffic, even under high offered load, remove starvation and yield high performance. In comparison, we find that well-known noncompeting flow models for mesh networks over-estimate network-wide throughput by a factor of 2. Finally, our placement study shows that a regular grid topology achieves up to 50 percent greater throughput than random node placement.
---
paper_title: Enabling large-scale wireless broadband: the case for TAPs

paper_content:

The vision is tantalizing: a high-performance, scalable, and widely deployed wireless Internet that facilitates services ranging from radically new and unforeseen applications to true wireless "broadband" to residences and public spaces at rates of 10s of Mb/sec. However, while high-speed wireless access is easy to achieve in an enterprise network via low-cost IEEE 802.11 (WiFi) access points, wireless technology in public spaces is in its infancy. "Hot spots" provide high-speed wireless access, but do so in very few isolated "islands" at immense costs. Likewise, while fixed wireless (e.g. LMDS) and 3G can provide ubiquitous coverage and 3G can support mobility, throughputs can often be two orders of magnitude slower than WiFi.In this paper, we formulate the challenges of building a high-performance, scalable and widely deployed wireless Internet along 10 premises. We make the case for the requirement of a fundamental new architecture based on beamforming antennas deployed on fixed, wire-powered Transit Access Points (TAPs) that form a multi-hopping wireless backbone with a limited number of wired ingress/egress points. To address scalability, deployability, and performance challenges we present distributed, opportunistic and coordinated resource management problems and a novel "network is the channel" framework that searches for fundamental information-theoretic tradeoffs between protocol overhead and capacity.
---
paper_title: XORs in the air: practical wireless network coding

paper_content:

This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic and potentially bursty flows, and practical issues facing the integration of network coding in the current network stack. We evaluate our design on a 20-node wireless network, and discuss the results of the first testbed deployment of wireless network coding. The results show that using COPE at the forwarding layer, without modifying routing and higher layers, increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.
---
paper_title: Opportunistic networking: data forwarding in disconnected mobile ad hoc networks

paper_content:

Opportunistic networks are one of the most interesting evolutions of MANETs. In opportunistic networks, mobile nodes are enabled to communicate with each other even if a route connecting them never exists. Furthermore, nodes are not supposed to possess or acquire any knowledge about the network topology, which (instead) is necessary in traditional MANET routing protocols. Routes are built dynamically, while messages are en route between the sender and the destination(s), and any possible node can opportunistically be used as next hop, provided it is likely to bring the message closer to the final destination. These requirements make opportunistic networks a challenging and promising research field. In this article we survey the most interesting case studies related to opportunistic networking and discuss and organize a taxonomy for the main routing and forwarding approaches in this challenging environment. We finally envision further possible scenarios to make opportunistic networks part of the next-generation Internet
---
paper_title: Exploiting multiuser diversity for medium access control in wireless networks

paper_content:

Multiuser diversity refers to a type of diversity present across different users in a fading environment. This diversity can be exploited by scheduling transmissions so that users transmit when their channel conditions are favorable. Using such an approach leads to a system capacity that increases with the number of users. However, such scheduling requires centralized control. In this paper, we consider a decentralized medium access control (MAC) protocol, where each user only has knowledge of its own channel gain. We consider a variation of the ALOHA protocol, channel-aware ALOHA; using this protocol we show that users can still exploit multiuser diversity gains. First we consider a backlogged model, where each user always has packets to send. In this case we show that the total system throughput increases at the same rate as in a system with a centralized scheduler. Asymptotically, the fraction of throughput lost due to the random access protocol is shown to be 1/e. We also consider a splitting algorithm, where the splitting sequence depends on the users' channel gains; this algorithm is shown to approach the throughput of an optimal centralized scheme. Next we consider a system with an infinite user population and random arrivals. In this case, it is proved that a variation of channel-aware ALOHA is stable for any total arrival rate in a memoryless channel, given that users can estimate the backlog. Extensions for channels with memory are also discussed.
---
paper_title: ExOR: opportunistic multi-hop routing for wireless networks

paper_content:

This paper describes ExOR,an integrated routing and MAC protocol that increases the throughput of large unicast transfers in multi-hop wireless networks. ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect which intermediate nodes actually received the transmission. This deferred choice gives each transmission multiple opportunities to make progress. As a result ExOR can use long radio links with high loss rates, which would be avoided by traditional routing. ExOR increases a connection's throughput while using no more network capacity than traditional routine.ExOR's design faces the following challenges. The nodes that receive each packet must agree on their identities and choose one forwarder.The agreement protocol must have low overhead, but must also be robust enough that it rarely forwards a packet zero times or more than once. Finally, ExOR must choose the forwarder with the lowest remaining cost to the ultimate destination.Measurements of an implementation on a 38-node 802.11b test-bed show that ExOR increases throughput for most node pairs when compared with traditional routing. For pairs between which traditional routing uses one or two hops, ExOR's robust acknowledgments prevent unnecessary retransmissions,increasing throughput by nearly 35%. For more distant pairs, ExOR takes advantage of the choice of forwarders to provide throughput gains of a factor of two to four.
---
paper_title: Great expectations: the value of spatial diversity in wireless networks

paper_content:

The effect of spatial diversity on the throughput and reliability of wireless networks is examined. Spatial diversity is realized through multiple independently fading transmit/receive antenna paths in single-user communication and through independently fading links in multiuser communication. Adopting spatial diversity as a central theme, we start by studying its information-theoretic foundations, then we illustrate its benefits across the physical (signal transmission/coding and receiver signal processing) and networking (resource allocation, routing, and applications) layers. Throughout the paper, we discuss engineering intuition and tradeoffs, emphasizing the strong interactions between the various network functionalities.
---
paper_title: ExOR: opportunistic multi-hop routing for wireless networks

paper_content:

This paper describes ExOR,an integrated routing and MAC protocol that increases the throughput of large unicast transfers in multi-hop wireless networks. ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect which intermediate nodes actually received the transmission. This deferred choice gives each transmission multiple opportunities to make progress. As a result ExOR can use long radio links with high loss rates, which would be avoided by traditional routing. ExOR increases a connection's throughput while using no more network capacity than traditional routine.ExOR's design faces the following challenges. The nodes that receive each packet must agree on their identities and choose one forwarder.The agreement protocol must have low overhead, but must also be robust enough that it rarely forwards a packet zero times or more than once. Finally, ExOR must choose the forwarder with the lowest remaining cost to the ultimate destination.Measurements of an implementation on a 38-node 802.11b test-bed show that ExOR increases throughput for most node pairs when compared with traditional routing. For pairs between which traditional routing uses one or two hops, ExOR's robust acknowledgments prevent unnecessary retransmissions,increasing throughput by nearly 35%. For more distant pairs, ExOR takes advantage of the choice of forwarders to provide throughput gains of a factor of two to four.
---
paper_title: Simple opportunistic routing protocol for wireless mesh networks

paper_content:

Multihop wireless mesh networks are becoming a new attractive communication paradigm. Many cities and public places have deployed or are planning to deploy mesh networks to provide Internet access to residents and local businesses. Routing protocol design is critical to the performance and reliability of wireless mesh networks. Traditional routing protocols send traffic along pre-determined paths and have been shown ineffective in coping with unreliable and unpredictable wireless medium. In this paper, we develop a simple opportunistic adaptive routing protocol (SOAR) for wireless mesh networks. SOAR maximizes the progress each packet makes by using priority-based timers to ensure that the most preferred node forwards the packet with little coordination overhead. Moreover, SOAR minimizes resource consumption and duplicate transmissions by judiciously selecting forwarding nodes to prevent routes from diverging. To further protect against packet losses, SOAR uses local recovery to retransmit a packet when an ACK is not received within a specified time. SOAR uses a combination of selective ACKs, piggyback ACKs, and ACK compression to protect against ACK loss while minimizing ACK overhead. We evaluate SOAR using NS-2 simulations. Our preliminary results show that SOAR is promising to achieve high efficiency and effectively support multiple simultaneous flows.
---
paper_title: Least-Cost Opportunistic Routing

paper_content:

In opportunistic routing, each node maintains a group of candidate relays to reach a particular destination, and transmits packets to any node in this group. If a single candidate relay receives the packet, it becomes the effective relay to forward the packet further. If no candidate receives the packet, then the current sender re-transmits. If multiple candidates receive the packet, then the link layer chooses a single receiver to be the relay. This choice could be made at random, or it could be driven by information coming from the routing layer, for example to use the best receiver as the relay. This paper addresses the least-cost opportunistic routing (LCOR) problem: how to assign and prioritize the set of candidate relays at each node for a given destination such that the expected cost of forwarding a packet to the destination is minimized. We solve this problem with a distributed algorithm that provably computes the optimal assignment of candidate relays that each node should allow to reach a particular destination. Prior proposals based on single-path routing metrics or geographic coordinates do not explicitly consider this tradeoff, and as a result make choices which are not always optimal.
---
paper_title: On selection of candidates for opportunistic anypath forwarding

paper_content:

Opportunistic routing schemes that exploit the broadcast nature of wireless transmissions for selecting the best next-hop at that instant among a set of candidates are being actively explored [1-3]. These schemes which we refer to as opportunistic any-path forwarding (OAPF), reduce the number of transmissions needed for reliable packet delivery.
---
paper_title: ExOR: opportunistic multi-hop routing for wireless networks

paper_content:

This paper describes ExOR,an integrated routing and MAC protocol that increases the throughput of large unicast transfers in multi-hop wireless networks. ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect which intermediate nodes actually received the transmission. This deferred choice gives each transmission multiple opportunities to make progress. As a result ExOR can use long radio links with high loss rates, which would be avoided by traditional routing. ExOR increases a connection's throughput while using no more network capacity than traditional routine.ExOR's design faces the following challenges. The nodes that receive each packet must agree on their identities and choose one forwarder.The agreement protocol must have low overhead, but must also be robust enough that it rarely forwards a packet zero times or more than once. Finally, ExOR must choose the forwarder with the lowest remaining cost to the ultimate destination.Measurements of an implementation on a 38-node 802.11b test-bed show that ExOR increases throughput for most node pairs when compared with traditional routing. For pairs between which traditional routing uses one or two hops, ExOR's robust acknowledgments prevent unnecessary retransmissions,increasing throughput by nearly 35%. For more distant pairs, ExOR takes advantage of the choice of forwarders to provide throughput gains of a factor of two to four.
---
paper_title: Simple opportunistic routing protocol for wireless mesh networks

paper_content:

Multihop wireless mesh networks are becoming a new attractive communication paradigm. Many cities and public places have deployed or are planning to deploy mesh networks to provide Internet access to residents and local businesses. Routing protocol design is critical to the performance and reliability of wireless mesh networks. Traditional routing protocols send traffic along pre-determined paths and have been shown ineffective in coping with unreliable and unpredictable wireless medium. In this paper, we develop a simple opportunistic adaptive routing protocol (SOAR) for wireless mesh networks. SOAR maximizes the progress each packet makes by using priority-based timers to ensure that the most preferred node forwards the packet with little coordination overhead. Moreover, SOAR minimizes resource consumption and duplicate transmissions by judiciously selecting forwarding nodes to prevent routes from diverging. To further protect against packet losses, SOAR uses local recovery to retransmit a packet when an ACK is not received within a specified time. SOAR uses a combination of selective ACKs, piggyback ACKs, and ACK compression to protect against ACK loss while minimizing ACK overhead. We evaluate SOAR using NS-2 simulations. Our preliminary results show that SOAR is promising to achieve high efficiency and effectively support multiple simultaneous flows.
---
paper_title: Simple opportunistic routing protocol for wireless mesh networks

paper_content:

Multihop wireless mesh networks are becoming a new attractive communication paradigm. Many cities and public places have deployed or are planning to deploy mesh networks to provide Internet access to residents and local businesses. Routing protocol design is critical to the performance and reliability of wireless mesh networks. Traditional routing protocols send traffic along pre-determined paths and have been shown ineffective in coping with unreliable and unpredictable wireless medium. In this paper, we develop a simple opportunistic adaptive routing protocol (SOAR) for wireless mesh networks. SOAR maximizes the progress each packet makes by using priority-based timers to ensure that the most preferred node forwards the packet with little coordination overhead. Moreover, SOAR minimizes resource consumption and duplicate transmissions by judiciously selecting forwarding nodes to prevent routes from diverging. To further protect against packet losses, SOAR uses local recovery to retransmit a packet when an ACK is not received within a specified time. SOAR uses a combination of selective ACKs, piggyback ACKs, and ACK compression to protect against ACK loss while minimizing ACK overhead. We evaluate SOAR using NS-2 simulations. Our preliminary results show that SOAR is promising to achieve high efficiency and effectively support multiple simultaneous flows.
---
paper_title: Linear network coding

paper_content:

Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.
---
paper_title: On randomized network coding

paper_content:

We consider a randomized network coding approach for multicasting from several sources over a network, in which nodes independently and randomly select linear mappings from inputs onto output links over some field. This approach was first described in [3], which gave, for acyclic delay-free networks, a bound on error probability, in terms of the number of receivers and random coding output links, that decreases exponentially with code length. The proof was based on a result in [2] relating algebraic network coding to network flows. In this paper, we generalize these results to networks with cycles and delay. We also show, for any given acyclic network, a tighter bound in terms of the probability of connection feasibility in a related network problem with unreliable links. From this we obtain a success probability bound for randomized network coding in link-redundant networks with unreliable links, in terms of link failure probability and amount of redundancy.
---
paper_title: Network Information Flow

paper_content:

We introduce a new class of problems called network information flow which is inspired by computer network applications. Consider a point-to-point communication network on which a number of information sources are to be multicast to certain sets of destinations. We assume that the information sources are mutually independent. The problem is to characterize the admissible coding rate region. This model subsumes all previously studied models along the same line. We study the problem with one information source, and we have obtained a simple characterization of the admissible coding rate region. Our result can be regarded as the max-flow min-cut theorem for network information flow. Contrary to one's intuition, our work reveals that it is in general not optimal to regard the information to be multicast as a "fluid" which can simply be routed or replicated. Rather, by employing coding at the nodes, which we refer to as network coding, bandwidth can in general be saved. This finding may have significant impact on future design of switching systems.
---
paper_title: Wireless Network Coding: Opportunities & Challenges

paper_content:

Wireless networks suffer from a variety of unique problems such as low throughput, dead spots, and inadequate support for mobility. However, their characteristics such as the broadcast nature of the medium, spatial diversity, and significant data redundancy, provide opportunities for new design principles to address these problems. There has been recent interest in employing network coding in wireless networks. This paper explores the case for network coding as a unifying design paradigm for wireless networks, by describing how it addresses issues of throughput, reliability, mobility, and management. We also discuss the practical challenges facing the integration of such a design into the network stack.
---
paper_title: Multipath code casting for wireless mesh networks

paper_content:

Designing high throughput wireless mesh networks involves solving interrelated scheduling, routing, and interference problems. In this paper, we exploit the broadcast properties and the path diversity of wireless meshes to implement an efficient multipath routing protocol, Multipath Code Casting (MC2). In contrast to prior work in opportunistic routing, which required strong coordination across nodes to prevent information repetition, our design is based on network coding and does not require node coordination. Moreover, it provides a unified framework to deal with data transmissions across multiple and, often, unreliable transmission paths. Our design also includes a novel rate-scheduling algorithm that guarantees (proportionally) fair allocation of resources across multiple (multipath) flows, ensures that data use the paths with the best performance, and prevents information overflow by controlling the data rate across each path. Using simulations and a prototype implementation, we show that our algorithms provide over 30% performance improvement compared to traditional singlepath approaches when applied to realistic and other exemplar topologies; in some scenarios, our approach can even double the throughput. Our approach also performs better than 20% compared to other multipath routing schemes.
---
paper_title: Trading structure for randomness in wireless opportunistic routing

paper_content:

Opportunistic routing is a recent technique that achieves high throughput in the face of lossy wireless links. The current opportunistic routing protocol, ExOR, ties the MAC with routing, imposing a strict schedule on routers' access to the medium. Although the scheduler delivers opportunistic gains, it misses some of the inherent features of the 802.11 MAC. For example, it prevents spatial reuse and thus may underutilize the wireless medium. It also eliminates the layering abstraction, making the protocol less amenable to extensions to alternate traffic types such as multicast. This paper presents MORE, a MAC-independent opportunistic routing protocol. MORE randomly mixes packets before forwarding them. This randomness ensures that routers that hear the same transmission do not forward the same packets. Thus, MORE needs no special scheduler to coordinate routers and can run directly on top of 802.11. Experimental results from a 20-node wireless testbed show that MORE's median unicast throughput is 22% higher than ExOR, and the gains rise to 45% over ExOR when there is a chance of spatial reuse. For multicast, MORE's gains increase with the number of destinations, and are 35-200% greater than ExOR.
---
paper_title: XORs in the air: practical wireless network coding

paper_content:

This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic and potentially bursty flows, and practical issues facing the integration of network coding in the current network stack. We evaluate our design on a 20-node wireless network, and discuss the results of the first testbed deployment of wireless network coding. The results show that using COPE at the forwarding layer, without modifying routing and higher layers, increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.
---
paper_title: Loss-aware network coding for unicast wireless sessions: design, implementation, and performance evaluation

paper_content:

Local network coding is growing in prominence as a technique to facilitate greater capacity utilization in multi-hop wireless networks. A specific objective of such local network coding techniques has been to explicitly minimize the total number of transmissions needed to carry packets across each wireless hop. While such a strategy is certainly useful, we argue that in lossy wireless environments, a better use of local network coding is to provide higher levels of redundancy even at the cost of increasing the number of transmissions required to communicate the same information. In this paper we show that the design space for effective redundancy in local network coding is quite large, which makes optimal formulations of the problem hard to realize in practice. We present a detailed exploration of this design space and propose a suite of algorithms, called CLONE, that can lead to further throughput gains in multi-hop wireless scenarios. Through careful analysis, simulations, and detailed implementation on a real testbed, we show that some of our simplest CLONE algorithms can be efficiently implemented in today's wireless hardware to provide a factor of two improvement in throughput for example scenarios, while other, more effective, CLONE algorithms require additional advances in hardware processing speeds to be deployable in practice.
---
paper_title: Linear network coding

paper_content:

Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.
---
paper_title: On randomized network coding

paper_content:

We consider a randomized network coding approach for multicasting from several sources over a network, in which nodes independently and randomly select linear mappings from inputs onto output links over some field. This approach was first described in [3], which gave, for acyclic delay-free networks, a bound on error probability, in terms of the number of receivers and random coding output links, that decreases exponentially with code length. The proof was based on a result in [2] relating algebraic network coding to network flows. In this paper, we generalize these results to networks with cycles and delay. We also show, for any given acyclic network, a tighter bound in terms of the probability of connection feasibility in a related network problem with unreliable links. From this we obtain a success probability bound for randomized network coding in link-redundant networks with unreliable links, in terms of link failure probability and amount of redundancy.
---
paper_title: Efficient Operation of Wireless Packet Networks Using Network Coding

paper_content:

The marriage of network coding and wireless packet networks is a natural and attractive one. So, despite network coding being a still nascent field, a considerable body of work on this subject already exists. In this paper, we give a brief overview of this work and hope, thereby, to provide the reader with a firm theoretical basis from which practical implementations and theoretical extensions can be developed.
---
paper_title: Routing with opportunistically coded exchanges in wireless mesh networks

paper_content:

Network coding is known to improve network throughput by mixing information from different flows and conveying more information in each transmission. Recently there have been some proposals for applying network coding to wireless mesh networks leveraging the broadcast nature of wireless transmissions. These approaches exploit coding opportunities passively while forwarding packets but they do not proactively change routing of flows to create more coding opportunities. In this paper, we attempt to investigate the extent of performance gain possible when routing decisions are made with the awareness of coding. We first define the expected number of coded transmissions for a successful exchange of packets between two nodes through an intermediate node. We then formulate optimal routing with coding, given the topology and traffic, as a linear programming problem. We conduct a preliminary evaluation of coding-aware routing and show that it offers significant gain particularly when there are many long distance flows.
---
paper_title: XORs in the air: practical wireless network coding

paper_content:

This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic and potentially bursty flows, and practical issues facing the integration of network coding in the current network stack. We evaluate our design on a 20-node wireless network, and discuss the results of the first testbed deployment of wireless network coding. The results show that using COPE at the forwarding layer, without modifying routing and higher layers, increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.
---
paper_title: Loss-aware network coding for unicast wireless sessions: design, implementation, and performance evaluation

paper_content:

Local network coding is growing in prominence as a technique to facilitate greater capacity utilization in multi-hop wireless networks. A specific objective of such local network coding techniques has been to explicitly minimize the total number of transmissions needed to carry packets across each wireless hop. While such a strategy is certainly useful, we argue that in lossy wireless environments, a better use of local network coding is to provide higher levels of redundancy even at the cost of increasing the number of transmissions required to communicate the same information. In this paper we show that the design space for effective redundancy in local network coding is quite large, which makes optimal formulations of the problem hard to realize in practice. We present a detailed exploration of this design space and propose a suite of algorithms, called CLONE, that can lead to further throughput gains in multi-hop wireless scenarios. Through careful analysis, simulations, and detailed implementation on a real testbed, we show that some of our simplest CLONE algorithms can be efficiently implemented in today's wireless hardware to provide a factor of two improvement in throughput for example scenarios, while other, more effective, CLONE algorithms require additional advances in hardware processing speeds to be deployable in practice.
---
paper_title: Trading structure for randomness in wireless opportunistic routing

paper_content:

Opportunistic routing is a recent technique that achieves high throughput in the face of lossy wireless links. The current opportunistic routing protocol, ExOR, ties the MAC with routing, imposing a strict schedule on routers' access to the medium. Although the scheduler delivers opportunistic gains, it misses some of the inherent features of the 802.11 MAC. For example, it prevents spatial reuse and thus may underutilize the wireless medium. It also eliminates the layering abstraction, making the protocol less amenable to extensions to alternate traffic types such as multicast. This paper presents MORE, a MAC-independent opportunistic routing protocol. MORE randomly mixes packets before forwarding them. This randomness ensures that routers that hear the same transmission do not forward the same packets. Thus, MORE needs no special scheduler to coordinate routers and can run directly on top of 802.11. Experimental results from a 20-node wireless testbed show that MORE's median unicast throughput is 22% higher than ExOR, and the gains rise to 45% over ExOR when there is a chance of spatial reuse. For multicast, MORE's gains increase with the number of destinations, and are 35-200% greater than ExOR.
---
paper_title: Wireless mesh networks: a survey

paper_content:

Wireless mesh networks (WMNs) consist of mesh routers and mesh clients, where mesh routers have minimal mobility and form the backbone of WMNs. They provide network access for both mesh and conventional clients. The integration of WMNs with other networks such as the Internet, cellular, IEEE 802.11, IEEE 802.15, IEEE 802.16, sensor networks, etc., can be accomplished through the gateway and bridging functions in the mesh routers. Mesh clients can be either stationary or mobile, and can form a client mesh network among themselves and with mesh routers. WMNs are anticipated to resolve the limitations and to significantly improve the performance of ad hoc networks, wireless local area networks (WLANs), wireless personal area networks (WPANs), and wireless metropolitan area networks (WMANs). They are undergoing rapid progress and inspiring numerous deployments. WMNs will deliver wireless services for a large variety of applications in personal, local, campus, and metropolitan areas. Despite recent advances in wireless mesh networking, many research challenges remain in all protocol layers. This paper presents a detailed study on recent advances and open research issues in WMNs. System architectures and applications of WMNs are described, followed by discussing the critical factors influencing protocol design. Theoretical network capacity and the state-of-the-art protocols for WMNs are explored with an objective to point out a number of open research issues. Finally, testbeds, industrial practice, and current standard activities related to WMNs are highlighted.
---
paper_title: ExOR: opportunistic multi-hop routing for wireless networks

paper_content:

This paper describes ExOR,an integrated routing and MAC protocol that increases the throughput of large unicast transfers in multi-hop wireless networks. ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect which intermediate nodes actually received the transmission. This deferred choice gives each transmission multiple opportunities to make progress. As a result ExOR can use long radio links with high loss rates, which would be avoided by traditional routing. ExOR increases a connection's throughput while using no more network capacity than traditional routine.ExOR's design faces the following challenges. The nodes that receive each packet must agree on their identities and choose one forwarder.The agreement protocol must have low overhead, but must also be robust enough that it rarely forwards a packet zero times or more than once. Finally, ExOR must choose the forwarder with the lowest remaining cost to the ultimate destination.Measurements of an implementation on a 38-node 802.11b test-bed show that ExOR increases throughput for most node pairs when compared with traditional routing. For pairs between which traditional routing uses one or two hops, ExOR's robust acknowledgments prevent unnecessary retransmissions,increasing throughput by nearly 35%. For more distant pairs, ExOR takes advantage of the choice of forwarders to provide throughput gains of a factor of two to four.
---
paper_title: Utility-Based Opportunistic Routing in Multi-Hop Wireless Networks

paper_content:

Recently, opportunistic routing (OR) has been widely used to compensate for the low packet delivery ratio of multi-hop wireless networks. Previous works either provide heuristic solutions without optimality analysis, or assume that unlimited retransmission is available for delivering a data packet. In this paper, we apply OR to a utility-based routing where the successful delivery of a data packet generates benefit. The objective is to maximize utility, defined as a function of benefit and cost of transmission. As the link reliability of each relay determines eventual packet delivery and hence utility, OR offers the ability to increase reliability through opportunistic relays. We explore the optimality of utility-based routing through OR without allowing retransmission, and observe that the optimal scheme requires exhaustive searching of all paths from source to destination. We then propose a heuristic solution to select relays and determine priorities among them. Finally, we provide distributed implementations for both schemes. Simulations on NS-2 and our customized simulator are conducted to verify the effectiveness of the heuristic compared with the optimal.
---
paper_title: a high-throughput path metric for multi-hop wireless routing

paper_content:

This paper presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29-node 802.11b test-bed demonstrate the poor performance of minimum hop-count, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer.
---
paper_title: Social Welfare Based Routing in Ad hoc Networks

paper_content:

Due to resource scarcity, a paramount concern in ad hoc networks is to utilize the limited resources efficiently. The self-organized nature of ad hoc networks makes the social welfare based approach an efficient way to allocate the limited resources. However, the effect of instability of wireless links has not been adequately addressed in the literature. To efficiently address the routing problem in ad hoc networks, we introduce a new metric, maximum expected social welfare, and integrate the cost and stability of nodes in a unified model to evaluate the optimality of routes. The expected social welfare is defined in terms of expected benefit (of the routing source) minus the expected costs incurred by forwarding nodes. Based on our new metric, we design an optimal and efficient algorithm, and implement the algorithm in both centralized (optimal) and distributed (near-optimal) manners. We also extend our work to incorporate retransmission and study the effect of local and global retransmission restrictions on the selection of routes.
---
paper_title: Simple opportunistic routing protocol for wireless mesh networks

paper_content:

Multihop wireless mesh networks are becoming a new attractive communication paradigm. Many cities and public places have deployed or are planning to deploy mesh networks to provide Internet access to residents and local businesses. Routing protocol design is critical to the performance and reliability of wireless mesh networks. Traditional routing protocols send traffic along pre-determined paths and have been shown ineffective in coping with unreliable and unpredictable wireless medium. In this paper, we develop a simple opportunistic adaptive routing protocol (SOAR) for wireless mesh networks. SOAR maximizes the progress each packet makes by using priority-based timers to ensure that the most preferred node forwards the packet with little coordination overhead. Moreover, SOAR minimizes resource consumption and duplicate transmissions by judiciously selecting forwarding nodes to prevent routes from diverging. To further protect against packet losses, SOAR uses local recovery to retransmit a packet when an ACK is not received within a specified time. SOAR uses a combination of selective ACKs, piggyback ACKs, and ACK compression to protect against ACK loss while minimizing ACK overhead. We evaluate SOAR using NS-2 simulations. Our preliminary results show that SOAR is promising to achieve high efficiency and effectively support multiple simultaneous flows.
---
paper_title: Simple opportunistic routing protocol for wireless mesh networks

paper_content:

Multihop wireless mesh networks are becoming a new attractive communication paradigm. Many cities and public places have deployed or are planning to deploy mesh networks to provide Internet access to residents and local businesses. Routing protocol design is critical to the performance and reliability of wireless mesh networks. Traditional routing protocols send traffic along pre-determined paths and have been shown ineffective in coping with unreliable and unpredictable wireless medium. In this paper, we develop a simple opportunistic adaptive routing protocol (SOAR) for wireless mesh networks. SOAR maximizes the progress each packet makes by using priority-based timers to ensure that the most preferred node forwards the packet with little coordination overhead. Moreover, SOAR minimizes resource consumption and duplicate transmissions by judiciously selecting forwarding nodes to prevent routes from diverging. To further protect against packet losses, SOAR uses local recovery to retransmit a packet when an ACK is not received within a specified time. SOAR uses a combination of selective ACKs, piggyback ACKs, and ACK compression to protect against ACK loss while minimizing ACK overhead. We evaluate SOAR using NS-2 simulations. Our preliminary results show that SOAR is promising to achieve high efficiency and effectively support multiple simultaneous flows.
---
paper_title: Experimentation and performance evaluation of rate adaptation algorithms in wireless mesh networks

paper_content:

In this paper we present an experimental study conducted in 802.11-based mesh networks of three existing rate adaptation algorithms. The aim of this study is twofold. On the one hand, we explore the ability of these algorithms to cope with moderate to high medium contention levels. On the other hand, we investigate their performance on medium-distance 802.11 links. Our study indicates that, in congested networks, the network throughput can degrade up to ten times with respect to the best performance if the rate decision process is based solely on frame loss rates, without differentiating between the various causes of losses (i.e., channel errors or collisions). In addition, we have shown that these rate adaptation strategies perform reasonably well when the time correlation between channel errors is at least of the order of the sampling period used to estimate the channel dynamics. We believe that this study can be useful to derive correct guidelines for the design of new optimized rate adaptation algorithms taking into consideration the above factors.
---
paper_title: Cooperative Opportunistic Routing Using Transmit Diversity in Wireless Mesh Networks

paper_content:

We propose a new high performance forwarding scheme, denoted transmit diversity based cooperative opportunistic routing (TDiCOR), that efficiently exploits multiuser and transmit diversity to improve the overall throughput in wireless multi-hop networks. Neighboring nodes cooperate through simultaneous transmissions in a MISO fashion in order to overcome the destructive effects of fading. TDiCOR uses distributed transmit diversity to increase the robustness of acknowledgements as well as data transmissions while preserving the opportunistic nature by using multiple candidates for packet relaying. We present measurements from a wireless testbed which suggest that cooperation using transmit diversity is feasible even with today's off-the-shelf hardware. At the instance of TDiCOR, we demonstrate how to realize the idea of cooperative opportunistic routing as an operational protocol and present very promising simulation results. TDiCOR outperforms traditional routing (i.e. DSR) in typical outdoor scenarios in terms of throughput by 30% and by 50% in indoor scenarios with high shadow fading, without consuming additional bandwidth or additional hardware resources.
---
paper_title: An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding-Aware Routing

paper_content:

A recent approach, COPE, for improving the throughput of unicast traffic in wireless multi-hop networks exploits the broadcast nature of the wireless medium through opportunistic network coding. In this paper, we analyze throughput improvements obtained by COPE-type network coding in wireless networks from a theoretical perspective. We make two key contributions. First, we obtain a theoretical formulation for computing the throughput of network coding on any wireless network topology and any pattern of concurrent unicast traffic sessions. Second, we advocate that routing be made aware of network coding opportunities rather than, as in COPE, being oblivious to it. More importantly, our work studies the tradeoff between routing flows "close to each other" for utilizing coding opportunities and "away from each other" for avoiding wireless interference. Our theoretical formulation provides a method for computing source-destination routes and utilizing the best coding opportunities from available ones so as to maximize the throughput. We handle scheduling of broadcast transmissions subject to wireless transmit/receive diversity and link interference in our optimization framework. Using our formulations, we compare the performance of traditional unicast routing and network coding with coding-oblivious and coding-aware routing on a variety of mesh network topologies, including some derived from contemporary mesh network testbeds. Our evaluations show that a route selection strategy that is aware of network coding opportunities leads to higher end-to-end throughput when compared to coding-oblivious routing strategies.
---
paper_title: Routing with opportunistically coded exchanges in wireless mesh networks

paper_content:

Network coding is known to improve network throughput by mixing information from different flows and conveying more information in each transmission. Recently there have been some proposals for applying network coding to wireless mesh networks leveraging the broadcast nature of wireless transmissions. These approaches exploit coding opportunities passively while forwarding packets but they do not proactively change routing of flows to create more coding opportunities. In this paper, we attempt to investigate the extent of performance gain possible when routing decisions are made with the awareness of coding. We first define the expected number of coded transmissions for a successful exchange of packets between two nodes through an intermediate node. We then formulate optimal routing with coding, given the topology and traffic, as a linear programming problem. We conduct a preliminary evaluation of coding-aware routing and show that it offers significant gain particularly when there are many long distance flows.
---
paper_title: XORs in the air: practical wireless network coding

paper_content:

This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic and potentially bursty flows, and practical issues facing the integration of network coding in the current network stack. We evaluate our design on a 20-node wireless network, and discuss the results of the first testbed deployment of wireless network coding. The results show that using COPE at the forwarding layer, without modifying routing and higher layers, increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.
---
paper_title: Loss-aware network coding for unicast wireless sessions: design, implementation, and performance evaluation

paper_content:

Local network coding is growing in prominence as a technique to facilitate greater capacity utilization in multi-hop wireless networks. A specific objective of such local network coding techniques has been to explicitly minimize the total number of transmissions needed to carry packets across each wireless hop. While such a strategy is certainly useful, we argue that in lossy wireless environments, a better use of local network coding is to provide higher levels of redundancy even at the cost of increasing the number of transmissions required to communicate the same information. In this paper we show that the design space for effective redundancy in local network coding is quite large, which makes optimal formulations of the problem hard to realize in practice. We present a detailed exploration of this design space and propose a suite of algorithms, called CLONE, that can lead to further throughput gains in multi-hop wireless scenarios. Through careful analysis, simulations, and detailed implementation on a real testbed, we show that some of our simplest CLONE algorithms can be efficiently implemented in today's wireless hardware to provide a factor of two improvement in throughput for example scenarios, while other, more effective, CLONE algorithms require additional advances in hardware processing speeds to be deployable in practice.
---
paper_title: Multipath code casting for wireless mesh networks

paper_content:

Designing high throughput wireless mesh networks involves solving interrelated scheduling, routing, and interference problems. In this paper, we exploit the broadcast properties and the path diversity of wireless meshes to implement an efficient multipath routing protocol, Multipath Code Casting (MC2). In contrast to prior work in opportunistic routing, which required strong coordination across nodes to prevent information repetition, our design is based on network coding and does not require node coordination. Moreover, it provides a unified framework to deal with data transmissions across multiple and, often, unreliable transmission paths. Our design also includes a novel rate-scheduling algorithm that guarantees (proportionally) fair allocation of resources across multiple (multipath) flows, ensures that data use the paths with the best performance, and prevents information overflow by controlling the data rate across each path. Using simulations and a prototype implementation, we show that our algorithms provide over 30% performance improvement compared to traditional singlepath approaches when applied to realistic and other exemplar topologies; in some scenarios, our approach can even double the throughput. Our approach also performs better than 20% compared to other multipath routing schemes.
---
paper_title: Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

paper_content:

The stability of a queueing network with interdependent servers is considered. The dependency among the servers is described by the definition of their subsets that can be activated simultaneously. Multihop radio networks provide a motivation for the consideration of this system. The problem of scheduling the server activation under the constraints imposed by the dependency among servers is studied. The performance criterion of a scheduling policy is its throughput that is characterized by its stability region, that is, the set of vectors of arrival and service rates for which the system is stable. A policy is obtained which is optimal in the sense that its stability region is a superset of the stability region of every other scheduling policy, and this stability region is characterized. The behavior of the network is studied for arrival rates that lie outside the stability region. Implications of the results in certain types of concurrent database and parallel processing systems are discussed. >
---
paper_title: ExOR: opportunistic multi-hop routing for wireless networks

paper_content:

This paper describes ExOR,an integrated routing and MAC protocol that increases the throughput of large unicast transfers in multi-hop wireless networks. ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect which intermediate nodes actually received the transmission. This deferred choice gives each transmission multiple opportunities to make progress. As a result ExOR can use long radio links with high loss rates, which would be avoided by traditional routing. ExOR increases a connection's throughput while using no more network capacity than traditional routine.ExOR's design faces the following challenges. The nodes that receive each packet must agree on their identities and choose one forwarder.The agreement protocol must have low overhead, but must also be robust enough that it rarely forwards a packet zero times or more than once. Finally, ExOR must choose the forwarder with the lowest remaining cost to the ultimate destination.Measurements of an implementation on a 38-node 802.11b test-bed show that ExOR increases throughput for most node pairs when compared with traditional routing. For pairs between which traditional routing uses one or two hops, ExOR's robust acknowledgments prevent unnecessary retransmissions,increasing throughput by nearly 35%. For more distant pairs, ExOR takes advantage of the choice of forwarders to provide throughput gains of a factor of two to four.
---
paper_title: CodeOR: Opportunistic routing in wireless mesh networks with segmented network coding

paper_content:

Opportunistic routing significantly increases unicast throughput in wireless mesh networks by effectively utilizing the wireless broadcast medium. With network coding, opportunistic routing can be implemented in a simple and practical way without resorting to a complicated scheduling protocol. Due to constraints of computational complexity, a protocol utilizing network coding needs to perform segmented network coding, which partitions the data into multiple segments and encode only packets in the same segment. However, existing designs transmit only one segment at any given time while waiting for its acknowledgment, which degrades performance as the size of the network scales up. In this paper, we propose CodeOR, a new protocol that uses network coding in opportunistic routing to improve throughput. By transmitting a window of multiple segments concurrently, it improves the performance of existing work by a factor of two on average (and a factor of four in some cases). CodeOR is especially appropriate for real-time multimedia applications through the use of a small segment size to decrease decoding delay, and is able to further increase network throughput with a smaller packet size and a larger window size.
---
paper_title: Trading structure for randomness in wireless opportunistic routing

paper_content:

Opportunistic routing is a recent technique that achieves high throughput in the face of lossy wireless links. The current opportunistic routing protocol, ExOR, ties the MAC with routing, imposing a strict schedule on routers' access to the medium. Although the scheduler delivers opportunistic gains, it misses some of the inherent features of the 802.11 MAC. For example, it prevents spatial reuse and thus may underutilize the wireless medium. It also eliminates the layering abstraction, making the protocol less amenable to extensions to alternate traffic types such as multicast. This paper presents MORE, a MAC-independent opportunistic routing protocol. MORE randomly mixes packets before forwarding them. This randomness ensures that routers that hear the same transmission do not forward the same packets. Thus, MORE needs no special scheduler to coordinate routers and can run directly on top of 802.11. Experimental results from a 20-node wireless testbed show that MORE's median unicast throughput is 22% higher than ExOR, and the gains rise to 45% over ExOR when there is a chance of spatial reuse. For multicast, MORE's gains increase with the number of destinations, and are 35-200% greater than ExOR.
---
paper_title: Dice: a game theoretic framework for wireless multipath network coding

paper_content:

Network coding has emerged as a promising approach that enables reliable and efficient end-to-end transmissions in lossy wireless mesh networks. Existing protocols have demonstrated its resilience to packet losses, as well as the ability to integrate naturally with multipath opportunistic routing. However, these heuristics do not take into account the inherent resource competition in wireless networks, thereby compromising the coding advantages. In this paper, we take a game-theoretic perspective towards optimized resource allocation for network coding based unicast protocols. We design decentralized mechanisms that achieve better efficiency-fairness tradeoff, for both cooperative and selfish users. Our framework features a modularized optimization of two subproblems: the multipath routing of coded information flows for each player, and the broadcast and coding rate allocation among competing players. We have implemented the framework on a wireless emulation testbed and demonstrated its high performance in terms of throughput and fairness.
---
paper_title: Optimized multipath network coding in lossy wireless networks

paper_content:

Network coding has been a prominent approach to a series of problems that used to be considered intractable with traditional transmission paradigms. Recent work on network coding includes a substantial number of optimization based protocols, but mostly for wireline multicast networks. In this paper, we consider maximizing the benefits of network coding for unicast sessions in lossy wireless environments. We propose Optimized Multipath Network Coding (OMNC), a rate control and routing protocol that dramatically improves the throughput of lossy wireless networks. OMNC employs multiple paths to push coded packets to the destination, and uses the broadcast MAC to deliver packets between neighboring nodes. The coding and broadcast rate is allocated to transmitters by a distributed optimization algorithm that maximizes the advantage of path diversity while avoiding congestion. With extensive experiments on an emulation testbed, we find that OMNC achieves significant throughput improvement over traditional best path routing protocols, and existing multipath routing protocols with network coding.
---
paper_title: CodeOR: Opportunistic routing in wireless mesh networks with segmented network coding

paper_content:

Opportunistic routing significantly increases unicast throughput in wireless mesh networks by effectively utilizing the wireless broadcast medium. With network coding, opportunistic routing can be implemented in a simple and practical way without resorting to a complicated scheduling protocol. Due to constraints of computational complexity, a protocol utilizing network coding needs to perform segmented network coding, which partitions the data into multiple segments and encode only packets in the same segment. However, existing designs transmit only one segment at any given time while waiting for its acknowledgment, which degrades performance as the size of the network scales up. In this paper, we propose CodeOR, a new protocol that uses network coding in opportunistic routing to improve throughput. By transmitting a window of multiple segments concurrently, it improves the performance of existing work by a factor of two on average (and a factor of four in some cases). CodeOR is especially appropriate for real-time multimedia applications through the use of a small segment size to decrease decoding delay, and is able to further increase network throughput with a smaller packet size and a larger window size.
---
paper_title: Trading structure for randomness in wireless opportunistic routing

paper_content:

Opportunistic routing is a recent technique that achieves high throughput in the face of lossy wireless links. The current opportunistic routing protocol, ExOR, ties the MAC with routing, imposing a strict schedule on routers' access to the medium. Although the scheduler delivers opportunistic gains, it misses some of the inherent features of the 802.11 MAC. For example, it prevents spatial reuse and thus may underutilize the wireless medium. It also eliminates the layering abstraction, making the protocol less amenable to extensions to alternate traffic types such as multicast. This paper presents MORE, a MAC-independent opportunistic routing protocol. MORE randomly mixes packets before forwarding them. This randomness ensures that routers that hear the same transmission do not forward the same packets. Thus, MORE needs no special scheduler to coordinate routers and can run directly on top of 802.11. Experimental results from a 20-node wireless testbed show that MORE's median unicast throughput is 22% higher than ExOR, and the gains rise to 45% over ExOR when there is a chance of spatial reuse. For multicast, MORE's gains increase with the number of destinations, and are 35-200% greater than ExOR.
---
paper_title: XORs in the air: practical wireless network coding

paper_content:

This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic and potentially bursty flows, and practical issues facing the integration of network coding in the current network stack. We evaluate our design on a 20-node wireless network, and discuss the results of the first testbed deployment of wireless network coding. The results show that using COPE at the forwarding layer, without modifying routing and higher layers, increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.
---
paper_title: Routing with opportunistically coded exchanges in wireless mesh networks

paper_content:

Network coding is known to improve network throughput by mixing information from different flows and conveying more information in each transmission. Recently there have been some proposals for applying network coding to wireless mesh networks leveraging the broadcast nature of wireless transmissions. These approaches exploit coding opportunities passively while forwarding packets but they do not proactively change routing of flows to create more coding opportunities. In this paper, we attempt to investigate the extent of performance gain possible when routing decisions are made with the awareness of coding. We first define the expected number of coded transmissions for a successful exchange of packets between two nodes through an intermediate node. We then formulate optimal routing with coding, given the topology and traffic, as a linear programming problem. We conduct a preliminary evaluation of coding-aware routing and show that it offers significant gain particularly when there are many long distance flows.
---

Title: Survey on diversity-based routing in wireless mesh networks: Challenges and solutions

Section 1: Introduction
Description 1: Introduce the concept of multi-hop ad hoc networks, specifically wireless mesh networks, highlighting their benefits and current challenges in terms of routing.

Section 2: Background and taxonomy
Description 2: Provide an overview of general routing approaches in wireless mesh networks, introducing three main routing categories and related sub-categories, and describe the representative features, benefits, and design challenges of these classes.

Section 3: Opportunistic routing
Description 3: Discuss the characteristics, benefits, and challenges of opportunistic routing, dividing it into scheduled and not-scheduled approaches, and describe the most relevant schemes proposed for both sub-categories.

Section 4: Coding-based routing
Description 4: Explain the principles of network coding and its advantages in wireless networks, dividing the approaches into inter-flow and intra-flow coding, and outline the key issues and representative schemes for both.

Section 5: Hybrid routing
Description 5: Describe a hybrid paradigm combining opportunistic forwarding and network coding, highlight its benefits, and outline critical issues specifically related to the hybrid approach, dividing it into destination-based and neighborhood-based schemes.

Section 6: Overview of representative solutions
Description 6: Analyze the design choices and operations of some of the most representative solutions in each of the three routing categories discussed earlier.

Section 7: Discussion
Description 7: Summarize common functionalities and mechanisms considered as basic building blocks for diversity-based routing solutions, and present a comparative analysis of various approaches.

Section 8: Conclusions
Description 8: Present the key findings of the survey, discuss open research issues, and highlight future research directions to improve diversity-based routing in wireless mesh networks.