Minimum latency scheduling for Multi-Regional Query in Wireless Sensor Networks
Mingyuan Yan, Jing He, Shouling Ji, Yingshu Li · 2011
Query scheduling as one of the most important technologies used in query processing has been widely studied recently. Unfortunately, to the best of our knowledge, no previous work focuses on the Minimum Latency Multi-Regional Query Scheduling (ML-MRQS) problem. In this paper, we investigate the ML-MRQS problem in Wireless Sensor Networks (WSNs), which aims to generate a scheduling plan with minimum latency for a more practical query model called Multi-Regional Query (MRQ). A MRQ targets at user interested data from multiple region-sofa WSN, where each region is a subarea of the WSN. We claim that the ML-MRQS problem is NP-hard. Therefore, we propose a heuristic scheduling algorithm Multi-Regional Query Scheduling Algorithm (MRQSA) to solve this problem. Theoretical analysis shows that the latency of MRQSA is upper bounded by 23A + B + C for a MRQ with m query regions R1, R2…, Rm, where A = maxi=1mDileft, B = maxi=1m{(23Di+5Δ+21)ki}, C = Σi=1mHi+5Δ−m+17, m is the number of regions, Δ is the maximum node degree in the WSN, A is the diameter of Ri, kiis the maximum overlapped degree of sensor nodes in TU, Hi represents the distance of Riwith respect to the sink, and Dileftis the diameter of the non-overlapped part of Ri. Extensive simulations are conducted to verify the performance of our algorithm, which show that MRQSA significantly reduces the query latency when compared with the most recently published multi-query scheduling algorithm.