Constructing a Message-Pruning Tree with Minimum Cost for Tracking Moving Objects in Wireless Sensor Networks Is NP-Complete and an Enhanced Data Aggregation Structure

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 minimal 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 construct 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.