A Sustainable WSN System with Heuristic Schemes in IIoT

Wenjun Li,Siyang Zhang,Guangwei Wu,Aldosary Saad,Amr Tolba,4 and Gwang-jun Kim

1School of Computer and Communication Engineering,Changsha University of Science and Technology,Changsha,410114,China

2College of Computer and Information Engineering,Central South University of Forestry and Technology,Changsha,410114,China

3Computer Science Department,Community College,King Saud University,Riyadh,11437,Saudi Arabia

4Mathematics and Computer Science Department,Faculty of Science,Menoufia University,Egypt

5Department of Computer Engineering,Chonnam National University,Gwangju,61186,Korea

Abstract: Recently, the development of Industrial Internet of Things has taken the advantage of 5G network to be more powerful and more intelligent.However,the upgrading of 5G network will cause a variety of issues increase,one of them is the increased cost of coverage.In this paper, we propose a sustainable wireless sensor networks system, which avoids the problems brought by 5G network system to some extent.In this system, deploying relays and selecting routing are for the sake of communication and charging.The main aim is to minimize the total energy-cost of communication under the precondition,where each terminal with low-power should be charged by at least one relay.Furthermore, from the perspective of graph theory, we extract a combinatorial optimization problem from this system.After that,as to four different cases, there are corresponding different versions of the problem.We give the proofs of computational complexity for these problems,and two heuristic algorithms for one of them are proposed.Finally, the extensive experiments compare and demonstrate the performances of these two algorithms.

Keywords:Industrial Internet of Things;sustainable wireless sensor network system;combinatorial optimization problem;heuristic algorithms

1 Introduction

With the improvement of intelligent level of manufacturing industry,sensors or smart devices with capabilities of sensing,monitoring,data transmission and simple calculation are used in industry.It promotes the development of Industrial Internet of Things (IIoT).Moreover, it also brings a great number of problems and numerous challenges, which have attracted a great attention from a large number of engineers and scientists[1,2].Among all the parts of IIoT,wireless sensor networks(WSN)play an important role in it.

In the past few years, with the maturity of 5G technology,4G network is gradually replaced by 5G network due to its advantages,such as high speed,large capacity and low delay[3].Nevertheless,it has its own shortages.Compared with 4G signal,5G signal transmission distance is shorter.Hence,the coverage of 5G station is smaller than 4G station.To deal with this problem,a reasonable way is to deploy a large number of 5G stations.Fig.1 shows an instance of the coverage comparison between 5G station and 4G station.Obviously,this method results in a very high cost.To avoid the problem mentioned above to some extent, we proposed a sustainable WSN system with simple topological structure.

Figure 1:An instance of coverage comparison between 5G station and 4G station

In our proposed system, some terminals and a sink are given.The terminals with low-power can be charged by relays and wireless information can be transmitted via relays.More precisely,the information can be transmitted in multi-hop,but the energy can only be transmitted in one-hop since the energy loss is too large in the process of wireless power transmission.The tasks of the system include deploying relays to make up a communication network and selecting routing for each terminal.Further,the aim of it is to minimize the energy assumption of communication(communication cost)under the restriction that each terminal can be charged by at least one relay.We extract a combinatorial optimization problem,called Sustainable Communication(SC)Problem,from the system mentioned above.

The followings are the main contributions of this paper:(a)proposing a sustainable wireless sensor network system framework;(b)showing some models and corresponding combinatorial problems for different cases of the system;(c)proving the computational complexity of the problems,and(d)giving two heuristic algorithms and some simulation results for one of the problems.

The structure of the rest of paper is composed of the following four sections.Section 2 is about related works.Section 3 presents our proposed sustainable wireless sensor network system,including description and some explanations of the system, some models and corresponding combinatorial optimization problems of the system,computational complexity proofs and two heuristic algorithms for the problems.In Section 4, we give the performance analysis for the two algorithms showed in Section 3 and an instance of engineering application.The last section concludes this paper.

2 Related Work

In this section, we will show some related work about our proposed sustainable wireless sensor network system.Since relay deployment and routing selection are the two tasks needed to construct the system,we review the major related works about these two items.

The relay deployment problem has attracted a lot of attentions.The authors in [4] studied the energy provisioning and relay deployment problem in two-tiered WSN.They modeled this problem as an NP-hard problem(Mixed-integer Nonlinear programming),and proposed a heuristic algorithm to address it.Patel et al.[5]considered the nodes(including sensor,relay and base station)deployment problem in WSN.On the basis of ensuring the coverage,connectivity,bandwidth and robustness,they proposed several different strategies based on the number of sensors,network lifetime and energy consumption.The authors in[6]modeled the relay sensor deployment problem as the Steiner Minimum Tree problem,where the amount of steiner points is minimum and the edge length is bounded.Liu et al.[7]investigated the problem in WSN inspecting tunnels.Based on the comprehensive consideration of energy cost,coverage,connectivity,network lifetime and data latency,they proposed a strategy of deploying relays.Furthermore, the authors studied the same problem in the application of pipeline inspection [8].The authors in [9] considered designing WSN with relays, where the networks are deployed underground, but relays are placed above ground.The authors in [10] studied the relay deployment problem in the same network with the constraints of load balance.

For the IEEE 802.16j WiMAX networks,there is a long history of research for the relay deployment problem.The authors in [11] considered the relay station deployment problem for minimizing the network operational cost.Based on the Bender’s decomposition method,they divided the original problem into some small subproblems expressed by Boolean variables.Yu et al.[12]investigated the problem of base and relay station deployment in relay networks with multi-hop.Later, the authors considered the same problem in[13].They proposed a clustering approach,the main idea of which is similar to the Divide and Conquer method[14].Huang et al.considered the relay selection problem in relaying network with two hops, the aim of which is to maximize the system capacity [15].The authors in [16] studied the relay station deployment cooperative communications problem, which aims to deploy minimum relay stations such that the data rate requests of the subscriber stations are satisfied.They proved that the problem is NP-complete firstly, where NP is the abbreviation of nondeterministic polynomial.And then, they proposed anO(logn)-approximation algorithm for the problem.Furthermore, they developed an approximation algorithm with a constant ratio for it in the case that any relay station is connected to constant subscriber stations.Lu et al.[17]investigated the relay station deployment problem aiming to maximize network capacity under the cost constraint.For this problem, they considered two different kinds of relay stations.The one is Transparent Relay Station,and the other is Non-Transparent Relay Stations.These two types of relay stations hold different functions and have different prices.They proved that the problem is NP-hard.Furthermore,they developed a heuristic scheme to achieve a suboptimal solution for it.Chang et al.[18] studied this problem with bandwidth constraint of relay stations.This problem aims to deploy relays in right locations such that the network throughput is maximized under the restriction of bandwidth requirement.Since the bandwidth constraint of relay stations may lead to load unbalance and bandwidth starvation,the authors put forward some measures to avoid these two situations.The most crucial measure is to divide the original region into several parts, which have the same traffic demands.

The authors in [19] developed a cooperative network, which is focused on maximizing energy efficiency under QoS (Quality of Service)constraints.The proposed strategies for the cooperative network include how to deploy relays at the right locations under consideration of energy efficiency and QoS.

It should be pointed out that relay deployment problem and relay selected problem have great similarity.Because selecting some relays from the deployed relays is the same as deploying some relays to candidate relay locations from the combinatorial optimization perspective.If all the relays are deployed in the wireless networks,then relay selection becomes another important task with respected to some optimization targets in this case.Zappone et al.[20]studied an energy efficiency problem in networks with users and relays.The aim of it is to optimize the relay assignment and transmit powers jointly such that the user-fairness are considered and the minimum bit/J efficiency is maximized.They modeled it as a mixed-integer optimization problem.The authors in[21]considered a relay selection problem with fairness of users in relay networks,which are decoded-and-forwarded and full-duplex.They proposed a relay selection algorithm for two different models.There have been some research works considering user cooperation problems in other types of relay networks.

During the wireless network construction, relay deployment usually includes routing selection operation implicitly.Routing selection is a trivial problem in the networks with only one or two hops.However, if the wireless network has multi hops, then it becomes an important and complicated problem for minimizing energy consumption and maximizing network lifetime.Chai et al.[22]considered the routing selection problem in Mesh Networks,which aims to minimize the end-to-end delay.Their main contribution is based on a delay-and interference-aware routing method.Mahmood et al.proposed a search based genetic algorithm for routing selection in wireless mesh network[23].Li et al.[24]considered an optimization problem,called Superposed Data Uploading Problem,in multihop wireless network with smart devices.In the problem,the task is to select routing for each terminal,and the aim is to minimize the total energy cost.There were some other works showing theoretical or practical studies about routing selection,which are modeled as some corresponding optimization problems.Furthermore,some efficient heuristic algorithms or schemes are proposed.

3 Our Proposed Sustainable WSN System

In this section, we show the framework of our proposed system first.Later, some models and corresponding formal mathematical definitions of combinatorial optimization problems are given.And then, the NP-hardness of the combinatorial problems are presented.At last, two heuristic algorithms for one of the NP-hard problems are shown.

3.1 System Framework

In this part, we will show details of our proposed sustainable wireless sensor network system framework.In the system,there are some fixed terminals and a fixed sink.And there are some relays which not only can transmit data but also can charge of terminals.The system should satisfy the following two conditions:Communication condition.Each terminal’s data can be transmitted to the sink via some relays;Sustainability condition.Each terminal can be charged by at least one relay.The first condition is trivial, since communication is the fundamental function of the system.The second condition is to ensure sustainable running of the whole system.

To construct such a sustainable wireless sensor network system,we have to accomplish two tasks:(1)Relays deployment task (deploying a limited or unlimited number of relays at the restricted or unrestricted locations);and(2)Routing selection task(for each terminal,select a routing of the transmission from it to the sink).The optimization target of the system is to minimize the communication cost under the case that the system satisfies the communication condition and sustainable condition.It should be remarked that we will not consider energy consumption of terminal charging,since only a few of terminals are in the state of lower battery and need to be charged in practice.Moreover,we assume the possibility of data transmission from each terminal to the sink is the same.In order to introduce our proposed system clearly,we will give some necessary explanations on some issue about the system,such as relay deployment,energy consumption of wireless communication,energy loss of wireless charging,and the topology of the constructed network.

Firstly,the system should focus on the number of relays and the candidate locations for deploying relays.Since relays may be expensive,it is reasonable that the number of relays is usually limited.For the reason that the environment may be complex and there are some constraints of the applications,relays should not be deployed at somewhere.It means that the candidate locations for deploying relays may be restricted.Secondly,in our system,we just consider the energy loss during the RF(Radio Frequency)transmission in our system.And we assume energy consumption(communication cost)function isEC(Dist(a,b))=c*Dist(a,b)q,whereDis t(a,b)is the distance between senderaand receiverb,andc,qare constants.Thirdly,there is a valid distance from relays and the charged terminals,calledcharging radius(Rcha).Generally, the radius of charging is smaller than that of the wireless communication,calledcommunication radius(Rcom).Last, for the network in our proposed system, there is a fixed sink s,which connects the communication network with extranet.And we assume the communication radius of the terminals,relays and sink are the same.

Fig.2 shows an instance of communication and charging network for our proposed system.In the network,c,e,fandgare the deployed relay nodes.We omit all the candidate locations nodes except the deployed relay nodes.Here,a,banddare the fixed terminated nodes,andhis a fixed sink node.The charging radiusRcha=15 and the communication radiusRcom=25.Pathsa→c→g→h,b→c→g→handd→f→g→hare valid communication paths from relay nodesa,banddtoh,respectively.In this instance,terminalccan chargeaandbsinceDist(a,c) =Dist(b,c) = 10 ≤Rcha.However,relayfcannot charge terminaldfor the reason thatDist(d,f) = 25＞Rcha,and pathd→e→g→his an invalid communication path sinceDist(e,g) = 50＞Rcom.Therefore,in this instance,the sustainable wireless sensor network system has to use at least 4 relays though only three relays used for communication.

Figure 2: An instance of communication and charging network. Rcha=15 and Rcom=25.Since the distance between node d and f is 25 (larger then Rcha), terminal d can only be charged by e though it not on any communication path from terminal d to s

3.2 Models and Combinatorial Optimization Problems

In this part, based on the proposed sustainable wireless sensor network system mentioned in the previous subsection, we extract four different models for four different cases, and show the corresponding formal definitions of combinatorial optimization problems.

Assume the scenario of the communication system is in three-dimensional Euclidean space(R3).Steris a set of fixed terminal node,sis a fixed sink node,the aim is to deploy a setSrelof relay nodes satisfying that(a)for each terminal nodev∈Ster,there is a relay nodeu∈SrelwithDist(u,v) ≤Rcha;(b)for each terminal nodev∈Ster, there is a communication pathPv(a routing path)fromvto the sink nodessuch that the distance of any two adjacent nodes onPvis no larger thanRcom, and(c)the total communication cost (energy consumption)W(p) = ∑v∈VterW(Pv) is minimized, whereW(Pv) = ∑(a,b)∈E(Pv)EC(Dist(a,b)).For the total communication cost function, there is an implied assumption that each terminal work at the same frequency.Actually,the terminals do not work all the time.This fact leads to the trouble of calculating the total communication cost.Our assumption can deal with it and seems rational.

Obviously,for different models of the proposed sustainable wireless sensor network system,the corresponding combinatorial optimization problems will be different.In this paper,we consider two issues about the system.The one is the limitation for the number of relays to be deployed, and the other is candidate location restriction.For the former, the number of relays deployed in the system could be finite or infinite.For the latter,candidate locations could be anywhere or restricted to some fixed positions.Above all, we consider the following four cases (Case 1-4)which correspond to the problems SC-1,-2,-3 and-4,respectively:

(a)Case 1:The number of relays is finite and the candidate locations are restricted;

(b)Case 2:The number of relays is infinite and the candidate locations are restricted;

(c)Case 3:The number of relays is finite and the candidate locations are unrestricted;

(d)Case 4:The number of relays is infinite and the candidate locations are unrestricted.

Now,we are going to present the formal definition of the four problems as follows:

Definition 1. New Sustainable Communication Problem 1 (SC-1): Given a setSterof terminals nodes, a setSrelof candidate location nodes and a sink nodesin R3, communication cost functionEC,wireless communication radiusRcomand wireless charging radiusRcha,choose at mostkcandidate location nodes(the chosen candidate location node is a deployed relay node)such that:

(a)for eachv∈Ster,there is a relay nodeuwithDist(u,v)≤Rcha;

(b)for eachv∈Ster,there is a pathPvfromvto the sink nodesvia relay nodes,where the distance of any two adjacent nodes onPvis no larger thanRcom;

(c)the total communication cost is minimized.

Definition 2. New Sustainable Communication Problem 2 (SC-2): Given a setSterof terminals nodes,a setSrelof candidate location nodes and a sink nodesin R3,communication cost functionEC,wireless communication radiusRcomand wireless charging radiusRchachoose some candidate location nodes(the chosen candidate location node is a deployed relay node)such that:

(a)for eachv∈Ster,there is a relay nodeuwithDist(u,v)≤Rcha;

(b)for eachv∈Ster,there is a pathPvfromvto the sink nodesvia relay nodes,where the distance of any two adjacent nodes onPvis no larger thanRcom;

(c)the total communication cost is minimized.

Definition 3. New Sustainable Communication Problem 3 (SC-3): Given a setSterof terminals nodes,and a sink nodesin R3,communication cost functionEC,wireless communication radiusRcomand wireless charging radiusRcha,deploy at mostkrelay nodes such that:

(a)for eachv∈Ster,there is a relay nodeuwithDist(u,v)≤Rcha;

(b)for eachv∈Ster,there is a pathPvfromvto the sink nodesvia relay nodes,where the distance of any two adjacent nodes onPvis no larger thanRcom;

(c)the total communication cost is minimized.

Definition 4. New Sustainable Communication Problem 4 (SC-4): Given a setSterof terminals nodes,a setSrelof candidate location nodes and a sink nodesin R3,communication cost functionEC,wireless communication radiusRcomand wireless charging radiusRcha,deploy some relay nodes such that:

(a)for eachv∈Ster,there is a relay nodeuwithDist(u,v)≤Rcha;

(b)for eachv∈Ster,there is a pathPvfromvto the sink nodesvia relay nodes,where the distance of any two adjacent nodes onPvis no larger thanRcom;

(c)the total communication cost is minimized.

3.3 Computational Complexity Proofs

In this subsection,we will prove the computational complexity of the problems SC-1,-2,and-3.The results are summarized in the Tab.1.It shows that the two problems SC-1 and SC-3 are NP-hard,and the problem SC-2 is inP.However,the computational complexity of SC-4 is still open.

Table 1: A summary of the computational complexity of the problems

In our proposed new communication system model,the relays not only can be used for transmitting data but also can be used for charging terminals.Moreover,from the definitions of SC-1,we know that the number of relay nodes is limited.Furthermore, there is a simple observation that finding a minimum number of relays to charge all the terminals in R2in polynomial time is impossible unless P=NP.Because of these,we reduce the NP-hard problem Discrete Unit Disk Cover problem(DUDC)and the Unit Disk Cover problem(UDC)in Euclidean plane to a special version of SC-1 and SC-3 respectively,which proves the NP-hardness of SC-1 and SC-3.We prove the problem SC-2 is inPby providing an optimal polynomial algorithm for it.The details are as follows.

Theorem III.1.The problem SC-1 is NP-hard.

Proof:Note that the problem DUDC in Euclidean plane is NP-complete.Before proving the NPhardness of the problem SC-1, we show the formal definition of the optimization and the decision versions of the problem DUDC.

Definition 5.Minimum Discrete Unit Disk Cover problem(MDUDC):Given a setSofnpoints and a setDofmunit disks in the Euclidean plane,find a minimum setD′?Dsuch thatS∩D′=S.

Definition 6. Parameterized Discrete Unit Disk Cover problem (PDUDC): Given a setSofnpoints,a setDofmunit disks in the Euclidean plane and a parameterk,does there exist a setD*?Dwith cardinality at mostksuch thatS∩D*=S?

LetIDUDC=(S,D,k)be an instance of PDUDC in R2,whereS={p1,p2,...,pn}is a set ofnnodes,D={d1,d2,...,dm}is a set of unit disks in R2,and a parameterk.Now,we are going to construct an instancefor a special version of the problem SC-1(assume SC-1*)based onIDUDCas follows:

(1)For each nodepi∈S,create a terminal nodeti∈with the same coordinates ofpi;

(2)For each diskdi∈D,create a candidate location noderi∈with the same coordinates of the center ofdi;

(3)Letbe the radius of the unit disks inD;

(4)Create a sink nodeat any location such thatfor any terminalti∈;

(5)Letbe the value

(6)Letk*=k.

Fig.3 shows an instance of.Compared with SC-1,SC-1*holds three particularities.The first one is that all the terminal nodes,all candidate location nodes and the sink node are in a Euclidean plane(a special case of R3).The second one is that for any terminal nodev,the inequalityDist(v,)≤Rcomholds.In other words,each terminal can communicate with sink node directly.It means that the instance satisfies the communication condition even though no relay can be used to data transmission.The last one is thatDist(ti,chafor any terminalti∈Vter,which implies that the sink cannot charge any terminal.

Figure 3:An instance of ,where each terminal can communicate with the sink directly,the distance between each terminal and the sink is smaller than Rcom

In the following, we will prove that SC-1*is NP-hard by contradiction.Assume there is an algorithmAthat solves SC-1*in polynomial time.This means that if for any instanceI*of SC-1*,Acan find a subset?Vloc*with size atk*(if exists)such that for each terminal node∈,there exists at least one nodevloc∈withDist(vter,Vloc) ≤Rcha,and there is a communication path fromvtertovia the nodes in.Ifk*is the minimum number of relays charging all the nodes in, thenAcan outputs a valid solution forI*, sincehas the value max {Dist(ti,)|ti∈}.Thus,Acan find a minimum setD′?Dsuch thatS∩D′=Sin polynomial time,which contradicts to the fact that PDUDC is an NP-hard problem.

Corollary III.1.The problem SC-3 is NP-hard.

Proof:The NP-hardness proof of the problem SC-3 is almost the same as that of SC-1.The only difference between them is that we make a reduction from the UDC problem(not from the problem DUDC)in R2to a special version of SC-3.In the problem DUDC, there is a given set of discrete unit disks, which are corresponding to the chosen candidate locations nodes or the deployed relay nodes in the problem SC-1.But in the problem UDC,the solution space is continuous,which can be corresponding to the solution space of the problem SC-3.

Theorem III.2.The problem SC-2 is inP.

Proof:Since there is no limitation for the number of relay nodes,we can choose all of them first.And then,by using Dijkstra’s algorithm,we find a shortest transmission path from each terminal to the sink.Obviously,it is a polynomial optimal algorithm.

3.4 Two Heuristic Algorithms for SC-1

Note that once a problem is proved to be NP-hard, then it is reasonable to design heuristic algorithm for it.In this subsection,we give two heuristic algorithms for SC-1.The similar main idea of these two algorithms could be used to solve the other three problems.

The input of our algorithms consists of a set of candidate location nodesSloc, a set of terminal nodesSter, a sink nodes, a parameterk, wireless communication radiusRcomand wireless charging radiusRchar.The main idea of our algorithms can be summarized as follows:

(A)construct a graph based on the input instance of the problem SC-1;

(B)for each terminal node,find a shortest path from it to the sink node onG(assumePis the path set of these paths);

(C)find a minimal setD(a charging node set)of candidate location nodes such that for each terminal nodeu,there is at least one nodev∈Dsuch that inDist(u,v)≤Rcom;and

(D)use Local Search method to reduce the relay nodes ofVrel=Vlov∩(D∩V(P))if the number of vertices inVrelis larger than the number limitation of relays(parameterk).

For two different approaches of Local Search, we obtain two different algorithms.The whole algorithm can be divided into two phases.The first phase consisting of steps(A)-(C)is a subroutine to choose a set of candidate location nodes which satisfy the communication condition and the sustainability condition,but may not satisfy the number limitation of relays.Algorithm 1(called Relays Deployment Initialization,abbreviated as RDI))shows this phrase.The second phase,step(D),is to reservekby two different algorithms(Algorithm 2 and 3),which are called Relays Compression on Path(RCOP)and Relays Compression in Graph(RCIG),respectively.Therefore,our first algorithm for the problem SC-1 is made up of RDI and RCOP,and the second one consists of RDI and RCIG.

Now,we are going to show the details of steps(A)-(D)of our algorithms.

Step (A): It is natural to construct a graph based on the topology of network derived from the proposed system.In the following,we will show constructing an edge weighted-and-colored undirected graphG=V=(Vloc∪Vter∪{vsink},E=(Egrey∪Eblack)):

(a)for each candidate location nodeainSloc,create a candidate location vertexvaand add it toVloc;

(b)for each terminal nodeainSter,create a terminal vertexvband add itVter;

(c)for the sink nodes,create a sink vertexvsink;

(d)for each terminal nodeaand each candidate location nodeb,ifDist(a,b)≤Rcha,then create a black edge(va,vb)with weightc*Dist(va,vb)qand add it toEgrey;and

(e)for each candidate location nodeaand each candidate location (or terminal)nodeb, ifDist(va,vb) ≤Rcomand there is no black edge between them, create a grey edge (va,vb)with weightc*Dist(va,vb)qand add it toEblack.

Step(B):For each vertexv∈Vter,the algorithm uses Dijsktra’s algorithm to find a shortest path formvto the sink vertex.

Step (C): This step is to find a charging node setDofVterwith small size as possible.In our algorithms,the vertex setDcan be divided into two setsD1andD2,whereD1?V(P)consists of all the vertices adjacent to some vertex inVterby black edges.In the following,we just to show how to find the vertex setD2.LetGblack=((V1,V2),Eblack)be the graph induced by the edge setEblack,whereV1=Vter,V2=V(Eblack)V1.From the construction ofG, we know thatGblackis a bipartite graph,andD1?V2.LetV2*=V2D1, andV1*=VterNGblack(D1), whereNGblack(D1) is the vertex set ofD1’s neighbors inGblack.LetG*=(V*=(V*1,V*1)),E*)be a subgraph ofGblackinduced by the vertex setV*.Then,we use a simple greedy algorithm to find a minimal setD2?V2*dominating all the nodes ofV1*inG*.The greedy strategy is to choose a vertex fromV2*with maximum degree inG*step by step until all the nodes ofV1*are dominated,and the vertex setD2consists of all these chosen vertices.

Step (D): If |Vrel=Vloc∩(D∪V(P))|＞k, then we have to decrease the number of vertices inVreluntil it is no larger thank.To achieve this goal, we have two different ways (two different Local Search rules).They lead to two different heuristic algorithms,which are shown as the algorithms RCOP(Algorithm 2)and RCIG(Algorithm 3),respectively.Let graphGPbe the union of all paths inP.And if a vertexv∈VrelDis a degree-2 vertex inGP,then we color it with black.The strategy of our local search rules is to remove the black vertices under the communication condition and sustainability condition.Assumevis a black vertex on a pathP(a,vsink)ofP,andv+,v-are the two neighbors of a onP(a,vsink), wherev+,v-are on the pathP(a,v)andP(v,vsink)inGP, respectively.In the first rule, we consider the case that(v+,v-) ∈E.If so, we replace the sub-path (v+,v,v-)by (v+,v-)in all paths containing (v+,v,v-)inP(an example is shown in Fig.4a).After the implementation of such an operation, the number of vertices inVrelis decreased by 1.The algorithm RCOP executes this operation repeatedly until|Vrel|≤k.In the second rule,we refine the selection of black vertex as follows.If there exists a vertexu∈(V(P)Vter) such that(u,v+) ∈E, then we replace the sub-pathP(v+,vsink)by (v+,v-)andP(u,vsink)in all paths containingP(v+,vsink)inP, whereP(v+,vsink),P(u,vsink)are the paths inGPfromv+tovsink, and fromutovsink, respectively (an example is shown in Fig.4b).This operation implementation makes the cost of communication increased but the number of vertices inVreldecreased at least 1.For the greedy strategy, we define an evaluation indicator aswhereΔcost(v,u) andΔrelay(v,u) are the increment of communication cost and number of relay vertices decrement after replacing the sub-pathP(v+,vsink)by(v+,u)∪P(u,vsink) in all paths containing(P(v+,vsink))inP.LetΔ(v)=min{Δ(v,u)|u∈(V(P)Vter)}.In order to make the increment as small as possible,we pick the vertexv’with minimumΔ(v′)among all the vertices inB,and execute the paths replacement operation as the local search rule for each step in the algorithm RCIG until a relay vertex set with size of at mostkis found.

Figure 4: Two instances of local search rules,where the subgraph(a)shows the local search rule for the algorithm RCOP,and the subgraph(b)shows that of RCIG

Algorithm 1:RDI Input:a set of terminal nodes Ster,a set of relay nodes Sloc,a sink node s,k,Rcom,Rchar.Output:a graph G,a set of paths P,a set D ?Vloc dominating all the vertices of Vter,where Vter,Vloc are the vertex sets of G corresponding to Ster,Sloc respectively.01:Initial an edge weighted-and-colored undirected graph G,where G =(V =Vloc ∪Vter ∪Vsink,E =Egrey ∪Eblack) with Vloc = Vter = Vsink = ?and Egrey = Eblack = ?, a path set P = ?and vertices sets D=D1 =D2 =?;02:Construct G based on the input;03:if G is not connected then 04: Output‘The input is invalid’,and return;05:For ?a ∈Vter,find a shortest path from a to vsink on G by the Dijsktra’s algorithm,and add it to P;06:Let Gblack be an subgraph of G induced by Eblack;07:Let D1 =V(P)∩V(Gblack)Vter;08: Let G* = ((V*1,V*2),E*) be an induced bipartite subgraph of Gblack, where V*1 =VterNGblack(D1),V*2 =V(Gblack)VterD1;09:while V1 /=?do 10: find the vertex v ∈V*2 with the maximum degree in G*and add it to D2;11: V1 =V1NG*(v);12:end 13:return G,P* =P,D=D1 ∪D2;

Algorithm 2:RCOP Input:A graph G =(V =Vloc ∪Vter ∪{vsink},E),where Vloc,Vter,and vsink are a set of candidate location vertices,a set of terminal vertices,and a sink vertex respectively,E is an edge set,a set of paths P,a set of vertices D,and an integer k.Output:A set Vrel ?Vloc with|Vrel|≤k,a set of paths P*and the communication cost.01:Initially color all vertices in G to be white;02:Let GP be a graph constructed by combining all the paths of P;03:Color each vertex v ∈(V(P)∩VlocD)to be black if v is a degree-2 vertex in GP;04:Let B be the set of all the black vertices in GP;(Continued)

Algorithm 2:Continued 05:while|Vrel =(V(P)∪D)∩Vloc|＞k&&B/=?do 06: find a vertex v ∈B such that(v+,v-)∈E;07: replace(v+,v,v-)by(v+,v-)in all paths containing(v+,v,v-)in P;08: B=Bv;09:end 10:if|Vrel|≤k then 11: return Vrel,P* =P,and W (P);12:else 13: Output “Cannot find k candidate location vertices satisfying communication and sustainable conditions”.

Algorithm 3:RCIG Input:A graph G =(V =Vloc ∪Vter ∪{vsink},E),where Vloc,Vter,and vsink are a set of candidate location verti ces,a set of f vertices D put:A set V terminal vertices,and a sink vertex respectively,E is an edge set,a set of paths P,a set o,and an integer k.Outrel ?Vloc with|Vrel|≤k,a set of paths P*and the communication cost.01:Initially color all vertices in G to be white;02:Let GP be a graph constructed by combining all the paths of P;03:Color each vertex v ∈(V(P)∩VlocD)to be black if v is a degree-2 vertex in GP;04:Let B be the set of all the black vertices in GP;05:while|Vrel =(V(P)∪D)∩Vloc|＞k&&B/=?do 06: For a vertex v ∈B,let Δ(v)=min{Δ(v,u)=Δcost(v,u)Δrelay(v,u)|u ∈V(P)V(ter)};07: Let v′∈B be the vertex with minimum value of Δ,and Δ(v′)=Δ(v′,u′)=Δcost(v′,u′)Δrelay(v′,u′);08: Replace P(v’+,vsink)by(v’+,u’)and P(u’,vsink)in all paths containing P(v’+,vsink)in P;09: Update the black vertex set B;10:end 11:if|Vrel|≤k then 12: return Vrel,P* =P,and W (P);13:else 14: Output “Cannot find k candidate location vertices satisfying communication and sustainable conditions”.

4 Performance Analysis and Engineering Applications

In this section, we will illustrate some simulation experiments to evaluate the proposed two heuristic algorithms first.And then,we present an instance of communication system in a chemical plant as an engineering application of our proposed sustainable wireless sensor network system.

4.1 Performance Analysis

As we mentioned,the function of energy consumption isEC(Dist(a,b))=c*Dist(a,b)q,2 ≤q≤4.For sake of simplification,we set in ourc=1 andq=2 in our experiments.Taking into account the reality,we set the wireless communication radiusRcom=40 m and the wireless charging radiusRcha=15.Each experiment was performed 1000 times,and the value of each result is an average.All the terminals,candidate locations and the sink are randomly generated in a limited R3.

Tab.2 shows the simulation experiment results on the algorithm RDI.There are four different simulation scenarios,the size of which are 100 m*100 m*10 m,150 m*150 m*15 m,200 m*200 m*20 m,and 250 m*250 m*25 m,and the number of candidate location nodes in the scenarios are 100,225,400,and 625,respectively.For each scenario,there are five different values of terminal nodes number,which are 10,20,30,40,and50.It is easy to see that the communication cost and number of charging nodes increase with the growth of the number of terminal nodes.The reason is that the total communication cost is related to the number of communication path,which is determined by the number of terminal nodes.

Table 2: Experiment of the algorithm RDI

Fig.5 shows the performance of the algorithm RCOP and RCIG.In the experiments, there are four simulation scenarios(four cases)which are the same as that showed in Tab.2,and the number of candidate location nodes are also the same.However,the number of terminal nodes is fixed at 20.The horizontal axis shows different number limitation of relay nodes(parameterk),and the vertical axis shows the total communication costW(P).For the one hand,in each case,the total communication cost decreases with the growth of number of relay node.It is because of that the limitation of the deployed relay makes some shortest path deserted.On the other hand, the communication cost of algorithm RCOP is slightly larger than that of the algorithm RCIG.The reason is that,the local search rule in the algorithm RCOP just tries to find substituted edge between the nodes on some path.But,the local search rule in the algorithm RCIG tries to find that between any two nodes in the whole graph.However,less communication cost is obtained by more running time.For the algorithm RCOP,the total running time is(O(|V|3)).And the time complexity of RCIG is(O(|E||V|3)),which is larger than that of RCOP.

Figure 5:Performance of two algorithms RCOP and RCIG.The subgraphs(a)-(d)show the cases 1-4,where the size of simulation scenarios are 100*100*10,150*150*15,200*200*20 and 250*250*25,and the number of candidate location nodes in the scenarios are 100,225,400,and 625 respectively

4.2 Engineering Applications

Now,we are going to show an engineering application of our proposed sustainable wireless sensor network system.Let us see the scenario shown in Fig.6.In a large chemical plant, there are some fixed terminals,which are used to monitor,collect and transmit various parameters of reactors,storage equipment or environment,such as pressure,temperature,humidity,concentration of various chemical elements,etc.Moreover,there is a sink node,which connects the communication network with external network.At the side of the plant,there is a 4G station,which could deliver data to the control center.Assume there is a project that will last one to two weeks,the task of which is to gather the collection data from the terminals to the control center.Due to the reason that each parameter is very important for the running of equipments and the safety of the chemical plant,timely collection and transmission of collected data to a server or controller binding to the station is important and particularly necessary.Due to the needs of the project itself,the 4G station should be replaced by a 5G station.However,there is a problem for the coverage of the 5G station.In the scenario, the size of the plant is no less than 2000 m*1500 m.Nevertheless,generally,the 5G signal cannot be transmitted beyond 400 m.Moreover,compared with 4G signal,5G signal is more easily blocked by obstacles such as plant buildings and equipments.Hence, a 5G station cannot cover all the terminals.This will lead to two problems for the uncovered terminals.The one is that the data collected by them cannot send data to the control center.The other one is that if a terminal runs out of power it will not work,which makes the whole system cannot run properly.One reasonable way is to deploy a number of 5G stations such that all the terminals are covered.But this will cost a lot.

In this case,it is easy to see that using some relays to make up a wireless communication network with relays is a feasible way.In order to ensure that the terminal has continuous power supply, the relay deployed in the network should hold the function of wireless charging.If a terminal’s power is in the state of low-level, then the relays which are not far more than a certain value (radius of wireless charging)can charge this terminal.And more precisely, our proposed sustainable wireless sensor network system can be used to accomplish the extremely project shown in Fig.6.

Figure 6:An instance of chemical plant with fixed terminals,where a large part of terminals cannot communicate the 5G station directly

5 Conclusions

In this paper, we proposed a sustainable wireless sensor network communication system which holds the property of sustainable communication via charging the terminals by relays.And we extracted some combinatorial optimization problems from it for different cases under some reasonable assumptions.We have investigated these problems from the aspects of computational complexity,heuristic algorithms and engineering application.It is possible that our proposed system can be also suitable for some other applications in IoT.

Funding Statement:The authors would like to extend their gratitude to King Saud University(Riyadh,Saudi Arabia)for funding this research through Researchers Supporting Project number (RSP-2021/260).And this work was supported by the Natural Science Foundation of Hunan Province,China(Grant No.2020JJ4949),and the Postgraduate Scientific Research Innovation Project of Hunan Province(Grant No.CX20200883).

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.