Runwei Zhang
ABSTRACT
Energy efficiency of wireless sensor networks (WSNs) can be improved by moving base stations (BSs), as this scheme evenly distributes the communication load in the network. However, physically moving the BSs is complicated and costly. In this paper, we propose a new scheme: virtually moving the BSs. We deploy an excessive number of BSs and adaptively re-select a subset of active BSs so as to emulate the physical movement. Beyond achieving high energy-efficiency, this scheme obviates the difficulties associated with physically moving the BSs.
The challenges are (i) that the energy efficiency of BSs should be considered as well, in addition to that of the sensor nodes and (ii) that the number of candidate subset of active BSs is exponential with the number of BSs. We show that scheduling the virtual movement of BSs is NP-hard. Then, we propose a polynomial-time algorithm that is guaranteed under mild conditions to achieve a lifetime longer than 62% of the optimal one. In practice, as verified through extensive numerical simulations, the lifetime achieved by the proposed algorithm is always very close to the optimum.
- G. Barrenetxea, B. Berefull-Lozano, and M. Vetterli. Lattice networks: capacity limits, optimal routing, and queueing behavior. Networking, IEEE/ACM Transactions on, 14(3):492--505, June 2006. Google Scholar
Digital Library
- S. Basagni, A. Carosi, E. Melachrinoudis, C. Petrioli, and Z. M. Wang. Controlled sink mobility for prolonging wireless sensor networks lifetime. Wirel. Netw., 14(6):831--858, Dec. 2008. Google ScholarDigital Library
- L. Ben Saad and B. Tourancheau. Multiple mobile sinks positioning in wireless sensor networks for buildings. In Sensor Technologies and Applications, 2009. SENSORCOMM., June 2009. Google ScholarDigital Library
- Y. Bi, L. Sun, J. Ma, N. Li, I. Khan, and C. Chen. Hums: An autonomous moving strategy for mobile sinks in data-gathering sensor networks. Eurasip Journal on Wireless Communications and Networking, 2007.Google ScholarCross Ref
- A. Bogdanov, E. Maneva, and S. Riesenfeld. Power-aware base station positioning for sensor networks. In INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, 2004.Google ScholarCross Ref
- A. Z. Broder, A. M. Frieze, and E. Upfal. On the satisfiability and maximum satisfiability of random 3-cnf formulas. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 322--330, 1993. Google ScholarDigital Library
- J.-H. Chang and L. Tassiulas. Maximum lifetime routing in wireless sensor networks. Networking, IEEE/ACM Transactions on, 12(4):609--619, Aug 2004. Google ScholarDigital Library
- M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1--2):95--110, 1956.Google Scholar
- S. Gandham, M. Dawande, R. Prakash, and S. Venkatesan. Energy efficient schemes for wireless sensor networks with multiple mobile base stations. In IEEE Global Telecommunications Conference 2003.Google ScholarCross Ref
- N. Garg and J. Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput., 37(2):630--652, May 2007. Google ScholarDigital Library
- P. Gonzalez-Brevis, J. Gondzio, Y. Fan, H. Poor, J. Thompson, I. Krikidis, and P.-J. Chung. Base station location optimization for minimal energy consumption in wireless networks. IEEE Vehicular Technology Conference, 2011.Google Scholar
- K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp. J. ACM, 50(6):795--824, Nov. 2003. Google ScholarDigital Library
- J. Luo and J. Hubaux. Joint mobility and routing for lifetime elongation in wireless sensor networks. 2005. 24th Annual Joint Conference of the INFOCOM, 2005.Google Scholar
- J. Luo and J.-P. Hubaux. Joint sink mobility and routing to maximize the lifetime of wireless sensor networks: The case of constrained mobility. IEEE/ACM Trans. Netw., 18(3):871--884, June 2010. Google ScholarDigital Library
- Y. Shi and Y. Hou. Some fundamental results on base station movement problem for wireless sensor networks. IEEE/ACM Trans. Netw., 2011.Google Scholar
- Y. Tanaka, S. Imahori, M. Sasaki, and M. Yagiura. An lp-based heuristic algorithm for the node capacitated in-tree packing problem. Computers and Operations Research, 39(3):637--646, 2012. Google ScholarDigital Library
- Z. Vincze, R. Vida, and A. Vidacs. Deploying multiple sinks in multi-hop wireless sensor networks. In Pervasive Services, IEEE International Conference on, pages 55--63, july 2007.Google Scholar
- Y. Yun and Y. Xia. Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications. Mobile Computing, IEEE Transactions on, 9(9):1308--1318, Sept 2010. Google ScholarDigital Library
- R. Zhang, F. Ingelrest, G. Barrenetxea, P. Thiran, and M. Vetterli. The beauty of the commons: Optimal load sharing by base station hopping in wireless sensor networks. Selected Areas in Communications, IEEE Journal on, PP(99):1--1, 2015.Google Scholar
- R. Zhang, P. Thiran, and M. Vetterli. Virtually Moving Base Stations for Energy Efficiency in Wireless Sensor Networks. Technical report, http://infoscience.epfl.ch/record/206994.Google Scholar
- G. Zussman and A. Segall. Energy efficient routing in ad hoc disaster recovery networks. In INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies, volume 1, pages 682--691 vol.1, March 2003.Google ScholarCross Ref
Index Terms
- Virtually Moving Base Stations for Energy Efficiency in Wireless Sensor Networks
Recommendations
An energy efficient clustering method for wireless sensor networks
EHAC'07: Proceedings of the 6th WSEAS International Conference on Electronics, Hardware, Wireless and Optical CommunicationsWireless sensor networks have many sensor nodes with a limited energy in a limited area. One of key issues in wireless sensor networks is to prolong the network lifetime. In this paper, we propose a scheme to construct an energy-efficient cluster ...
Energy consumption considerations in dynamic wireless sensor networks with nodes and base stations mobility
Energy conservation is a critical issue in the design of sensor networks since the sensor nodes are battery-powered. This paper proposes a wireless sensor network with mobile sensor nodes and base stations to prolong the network lifetime. The movement ...
An energy efficient clustering method for wireless sensor networks
EHAC'07: Proceedings of the 6th WSEAS International Conference on Electronics, Hardware, Wireless and Optical CommunicationsWireless sensor networks have many sensor nodes with a limited energy in a limited area. One of key issues in wireless sensor networks is to prolong the network lifetime. In this paper, we propose a scheme to construct an energy-efficient cluster ...
Comments