The d-hop k-data coverage query problem in wireless sensor networks

ABSTRACT

The task of querying wireless sensor network (WSN) to retrieve data of interest is very significant and a wealth of query types have been proposed in the context of WSNs. This article describes the d-hop k-data coverage query problem, which is a novel query type, aiming at extracting "feature(s) distribution maps" from WSNs. This problem generalizes earlier research problems, like top-k, skyband, and d-hop dominating sets. For this problem, we provide a fully distributed solution, the DaCoN protocol, that avoids constructing a "network spanner", since such a structure requires an expensive initialization procedure, misses the notion of neighborhoods, and most importantly, it creates hot-spots of communication, that shorten the network lifetime (i.e., some nodes deplete their energy very fast). We have developed a simulator to study the performance and behavior of the DaCoN protocol for various sensornet topologies and data distributions, and the obtained results attested the energy-efficiency and effectiveness of the protocol.

REFERENCES

• 1: S. M. Nazrul Alam , Zygmunt J. Haas, Coverage and connectivity in three-dimensional networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161128]
• 2: A. D. Amis, R. Prakash, T. H. P. Vuong, and D. T. Huynh. Max-min d-cluster formation in wireless ad hoc networks. In Proceedings of IEEE International Conference on Computer Communications (INFOCOM), pages 32--41, 2000.
• 3: Brian Babcock , Chris Olston, Distributed top-k monitoring, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872764]
• 4: J. H. Chang and L. Tassiulas. Energy conserving routing in wireless ad-hoc networks. In Proceedings of IEEE International Conference on Computer Communications (INFOCOM), pages 22--31, 2000.
• 5: A. Deligiannakis, Y. Kotidis, and N. Roussopoulos. Hierarchical in-network data aggregation with quality guarantees. In Proceedings of International Conference on Extending Data Base Technology (EDBT), pages 658--675, 2004.
• 6: Tao-Young Fu , Wen-Chih Peng , Wang-Chien Lee, Optimizing parallel itineraries for knn query processing in wireless sensor networks, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321496]
• 7: R. Gandhi and S. Parthasarathy. Fast distributed well connected dominating sets for ad hoc networks. Technical Report CS-TR-4559, Computer Science Department, University of Maryland at College Park, 2004.
• 8: Deepak Ganesan , Deborah Estrin , John Heidemann, Dimensions: why do we need a new data handling architecture for sensor networks?, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.143-148, January 2003 [doi>10.1145/774763.774786]
• 9: M. Hefeeda and H. Ahmadi. A probabilistic coverage protocol for wireless sensor networks. In Proceedings of IEEE International Conference on Network Protocols (ICNP), pages 41--50, 2007.
• 10: Chi-Fu Huang , Yu-Chee Tseng, The coverage problem in a wireless sensor network, Mobile Networks and Applications, v.10 n.4, p.519-528, August 2005 [doi>10.1145/1160162.1160175]
• 11: Holger Karl , Andreas Willig, Protocols and Architectures for Wireless Sensor Networks, John Wiley & Sons, 2005
• 12: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, Progressive skyline computation in database systems, ACM Transactions on Database Systems (TODS), v.30 n.1, p.41-82, March 2005 [doi>10.1145/1061318.1061320]
• 13: D. M. Pennock, G. W. Flake, S. Lawrence, E. J. Glover, and C. L. Giles. Winners don't take all: Characterizing the competition for links on the Web. Proceedings of the National Academy of Sciences, 99(8):5207--5211, 2002.
• 14: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 15: A. Sharaf , Jonathan Beaver , Alexandros Labrinidis , K. Chrysanthis, Balancing energy efficiency and quality of aggregate data in sensor networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.384-403, December 2004 [doi>10.1007/s00778-004-0138-0]
• 16: Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024]
• 17: Minji Wu , Jianliang Xu , Xueyan Tang , Wang-Chien Lee, Top-k Monitoring in Wireless Sensor Networks, IEEE Transactions on Knowledge and Data Engineering, v.19 n.7, p.962-976, July 2007 [doi>10.1109/TKDE.2007.1038]
• 18: J. Xin and G. Wang. Energy-efficient skyline queries over sensor network using mapped skyline filters. In Proceedings of International Asia-Pacific Web Conference/ Web Age Information Management (APWeb/WAIM), pages 144--156, 2007.
• 19: J. Xin, G. Wang, L. Chen, X. Zhang, and Z. Wang. Continuously maintaining sliding window skylines in a sensor network. In Proceedings of International Conference on Database Systems for Advanced Applications (DASFAA), pages 509--521, 2007.
• 20: Mohamed Younis , Kemal Akkaya, Strategies and techniques for node placement in wireless sensor networks: A survey, Ad Hoc Networks, v.6 n.4, p.621-655, June, 2008 [doi>10.1016/j.adhoc.2007.05.003]
• 21: D. Zeinalipour-Yazti , Z. Vagena , D. Gunopulos , V. Kalogeraki , V. Tsotras , M. Vlachos , N. Koudas , D. Srivastava, The threshold join algorithm for top-k queries in distributed sensor networks, Proceedings of the 2nd international workshop on Data management for sensor networks, August 30-30, 2005, Trondheim, Norway [doi>10.1145/1080885.1080896]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Keywords:
data coverage, distributed algorithms, energy efficiency, wireless sensor networks