ABSTRACT
CONTENTS 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 9.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
9.2.1 Periodic Query Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 9.2.2 Dynamic Query Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 9.2.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
9.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 9.3.1 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 9.3.2 Multi-regional Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 9.3.3 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
9.4 Multi-regional Query Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 9.4.1 Construction of MRQF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 9.4.2 MRQSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
9.4.2.1 Scheduling Initialization . . . . . . . . . . . . . . . . . . . . . 207 9.4.2.2 Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . . . 207
9.4.3 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 9.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
9.5.1 Simulation Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 9.5.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
Wireless sensor networks (WSNs) have variety of applications due to low cost and easy deployment, e.g., environmental monitoring, battlefield surveillance, and traffic control [120]. One major task of WSNs is to collect sensed data from sensor nodes deployed in the monitoring area. Hence, WSNs are also called data-centric networks where the sensed data of all the sensor nodes can be viewed as a database. Due to the fact that sensor nodes are usually randomly deployed in hostile or unreachable areas, the only way that users can interact with WSNs and obtain useful information is to disseminate queries from a special node called the sink (or base station). Therefore, query processing is one of the most important issues in WSNs and has been widely studied [147]-[148]. Early research of query processing mainly focuses on how to improve query efficiency [149][150] while minimizing the energy consumption. With the emergence of real-time query processing [151], e.g., fire monitoring in forests, minimum latency becomes another primary concern. Hence, minimum latency query scheduling, which aims to derive a collision-free query scheduling plan with minimum latency, shows its advantage in time-sensitive applications.
