Transcript manet-intro
Introduction to Ad Hoc Networking Perkin’s book: Ch 1 and Ch 2. Some data collected from the Internet by Prof. Yu-Chee Tseng tseng:1 Model of Operations tseng:2 Assumptions Symmetric Links: unidirectional links are difficult to dealt with, and sometimes at the verge of failure Layer-2 Routing: Most protocols are presented in layer-3 routing, but can be easily retooled as a layer-2 ones. Proactive vs. Reactive Protocols (to be elaborated later) tseng:3 Applications ad hoc conferencing home networking emergency services personal area network (PAN) ubiquitous computing “computers are all around us, constantly performing mundane tasks to make our lives a litter easier” “Ubiquitous intelligent internetworking devices that detect their environment, interact with each other, and respond to changing environmental condition will create a future that is as challenging to imagine as a science fiction scenario.” tseng:4 Sensor Dust: a large collection of tiny sensor devices once situated, the sensors remain stationary largely homogeneous power is likely to be a scarce resource, which determines the lifetime of the network can offer detailed information about terrain or environmental dangerous conditions. Intelligent Transportation System: may be integrated with cars, positioning devices, etc. tseng:5 Technical Factors scalability power budget vs. latency protocol deployment and incompatibility standards “Unless a miracle happens (e.g., the IETF manet working group is able to promulgate a widely deployed ad hoc networking protocol), ad hoc networks will gain momentum only gradually because users will have to load software or take additional steps to ensure interoperability. wireless data rate e.g., TCP over multi-hop wireless links security issues tseng:6 More Extensions (DoD’s Perspective) could be a group of hosts supported by one or more radios could across the Internet tseng:7 IEFT MANET Working Group goal: to standardize an interdomain unicast routing protocol which provides one or more modes of operation, each mode specialized for efficient operation in a given mobile networking “context”, where a context is a predefined set of network characteristics. a dozen candidate routing protocols have been proposed. tseng:8 Applications of Ad Hoc Networks tseng:9 Network Architectures No Infrastructure (ad hoc networks): no base stations; no fixed network infrastructure tseng:10 MANET MANET = Mobile Ad Hoc Networks multi-hop communication needs support of dynamic routing protocols tseng:11 Nokia Rooftop Product tseng:13 Nokia RoofTop RoofTop solution (Nokia, Finland) Wireless router a radio frequency (RF) modem a digital Internet protocol (IP) router tseng:14 FHP FHP Wireless, USA ad hoc network in a campus tseng:15 FHP Wireless tseng:16 FHP Wireless tseng:17 MeshNetworks MeshNetworks, USA tseng:18 System – MeshNetworks Architecture tseng:19 Networking Scenario : To Internet tseng:20 SkyPilot NeighborNet SkyPilot Network, USA tseng:21 Routing = Ants Searching for Food ?? ? ?? ? ?? ? ? ? ? ? ? ?? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? tseng:22 tseng:23 Three Main Issues in Ants’ Life Route Discovery: searching for the places with food Packet Forwarding: delivering foods back home Route Maintenance: when foods move to new place tseng:24 Proactive vs. Reactive Routing Proactive Routing Protocol: continuously evaluate the routes attempt to maintain consistent, up-to-date routing information when a route is needed, one may be ready immediately when the network topology changes the protocol responds by propagating updates throughout the network to maintain a consistent view Reactive Routing Protocol: on-demand Ex: DSR, AODV tseng:25 Ad hoc routing protocols AD-HOC MOBILE ROUTING PROTOCOLS TABLE DRIVEN/ PROACTIVE DSDV ON-DEMAND-DRIVEN REACTIVE HYBRID DSR AODV CGSR ZRP tseng:26 DSDV Destination Sequenced Distance Vector Table-driven Based on the distributed Bellman-Ford routing algorithm Each node maintains a routing table Routing hops to each destination Sequence number tseng:27 DSDV Problem A lot of control traffic in the network Solution two types of route update packets Full dump All available routing information Incremental Only information changed since the last full dump tseng:28 Clustering Protocol Cluster Gateway Switch Routing (CGSR) Table-driven for inter-cluster routing Uses DSDV for intra-cluster routing C2 C1 M2 C3 tseng:29 AODV Ad hoc On-demand Distance Vector On-demand driven Nodes that are not on the selected path do not maintain routing information Route discovery The source node broadcasts a route request packet (RREQ) The destination or an intermediate node with “fresh enough” route to the destination replies a route reply packet (RREP) tseng:30 AODV N2 Source N1 N5 Destination N7 N4 N3 N8 N2 N5 N6 (a) RREQ Source N1 Destination N7 N4 N3 N8 N6 (b) RREP tseng:31 AODV Problem A node along the route moves Solution Upstream neighbor notices the move Propagates a link failure notification message to each of its active upstream neighbors The source node receives the message and reinitiate route discovery tseng:32 DSR Dynamic Source Routing On-demand driven Based on the concept of source routing Required to maintain route caches Two major phases Route discovery Route maintenance A route error packet tseng:33 DSR N1-N2 N1-N2-N5 N2 N8 N5 N1 N1-N3-N4 N1 N7 N4 N1 N1-N3-N4 N1-N3 N3 N1-N3-N4-N7 N1-N3-N4 N2 N1-N3-N4-N6 N6 N1-N2-N5N8 N5 N1-N2-N5N8 N8 N1-N2-N5N8 N1 N7 N4 N3 N6 tseng:34 ZRP Zone Routing Protocol Hybrid protocol On-demand Proactive ZRP has three sub-protocols Intrazone Routing Protocol (IARP) Interzone Routing Protocol (IERP) Bordercast Resolution Protocol (BRP) tseng:35 Zone of Node Y Border Node Zone of Node Y Bordercasting Zone Radius = Border Node Node X r Hops Node Z Zone of Node X Zone of Node Z LAR Location-Aided Routing Location information via GPS Shortcoming GPS availability is not yet worldwide Position information come with deviation tseng:37 LAR Request Zone Expected Zone (Xd+R, Yd+R) DEST R (Xd,Yd) SRC tseng:38 (Xs,Ys) DREAM Distance Routing effect Algorithm for mobility Position-based Each node maintains a position database Regularly floods packets to update the position Temporal resolution Spatial resolution tseng:39 PAR Power-Aware Routing N1 + N2 – SRC + – DES T + + – – N3 + – N4 + – tseng:40