Quality aware query scheduling in wireless sensor networks

ABSTRACT

We study query scheduling in Wireless Sensor Networks (WSNs) with a focus on two important metrics: Quality of Service (QoS) and Quality of Data (QoD). The motivation comes from our observation that most WSN scheduling techniques ignore the quality requirements of queries. As a result, they are inefficient or inapplicable to quite a few applications that have different quality requirements. In this paper, we propose a distributed Quality Aware Scheduling (QAS) framework to address this problem. QAS works on top of existing quality-unaware query scheduling protocols and allows individual users to specify their QoS and QoD requirements on their queries. Given these quality requirements, QAS determines the target qualities to be provided in scheduling and the execution order of these queries so as to maximize the total system profit. Our preliminary results show that QAS significantly outperforms the baseline scheduling algorithms in terms of system profit.

REFERENCES

• 1: D. J. Abadi, Y. Ahmad, M. Balazinska, U. Çetintemel, M. Cherniack, J.-H. Hwang, W. Lindner, A. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. B. Zdonik, "The design of the borealis stream processing engine," in CIDR, 2005.
• 2: R. K. Abbott and H. Garcia-Molina, "Scheduling real-time transactions: A performance evaluation," ACM Trans. Database Syst., vol. 17, no. 3, pp. 513--560, 1992.
• 3: M. Amirijoo, S. Son, and J. Hansson, "Qod adaptation for achieving lifetime predictability of wsn nodes communicating over satellite links," in INSS, June 2007.
• 4: Q. Cao, T. F. Abdelzaher, T. He, and J. A. Stankovic, "Towards optimal sleep scheduling in sensor networks for rare-event detection," in IPSN, 2005.
• 5: H.-R. Chen and Y.-H. Chin, "An adaptive scheduler for distributed real-time database systems," Inf. Sci., vol. 153, pp. 55--83, 2003.
• 6: J. R. Haritsa, M. J. Carey, and M. Livny, "Value-based scheduling in real-time database systems," VLDB J., vol. 2, no. 2, pp. 117--152, 1993.
• 7: B. Hohlt, L. Doherty, and E. A. Brewer, "Flexible power scheduling for sensor networks," in IPSN, 2004.
• 8: D. Hong, T. Johnson, and S. Chakravarthy, "Real-time transaction scheduling: A cost conscious approach," in SIGMOD, 1993.
• 9: IntelLabData, "http://berkeley.intel-research.net/labdata."
• 10: G. Lu, N. Sadagopan, B. Krishnamachari, and A. Goel, "Delay efficient sleep scheduling in wireless sensor networks," in INFOCOM. IEEE, 2005.
• 11: S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, "Tinydb: an acquisitional query processing system for sensor networks," ACM Trans. Database Syst., vol. 30, no. 1, pp. 122--173, 2005.
• 12: H. Pang, M. J. Carey, and M. Livny, "Multiclass query scheduling in real-time database systems," IEEE Trans. Knowl. Data Eng., vol. 7, no. 4, pp. 533--551, 1995.
• 13: L. Peng and K. S. Candan, "Data-quality guided load shedding for expensive in-network data processing," in ICDE, 2007.
• 14: H. Qu and A. Labrinidis, "Preference-aware query and update scheduling in web-databases," in ICDE, 2007, pp. 356--365.
• 15: Q. Ren and Q. Liang, "Energy and quality aware query processing in wireless sensor database systems," Inf. Sci., vol. 177, no. 10, pp. 2188--2205, 2007.
• 16: SDGEN, "http://www.cse.ust.hk/catalac/."
• 17: M. L. Sichitiu, "Cross-layer scheduling for power efficiency in wireless sensor networks," in INFOCOM, 2004.
• 18: H. Wu and Q. Luo, "Adaptive holistic scheduling for query processing in sensor networks," HKUST-CSE Technical Report, http://www.cse.ust.hk/tahoe, April, 2007.
• 19: H. Wu, Q. Luo, J. Li, and A. Labrinidis, "Quality aware scheduling for query processing in wireless sensor networks," HKUST-CSE Technical Report, http://www.cse.ust.hk/tahoe, January, 2009.
• 20: H. Wu, Q. Luo, and W. Xue, "Distributed cross-layer scheduling for in-network sensor query processing," in PerCom. IEEE Computer Society, 2006, pp. 180--189.
• 21: Y. Yao and J. Gehrke, "Query processing in sensor networks," in CIDR, 2003.
• 22: D. Yates, E. Nahum, J. Kurose, and P. Shenoy, "Data quality and query cost in wireless sensor networks," in Pervasive Computing and Communications Workshops, March 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures; Complexity measures

General Terms:
Algorithms, Experimentation