Self-Organization in Sensor and Actor Networks explores self-organization mechanisms and methodologies concerning the efficient coordination between intercommunicating autonomous systems.Self-organization is often referred to as the multitude of algorithms and methods that organise the global behaviour of a system based on inter-system communication. Studies of self-organization in natural systems first took off in the 1960s. In technology, such approaches have become a hot research topic over the last 4-5 years with emphasis upon management and control in communication networks, and especially in resource-constrained sensor and actor networks. In the area of ad hoc networks new solutions have been discovered that imitate the properties of self-organization. Some algorithms for on-demand communication and coordination, including data-centric networking, are well-known examples.Key features include:Detailed treatment of self-organization, mobile sensor and actor networks, coordination between autonomous systems, and bio-inspired networking.Overview of the basic methodologies for self-organization, a comparison to central and hierarchical control, and classification of algorithms and techniques in sensor and actor networks.Explanation of medium access control, ad hoc routing, data-centric networking, synchronization, and task allocation issues.Introduction to swarm intelligence, artificial immune system, molecular information exchange.Numerous examples and application scenarios to illustrate the theory.Self-Organization in Sensor and Actor Networks will prove essential reading for students of computer science and related fields; researchers working in the area of massively distributed systems, sensor networks, self-organization, and bio-inspired networking will also find this reference useful.
Author(s): Falko Dressler
Edition: 1
Year: 2008
Language: English
Pages: 386
Self-Organization in Sensor and Actor Networks......Page 5
Contents......Page 9
Foreword......Page 15
Preface......Page 17
About the Author......Page 21
List of Abbreviations......Page 23
I Self-Organization......Page 27
1 Introduction to Self-Organization......Page 29
1.1 Understanding self-organization......Page 30
1.2 Application scenarios for self-organization......Page 31
2 System Management and Control – A Historical Overview......Page 33
2.1 System architecture......Page 34
2.2.1 Centralized control......Page 36
2.2.2 Distributed systems......Page 37
2.2.3 Self-organizing systems......Page 40
3.1 Complex systems......Page 43
3.2 Self-organization and emergence......Page 45
3.3.2 Blueprints and templates......Page 48
3.4 Self-X capabilities......Page 49
3.5 Consequences of emergent properties......Page 50
3.6.1 Asimov’s Laws of Robotics......Page 52
3.6.2 Attractors......Page 54
3.7 Limitations of self-organization......Page 56
4.1 Development of understandings......Page 59
4.2 Examples in natural sciences......Page 60
4.2.1 Biology......Page 61
4.2.2 Chemistry......Page 62
4.3.1 Exploring bio-inspired......Page 63
4.3.2 Bio-inspired techniques......Page 64
4.3.3 Self-organization vs bio-inspired......Page 66
5.1.1 Autonomous systems......Page 67
5.1.2 Multi-robot systems......Page 68
5.1.3 Autonomic networking......Page 69
5.1.4 Mobile Ad Hoc Networks......Page 70
5.1.5 Sensor and Actor Networks......Page 71
5.2 Operating Sensor and Actor Networks......Page 72
6.1 Basic methods......Page 75
6.1.1 Positive and negative feedback......Page 76
6.1.2 Interactions among individuals and with the environment......Page 78
6.1.3 Probabilistic techniques......Page 79
6.2.1 Design process......Page 80
6.2.2 Discussion of the design paradigms......Page 81
6.3 Developing nature-inspired self-organizing systems......Page 83
6.4.1 Overview of modeling techniques......Page 84
6.4.2 Differential equation models......Page 85
6.4.4 Choosing the right modeling technique......Page 86
Appendix I Self-Organization – Further Reading......Page 87
II Networking Aspects: Ad Hoc and Sensor Networks......Page 91
7.1 Ad hoc networks......Page 93
7.1.1 Basic properties of ad hoc networks......Page 94
7.1.2 Mobile Ad Hoc Networks......Page 96
7.2.1 Basic properties of sensor networks......Page 99
7.2.2 Composition of single-sensor nodes......Page 102
7.2.3 Communication in sensor networks......Page 105
7.2.5 Coverage and deployment......Page 109
7.2.6 Comparison between MANETs and WSNs......Page 111
7.2.7 Application examples......Page 112
7.3.1 Required functionality and constraints......Page 116
7.3.2 Research objectives......Page 118
8.1 Properties and objectives......Page 121
8.2.1 Horizontal dimension......Page 123
8.2.2 Vertical dimension......Page 125
8.3.1 Mapping with primary self-organization methods......Page 127
8.3.2 Global state......Page 129
8.3.3 Location information......Page 130
8.3.4 Neighborhood information......Page 131
8.3.5 Local state......Page 132
8.3.6 Probabilistic techniques......Page 133
9 Medium Access Control......Page 135
9.1 Contention-based protocols......Page 136
9.2 Sensor MAC......Page 139
9.2.1 Synchronized listen/sleep cycles......Page 140
9.2.2 Performance aspects......Page 142
9.2.3 Performance evaluation......Page 144
9.3 Power-Control MAC protocol......Page 145
9.4 Conclusion......Page 148
10 Ad Hoc Routing......Page 149
10.1.1 Address-based routing vs data-centric forwarding......Page 151
10.1.2 Classification of ad hoc routing protocols......Page 153
10.2.1 Destination Sequenced Distance Vector......Page 157
10.2.2 Dynamic Source Routing......Page 158
10.2.3 Ad Hoc on Demand Distance Vector......Page 160
10.2.4 Dynamic MANET on Demand......Page 164
10.3 Optimized route stability......Page 167
10.4 Dynamic address assignment......Page 169
10.4.1 Overview and centralized assignment......Page 170
10.4.2 Passive Duplicate Address Detection......Page 171
10.4.3 Dynamic Address Allocation......Page 172
10.5 Conclusion......Page 175
11 Data-Centric Networking......Page 179
11.1 Overview and classification......Page 181
11.1.1 Data dissemination......Page 182
11.1.2 Network-centric operation......Page 184
11.2 Flooding, gossiping and optimizations......Page 185
11.2.1 Flooding......Page 186
11.2.2 Pure gossiping......Page 189
11.2.3 Optimized gossiping......Page 191
11.3 Agent-based techniques......Page 196
11.4.1 Basic algorithm......Page 199
11.4.2 Mobility support......Page 202
11.4.3 Energy efficiency......Page 203
11.5 Data aggregation......Page 204
11.5.1 Principles and objectives......Page 205
11.5.2 Aggregation topologies......Page 207
11.6 Conclusion......Page 210
12 Clustering......Page 211
12.1 Principles of clustering......Page 212
12.1.1 Requirements and classification......Page 213
12.1.2 k-means......Page 215
12.1.3 Hierarchical clustering......Page 216
12.2 Clustering for efficient routing......Page 217
12.2.1 Low-Energy Adaptive Clustering Hierarchy......Page 218
12.2.2 Hybrid Energy-Efficient Distributed Clustering Approach......Page 221
12.3 Conclusion......Page 222
Appendix II Networking Aspects – Further Reading......Page 225
III Coordination and Control: Sensor and Actor Networks......Page 229
13.1 Introduction......Page 231
13.1.1 Composition of SANETs – an example......Page 232
13.1.2 Properties and capabilities......Page 233
13.1.3 Components of SANET nodes......Page 236
13.1.4 Application examples......Page 238
13.2 Challenges and research objectives......Page 240
13.2.1 Communication and coordination......Page 241
13.2.2 Collaboration and task allocation......Page 242
13.3 Limitations......Page 243
14 Communication and Coordination......Page 245
14.1.1 Problem statement......Page 246
14.1.2 Logical time......Page 248
14.2 Time synchronization in WSNs and SANETs......Page 249
14.2.1 Requirements and objectives......Page 250
14.2.2 Conventional approaches......Page 251
14.2.3 Algorithms for WSNs......Page 254
14.3.1 Scalable coordination......Page 257
14.3.2 Selected algorithms......Page 258
14.3.3 Integrated sensor–actor and actor–actor coordination......Page 261
14.3.4 Problems with selfish nodes......Page 263
14.4 In-network operation and control......Page 264
14.5 Conclusion......Page 270
15 Collaboration and Task Allocation......Page 273
15.1 Introduction to MRTA......Page 274
15.1.1 Primary objectives......Page 276
15.1.2 Classification and taxonomy......Page 278
15.2.1 Open Agent Architecture......Page 281
15.2.2 Murdoch......Page 283
15.2.3 Dynamic negotiation algorithm......Page 284
15.3 Emergent cooperation......Page 288
15.3.1 Stimulation by work......Page 289
15.3.2 Stimulation by state......Page 290
15.4 Conclusion......Page 293
Appendix III Coordination and Control – Further Reading......Page 295
IV Self-Organization Methods in Sensor and Actor Networks......Page 299
16 Self-Organization Methods – Revisited......Page 301
16.1 Self-organization methods in SANETs......Page 303
16.2 Positive and negative feedback......Page 304
16.3 Interactions among individuals and with the environment......Page 308
16.4 Probabilistic techniques......Page 312
17 Evaluation Criteria......Page 317
17.1 Scalability......Page 318
17.2.1 Energy management......Page 319
17.2.2 Transmission power management......Page 320
17.3.1 Definition of ‘network lifetime’......Page 321
17.3.2 Scenario-based comparisons of network lifetime......Page 326
V Bio-inspired Networking......Page 329
18 Bio-inspired Systems......Page 331
18.1.1 Ideas and concepts......Page 332
18.1.2 Bio-inspired research fields......Page 334
18.2.1 Principles of ant foraging......Page 338
18.2.2 Ant-based routing......Page 341
18.2.3 Ant-based task allocation......Page 342
18.3.1 Principles of the immune system......Page 344
18.3.2 Application examples......Page 348
18.4.1 Introduction to signaling pathways......Page 349
18.4.2 Applicability in SANETs......Page 353
18.5 Conclusion......Page 355
Appendix IV Bio-inspired Networking – Further Reading......Page 357
Bibliography......Page 361
Index......Page 381
