Guide to Wireless Ad Hoc Networks

Guide to Wireless Ad Hoc Networks......Page 1
Guide to Wireless Ad Hoc Networks......Page 3
Organization and Features......Page 6
Supplementary Resources......Page 8
Acknowledgments......Page 9
Contents......Page 10
Contributors......Page 12
1.1 Introduction......Page 16
1.2 Background......Page 19
1.3.1 Definitions......Page 20
1.3.1.1 Node Placement Models......Page 21
1.3.1.2 Wireless Signal Propagation Models......Page 23
1.3.2 Data Sampling and Simulation Methodology......Page 24
1.3.3 Data Sampling Methodology......Page 26
1.3.3.1 Simulation Methodology......Page 27
1.3.4 Topological Structure of the Network and Link Reliability Analysis......Page 28
1.3.4.1 Node Degree Distributions......Page 29
1.3.4.2 Bridges and Articulation Points Analysis......Page 30
1.3.4.3 Link Quality Analysis......Page 33
1.3.4.4 Traffic Analysis......Page 34
1.3.5 Thoughts for Practitioners......Page 36
1.3.6 Directions for Future Research......Page 37
Keywords......Page 38
Problems......Page 39
References......Page 40
2.1 Introduction......Page 42
2.2 Background......Page 44
2.2.1 Hidden Terminal Problem......Page 45
2.2.2 Self-Configuring and Self-Organizing MANETs......Page 46
2.2.3 Self-Healing......Page 48
2.3 Thoughts for Practitioners......Page 50
2.4 Directions for Future Research......Page 51
Terminologies......Page 52
References......Page 53
3.1 Introduction......Page 57
3.2.1.1 Nuglets......Page 59
3.2.1.2 Sprite......Page 60
3.2.2.1 CONFIDANT......Page 62
3.2.2.2 CORE......Page 64
3.2.2.3 OCEAN......Page 65
3.3 Thoughts for Practitioners......Page 66
3.4 Directions for Future Research......Page 67
Terminologies......Page 68
References......Page 70
4.1 Introduction......Page 72
4.2 Background......Page 74
4.3.1 Expected Properties of MANET Routing Protocols......Page 76
4.3.2.1 Proactive Routing Protocols......Page 77
4.3.2.3 Hybrid Routing Protocols......Page 78
Dynamic Destination-Sequenced Distance-Vector Routing Protocol......Page 79
Wireless Routing Protocol......Page 80
Cluster Gateway Switch Routing Protocol......Page 82
Fisheye State Routing......Page 83
Zone-Based Hierarchical Link State Routing Protocol......Page 84
Landmark Ad Hoc Routing......Page 85
Associativity-Based Routing......Page 86
Signal Stability-Based Adaptive Routing Protocol......Page 88
Cluster-Based Routing Protocol......Page 89
Dynamic Source Routing......Page 90
Ad Hoc On-Demand Distance Vector Routing......Page 91
Dual-Hybrid Adaptive Routing......Page 92
Zone Routing Protocol......Page 93
Sharp Hybrid Adaptive Routing Protocol......Page 94
Neighbor-Aware Multicast Routing Protocol......Page 95
4.3.3.4 Other Routing Protocols......Page 97
4.3.3.5 Other Recent Works on MANET Routing for Reference......Page 98
4.3.4.1 Mobility Factors......Page 99
4.3.4.3 Security Issues......Page 100
4.4 Thoughts for Practitioners......Page 101
4.5 Directions for Future Research......Page 102
4.6 Conclusions......Page 103
Terminologies......Page 104
Questions......Page 105
References......Page 106
5.1 Introduction......Page 110
5.2 Multicast Protocol Design Considerations......Page 113
5.3.1 Multicast Protocols Classification......Page 115
5.3.2.1 Mesh-Based Example: ODMRP......Page 117
5.3.2.2 Tree-Based Example: MOLSR......Page 118
5.3.2.3 Shared Tree Example: MAODV......Page 119
5.3.2.4 Overlay Example: MOST......Page 121
5.4 Thoughts for Practitioners......Page 122
5.5 Reliable Multicast Protocols......Page 123
5.5.1 Classification of Reliable Multicast Protocols......Page 124
5.5.2.1 ARQ-Based Example: RMA and RALM......Page 125
5.5.2.2 FEC-Based Example: RMDP......Page 126
5.5.2.4 Epidemic Protocol Example: EraMobile......Page 127
5.6.1 QoS Multicast Routing......Page 128
5.7 Conclusions and Synthesis......Page 129
Terminologies......Page 130
Questions......Page 131
References......Page 132
6.1.1 Background......Page 134
6.1.2 Overview of the Chapter......Page 136
6.2.1 Heuristic-Based Broadcasting......Page 137
6.2.2 Neighbor Coverage-Based Broadcast......Page 138
6.2.4 Combining Multipoint Relay and Dominating Set-Based Broadcasting......Page 141
6.2.6 Cluster-Based Broadcasting......Page 142
6.2.7 Resource-Aware Broadcasting......Page 144
6.2.8 Distributed and Efficient Flooding......Page 145
6.3 Variable Radius Optimized Broadcasting......Page 146
6.3.1 Relative Neighborhood Graph......Page 147
6.3.2 Minimum Spanning Tree Graph......Page 148
6.3.4 RNG- and LMST-Based Broadcasting......Page 150
6.3.6 Incremental Power Broadcasting......Page 151
6.4 Reliable Broadcasting......Page 152
6.5.1 Proactive Routing Protocols......Page 155
6.5.2 Reactive Routing Protocols......Page 156
6.5.3 Self-selecting Route Discovery......Page 157
6.6 Thoughts for Practitioners......Page 158
Terminologies......Page 159
References......Page 160
7.1 Introduction......Page 164
7.2 Background......Page 166
7.3.1 Greedy Forwarding......Page 169
7.3.2 Void Handling......Page 174
7.4.1 Geographic Multicast......Page 186
7.4.2 Geocast......Page 188
7.4.3 Trajectory-Based Forwarding......Page 190
7.5 Thoughts for Practitioners......Page 192
7.6 Directions for Future Research......Page 193
Terminologies......Page 195
Questions......Page 196
References......Page 197
8.1 Introduction......Page 202
8.2 Background......Page 203
8.2.1 Formal Verification Techniques......Page 204
8.2.2 The State Explosion Problem and Remedies......Page 206
8.3 Tools......Page 207
8.4 Thoughts for Practitioners......Page 209
8.4.1.1 Understanding the Protocol......Page 210
8.4.1.2 OLSR State Machine......Page 211
8.4.1.5 Modeling the Channel......Page 212
8.4.1.6 Creating the Model......Page 213
8.4.1.7 Verifying the Model......Page 214
8.5 Proposals for Routing Verification......Page 215
8.6 Directions for Future Research......Page 219
Terminologies and Keywords......Page 220
References......Page 221
9.1 Introduction......Page 224
9.2 Overview......Page 225
9.3.1 Mobility Models......Page 226
9.3.2 Different Levels of Mobility......Page 228
9.3.3.1 Main Target: Connection-Based Routing......Page 229
9.3.3.2 Mobility Scheme: Controlled vs. Uncontrolled......Page 230
9.3.3.3 Why Mobility Helps: Enlarge Routing Probability......Page 232
9.3.4.2 Mobility Scheme: Random Movement......Page 233
9.3.4.3 Why Mobility Helps: Short-Range Transmission......Page 234
9.3.5.1 Main Target: Building Security Association......Page 235
9.3.5.3 Why Mobility Helps: Encounters and Help from Common Friends......Page 236
9.3.6.1 Main Target: Increase Node Coverage and Detection Rate......Page 237
9.3.6.3 Why Mobility Helps: After-Deployment Movement......Page 238
9.3.7.1 Main Target: Information Dissemination......Page 239
9.3.7.2 Mobility Scheme: Zone and Contact......Page 240
9.3.8.1 Main Target: Reducing Uncertainty while Building Trust......Page 241
9.3.8.2 Mobility Scheme: Hierarchical Movement......Page 243
9.4 Directions for Future Research......Page 244
9.5 Conclusion......Page 245
Questions......Page 246
References......Page 247
10.1 Introduction......Page 249
10.2 Classification......Page 250
10.3.1.1 Random Waypoint (RWP) Mobility Model......Page 252
10.3.1.2 Random Walk Mobility Model (RWM)......Page 253
10.3.1.3 Random Direction Mobility Model (RDM)......Page 254
10.3.1.4 Smooth Mobility Model (SM)......Page 255
10.3.2 Group Mobility Models......Page 256
10.3.3 Obstacle Models......Page 257
10.3.5 Trace-Based Mobility Models......Page 258
10.4 Impact of Mobility Models on the Performance of Wireless Networks......Page 261
10.6 Conclusion......Page 262
10.7 Terminology......Page 263
References......Page 264
11.1 Introduction......Page 267
11.2 Background: Mobility Models......Page 269
11.2.1 Entity Mobility Models......Page 270
11.2.2 Group Mobility Models......Page 271
11.2.2.1 Mobility Based on Social Networks......Page 272
11.3 Background: Radio Wave Propagation Models......Page 273
11.3.2 Two-Ray Ground......Page 275
11.3.5 Site-Specific Modeling......Page 276
11.4.1 The World of CosMos......Page 277
11.4.2 Scenario Creation......Page 278
11.4.3.1 Example......Page 280
11.4.4 Radio Wave Propagation......Page 282
11.5.1 Preparation, Documentation, and Evaluation of Simulations......Page 284
11.5.2 Network Simulation Packages......Page 285
11.5.3 Support for Mobility Models......Page 286
11.5.4 Mobility Generation Tools......Page 287
11.6 Directions for Future Research......Page 288
11.7 Conclusions......Page 289
Questions......Page 290
References......Page 291
12.1 Introduction......Page 293
12.2.1 Admission Control......Page 294
12.2.5 End-to-End Delay......Page 295
12.3 Challenges of QoS Provisioning in WANET......Page 296
12.4 Factors Affecting QoS Protocol Performance......Page 298
12.5.1 Integrated Service (IntServ) Model......Page 299
12.5.2 Differentiated Service (DiffServ) Model......Page 301
12.5.3 Flexible QoS Model for WANET (FQMW)......Page 302
12.5.4 Service Differentiation in Wireless Ad Hoc Network (SWAN)......Page 304
12.6 QoS Signalling - INSIGNIA......Page 305
12.7 QoS MAC Protocol......Page 307
12.8 QoS Routing Mechanism......Page 309
12.8.1.1 Protocols Relying on Contention-Free MAC......Page 311
12.8.2 Classification Based on Routing Protocol: the QoS Provisioning Mechanism Interaction......Page 312
12.8.3 Classification Based on the Routing Information Update Mechanism Employed......Page 313
12.9.1 Bandwidth Reservation in WANET......Page 314
12.9.3 Queuing......Page 315
12.9.4 Dealing with Congestion......Page 316
Terminologies......Page 317
Questions......Page 318
References......Page 319
13.1 Introduction......Page 323
13.2 Background......Page 324
13.3.1 At the Middleware Layer in the Wireless end Hosts......Page 325
13.4.1.1 Delay Monitor......Page 326
13.4.1.3 Priority Adaptor......Page 327
Off-Line Model Identification......Page 328
PI Controller Design......Page 330
13.4.2 Cross-Layer Proportional Delay Differentiation Scheduler......Page 331
13.5 Evaluation and Implementation......Page 338
Terminologies......Page 341
References......Page 342
14.1 Introduction......Page 344
14.2 Background......Page 345
14.2.1.3 Dynamic Host Configuration Protocol (DHCP)......Page 346
14.2.2.2 Zero Configuration Networking (Zeroconf)......Page 347
14.3.1.1 MANETconf......Page 348
14.3.1.2 Buddy Protocol......Page 349
14.3.1.3 Prophet Allocation Protocol......Page 350
14.3.1.4 Prime DHCP......Page 351
14.3.2.2 Weak DAD......Page 352
14.3.2.3 Passive DAD......Page 353
14.4 Thoughts for Practitioners......Page 354
14.5.1 Preliminaries of Number Theory......Page 355
14.5.3 Address Space and Quadratic Residue Algorithm......Page 356
14.5.4 Address Allocation Protocol......Page 357
14.5.5 Network Partitioning and Network Merger......Page 359
14.5.6 Performance Evaluation......Page 361
Terminologies......Page 362
Questions......Page 363
References......Page 364
15.1 Introduction......Page 366
15.2.1 Physical Layer......Page 368
15.2.3 Routing Layer......Page 369
15.3 Modeling Resource Allocation and Congestion Control - Preliminaries......Page 370
15.3.1.1 Dual Problem and Lagrange Multipliers......Page 371
15.3.2 Interference Modeling......Page 372
15.4 Analysis of Congestion......Page 373
15.4.1.1 Effect of Mobility......Page 374
15.4.2 Alternative Congestion Avoidance Mechanisms......Page 375
15.4.2.2 Locality of Congestion Regions......Page 376
15.5.1 Rate-Control......Page 377
15.5.1.1 Avoiding False Congestion Alarms......Page 378
15.5.2 Routing......Page 379
15.5.3 Scheduling......Page 380
15.6.2 Standardization of Control Messages......Page 381
15.7.2 Basic Congestion Control Model......Page 382
15.7.2.2 Rate Control Component......Page 383
15.7.2.3 Scheduling Component......Page 384
15.7.2.4 Capturing the Capacity Region......Page 385
Route-Independent Case......Page 386
15.7.3.1 Decomposing the Congestion Control Problem......Page 387
15.7.3.2 The Scheduling Problem......Page 389
15.8.1 Heuristic Protocol Development......Page 390
15.8.1.2 Providing the Right Abstractions......Page 391
15.8.2.2 Realistic Interference Models......Page 392
Effect of Contention-Based Schedulers......Page 393
Terminologies......Page 394
Questions......Page 396
References......Page 397
16.1 Introduction......Page 401
Random Key Distribution......Page 403
Combinatorial Design on Key Distribution......Page 404
16.2.1.2 Public Key Management......Page 405
16.2.2 Broadcast Packet Authentication......Page 406
Network Model......Page 407
One-way Hash Function......Page 408
16.2.2.3 Classification of Broadcast Authentication Protocols......Page 409
16.3.1 Introduction......Page 410
16.3.2 Overview......Page 411
16.3.3 Design Objectives......Page 413
16.3.4.1 Optimization of Design Objectives......Page 415
16.3.5 Key Allocation......Page 416
16.3.6.1 Initialization......Page 417
16.3.7 Evaluations......Page 418
16.3.7.1 Small Memory Footprint......Page 419
16.3.7.3 Resilience to Break-ins......Page 420
16.4.1 Main Idea......Page 421
16.4.2 Packet Authentication......Page 422
16.4.3 Risk Management......Page 425
16.4.4 Evaluation......Page 426
16.4.5 Grid Topology......Page 427
16.4.6 Random Topology......Page 430
16.6 Direction for Future Research......Page 431
Terminologies......Page 432
References......Page 433
17.1 Introduction......Page 436
17.2 Intrusion Detection Systems......Page 437
17.3 Intrusion Detection Issues in MANETs......Page 438
17.4.1 Proposed IDSs......Page 440
17.4.1.1 Distributed and Cooperative IDS [28, 29]......Page 441
17.4.1.2 Cooperative IDS Using Cross-Feature Analysis in MANETs [7, 8]......Page 442
17.4.1.3 Zone-Based Intrusion Detection System [22]......Page 443
17.4.1.4 General Cooperative Intrusion Detection Architecture [20]......Page 445
17.4.1.5 Intrusion Detection Using Multiple Sensors [12]......Page 446
17.4.1.6 Specification-Based IDS for AODV [25]......Page 447
17.4.1.7 DEMEM: Distributed Evidence-Driven Message Exchanging ID Model [24]......Page 448
17.4.1.9 An IDS Architecture with Stationary Secure Database [18]......Page 450
17.4.1.10 An IDS Model Integrating Different Techniques [9]......Page 451
17.4.2.1 Watchdog and Pathrater [15]......Page 453
17.4.2.2 Nodes Bearing Grudges [4]......Page 454
17.4.2.3 LiPaD: Lightweight Packet Drop Detection for Ad Hoc Networks [2]......Page 455
17.4.2.4 Intrusion Detection and Response for MANET [17]......Page 456
17.5 Thoughts for Practitioners......Page 457
17.6 Directions for Future Research......Page 458
17.7 Conclusions......Page 459
Terminologies......Page 460
References......Page 461
18.1 Introduction......Page 464
18.2 Organization......Page 465
18.4 Taxonomy of Ad Hoc Network Routing Attacks......Page 466
18.4.1 Elements of Attack Behavior......Page 467
18.4.2 Attack Behavior......Page 468
18.4.3.2 Wormhole......Page 469
18.4.3.5 Selfishness......Page 471
18.5.1 OLSR Fundamentals......Page 472
18.5.2 Protocol Analysis......Page 473
18.5.2.2 Propagation Analysis......Page 474
18.5.3 Causal Relations - Effects and Behavior......Page 475
18.5.3.2 Effects of Attacks (Malicious Behavior)......Page 476
18.5.4 Risk Estimation......Page 477
18.8 Directions for Future Research......Page 478
Terminologies......Page 479
References......Page 480
19.1 Introduction......Page 482
19.2.1 Wireless Medium: Promiscuous......Page 484
19.2.2 Mobility: Broken Links and Dynamically Changing Topology......Page 485
19.2.4 Battery-Powered Devices: Constrained Resources......Page 486
19.3.1 Concepts: Trust and Reputation......Page 487
19.3.2 Components of Trust Management Systems......Page 488
19.4 Trust Management Systems in MANET......Page 489
19.4.1 Quantifying Trust in Mobile Ad Hoc Networks......Page 490
19.4.2 Establishing Trust in Pure Ad Hoc Networks......Page 491
19.4.3 Propagating Trust in Ad Hoc Networks for Reliable Routing......Page 492
19.4.4 Performance Analyses of the CONFIDANT Protocol (Cooperation Of Nodes: Fairness In Dynamic Ad-Hoc NeTworks)......Page 493
19.4.5 A Reputation-Based Mechanism for Isolating Selfish Nodes in Ad Hoc Networks......Page 494
19.4.7 Trust Model Based Routing Protocol for Secure Ad Hoc Networks......Page 496
19.4.8 Information Theoretic Framework of Trust Modeling and Evaluation for Ad Hoc Networks......Page 497
19.4.9 Trust Evaluation in Ad Hoc Networks......Page 498
19.4.10 Trust-Enhanced Secure Ad Hoc Network Routing......Page 499
19.5.1 Behavioral Evidence......Page 500
19.5.2 Recommendations......Page 501
19.5.3 Modeling Ignorance in Trust Relationships......Page 502
19.5.4 Selective Malicious Behaviors......Page 503
19.6 Directions for Future Research......Page 504
Terminologies......Page 505
References......Page 506
20.1 Introduction......Page 512
20.3 Network Architectures and Characteristics......Page 514
20.4 Routing Protocols......Page 516
20.4.1 Ad Hoc Routing......Page 517
20.4.2 Position-Based Routing......Page 518
20.4.3 Cluster-Based Routing......Page 521
20.4.4 Broadcast Routing......Page 522
20.4.5 Geocast Routing......Page 524
20.5 Data Sharing and Data Dissemination......Page 526
20.6 Mobility Model......Page 527
20.7 Security......Page 528
20.9 Directions for Future Research......Page 529
Terminologies......Page 530
Questions......Page 531
References......Page 532
21.1 Introduction......Page 535
21.2 Background......Page 537
21.3 Architecture for Connecting MANET to IP-Based Access Networks......Page 538
21.3.1 Characteristics of the Internet Gateway......Page 539
21.3.2.2 Propagation of the Prefix Information Through Multiple Hops......Page 542
21.3.2.3 Gateway Discovery......Page 544
21.4.1 Address Auto-Configuration: Problem Statement......Page 545
21.4.2 Address Auto-configuration......Page 547
Construction of a Valid IPv6 Address......Page 548
Duplicate Address Detection (DAD)......Page 549
21.4.2.2 Conflict-Free Allocation Technique for Address Auto-Configuration......Page 553
21.5.1 Global Connectivity......Page 555
21.5.2 Prefix Continuity......Page 556
21.5.4 Automatic Configuration with Multiple Gateways......Page 557
21.5.5 Mobile Multi-Gateway Support......Page 558
21.5.5.1 Distributed Algorithm for Opportunistic Gateway Configuration......Page 559
21.6 Thoughts for Practitioners......Page 561
21.7 Directions for Future Research......Page 562
21.8 Conclusions......Page 563
Terminologies......Page 564
Questions......Page 565
References......Page 566
back-matter......Page 570