Mobile Ad-Hoc Networks (MANETs) PDF

Mobile Ad-Hoc Networks (MANETs) AGENDA  Characteristics  Applications  Routing Protocols Requirements  Standardization  MANET Routing Protocols CHARACTERISTICS Each node serves as a router and forwards packets for other nodes in the network.  Rapidly deployable, self configuring....

Mobile Ad-Hoc Networks (MANETs) AGENDA  Characteristics  Applications  Routing Protocols Requirements  Standardization  MANET Routing Protocols CHARACTERISTICS Each node serves as a router and forwards packets for other nodes in the network.  Rapidly deployable, self configuring.  Independent of any fixed infrastructure or centralized administration (no “access point” or backbone).  Topology can be very dynamic.  Bandwidth-constrained variable-capacity links  Limited physical security  Nodes with limited battery life and storage capabilities  EXAMPLE…. APPLICATIONS  Military Rapidly deployable battle-site networks  Unmanned aerial vehicles    Sensor Networks Disaster management Disaster relief teams  Rescue Operations   Neighborhood area networks (NANs) Shareable Internet access in high density urban settings  Students on campus   Impromptu communications among groups of people Meetings/conferences  Wearable computing   Automobile communications MAJOR CONCERNS ➢ Mobility: link breakage ➢ Power consumption ➢ QoS ➢ Scalability ➢ Security 6 CHALLENGES ➢ MAC protocol design (802.11 DCF): directional antenna, cognitive radio ➢ Routing ➢ End-to-end QoS support: mobility and intra-flow interference. ➢ Multicast/Broadcast Routing 7 ROUTING PROTOCOL REQUIREMENTS ➢ Why is it different from routing in other types of network? Because both end nodes and routers are mobile Self starting and self organizing  Multi-hop operation with a routing mechanism designed for mobile nodes  Dynamic topology maintenance  Rapid convergence  Minimal network traffic overhead  Scalable to large networks  STANDARDIZATION     The Internet Engineering Task Force (IETF) created the Mobile Ad-hoc Networks working group. The purpose of the MANET working group is to standardize IP routing protocol functionality suitable for wireless routing applications within dynamic topologies with increased dynamics due to node motion or other factors. The working group also serve as a meeting place and forum for those developing and experimenting with MANET approaches. Currently the group is pursuing a reactive, a proactive and hybrid protocol. No protocol has been standardized yet. AD HOC ROUTING ➢ ➢ ➢ ➢ On-demand (reactive) routing: Upon arrival of a connection request, the source node floods route discovery messages and find a route for packet forwarding. For example, Ad hoc On-demand Distance Vector (AODV) protocol, Dynamic Source Routing (DSR) protocol. Proactive routing: Nodes flood updates throughout the network whenever the network topology changes. For example, Optimized Link State Routing (OLSR) protocol. Hybrid routing: Route discovery is basically conducted reactively but link state update is conducted proactively within a certain range, e.g., 2-hop neighborhood of a node. For example, Zone Routing Protocol (ZRP) IETF MANET group: http://www.ietf.org/html.charters/manetcharter.html 10 ON-DEMAND VS. PROACTIVE ➢ ➢ On-demand (reactive) routing: Low routing overhead but long route discovery latency. Proactive routing: High routing overhead especially in the case of high mobility but short route discovery latency. 11 DYNAMIC SOURCE ROUTING (DSR) ➢ ➢ DSR is an on-demand routing protocol for MANETs. The whole source-to-destination route is included in every data packet and no routing table is needed for packet forwarding in each node. ➢ Loop freedom is guaranteed. ➢ Large overhead in the packets. 12 ROUTE DISCOVERY ➢ ➢ ➢ ➢ ➢ The source node broadcasts a RREQ (request) message to request a path to the destination. A tuple (SrcID, RequestID) is used to uniquely identify a route request. A node v receiving the RREQ will, - discard the packet if it is an old or duplicate one - discard the packet if v is already in the route list - send an RREP (reply) packet back to the source through the reverse route if v is the destination. - otherwise, append itself in the route list and re-broadcast the packet. Both RREQ and RREP will be sent out only once in each node. If a node has a record in its cache showing how to reach the destination, it can reply an RREP to the source immediately. 13 Route Discovery CS541 Advanced Networking Route request for A->G Red – RREQ, Green - RREP B A-B-D-G A-B A A-B-D D A G 14 A-B-D-G A-B-D-G A-C-E A E C A-C H A-C-E A-C-E F ROUTE MAINTENANCE ➢ ➢ A link-layer hop-by-hop ACK is usually used for reliable transmissions. For example, 802.11 DCF supports the link-layer ACK. A RERR will be sent by the end node to the source node if it detects a link breakage. Nodes along the path will then update their caches accordingly and the source node will initiate a new route discovery. 15 Route Maintenance RERR RERR CS541 Advanced Networking B G 16 D G A Route Cache (A) G: A, B, D, G F: C, E, F H E C F ROUTE OPTIMIZATION ➢ ➢ ➢ Route Caching: Each node caches a new route it learns by any means. For example, when A finds route [A,B,D,E,F] to F, A also learns route [A,B,D,E] to E; D forwards data [A,B,D,E,F], D learns route [D,E,F] to F; So a node usually organizes its cache in the format of a shortest path tree with itself as the root. Avoid RREP Storm Problem: An intermediate node will delay transmitting the route reply for a random period of d. During this period, cancel the route reply if overhearing any packet containing a better route. Limit the Propagation of RREQ Packets: First, set TTL = 1 for first route request packet. If no route reply is received after some time period, set TTL = maximum for next RREQ. . 17 ROUTE OPTIMIZATION ➢ ➢ ➢ Reflect Shorter Route: A node can send an unsolicited RREP to the source to inform the shorter route. Improve Error Handling: exponential backoff is used to limit the rate at which new route discoveries are initiated. Piggyback Data on RREQs 18 MANET ROUTING PROTOCOLS  Reactive  Does not take initiative for finding routes  Establishes routes “on demand” by flooding a query  Less routing overhead in average because, does not use bandwidth except when needed (when finding a route)  Much network overhead in the flooding process when querying for routes  Higher latency in establishing the path  Example: Dynamic Source Routing (DSR) DRS PROTOCOL  Suppose node A wishes to send a packet to node B, but does not currently have a valid route to the destination  Need  for route discovery Node A broadcasts a ROUTE_REQUEST packet  Each node forwards the packet to its neighbors unless they are the destination or have a valid route to the destination  As the packet traverses the network, each intermediate node adds its address to the header, establishing the reverse route  The destination, node B, sends a ROUTE_REPLY packet to node A  If the links are not bi-directional, node B must perform its own route discovery to respond to node A DRS PROTOCOL DRS PROTOCOL DRS PROTOCOL  Intermediate nodes may cache accumulated route record contained in the ROUTE_REQUEST packet headers in order to reduce routing overhead  Security  Confirmation of the receipt of a packet can be done by passive acknowledgement  Node  concerns overhears a downstream node forwarding the packet DSR also contains provisions to avoid route reply storms MANET ROUTING PROTOCOLS  Proactive  Establish routes in advance  Routes are set up based on continuous control traffic. All routes are maintained all the time  Constant  Routes overhead created by control traffic are always available  Example: Optimized Link State Routing Protocol (OLSR) OLSR PROTOCOL  The Optimized Link-State Routing protocol can be divided in to three main modules:  Neighbor/link sensing  Optimized flooding/forwarding (Multi Point Relaying)  Link-State messaging and route calculation NETWORK / LINK SENSING Routers maintain awareness of current network topology by exchanging “HELLO messages”  All nodes transmit HELLO messages on a given interval.  Each node tells the entire network about its immediate neighbors   So each node forms a picture of the entire network topology  Each  node can then calculate the best route to any destination These contain all heard-of neighbors grouped by status. MULTI-POINT RELAYING  Flooding the network with HELLO messages incurs too much overhead  OLSR uses multi-point relay (MPR) nodes to decrease the number of unnecessary broadcasts (only selected nodes broadcast HELLO) Reduce the number of duplicate retransmissions while forwarding a broadcast packet.  Restricts the set of nodes retransmitting a packet from all nodes(regular flooding) to a subset of all nodes.  The size of this subset depends on the topology of the network.  MULTI-POINT RELAYING MULTI-POINT RELAYING LINK STATE FUNCTIONALITY In a classic link-state scheme all nodes flood the network with link-state information.  OLSR has two link-state optimizations:   Only MPR selectors are declared in link-state messages. This minimizes the size of link-state messages.  Only nodes selected as MPRs will generate link-state messages. This minimizes the set of nodes emitting link-state messages. MANET ROUTING PROTOCOLS  Hybrid  This type of protocols combines the advantages of proactive and of reactive routing.  The routing is initially established with some proactively prospected routes and then serves the demand from additionally activated nodes through reactive flooding.  Advantage  Example: depends on number of nodes activated. Zone Routing Protocol (ZRP) ZONE ROUTING PROTOCOL (ZRP)  Proactive within the node’s local neighborhood, reactive for inter-zone routing Intra-zone routing: Proactively maintain routes to all nodes within the source node’s own zone.  Inter-zone routing: Use an on-demand protocol (similar to DSR or AODV) to determine routes to outside zone.     Proposed to reduce the control overhead of proactive routing protocols and decrease the latency caused by route discovery in reactive routing protocols Uses ‘Bordercast’ instead of neighbor broadcast Neighbor Discovery/Maintenance (NMD) and Border Resolution Protocol (BRP) used for query control, route accumulation etc. ZONE ROUTING PROTOCOL (ZRP) 1 Hop 2 Hops Multi Hops B F A C D E G H MORE AD HOC ROUTING PROTOCOLS… Temporally Ordered Routing Algorithm (TORA)  Linked Cluster Architecture (LCA)  Reliable Ad hoc On-demand Distance Vector Routing Protocol  Ad hoc On-demand Routing Protocol (AORP)  Hybrid Routing Protocol for Large Scale Mobile Ad Hoc Networks with Mobile Backbones (HRPLS)  Multicast routing protocols  Protocol Independent Multicast (PIM)  Multicast Zone Routing (MZR)  Multicast Optimized Link State Routing (MOLSR)  On-demand Multicast Routing Protocol (OMRP)  REFERENCES MANET IETF working group http://datatracker.ietf.org/wg/manet/charter/  IETF DSR RFC: http://tools.ietf.org/html/rfc4728  IETF OLSR RFC: http://tools.ietf.org/html/rfc3626  INRIA OLSR page http://hipercom.inria.fr/olsr/  The Zone Routing Protocol Web Page http://www.zrp.be/ 