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

• Author(s) / Creator(s)

  • Nikolaidis, Ioanis
  • Nascimento, Mario A.
  • Malhotra, Baljeet

• 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

  2009

• Subjects / Keywords

  • Sensor networks
  • Database Systems
  • Dominating set tree
  • Aggregation
  • Filtering
  • Pruning
  • Continuous top-k queries
  • Communication Networks

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3959CF9H

• License

  Attribution 3.0 International