A Multipath Routing Protocol Based on Clustering and Ant Colony Optimization for Wireless Sensor Networks

Published Online October 2009 in MECS

The wireless sensor networks (WSNs) technology have been widely applied in military, industry, agriculture and many other areas [1][2]. In the WSNs, a lot of nodes operate on limited batteries, making energy resource be the major bottleneck, so an economical and frugal management of energy is essential for improving energy efficiency. Because the energy consumption of communication is the major part of the energy

Manuscript received July 20, 2009; revised July 20, 2009; accepted July 20, 2009.

This paper is partly supported by Shanghai Normal University SK200709, DZL805, CL200652 and PL531.

consumption in WSNs [3][4], a high performance routing protocol is often a key requirement in WSNs system. The design of routing protocols in WSNs is very challenging due to their inherent characteristics of large scale, no global identification, dynamic topology, and very limited power, memory, and computational capacities for each sensor. Currently, many energy-efficient routing algorithms have been studied for saving energy [5][6].

The existing routing protocols in WSNs can be categorized into flat routing protocols and hierarchical routing protocols, or single-path routing protocols and multipath routing protocols [7]. Recent research on WSNs routing protocols has proven that clustering and multipath are needed to improve energy efficiency and load balancing.

When designing multipath routing algorithms, many parameters (e.g., path length, energy consumption of communication) also need be considered. The optimization of network parameters for WSNs routing process might be considered as a combinatorial optimization problem. Our proposed approach benefits from the success of ant colony optimization (ACO) [8] in solving the problem. The ACO algorithm is a heuristic algorithm introduced by Dorigo and his collaborators for solving some combinatorial optimization problems [9], such as traveling salesman problem (TSP) [10]. The ACO algorithm has some characteristics, such as distributed computing, self organization and positive feedback, suited for searching routing in modern communication networks.

However, few of the existing works have considered the integration of clustering, multipath and ACO to maximize the network lifetime and achieve load balancing in WSNs. Motivated by the advantages of clustering, multipath and ACO, this paper proposes a multipath routing protocol (MRP) based on dynamic clustering and ACO for reactive WSNs. The main objective of our work is to maximize network lifetime and at the same time achieve load balancing. The main contributions of this paper are listed:

• 1)    A novel distributed algorithm based on some parameters (such as signal strength, residual energy of node) is designed to form cluster among the nodes located in the event area.

• 2)    An extended ACO algorithm based on many metrics (such as residual energy, path length, energy consumption of communication) is applied to search for the multiple paths between the cluster head (CH) and sink node.

• 3)    A load balancing function is further proposed to distribute the traffic over discovered multiple paths.

The rest of this paper is organized as follows. Section 2 introduces some related routing algorithms. In section 3 we propose the system model and the motivation of our work. The details of the MRP algorithm are described in section 4. The performance evaluation of our scheme as well as the comparison with the previous typical routing algorithms is presented in section 5. Section 6 draws the conclusion.

• II.    Related work

Wireless ensor networks are a kind of decentralized network of autonomous nodes that collect and process information, and send the information to a sink node over wireless links. Limited energy nodes are not taken into account in the traditional routing protocols, which has significant impact on the overall energy dissipation. Therefore, new routing protocols need be designed for WSNs.

• A.    Hierarchical Routing

Hierarchical (clustering) technology is particularly promising and has received much attention in the research community. In a hierarchical network, the data gathered by sensor nodes is transmitted to CHs. The sensed data from nodes within one cluster usually exhibit high correlation, and therefore, a CH can aggregate data to remove redundancy and only send one packet to the sink.

In the last few years, many hierarchical routing algorithms are proposed for WSNs. One pioneering work in the literature is LEACH (Low-Energy Adaptive Clustering Hierarchy) [11]. LEACH is an applicationspecific data dissemination protocol that uses clustering to prolong the network lifetime. However, the assumption that all nodes are capable of communicating with any node in the field does not allow the network to be scalable, and LEACH does not guarantee good clusterhead distribution. To improve LEACH performance, Lindsey et al. introduced chain into clustering (power-efficient gathering in sensor information systems, PEGASIS) [12]. In this work, all nodes are connected in a chain and communicate only with the nearest neighbor. Nodes take turns to be the CH and send aggregation data to sink. Although PEGASIS outperforms LEACH in network lifetime, it assumes that all nodes have a global knowledge of the network. Thus, PEGASIS may not be efficient with closely deployed nodes in a specific area. In [13], the authors designed an ant-based algorithm (T-ANT) to cluster and achieve a uniform distribution of CHs in the network.

• B.    Multipath Routing

Multipath routing uses multiple paths to transmit data, which can achieve both load balancing and fault tolerance. There are two different multipath routings between source node and sink node. One is disjoint multipath routing [14], where the alternative paths do not intersect each other. The other is braided multipath routing, where there are typically no completely disjoint paths [15][16].

In [14], Ganesan et al. presented a disjoint multipath routing based on local information, which is a distributed algorithm and can achieve load balancing. This algorithm uses a primary route to transmit data. Only when the primary route fails, the alternative route can be used. However, this algorithm is not attractive for the network lifetime.

In [15], a meshed multipath routing with efficient strategy has been described. Such an algorithm can achieve a better throughout than the traditional multipath algorithms. However, this approach requires nodes to be equipped with GPS (Global Positioning System), which increases the cost of node.

In [16], Okdem et al. introduced a multipath routing algorithm based on Ant Colony Optimization (ACO), which uses a class of agent-like ants to develop multiple reliable routes between source and sink. It is very effective in dealing with the failure of link and searching for the routes. Due to the large number of nodes, the number of ants is quite large so that it may lead to much higher traffic in network than other algorithms.

• C.    Ant Routing

As an effective distributed approach, the ACO algorithms have been introduced to the design of routing protocol and have received many achievements [17]-[25].

The ACO algorithm was firstly used in traditional network [17]. ARA [18] was the first algorithm used in mobile ad hoc networks (MANETs), which exploits the pheromone laying behavior of ants to search for routing. The above two algorithms are however not suitable for WSNs. In [19], Liu et al. used an improved ACO algorithm (PACO) to search for multipath between source node and sink node in MANETs. Although the PACO improves the efficiency of data transmission, the number of ants for searching routing is great, resulting in great energy consumption at start-up stage. Moreover, the PACO only uses the length of path as metric without considering the current energy of nodes. So these discovered paths may contain the low energy nodes, which will shorten the working time of those paths.

Recently, routing protocol based on ACO for WSNs has been the focus of many studies [20]-[25]. In [20], Zhang et al. study three distinct Ant-based algorithms for WSNs. However, the authors only focus on the building of an initial pheromone distribution, and thus, the algorithms are only good at system start-up phase. In [21], Camilo et al. present a new WSNs routing algorithm based on ACO which can minimize communication load and save energy. Nevertheless, the algorithm does not consider the data correlation feature, the energy consumption of communication is huge when there exist a lot of sources in network. In [22], Liu et al. introduce a routing strategy on the basis of ant algorithm for WSNs, using deflection angle, energy and distance as routing factors to help ant to search for routing. The convergence rate of the algorithm is good. However, the algorithm did not utilize the redundancy of data, such that the disadvantage of the algorithm is the same as [21]. Reinforcement learning scheme is proposed in [23], which reduces the energy consumption and shortens the time delay. The algorithm, however, only uses distance as metric, so it can not protect the minimum energy node, and therefore, it may result in shorten the network lifetime. In [24], Tu et al. construct a chain by means of ant colony algorithm that connects all the nodes in the networks. Although the algorithm can find suboptimal routing for mobile agent, the time delay of the algorithm is long, and the cost of reconstructing routing is also high. In [25], Ren et al. proposed a multipath routing based on ant colony system, which extends the network lifetime. Although the algorithm balances the energy consumption among nodes by multipath, it does not take into consideration the influence of the minimum energy node on multiple paths.

Although these algorithms presented above have some advantages, there still exist some shortcomings blocking their application in the large scale WSNs. To overcome the disadvantages of conventional ant-based routing algorithms, we proposed an improved protocol by integrating the advantages of hierarchical routing, multipath routing and ACO.

• III.    System model and problem statement

• A. System Model

• 1)    Network Model

A WSN consists of large number of sensors, and wireless links representing direct communication between the sensors within the radio range. A WSN is modeled as an undirected graph G( V,E,W ), where V = { v ₁, v ₂, ⋅⋅⋅ , v_n } is the set of all the nodes. Each v n has its maximum communication radio range with radius R . E is the set of all bidirectional wireless links (i, j) ( i , j ∈ V ). A link (i,j) , denoted by e ( i , j ) ∈ E , exists between v_i and v j if d ( v_i , v j ) ≤ R. It indicates that node v i and node v j can directly communicate with each other. d(v i ,v j ) is the distance between node v i and node v j . W is the weight set of all directed links (i,j) . The weight e ij of link (i,j) is the energy consumption of communication between i and j . Let S_e ={ v₁ , v₂ , … , v_l } be the set of all nodes in the event area. Note that S e is the subset of V ( S_e ⊆ V ). Let N i denote the set of neighbors of node i and N_i = { j | d_ij ≤ R , j ∈ V }.

In this paper, the following assumptions are adopted:

• •    N sensor nodes are uniformly distributed within a square field. Each sensor nodes has unique ID.

Sensor nodes in the event area are grouped to cluster.

• •    All sensor nodes keep static or less movement after being deployed.

• •    The energy of sensor nodes cannot be recharged.

• •    Sensor nodes are location-unaware, i.e. a sensor node need not rely on the expensive devices, such as Global Positioning System (GPS) to receive the position information for finding the shortest path routing to the sink.

• •    Communication is symmetric. Nodes can estimate distance based on the signal strength each other, and at the same time the radio power can be controlled.

• •    We assume ideal MAC layer conditions. That is, perfect transmission of data on a node-to-node link.

• 2)    Radio Model

In order to evaluate the energy dissipation between node i and node j , we use the radio model used in [11], [28]. The energy costs of transmitting and receiving a k bit data packet between node i and node j with distance d are denoted by E T (i,j) and E R (i,j) which may be computed by:

E T ( i , j ) = k ( E elec + E amp × d ^γ )           (1)

E R ( i , j ) = kE elec                       (2)

where E elec and E amp are the per bit energy dissipation for transmission and reception, respectively; γ ∈ {2, 4} can be seen as the path loss exponent.

• 3)    Problem Statement

The MRP algorithm uses ACO algorithm to search for multiple paths after cluster is formed. The process of ants moving will result in forming multiple paths between CH and sink. After multiple paths are formed, data will be transferred along the multiple paths. The model of data transmission in MRP is shown in Fig. 1.

Figure 1. Data Transmission Model

From Fig. 1, we know that MRP can maximize the network lifetime from two ways. One is to reduce the transmitted data by clustering, which can use data aggregation to reduce energy consumption. The other is to use multiple paths to achieve load balancing (i.e., it can avoid frequently using the path, in which the minimum energy node locates.).

Based on the above introduction, we can describe the objective of MRP as follows: maximizing the network lifetime (Tnet), while minimizing the energy consumption between the CH and sink, which can be formulated as follows:

max ^Tnet , min Z    e ij                ⁽³⁾

• [ i , j e V ,( i , j )e E ]

Theorem 1: Network lifetime is associated with residual energy of node, the energy consumption and the number of hops in path p .

In order to prove the theorem, we use a simplified model of energy consumption, in which energy consumption is same in each node.

Prove: N is the set of discovered paths between the CH and sink. The energy consumption of path p (p e N ) is the sum of the energy expended at each sensor node along the path. If (n1,n2,•••,nm) denotes the sequence of nodes along path p, the total energy consumption E(p) is given by m-1

E ( P ) = Z ( E r + E cpu + E, ) = ( E r + E cpu + E, ) x ( m - 1) (4) k =1

where E r and E t represent the energy consumption of receiving or transmitting L -bit data, respectively. E cpu is the energy consumption used in these jobs, such as computation, sensing events etc..

From [3][4], we have

Ecpu << Et + Er(5)

Therefore, we have

E(p) = (Et + Er) x (m -1)(6)

In (6), because the value of ( m -1) is equal to the number of hops between the CH and sink, we have

E (p) = (Er + Et) x hcH (p)(7)

where h_CH ( p ) is the number of hops in path p .

Thus, E r + E t can be given by

Er + Et = E (p)/ hcH (p)(8)

Since the working time T(P) of path p is partly determined by the minimum energy node in path p , T(P) is given by

T (p) = EmJ p)/(Er + Et)(9)

where E min (p) is the current energy of the minimum energy node in path p .

Using (8) and (9), we have

T (p) = EmJ p) x hcH (p)/ E (p)(10)

We define the network lifetime T net as the time when the first node in the network runs out of energy. Then, T net is given by

^Tnet = min ^{T (} p ) = min ^E min ⁽ p ) ^{X h}CH ⁽ p ) / ^{E (} p ) ⁽¹¹⁾ p e N p e N

Therefore, T_net is associated with the residual energy of the minimum energy node, energy consumption in a path and hop distance to sink.

According to (3), (11), it is obvious that maximizing the network lifetime Tnet is equivalent to maximizing the minimum T(P). We have max imize min T( p) (12) p e N

From (12), we infer that MRP needs to prolong working time of the minimum energy node and reduce the energy consumption in a path in order to maximize the network lifetime.

W . DESCRIPTION OF MRP

MRP is divided into three phases: cluster formation, constructing multipath and data transmission. The first phase is executed when an event happens. Its objective is to realize dynamic clustering. In the second phase, the CH use ACO to search for multiple paths. The last phase dynamically chooses a path to transmit data according to an evaluation function.

To start the operation of the routing scheme, nodes having information for the sink initialize the routing task by transmitting an ADV message to neighbor nodes. Each node then broadcasts the ADV message to its neighbor nodes and so on. At the end of the initiation stage of network, each node constructs a table containing neighbor information, which is shown in Tab. I.

TABLE I.

N eighbors information

Neighbor ID	Phermone Value	Residual Energy	Distance to Sink	Hop count	Tag
i	T ci	E i	D is	h i	0
j	T cj	E j	D js	h j	0
				0	0

The information in Tab. I will be used to help ant search for routing. ID indicates the identification number of a node. T _ci is the pheromone value on link (c,i) , which represents the local link situation and quality. At the beginning, the pheromone in the network is a constant; then, it varies with ant routing. D is is the distance between node i and sink, and it may be estimated by received signal strength ( RSS ) [26]. Hop count is the number of hops from a node to sink. Tag indicates the instance of being visited by an ant. Tag =1 indicates that the current node has been visited by an ant, otherwise, Tag =0.

• 1)    Phase I: Cluster Formation

The conventional hierarchical routing algorithms [11, 12, 27] do not fit for monitoring burst events in reactive WSNs. For example, though there is no event happening, each CH will still have to flood control packets to periodically reconstruct cluster; clustering is not related to an event, i.e., nodes sensing the event locate in different clusters, which will reduce the data aggregation efficiency; when reconstructing the clusters, an event may happen, and it will result in the event not being detected.

In order to overcome the disadvantages [10, 12, 27], MRP adopts a dynamic clustering algorithm, i.e., nodes have information about an event taking place nearby will join clustering. The clustering algorithm obeys the rules as follows:

• •    Nodes located in the event area can sense the distance to the event according to RSS .

• •    Nodes know the residual energy of neighbor nodes in the event area.

• •    If RSS i >  Threshold Value [27], node i locates in

the event area. ( RSS_i is the received signal strength of node i )

Theorem 2: When a CH locates in the center of the event area, the sum of energy consumption for transmitting data is the least in the cluster.

Prove: There is m nodes distributed in a cluster. Node i locates the center of the event area with coordinate (0,0).

We have

m

= £ ( x k + y 2 )

к =1, k * i

where Di is the sum of distance between node i and other nodes in the same cluster. (Node i is the CH.)

If node j is selected as the CH with coordinate ( x j , y j ), we have

m

D j = £ ⁽ x k - x ) ^{2 + (} У к - y_; ) ^{2          (14)}

к =1, к * j

We calculate the expectation of (13), (14) respectively as follows

m

E(Д) = E( £ (x2 + Уj2))(15)

j =1, j * i

m

E(Dj) = E( £ (Xk -x ) + (Ук — yj-)2)(16)

к =1, к * j

According to (15), (16), we have

m

E (Д) = E [(x2 + y2) + £ (x2 + y2)](17)

к =1, к *{ i , j }

m

E ( Dj) = E [( x 2 + y 2 ) + £ ( x k - x ) + ( У к — y j -)² ] (18) к =1, к *{ i , j }

From (18), we have

m

E ⁽ D J= E ^[( x j ^{2 + y}j ^{2 )] +} E ^[ £   ⁽ x k ^- x j ^{) 2 + ( y}k ^- y j ^{) 2 ]}

к = 1, k * { i , j }

m

= E [( x 2 + У 2 )] +   £   2 Cov ( X , Y)

к = 1, к * { i , j }

where X, Y are the set of coordinates. Cov(X,Y) is given by

Cov ( X , Y ) = D ( X ) + D ( Y )                   (₂₀₎

= E ( X 2 ) + E ( Y ²) - E ² ( X ) - E 2 ( Y )   ( )

where D ( X ), D ( Y ) are variance of X, Y, respectively.

E ( X ) = 0, E ( Y ) = 0 .

From (19), (20), we have

m

E ( D ) = E [( x 2 + у 2 ) + 2 £ ( x k ) ² + ( У к ) 2 ]    (21)

к =1, к *{ i , j }

From (17), (21), we have

E ( D i ) <  E ( D j )                    (22)

According to the radio model described above, we can infer that the energy consumption is associated with radio distance, i.e., the shorter of radio distance is, the smaller of energy consumption would be. Considering (22), we can draw a conclusion that the CH locating in the center of event area consumes the least energy for transmitting data.

In order to prolong the network lifetime, we can describe the goal of clustering: maximizing the working time of a cluster, while minimizing the energy consumption in the cluster, which can be formulated as follows:

max T_C , min £ E Se             (23)

( i , j e Se )

where T_C is the working time of a cluster. E_Se is the sum of energy consumption in a cluster.

Since the CH takes on a lot of work in a cluster, the residual energy needs to be considered when selecting a CH. Based on Theorem 2 and (23), a node with the higher residual energy, more neighbors and stronger signal strength (i.e., the node is nearer to the signal center) has more opportunity of becoming a CH in the event area. The objective function for becoming a CH, qi, is given by qi = (Ei)k1x (Ki)k2 x (SEi)k3                (24)

where E i is the residual energy of node i . K i is a temporary set of node i , which is used to store the number of neighbors in the event area. SE i is the sensed signal strength to an event. k 1 , k 2 , k 3 are parameters to control the weights of E i , K i and SE i respectively.

Algorithm 1 represents the pseudo-code of cluster formation. K is a temporary set which is used to store the number of CH advertisement overheard. There are two timers associated with each sensor: T a and T i . T a is a delay time ， when a node located in the event area records the number of neighbors. It is related to network scale. T i is the waiting time when node i broadcast to be a CH, which is given by

T = q / q i                       (25)

where q is a coefficient, which is used to control the value of T i . T i is inversely proportional to q i , i.e., the waiting time of a node with the highest q i is the shorest.

Algorithm 1: Cluster Formation

Begin

• 1 ：    Schedule each node wait time with T_a sec. delay

• 2:     while ( T a * 0)

• 3:        if Threshold <  RSS i then

• ^4:          if node j is in the event area and Threshold <  RSS_j

• 5:            K i = K i +1;

• 6:           end-if

• 7:         end-if

• 8:      end-while

• 9:      if Threshold <  RSS i then

• 10:       node i calculates q_i and T_i ;

• 11:       if T i ^ 0 then

• 12:         wait;

• 13:         collect the sender of any other incoming CH advertise-

• 14:         ment in K ;

• 15:         else

• 16:         if K =0 then

• 17:          send CH advertisement message;

• 18:           else

• 19:            send a join-request to the node j ( q j is the biggest);

• 20:          end-if

• 21:       end-if

• 22:    end-if

• 23    broadcast TDMA schedule to members;

End

Phase I allows only one CH in the event area.

• 2)    Phase II: Constructing Multipath

In MRP, when the CH needs to deliver data to sink, an improved ACO algorithm is used to establish multiple paths with optimal or suboptimal energy consumption.

There are three kinds of ants in MRP: search ant (SANT), backward ant (BANT) and abnormal ant (AANT). A SANT is used to collect information about multiple paths and intermediate nodes as it travel along the path. A BANT is used to update the pheromone value along the reverse path, and bring information of path to source node, such as residual energy of node, path length and energy consumption of the current path. MRP adds a new type of ant: Abnormal ant (AANT), which is used to partly avoid stagnation of the protocol.

The procedure of searching for multiple paths is as follows:

• •    The CH creates several SANTs to search for sink.

The SANTs gather path information as they travel along the paths.

• •    Sink creates a BANT when a SANT arrives. The BANT is sent back following the reverse path. When it moves, it need update the pheromone on the link (i,j) at the reverse path.

of SANT is related to the network scale and the demand of application.

The format of message brought by a SANT is shown in Fig.2.

Message Type

SID

DID

К

^min

Ep

H

TTL

Figure 2. Message Format of a BANT

The message type field indicates that it is a SANT. The S_ID field denotes the previous node identification. The field D_ID is next node identification. The K field is the number of a SANT. The E min field gives the minimum energy till the current node. The Ep field gives the sum of energy consumption till the current node. The H field gives the hop count so far. The TTL (time-to-live) field gives the depth that a SANT can travel (When a SANT is forwarded, the value of TTL is decremented. That is to say, if TTL reaches to zero before the SANT arrives at sink, the SANT message is discarded.).

In order to balance load among nodes and maximize the network lifetime, we modify those equations of the basic ACO as follows:

T ⁽ t ) ^x n ij ⁽ t t)

P j ( t ) ЧЕ т а ⁽ t ) ^{x п (} t )’

K

0,

Vj' e N. and j t MK i                 (26)

otherwise where Pij(t) is the probability of selecting the next hop node j of the current node i. nij denotes the local heuristic value of the link (i,j), and ту is the pheromone value on link (i,j). a and p are two parameters, which are used to control the relative weight of pheromone trail and heuristic value, respectively. M k contains the nodes already visited. In MRP, Mk is kept in the node’s memory instead of keeping in a SANT’s memory. This approach can decrease the size of the data to be transmitted and save energy. nij can be given by n = 1

n max

^A ij n min

(Aij > Amax)

(Amin < Aj < Amax)

(Aij < Amin)

A ij

( E j ) ^{k 4} ( d ij ) ^{k 5}

+ e ij

e ij =1

( E j ) ^{k 4} ( d ij ) ^{k 5} 0

d js ) k ₆ d is

⁽ hj <  h i )

otherwise

where k 4 , k 5 , k 6 are three parameters, which are used to control the impacts of E_j , E_y , 9 _ij on A i _j , respectively. n _min and n _max are parameters predetermined.

Equation (30) and (31) are used to update the pheromone value at link (i,j) .

T ij ( t , t + 1) = (1 - p ) xT j ( t ) + p xA r k ( t , t + 1)     (30)

A r k ( t , t + 1) = X x ( E + E j )d j            (31)

where p is evaporation factor which serves to diminish the intensity of existing trail over time. X is a coefficient. d_i j is the distance between node i and node j . E_i is the residual energy of node i .

Algorithm 2 represents the basic operations of a SANT. RAND(x) is a function to generate a random number uniformly distributed between 0 and x .

Algorithm 2: A SANT for the Proposed MRP

Begin

1 ： if TTL<>0 then

• 2:        if a SANT arrives at sink then

• 3:        create and release a new BANT;

• 4:         else

• 5:         if RAND (x)<0.001 then

• 6:          create a AANT;

• ₇          the AANT randomly chooses a node as the next hop

:     node;

• 8:           else

• 9:           choose the next hop node j according to (26)-(29);

• 10:          refresh the residual energy of i and j ;

• 11:          if selected node visited then

• 12:           back to the previous hop node;

• 13:           re-elect another node as the next hop node;

• 14:           end-if

• 15:          using (30), (31) to refresh pheromone value of link (i,j) ;

• 16:         end-if

• 17    end-if

• 18    end-if

End

• b) Backward ant (BANT)

When a BANT is back along the reverse path passed by a SANT, the BANT also need update the pheromone value on link (i,j) (Equ. (30) and (32) are used to calculate and update the pheromone value) .

a r k ( t , t + 1) = c x f ⁽ t )   f best ⁽ t )

^{ij ,                         f}best ^{( t * )}

According to (12), we have f (t) = c 0

f 1 ^{k 7} ( t ) f 2 ^{k 8} ( t ) f 3 ^{k 9} ( t )

f 1 ( t ) =    min   ( E i ) 1 e(n1,n 2 ,-,nm)	(34)
f 2 ( t ) - Z E j ( i , j )c p	(35)
f 3 ( t ) - Z ( i , j )	(36)

(i, j >' p f6est (t) = max[ f (t)], t- 1, -., t              (37)

where f(t) is the evaluation function on the current path. f1(t) is the minimum energy node in path p. f2(t) is the sum of energy consumption in path p. f3(t) is the length of path p. fbest(t*) is the optimal solution so far. (n1, n2, …, nm) denotes the sequence of nodes along path p. c and c0 are coefficients, which can be used to control the value of (32), (33) respectively. k7, k8 and k9 are weights that determine the relative importance of f1(t), f2(t) and f3(t) respectively.

In (32), a scheme of negative feedback is introduced into realizing reward or punishment to the current result. The scheme is helpful of fairness among found multiple paths.

The format of message brought by a BANT is shown in Fig. 3.

Message Type

DID

К

F • ^mm

Ep

Length

Figure 3. Message Format of a BANT

The Message Type field indicates that it is a BANT. The Length field is the path length from sink to the current node. The meaning of other fields is same as that of message brought by a SANT.

Algorithm 3 denotes the basic operations of a BANT.

Algorithm 3: A BANT for the Proposed MRP

Begin

• 1 ：    if sink is reached then

• 2:        a new BANT is generated;

• 3:          while the CH is not reached

• 4:          the BANT moves along the reverse path;

the BANT using (30), (31) to update pheromone

^:        value of link (i,j ) ;

.               , ., j f ( t )         iff ( t ) >  f_tel ( t *)

• 6:              Jb«(t )-V.^;

^ j ( t )       otherwise

• 7:            calculate E min , E p and Length ;

• 8:            update the residual energy of i and j ;

• 9:          end-while

• 10:       end-if

End

• 3)    Phase III: Data Transmission

MRP is different to these algorithms in [14], [25] because the CH in MRP dynamically chooses one path to transmit data. According to (12), a load balancing function of path i is given by fi = k10 x Emin (i) + k11/ E(i) + k12/ Length     (38)

where k₁₀ , k₁₁ , k₁₂ are weight values, k₁₀ + k₁₁ + k₁₂ =1. E_min(i) is the residual energy of the minimum energy node in path i . E(i) is the sum of energy consumption in path i . Length i is the length of path i , which can be used to estimate the delay of a path.

The selecting probability P i of path i is given by

N

Pi - fi / Z f j ; (i=1, •", N )             (39)

j=1

N

Z Pi - 1                    (40)

i -1

where N is the set of discovered paths.

The CH uses (38)-(40) to calculate the probability and transmit data along the selected path. Since the path is dynamically chosen, load balancing among the paths is achieved.

• 4)    Route Maintainence

In MRP, route maintainence is responsible for the maintenance of the routes during the communication. The process of route maintainence will be initiated when there comes out these conditions as follows:

• •    When the residual energy of the current CH is lower than 50% average energy of all nodes in the cluster, a new CH will be selected according to (24). If there are more than two paths to sink, the new CH will send the packets via these paths. Otherwise, the new CH will initiate a new route discovery process.

• •    When the number of multiple paths is less than two, that means the reliability of path decreased seriously. The current CH will initiate a new route discovery process.

Ⅴ. performance evaluation

Various performance metrics are used for comparing different routing strategies in WSNs. We have used the following:

• •    Average Energy : The metric gives the average of

energy of all nodes at the end of simulation.

• •    Energy consumption : The metric gives the energy consumption of nodes in the event area for transmitting a data packet to sink.

• •    The standard deviation of energy : The metric gives the average variance between energy levels on all nodes.

• •    Network lifetime : This metric gives the time of the first node running out of its energy.

• 500. For the same number of nodes, we randomly generate ten network topologies and run these algorithms over them to obtain the average results. In each network, the sensor nodes are randomly distributed on a M x M region with M =200m. For radio power consumption setting, we adopt the first-order model [11] and set E elect =50nJ/bit, E_amp =100pJ/bit/m², and у = 2 . The energy for data aggregation is set to E DA =5nJ/bit. The parameters ( k 1 , k 2 , k 3 , k 4 , k 5 , k 6 , k 7 , k 8 , k 9 , k 10 , k 11 , k 12 ) are set to (0.5, 0.1, 0.4, 2, 1, 1, 0.4, 0.2, 0.4, 0.5, 0.3, 0.2).

We constructed an event driven simulator by using VC++. By using the simulator, the proposed scheme was compared with the TEEN [27] dynamic clustering algorithm and the other two kinds of multipath algorithms in [14] (MP) and [25] (MACS) respectively.

We evaluate these four algorithms over a set of sensor networks with the number of nodes ranging from 100 to

Table II lists the other simulation settings. T ini ( i , j ) is the initial pheromone value at a link (i, j) .

TABLE II.

L ist of many P arameters used

Parameter	Value
a	2
e	2
p	0.2
T.m ( i . j )	k
the number of event	1
packet size	512 bytes
broadcast packet size	20 bytes
the coordinate of sink	(0,200)
event radius	20 m

• f 0.01,if node i and node j are neighbors k = ■!                                                       .

• [ 0      otherwise

We designed two scenarios to compare the performance of the different algorithms. The first scenario (Fig. 4) simulates a homogeneous WSN where the sensor nodes were randomly deployed with same initial energy. The initial energy of each node is 2 joules. The second scenario (Fig. 5) simulates a heterogeneous WSN where the network is composed of many nodes with different initial energy. The energy level changes between 1 joule and 2 joules, which are uniformly distributed over the nodes.

TEEN MP MACS MRP

100%

98%

96%

94%

Number of Nodes

TEEN MP MACS MRP

b) Energy Consumption

a) Average Energy

—•— TEEN —■-- MP      MACS      MRP

Number of Nodes

— ♦ — TEEN —■— MP     MACS MRP

Number of Nodes

c) Standard Deviation

d) Network Lifetime

• Figure 4.    Performance in WSNs with same initial energy levels

Fig.4 presents the results of the simulation for the studied metrics to different network scale in scenario one. MRP has better results compared to the other algorithms.

In Fig. 4a), the average energy of the MRP is the highest than other algorithms. This indicates that there exists more residual energy of nodes in MRP, which implies MRP need less energy for transmitting data.

In Fig. 4b), it shows a linear increase of energy consumption as the network becomes denser, as more sensor nodes get involved with for all the algorithms. That brings more traffic into network. It is obvious that there is less energy consumption of MRP and TEEN. However, MRP outperforms TEEN algorithm. Although TEEN also belongs to a dynamically clustering algorithm, the structure of cluster in TEEN is not related to the event area. Therefore, energy consumption of TEEN is higher than that of MRP. MP and MACS are the most costly algorithms because they did not use clustering to reduce the traffic. And with the source nodes increasing (i.e., the network topology is from sparse to dense), the energy consumption of MP and MACS is much greater than the other two algorithms. The reason is that MP and

MACS algorithms fail to take advantage of the feature of the data correlation when the number of neighbor nodes becomes more.

In Fig. 4c), when compared with the other algorithm, MRP presents a significant reduction on the standard deviation. It indicates that MRP can efficiently balance the energy consumption on all nodes.

Fig. 4d) shows the network lifetime for the four algorithms. It is evident that the network lifetime of MRP is almost twice of that obtained by the other algorithms. The influence of network size is the lowest to MRP. The reason is that clustering and dynamically choosing one path to transmit data can greatly contribute on reducing energy consumption and achieving load balancing among all nodes. MACS outperforms TEEN because it can alternately use multiple paths to transmit data.

Among of the four algorithms, the performance of MP is the worst. The reason is that MP always uses the primary path to transmit data, which results in energy of the nodes in the primary route depleted very soon.

—♦— TEEN —■— MP MACS MRP

100   200   300 400   500

Number of Nodes

—о  TEEN —■— MP — △ — MACS    MRP

b) Energy Consmption

a) Average Energy

TEEN MP MACS MRP

100 200 300 400 500

Number of Nodes

Number of Nodes

c) Standard Deviation

d) Network Lifetime

• Figure 5.    Performance in WSNs with different initial energy levels

The results illustrated in Fig. 5 correspond to the second scenario. From Fig. 5, we can see that the results are very similar to those of the first scenario. Although the initial energy of nodes is randomly distributed, MRP still presents the best results. That can be explained by the adaptability of the protocol, which can efficiently balance the energy consumption among nodes by dynamic clustering and using multiple paths to transmit data. The simulation results also illuminate that MRP is suitable for either the homogeneous network or the heterogeneous network.

И . CONCLUSION

For monitoring the burst events in WSNs, we have proposed a novel multipath routing protocol based on clustering and ACO. By introducing an objective function to carry out dynamic clustering, MRP improves the efficiency of data aggregation, thus, reduce the energy consumption. We also use an improved ACO algorithm to search for the optimal and suboptimal paths based on many metrics that can balance the energy consumption among nodes. Furthermore, a load balancing function is presented for dynamically choosing one path to transmit data. Performance evaluation shows that MRP achieves better load balancing and lower energy consumption, and then, maximizes the network lifetime.

As explained before, MRP has some parameters that need to be set. The value of these parameters has a great impact on the performance of the algorithm. As for future research, we plan on making the algorithm compatible with different networks by adaptively adjusting the value of these parameters. Furthermore, we intend to extend the algorithm to monitor high-speed objects.

Acknowledgment

This work was supported by the National High-Tech Research and Development Plan of China (Grant No. 2007AA10Z241, 2006AA10A301) and the National

Natural Science Foundation of China (Grant No. 60864003). We would like to thank the anonymous reviewers for their perspicacious comments.