Network Coding-Aware Routing in Wireless Networks

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

IEEE/ACM TRANSACTIONS ON NETWORKING1 Network Coding-Aware Routing in Wireless Networks Sudipta Sengupta,Senior Member,IEEE,Shravan Rayanchu,and Suman Banerjee,Member,IEEE

Abstract—A recent approach—COPE,presented by Katti et al. (Proc.ACM SIGCOMM2006,pp.243–254)—for improving the throughput of unicast traf?c in wireless multihop networks exploits the broadcast nature of the wireless medium through op-portunistic network coding.In this paper,we analyze throughput improvements obtained by COPE-type network coding in wire-

between routing?ows 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 persity and link interfer-ence in our optimization 07ac4c2bb4daa58da0114a96ing 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 op-portunities leads to higher end-to-end throughput when compared to coding-oblivious routing strategies.

Index Terms—COPE,network coding,network coding-aware routing,opportunistic network coding,wireless broadcast sched-uling,wireless link scheduling,wireless networks.

I.I NTRODUCTION

N ETWORK coding is gaining popularity as a mechanism to increase the utilization of both wired and wireless net-works.We explain the basic idea of network coding using a very simple example consisting of three wireless nodes as shown in Fig.1(a).In the?gure,node1wants to send a single packet

to node3,while node3wants to send a single packet to node1.Due to transmission range limitations,both these paths go via 07ac4c2bb4daa58da0114a96ing standard techniques of packet forwarding, four wireless transmissions would be needed to complete these end-to-end packet transfers.The following are a possible se-quence of these transmissions:i)packet is transmitted by1,

Manuscript received August11,2008;revised February04,2009;June07, 2009;September06,2009;and November02,2009;approved by IEEE/ACM T RANSACTIONS ON N ETWORKING Editor D.Rubenstein.

S.Sengupta is with Microsoft Research,Redmond,W A98052USA(e-mail: sudipta@07ac4c2bb4daa58da0114a96).

S.Rayanchu and S.Banerjee are with the University of Wisconsin–Madison, Madison,WI53706USA(e-mail:shravan@07ac4c2bb4daa58da0114a96;suman@07ac4c2bb4daa58da0114a96). Digital Object Identi?er10.1109/TNET.2010.2042727Fig.1.Illustration of network coding.

with2being the intended recipient;ii)packet is transmitted by3,with2being the intended recipient;iii)packet is trans-mitted by2,with3being the intended recipient;and iv)packet is transmitted by2,with1being the intended recipient.

In comparison,using a simple form of network coding(as employed in the COPE approach[10]),the same two packets can be transferred by using three wireless transmissions instead of four using the following sequence:i)1transmits packet, with2being the intended recipient;ii)3transmits packet with 2being the intended recipient;and iii)node2transmits a new packet obtained by performing an XOR of packets and. Both nodes1and3are intended recipients of this new packet. Wireless medium being inherently broadcast in nature allows such communication to be possible.Assuming node1still has a copy of packet,it can obtain packet by performing an XOR of packets and.Similarly,node3can obtain packet by performing an XOR of packets and.Overall,this simple form of network coding achieved the same packet transfer effect on this two-hop path by using three transmissions instead of four and would lead to a throughput improvement of33%in this 07ac4c2bb4daa58da0114a96ing prior terminology[10],we will refer to the original packets(and)as native packets and the packet derived as a combination of native packets as a coded packet. In this paper,we focus on network coding as applicable to a multihop wireless network where there are multiple concurrent unicast sessions.We provide a theoretical framework for inves-tigating the potential interactions between coding opportunities and routing decisions.Our goal is to develop techniques for sys-tematically quantifying the bene?ts of network coding-aware routing across arbitrary wireless network topologies and traf?c demands.We use a COPE-type network coding scheme for uni-cast traf?c that exploits the broadcast nature of the wireless medium.More speci?cally,we study the following related set of issues in this paper.

Estimating Coding Bene?ts:Given any wireless topology,a set of traf?c demands,and a coding-oblivious1routing strategy 1Coding-oblivious routing implies that routing decisions are not made based on coding opportunities available.This approach requires no change in existing routing mechanisms.

1063-6692/$26.00?2010IEEE

Authorized licensed use limited to: Tsinghua University Library. Downloaded on April 20,2010 at 12:00:33 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

2IEEE/ACM TRANSACTIONS ON

NETWORKING

Fig.2.Coding-oblivious versus coding-aware routing.

(e.g.,based on shortest-hop routing,ETX[3],and WCETT

[5]),what is the potential bene?t of using network coding on end-to-end throughput?Note that this question assumes that the routing decisions are made by an independent routing protocol and our goal is to quantify bounds on throughput gains of network coding under this scenario.

Coding-Aware(and Interference-Aware)Routing:Prior work has shown that wireless routing protocols need interfer-ence(and link-quality)awareness for improved performance [3],[5],[9].Introduction of network coding,therefore,raises new questions in the route selection process—should routing decisions now need to be aware of coding opportunities,and if so,what are the approaches to design coding-aware routing in wireless networks?

We illustrate the new opportunity presented by network coding in the context of route selection using a simple example (Fig.2).The example shows two?ows,one from node1to node4and the other from node4to node5.The link transmis-sion rates are set to1unit,and the value of each?ow is also set to1unit.If we assume a simple scenario where there are no losses on these wireless links,then Fig.2(a)shows the best paths for the two?ows in absence of network coding.These are the shortest and minimum interference paths for the?ows, which result in an end-to-end throughput of0.25.However, if the nodes are allowed to perform network coding,then the throughput of these?ows can be improved by choosing paths for the two?ows as shown in Fig.2(b).Note that such a choice increases the path overlap of the two?ows to increase coding 07ac4c2bb4daa58da0114a96ing the techniques developed in this paper,it can be shown that routing the?ows as in Fig.2(b)results in a throughput of0.3325,an improvement of33%compared to the previous case.

Clearly,there is a tradeoff between routing choices that facil-itate more coding and routing choices that mitigate interference in the network.We,therefore,present a systematic approach for choosing routes that optimize the tradeoffs between the con-?icting effects of increased coding opportunities and increased wireless interference.

Impact of Multipath Routing:Many network traf?c engineering techniques have shown that multipath routing approaches are known to better utilize the capacity of any network.Therefore,in this paper,we consider coding aware multipath routing.More speci?cally,we study how the ability to route traf?c demands along multiple paths is enhanced by the ability to code packets inside the wireless network.Our formulations can also be used in single-path routing scenarios where a path needs to be determined in a coding-aware manner or is computed based on a coding-oblivious metric like ETX. We answer all of these questions in the context of an oppor-tunistic network coding scheme such as COPE[10].COPE uses the easy-to-implement and relatively inexpensive XOR opera-tion to perform coding.In addition,COPE’s approach to net-work coding has two other attractive properties.

1)Opportunistic Coding:Each wireless node uses only

packets in its local queues for coding(the rules are de-scribed in Section II-B).This allows bene?ts of network coding through local decisions without requiring any form of global coordination between different nodes.

2)Opportunistic Listening:Exploiting the broadcast nature

of the wireless medium,COPE sets each node into a promiscuous mode to snoop on all packets communicated by its neighbors.The snooped packets are used in coding decisions.

We illustrate the advantage of opportunistic listening using the example in Fig.1(b),where there are four intended packet transfers as follows:from1to3,3to1,4to5,and5to4.Due to range limitations,all transfers need to go via node2.Let us as-sume that nodes1,3,4,and5transmit their packets in sequence to packet2.When node1transmits its packet to node2,nodes4 and5,in promiscuous mode,snoop on the packet.Similarly, when node4transmits its packet to2,nodes1and3snoop on this packet.Therefore,at the end of these four packet transmis-sions,if node2were to transmit a single coded packet that XORs all of the four packets,then each node(1,3,4,and5)would be able to correctly decode their intended packets.Thus,the packet transfers are completed by using just?ve packet trans-missions.Note that in absence of coding,eight packet transmis-sions would have been necessary,while coding without oppor-tunistic listening would have required six.

A.Prior Work on Network Coding

The notion of network coding was?rst proposed by Ahlswede et al.[1]for achieving the min-cut capacity in the context of multicast communication.Since then,a large body of work has explored ef?cient construction of network codes,e.g.,[2], [4],[11],[15],and[18].In[22],the authors provide a linear optimization-based approach for network code construction for multiple unicasts.In the context of wireless networks,Lun et al.

[16],[17]studied the problem of minimum-cost(energy)mul-ticast involving a single session with a single source node. Ramamoorthy et al.[19]derived results for maximum?ow achievable in random wireless networks(modeled as geometric random graphs)for a similar single multicast session with a single source.

Li et al.[13],[14]show that in some multihop wireless sce-narios with multiple unicast sessions,network coding would provide marginal bene?ts over traditional approaches that do not involve network coding.Ho et al.[8]consider network coding across multiple unicasts within the class of network codes re-stricted to XOR coding between pairs of?ows.To the best of our knowledge,there is no prior work analyzing the bene?ts of COPE-type opportunistic network coding for unicast traf?c in wireless networks or making routing decisions aware of coding opportunities.

Authorized licensed use limited to: Tsinghua University Library. Downloaded on April 20,2010 at 12:00:33 UTC from IEEE Xplore. Restrictions apply.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. SENGUPTA et al.:NETWORK CODING-AWARE ROUTING IN WIRELESS NETWORKS3 A dynamic routing-scheduling-coding strategy for wireline

networks for serving multiple unicast sessions when linear net-

work coding is allowed across sessions is proposed in[26].Our

work differs in that it applies to wireless networks with broad-

cast capability,models the details of the COPE opportunistic

network coding protocol[10],and adds coding-aware routing

on top of it.

B.Unique Contributions of Our Work

Ours is the?rst work that provides a detailed analytical eval-

uation of a practical network coding approach,such as COPE,

that is applicable to wireless environments with multiple unicast

sessions.More speci?cally,our solutions are applicable to any

multihop wireless network topology and any pattern of concur-

rent unicast traf?c demands.Our results are valid both in pres-

ence and absence of opportunistic listening mechanisms.In con-

trast,the COPE paper[10]constructs and analyzes the best-case

bounds for reduction in number of transmissions with oppor-

tunistic network coding.

A second important contribution is that this paper introduces

the notion

of joint coding-aware and interference-aware routing

in multihop wireless networks.It illustrates the tradeoffs be-

tween needs of increased coding and decreased interference in

a systematic manner and identi?es ef?cient routing choices by

selecting the appropriate operating point.(Note that COPE does

not consider coding-aware routing.)

Finally,this paper illustrates how a coding approach such as

COPE can be integrated with a multipath routing solution to

further increase end-to-end throughput.

The dif?culty of the optimization problem tackled in this

paper arises from at least two aspects.First,for a given routing,

many combinations of coding opportunities at different nodes

are possible,and a subset needs to be selected from the avail-

able ones so as to optimize a global objective(e.g.,network

throughput).Second,when the routing is made aware of the

coding opportunities,it has to make choices between routing

?ows“close to each other”for utilizing coding opportunities

and“away from each other”for avoiding interference.

that we do not de?ne a full-?edged network coding

protocol in this paper,but instead focus on algorithmic anal-

ysis(using linear programming-based formulations)that quan-

ti?es potential bene?ts across arbitrary wireless topologies,de-

mands,as well as impact of joint network coding and interfer-

ence-aware routing techniques.Our framework and its evalua-

tion are fairly general—they properly model arbitrary interfer-

ence between wireless nodes,availability of different data rates,

link loss rates,and other usual practical phenomenon observed

in wireless environments.We believe our work provides inter-

esting insights to design protocols that integrate network coding

and routing selection techniques.

Independently,and in the same conference as[20],the au-

thors in[23]propose a link cost metric for routing in multihop

wireless networks that can utilize network coding opportunities.

Their work can be viewed as complementary to ours and can be

used for routing connections one at a time(as they arrive over

time)(i.e.,in an online setting)in a coding-aware manner.

C.Roadmap

The rest of the paper is structured as follows.In the next

section,we introduce notation and formally state the rules for

(COPE-type)network coding and our modeling assumptions.

In Section III,we consider how to schedule broadcast trans-

missions for network coding subject to wireless transmit/re-

ceive persity and link interference.In Section IV,we con-

sider maximum throughput coding-aware routing without op-

portunistic listening and give a linear programming formulation

for the multipath routing version of the problem.In Section V,

we add opportunistic listening to our optimization framework.

In Section VII,using the theoretical formulations developed,

we evaluate the bene?ts of network coding(with and without

coding-aware routing)over traditional routing(without coding)

on various topologies,including some derived from real mesh

network testbed deployments.

II.N ETWORK C ODING:N OTATION AND M ODELING

A SSUMPTIONS

A.Notation

The wireless network topology,given by the nodes and the

links corresponding to pairs of nodes within direct communica-

tion range,is modeled as a graph with node set

and(directed)edge set.Each node in the network can be

a source or destination of traf?c.The sets of incoming and out-

going edges at node are denoted by and,respec-

tively.We let represent a directed link in the network

from node to node.The transmitting node for link will be

denoted by and its receiving node by.We will denote

the reverse of link by.The rate of trans-

mission on link will be denoted by and its delivery proba-

bility by.Thus,the effective rate of transmission on link is

.

Let be the set of demands.A demand has source

node,destination node,and traf?c value.For

given routing/coding scheme,the de?ned

maximum such with

values by can routed by

network.In we will be maximizing

the throughput for coding-aware network routing.

For a path and links,we will use to denote

that link is on path and to denote that path

contains link followed by link in consecutive order(this

assumes).For a path and node,we will use

to denote that node is on path.

B.Coding Rules and Modeling Assumptions

Consider packets at a node that have distinct

next-hop nodes,respectively.Suppose these are

coded together to form the coded packet

that is broadcast to all the above next-hop nodes.This is a

valid network coding if the next-hop node for each packet

already has all other packets for(so that it can decode

).This can happen if:

1)node is the previous-hop node of packet;or

2)node overheard packet from the transmission of its

previous-hop node(opportunistic listening).

Authorized licensed use limited to: Tsinghua University Library. Downloaded on April 20,2010 at 12:00:33 UTC from IEEE Xplore. Restrictions apply.

本文来源：https://www.bwwdw.com/article/htal.html