An Asynchronous Clustering and Mobile Data Gathering Schema Based on Timer Mechanism in Wireless Sensor Networks

Jin Wang ,Yu Gao,Wei Liu,Wenbing Wu and Se-Jung Lim

Abstract:Recently,Wireless sensor networks (WSNs) have become very popular research topics which are applied to many applications.They provide pervasive computing services and techniques in various potential applications for the Internet of Things (IoT).An Asynchronous Clustering and Mobile Data Gathering based on Timer Mechanism (ACMDGTM) algorithm is proposed which would mitigate the problem of“hot spots” among sensors to enhance the lifetime of networks.The clustering process takes sensors’ location and residual energy into consideration to elect suitable cluster heads.Furthermore,one mobile sink node is employed to access cluster heads in accordance with the data overflow time and moving time from cluster heads to itself.Related experimental results display that the presented method can avoid long distance communicate between sensor nodes.Furthermore,this algorithm reduces energy consumption effectively and improves package delivery rate.

Keywords:Internet of things,wireless sensor networks,clustering,mobile data collection,timer.

1 Introduction

Wireless sensor networks (WSNs) [Bagde and Mehetre (2016)] takes a role of fundamental infrastructure for the Internet of Things (IoT),which owns the ability to perceive,handle and transmit information to upper layers.WSNs can be viewed as multihop and self-organizing networks connected by wireless communication between numerous micro sensor nodes.A sensor node has a major role for collecting data from the sustainable environment.WSNs have become very popular and essential in recent years and they provide pervasive computing services and techniques in different fields like combat surveillance,environment exploration,smart health,industrial and agricultural observation,smart home,etc.[Wang,Cao,Li et al.(2015); Wang,Abid,Lee et al.(2011)].

Sensors are generally battery-powered and once they exhaust their energy,they will be unserviceable.Nodes located around the sink consume more energy for information forwarding and that is so called “hot spot” phenomenon which resulting in a short lifetime to the system [Tirkolaee,Hosseinabadi,Soltani et al.(2018)].Thus,it is important to design optimized data collection algorithm to mitigate the unbalanced energy distribution and reduce the traffic burden of the center areas.With the purpose of addressing this issue,the mobile sink has been employed for network performance enhancement [Wang,Cao,Ji et al.(2017); Dahane,Berrached and Loukil (2015)].

Recently,numerous researches have begun to use mobile sinks to assist in gathering data in WSNs [Yasmine,Bouabdellah and Fayçal (2016)].Mobility Based Data Gathering schema can be classified as Mobile Sink Based Data Collection (MSDC),Single-hop Communication Based Data Collection (SHDC) and Rendezvous Based Data Collection(RBDC).In MSDC,sink node changes the location constantly during the process of data collection,and then data is transmitted to sink node by multi-hop communication.In SHDC,sink node needs to access each source node and gathers data by single-hop communication.RBDC concentrates on the data in sensor nodes nearby the moving path in advance,then sensor nodes transmit the data to sink node via the mobile sink.

Liu et al.[Liu,Fan,Zheng et al.(2011)],proposed a centralized approach to equally compute the optimum traffic load in each link and the suitable information gathering rate for each node.This method belongs to relay routing schema and it is based on static information gathering.However,their method could result in the uneven energy distribution of the system and many data dropped among sensors which locate around the static data collector.In Ren et al.[Ren,Liang and Xu (2013)],Ren et al.adopts a mobile sink to handle the data gathering issue and they only consider single-hop data transmission.They presented an extensible and distributed online solution which is independent of hypothesizes of global information to maximize data collection.Meanwhile,an offline method adopts the approximation ratio is also presented.However,this scheme may lead to limiting the system’s performance.

With the purpose of preserving the nodes’ energy,balancing traffic load as well as enhancing the lifetime of WSNs,an Asynchronous Clustering and Mobile Data Gathering based on Timer Mechanism (ACMDGTM) algorithm is presented to address the nonuniform energy consumption problem.Our contribution mainly contains the following points:

● We divide the wireless sensor network into a couple of square virtual grid rather than triangle or hexagon grid because of connectivity and coverage of the square.

● We adopt a distributed approach for cluster head election in accordance with their residual energy and geographical location,which can decrease energy consumption during intra-cluster communication.

● We determine an optimal moving path for mobile sink according to the overflow time of sensors and sink’s moving time to cluster heads.And the rendezvous points are utilized to enhance the efficiency of data collection.

The rest part of the article is organized as follows.Some relevant literatures are briefly introduced in Section 2.Section 3 gives several basic assumptions and presents model of network and energy.Then our Asynchronous Clustering and Mobile Data Gathering based on Timer Mechanism (ACMDGTM) algorithm is presented detailly in Section 4.Analysis and explanation of simulation is shown in Section 5.Section 6 makes a conclusion for the whole paper.

2 Related work

2.1 Overview of clustering method

A famous clustering algorithm for WSNs is presented by Heinzelman et al.[Heinzelman,Chandrakasan and Balakrishnan (2000)],which is called LEACH,and it decreases energy consumption by utilizing a dynamic clustering method.LEACH is a routing protocol in WSNs where sensors are homogenous and the base station is fixed,and it selects cluster head randomly according to a threshold value as given in Eq.(1).Here,r represents the current round andPdenotes the percentage of cluster heads in all nodes.G is the collection of sensors which have not been elected as cluster heads during1/Prounds.After the random selection,cluster heads broadcast information to nearby nodes for clustering.Nearby nodes receive the invitation and choose the cluster head with the closest distance to join.Then cluster members send data to its corresponding cluster heads.Finally,the fused data is forwarded to the base station by cluster heads.However,the main shortcoming of LEACH mainly appears in the uneven distribution of cluster heads and the frequent cluster formation consume more energy during each round in LEACH.

PEGASIS [Lindsey,Raghavendra and Lindsey (2003)] as a chain-based protocol has achieved great improvement compared to LEACH.In PEGASIS,each node only concerns its relayer which is closer to the sink and the chain is formed utilizing greed algorithm.Leaders are elected by turns to communicate with the sink.The chain construction reduces the energy consumption,meanwhile,it results in heavy network latency.

2.2 Mobility-based sink collection

Compared with gathering data by a static sink,introducing sink mobility technology for data gathering can make a more evenly energy distribution and prolong the network’s lifespan.Velmani et al.[Velmani and Kaarthick (2015)] proposed a clustering method using a tree construction which economizes energy and adjusts the link during data gathering.It constructs the Data Collection Tree (DCT) to design optimal path with the mobile sink,thereby avoiding frequent cluster formation and reducing the heavy burden of cluster heads.

Xie et al.[Xie and Pan (2016)] considered a periodically data gathering method which introduces mobile data collector.The mobile data collector gathers data from cluster heads via single-hop communication,and once it traverses all the cluster heads it will return to the starting point.They try to search an obstacle-avoiding path utilizing spanning graphs to realize an efficient resource scheduling.Cheng et al.[Cheng and Yu(2016)],focus on shortening the moving path to reduce the data delay.They mainly consider that the mobile sink can visit the overlapping area of nodes rather than visiting one by one.

In Wang et al.[Wang,Guo and Yang (2016)],with the purpose of evenly distributing energy consumption,Wang et al.employed a mobile agent to gather data from appointed nodes.An adaptive method is developed for inter-cluster data transmission as well as maximizing network utility.

Zhao et al.[Zhao,Yang and Wang (2015)] proposed a LBC-DDU methodology with a mobile sink.The construction of their presented system contains three layers.The bottom layer is consisted of numerous sensors,and they form clusters in a self-organized way.Nodes with rich energy are more likely to be chosen as cluster heads in each cluster.The middle layer contains all the cluster heads and the top layer is SenCar layer.After SenCar receives the information from cluster heads,it utilizes this information to schedule the sojourn points for SenCar.Finally,this algorithm adopts a dual data transmission for SenCar to gather information from multiple targets and enhance the data gathering efficiency.Their results showed that LBC-DDU algorithm greatly economizes the energy of the network and enhances the data gathering efficiency of SenCar.Whereas,its drawback is that it is difficult to choose the suitable sojourn points for energy balancing.In Jian et al.[Jian,Jian,Tian et al.(2017)],the authors proposed a multi-hop clustering method which employs multiple mobile sinks for balancing the traffic load.For some delay sensitive application,authors introduce sojourn points and rendezvous nodes to simplify the moving path of collectors.As a result,the authors analyzed the lifetime in different situations and saved much energy by balancing the load.

In Xue et al.[Xue,Jiang and Zhao (2017)],the authors presented a global adaptive candidate selection method to optimize energy consumption called ABC algorithm.With the purpose of creating a fair comparison environment,they set each method the same initial population on test function.They applied this algorithm to the clustering problem for improving the efficiency of the whole network.

In order to maximizing total bandwidth utility for proportional fairness,Cheng et al proposed a clustering and scheduling based energy efficient routing method [Cheng,You,Fu et al.(2016)].The algorithm was composed of two parts.In clustering phase,each sensor chooses a suitable cluster heads in accordance with the consumed energy.Then they achieved the proportional fairness via time-slot resource.

In Sharma et al.[Sharma,Bansal and Bansal (2017)],the authors proposed clustering method called HEC in the energy heterogeneous network to reduce energy consumption.They allowed only advanced nodes to be cluster heads in the initial stage.In the second stage,they allowed all nodes to be selected as cluster heads.Finally,they let clustering relaxed in direct transmission.

Liu et al.[Liu,Duan,Wanet al.(2017)] proposed a hybrid copolymerization method based on data bottleneck by combining fuzzy co-clustering and possibility clustering.They proved that their algorithm has better accuracy and robustness.In Kumar et al.[Kumar,Sahoo and Kumar (2017)],authors achieve some improvement based on CSO algorithm.They utilize opposition-based learning as well as Cauchy mutation to increase the multiformity of the CSO algorithm.

Some other work utilizes sink mobility technology with the combination of computational intelligence techniques in wireless sensor networks can be found in Wang et al.[Wang,Cao,Sherratt et al.(2017); Wang,Zuo,Shen et al.(2015); Wang,Cao,Li et al.(2017); Wang,Ju,Gao et al.(2018); Wang,Cao,Ji et al.(2017)].The authors therein mainly applied Ant Colony Optimization (ACO),Glowworm Swarm Optimization (GSO)as well as Particle Swarm Optimization (PSO) algorithms to optimize the network perforce during the routing phase.

3 System model

3.1 Basic hypothesis

We assume that our network consists of a single mobile sink and a large number of fixed sensors.We make the following basic hypothesis:

● Sensors keep motionless and the network is homogeneous after random deployment.

● All the sensors are battery-powered and non-rechargeable so that once node exhausts its energy,it will be useless.

● We assume that the wireless communication channels are always in the ideal state and there is no collision occurring during transmission.

● The mobile sink is carried by an intelligent car or a robot and it can move freely among the sensor field in a constant speed.

● Sensors have a limited transmission range whereas the mobile sink is not restricted to energy and it has an adequate transmission range to communicate with any node in the network.

3.2 Network model

We setNsensor nodes dispersed within a square area with side length L and sensors are represented byN= ｛n1,n2,n3,......,nn｝respectively.We deploy a single mobile sink in the bottom right corner of the rectangle field.The sensor field is cut into some square virtual grid with length of side l,as Fig.1 shows.

Figure1:Network model

We regard each virtual grid as a cluster and the whole sensor field can be denoted asC= ｛c1,c2,c3,......,cn｝.In order to ensure any node in a cluster can communicate with others freely,the side length l should satisfy the following equation:

Where R represents sensors’ communication range.The margin of the sensor field may not large enough to satisfy the above condition and we still see them as a cluster.

3.2 Energy model

Sensors are generally energy constrained in practical application scenarios,and it is not cost-effective to change batteries for sensors in general,which reduce the life of WSNs to some extent.The first radio energy model [Ahmad,Javaid,Imran et al.(2016)] is applied to calculate the energy consumption during data transmission in this paper.Due to the power dissipation of transmission unit in sensors is much bigger than the sum of other units,we only take energy used in transmission into consideration.As Fig.2 shows,the energy consumed during the transmission process is composed of sending and receiving.

Figure2:Energy model

The free space as well as the multi-path fading model is adopted based on the transmission distance between source node and target node [Wang,Yin,Zhang et al.(2013)].We choose the free space model when the transmission distance is under a thresholdd0,otherwise,the multi-path fading model is chosen.The energy the sender consumes for transmitting k-bit length data through a distancedCan be calculated as follows:

whereEelecdenotes the energy dissipation used for sender or receiver circuit.The amplification coefficient under two different is represented byεfsandεmprespectively.k is the amount of data transmitted.

The energy consumed k-bit data receiving can be calculated using Eq.(4):

4 Our proposed timer-based mobile data collection approach

In this section,an Asynchronous Clustering and Mobile Data Gathering based on Timer Mechanism (ACMDGTM) algorithm which introduces a mobile sink is presented.Each cluster elects its cluster heads in accordance with nodes’ residual energy as well as their position.Additionally,we schedule an optimal moving path according to nodes’ data overflow time and mobile sink’s arriving time.In our algorithm,nodes in each cluster send data to their corresponding cluster heads and mobile sink traverse all cluster head for data gathering.

4.1 Initializing the network

Nsensors are set within a square area the length of which is L,and they are denoted byN= ｛N1,N2,N3,......,Nn｝respectively.Initially,the sensor field is cut into amounts of square grid as shown in Fig.1.

Figure3:Cluster formation

4.2 Selecting the cluster heads

Different from other clustering methods,we divide the network into square virtual grids with l side length and each grid represents a cluster.

As shown in Fig.3,blue square represents the cluster heads and the red triangle on the boundary is the mobile sink.Next,we will discuss the selection of cluster heads.

This algorithm uses Asynchronous mechanism to select cluster head.The selection process considers node location and its residual energy.Each member node builds appropriate route and then they send data to their corresponding cluster heads.The flow chart for cluster head selection is shown in Fig.4.

Figure4:The selection of cluster head in one cluster

Step 1:We firstly choose the node which owns a minimum d as a candidate cluster head.The value of d which represents transmission efficiency between the cluster head and its members is shown in Eq.(5):

where (xi,yi)represents coordinate of the candidate cluster headiand (xj,yj)represents coordinate of its neighbors.Neiidenotes the set of neighbors of nodei.

Step 2:The candidate cluster headiCalculatesT(i)according to Eq.(6),where SymbolEiandEjrepresent the residual energy of candidate cluster headiand its neighborjrespectively.Neiidenotes the set of neighbors of nodei.

Step 3:IfT(i)is more than zero,candidate cluster headibroadcast a successful selection message among the whole cluster to claim it as a final cluster head.Otherwise,this paper recalculated the value ofT(i)in accordance with selecting the node which owns a secondary minimum value of d untilT(i)is a nonnegative real number.

4.3 Process of intra-cluster routing

The process established for intra-cluster data transmission is shown as Fig.5,and the details are as follows.

Figure5:Flow chart of intra-cluster data transmission

Step 1:After the cluster heads are selected successfully,these cluster heads broadcast their ID,position and residual energy within the maximum transmission radius to claim itself as a final cluster head.

Step 2:When other nodes receive the information from cluster heads,they record this information.

Step 3:Member nodes reply a join-cluster message to join the corresponding clusters.

The cluster head selection only needs the corresponding information within the cluster so that it can be conducted distributedly in each virtual grid at different times.Frequent cluster heads selection will lead to unnecessary energy consumption and each cluster reselect its cluster head only whenT(i)does not satisfy the condition.

4.4 Mobile sink accessing cluster heads

We firstly define several rendezvous points in the sensor field.The rendezvous points should be covered by as many cluster heads as possible.Therefor we set rendezvous points at the junction of clusters and it is shown as Fig.6.

Figure6:Rendezvous points selection

Mobile sink set timers for each cluster head to record the time since it visited the cluster heads last time.When mobile sink completes a data transmission for a cluster head,it will restart its timer for the corresponding head.The best moving path of the mobile sink is searched according to data overflow time of cluster heads and moving time from cluster heads to itself.Eq.(7) is the weighted sum about mobile sink to cluster headCHi:

whereT0represents data overflow time of sensors andTCHirepresents the time the cluster head has restored the data packages.Tmrepresents the moving time of the mobile sink needs to spend to access the cluster heads and it can be calculated as:

WhereReCHidenotes the closest rendezvous point ofCHifrom the current position of the mobile sink andVmdenotes the mobile sink’s speed.

After calculateWCH,the mobile sink chooses the cluster head with minimumWCHas its next destination and it will visit the corresponding closest rendezvous points for data collection until all cluster heads are visited.

5 Experimental results

5.1 Simulation environment

In order to analyze the performance of our presented schema,we introduce Matlab simulator here.300 sensors are deployed randomly within a square area with 400 m side length.Tab.1 introduces the relevant parameters used in the simulation.

Table1:Simulation parameters

5.2 Performance analysis

We evaluate our ACMDGTM algorithm compared with the classical LEACH and TCBDGA algorithms about the lifetime of the network,round when the first node dies and data delivery.

Lifetime is regard as an essential index to evaluate the quality of the network.The number of nodes alive can reflect the lifetime of the whole network.We assume that there is no other reason to affect nodes of death except depletion of energy.As is shown in Fig.7,there are no sensor nodes alive for LEACH and TCBDGA algorithms when the round is close to 830 and 1080 respectively.However,in our proposed schema,the selection of cluster heads considers location as well as residual energy of nodes via virtual grids rather than selecting randomly.So,the number of rounds is close to 1350 when alive nodes become zero in proposed algorithm.Compared with the LEACH and TCBDGA algorithm,our presented ACMDGTM schema can better enhance the network’s lifetime.

Figure7:Comparison of alive nodes

We define the network lifetime as the time when the first sensor node exhausts its energy.Thus,Tab.2 illustrates the rounds when nodes in the network begin to die of these three methods.It can be seen that ACMDGTM algorithm is superior to LEACH and TCBDGA.

Table2:Round when nodes begin to die

In Fig.8,the network lifetime with different initial energy for three algorithms is demonstrated.The mobile sink accesses cluster heads in ACMDGTM algorithm based on data overflow time of cluster heads and moving time from cluster heads to itself.Therefore,as the initial energy increases,round of presented methods when nodes to die is great put off than the LEACH and TCBDGA algorithm.

Figure8:Comparison of round when the first node dies

Figure9:Comparison of data delivery

From Fig.9,it can be seen that as the number of round increases,packets delivered by node increases accordingly.The reason is that ACMDGTM algorithm selects optimal cluster heads and uses the mobile sink to gather data from cluster heads.Furthermore,this algorithm reduces the transmission path and improves the efficiency of data collection more than other two algorithms.

6 Conclusion

In this paper,we present an Asynchronous Clustering and Mobile Data Gathering schema based on Timer Mechanism (ACMDGTM) with a single mobile sink in wireless sensor networks.In ACMDGTM,the location and residual energy are both considered when selecting cluster heads.The mobile sink searches the optimal moving path according to the data overflow time and moving time from cluster heads to itself.Because of these reasons,the simulation results indicate that the presented schema outperforms than the LEACH and TCBDGA algorithms in aspects of minimizing energy consumption and maximizing the lifetime of network.

Acknowledgments:This work is supported by the National Natural Science Foundation of China (61772454,61811530332,61811540410,U1836208).