Abstract: Wireless sensor networks (WSN) is an energy limited system, thus this study presents an energy-aware quality of service (QoS) routing algorithm for it, which can also run efficiently with best-effort traffic. Furthermore, our work differs from existing algorithms in two ways: (1) We improve the first order energy consumption model with dynamic clustering; (2) We use clustering to build the multi-objectives programming model to support QoS. Simulations and comparisons with some typical route algorithms show that our algorithm is robust and effective.
INTRODUCTION
Wireless sensor networks consist of hundreds to thousands of small, low-cost, low-powered sensor nodes, where the nodes are densely deployed across certain geographical areas (Hill, 2003; Liu and Das, 2006).
In traditional best-effort 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 real-time 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 Non-deterministic Polynomial-time hard (NP-hard) 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:
(1) |
where, Eelec, l, d and εamp denote energy of electronic signals; size of a message, distance between transmitter and receiver and amplification factor, respectively. In addition, d0, M and dtoBS 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:
(2) |
When there are N nodes in WSN, the optimal number of the Cluster-heads (CHs) (Jung et al., 2007):
(3) |
Generally, we have Eelec = 50 nJ/bit, eamp = 0.0013 pJ/bit/m4 and efs = 10 pJ/bit/m2.
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: Re-compute 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:
(4) |
where, Cj is the center of jth cluster and is the center nearest to node object dj, 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.
MULTI-OBJECTIVE 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 (xi,yi), vi 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 i-th and j-th mobile hosts will stay connected, satisfies:
(5) |
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 (x0, y0) be the coordinate of mobile source node, (xn+1, yn+1) be that of mobile destination node. (xi, yi), 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:
(6) |
where, k1 is the time delay factor for transmission and k2 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 multi-objective 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 multi-objective 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:
(7) |
where, C(P) is the cost of the chosen route P and wk is the k-th weight of the index, satisfying w1 + w2 + w3 = 1.
From the comprehensive evaluation function, if there are N routes {Pi} existing between source node and destination node and C(Pi) > C(Pj) for all i ≠ j, then we should choose Pj 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 multi-objective 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 1-3.
Using DSR protocol, when there are some packets to transmit from node 1 to node 5, the route is 1-3-5. 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 1-4-5 in multi-objective 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 energy-aware Qos routing algorithm for WSN, which can also run efficiently with best-effort traffic. We have improved the first order energy consumption model with dynamic clustering; Based on clustering, we have built the multi-objectives 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.