4003-543/4005-742 Ad Hoc Networks Module 5. Location Awareness -- Lecture Notes Prof. Alan Kaminsky Rochester Institute of Technology -- Department of Computer Science Determining Location Global Positioning System (GPS) Pro: Highly accurate Con: Inaccurate or unusable indoors Con: Somewhat expensive (although GPS receivers are getting cheaper)   RFID and similar technologies Pro: Highly accurate Pro: Cheap Con: Very short range   Triangulation or trilateration with known beacon locations Triangulation is based on the angles to the beacons Trilateration is based on the distances to the beacons See "Trilateration" (PDF, 45,320 bytes)   Determining inter-node angles or distances for use in triangulation or trilateration Signal strength measurements Example: Cellular telephones Pitfalls: Not very accurate Time of flight (ToF) measurements Example: GPS Pitfalls: Requires transmitter's and receiver's clocks to be synchronized Round trip time (RTT) measurements Pitfalls: Requires bidirectional connectivity Direction of arrival (DoA) measurements Pitfalls: Requires directionally sensitive (i.e. more complicated) antennas Common pitfalls Shadowing (non-line-of-sight) Multipath Location Aware Ad Hoc Routing Martin Mauve et al. A survey on position-based routing in mobile ad hoc networks. IEEE Network, 15(6):30-39, November 2001.   Two issues Location service Routing algorithm   Location service: Determine the location of a given node Alternative: Use a central (sessile) location server or servers Alternative: Each node floods its location to all nodes periodically Alternative: Each node sends its location to a subset of the nodes periodically; to find a location, a node queries nearby nodes   Routing algorithm: Forward packets based on location   Greedy routing Forward to the nearest reachable node that is closer to the destination than this node Forward to the farthest reachable node that is closer to the destination than this node Forward to the reachable node that is closest to the line between this node and the destination All these schemes fail if this node is closer to the destination than any other nearby node In that case some kind of recovery strategy is needed to backtrack and find an alternate route   Restricted directional flooding Determine region where destination could be, based on (mobile) destination's speed and direction Flood packet to all adjacent nodes in the cone between this node and the destination region that are closer to the destination Again, this scheme fails if there is no adjacent node that meets the criteria, and a recovery strategy is necessary   Location Aided Routing An add-on to a reactive ad hoc routing protocol like DSR Don't flood route request packets to every node Only flood route request packets to nodes in a "request zone" between the source and the destination   Hierarchical routing Use a regular (non-location-aware) ad hoc routing protocol to route between nearby nodes, e.g. reactive DSR Use a location-aware ad hoc routing protocol to route between far away nodes, e.g. greedy routing Location Aware Applications TBD Ad Hoc Networks • 4003-543-01/4005-742-01 • Spring Quarter 2007 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2006 Alan Kaminsky. All rights reserved. Last updated 01-May-2006. Please send comments to ark­@­cs.rit.edu.