Mao Connectivity of Communication Networks

1. Auflage 2017
ISBN: 978-3-319-52989-9
Verlag: Springer Nature Switzerland
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 435 Seiten

This book introduces a number of recent developments on connectivity of communication networks, ranging from connectivity of large static networks and connectivity of highly dynamic networks to connectivity of small to medium sized networks. This book also introduces some applications of connectivity studies in network optimization, in network localization, and in estimating distances between nodes. The book starts with an overview of the fundamental concepts, models, tools, and methodologies used for connectivity studies. The rest of the chapters are divided into four parts: connectivity of large static networks, connectivity of highly dynamic networks, connectivity of small to medium sized networks, and applications of connectivity studies.

Autoren/Hrsg.

Mao, Guoqiang

Inhaltsverzeichnis

1;Preface;5
2;Contents;8
3;1 Introduction;14
3.1;1.1 Connection Models;14
3.1.1;1.1.1 Erd?s–Rényi Connection Model;15
3.1.2;1.1.2 Unit Disk Connection Model;16
3.1.3;1.1.3 Log-Normal Connection Model;16
3.1.4;1.1.4 Random Connection Model;18
3.1.5;1.1.5 SINR Connection Model;19
3.2;1.2 Network Models;20
3.3;1.3 Graph Theoretic Tools for Connectivity Analysis;24
3.3.1;1.3.1 Continuum Percolation Theory;24
3.3.1.1;1.3.1.1 Coupling and Scaling Technique;27
3.3.2;1.3.2 Branching Process;29
3.3.3;1.3.3 Algebraic Graph Theory;32
3.4;1.4 Notes and Further Readings;35
4;Part I Connectivity of Large Static Networks;36
4.1;2 Large Network Models and Their Implications;37
4.1.1;2.1 Comparative Outline of Three Large Network Models;40
4.1.2;2.2 Estimating the Number of Isolated Nodes;43
4.1.2.1;2.2.1 Expected Number of Isolated Nodes in an Asymptotically Infinite Network;44
4.1.2.2;2.2.2 Impact of Boundary Effect on the Number of Isolated Nodes;53
4.1.2.3;2.2.3 The Number of Isolated Nodes in a Region A1r? of an Infinite Network with Node Density log?+bC;57
4.1.2.4;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
4.1.3;2.3 Vanishing of Finite Components with More Than One Nodes;62
4.1.3.1;An Analysis of the First Term in (2.3.8);71
4.1.3.2;An Analysis of the Second Term in (2.3.8);79
4.1.4;2.4 Notes and Further Readings;83
4.2;3 Connectivity of Large Wireless Networks: Sufficient and Necessary Conditions;85
4.2.1;3.1 Connectivity of Large Wireless Networks: The Unit Disk Connection Model;87
4.2.2;3.2 Connectivity of Large Networks: The Random Connection Model;91
4.2.2.1;3.2.1 Necessary Condition for Almost Sure Connectivity;92
4.2.2.1.1;3.2.1.1 Distribution of the Number of Isolated Nodes on a Torus;92
4.2.2.1.2;3.2.1.2 An Evaluation of the b1 Term;96
4.2.2.1.3;3.2.1.3 An Evaluation of the b2 Term;96
4.2.2.1.4;3.2.1.4 An Evaluation of the b3 Term;99
4.2.2.1.5;3.2.1.5 Distribution of the Number of Isolated Nodes on a Square;104
4.2.2.2;3.2.2 Sufficient Condition for Almost Sure Connectivity;105
4.2.3;3.3 Special Cases of the Network Model and the Random Connection Model;112
4.2.4;3.4 Notes and Further Readings;113
4.3;4 Giant Component in Large Wireless Networks;115
4.3.1;4.1 Giant Component in One-Dimensional Networks;118
4.3.1.1;4.1.1 Giant Component in a Finite Network;118
4.3.1.2;4.1.2 Giant Component in Asymptotically Infinite Networks;123
4.3.1.2.1;4.1.2.1 When n(1-r)n?e-c as n??;123
4.3.1.2.2;4.1.2.2 When n(1-2r)n?0 and n(1-r)n?? as n??;128
4.3.1.2.3;4.1.2.3 When n(1-2r)n?e-c and n(1-r)n?? as n??;129
4.3.2;4.2 Securing a Giant Component with the Unit Disk Connection Model;130
4.3.3;4.3 Extension into More General Connection Models;134
4.3.4;4.4 Notes and Further Readings;135
4.4;5 Critical Density for Percolation;137
4.4.1;5.1 A Lower Bound for the Critical Density;139
4.4.1.1;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
4.4.2;5.2 An Upper Bound for the Critical Density;151
4.4.2.1;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
4.4.3;5.3 Notes and Further Reading;158
4.5;6 Phase Transitions in Large Networks;160
4.5.1;6.1 Phase Transition Width for Network with Different Orders of Connectivity;165
4.5.1.1;6.1.1 Case When d=2, 3;168
4.5.1.2;6.1.2 Case When d=1;173
4.5.2;6.2 A Discussion on Properties of the Phase TransitionWidth of a k-Connected Network;175
4.5.3;6.3 Simulation Studies of the Phase Transition Width;180
4.5.3.1;Computing the Phase Transition Width ?k(n,?);180
4.5.4;6.4 Notes and Further Readings;184
4.6;7 Connectivity of Large Wireless Networks in the Presence of Interference;186
4.6.1;7.1 Connections in Carrier Sense Multiple Access(CSMA) Networks;186
4.6.2;7.2 Sufficient Condition for Almost Surely Connected CSMA Networks;189
4.6.2.1;7.2.1 An Upper Bound on Interference and the Associated Transmission Range;190
4.6.2.2;7.2.2 A Sufficient Condition for Connectivity;195
4.6.3;7.3 Necessary Condition for Almost Surely Connected CSMA Networks;197
4.6.3.1;7.3.1 Construction of Scheduling Algorithm for CSMA Networks;198
4.6.3.2;7.3.2 Probability of Having No Isolated Node;200
4.6.4;7.4 Notes and Further Readings;208
5;Part II Connectivity of Highly Dynamic Networks;210
5.1;8 Connectivity of Dynamic Networks;211
5.1.1;8.1 Challenges and Opportunities in Dynamic Networks;211
5.1.2;8.2 Connectivity Matrix and Probabilistic Connectivity Matrix for Dynamic Networks;214
5.1.2.1;8.2.1 Connectivity Matrix of Deterministic Dynamic Networks;215
5.1.2.2;8.2.2 Probabilistic Connectivity Matrix of Probabilistic Dynamic Networks;218
5.1.3;8.3 Notes and Further Readings;220
5.2;9 Information Propagation in One-Dimensional Dynamic Networks;222
5.2.1;9.1 Information Propagation Process in VANETs with Single Traffic Stream;224
5.2.1.1;9.1.1 Catch-Up Process for a General Speed Distribution;226
5.2.1.2;9.1.2 Modeling the Movement of Single Vehicle;226
5.2.1.3;9.1.3 Modeling the Movement of the Head and Tail;226
5.2.1.3.1;9.1.3.1 Catch-Up Delay;228
5.2.1.3.2;9.1.3.2 Distribution of the Gaps lc;230
5.2.1.4;9.1.4 Catch-Up Process for a Gaussian Speed Distribution;230
5.2.1.4.1;9.1.4.1 Catch-Up Delay in a Basic Catch-Up Process;231
5.2.1.4.2;9.1.4.2 Catch-Up Delay with Overtaking Permitted;233
5.2.1.5;9.1.5 Analysis of the Forwarding Process;234
5.2.1.5.1;9.1.5.1 Cluster Length;235
5.2.1.5.2;9.1.5.2 Hop Count Statistics in a Cluster;238
5.2.1.6;9.1.6 Information Propagation Speed;239
5.2.1.7;9.1.7 Simulation Results;239
5.2.1.7.1;9.1.7.1 Catch-Up Process;239
5.2.1.7.2;9.1.7.2 Forwarding Process;241
5.2.1.7.3;9.1.7.3 Information Propagation Speed;241
5.2.2;9.2 Information Propagation Process in VANETs with Multiple Traffic Streams;245
5.2.2.1;9.2.1 Forwarding Process;247
5.2.2.2;9.2.2 Catch-Up Process;248
5.2.2.2.1;9.2.2.1 Modeling the Movement of Single Vehicle;248
5.2.2.2.2;9.2.2.2 The Distance Between a Pair of Vehicles;249
5.2.2.2.3;9.2.2.3 Pseudo Catch-Up Events;252
5.2.2.2.4;9.2.2.4 The Catch-Up Process Between H? and P?;256
5.2.2.2.5;9.2.2.5 Delay of a Catch-Up Process;257
5.2.2.3;9.2.3 Information Propagation Speed;259
5.2.2.4;9.2.4 Simplified Results Charactering the Information Propagation Process;259
5.2.2.4.1;9.2.4.1 Simplified Hop Count;260
5.2.2.4.2;9.2.4.2 Simplified Cluster Length;261
5.2.2.4.3;9.2.4.3 Simplified Catch-Up Delay;262
5.2.2.5;9.2.5 Simplified IPS;263
5.2.2.6;9.2.6 Simulation Results;264
5.2.3;9.3 Notes and Further Readings;268
5.3;10 Information Propagation in Two-Dimensional Dynamic Networks;271
5.3.1;10.1 Information Dissemination Scheme and Network Model;272
5.3.1.1;10.1.1 Network Model;272
5.3.1.2;10.1.2 Information Dissemination Scheme;274
5.3.2;10.2 Analytical Characterization of the Information Propagation Process;275
5.3.2.1;10.2.1 The Probability of Direct Connection;275
5.3.2.2;10.2.2 The Effective Node Degree;277
5.3.2.3;10.2.3 Percolation Probability;280
5.3.2.4;10.2.4 Expected Fraction of Informed Nodes;282
5.3.2.5;10.2.5 Energy and Bandwidth Efficiency;282
5.3.2.6;10.2.6 Information Dissemination Delay;284
5.3.2.7;10.2.7 Optimization of the Inter-Transmission Time Interval;286
5.3.3;10.3 Simulation Studies of the Information Propagation Process;288
5.3.3.1;10.3.1 Real Mobility Trace Simulation;293
5.3.4;10.4 Notes and Further Readings;295
6;Part III Connectivity of Small to Medium Sized Networks;296
6.1;11 Connectivity of One-Dimensional Small to Medium SizedNetworks;297
6.1.1;11.1 Probabilities of k-Hop Connection in One-Dimensional Ad Hoc Networks;298
6.1.2;11.2 Connectivity of One-Dimensional Infrastructure BasedNetworks;300
6.1.2.1;11.2.1 Characterization of Type-II Connectivity Probability;302
6.1.2.1.1;11.2.1.1 Exact Probability that a Sub-Interval Is Type-II Connectedfor rp=ro;303
6.1.2.1.2;11.2.1.2 Asymptotic Probability That a Sub-Interval Is Type-II Connected for rp=ro;306
6.1.2.2;11.2.2 Average Number of Clusters;308
6.1.2.3;11.2.3 The Optimal Distribution of Powerful Nodes;310
6.1.2.3.1;11.2.3.1 Minimizing the Average Number of Clusters;310
6.1.2.3.2;11.2.3.2 Maximizing the Asymptotic Type-II Connectivity Probability;311
6.1.2.4;11.2.4 Impact of Different Parameters on Connectivity;312
6.1.3;11.3 Notes and Further Readings;315
6.2;12 Connectivity of Two-Dimensional Small to Medium SizedNetworks;317
6.2.1;12.1 Probabilities of k-Hop Connection Under the Unit Disk Connection Model;318
6.2.1.1;12.1.1 Simulation Studies;321
6.2.2;12.2 Probabilities of k-Hop Connection Under the Random Connection Model;322
6.2.2.1;12.2.1 Simulation Studies;325
6.2.3;12.3 Probabilities of k-Hop Connection in Wireless Networks Subject to Fading;328
6.2.3.1;12.3.1 Per Hop Energy Consumption;330
6.2.3.2;12.3.2 Routing Algorithm;331
6.2.3.3;12.3.3 Analysis Assuming the Unit Disk Model;332
6.2.3.3.1;12.3.3.1 Spatial Dependence Problem;333
6.2.3.3.2;12.3.3.2 Distribution of the Remaining Distance;334
6.2.3.3.3;12.3.3.3 Hop Count Statistics;337
6.2.3.3.4;12.3.3.4 Results for Successful Transmissions;337
6.2.3.3.5;12.3.3.5 Results for Unsuccessful Transmissions;337
6.2.3.4;12.3.4 Impact of Spatial Dependence Problem;338
6.2.3.5;12.3.5 Analysis Assuming the Log-Normal-Nakagami Model;340
6.2.3.5.1;12.3.5.1 Random Split of a Poisson Point Process;340
6.2.3.5.2;12.3.5.2 Probability of Direct Connection;341
6.2.3.5.3;12.3.5.3 Distribution of the Remaining Distance;342
6.2.3.5.4;12.3.5.4 Hop Count Statistics;345
6.2.3.6;12.3.6 Simulation Studies;345
6.2.3.6.1;12.3.6.1 Hop Count Statistics;346
6.2.3.6.2;12.3.6.2 Effective Energy Consumption;348
6.2.3.6.3;12.3.6.3 Impact of Node Density and Path Loss Exponent on the Optimum Transmission Range;351
6.2.4;12.4 Notes and Further Readings;352
6.3;13 A New Measure of Wireless Network Connectivity;354
6.3.1;13.1 Motivation for a New Connectivity Measure;355
6.3.2;13.2 Probabilistic Connectivity Matrix and Its Properties;358
6.3.2.1;13.2.1 Computation of the Probabilistic Connectivity Matrix;361
6.3.2.2;13.2.2 Some Key Inequalities for Connection Probabilities;362
6.3.3;13.3 The Largest Eigenvalue of the Probabilistic Connectivity Matrix;366
6.3.3.1;13.3.1 Proof of Theorem 192;370
6.3.4;13.4 A Decentralized Algorithm for Finding the Largest Eigenvalue;371
6.3.4.1;13.4.1 A Basic Recursion;371
6.3.4.2;13.4.2 Properties of the Recursion;372
6.3.4.3;13.4.3 Local Detection of Convergence;374
6.3.4.4;13.4.4 The Flooding Algorithm;376
6.3.4.5;13.4.5 Practical Issues and Convergence Rates;378
6.3.4.6;13.4.6 Simulation Studies;378
6.3.4.7;13.4.7 Proof of Theorem 199;379
6.3.5;13.5 Notes and Further Readings;384
7;Part IV Applications of Connectivity Studies;386
7.1;14 Applications of Connectivity Studies;387
7.1.1;14.1 Access and Connectivity Properties of Vehicular Networks;388
7.1.1.1;14.1.1 System Model;389
7.1.1.2;14.1.2 Analysis of Access and Connectivity Probabilities;390
7.1.1.3;14.1.3 Performance Evaluation Under Specific Connection Models;394
7.1.1.3.1;14.1.3.1 Unit Disk Connection Model;395
7.1.1.3.2;14.1.3.2 Log-Normal Connection Model;400
7.1.1.4;14.1.4 Analytical and Simulation Results;401
7.1.1.4.1;14.1.4.1 Unit Disk Connection Model;401
7.1.1.4.2;14.1.4.2 Log-Normal Connection Model;404
7.1.2;14.2 Distance Estimation via Connectivity;406
7.1.2.1;14.2.1 The Connectivity-Based Distance Estimation Method;407
7.1.2.1.1;14.2.1.1 Estimating Distances Under the Unit Disk Connection Model;408
7.1.2.1.2;14.2.1.2 Extension Under the General Random Connection Model;409
7.1.2.1.3;14.2.1.3 Distance Estimation Under the Log-Normal Connection Model;410
7.1.2.1.4;14.2.1.4 Formulating S and f(d);411
7.1.2.2;14.2.2 Performance Analysis of the Distance Estimator;412
7.1.2.2.1;14.2.2.1 Impact of Imprecise Knowledge of Parameters ? and ?dB;412
7.1.2.2.2;14.2.2.2 Bias and Standard Deviation;413
7.1.2.2.3;14.2.2.3 Root Mean Square Error;416
7.1.2.3;14.2.3 Analysis Based on the CRLB;417
7.1.2.3.1;14.2.3.1 Influence of ?;418
7.1.2.3.2;14.2.3.2 Influence of d;419
7.1.2.3.3;14.2.3.3 Influences of r;419
7.1.2.4;14.2.4 Practical Implementation of the Distance Estimation Technique;421
7.1.3;14.3 Connectivity Based Localization;422
7.1.4;14.4 Notes and Further Readings;425
8;Appendix;427
8.1;Landau's Order Notation;427
8.2;Frequently Used Statistical Inequalities and Functions;427
8.2.1;Chebyshev's Inequality;427
8.2.2;Markov Inequality;428
8.2.3;Jensen Inequality;428
8.2.4;Fortuin–Kasteleyn–Ginibre (FKG) Inequality;428
8.2.5;Q-Function;428
8.2.6;Error Function;428
8.2.7;Lambert W Function;429
9;Bibliography;430