Optimal Stop Points for Data Gathering in Sensor Networks with Mobile Sinks

Junyoung Park, Kyoungjin Moon, Sungjoo Yoo, Sunggu Lee

.

DOI: 10.4236/wsn.2012.41002                

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.

Keywords

Wireless Sensor Network (WSN); Mobile Sink; Energy Efficiency; Optimization; Tabu Search Heuristic

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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
[8]	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
[9]	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
[10]	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.
[11]	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
[12]	A. Giannakos, G. Karagiorgos and I. Stavrakakis, “A Message-Optimal Sink Mobility Model for Wireless Sensor Networks,” Proceedings of the Eighth International Conference on Networks, 2009. doi:10.1109/ICN.2009.53
[13]	T. Shi and Y. Thomas Hou, “Theoretical Results on Base Station Movement Problem for Sensor Network,” 27th Conference on Computer Communications IEEE, 2008, pp. 13-18.
[14]	R. C. Shah, S. Roy, S. Jain and W. Brunette, “Data MULEs: Modeling and Analysis of a Three-Tier Architecture for Sparse Sensor Networks,” Sensor Network Protocols and Applications, Vol. 1, No. 2-3, 2003, pp. 215-223. doi:0.1109/SNPA.2003.1203354
[15]	V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala and V. Pandit, “Local Search Heuristic for K-Median and Facility Location Problems,” Proceedings of the ACM Symposium on Theory of Computing, 2001, pp. 21-29.
[16]	F. Glover and M. Laguna, “Tabu Search,” Kluwer Academic, Boston, 1997.
[17]	F. Glover and M. Laguna, “Tabu Search,” In: C. R. Reeves, Ed., Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications, Oxford, 1992, pp. 70-150.
[18]	Xpressmp. http://www.dash.co.uk
[19]	M. Evans, N. Hastings and B. Peacock, “Statistical Distributions,” 3rd Edition, Wiley Press, New York, 2000, pp. 34-42.
[20]	S. L. Wu and Y. C. Tseng, “Wireless Ad Hoc Networking,” Auerbach Publications, Boca Raton, 2007. doi:10.1201/9781420013825