Huang Ru,Zhu Yu,Miao Peng,Zhu Jie

(1.School of Information Science&Engineering,East China University of Science and Technology,Shanghai,200237,P.R.China;2.Institute of RF-&OE-ICs,Southeast University,Nanjing,210096,P.R.China;3.Department of Electronic Engineering,Shanghai Jiaotong University,Shanghai,200240,P.R.China)

INTRODUCTION

Data-gathering is a critical operation in wireless sensor networks(WSNs)for extracting the useful information from the operating environment to the base station sink.Constrained by the limited and non-replenished energy resources,minimizing energy consumption is regarded as a major performance criterion to provide the maximum network lifetime in WSNs.Technologies used to balance the energy consumption in networks are universally accepted as a key factor for prolonging the lifetime[1-2].However,without the geographic information support, the periodic low-rate data flooding throughout the network would cost lots of energy. Therefore,many current researches[3-6]focus on energy optimizing location-aided routing protocols with both low power and fault tolerance to overcome the above disadvantages.And the core technologies in above researches are realized by efficiently using geographic-aware information to limit the new route search into a smaller″request zone″,which is estimated according to the prior position and the mobility information of destination,thus conserving more energy.The size of the ″request zone″is too large if the obtained information is inaccurate.To solve the above problems,the greedy perimeter stateless routing(GPSR)[7]is proposed to utilize the greedy decisions forwarding perimeter-mode packets in a derived simple planar graph.The energy of those nodes on the planar graph should be quickly depleted for concentrated traffic on the promiscuous listening mode.The above routing problems can be proved by NP-hard.Swarm intelligence, which is the emergent collective intelligence of groups of simple agents,is an efficient way to solve the concerned problems.Swarm is a population of interacting individuals,which contributes to optimize some global objectives via collaborative operations. As an important research domain of swarm intelligence,ant colony optimization(ACO)is a constructive meta-heuristic optimization method and has been successfully used to build energy-saving routing[8-10]. In the process of routing construction in WSNs, ant-like agents concurrently and asynchronously build optimal solutions via applying a stochastic local decision policy and using pheromone trails and heuristic information.However,those swarm intelligent themes only put emphasis on the positivefeedback mechanism to search optimization and have made some modifications to fit different network types,which cannot satisfy the special characteristics of WSNs.This paper proposes a heuristic theoretical optimal routing algorithm(TORA). In the algorithm,prior theoretical results can be combined with the swarm intelligence-inspired mode to further enhance the energy-efficiency of routing construction in WSNs.

1 SYSTEM MODEL

WSNs can be represented by a weighted undirected graph G=(V,E,W),where V and E represent the set of nodes and links in G respectively,while W denotes the set of weights with E?G.Each link＜i,j＞∈ E is associated with a delay parameter D＜i,j＞∈ W and the total delay requirement for QoS is set as D Threshold.In WSNs,the energy consumption of sensors should be unbalanced for the asymmetric traffic distribution in data flow.In the data-gathering routing rooted at sink,the energy cost of each sensor is related with its own locality hierarchy in the tree structure.If the geographical position of sensor is closer to the sink,its hierarchy in the tree structure and its corresponding energy cost are higher due to the large amount of data aggregation.According to the above analyses,WSNs are divided into three categories of functional regions according to the event radius(ER)model[11]with disparity in the energy cost caused by the unbalanced streams distribution.In the ER model,events are sensed by a subset of nodes V s?V,i.e.the data-sensing region.The data-merging region V c?V is defined as a disk centered at sink with radius d crical denoting the critical distance of the V c boundary from the sink. And the sensors in V r=V- V s∪V c compose the data-relaying region. It is assumed that each sensor node maintains the information of a cache storing neighborhood and the self-address obtained by GPS and known by sink as a priori,and each artificial ant ak(k=1,2,…,|V s|)has a memory Mk,whose components are denoted in Table 1.

The current feasible neighborhood of ak is defined as AK=(V-L(v))∩O(i),where O(i)is the set of neighbors in ni.Via the functional region division of sensor networks and the ability of ant memory,the artificial ant can roughly estimate the energy-cost-level of each reached sensor and correspondingly adjust the weight in heuristic information of routing selection to improve the reliability of data-gathering tree.

Let Ri=Ei(lef)/Ei(ini), which denotes the remaining energy level of ni∈V.The routing tree problem A is defined to find a series of optimal paths t mult=from V s?V to destination sink subjected to the following conditions Eqs.(1,2)are constraint conditions for QoS requirement of energy optimization and temporal consistency,wheredenotes the average remaining energy ratio of optimal path p*k,A a NP-hard constrained path optimization(CPO)problem and solved by Lagrange multiplier(LM)algorithm.The Lagrange function is described as

The solutions can be obtained by calculating the partial differential of Lagrange function matrix,but it is not suitable for the resource-limited sensor nodes in WSNs.Therefore,this paper proposes TORA algorithm to solve this primary problem A with a fully distributed way in ACO approach.

2 OPTIMAL ROUTING STRUC-TURE

2.1 Design of heuristic factor

It is assumed that nv∈V s sends l bit message on multi-hop way to sink,which requires K(v)-1 relay nodes and the i th hop distance di,where K(v)shows the number of theoretic hops from nv to sink. Based on the first-order-radiomodel[12],the energy expended by relaying l bit message over distance d i is E relay(l,di)=(2E elec+X amp dni)×l. Denoting that d(nv,sink)is the distance between the source nv(v∈[1,|V s|])and sink.The total cost on path from nv to sink iswhich can be proved as a strict convex function,and its minimal value is only obtained under the condition that each hop distance is equal to d(ovp)tim=d(nv,sink)/K(v)according to Jensen′s inequality.And then the optimal hop-counts(Eq.(4))is calculated by imposing the derivative operation,i.e.,?P total(di)/?K=0.

where T1 and T2 are node energy parameters.We set vector J(v)as the coordinate sequence of theoretical points,i.e.,J(v)={n(v)(t)},t∈ [1,K(v)]. The rectangular coordinates of each theoretical point for minimal P total is deduced as follows

At c(j)hop, the distance-error between theoretical optimal sensor and actual counterpart is calculated by Eq.(6).

Defining that triple S=(B,R,H)is the current state obtained by the ant agent for next hop selection,i.e.,during the process of routing building,the bias B,the remaining energy level R and the hop counts H are taken into account.Assuming that state vector Sj=(Bj,Rj,Hj)∈S,and each tuple of S j is defined as follows

where Bj provides the location-aided energyefficiency information for the process of path building and helps ant agent to adjust the forward direction to sink based on the bias value.Rj shows the energy status of nj and Hj the hops of ant agent to reach the source node through node nj.With the accumulation of hop-counts, the probability of reached nj belonging to data-merging region V c increases and the higher energy consumption is consequently expended. Therefore, according to the distribution trait of energy cost in routing tree,the relationship between each tuple in S is defined as Eq.(10),which indicates that the closer the current sensor to sink,the larger the weight of remaining-energy-level regarded as energy efficiency factor.∈

The cost W is associated with each nj∈AK as local evaluation information for noderobustness. The higher the value of,the greater the probability that njis selected as the next hop node on the building of optimal routing path.If k=argmax n j∈the ant at current sensor ni tends to choose nk as the next hop sensor.Therefore,the structure of heuristic factor for ACO is designed as

Eq.(11)embodies the idea that artificial ant can adaptively choose the high-energy-efficient sensor as its next hop in each step and adjust corresponding variable weight to improve the reliability of data-gathering tree.In two extreme cases,i.e.,if Hj=0 or E(lef)j=0,then Zij→0,which indicates that nj belongs to data-sensing region(nj∈V s),or it runs out of energy,then the ant agent should abandon the selection of njduring the path building.

2.2 Algorithm f low

At the initial stage of TORA,the optimal routing tree t mult is empty and each sensor in V s?V takes sink as common destination.The sink instructs sensors in V s to create ant-like agents for constructing optimal routing paths and compute the corresponding theoretic point sequence J(v). The above task is sent by″interest″, which also contains the address coordinate of sink, i.e., (x sink,y sink), and propagates through the network to Vs.The ant dispatched from sensor nv∈V s is denoted as aforwk .In each step,aforwk chooses the next unvisited node in current feasible neighborhood with the improved transition probability given by Eq.(12)and constructs p(v)∈t mult from source to sink,if it does not meet any sensor which has been added to t mult.

When afkorwarrives at sink,the corresponding backward ant abkackis created and backes along the built p(v)to nv,and any sensor visited by akbackis set with a mark,which denotes that the sensor belongs to t mult.Meanwhile,akbackcarries the path information copied from afkorwand deposits the pheromone trails on visited sensors according to

where d∈(0,1)represents the volatility degree of pheromone. Total remaining energy ratioRiand chopcarried by akfo

rware used to update pheromone.

According to the updating rule,pheromones of those sensors in tmultshould be adaptively reinforced and subjected to constraint conditions Eqs.(1,2)of A.abackk dies when it arrives at nv∈V s,and the optimal routing from nv to sink is set up.In the other case,if aforwk meets nj∈ tmult,it stops further search to set the current graft sensor nj as destination and comes back to source for re-executing the above algorithm. The algorithm is terminated when all sour cesensors in V s are added into t mult,which is composed of those corresponding optimal routing paths from each source sensor to sink.In TORA,it is proved that the final routing tree structure is loop-free by using the taboo list in memory of ant and the time-complexity of TORA has the linear relationship with the steps moved by artificial ants. According to the function connection between the solution quality and the steps,the optimal solution can be obtained by the concurrent processing of m ant agents in k log2 m steps and the time-complexity is deduced as O(mk log2m).

3 SIMULATION RESULTS

TORA is simulated by using NS2 platform in a network of adjustable-density sensors(25—140)randomly distributed over a square of 500×500 units with the base station at(15,480).The link layer is implemented using IEEE802.11 MAC protocol.Each sensor has tunable communication radius a c(a c≥d(v)optim).In the radio model,each radio dissipates Eelec=50 nJ/bit to run the transmitter or the receiver circuitry and X amp=100 p J/bit/m2for the transmitter amplifies. The parameters of ACO are set in Table 2.

Table 2 Experimental parameters and results

The parameter e MSE is defined as the factor to evaluate the degree of approximation between t mult and the theoretical optimum counterpart.

where d(v)tis actual tth-hop distance and|V s|the number of sensors in Vs.The better the degree of the approximation between actual routing and the theoretical model,the less the total energy cost.The percentages of deviation among classical geographic-aided routing GPRS,minimum energy consumption routing, MEC[13], greedy algorithm[14]and TORA are compared with respect to e MSE.As shown in Fig.1,the deviation in TORA always keeps the smallest value compared with the other schemes with an increase of node density,which denotes that TORA performs better than other schemes on the realization of minimal total energy-cost level in networks,because the prior theoretical results are adapted to the design of heuristic factor in TORA.

Energy balance analysis is shown in Fig.2 at the node level after 80 times of transmission-operations,where R is the ratio of remaining and initial energy levels. In annular domain with center at sink and radius r∈[5,10],we randomly select 40 deployed sensors for energy-status observation by using different routing algorithms.The peak values of each curve in Fig.2 are corresponding to the normalized remaining energy level.Simulation results show that the average level of TORA is higher than the other two algorithms(GPRS and MEC)because that the adaptive ant-agents mode is used in TORA.

Fig.1 Fitting degree to theoretical optimal structure

Fig.2 Comparison of remaining energy level

In Fig.3,based on the final routing structure t mult,the performance of TORA with and without variable weight j j=Rj/Bj(i.e.,energy factor)in heuristic factors is compared according to the number of rounds versus the survival rate of sensors.An important objective of TORA is to extend the QoS-service lifetime of WSNs,which is measured with respect to the spent time until 30% nodes in G deplete their energy.R2 and R1 are defined as the corresponding lower bounds of QoS-service lifetime when Z ij with or without the variable weight jj.Fig.3 shows that R1＜R2,which means that the QoS-service lifetime of WSNs is prolonged and the robustness of the final optimal routing tree is improved by introducing the variable weight j j into heuristic factor.Therefore,TORA with variable weight outperforms that without variable weight.

Because the average delay is restricted below scheduled delay QoS-constraint,it is set as 8 ms in the simulation.Fig.4 shows the mean of endto-end delay comparison and the average delay of TORA is less than those of M EC and GPRS,which is benefited by the updating pheromone rule(Eq.(14))based on the delay constraint to reinforce the trails on optimal paths and weaken the trails on those bad ones.

Fig.3 Survival ratevs rounds

Fig.4 End-to-end packet delay

4 CONCLUSION

For constructing the optimal routing structure in WSNs,it is important to minimize the total energy cost of data transfer from the data-sensing region to a fixed sink with delay constraint of QoS, and to improve energy robustness of routing tree structure for reducing the probability of disconnected subnets,which is caused by unreasonable energy distribution on sensors in data-gathering routing structure.This paper presents an optimal tree algorithm based on ACO,i.e.,TORA,to achieve the above two important objectives. By dividing WSNs into different kinds of functional regions, energy consumption of each sensor can be roughly estimated in advance. The novel designs of heuristic factor construction and pheromone updating rule can endow artificial ants the ability to adaptively detect the local energy status in WSNs and intelligently approach the prior theoretic model in the process of routing construction.Experimental results prove that the proposed optimal routing tree can improve the energy efficiency and the QoS-service performance of data gathering routing scheme in WSNs.

[1] Bouabdallah F,Bouabdallah N,Boutaba R.On balancing energy consumption in wireless sensor networks [J].IEEE Transactions on Vehicular Technology,2009,58(6):2909-2924.

[2] Zhang Habo, Shen Hong. Balancing energy consumption to maximize network lifetime in dataga thering sensor networks[J].IEEE Transactions on Parallel and Distributed Systems, 2009,20(10):1526-1539.

[3] Bruck J,Gao Jie,Jiang Anxiao.M AP:medial axis based geometric routing in sensor networks[J].Journal of Wireless Networks, Springer Netherlands,2007,13(6):835-853.

[4] Yu Fucai,Choi Younghwan,Park S,et al.Sink location service for geographic routing in wireless sensor networks[C]//Wireless Communications and Networking Conference.USA:IEEE,2008:2111-2116.

[5] Chen Chi,Aksoy D,Demir T.Processed data collection using opportunistic routing in location aware wireless sensor networks [C]//The 7th International Conference on Mobile Data Management.Japan:IEEE,2006:150.

[6] Deb D,Srijita B R,Chaki N.Design of a low-cost positioning framework for location aided energy efficient routing[C]//The 5th IEEE Conference on Wireless Communication and Sensor Networks(WCSN).India:IEEE,2009:1-6.

[7] Karp B,Kung H T.GPSR: greedy perimeter stateless routing for wireless networks[C]//The 6th Annual International Conference on Mobile Computing and Networking.USA:IEEE,2000:243-254.

[8] Zhong Zhicheng,Tian Zhizhong,Li Zhe,et al.An ant colony optimization competition routing algorithm for WSN [C]//The 4th International Conference on Wireless Communications,Networking and Mobile Computing.China:IEEE,2008:1-4.

[9] Park J,Sahni S.An online heuristic for maximum lifetime routing in wireless sensor networks[J].IEEE Transactions on Computers,2006,55(8):1048-1056.

[10]Xie Hui,Zhang Zhigang,Zhou Xueguang.A novel routing protocol in wireless sensor networks based on ant colony optimization [C]//International Conference on Environmental Science and Information Application Technology. Wuhai,China: [s.n.],2009:646-649.

[11]Boukerche A,Cheng X,Linus J.Energy-aware data-centric routing in microsensor networks[C]//The 6th ACM International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems.USA:ACM,2003:42-49.

[12]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks [C]//Hawaii Conference on System Sciences. USA: IEEE,2000:1-10.

[13]Park N,Kim D,Doh Y,et al.An optimal and lightweight routing for minimum energy consumption in wireless sensor networks[C]//The 11st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications.China:IEEE,2005:387-393.

[14]Panigrahi B,De S,Sun Luk J.A greedy minimum energy consumption forwarding protocol for wireless sensor networks [C]//International Communication Systems and Networks and Workshops.USA:IEEE,2009:1-6.