Maximizing the Lifetime of Query-Based Wireless Sensor Networks

Abstract

We consider the problem of maximizing the lifetime of a query-based wireless sensor network in which all of the sensor nodes are both producers and consumers of network resources. Of particular concern is the problem of selecting a common transmission range for all of the sensor nodes, the resource replication level (or time-to-live counter), and the active/sleep schedule of nodes while satisfying connectivity and quality-of-service constraints. To this end, we first formulate a general, mixed-integer programming model that selects the optimal operating parameters in each period of a finite planning horizon. Subsequently, we examine in detail specific connectivity and quality-of-service constraints that can be considered within this framework. Due to the complexity of the model, we formulate an alternative linearized version that can be solved more efficiently. Additionally, we devise a simple algorithm to solve a special case of the problem when alive nodes are always active. Computational results indicate that the maximum attainable lifetime can be significantly improved by adjusting the key operating parameters as sensor nodes fail over time due to energy depletion.

References

1. J. Ahn and B. Krishnamachari. 2006a. Derivations of the expected energy costs of search and replication in wireless sensor networks. Tech. rep. CENG-2006-3, Computer Engineering, University of Southern California.
2. J. Ahn and B. Krishnamachari. 2006b. Fundamental scaling laws for energy-efficient storage and querying in wireless sensor networks. In Proceedings of the 7^th ACM International Symposium on Mobile Ad Hoc Networking and Computing. 334--343.
3. J. Ahn and B. Krishnamachari. 2007. Modeling search costs in wireless sensor networks. In Proceedings of the 5^th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. 1--6.
4. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. 2002. Wireless sensor networks: A survey. Comput. Netw. 38, 4, 393--422.
5. J. N. Al-Karaki and A. E. Kamal. 2004. Routing techniques in wireless sensor networks: A survey. IEEE Wirel. Comm. 11, 6--28.
6. G. Anastasi, M. Conti, M. D. Francesco, and A. Passarella. 2009. Energy conservation in wireless sensor networks: A survey. Ad Hoc Netw. 7, 4, 537--568.
7. Y. P. Aneja, R. Chandrasekaran, X. Li, and K. P. K. Nair. 2010. A branch-and-cut algorithm for the strong minimum energy topology in wireless sensor networks. Euro. J. Oper. Res. 204, 3, 604--612.
8. B. Ata. 2005. Dynamic power control in a wireless static channel subject to a quality-of-service constraint. Oper. Res. 53, 5, 842--851.
9. B. Behdani, J. Smith, and Y. Xia. 2013. The lifetime maximization problem in wireless sensor networks with a mobile sink: MIP formulations and algorithms. IIE Trans. 45, 10, 1094--1113.
10. B. Behdani, Y. Yun, J. Smith, and Y. Xia. 2012. Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks. Comput. Oper. Res. 39, 5, 1054--1061.
11. P. Bellavista, A. Corradi, and E. Magisretti. 2005. Comparing and evaluating lightweight solutions for replica dissemination and retrieval in dense manets. In Proceedings of the 10^th IEEE Symposium on Computers and Communications. 43--50.
12. C. Bettstetter. 2002. On the minimum node degree and connectivity of a wireless multihop network. In Proceedings of the 3^rd ACM International Symposium on Mobile Ad Hoc Networking and Computing. 80--91.
13. C. Bettstetter. 2004. On the connectivity of ad hoc networks. The Comput. J. 47, 4, 432--447.
14. R. Cerulli, R. Dedonato, and A. Raiconi. 2012. Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges. Euro. J. Oper. Res. 220, 1, 58--66.
15. I. R. Chen, A. P. Speer, and M. Eltoweissy. 2011. Adaptive fault tolerant qos control algorithms for maximizing system lifetime of query-based wireless sensor networks. IEEE Trans. Depend. Secure Comput. 8, 2, 161--176.
16. P. Chen, B. O'dea, and E. Callaway. 2002. Energy efficient system design with optimum transmission range for wireless ad hoc networks. In Proceedings of the IEEE International Conference on Communications (ICC'02). Vol. 2. 945--952.
17. C. F. Chiasserini, R. Gaeta, M. Garetto, M. Gribaudo, D. Manini, and M. Sereno. 2007. Fluid models for large-scale wireless sensor networks. Perform. Eval. 64, 7--8, 715--736.
18. CPLEX. 2011. IBM ilog: CPLEX. http://www.ilog.com/products/cplex.
19. G. Degirmenci, J. P. Kharoufeh, and R. O. Baldwin. 2013. On the performance evaluation of querybased wireless sensor networks. Perform. Eval. 70, 2, 124--147.
20. J. Deng, Y. S. Han, P. Chen, and P. K. Varshney. 2004. Optimum transmission range for wireless ad hoc networks. Electrical Engin. Comput. Sci. 2, 1024--1029.
21. I. Dietrich and F. Dressler. 2009. On the lifetime of wireless sensor networks. ACM Trans. Sensor Netw. 5, 1, 1--39.
22. P. Diggle. 2003. Statistical Analysis of Spatial Point Patterns. Arnold, London.
23. F. Flammini, A. Gaglione, F. Ottello, A. P. C. Pragliola, and A. Tedesco. 2010. Towards wireless sensor networks for railway infrastructure monitoring. In Proceedings of the Conference on Electrical Systems for Aircraft, Railway and Ship Propulsion (ESARS'10). 1--6.
24. Q. Gao, K. J. Blow, D. J. Holding, I. W. Marshall, and X. H. Peng. 2006. Radio range adjustment for energy efficient wireless sensor networks. Ad Hoc Netw. 4, 1, 75--82.
25. V. C. Gungor and G. P. Hancke. 2009. Industrial wireless sensor networks: Challenges, design principles, and technical approaches. IEEE Trans. Industr. Electron. 56, 10, 4258--4265.
26. R. W. Ha, P. H. Ho, X. S. Shen, and J. Zhang. 2006. Sleep scheduling for wireless sensor networks via network flow model. Comput. Comm. 29, 13--14, 2469--2481.
27. C. Herring and S. Kaplan. 2000. Component-based software systems for smart environments. IEEE Personal Comm. 7, 5, 60--61.
28. D. S. Hochbaum. 1995. A nonlinear knapsack problem. Oper. Res. Lett. 17, 3, 103--110.
29. B. Krishnamachari and J. Ahn. 2006. Optimizing data replication for expanding ring-based queries in wireless sensor networks. In Proceedings of the 4^th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. 1--10.
30. J. Liu, X. Jiang, S. Horiguchi, and T. T. Lee. 2010. Analysis of random sleep scheme for wireless sensor networks. Int. J. Sensor Netw. 7, 1, 71--84.
31. A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson. 2002. Wireless sensor networks for habitat monitoring. In Proceedings of the 1^st ACM International Workshop on Wireless Sensor Networks and Applications. 88--97.
32. C. R. Mann, R. O. Baldwin, J. P. Kharoufeh, and B. E. Mullins. 2007. A trajectory-based selective broadcast query protocol for large-scale, high-density wireless sensor networks. Telecomm. Syst. 35, 1--2, 67--86.
33. C. R. Mann, R. O. Baldwin, J. P. Kharoufeh, and B. E. Mullins. 2008. A queueing approach to optimal resource replication in wireless sensor networks. Perform. Eval. 65, 10, 689--700.
34. A. Milenkovic, C. Otto, and E. Jovanov. 2006. Wireless sensor networks for personal health monitoring: Issues and an implementation. Comput. Comm. 29, 13--14, 2521--2533.
35. H. Miranda, S. Leggio, L. Rodrigues, and K. Raatikainen. 2007. An algorithm for dissemination and retrieval of information in wireless ad hoc networks. In Proceedings of the 13^th International Euro-Par Conference (Euro-Par'07). 891--900.
36. A. Mishra, F. M. Gondal, A. A. Afrashteh, R. R. Wilson, R. D. Moffitt, R. K. Kapania, and S. Bland. 2006. Embedded wireless sensors for aircraft/automobile tire structural health monitoring. In Proceedings of the 2^nd IEEE Workshop on Wireless Mesh Networks. 163--165.
37. D. Niyato, E. Hossain, and A. Fallahi. 2007. Sleep and wakeup strategies in solar-powered wireless sensor/mesh networks: Performance analysis and optimization. IEEE Trans. Mobile Comput. 6, 2, 221--236.
38. I. Papadimitriou and L. Georgiadis. 2005. Maximum lifetime routing to mobile sink in wireless sensor networks. In Proceedings of the 13^th IEEE Software, Telecommunications and Computer Networks Conference (SoftCOM'05).
39. L. Rodero-Merino, A. F. Anta, L. Lopez, and V. Cholvi. 2010. Performance of random walks in one-hop replication networks. Comput. Netw. 54, 781--796.
40. M. Sarkar and R. L. Cruz. 2004. Analysis of power management for energy and delay trade-off in a wlan. In Proceedings of the Conference on Information Sciences and Systems.
41. C. Schurgers and M. B. Srivastava. 2001. Energy efficient routing in wireless sensor networks. In Proceedings of the IEEE Military Communications Conference. 357--361.
42. A. Sinha and A. P. Chandrakasan. 2001. Dynamic power management in wireless sensor networks. IEEE Design Test Comput. Mag. 18, 2, 62--74.
43. Y. B. Turkogullari, N. Aras, I. K. Altinel, and C. Ersoy. 2010. Optimal placement, scheduling, and routing to maximize lifetime in sensor networks. J. Oper. Res. Soc. 61, 6, 1000--1012.
44. M. Welsh. 2004. Harvard sensor networks lab: Volcano monitoring. http://fiji.eecs.harvard.edu/Volcano.
45. X. Xing, G. Wang, J. Wu, and J. Li. 2009. Square region-based coverage and connectivity probability model in wireless sensor networks. In Proceedings of the 5^th International Conference on Collaborative Computing: Networking, Applications and Worksharing. 1--8.
46. W. Ye, J. Heidemann, and D. Estrin. 2004. Medium access control with coordinated adaptive sleeping for wireless sensor networks. IEEE/ACM Trans. Netw. 12, 3, 493--506.
47. Y. Yun and Y. Xia. 2010. Maximizing the lifetime of wireless sensor networks with mobile sink in delay tolerant applications. IEEE Trans. Mobile Comput. 9, 9, 1308--1318.
48. Y. Yun, Y. Xia, B. Behdani, and J. Smith. 2013. Distributed algorithm for lifetime maximization in delay-tolerant wireless sensor network with mobile sink. IEEE Trans. Mobile Comput. 12, 10, 1920--1930.
49. Z. Zhang, G. Mao, and B. Anderson. 2010. On the effective energy consumption in wireless sensor networks. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC'10). 1--6.

Index Terms

• Networks

  • Network protocols