Sensor and Ad-Hoc Networks (eBook)

Preface 6
Acknowledgement 8
Contents 9
Contributors 11
1 Establishing New Research Initiatives for Theoretical and Algorithmic Aspects of Sensor and Ad Hoc Networks 14
1.1 Introduction 14
1.2 Challenges for Sensor and Ad Hoc Networks 16
1.2.1 Interoperability 16
1.2.2 Network Interoperability 17
1.2.3 Middleware Interoperability 17
1.2.3.1 Object-Oriented Middleware 17
1.2.3.2 Service-Oriented Middleware 18
1.2.4 Adaptability 18
1.2.5 Scalability 21
1.2.6 Reliability 22
1.2.7 Energy Efficiency 23
1.2.8 Security 24
1.2.9 Testbeds and Benchmarks 26
1.3 General Recommendations for Future Research 26
1.4 Conclusion 28
2 Random Graph Models and the Limits of Scalability in Ad Hoc and Sensor Networks 32
2.1 Introduction 32
2.1.1 The Scalability Paradox 32
2.1.2 Some Fundamental Results 33
2.1.3 Escapes from the Vanishing Throughput Effect 34
2.2 Why Does the Throughput Vanish? 35
2.3 Previous Results on Connectivity 37
2.4 A Common Generalization of Models 39
2.4.1 Motivation 39
2.4.2 The Random Vertex Model (RVM) 40
2.4.3 Examples 41
2.5 Analysis 43
2.6 On Sufficiency 50
2.7 Discussion 50
2.7.1 Node Degrees vs Asymptotic Connectivity 50
2.7.2 Other Parameters vs the Limits of Scalability 51
2.8 Conclusion 52
3 Analysis of Effective Connectivity in Mobile Wireless Communications 55
3.1 Introduction 55
3.2 Effective Node Coverage 56
3.3 Effective Connectivity Model 57
3.3.1 Region A 58
3.3.2 Region B 58
3.3.3 Region C 59
3.3.4 Region D 60
3.3.5 Region E 60
3.3.5.1 Subcase E1 61
3.3.5.2 Subcase E2 62
3.3.5.3 Subcase E3 63
3.3.5.4 Subcase E4 64
3.4 Random Walk Analytical Model 65
3.4.1 Region A 66
3.4.2 Region B 67
3.4.3 Region C 67
3.4.4 Region D 68
3.4.5 Region E 69
3.4.5.1 Subcase E1 69
3.4.5.2 Subcase E2 69
3.4.5.3 Subcase E3 71
3.4.5.4 Subcase E4 73
3.5 Random Waypoint Analytical Model 75
3.5.1 Region A 76
3.5.2 Region B 76
3.5.3 Region C 77
3.6 Analysis 78
3.6.1 Random Walk Analytical vs Simulated 78
3.6.2 Random Waypoint Analytical vs Simulated 80
3.7 Conclusion 82
4 Some Detectability Issues in Sensor Networks 84
4.1 Introduction 84
4.2 Related Work 86
4.3 Detectability -- Theory and Practices 87
4.3.1 Randomly Deployed Fixed Sensors 88
4.3.1.1 Straight Moving Intruders 88
4.3.2 Mobile Sensors 91
4.3.2.1 Arranged Moving Sensors and Straight Moving Intruders 91
4.3.2.2 Randomly Moving Sensors and Straight Moving Intruders 95
4.4 Various Factors 95
4.4.1 Vertical Intruder, Uniform Sensor Deployment 96
4.4.2 Vertical Intruder, Random Sensor Deployment 99
4.4.3 Random Intruder, Uniform Sensor Deployment 100
4.4.4 Random Intruder, Random Sensor Deployment 102
4.5 Effectiveness of Sensor Deployment and Movement 103
4.5.1 Static Sensors 103
4.5.2 Randomly Moving Sensors 103
4.5.3 Random Straight-Line Moving Sensors 104
4.5.4 Sine Wave Moving Sensors 105
4.6 Concluding Remarks and Discussions 108
5 Comparative Methods of Channel Assignment in Multivariate Wireless Networks 111
5.1 Introduction 111
5.2 Problem Formulation 113
5.2.1 Network System Models 113
5.2.2 Problem Formulation 114
5.3 Related Work 117
5.4 Transition Phenomena 119
5.5 Our Approaches 121
5.5.1 Complexity Result 121
5.5.2 Backbone Based Approach 122
5.5.3 Spanning Tree Based Approach (STBA) 125
5.5.4 Assign Channels 126
5.6 Performance Evaluation 126
5.7 Conclusion 129
6 Heterogeneous Wireless Networks: QoS-Aware Integration Architecture 132
6.1 Introduction 132
6.2 Networking Architecture and Problem Description 133
6.2.1 Problem Description 134
6.2.2 Basic Architecture 136
6.2.3 Network Model 136
6.3 Proposed Approach 139
6.3.1 Downlink Rate Adjustment of an Existing Call 139
6.3.1.1 DL Rate Adjustment without Changing Existing Traffic 139
6.3.1.2 Downlink Rate Adjustment by Changing Existing Traffic 139
6.3.2 New Call Request 142
6.3.2.1 Proxy Cellular Connection Based on DL Rate 142
6.3.2.2 Proxy Cellular Connection Based on Call Elapsed Time 143
6.3.2.3 Proxy Cellular Connection Randomly 143
6.3.2.4 Free as Much Cellular Bandwidth as Possible (Greedy Method) 143
6.4 Performance Evaluation 144
6.4.1 Simulation Environment 144
6.4.2 Performance Results 146
6.4.2.1 User and Integrated System's Throughput 147
6.4.2.2 Concurrent and Average Number of Users 148
6.4.2.3 Number of Accepted/Dropped/Blocked Calls 149
6.4.2.4 Available NodeB Bandwidth 149
6.4.2.5 Impact of Shuffling on System Performance Metrics 149
6.4.2.6 Impact of AP Selection Methods on System Performance Metrics 151
6.4.2.7 Impact of MKAR Simplification Method on System Performance Metrics 152
6.4.2.8 Rate Adjustment Analysis 152
6.5 Literature Review 153
6.6 Conclusion 154
7 Distributed Energy-Aware Topology Control Algorithm for Wireless Sensor Networks 156
7.1 Introduction 156
7.2 Network Model and Preliminaries 156
7.2.1 Network Model 158
7.2.2 Election Factor 158
7.2.3 Energy Life of Node 158
7.2.4 Energy Model for Communications 159
7.3 Energy-Aware Topology Control Algorithm 159
7.3.1 EAMCDS Construction 159
7.3.2 Local Delaunay Triangulation Construction 162
7.3.3 Topology Reconstruction 162
7.4 Simulation Results and Analysis 162
7.4.1 Performance Metrics 163
7.4.2 Size of CDS 164
7.4.3 Lifetime of Network 166
7.5 Conclusion 168
8 MFACE: A Multicast Backbone-Assisted Face Traversal Algorithm for Arbitrary Planar Ad Hoc and Sensor Network Topologies 170
8.1 Introduction 170
8.2 Preliminaries 172
8.3 Related Work 174
8.3.1 Face Traversal in Unicast Communication 174
8.3.2 Face Traversal in Multicast Communication 175
8.4 A Generic Multicast Face Algorithm 177
8.4.1 Intersection with the Starting Edge st 179
8.4.2 Intersection with Any Other Edge of the Backbone 179
8.5 Correctness of MFACE 181
8.6 The Performance of MFACE and FACE 184
8.7 Conclusion and Open Research Topics 186
9 Service-Driven Query Routing in Sensor-Actuator Networks 190
9.1 Introduction 190
9.2 Routing Protocols in SANETs 192
9.2.1 Data-Centric Routing 193
9.2.2 Hierarchical Routing 193
9.2.3 Location-Based Routing 194
9.2.4 Actuator-Aware Routing 194
9.3 SDRP: A Service-Driven Routing Protocol for SANETs 195
9.3.1 Path Learning 195
9.3.2 Query Routing 196
9.4 Implementation 196
9.5 Evaluation 197
9.5.1 Energy Consumption and Scalability 197
9.5.1.1 Scalability with Regard to the Number of Nodes 197
9.5.1.2 Scalability with Regard to the Number of Queries 199
9.5.2 TinySOA vs. TinyDB 200
9.5.2.1 Energy Consumption 200
9.5.2.2 Response Time 202
9.5.2.3 AdHoc Network Deployment 202
9.6 Services in Current SANETs 203
9.6.1 Middleware Services 203
9.6.2 In-Network Services 206
9.6.3 Cross-Layer Services 206
9.7 TinySOA vs. Other Existing Service-Oriented Systems 207
9.8 Conclusion 208
10 Multiscale Anchor-Free Distributed Positioning in Sensor Networks 211
10.1 Introduction 211
10.2 Preliminaries 213
10.3 Hardness Result 213
10.4 Hierarchical Localization 216
10.4.1 Distributed Algorithm 220
10.5 Implementation and Simulation Results 222
10.6 Conclusion and Future Work 226
11 Evaluation of Time Synchronization over Mobile Ad hoc Networks 229
11.1 Introduction 229
11.2 Related Work 230
11.3 Problem Formulation and Analysis 231
11.3.1 Assumptions 231
11.3.2 Comparison of Time Convergence 233
11.3.2.1 Local Time Synchronization (LS) Scheme 233
11.3.2.2 Global Time Synchronization (GS) Scheme 234
11.3.3 Comparison with Reference to Mobility 236
11.3.3.1 Mobility and LS Scheme 236
11.3.3.2 Mobility and GS Scheme 237
11.3.4 In Terms of Stochastic Time Delay 238
11.4 Theoretical Results 238
11.5 Conclusion and Future Work 240
11.5 Appendix I 240
11.5 Appendix II 241
12 Universal Modular Framework for Sensor Networks 244
12.1 Introduction 244
12.2 Related Work 245
12.3 Future Sensor Networks 246
12.3.1 Vision of Future Networks 246
12.3.2 Node Classification 247
12.4 Modular Approach 247
12.5 Challenges When Designing Modular Protocols 248
12.6 Universal Modular Framework 249
12.6.1 Cross-Layer Data Repository 249
12.6.2 Modular Hetorogeneous Sensornetwork Architecture (Mohesa) 252
12.6.2.1 Functional Modules 253
12.6.2.2 Regulating Modules 253
12.6.3 Application Layer 255
12.6.4 Physical Layer 255
12.7 Coping with Interdependencies Between Modules 255
12.8 Future Work 257
12.9 Conclusion 258
13 Application and Evaluation of Hierarchical Agglomerative Clustering in Wireless Sensor Networks 261
13.1 Introduction 261
13.2 HAC Concept Introduction 263
13.2.1 Input Data Set 263
13.2.2 Computation of Resemblance Coefficients 263
13.2.3 Execution of the HAC Method 265
13.3 Cluster Generation for WSNs 266
13.3.1 Application of HAC with Quantitative Data 266
13.3.2 Application of HAC with Qualitative Data 268
13.3.3 Cluster Maintenance 270
13.4 Distributed HAC (DHAC) Algorithm 270
13.4.1 DHAC Using Quantitative Data 271
13.4.2 DHAC Using Qualitative Connectivity Data 275
13.5 Evaluation of DHAC 276
13.5.1 Evaluation of Clustering Methods and Parameters 277
13.6 Conclusions and Future Work 281
14 A Fault-Tolerant Scheme for Detection of DDoS Attack Patterns in Cluster-Based Wireless Sensor Networks 283
14.1 Introduction 283
14.2 Background 285
14.2.1 Related Work 285
14.2.2 The Graph Neuron 286
14.2.3 Notations 287
14.3 Attack Model 287
14.4 The Detection Scheme 289
14.4.1 Assumptions 289
14.4.2 Optimal Cluster Size 290
14.4.3 The Scheme 292
14.5 Evaluation 295
14.5.1 Experimental Setup 296
14.5.2 Simulation Parameters 296
14.5.3 Analysis 296
14.5.3.1 Detection Rate vs. Node Loss Ratio 297
14.5.3.2 Scheme Convergence Delay 300
14.5.3.3 Energy Decay Rate 300
14.6 Conclusions 301
15 Forming Energy-Efficient Bluetooth Scatternets for Sensor Networks 303
15.1 Introduction 303
15.2 Background and Related Work 304
15.3 Model and Problem Statement 306
15.4 Algorithm 307
15.5 Routing 310
15.6 Simulation Results 310
15.7 Conclusion 311
Index 313