Coping with Communication Gray Zonesin IEEE 802.11b based Ad hoc NetworksHenrik [email protected] Nordströ[email protected] [email protected] of Information TechnologyUppsala UniversityS-751 05 Uppsala, SwedenABSTRACTOur experiments with IEEE 802.11b based wireless ad hocnetworks show that neighbor sensing with broadcast mes-sages introduces “communication gray zones”: in such zonesdata messages cannot be exchanged although the HELLO mes-sages indicate neighbor reachability. This leads to a system-atic mismatch between the route state and the real worldconnectivity, resulting in disruptive behavior for multi-mediadata transfer over ad hoc routing protocols. Concentratingon AODV we explore this issue and evaluate three differenttechniques to overcome the gray zone problem. We presentquantitative measurements of these improvements and dis-cuss the consequences for ad hoc routing protocols and theirimplementations.Categories and Subject DescriptorsC.2.1 [Computer-Communication Networks]: NetworkArchitecture and Design—wireless communication; C.2.2 [Computer-Communication Networks]: Net-work Protocols—routing protocolsGeneral TermsDesign, Experimentation, Measurement, PerformanceKeywordsCommunication gray zone, gray zone, IEEE 802.11b, MANET,mobile ad hoc networks, real-world experiment, routing pro-tocols1. INTRODUCTIONWireless ad hoc networks consist of autonomous mobilenodes which provide a joint network service. The involvedrouting protocols must detect multihop paths and, in therange of a few seconds or below, react on changes in thetopology. Such timing requirements and the characteristicsPermission 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.WoWMoM’02, September 28, 2002, Atlanta, Georgia, USA.Copyright 2002 ACM 1-58113-474-6/02/0009 ...$5.00.of wireless links make conventional Internet routing proto-cols inappropriate for ad hoc networks.Several ad hoc routing protocols like DSR [6], AODV [13]or OLSR [5] have been proposed in the last 5 to 10 years.These protocols have been subject to intensive evaluationsthrough simulation, but far less effort has been documentedon the evaluation of the corresponding protocol implementa-tions. When we measured the performance of our own fullyconformant AODV implementation (called AODV-UU [2]),we observed an unexpected high amount of packet loss, es-pecially during route changes. We found that the increasedamount of packet loss coincided with specific geographic lo-cations that we call communication gray zones. Inside grayzones the packet loss is severe and applications with contin-uous packet flow, like streaming multi-media and large filetransfers, will suffer severe performance losses under suchcircumstances.Reproducing our tests and comparing them with the be-havior of the implementations of OLSR [12] and LUNAR [8]confirmed AODV-UU’s poor results. OLSR and LUNARwere chosen for comparison because of their availability andtheir different routing strategies. AODV is a reactive proto-col which discovers and maintains routes on demand. Whena route to an unknown node is needed AODV broadcasts aroute request that is disseminated through the network. Ifthe destination, or a fresh route to the destination, is founda route reply is unicasted back to the source. During thisprocess routes are set-up inside the traversed nodes’ routingtables. In addition, periodic broadcast HELLO beacons areused to sense neighboring nodes and based on this routescan be added, deleted or updated. OLSR is a proactive pro-tocol which senses the network topology in the 10-secondrange using broadcast messages. LUNAR is a hybrid proto-col as the on-demand discovery is combined with a proactiveroute re-discovery every third second. As with AODV, theroute requests are broadcasted while the route replies aresent via unicast.In this paper we show that gray zones are linked to the dif-ference between messages that are broadcasted (e.g., AODV’sHELLO messages) and the other unicast data packets. Threedifferent schemes counteracting the communication gray zoneswere added to AODV-UU, and their effectiveness was vali-dated through controlled real world measurements with Ping,MP3 streaming and intermittent HTTP traffic. We discussthese findings and how they relate to other ad hoc routingprotocols in general.The rest of the paper is outlined as follows. In Section 2we explain the gray zone problem and why it appears. InSection 3 we describe three mechanisms that reduce or elim-inate the gray zone problem. Results from experiments withthe enhanced AODV-UU implementation are reported inSection 4 before discussing and concluding our findings inSections 5 and 6, respectively.2. COMMUNICATION GRAY ZONESComparisons of MANET routing protocols based on sim-ulations, which often present AODV in a favorable man-ner with good performance, are readily available, such asthose in [4] and [7]. However, these findings could not bereproduced in real world: We observed strange performanceproblems of the AODV-UU implementation. In this sec-tion we explain how the problem of “communication grayzones” manifests itself and why AODV’s standard HELLOmessages are inappropriate for neighbor sensing when us-ing IEEE 802.11b. We also discuss why this problem is notevident in simulations using ns-2.2.1 Performance Problems of Original AODVWe compared the performances of AODV-UU with thosefor OLSR [12] and LUNAR [8] in identical scenarios. In mostcases AODV-UU performed better than OLSR, but that waswhat we expected because OLSR suffers from a 10 secondsre-route time. LUNAR and AODV-UU were approximatelyon par in most tests, but as the LUNAR implementation in-dicated some problems in stressed multi-hop configurationswe had expected AODV-UU to win those contests. However,a more careful analysis of the AODV-UU results indicatedthat in some specific locations a node could have a validroute in its routing table, but no data got through to thatnext hop. We call the areas where we experienced this prob-lem communication gray zones. In such gray zones, a nodewill experience considerable packet loss. The