G.Sheebaand T.M.Selvarajan
1Department of Mathematics,Government Engineering College,Trivandrum,695035,India
2Department of Mathematics,Noorul Islam Centre for Higher Education,Kumaracoil,Thuckalay,629175,India
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 γdns(G)is a γdns-set of G.Here,the γ_dns(G)of various standard graphs is resolved and some of its general properties are contemplated.A connected graph usually has an order n with detour non-split domination number as n or n - 1 are characterized.Also connected graphs of order n ≥4 and detour diameter D ≤4 with detour non-split dominating number n or n - 1 or n - 2 are additionally portrayed.While considering any pair of positive integers to be specific a and b,there exists a connected graph G which is normally indicated as dn(G) = a,γ(G) = b and γdns(G)=a+b-2,here γdns(G)indicates the detour domination number and dn(G)indicates the detour number of a graph.The time is taken for the construction and the size of DNSDS are considered for examining the performance of the proposed method.The simulation result confirms that the DNSDS nodes are energy efficient.
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 graphGas finite,undirected,and connected lacking loops.Let the order ofGbe denoted as p and its size be denoted as q respectively.For knowing more about the basic terminologies in graph theory,consider two edges,that are said to be adjacent when both the vertices (i.e.,) are in edgeG.Incase whenuv∈E(G),then we can easily say that the edgeuis a neighbor ofvand it is represented using the notationN(v)that is nothing but the neighbor set of edgev.The vertex degreev∈Visdeg(v)= |N(v)|.A vertexvis understood as a universal vertex whendeg(v)=p-1.The subgraph stimulated by setSof vertices ofGis symbolized as＜Si＞with V(＜Si＞)=S and E(＜Si＞)={uv∈E(G):u,v∈S}.The path that exists between two vertices of a graph and the one which visits each vertex just one time is said to be the Hamiltonian path orHamilton path.Incase if there is a Hamiltonian path with adjacent endpoints,the resultant graph cycle is described as a Hamiltonian cycle.
In a connected graphGwith two vertices namely u and v;the distance denoted asd(u,v)among two vertices is the length of a shortestu-vpath inG.Usually,theu-vgeodesic is indicated as theu-vpath which has the lengthd(u,v).Let x be a vertex that is understood to lie on au-vgeodesicP,xis a vertex ofPtogether with the vertices namelyuandv.The closed intervalI[u,v]encloses the verticesuandvalong with every vertex within theu-vgeodesic.Incase whenI[u,v]= {u,v}thenuandvare said to be adjacent.For a setSof vertices,letI[S]= ∪u,v∈SI[u,v].Then certainlyS⊆I[S].A setS⊆V(G)is supposed to be a geodetic set ofGwhenI[S]=V.The geodetic number is usually denoted asg(G)and a graph is expressed as the minimum order of its geodetic sets and any geodetic set of orderg(G)is ag-set ofG.Theg(G)of graphs was studied in[7-14].
In any connected graph G,with two verticesuandv,the detour distanceD(u,v)is defined as the length of the longestu-vpath inG.Theu-vdetour is indicated as theu-vpath of lengthD(u,v).).Let x be a vertex that is understood to lie on au-vdetourP,xis a vertex ofPtogether with the vertices namelyuandv.The utmost detour distance fromvto a vertex ofGis the detour eccentricityeD(v)of a vertexvinG.The leasteD(v)amid the vertices of G is the detour radius,radD(G)ofGand the utmosteD(v)is the detour diameter,diamD(G)of G.We denote detour radius by R and detour diameter byD.The closed intervalID[u,v]for two vertices u and v,includes all the vertices that exist within au-vdetour along with u and v.For a setSof vertices,letID[S]= ∪u,v∈DID[u,v].Then certainly,S⊆ID[S].A setS⊆Vis termed as detour set ifID[S]=V.The detour numberdn(G)ofGis usually in the least order of its detour sets as well as any detour set of orderdn(G)is called adn-set ofGand is initiated and studied in[15-19].A setS⊆Vis termed as dominating set ofGif for eachv∈VSis adjacent to some vertex inS.A dominating setSis said to be minimal if no subset ofSis dominating setG.The domination number ofGis symbolized asγ(G)and is the minimum cardinality of a minimal dominating set ofGand was studied in[20].Dominating Sets and Domination Polynomial of Fan Related Graphs were studied in[21].A dominating setDis supposed to be a non-split dominating set ofGif＜V-D＞is connected.The minimum cardinality of a non-split dominating set ofGis called the non-split domination number ofGand is denoted byγns(G)is calledγns-set ofGand is deliberated in[22].
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γdns(G)is aγdns-set ofG.
Example 3.2.2:Assume a graphGin Fig.1,with no two-element subset ofGis a DNSDS ofGand soγdns(G)≥3.LetS={v1,v4,v9}.ThenSis a DNSDS ofGconsequentlyγdns(G)=3.
Observation:
(i) All end vertex of a connected graph,G belongs to every DNSDS of G.
(ii) Let order ofGben≥3 withvas its cut vertex,then every DNSDS ofGcarries a minimum of a single element from each component ofG-v.
(iii) For the starG=K1,n-1(n≥3),γdns(G)=n.
Figure 1:Graph G is a DNSDS of G
• Theorem 1:For the pathG=Pn(n≥4),γdns(G)=n-2.
• Proof:LetPnbev1,v2,...,vn.ThenS=V-{v2,v3} is a DNSDS ofGaccordinglyγdns(G)≤n-2.We prove thatγdns(G)=n-2.In contrast,supposeγdns(G)≤n-3.In that case,S′ofGis available then|S′|≤n-3.Now＜V-S′＞is a pathPsuch that|P|≥3.Letbe an internal vertex of P.Thenis not dominated by any vertex ofS′.HenceS′is not a DNSDS ofG,there is a negation.As a resultγdns(G)=n-2.
• Theorem 2:For the cycleG=Cn(n≥4),γdns(G)=-2.
• Proof:This is alike the attestation of Theorem 3.2.4.
• Theorem 3:For the complete bipartite graphG=Km,n(2 ≤m≤n),γdns(G)=2.
• Proof:AssumeLandWas bipartite sets ofGandxy∈E(G).ThenS={x,y}is a DNSDS ofGthusγdns(G)=2.
• Theorem 4:For wheelG=Wn=K1+Cn-1(n≥4),γdns(G)=2.Proof:LetV(K1)=xandy∈V(Cn-1).ThenS= {x,y}is a DNSDS ofGwith the intention thatγdns(G)=2.
• Theorem 5:For the complete graphG=Kn(n≥3),γdns(G)=2.
• Proof:Letxy∈E(G).ThenS={x,y}is a DNSDS ofGthusγdns(G)=2.
• Theorem 6:For double starGof order(n≥4),γdns(G)=2.
• Proof:Let the set,Scarriesn-2 end vertices ofG.By Observation 3.2.3(i),Sis a subset of each DNSDS ofGand as a resultγdns(G)≥n-2.Since S is a DNSDS ofG,it goes withγdns(G)=n-2.
• Theorem 7:For helm graphG=Hr,γdns(G)=r+1.
• Proof:Assumexas central vertex andZas the set ofrend vertices ofG.By Observation 3.2.3(i),Zis a subset of each DNSDS ofG.Sincexis not subjugated by any vertex ofZ,Zis not a DNSDS ofGthusγdns(G)≥r+1.LetZ′=Z∪{x}.ThenID[Z′]=Vand＜V-Z′＞doesn’t have isolated vertices.As a resultZ′is a DNSDS ofGandγdns(G)=r+1.
• Theorem 8:For banana tree graphG=Br.s,γdns(G)=r+1.
• Proof:Assumexas central vertex andZas the set ofrend vertices ofG.By Observation 3.2.3(i),Zis a subset of each DNSDS ofG.Sincexis not subjugated by any vertex ofZ,Zis not a DNSDS ofGthusγdns(G)≥r+1.LetZ′=Z∪{x}.ThenID[Z′]=Vand＜V-Z′＞doesn’t have isolated vertices.As a resultZ′is a DNSDS of G andγdns(G)=r+1.
• Theorem 9:AssumeRegardGas a connected graph with ordern≥3 withD≥2.Thenγdns(G)≤n-1.
• Proof:AssumeP:v0,v1,v2,...,vDas a detour diametral path inG.AsD≥2,Pcontains at least one internal vertex.LetS=V-{v1}.The S is a DNSDS ofGwithγdns(G)≤n-1.
• Remark 10:The bound in Theorem 3.2.12 is spiky.For pathG=P3,γdns(G)=2=n-1.
• Theorem 11:AssumeRegardGas a connected graph with ordern≥2.Alsoγdns(G)=nas long asGisK2.
• Proof:Letγdns(G)=n.In contrast whenGK2.By Theorem 3.2.12,γdns(G)≤n-1,which is a contradiction.As a result,D=1.HenceG=K2.The reverse is apparent.
• Theorem 12:RegardGas a connected graph with ordern≥4 which is not a star.Thenγdns(G)≤n-2.
• Proof:AssumeGas a tree.SinceGK1,n-1,G holds two adjacent vertices,sayxandy.ThenS=V(G)-{x,y}is a DNSDS ofGso thatγdns(G)≤n-2.After that imagine thatGis not a tree.ThenGincludes a cycle saysC.LetC:v1,v2,...,vr(r≥3)be the longest cycle inG.Suppose that all the vertices ofCare cut-vertices ofG.ThenS=V(G)-V(C)is a DNSDS ofGand soγdns(G)≤n-|V(G)| ≤n-3,therefore is a negation.Suppose thatGholds as a minimum one cut-vertex,sayv1.ThenS=V(G)-{v1,v2}is a DNSDS ofGas a resultγdns(G)≤n-2,which is a contradiction.If no vertex ofGis a cut vertex ofG,by the similar argument,it can show thatγdns(G)≤n-2,which is a contradiction.
• Remark 13:The bound in Theorem 2.15 is spiky.For cycleG=C4,γdns(G)=2=n-2.
• Theorem 14:AssumeRegardGas a connected graph with ordern≥3.Alsoγdns(G)=n-1 as long asG=K1,n-1orK3.
• Proof:Letγdns(G)=n-1.Ifn= 3,thenG=K1.2orK3,which satisfies the requirements of this theorem.So we have done.Letn≥4.But whenGK1,n-1,then according to the Theorem 3.2.15,γdns(G)≤n-2,therefore is a negation.For that reasonG=K1,n-1.The converse is clear.Now we distinguish connected graph with ordern≥4 and detour diameterD≤4 withγdns(G)=n-2.For this purpose,we introduce family I of graph• Theorem 15:AssumeGas a connected graph withn≥4 andD≤4.Thenγdns(G)=n-2 as long asGis eitherC4orK4orK4-{e}or a double star of the graphGspecified in Fig.2 of the family I.
Figure 2:Graph G specified in the family I
• Proof:Letγdns(G)=n-2.So we enclose the two subsequent cases.
• Case (i):IfGis a tree.According to Theorem 3.2.17,GK1,n-1.SupposeGis a double star,thenGsatisfies the requirements of this theorem.So,we have done.Let us assume thatGis neither a star nor a double star.ThenGcontains a pathP:x,y,z.LetS=V-{x,y,z}.ThenSis a DNSDS of a graph as a consequenceγdns(G)≤n-3,therefore is a negation.
• Case (ii):IfGis not a tree.Then it holds as a minimum of one cycleC.LetCbe a girth inGandC(G)be its length.SinceD≤4.We have thatC(G)≤4.LetCbev1,v2,v3,v4,v1.IfG=K4-{e},then we are done.IfG=K4,then we are done.Suppose thatGis neitherC4norK4-{e}norK4.Then there exists one vertexxto such a degree which is adjacent tov1,say.ThenS=V-{v1,v2,v3}is a detour non-split domination number of a graph as a result,γdns(G)≤n-3,therefore is a negation.LetC(G)= 3.LetCbev1,v2,v3,v1.SinceD≤4,there exists a minimum of one vertex(x)therebyxv1∈E(G).Ifd(v2)=d(v3)=2 and the edges incident withv1are end edges,then the graphGis given in family I of Fig.2a.This satisfies the requirements of this theorem.If at least one edge incident withxis not an end edge,subsequentlyγdns(G)≤n-3,which is a contradiction.Ifdeg(v1)= 2,deg(v2)≥3 anddeg(v3)≥3,then sinceD≤4,the edges incident atv2andv3are end edges.Then graphGis given in the family I of Fig.2b.SinceD≤4,deg(vi)≥3 for all i(1 ≤i ≤3)is not possible.The reverse is apparent.
• Theorem 16:While considering whichever pair of positive integers to be specific a and b,there exists a connected graphGtherebydn(G)=a,γ(G)=bandγdns(G)=a+b-2.Proof:LetP2(b-2)+1:x,v1,v2,...,v2(b-2)+2,ybe a path on 2(b - 2) + 2 vertices.Has a graph attained fromP2(b-2)+2by accumulating the new verticesx1,x2,...,xa-1and introduced as edgexxi(1 ≤i≤a-1).Assume graphGgained fromHby summing up new verticesu1,u2,...,ub-2with initiating the edgesuivi(1 ≤i≤2(b-2)-1)anduivi+1(2 ≤i≤2(b-2)is revealed in Fig.3.SinceID[X]=V,Xis a detour set ofGtherefore,dn(G)=a.Subsequently,we illustrate thatγ(G)=b.We view that allγ-set ofGcontainsui(1 ≤i≤b-2)and the verticesxandyandγ(G)=b-2+2 =b.LetS= {x,y,u1,u2,...,ub-2}.ThenSis a dominating set ofGso thatγ(G)=b.After that,we show thatγdns(G)=a+b-2.The end vertices ofGbeX= {x,x1,x2,...,xa-1,y}.By Observing 3.2.3(i),X is a subset of every DNSDS ofGand soγdns(G)≥a.It is handily seen that each DNSDS ofGholds eachui(1 ≤i≤b-2)and soγdns(G)≥a+b-2.LetS′=X ∪{u1,u2,...,ub-2}.ThenS′is DNSDS ofGso thatγdns(G)=a+b-2.
Figure 3:Graph G gained from H by summing up new vertices
3.2 The Detour Non-Split Domination Number of Join of Graph
AssumeHand as weKas two graphs.The combination of two graphs namelyGandHis symbolized asG+Hand defined as the graph withV(G+H)=V(G)∪V(H)andE(G+H)=E(G)∪E(H)∪{uv:u∈V(G),v∈V(H)}.
• Theorem 1:IfKandHare two connected graphs that contain either a Hamiltonian path or a Hamiltonian cycle.Thenγdns(K+H)=2.
• Proof:LetP1:u0,u1,u2,...,ulbe a Hamiltonian path in K,similarlyP2:v0,v1,v2,...,vkbe a Hamiltonian path inG,wherel+k=n.ThenP1∪P2is a Hamiltonian path inK+H.LetS={u0,v0}.ThenSis a DNSDS ofK+Hconsequentlyγdns(K+H)=2.
• Corollary 2:
(i) LetK=Pn(n≥4)andH=Pm(m≥4).Thenγdns(K+H)=2.
(ii) LetK=Pn(n≥4)andH=Cm(m≥4).Thenγdns(K+H)=2.
(iii) LetK=Cn(n≥4)andH=Cm(m≥4).Thenγdns(K+H)=2.
(iv) LetK=Kn(n≥3)andH=Km(m≥4).Thenγdns(K+H)=2.
(v) LetK=Kn(n≥4)andH=Pm(m≥4).Thenγdns(K+H)=2.
(vi) LetK=Kn(n≥4)andH=Cm(m≥4).Thenγdns(K+H)=2.
3.3 The Detour Non-Split Domination Number of Corona Product of Graph
The corona productK°His described as the graph gained fromKandHby attaining one copy ofKand|V(K)|copies ofHand then by joining an edge of,all the vertices from the ith-copy ofHto the ith-vertex ofK,wherei=1,2,...,|V(H)|.
• Theorem 1:Assume two connected graphs notably,Kas well asHwith ordersn1andn2respectively.If H contains either a Hamiltonian path or a Hamiltonian cycle,thenγdns(K°H)=n1.
• Proof:Ifn2=1,then the result is obvious.LetH1=(V1,E1),H2=(V2,E2),...,Hn1=(Vn1,En1)be then1copies ofHinK°H.LetQi:vi1,vi2,...,vin2,(1 ≤i≤n1)be a Hamiltonian path inHi(1 ≤i≤n1).AssumeVas the vertex ofKandV={v1,v2,...,vn1}.Then set of cut vertices inK°HisV.By Observing 3.2.3(ii),every DNSDS ofK°Hholds minimum vertex from everyQi(1 ≤i≤n1)consequentlyγdns(G)≥n1.Let S = {v11,v21,...,vn11}.ThenSis a DNSDS ofK°Hso thatγdns(G)=n1.
• Corollary 2:
(i) LetK=Pn(n≥4)andH=Pm(m≥4).Thenγdns(K°H)=n.
(ii) LetK=Pn(n≥4)andH=Cm(m≥4).Thenγdns(K°H)=n.
(iii) LetK=Cn(n≥4)andH=Cm(m≥4).Thenγdns(K°H)=n.
(iv) LetK=Kn(n≥3)andH=Km(m≥4).Thenγdns(K°H)=n.
(v) LetK=Kn(n≥4)andH=Pm(m≥4).Thenγdns(K°H)=n.
(vi) LetK=Kn(n≥4)andH=Cm(m≥4).Thenγdns(K°H)=n.
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.
Table 1:Notations and their description
In this section,we have illustrated and investigated fewer limitations,namely the experimental parameters and performance indicators,before presenting the assessment results.
5.1 Simulation Setup
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.
Table 2:Simulation constraints
5.2 Performance Evaluation
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.
推荐访问:Efficient Detour Construction
