A COMPETITIVE ANALYSIS OF IMPROVED COVER-BASED 2-CONNECTED NODE PLACEMENT ALGORITHM FOR THE 2-CONNECTED RELAY NODE PLACEMENT PROBLEM UNDER DELAY CONSTRAINT IN WIRELESS SENSOR NETWORKS
Abstract
Wireless Sensor Networks (WSNs) have become an integral part of various industries and applications. However, frequent link interruptions and network unreliability caused by electromagnetic interferences may lead to high delay and packet loss, posing a challenge in achieving high reliability and stability in WSNs. In this paper, we propose an algorithm called Improved Cover-based 2-Connected Node Placement (IC2NP) to solve the Delay Constrained Relay Node Placement (DCRNP) problem in WSNs. The algorithm aims to build at least two node-disjoint paths meeting the hop constraint between each sensor and the sink by deploying certain relay nodes (RNs). IC2NP provides a feasible solution with a time complexity of O(N^4) and an approximation ratio guaranteed to be O(ln n). Through extensive simulations, we validate that IC2NP outperforms the existing method in terms of success rate, deployment budget, and running time. This paper also summarizes related work on the Relay Node Placement (RNP) problem and previous research on the DCRNP problem. The proposed algorithm can enhance the deployment success rate of 2-connected DCRNP by changing the deployment rules.
Keywords:
Wireless Sensor Networks, Delay Constrained Relay Node Placement, Improved Cover-based 2-Connected Node Placement, Relay Node Placement, Hop Count ConstraintDownloads
Published
Issue
Section
How to Cite
License
Copyright (c) 2023 Hwang S F, Chao W L2 , Wu C L
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
M. Raza, N. Aslam, H. Le-Minh, S. Hussain, Y. Cao, and N. M. Khan, "A Critical Analysis of Research Potential, Challenges, and Future Directives in Industrial Wireless Sensor Networks," IEEE Communications Surveys and Tutorials, Article vol. 20, no. 1, pp. 39-95, 2018.
N. Lu, N. Cheng, N. Zhang, X.M. Shen, and J. W. Mark, "Connected Vehicles: Solutions and Challenges," IEEE Internet of Things Journal, Review vol. 1, no. 4, pp. 289-299, Aug 2014.
J. Lin, W. Yu, N. Zhang, X. Y. Yang, H. L. Zhang, and W. Zhao, "A Survey on Internet of Things: Architecture, Enabling Technologies, Security and Privacy, and Applications," IEEE Internet of Things Journal, Article vol. 4, no. 5, pp. 1125-1142, Oct 2017.
X. M. Li, D. Li, J. F. Wan, A. V. Vasilakos, C. F. Lai, and S. Y. Wang, "A review of industrial wireless networks in the context of Industry 4.0," Wireless Networks, Review vol. 23, no. 1, pp. 23-41, Jan 2017.
H. Zhang, H. Xing, J. Cheng, A. Nallanathan, and V. Leung, “Secure resource allocation for OFDMA two-way relay wireless sensor networks without and with cooperative jamming,” IEEE Trans. Ind. Informat., vol. 12, no. 5, pp. 1714–1725, Oct. 2017.
K. Wang, Y. Wang, Y. Sun, S. Guo, and J. Wu, “Green industrial internet of things architecture: An energy-effificient perspective” IEEE Commun. Mag., vol. 54, no. 12, pp. 48–54, Dec. 2016
Z. Ning, X. Wang, X. Kong, and W. Hou, “A social-aware group formation framework for information diffusion in narrowband internet of things,” IEEE Internet Things J., vol. 5, no. 3, pp. 1527–1538, Jun. 2018.
D.J. Yang, S. Misra, X. Fang, G.L. Xue, and J. S. Zhang, “Two-Tiered constrained relay node placement in wireless sensor networks: Computational complexity and effificient approximations,” IEEE Trans. MobileComput., vol. 11, no. 8, pp. 1399–1411, Aug. 2012.
V. C. Gungor and G. P. Hancke, “Industrial wireless sensor networks: Challenges, design principles, and technical approaches,” IEEE Trans.Ind. Electron., vol. 56, no. 10, pp. 4258– 4265, Oct. 2009.
A.A. Kumer S., K. Øvsthus, and L.M. Kristensen, “An industrial perspective on wireless sensor networks—A survey of requirements, protocols and challeges,” IEEE Commun. Survey Tuts., vol. 16, no. 3, pp. 1391–1412, Jan. 2014.
L. Gouveia, “Multicommodity flflow models for spanning trees with hop constraints,” Eur. J. Oper. Res., vol. 95, no. 1, pp. 178–190, Nov. 1996.
Chaofan M, Wei L, Meng Z, et al. Relay Node Placement in Wireless Sensor Networks with Respect to Delay and Reliability Requirements[J]. IEEE Systems Journal, 2018:1-12.
Lin G, Xue G (1999) Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge-length. Inf Process Lett69(2):53–57
Chen D, Du DZ, Hu XD, Lin G, Wang L, Xue G (2000) Approximations for Steiner Trees with Mnimum Number of Steiner Points.J Glob Optim 18(3):17–33
Cheng XZ, Du DZ, Wang LS, Xu BG (2007) Relay Sensor Placement in Wireless Sensor Networks. Wirel Netw 14(3):347–355
Lloyd E, Xue G (2007) Relay Node Placement in Wireless Sensor Networks. IEEE Trans Comput 56(1):134–138
S. Misra, S. Hong, G. Xue, and J. Tang, “Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirement,” in Proc. IEEE INFOCOM, 2008, pp. 879–887.
S. Misra, S. Hong, G. Xue, and J. Tang, “Constrained relay node placement in wireless sensor networks: Formulation and approximations,” IEEE/ACM Trans. Netw., vol. 18, no. 2, pp. 434–447, Apr. 2010.
Yang DJ, Misra S, Fang X, Xue GL, Zhang JS (2012) Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks: Computational Complexity and Efficient Approximations. IEEE Trans Mobile Comput 11(8):1399–1411
A. Chelli, M. Bagaa, D. Djenouri, I. Balasingham, and T. Taleb, "One-Step Approach for Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks," IEEE Wireless Communications Letters, vol. 5, no. 4, pp. 448-451, 2016.
C. Ma, W. Liang, M. Zheng, and H. Sharif, “A connectivity-aware approximation algorithm for relay node placement in wireless sensor networks,” IEEE Sensors J., vol. 16, no. 2, pp. 515–528, Jan. 2016.
A. Bhattacaya and A. Kumar, “Delay constrained optimal relay placement for planned wireless sensor networks,” in Proc. IEEE 18th Int. Workshop Quality Service, 2010, pp. 1–9. [23] A. Bhattacharya and A. Kumar, “A shortest path tree based algorithm for relay placement in a wireless sensor network and its performance analysis,” Comput. Netw., vol. 71, no. 4, pp. 48–62, 2014.
A. Nigam and Y.K. Agarwal, “Optimal relay node placement in delay constrained wireless sensor network design,” Eur. J. Oper. Res., vol. 233, no. 1, pp. 220–233, 2014. [25] L. Sitanayah, K.N. Brown, and C.J. Sreenan, “A fault-tolerant relay placement algorithm for ensuring k vertex-disjoint shortest paths in wire less sensor networks,” Ad Hoc Netw., vol. 23, no. 2014, pp. 145–162, 2014.
Wang WL, Liou BH, Solomon A. 2-Connected relay placement problem in wireless sensor networks[C]// Second International Conference on Digital Information & Communication Technology & Its Applications. IEEE, 2012.
Hwang S F, Chao W L, Wu C L, et al. 2-Connected Relay Node Placement Scheme in Disjoint Wireless Sensor Networks[C]// 2014 IEEE 5th International Conference on Software Engineering and Service Science. 0.
S. Rajagopalan and V. Vazirani, “Primal-Dual RNC approximation algorithms for set cover and covering integer programs” SIAM J. Comput. vol. 28, pp. 525–540, 1998. T.H. Cormen, C. E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithm.
Cambridge, MA, USA: The MIT Press, 2009, pp. 1117–1122.
