QUALITY OF SERVICE AWARE OPTIMIZATION OF SENSOR NETWORK QUERIES

• text

Thesis

Traditional format

QUALITY OF SERVICE AWARE OPTIMIZATION OF SENSOR NETWORK QUERIES

Ixent Galpin

PhD

2010-08-14

University of Manchester

331

Abstract 14 Declaration 15 Copyright 16 The Author 17 Acknowledgements 18 Glossary 211 Introduction 221.1 SettingtheScene ........................... 22 1.2 Fundamentals............................. 25 1.3 Motivation............................... 28 1.4 Aim, Objectives and Research Contributions . . . . . . . . . . . . 30 1.5 TechnicalApproach.......................... 32 1.6 AGuideforReaders ......................... 362 Background 382.1 QueryProcessing ........................... 39 2.1.1 ClassicalQueryProcessing.................. 39 2.1.2 DistributedQueryProcessing ................ 43 2.1.3 StreamQueryProcessing................... 46 2.1.4 AdaptiveQueryProcessing ................. 482.2 SensorNetworks............................ 49 2.3 QoSinSensorNetworkApplications ................ 54 2.4 Conclusion............................... 5923 Related Work 623.1 FrameworkforComparison...................... 63 3.1.1 QoSExpectations....................... 63 3.1.2 QueryOptimization ..................... 643.2 The State of the Art in Sensor Network Query Processing . . . . . 66 3.3 QoS-awareness in Other Modes of Query Processing . . . . . . . . 76 3.4 Incorporating Alternative Decision-making Policies into Query Op-timizers ................................ 80 3.5 Conclusion............................... 844 The SNEE Query Processing Stack 85 4.1 QueryProcessingStackOverview.................. 87 4.2 QueryLanguage............................ 88 4.3 QoSExpectations........................... 92 4.4 Metadata ............................... 94 4.5 QueryProcessingStackDesignIssues................ 98 4.6 CharacterizationofQueryStackSteps . . . . . . . . . . . . . . . 1024.6.1 Single-sitePhase ....................... 102 4.6.2 Routing ............................ 104 4.6.3 Where-scheduling....................... 105 4.6.4 When-scheduling ....................... 1084.7 Conclusion............................... 1115 A Fixed Goal Instantiation of SNEE 114 5.1 Routing ................................ 115 5.2 Where-Scheduling........................... 119 5.3 When-Scheduling ........................... 126 5.4 Conclusion............................... 1306 A QoS-aware Instantiation of SNEE 132 6.1 TechnicalApproach.......................... 133 6.2 Routing ................................ 1346.2.1 AlgorithmDescription .................... 135 6.2.2 ExampleOutput ....................... 146 6.2.3 Discussion........................... 1496.3 Where-Scheduling........................... 151 36.3.1 AlgorithmDescription .................... 151 6.3.2 Exampleoutput........................ 166 6.3.3 Discussion........................... 1696.4 When-Scheduling ........................... 170 6.4.1 AlgorithmDescription .................... 170 6.4.2 ExampleOutput ....................... 178 6.4.3 Discussion........................... 1816.5 Conclusion............................... 1837 Evaluation 1847.1 Identifying a Baseline: Fixed-Goal SNQP Evaluation . . . . . . . 185 7.1.1 ExperimentSetup....................... 187 7.1.2 Results............................. 1897.2 EvaluationofQoS-awarenessinSNQPs . . . . . . . . . . . . . . . 192 7.2.1 ExperimentSetup....................... 194 7.2.2 Results............................. 1977.3 Discussion............................... 202 7.4 Conclusion............................... 2048 Concluding Remarks 2068.1 ResearchContributions........................ 206 8.2 SignificanceoftheResults ...................... 208 8.3 FutureWorkDirections........................ 211Appendices 215A SNEEql Physical Algebra 215B Deriving Cost Estimation Models from Operator Implementa- tions 220C QoS-aware Where-scheduling: Supplementary Material 225C.1 NeighbourGenerationExample ................... 225 C.2 Post-processingExample....................... 225D QoS-aware When-scheduling: Supplementary Material 230D.1 GeometricProgramming ....................... 230 D.2 Modellingthewhen-schedulingproblem. . . . . . . . . . . . . . . 2324D.2.1 ModellingtheMemoryConstraint(C1). . . . . D.2.2 Modelling the Processing time constraint (C2) . D.2.3 ModellingtheTotalEnergyQoSMetric . . . . D.2.4 ModellingtheLifetimeQoSMetric . . . . . . .E Evaluation: Scenarios Used for ExperimentsF Fixed-Goal SNQP Evaluation: Breakdown of Results. . . . . . 232 . . . . . . 233 . . . . . . 235 . . . . . . 236238252F.1 6-month Energy Consumption per Node (J) Results . . F.2 Lifetime(days)Results........................ 257 F.3 BufferingfactorResults ....................... 261 F.4 DeliveryTime(s)Results ...................... 266G QoS-aware SNQP Evaluation: Breakdown of Results 271G.1 Acquisitioninterval(s)Results ................... 271 G.2 DeliveryTime(s)Results ...................... 274 G.3 BufferingfactorResults ....................... 281 G.4 6-month Total Network Energy Consumption (J) Results . . . . . 287 G.5 Lifetime(days)Results........................ 294 G.6 6-month Energy Consumption per Node (J) Results . . . . . . . . 300H QoS-aware SNQP Evaluation: Example QEPs 307H.1 Scenario5............................... 307 H.2 Scenario6............................... 311Bibliography 318

Sensor networks comprise resource-constrained wireless nodes with the capabil- ity of gathering information about their surroundings and have recently risen to prominence with the promise of being an effective computing platform for di- verse applications, ranging from event detection to environmental monitoring. The database community proposed the use of sensor network query processors (SNQPs) as means to meet data collection requirements using a declarative query language. Declarative queries posed against a sensor network constitute an effec- tive means to repurpose sensor networks and reduce the high software develop- ment costs associated with them.The range of sensor network applications is very broad. Such applications have diverse, and often conflicting, QoS expectations in terms of the delivery time of results, the acquisition interval at which data is collected, the total energy consumption of the deployment, or the network lifetime. The conflicting nature of these desiderata is aggravated by the resource-constrained nature of sensor networks as a computing fabric, making it particularly challenging to reconcile the trade-offs that arise. Previously, SNQPs have been focussed on evaluating queries as energy-efficiently as possible. There has been comparatively less work on attempting to meet a broad range of optimization goals and constraints that captured these QoS expectations. In this respect, previous work in SNQP has not aimed at being general purpose across the breadth of applications to which sensor networks have been applied.This PhD dissertation presents an approach for enabling QoS-awareness in SNQPs so that query evaluation plans are generated that exhibit good perfor- mance for a broader range of sensor network applications in terms of their QoS expectations. The research contributions reported here include (a) a functional decomposition of the decision-making steps required to compile a declarative query into a query evaluation plan in a sensor network setting; (b) algorithms to implement these decision-making steps; and (c) an empirical evaluation to show the benefits of QoS-awareness compared to a representative fixed-goal SNQP.

• Sensor networks
• Query Processing
• Quality of Service

• Galpin, Ixent

• Faculty of Engineering and Physical Sciences
• School of Computer Science

uk-ac-man-scw:136326

Galpin, Ixent

14th November, 2011, 11:13:37

Galpin, Ixent

30th November, 2011, 19:25:57