Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 241Location-Aided Routing (LAR) in Mobile Ad Hoc NetworksYoung-Bae Ko and Nitin H. VaidyaYu-Ta Chen2006 Advanced Wireless Network2Basic IdeaRoute discovery using flooding algorithm:CDBSEAX3Basic Idea (cont.)Location informationMinimize the search zoneReduce the number of routing messagesSpeed and direction informationMore minimization of the search zoneIncreases the probability to find a node4Basic Idea (cont.)Each node knows its current locationUsing last known location information and average speed for route discoveryLimited destination zone – expected zoneRestricted flooding – request zoneRoute discovery is initiated whenSource does not know a route to destinationPrevious route from source to destination is broken5DefinitionsExpected zoneS knows the location of D at time t0Current time is t1The location of D at t1 is the expected zone6Expected ZoneNo direction informationDirection information: moving toward north7Definitions (cont.)Request zoneS defines a request zone for the route requestThe request zone includes expected zoneThe route request messages only flood in request zoneIf S can not find a route within the timeout interval, create a expanded request zone8Request Zone9LAR Scheme 1The request zone is the smallest rectangle to include the expected zone and the location of sourceS Includes the coordinates of corners and location of D(t0) in routing messagesThe node outside the rectangle should not forward route message to neighborsWhen D receives the message, it replies a route reply message including its current location and current timeWhen S receives the route reply message, it records the location of node D.10LAR Scheme 1 (example)Network SpaceExpected zoneA (Xs, Yd+R)(Xd, Yd)Request zoneB (Xd+R, Yd+R)S (Xs, Ys)D (Xd+R, Ys)RSource node outside the expected zoneI (Xi, Yi)J (Xj, Yj)D11LAR Scheme 1 (example)Network SpaceExpected zoneA (Xd-R, Yd+R)(Xd, Yd)S (Xs, Ys)Request zoneB (Xd+R, Yd+R)C (Xd-R, Yd-R)D (Xd+R, Yd-R)RSource node within the expected zoneD12LAR Scheme 2The distance between S and D is DISTsS includes DISTs and (Xd, Yd) in route request messageWhen node I receives route requestCalculates its distance to D (DISTi)If DISTs+δ DISTi then forwards the request and replace DISTs by DISTiOtherwise, node I discards the route requestδ is a parameter for increasing the probability of finding a route or dealing with location errorThe request is forwarded closer and closer to destination D13LAR Scheme 2 (example)Network SpaceD (Xd, Yd)S (Xs, Ys)NIKDISTnDISTsDISTiDISTkParameter δ= 014Error in Location EstimateImpact of location errorGPS may include some errorWith a larger location error, the size of request zone increasesUsually location error contributes to an increase in routing overheadBut routing overhead may decrease with increasing error, why?In LAR scheme 1, radius of expected zone = e + v(t1 – t0), e is location errorIn LAR scheme 2, there is no modification15Simulation ResultDifferent average speed of nodes# of Routing packets per Data packetPercentage of Improvement16Simulation Result (cont.)Different transmission range of nodes# of Routing packets per Data packet# of Routing packets per Data packet17Simulation Result (cont.)Different number of nodes in network# of Routing packets per Data packet# of Routing packets per Data packet18Simulation Result (cont.)Different location error# of Routing packets per Data packetPercentage of ImprovementLocation Error (units)Location Error (units)19Simulation Result (cont.)LAR perform better in various speedEspecially in high speedLAR perform better in various transmission rangeException: very low transmission rateLAR perform better in various amount of nodesException: small amount of nodes20Variations and OptimizationsAlternative definition of request zone in LAR scheme 1DExpected ZoneAlternative Request ZoneOriginal Request ZoneS21Variations and Optimizations (cont.)Adaptation of request zoneIf an intermediate node I holds a more recent location information of D, it can update the request zoneDSIJAdapted Request Zone as per node JAdapted Request Zone as per node IInitial Request Zone22Variations and Optimizations (cont.)Adaptation of request zoneEven though LAR scheme 2 does not explicitly define request zone, the zone that the source node ask can be seen as a circular zoneDSIDISTsDISTi23Variations and Optimizations (cont.)Local searchAllow any intermediate node I detecting route error to initiate a route discoveryNode I uses a request zone based on its own location information for node DSISIDDRequest Zone determined by S Request Zone determined by I24ConclusionLocation information significantly lower routing overheadVarious optimizations can be done to adjust LAR to a certain