Energy conservation algorithms for maintaining coverage and connectivity in wireless sensor networks

L. Liu; B. Hu; L. Li

Energy conservation algorithms for maintaining coverage and connectivity in wireless sensor networks

Access Full Text

Energy conservation algorithms for maintaining coverage and connectivity in wireless sensor networks

Author(s): L. Liu ; B. Hu ; L. Li
DOI: 10.1049/iet-com.2009.0129

For access to this article, please select a purchase option:

Buy article PDF

Buy Knowledge Pack

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership

Recommend Title Publication to library

IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Author(s): L. Liu ¹ ; B. Hu ^{1, 2} ; L. Li ^{1, 3}
- Affiliations: 1: School of Information Science and Engineering, Lanzhou University, Lanzhou, People's Republic of China
  2: Department of Computing, Birmingham City University, Birmingham, UK
  3: School of Computer and Information, Hefei University of Technology, Hefei, People's Republic of China
Source: Volume 4, Issue 7, 30 April 2010, p. 786 – 800
DOI: 10.1049/iet-com.2009.0129 , Print ISSN 1751-8628, Online ISSN 1751-8636

Published

Energy conservation, coverage and connectivity are three critical application requirements in wireless sensor networks, especially in sensor networks for vehicular applications. Related researches have either concerned coverage, connectivity and energy conservation separately or required sensing/transmission range restrictions. In this study, the authors aim to maximise the network lifetime by redundant sensor nodes, while maintaining coverage and connectivity simultaneously, without any sensing or transmission range restriction. We propose maximum disjoint sets for maintaining coverage and connectivity (MDS-MCC) problem and the authors prove it is NP-complete. We also present two algorithms to solve MDS-MCC, Heuristic Algorithm and Network Flow Algorithm. We analyse and compare the performance of these two algorithms through simulations. According to several metrics, the authors give some suggestions of designing a sensor network. Furthermore, we study MDS-MCC problem under some special conditions, and an important theoretical result is obtained while designing a sensor network. As well as aiming to design an energy conservation sensor network, the present work can also be applied in applications requiring fault tolerance by redundancy.

References

1. 1)
  - Ye, F., Zhong, G., Lu, S., Zhang, L.: `Energy efficient robust sensing coverage in large sensor networks', Technical Report, , http://www.cs.ucla.edu/~yefan/coverage-tech-report.ps, accessed October 2002.
2. 2)
  - Cheriyan, J., Vempala, S., Vetta, A.: `Approximation algorithms for minimum-cost ', Proc. 34th Annual ACM Symp. the Theory of Computing, 2002, ACM, p. 306–312.
3. 3)
  - Estrin, D., Govindan, R., Heidemann, J., Kumar, S.: `Next century challenges: scalable coordination in sensor networks', Proc. ACM Int. Conf. Mobile Computing and Networking (MOBICOM99), 1999, Washington, p. 263–270.
4. 4)
  - M. Cardei , D.-Z. Du . Improving wireless sensor network lifetime through power aware organization. Wirel. Netw. , 3 , 333 - 340
5. 5)
  - M. Cardei , D. MacCallum , X. Cheng , M. Min , X. Jia , D. Li , D.-Z. Du . Wireless sensor networks with energy efficient organization. J. Interconnection Netw. , 213 - 229
6. 6)
  - I.F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci . (2003) Wireless sensor networks: a survey’, computer networks.
7. 7)
  - Kortsarz, G., Nutov, Z.: `Approximating node connectivity problems via set covers', Proc. Third Int. workshop Approximation Algorithms for Combinatorial Optimization (APPROX), 2000, Springer, p. 194–205.
8. 8)
  - D. Culler , D. Estrin , M. Srivastava . Overview of wireless sensor networks. IEEE Computer , 41 - 49
9. 9)
  - S. Khuller , R. Thurimella . Approximation algorithms for graph augmentation. J. Algorithms , 2 , 214 - 225
10. 10)
  - H. Li , H. Miao , L. Liu , L. Li , H. Zhang . Energy conservation in wireless sensor networks and connectivity of graphs. Theor. Comput. Sci. , 81 - 89
11. 11)
  - Kar, K., Banerjee, S.: `Node placement for connected coverage in sensor networks', Proc. WiOpt 2003: Modeling Optimization Mobile, Ad Hoc Wireless Networks, March 2003, p. 50–52.
12. 12)
  - M. Cardei , S. Yang , J. Wu . Algorithms for fault-tolerant topology in heterogeneous wireless sensor networks. IEEE Trans. Parallel Distrib. Syst. , 3 , 545 - 558
13. 13)
  - F. Harary . (1969) Graph theory.
14. 14)
  - Xu, Y., Heidemann, J., Estrin, D.: `Geography-informed energy conservation for ad hoc routing', Proc. ACM Int. Conf. Mobile Computing and Networking (MOBICOM01), 2001, Italy, p. 70–84.
15. 15)
  - X. Jia , D. Kim , S. Makki , P. Wan , C. Yi . Power assignment for k-connectivity in wireless ad hoc networks. J. Combinat. Optim. , 2 , 213 - 222
16. 16)
  - Wang, X., Xing, G., Zhang, Y., Lu, C., Pless, R., Gill, C.D.: `Integrated coverage and connectivity configuration in wireless sensor networks', Proc. First ACM Conf. Embedded Networked Sensor System, November 2003, p. 28–39.
17. 17)
  - Zhang, H., Hou, J.C.: `Maintaining sensing coverage and connectivity in large sensor networks', Technical Report UIUC, 2003.
18. 18)
  - D. Tian , N.D. Georganas . A node scheduling scheme for energy conservation in large wireless sensor networks. Wirel. Commun. Mobile Comput. , 2 , 271 - 290
19. 19)
  - F. Ingelrest , D. Simplot-Ryl , I. Stojmenovic . Optimal transmission radius for energy efficient broadcasting protocol in ad hoc and sensor networks. IEEE Trans. Parallel Distrib. Syst. , 6 , 536 - 547
20. 20)
  - F. Lin , P.L. Chiu . A near-optimal sensor placement algorithm to achieve complete coverage/discrimination in sensor networks. IEEE Commun. Lett. , 1 , 43 - 45
21. 21)
  - Heizelman, W.R., Chandrakasan, A., Balakrishnan, H.: `Energy-efficient communication protocol for wireless micro sensor networks', IEEE Proc. Hawaii Int. Conf. System Sciences, 2000, p. 1–10.
22. 22)
  - Williams, B., Camp, T.: `Comparison of broadcasting techniques for mobile ad hoc networks', Proc. ACM Int. Symp. Mobile Ad Hoc Networking Computing (MOBIHOC), 2002, p. 194C205.
23. 23)
  - Ghosh, A., Wang, Y., Krishnamachari, B.: `Efficient distributed topology control in 3-dimensional wireless networks', Fourth Annual IEEE Communications Society Conf. Sensor, Mesh and Ad Hoc Communications and Networks (SECON), June 2007, p. 91–100.
24. 24)
  - Gabow, H.N.: `A representation for crossing set families with applications to submodular flow problems', Proc. 4th ACMSIAM Symposium on Discrete Algorithms, 1993, Austin, TX, p. 202–211.
25. 25)
  - S. Even , R.E. Tarjan . Network flow and testing graph connectivity. SIAM J. Comput. , 507 - 518
26. 26)
  - S. Papavassiliou , J. Zhu . (2005) Architecture and modeling of dynamic wireless sensor networks. Handbook of sensor networks: compact wireless and wired sensing systems.
27. 27)
  - A. Frank , E. Tardos . An application of submodular flows. Linear Algebr. Appl. , 329 - 348
28. 28)
  - K. Chakrabarty , S.S. Lyengar , H. Qi , E. Cho . Grid coverage for surveillance and target location in distributed sensor networks. IEEE Trans. Comput. , 12 , 1448 - 1453
29. 29)
  - Slijepcevic, S., Potkonjak, M.: `Power efficient organization of wireless sensor networks', Proc IEEE Int. Conf. Communications, June 2001, p. 472–476.

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Energy conservation algorithms for maintaining coverage and connectivity in wireless sensor networks

Energy conservation algorithms for maintaining coverage and connectivity in wireless sensor networks

Buy article PDF

Buy Knowledge Pack

Thank you

References

Related content