ZHAI Pu，ZHANG Deyu，LIU Siwei

(1.Shenyang Ligong University,Shenyang 110159,China;2.International School,Beijing University of Posts and Telecommunications,Beijing 100000,China)

A Location-Based Clustering Topology Control Algorithm in WSN

ZHAI Pu1，ZHANG Deyu1，LIU Siwei2

(1.Shenyang Ligong University,Shenyang 110159,China;2.International School,Beijing University of Posts and Telecommunications,Beijing 100000,China)

Aiming at the existing problems in Leach algorithm,which has short network survival time and high energy consumption,a new location-based clustering topology control algorithm is proposed.Based on Leach algorithm,improvements have been done.Firstly,when selecting cluster head,node degree,remaining energy,and the number of being cluster head，these three elements are taken into consideration.Secondly,by running the minimum spanning tree algorithm,the tree routing is constructed.Finally,selecting the next hop between clusters is done by MTE algorithm.Simulation results show that the presented control algorithm has not only a better adaptability in the large-scale networks,but also a bigger improvement in terms of some indicators of performance such as network lifetime and network energy consumption.

Wireless Sensor Network;location information;clustering;the minimum spanning tree;topology control

Network topology control is pointing that under the premise of meeting network coverage and connectivity,a data forwarding optimization network structure can be formed through the power control and selection of backbone node and elimination of unnecessary communication link between nodes.Good network topology and topology control algorithm can improve the efficiency of routing and MAC protocol,and lay the foundation of data fusion,time synchronization and object localization etc.,and even can prolong the network lifetime by reducing the energy consumption.Therefore,topology control is one of the core technologies in sensor networks.

Scholars have shown that the hierarchical topology control[1]is an effective method to reduce the energy consumption of the network.Among them,Leach[2](Low Energy Adaptive Clustering Hierarchy)algorithm is the first hierarchical topology control algorithm proposed in wireless sensor networks.The random election of cluster head in the algorithm easily leads to uneven distribution of cluster head.At the same time,it does not take into account the factors such as residual energy,resulting in that some nodes with low remaining energy are selected as cluster heads,which leads to premature death of that node.Aiming at the deficiency of Leach,paper[3]proposed centralized cluster head election algorithm,namely Leach-C(Leach-Centralized)clustering algorithm.This method takes into account the election of its own resource,but this centralized control algorithm increases the load of network.Paper[4]proposed GAF(Geographic Adaptive Fidelity)algorithm,which considers the location information of sensor nodes,and the monitoring region is divided into a plurality of square cells,and direct communication can be achieved between adjacent cells.While in real-world networks,nodes in adjacent cells are difficult to complete a jump communication.In addition,if the communication radius is smaller,the partition of region will be smaller,which increases the number of network clusters and the cluster efficiency is not high.

Aiming at the shortcomings of Leach algorithm,a new location-based clustering topology control algorithm is proposed in this paper.The algorithm determines the numbers of optimal cluster firstly,then the network is divided into a plurality of hexagonal area and each region gathers into a cluster.When selecting the cluster head in the cluster area,three elements including the residual energy of node,the node degree and the times having been cluster head are taken into consideration.In addition,the TDMA mechanism is to be run within the cluster and the CSMA/CA mechanism will be run between the clusters to reduce the consumption of communication between nodes.

1 NETWORK MODEL

This algorithm will divide the network into non-overlapping hexagonal regional,and area number is defined as:

Areaid={(col,line)|col=GetCol(xi,yi,d),line=GetLine(xi,yi,d)}

Among them,where(xi,yi)is coordinate of the nodei,drepresents the hexagon side.The network model of the algorithm is shown in figure 1.

Figure 1 Network model

2 DETAILED DESCRIPTION OF THE ALGORITHM

2.1 The basic idea

The algorithm determines the length of regular hexagon region according to the optimal cluster number.Sensor nodes based on their respective edge length and location coordinates and other information to determine the district number.In order to reduce the burden of cluster heads of data fusion,a minimum spanning tree by Prim algorithm of cluster is formed and cluster nodes communicating with the cluster head by the spanning tree.When selecting the cluster head,the elements including node residual energy,the number as cluster head and node degrees are considered preferentially.In addition,multi-hop routing is employed for communication between inter-clusters,and the communication link cost model is used,meanwhile,the improved MTE(minimum-transmission-energy)[5-6]algorithm is used to select the next hop.Thus,the energy consumption among nodes is reduced and the network life cycle is prolonged.

2.2 The definition

The optimal cluster number,minimum transmission power,link communication cost model,cluster head selection weighted probability formula and related terms are defined in this section.

1)the optimal number of clusters

We can get the optimal number of cluster according to the energy scheme[7].

(1)

(2)

2)Determine the communication link cost[8]

For any node in the network,a communication link(v1,v2)(E)cost function between nodev1andv2is defined as:

(3)

Where,p(v1,v2)is the minimum transmission power of nodes,k1andk2are weighting factors of the node,EInitis the initial energy.Ecurr(v1)andEcurr(v2)are the residual energy of nodev1andv2,respectively.PRis the received power.

3)Node Degree

The number of logical neighbors after the minimum spanning tree is constructed.

4)The probability weight of cluster head selection

(4)

Where,p1+p2+p3=1,Ecurris the current node residual energy and 1/notheris the energy will be consumed in the next period.Commonly set 15<=nother<=25,dis node degree andnis the number of times having been cluster head.

3 ALGORITHM DESIGN

The algorithm is to complete several parts as follows:the partition,running the minimum spanning tree algorithm within the cluster,establishing a cluster structure,cluster updating and several other steps.The algorithm flow chart is shown in Figure 2.

Figure 2 The flow chart of algorithm

1)Partition

The network nodes are randomly throwing to the target area,the node gets the position information of Location(x,y)according to the GPS,then the ID number and the location information are sent to the base station.At the same time,node saves its neighbor information,and sent the confirm information to the neighbors.The base station statistics whole network topology information received.Calculating the optimal cluster number according to the formula(1)and then getting hexagonal side length.Then the base station broadcastsdin the whole network,and other nodes calculate area ID according todand their coordinates and delete the nodes which are not in the same area.Finally,partition is finished.

2)Minimum spanning tree algorithm is used within the cluster

Firstly,nodes calculate the communication link cost according to the formula(3).Take the link cost as weights and generate the minimum spanning tree Prim algorithm.The network structure is shown in Figure 4.

Figure 3 Network structure diagram

3)Establish cluster structure

a)Select the cluster head

When selecting cluster head,the residual energy,number of nodes as an cluster head,node degree three factors are taken into account.Calculating the weight of probabilitypby the formula(4).Nodes with more residual energy and bigger node degree and the small times as cluster head have bigger opportunity to be the new cluster head.In the simulation,we setp1=3/23，p2=13/23，p3=7/23，nother=22.

First of all,the node broadcasts the weight information.Comparing node probability weights after receiving the message.If the weight of probability itself is larger,then broadcast its information.Secondly,the cluster node sends a request message to cluster head to join the cluster.The nodes of cluster head give confirmation and save the information of nodes in the cluster.Finally,the cluster head nodes send the message of being cluster head successfully to Base Station.Base station updates the whole network topology information,and the establishment of cluster structure is completed.

b)Slot assignment and cluster coding

In the algorithm,TDMA mechanism is implemented within the clusters,and CSMA/CA mechanism is used inter-cluster,and DSSS(direct-sequence spread spectrum)encoding is employed between the cluster.

c)Establish routes between clusters

4 SIMULATION AND ANALYSIS

4.1 Evaluation index and test environment

This performance analysis and simulates[9]mainly from two aspects which includes energy consumption of network nodes and network lifetime.

The simulation test environment is in the fedora10.0 which is installed in the PC with the memory of 2GB and CPU is Intel(R)Core(TM)i5-2400 3.1 GHz.After loading and configuring,compile the source code and then run the otcl script in NS2.Modify the otcl script according to the requirement and compile and run the code again.

With the simulation tool NS2,leach,GAF and the improved algorithm are simulated and the scene parameters[10]are shown in table 1.

Table 1 Summary of scene parameters

After the nodes are distributed,all the nodes are black,and during the procedure of establishing network,the nodes joined the network turn blue and the others stay black.After the network is finished,all the nodes turn blue.The running procedure of the algorithm is shown from figure 4 to figure 6.

Figure 4 Begin to establish the network

Figure 5 The procedure of establishing the network

Figure 6 The network finishes establishing

4.2 Test results and analysis

1)Energy consumption of network nodes

As can be seen from the graph,node energy variance of Leach algorithm is maximum.Because the cluster heads and the size of cluster are not uniform in leach algorithm and cluster head selection is also random,so a part of the node energy consumption of nodes will be quickly,thus the energy balance is relatively poor.This algorithm gets rid of the deficiencies,so the energy consumption of the network as a whole is more balanced.

Figure 7 Nodes energy variance diagram after the operation

2)Network lifetime

In this experiment,the default is that the network is death when the number of remaining nodes in the network is less than 80% of the total of the whole.

Figure 8 The relationship graphs between the number of simulation nodes and survival time

As seen from figure 8,when the number of nodes is 200,the advantage doesn′t appear in the improved algorithm,while the number is 300,the life time is longer than both leach and GAF.So when the size of network is small,compared with leach and GAF,the performance of the algorithm is not ideal.Because the number of sensor nodes is so small and the randomness of distribution between nodes is relatively large.Some nodes lie in the border area of hexagon and the number of nodes in the region is less too,making the node premature death.With the increase of network size,the advantage of this algorithm is obvious,and the survival time is long compared with GAF algorithm.Because that the GAF does not consider the optimal number of clusters which just simply assures that two adjacent regions can be directly communicated.

Figure 9 The number of nodes n=1000,the node survival time comparison graph of leach,GAF and improved algorithm

Can see from the figure 9 that when the algorithm of leach is running,nodes begin to death at 200s and end at 1600s,so the effective working time is 1200s.When GAF is running,nodes begin to death at 250s and end at 2000s,so the effective working time is 1900s.While the improved algorithm is running,nodes begin to death at 300s and end at 2500s,so the effective working time is 2100s.Can conclude that the life time improves 75%than the algorithm of leach and 11%than GAF.Therefore,can know that when the size of nodes is 1000,the survival time of improved algorithm is longer than leach and GAF.From figure 8 and 9,a conclusion that the algorithm is not so well in small network while have big advantage in the big network can be made.

5 CONCLUSION

Aiming at the shortcomings of Leach algorithm,the algorithm improved the structural topology.Simulation results show that the proposed algorithm balances the energy consumption of nodes and prolongs the network lifetime.Shortcomings of this algorithm are that it is especially suitable for large-scale network,and it is to be improved in small networks.

[1]KANG Yimei,LI Zhijun,HU Jiang,et al.A low-power hierarchical topology control algorithm for wireless sensor networks[J].Journal of automation,2010，36(4)：543-549.

[2]Heinzelman W R,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[3]Muruganathan S D,Ma DCF,Bhasin PI,et al.A centralized energy-efficient routing protocol for wireless sensor networks[J].IEEE Communications Magazine,2005,43(3):8-13.

[4]Younis O,Fahmy S.HEED:A hybrid,energy-efficient,distributed clustering approach for ad hoc sensor networks[J].IEEE Trans.on Mobile Computing,2004,3(4):660-669.

[5]T.Shepard.A channel access scheme for large dense packet radio networks[C].In Proc ACM SIGCOMM,tanford,CA,Aug,1996:219-230.

[6]M.Ettus.System capacity,latency,and power consumption in multihop-routed SS-CDMA wireless networks[C].In Proc Radio and Wireless Conf(RAWCON),Colorado Springs,CO,Aug,1998:55-58.

[7]F.V.C.Martins,E.G.Garrano,E.F.Wanner,et al.A hybrid multiobjective evolutionary approach for improving the performance of wireless sensor networks[J].IEEE Transactions on Sensors,2011,11(3):545-554.

[8]Labrador Miguel A,Wightman Pedro M.Topology Control in Wireless Sensor Networks[M].Springer Science Business Media B.V,2009.

[9]Zhu C,Zheng C,Shu L,et al.A survey on coverage and connectivity issues in wireless sensor networks[J].Journal of Network and Computer Applications,2012,35(2):619-632.

[10]Cheng CT,Tse CK,Lau FCM.A clustering algorithm for wireless sensor,networks based on social insect colonies[J].IEEE Transactions on Sensors,2011,11(3):711-721.

馬金發(fā))

date： 2013-12-09

FonndationitemFinancial by program for Liaoning Outstanding Talents in University(LR2012007)

Biography： ZHAI Pu(1988—),Female,Master Degree Candidate.

1003-1251(2014)04-0081-06

TP393DocumentcodeA