Georouting in ad hoc netsGeo routing – key elementsFinding the most forward neighborGot stuck? Perimeter forwardingGreedy Perimeter ForwardingGPSR vs DSRGPRS commentaryGeographic Random Forwarding (GeRaF) M.Zorzi and R.R.RaoKeeping track of on/off nodesGeRaF: Key IdeaPractical ImplementationContention ResolutionFewer Hops than GAFConclusionsMobility assisted routingMobility Diffusion and “last encounter” routingSlide 17Mobility induced, distributed embedded route/directory treeGeorouting in ad hoc nets•References:•Brad Karp and H.T. Kung “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks”, Mobicom 2000•M. Zorzi, R.R. Rao, ``Geographic Random Forwarding (GeRaF) for ad hoc and sensor networks: energy and latency performance,'' IEEE Trans. on Mobile Computing, vol. 2, Oct.-Dec. 2003 •H. Dubois Ferriere et al ”Age Matters: Efficient Route discovery in Mobile Ad Hoc Networks Using Enounter ages”, Mobihoc June 2003Geo routing – key elements•Greedy forwarding–Each nodes knows own coordinates–Source knows coordinates of destination–Greedy choice – “select” the most forward nodeFinding the most forward neighbor•Beaconing: periodically each node broadcasts to neighbors own {MAC ID, IP ID, geo coordinates}•Each data packet piggybacks sender coordinates•Alternatively (for low energy, low duty cycle ops) the sender solicits “beacons” with “neighbor request” packetsGot stuck? Perimeter forwardingGreedy Perimeter ForwardingD is the destination; x is the node where the packet enters perimeter mode; forwarding hops are solid arrows;GPSR vs DSRGPRS commentary•Very scalable:–small per-node routing state –small routing protocol message complexity–robust packet delivery on densely deployed, mobile wireless networks•Outperforms DSR•Drawback: it requires explicit forwarding node address–Beaconing overhead–nodes may go to sleep (on and off)Geographic Random Forwarding (GeRaF)M.Zorzi and R.R.Rao•Nodes in turns go to sleep and wake up, source does not know which nodes are on/off•Source cannot explicitly address the next hop, must randomly select•ideally, the best available node to act as a relay is chosen•this selection is done a posteriori, i.e., after the transmission has taken place•it is a receiver contention schemeKeeping track of on/off nodes•Related work•SPAN: in a dense environment, multiple subnets which guarantee connectivity are present, can be alternated•GAF: area divided in grids so that within each grid any node will do (equivalent for routing)GeRaF: Key IdeaGoal: pick the relay closest to the destinationbroadcast message is sent, all active nodes within range receive itcontention phase takes place: nodes closer to the destination are likely to winthe winner becomes itself the sourcePractical Implementation•major problem: how to pick the best relay?•solution: partition the area and pick relays from slice closest to the destination•nodes can determine in which region they are•nodes in highest priority region contend firstContention Resolution•Assume 802.11 RTS/CTS •Source transmits RTS with source and destination coordinates•Stations in priority region #1 are solicited•If none responds, stations in region #2 are solicitedFewer Hops than GAFall distances normalized to the coverage radiusConclusions•nodes who receive a message volunteer and contend to act as relays•advantages:–no need for complicated routing tables or routing-related signaling–near-optimal multihop behavior, much better than alternative solutions (eg GAF, SPAN)–significant energy/latency gains if nodes are densely deployedMobility assisted routing•Mobility (of groups) was helpful to scale the routing protocol – see LANMAR•Can mobility help in other cases?•(a) Mobility induced distributed route/directory tree•(b) Destination discovery (if coordinates not know)Mobility Diffusion and “last encounter” routing•Imagine a roaming node “sniffs” the neighborhood and learns/stores neighbors’ IDs•Roaming node carries around the info about nodes it saw before•If nodes move randomly and uniformly in the field (and the network is dense), there is a trail of nodes – like pointers – tracing back to each ID•The superposition of these trails is a tree – it is a routing tree (to send messages back to source); or a distributed directory system (to map node ID to geo-coordinates, for example)•“Last encounter” routing: next hop is the node that last saw the destination•Ref: H. Dubois Ferriere et al”Age Matters: Efficient Route discovery in Mobile Ad Hoc Networks Using Enounter ages, Mobihoc June 2003.Fresh algorithm – H. Dubois Ferriere, Mobihoc 2003Mobility induced, distributed embedded route/directory treeBenefits: •(a) avoid overhead of periodic advertising of node location (eg, Landmark routing) •(b) reduce flood search O/H (to find ID)•(c ) avoid registration to location server (to DNS, say)Issue:•Motion pattern impact (localized vs random
View Full Document
Unlocking...