Question? Leave a message!




MOBILE ADHOC NETWORKS (MANETs)

MOBILE ADHOC NETWORKS (MANETs) 32
MOBILE ADHOC NETWORKS (MANETs): An Introduction Dr. A K Verma Department of Computer Science and Engineering Thapar University PatialaAN OVERVIEW  Wireless Networks  MANET (Defn. , applications)  Routing (Defn. , Types) Routing Protocols in MANET Proactive (6) Reactive (5) Hybrid (1)Wireless Networks Need: Access computing and communication services, on the move  Infrastructurebased Networks –traditional cellular systems (base station infrastructure)  Wireless LANs – Infrared (IrDA) or radio links (Wavelan) –very flexible within the reception area; adhoc networks possible –low bandwidth compared to wired networks (110 Mbit/s)  Ad hoc Networks –useful when infrastructure not available, impractical, or expensive –military applications, rescue, home networkingCellular Wireless Single hop wireless connectivity to the wired world –Space divided into cells –A base station is responsible to communicate with hosts in its cell –Mobile hosts can change cells while communicating –Handoff occurs when a mobile host starts communicating via a new base stationMultiHop Wireless  May need to traverse multiple links to reach destination  Mobility causes route changesMobile Ad hoc Networks (MANETs)  Host movement frequent  Topology change frequent B A A B  No cellular infrastructure. Multihop wireless links  Data must be routed via intermediate nodesWHY ADHOC NETWORKS  Setting up of fixed access points and backbone infrastructure is not always viable Infrastructure may not be present in a disaster area or war zone Infrastructure may not be practical for shortrange radios; Bluetooth (range 10m) Ad hoc networks: Do not need backbone infrastructure support Are easy to deploy Useful when infrastructure is absent, destroyed or impracticalApplications of MANET  Personal area networking –cell phone, laptop, ear phone, wrist watch  Military environments –soldiers, tanks, planes  Civilian environments –taxi cab network –meeting rooms –sports stadiums –boats, small aircraft  Emergency operations –searchandrescue –policing and fire fightingChallenges in Mobile Environments  Limitations of the Wireless Network packet loss due to transmission errors variable capacity links frequent disconnections/partitions limited communication bandwidth Broadcast nature of the communications  Limitations Imposed by Mobility dynamically changing topologies/routes lack of mobility awareness by system/applications  Limitations of the Mobile Computer short battery lifetime limited capacitiesRouting in MANETs Challenges for Routing Protocols No centralized entity Host is no longer just an end system Acting as an intermediate system Changing network topology over time Every node can be mobileEffect of mobility on the protocol stack  Application –new applications and adaptations  Transport –congestion and flow control  Network –addressing and routing  Link –media access and handoff  Physical –transmission errors and interferenceROUTING • Network with nodes, edges • Goal: Devise scheme for transferring message from one node to another. –Which path –Who decides – source or intermediate nodes msgWHICH PATH  Generally try to optimize something: –Shortest path (fewest hops) –Shortest time (lowest latency) –Shortest weighted path (utilize available bandwidth) –Etc.Routing Ants Searching for Food Example: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 placeWho determines route 2 General Approaches:  Source (“path”) routing Source specifies entire route: places complete path to destination in message header: A – D – F – G Intermediate nodes just forward to specified next hop: D would look at path in header, forward to F Like airline travel – get complete set of tickets to final destination before departing…Who determines route …..contd.  Destination (“hopbyhop”) routing –Source specifies only destination in message header: G –Intermediate nodes look at destination in header, consult internal tables to determine appropriate next hop –Like postal service – specify only the final destination on an envelope, and intermediate post offices select where to forward next…Comparison •Destination routing  Source routing No source storage –Moderate source storage (entire route for High intermediate node each desired dest.) storage (table w/ routing instructions for all possible –No intermediate node dests.) storage Lower routing overhead –Higher routing (just dest in header, only overhead (entire path in routers need deal w/ route message header, route discovery) discovery messages)AD HOC ROUTING  Every node participates in routing: no distinction between “routers” and “end nodes” •No external network setup: “selfconfiguring” •Especially useful when network topology is dynamic (frequent network changes – links break, nodes come and go)ROUTING PROTOCOLS IN MANET  Many protocols have been proposed  Some specifically invented for MANET  Others adapted from protocols for wired networks  9 routing protocols in draft stage, 4 drafts dealing with broadcast / multicast / flow issues (Other protocols being researched) Standardization efforts in IETF –MANET, MobileIP working groups –http://www.ietf.orgROUTING PROTOCOLS IN MANET …..contd. Proactive protocols (TableDriven approach) –Traditional distributed shortestpath protocols –Maintain routes between every host pair at all times –Based on periodic updates; High routing overhead –Example: DSDV (destination sequenced distance vector) Reactive protocols (DemandBased approach) –Determine route if and when needed –Source initiates route discovery –Example: DSR (dynamic source routing) Hybrid protocols –Adaptive; Combination of proactive and reactive –Example : ZRP (zone routing protocol)I) PROACTIVE PROTOCOLS (TABLE DRIVEN)  Distance Sequenced Distance Vector (DSDV)  Wireless Routing Protocol (WRP)  Global State Routing (GSR)  Fisheye State Routing (FSR)  Hierarchical State Routing (HSR)  Common Gateway Switch Routing (CGSR)1a) DSDV Each node maintains a routing table which stores –next hop, cost metric towards each destination –a sequence number that is created by the destination itself Each node periodically forwards routing table to neighbors –Each node increments and appends its sequence number when sending its local routing table Each route is tagged with a sequence number; routes with greater sequence numbers are preferred Each node advertises a monotonically increasing even sequence number for itself When a node decides that a route is broken, it increments the sequence number of the route and advertises it with infinite metric Destination advertises new sequence numberDSDV….contd. When X receives information from Y about a route to Z –Let destination sequence number for Z at X be S(X), S(Y) is sent from Y Z X Y – If S(X) S(Y), then X ignores the routing information received from Y – If S(X) = S(Y), and cost of going through Y is smaller than the route known to X, then X sets Y as the next hop to Z – If S(X) S(Y), then X sets Y as the next hop to Z, and S(X) is updated to equal S(Y)1b) Wireless Routing Protocol (WRP)  Each node maintains four separate tables to exchange routing information a distance table a routing table a linkcost table a message retransmission list (MRL)  Predecessor and Successor information helps in avoiding loops  Nodes send HELLO message to each other when idle to announce presence1c) GLOBAL STATE ROUTING (GSR) Uses link state Routing Scheme  Each node maintains four tables Neighbor list Topology table Next hop table Distance table  All tables are updated on link change1d) Fisheye State Routing (FSR)1e) Hierarchical State Routing (HSR)1f) Clusterhead Gateway Switching Routing (CGSR)II) REACTIVE PROTOCOLS (DEMAND BASED)  Dynamic Source Routing (DSR)  Ad hoc On Demand distance Vector Routing (AODV)  Associativity Based Routing (ABR)  Signal Stability Algorithm (SSA)  Temporally Ordered Routing Algorithm (TORA)2a) Dynamic Source Routing (DSR) When node S wants to send a packet to node D, but does not know a route to D, node S initiates a route discovery Source node S floods Route Request (RREQ) Each node appends own identifier when forwarding RREQRoute Discovery in DSR Y Z S E F B C M L J A G H D K I N Represents a node that has received RREQ for D from SRoute Discovery in DSR Broadcast transmission Y Z S E F B C M L J A G H D K I N Represents transmission of RREQ X,Y Represents list of identifiers appended to RREQRoute Discovery in DSR Y Z S,E S E F B C M L J A G S,C H D K I N •Node H receives packet RREQ from two neighbors: potential for collisionRoute Discovery in DSR Y Z S E F S,E,F B C M L J A G H D K S,C,G I N •Node C receives RREQ from G and H, but does not forward it again, because node C has already forwarded RREQ onceRoute Discovery in DSR Y Z S E S,E,F,J F B C M L J A G H D K S,C,G,K I N •Nodes J and K both broadcast RREQ to node D • Since nodes J and K are hidden from each other, their transmissions may collideRoute Discovery in DSR Y Z S E S,E,F,J,M F B C M L J A G H D K I N •Node D does not forward RREQ, because node D is the intended target of the route discoveryRoute Discovery in DSR Destination D on receiving the first RREQ, sends a Route Reply (RREP) RREP is sent on a route obtained by reversing the route appended to received RREQ RREP includes the route from S to D on which RREQ was received by node DAd Hoc OnDemand Distance Vector Routing (AODV) Route Requests (RREQ) are forwarded in a manner similar to DSR When a node rebroadcasts a Route Request, it sets up a reverse path pointing towards the source –AODV assumes symmetric (bidirectional) links When the intended destination receives a Route Request, it replies by sending a Route Reply (RREP) Route Reply travels along the reverse path setup when Route Request is forwardedRoute Requests in AODV Y Z S E F B C M L J A G H D K I N Represents a node that has received RREQ for D from SRoute Requests in AODV Y Broadcast transmission Z S E F B C M L J A G H D K I N Represents transmission of RREQRoute Requests in AODV Y Z S E F B C M L J A G H D K I N Represents links on Reverse PathRoute Requests in AODV Y Z S E F B C M L J A G H D K I N • Node C receives RREQ from G and H, but does not forward it again, because node C has already forwarded RREQ onceRoute Requests in AODV Y Z S E F B C M L J A G H D K I NRoute Requests in AODV Y Z S E F B C M L J A G H D K I N • Node D does not forward RREQ, because node D is the intended target of the RREQRoute Requests in AODV Y Z S E F B C M L J A G H D K I N Forward links are setup when RREP travels along the reverse path Represents a link on the forward path2c) Associativity Based Routing (ABR)  Based on degree of association of stability  All nodes generate beacons to announce their presence  Node updates its associativity tick when it receives beacon from others High associativity tick implies stable node  Destination chooses best route by examining the associativity tick of multiple routes taken by the packet (threshold associativity) 2c) Signal Stability Algorithm (SSA)  Channel strength based on beacon signal Route discovery attempted through strong channel first  Destination knows that route is along the strongest channels availableSignal Stability Routing (SSA)Signal Stability Routing (SSA)Signal Stability Routing (SSA)2e) TemporallyOrdered Routing Algorithm (TORA) Route optimality is considered of secondary importance; longer routes may be used At each node, a logically separate copy of TORA is run for each destination, that computes the height of the node with respect to the destination Height captures number of hops and next hop Route discovery is by using query and update packets TORA modifies the partial link reversal method to be able to detect partitions When a partition is detected, all nodes in the partition are informed, and link reversals in that partition ceasePower Aware Routing Protocol – Modify DSR to incorporate weights and prefer a route with the smallest aggregate weight – Assign a weight to each link: function of energy consumed when transmitting a packet on that link, as well as the residual energy level S E C D3a) Zone Routing Protocol (ZRP) ZRP combines proactive and reactive approaches All nodes within hop distance at most d from a node X are said to be in the routing zone of node X All nodes at hop distance exactly d are said to be peripheral nodes of node X’s routing zone Intrazone routing: Proactively maintain routes to all nodes within the source node’s own zone. Interzone routing: Use an ondemand protocol (similar to DSR or AODV) to determine routes to outside zone.Zone Routing Protocol (ZRP) Radius of routing zone = 2 (w.r.t. node S)Classification of Routing Protocols in MANETVANETsSensor Networks A Sensor System Sensor NodeMOBILE COMMUNICATION STANDARDS Data Rate Vs. Mobility (source: www.zurich.ibm.com)MOBILE COMMUNICATION STANDARDS 1. Bluetooth 2. Code Division Multiple Access (CDMA) 3. Digital Enhanced Cordless Telecommunications (DECT) 4. Frequency Division Multiple Access (FDMA) 5. General Packet Radio Services (GPRS) 6. Global System for Mobile Communication (GSM) 7. GSM/EDGE Radio Access Network (GERAN) 8. IMode 9. Mobile Station Application Execution Environment (MExE) 10. Synchronization Markup Language (SyncML) 11. Time Division Multiple Access (TDMA) 12. Universal Mobile Telecommunication Services (UMTS) 13. Wireless Application Protocol (WAP)THANK YOUREFERENCES 1. A.S. Tanenbaum, “Computer Networks”, PHI, 2001. 2. Black, Uyless, “Computer Networks: Protocols Standards and Interfaces”, PHI, 1998. 3. A. Iwata, C. C. Chiang, G. Pei, M. Gerla, and T. W. Chen, “Scalable Routing Strategies for Ad Hoc Wireless Networks”, IEEE Journal on Selected areas in communications, Special Issue on Ad hoc Networks, Aug. 1999, pp. 136979. 4. B.A. Miller, C. Bisdikian, “Bluetooth Revealed” Prentice Hall, Englewood Cliffs, N.J., 2000 . 5. C. Bisdikian, “An overview of the Bluetooth wireless technology”, IEEE Commn. Magazine, Dec 2001. 6. C.E. Perkins, “Ad Hoc Networking”, Addison Wesley, Reading, MA,2000.7. C.E. Perkins and P. Bhagwat “Highly dynamic destination sequenced distance vector routing (DSDV) for mobile computers”, Proc. of the ACM SIGCOMM conference on communications architectures, Protocols and applications, London, UK, Sept 1994, pp.234244. 8. C.E. Perkins and E M Royer, “Ad Hoc on demand distance vector routing”, Proc. of IEEE workshop on mobile computing systems and applications (WMCSA), New Orleans, LA, February 1999, pp. 90100. 9. C.E. Perkins , E M Royer and Samir R Das, “Ad Hoc On demand Distance Vector Routing”, October1999 IETF Draft, 33 Pages. 10. C. Raghavendra, S. Singh, “PAMAS:power aware multiaccess protocol with signaling for ad hoc networks”, ACM Computer Communication Review, July 1998, pp. 526.11. C. R. Liu and J.S. Liu, “QoS routing in Ad Hoc wireless networks”, IEEE Journal on selected areas in communications, special issue on wireless Ad Hoc networks, Vol. 17, no.8, August 1999, pp.1426143. 12. C K Toh, “Longlived Ad Hoc Routing based on the concept of Associativity” March 1999 IETF Draft, 8 pages. 13. C.K. Toh, “Ad Hoc Mobile Wireless Networks: Protocols and Systems”, Prentice Hall PTR, Englewood Cliffs, NJ,2002. 14. ChaiKeong Toh, “A novel distributed routing protocol to th support Ad Hoc Mobile Computing”, Proc. IEEE 15 annual Int’l Phoenix conference on Computer and Communication, March 1996, pp. 48086. 15. Corson M. and J. Macker, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations”, RFC 2501, January 1999.16. D. Cavendish and M. Gerla, “Internet QoS Routing using the BellmanFord Algorithm”, IFIP 1998 Published by Chapman Hall, 20 pages. 17. DA Maltz, J. Broch, J. Jetcheva and D.B. Johnson, “The effect of ondemand behavior in routing protocols for multihop wireless Ad Hoc Networks”, IEEE Journal on selected areas in communications, special issue on wireless Ad Hoc networks, Vol. 17, no. 8, Aug. 1999, pp. 14391453. 18. D. P. Agrawal, QingAn Zeng, “Introduction to wireless and Mobile Systems”, Brooks/Cole, 2003. 19. David B. Johnson, Davis A. Maltz, “Dynamic Source Routing in Ad Hoc Networks”, Mobile Computing, T. Imielinski and H. Korth Eds, Kluwer 1996, pp. 15281.20. David B. Johnson, Davis A. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks” Oct.1999 IETF Draft, 49 Pages. 21. E.M. Roger and C.K. Toh, “A Review of Current Routing Protocols for Adhoc Mobile Networks”, IEEE Personal Communications, vol 6, No. 2, April 1999, pp 4655. 22. G. Anastasi, M. Conti, E Gregori, “IEEE 802.11 ad hoc networks: protocols,performance and open issues, in”: S. Basagani, M. Conti, S. Giordano, I. Stojmenovic (Eds)”, Ad Hoc Networking, IEEE Press Wiley,NY,2003. 23. G. Pei, M. Gerla, T.W. Chen, “Fisheye state routing –a routing scheme for Adhoc wireless networks”, Proc. of IEEE international conference on communications (ICC), New Orleans, LA, June 2000, pp. 7074.24. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, “Wireless Sensor Networks: A Survey”, Computer Networks, Vol. 38, 2002, pp.393422. 25. Imrich Chlamtac, Marco Conti, Jennifer J.N. Liu, “Mobile Adhoc networking: imperatives and challenges”, Elsevier Ad Hoc Networks, vol. 1, 2003 pp. 1364 26. J. Lundberg, “Routing Security in Ad Hoc Networks”, 2000 http://citeseer.nj.nec.com/400961.html 27. Kui Wu, Janelle Harms, “QoS support in mobile ad hoc networks”,Crossing boundaries,1(1), 2001 http://www.ualberta.ca/ gsa/ ejournal M. Gerla, G. Pei, and S.J. Lee, “Wireless Mobile Adhoc Networking Routing”, Proc. of the ACM/IEEE WINLAB/Berkeley Focus, New Brunswick, NJ, May 1999.29. M.R. Pearlman and Z.J. Haas, “Determining the optimal configuration for Zone routing protocol”, IEEE Journal on selected areas in communications, special issue on wireless Ad Hoc networks, August 1999, vol. 17, no.8, pp.13951414. 30. M. Weiser, ” The Computer for the TwentyFirst Century”, Scientific American,1991. 31. Mingliang Jiang, Jinyang Li, Y.C.Tay, “Cluster Based Routing Protocol”, IETF Draft Aug. 1999 (27 pages) 32. Navid Nikaein, Christian Bonnet, “A glance at quality of service th models in mobile ad hoc networks”, Proc. of DNAC 2002: 16 Conference of New Architectures for Communications, Paris, France, 2002. 33. P. Krishna, N.H. Vaidya, M. Chatterjee, D.K. Pradhan, “A clusterbased approach for routing in dynamic networks”, ACM Computer Communication Review (CCR), 1997.34. R. Dube et al. “Signal Stability based adaptive routing for Ad Hoc Mobile Networks” IEEE Pers. Comm., February 1997, pp. 4645. 35. R. Kravets and P. Krishnan, “Power Management Techniques for mobile communication”, MOBICOM’98, pp.157168 36. S. Ramanathan M. Streenstrup, “A Survey of Routing Techniques for Mobile Communication Networks”, ACM/Baltzer Mobile Networks and Applications, special issue on Routing in Mobile Communication networks, Vol. 1, No. 2, October 1996, pp 89104. 37. S. Giordano, Mobile adhoc networks, in : I. Stojmenovic (Ed.), “Handbook of Wireless Networks and Mobile Computing”, Wiley, NY, 200238. S. Sajama, Zygmunt Haas, “Independent tree ad hoc multicast routing (ITAMAR)”, special issue on Mobile Ad Hoc Network, ACM/Kluwer MONET Vol. 8, No.5, 2003. 39. S. Murthy and J. J. GarciaLunaAceves, “An efficient routing protocol for wireless networks”, ACM Mobile networks and App. J., Special Issue on Routing in Mobile Communication Networks, Oct. 1996, pp. 18397. 40. SungJu Lee, William Su, Mario Gerla, “Wireless ad hoc multicast routing with mobility prediction”, ACM/Kluwer Mobile networks and Applications Vol. 6 No.4, 2001, pp.351 360. 41. T.W. Chen and M. Gerla, “Global state routing: A new routing scheme for Ad Hoc wireless networks”, Proc. of IEEE international conference on communications (ICC), Atlanta, GA, June 1998, pp.171175.42. V.D. Park and M.S. Corson, “A highly adaptive distributed routing routing protocol for mobile wireless networks”, Proc. INFOCOMM 97, April 1997, 9 pages. 43. V. Karpijoki, “Security in Ad Hoc Networks”, 2000 http://citeseer.nj.nec.com/karpijoki01security.html 44. www.isi.edu 45. www.istwsi.org (wireless World Research Forum) 46. www.ietf.org (Internet Expert Task Force) 47. www.meshnetworks.com 48. www.spanworks.com 49. www.bluetooth.com 50. Y. C. Hu, A. Perrig, D.B. Johnson, “Ariadne: a secure on th demand routing protocol for ad hoc networks”, Proc. 8 ACM Conference MOBICOM2002, Atlanta, GA, Sept 2328,2002.51. Y. Zhang, W. lee, Y. Huang, ”Intrusion detection techniques for mobile wireless networks”, ACM/Kluwer Mobile Networks and Applications (MONET) Vol. 9, No.5, 2003. 52. Z.J. Haas and M.R. Pearlman, “The performance of Query Control Schemes for the Zone Routing Protocol ”, ACM SIGCOMM 1998.Thank You