Approximation Algorithms for Capacitated Minimum Forest Problems in Wireless Sensor Networks With a Mobile Sink
To deploy a wireless sensor network for the purpose of large-scale monitoring, in this paper, the authors propose a heterogeneous and hierarchical wireless sensor network architecture. The architecture consists of sensor nodes, gateway nodes and mobile sinks. The sensors transmit their sensing data to the gateway nodes for temporary storage through multi-hop relays, while the mobile sinks travel along pre-determined trajectories to collect data from nearby gateway nodes. Under this paradigm of data gathering, they formulate a novel constrained optimization problem, namely, the capacitated minimum forest problem, for the decision version of which they first show NP-completeness. They then devise approximation algorithms and provide upper bounds for their approximation ratios.