Ad Hoc Networks Issues and Routing Raj Jain Washington University in Saint Louis Saint Louis MO 63130 Jain cse wustl edu Audio Video recordings of this lecture are available at http www cse wustl edu jain cse574 10 Washington University in St Louis CSE574s 19 1 2010 Raj Jain Overview Characteristics Applications Issues Cellular vs Ad Hoc Routing Requirements parameters classification Dynamic Source Routing DSR Ad Hoc On demand Distance Vector AODV Optimized Link State Routing OLSR Washington University in St Louis CSE574s 19 2 2010 Raj Jain Ad Hoc Networks Characteristics No Fixed Infrastructure Dynamic Topology Mobility Multi hopping Obstacles spectrum reuse energy conservation Self Organization Addressing routing clustering location power control Energy conservation Scalability Thousands of nodes Security Limited Bandwidth constrained Congestion is a norm Ref RFC2501 Washington University in St Louis CSE574s 2010 Raj Jain 19 3 Ad Hoc Networks Applications Emergency Disasters Wearable computing Battlefield Unmanned ground airborne underwater vehicles Hybrid Multi hop cellular Wireless Mesh Networks Sensor Networks Washington University in St Louis CSE574s 19 4 2010 Raj Jain Sensor Networks A large number of low cost low power multifunctional and small sensor nodes consisting of sensing data processing and communicating components Key Issues Internet 1 Scalability 2 Power consumption 3 Fault tolerance Task Sink Manager 4 Data Fusion 5 Traffic Low throughput Delay sensitive Washington University in St Louis CSE574s 19 5 Sensor Field 2010 Raj Jain Issues in Ad Hoc Networks 1 2 3 4 5 6 7 8 Medium Access Distributed no time sync directional antennas Routing Route acquisition delay quick reconfig loop free Multicasting Common in Ad Hoc Emergency military Transport Layer Frequent path breaks QoS Self organization Neighbor discovery report link failures Security DoS jamming energy depletion Energy management Transmission Power battery monitoring processor power 9 Addressing and Service Discovery Global 10 Pricing Scheme Incentives for relaying Washington University in St Louis CSE574s 19 6 2010 Raj Jain Cellular vs Ad Hoc Cellular Network Fixed Infrastructure Single hop wireless links Centralized routing Base station Single point of failure Seamless connectivity Ad Hoc Networks Infrastructure less Multi hop wireless links Distributed Routing Resilient Mobility Frequent link breaks Quick and cost effective setup High cost and long deployment time Commercial sector Simple Mobile Complex Base No forwarding fairness issues Time Sync TDMA Static frequency reuse cells Washington University in St Louis Defense Emergency Disaster All complexity in Mobile Fairness own vs other s traffic Time Sync difficult CSMA Dynamic freq reuse CSMA CSE574s 19 7 2010 Raj Jain Ad Hoc Media Access Control C A D C B A B Fully distributed operation CSMA Hidden Node Reachable from a receiving end of a link but not from the transmitting end A cannot hear C but can interfere with its transmissions to B Exposed Node Other nodes in the vicinity cannot talk When B is talking to A C cannot talk to D Use of Directional Antennas Steer able antennas Multiple Access Collision Avoidance MACA Use RTS CTS with Binary Back off e g 802 11 Washington University in St Louis CSE574s 19 8 2010 Raj Jain Ad Hoc Routing Requirements Fully distributed Global state all nodes all time maintenance expensive Localized Loop Free routing Minimize route acquisition delay Proactive Quick route reconfiguration Adaptive to Frequent changes Changes in unrelated parts should not impact a node Energy conservation Sleep periods Unidirectional Link Support Minimize Bits Transmitted Bits Delivered Avg hops Control bits data bits Overhead Control packets data packets Overhead Washington University in St Louis CSE574s 19 9 2010 Raj Jain Classification of Routing Protocols Routing Updates Proactive Before needed Reactive On demand Hybrid Combined Know neighbors Others on demand Temporal Information Past History Prediction Based on node lifetime location Topology Organization Flat Global addresses as in 802 11 Hierarchical Geographical or Hop distance Resource Optimization Power Aware Local or global battery power Geographical info based Efficient Flooding Murthy and Manoj list 40 routing schemes for Ad hoc nets Washington University in St Louis CSE574s 19 10 2010 Raj Jain Routing in Wired Networks Review 1 Distance Vector Each node sends its complete table distances to all nodes in the network to its neighbors Large vectors to small number of nodes Use Dijkstra s algorithm to compute the shorted path Routing Information Protocol RIP is a distance vector protocol 2 Link State Each nodes sends its link information distances to its neighbors to all nodes in the network Small vectors to large number of nodes Use Bellman Ford to compute the shortest path Open Shorted Path First OSPF is a link state routing protocol Washington University in St Louis CSE574s 19 11 2010 Raj Jain OLSR Optimized Link State Routing Protocol Proactive Routes are prepared before needed Optimize Min flooding duplication in highly connected nets Ask only a subset of your neighbors to forward your link states This is subset is your Multipoint Relay MPR If X is your MPR you are X s MPR selector Each MPR has a set of MPR selectors Each node sends LS to all its neighbors MPRs forward LS of their MPR selectors Other neighbors use the information to compute routing tables But do not forward OLSR significantly reduces the LS control traffic Ref RFC 3626 and draft ietf manet olsrv2 01 txt Washington University in St Louis CSE574s 19 12 2010 Raj Jain OLSR Example Node 5 has selected 4 8 as MPR Node 5 sends a LS to 2 3 4 6 7 8 11 Nodes 2 3 6 7 11 use the info but do not forward Nodes 4 uses the info and forwards it to 1 6 12 13 Node 8 uses the info and forwards it to 6 9 10 1 2 11 3 5 4 6 7 9 8 13 10 12 Washington University in St Louis CSE574s 19 13 2010 Raj Jain Selection of MPR Selection of MPR is arbitrary You can select all your neighbors as MPR Lots of duplication no optimization Optimal Min set such that all 2 hop neighbors get your LS Finding optimal MPR is NP complete Heuristics N1 x 1 hop neighbors N2 x 2 hop neighbors not covered MPR x MPRs of x empty initially From N1 x MPR x Select the node that has maximum connectivity to uncovered nodes Add that node to MPR x Washington University in St Louis CSE574s 19 14 2010 Raj Jain Dynamic Source Routing DSR On Demand routing using Source
View Full Document
Unlocking...