Ad Hoc Networks: Issues and RoutingOverviewAd Hoc Networks: CharacteristicsAd Hoc Networks: ApplicationsSensor NetworksIssues in Ad Hoc NetworksCellular vs. Ad HocAd Hoc: Media Access ControlAd Hoc Routing: RequirementsClassification of Routing ProtocolsRouting in Wired Networks: ReviewOLSROLSR: ExampleSelection of MPRDynamic Source Routing (DSR)DSR: ExampleAODVAODV (Cont)AODV: ExampleSummaryReading AssignmentOptional ReadingHomework14-1©2006 Raj JainCSE574sWashington University in St. LouisAd Hoc Networks: Ad Hoc Networks: Issues and RoutingIssues and RoutingRaj Jain Washington University in Saint LouisSaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse574-06/14-2©2006 Raj JainCSE574sWashington University in St. LouisOverviewOverviewCharacteristics, Applications, IssuesCellular vs. Ad HocRouting: Requirements, parameters, classificationDynamic Source Routing (DSR)Ad Hoc On-demand Distance Vector (AODV)Optimized Link State Routing (OLSR)14-3©2006 Raj JainCSE574sWashington University in St. LouisAd Hoc Networks: CharacteristicsAd Hoc Networks: CharacteristicsNo Fixed InfrastructureDynamic Topology (Mobility)Multi-hopping: Obstacles, spectrum reuse, energy conservationSelf-Organization: Addressing, routing, clustering, location, power controlEnergy conservationScalability: Thousands of nodesSecurity: LimitedBandwidth constrained: Congestion is a normRef: RFC250114-4©2006 Raj JainCSE574sWashington University in St. LouisAd Hoc Networks: ApplicationsAd Hoc Networks: ApplicationsEmergency, DisastersWearable computingBattlefield: Unmanned ground/airborne/underwater vehiclesHybrid: Multi-hop cellularWireless Mesh NetworksSensor Networks14-5©2006 Raj JainCSE574sWashington University in St. LouisSensor NetworksSensor NetworksA large number of low-cost, low-power, multifunctional, and small sensor nodes consisting of sensing, data processing, and communicating componentsKey Issues:1. Scalability2. Power consumption3. Fault tolerance4. Data Fusion5. Traffic: Low throughput, Delay sensitiveInternetSensor FieldSinkTask Manager14-6©2006 Raj JainCSE574sWashington University in St. LouisIssues in Ad Hoc NetworksIssues in Ad Hoc Networks1. Medium Access: Distributed, no time sync, directional antennas2. Routing: Route acquisition delay, quick reconfig, loop free3. Multicasting: Common in Ad-Hoc, Emergency/military4. Transport Layer: Frequent path breaks5. QoS6. Self-organization: Neighbor discovery, report link failures7. Security: DoS, jamming, energy depletion8. Energy management: Transmission Power, battery monitoring, processor power9. Addressing and Service Discovery: Global10. Pricing Scheme: Incentives for relaying14-7©2006 Raj JainCSE574sWashington University in St. LouisCellular vs. Ad HocCellular vs. Ad HocCellular Network Ad Hoc Networks Fixed Infrastructure Infrastructure-less Single-hop wireless links Multi-hop wireless links Centralized routing Distributed Routing Base station: Single point of failure Resilient Seamless connectivity Mobility Frequent link breaks High cost and long deployment time Quick and cost effective setup Commercial sector Defense, Emergency, Disaster Simple Mobile, Complex Base All complexity in Mobile No forwarding fairness issues Fairness: own vs other’s traffic Time Sync TDMA Time Sync difficult CSMA Static frequency reuse (cells) Dynamic freq reuse CSMA14-8©2006 Raj JainCSE574sWashington University in St. LouisAd Hoc: Media Access ControlAd Hoc: Media Access ControlFully 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 BExposed Node: Other nodes in the vicinity cannot talk.When B is talking to A, C cannot talk to DUse of Directional Antennas, Steer-able antennasMultiple Access Collision Avoidance (MACA): Use RTS/CTS with Binary Back off, e.g., 802.11ABCABCD14-9©2006 Raj JainCSE574sWashington University in St. LouisAd Hoc Routing: RequirementsAd Hoc Routing: RequirementsFully distributedGlobal state (all nodes-all time) maintenance expensive LocalizedLoop-Free routingMinimize route acquisition delay: ProactiveQuick route reconfiguration: Adaptive to Frequent changes. Changes in unrelated parts should not impact a node.Energy conservation: Sleep periodsUnidirectional Link SupportMinimize:Bits Transmitted/Bits Delivered = Avg hopsControl bits/data bits = OverheadControl packets/data packets = Overhead14-10©2006 Raj JainCSE574sWashington University in St. LouisClassification of Routing ProtocolsClassification of Routing ProtocolsRouting Updates:Proactive: Before neededReactive: On-demandHybrid: Combined. Know neighbors. Others on-demand.Temporal Information:Past HistoryPrediction:Based on node lifetime, locationTopology Organization:Flat: Global addresses as in 802.11Hierarchical: Geographical or Hop distanceResource Optimization:Power-Aware: Local or global battery powerGeographical info basedEfficient FloodingMurthy and Manoj list 40+ routing schemes for Ad-hoc nets.14-11©2006 Raj JainCSE574sWashington University in St. LouisRouting in Wired Networks: ReviewRouting in Wired Networks: Review1. Distance Vector:Each node sends its complete table (distances to all nodes in the network) to its neighbors Large vectors to small number of nodesUse Dijkstra’s algorithm to compute the shorted pathRouting Information Protocol (RIP) is a distance vector protocol2. Link State: Each nodes sends its link information (distances to its neighbors) to all nodes in the network Small vectors to large number of nodesUse Bellman-Ford to compute the shortest pathOpen Shorted Path First (OSPF) is a link state routing protocol14-12©2006 Raj JainCSE574sWashington University in St. LouisOLSROLSROptimized Link State Routing Protocol Proactive Routes are prepared before neededOptimize Min flooding duplication in highly connected netsAsk only a subset of your neighbors to forward your link statesThis 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 selectorsEach node sends LS to all its neighborsMPRs forward LS of their MPR selectorsOther neighbors use the information to compute
View Full Document