Monitoring Exact Top-K Values in Wireless Sensor Networks Using Dominating Set Trees

  • Author(s) / Creator(s)
  • Technical report TR09-01. Finding the top-k values is an important type of aggregation query in wireless sensor networks. Previous proposals relied on a given underlying logical tree topology for data aggregation/forwarding, but did not pay due attention to the role of such topology. In this paper we first argue that the underlying tree topology plays a very important role in the query processing cost. We then propose the use of a particular tree topology, based on Dominating Sets, which is well suited to explore the network's physical topology for processing the top-k queries efficiently. Experimental results obtained using real and synthetic datasets confirm that by simply replacing the tree topologies used in previous proposals with the Dominating Set-based Tree (DST) one can reduce the cost of the top-k queries considerably, but the gain depends on k and other network related parameters. In addition we also propose two new algorithms, TAGP and ATAK, for processing the top-k queries. Our experimental results reveal that in all examined cases ATAK consistently performs better than other techniques while exploiting the proposed logical tree topology effectively. | TRID-ID TR09-01

  • Date created
  • Subjects / Keywords
  • Type of Item
  • DOI
  • License
    Attribution 3.0 International