Topology Control in Wireless Ad Hoc and Sensor Networks

curry0732 · 发表于 2006-11-20 16:36:55

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？注册

x

Topology Control in Wireless Ad Hoc and Sensor Networks

nikka · 发表于 2007-2-15 14:09:51

good good

nikka · 发表于 2007-2-15 14:11:16

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