Abstract
Wireless sensor networks have often been used to monitor and report the locations of moving objects. Since sensors can also be used for storage, a wireless sensor network can be considered a distributed database, enabling us to update and query the location information of moving objects. Many researchers have studied the problem of how to construct message-pruning trees that can update a database and query objects with minimum cost (the Minimum Cost Message-Pruning Tree problem). The trees are constructed in such a way that the total cost of updating the database and querying objects is kept as minimum as possible, while the hardness of the Minimum Cost Message-Pruning Tree problem remains unknown. In this paper, we first show that the Minimum Cost Message-Pruning Tree problem is NP-complete. Subsequently, since the message-pruning tree with minimum cost is hard to be constructed in polynomial time, we propose a new data aggregation structure, a message-pruning tree with shortcuts, instead of the message-pruning tree. Simulation results show that the proposed data aggregation structure significantly reduces the total cost of updating the database and querying objects, as compared to the message-pruning tree. © 2008 IEEE.