Subscribe Now Subscribe Today
Research Article
 

An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks



Liqun Shan, Jinkuan Wang and Wei Wei
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

In Wireless Sensor Networks (WSNs), each sensor obtains data and have to communicate these data to a central node. Because sensors are battery powered they are highly energy constrained. Data aggregation can be used to combine data of several sensors into a single message, thus reducing the data traffic and the power consumption. This study has considered the problem of maximizing the time at which the first node with data aggregation in WSNs drains out of energy. It investigated optimal data aggregation routing for achieving the goal above. The problem is formulated as a linear programming problem. By solving the network lifetime optimization problem, the optimal solutions and the distributed implementation can be obtained that are based on the primal-dual decomposition. Simulation results indicate that the algorithm is superior to the existing methods.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Liqun Shan, Jinkuan Wang and Wei Wei, 2012. An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks. Information Technology Journal, 11: 1463-1469.

DOI: 10.3923/itj.2012.1463.1469

URL: https://scialert.net/abstract/?doi=itj.2012.1463.1469
 
Received: March 02, 2012; Accepted: April 21, 2012; Published: July 03, 2012



INTRODUCTION

The primitive operation of Wireless Sensor Networks (WSNs) is to monitor the physical environment, process the sensed information and deliver the results to a specific sink node. WSNs consist of low-power and energy-constrained sensor nodes. For an energy-constrained system, the primary target is to design energy-efficient protocols to maximize the network lifetime (Raghunathan et al., 2006). The study defined the network lifetime is the time when the first sensor node runs out of its energy. When optimizing data aggregation and routing are combined, data aggregation reduces the traffic across the network and reduces the power consumption of the nodes close to the sink node. At the same time, the routing can balance the traffic to avoid overwhelming the bottleneck nodes. It also considered a large scale WSNs whose nodes have knowledge of only nodes in their neighborhoods, so an efficient decentralized data aggregation routing is very important.

Data aggregation is a data processing way by which multiple input packets from neighbor nodes are aggregated into one output packet at a node (Krishnamachari et al., 2002). The selection of the node that performs aggregation so as to minimize the number of transmissions per unit data has been proved to be equivalent to the minimum Steiner tree problem. The aggregation tree problem is NP-Hard (Cristescu et al., 2004). The problem of designing energy-efficient routing algorithms to maximize network lifetime has been extensively studied in general multi-hop wireless networks (Kalpakis et al., 2003; Shan et al., 2011; Guo et al., 2010; Wei et al., 2010; Zeydan et al., 2010). Utility-based algorithm (Xue et al., 2010) have been proposed, but the authors don’t take into account data aggregation at the intermediate nodes. There are many works using data aggregation trees to collect data from the network (Wu et al., 2008; Luo et al., 2011). Other works formulate the data aggregation routing into the optimization problem subject to the trees (Hua and Yum, 2008; Liu et al., 2010).

This study, proposed an efficient network lifetime maximizing routing strategy with data aggregation. It exploited the potential for collaboration among sensors in data gathering and processing. The proposed routing algorithm also combines data aggregation and interference avoidance to maximize network lifetime. This study presented a linear optimization formulation of the network lifetime maximization problem that account for interference and data correlation. The distributed implementation is presented based on the dual decomposition, where the relay selection and transmission rate allocation are performed by the nodes distributively. Numerical studies are used to evaluate the performance of these different routing strategies.

PRELIMINARIES

We consider a WSN consisting of N nodes, given a graph G = (V, E) representing the WSN and a base station (sink node) sεV, to be responsible for collecting data from all other nodes. Two nodes that are within the transmission range of each other can communicate directly and form a wireless link. Let, L be the set of wireless links, denoted as lij = {(i, j)| a wireless link goes from i to j}. Define as a set of outgoing nodes set from node i, Nin(i) as a set of incoming nodes set to node i. Let dij be the Euclidean distance of node i and node j.

Considering the patio-temporal correlation characteristics of the physical medium, we use this data aggregation model (Hua and Yum, 2008). Each node performs two different operations for the data received from its neighbors. For the raw data from its incoming links, it encodes the data using the local information. For the aggregated data from its incoming links, it directly relays the data to the outgoing links. Let rij denotes the traffic generating rate over link l and tij denotes the aggregated transit traffic. The aggregated transit traffic tij consists of two parts: the transit traffic passed and the raw data originated from the neighbors that are compressed using the local information. One important constraint of traffic routing in a network is flow conservation. This constraint can be formally expressed as:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(1)

where, ρij = exp(-θd2ij) is the correlation coefficient that decreases exponentially with the distance between the nodes i and j and θ is the correlation parameter. eji is a routing variable over the link (j,i). If node i is a bottleneck node eji = 0, else eji = 1.

We consider synchronous direct sequence CDMA (DS-CDMA) where all nodes use a variable spreading sequences L:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(2)

where, hij = 1/d2ij is the link gain, σ2 is the thermal noise, γ is a certain target SIR. Pij denotes the transmit power from node i to node j. The transmission rate between the nodes i and j in bits-per-second (b sec-1) is determined by the spreading rate vij = W/Lij, where W is the system bandwidth. Clearly, the flow conservation law requires:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(3)

For power used for receiving and transmitting, we adopt the first-order radio model (Chandrakasan and Balakrishnan, 2000). Specifically, a node needs to run the circuitry for the transmitting amplifier. Let prij (joules per/bit) be the power consumption over the link , when it receives one unit of data and ptij (J/bit) be the power consumption when one unit of data is sent over the link (i,j). We have:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(4)

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(5)

where, εelec is a distance-independent constant that represents the energy consumption to run the transmitter or receiver circuitry and εamp is the coefficient of the distance-dependent term that represents the transmit amplifier. α is the path loss exponent which is usually between 2 and 4 for free-space and short-to-medium-range radio communication.

The routing variables eij and the node flow set tij jointly determine the traffic sent along a wireless link (i,j). Further, tij and the input traffic rij jointly determine the traffic received at node i. Thus, we have the wireless node i’s power consumption rate pi in joules per second as:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(6)

Let Ti denote the lifetime index of wireless node i and T as the lifetime of the wireless network at which the first node in the network runs out of energy, that is:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(7)

PROBLEM FORMULATION AND DUAL DECOMPOSITION

Here, we first give the problem formulation and then derive the optimal transmission rate allocation and relay selection solution. Then, the distributed implementation is given by the dual decomposition.

Transmission rate allocation and relay selection: The joint design problem is equivalent to selecting the optimal transmission rate allocation {tij} and relay selection {eij} such that the network lifetime can be maximized while {tij} and {eij} should subject to the total relay rate constraints in Eq. 3 and the individual power constraints in Eq. 6. This is cast into the following problem:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(8)

In the context of maximum lifetime routing, if we regard lifetime of a node as a certain “resource” of its own, then the goal of maximizing network lifetime can be regarded as to “allocate lifetime” to each node so that the max-min fairness criterion is satisfied. This “lifetime allocation” mechanism needs to be achieved via routing and has to satisfy the traffic input, flow conservation and power consumption constraints.

We further adopt the concept of “utility” that has been widely used in the area of resource allocation. It is shown by Kelly (1997) and Srikant (2004) that by defining an appropriate utility function, the problem of achieving max-min problem can be converted into the problem of maximizing the sum of utilities of all nodes. Thus, we define the utility Ui of a node i as a function of its lifetime Ti as:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(9)

where Ti = Ei/pi, Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor NetworksImage for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks It is shown that Ti, iεN satisfies the max-min fair if and only if it solves the aggregated utility maximization problem Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks with Ui defined as in Eq. 8.

We reformulate the problem of maximum network lifetime as to maximize the aggregated utility of all nodes within the network:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(10)

The partial corresponding Lagrangian function is:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(11)

where:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(12)

where, λij is the Lagrangian multiplier for the transmission rate conservation constraint at each node i. This results in the Lagrangian (10) can be transformed into an optimization problem (13) as follows:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(13)

We denote g(λ) = maxt,e L(t,e,λ) and the dual problem can be expressed as:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(14)

The dual problem Eq. 14 can be decomposed into three subproblems:

Subproblem 1: Aggregated transmission rate allocation: Given the multipliers λij, for any t and any iε{1,…N}, the optimal transmission rate tij is obtained by minimizing l. Let t*ij and denote the optimized variables, there is:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(15)

And:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(16)

Here, Eq. 14 indicates that the optimal rate allocation should be larger than zero and smaller than the maximal individual spreading rate which can be obtained from Eq. 3

Subproblem 2: Relay selection: Given the optimized l* (eijij) where tijεt, the optimal relay selected by each node is obtained as follows:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(17)

And:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(18)

Subproblem 3: Multiplier update: Find the optimal multipliers λij such that the dual function g(.) is minimized, thus:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(19)

We adopt the sub-gradient algorithm to obtain the optimal multipliers λ*ij. Let denotes the sub-gradient of the dual function g(λ) in Eq. 13, that is:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(20)

The iterative sub-gradient search is given by:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(21)

where, t is the iteration number and δ(t) is a sequence of scalar step sizes. λ(t) is the vector of Lagrangian multipliers during the tth iteration. [.]+ is defined as [.]+ = max(.,0). The iterative algorithm is terminated when |g(λ(t+1))-g(λ(t))|≤ε, where ε is a positive number which is close to zero. The sub-gradient update is guaranteed to converge to the optimal multipliers λ*ij as long as δ(t) is chosen to be sufficiently small. According to (Bertsekas and Tsitsiklis, 1997), the step size δ(t) should satisfy the following conditions:

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
(22)

Note that the optimization problem in Eq. 8 includes both the real and combinatorial variables and hence, the optimization is not convex. Since the duality gap p*-d* is not zero for general system utilities, we could not obtain the optimal solution of the original problem by solving the dual problem. According to Wang et al. (2009), when the number of nodes is large enough, the optimization problem in Eq. 8 satisfying the “time-sharing condition” and the duality gap for the distributed algorithm is nearly zero for general utilities.

Distributed algorithm based on decomposition: Here, we will give a distributed implementation on the aggregated rate allocation and relay selection solution using primal-dual decomposition. In the previous section, the dual problem Eq. 14 is decomposed into three subproblems, where the subproblem 1 and 2 can be performed at each transmission node and the subproblem 3 should be solved at the relays. Hence, we have the following distributed algorithm.

Algorithm 1: Distributed algorithm
Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks

Note that the distributive algorithm offers a few advantages from implementation perspective. Firstly, it offers flexibility as the relays do not need to know about the information of each other. Hence, when new nodes join or quit the networks, the rate allocation and relay selection operation is completely autonomous. Secondly, since the load of the computation can be shared by the nodes distributively, the complexity order of the distributed algorithm can be reduced to O(N2) instead of O(NN) in the centralized solution. Finally, the distributed algorithm has a good economic meaning that is the Lagrangian multiplier λij can be regarded as the price for the unit rate. The relays choose the price and sell the rate to the transmission nodes while transmission nodes select the relay and the relay rate according to the rate price chosen by the relay.

SIMULATION RESULTS

We evaluated the performance of our algorithm via simulation in this section. The number of sensor nodes in the network is varied between N = 20-N = 80 which is uniformly distributed over a square area of dimension 100x100 m2. The maximum transmission range of each node is 20 m. In our simulation, for the power consumption model, we set εelec = 50 nJ/b, εamp = 100 pJ/b/m4 and α = 2. The initial energy reserve on each node is 1 kJ. For data correlation setting, the correlation parameter θ is varied from θ = 0.01 m-2 (high correlation) to θ = 0.01 m-2 (low correlation) in the experiments. The data generating rate on all nodes is 1 kb sec-1. The noise power is σ2 = 10-13 Watts which corresponds to thermal noise power for a bandwidth of W = 1 MHz. The target SIR is selected to be γ = 5 (7 dB).

We compared the performance of our algorithm (MLAR) with the Minimum Energy Routing (MER) algorithm and the Maximum Lifetime Routing (MLR). The target of MER is to minimize the energy consumption for each data unit routed through the network. For each data source, the algorithm finds its shortest path to the data sink in terms of energy cost. The route for each data source is fixed throughout the entire network lifetime.

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
Fig. 1: Network lifetime. MLAR: Maximum lifetime aggregation routing; MER: Minimum energy routing; MLR: Maximum lifetime routing

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
Fig. 2: Network lifetime vs. correlation parameter

The objective of MLR is to maximize the network lifetime by jointly optimizing data aggregation and routing. The algorithm adopts a model to integrate data aggregation with the underlying routing scheme and present a smoothing approximation function for the optimization problem.

Figure 1 shows the lifetime of the same network when the data is routed by different algorithm under two data correlation settings (θ = 0.001 m-2 and θ = 0.01 m-2). From this figure, we first see that the results of the MLAR algorithm are optimal. This demonstrates that the utility function is a good approximation to the original objective function.

We also see from the Fig. 1 the network lifetime obtained by MLAR algorithm is around 1.5 times that given by MLR algorithm and 3.5 times that given by MER algorithm with θ = 0.001 m-2; For θ = 0.01 m-2, the network lifetime of MLAR algorithm is around twice and three times of those given by both MLR and MER algorithms, respectively for the network size of 80 nodes. In particular, the network lifetime returned by MLAR and MLR algorithms increase gradually when the network size grows while those of MER algorithms decrease continuously. The reason is that the overall source data rate is proportional to the number of nodes in the network. Therefore, it is reasonable that the network lifetime should decrease with the increase of network size as more traffic is generated. However, the increase of nodes in the network also drives the network topology from sparse to dense which has two effects. First, the distance between neighboring nodes becomes smaller, so a node needs less power to send data to its neighbors. Second, the data correlation between neighboring nodes becomes higher, so more redundant information can be removed with data aggregation. Both effects help reduce the energy consumption. However, MER algorithms fail to take advantage of this feature and the network lifetime returned by both algorithms drops continuously as the network size grows. MLAR and MLR algorithms can optimize both routing and data aggregation. Therefore, it performs much better than MER algorithms. The performance returned by MLAR outperforms MLR algorithm. The reason is that MLAR algorithm balances energy consumption of each node by iteratively adjusting traffic on different routing paths. The traffic is adjusted until a node is a bottleneck node in MLR algorithm, so that the network lifetime should decrease with the increase of bottleneck nodes.

In Fig. 2, we show the average network lifetimes given by MLAR, MLR and MER algorithms as the correlation parameter increases from 0.001-0.01.We can see that MER algorithm achieves better network lifetime for the smaller network size (40 nodes) than the larger network size (80 nodes) under all correlation situations. For the same network size, the performance of MLAR, MLR and MER algorithms decrease as the data correlation becomes smaller.

The convergence of the Lagrangian multiplier is shown in Fig. 3 which indicates the convergence of the iteration algorithm for various network sizes (60 and 80 nodes). We can see that MLAR algorithm requires small number of iterations to converge to over 88 and 85%, respectively for network size 60 and 80 nodes.

Image for - An Energy-efficient Data Aggregation Routing Algorithm in Wireless Sensor Networks
Fig. 3: Convergence of iteration algorithm

CONCLUSIONS

Data aggregation could eliminate redundant data flows so as to reduce the total energy consumption in wireless sensor networks. In this paper, we model the data aggregation routing problem as an optimization problem, where the objective function is to maximize the lifetime of the network. The proposed solution approach is based on Lagrangian relaxation for calculating an energy-efficient data aggregation routing. According to computational experiments, we have shown that the scheme can significantly reduce data traffic and improve the network lifetime. The distributed algorithm can converge efficiently. In the future, our work for multiple sink nodes and for nodes with sleeping mode would be of interest.

ACKNOWLEDGMENTS

This research has been supported by the National Natural Science Foundation of China under Grant No. 60874108, by the Fundamental Research Funds for the Central Universities under Grant No. N090423002 and by Directive Plan of Science Research from the Bureau of Education of Hebei Province, China, under Grant No. Z2009105 the Natural Science Foundation of Hebei Province under Grant No. F2011501021. We also thank the anonymous reviewers for their insightful and valuable hints.

REFERENCES

1:  Raghunathan, V., S. Ganeriwal and M. Srivastava, 2006. Emerging techniques for long lived wireless sensor networks. IEEE Commun. Mag., 44: 108-114.
CrossRef  |  Direct Link  |  

2:  Krishnamachari, B., D. Estrin and S. Wicker, 2002. The impact of data aggregation in wireless sensor networks. Proceedings of the 22nd International Conference on Distributed Computing Systems Workshops, July 2-5, 2002, Vienna, Austria, pp: 575-578
CrossRef  |  

3:  Cristescu, R., B. Beferull-Lozano and M. Vetterli, 2004. On network correlated data gathering. Proc. IEEE INFOCOM, 4: 2571-2582.
Direct Link  |  

4:  Kalpakis, K., K. Dasgupta and P. Namjoshi, 2003. Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks. Comput. Networks, 42: 697-716.
CrossRef  |  Direct Link  |  

5:  Shan, L., J. Wang, Y. Zhao and Y. Liu, 2011. Synchronous aggregation scheduling with minimal latency in multihop sensornet. Inf. Technol. J., 10: 1626-1631.
CrossRef  |  

6:  Guo, L., B. Wang, Z. Liu and W. Wang, 2010. An energy equilibrium routing algorithm based on cluster-head prediction for wireless sensor networks. Inform. Technol. J., 9: 1403-1408.
CrossRef  |  Direct Link  |  

7:  Wei, W., B. Zhou, A. Gao and Y. Mei, 2010. A new approximation to information fields in sensor nets. Inform. Technol. J., 9: 1415-1420.
CrossRef  |  Direct Link  |  

8:  Zeydan, E., D.K. Tureli, C. Comaniciu and U. Tureli, 2010. Bottleneck throughput maximization for correlated data routing: A game theoretic approach. Proceedings of the 44th Annual Conference on Information Sciences and Systems, March 17-19, 2010, Princeton, NJ., USA., pp: 1-6
CrossRef  |  

9:  Xue, Y., Y. Cui and K. Nahrstedt, 2010. A utility-based distributed maximum lifetime routing algorithm for wireless networks. Proceedings of the 2nd International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks, August 24-24, 2005, Lake Vista, FL., USA., pp: 10-18
CrossRef  |  

10:  Wu, Y., S. Fahmy and N.B. Shroff, 2008. On the construction of a maximum-lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm. Proceedings of the IEEE 27th Conference on Computer Communications, April 13-18, 2008, Phoenix, AZ., USA., pp: 356-360
CrossRef  |  

11:  Luo, D., X. Zhu, X. Wu and G. Chen, 2011. Maximizing lifetime for the shortest path aggregation tree in wireless sensor networks. Proceedings of the IEEE INFOCOM Conference, April 10-15, 2011, Shanghai, China, pp: 1566-1574
CrossRef  |  

12:  Hua, C. and T.S.P. Yum, 2008. Optimal routing and data aggregation for maximizing lifetime of wireless sensor networks. IEEE/ACM Trans. Networking, 16: 892-903.
CrossRef  |  Direct Link  |  

13:  Liu, F., C.Y. Tsui and Y.J. Zhang, 2010. Joint routing and sleep scheduling for lifetime maximization of wireless sensor networks. IEEE Trans. Wireless Commun., 9: 2258-2267.
CrossRef  |  Direct Link  |  

14:  Heinzelman, W.R., A. Chandrakasan and H. Balakrishnan, 2000. Energy-efficient communication protocol for wireless microsensor networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, January 4-7, 2000, Maui, HI., USA., pp: 1-10
CrossRef  |  Direct Link  |  

15:  Kelly, F., 1997. Charging and rate control for elastic traffic. Eur. Trans. Telecommun., 8: 33-37.
CrossRef  |  Direct Link  |  

16:  Srikant, R., 2004. The Mathematics of Internet Congestion Control. Birkhauser Publisher, Boston, MA., USA., ISBN: 9780817632274, Pages: 164

17:  Bertsekas, D.P. and J.N. Tsitsiklis, 1997. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, USA., ISBN: 9781886529014, Pages: 715

18:  Wang, R., V.K.N. Lau, L. Lv and B. Chen, 2009. Joint cross-layer scheduling and spectrum sensing for OFDMA cognitive radio systems. Wireless Commun., 8: 2410-2416.
CrossRef  |  

©  2022 Science Alert. All Rights Reserved