INTRODUCTION
Wireless sensor networks consist of hundreds to thousands of small,
lowcost, lowpowered sensor nodes, where the nodes are densely deployed
across certain geographical areas (Hill, 2003; Liu and Das, 2006).
In traditional besteffort routing, throughput and delay are the main
concerns. But there is no guarantee that a certain performance of throughput
or delay will be ensured throughout the connection (Jung et al.,
2007; Wadaa et al., 2005). On the other hand, when realtime or
multimedia data are involved in communication, some performance guarantees
for certain metrics such as delay, bandwidth and delay jitter are needed.
Such guarantees can be achieved by employing special mechanisms known
as QoS protocols (Heinzelman et al., 2002).
If we implement some works with WSN, QoS is another important problem in WSN
design. Different network routing will cause different QoS levels. But it is
a Nondeterministic Polynomialtime hard (NPhard) problem to search a path
that meets the QoS requirements in WSN. When the number of nodes in WSN rises,
the solution space of routing path increases exponentially. Therefore it is
necessary to use efficient optimization algorithms to accelerate the searching
process (Fan et al., 2008).
ENERGY CONSUMPTION MODEL
A sensor uses its energy to carry out three main actions: acquisition,
communication and data processing (Muruganathan et al., 2005; Saha
et al., 2007). Although varying according to the monitoring type,
the power consumption to perform the data acquisition is not very important (Wadaa et al., 2005).

Fig. 1: 
Communication power consumption model in WSNs 
The communications consume much
more energy than other tasks, in emission as well as in reception (Fig.
1).
To transmit a message of l bits over a distance of d meters, the
energy that transmitter consumes is given by:
where, E_{elec}, l, d and ε_{amp} denote
energy of electronic signals; size of a message, distance between transmitter
and receiver and amplification factor, respectively. In addition, d_{0},
M and d_{toBS} represent the limit distance over which the transmission
factors change their value, the size of the area and the distance to the
base station.
To receive a message of l bits, the receiver consumes:
When there are N nodes in WSN, the optimal number of the Clusterheads
(CHs) (Jung et al., 2007):
Generally, we have E_{elec} = 50 nJ/bit, e_{amp} = 0.0013
pJ/bit/m^{4} and e_{fs} = 10 pJ/bit/m^{2}.
DYNAMIC CLUSTERING ALGORITHMS
One of the most common clustering algorithms, the dynamic clustering
technique, aims at assigning each pattern data set to the cluster having
the nearest centroid. The basic steps of clustering are:
Step 1: All nodes are assigned a cluster number between 1 and
k randomly, k is number of cluster desired which can be computed from
Eq. 3.
Step 2: Find the cluster center of each cluster.
Step 3: For each node, find the cluster center that is closest
to the node. Assign the node to the cluster whose center is closest to
it.
Step 4: Recompute the cluster centers with the new assignment
of nodes.
Step 5: Repeat Steps 3 and 4 till clusters do not change or for
a fixed number of times.
Dynamic clustering algorithms employ an iterative approach to group the
node into a predefined k number of clusters by minimizing a cost function:
where, C_{j} is the center of jth cluster and is the center nearest
to node object d_{j}, n is the number of elements in node set,
q is an integer which defines the nature of the distance function. For
numeric valued nodes sets, a cluster center is represented by the mean
value of each attribute, the mean being computed over all objects belonging
to the cluster.
MULTIOBJECTIVE PROGRAMMING ALGORITHM
Put here, we introduce mobility prediction method utilizing the
location and mobility information provided by GPS. In our initial approach,
we assume a free space propagation model, where the received signal strength
solely depends on its distance to the transmitter. We also assume that
all nodes in the network have their clock synchronized. Therefore, if
the motion parameters of two neighbors are known, we can determine the
period of time during which these two nodes will remain connected.
Assume that two nodes i and j are within the transmission range r. Let
(x_{i},y_{i}), v_{i} and θ_{i} be
the coordinate, the speed and the moving direction of mobile host i.

Fig. 2: 
The propagation of message on their way to the destination
node E 
Then,
the amount of time t, for which the ith and jth mobile hosts will stay
connected, satisfies:
If we can predict the Link Expiration Time (LET) along each hop on the
route, we will be able to predict the Route Expiration Time (RET). When
a node is forwarding the message, it also appends its own ID and the LET
for the last link of the message arrives at the destination, thus it contains
the list of nodes along the route it has traveled and the LETs for each
hop along the route. The destination can then determine the RET for the
route by using the minimum of the set of LETs along the route (Su et
al., 2001).
In Fig. 2, the source A sends a message for destination
node E. Node B, C, D and F will forward the message and append information
such as their own node ID and the LET of the last link that the message
was received from. Therefore in our example, two messages arrive at node
E. One contains path (A, B, C, D, E) with LETs = (10, 9, 12, 13) and the
other contains path (A, B, F, C, D, E) with LETs = (10, 12, 12, 12, 13).
Since RET is the minimum of the set of LETs for the route, node E can
then obtain the RET for both routes. In our example, path (A, B, F, C,
D, E) is more stable than path (A, B, C, D, E) since it has larger RET
of value 10. However, path (A, B, F, C, D, E) has more hops than path
(A, B, C, D, E) since it has hops of value 5.
The delay experienced by the last packet, which has arrived along the
route, is another important performance index in WSNs. Since network load
conditions will change from time to time during connection, the delay
will also change accordingly. It depends largely on the transmission time
and processing time.
In our example, there are n hops in the route. Let (x_{0}, y_{0})
be the coordinate of mobile source node, (x_{n+1}, y_{n+1})
be that of mobile destination node. (x_{i}, y_{i}), i
= 1,2,L...,n represents the coordinate of the middle node. Then, the amount
of time two mobile hosts will delay, D is predicted by:
where, k_{1} is the time delay factor for transmission and k_{2}
is the time delay factor for processing the packets?
Though deeply analyzing the two important performance indexes in WSNs
(index of stability and index of dynamic delay), we build the multiobjective
programming model. Then how to evaluate the route? The key is to design
a comprehensive evaluation index. This index should reflect to the performances
of be chosen routes, can be the standard of routing.
In multiobjective programming model, there are three generous characters
in the progress. They, respectively are index of stability S(P), index
of dynamic time delay D(P) and index of hops H(P), respectively. All of
the above reflect to the performances of the chosen route P. We define
the comprehensive evaluation function:
where, C(P) is the cost of the chosen route P and w_{k} is the
kth weight of the index, satisfying w_{1} + w_{2} + w_{3}
= 1.
From the comprehensive evaluation function, if there are N routes {P_{i}}
existing between source node and destination node and C(P_{i})
> C(P_{j}) for all i ≠ j, then we should choose P_{j}
as our route.
SIMULATIONS
We use MATLAB to simulate the Energy Consumption Model.
Figure 3 presents the results. When the number of the nodes in sensor
filed is growing, the more CHs are needed.
Present simulation models a network of 500 mobile hosts placed randomly
within a 5000x5000 m area. Different number of the CHs will cause different
energy consumption. Energy consumption is the most important problem in
WSNs. In Fig. 4, when there are six CHs in the filed,
the cost of energy consumption is the least.
In dynamic clustering model, our simulation models a network of 300 mobile
hosts placed randomly within a 5000x5000 m area. From Eq.
3, we find that when there are 5 CHs in the sensor filed, the cost
of energy consumption is the least. Using dynamic clustering model, we
assign all the nodes in sensor filed into 5 classes (Fig.
5).
The algorithm is effective and robust. The program runs less than 10
m sec in notebook computer (Intel Core Duo processor 1.66 GHz). Then,
we take the random mobility of the nodes into further consideration.

Fig. 3: 
Simulation of the energy consumption model 

Fig. 4: 
Relation between the number of CHs and the energy consumption 

Fig. 5: 
Simulation of the dynamic clustering model 
Table 1: 
The initial distance between nodes (m) 

Table 2: 
The initial time delay between nodes (msec) 

Table 3: 
The survive time between nodes (msec) 

We
find that when the velocity of nodes is less than 20 m sec^{1}, the
result of the dynamic clustering model keeps the same after one minute.
Moreover, we use Matlab and Lingo to simulate the multiobjective programming
process. Our simulation models a network of 5 mobile hosts placed randomly
within a 1000x1000 m area. We set the longest distance in one hop is 500
m. There are some packets which need to be transmitted from node 1 to
node 5. The initial distance, initial time delay and initial survive time
between nodes were determined randomly by Matlab and shown in Table
13.
Using DSR protocol, when there are some packets to transmit from node
1 to node 5, the route is 135. This route is shortest, but its dynamic
time delay is 102 m sec. It is out of place to some situations strict
to the time delay. In these situations, we can improve the weight of the
dynamic time delay index. Then the route is 145 in multiobjective programming
model. This route is not the shortest route, but its time delay is 32
m sec, about one third of the time delay obtain by DSR protocol, which
proves the effectiveness of our algorithm.
CONCLUSIONS
We have proposed an energyaware Qos routing algorithm for WSN,
which can also run efficiently with besteffort traffic. We have improved
the first order energy consumption model with dynamic clustering; Based
on clustering, we have built the multiobjectives
programming model to support QoS. Simulation and comparisons with some
typical route algorithms show that our approach is robust and effective
and also demonstrate the effectiveness of our approach for different metrics
with respect to the baseline approach where same link cost function is
used without any service differentiation mechanism.
ACKNOWLEDGMENT
The study is supported by the ZJNSF (Grant No. Y106162), China.