An Approach of Distributed Joint Optimization for Cluster-based Wireless Sensor Networks

Zhixin Liu,Yazhou Yuan,Xinping Guan,and Xinbin Li

An Approach of Distributed Joint Optimization for Cluster-based Wireless Sensor Networks

Zhixin Liu,Yazhou Yuan,Xinping Guan,and Xinbin Li

—Wirelesssensornetworks(WSNs)areenergyconstrained,so energy saving is one of the most important issues in typical applications.The clustered WSN topology is considered in this paper.To achieve the balance of energy consumption and utility of network resources,we explicitly model and factor the effect of power and rate.A novel joint optimization model is proposed with the protection for cluster head.By the mean of a choice of two appropriate sub-utility functions,the distributed iterative algorithm is obtained.The convergence of the proposed iterative algorithm is proved analytically.We consider general dual decomposition method to realize variable separation and distributed computation,which is practical in large-scale sensor networks.Numerical results show that the proposed joint optimal algorithm converges to the optimal power allocation and rate transmission,and validate the performance in terms of prolonging of network lifetime and improvement of throughput.

Index Terms—Wireless sensor networks(WSNs),joint optimization,power control,distributed algorithm.

I.INTRODUCTION

OVER the past few years,wireless sensor network(WSN) has been applied widely in many fi elds,such as intelligent traf fi c,industrial and meteorological monitoring,and so on.WSN is usually composed of large amount of sensors that are randomly distributed in a certain region.WSN can perform collecting,processing and transmitting for large amount of data in one hop or multi-hop self-organization manner.Typically,sensor nodes are empowered by some low capacity batteries.Because of the special work environment, the energy resources of sensors are usually irreplaceable[1]. Under such constraint condition,energy saving and lifetime prolonging become the hot topics in the researches of WSNs. The unbalance of energy consumption is a common problem in WSNs.There are some nodes that will relay data passivelytoo much for others,and they become bottleneck nodes in the network.For the lack of information of the whole network, it may result in the death of some nodes earlier and the deterioration of network performance.So how to allocate the energy of nodes,adjust the transmitting rate and balance the energy consumption become an important issue[2-3].References[4-5]focused on the method of cross-layer design to achieve power control scheme and save energy.However, the extra overhead caused by frequently scheduling among different protocol layers cannot be avoided.That results in the poor performance in the aspect of information exchange. In order to get tradeoff between topology coverage and fault tolerance,Zhao et al,proposed a distributed adaptive power control scheme[6],which could guarantee the connectivity of networks and prolong the lifetime.The problem of source extraction in bandwidth-constrained WSN was considered in[7],and three kinds of sensor network topologies were considered in order to show the impact of topology on the performance and energy ef fi ciency.

From network performance respective,energy saving design of routing algorithm provides a promising approach for maximizing the lifetime of WSN.Generally,there are two types of routing protocol algorithms, fl at routing and hierarchical routing[8].In cluster routing algorithms,the criterion of cluster selection adopted in existing research is usually based on a certain of rules,such as residual energy,coverage,probability of outage,and so on.The fl exible and adaptive multi-hop network can be formed with the relaying of clusters,which is favorable for stochastic topology[9].

Among clustering algorithms,low energy adaptive clustering hierarchy(LEACH)is one of the most recognized classical clustering algorithms in WSNs[10].LEACH selects cluster heads dynamically and frequently by a round mechanism, and allows different nodes to become cluster heads at each round.Some lately improved algorithms based on LEACH pay more attention to how to save energy and/or guarantee fairness,such as power ef fi cient gathering in sensor information systems(PEGASIS),hybrid,energy-ef fi cient,distributed (HEED),energy-ef fi cient cluster formation(EECF).In routing protocol design,it is considered how to balance the energy consumption among nodes during the formation of cluster, and neglect the consumption during the data transmission. For the difference of roles,cluster head is in charge of data fusion,computation,storage,delivery,and consumes more energy[11-12].In homogeneous network,cluster head and member nodes have the same features and energy constraints. Once the cluster head exhausts energy,the member nodes will loss the relay,and network recon fi guration and routing re-setupare needed.Frequent change of routing and topology will increase the network overhead and decrease the network performance[13-14].Besides,some other network performances such as coverage,real-time and lifetime,are involved when the cluster routing is considered.In[15],the maximization of the coverage time for a clustered wireless sensor network by optimal balancing power consumption among cluster heads was considered,and stochastic as well as deterministic network models were investigated,respectively. In[16],a distributed energy-ef fi cient clustering with improved coverage algorithm was proposed,which could cluster the sensor network with the least number of cluster heads to cover the whole network and assign a unique ID to each node only based on local information.

In this paper,regarding the special role of cluster head,it is proposed that performance of cluster head is protected fi rst by reducing the interference from member nodes.Involving the effect and relation of power and rate,a novel joint optimization model is presented with the protection for cluster head.Based on the optimization model proposed in this paper,the cost function is designed and the dual decomposition method is adopted to get distributed optimal iterative algorithm.The ef fi ciency of cluster head is improved and the extra cost, caused by the death of cluster head,is reduced.The network lifetime is prolonged effectively.By the mean of choosing two appropriate sub-utility functions,the distributed iterative algorithm is achieved.

The rest of the paper is organized as follows.In Section II,the network model and system formulation are given.The optimization strategy is proposed and the convergence of the algorithm is proven in Section III.Simulation results are given in Section IV to validate the effectiveness of the proposed algorithm.Finally,conclusions are drawn in Section V.

II.NETWORKMODEL ANDPROBLEMFORMULATION

Fig.1 shows a schematic of the networks.The stationary network topology is considered.It containsMsensor nodes andNclusters randomly distributed in the sensing region.LetNibe the number of member nodes in clusteri.There areLlinks,and the signal to interference plus noise ratio(SINR)in linklisγl.

For the clustering routing,there usually are three phases, the phase of cluster set-up,stable operation and cluster update. Cluster head can be selected or migrated according to some routing rule or algorithm and it is neglected here.We focus on the period of stable transmission in each round.The cluster head,denoted asCHn,can either communicates with base station(BS)directly or transmit data in multi-hop to a destination,depending on the routing algorithm.In a cluster, the cluster head takes the charge of relaying data from other member node.The energy consumption of cluster head will be more than other nodes.Once the cluster head exhausts energy,the whole cluster will not work.The topology will change with the join-in or quit of some nodes.Moreover, the interference among different clusters cannot be avoided, and this kind of interference will cause low communication quality,even failure of communication.So cluster heads play an important role in the WSNs.It is necessary to keep the topology stable by the mean of protecting cluster heads.For clustern,the protection for cluster headCHnis formulated as threshold constraint.

wheregiis channel gain,piis transmission power of nodesi,Qnis the demand of protection.

Fig.1.The topology of network.

Denoterias the transmission rate of nodei,which is larger than the minimum rate,i.e.,ri＞rmin.There exists a constraint of transmitting power and it is denoted aspi＜pmax. According to Shannon principle of wireless communication, the channel capacityclis as follows.

whereWis bandwidth,pis average power,dis the distance andζis a constant related to modulation,ais attenuation factor of channel and its typical value is 2～5.Denote s(l)as the user set on linkl,clas the capacity limitation.In fact,the actual rate is lower thancl,so we model the constraint that linklmust satisfy the link capacity constrain as(3)

whereβis the ef fi ciency factor,0＜β＜1.The factorβintroduced here is to leave some leeway against channel uncertainty.

Next,we analyze the cost function of optimal problem.The objective is to get higher throughput with lower transmitting power.The optimization cost function is designed as the sum of each node’s utility.

HereG(ri,pi)is an increasing function ofri,and decreasing function ofpi.It means that the utility of network is to get more data exchange with less power consumption.Based on above description,we formulate the problem as a network utility maximum problem.

Remark 1.The four constraints are interpreted as follows. The fi rst one is the rate constraint;the second is the protection constraint for cluster head;the third and forth are variable constraint of rate and power,respectively.

To guarantee solvability of the optimal problem,the cost functionG(r,p)is chosen as a second derivable function ofr,p,and it is a concave function of variables.Here we select the cost function as follows

wheref1(ri)is a concave function ofri,which can be regarded as the throughput bene fi t;f2(pi)is a convex function ofpi,which can be regarded as the payment of power consumption.αis a weighted factor,which can re fl ect the emphasis on rate utility or power utility.SoG(ri,pi)is the net income of nodei.Here we use the sum of the net utility of all nodes as a measure of system performance.The objective of the optimal problem is to maximize the whole utility of the network.

III.DESIGN OFJOINTOPTIMIZATIONSTRATEGY

The joint optimization problem is formulated as a nonlinear optimization problem.In problem(6),the goal is to maximize the sum of network utility.To fi t the feature of distributed operation in large scale sensor networks,dual decomposition method is used.The Lagrangian dual function of problem(5) can be converted into

whererrr=[r1,r2,...,rn]is the vector of transmitting rate,ppp=[p1,p2,...,pn]is the vector of user power,λ=[λ1,λ2,...,λn]andμ=[μ1,μ2,...,μn]are vectors of Lagrangian multipliers,respectively.From above expression,the dual problem is given by

whereφ(λ,μ)=maxrrr,pppL(rrr, ppp).In the dual formulation,Lagrange multipliersλ,μcan be interpreted as cost of constraint. One bene fi cial observation is that each node can compute its rate and power individually.For given multipliersλandμ,the optimal power and rate can be obtained by solving the dual problem.To separate the variables,rewritingL(rrr, ppp),one has

ThusL(rrr, ppp)can be divided into three parts.The fi rst part can be converted to optimal rate sub-problem,the second part can be converted to optimal power sub-problem,and the last one is independent ofrrr, ppp.For givenλandμ,the third part is constant.

Sub-problem 1.

Sub-problem 2.

Obviously,the above two sub-problems are independent of variableλ,μ.Once the optimalλ,μare gained,it is easy to get the optimal solution.Next,we analyze the optimal multipliersλ?,μ?based on sub-gradient method.At timet+1,the multipliers are updated according to sub-gradient direction,and the rules are given as follows.

where[·]+means that if the expression in the bracket is less than 0,the value is 0.δ(n)is an iterative step.The step has a major effect on convergence rate.Next,we prove that the multiplier can converge to the unique optimal point.

Without loss of generality,multiplierλis taken as an example to analyze the convergence.

De fi nition 1.For an arbitrarily givenε＞0,if there exists a bounded step series 0＜δ(t)＜ˉδ,such that

Then the iterative algorithm can converge into theεneighborhood ofλ?,whereλ?is the optimal value of dual variable in dual system.

The limit of(20)can be expressed as

From De fi nition 1,one can get that the algorithm will converge in the region of radiusˉδR2/2.When the iterative step is chosen appropriately,there will be further constraint for the upper bound ofˉδ.In[17],the theorem shows that the algorithm can converge to the optimal solution with arbitrary precision,if the following constraints are satis fi ed.

Remark 2.The implementation of power adjustment is completed at sensor node;the update of multiplier is completed as link.For one-hop routing in a cluster,multiplier is updated at cluster head.

Remark 3.The information of multiplierwhich is needed in the rate adjusting algorithm,is supplied by link algorithm,while the information of multiplierPNn=1μngi, which is needed in the power adjusting algorithm,is supplied by cluster head.

Remark 4.The information of rate,which is needed in the update ofλ,can be obtained using local information,while the information ofwhich is need in the update ofμ,can be supplied by cluster head.

It is necessary to point out that there will not be any extra heavy burden of network resource,because during the operation of algorithm the exchanged information between node and link is just the computing result.All the parameters information needed in the iteration can be obtained using local information.So the distributed algorithm is suitable for wireless sensor networks.The fl ow chart of the algorithm is shown in Fig.2.

IV.SIMULATIONS ANDPERFORMANCEANALYSIS

In this section,we give numerical examples for the proposed optimal algorithm by considering the wireless sensor networks as shown in Fig.1.The simulations are executed using Matlab. The considered network environment and related parameters are as follows.There are 100 nodes placed in an interesting region of 200×200(m2),and one base station is located at the center.We assume that each sensor node has an initial energy of 2J,and the energy consumption model in each node is the same as[16].Some other parameters in the simulation are listed in Table I.

Fig.2.The fl ow chart of the algorithm.

TABLE IPARAMETERS SETTING

For the topology control of WSNs,usually there are three phases.They are cluster set-up,the phase of stable operation and cluster update.In the cluster based WSN,the change of topology is caused by energy consumption.The common analysis of clustering algorithm usually focus on the fi rst and last phases,and pay more attention to the scale of cluster,energy consumption,lifetime and stability of topology.However,the neglect of adjustment in the phase of stable operation will result in the imbalance of energy consumption among the nodes.If the cluster head is exhausted,the cluster has to turn into the phase of cluster update.That will affect the cluster stability and lifetime of networks.The power control scheme is operated during the phase of stable operation.So the other two phases are omitted.In the phase of stable operation,we fi rst focus on the process of rate adjustment.The adjusting curves are given in Fig.3.One can see that the algorithm has better convergence rate.

The weighted factor introduced in(6)is used as a tradeoff utility between rate and power.For the contradiction between two performance indexes,it is necessary to balance them.We de fi ne the average rate of clusternas

Next we evaluate the effect of weighted factor on the performance of rate.As shown in Fig.4,one can see that the rate will be predominate in the networks’utility with the increment ofα,and the average rate also increases.However, the improvement of throughput is at the expense of energy consumption and the lifetime of network.

Fig.3.The convergence curves of rate.

Fig.4.The average throughput of cluster with differentα.

To evaluate the performance of joint optimization in terms of energy balance and lifetime prolonging,we compare the proposed scheme with some other cluster routing algorithms, LEACH and EECF.LEACH is one of the most famous clustering algorithms and is proposed by Heinzelman in MIT. EECF is an improved clustering algorithm,which focuses on how to reduce the exchanged inner information in the network and improve the convergence speed.Here we do not change the clustering rules of two algorithms,and adopt the joint optimization strategy in stable operation.The results are shown in Figs.5 and 6.For LEACH protocol,the number of alive nodes with joint optimization is more than that of original algorithm.The difference in EECF protocol is more obvious as shown in Fig.6.The more the alive nodes are,the longer the lifetime of network will be.It is a bene fi t to keep the network topology stable.With different initial energy,the average rates of cluster of three algorithms are given in Fig.7. With same energy consumption,the average rate using joint optimization is higher than the other two.The reason is that in the joint optimization scheme,it considers both power and rate performance and approach dynamic balance.The proposed scheme can improve the throughput and reduce the energy consumption.

Fig.5.The lifetime comparison with LEACH.

Fig.6.The lifetime comparison with EECF.

Fig.7.The comparison of average rate.

V.CONCLUSIONS

Motivated by the signi fi cant role of cluster head in clusterbased WSNs,we present how to jointly allocate the power and rate of sensor node.To improve network throughput and reduce energy consumption,we formulate a novel joint optimization model with the protection for cluster head.The cost function composed of two appropriate sub-utility functions is introduced to evaluate the joint performance of rate and power.The distributed algorithm is given based on dual decomposition method and the convergence of the proposed iterative algorithm is proved analytically.Numerical results show that the performance can be improved in terms of network lifetime and throughput.Further research of the paper are as follows.First,we assume that the all the sensor nodes are fi xed and the cluster heads communicate with the base station in one hop.How to extend the method in mobile and multi-hop scenario is to be addressed.Second,in the cost function,the weighted factor is given factitiously to balance two aspects of performance.It can also be regarded as a variable and it is an interesting problem to get the optimal solution in dynamic networks.

ACKNOWLEDGEMENT

The authors would like to thank anonymous reviewers for their constructive comments which helped us to improve the quality of this paper.

REFERENCES

[1]Wang H,Yang Y H,Ma M D,He J H,Wang X M.Network lifetime maximization with cross-layer design in wireless sensor networks.IEEE Transactions on Wireless Communications,2008,7(10),3759-3768

[2]Liao S B,Yang Z K,Cheng W Q.Joint power control and rate adaptation for wireless sensor networks.Acta Electronica Sinica,2008,36(10), 1931-1937

[3]Chen J M,Yu Q,Chai B,Sun Y X,Fan Y F,Shen S.Dynamic channel assignment for wireless sensor networks:a regret matching based approach.IEEE Transactions on Parallel and Distributed Systems, 2015,26(1),95-106

[4]Cimatti G,Rovath R,Setti G.Chaos based spreading in ds-uwb sensor networks increases available bit rate.IEEE Transactions on Circuits and Systems-Part I,2007,54(6),1327-1339

[5]Reena J L.Joint congestion and power control in uwb based wireless sensor networks.In:Proceedings of the 32nd IEEE Conference on Local Computer Networks.Dublin,Ireland:IEEE,2007,911-918

[6]Zhao X J,Zhuang Y,Zhao J,Xue T T.Adaptive power control strategy for wireless sensor networks.Journal of Electronics and Information Technology,2010,32(9),2231-2235

[7]Chen H B,Tse C K,Feng J H.Impact of topology on performance and energy ef fi ciency in wireless sensor networks for source extraction.IEEE Transactions on Parallel and Distributed Systems,2009,20(6),886-897

[8]Younis O,Krunz M,Ramasubramanian S.Node clustering in wireless sensor networks:recent developments and deployment challenges.IEEE Network,2006,20(3),20-25

[9]Liu A F,Zhang P H,Chen Z G.Theoretical analysis of the lifetime and energy hole in cluster based wireless sensor networks.Journal of Parallel and Distributed Computing,2011,71(10),1327-1355

[10]Heinzelman W,Chandrakasan A,Balakorishnan H.Energy ef fi cient communication protocol for wireless microsensor networks.In:Proceedings of the 2000 International Conference on System Sciences.Hawaii: IEEE,2000.4-7

[11]Zhang D,Zhou J,Guo M,Cao J,Li T.TASA:tag free activity sensing using RFID tag arrays.IEEE Transactions on Parallel Distribution System,2011,22(4),558-570

[12]Khalil E A,Attea B A.Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks.SwarmandEvolutionary Computation,DOI:10.1016/j.swevo.2011.06004,2011.

[13]He J P,Cheng P,Shi L,Chen J M,Sun Y X.Time synchronization in WSNs:a maximum-value-based consensus approach.IEEE Transactions on Automatic Control,2014,59(3):660-675

[14]Zhang D,Guo M,Zhou J,Kang D,Cao J.Context reasoning using extended evidence theory in pervasive computing environments.Future Generation Computer Systems,2010,26(2):207-216

[15]Shu T,Krunz M.Coverage-time optimization for clustered wireless sensor networks:a power-balancing approach.IEEE/ACM Transactions on Networking,2010,18(1):202-215

[16]Liu Z X,Zheng Q C,Xue L,Guan X P.A distributed energyef fi cient clustering algorithm with improved coverage in wireless sensor networks.Future Generation Computer Systems,2012,28(3):780-790

Yazhou Yuan Ph.D.candidate at the School of Electronics,Information and Electrical Engineering, Shanghai Jiao Tong University,Shanghai,China.His research interests include wireless sensor networks, industrial cognitive radio and applications.Corresponding author of this paper.

Xinping Guan received his B.S.degree in mathematics from Harbin Normal University in 1986, and his M.S.degree in applied mathematics and his Ph.D.degree in electrical engineering from Harbin Institute of Technology,Harbin,China,in 1991, and 1999,respectively.He is currently a professor in the Department of Automation,the School of Electronic,Information,and Electrical Engineering, Shanghai Jiao Tong University,Shanghai,China.His research interests include wireless sensor networks, congestion control of networks,robust control and intelligent control for nonlinear systems,chaos control,and synchronization. He received a Special Appointment Professorship under the CheungKong Scholars Programme by the Ministry of Education of China in 2005 and the National Science Fund for Distinguished Young Scholars of China in 2005. He became a senior member of IEEE in 2004.

Xinbin Li received his M.Sc.degree in control theory and control engineering from Yanshan University,Qinhuangdao,China in 1999,and his Ph.D. degree in general and fundamental mechanics from Peking University,Beijing,China in 2004.He is now a professor in the Institute of Electrical Engineering, Yanshan University.His research interests include nonlinear system and networked control system.

u

his B.S.,M.S.,and Ph.D. degrees in control theory and engineering from Yanshan University,Qinhuangdao,China,in 2000, 2003,and 2006,respectively.He is currently a professor in the Department of Automation,the Institute of Electrical Engineering,Yanshan University.He visited the University of Alberta,Edmonton,AB, Canada,in 2009.His research interests include performance optimization and energy-ef fi cient protocol design in wireless sensor networks,wireless resource allocation in cognitive radio networks,and Femtocell networks.

Manuscript received August 19,2014;accepted March 10,2015.This work was supported partly by National Natural Science Foundation of China (61473247,61104033,61172095)and Hebei Provincial Natural Science Fund (F2012203109).Recommended by Associate Editor Jiming Chen.

:Zhixin Liu,Yazhou Yuan,Xinping Guan,Xinbin Li.An approach of distributed joint optimization for cluster-based wireless sensor networks.IEEE/CAA Journal of Automatica Sinica,2015,2(3):267-273

Zhixin Liu is with the Institute of Electrical Engineering,Yanshan University,Qinhuangdao 066004,China(e-mail:lzxauto@ysu.edu.cn).

Yazhou Yuan is with the School of Electronic,Information and Electrical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China(e-mail: ysu-yyz@163.com).

Xinping Guan is with the Institute of Electrical Engineering,Yanshan University,Qinhuangdao 066004,China,and also with the School of Electronic,Information and Electrical Engineering,Shanghai Jiao Tong University, Shanghai 200240,China(e-mail:xpguan@sjtu.edu.cn).

Xinbin Li is with the Institute of Electrical Engineering,Yanshan University, Qinhuangdao 066004,China(e-mail:lixb@ysu.edu.cn).