Optimal Stop Points for Data Gathering in Sensor Networks with Mobile Sinks
- 1
- 2
- 3
- 4
Abstract
Given a wireless sensor network (WSN) in which a mobile sink is used to collect data from the sensor nodes, this paper addresses the problem of selecting a set of stop points that results in low energy usage by the sensor nodes. This paper assumes an approach in which a mobile sink travels along a fixed path and uses a stop-and-collect protocol since this has previously been shown to be an efficient WSN data collection method. The problem of selecting an optimal set of stop points is shown to be an NP-hard problem. Then, an Integer Linear Programming (ILP) formulation is used to derive an optimal algorithm that can be used for small problem instances. Next, a polynomial-time Tabu-search-based heuristic algorithm is proposed. Simulations are used to compare the energy consumption values, computation times and expected network lifetimes when using the optimal ILP algorithm, the proposed heuristic algorithm and several other possible heuristic algorithms. The results show that the proposed heuristic algorithm results in near-optimal energy usage values with low computation times, thereby making it suitable for large-sized WSNs.
- A. Kansal, A. A. Somasundara, D. D. Jea, M. B. Srivastaba and D. Estring, “Intelligent Fluid Infrastructure for embedded Networks,” Proceedings of MobiSys, 2004, pp. 111-124.
- A. Kinalis, S. Nikoletseas, D. Patroumpa and J. Rolim, “Biased Sink Mobility with Adaptive Stop Times for Low Latency Data Collection in Sensor Networks,” Proceedings of Globecom, Vol. 30, 2009, pp. 1-6.
- W. Aioffi, G. Mateus and F. Quintao, “Optimization Issues and Algorithms for Wireless Sensor Networks with Mobile Sinks,” Proceedings of the International Network Optimization Conference, Paris, 2007.
- Y. Gu, D. Bozdag, E. Ekici, F. Ozguner and C. G. Lee, “Partitioning Based Mobile Element Scheduling in Wireless Sensor Networks,” Proceedings of the Sensor and Ad-Hoc Communication and Networks, Santa Clara, 2005.
- R. Sugihara and R. K. Gupta, “Scheduling under Location and Time Constraints for Data Collection in Sensor Net- works,” Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS), Work in Progress Session, 2007.
- R. Sugihara and R. K. Gupta, “Improving the Data Delivery Latency in Sensor Networks with Controlled Mobility,” Proceedings of the 4th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), Vol. 5067, 2008, pp. 386-399.
- G. Xing, T. Wang, Z. Xie and W. Jia, “Rendezvous Planning in Mobility-Assisted Wireless Sensor Net-works,” Proceedings of the 28th IEEE International Real-Time Systems Symposium (RTSS), 2007, pp. 311-320. doi:10.1109/RTSS.2007.44
- G. Xing, T. Wang, W. Jia and M. Li “Rendezvous Design Algorithm for Wireless Sensor Networks with a Mobile Base Station,” Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2008, pp. 231-239. doi:10.1145/1374618.1374650
- J. Rao and S. Biswas, “Network-Assisted Sink Navigation for Distributed Data Gathering: Stabilityand Delay- Energy Trade-Offs,” Computer Communications, Vol. 33, No. 2, 2010, pp. 160-175. doi:10.1016/j.comcom.2009.08.009
- J. Luo, J. Panchard, M. Piorkowski, M. Grossglauser and J. P. Hubaux, “MobiRoute: Routing Towards a Mobile Sink for Improving Lifetime in Sensor Networks,” Proceedings of the 4th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), 2006, pp. 480-497.
- S. Gao and H. K. Zhang, “Energy Efficient Path-Constrained Sink Navigation in Delay-Guaranteed Wireless Sensor Networks,” Networks, Vol. 5, No. 6, 2010, pp. 658-665. doi:10.4304/jnw.5.6.658-665