AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

Approximation Designs for Energy Harvesting Relay Deployment in Wireless Sensor Networks

School of Modern Posts, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China
ByteDance Inc., Shanghai 201100, China
Key Laboratory of Artificial Intelligence of Ministry of Education, Department of Computer Science and Engineering Shanghai Jiao Tong University, Shanghai 200240, China
Show Author Information

Abstract

Energy harvesting technologies allow wireless devices to be recharged by the surrounding environment, providing wireless sensor networks (WSNs) with higher performance and longer lifetime. However, directly building a wireless sensor network with energy harvesting nodes is very costly. A compromise is upgrading existing networks with energy harvesting technologies. In this paper, we focus on prolonging the lifetime of WSNs with the help of energy harvesting relays (EHRs). EHRs are responsible for forwarding data for sensor nodes, allowing them to become terminals and thus extending their lifetime. We aim to deploy a minimum number of relays covering the whole network. As EHRs have several special properties such as the energy harvesting and depletion rate, it brings great research challenges to seek an optimal deployment strategy. To this end, we propose an approximation algorithm named Effective Relay Deployment Algorithm, which can be divided into two phases: disk covering and connector insertion using the partitioning technique and the Steinerization technique, respectively. Based on probabilistic analysis, we further optimize the performance ratio of our algorithm to (5 + 6/K) where K is an integer denoting the side length of a cell after partitioning. Our extensive simulation results show that our algorithm can reduce the number of EHRs to be deployed by up to 45% compared with previous work and thus validate the efficiency and effectiveness of our solution.

Keywords

energy harvestingapproximation algorithmwireless sensor networkconstraint relay deployment

Electronic Supplementary Material

Download File(s)
1964_ESM.pdf (272.2 KB)

References

[1]
Wahyono I, Asfani K, Mohamad M, Rosyid H, Afandi A, Aripriharta. The new intelligent wireless sensor network using artificial intelligence for building fire disasters. In Proc. the 3rd International Conference on Vocational Education and Electrical Engineering, October 2020. DOI: 10.1109/ICVEE50212.2020.9243210.
[2]
Feng S, Shi H, Huang L, Shen S, Yu S, Peng H, Wu C. Unknown hostile environment-oriented autonomous WSN deployment using a mobile robot. Journal of Network and Computer Applications, 2021, 182: Article No. 103053. DOI: 10.1016/j.jnca.2021.103053.
[3]

Seo J, Park H. Forest environment monitoring application of intelligence embedded based on wireless sensor networks. KSⅡ Transactions on Internet and Information Systems, 2016, 10(4): 1555-1570. DOI: 10.3837/tiis.2016.04.005.
Crossref Google Scholar
[4]

Zhou Y, Liu L, Wang L, Hui N, Cui X, Wu J, Peng Y, Qi Y, Xing C. Service-aware 6G: An intelligent and open network based on the convergence of communication, computing and caching. Digital Communications and Networks, 2020, 6(3): 253-260. DOI: 10.1016/j.dcan.2020.05.003.
Crossref Google Scholar
[5]

Zhou Y, Tian L, Liu L, Qi Y. Fog computing enabled future mobile communication networks: A convergence of communication and computing. IEEE Communications Magazine, 2019, 57(5): 20-27. DOI: 10.1109/MCOM.2019.1800235.
Crossref Google Scholar
[6]

Zhou Y, Liu H, Pan Z, Tian L, Shi J. Cooperative multicast with location aware distributed mobile relay selection: Performance analysis and optimized design. IEEE Transactions on Vehicular Technology, 2017, 66(9): 8291-8302. DOI: 10.1109/TVT.2017.2682903.
Crossref Google Scholar
[7]
Hou Y, Shi Y, Sherali H, Midkiff S. Prolonging sensor network lifetime with energy provisioning and relay node placement. In Proc. the 2nd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, September 2005, pp. 295-304. DOI: 10.1109/SAHCN.2005.1557084.
[8]

Rahman M N, Matin M A. Efficient algorithm for prolonging network lifetime of wireless sensor networks. Tsinghua Science and Technology, 2011, 16(6): 561-568. DOI: 10.1016/S1007-0214(11)70075-X.
Crossref Google Scholar
[9]
Zhang W, Xue G, Misra S. Fault-tolerant relay node placement in wireless sensor networks: Problems and algorithms. In Proc. the 26th IEEE International Conference on Computer Communications, May 2007, pp. 1649-1657. DOI: 10.1109/INFCOM.2007.193.
[10]

Ku M L, Li W, Chen Y, Ray Liu K J. Advances in energy harvesting communications: Past, present, and future challenges. IEEE Communications Surveys Tutorials, 2016, 18(2): 1384-1412. DOI: 10.1109/COMST.2015.2497324.
Crossref Google Scholar
[11]
Atapattu S, Jiang H, Evans J, Tellambura C. Time-switching energy harvesting in relay networks. In Proc. the IEEE International Conference on Communications, June 2015, pp. 5416-5421. DOI: 10.1109/ICC.2015.7249185.
[12]
Ji B, Chen Z, Li Y, Chen S, Zheng G, Wen H. Energy harvesting and information transmission scheme with UAV relay cooperation. EURASIP Journal on Wireless Communications and Networking, 2019: Article No. 278. DOI: 10.1186/s13638-019-1598-7.
[13]

Sharma S, Roy S D, Kundu S. Secure communication with energy harvesting multiple half-duplex DF relays assisted with jamming. Wireless Networks, 2020, 26(2): 1151-1164. DOI: 10.1007/s11276-018-1859-0.
Crossref Google Scholar
[14]
Raghunathan V, Kansal A, Hsu J, Friedman J, Srivastava M B. Design considerations for solar energy harvesting wireless embedded systems. In Proc. the International Symposium on Information Processing in Sensor Networks, April 2005, pp. 457-462. DOI: 10.1109/IPSN.2005.1440973.
[15]

Meninger S, Mur-Miranda J O, Amirtharajah R, Chandrakasan A, Lang J H. Vibration-to-electric energy conversion. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2001, 9(1): 64-76. DOI: 10.1109/92.920820.
Crossref Google Scholar
[16]
He S, Wang W. Location-aware QoE-driven wireless relay deployment for energy efficient multimedia communications. In Proc. the 17th International Symposium on Web and Wireless Geographical Information Systems, May 2019, pp. 160-173. DOI: 10.1007/978-3-030-17246-613.
[17]

Zhao M, Zhao J, Zhou W, Zhu J, Zhang S. Energy efficiency optimization in relay-assisted networks with energy harvesting relay constraints. China Communications, 2015, 12(2): 84-94. DOI: 10.1109/CC.2015.7084404.
Crossref Google Scholar
[18]

In C, Kim H, Choi W. Achievable rate-energy region in two-way decode-and-forward energy harvesting relay systems. IEEE Transactions on Communications, 2019, 67(6): 3923-3935. DOI: 10.1109/TCOMM.2019.2901783.
Crossref Google Scholar
[19]
Bhowmick A, Chatterjee A, Verma T. Performance of DF relaying in an energy harvesting full duplex cognitive radio network. In Proc. the International Conference on Vision Towards Emerging Trends in Communication and Networking, March 2019. DOI: 10.1109/ViTECoN.2019.8899470.
[20]
Rao Y S, Madhukumar A S, Sirigina R P. RF energy harvesting based relays: Non-orthogonal AF vs dynamic DF. In Proc. the 20th International Symposium on Wireless Personal Multimedia Communications, December 2017, pp. 506-510. DOI: 10.1109/WPMC.2017.8301865.
[21]
Jiang D, Zheng H, Tang D, Tang Y. Relay selection and power allocation for cognitive energy harvesting two-way relaying networks. In Proc. the 5th IEEE International Conference on Electronics Information and Emergency Communication, May 2015, pp. 163-166. DOI: 10.1109/ICEIEC.2015.7284511.
[22]
Song X, Xu S. Joint optimal power allocation and relay selection in full-duplex energy harvesting relay networks. In Proc. the 10th International Conference on Communication Software and Networks, July 2018, pp. 80-84. DOI: 10.1109/ICCSN.2018.8488216.
[23]
Djenouri D, Bagaa M. Energy harvesting aware relay node addition for power-efficient coverage in wireless sensor networks. In Proc. the 2015 IEEE International Conference on Communications, June 2015, pp. 86-91. DOI: 10.1109/ICC.2015.7248303.
[24]

Zhu X, Li J, Zhou M. Optimal deployment of energy-harvesting directional sensor networks for target coverage. IEEE Systems Journal, 2019, 13(1): 377-388. DOI: 10.1109/JSYST.2018.2820085.
Crossref Google Scholar
[25]

Qiao G, Leng S, Zhang K, Yang K. Joint deployment and mobility management of energy harvesting small cells in heterogeneous networks. IEEE Access, 2017, 5: 183-196. DOI: 10.1109/ACCESS.2016.2635878.
Crossref Google Scholar
[26]

Verdonck L, Beullens P, Caris A, Ramaekers K, Janssens G K. Analysis of collaborative savings and cost allocation techniques for the cooperative carrier facility location problem. The Journal of the Operational Research Society, 2016, 67(6): 853-871. DOI: 10.1057/jors.2015.106.
Crossref Google Scholar
[27]
Wu S, Yang J, Peng R, Zhai Q. Optimal design of facility allocation and maintenance strategy for a cellular network. Reliability Engineering System Safety, 2021, 205: Article No. 107253. DOI: 10.1016/j.ress.2020.107253.
[28]

Garcia V, Zhou Y, Shi J. Coordinated multipoint transmission in dense cellular networks with user-centric adaptive clustering. IEEE Transactions on Wireless Communications, 2014, 13(8): 4297-4308. DOI: 10.1109/TWC.2014.2316500.
Crossref Google Scholar
[29]

Basappa M, Acharyya R, Das G K. Unit disk cover problem in 2D. Journal of Discrete Algorithms, 2015, 33: 193-201. DOI: 10.1016/j.jda.2015.05.002.
Crossref Google Scholar
[30]

Biniaz A, Liu P, Maheshwari A, Smid M. Approximation algorithms for the unit disk cover problem in 2D and 3D. Computational Geometry: Theory and Applications, 2017, 60: 8-18. DOI: 10.1016/j.comgeo.2016.04.002.
Crossref Google Scholar
[31]

Zhou Y, Liu H, Pan Z, Tian L, Shi J, Yang G. Two-stage cooperative multicast transmission with optimized power consumption and guaranteed coverage. IEEE Journal on Selected Areas in Communications, 2014, 32(2): 274-284. DOI: 10.1109/JSAC.2014.141208.
Crossref Google Scholar
[32]

Misra S, Majd N E, Huang H. Approximation algorithms for constrained relay node placement in energy harvesting wireless sensor networks. IEEE Transactions on Computers, 2014, 63(12): 2933-2947. DOI: 10.1109/TC.2013.171.
Crossref Google Scholar
[33]

Luo Y, Zhang J, Letaief K B. Optimal scheduling and power allocation for two-hop energy harvesting communication systems. IEEE Transactions on Wireless Communications, 2013, 12(9): 4729-4741. DOI: 10.1109/TW.2013.081413.122021.
Crossref Google Scholar
[34]
Misra S, Majd N E, Huang H. Constrained relay node placement in energy harvesting wireless sensor networks. In Proc. the 8th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems, October 2011, pp. 25-34. DOI: 10.1109/MASS.2011.137.
[35]
Xu S, Shen H. The fault-tolerant facility allocation problem. In Proc. the 20th International Symposium on Algorithms and Computation, December 2009, pp. 689-698. DOI: 10.1007/978-3-642-10631-6_70.
[36]

Tsao Y C, Mangotra D, Lu J C, Dong M. A continuous approximation approach for the integrated facility-inventory allocation problem. European Journal of Operational Research, 2012, 222(2): 216-228. DOI: 10.1016/j.ejor.2012.04.033.
Crossref Google Scholar
[37]
Chen W, Chen H, Zhao F. Energy and spectral efficient mobile relay deployment in relay-aided cellular networks. In Proc. the 2015 International Conference on Wireless Communications & Signal Processing, October 2015. DOI: 10.1109/WCSP.2015.7340992.
[38]
Chang J, Chen Y. A relay station deployment scheme with a rotational clustering algorithm for multi-hop relay networks. In Proc. the 2016 International Conference on System Science and Engineering, July 2016. DOI: 10.1109/ICSSE.2016.7551543.
[39]
Chang B, Liang Y, Su S. Analyses of QoS-based relay deployment in 4G LTE-A wireless mobile relay networks. In Proc. the 1st Asia-Pacific Conference on Communications, October 2015, pp. 62-67. DOI: 10.1109/APCC.2015.7412581.
[40]
Gan X, Lu H, Yang G Y. Improving energy efficiency by optimizing relay nodes deployment in wireless sensor networks. In Proc. the 9th IEEE International Conference on Communication Software and Networks, May 2017, pp. 306-310. DOI: 10.1109/ICCSN.2017.8230125.
[41]

Li Y, Zhang Y, Zhou H, Jiang T. To relay or not to relay: Open distance and optimal deployment for linear underwater acoustic networks. IEEE Transactions on Communications, 2018, 66(9): 3797-3808. DOI: 10.1109/TCOMM.2018.2822287.
Crossref Google Scholar
[42]

Cui Q, Yang X, Hämäläinen J, Tao X, Zhang P. Optimal energy-efficient relay deployment for the bidirectional relay transmission schemes. IEEE Transactions on Vehicular Technology, 2014, 63(6): 2625-2641. DOI: 10.1109/TVT.2013.2295413.
Crossref Google Scholar
[43]

Lin G H, Xue G. Steiner tree problem with minimum number of Steiner points and bounded edge-length. Information Processing Letters, 1999, 69(2): 53-57. DOI: 10.1016/S0020-0190(98)00201-4.
Crossref Google Scholar
[44]

Chen D, Du D Z, Hu X D, Lin G H, Wang L, Xue G. Approximations for Steiner trees with minimum number of Steiner points. Theoretical Computer Science, 2001, 262(1/2): 83-99. DOI: 10.1016/S0304-3975(00)00182-1.
Crossref Google Scholar
[45]
Du D Z, Wang L, Xu B. The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points. In Proc. the 7th Annual International Conference on Computing and Combinatorics, August 2001, pp. 509–518. DOI: 10.1007/3-540-44679-6_57.
[46]

Măndoiu I I, Zelikovsky A. A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points. Information Processing Letters, 2000, 75(4): 165-167. DOI: 10.1016/S0020-0190(00)00095-8.
Crossref Google Scholar
[47]

Liu L, Zhou Y, Yuan J, Zhuang W, Wang Y. Economically optimal MS association for multimedia content delivery in cache-enabled heterogeneous cloud radio access networks. IEEE Journal on Selected Areas in Communications, 2019, 37(7): 1584-1593. DOI: 10.1109/JSAC.2019.2916280.
Crossref Google Scholar
[48]

Liu L, Zhou Y, Yuan W Z, Tian L. Tractable coverage analysis for hexagonal macrocell-based heterogeneous UDNs with adaptive interference-aware CoMP. IEEE Transactions on Wireless Communications, 2019, 18(1): 503-517. DOI: 10.1109/TWC.2018.2882434.
Crossref Google Scholar
[49]

Liu L, Zhou Y, Garcia V, Tian L, Shi J. Load aware joint CoMP clustering and inter-cell resource scheduling in heterogeneous ultra dense cellular networks. IEEE Transactions on Vehicular Technology, 2018, 67(3): 2741-2755. DOI: 10.1109/TVT.2017.2773640.
Crossref Google Scholar
[50]
Kashyap A, Khuller S, Shayman M A. Relay placement for higher order connectivity in wireless sensor networks. In Proc. the 2006 IEEE International Conference on Computer Communications, April 2006. DOI: 10.1109/INFOCOM.2006.273.
[51]
Bredin J, Demaine E D, Hajiaghayi M T, Rus D. Deploying sensor networks with guaranteed capacity and fault tolerance. In Proc. the 6th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, May 2005, pp. 309-319. DOI: 10.1145/1062689.1062729.
[52]
Willson J, Zhang Z, Wu W, Du D. Fault-tolerant coverage with maximum lifetime in wireless sensor networks. In Proc. the 2015 IEEE International Conference on Computer Communications, April 26-May 1, 2015, pp. 1364-1372. DOI: 10.1109/INFOCOM.2015.7218513.
[53]

Lloyd E L, Xue G. Relay node placement in wireless sensor networks. IEEE Transactions on Computers, 2007, 56(1): 134-138. DOI: 10.1109/TC.2007.250629.
Crossref Google Scholar
[54]

Huang C, Zhang R, Cui S. Optimal power allocation for outage probability minimization in fading channels with energy harvesting constraints. IEEE Transactions on Wireless Communications, 2014, 13(2): 1074-1087. DOI: 10.1109/TW.2013.121813.130953.
Crossref Google Scholar
[55]

Luo Y, Zhang J, Letaief K B. Transmit power minimization for wireless networks with energy harvesting relays. IEEE Transactions on Communications, 2016, 64(3): 987-1000. DOI: 10.1109/TCOMM.2016.2519418.
Crossref Google Scholar
[56]

Sudevalayam S, Kulkarni P. Energy harvesting sensor nodes: Survey and implications. IEEE Communications Surveys and Tutorials, 2011, 13(3): 443-461. DOI: 10.1109/SURV.2011.060710.00094.
Crossref Google Scholar
[57]
Lee J, Leyffer S. Mixed Integer Nonlinear Programming. Springer, 2012. DOI: 10.1007/978-1-4614-1927-3.
[58]

Fowler R J, Paterson M, Tanimoto S L. Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 1981, 12(3): 133-137. DOI: 10.1016/0020-0190(81)90111-3.
Crossref Google Scholar
[59]
Du D Z, Ko K I, Hu X. Design and Analysis of Approximation Algorithms. Springe, 2012.
Journal of Computer Science and Technology
Volume 37 Issue 4,
July 2022
Pages 779-796
DOI: 10.1007/s11390-022-1964-5
Cite this article:
Wang Y, Liu Y-X, Zhu S-J, et al. Approximation Designs for Energy Harvesting Relay Deployment in Wireless Sensor Networks. Journal of Computer Science and Technology, 2022, 37(4): 779-796. https://doi.org/10.1007/s11390-022-1964-5

444

Views

0

Crossref

1

Web of Science

2

Scopus

0

CSCD

Altmetrics
Received: 12 October 2021
Revised: 28 May 2022
Accepted: 06 June 2022
Published: 25 July 2022
©Institute of Computing Technology, Chinese Academy of Sciences 2022
Return