Wireless Ad Hoc and Sensor Networks: Theory and Applications

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 9
Introduction......Page 15
Organization of the Book......Page 18
Acknowledgments......Page 23
Abbreviations......Page 25
Part I: Introduction......Page 33
1.1 Introduction......Page 35
Based on Communication Coverage Area......Page 36
First-Generation Mobile Systems......Page 37
2.5G Mobile Systems......Page 38
1.2.2 Wireless Access Points......Page 39
Security......Page 40
Mobile Ad Hoc Networks......Page 41
Wireless Sensor Networks......Page 43
1.3 Conclusion......Page 46
Problems......Page 47
2.1 Wireless Channels......Page 49
2.1.1 Free-Space Propagation Model......Page 50
2.1.2 Two-Ray Ground Model......Page 51
2.1.3 The Log-Distance Path-Loss Model......Page 52
2.2 The Wireless Communication Graph......Page 53
Power Assignment......Page 55
Asymptotic Power Assignment......Page 57
Topology Control......Page 58
Limitations......Page 59
2.4 The Wireless Interference Graph......Page 60
Protocol-Interference Model (PrIM)......Page 61
RTS/CTS Model......Page 62
2.5 Related Graph Problems and Geometry Concepts......Page 64
2.5.1 Geometry Concepts......Page 66
2.6.1 Wireless Ad Hoc Networks......Page 67
2.6.2 Wireless Sensor Networks......Page 68
2.7 Mobility Models......Page 70
Random-Waypoint Model......Page 71
Group Mobility......Page 72
2.8 Conclusion......Page 73
Problems......Page 74
Part II: Wireless MACs......Page 77
Contention-Based MAC......Page 79
3.2 IEEE 802.11 Architecture and Protocols......Page 81
802.11g......Page 83
3.2.2 Distributed Coordination Function......Page 84
3.2.3 Problems and Solutions for the Ad Hoc Model......Page 85
3.2.4 Ad Hoc Networking Support......Page 87
Synchronization Maintenance......Page 88
3.2.5 Power Management......Page 89
3.2.6 Centrally Controlled Access Mechanism......Page 90
3.2.7 Other Extensions and Enhancements......Page 91
Technical Advantages over WiFi......Page 92
3.4 Bluetooth......Page 93
Possible Bluetooth Uses......Page 94
3.5.1 B-MAC......Page 95
3.5.2 Z-MAC......Page 96
3.5.3 X-MAC......Page 99
3.5.4 Funneling-MAC......Page 100
Problems......Page 101
4.1 Introduction......Page 103
Network Model......Page 105
4.2.2 Problem Formulation......Page 106
4.3 Centralized Scheduling......Page 107
4.3.1 Scheduling under the Protocol-Interference Model......Page 108
4.3.2 Scheduling under the RTS/CTS Model......Page 109
4.3.3 Scheduling under the fPrIM......Page 113
4.4.1 Algorithm for the RTS/CTS Model......Page 117
4.4.2 Faster Algorithm for the RTS/CTS Model......Page 119
4.4.3 Distributed Algorithm for the fPrIM......Page 121
4.5.1 Scheduling with Traffic Load......Page 122
4.5.2 Necessary and Sufficient Conditions for Schedulable Flows......Page 125
4.6 Further Reading......Page 126
4.7 Conclusion and Remarks......Page 128
Problems......Page 129
5.1 Introduction......Page 131
5.2 Network System Model......Page 133
5.3.1 Centralized Method for Maximizing Capacity......Page 134
5.3.2 Distributed Coloring for Minimizing Channels......Page 138
5.4 List-Coloring for Ad Hoc Networks......Page 144
Complexity Result......Page 145
5.5 Transition Phenomena on Channel Availability......Page 146
5.6 Further Reading......Page 148
Problems......Page 150
6.1 Introduction......Page 152
6.2.2 A Technical Lemma......Page 155
6.3 Throughput and Bottleneck of General Graphs......Page 158
6.4.1 First-Fit Prefix-Free Coloring......Page 161
6.4.2 Tile Prefix-Free Coloring......Page 164
6.4.3 Improved Approximation Ratio......Page 167
6.5.1 A General Wireless Network Model......Page 168
6.5.2 Simple Distributed Method for a MIS......Page 170
6.5.3 Polynomial-Time-Approximation Scheme for a MIS......Page 171
6.6 Further Reading......Page 180
6.7 Conclusion and Remarks......Page 182
Problems......Page 183
Part III: Topology Control and Clustering......Page 185
7.2 Network Models and Problem Formulation......Page 187
7.3.1 Algorithms for General Graphs......Page 189
7.3.2 Algorithms for Graphs Modeling Wireless Ad Hoc Networks......Page 192
7.4 Message Lower Bound for Distributed-Backbone Construction......Page 193
7.5.1 Algorithm by Das et al.......Page 195
7.5.2 Algorithm by Wu and Li......Page 196
7.5.3 Algorithm by Stojmenovic et al.......Page 197
7.6.1 MIS Construction......Page 198
7.6.2 Connected-Dominating-Set Construction......Page 200
7.6.3 Properties of Constructed Backbone......Page 201
7.7 Efficient Distributed-Backbone-Formation Method......Page 202
7.7.1 Clustering......Page 203
7.7.2 Finding Connectors......Page 205
7.7.3 The Properties of Backbone......Page 209
7.8 Linear-Programming-Based Approaches......Page 211
Greedy Method Based on Node Positions......Page 216
Grid-Partition-Based Approach......Page 217
7.10 Further Reading......Page 218
7.11 Conclusion and Remarks......Page 219
Problems......Page 220
8.1 Introduction......Page 222
8.2 Study of Typical Methods......Page 223
8.3 Centralized Low-Cost Backbone-Formation Algorithms......Page 225
8.4 Efficient Distributed Low-Cost Backbone-Formation Algorithms......Page 226
8.4.2 Finding Connectors......Page 227
8.5 Performance Guarantee......Page 229
8.5.1 Total Cost of the Backbone......Page 230
8.5.2 Unicast Performance......Page 234
8.5.3 Message Complexity......Page 236
8.6.1 pplicat onPracticalAi......Page 237
Security Level......Page 238
8.6.2 Dynamic Update......Page 239
8.6.3 Practical Implementation......Page 240
8.7 Further Reading......Page 241
Problems......Page 243
9.1.1 Ad Hoc Networks: Graph Model......Page 245
9.1.2 Geometrical Spanner......Page 246
9.1.4 Efficient Localized Construction......Page 247
9.1.5 Relay Regions......Page 248
9.2.1 Unicast Topology......Page 251
9.2.2 Energy-Efficient Broadcast Topology......Page 254
9.3.1 Relative Neighborhood Graph......Page 256
9.3.2 Gabriel Graph......Page 257
9.3.4 Local Delaunay Graph......Page 258
9.4.1 Yao Graph......Page 260
9.4.3 Sparse Yao......Page 261
9.4.4 Yao and Sink Structure......Page 262
9.5.1 Delaunay Triangulation plus Yao Structure......Page 263
9.5.2 Local Delaunay Graph plus Yao Structure......Page 264
9.6 Low-Weighted Structures......Page 265
9.7 A Unified Structure: Energy Efficiency for Unicast and Broadcast......Page 270
9.7.1 Power-Efficient Unicast: Spanner, Planar, and Bounded Degree......Page 271
9.7.2 Unified Power-Efficient Topology: Degree-Bounded Planar Spanner......Page 274
9.7.3 Expected Interference in Random Networks......Page 279
9.8 Spanners for Heterogeneous Networks......Page 282
9.8.1 Heterogeneous Wireless Network Model......Page 283
9.8.2 Limitations......Page 284
9.8.3 Heterogeneous Sparse Structure......Page 285
9.8.4 Heterogeneous Power Spanner......Page 286
9.8.5 Heterogeneous Degree-Bounded Spanner......Page 287
Method 1 Partition Transmission Disks......Page 289
9.9 Fault-Tolerant Structures......Page 291
9.9.1 Fault Tolerance Based on a Geometric Approach......Page 293
9.9.2 Fault Tolerance Based on a Greedy Approach......Page 295
9.10 Other Spanners......Page 298
9.11 Conclusion and Remarks......Page 299
Problems......Page 300
10.1 Introduction......Page 302
10.2.1 Strong Connectivity......Page 305
10.2.2 Symmetric Connectivity......Page 307
10.2.3 Biconnectivity......Page 308
10.2.4 k-Connectivity......Page 310
10.3.1 Directed Unicast......Page 312
10.3.2 Symmetric Unicast......Page 313
10.3.3 Broadcast and Multicast......Page 314
10.4 Further Reading......Page 316
10.5 Conclusion and Remarks......Page 317
Problems......Page 319
11.1 Introduction......Page 321
11.2.1 Point Process......Page 324
11.3 Critical Range for Connectivity......Page 325
11.4.1 Lower Bound......Page 328
11.4.2 Upper Bound......Page 330
11.5 Connectivity with Bernoulli Nodes......Page 333
System Settings......Page 336
Transmission Phenomena for Connectivity......Page 337
Connectivity for a Small Point Set......Page 338
11.7 Further Reading......Page 339
11.8 Conclusion and Remarks......Page 342
Problems......Page 343
12.2 Critical Node Degree for Connectivity......Page 345
12.3 Critical Range for Connectivity in Sparse Networks......Page 347
12.4 Critical Range for Connectivity for Mobile Networks......Page 348
12.5 Critical Sensing Range for Coverage......Page 352
12.6 Critical Range for Successful Routing......Page 354
12.7 Further Reading......Page 362
12.8 Conclusion and Remarks......Page 363
Problems......Page 364
Part IV: Wireless Network Routing Protocols......Page 365
13.1 Introduction......Page 367
13.2.1 Destination-Sequenced Distance-Vector Routing......Page 368
13.2.2 Optimized Link-State Routing......Page 369
13.2.3 Metric-Based Routings......Page 370
13.2.4 Multipath Unicast Routing......Page 371
13.3 Reactive Approaches......Page 372
13.3.1 Ad Hoc On-Demand Vector Routing......Page 373
13.3.2 Dynamic Source Routing......Page 375
13.3.3 Opportunistic Routing......Page 377
13.4 Geographic Approaches......Page 379
Compass Routing......Page 380
Most-Forwarding Routing (MFR)......Page 381
Greedy-Compass Routing......Page 382
13.4.2 Right-Hand Rule and Face Routing......Page 383
13.4.3 Combining Face Routing with Greedy Routing......Page 385
13.4.4 Routing on Delaunay Triangulation......Page 386
13.4.5 Delivery Guarantee of Localized Routing Protocols......Page 388
13.4.6 Location-Aided Routing......Page 389
13.4.8 Location Service......Page 391
13.4.9 Node Localization......Page 392
13.5.1 Zone Routing Protocol......Page 393
13.5.2 Backbone-Based Routing......Page 394
13.6 Further Reading......Page 396
13.7 Conclusion and Remarks......Page 397
Problems......Page 399
Nonadjustable Power......Page 401
Broadcasting and Multicasting......Page 402
Distributed or Localized Algorithms?......Page 403
Message Contents......Page 404
Performance Measurement......Page 405
14.2.1 Centralized Clustering for Nonadjustable Power......Page 406
14.2.2 Based on MST and Variations for Adjustable Power......Page 408
14.2.3 Theoretical Performance Analysis......Page 410
Clustering Without Geometry Property......Page 412
Clustering with Geometry Property......Page 414
14.3.2 Localized Low-Weighted Structures for Adjustable-Power Scenario......Page 415
Structure Based on RNG......Page 417
Structure Based on LMST......Page 418
Combining RNG......Page 419
14.3.3 Combining Clustering and Low Weight......Page 420
Selecting Forwarding Neighbors......Page 421
Gossip and Probabilistic Schemes......Page 422
Area-Based Decision......Page 423
14.4 Scheduling Active and Sleep Periods......Page 424
14.5.1 Fixed Transmission Power......Page 426
Multicast with Asymmetric Communication......Page 428
Multicast with Symmetric Communication......Page 429
14.6 Further Reading......Page 430
14.7 Conclusion and Remarks......Page 431
Problems......Page 432
15.1 Introduction......Page 434
15.2.1 Preliminaries......Page 435
15.2.2 Communication Model......Page 438
15.3.1 Truthful Mechanism for Unicast......Page 440
VCG Mechanism on LCPT Is Not Strategy-Proof......Page 441
Strategy-Proof Mechanism on LCPT......Page 442
Constructing the NST......Page 444
VCG Mechanism on the NST Is Not Strategy-Proof......Page 445
Strategy-Proof Mechanism Based on NST......Page 446
Computational Complexity......Page 447
15.4 Sharing Multicast Costs or Payments Among Receivers......Page 448
15.4.1 Fair Payment-Sharing Scheme......Page 449
Payment Scheme......Page 452
Distributed-Payment Algorithm......Page 453
15.4.3 Payment-Sharing Among Receivers......Page 454
15.4.5 Truthful Multicast Using a Share-Based Tree......Page 459
15.4.6 Payment-Sharing Among Selfish Receivers......Page 461
15.5 Existence of Truthful Payment Scheme......Page 463
15.6.1 Reputation-Based Approaches......Page 465
15.6.2 Algorithmic Mechanism Design......Page 466
15.7 Conclusion and Remarks......Page 468
Repeated Games......Page 469
Problems......Page 470
16.1 Introduction......Page 472
16.2.1 Network System Models......Page 473
16.3 Problem Formulation for Cross-Layer Optimization......Page 476
16.3.2 Maximize Throughput......Page 477
Dynamic Channel Assignment......Page 478
Polynomial-Time Schedulable Flows......Page 479
16.3.4 Integrated Cross-Layer Mixed IP......Page 480
16.4.1 Polynomial-Time Scheduling Method......Page 481
16.4.2 Correctness and Performance Guarantee......Page 483
The Proof of Theorem 16.1......Page 485
16.4.3 Improvement and Implementations......Page 486
16.5 Further Reading......Page 487
16.6 Conclusion......Page 490
Problems......Page 491
Part V: Other Issues......Page 493
17.1 Introduction......Page 495
17.2.1 Time of Arrival (ToA)......Page 497
17.2.2 Time Difference of Arrival (TDoA)......Page 499
17.2.3 Angle of Arrival (AoA)......Page 500
17.2.4 Signal Strength......Page 501
17.3 Computational Complexity of Sensor Network Localization......Page 502
17.3.1 Complexity Results with Distance Information......Page 504
17.3.2 Complexity Results with Other Information......Page 507
17.4 Progressive Localization Methods......Page 508
17.4.1 Trilateration......Page 509
17.4.2 Multilateration......Page 510
17.4.3 Sweep and Linear-Programming-Based Techniques......Page 511
17.4.4 Distributed Localization Using Noisy Data......Page 512
17.5.2 Distance to Anchors......Page 514
DV-Hop......Page 515
Node Position......Page 516
17.6 Target Tracking and Classification......Page 517
17.6.2 Network-Based Tracking......Page 518
17.6.3 Collaborative Signal Processing......Page 519
Using Space–Time Cells......Page 520
Single-Target Tracking......Page 521
Target Classification......Page 522
17.6.5 Target Tracking Based on Cooperative Binary Detection......Page 524
System Model......Page 525
Algorithm......Page 526
Data Aggregation......Page 527
17.6.6 Distributed Prediction Tracking (DPT)......Page 528
Sensor-Selection Algorithm......Page 529
17.7.1 Active Badge and Bat......Page 530
17.7.2 Cricket......Page 531
17.8 Conclusion and Remarks......Page 532
Problems......Page 533
18.1 Introduction......Page 535
18.2 Capacity of Unicast for an Arbitrary Network......Page 538
18.3 Capacity of Unicast for Randomly Deployed Networks......Page 540
18.4 Capacity of Broadcast for an Arbitrary Network......Page 542
18.5 Capacity of Broadcast for Randomly Deployed Networks......Page 544
18.6 Further Reading......Page 549
18.7 Conclusion and Remarks......Page 550
Problems......Page 551
19.1 Introduction......Page 553
19.2 Cryptography Fundamentals......Page 554
Block Ciphers and Stream Ciphers......Page 555
Data-Encryption Standard......Page 558
Advanced Encryption System (AES)......Page 560
19.2.2 Public-Key-Encryption Methods......Page 562
RSA Cryptosystem......Page 563
ElGamal Cryptosystem......Page 564
19.2.3 Digital-Signature Methods......Page 565
19.2.4 Key-Agreement and Key-Distribution Protocols......Page 566
19.3 Key-Predistribution Protocols......Page 568
19.4.1 Secure Routing for Sensor Networks......Page 570
19.4.2 Stochastic Routing Protocols......Page 572
19.5 Further Reading......Page 574
19.6 Conclusion and Remarks......Page 575
Problems......Page 576
Abbreviations......Page 579
Organizations......Page 581
Index......Page 611