Topology Control in Wireless Ad Hoc and Sensor Networks

curry0732

Topology Control in Wireless Ad Hoc and Sensor Networks

nikka

good good  

nikka

Contents
About the Author xiii
Preface xv
Acknowledgments xix
List of Abbreviations xxi
List of Figures xxiii
List of Tables xxvii
I Introduction 1
1 Ad Hoc and Sensor Networks 3
1.1 The Future ofWireless Communication . . . . . . . . . . . . . . . . . . . 3
1.1.1 Ad hoc networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Wireless sensor networks . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Ad hoc networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Wireless sensor networks . . . . . . . . . . . . . . . . . . . . . . 9
2 Modeling Ad Hoc Networks 13
2.1 TheWireless Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 The free space propagation model . . . . . . . . . . . . . . . . . . 14
2.1.2 The two-ray ground model . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3 The log-distance path model . . . . . . . . . . . . . . . . . . . . . 15
2.1.4 Large-scale and small-scale variations . . . . . . . . . . . . . . . 16
2.2 The Communication Graph . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Modeling Energy Consumption . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Ad hoc networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.2 Sensor networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Mobility Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
viii CONTENTS
3 Topology Control 27
3.1 Motivations for Topology Control . . . . . . . . . . . . . . . . . . . . . . 27
3.1.1 Topology control and energy conservation . . . . . . . . . . . . . 27
3.1.2 Topology control and network capacity . . . . . . . . . . . . . . . 28
3.2 A Definition of Topology Control . . . . . . . . . . . . . . . . . . . . . . 30
3.3 A Taxonomy of Topology Control . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Topology Control in the Protocol Stack . . . . . . . . . . . . . . . . . . . 33
3.4.1 Topology control and routing . . . . . . . . . . . . . . . . . . . . 33
3.4.2 Topology control and MAC . . . . . . . . . . . . . . . . . . . . . 34
II The Critical Transmitting Range 37
4 The CTR for Connectivity: Stationary Networks 39
4.1 The CTR in Dense Networks . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2 The CTR in Sparse Networks . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 The CTR with Different Deployment Region and Node Distribution . . . 49
4.4 Irregular Radio Coverage Area . . . . . . . . . . . . . . . . . . . . . . . . 50
5 The CTR for Connectivity: Mobile Networks 53
5.1 The CTR in RWPMobile Networks . . . . . . . . . . . . . . . . . . . . . 55
5.2 The CTR with Bounded, Obstacle-free Mobility . . . . . . . . . . . . . . 60
6 Other Characterizations of the CTR 63
6.1 The CTR for k-connectivity . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2 The CTR for Connectivity with Bernoulli Nodes . . . . . . . . . . . . . . 65
6.3 The Critical Coverage Range . . . . . . . . . . . . . . . . . . . . . . . . . 68
III Topology Optimization Problems 71
7 The Range Assignment Problem 73
7.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.2 The RA Problem in One-dimensional Networks . . . . . . . . . . . . . . 74
7.3 The RA Problem in Two- and Three-dimensional Networks . . . . . . . . 76
7.4 The Symmetric Versions of the Problem . . . . . . . . . . . . . . . . . . 78
7.4.1 The SRA problem in one-dimensional networks . . . . . . . . . . 79
7.4.2 The SRA problem in two- and three-dimensional networks . . . . 80
7.4.3 Approximation algorithms for WSRA . . . . . . . . . . . . . . . . 85
7.5 The Energy Cost of the Optimal Range Assignment . . . . . . . . . . . . 85
8 Energy-efficient Communication Topologies 87
8.1 Energy-efficient Unicast . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.2 Energy-efficient Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . . 92
CONTENTS ix
IV Distributed Topology Control 95
9 Distributed Topology Control: Design Guidelines 97
9.1 Ideal Features of a Topology Control Protocol . . . . . . . . . . . . . . . 97
9.2 The Quality of Information . . . . . . . . . . . . . . . . . . . . . . . . . . 99
9.3 Logical and Physical Node Degrees . . . . . . . . . . . . . . . . . . . . . 99
10 Location-based Topology Control 103
10.1 The R&M Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
10.1.1 The power consumption model . . . . . . . . . . . . . . . . . . . 104
10.1.2 Relay region and enclosure graph . . . . . . . . . . . . . . . . . . 105
10.1.3 Protocol description . . . . . . . . . . . . . . . . . . . . . . . . . 107
10.1.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
10.2 The LMST Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
10.2.1 Protocol description . . . . . . . . . . . . . . . . . . . . . . . . . 110
10.2.2 Protocol analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.2.3 The FLSSk protocol . . . . . . . . . . . . . . . . . . . . . . . . . 114
11 Direction-based Topology Control 115
11.1 The CBTC Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
11.1.1 The basic CBTC protocol . . . . . . . . . . . . . . . . . . . . . . 116
11.1.2 Dealing with asymmetric links . . . . . . . . . . . . . . . . . . . 119
11.1.3 Protocol analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
11.1.4 Removing energy-inefficient links . . . . . . . . . . . . . . . . . . 121
11.1.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
11.1.6 CBTC variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.2 The DistRNG Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
12 Neighbor-based Topology Control 127
12.1 The Number of Neighbors for Connectivity . . . . . . . . . . . . . . . . . 127
12.2 The KNeigh Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
12.2.1 Protocol description . . . . . . . . . . . . . . . . . . . . . . . . . 135
12.2.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
12.3 The XTC Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
12.3.1 Protocol description . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.3.2 Protocol analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
13 Dealing with Node Mobility 143
13.1 TC Design Guidelines with Mobility . . . . . . . . . . . . . . . . . . . . 144
13.2 TC inMobile Networks: an Example . . . . . . . . . . . . . . . . . . . . 147
13.3 The Effect of Mobility on the CNN . . . . . . . . . . . . . . . . . . . . . 152
13.4 Distributed TC in Mobile Networks: Existing Solutions . . . . . . . . . . 153
13.4.1 The LINT protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 154
13.4.2 The mobile version of CBTC . . . . . . . . . . . . . . . . . . . . 155
x CONTENTS
V Toward an Implementation of Topology Control 159
14 Level-based Topology Control 161
14.1 Level-based TC:Motivations . . . . . . . . . . . . . . . . . . . . . . . . . 162
14.2 The COMPOW Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
14.2.1 The optimal common power level . . . . . . . . . . . . . . . . . . 163
14.2.2 Protocol description . . . . . . . . . . . . . . . . . . . . . . . . . 166
14.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
14.3 The CLUSTERPOW Protocol . . . . . . . . . . . . . . . . . . . . . . . . 169
14.3.1 Protocol description and properties . . . . . . . . . . . . . . . . . 170
14.3.2 Implementing CLUSTERPOW . . . . . . . . . . . . . . . . . . . 173
14.3.3 The tunneled version of CLUSTERPOW . . . . . . . . . . . . . . 174
14.4 The KNeighLev Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 176
14.4.1 Protocol description and properties . . . . . . . . . . . . . . . . . 176
14.4.2 Optimizations: the KNeighLevU protocol . . . . . . . . . . . . . 180
14.4.3 KNeighLev versus KNeighLevU . . . . . . . . . . . . . . . . . 182
14.4.4 Setting the value of k . . . . . . . . . . . . . . . . . . . . . . . . 183
14.5 Comparing CLUSTERPOW and KNeighLev . . . . . . . . . . . . . . . . 184
15 Open Issues 189
15.1 TC for Interference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
15.2 More-realisticModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
15.2.1 More-realistic radio channel models . . . . . . . . . . . . . . . . . 193
15.2.2 More-realistic energy models . . . . . . . . . . . . . . . . . . . . 194
15.3 Mobility and Topology Control . . . . . . . . . . . . . . . . . . . . . . . 196
15.4 Considering MultiHop Data Traffic . . . . . . . . . . . . . . . . . . . . . 196
15.5 Implementation of TC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
VI Case Study and Appendices 201
16 Case Study: TC and Cooperative Routing in Ad Hoc Networks 203
16.1 Cooperation in Ad Hoc Networks . . . . . . . . . . . . . . . . . . . . . . 203
16.2 Reference Application Scenario . . . . . . . . . . . . . . . . . . . . . . . 205
16.3 Modeling Routing as a Game . . . . . . . . . . . . . . . . . . . . . . . . 207
16.4 A Practical Interpretation of Truthfulness . . . . . . . . . . . . . . . . . . 209
16.5 Truthful Routing without TC . . . . . . . . . . . . . . . . . . . . . . . . . 210
16.6 Truthful Routing with TC . . . . . . . . . . . . . . . . . . . . . . . . . . 211
16.6.1 The COMMIT routing protocol . . . . . . . . . . . . . . . . . . . 212
16.6.2 The COMMIT pricing scheme . . . . . . . . . . . . . . . . . . . . 213
16.6.3 Protocol analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
16.6.4 Interplay between TC and COMMIT routing . . . . . . . . . . . . 219
16.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
A Elements of Graph Theory 225
A.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
A.2 Proximity Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
CONTENTS xi
B Elements of Applied Probability 233
B.1 Basic Notions of Probability Theory . . . . . . . . . . . . . . . . . . . . . 233
B.2 Geometric Random Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 236
B.3 Occupancy Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
B.4 Continuum Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
References 241
Index 249

nikka

Save me 400 RMB

nikka

wonderful
Pls more books about ad hoc

zzz275

good.

zlongs1

非常感谢！

littleboyyz

thank for sharing!