An Online Algorithm for Data Collection by Multiple Sinks in Wireless Sensor Networks

Abstract— Data collection by multiple sinks is a fundamental problem in wireless sensor networks. Existing works focused on designing the optimal offline methods provided that the number and positions of sensors and sinks (or trajectories of mobile sinks) are predetermined. This may not be practical as, though sensors are cheap, sinks are quite expensive in reality. A more practical scenario is that sinks are deployed step by step during the network operation due to the budget constraint, and we do not know the number, positions and capacities of sinks in prior. In this paper, we investigate the problem of data collection by multiple sinks, and design a suboptimal online algorithm via primal-dual approach, requiring very little priori knowledge. We theoretically derive the competitive ratio of the online algorithm, and further improve it by finding the optimal sink location with an approximation ratio. We also analyze the computational complexity of the improved approach. Extensive simulations are conducted to demonstrate the performance of the proposed online algorithm and performance-complexity tradeoff. Once we decide to use multiple sinks for data collection, the problem comes where to deploy them and how much data to be transmitted from each sensor to each sink. Existing works focused on designing the optimal offline methods provided that the number and positions of sensors and sinks (or trajectories of mobile sinks) are predetermined. < final year projects >