第1页 / 共614页
第2页 / 共614页
第3页 / 共614页
第4页 / 共614页
第5页 / 共614页
第6页 / 共614页
第7页 / 共614页
第8页 / 共614页
Wireless Ad Hoc and Sensor Networks Theory and Applications.pdf
Cover
Half-title
Title
Copyright
Contents
Preface
Introduction
Audience
Organization of the Book
Acknowledgments
Abbreviations
Part I: Introduction
1 History of Wireless Networks
1.1 Introduction
1.2 Different Wireless Networks
Based on Network Architecture
Based on Communication Coverage Area
1.2.1 Wireless Cellular Networks
First-Generation Mobile Systems
Second-Generation Mobile Systems
2.5G Mobile Systems
Third-Generation Mobile Systems
1.2.2 Wireless Access Points
Limitations
Security
1.2.3 Wireless Ad Hoc Networks
Mobile Ad Hoc Networks
Wireless Sensor Networks
Mesh Networks
1.3 Conclusion
Problems
2 Wireless Transmission Fundamentals
2.1 Wireless Channels
2.1.1 Free-Space Propagation Model
2.1.2 Two-Ray Ground Model
2.1.3 The Log-Distance Path-Loss Model
2.1.4 Large-Scale and Small-Scale Variations
2.2 The Wireless Communication Graph
2.3 Power Assignment and Topology Control
Power Assignment
Asymptotic Power Assignment
Topology Control
Limitations
2.4 The Wireless Interference Graph
Protocol-Interference Model (PrIM)
Fixed Power-Protocol-Interference Model (fPrIM)
RTS/CTS Model
Transmitter Interference Model (TxIM)
Physical-Interference Model (PhIM)
2.5 Related Graph Problems and Geometry Concepts
2.5.1 Geometry Concepts
2.6 Energy-Consumption Models
2.6.1 Wireless Ad Hoc Networks
2.6.2 Wireless Sensor Networks
2.7 Mobility Models
Random-Walk and Random-Direction Models
Random-Waypoint Model
Random-Trip Mobility Model
Markov Mobility Models
Smooth Random-Mobility Model
Group Mobility
Other Issues
2.8 Conclusion
Problems
Part II: Wireless MACs
3 Wireless Medium-Access Control
3.1 Introduction
Contention-Based MAC
TDMA-Based Node and/or Link Scheduling
3.2 IEEE 802.11 Architecture and Protocols
3.2.1 Various IEEE 802.11 Protocols
802.11a
802.11b
802.11g
802.11n
3.2.2 Distributed Coordination Function
3.2.3 Problems and Solutions for the Ad Hoc Model
3.2.4 Ad Hoc Networking Support
Synchronization Maintenance
Synchronization Acquirement
3.2.5 Power Management
3.2.6 Centrally Controlled Access Mechanism
3.2.7 Other Extensions and Enhancements
3.3 WiMAX
Technical Advantages over WiFi
Applications for WiMAX
3.4 Bluetooth
Pairing
Air Interface
Possible Bluetooth Uses
3.5 MAC Protocols for Wireless Sensor Networks
3.5.1 B-MAC
3.5.2 Z-MAC
3.5.3 X-MAC
3.5.4 Funneling-MAC
3.6 Conclusion
Problems
4 TDMA Channel Assignment
4.1 Introduction
4.2 System Model and Assumptions
4.2.1 Network and Interference Models
Network Model
Interference Models
4.2.2 Problem Formulation
4.3 Centralized Scheduling
4.3.1 Scheduling under the Protocol-Interference Model
4.3.2 Scheduling under the RTS/CTS Model
4.3.3 Scheduling under the fPrIM
4.4 Distributed Algorithms
4.4.1 Algorithm for the RTS/CTS Model
4.4.2 Faster Algorithm for the RTS/CTS Model
4.4.3 Distributed Algorithm for the fPrIM
4.5 Weighted Coloring and Schedulable Flows
4.5.1 Scheduling with Traffic Load
4.5.2 Necessary and Sufficient Conditions for Schedulable Flows
4.6 Further Reading
4.7 Conclusion and Remarks
Problems
5 Spectrum Channel Assignment
5.1 Introduction
5.2 Network System Model
5.3 List-Coloring for Access Networks
5.3.1 Centralized Method for Maximizing Capacity
5.3.2 Distributed Coloring for Minimizing Channels
5.4 List-Coloring for Ad Hoc Networks
Complexity Result
5.5 Transition Phenomena on Channel Availability
5.6 Further Reading
5.7 Conclusion and Remarks
Problems
6 CDMA Code Channel Assignment
6.1 Introduction
6.2 System Model and Assumptions
6.2.1 Problem Formulations
6.2.2 A Technical Lemma
6.3 Throughput and Bottleneck of General Graphs
6.4 Approximation Algorithms for Interference Graphs
6.4.1 First-Fit Prefix-Free Coloring
6.4.2 Tile Prefix-Free Coloring
6.4.3 Improved Approximation Ratio
6.5 Maximum Weighted Independent Set for a General Wireless Network Model
6.5.1 A General Wireless Network Model
6.5.2 Simple Distributed Method for a MIS
6.5.3 Polynomial-Time-Approximation Scheme for a MIS
6.6 Further Reading
6.7 Conclusion and Remarks
Problems
Part III: Topology Control and Clustering
7 Clustering and Network Backbone
7.1 Introduction
7.2 Network Models and Problem Formulation
7.3 Centralized Algorithms for a Connected Dominating Set
7.3.1 Algorithms for General Graphs
7.3.2 Algorithms for Graphs Modeling Wireless Ad Hoc Networks
7.4 Message Lower Bound for Distributed-Backbone Construction
7.5 Some Backbone-Formation Heuristics
7.5.1 Algorithm by Das et al.
7.5.2 Algorithm by Wu and Li
7.5.3 Algorithm by Stojmenovic et al.
7.6 Efficient Distributed-Nontrivial-Backbone-Formation Method
7.6.1 MIS Construction
7.6.2 Connected-Dominating-Set Construction
7.6.3 Properties of Constructed Backbone
7.7 Efficient Distributed-Backbone-Formation Method
7.7.1 Clustering
7.7.2 Finding Connectors
7.7.3 The Properties of Backbone
7.8 Linear-Programming-Based Approaches
7.9 Geometry-Position-Based Approaches
Greedy Method Based on Node Positions
Grid-Partition-Based Approach
7.10 Further Reading
7.11 Conclusion and Remarks
Problems
8 Weighted Network Backbone
8.1 Introduction
8.2 Study of Typical Methods
8.3 Centralized Low-Cost Backbone-Formation Algorithms
8.4 Efficient Distributed Low-Cost Backbone-Formation Algorithms
8.4.1 Finding Dominators
8.4.2 Finding Connectors
8.5 Performance Guarantee
8.5.1 Total Cost of the Backbone
8.5.2 Unicast Performance
8.5.3 Message Complexity
8.5.4 Time Complexity
8.6 Discussion
8.6.1 pplicat onPracticalAi
Energy-Consumption Rate
Fault-Tolerant Rate
Security Level
8.6.2 Dynamic Update
8.6.3 Practical Implementation
8.7 Further Reading
8.8 Conclusion and Remarks
Problems
9 Topology Control with Flat Structures
9.1 Introduction
9.1.1 Ad Hoc Networks: Graph Model
9.1.2 Geometrical Spanner
9.1.3 Power Spanner
9.1.4 Efficient Localized Construction
9.1.5 Relay Regions
9.2 Current State of Knowledge
9.2.1 Unicast Topology
9.2.2 Energy-Efficient Broadcast Topology
9.3 Planar Structures
9.3.1 Relative Neighborhood Graph
9.3.2 Gabriel Graph
9.3.3 Delaunay Triangulation
9.3.4 Local Delaunay Graph
9.4 Bounded-Degree Spanner and Yao’s Family
9.4.1 Yao Graph
9.4.2 Symmetric Yao
9.4.3 Sparse Yao
9.4.4 Yao and Sink Structure
9.4.5 Ordered Yao
9.5 Bounded-Degree Planar Spanner
9.5.1 Delaunay Triangulation plus Yao Structure
9.5.2 Local Delaunay Graph plus Yao Structure
9.5.3 Gabriel Graph plus Yao Structure
9.6 Low-Weighted Structures
9.7 A Unified Structure: Energy Efficiency for Unicast and Broadcast
9.7.1 Power-Efficient Unicast: Spanner, Planar, and Bounded Degree
9.7.2 Unified Power-Efficient Topology: Degree-Bounded Planar Spanner
9.7.3 Expected Interference in Random Networks
9.7.4 Discussion
9.8 Spanners for Heterogeneous Networks
9.8.1 Heterogeneous Wireless Network Model
9.8.2 Limitations
9.8.3 Heterogeneous Sparse Structure
9.8.4 Heterogeneous Power Spanner
9.8.5 Heterogeneous Degree-Bounded Spanner
Method 1 Partition Transmission Disks
9.9 Fault-Tolerant Structures
9.9.1 Fault Tolerance Based on a Geometric Approach
9.9.2 Fault Tolerance Based on a Greedy Approach
9.10 Other Spanners
9.11 Conclusion and Remarks
Problems
10 Power Assignment
10.1 Introduction
10.2 Power Assignment for Connectivity
10.2.1 Strong Connectivity
10.2.2 Symmetric Connectivity
10.2.3 Biconnectivity
10.2.4 k-Connectivity
10.3 Power Assignment for Routing
10.3.1 Directed Unicast
10.3.2 Symmetric Unicast
10.3.3 Broadcast and Multicast
10.4 Further Reading
10.5 Conclusion and Remarks
Problems
11 Critical Transmission Ranges
11.1 Introduction
11.2 Preliminaries
11.2.1 Point Process
11.2.2 Connectivity and Minimum Degree
11.3 Critical Range for Connectivity
11.4 Critical Range for k-Connectivity
11.4.1 Lower Bound
11.4.2 Upper Bound
11.5 Connectivity with Bernoulli Nodes
11.6 Practical Performances
System Settings
Transmission Phenomena for Connectivity
Connectivity and Minimum Degree
Connectivity for a Small Point Set
Practical Transmission Ranges for k-Connectivity
11.7 Further Reading
11.8 Conclusion and Remarks
Problems
12 Other Transition Phenomena
12.1 Introduction
12.2 Critical Node Degree for Connectivity
12.3 Critical Range for Connectivity in Sparse Networks
12.4 Critical Range for Connectivity for Mobile Networks
12.5 Critical Sensing Range for Coverage
12.6 Critical Range for Successful Routing
12.7 Further Reading
12.8 Conclusion and Remarks
Problems
Part IV: Wireless Network Routing Protocols
13 Energy-Efficient Unicast Routing
13.1 Introduction
13.2 Proactive Approaches
13.2.1 Destination-Sequenced Distance-Vector Routing
13.2.2 Optimized Link-State Routing
13.2.3 Metric-Based Routings
13.2.4 Multipath Unicast Routing
13.3 Reactive Approaches
13.3.1 Ad Hoc On-Demand Vector Routing
13.3.2 Dynamic Source Routing
13.3.3 Opportunistic Routing
13.4 Geographic Approaches
13.4.1 Simple Heuristics
Compass Routing
Random Compass Routing
Greedy Routing
Most-Forwarding Routing (MFR)
Nearest-Neighbor Routing (NNR)
Farthest-Neighbor Routing (FNR)
Greedy-Compass Routing
13.4.2 Right-Hand Rule and Face Routing
13.4.3 Combining Face Routing with Greedy Routing
13.4.4 Routing on Delaunay Triangulation
13.4.5 Delivery Guarantee of Localized Routing Protocols
13.4.6 Location-Aided Routing
13.4.7 Geocasting
13.4.8 Location Service
13.4.9 Node Localization
13.5 Clustering and Hierarchical Routing
13.5.1 Zone Routing Protocol
13.5.2 Backbone-Based Routing
13.6 Further Reading
13.7 Conclusion and Remarks
Problems
14 Energy-Efficient Broadcast/Multicast
14.1 Introduction
Nonadjustable Power
Adjustable Power
Broadcasting and Multicasting
Distributed or Localized Algorithms?
MAC Specification
Reliability
Message Contents
Jitter and Random-Assessment Delay (RAD)
Performance Measurement
14.2 Centralized Methods
14.2.1 Centralized Clustering for Nonadjustable Power
14.2.2 Based on MST and Variations for Adjustable Power
14.2.3 Theoretical Performance Analysis
14.3 Efficient Distributed or Localized Methods
14.3.1 Based on Distributed CDS for Fixed-Power Scenario
Clustering Without Geometry Property
Clustering with Geometry Property
14.3.2 Localized Low-Weighted Structures for Adjustable-Power Scenario
Structure Based on RNG
Structure Based on LMST
Combining RNG
A Negative Result
14.3.3 Combining Clustering and Low Weight
14.3.4 Flooding-Based Methods
Selecting Forwarding Neighbors
Gossip and Probabilistic Schemes
Area-Based Decision
Neighbor-Coverage-Based Decision
14.4 Scheduling Active and Sleep Periods
14.5 Energy-Efficient Multicast
14.5.1 Fixed Transmission Power
14.5.2 Dynamically Adjustable Transmission Power
Multicast with Asymmetric Communication
Multicast with Symmetric Communication
14.6 Further Reading
14.7 Conclusion and Remarks
Problems
15 Routing with Selfish Terminals
15.1 Introduction
15.2 Preliminaries and Network Model
15.2.1 Preliminaries
15.2.2 Communication Model
15.2.3 Problem Statement
15.3 Truthful Payment Schemes for Multicast
15.3.1 Truthful Mechanism for Unicast
15.3.2 Least-Cost-Path Tree
Constructing a LCPT
VCG Mechanism on LCPT Is Not Strategy-Proof
Strategy-Proof Mechanism on LCPT
Computational Complexity
15.3.3 Node-Weighted Steiner Tree
Constructing the NST
VCG Mechanism on the NST Is Not Strategy-Proof
Strategy-Proof Mechanism Based on NST
Computational Complexity
15.4 Sharing Multicast Costs or Payments Among Receivers
15.4.1 Fair Payment-Sharing Scheme
15.4.2 Truthful Multicast Using Source-Based Tree
Construct Multicast Tree
Payment Scheme
Distributed-Payment Algorithm
15.4.3 Payment-Sharing Among Receivers
15.4.4 Distributed Computing of Payment-Sharing
15.4.5 Truthful Multicast Using a Share-Based Tree
15.4.6 Payment-Sharing Among Selfish Receivers
15.5 Existence of Truthful Payment Scheme
15.6 Further Reading
15.6.1 Reputation-Based Approaches
15.6.2 Algorithmic Mechanism Design
15.7 Conclusion and Remarks
Collusion
Truthful Distributed Implementation
Repeated Games
Nash Design
Central Authority
Dynamism and Mobility
Problems
16 Joint Routing, Channel Assignment,
16.1 Introduction
16.2 System Model and Assumptions
16.2.1 Network System Models
16.3 Problem Formulation for Cross-Layer Optimization
16.3.1 Maximize Fairness
16.3.2 Maximize Throughput
16.3.3 Link Scheduling
Dynamic Channel Assignment
Polynomial-Time Schedulable Flows
16.3.4 Integrated Cross-Layer Mixed IP
16.4 Efficient Link, Channel Scheduling
16.4.1 Polynomial-Time Scheduling Method
RTS/CTS
fPrIM
TxIM
PrIM
16.4.2 Correctness and Performance Guarantee
The Proof of Theorem 16.1
16.4.3 Improvement and Implementations
16.5 Further Reading
16.6 Conclusion
Problems
Part V: Other Issues
17 Localization and Location Tracking
17.1 Introduction
17.2 Available Information
17.2.1 Time of Arrival (ToA)
17.2.2 Time Difference of Arrival (TDoA)
17.2.3 Angle of Arrival (AoA)
17.2.4 Signal Strength
17.3 Computational Complexity of Sensor Network Localization
17.3.1 Complexity Results with Distance Information
17.3.2 Complexity Results with Other Information
17.4 Progressive Localization Methods
17.4.1 Trilateration
17.4.2 Multilateration
17.4.3 Sweep and Linear-Programming-Based Techniques
17.4.4 Distributed Localization Using Noisy Data
17.5 Network-Wide Localization Methods
17.5.1 Algorithm
17.5.2 Distance to Anchors
Sum-Dist
DV-Hop
Euclidean
Node Position
17.6 Target Tracking and Classification
17.6.1 Pattern Matching Using Database
17.6.2 Network-Based Tracking
17.6.3 Collaborative Signal Processing
17.6.4 Target Tracking Using Space–Time Cells
Using Space–Time Cells
Single-Target Tracking
Multiple-Targets Tracking
Target Classification
17.6.5 Target Tracking Based on Cooperative Binary Detection
System Model
Algorithm
Data Aggregation
17.6.6 Distributed Prediction Tracking (DPT)
DPT Algorithm
Sensor-Selection Algorithm
Failure Recovery
17.7 Experimental Location and Tracking Systems
17.7.1 Active Badge and Bat
17.7.2 Cricket
17.7.3 RADAR
17.8 Conclusion and Remarks
Problems
18 Performance Limitations of Random
18.1 Introduction
18.2 Capacity of Unicast for an Arbitrary Network
18.3 Capacity of Unicast for Randomly Deployed Networks
18.4 Capacity of Broadcast for an Arbitrary Network
18.5 Capacity of Broadcast for Randomly Deployed Networks
18.6 Further Reading
18.7 Conclusion and Remarks
Problems
19 Security of Wireless Ad Hoc Networks
19.1 Introduction
19.2 Cryptography Fundamentals
19.2.1 Conventional Encryption Methods
Block Ciphers and Stream Ciphers
Data-Encryption Standard
Advanced Encryption System (AES)
19.2.2 Public-Key-Encryption Methods
RSA Cryptosystem
ElGamal Cryptosystem
19.2.3 Digital-Signature Methods
19.2.4 Key-Agreement and Key-Distribution Protocols
19.3 Key-Predistribution Protocols
19.4 Secure Routing Protocols
19.4.1 Secure Routing for Sensor Networks
19.4.2 Stochastic Routing Protocols
19.5 Further Reading
19.6 Conclusion and Remarks
Problems
Bibliography
Abbreviations
Organizations
Index
CUUS080-FM
CUFX279/Li
978 0 521 86523 4
April 25, 2008
11:56
This page intentionally left blank
ii
CUUS080-FM
CUFX279/Li
978 0 521 86523 4
April 25, 2008
11:56
Wireless Ad Hoc and Sensor Networks
Wireless Ad Hoc and Sensor Networks describes the theory of ad hoc networks. It also
demonstrates techniques for designing efficient algorithms and systematically analyzing
their performance.
Li develops the fundamental understanding required to tackle problems in these
networks by first reviewing relevant protocols, then formulating problems mathemat-
ically, and solving them algorithmically. Wireless MAC protocols, including various
IEEE 802.11 protocols, 802.16, Bluetooth, and protocols for wireless sensor networks
are treated in detail. Channel assignment for maximizing network capacity is covered;
topology control methods are explored at length; and routing protocols for unicast,
broadcast, and multicast are described and evaluated. Cross-layer optimization is also
considered.
The result is a detailed account of the various algorithmic, graph-theoretical, computa-
tional-geometric, and probabilistic approaches to attack problems faced in these net-
works, delivering an understanding that will allow readers to develop practical solutions
for themselves. This title is an invaluable resource for graduate students and researchers
in electrical engineering and computer science departments, as well as for practitioners
in the communications industry.
XiangYang Li is currently an associate professor of computer science at the Illinois
Institute of Technology. He also holds a visiting professorship or adjunct-professorship
at TianJing University, WuHan University, and NanJing University, in China. He was
awarded his Ph.D. in 2001 from the Department of Computer Science at the University
of Illinois at Urbana-Champaign. A leading researcher in the field of wireless networks,
he has made important contributions in the areas of network topology and routing.
His current research interests include cooperation, energy efficiency, and distributed
algorithms for wireless ad hoc and sensor networks.
i
CUUS080-FM
CUFX279/Li
978 0 521 86523 4
April 25, 2008
11:56
ii
CUUS080-FM
CUFX279/Li
978 0 521 86523 4
April 25, 2008
11:56
Wireless Ad Hoc and
Sensor Networks
Theory and Applications
XIANGYANG LI
Illinois Institute of Technology
iii
CAMBRIDGE UNIVERSITY PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
Information on this title: www.cambridge.org/9780521865234
© Cambridge University Press 2008
This publication is in copyright. Subject to statutory exception and to the provision of
relevant collective licensing agreements, no reproduction of any part may take place
without the written permission of Cambridge University Press.
First published in print format
2008
ISBN-13 978-0-511-42325-3
eBook (EBL)
ISBN-13 978-0-521-86523-4
hardback
Cambridge University Press has no responsibility for the persistence or accuracy of urls
for external or third-party internet websites referred to in this publication, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.
CUUS080-FM
CUFX279/Li
978 0 521 86523 4
April 25, 2008
11:56
To my wife, Min
my daughter, Sophia
my son, Kevin
and my families
v
CUUS080-FM
CUFX279/Li
978 0 521 86523 4
April 25, 2008
11:56
vi
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
