routing protocols(1).pdf

SPB-150005 View metadata, 4 similar citation and October 17, 2008 papers Time: 5:59 at core.ac.uk Proof 1 brought to you by CORE...

SPB-150005 View metadata, 4 similar citation and October 17, 2008 papers Time: 5:59 at core.ac.uk Proof 1 brought to you by CORE provided by The International Islamic University Malaysia Repository 1 Chapter 4 2 3 Routing in Mobile Ad Hoc Networks 4 5 OF 6 Al-Sakib Khan Pathan and Choong Seon Hong 7 8 9 RO 10 11 12 13 Abstract A Mobile Ad Hoc Network (MANET) is built on the fly where a 14 number of wireless mobile nodes work in cooperation without the engagement of any centralized access point or any fixed infrastructure. Two nodes in such a DP 15 16 network can communicate in a bidirectional manner if and only if the distance 17 between them is at most the minimum of their transmission ranges. When a 18 node wants to communicate with a node outside its transmission range, a multi- 19 hop routing strategy is used which involves some intermediate nodes. Because 20 of the movements of nodes, there is a constant possibility of topology change in TE 21 MANET. Considering this unique aspect of MANET, a number of routing 22 protocols have been proposed so far. This chapter gives an overview of the past, 23 current, and future research areas for routing in MANET. In this chapter we 24 will learn about the following things: EC 25  The preliminaries of mobile ad hoc network 26  The challenges for routing in MANET 27  Expected properties of a MANET routing protocol 28  Categories of routing protocols for MANET 29 RR  Major routing protocols for MANET 30  Criteria for performance comparison of the routing protocols for MANET 31  Achievements and future research directions 32  Expectations and reality 33 CO 34 35 4.1 Introduction 36 37 With the staggering growth of wireless handheld devices and plummeting costs 38 of mobile telecommunications, mobile ad hoc network has emerged as a major UN 39 area of research for both the academic and the industrial sectors. A mobile ad 40 41 A.-S.K. Pathan (*) 42 Department of Computer Engineering, Kyung Hee University, 1 Seocheon, Giheung, 43 Yongin, Gyeonggi 449701, Korea 44 e-mail: [email protected], [email protected] S. Misra et al. (eds.), Guide to Wireless Ad Hoc Networks, Computer Communications and Networks, DOI 10.1007/978-1-84800-328-6_4, Ó Springer-Verlag London Limited 2009  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 45 hoc network (MANET) is built on the fly where a number of mobile nodes 46 work in cooperation without the engagement of any centralized access point 47 or any fixed infrastructure. MANETs are self-organizing, self-configuring, 48 and dynamic topology networks, which form a particular class of multi-hop 49 networks. Minimal configuration, absence of infrastructure, and quick deploy- OF 50 ment make them convenient for combat, medical, and other emergency 51 situations. All nodes in a MANET are capable of movement and can be 52 interconnected in an arbitrary manner. 53 The issue of routing in MANET is somewhat challenging and non-trivial. Due RO 54 to the mobility of the nodes, connectivity between any two nodes in the network is 55 considered intermittent and often it is very difficult, if not impossible to use 56 traditional wired network’s routing mechanisms. Basically, the major challenges 57 for routing in MANET are imposed by the resource constraints and mobility of 58 the nodes participating in the network. As there is no fixed infrastructure in such a DP 59 network, we consider each node as a host and a router at the same time. Hence, 60 during routing of data packets within the network, at each hop, each host also has 61 to perform the tasks of a router. In fact, these special aspects of mobile ad hoc 62 networks have attracted many researchers to work on solving the routing issues in 63 MANET. A sample model of mobile ad hoc network is presented here in Fig. 4.1, 64 which consists of some mobile devices with wireless communication facilities. TE 65 So far, a significant number of proposals for routing in MANET have seen the 66 daylight. However, it is apparent that there could not be a single solution for 67 routing in MANETs. Different deployment scenarios and application-dependent 68 requirements need the employment of different types of routing mechanisms. In EC 69 this chapter, we will learn about the routing protocols for MANET, their 70 features, advantages, drawbacks, and future expectations. 71 Let us start this chapter with a brief background of MANET. We will know 72 about how the practitioners, researchers, scientists, and industrialists have tried 73 RR 74 75 76 77 CO 78 79 80 81 82 UN 83 84 85 86 87 88 89 Fig. 4.1. An Example of Mobile Ad Hoc Network (MANET)  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 90 to solve this challenging issue for MANET. We will know various types of 91 routing schemes those are already proposed or those could be applied for these 92 types of networks. Considering the practical scenarios, we will also discuss how 93 the reality might betray the expectations. 94 OF 95 96 97 4.2 Background 98 From the advent of packet radio network up to today’s MANET, the whole life RO 99 100 cycle of ad hoc networks can be categorized mainly into three parts: first 101 generation, second generation, and third generation. Today’s ad hoc networks 102 are considered as the third-generation networks. 103 The first generation goes back to 1972. At that time, they were called PRNET (Packet Radio Networks). In 1973, the Defense Advanced Research DP 104 105 Projects Agency (DARPA) initiated research on the feasibility of using packet- 106 switched radio communications to provide reliable computer communications 107 [1, 2]. This development was motivated by the need to provide computer net- 108 work access to mobile hosts and terminals, and to provide computer commu- 109 nications in a mobile environment. TE 110 The second generation of ad hoc networks emerged in 1980s, when the ad 111 hoc network systems were further enhanced and implemented as a part of the 112 SURAN (Survivable Adaptive Radio Networks) program. This provided a 113 packet-switched network to the mobile battlefield in an environment without EC 114 infrastructure. This program proved to be beneficial in improving the radio 115 performance by making them smaller, cheaper, and resilient to electronic 116 attacks. 117 In the 1990s, the concept of commercial ad hoc networks arrived with 118 handheld computers and other small portable communication equipments. At RR 119 the same time, the idea of a collection of mobile nodes was proposed at several 120 research conferences. From then up to today, research works have been going 121 on for solving various issues of mobile ad hoc networks. 122 We mentioned the formal definition of a mobile ad hoc network earlier. Let CO 123 us investigate how the unique characteristics of MANET make the task of 124 routing complicated. So far we have learnt that the major features of this type 125 of network are each node is considered both as a host and as a router; the nodes 126 in the network are allowed to move while participating in the network; for their 127 connectivity they use wireless communications; there is no centralized entity in UN 128 the network; and the nodes are mainly battery-powered. Now, let us consider 129 the following network structure for starting our discussion on routing in 130 MANET. 131 132 Example 4.1 In Fig. 4.2, a sample model of MANET is presented where there 133 are three nodes; A, B, and C. The radio transmission ranges of the nodes are 134 shown as circles.  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 135 136 137 138 139 OF 140 141 142 143 RO 144 145 146 Fig. 4. 2 A MANET with three nodes 147 148 In the figure, node A and node B are within the transmission ranges of each other. We call any of these nodes as a neighbor of the other. Likewise, B and C DP 149 150 are neighbors. But, A and C are not neighbors as none of their transmission 151 ranges covers other node. In this setting, the neighbors can communicate 152 directly and no routing is required. But, if node A and C want to communicate 153 with each other, they must seek help from node B, who can help them by 154 forwarding their data packets. Here, we can reach this decision that it is quite TE 155 natural. Yes, it could be done as node A knows about B and C knows about B, 156 so both A and C can use B as an intermediate node for their communications! 157 Simple neighbor information could be used in such a case. 158 Example 4.2 Now, the task of routing data packets becomes more complicated EC 159 160 if we consider a model like that presented in Fig. 4.3. 161 With the addition of node D, we have several options to exchange data 162 between A and C. For example, a packet from A can take the path, A-B-C or 163 A-D-C or A-D-B-C or A-B-D-C. This is where we need to employ efficient RR 164 mechanism or logic for routing the packet in the best possible way. The whole 165 166 167 CO 168 169 170 171 172 UN 173 174 175 176 177 178 179 Fig. 4. 3 A MANET with four nodes  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 180 scenario gets even more complicated with the increase of the number of nodes in 181 the network. If two nodes are far from each other and if they must have to 182 communicate using a path involving multiple intermediate nodes, in that case, 183 neighbor information might not be enough to solve the problem. Even if 184 neighbor information is used, it is not possible or inefficient for a MANET to OF 185 provide the full topological information to each node in the network. Because 186 of the mobility of nodes within the network, the scenario becomes more and 187 more complex. Hence, to allow a MANET to operate successfully maintaining 188 all the properties of ad hoc networks, different routing protocols were devel- oped by the practitioners. Sometimes, choosing a single routing protocol does RO 189 190 not provide the complete solution, rather the system and environment settings 191 require different approaches of routing. As we have seen in Figs. 4.2 and 4.3, 192 based on the situation we can apply different routing mechanisms. While only 193 neighbor information is enough for solving the routing problem in Fig. 4.2, some extra mechanism is necessary for efficient routing in case of Fig. 4.3. DP 194 195 196 197 4.3 Routing Protocols 198 199 From the very beginning of the concept of mobile ad hoc network, the research- TE 200 ers took the issue of routing as a major challenge. With the course of time, many 201 routing protocols have been proposed. In this section, we will learn about 202 various routing protocols for MANET, their major aspects, and their relative 203 pros and cons. EC 204 205 206 207 4.3.1 Expected Properties of MANET Routing Protocols 208 RR Considering the special properties of MANET, when thinking about any rout- 209 ing protocol, we generally expect the following properties, though all of these 210 might not be possible to incorporate in a single solution: 211 212  A routing protocol for MANET should be distributed in manner in order to increase its reliability. Where all nodes are mobile, it is unacceptable to have CO 213 214 a routing protocol that requires a centralized entity. Each node should be 215 intelligent enough to make routing decisions using other collaborating 216 nodes. A distributed but virtually centralized protocol might be a good idea. 217  The routing protocol should assume routes as unidirectional links. Wireless medium may cause a wireless link to be opened in unidirection only due to UN 218 219 physical factors. It may not be possible to communicate bidirectionally. 220 Thus a routing protocol must be designed considering unidirectional links. 221  The routing protocol should be power-efficient. It should consider every 222 possible measure to save power, as power is very important for small battery- 223 powered devices. To save power, the routing-related loads could be distrib- 224 uted among the participating nodes.  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 225  The routing protocol should consider its security. MANET routing proto- 226 cols in many cases lack proper security. Generally, a wireless medium is 227 highly vulnerable and susceptible to various sorts of threats and attacks. 228 Because of the use of wireless technology in MANETs, the methods of 229 attacks against such networks are larger in scale than those of their wired OF 230 counterparts [4, 5]. At physical layer, denial of service attacks may be 231 avoided using coded or frequency hopping spread spectrum; however, 232 at routing level, we need authentication for communicating nodes, non- 233 repudiation, and encryption for private networking to shun hostile entities.  Hybrid protocols, which combine the benefits of different routing protocols RO 234 235 can be preferred in most of the cases. A protocol should be much more 236 reactive (which reacts on demand) than proactive (which uses periodic 237 refreshment of information) to avoid protocol overhead. 238  A routing protocol should be aware of Quality of Service (QoS). It should know about the delay and throughput for the route of a source–destination DP 239 240 pair, and must be able to verify its longevity so that a real-time application 241 may rely on it. 242 243 244 4.3.2 Categorizing the Routing Protocols for MANET TE 245 246 One of the most interesting aspects for routing in MANET, which many 247 research works have tried to solve is, whether or not the nodes in the network 248 should keep track of routes to all possible destinations, or instead keep track of EC 249 only those destinations of immediate interest. Generally, a node in MANET 250 does not need a route to a destination until the node is necessarily be the 251 recipient of packets, either as the final destination or as an intermediate node 252 along the path from the source to the destination. As this is still a controversial 253 RR issue, we can assume that the mechanism should not be fixed for all types of 254 settings, instead based on the situation and application at hand, any of the 255 methods could be chosen. 256 Though there is no common consensus about the method of keeping the 257 information about routes in the network, many routing protocols have been CO 258 proposed by this time on the basis of all the available methods. The routing 259 protocols for MANET could be broadly classified into two major categories: 260 261  Proactive Routing Protocols 262  Reactive Routing Protocols UN 263 264 4.3.2.1 Proactive Routing Protocols 265 266 Proactive protocols continuously learn the topology of the network by exchan- 267 ging topological information among the network nodes. Thus, when there is a 268 need for a route to a destination, such route information is available immedi- 269 ately. The main concern regarding using a proactive routing protocol is: if the  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 270 network topology changes too frequently, the cost of maintaining the network 271 might be very high. Moreover, if the network activity is low, the information 272 about the actual topology might even not be used and, in such a case, the 273 investment with such limited transmission ranges and energies is lost, which 274 might result in a shorter lifetime of the network than that is expected. Proactive OF 275 protocols are sometimes called as table-driven routing protocols. 276 277 278 4.3.2.2 Reactive Routing Protocols RO 279 The reactive routing protocols, on the other hand, are based on some sort of 280 query-reply dialog. Reactive protocols proceed for establishing route(s) to the 281 destination only when the need arises or on demand basis. They do not need 282 periodic transmission of topological information of the network; hence, they 283 primarily seem to be resource-conserving protocols. Reactive protocols are also DP 284 known as on-demand routing protocols. 285 286 287 4.3.2.3 Hybrid Routing Protocols 288 289 Often reactive or proactive feature of a particular routing protocol might not be TE 290 enough; instead a mixture might yield better solution. Hence, in the recent days, 291 several hybrid protocols are also proposed. The hybrid protocols include some 292 of the characteristics of proactive protocols and some of the characteristics of 293 reactive protocols. EC 294 Based on the method of delivery of data packets from the source to destina- 295 tion, classification of the MANET routing protocols could be done as follows: 296  Unicast Routing Protocols: The routing protocols that consider sending 297 information packets to a single destination from a single source. 298 RR  Multicast Routing Protocols: Multicast is the delivery of information to a 299 group of destinations simultaneously, using the most efficient strategy to 300 deliver the messages over each link of the network only once, creating copies 301 only when the links to the destinations split. Multicast routing protocols for 302 MANET use both multicast and unicast for data transmission. CO 303 304 Multicast routing protocols for MANET can be classified again into two 305 categories: 306  Tree-based multicast protocol 307  Mesh-based multicast protocol UN 308 309 Mesh-based routing protocols use several routes to reach a destination while 310 the tree-based protocols maintain only one path. Tree-based protocols ensure 311 less end-to-end delay in comparison with the mesh-based protocols. Besides all 312 of these categories, recently some geocast routing protocols are also pro- 313 posed, which aim to send messages to some or all of the wireless nodes within a 314 particular geographic region. Often the nodes know their exact physical  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 315 positions in a network, and these protocols use that information for transmit- 316 ting packets from the source to the destination(s). 317 318 319 OF 320 4.3.3 Proposed Routing Protocols: Major Features 321 322 In this section, we will investigate the major routing protocols for MANET. We 323 will explore their distinctive features with easily understandable examples wher- ever necessary. RO 324 325 326 327 4.3.3.1 Proactive Routing Protocols 328 Dynamic Destination-Sequenced Distance-Vector Routing Protocol DP 329 330 Dynamic Destination-Sequenced Distance-Vector Routing Protocol (DSDV) 331 is developed on the basis of Bellman–Ford routing algorithm with some 332 modifications. In this routing protocol, each mobile node in the network keeps 333 a routing table. Each of the routing table contains the list of all available 334 destinations and the number of hops to each. Each table entry is tagged with TE 335 a sequence number, which is originated by the destination node. Periodic 336 transmissions of updates of the routing tables help maintaining the topology 337 information of the network. If there is any new significant change for the 338 routing information, the updates are transmitted immediately. So, the routing EC 339 information updates might either be periodic or event-driven. DSDV protocol 340 requires each mobile node in the network to advertise its own routing table to its 341 current neighbors. The advertisement is done either by broadcasting or by 342 multicasting. By the advertisements, the neighboring nodes can know about 343 any change that has occurred in the network due to the movements of nodes. RR 344 The routing updates could be sent in two ways: one is called a ‘‘full dump’’ and 345 another is ‘‘incremental.’’ In case of full dump, the entire routing table is sent to 346 the neighbors, whereas in case of incremental update, only the entries that 347 require changes are sent. Full dump is transmitted relatively infrequently when no movement of nodes occur. The incremental updates could be more CO 348 349 appropriate when the network is relatively stable so that extra traffic could be 350 avoided. But, when the movements of nodes become frequent, the sizes of the 351 incremental updates become large and approach the network protocol data unit 352 (NPDU). Hence, in such a case, full dump could be used. Each of the route update packets also has a sequence number assigned by the transmitter. For UN 353 354 updating the routing information in a node, the update packet with the highest 355 sequence number is used, as the highest number means the most recent update 356 packet. Each node waits up to certain time interval to transmit the advertise- 357 ment message to its neighbors so that the latest information with better route to 358 a destination could be informed to the neighbors. Let us explain DSDV routing 359 protocol with an example.  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 360 361 362 363 364 OF 365 366 367 368 RO 369 370 371 Fig. 4.4 A sample MANET using DSDV 372 373 Example 4.3 Figure 4.4 shows a sample network consisting of six mobile nodes. DP 374 375 Table 1.1 shows a sample structure of the forwarding table maintained in node 376 M2. The Install time field helps determine when to delete a stale route. As in 377 DSDV, any change in the routing path is immediately propagated throughout 378 the network, it is very rare that deletion of stale routes occur. The Stable_data 379 field contains the pointers that are needed to be stored when there is a competi- TE 380 tion with other possible routes to any particular destination. Table 1.2 shows a 381 sample advertisement table of node M2 using DSDV. 382 Now, in Fig. 4.4, if a node, say M3, moves close to M6, only the entry for M3 383 needs to be changed. After some time M2 will get the information of M3 from EC 384 M4, as M4 will get the information about M3 from M6, and accordingly M2 385 can adjust the entry for M3 in its own routing (forwarding) table. If M3 quits 386 the network after some time interval, its entry will be deleted from M2’s routing 387 table. 388 RR 389 390 Wireless Routing Protocol 391 Wireless Routing Protocol (WRP) belongs to the general class of path-finding 392 algorithms [8, 10, 11], defined as the set of distributed shortest-path algorithms CO 393 394 that calculate the paths using information regarding the length and second-to-last 395 hop of the shortest path to each destination. WRP reduces the number of cases in 396 397 Table 1.1 Structure of node M2’s forwarding table UN 398 Destination Next Hop Metric Sequence Number Install Flags Stable_data 399 M1 M1 1 S593_M1 T001_M2 – Ptrl_M1 400 M2 M2 0 S983_M2 T001_M2 – Ptrl_M2 401 M3 M3 1 S193_M3 T002_M2 – Ptrl_M3 402 M4 M4 1 S233_M4 T001_M2 – Ptrl_M4 403 M5 M4 2 S243_M5 T001_M2 – Ptrl_M5 404 M6 M4 2 S053_M6 T002_M2 – Ptrl_M6  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 405 Table 1.2 Route table advertised by node M2 406 Destination Metric Sequence Number 407 M1 1 S593_M1 408 M2 0 S983_M2 409 M3 1 S193_M3 OF 410 M4 1 S233_M4 411 M5 2 S243_M5 M6 2 S053_M6 412 413 RO 414 which a temporary routing loop can occur. For the purpose of routing, each node 415 maintains four things: 416 417 1. A distance table 418 2. A routing table DP 419 3. A link-cost table 420 4. A message retransmission list (MRL) 421 The distance table of node x contains the distance of each destination node y 422 423 via each neighbor z of x and the predecessor node reported by z. The routing 424 table of node x is a vector with an entry for each known destination y, which TE 425 specifies: 426  The identifier of the destination y 427  The distance to the destination y 428  The predecessor of the chosen shortest path to y EC 429  The successor of the chosen shortest path to y 430  A tag to identify whether the entry is a simple path, a loop, or invalid 431  Storing predecessor and successor in the table is beneficial to detect loops 432 and to avoid count-to-infinity problems. 433 RR 434 The link-cost table of node x lists the cost of relaying information through 435 each neighbor z, and the number of periodic update periods that have elapsed 436 since node x received any error-free message from z. The message retransmis- 437 sion list (MRL) contains information to let a node know which of its neighbors has not acknowledged its update message and to retransmit the update message CO 438 439 to that neighbor. 440 WRP uses periodic update message transmissions to the neighbors of a node. 441 The nodes in the response list of update message (which is formed using MRL) 442 should send acknowledgments. If there is no change from the last update, the nodes in the response list should send an idle Hello message to ensure connec- UN 443 444 tivity. A node can decide whether to update its routing table after receiving an 445 update message from a neighbor and always it looks for a better path using the 446 new information. If a node gets a better path, it relays back that information to 447 the original nodes so that they can update their tables. After receiving the 448 acknowledgment, the original node updates its MRL. Thus, each time the 449 consistency of the routing information is checked by each node in this protocol,  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 450 which helps to eliminate routing loops and always tries to find out the best 451 solution for routing in the network. 452 453 454 Cluster Gateway Switch Routing Protocol OF 455 Cluster Gateway Switch Routing Protocol (CGSR) considers a clustered 456 mobile wireless network instead of a ‘‘flat’’ network. For structuring the net- 457 work into separate but interrelated groups, cluster heads are elected using a 458 cluster head selection algorithm. By forming several clusters, this protocol RO 459 achieves a distributed processing mechanism in the network. However, one 460 drawback of this protocol is that, frequent change or selection of cluster 461 heads might be resource hungry and it might affect the routing performance. 462 CGSR uses DSDV protocol as the underlying routing scheme and, hence, it has 463 the same overhead as DSDV. However, it modifies DSDV by using a hierarch- DP 464 ical cluster-head-to-gateway routing approach to route traffic from source to 465 destination. Gateway nodes are nodes that are within the communication 466 ranges of two or more cluster heads. A packet sent by a node is first sent to its 467 cluster head, and then the packet is sent from the cluster head to a gateway to 468 another cluster head, and so on until the cluster head of the destination node is 469 TE reached. The packet is then transmitted to the destination from its own cluster 470 head. 471 472 Example 4.4 Figure 4.5 shows two clusters C1 and C2 each of which has a 473 cluster head. A gateway is the common node between two clusters. Any source EC 474 node passes the packet first to its own cluster head, which in turn passes that to 475 the gateway. 476 The gateway relays the packet to another cluster head and this process 477 continues until the destination is reached. In this method, each node must 478 keep a ‘‘cluster member table’’ where it stores the destination cluster head for RR 479 each mobile node in the network. These cluster member tables are broadcasted 480 by each node periodically using the DSDV algorithm. Nodes update their 481 482 CO 483 484 485 486 487 UN 488 489 490 491 492 493 494 Fig. 4.5 Clustered MANET  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 495 cluster member tables on reception of such a table from a neighbor. Also each 496 node maintains a routing table that is used to determine the next hop to reach 497 the destination. 498 499 Global State Routing OF 500 501 In Global State Routing (GSR) protocol , nodes exchange vectors of link states 502 among their neighbors during routing information exchange. Based on the link 503 state vectors, nodes maintain a global knowledge of the network topology and optimize their routing decisions locally. Functionally, this protocol is similar to RO 504 505 DSDV, but it improves DSDV in the sense that it avoids flooding of routing 506 messages. In this protocol, each node maintains one list and three tables. They are: 507  A neighbor list 508  A topology table DP 509  A next hop table 510  A distance table 511 512 Neighbor list contains the set of neighboring nodes of a particular node x. 513 Each destination y has an entry in the topology table of x. Each entry in this 514 topology table has two parts, one is the link state information reported by TE 515 destination y and the other is the timestamp indicating the time node y has 516 generated this link state information. Next hop contains the identity of the next 517 hop node, to which a packet is to be forwarded to reach a particular destination. 518 The distance table contains the shortest distance between x and y. EC 519 Though the operational structure of GSR is similar to DSDV, it does not 520 flood the link state packets. Instead, in this protocol nodes maintain link state 521 table based on the up-to-date information received from neighboring nodes, 522 and periodically exchange it with their local neighbors only. Information dis- 523 seminated as the link state with larger sequence number replaces the one with RR 524 smaller sequence number. 525 526 Fisheye State Routing 527 Fisheye State Routing (FSR) is built on top of GSR. The novelty of FSR is CO 528 that it uses a special structure of the network called the ‘‘fisheye.’’ This protocol 529 reduces the amount of traffic for transmitting the update messages. The basic 530 idea is that each update message does not contain information about all nodes. 531 Instead, it contains update information about the nearer nodes more frequently 532 than that of the farther nodes. Hence, each node can have accurate and exact UN 533 information about its own neighboring nodes. The following example explains 534 the fisheye state routing protocol. 535 536 Example 4.5 In FSR, the network is viewed as a fisheye by each participating 537 node. An example of this special structure is shown in Fig. 4.6. 538 Here, the scope of fisheye is defined as the set of nodes that can be reached 539 within a given number of hops from a particular center node. In the figure, we  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 540 541 542 543 544 OF 545 546 547 548 RO 549 550 551 552 553 DP 554 555 Fig. 4.6 Fisheye structure 556 557 have shown three scopes with one, two, and three hops. The center node has the 558 most accurate information about all nodes in the white circle and so on. Each 559 circle contains the nodes of a particular hop from a center node. The advantage TE 560 of FSR is that, even if a node does not have accurate information about a 561 destination, as the packet moves closer to the destination, more correct infor- 562 mation about the route to the destination becomes available. 563 EC 564 Hierarchical State Routing 565 566 Hierarchical State Routing (HSR) combines dynamic, distributed multilevel 567 hierarchical clustering technique with an efficient location management scheme. 568 This protocol partitions the network into several clusters where each elected cluster RR 569 head at the lower level in the hierarchy becomes member of the next higher level. 570 The basic idea of HSR is that each cluster head summarizes its own cluster 571 information and passes it to the neighboring cluster heads using gateways. After 572 running the algorithm at any level, any node can flood the obtained information to its lower level nodes. The hierarchical structure used in this protocol is efficient CO 573 574 enough to deliver data successfully to any part of the network. 575 Example 4.6 Figure 4.7 shows the clustering and hierarchy used in HSR. Here, 576 each node has a hierarchical address by which it could be reached. A gateway 577 can be reached from the root via more than one path; hence it can have more UN 578 than one hierarchical address. 579 580 Zone-Based Hierarchical Link State Routing Protocol 581 582 In Zone-Based Hierarchical Link State Routing (ZHLS) protocol , the 583 network is divided into non-overlapping zones as in cellular networks. Each 584 node knows the node connectivity within its own zone and the zone connectivity  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 585 586 587 588 589 OF 590 591 592 593 RO 594 595 596 597 598 DP 599 600 601 602 603 604 TE 605 606 607 608 Fig. 4.7 Clustering and hierarchical structure used in HSR EC 609 610 611 information of the entire network. The link state routing is performed by 612 employing two levels: node level and global zone level. ZHLS does not have 613 any cluster head in the network like other hierarchical routing protocols. The RR 614 zone level topological information is distributed to all nodes. Since only zone 615 ID and node ID of a destination are needed for routing, the route from a source 616 to a destination is adaptable to changing topology. The zone ID of the destina- 617 tion is found by sending one location request to every zone. CO 618 619 Landmark Ad Hoc Routing 620 621 Landmark Ad Hoc Routing (LANMAR) combines the features of Fisheye 622 State Routing (FSR) and Landmark Routing. It uses the concept of land- mark from Landmark Routing, which was originally developed for fixed wide UN 623 624 area networks. A landmark is defined as a router whose neighbor routers within 625 a certain number of hops contain routing entries for that router. Using this 626 concept for the nodes in the MANET, LANMAR divides the network into 627 several pre-defined logical subnets, each with a pre-selected landmark. All nodes 628 in a subnet are assumed to move as a group, and they remain connected to each 629 other via Fisheye State Routing (FSR). The routes to the landmarks, and hence  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 630 the corresponding subnets, are proactively maintained by all nodes in the net- 631 work through the exchange of distance-vectors. LANMAR could be regarded 632 as an extension of FSR, which exploits group mobility by summarizing the 633 routes to the group members with a single route to a landmark. 634 OF 635 636 Optimized Link State Routing 637 Optimized Link State Routing (OLSR) protocol inherits the stability of link 638 state algorithm. Usually, in a pure link state protocol, all the links with neighbor RO 639 nodes are declared and are flooded in the entire network. But, OLSR is an 640 optimized version of a pure link state protocol designed for MANET. This 641 protocol performs hop-by-hop routing; that is, each node in the network uses its 642 most recent information to route a packet. Hence, even when a node is moving, 643 its packets can be successfully delivered to it, if its speed is such that its move- DP 644 ments could at least be followed in its neighborhood. The optimization in the 645 routing is done mainly in two ways. Firstly, OLSR reduces the size of the 646 control packets for a particular node by declaring only a subset of links with 647 the node’s neighbors who are its multipoint relay selectors, instead of all links in 648 the network. Secondly, it minimizes flooding of the control traffic by using only 649 the selected nodes, called multipoint relays to disseminate information in the TE 650 network. As only multipoint relays of a node can retransmit its broadcast 651 messages, this protocol significantly reduces the number of retransmissions in 652 a flooding or broadcast procedure. 653 EC 654 Example 4.7 Figure 4.8 shows a sample network structure used in OLSR. 655 OLSR protocol relies on the selection of multipoint relay (MPR) nodes. 656 Each node calculates the routes to all known destinations through these 657 nodes. These MPRs are selected among the one hop neighborhood of a node 658 using the bidirectional links, and they are used to minimize the amount of RR 659 broadcast traffic in the network. 660 661 4.3.3.2 Reactive Routing Protocols 662 All of the protocols mentioned in the previous section use periodic transmis- CO 663 664 sions of routing information. In this section, we will investigate the working 665 principles of some reactive routing protocols for mobile ad hoc networks. As 666 stated earlier, unlike proactive protocols, reactive protocols proceed for finding 667 a route to a destination only when a source node needs to transmit data to another node in the network. UN 668 669 670 Associativity-Based Routing 671 672 Associativity-Based Routing (ABR) protocol defines a new type of routing 673 metric for mobile ad hoc networks. This routing metric is termed as degree of 674 association stability. In this routing protocol, a route is selected based on the  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 675 676 677 678 679 OF 680 681 682 683 RO 684 685 686 687 688 DP 689 690 691 692 Fig. 4.8 Multipoint Relays (MPRs) are in gray color. The transmitting node is shown at the 693 center of the sample structure 694 TE 695 degree of association stability of mobile nodes. Each node periodically gener- 696 ates beacon to announce its existence. Upon receiving the beacon message, a 697 neighbor node updates its own associativity table. For each beacon received, the 698 associativity tick of the receiving node with the beaconing node is increased. A EC 699 high value of associativity tick for any particular beaconing node means that the 700 node is relatively static. Associativity tick is reset when any neighboring node 701 moves out of the neighborhood of any other node. ABR protocol has three 702 phases for the routing operations: 703  Route discovery RR 704  Route reconstruction 705  Route deletion 706 707 The route discovery phase is done by a broadcast query and await-reply (BQ- REPLY) cycle. When a source node wants to send message to a destination, it CO 708 709 sends the query. All other nodes receiving the query append their addresses and 710 their associativity ticks with their neighbors along with QoS information to the 711 query packet. A downstream node erases its immediate upstream node’s asso- 712 ciativity tick entries and retains only the entry concerned with itself and its upstream node. This process continues and eventually the packet reaches the UN 713 714 destination. On receiving the packet with the associativity information, the 715 destination chooses the best route and sends the REPLY packet using that 716 path. If there are multiple paths with same overall degree of association stabi- 717 lity, the route with the minimum number of hops is selected. Route reconstruc- 718 tion is needed when any path becomes invalid or broken for the mobility or 719 failure of any intermediate node. If a source or upstream node moves, a route  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 720 721 722 723 724 OF 725 726 727 728 RO 729 730 731 732 (a) (b) 733 Fig. 4. 9 Route maintenance in ABR for two different scenarios DP 734 735 736 notification (RN) message is used to erase the route entries associated with 737 downstream nodes. When the destination node moves, the destination’s 738 immediate upstream node erases its route. A localized query (LQ[H]) process, 739 where H refers to the hop count from the upstream node to the destination, is TE 740 initiated to determine whether the node is still reachable or not. Route deletion 741 broadcast is done if any discovered route is no longer needed. Figure 4.9 shows 742 the working principle of ABR protocol. 743 Example 4.8 Figure 4.9 shows two different scenarios for route maintenance EC 744 745 where ABR is used. In Figure 4.9(a), the source moves to another place, as a 746 result of which a new BQ request is used to find out the route to the destination. 747 The RN message is used to erase the route entries associated with the 748 downstream nodes. In Figure 4.9(b), the destination changed its position. RR 749 Hence, immediate upstream node erases its route and determines if the node 750 is still reachable by a localized query (LQ[H]) process. 751 752 Signal Stability–Based Adaptive Routing Protocol CO 753 754 Signal Stability–Based Adaptive Routing (SSA) protocol focuses on 755 obtaining the most stable routes through an ad hoc network. The protocol 756 performs on-demand route discovery based on signal strength and location 757 stability. Based on the signal strength, SSA detects weak and strong channels in the network. SSA can be divided into two cooperative protocols: the Dynamic UN 758 759 Routing Protocol (DRP) and the Static Routing Protocol (SRP). DRP uses two 760 tables: Signal Stability Table (SST) and Routing Table (RT). SST stores the 761 signal strengths of the neighboring nodes obtained by periodic beacons from 762 the link layer of each neighboring node. These signal strengths are recorded as 763 weak or strong. DRP receives all the transmissions and, after processing, it 764 passes those to the SRP. SRP passes the packet to the node’s upper layer stack if  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 765 it is the destination. Otherwise, it looks for the destination in routing table and 766 forwards the packet. If there is no entry in the routing table for that destination, 767 it initiates the route-finding process. Route-request packets are forwarded to 768 the neighbors using the strong channels. The destination, after getting the 769 request, chooses the first arriving request packet and sends back the reply. OF 770 The DRP reverses the selected route and sends a route-reply message back to 771 the initiator of route-request. The DRPs of the nodes along the path update 772 their routing tables accordingly. In case of a link failure, the intermediate nodes 773 send an error message to the source indicating which channel has failed. The source in turn sends an erase message to inform all nodes about the broken link RO 774 775 and initiates a new route-search process to find a new path to the destination. 776 777 778 Temporarily Ordered Routing Algorithm DP 779 Temporally Ordered Routing Algorithm (TORA) is a reactive routing 780 protocol with some proactive enhancements where a link between nodes is 781 established creating a Directed Acyclic Graph (DAG) of the route from the 782 source node to the destination. This protocol uses a ‘‘link reversal’’ model in 783 route discovery. A route discovery query is broadcasted and propagated 784 TE throughout the network until it reaches the destination or a node that has 785 information about how to reach the destination. TORA defines a parameter, 786 termed height. Height is a measure of the distance of the responding node’s 787 distance up to the required destination node. In the route discovery phase, this 788 parameter is returned to the querying node. As the query response propagates EC 789 back, each intermediate node updates its TORA table with the route and height 790 to the destination node. The source node then uses the height to select the best 791 route toward the destination. This protocol has an interesting property that it 792 frequently chooses the most convenient route, rather than the shortest route. 793 RR For all these attempts, TORA tries to minimize the routing management traffic 794 overhead. 795 796 797 Cluster-Based Routing Protocol CO 798 799 Cluster-Based Routing Protocol (CBRP) is an on-demand routing proto- 800 col, where the nodes are divided into clusters. For cluster formation, the 801 following algorithm is employed. When a node comes up in the network, it 802 has the undecided state. The first task of this node is to start a timer and to broadcast a HELLO message. When a cluster-head receives this HELLO UN 803 804 message, it replies immediately with a triggered HELLO message. After that, 805 when the node receives this answer, it changes its state into the member state. 806 But when the node gets no message from any cluster-head, it makes itself as a 807 cluster-head, but only when it has bidirectional link to one or more neighbor 808 nodes. Otherwise, when it has no link to any other node, it stays in the undecided 809 state and repeats the procedure with sending a HELLO message again.  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 810 Each node has a neighbor table. For each neighbor, the node keeps the status 811 of the link and state of the neighbor in the neighbor table. A cluster head keeps 812 information about all of its members in the same cluster. It also has a cluster 813 adjacency table, which provides information about the neighboring clusters. 814 OF 815 Example 4.9 The network structure shown in Fig. 4.5 could be used to explain 816 the clustering used in CBRP. However, while CGSR is a proactive routing 817 protocol, CBRP is a reactive or on-demand routing protocol. Though the basic 818 clustering mechanisms are same, the difference lies in the method of routing in the network. In case of CBRP, for sending data packets a source node floods RO 819 820 route-request packet to the neighboring cluster heads. On receiving the request, 821 a cluster head checks whether the destination node is its own cluster or not. If it 822 is within that cluster, it sends the request to the node, and if not, it again sends 823 the request to the neighboring cluster head. This process continues and the destination eventually gets the route request. The reply from the destination is DP 824 825 sent using the reverse path of the route. In case of a route failure, a local repair 826 mechanism is used. When a node finds the next hop is unreachable, it checks 827 whether the next hop can be reached through any of its neighbors or whether 828 the hop after the next hop can be reached via any other neighbor. If any of these 829 works, the packet can be routed using the repaired path. TE 830 831 832 Dynamic Source Routing 833 Dynamic Source Routing (DSR) allows nodes in the MANET to dynami- EC 834 cally discover a source route across multiple network hops to any destination. 835 In this protocol, the mobile nodes are required to maintain route caches or the 836 known routes. The route cache is updated when any new route is known for a 837 particular entry in the route cache. 838 Routing in DSR is done using two phases: route discovery and route main- RR 839 tenance. When a source node wants to send a packet to a destination, it first 840 consults its route cache to determine whether it already knows about any route 841 to the destination or not. If already there is an entry for that destination, the 842 source uses that to send the packet. If not, it initiates a route request broadcast. CO 843 This request includes the destination address, source address, and a unique 844 identification number. Each intermediate node checks whether it knows about 845 the destination or not. If the intermediate node does not know about the 846 destination, it again forwards the packet and eventually this reaches the desti- 847 nation. A node processes the route request packet only if it has not previously UN 848 processed the packet and its address is not present in the route record of the 849 packet. A route reply is generated by the destination or by any of the inter- 850 mediate nodes when it knows about how to reach the destination. Figure 4.10 851 shows the operational method of the dynamic source routing protocol. 852 853 Example 4.10 In Fig. 4.10, the route discovery procedure is shown where S1 is 854 the source node and S7 is the destination node.  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 855 856 857 858 859 OF 860 861 (a) 862 863 RO 864 865 866 867 868 DP 869 870 871 (b) 872 873 Fig. 4.10 (a) Route Discovery (b) Using route record to send the route reply 874 TE In this example, the destination gets the request through two paths. It 875 chooses one path based on the route records in the incoming request packet 876 and accordingly sends a reply using the reverse path to the source node. At each 877 hop, the best route with minimum hop is stored. In this example, we have shown 878 the route record status at each hop to reach the destination from the source EC 879 node. Here, the chosen route is S1-S2-S4-S5-S7. 880 881 882 Ad Hoc On-Demand Distance Vector Routing 883 RR 884 Ad Hoc On-Demand Distance Vector Routing (AODV) is basically an 885 improvement of DSDV. But, AODV is a reactive routing protocol instead of 886 proactive. It minimizes the number of broadcasts by creating routes based on 887 demand, which is not the case for DSDV. When any source node wants to send a packet to a destination, it broadcasts a route request (RREQ) packet. The CO 888 889 neighboring nodes in turn broadcast the packet to their neighbors and the 890 process continues until the packet reaches the destination. During the process 891 of forwarding the route request, intermediate nodes record the address of the 892 neighbor from which the first copy of the broadcast packet is received. This record is stored in their route tables, which helps for establishing a reverse path. UN 893 894 If additional copies of the same RREQ are later received, these packets are 895 discarded. The reply is sent using the reverse path. 896 For route maintenance, when a source node moves, it can re-initiate a route 897 discovery process. If any intermediate node moves within a particular route, the 898 neighbor of the drifted node can detect the link failure and sends a link failure 899 notification to its upstream neighbor. This process continues until the failure  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 900 901 902 903 904 OF 905 906 907 908 (a) RO 909 910 911 912 913 DP 914 915 916 917 918 919 (b) TE 920 Fig. 4. 11 AODV protocol (a) Source node broadcasting the route request packet. (b) Route 921 reply is sent by the destination using the reverse path 922 923 notification reaches the source node. Based on the received information, the EC 924 source might decide to re-initiate the route discovery phase. Figure 4.11 shows 925 an example of AODV protocol’s operational mechanism. 926 Example 4.11 In Fig. 4.11, S1 is the source node and S7 is the destination node. 927 The source initiates the route request and the route is created based on demand. 928 RR Route reply is sent using the reverse path from the destination. 929 930 931 4.3.3.3 Hybrid Routing Protocols 932 Dual-Hybrid Adaptive Routing CO 933 934 Dual-Hybrid Adaptive Routing (DHAR) uses the Distributed Dynamic 935 Cluster Algorithm (DDCA) presented in. The idea of DDCA is to dyna- 936 mically partition the network into some non-overlapping clusters of nodes 937 consisting of one parent and zero or more children. Routing is done in DHAR utilizing a dynamic two-level hierarchical strategy, consisting of opti- UN 938 939 mal and least-overhead table-driven algorithms operating at each level. 940 DHAR implements a proactive least-overhead level-2 routing protocol in 941 combination with a dynamic binding protocol to achieve its hybrid character- 942 istics. The level-2 protocol in DHAR requires that one node generates an 943 update on behalf of its cluster. When a level-2 update is generated, it must be 944 flooded to all the nodes in each neighboring cluster. Level-2 updates are not  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 945 transmitted beyond the neighboring clusters. The node with the lowest node ID 946 in each cluster is designated to generate level-2 updates. The binding process is 947 similar to a reactive route discovery process; however, a priori knowledge of 948 clustered topology makes it significantly more efficient and simpler to accom- 949 plish the routing. To send packets to the desired destination, a source node uses OF 950 the dynamic binding protocol to discover the current cluster ID associated with 951 the destination. Once determined, this information is maintained in the 952 dynamic cluster binding cache at the source node. The dynamic binding proto- 953 col utilizes the knowledge of the level-2 topology to efficiently broadcast a binding request to all the clusters. This is achieved using reverse path forward- RO 954 955 ing with respect to the source cluster. 956 957 Adaptive Distance Vector Routing 958 Adaptive Distance Vector (ADV) routing protocol is a distance-vector DP 959 routing algorithm that exhibits some on-demand features by varying the fre- 960 quency and the size of routing updates in response to the network load and 961 mobility patterns. This protocol has the benefits of both proactive and reactive 962 routing protocols. ADV uses an adaptive mechanism to mitigate the effect of 963 periodic transmissions of the routing updates, which basically relies on the 964 TE network load and mobility conditions. To reduce the size of routing updates, 965 ADV advertises and maintains routes for the active receivers only. A node is 966 considered active if it is the receiver of any currently active connection. There is 967 a receiver flag in the routing entry, which keeps the information about the status 968 of a receiver whether it is active or inactive. To send data, a source node EC 969 broadcasts network-wide an init-connection control packet. All the other 970 nodes turn on the corresponding receiver flag in their own routing tables and 971 start advertising the routes to the receiver in future updates. When the destina- 972 tion node gets the init-connection packet, it responds to it by broadcasting a 973 RR receiver-alert packet and becomes active. To close a connection, the source node 974 broadcasts network-wide an end-connection control packet, indicating that the 975 connection is to be closed. If the destination node has no additional active 976 connection, it broadcasts a non-receiver-alert message. If the init-connection and 977 receiver-alert messages are lost, the source advertises the receiver’s entry with its CO 978 receiver flag set in all future updates. ADV also defines some other parameters 979 like trigger meter, trigger threshold, and buffer threshold. These are used for 980 limiting the network traffic based on the network’s mobility pattern and net- 981 work speed. 982 UN 983 Zone Routing Protocol 984 985 Zone Routing Protocol (ZRP) is suitable for wide variety of MANETs, 986 especially for the networks with large span and diverse mobility patterns. In this 987 protocol, each node proactively maintains routes within a local region, which is 988 termed as routing zone. Route creation is done using a query-reply mechanism. 989 For creating different zones in the network, a node first has to know who its  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 990 neighbors are. A neighbor is defined as a node with whom direct communica- 991 tion can be established, and that is, within one hop transmission range of a 992 node. Neighbor discovery information is used as a basis for Intra-zone Rout- 993 ing Protocol (IARP), which is described in detail in. Rather than blind 994 broadcasting, ZRP uses a query control mechanism to reduce route query OF 995 traffic by directing query messages outward from the query source and away 996 from covered routing zones. A covered node is a node which belongs to the 997 routing zone of a node that has received a route query. During the forwarding 998 of the query packet, a node identifies whether it is coming from its neighbor or RO 999 not. If yes, then it marks all of its known neighboring nodes in its same zone as 1000 covered. The query is thus relayed till it reaches the destination. The destina- 1001 tion in turn sends back a reply message via the reverse path and creates the 1002 route. 1003 DP 1004 1005 Sharp Hybrid Adaptive Routing Protocol 1006 1007 Sharp Hybrid Adaptive Routing Protocol (SHARP) combines the features 1008 of both proactive and reactive routing mechanisms. SHARP adapts between 1009 reactive and proactive routing by dynamically varying the amount of routing TE 1010 information shared proactively. This protocol defines the proactive zones 1011 around some nodes. The number of nodes in a particular proactive zone is 1012 determined by the node-specific zone radius. All nodes within the zone radius of 1013 a particular node become the member of that particular proactive zone for that EC 1014 node. If for a given destination a node is not present within a particular 1015 proactive zone, reactive routing mechanism (query-reply) is used to establish 1016 the route to that node. Proactive routing mechanism is used within the proac- 1017 tive zone. Nodes within the proactive zone maintain routes proactively only 1018 with respect to the central node. In this protocol, proactive zones are created RR 1019 automatically if some destinations are frequently addressed or sought within 1020 the network. The proactive zones act as collectors of packets, which forward the 1021 packets efficiently to the destination, once the packets reach any node at the 1022 zone vicinity. CO 1023 1024 Example 4.12 In Fig. 4.12, some proactive zones are shown in a sample 1025 MANET. Here, we have four destination nodes, A, B, C, and D. As destination 1026 D is not used heavily, no proactive zone is created within its surroundings. 1027 But for the other three destinations, A, B, and C, proactive zones of different sizes are created. As node A has the highest number of calls within the network UN 1028 1029 as a destination, its proactive zone is the largest among all the destinations. Any 1030 routing within the proactive zone is done using proactive routing mechanisms. 1031 But, outside of the proactive zones, reactive routings are employed. The zone 1032 radius acts as a virtual knob to control the mix of proactive and reactive routing 1033 for each destination in SHARP. For example, in case of destination D in the 1034 figure, reactive mechanism is used.  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 1035 1036 1037 1038 1039 OF 1040 1041 1042 1043 RO 1044 1045 1046 1047 1048 DP 1049 1050 1051 1052 Fig. 4.12 Proactive zones around the hot destinations in SHARP 1053 1054 Neighbor-Aware Multicast Routing Protocol TE 1055 1056 Neighbor-Aware Multicast Routing Protocol (NAMP) is a tree-based 1057 hybrid routing protocol, which utilizes neighborhood information. The routes 1058 in the network are built and maintained using the traditional request and reply EC 1059 messages or on-demand basis. This hybrid protocol uses neighbor information 1060 of two-hops away for transmitting the packets to the receiver. If the receiver is 1061 not within this range, it searches the receiver using dominant pruning flooding 1062 method and forms a multicast tree using the replies along the reverse path. 1063 Although the mesh structure is known to be more robust against topological RR 1064 changes, the tree structure is better in terms of packet transmission. As NAMP 1065 targets to achieve less end-to-end delay of packets, it uses the tree structure. 1066 There are mainly three operations addressed in NAMP: 1067  Multicast tree creation CO 1068  Multicast tree maintenance 1069  Joining and leaving of nodes from the multicast group 1070 1071 All the nodes in the network keep neighborhood information of up to two- 1072 hop away nodes. This neighborhood information is maintained using a proac- tive mechanism. Periodic hello packet is used for this. To create the multicast UN 1073 1074 tree, the source node sends a flood request packet to the destination with data 1075 payload attached. This packet is flooded in the network using dominant prun- 1076 ing method, which actually minimizes the number of transmissions in the net- 1077 work for a particular flood request packet. During the forwarding process of the 1078 packet, each node selects a forwarder and creates a secondary forwarder list 1079 (SFL). The secondary forwarder list (SFL) contains the information about the  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 1080 nodes that were primarily considered as possible forwarders but finally were not 1081 selected for that purpose. Each intermediate node uses the chosen forwarder to 1082 forward the packet, but keeps the knowledge about other possible forwarders in 1083 SFL. Secondary forwarder list is used for repairing any broken route in the net- 1084 work. In fact, link failure recovery is one of the greatest advantages of NAMP. The OF 1085 next example shows some figures to explain NAMP’s operations in brief. 1086 1087 Example 4.13 Figure 4.13 shows a sample network where NAMP has created 1088 the multicast tree consisting of the source, destination, and intermediate nodes (forwarders). Here, S1 is the source, S12 is the destination. Nodes S3, S6, S9, RO 1089 1090 and S11 are the forwarding nodes. For each forwarding hop, each forwarder 1091 maintains the information of the neighboring nodes in the secondary forwarder 1092 list. In case of a link failure as shown in Fig. 4.13(b), S3 immediately finds an 1093 alternate path to repair the existing route for the S1-S12 source–destination pair. Figure 4.13(c) shows that S3 repairs the path to use the existing route to DP 1094 1095 1096 1097 1098 1099 TE 1100 1101 1102 1103 (a) EC 1104 1105 1106 1107 1108 RR 1109 1110 1111 1112 CO 1113 (b) 1114 1115 1116 1117 UN 1118 1119 1120 1121 1122 (c) 1123 1124 Fig. 4.13 (a) Network sample (b) Link failure (c) Link failure recovery in NAMP  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 1125 reach the destination using the alternate node S7. Link failure recovery is done 1126 locally in NAMP, which is one of its greatest advantages. 1127 1128 1129 4.3.3.4 Other Routing Protocols OF 1130 In addition to the mentioned routing protocols for MANET, there are some 1131 other routing protocols that do not rely on any traditional routing mechanisms, 1132 instead rely on the location awareness of the participating nodes in the network. 1133 Generally, in traditional MANETs, the nodes are addressed only with their IP RO 1134 addresses. But, in case of location-aware routing mechanisms, the nodes are 1135 1136 often aware of their exact physical locations in the three-dimensional world. 1137 This capability might be introduced in the nodes using Global Positioning 1138 System (GPS) or with any other geometric methods. GPS is a worldwide, satellite-based radio navigation system that consists of 24 satellites in six orbital DP 1139 1140 planes. By connecting to the GPS receiver, a mobile node can know its current 1141 physical location. Also sometimes the network is divided into several zones or 1142 geographic regions for making routing little bit easier. Based on these concepts, 1143 several geocast and location-aware routing protocols have already been pro- 1144 posed. Geocasting is basically a variant of the conventional multicasting where TE 1145 the nodes are considered under certain groups within particular geographical 1146 regions. In geocasting, the nodes eligible to receive packets are implicitly 1147 specified by a physical region; membership in a geocast group changes when- 1148 ever a mobile node moves in or out of the geocast region. EC 1149 The major feature of these routing protocols is that, when a node knows 1150 about the location of a particular destination, it can direct the packets toward 1151 that particular direction from its current position, without using any route 1152 discovery mechanism. Recently, some of the researchers proposed some loca- 1153 tion-aware protocols that are based on these sorts of idea. Some of the examples RR 1154 of them are Geographic Distance Routing (GEDIR) , Location-Aided 1155 Routing (LAR) , Greedy Perimeter Stateless Routing (GPSR) , Geo- 1156 GRID , Geographical Routing Algorithm (GRA) , etc. Other than 1157 these, there are a number of multicast routing protocols for MANET. Some of the mentionable multicast routing protocols are: Location-Based Multicast CO 1158 1159 Protocol (LBM) , Multicast Core Extraction Distributed Ad hoc Routing 1160 (MCEDAR) , Ad hoc Multicast Routing protocol utilizing Increasing id- 1161 numberS (AMRIS) , Associativity-Based Ad hoc Multicast (ABAM) , 1162 Multicast Ad hoc On-Demand Distance-Vector (MAODV) routing , Dif- ferential Destination Multicast (DDM) , On-Demand Multicast Routing UN 1163 1164 Protocol (ODMRP) , Adaptive Demand-driven Multicast Routing 1165 (ADMR) protocol , Ad hoc Multicast Routing protocol (AMRoute) , 1166 Dynamic Core-based Multicast routing Protocol (DCMP) , Preferred Link- 1167 Based Multicast protocol (PLBM) , etc. Some of these multicast protocols 1168 use location information and some are based on other routing protocols or 1169 developed just as the extension of another unicast routing protocol. For  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 1170 1171 1172 1173 1174 OF 1175 1176 1177 1178 RO 1179 1180 1181 1182 1183 DP 1184 1185 1186 1187 1188 1189 TE 1190 1191 1192 Fig. 4.14 Major Routing Protocols for MANET at a glance 1193 EC 1194 example, MAODV is the multicast-supporting version of AODV. Figure 4.14 1195 shows the major routing protocols for MANET at a glance. 1196 1197 4.3.3.5 Other Recent Works on MANET Routing for Reference 1198 RR 1199 In this section, we mention a list of references of the recent works on routing in 1200 MANET so that it could be used as a reference by the practitioners. Some of 1201 these works have taken the major routing protocols as their bases and some of 1202 them have enhanced various performances of the previous routing protocols. Mentionable recent works are: node-density-based routing , load-balanced CO 1203 1204 routing , optimized priority-based energy-efficient routing , reliable on- 1205 demand routing with mobility prediction , QoS routing , secure distrib- 1206 uted anonymous routing protocol , robust position-based routing , 1207 routing with group motion support , dense cluster gateway based routing protocol , dynamic backup routes routing protocol , gathering-based UN 1208 1209 routing protocol , QoS-aware multicast routing protocol , recycled path 1210 routing , QoS multicast routing protocol for clustering in MANET , 1211 secure anonymous routing protocol with authenticated key exchange , self- 1212 healing on-demand geographic path routing protocol , stable weight-based 1213 on-demand routing protocol , fisheye zone routing protocol , on- 1214 demand utility-based power control routing , secure position-based routing  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 1215 protocol , scalable multi-path on-demand routing , virtual coordinate- 1216 based routing , etc. 1217 1218 1219 OF 1220 4.3.4 Criteria for Performance Evaluation of MANET Routing 1221 Protocols 1222 1223 Performance of a particular routing protocol depends on the requirements and settings of a mobile ad hoc network. One routing protocol might seem to be RO 1224 1225 efficient in a scenario while it might not be efficient in a different scenario. 1226 However, to analyze the routing protocols in MANET, we generally take some 1227 common criteria as the basis of comparison. Commonly used criteria are the 1228 end-to-end delay, control overhead, processing overhead of nodes, memory requirement, and packet-delivery ratio. Of these criteria, packet-delivery ratio DP 1229 1230 mainly tells about the reliability of the protocol. So, reliability of a routing 1231 protocol depends on how efficiently it can transmit data from source to the 1232 destination. The less the packet loss ratio is, the better the performance of that 1233 routing protocol. Often security becomes the key aspect of MANET. In such 1234 cases, the protocol that might ensure better security is considered as more TE 1235 efficient for that application. 1236 So far, we have talked about different types of routing protocols. We mainly 1237 categorized them into reactive, proactive, and hybrid protocols. Generally 1238 speaking, reactive protocols require less amount of memory, processing power, and energy than that of the proactive protocols. Having the knowledge EC 1239 1240 of the MANET routing protocols and their comparison criteria, let us now 1241 investigate the key influencing factors for routing performance in different 1242 settings of MANETs. 1243 RR 1244 4.3.4.1 Mobility Factors 1245 1246  Velocity of nodes: The velocity of the mobile nodes within a MANET is not 1247 fixed. As there is no speed limitation of the wireless devices, high speed of nodes might affect the performance of many protocols. A protocol is con- CO 1248 1249 sidered good for MANET if it can perform well both in relatively static and 1250 in fully dynamic network state, though it is true that routing in a highly 1251 mobile MANET is a tough task. 1252  Direction of mobility: The direction of a node’s mobility is not known in advance. It is a very common incident that a node travels to a direction where UN 1253 1254 the number of neighbor nodes is less or there is no neighbor node. This is 1255 called drifting away of a node from a MANET. A hard-state approach or a 1256 soft-state approach could be used to handle such incidents. In hard-state 1257 approach, the node explicitly informs all the other nodes in the MANET 1258 about its departure or movement from a position, while in a soft-state 1259 approach a time out value is used to detect the departure.  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 1260  Group or individual mobility: MANETs are often categorized as Pure 1261 MANET and Military MANET. In a pure MANET, it is not obvious that 1262 the nodes should move in groups, but in case of military MANET, group 1263 mobility is the main concern. A military MANET can maintain a well- 1264 defined chain of commands, which is absent in case of a pure MANET. So OF 1265 the routing strategies could vary depending upon this factor. Two MANET 1266 protocols considered as good for supporting group mobility are: LANMAR 1267 , developed by University of California at Los Angeles, and OLSR , 1268 which is developed by the French National Institute for Research in Com- puter Science and Control (INRIA). RO 1269 1270  Frequency of changing of mobility model: Routing strategy could also vary 1271 depending on the mobility model of the MANET. The topology of an ad hoc 1272 network could definitely change over time. But, the key factor here is the 1273 change of overall mobility model in a fast or relatively slow fashion. If the nodes change their relative positions too frequently, the maintenance cost of DP 1274 1275 the overall network gets higher. For example, a MANET formed with war 1276 planes, tanks, helicopters, and ships is highly dynamic, while an ad hoc 1277 network formed with some laptops and palmtops carried by the participants 1278 in a conference is relatively less dynamic. 1279 TE 1280 4.3.4.2 Wireless Communication Factors 1281 1282  Consumption of power: Power is a valuable resource in wireless networking. 1283 Especially for routing, power is highly needed. According to an experiment EC 1284 by Kravets and Krishnan (1998), power consumption caused by networking- 1285 related activities is approximately 10% of the overall power consumption of 1286 a laptop computer. This figure rises up to 50% in handheld devices. In ad 1287 hoc network, every node has to contribute for maintaining the network 1288 connections. Hence, routing protocol should consider everything to save RR 1289 power of the participating battery-powered devices. 1290  Bandwidth: For any type of wireless communications, bandwidth available 1291 for the network is a major concern. An efficient routing protocol should try 1292 to minimize the number of packet-transmissions or control overhead for the maintenance of the network. CO 1293 1294  Error rate: Wireless communication is always susceptible to high error rate. 1295 Packet loss is a common incident. So, the routing strategies should be 1296 intelligent enough to minimize the error rate for smooth communications 1297 among the nodes.  Unidirectional link: Sometimes it is convenient for a routing protocol to UN 1298 1299 assume routes as unidirectional links. 1300 1301 4.3.4.3 Security Issues 1302 1303  Unauthorized access: Security has recently become a major issue for ad hoc 1304 network routing. Most of the ad hoc network routing protocols that are  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 1305 currently proposed lack security. A wireless network is more vulnerable than 1306 a wired network. So, based on the requirement, sometimes preventing 1307 unauthorized access to the network becomes the major concern. 1308  Accidental association with other networks: Accidental associations between 1309 a node in one wireless network and a neighboring wireless network are just OF 1310 now being recognized as a security concern, as enterprises confront the issue 1311 of overlapping networks. At the routing level it should be ensured that the 1312 nodes can recognize their own network. 1313 RO 1314 1315 4.3.4.4 Other Factors 1316  Reliability of the network: Reliability is sometimes defines as how efficiently a 1317 routing protocol can dispatch packets to the appropriate destinations. A 1318 routing protocol must be efficient enough to handle successful packet deliv- DP 1319 ery so that an application may rely on it. 1320  Size of the network: The overall network size could be a crucial factor. A 1321 routing protocol might be good for a small network, but might not be fit for 1322 use in a large ad hoc network or vice versa. 1323  Quality of service: In the real-time applications, QoS becomes a key factor 1324 for evaluating the performance of a routing protocol. TE 1325  Timing: Regardless of the method of communication used, access time and 1326 tuning time must be considered. Tuning time is the measure of the amount of 1327 time each node spends in active mode. In the active mode a node consumes 1328 maximum power. So, minimizing the tuning time is one of the critical factors EC 1329 to conserve power. 1330 1331 1332 1333 4.4 Thoughts for Practitioners RR 1334 1335 It is still a matter of debate whether the routing protocols for mobile ad hoc 1336 networks should be predicted based on the network overhead or the optimiza- 1337 tion of the network path. In this chapter, we have learnt about a number of routing protocols for MANET, which are broadly categorized as proactive and CO 1338 1339 reactive. Proactive routing protocols tend to provide lower latency than that of 1340 the on-demand protocols, because they try to maintain routes to all the nodes in 1341 the network all the time. But the drawback for such protocols is the excessive 1342 routing overhead transmitted, which is periodic in nature without much con- sideration for the network mobility or load. On the other hand, though reactive UN 1343 1344 protocols discover routes only when they are needed, they may still generate a 1345 huge amount of traffic when the network changes frequently. 1346 Depending on the amount of network traffic and number of flows, the 1347 routing protocols could be chosen. When there is congestion in the network 1348 due to heavy traffic, in general case, a reactive protocol is preferable. Sometimes 1349 the size of the network might be a major considerable point. For example,  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 4 Routing in Mobile Ad Hoc Networks 1350 AODV, DSR, OLSR are some of the protocols suitable for relatively smaller 1351 networks, while the routing protocols like TORA, LANMAR, ZRP are suita- 1352 ble for larger networks. Network mobility is another factor that can degrade the 1353 performance of certain protocols. When the network is relatively static, proac- 1354 tive routing protocols can be used, as storing the topology information in such OF 1355 case is more efficient. On the other hand, as the mobility of nodes in the network 1356 increases, reactive protocols perform better. 1357 Overall, the answer to the debating point might be that the mobility and 1358 traffic pattern of the network must play the key role for choosing an appro- priate routing strategy for a particular network. It is quite natural that one RO 1359 1360 particular solution cannot be applied for all sorts of situations and, even if 1361 applied, might not be optimal in all cases. Often it is more appropriate to apply 1362 a hybrid protocol rather than a strictly proactive or reactive protocol as hybrid 1363 protocols often possess the advantages of both types of protocols. DP 1364 1365 1366 4.5 Directions for Future Research 1367 1368 The structure of the Internet that is used today is based mainly on wired 1369 communications. The emerging technologies like fiber optics–based high- TE 1370 speed wired networks would flourish in the near future. With this existing 1371 network of networks, semi-infrastructure and infrastructure-less wireless net- 1372 works will also be used in abundance. Figure 4.15 shows a conceptual view of 1373 the future global Internet structure. MANETs would definitely play an impor- EC 1374 tant role in the future Internet structure, especially for the mobile Internet. 1375 Hence, in some cases, it might be necessary that the routing protocols of 1376 MANET work in perfect harmony with their wired counterparts. Considering 1377 different approaches of routing, a hybrid approach might be more appropriate 1378 for such scenarios. RR 1379 More and more efficient routing protocols for MANET might come in front 1380 in the coming future, which might take security and QoS (Quality of Service) as 1381 the major concerns. So far, the routing protocols mainly focused on the 1382 CO 1383 1384 1385 1386 1387 UN 1388 1389 1390 1391 1392 1393 1394 Fig. 4.15 Future Global Internet Structure  SPB-150005 4 October 17, 2008 Time: 5:59 Proof 1 A.-S.K. Pathan and C.S. Hong 1395 methods of routing, but in future a secured but QoS-aware routing protocol 1396 could be worked on. We should keep this in mind that ensuring both of these 1397 parameters at the same time might be difficult. A very secure routing protocol 1398 surely incurs more overhead for routing, which might degrade the QoS level. So 1399 an optimal trade-off between these two parameters could be searched. OF 1400 We saw that in the recent years some multicast routing protocols have been 1401 proposed. The reason for the growing importance of multicast is that this 1402 strategy could be used as a means to reduce bandwidth utilization for mass 1403 distribution of data. As there is a pressing need to conserve scarce bandwidth RO 1404 over wireless media, it is natural that multicast routing should receive some 1405 attention for ad hoc networks. So it is, in most of the cases, advantageous to use 1406 multicast rather than multiple unicast, especially in ad hoc environment where 1407 bandwidth comes at a premium. Another advantage of multicasting is that it 1408 provides group communication facility. A group of nodes can be addressed at DP 1409 the same time using only a group identifier. So it is an efficient communication 1410 tool for using in multipoint applications. 1411 Ad hoc wireless networks find applications in civilian operations (collabora- 1412 tive and distributed computing) emergency search-and-rescue, law enforcement, 1413 and warfare situations, where setting up and maintaining a communication 1414 infrastructure is very difficult. In all these applications, communication and TE 1415 coordination among a given set of nodes are necessary. Considering all these, 1416 in future the routing protocols might especially emphasize the support for multi- 1417 casting in the network. 1418 EC 1419 1420 1421 4.6 Conclusions 1422 1423 In this chapter, we have talked about MANET, the challenges for routing in RR 1424 MANET, major routing protocols, the major features of MANET routing 1425 protocols, key aspects for routing in MANET, and future research issues for 1426 routing in MANET. We categorized the proposed routing protocols based on 1427 their working principles and discussed which type of protocol might be used in which situation. CO 1428 1429 The proliferation of mobile ad hoc networks is looming on the horizon. 1430 Exploitation of these types of infrastructure-less networks are expected to 1431 flourish in future, not only for civil but also for military reconnaissance scenar- 1432 ios. It is quite reasonable to think that the security and QoS (Quality of Service) requirements might differ largely for different types of civil and military appli- UN 1433 1434 cations. Based on these two critical aspects, appropriate routing protocols 1435 should have to be chosen for the application at hand.