350Accesses
Abstract
A major challenge in wireless underground sensor networks is the signal attenuation originated from multi-environment transmission between underground sensor nodes and the above-ground base station. To overcome this issue, an efficient approach is deploying a set of relay nodes aboveground, thereby reducing transmission loss by shortening transmitting distance. However, this introduces several new challenges, including load balancing and transmission loss minimization. This paper tackles the problem of deploying relay nodes to reduce transmission loss under a load balancing constraint by proposing two approximation algorithms. The first algorithm is inspired by Beam Search, combined with a new selection scheme based on Boltzmann distribution. The second algorithm aims to further improve the solutions obtained by the former by reducing the transmission loss. We observe that we can find an optimal assignment between sensor nodes and a set of the chosen relay in polynomial time by reformulating the part of the problem as a bipartite matching problem with minimum cost. Experimental results indicate that the proposed methods perform better than the other existing ones in most of our test instances while reducing the execution time.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.








Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Akyildiz IF, Stuntebeck EP (2006) Wireless underground sensor networks: research challenges. Ad Hoc Netw 4(6):669–686
Yu X, Wu P, Han W, Zhang Z (2012) Overview of wireless underground sensor networks for agriculture. African Journal of Biotechnology 11(17):3942–3948
Parameswaran V, Zhou H, Zhang Z (2012) Irrigation control using wireless underground sensor networks. In: 2012 sixth international conference on sensing technology (ICST). IEEE, pp 653–659
Yu X, Wu P, Wang N, Han W, Zhang Z (2012) Survey on wireless sensor networks agricultural environment information monitoring. Journal of Computational Information Systems 8(19):7919–7926
Baggio A (2005) Wireless sensor networks in precision agriculture. In: ACM workshop on real-world wireless sensor networks (REALWSN 2005), vol 20. Citeseer, pp 1567–1576
Ball MG, Qela B, Wesolkowski S (2016) A review of the use of computational intelligence in the design of military surveillance networks. In: Recent advances in computational intelligence in defense and security. Springer, Berlin, pp 663–693
Noel AB, Abdaoui A, Elfouly T, Ahmed MH, Badawy A, Shehata MS (2017) Structural health monitoring using wireless sensor networks: a comprehensive survey. IEEE Communications Surveys & Tutorials 19(3):1403–1423
Mostafaei H (2018) Energy-efficient algorithm for reliable routing of wireless sensor networks. IEEE Trans Ind Electron 66(7):5567–5575
Singh SP, Sharma SC (2015) A survey on cluster based routing protocols in wireless sensor networks. Procedia Comput Sci 45:687–695
Paul A, Sato T (2017) Localization in wireless sensor networks: a survey on algorithms, measurement techniques, applications and challenges. Journal of Sensor and Actuator Networks 6(4):24
Yessad N, Omar M, Tari A, Bouabdallah A (2018) Qos-based routing in wireless body area networks: a survey and taxonomy. Computing 100(3):245–275
Khan I, Belqasmi F, Glitho R, Crespi N, Morrow M, Polakos P (2015) Wireless sensor network virtualization: a survey. IEEE Communications Surveys & Tutorials 18(1):553–576
Dhand G, Tyagi SS (2016) Data aggregation techniques in wsn: survey. Procedia Comput Sci 92:378–384
Yetgin H, Cheung KTK, El-Hajjar M, Hanzo LH (2017) A survey of network lifetime maximization techniques in wireless sensor networks. IEEE Communications Surveys & Tutorials 19(2):828–854
Ghaffari A (2015) Congestion control mechanisms in wireless sensor networks: a survey. J Netw Comput Appl 52:101–115
Dutta N, Saxena A, Chellappan S (2010) Defending wireless sensor networks against adversarial localization. In: 2010 eleventh international conference on mobile data management. IEEE, pp 336–341
Min J, Kim J, Kwon Y, Lee Y (2012) Multi-channel mac protocol for real-time monitoring of weapon flight test in wireless sensor network. In: Proceedings of the sixth international conference on sensor technologies and applications, pp 83–88
Basagni S, Carosi A, Petrioli C, Phillips CA (2009) Heuristics for lifetime maximization in wireless sensor networks with multiple mobile sinks. In: 2009 IEEE international conference on communications. IEEE, pp 1–6
Behdani B, Smith JC, Ye X (2013) The lifetime maximization problem in wireless sensor networks with a mobile sink: mixed-integer programming formulations and algorithms. IIE Trans 45(10):1094–1113
Akyildiz IF, Sun Z, Vuran MC (2009) Signal propagation techniques for wireless underground communication networks. Phys Commun 2(3):167–183
Akkaş MA, Akyildiz IF, Sokullu R (2012) Terahertz channel modeling of underground sensor networks in oil reservoirs. In: 2012 IEEE global communications conference (GLOBECOM). IEEE, p 2012
Akkaş MA, Sokullu R (2015) Wireless underground sensor networks: channel modeling and operation analysis in the terahertz band. International Journal of Antennas and Propagation, 2015
Miao G, Himayat N, Li Y, Swami A (2009) Cross-layer optimization for energy-efficient wireless communications: a survey. Wirel Commun Mob Comput 9(4):529–542
Al-Karaki JN, Kamal AE (2004) Routing techniques in wireless sensor networks: a survey. IEEE Wireless Communications 11(6):6–28
Yang Y, Fonoage MI, Cardei M (2010) Improving network lifetime with mobile wireless sensor networks. Computer Communications 33(4):409–419
Campobello G, Segreto A, Serrano S (2016) Data gathering techniques for wireless sensor networks: a comparison. Int J Distributed Sensor Netw 12(3):4156358
Tam NT, Binh HTT, Dung DA, Lan PN, Yuan B, Yao X et al (2019) A hybrid clustering and evolutionary approach for wireless underground sensor network lifetime maximization. Inf Sci 504:372–393
Bo Y, Chen H, Yao X (2017) Optimal relay placement for lifetime maximization in wireless underground sensor networks. Inf Sci 418:463–479
Tam NT, Binh HTT, Hung TH, Dung DA, et al. (2019) Prolong the network lifetime of wireless underground sensor networks by optimal relay node placement. In: International conference on the applications of evolutionary computation (Part of EvoStar). Springer, Berlin, pp 439–453
Pan J, Cai L, Hou YT, Yi S, Shen SX (2005) Optimal base-station locations in two-tiered wireless sensor networks. IEEE Transactions on Mobile Computing (5):458–473
Li L, Vuran MC, Akyildiz IF (2007) Characteristics of underground channel for wireless underground sensor networks. In: Proc. Med-Hoc-Net, vol 7, pp 13–15
Bari A, Jaekel A, Jiang J, Xu Y (2012) Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirements. Comput Commun 35(3):320–333
Gao Z, Chen K, Qiu X (2014) Relay node placement with base stations in wireless sensor networks fault-tolerant. Chin J Electron 23(4):794–800
Sitanayah L, Brown KN, Sreenan CJ (2014) A fault-tolerant relay placement algorithm for ensuring k vertex-disjoint shortest paths in wireless sensor networks. Ad Hoc Netw 23:145–162
Lee S, Younis M, Lee M (2015) Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance. Ad Hoc Netw 24:1–19
Liu L, Ma M, Liu C, Shu Y (2017) Optimal relay node placement and flow allocation in underwater acoustic sensor networks. IEEE Trans Commun 65(5):2141–2152
Liu L, Liu C, Shu Y, Ma M (2018) Optimal relay node placement for connectivity recovery in underwater acoustic sensor networks. In: 2018 IEEE international conference on information communication and signal processing (ICICSP). IEEE, pp 33–37
Su R, Venkatesan R, Li C (2015) An energy-efficient relay node selection scheme for underwater acoustic sensor networks. Cyber-Physical Systems 1(2-4):160–179
Whitley LD et al (1989) The genitor algorithm and selection pressure: why rank-based allocation of reproductive trials is best. In: Icga. Fairfax, VA, vol 89, pp 116–123
Croce FD, Ghirardi M, Tadei R (2004) Recovering beam search: enhancing the beam search approach for combinatorial optimization problems. J Heuristics 10(1):89–104
Ponte A, Paquete L, Figueira JR (2012) On beam search for multicriteria combinatorial optimization problems. In: International conference on integration of artificial intelligence (AI) and operations research (OR) techniques in constraint programming. Springer, Berlin, pp 307–321
Bach A (1990) Boltzmann’s probability distribution of 1877. Arch Hist Exact Sci, pp 1–40
Thompson CJ (2015) Mathematical statistical mechanics. Princeton University Press, Princeton
Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. MIT Press, Cambridge
Acknowledgments
This research is funded by the VNU University of Science under project number TN.19.02 and by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 102.01-2019.304. This research is supported by the Domestic Master/ PhD Scholarship Programme of Vingroup Innovation Foundation.
Author information
Authors and Affiliations
Hanoi University of Science and Technology, Hanoi, Vietnam
Nguyen Thi Tam, Dinh Anh Dung, Tran Huy Hung & Huynh Thi Thanh Binh
VNU University of Science, Hanoi, Vietnam
Nguyen Thi Tam
University Technology of Sydney, Ultimo, NSW, 2007, Australia
Shui Yu
- Nguyen Thi Tam
You can also search for this author inPubMed Google Scholar
- Dinh Anh Dung
You can also search for this author inPubMed Google Scholar
- Tran Huy Hung
You can also search for this author inPubMed Google Scholar
- Huynh Thi Thanh Binh
You can also search for this author inPubMed Google Scholar
- Shui Yu
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toHuynh Thi Thanh Binh.
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Tam, N.T., Dung, D.A., Hung, T.H.et al. Exploiting relay nodes for maximizing wireless underground sensor network lifetime.Appl Intell50, 4568–4585 (2020). https://doi.org/10.1007/s10489-020-01735-y
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative