rfworld
2012-11-01, 08:22 PM
HANDBOOK OF WIRELESS NETWORKS AND MOBILE COMPUTING
Edited by Ivan Stojmenovic
Copyright © 2002 John Wiley & Sons, Inc.
ISBNs: 0-471-41902-8 (Paper); 0-471-22456-1 (Electronic)
CONTENTS
1 Handoff in Wireless Mobile Networks 1
Qing-An Zeng and Dharma P. Agrawal
1.1 Introduction 1
1.2 Types of Handoffs 1
1.3 Handoff Initiation 2
1.4 Handoff Decision 4
1.5 Handoff Schemes 4
1.6 Summary 24
References 24
2 Location Management in Cellular Networks 27
Jingyuan Zhang
2.1 Introduction 27
2.2 Cellular Networks 27
2.3 Location Management 29
2.4 Common Assumptions for Performance Evaluation 30
2.5 Location Management Schemes 34
2.6 Summary 46
Acknowledgments 47
References 47
3 Heuristics for Solving Fixed-Channel Assignment Problems 51
Harilaos G. Sandalidis and Peter Stavroulakis
3.1 Introduction 51
3.2 Resource Management Tasks 51
3.3 Interference in Cellular Systems 52
3.4 Frequency Management and Channel Assignment Issues 54
3.5 Channel Assignment 56
v
3.6 Fixed-Channel Assignment Problem 57
3.7 Heuristic Techniques for Combinatorial Optimization 60
3.8 Heuristic FCA Schemes 62
3.9 Conclusions 67
References 67
4 Channel Assignment and Graph Multicoloring 71
Lata Narayanan
4.1 Introduction 71
4.2 Preliminaries 74
4.3 Basic Types of Algorithms 77
4.4 Lower Bounds 78
4.5 The Static Case 82
4.6 The Online Case 90
4.7 Discussion and Open Problems 91
References 92
5 Channel Assignment and Graph Labeling 95
Jeannette C. M. Janssen
5.1 Introduction 95
5.2 Lower Bounds 99
5.3 Algorithms 104
5.4 Conclusions and Open Problems 114
Acknowledgments 115
References 115
6 Wireless Media Access Control 119
Andrew D. Myers and Stefano Basagni
6.1 Introduction 119
6.2 General Concepts 119
6.3 Wireless Issues 123
6.4 Fundamental MAC Protocols 124
6.5 Centralized MAC Protocols 127
6.6 Ad Hoc MAC Protocols 130
6.7 Summary 141
References 142
7 Traffic Integration in Personal, Local, and Geographical Wireless Networks 145
Raffaele Bruno, Marco Conti, and Enrico Gregori
7.1 Introduction 145
7.2 A Technology for WPAN: Bluetooth 147
7.3 Technologies for High-Speed WLANs 153
vi CONTENTS
7.4 Third-Generation Cellular Systems: UMTS 160
Acknowledgments 168
References 168
8 Fair Scheduling in Wireless Packet Data Networks 171
Thyagarajan Nandagopal and Xia Gao
8.1 Introduction 171
8.2 Models and Issues 172
8.3 Wireless Fair Queueing Architecture 180
8.4 Algorithms for Wireless Fair Queueing 186
8.5 Issues and Future Directions 190
References 193
9 Randomized Initialization Protocols for Radio Networks 195
Koji Nakano and Stephan Olariu
9.1 Introduction 195
9.2 State of the Art 197
9.3 A Refresher of Basic Probability Theory 198
9.4 Energy-Efficient Prefix Sums Protocols 200
9.5 Initializing a Single-Channel RN 202
9.6 Initializing a k-Channel RN 207
9.7 Energy-Efficient Initialization Protocols 208
9.8 Concluding Remarks and Open Problems 215
Acknowledgments 216
References 216
10 Leader Election Protocols for Radio Networks 219
Koji Nakano and Stephan Olariu
10.1 Introduction 219
10.2 A Brief Refresher of Probability Theory 222
10.3 Oblivious Leader Election Protocols 224
10.4 Uniform Leader Election Protocols 227
10.5 Nonuniform Leader Election Protocol 234
10.6 Concluding Remarks and Open Problems 240
Acknowledgments 241
References 241
11 Data Broadcast 243
Jianliang Xu, Dik-Lun Lee, Qinglong Hu, and Wang-Chien Lee
11.1 Introduction 243
11.2 Data Scheduling 245
11.3 Air Indexing 253
CONTENTS vii
11.4 Other Issues 260
11.5 Summary 262
Acknowledgments 262
References 263
12 Ensemble Planning for Digital Audio Broadcasting 267
Albert Gräf and Thomas McKenney
12.1 Introduction 267
12.2 The Ensemble Planning Problem 268
12.3 Basic Solution Techniques 271
12.4 Lower Bounds 273
12.5 A Tabu Search Method 274
12.6 Conclusion 286
Acknowledgments 287
References 287
13 Transport over Wireless Networks 289
Hung-Yun Hsieh and Raghupathy Sivakumar
13.1 Introduction 289
13.2 Overview of TCP 291
13.3 TCP over Wireless Networks 293
13.4 Approaches to Improve Transport Layer Performance 297
13.5 Summary 306
References 307
14 Security and Fraud Detection in Mobile and Wireless Networks 309
Azzedine Boukerche
14.1 Introduction 309
14.2 Network Security Problems 310
14.3 Network Security Management Plan 311
14.4 Intrusion Detection Systems (IDS) 311
14.5 Securing Data Transfer in Digital Mobile Systems 312
14.6 Securing Wireless Ad Hoc Networks 313
14.7 Authentication of Mobile Users 315
14.8 Subscription and Fraud Detection in Mobile Phone Systems 317
14.9 Conclusion 321
References 322
15 Mobile Ad Hoc Networks 325
Silvia Giordano
15.1 Introduction 325
15.2 Layered Architecture of Mobile Ad Hoc Networks 327
viii CONTENTS
15.3 MAC Layer 331
15.4 Mobile Ad Hoc Networks and the Internet 335
15.5 Routing in Self-Organized Networks 339
15.6 People-Based Networks 341
15.7 Conclusion 342
Acknowledgments 343
References 343
16 Broadcast Scheduling for TDMA in Wireless Multihop Networks 347
Errol L. Lloyd
16.1 Introduction 347
16.2 What Is Broadcast Scheduling? 347
16.3 The Complexity of Broadcast Scheduling 351
16.4 Centralized Algorithms 352
16.5 Distributed Algorithms 359
16.6 Related Results 366
16.7 Summary and Open Problems 368
Acknowledgments 368
References 368
17 Mobile Ad Hoc Networks and Routing Protocols 371
Yu-Chee Tseng, Wen-Hua Liao, and Shih-Lin Wu
17.1 Introduction 371
17.2 Unicast Routing Protocols for MANET 372
17.3 Broadcasting Protocols for MANET 381
17.4 Multicasting Protocols for MANET 383
17.5 QoS Routing 385
17.6 Extending Cellular Systems with Ad Hoc Links 389
17.7 Conclusions 390
Acknowledgments 391
References 391
18 Routing with Guaranteed Delivery in Geometric and 393
Wireless Networks
Jorge Urrutia
18.1 Introduction 393
18.2 Applications to Ad Hoc Wireless Communication Networks 401
18.3 Delaunay Triangulations 403
18.4 Conclusions 404
Acknowledgments 404
References 404
CONTENTS ix
19 Power Optimization in Routing Protocols for Wireless and 407
Mobile Networks
Stephanie Lindsey, Krishna M. Sivalingam, and Cauligi S. Raghavendra
19.1 Introduction 407
19.2 Background 408
19.3 Energy Analysis of AODV and DSR Routing Protocols 409
19.4 Power-Aware Routing Metrics 413
19.5 Routing Based on Balanced Energy Consumption of Nodes 417
19.6 Broadcast and Multicast Tree Construction 418
19.7 Topology Control Using Transmit Power Adjustment 419
19.8 Summary 421
Acknowledgments 421
References 421
20 Dominating-Set-Based Routing in Ad Hoc Wireless Networks 425
Jie Wu
20.1 Introduction 425
20.2 Preliminaries 427
20.3 Formation of a Connected Dominating Set 431
20.4 Extensions 438
20.5 Conclusions and Future Directions 447
Acknowledgments 448
References 448
21 Location Updates for Efficient Routing in Ad Hoc Networks 451
Ivan Stojmenovic´
21.1 Introduction 451
21.2 Classification of Routing Algorithms 452
21.3 Location Updates Between Neighboring Nodes 457
21.4 Request Zone Routing 458
21.5 Doubling Circles Routing 459
21.6 Quorum-Based Strategies 460
21.7 Home-Agent-Based Strategy 463
21.8 Performance Evaluation Issues 465
21.9 Conclusion 468
References 468
22 Topological Design, Routing, and Handover in Satellite Networks 473
Afonso Ferreira, Jérôme Galtier, and Paolo Penna
22.1 Introduction 473
22.2 Topologies 473
x CONTENTS
22.3 Network Mobility and Traffic Modeling 478
22.4 Routing and Handover 484
22.5 Conclusions 491
Acknowledgments 491
References 491
23 Multicasting: From Fixed Networks to Ad Hoc Networks 495
Thomas Kunz
23.1 Introduction 495
23.2 Motivation 495
23.3 Multicasting in Fixed/Wired Networks 497
23.4 Multicasting in Fixed Infrastructure Cellular Networks 497
23.5 Multicasting in Mobile Ad Hoc Networks: Adopting Wireless 500
Protocols
23.6 Multicasting in Mobile Ad Hoc Networks: MANET-Inspired 502
Multicast Protocols
23.7 Conclusions 506
Acknowledgments 508
References 508
24 Broadcasting in Radio Networks 509
Andrzej Pelc
24.1 Introduction 509
24.2 Communication Scenarios 510
24.3 The Graph Model 512
24.4 The Geometric Model 519
24.5 Other Variants of the Problem 521
24.6 Conclusion and Open Problems 525
Acknowledgments 526
References 526
25 Mobile IP Protocols 529
Christos Douligeris and Thanos Vasilakos
25.1 Introduction 529
25.2 Mobility Requirements and Constraints in an IP Environment 530
25.3 Mobile IP Protocol Overview 531
25.4 Route Optimization 544
25.5 Mobility Support for IPv6 546
25.6 Connectivity with 3G Networks 547
25.7 Management of Information Bases 549
25.8 Conclusions 550
References 551
CONTENTS xi
26 Data Management in Wireless Mobile Environments 553
Sandeep K. S. Gupta and Pradip K. Srimani
26.1 Introduction 553
26.2 Data Management Issues in Mobile Environments 555
26.3 Caching of Data 555
26.4 An Informal Overview 557
26.5 Formal Description of the Scheme 564
26.6 Performance Analysis 566
26.7 Performance Comparison 570
26.8 Summary 574
Acknowledgments 578
References 578
27 Mobile, Distributed, and Pervasive Computing 581
Michel Barbeau
27.1 Introduction 581
27.2 Pervasive Computing Applications 582
27.3 Architecture of Pervasive Computing Software 583
27.4 Open Protocols 584
27.5 Summary 598
Acknowledgments 599
References 599
28 Indoor Wireless Environments 601
Lakshmi Ramachandran
28.1 Introduction 601
28.2 The Physical Layer 602
28.3 Media Access Control 604
28.4 Network Topology 615
28.5 Characterization of the Environment 620
28.6 Challenges for the Future: Nomadic Computing 621
28.7 Summary 621
Acknowledgments 621
References 622
Index 625
Edited by Ivan Stojmenovic
Copyright © 2002 John Wiley & Sons, Inc.
ISBNs: 0-471-41902-8 (Paper); 0-471-22456-1 (Electronic)
CONTENTS
1 Handoff in Wireless Mobile Networks 1
Qing-An Zeng and Dharma P. Agrawal
1.1 Introduction 1
1.2 Types of Handoffs 1
1.3 Handoff Initiation 2
1.4 Handoff Decision 4
1.5 Handoff Schemes 4
1.6 Summary 24
References 24
2 Location Management in Cellular Networks 27
Jingyuan Zhang
2.1 Introduction 27
2.2 Cellular Networks 27
2.3 Location Management 29
2.4 Common Assumptions for Performance Evaluation 30
2.5 Location Management Schemes 34
2.6 Summary 46
Acknowledgments 47
References 47
3 Heuristics for Solving Fixed-Channel Assignment Problems 51
Harilaos G. Sandalidis and Peter Stavroulakis
3.1 Introduction 51
3.2 Resource Management Tasks 51
3.3 Interference in Cellular Systems 52
3.4 Frequency Management and Channel Assignment Issues 54
3.5 Channel Assignment 56
v
3.6 Fixed-Channel Assignment Problem 57
3.7 Heuristic Techniques for Combinatorial Optimization 60
3.8 Heuristic FCA Schemes 62
3.9 Conclusions 67
References 67
4 Channel Assignment and Graph Multicoloring 71
Lata Narayanan
4.1 Introduction 71
4.2 Preliminaries 74
4.3 Basic Types of Algorithms 77
4.4 Lower Bounds 78
4.5 The Static Case 82
4.6 The Online Case 90
4.7 Discussion and Open Problems 91
References 92
5 Channel Assignment and Graph Labeling 95
Jeannette C. M. Janssen
5.1 Introduction 95
5.2 Lower Bounds 99
5.3 Algorithms 104
5.4 Conclusions and Open Problems 114
Acknowledgments 115
References 115
6 Wireless Media Access Control 119
Andrew D. Myers and Stefano Basagni
6.1 Introduction 119
6.2 General Concepts 119
6.3 Wireless Issues 123
6.4 Fundamental MAC Protocols 124
6.5 Centralized MAC Protocols 127
6.6 Ad Hoc MAC Protocols 130
6.7 Summary 141
References 142
7 Traffic Integration in Personal, Local, and Geographical Wireless Networks 145
Raffaele Bruno, Marco Conti, and Enrico Gregori
7.1 Introduction 145
7.2 A Technology for WPAN: Bluetooth 147
7.3 Technologies for High-Speed WLANs 153
vi CONTENTS
7.4 Third-Generation Cellular Systems: UMTS 160
Acknowledgments 168
References 168
8 Fair Scheduling in Wireless Packet Data Networks 171
Thyagarajan Nandagopal and Xia Gao
8.1 Introduction 171
8.2 Models and Issues 172
8.3 Wireless Fair Queueing Architecture 180
8.4 Algorithms for Wireless Fair Queueing 186
8.5 Issues and Future Directions 190
References 193
9 Randomized Initialization Protocols for Radio Networks 195
Koji Nakano and Stephan Olariu
9.1 Introduction 195
9.2 State of the Art 197
9.3 A Refresher of Basic Probability Theory 198
9.4 Energy-Efficient Prefix Sums Protocols 200
9.5 Initializing a Single-Channel RN 202
9.6 Initializing a k-Channel RN 207
9.7 Energy-Efficient Initialization Protocols 208
9.8 Concluding Remarks and Open Problems 215
Acknowledgments 216
References 216
10 Leader Election Protocols for Radio Networks 219
Koji Nakano and Stephan Olariu
10.1 Introduction 219
10.2 A Brief Refresher of Probability Theory 222
10.3 Oblivious Leader Election Protocols 224
10.4 Uniform Leader Election Protocols 227
10.5 Nonuniform Leader Election Protocol 234
10.6 Concluding Remarks and Open Problems 240
Acknowledgments 241
References 241
11 Data Broadcast 243
Jianliang Xu, Dik-Lun Lee, Qinglong Hu, and Wang-Chien Lee
11.1 Introduction 243
11.2 Data Scheduling 245
11.3 Air Indexing 253
CONTENTS vii
11.4 Other Issues 260
11.5 Summary 262
Acknowledgments 262
References 263
12 Ensemble Planning for Digital Audio Broadcasting 267
Albert Gräf and Thomas McKenney
12.1 Introduction 267
12.2 The Ensemble Planning Problem 268
12.3 Basic Solution Techniques 271
12.4 Lower Bounds 273
12.5 A Tabu Search Method 274
12.6 Conclusion 286
Acknowledgments 287
References 287
13 Transport over Wireless Networks 289
Hung-Yun Hsieh and Raghupathy Sivakumar
13.1 Introduction 289
13.2 Overview of TCP 291
13.3 TCP over Wireless Networks 293
13.4 Approaches to Improve Transport Layer Performance 297
13.5 Summary 306
References 307
14 Security and Fraud Detection in Mobile and Wireless Networks 309
Azzedine Boukerche
14.1 Introduction 309
14.2 Network Security Problems 310
14.3 Network Security Management Plan 311
14.4 Intrusion Detection Systems (IDS) 311
14.5 Securing Data Transfer in Digital Mobile Systems 312
14.6 Securing Wireless Ad Hoc Networks 313
14.7 Authentication of Mobile Users 315
14.8 Subscription and Fraud Detection in Mobile Phone Systems 317
14.9 Conclusion 321
References 322
15 Mobile Ad Hoc Networks 325
Silvia Giordano
15.1 Introduction 325
15.2 Layered Architecture of Mobile Ad Hoc Networks 327
viii CONTENTS
15.3 MAC Layer 331
15.4 Mobile Ad Hoc Networks and the Internet 335
15.5 Routing in Self-Organized Networks 339
15.6 People-Based Networks 341
15.7 Conclusion 342
Acknowledgments 343
References 343
16 Broadcast Scheduling for TDMA in Wireless Multihop Networks 347
Errol L. Lloyd
16.1 Introduction 347
16.2 What Is Broadcast Scheduling? 347
16.3 The Complexity of Broadcast Scheduling 351
16.4 Centralized Algorithms 352
16.5 Distributed Algorithms 359
16.6 Related Results 366
16.7 Summary and Open Problems 368
Acknowledgments 368
References 368
17 Mobile Ad Hoc Networks and Routing Protocols 371
Yu-Chee Tseng, Wen-Hua Liao, and Shih-Lin Wu
17.1 Introduction 371
17.2 Unicast Routing Protocols for MANET 372
17.3 Broadcasting Protocols for MANET 381
17.4 Multicasting Protocols for MANET 383
17.5 QoS Routing 385
17.6 Extending Cellular Systems with Ad Hoc Links 389
17.7 Conclusions 390
Acknowledgments 391
References 391
18 Routing with Guaranteed Delivery in Geometric and 393
Wireless Networks
Jorge Urrutia
18.1 Introduction 393
18.2 Applications to Ad Hoc Wireless Communication Networks 401
18.3 Delaunay Triangulations 403
18.4 Conclusions 404
Acknowledgments 404
References 404
CONTENTS ix
19 Power Optimization in Routing Protocols for Wireless and 407
Mobile Networks
Stephanie Lindsey, Krishna M. Sivalingam, and Cauligi S. Raghavendra
19.1 Introduction 407
19.2 Background 408
19.3 Energy Analysis of AODV and DSR Routing Protocols 409
19.4 Power-Aware Routing Metrics 413
19.5 Routing Based on Balanced Energy Consumption of Nodes 417
19.6 Broadcast and Multicast Tree Construction 418
19.7 Topology Control Using Transmit Power Adjustment 419
19.8 Summary 421
Acknowledgments 421
References 421
20 Dominating-Set-Based Routing in Ad Hoc Wireless Networks 425
Jie Wu
20.1 Introduction 425
20.2 Preliminaries 427
20.3 Formation of a Connected Dominating Set 431
20.4 Extensions 438
20.5 Conclusions and Future Directions 447
Acknowledgments 448
References 448
21 Location Updates for Efficient Routing in Ad Hoc Networks 451
Ivan Stojmenovic´
21.1 Introduction 451
21.2 Classification of Routing Algorithms 452
21.3 Location Updates Between Neighboring Nodes 457
21.4 Request Zone Routing 458
21.5 Doubling Circles Routing 459
21.6 Quorum-Based Strategies 460
21.7 Home-Agent-Based Strategy 463
21.8 Performance Evaluation Issues 465
21.9 Conclusion 468
References 468
22 Topological Design, Routing, and Handover in Satellite Networks 473
Afonso Ferreira, Jérôme Galtier, and Paolo Penna
22.1 Introduction 473
22.2 Topologies 473
x CONTENTS
22.3 Network Mobility and Traffic Modeling 478
22.4 Routing and Handover 484
22.5 Conclusions 491
Acknowledgments 491
References 491
23 Multicasting: From Fixed Networks to Ad Hoc Networks 495
Thomas Kunz
23.1 Introduction 495
23.2 Motivation 495
23.3 Multicasting in Fixed/Wired Networks 497
23.4 Multicasting in Fixed Infrastructure Cellular Networks 497
23.5 Multicasting in Mobile Ad Hoc Networks: Adopting Wireless 500
Protocols
23.6 Multicasting in Mobile Ad Hoc Networks: MANET-Inspired 502
Multicast Protocols
23.7 Conclusions 506
Acknowledgments 508
References 508
24 Broadcasting in Radio Networks 509
Andrzej Pelc
24.1 Introduction 509
24.2 Communication Scenarios 510
24.3 The Graph Model 512
24.4 The Geometric Model 519
24.5 Other Variants of the Problem 521
24.6 Conclusion and Open Problems 525
Acknowledgments 526
References 526
25 Mobile IP Protocols 529
Christos Douligeris and Thanos Vasilakos
25.1 Introduction 529
25.2 Mobility Requirements and Constraints in an IP Environment 530
25.3 Mobile IP Protocol Overview 531
25.4 Route Optimization 544
25.5 Mobility Support for IPv6 546
25.6 Connectivity with 3G Networks 547
25.7 Management of Information Bases 549
25.8 Conclusions 550
References 551
CONTENTS xi
26 Data Management in Wireless Mobile Environments 553
Sandeep K. S. Gupta and Pradip K. Srimani
26.1 Introduction 553
26.2 Data Management Issues in Mobile Environments 555
26.3 Caching of Data 555
26.4 An Informal Overview 557
26.5 Formal Description of the Scheme 564
26.6 Performance Analysis 566
26.7 Performance Comparison 570
26.8 Summary 574
Acknowledgments 578
References 578
27 Mobile, Distributed, and Pervasive Computing 581
Michel Barbeau
27.1 Introduction 581
27.2 Pervasive Computing Applications 582
27.3 Architecture of Pervasive Computing Software 583
27.4 Open Protocols 584
27.5 Summary 598
Acknowledgments 599
References 599
28 Indoor Wireless Environments 601
Lakshmi Ramachandran
28.1 Introduction 601
28.2 The Physical Layer 602
28.3 Media Access Control 604
28.4 Network Topology 615
28.5 Characterization of the Environment 620
28.6 Challenges for the Future: Nomadic Computing 621
28.7 Summary 621
Acknowledgments 621
References 622
Index 625