A fast algorithm for data collection along a fixed track

Recent research shows that significant energy saving can be achieved in wireless sensor networks (WSNs) with a mobile base station that collects data from sensor nodes via short-range communications. However, a major performance bottleneck of such WSNs is the significantly increased latency in data collection due to the low movement speed of mobile base stations. In this paper we study the problem of finding a data collection path for a mobile base station moving along a fixed track in a wireless sensor network to minimize the latency of data collection. The main contribution is an O(mnlog⁡n)O(mnlog⁡n) expected time algorithm, where n is the number of sensors in the networks and m is the complexity of the fixed track.