Computers, Materials & Continua DOI:10.32604/cmc.2022.021781 | ![]() |
Article |
Construction of an Energy-Efficient Detour Non-Split Dominating Set in WSN
1Department of Mathematics, Government Engineering College, Trivandrum, 695035, India
2Department of Mathematics, Noorul Islam Centre for Higher Education, Kumaracoil, Thuckalay, 629175, India
*Corresponding Author: G. Sheeba. Email: gsheeba1234@gmail.com
Received: 14 July 2021; Accepted: 16 November 2021
Abstract: Wireless sensor networks (WSNs) are one of the most important improvements due to their remarkable capacities and their continuous growth in various applications. However, the lifetime of WSNs is very confined because of the delimited energy limit of their sensor nodes. This is the reason why energy conservation is considered the main exploration worry for WSNs. For this energy-efficient routing is required to save energy and to subsequently drag out the lifetime of WSNs. In this report we use the Ant Colony Optimization (ACO) method and are evaluated using the Genetic Algorithm (GA), based on the Detour non-split dominant set (GA) In this research, we use the energy efficiency returnee non-split dominating set (DNSDS). A set S ⊆ V is supposed to be a DNSDS of G when the graph G = (V, E) is expressed as both detours as well as a non-split dominating set of G. Let the detour non-split domination number be addressed as γ_dns (G) and is the minimum order of its detour non-split dominating set. Any DNSDS of order
Keywords: Domination number; non-split domination number; detour number; detour non-split domination number
In WSN, for its capability of detection and processing the substantial section of the sensor node is often set in massive sums. These sensor nodes collect information from the viewing zone and the base station. Communication is the primary role of the WSN. Each sensor node is energy-protected here [1]. The delay and the duration of transmission are to be reduced each time when the packet is exchanged. To do so, the nodes have to be energy-rich [2]. In WSN, communication is carried out with the backbones, only the set of nodes. It may be able to generate backbones through the use of DNSDS [3]. Treat the packet from one bundle to the next until DNSDS nodes reach the destination. The backbone usage reduces overhead communication [4], builds capacity for data transmission, and reduces packet latency.
In this article, we design a population-based search technique specifically for the ACO which is supported by ant behavior in the creation of EE-DNSDS to provide answers to the optimization problem [5]. It evaluates its performance against the DNSDS based on the GA. The GA approach is a search solution both for the population and for natural biological development [6]. The rest of the paper is as follows: The notion of developing a DNSDS is outlined in Section 2. The background of the work is presented in Section 3. The suggested work is presented in Section 4. Section 5 explains experimental evaluation together with settings of stimulation, performance measures, and evaluation results. Section 6 provides for the conclusion.
We consider graph
In a connected graph
In any connected graph G, with two vertices
Ant Colony Optimization (ACO) is appropriate to track optimum paths depending on the behavior of the ants used to look through the food. When a food source is found, it goes back to the province by leaving ‘marks’ (predominantly called pheromones) which signals how much food is available. If others approach the marks, they have a certain probability and they will follow the path. In this event, it is not an easy for others to replenish the food with their own markings. The pathway is located by other ants and is further grounded till some ants flood the province from diverse food sources. As they release pheromones when transporting the food, a shorter path is bound to be more grounded, improving the “solution.” Meanwhile, few ants continue to search for food sources closer to home. When the food resource is depleted, the path is no longer established with pheromones and eventually decays. Because the ant-colony moves in a fairly dynamic manner, and the ACO performs better in graphs with changing topologies. Examples of such frameworks include computer networks and worker artificial intelligence simulations.
3.1 The Detour Non-Split Domination Number of a Graph
A set S ⊆ V is a Detour Non-Split Dominating Set (DNSDS) of G when the graph G = (V, E) is expressed as both detours as well as a non-split dominating set of G. Let the detour non-split domination number be addressed as γ_dns (G) and is the least order of its DNSDS. Any DNSDS of order
Example 3.2.2: Assume a graph
Observation:
(i) All end vertex of a connected graph, G belongs to every DNSDS of G.
(ii) Let order of
(iii) For the star
Figure 1: Graph
• Theorem 1: For the path
• Proof: Let
• Theorem 2: For the cycle
• Proof: This is alike the attestation of Theorem 3.2.4.
• Theorem 3: For the complete bipartite graph
• Proof: Assume
• Theorem 4: For wheel
• Theorem 5: For the complete graph
• Proof: Let
• Theorem 6: For double star
• Proof: Let the set,
• Theorem 7: For helm graph
• Proof: Assume
• Theorem 8: For banana tree graph
• Proof: Assume
• Theorem 9:
• Proof: Assume
• Remark 10: The bound in Theorem 3.2.12 is spiky. For path
• Theorem 11:
• Proof: Let
• Theorem 12: Regard
• Proof: Assume
• Remark 13: The bound in Theorem 2.15 is spiky. For cycle
• Theorem 14:
• Proof: Let
• Theorem 15: Assume
Figure 2: Graph
• Proof: Let
• Case (i): If
• Case (ii): If
• Theorem 16: While considering whichever pair of positive integers to be specific a and b, there exists a connected graph
Figure 3: Graph
3.2 The Detour Non-Split Domination Number of Join of Graph
Assume
• Theorem 1: If
• Proof: Let
• Corollary 2:
(i) Let
(ii) Let
(iii) Let
(iv) Let
(v) Let
(vi) Let
3.3 The Detour Non-Split Domination Number of Corona Product of Graph
The corona product
• Theorem 1: Assume two connected graphs notably,
• Proof: If
• Corollary 2:
(i) Let
(ii) Let
(iii) Let
(iv) Let
(v) Let
(vi) Let
• Theorem 3: Assume
• Proof: Let V (
• Theorem 4: Assume
• Proof: Let
• Theorem 5: Assume
• Proof: Let
• Theorem 6: Assume
• Proof: Let
The scavenging behavior of ants excites ACO. When ants walk, they leave a pheromone trail in each node they pass through. The pheromone likelihood, which is provided on every node, aids in determining the shortest path of food from source to destination. A DNSDS, which is rich in energy, is produced in our suggested study. We use two rules in the ACO algorithm to do this: (i) the pheromone updating rule (which signals the updated for each node and is handled in Eq. (4)) and (ii) the state transition rule (which assists with choosing the next node based on the probability value and is addressed in Eq. (1) [22].
In our algorithm, we start with τ0 in each node of the graph. Ants wander throughout the graph randomly by dropping pheromones on all nodes. In this fashion, the ant iterates N times. During this each chosen node with a high P and E based on the probabilistic state transition criteria is added to the DNSDS.
The τ of the nodes which are in the DNSDS is refreshed by the pheromone updating rule.
In Eq. (4), the value of ρ is always 0 ≤ ρ ≤ 1. The τ of the nodes that are unavailable in the DNSDS is evaporated by Eq. (5).
Notations utilized in the work are specified in Tab. 1.
In this section, we have illustrated and investigated fewer limitations, namely the experimental parameters and performance indicators, before presenting the assessment results.
The simulation is completed by assuming the sensor field to be 1000 × 1000. During its execution, the following suspicions are taken into account:
• Sensor nodes are homogeneous and fixed.
• The region is both constrained and consistent.
The energy and degree of the node are taken into account during the DNSDS creation process. Using ACO and the GA, we led large-scale replications to create the DNSDS. We have evaluated the effectiveness of both strategies. Tab. 2 specifies the simulated limitations used to raise the EE-DNSDS using the ACO approach.
The evaluation of the performance is completed by considering two measurements. To be specific the construction time and the size of the DNSDS between the ACO technique and the GA are as follows:
DNSDS Construction Time: Fig. 4 addresses the DNSDS construction time exploited by GA and the ACO technique. While contrasting the ACO and GA, the ACO utilized not as much DNSDS construction time as GA. When the node gets tally to build, the ACO technique performs better when compared to GA.
Figure 4: Comparison of DNSDS construction time
DNSDS Size: Fig. 5 addresses the simulation yield of DNSDS size for different quantities of nodes. We have considered the DNSDS is off to be in average size. In the projected system, the DNSDS size is low in ACO than the GA for the more modest number of nodes. As the node count gets expanded, the average DNSDS size of ACO is lower than the GA.
Figure 5: Comparison of DNSDS size
By modifying the ACO approach, we created an Energy Efficient Detour Non-Split Dominating Set (EE-DNSDS) in this paper. The scavenging behavior of ants inspires the ACO process. The DNSDS created an abundance of energy. The correlation between two algorithms, specifically the ACO and the GA, is performed here. When comparing the ACO and GA, the ACO used less DNSDS build time than the GA. As the number of nodes increases, the average DNSDS size of ACO is roughly equal to that of GA. This is accomplished by employing the network’s energy-efficient DNSDS nodes. Furthermore, the number of standard graphs is resolved and a fraction of its overall qualities are considered in the detour non-split domination. Other optimization approaches can be used in the future, and performance measures can be checked and compared.
Acknowledgement: The authors would like to thank Noorul Islam Centre for Higher Education, also we like to thank anonymous reviewers for their so-called insights.
Funding Statement: The authors received no specific funding for this study.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
1. D. Anusha, J. John and S. J. Robin, “The geodetic hop domination number of complementary prisms,” Discrete Mathematics, Algorithms and Applications, vol. 1, no. 6, pp. 1–10, 2021. [Google Scholar]
2. X. Qiu and X. Guo, “On graphs with same distance distribution,” Applied Mathematics, vol. 8, no. 6, pp. 799–807, 2017. [Google Scholar]
3. G. Chartrand, F. Harary and P. Zhang, “On the geodetic number of a graph,” Networks, vol. 39, no. 1, pp. 1–6, 2002. [Google Scholar]
4. G. Chartrand, G. L. Johns and P. Zhang, “On the detour number and a geodetic number of a graph,” Arscombinatoria, vol. 72, pp. 3–15, 2004. [Google Scholar]
5. G. Chartrand, G. L. Johns and P. Zhang, “The detour number of a graph,” Utilitas Mathematica, vol. 64, pp. 97–113, 2008. [Google Scholar]
6. J. John and N. Arianayagam, “The total detour number of a graph,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 17, no. 4, pp. 337–350, 2014. [Google Scholar]
7. J. John and N. Arianayagam, “The detour domination number of a graph,” Discrete Mathematics, Algorithms and Applications, vol. 9, no. 1, pp. 1750–1756, 2017. [Google Scholar]
8. J. John and V. R. S. Kumar, “The total detour domination number of a graph,” Infokara Research, vol. 8, no. 8, pp. 434–440, 2019. [Google Scholar]
9. J. John and V. R. S. Kumar, “The open detour number of a graph,” Discrete Mathematics, Algorithms and Applications, vol. 13, no. 1, pp. 2050–2088, 2021. [Google Scholar]
10. J. John, P. A. P. Sudhahar and D. Stalin, “On the (M, D) number of a graph,” Proyecciones Journal of Mathematics, vol. 38, no. 2, pp. 255–266, 2019. [Google Scholar]
11. J. John and D. Stalin, “Distinct edge geodetic decomposition in graphs,” Communications in Combinatorics and Optimization, vol. 6, no. 2, pp. 185–196, 2021. [Google Scholar]
12. J. John and D. Stalin, “Edge geodetic self-decomposition in graphs,” Discrete Mathematics, Algorithms, and Applications, vol. 12, no. 5, pp. 2050–2064, 2020. [Google Scholar]
13. J. John and D. Stalin, “The edge geodetic self decomposition number of a graph,” RAIRO Operations Research, vol. 11, no. 2, pp. 1935–1947, 2020. [Google Scholar]
14. J. John, “The forcing monophonic and forcing geodetic numbers of a graph,” Indonesian Journal of Combinatorics, vol. 4, no. 2, pp. 114–125, 2020. [Google Scholar]
15. V. R. Kulli and B. Janakiram, “The non-split domination number of a graph,” Indian Journal of Pure and Applied Mathematics, vol. 31, no. 5, pp. 545– 550, 2000. [Google Scholar]
16. J. V. X. Parthipan and C. C. Selvaraj, “Connected detour domination number of some standard graphs,” JASC: Journal of Applied Science and Computations, vol. 5, no. 11, pp. 486–489, 2018. [Google Scholar]
17. A. P. Santhakumaran and S. Athisayanathan, “The upper edge-to-vertex detour number of a graph,” Algebra and Discrete Mathematics, vol. 13, no. 1, pp. 128–138, 2012. [Google Scholar]
18. A. P. Santhakumaran and S. Athisayanathan, “Connected detour number of a graph,” Journal of Prime Research in Mathematics, vol. 69, pp. 205–218, 2009. [Google Scholar]
19. A. P. Santhakumaran and S. Athisayanathan, “The forcing connected detour number of a graph,” Proyecciones, vol. 33, no. 2, pp. 147– 155, 2014. [Google Scholar]
20. T. M. Selvarajan and D. A. Jeyanthi, “Dominating sets and domination polynomial of fan-related graphs,” Journal of Advanced Research in Dynamical and Control Systems, vol. 12, no. 3, pp. 123–130, 2020. [Google Scholar]
21. A. Potluri and A. Singh, “Hybrid metaheuristic algorithms for minimum weight dominating set,” Applied Soft Computing, vol. 13, no. 1, pp. 76–88, 2013. [Google Scholar]
22. A. Potlur and A. Singh, “Metaheuristic algorithms for computing capacitated dominating set with uniform and variable capacities,” Swarm and Evolutionary Computation, vol. 13, no. 2, pp. 22–33, 2013. [Google Scholar]
![]() | This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |