05-05-2011, 12:37 PM
Abstract
Two major factors that limit the throughput inmulti-hop wireless networks are the unreliability of wirelesstransmissions and co-channel interference. One promising techniquethat combats lossy wireless transmissions is opportunisticrouting (OR). OR involves multiple forwarding candidates torelay packets by taking advantage of the broadcast nature andspacial diversity of the wireless medium. Furthermore, recentadvances in multi-radio multi-channel transmission technologyallows more concurrent transmissions in the network, and showsthe potential of substantially improving the system capacity.However, the performance of OR in multi-radio multi-channelmulti-hop networks is still unknown, and the methodology ofstudying the performance of traditional routing (TR) can not bedirectly applied to OR. In this paper, we present our researchon computing an end-to-end throughput bound of OR in multiradiomulti-channel multi-hop wireless networks. We formulatethe capacity of OR as a linear programming (LP) problem whichjointly solves the radio-channel assignment and transmissionscheduling. Leveraging our analytical model, we gain the followinginsights into OR: 1) OR can achieve better performancethan TR under different radio/channel configurations, however,in particular scenarios, TR is more preferable than OR; 2) ORcan achieve comparable or even better performance than TRby using less radio resource; 3) for OR, the throughput gainedfrom increasing the number of potential forwarding candidatesbecomes marginal.
I. INTRODUCTION
Multi-hop wireless networks have attracted increasing attentionin recent years owing to its easy deployment andwide range of applications. Two major factors that limit thethroughput in multi-hop wireless networks are the unreliabilityof wireless transmissions and co-channel interference. Onepromising network-MAC cross-layer design to improve thewireless network throughput is opportunistic routing (OR)[1]–[7], which involves multiple forwarding candidates ateach hop, and the actual forwarder is selected after packettransmission according to the instant link reachability andavailability. It is quite different from the traditional routing(TR) that only one pre-selected next-hop node is involvedto forward packets at each hop. It has been shown thatOR achieves much higher throughput than TR in multi-hopwireless networks [1], [4], [7]. Furthermore, with the spurof modern wireless technologies, another way to improvesystem throughput is to allow more concurrent transmissionsby installing multiple radio interfaces on one node with eachradio tuned to a different orthogonal channel [8]–[10].This work was supported in part by the US National Science Foundationunder grants CNS-0746977, CNS-0716306, and CNS-0831628.When merging these two techniques, an interesting questionarises that “what is the end-to-end throughput bound orcapacity of OR in multi-radio multi-channel systems?”. In thispaper, we will propose a methodology to answer this question.In order to maximize the end-to-end throughput of ORin multi-radio multi-channel multi-hop networks, we shouldjointly address multiple issues: radio-channel assignment,transmission scheduling, and opportunistic forwarding strategy.In this paper, we carry out a comprehensive study onthese issues. We formulate the capacity of OR as a linearprogramming (LP) problem which jointly solves the radiochannelassignment and transmission scheduling. Leveragingour analytical model, we gain the following insights intoOR: 1) OR can achieve better performance than TR underdifferent radio/channel configurations, however, in particularscenarios, TR can be more preferable than OR; 2) OR canachieve comparable or even better performance than TR byusing less radio resource; 3) for OR, the throughput gainedfrom increasing the number of potential forwarding candidatesbecomes marginal.The rest of this paper is organized as follows. Section IIintroduces the system model and opportunistic routing. Wepropose the framework of computing the throughput boundsof OR in multi-radio multi-channel multi-hop networks inSection III. Examples and simulation results are presented andanalyzed in Section IV. Conclusions are drawn in Section V.
II. SYSTEM MODEL AND OPPORTUNISTIC ROUTINGPRIMER
We consider a multi-hop wireless network with N nodes.Each node ni (1 ≤ i ≤ N) is equipped with one or morewireless interface cards, referred to as radios in this work.Denote the number of radios in each node ni as ti (i =1...N ). Assume K orthogonal channels are available in thenetwork without any inter-channel interference. We considerthe system with channel switching capability, such that a radiocan dynamically switch across different channels. We assumethere is no performance gain to assign the same channel to thedifferent radios on the same node. For simplicity, we assumeeach node ni transmits at the same data rate Ri among allits radios and channels. We also assume half-duplex on eachradio, that is, a radio can not transmit and receive packetsat the same time. There is a unified transmission range RTand interference range RI for the whole network. Typically,RI > RT . Two nodes, ni and nj , can communicate witheach other if the Euclidean distance dij between them is lessthan RT and they are operated on the same channel.
Download full report
http://www.cs.ucdavis.edu/~kzeng/Publica...com-10.pdf
Two major factors that limit the throughput inmulti-hop wireless networks are the unreliability of wirelesstransmissions and co-channel interference. One promising techniquethat combats lossy wireless transmissions is opportunisticrouting (OR). OR involves multiple forwarding candidates torelay packets by taking advantage of the broadcast nature andspacial diversity of the wireless medium. Furthermore, recentadvances in multi-radio multi-channel transmission technologyallows more concurrent transmissions in the network, and showsthe potential of substantially improving the system capacity.However, the performance of OR in multi-radio multi-channelmulti-hop networks is still unknown, and the methodology ofstudying the performance of traditional routing (TR) can not bedirectly applied to OR. In this paper, we present our researchon computing an end-to-end throughput bound of OR in multiradiomulti-channel multi-hop wireless networks. We formulatethe capacity of OR as a linear programming (LP) problem whichjointly solves the radio-channel assignment and transmissionscheduling. Leveraging our analytical model, we gain the followinginsights into OR: 1) OR can achieve better performancethan TR under different radio/channel configurations, however,in particular scenarios, TR is more preferable than OR; 2) ORcan achieve comparable or even better performance than TRby using less radio resource; 3) for OR, the throughput gainedfrom increasing the number of potential forwarding candidatesbecomes marginal.
I. INTRODUCTION
Multi-hop wireless networks have attracted increasing attentionin recent years owing to its easy deployment andwide range of applications. Two major factors that limit thethroughput in multi-hop wireless networks are the unreliabilityof wireless transmissions and co-channel interference. Onepromising network-MAC cross-layer design to improve thewireless network throughput is opportunistic routing (OR)[1]–[7], which involves multiple forwarding candidates ateach hop, and the actual forwarder is selected after packettransmission according to the instant link reachability andavailability. It is quite different from the traditional routing(TR) that only one pre-selected next-hop node is involvedto forward packets at each hop. It has been shown thatOR achieves much higher throughput than TR in multi-hopwireless networks [1], [4], [7]. Furthermore, with the spurof modern wireless technologies, another way to improvesystem throughput is to allow more concurrent transmissionsby installing multiple radio interfaces on one node with eachradio tuned to a different orthogonal channel [8]–[10].This work was supported in part by the US National Science Foundationunder grants CNS-0746977, CNS-0716306, and CNS-0831628.When merging these two techniques, an interesting questionarises that “what is the end-to-end throughput bound orcapacity of OR in multi-radio multi-channel systems?”. In thispaper, we will propose a methodology to answer this question.In order to maximize the end-to-end throughput of ORin multi-radio multi-channel multi-hop networks, we shouldjointly address multiple issues: radio-channel assignment,transmission scheduling, and opportunistic forwarding strategy.In this paper, we carry out a comprehensive study onthese issues. We formulate the capacity of OR as a linearprogramming (LP) problem which jointly solves the radiochannelassignment and transmission scheduling. Leveragingour analytical model, we gain the following insights intoOR: 1) OR can achieve better performance than TR underdifferent radio/channel configurations, however, in particularscenarios, TR can be more preferable than OR; 2) OR canachieve comparable or even better performance than TR byusing less radio resource; 3) for OR, the throughput gainedfrom increasing the number of potential forwarding candidatesbecomes marginal.The rest of this paper is organized as follows. Section IIintroduces the system model and opportunistic routing. Wepropose the framework of computing the throughput boundsof OR in multi-radio multi-channel multi-hop networks inSection III. Examples and simulation results are presented andanalyzed in Section IV. Conclusions are drawn in Section V.
II. SYSTEM MODEL AND OPPORTUNISTIC ROUTINGPRIMER
We consider a multi-hop wireless network with N nodes.Each node ni (1 ≤ i ≤ N) is equipped with one or morewireless interface cards, referred to as radios in this work.Denote the number of radios in each node ni as ti (i =1...N ). Assume K orthogonal channels are available in thenetwork without any inter-channel interference. We considerthe system with channel switching capability, such that a radiocan dynamically switch across different channels. We assumethere is no performance gain to assign the same channel to thedifferent radios on the same node. For simplicity, we assumeeach node ni transmits at the same data rate Ri among allits radios and channels. We also assume half-duplex on eachradio, that is, a radio can not transmit and receive packetsat the same time. There is a unified transmission range RTand interference range RI for the whole network. Typically,RI > RT . Two nodes, ni and nj , can communicate witheach other if the Euclidean distance dij between them is lessthan RT and they are operated on the same channel.
Download full report
http://www.cs.ucdavis.edu/~kzeng/Publica...com-10.pdf