Connectivity of Communication Networks (eBook)

Dr Guoqiang Mao is a Professor of Wireless Networking at the School of Computing and Communications, University of Technology Sydney. He is also a Senior Principal Researcher at Data61, CSIRO, Australia. He received his PhD from Edith Cowan University, Australia in Telecommunication Networks. He has published two books, three scholarly book chapters, 70 journal papers, 100 conference papers in mostly IEEE journals (or journals of equal status) and conferences, which have been cited over 4,000 times. He is co-chair of IEEE Intelligent Transport Systems Society Technical Committee on Communication Networks (2013-now), editor for IEEE Transactions on Wireless Communications (2014-now), Editor for IEEE Transactions on Vehicular Technology (2010-now), and received Top Editor award for “outstanding contributions to IEEE Transactions on Vehicular Technology” in 2011, 2014 and 2015, among other professional activities.

Preface 5
Contents 8
1 Introduction 14
1.1 Connection Models 14
1.1.1 Erd?s–Rényi Connection Model 15
1.1.2 Unit Disk Connection Model 16
1.1.3 Log-Normal Connection Model 16
1.1.4 Random Connection Model 18
1.1.5 SINR Connection Model 19
1.2 Network Models 20
1.3 Graph Theoretic Tools for Connectivity Analysis 24
1.3.1 Continuum Percolation Theory 24
1.3.1.1 Coupling and Scaling Technique 27
1.3.2 Branching Process 29
1.3.3 Algebraic Graph Theory 32
1.4 Notes and Further Readings 35
Part I Connectivity of Large Static Networks 36
2 Large Network Models and Their Implications 37
2.1 Comparative Outline of Three Large Network Models 40
2.2 Estimating the Number of Isolated Nodes 43
2.2.1 Expected Number of Isolated Nodes in an Asymptotically Infinite Network 44
2.2.2 Impact of Boundary Effect on the Number of Isolated Nodes 53
2.2.3 The Number of Isolated Nodes in a Region A1r? of an Infinite Network with Node Density log?+bC 57
2.2.4 A Comparison of the Expected Number of Isolated Nodes in G(Xlog?+bC,g,A1r?) and in Its Counterpart in an Infinite Network 58
2.3 Vanishing of Finite Components with More Than One Nodes 62
An Analysis of the First Term in (2.3.8) 71
An Analysis of the Second Term in (2.3.8) 79
2.4 Notes and Further Readings 83
3 Connectivity of Large Wireless Networks: Sufficient and Necessary Conditions 85
3.1 Connectivity of Large Wireless Networks: The Unit Disk Connection Model 87
3.2 Connectivity of Large Networks: The Random Connection Model 91
3.2.1 Necessary Condition for Almost Sure Connectivity 92
3.2.1.1 Distribution of the Number of Isolated Nodes on a Torus 92
3.2.1.2 An Evaluation of the b1 Term 96
3.2.1.3 An Evaluation of the b2 Term 96
3.2.1.4 An Evaluation of the b3 Term 99
3.2.1.5 Distribution of the Number of Isolated Nodes on a Square 104
3.2.2 Sufficient Condition for Almost Sure Connectivity 105
3.3 Special Cases of the Network Model and the Random Connection Model 112
3.4 Notes and Further Readings 113
4 Giant Component in Large Wireless Networks 115
4.1 Giant Component in One-Dimensional Networks 118
4.1.1 Giant Component in a Finite Network 118
4.1.2 Giant Component in Asymptotically Infinite Networks 123
4.1.2.1 When n(1-r)n?e-c as n?? 123
4.1.2.2 When n(1-2r)n?0 and n(1-r)n?? as n?? 128
4.1.2.3 When n(1-2r)n?e-c and n(1-r)n?? as n?? 129
4.2 Securing a Giant Component with the Unit Disk Connection Model 130
4.3 Extension into More General Connection Models 134
4.4 Notes and Further Readings 135
5 Critical Density for Percolation 137
5.1 A Lower Bound for the Critical Density 139
5.1.1 Application of the Lower Bound on the Critical Density to the Unit Disk Connection Model and the Log-Normal Connection Model 148
5.2 An Upper Bound for the Critical Density 151
5.2.1 Application of the Upper Bound on the Critical Density to the Unit Disk Connection Model and the Log-Normal Connection Model 157
5.3 Notes and Further Reading 158
6 Phase Transitions in Large Networks 160
6.1 Phase Transition Width for Network with Different Orders of Connectivity 165
6.1.1 Case When d=2, 3 168
6.1.2 Case When d=1 173
6.2 A Discussion on Properties of the Phase TransitionWidth of a k-Connected Network 175
6.3 Simulation Studies of the Phase Transition Width 180
Computing the Phase Transition Width ?k(n,?) 180
6.4 Notes and Further Readings 184
7 Connectivity of Large Wireless Networks in the Presence of Interference 186
7.1 Connections in Carrier Sense Multiple Access(CSMA) Networks 186
7.2 Sufficient Condition for Almost Surely Connected CSMA Networks 189
7.2.1 An Upper Bound on Interference and the Associated Transmission Range 190
7.2.2 A Sufficient Condition for Connectivity 195
7.3 Necessary Condition for Almost Surely Connected CSMA Networks 197
7.3.1 Construction of Scheduling Algorithm for CSMA Networks 198
7.3.2 Probability of Having No Isolated Node 200
7.4 Notes and Further Readings 208
Part II Connectivity of Highly Dynamic Networks 210
8 Connectivity of Dynamic Networks 211
8.1 Challenges and Opportunities in Dynamic Networks 211
8.2 Connectivity Matrix and Probabilistic Connectivity Matrix for Dynamic Networks 214
8.2.1 Connectivity Matrix of Deterministic Dynamic Networks 215
8.2.2 Probabilistic Connectivity Matrix of Probabilistic Dynamic Networks 218
8.3 Notes and Further Readings 220
9 Information Propagation in One-Dimensional Dynamic Networks 222
9.1 Information Propagation Process in VANETs with Single Traffic Stream 224
9.1.1 Catch-Up Process for a General Speed Distribution 226
9.1.2 Modeling the Movement of Single Vehicle 226
9.1.3 Modeling the Movement of the Head and Tail 226
9.1.3.1 Catch-Up Delay 228
9.1.3.2 Distribution of the Gaps lc 230
9.1.4 Catch-Up Process for a Gaussian Speed Distribution 230
9.1.4.1 Catch-Up Delay in a Basic Catch-Up Process 231
9.1.4.2 Catch-Up Delay with Overtaking Permitted 233
9.1.5 Analysis of the Forwarding Process 234
9.1.5.1 Cluster Length 235
9.1.5.2 Hop Count Statistics in a Cluster 238
9.1.6 Information Propagation Speed 239
9.1.7 Simulation Results 239
9.1.7.1 Catch-Up Process 239
9.1.7.2 Forwarding Process 241
9.1.7.3 Information Propagation Speed 241
9.2 Information Propagation Process in VANETs with Multiple Traffic Streams 245
9.2.1 Forwarding Process 247
9.2.2 Catch-Up Process 248
9.2.2.1 Modeling the Movement of Single Vehicle 248
9.2.2.2 The Distance Between a Pair of Vehicles 249
9.2.2.3 Pseudo Catch-Up Events 252
9.2.2.4 The Catch-Up Process Between H? and P? 256
9.2.2.5 Delay of a Catch-Up Process 257
9.2.3 Information Propagation Speed 259
9.2.4 Simplified Results Charactering the Information Propagation Process 259
9.2.4.1 Simplified Hop Count 260
9.2.4.2 Simplified Cluster Length 261
9.2.4.3 Simplified Catch-Up Delay 262
9.2.5 Simplified IPS 263
9.2.6 Simulation Results 264
9.3 Notes and Further Readings 268
10 Information Propagation in Two-Dimensional Dynamic Networks 271
10.1 Information Dissemination Scheme and Network Model 272
10.1.1 Network Model 272
10.1.2 Information Dissemination Scheme 274
10.2 Analytical Characterization of the Information Propagation Process 275
10.2.1 The Probability of Direct Connection 275
10.2.2 The Effective Node Degree 277
10.2.3 Percolation Probability 280
10.2.4 Expected Fraction of Informed Nodes 282
10.2.5 Energy and Bandwidth Efficiency 282
10.2.6 Information Dissemination Delay 284
10.2.7 Optimization of the Inter-Transmission Time Interval 286
10.3 Simulation Studies of the Information Propagation Process 288
10.3.1 Real Mobility Trace Simulation 293
10.4 Notes and Further Readings 295
Part III Connectivity of Small to Medium Sized Networks 296
11 Connectivity of One-Dimensional Small to Medium SizedNetworks 297
11.1 Probabilities of k-Hop Connection in One-Dimensional Ad Hoc Networks 298
11.2 Connectivity of One-Dimensional Infrastructure BasedNetworks 300
11.2.1 Characterization of Type-II Connectivity Probability 302
11.2.1.1 Exact Probability that a Sub-Interval Is Type-II Connectedfor rp=ro 303
11.2.1.2 Asymptotic Probability That a Sub-Interval Is Type-II Connected for rp=ro 306
11.2.2 Average Number of Clusters 308
11.2.3 The Optimal Distribution of Powerful Nodes 310
11.2.3.1 Minimizing the Average Number of Clusters 310
11.2.3.2 Maximizing the Asymptotic Type-II Connectivity Probability 311
11.2.4 Impact of Different Parameters on Connectivity 312
11.3 Notes and Further Readings 315
12 Connectivity of Two-Dimensional Small to Medium SizedNetworks 317
12.1 Probabilities of k-Hop Connection Under the Unit Disk Connection Model 318
12.1.1 Simulation Studies 321
12.2 Probabilities of k-Hop Connection Under the Random Connection Model 322
12.2.1 Simulation Studies 325
12.3 Probabilities of k-Hop Connection in Wireless Networks Subject to Fading 328
12.3.1 Per Hop Energy Consumption 330
12.3.2 Routing Algorithm 331
12.3.3 Analysis Assuming the Unit Disk Model 332
12.3.3.1 Spatial Dependence Problem 333
12.3.3.2 Distribution of the Remaining Distance 334
12.3.3.3 Hop Count Statistics 337
12.3.3.4 Results for Successful Transmissions 337
12.3.3.5 Results for Unsuccessful Transmissions 337
12.3.4 Impact of Spatial Dependence Problem 338
12.3.5 Analysis Assuming the Log-Normal-Nakagami Model 340
12.3.5.1 Random Split of a Poisson Point Process 340
12.3.5.2 Probability of Direct Connection 341
12.3.5.3 Distribution of the Remaining Distance 342
12.3.5.4 Hop Count Statistics 345
12.3.6 Simulation Studies 345
12.3.6.1 Hop Count Statistics 346
12.3.6.2 Effective Energy Consumption 348
12.3.6.3 Impact of Node Density and Path Loss Exponent on the Optimum Transmission Range 351
12.4 Notes and Further Readings 352
13 A New Measure of Wireless Network Connectivity 354
13.1 Motivation for a New Connectivity Measure 355
13.2 Probabilistic Connectivity Matrix and Its Properties 358
13.2.1 Computation of the Probabilistic Connectivity Matrix 361
13.2.2 Some Key Inequalities for Connection Probabilities 362
13.3 The Largest Eigenvalue of the Probabilistic Connectivity Matrix 366
13.3.1 Proof of Theorem 192 370
13.4 A Decentralized Algorithm for Finding the Largest Eigenvalue 371
13.4.1 A Basic Recursion 371
13.4.2 Properties of the Recursion 372
13.4.3 Local Detection of Convergence 374
13.4.4 The Flooding Algorithm 376
13.4.5 Practical Issues and Convergence Rates 378
13.4.6 Simulation Studies 378
13.4.7 Proof of Theorem 199 379
13.5 Notes and Further Readings 384
Part IV Applications of Connectivity Studies 386
14 Applications of Connectivity Studies 387
14.1 Access and Connectivity Properties of Vehicular Networks 388
14.1.1 System Model 389
14.1.2 Analysis of Access and Connectivity Probabilities 390
14.1.3 Performance Evaluation Under Specific Connection Models 394
14.1.3.1 Unit Disk Connection Model 395
14.1.3.2 Log-Normal Connection Model 400
14.1.4 Analytical and Simulation Results 401
14.1.4.1 Unit Disk Connection Model 401
14.1.4.2 Log-Normal Connection Model 404
14.2 Distance Estimation via Connectivity 406
14.2.1 The Connectivity-Based Distance Estimation Method 407
14.2.1.1 Estimating Distances Under the Unit Disk Connection Model 408
14.2.1.2 Extension Under the General Random Connection Model 409
14.2.1.3 Distance Estimation Under the Log-Normal Connection Model 410
14.2.1.4 Formulating S and f(d) 411
14.2.2 Performance Analysis of the Distance Estimator 412
14.2.2.1 Impact of Imprecise Knowledge of Parameters ? and ?dB 412
14.2.2.2 Bias and Standard Deviation 413
14.2.2.3 Root Mean Square Error 416
14.2.3 Analysis Based on the CRLB 417
14.2.3.1 Influence of ? 418
14.2.3.2 Influence of d 419
14.2.3.3 Influences of r 419
14.2.4 Practical Implementation of the Distance Estimation Technique 421
14.3 Connectivity Based Localization 422
14.4 Notes and Further Readings 425
Appendix 427
Landau's Order Notation 427
Frequently Used Statistical Inequalities and Functions 427
Chebyshev's Inequality 427
Markov Inequality 428
Jensen Inequality 428
Fortuin–Kasteleyn–Ginibre (FKG) Inequality 428
Q-Function 428
Error Function 428
Lambert W Function 429
Bibliography 430