19-1©2010 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]/Video recordings of this lecture are available at:http://www.cse.wustl.edu/~jain/cse574-10/19-2©2010 Raj JainCSE574sWashington University in St. LouisOverviewOverview 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)19-3©2010 Raj JainCSE574sWashington University in St. LouisAd Hoc Networks: CharacteristicsAd 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 normRef: RFC250119-4©2010 Raj JainCSE574sWashington University in St. LouisAd Hoc Networks: ApplicationsAd Hoc Networks: Applications Emergency, Disasters Wearable computing Battlefield: Unmanned ground/airborne/underwater vehicles Hybrid: Multi-hop cellular Wireless Mesh Networks Sensor Networks19-5©2010 Raj JainCSE574sWashington University in St. LouisSensor NetworksSensor Networks A large number of low-cost, low-power, multifunctional, and small sensor nodes consisting of sensing, data processing, and communicating components Key Issues:1. Scalability2. Power consumption3. Fault tolerance4. Data Fusion5. Traffic: Low throughput, Delay sensitiveInternetSensor FieldSinkTask Manager19-6©2010 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 relaying19-7©2010 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 trafficTime Sync ⇒ TDMA Time Sync difficult ⇒ CSMA Static frequency reuse (cells) Dynamic freq reuse ⇒ CSMA19-8©2010 Raj JainCSE574sWashington University in St. LouisAd Hoc: Media Access ControlAd Hoc: Media Access Control 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.11ABCABCD19-9©2010 Raj JainCSE574sWashington University in St. LouisAd Hoc Routing: RequirementsAd 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 = Overhead19-10©2010 Raj JainCSE574sWashington University in St. LouisClassification of Routing ProtocolsClassification 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 FloodingMurthy and Manoj list 40+ routing schemes for Ad-hoc nets.19-11©2010 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 nodes¾ Use Dijkstra’s algorithm to compute the shorted path¾ Routing 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 nodes¾ Use Bellman-Ford to compute the shortest path¾ Open Shorted Path First (OSPF) is a link state routing protocol19-12©2010 Raj JainCSE574sWashington University in St. LouisOLSROLSR 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 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 selectors Each node sends LS to all its neighbors MPRs forward LS of their MPR selectors Other neighbors use the information to compute routing tablesBut do not forward. OLSR significantly reduces the LS control traffic Ref: RFC 3626 and draft-ietf-manet-olsrv2-01.txt19-13©2010 Raj JainCSE574sWashington University in St. LouisOLSR: ExampleOLSR: 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
View Full Document
Unlocking...