Energy-Efficient Routing Algorithm Based on Small-World Characteristics

Qian Sun,Gongxue Cheng,Xiaoyi Wang,＊,Jiping Xu,Li Wang,Huiyan Zhang,Jiabin Yu,Ning Cao and Ruichao Wang

1School of Artificial Intelligence,Beijing Technology and Business University,Beijing,100048,China

2Beijing Laboratory for Intelligent Environmental Protection,Beijing,100048,China

3Shandong Chengxiang Information Technology Co.Ltd.,Dezhou,253000,China

4University College Dublin,Dublin4,Ireland

Abstract:Water quality sensor networks are widely used in water resource monitoring.However,due to the fact that the energy of these networks cannot be supplemented in time,it is necessary to study effective routing protocols to extend their lifecycle.To address the problem of limited resources,a routing optimization algorithm based on a small-world network model is proposed.In this paper,a small-world network model is introduced for water quality sensor networks,in which the short average path and large clustering coefficient of the model are used to construct a super link.A short average path can reduce the network’s energy consumption,and a large coefficient can improve its fault-tolerance ability.However,the energy consumption of the relay nodes near the heterogeneous node is too great,and as such the energy threshold and non-uniform clustering are constructed to improve the lifecycle of the network.Simulation results show that,compared with the low-energy adaptive clustering hierarchy routing algorithm and the best sink location clustering heterogeneous network routing algorithm,the proposed improved routing model can effectively enhance the energy-utilization.The lifecycle of the network can be extended and the data transmission amount can be greatly increased.

Keywords:Water quality sensor networks;small-world characteristics;clustering routing protocol;heterogeneous clustering

1 Introduction

Environmental protection is an important topic,and safeguarding ecology and the environment has become a global research focus.In particular,the protection of the water environment is an important part of ecological protection [1].Advancements in the Internet of Things,big data,and others have resulted in the increasing usage of real-time environmental monitoring technology using wireless sensor networks (WSN).However,some problems still exist,such as limited resources [2,3].Experts have done a significant amount of research regarding this issue,e.g.,the energy-efficient fuzzy routing protocol for wireless sensor networks proposed by Jain et al.[4],the energy efficient protocol for routing and scheduling in wireless body area networks proposed by Yang et al.[5],and the energy-aware and load-balanced distributed geographic routing algorithm for wireless sensor networks with a dynamic hole proposed by Hadikhani et al.[6].Wang et al.[7],on the other hand,proposed an event-driven routing protocol for WSNs.

Although scholars carried out numerous pertinent studies,the problem of the limited network lifecycle caused by limited resources is still severe.To solve this problem,we propose a nonuniform clustering routing optimization algorithm based on small-world characteristics.Compared with the traditional routing protocol,it can effectively improve resource utilization,and has practical operability for water environment monitoring.

2 Construction of a Water Quality Sensor Network with Small-World Characteristics

2.1 Construction of a Water Quality Sensor Network

To protect the water environment,a flow model was built to simulate the working process of a water quality sensor network under practical water environment conditions.Water quality sensors were deployed to measure water quality parameters.The water quality sensor network was formed by a routing protocol and fed back to the monitoring and control center.Throughout the monitoring process,the water quality sensor nodes were powered by batteries,and the total energy of the entire network was limited.As shown in Fig.1,100 sensor nodes were deployed in the water,and consume the network’s energy over time.The black solid dots in the figure are the cluster head nodes.After deployment of the network,all nodes become green with sufficient energy.As time passes,due to uneven energy consumption,some of the nodes consume energy very fast,and their color gradually changes from green to red.When the nodes are dead,they are denoted as black circles.Therefore,it is important to overcome the resource limitations of wireless sensor networks and facilitate network monitoring through an effective routing algorithm.In this paper,we propose an effective method of maximizing the network lifecycle.

2.2 Small-World Network Model

The small-world characteristics of complex networks were analyzed to address the energy problem.The concept of small-world characteristics was proposed by Watts and Strogatz in 1998.A small-world network requires that a network with a small average path length still has a large clustering coefficient.The definition of a small-world network is as follows:if the distance L between two randomly selected nodes in the network (i.e.,the number of hops required to access each other) increases proportionally with the logarithm of the number of nodes n in the network,i.e.,L∝logN,the clustering coefficient of the network is not small [8].In small-world networks,most nodes are not adjacent to each other,but the neighbors of any given node are likely to be adjacent to each other.Most nodes can be accessed from any other node with few hops.The final coupling network that results whenn=16,k=8,andP=0.8 is shown in Fig.2.

2.3 Text Layout Construction of the Water Quality Sensor Network

Heterogeneous nodes are deployed to form a small-world network model with super links.The preset common nodes are powered by batteries,and their energies are limited.However,the energies of heterogeneous nodes can be supplemented.In the network model,sink nodes exist in the monitored area,and ordinary nodes transmit the monitored information to the sink node through multiple hops or super links.It is specified that each node in the network cannot move and has a unique ID.The steps of constructing a Watts-Strogatz small-world model (WS smallworld model) are as follows:starting from the regular graph,n nodes form a ring,in which each node is connected with each K/2 node that is adjacent to it,where K is an even number [9].An evolution diagram of the small-world model is shown in Fig.3.The deployment location of heterogeneous nodes in the network model is based on the ant colony algorithm [10].A transmission path diagram of the multi hop transmission of ordinary nodes in the network with super links is shown in Fig.4.

Figure 1:Plots of energy vs.time (a) Initial energy (b) Energy after 600 h (c) Energy after 850 h(d) Energy after 1150 h

Figure 2:Final coupling network:n=8,and P=16

Figure 3:Evolution of small-world model

Figure 4:Network model with super links

3 Improved Routing Protocol for Water Quality Sensor Networks Based on Small-World Characteristics

3.1 Analysis of Small-World Network Model

In wireless sensor networks,a shorter average path can reduce the energy consumption of the network,and a larger clustering coefficient can improve the fault tolerance ability of the network.Therefore,the network can continue to work when some nodes are dead,which can improve the network lifecycle [11].Regarding the construction of wireless sensor networks with small-world characteristics,Zhang et al.[12]suggested that the introduction of small-world characteristics can optimize the energy utilization rate of the network,thereby extending the lifecycle of the network.

A routing protocol based on small-world characteristics (RPSC) is introduced in this paper.We find that there are still some shortcomings in the RPSC.In heterogeneous sensor networks with small-world characteristics,ordinary nodes adopt a greedy routing strategy according to their location [13],and directly send the monitored water quality information to the sink or heterogeneous nodes,as shown in Fig.4.The solid lines represent super links,and the whole network is equivalent to the cluster routing network with heterogeneous nodes as cluster heads [14].When an ordinary node is one hop away from a sink node or heterogeneous node,it is necessary to transmit data to the sink or heterogeneous node through some relay nodes near the sink or heterogeneous node.As shown in Fig.5,node a,which is near the heterogeneous nodehj,transmits data frequently;however,the energy consumption of node a is too fast,leading to uneven energy consumption of nodes in the network and thus affecting the network lifecycle.Similarly,ordinary nodes must transmit data to the sink node through relay nodes near the sink node,which aggravates the energy consumption of the relay nodes near the sink.In addition,each node that monitors the data directly sends the data to the heterogeneous node or the sink [15].A large amount of unprocessed data will lead to data redundancy and increase the energy consumption of the network.Therefore,it is necessary to improve the RPSC.

Figure 5:Heterogeneous node transmission mode

3.2 Non-Uniform Clustering Routing Optimization Algorithm for Water Quality Sensor Networks with Small-World Characteristics

To solve the problem of fast energy consumption and data redundancy of the nodes that are near sink and heterogeneous nodes,an improved routing protocol based on small-world characteristics (IRPSC) is proposed by introducing the idea of non-uniform clustering.In a non-uniform cluster,the cluster head is the manager of the data transmission.An energy threshold is proposed to select the cluster head through multiple iterations.Thus,an effective energy consumption model is established.

The common nodes that are close to the heterogeneous nodes are responsible for the relay task and exhibit a high energy consumption.The same problem exists near the sink nodes.The idea of non-uniform clustering is used for optimization [16-20],as shown in Fig.6.The optimal number of heterogeneous nodes of a 100×100 network is two,and their locations are random [21].

Figure 6:Heterogeneous nodes with heterogeneous clustering

The energy consumption of the nodes closer to the heterogeneous nodeshiandhjand the sink node is great,and the energy consumption of the member nodes in the cluster is low.The cluster head node is responsible for transmitting less data in the cluster to balance the energy consumption.The maximum radius of the cluster is set toRmax.By controlling the radius range,the nearest competition radius between the sink and heterogeneous nodes is(1-c)Rmax,wherecis the parameter used to control the range of values,c∈(0,1).The competitive radiusRCHof cluster headVCHis

wheredmaxanddminare the maximum and minimum distances of the network nodes away from the sink node,respectively,andrepresents the distance from nodeVto the sink or heterogeneous nodeshiandhj.The competition radius is determined by Eq.(1),and a list of the energy statuses of the member nodes in the cluster is generated.The node with the largest energy value is selected as the cluster head node.

Clusters of different sizes are formed according to the distance between the ordinary nodes and heterogeneous nodes,and cluster heads are selected in rounds.Because the cluster head is responsible for the information transmission between heterogeneous nodes,the node with the largest energy value in the cluster is selected as the cluster head node.On this basis,the energy thresholdE(n)is set.When the energy of the cluster head is less than the energy threshold,the next round of cluster head selection is conducted,and the current cluster head is used as the node in the next round of the selection.The maximum energy of the common nodes isEmax,that is,the current energy of cluster head nodes isE≤Emax.The specified energy threshold is

wherenis the number of member nodes in the cluster after the competition radius is determined by Eq.(1),andE1,E2,...,Enare the energy statuses of each member node.According to Eq.(2),the node with the largest energy in the cluster is selected as the cluster head node in the first round.As the network runs,the cluster heads quickly consume energy.To avoid death of cluster head nodes,they are selected in rounds,which also balances the energy of cluster members.To prolong the lifecycle of the network,after the cluster head selection is completed,if a node does not detect water quality information,it enters the idle state;the energy consumption in the idle state is larger than that in the sleep state.In order to further reduce the energy consumption of nodes and prolong the lifecycle of the network,the idle nodes are set to the sleep state.

The data transmission mode in the network is shown in Fig.7.Water quality sensor nodes that detect water quality information can be divided into the following two situations according to the distance between the node and sink:the distance betweenV1and the sink is within one hop,so the data are directly sent to the sink,and the distance betweenV2and the sink is too far to arrive in one hop.At this time,nodeV2sends data to the cluster head of V2,VCH.Then,the distance betweenVCHand the sink is determined.In the second situation,as for the distance betweenV2and the sink,there are three sub-situations as shown in Fig.7.When the distance between the cluster head nodeVCH1and the sink is within one hop,the processed data is directly sent to the sink.When the distance between the cluster headVCH2and heterogeneous nodeh1is within one hop,the processed data is sent to heterogeneous nodeh1,and then transmitted to the sink byh1’s super link.Lastly,for cluster headVCH3,because the distance to the sink and heterogeneous node is too far for the data to arrive in one hop,the data is transmitted to the nearest heterogeneous nodeh2by other cluster head nodes,and then transmitted to the sink by the super link ofh2.

In IRPSC,by using the idea of non-uniform clustering,ordinary nodes transmit data to the cluster head.The cluster head can compress the data of the member nodes in the cluster to reduce energy consumption during data transmission.However,due to the rotation of the cluster head,the transmission path between nodes changes,and thus the energy consumption of network nodes is uniform and the lifecycle of the entire network is improved.In addition,the effective energy threshold and sleep state control can balance the energy consumption of the network and further improve the overall lifecycle of the network.

Figure 7:IRPSC data transmission mode

The number of heterogeneous nodes to be deployed in the water quality sensor network is specified asβ,and the deployment locations ofβheterogeneous nodes are found by an ant colony algorithm [22].The number of ordinary nodes isn,and the cluster number of ordinary nodes isnCH.A flow chart of the IRPSC algorithm is shown in Fig.8.

4 Simulation and Discussion

To prove the effectiveness of the IRPSC algorithm,two kinds of heterogeneous algorithms were introduced:the improved LEACH-C (ILC),and best sink locations (BSL).To analyze the experimental results,MatLab (MathWorks,USA) was used to carry out simulation experiments.It was assumed that 100 nodes were randomly distributed in the 100×100-m2network area,and the sink node was located in the interior of the sensor network area.

Fig.9 shows the simulation comparison of the number of dead nodes in each round of the four algorithms being compared.The experimental results show that the IRPSC algorithm has the longest network lifecycle,while the ILC algorithm has the shortest.

The data transmission amount of the four algorithms is compared in Fig.10.The RPSC algorithm is used after introducing small-world characteristics,and the IRPSC algorithm is an improved algorithm also used after introducing small-world characteristics.Comparing the number of surviving nodes in each round,it can be seen that the RPSC algorithm can effectively extend the network lifecycle after introducing the small-world model.However,there are still some deficiencies due to the death of the relay nodes and data redundancy.The IRPSC algorithm can extend the lifecycle much more than the RPSC algorithm because of the introduction of the nonuniform clustering and the specification of an effective energy threshold.After the improvement,the energy utilization rate of the network is further improved,the lifecycle of the network extended,and the data transmission amount greatly increased.

Figure 8:IRPSC algorithm flowchart

Figure 9:Network lifecycle

Figure 10:Data transmission amounts

5 Conclusions

In view of the limited resources available to water quality sensor networks,the energy consumption of the network can be reduced by constructing super links by introducing the small-world model of complex networks.However,the network is still inadequate.Based on the construction of a water quality sensor network with a small-world model,a heterogeneous sensor network is built based on the idea of heterogeneous clustering.Data compression and other processes are used to reduce energy consumption in the data transmission process.A cluster head rotation mechanism shortens the transmission path of nodes and controls the sleep state so that the energy consumption of network nodes is uniform and the network lifecycle is prolonged.

Funding Statement:This research was funded by the National Natural Science Foundation of China (Grant No.61802010),Hundred-Thousand-Ten-Thousand Talents Project of Beijing(Grant No.2020A28),National Social Science Fund of China (Grant No.19BGL184),and Beijing Excellent Talent Training Support Project for Young Top-Notch Team (Grant No.2018000026833TD01).

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