Lifetime maximization of wireless sensor networks with sink costs

Balanced distribution of the energy load of the sensors is important for the elongation of wireless sensor network (WSN) lifetimes. There are four main WSN design issues affecting the energy distribution among the sensors: sensor locations, sensor activity schedules, mobile sink routes, and data ow routes. Many studies try to make energy usage more efficient through optimal determination of these design issues. However, only very few studies handle these four design issues in a combined manner. Additionally, the cost of the sinks is neglected in all studies. In this study, a mixed integer linear program is rst proposed, in which the cost of the sinks is taken into consideration in terms of lifetime hours and the four design issues are integrated. Next, a heuristic solution procedure for the solution of large network instances is offered and the efficiency of the heuristic is proven by comparing its performance with that of commercial solvers in extensive numerical instances.

PDF

___

[1] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey. Comput Netw 2008; 52: 2292-2330.
[2] Popa L, Rostamizadeh A, Karp R, Papadimitriou C, Stoica, I. Balancing traffic load in wireless networks with curveball routing. In: International Symposium on Mobile Ad Hoc Networking and Computing; 9{14 September 2007; Montreal, Quebec, Canada. ACM. pp. 170-179.
[3] Li J, Mohapatra P. Analytical modeling and mitigation techniques for the energy hole problem in sensor net- works. Pervas Mobile Comput 2007; 3: 233-254.
[4] Wu X, Chen G, Das SK. Avoiding energy holes in wireless sensor networks with nonuniform node distribution. IEEE T Parall Distr 2008; 19: 710-720.
[5] Basagni S, Carosi A, Melachrinoudis E, Petrioli C, Wang ZM. Controlled sink mobility for prolonging wireless sensor networks lifetime. Wirel Netw 2008; 14: 831-858.
[6] Altnel _ IK, Aras N, Guney E, Ersoy C. Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks. Comput Netw 2008; 52: 2419-2431.
[7] Wang ZM, Basagni S, Melachrinoudis E, Petrioli C. Exploiting sink mobility for maximizing sensor networks lifetime. In: 38th Annual Hawaii International Conference on System Sciences; 3{6 January, 2005; Big Island, HI, USA. IEEE. p. 287a.
[8] Basagni S, Carosi A, Petrioli C, Phillips CA. Coordinated and controlled mobility of multiple sinks for maximizing the lifetime of wireless sensor networks. Wirel Netw 2011; 17: 759-778.
[9] Keskin ME, Altnel _ IK, Aras N, Ersoy C. Lifetime maximization in wireless sensor networks using a mobile sink with nonzero traveling time. Comput J 2011; 54: 1987-1999.
[10] Gandham SR, Dawande M, Prakash R, Venkatesan S. Energy efficient schemes for wireless sensor networks with multiple mobile base stations. In: IEEE Global Telecommunications Conference; 1{5 December 2003; San Francisco, CA, USA. IEEE. pp. 377-381.
[11] Azad AP, Chockalingam A. Mobile base stations placement and energy aware routing in wireless sensor networks. In: IEEE Wireless Communications and Networking Conference; 3{6 April 2006; Las Vegas, NV, USA. IEEE. pp. 264-269.
[12] Alsalih W, Akl S, Hassanein, H. Placement of multiple mobile base stations in wireless sensor networks. In: IEEE International Symposium on Signal Processing and Information Technology; 15{18 December 2007; Cairo, Egypt. IEEE. pp. 229-233.
[13] Jun L, Hubaux JP. Joint mobility and routing for lifetime elongation in wireless sensor networks. In: Annual Joint Conference of the IEEE Computer and Communications Societies; 13{17 March 2007; Miami, FL, USA. IEEE. pp. 1735-1746.
[14] Papadimitriou I, Georgiadis L. Maximum lifetime routing to mobile sink in wireless sensor networks. In: 15{17 September 2005; Split, Marina Frapa, Croatia. IEEE. pp. 1-5.
[15] Gatzianas M, Georgiadis L. A distributed algorithm for maximum lifetime routing in sensor networks with mobile sink. IEEE T Wirel Commun 2008; 7: 984-994.
[16] Yun Y, Xia Y. Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applica- tions. IEEE T Mobile Comput 2010; 9: 1308-1318.
[17] Yun Y, Xia Y, Behdani B, Smith JC. Distributed algorithm for lifetime maximization in a delay-tolerant wireless sensor network with a mobile sink. IEEE T Mobile Comput 2013; 12: 1920-1930.
[18] Behdani B, Yun YS, Smith JC, Xia Y. Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks. Comput Oper Res 2012; 39: 1054-1061.
[19] Guney E, Aras N, Altnel _ IK, Ersoy C. Efficient integer programming formulations for optimum sink location and routing in heterogeneous wireless sensor networks. Comput Netw 2010; 54: 1805-1822.
[20] Luo J, Hubaux JP. Joint sink mobility and routing to maximize the lifetime of wireless sensor networks: the case of constrained mobility. IEEE ACM T Network 2010; 18: 871-884.
[21] Guney E, Aras N, Altnel _ IK, Ersoy C. Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks. Comput Netw 2012; 39: 1530-1539.
[22] Turkogullar YB, Aras N, Altnel _ IK, Ersoy C. Optimal placement, scheduling, and routing to maximize lifetime in sensor networks. J Oper Res Soc 2010; 61: 1000-1012.
[23] Turkogullar YB, Aras N, Altnel _ IK, Ersoy C. A column generation based heuristic for sensor placement, activity scheduling and data routing in wireless sensor networks. Eur J Oper Res 2010; 207: 1014-1026.
[24] Turkogullar YB, Aras N, Altnel _ IK, Ersoy C. An efficient heuristic for placement, scheduling and routing in wireless sensor networks. Ad Hoc Netw 2010; 8: 654-667.
[25] Keskin ME, Altnel _ IK, Aras N, Ersoy C. Wireless sensor network lifetime maximization by optimal sensor deploy- ment, activity scheduling, data routing and sink mobility. Ad Hoc Netw 2014; 17: 18-36.
[26] Keskin ME, Altnel _ IK, Aras N, Ersoy C. Wireless sensor network design by lifetime maximisation: an empirical evaluation of integrating major design issues and sink mobility. Int J Sens Netw 2016; 20: 131-146.
[27] Keskin ME. A column generation heuristic for optimal wireless sensor network design with mobile sinks. Eur J Oper Res 2017; 260: 291-304.
[28] Khalily M, Shamsi M, Nadja -Arani MJ. A convex optimization model for topology control in network-coding-based wireless sensor networks. Ad Hoc Netw 2017; 59: 1-11
[29] Heinzelman WR, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsen- sor networks. In: 33rd Annual Hawaii International Conference on System Sciences; 4{7 January, 2000; Big Island, HI, USA. IEEE. pp. 1-10.
[30] Levis P, Lee N, Welsh M, Culler D. TOSSIM: Accurate and scalable simulation of entire TinyOS applications. In: International Conference on Embedded Networked Sensor Systems; 5{7 November 2003; Los Angeles, CA, USA. ACM. pp. 126-137.
[31] Varga A, Hornig R. An overview of the OMNeT++ simulation environment. In: International Conference on Simulation Tools and Techniques for Communications, Networks and Systems & Workshops; 3{7 March 2008; Marseilles, France. Brussels, Belgium: ICST. pp. 60-70.