Abstract
Wireless sensor networks (WSNs) are group of spatially distributed atomic sensors which are deployed widely in unattended environments. Each sensor node is capable of monitoring environmental parameters like temperature, pressure, humidity, vibration etc. And WSNs has wide range of applications starting from home automation to military surveillance. However, one of the noticeable issues in WSNs is its efficient energy usage because sensor nodes are battery powered, which cannot be replaced or recharged once deployed in target area. Since communication module consumes most of the node power, energy efficient topology construction and routing algorithm design plays the vital role for energy conservation. For energy efficient optimized topology construction selected nodes are being chosen to construct a virtual backbone. One of the principle practices followed for virtual backbone construction for optimized topology is Dominating Set (DS) of graph theory. However, generating a virtual backbone by DS or Connected Dominating Set (CDS) is NP-hard problem because of larger network size. To overcome this issue, in this paper an energy aware Total Edge Domination based semigraph model (TEDS) is proposed. The performance ratio of proposed TEDS algorithm is measured as \(\left( {3 + {{ln\Delta^{\prime}}} + \frac{1}{{{{\Delta^{\prime}}}}}} \right)\left| {{{opt}}} \right|\), where |opt| represents size of the network constructed using proposed model. The time complexity of the proposed model is measured as O(m) and message complexity \({\text{O}}\left( {mn + \frac{m}{{\Delta^{\prime}}}} \right)\), where \(\Delta^{\prime}\) is the maximum edge degree of the network. In addition, the performance of the network is simulated using the NS-2 simulator, and the performance metrics were studied.
Similar content being viewed by others
References
Zhou, H. Y., Luo, D. Y., Gao, Y., & Zuo, D. C. (2011). Modeling of node energy consumption for wireless sensor networks. Wireless Sensor Network, 3(01), 18–23.
Lin, S., Zhang, J., Zhou, G., Gu, L., Stankovic, J. A., & He, T. ( 2006). Adaptive Transmission Power Control for Wireless Sensor Networks. In Proceedings of Fourth International Conference on Embedded Networked Sensor Systems (pp. 223–236).
Kim, D., Wu, Y., Li, Y., Zou, F., & Du, D. Z. (2009). Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE Transactions on Parallel and Distributed Systems, 20(2), 147–157.
Fu, D., Han, L., Liu, L., Gao, Q., & Feng, Z. (2015). An efficient centralized algorithm for connected dominating set on wireless networks. Procedia Computer Science, 56, 162–167.
Asgarnezhad, R., & Torkestani, J. A. (2011). Connected dominating set problem and its application to wireless sensor networks. In The First International Conference on Advanced Communications and Computation, INFOCOMP (pp. 46–51).
Yu, J., Wang, N., & Wang, G. (2012). Constructing minimum extended weakly-connected dominating sets for clustering in ad hoc networks. Journal of Parallel and Distributed Computing, 72(1), 35–47.
Qian, X., et al. (2016). A wireless sensor network clustering algorithm based on hypergraph. International Journal of Future Generation Communication and Networking, 9(6), 297–312.
Saravanan, S., Poovazhaki, R., & Shanker, N. R. (2018). Cluster Topology in WSN with SCPS for QoS. Wireless Personal Communications, 99(3), 1295–1314.
Yavad, M., Rishiwal, V., Arora, G., & Makka, S. (2009). Modified minimum connected dominating set formation for wireless Adhoc networks. Journal of computing, 1(1), 200–203.
Fu, D., et al. (2016). A Greedy Algorithm on constructing the minimum connected dominating set in wireless network. International Journal of Distributed Sensor Networks, 12(7), 1703201.
Chang, T., Wang, K., & Hsieh, Y. (2008). A color theory based energy efficient routing algorithm for mobile wireless sensor networks. International Journal of Computer Networks and Communications, 52, 531–541.
Yin, B., Shi, H., & Shang, Y. (2011). An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks. Journal of Parallel and Distributed Computing, 71, 27–39.
Balaji, S., Kannan, K., & Venkatakrishnan, Y. B. (2013). Total dominating set based algorithm for connected dominating set in Ad hoc wireless networks. WSEAS Transactions on Mathematics, 12, 1164–1172.
Mohanty, J. P., Mandal, C., Reade, C., & Das, A. (2016). Construction of minimum connected dominating set in wireless sensor networks using pseudo dominating set. Ad Hoc Networks, 42, 61–73.
Fu, D., et al. (2015). An efficient centralized algorithm for connected dominating set on wireless networks. Procedia Computer Science, 56, 162–167.
Mohanty, J. P., Mandal, C., & Reade, C. (2017). Distributed construction of minimum connected dominating set in wireless sensor network using two-hop information. Computer Networks, 123, 137–152.
Haynes, T. W., Hedetniemi, S. T., & Slater, P. J. (1998). Fundamentals of domination in graphs. New York: Marcel Dekker.
Ding, L., Wu, W., Willson, J., Du, H., Lee, W., & Du, D.-Z. (2011). Efficient algorithms for topology control problem with routing cost constraints in wireless networks. IEEE Transactions on Parallel and Distributed Systems, 22(10), 1601–1609.
Kamath, S. S., & Bhat, R. S. (2003). Domination in Semigraphs. Electronic Notes in Discrete Mathematics, 15, 106–111.
Sampathkumar, E. (2000). Semigraphs and their applications, Report on the DST Project.
Hedetniemi, S. T., & Mitchell, S., (1977). Edge domination in trees. In Proc. 8th SE Conf. Combin., Graph Theory and Computing, Congr. Numer (vol. 19, pp. 489–509).
Kulli V. R., & Sigarakanti S. C. (1988) The connected edge domination number of a graph, Technical Report 8801, Dept Math. Gulbarga University
Guha, S., & Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20(4), 374–387.
Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., & Ko, K. I. (2004). A greedy approximation for minimum connected dominating sets. Theoretical Computer Science., 329(1–3), 325–330.
Suriya Praba, T., Sethukarasi, T., & Saravanan, S. (2019). Energy measure semigraph-based connected edge domination routing algorithm in wireless sensor networks. Mobile Information Systems. https://doi.org/10.1155/2019/4761304.
Acknowledgement
The authors wish to express their sincere thanks to SASTRA Deemed University for the infrastructural support needed to carry out this work.
Author information
Authors and Affiliations
Corresponding author
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
Praba, T.S., Saravanan, S. & Sethukarasi, T. An Efficient Energy Aware Semigraph-Based Total Edge Domination Routing Algorithm in Wireless Sensor Networks. Wireless Pers Commun 117, 2423–2439 (2021). https://doi.org/10.1007/s11277-020-07982-z
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11277-020-07982-z