| |
[摘要]：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. |
|
