Title 1
Preface 4
Organization 6
Table of Contents 10
Distributed Coalition Formation in Visual Sensor Networks: A Virtual Vision Approach 13
Introduction 13
Virtual Vision 14
Distributed Control in Camera Sensor Networks 15
Overview 16
Related Work 16
Camera Nodes 18
Local Vision Routines 18
Camera Node Behaviors 19
Sensor Network Model 20
Coalition Formation 21
Conflict Resolution 22
Node Failures and Communication Errors 24
Video Surveillance 26
Computing Camera Node Relevance 26
Surveillance Tasks 27
Results 27
Discussion 29
Conclusion 30
Efficient and Distributed Access Control for Sensor Networks 33
Introduction 33
System Models and Assumptions 34
Efficient and Distributed Access Control 36
The Baseline Approach 36
Enabling Privilege Delegation 38
Enabling Efficient Broadcast Query 40
Simulation Evaluation 44
Related Work 45
Conclusion and Open Problems 46
Optimizing End to End Routing Performance in Wireless Sensor Networks 48
Introduction 48
Spatial Complexity of Wireless Channels 50
Greedy Forwarding Based on ETX-Distance 51
Underlying Wireless Channel Evaluation 52
Virtual Distance Based Greedy Forwarding 52
ETX Embedding 53
Sample a Wireless Sensor Network with Beacons 55
Performance Evaluation 56
Evaluate the ETX-Embedding in TOSSIM 57
Related Work 58
Conclusion 59
Improving Event-to-Sink Throughput in Wireless Sensor Networks 62
Introduction 62
Preliminary 64
Packet Reliability v.s. Event Throughput 64
Hop-by-Hop Recovery Based on Time Out Mechanism 65
Hop-by-Hop Recovery Based on Out-of-Sequence Mechanism 65
Sink Centric Transport Protocol 66
Packet Loss Detection and Notification 67
Packet Retransmission 68
Performance Evaluation 69
Impact of Packet Inject Rate 70
Impact of the Hop Distances 72
Related Work 73
Conclusion 74
Dwarf: Delay-aWAre Robust Forwarding for Energy-Constrained Wireless Sensor Networks 76
Introduction 76
Related Work 78
Requirements and Assumptions 79
Alarm-System Scenario 79
MAC Protocol 80
Definitions 81
Algorithms 81
Alarm Forwarding 82
Node Status Observation 83
Startup 84
Evaluation 85
Analytical 85
Simulation 87
Conclusions 91
Localization for Anchoritic Sensor Networks 94
Introduction 94
Motivation 96
Related Work 97
Our Approach 98
Description 98
Theoretic Framework 99
Random Field Models 100
Boolean Model 100
Large Clouds 101
Random Walkers 101
Engineering Ramifications 101
Experimental Results 102
Reconstruction of the Sensor Locations 104
Proof of Theorem 1 104
Mobile Anchor-Free Localization for Wireless Sensor Networks 108
Introduction 108
Related Work 110
Mobile Geographic Distributed Localization (MGDL) 110
Overview of MGDL Algorithm 110
Measurement Procedure 112
Local Map Computation 112
Transformation Procedure 113
Mobile Measurement Techniques 114
ReTransformation Procedure 116
Simulation Result 116
Simulation Configuration 116
Localization Accuracy 118
Node Density 119
Node Speed 119
Communication Overhead 119
Summary 120
References 120
Optimal Cluster Association in Two-Tiered Wireless Sensor Networks 122
Introduction 122
Homogeneous Small Sensors 125
Homogeneous Application Nodes 125
Heterogeneous Application Nodes 130
Heterogeneous Small Sensors 131
Performance Studies 133
Conclusion 134
Distributed Facility Location Algorithms for Flexible Configuration of Wireless Sensor Networks 136
Introduction 136
Preliminaries 137
Related Work 138
Centralized Algorithms 139
One-Hop Approximation 141
Multi-hop Approximation 144
Experimental Results 146
Scalability 147
Network Dynamics 150
Conclusion and Outlook 151
SNTS: Sensor Network Troubleshooting Suite 154
Introduction 154
Related Work 156
Scope of the Fault Diagnosis Tool 158
System Architecture 159
Data Collection Component 159
Data Analysis Component 161
Interface 162
Case Study: EnviroTrack 162
Failure of the Tracking Protocol 163
Failure Diagnosis Scenario 164
Interpretation of the Rules 165
Effect of Parameter Tuning 166
Discussion 166
Conclusion 166
Design and Implementation of a Flexible Location Directory Service for Tiered Sensor Networks 170
Introduction 170
Services 171
Design 172
Architecture 172
Location Information Maintenance 173
Query Processing 173
Cost Benefits over a Centralized Directory Approach 175
Implementation 175
Experimental Results 177
Single Sensor Network 178
Multiple Sensor Networks 181
Related Work 183
Conclusion 184
A Semantics-Based Middleware for Utilizing Heterogeneous Sensor Networks 186
Introduction 186
System Overview 188
Semantic Model of Data Sources and PEs 189
Descriptions of Data Sources 190
Descriptions of PEs 192
Semantic Composition of Applications 193
Connecting a Stream to a PE 194
Automatic Composition of Applications 195
Experiments 196
Related Work 198
Conclusion 199
A Compilation Framework for Macroprogramming Networked Sensors 201
Introduction 201
ATaG: Abstract Task Graph 203
Programming Model 203
Runtime System 204
Compilation of Data-Driven Macroprograms: Overview 205
Compilation Framework 207
Compilation Input and Output 208
Compilation Modules 208
Demonstration 211
Discussion 213
Concluding Remarks 215
Passive Inspection of Sensor Networks 217
Introduction 217
SNIF 219
Deployment Support Network (DSN) 219
Physical Layer and Medium Access 220
Packet Decoder 220
Data Stream Processor 221
User Interface 222
Case Study: Data Gathering Applications 222
Application Model 223
Problems and Indicators 223
Application-Specific Operators 224
Operator Graph 226
Evaluation 228
Related Work 231
Conclusions 232
Separating theWheat from the Chaff: Practical Anomaly Detection Schemes in Ecological Applications of Distributed Sensor Networks 235
Introduction 235
Related Work 236
Bayesian Classifier Method 237
A Method Based on the Statistics of Differences Between Sensor Measurements 239
Statistical Inference 240
Statistical Anomalies: Error and Event Detection 243
Inference of Missing Readings 244
Application to Ecological Data from Sevilleta LTER Site 245
Discussion and Outlook 248
Image Change Detection Using Wireless Sensor Networks 252
Introduction 252
Processing at Sensors 254
Processing at Fusion Center 258
Performance Analysis and Results 262
Performance at the Sensor 263
Performance at the Fusion Center 263
Conclusions and Future Work 263
Near Optimal Sensor Selection in the COlumbia RIvEr (CORIE) Observation Network for Data Assimilation Using Genetic Algorithms 265
Introduction 265
Data Assimilation Overview 268
CORIE Data Assimilation Framework 268
Problem Formulation 269
Sensor Selection Using Genetic Algorithm 271
Representing the Network Configuration 272
Fitness Function and Selection 272
Crossover and Mutation 272
Experimental Results 272
Experimental Design 273
Results and Analysis 274
Related Work 275
Future Work 276
Conclusion 277
Data Salmon: A Greedy Mobile Basestation Protocol for Efficient Data Collection in Wireless Sensor Networks 279
Introduction 279
Model 282
The Data Salmon Protocol 282
The Dynamic Tree Maintenance Protocol 283
The Greedy Data Salmon Protocol 283
Proof of Optimality 284
Simulation Results 286
Discussion 289
Concluding Remarks 290
SDIP3: Structured and Dynamic Information Push and Pull Protocols for Distributed Sensor Networks 293
Introduction 293
Problem Formulation 295
System Model 295
Push and Pull Model 296
Event and Demand Distribution Models 298
Formulation of the Optimization Problem 298
Theoretical Analysis 299
Optimal Push Scopes for Disk Structures 300
Optimal Diamond Size 300
Push Scope Verification 301
Dynamic Balancing of Push and Pull 302
Boundary States 303
Boundary State Transition 303
Application: Distributed Traffic Information Networks 303
Traffic Network Simulations 303
Simulation Results 304
Conclusions 305
Efficient Computation of Minimum Exposure Paths in a Sensor Network Field 307
Introduction 307
Preliminaries and Problem Formulation 309
Single-Sensor Fields 310
Multiple-Sensor Fields 313
An Approximation Algorithm for Constructing MEPs 314
Defining Steiner Points 314
Description and Analysis of the Algorithm 316
Improving the Running Time 318
Conclusion 319
Energy Efficient Intrusion Detection in Camera Sensor Networks 321
Introduction 321
Related Work 323
Model 323
Geometric Preprocessing 324
Tasking the Cameras 325
Assigning Probabilities in a Graph 325
Assigning Probabilities in Continuous Space 327
Algorithm 328
Special Case 329
Deterministic Algorithm 329
Simulation Experiments 330
Conclusions and Further Work 332
Leveraging Redundancy in Sampling-Interpolation Applications for Sensor Networks 336
Introduction 336
Overview and Fundamentals 338
Hilbert Space Representation 340
Primary Subspace 341
Sensor Selection 342
Greedy Algorithm 343
Evaluation 345
Conclusion 349
References 349
A Fully Polynomial Approximation Algorithm for Collaborative Relaying in Sensor Networks Under Finite Rate Constraints 350
Introduction 350
System Model 352
Total Energy Minimization for Collaborative Relaying with Perfect CSI 353
Optimal Quantization for Optimal Collaborative Relaying 354
Quantization Protocol 355
Preliminaries 355
QBS and QBR: Independent Basestation-Source and Basestation-Relay Quantization Algorithms 356
Algorithm $QBS(k_s)$ 357
Algorithm $QBR(k_r)$ 358
Joint Source/Relay Quantization 358
2-Factor Approximation for Joint Quantization 359
Fully Polynomial Approximation Scheme 360
Relay to Clusterhead Quantization Algorithm QRB 364
Conclusions 364
A Connectivity Based Partition Approach for Node Scheduling in Sensor Networks 366
Introduction 366
Overview 368
Motivation 368
Problem Formulation 369
CPA Design 371
Group Merging 371
Load Balancing Energy Usage in Groups 373
Performance Evaluation 373
Under Ideal Radio Propagation Model 374
Under Irregular Radio Propagation Model 376
Related Work 377
Conclusion 378
Energy-Efficient Data Acquisition Using a Distributed and Self-organizing Scheduling Algorithm for Wireless Sensor Networks 380
Introduction 380
An Overview of the $DOSA$ Approach 381
LMAC: A Lightweight Medium Access Control Protocol 382
Preliminaries for Self-stabilization 383
$DOSA:$ A Distributed and Self-organizing Scheduling Algorithm 383
Dependency of $DOSA$ on LMAC 384
General Operation of $DOSA$ 385
Performance of $DOSA$ 389
Coping with a Dead Node 390
Coping with a New Node 391
Details of Implementation and Results 394
Related Work 396
Conclusion and Future Work 397
An Adaptive Scheduling Protocol for Multi-scale Sensor Network Architecture 398
Introduction 398
Motivating Application 399
COMPASS Overview 400
Adaptive Scheduling Service 401
Design Principles 401
Related Work 402
Contention-Based Protocols 402
Schedule-Based Protocols 403
Graph Coloring 404
Medium Access Scheduling in a Hierarchy 404
Intra-cluster Scheduling 406
Inter-cluster Scheduling 410
Evaluation 410
Conclusions and Future Work 413
Minimum-Energy Broadcast with Few Senders 416
Introduction 416
Our Contribution 418
Related Work 419
Outline 420
Preliminaries 420
A Naive, Brute-Force Algorithm 420
Algorithms 421
Small Synopsis of the Network Topology 421
Faster $O(1)$-Approximations 423
Future Work 426
Simple, Distributed Algorithms with Good Performance 426
Extension to Metrics of Bounded Doubling Dimension 427
$(1+\\epsilon)$-Approximation with Running Time Polynomial in $k$ (and $1/\\epsilon$) ? 427
Author Index 429