ExOR: Opportunistic Multi-Hop Routing for WirelessNetworksSanjit Biswas and Robert MorrisM.I.T. Computer Science and Artifical Intelligence Laboratorybiswas, rtm @csail.mit.eduABSTRACTThis paper describes ExOR, an integrated routing and MACprotocol that increases the throughput of large unicast trans-fers in multi-hop wireless networks. ExOR chooses each hopof a packet’s route after the transmission for that hop, sothat the choice can reflect which intermediate nodes actuallyreceived the transmission. This deferred choice gives eachtransmission multiple opportunities to make progress. As aresult ExOR can use long radio links with high loss rates,which would be avoided by traditional routing. ExOR in-creases a connection’s throughput while using no more net-work capacity than traditional routing.ExOR’s design faces the following challenges. The nodesthat receive each packet must agree on their identities andchoose one forwarder. The agreement protocol must havelow overhead, but must also be robust enough that it rarelyforwards a packet zero times or more than once. Finally,ExOR must choose the forwarder with the lowest remainingcost to the ultimate destination.Measurements of an implementation on a 38-node 802.11btest-bed show that ExOR increases throughput for mostnode pairs when compared with traditional routing. Forpairs between which traditional routing uses one or twohops, ExOR’s robust acknowledgments prevent unnecessaryretransmissions, increasing throughput by nearly 35%. Formore distant pairs, ExOR takes advantage of the choice offorwarders to provide throughput gains of a factor of two tofour.Categories and Subject DescriptorsC.2.2 [Computer Communications Networks]: NetworkProtocols—Routing Protocols ; C.2.1 [Computer Commu-nications Networks]: Network Architecture and Design—Wireless CommunicationGeneral TermsAlgorithms, Experimentation, PerformancePermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SIGCOMM’05, August 21–26, 2005, Philadelphia, Pennsylvania, USA.Copyright 2005 ACM 1-59593-009-4/05/0008 ...$5.00.Keywordswireless, mesh, 802.111. INTRODUCTIONMulti-hop wireless networks typically use routing tech-niques similar to those in wired networks [15, 16, 9, 4, 5].These traditional routing protocols choose the best sequenceof nodes between the source and destination, and forwardeach packet through that sequence. In contrast, cooperativediversity schemes proposed by the information theory com-munity [20, 14] suggest that traditional routing may not bethe best approach. Cooperative diversity takes advantage ofbroadcast transmission to send information through multi-ple relays concurrently. The destination can then choose thebest of many relayed signals, or combine information frommultiple signals. These schemes require radios capable ofsimultaneous, synchronized repeating of the signal [18], oradditional radio channels for each relay [11].This paper describes ExOR, an integrated routing andMAC technique that realizes some of the gains of cooper-ative diversity on standard radio hardware such as 802.11.ExOR broadcasts each packet, choosing a receiver to forwardonly after learning the set of nodes which actually receivedthe packet. Delaying forwarding decisions until after recep-tion allows ExOR to try multiple long but radio lossy linksconcurrently, resulting in high expected progress per trans-mission. Unlike cooperative diversity schemes, only a singleExOR node forwards each packet, so that ExOR works withexisting radios.The key challenge in realizing ExOR is ensuring that onlythe “best” receiver of each packet forwards it, in order toavoid duplication. ExOR operates on batches of packetsin order to reduce the communication cost of agreement.The source node includes in each packet a list of candidateforwarders prioritized by closeness to the destination. Re-ceiving nodes buffer successfully received packets and awaitthe end of the batch. The highest priority forwarder thenbroadcasts the packets in its buffer, including its copy of the“batch map” in each packet. The batch map contains thesender’s best guess of the highest priority node to have re-ceived each packet. The remaining forwarders then transmitin order, but only send packets which were not acknowledgedin the batch maps of higher priority nodes. The forwarderscontinue to cycle through the priority list until the desti-nation has 90% of the packets. The remaining packets aretransferred with traditional routing.Measurements of an ExOR implementation on a 32-node133...21100srcdstFigure 1: Example in which each of the source’stransmissions has many independent chances of be-ing received by an intermediate node.802.11b test-bed show that ExOR performs better than tra-ditional routing for almost all node pairs, typically boostingend-to-end throughput by a factor of two. The paper in-vestigates the conditions under which ExOR performs well,and the reasons for that performance.This paper contributes the first complete design and im-plementation of a link/network-layer diversity routing tech-nique that uses standard radio hardware. It demonstratesa substantial throughput improvement and provides insightinto the sources of that improvement.The rest of the paper is organized as follows. Section 2describes the basic idea behind ExOR. Section 3 presentsExOR’s design, followed by Section 5, which presents anevaluation of ExOR’s performance. Section 6 describes re-lated work, and Section 7 concludes.2. BASIC IDEAA simplified version of ExOR might work as follows. Asource node has a packet that it wishes to deliver to a distantdestination. Between the source and destination are otherwireless nodes willing to participate in ExOR. The sourcebroadcasts the packet. Some sub-set of the nodes receive thepacket. The nodes run a protocol to discover and agree onwhich nodes are in that sub-set. The node in the sub-set thatis closest to the destination broadcasts the packet. Again,the nodes that receive this second transmission agree on theclosest receiver, which broadcasts the packet. This processcontinues until the destination has received the
View Full Document
Unlocking...