• [email protected]
  • +971 507 888 742
Submit Manuscript
SciAlert
  • Home
  • Journals
  • Information
    • For Authors
    • For Referees
    • For Librarian
    • For Societies
  • Contact
  1. Information Technology Journal
  2. Vol 12 (4), 2013
  3. 656-663
  • Issues
    Online First Current Issue All Issues
  • Information About
    Aims and Scope Editorial Board Guide to Authors Article Processing Charges
    Submit a Manuscript

Information Technology Journal

Year: 2013 | Volume: 12 | Issue: 4 | Page No.: 656-663
DOI: 10.3923/itj.2013.656.663
crossmark

Facebook Twitter Reddit Linkedin E-mail
Research Article

Lifetime Maximization Algorithm for Chain Wireless Sensor Networks

Yourong Chen
College of Information Science and Technology, Zhejiang Shuren University, Hangzhou, 310015, China
LiveDNA: 86.4886

Tiaojuan Ren
College of Information Science and Technology, Zhejiang Shuren University, Hangzhou, 310015, China

Yaolin Liu
College of Information Science and Technology, Zhejiang Shuren University, Hangzhou, 310015, China

Ying Zhou
College of Information Science and Technology, Zhejiang Shuren University, Hangzhou, 310015, China

ABSTRACT


Many routing algorithms for chain wireless sensor networks were lack of theoretical analysis. It was difficult to judge whether these algorithms maximally prolonged network lifetime. In order to solve the problem, lifetime maximization algorithm for chain wireless sensor networks (LMA_CWSN) was proposed. The optimization method was used to research on the network lifetime maximization problem. Network optimization model was established. Non-negative slack variables and logarithmic barrier function were introduced. Newton method was used to solve the model. Finally, optimal value of network lifetime and optimal routing scheme were obtained. Simulation results show that LMA_CWSN makes full use of nodes’ energy to improve network lifetime, converges to the optimal value of network lifetime and optimal routing scheme after iteration calculation and outperforms LEACH (low-energy adaptive clustering hierarchy), PEGASIS (power-efficient gathering in sensor information systems) and Ratio_w (ratio weight routing algorithm). Under certain conditions, LMA_CWSN can guide the data routing for chain wireless sensor networks, try to meet the optimal scheme when node transmission path and data amount are selected and provide reference to assess the performance of other routing algorithms.
PDF Abstract XML References Citation

Keywords


  • optimization method
  • network lifetime
  • Newton algorithm
  • Chain wireless sensor networks

Article History

Received: October 12, 2012;   Accepted: November 29, 2012;   Published: January 22, 2013

How to cite this article

Yourong Chen, Tiaojuan Ren, Yaolin Liu and Ying Zhou, 2013. Lifetime Maximization Algorithm for Chain Wireless Sensor Networks. Information Technology Journal, 12: 656-663.

DOI: 10.3923/itj.2013.656.663

URL: https://scialert.net/abstract/?doi=itj.2013.656.663

INTRODUCTION


Tiny sensor technologies and inter-node wireless communication capabilities give the wide application prospect for Wireless Sensor Networks (WSNs). At present, most applications of WSNs are divided into two categories: monitoring and tracking. Monitoring includes indoor and outdoor environmental monitoring, health monitoring, power monitoring, inventory position monitoring, factory automation monitoring, earthquake and structural monitoring. Tracking includes animal, human, vehicle and other targets tracking. In short, WSNs have been applied to many fields such as environmental and weather monitoring, floods warning, farm management, smart home and intelligent transportation. It presents tremendous commercial value and application potential, brings far reaching impact to the field of human production and life and is taken more and more attention by industry and academia (Yick et al., 2008).

Currently, the research on WSNs routing algorithm have achieved some results. Lindsey et al. (2002) proposes a chain routing algorithm (PEGASIS). All nodes in the monitoring region self-organize into a link by greedy algorithm. In data dissemination phase, each node receives the information from nearest upstream neighbor node. Then it transmits the fused information to sink node through nearest downstream neighbor node. The algorithm assumes that all nodes can communicate with sink node. It is obviously not feasible in the actual network. The nodes which are far away sink node cause excessive data latency. Heinzelman et al. (2000) proposes Low-energy Adaptive Clustering Hierarchy (LEACH). LEACH includes three-tier network architecture such as sink node, cluster-head node and sensor node. In the algorithm, sensor nodes transmit the sensed data to cluster-head nodes. Cluster-head nodes fuse the data of sensor nodes and transmit them to sink node by multi-hop among cluster-head nodes. In large-scale WSNs or node energy imbalance WSNs, LEACH algorithm randomly selects cluster-head nodes which may be concentrated in special region and can not cover the entire monitoring region. It easily leads to split network and increase node energy consumption. Zhu et al. (2009) proposes ratio weight routing algorithm (Ratio_w) and sum weight routing algorithm (Sum_w). The algorithms consider energy consumption of link communication, node residual energy, energy consumption factor and residual energy factor to construct a new weight function. Dijkstra algorithm is used to construct the shortest path tree whose root is sink node. All nodes transmit the data to sink node along the shortest path tree. Shin and Sun (2011) proposes Chain Routing With Even Energy Consumption (CREEC). CREEC improves the network lifetime by two strategies: Firstly, energy distribution of each node is balanced as far as possible. Secondly, the node energy consumption is preliminarily simulated and the feedback mechanism is used to save node energy. Chen et al. (2009) and Chen and Lin (2012) divide the sensing region of WSNs into a number of smaller regions. The nodes construct a link in each smaller region. All nodes in the network self-organize into chains. The above references research on the WSNs routing protocol to improve network lifetime and reduce node energy consumption. They focus on transmission path selection of network packet. But the algorithms are lack of theoretical analysis. It is difficult to determine whether these algorithms have maximum network lifetime. Wang et al. (2008) breaks multi-sink node routing problem into a number of single-sink node routing problem. It considers constraints with four core parameters such as transmission flow, node energy, signal-to-noise ratio and transmission bandwidth. It establishes the network lifetime optimization model and uses the KKT method to obtain the optimal solution. The algorithm is fit for small WSNs. With the expansion of network, the algorithm needs to consider too many factors and equality constraints. The solution process is complexity.

Some routing algorithms such as PEGASIS, LEACH and Ratio_w for CWSNs are lack of theoretical analysis. It is difficult to judge whether these algorithms maximally prolonged network lifetime. In order to solve the problem, lifetime maximization algorithm for chain wireless sensor networks (LMA_CWSN) is proposed. The LMA_CWSN can obtain the optimal value of network lifetime and optimal routing solution. It can guide the data routing for CWSNs, try to meet the optimal scheme when node transmission path and data amount are selected and provide reference to assess the performance of other routing algorithms.

NETWORK OPTIMIZATION MODEL

WSNs are widely applied to CWSNs, such as unattended dangerous status monitoring of freight train, status monitoring of single street lamp, online monitoring of transmission line, factory automation monitoring. As shown in Fig. 1, the sensor nodes sense and gather the information in the monitoring region with various types of sensors, transmit the sensed information to sink node through CWSNs. The routing of CWSNs has many problems. If traditional stepwise multi-hop routing protocol is used, the routing path will be single and nodes which are near the sink node will frequently forward the information of other nodes. It leads to high node energy consumption and premature failure and reduces the network lifetime.

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
Fig. 1: Chain wireless sensor networks

Table 1: Notations
Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks

If each node directly transmits the information to sink node, the nodes which are farther away sink node will consume more energy and fail prematurely. Finding a CWSNs routing scheme to maximize network lifetime is great significance. Therefore LMA_CWSN is proposed in the following. The notations in the article are in Table 1.

System assumptions: Considering the application scenario of CWSNs, it is assumed that CWSNs have following characteristics:

• The positions of sink node and sensor nodes are fixed. All sensor nodes are uniformly distributed on each link. Sink node is distributed on one end of the link
• Because the deployment positions of nodes are pre-planned, sink node and sensor nodes can obtain the entire network topology information
• All sensor nodes have the same performance (such as radio maximum transmission power, maximum communication radius, distance between adjacent nodes, node energy consumption model et al.
• All sensor nodes in the network need to sense and transmit data. They take on data gather and relay tasks and transmit date to sink node by direct or multi-hop mode
• Energy of each sensor node is limited. But energy of sink node is unlimited

Optimization model establishment: As shown in Table 1, if node j is in the communication range of node i, node j is the neighbor node of node i. According to the definition of symbols, the equations N(i) = {j|dij<dmax, jεV}, U(i) = {k|dkB≥diB, N(i)} and X(i) = {k|dkB<diB, N(i)} are obtained. According to the characteristics of CWSNs, node i receives the data from upstream neighbor nodes and transmits data to sink node through downstream neighbor node (Hua and Yum, 2008).

According to the definition of network lifetime, the network lifetime maximization problem is transformed into the following optimization model. The goal of network optimization model 1 is to maximize network lifetime T and obtain optimal value Fij.

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(1)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(2)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(3)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(4)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(5)

where, Eq. 2 follows from flow balance constraint. The transmission data amount of node i consists of the received data amount from upstream neighbor nodes and its sensed data amount. Equation 3 follows from maximum data transmission constraint. Node data transmission bandwidth is limited and the total transmission data amount is also limited. Equation 4 follows from energy constraint. In the network lifetime, for node i the energy consumption of received data is ΣjεU(i)FjiEelec, the energy consumption of transmission data is ΣjεX(i)Fij (Eelec+εfsdγij).

Solution of optimization model: The non-negative slack variables yi and zi, ∀iεV are introduced. The formulas Eq. 4 and 5 are transformed into equation constraints:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(6)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(7)

The objective function of optimization model 1 is not concave function. The optimal value obtained by the Newton method may be not the global maximum value. Equation 1 can be transformed into min(-logT). Its optimization model is transformed into:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(8)

s.t.: constraints of Eq. 2, 5, 6 and 7:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(9)

Let:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(10)

where, θ≥1, ξ is much larger than θ.

The optimization model is modified, i.e.:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(11)

where, x = [T{Fij} y1…y|v| z1…z|v|]T, c = [0 0 H]T, H = [E1, E2, …, E|v|]:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(12)

The node can communicate with n = dmax/din nodes. Vector x has (n+2)|V|-(n2-n)/2+1 elements. Matrix A has 3|V|*((n+2)|V|-(n2-n)/2+1) elements. According to formula 12, some elements of A are defined as follows:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(13)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(14)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(15)

Newton method is used to solve the constrained optimization model 11. An initial solution vector x0 is determined in any feasible domain. The update iteration formula of Newton method is:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(16)

Δxk is obtained based on the following linear Eq. 17:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(17)

Let Hk = ∇2f(xk). According to Eq. 17, the solution of Δxk can be divided into the following two formulas:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(18)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(19)

where, f(xk) is secondary derivable for xk. Hk-1 is the positive diagonal matrix.

The Newton step sk is:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(20)

where, Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks. The sk guarantees that each element of xk+1 is non-negative (Ren et al., 2012). The following is convergence analysis of LMA_CWSN when sk is determined by formula 20.

Convergence analysis: To analyze the convergence of LMA_CWSN, the definition of self-concordant function is introduced.

Definition 1: (Wei et al., 2010): A convex function g:R→R, ∀xεR. If the inequality Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks holds, the function g is self-concordant function.

Lemma 1: (Wei et al., 2010): A convex function g:Rn→R, ∀x, vεRn if function Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks(t) = g(x+tv) is self-concordant function, the function g is also self-concordant function.

Let function:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(21)

where, Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks and Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks(sk), respectively denote f(xk) and f(xk+1):

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(22)

Theorem 1: The function Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks in formula 21 is self-concordant function. The function f(x) in formula 10 is also self-concordant function.

Proof: Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks(s) is convex function. The second and third derivatives of Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks(s) are:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(23)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(24)

Because ξ, θ, T. Fij, yi, zi are non-negative and ξ≥θ≥1, we have:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(25)

According to Definition 1, Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks(s) is self-concordant function. According to Lemma 2, f(x) is also self-concordant function. Therefore, the Theorem 1 is proved. According to the above definition and theorem, the convergence of optimization model (11) is analyzed in attenuation convergence phase (λ(xk)>0.25) and quadratic convergence phase (λ(xk)≤0.25).

Attenuation convergence phase: Attenuation convergence phase researches on the changes of objective function value in each iteration when (λ(xk)>0.25) . First Lemma 2 is given.

Lemma 2: (Wei et al., 2010): g:R→R is self-concordant function, ∀sεR and s≥0. If sg″(0)1/2<1 holds, the following inequality holds:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(26)

Theorem 2: If Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks holds, the following inequality of function f(x) in formula (10) holds:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(27)

Proof: According to Eq. 21, we have:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(28)

Equation 28 multiplies (Δxk)T on both sides, i.e.:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(29)

AΔxk = 0, then:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(30)

The first and second derivatives of function Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks(s) are obtained according to Eq. 30, i.e.:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(31)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(32)

According to Lemma 2, 0≤s≤1/(λ(xk)+1), we have:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(33)

According to Eq. 20 and 21, we have:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(34)

is Taylor expanded, i.e.:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(35)

According to Eq. 34 and 35, we have:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(36)

When λ(xk)>0.25, -λ(xk)2/2(1+λ(xk)) is monotonically decreasing function of λ(xk). When λ(xk) infinitely tends to 0.25, it has maximum value, i.e., the inequality Eq. 27 is obtained. Therefore, the Theorem 2 is proved.

In summary, according to the Theorem 2, in attenuation convergence phase, the objective function value drops by at least 0.025 than the previous iteration value. After iteration calculation, the objective function value tends to be minimum value. At that time it enters quadratic convergence phase from attenuation convergence phase.

Quadratic convergence phase: Quadratic convergence phase researches on the changes of objective function value in each iteration when λ(xk)≤0.25. The Lemma 3-5 is given.

Lemma 3: (Wei et al., 2010): g:Rn→R is self-concordant function. If Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks, ∀x, yεRn holds, the following inequality holds:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(37)

where, τεRn.

Lemma 4: (Wei et al., 2010): g:Rn→R is self-concordant function, Δxk is Newton increment. If Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks holds, the following inequality holds:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(38)

Lemma 5: (Wei et al., 2010): g:Rn→R is self-concordant function, Δxk is Newton increment, g* is the minimum value of objective function. If Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks holds, the following inequality holds:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(39)

According to Lemma 3-5, the Theorem 3 can be deduced.

Theorem 3: f* is the minimum value of function f(x) in Eq. 10. If Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks holds, the following inequality holds:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(40)

Proof: According to Eq. 24 and Lemma 3-4, we have:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(41)

Equation 41 is simplified with λ(xk+1)≥0, i.e.:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(42)

When λ(xk)≤0.25, Eq. 42 is simplified:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(43)

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(44)

where, m is a positive integer. According to Lemma 5, we have:

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
(45)

Then, the Eq. 40 is obtained. In quadratic convergence phase (λ(xk)≤0.25), after iteration calculation, the objective function value converges to the minimum. Therefore, the Theorem 3 is proved.

From the above content, Newton method is used to solve the network optimization model 1 and obtain the optimal value of network lifetime.

Algorithm implementation: LMA_CWSN is a centralized algorithm. After it obtains the node information and executes the following steps to calculate the optimal value of network lifetime:

Step 1: T0, F0ij, y0i, z0i and other parameters are initialized. The feasible initial value of strict positive vector x0 is determined
Step 2: According to xk, ∇f(xk), Hk-1, ωk and Δxk are calculated
Step 3: If k<M, go to step 4, else go to step 5
Step 4: According to Eq. 20, xk+1 is updated, k = k+1, go to step 2
Step 5: The optimal value of network lifetime and the corresponding values Fij are obtained. LMA_CWSN is end

Pseudo code of LMA_CWSN is as follows:
Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks

Time complexity of LMA_CWSN is time complexity of Newton method which iteratively executes M times. Time complexity of Newton method relates to the matrix multiplication in Eq. 22 and 23. Because time complexity of Aa,n×An,b is Θ(anb), its time complexity is Θ(|V|3). Finally, time complexity of LMA_CWSN is Θ(M|V|3). In short, the time complexity of LMA_CWSN is high. Its convergence needs certain time. Only when the energy consumption of data transmission is far greater than the energy consumption of optimal solution calculation, LMA_CWSN can work well.

SIMULATION AND ANALYSIS

Simulation parameters: In the simulation, the energy consumption of wireless data communication is only considered. The energy consumption of calculation, data fusion and query packet transceiver are not considered. The energy consumption of timeout retransmission and debug in the data transmission process are also not considered. In the network simulation region, the ordinates of all nodes are the same and the abscissa interval between adjacent nodes is 20 m. The simulation parameters in Table 2 are selected to iteratively calculate the network lifetime and the transmission data amount of nodes.

Simulation results analysis: In the simulation, the number of nodes is 10 and the related parameters in Table 2 are selected. The node distribution is shown in Fig. 2. The five-pointed star represents sensor node. The square represents sink node. All nodes arrange in the row, transmit the data to sink node with forwarding nodes and form the chain wireless network. The node IDs from left to right are 1-10. Then the LMA_CWSN is used to research on its performance. The network lifetime and transmission data amount of nodes are iteratively calculated 2000 times according to the algorithm implementation. Then, Fig. 3 and Table 2 are obtained.

The network lifetime of each iteration is obtained and normalized. As shown in Fig. 3, when the iteration number increases, the network lifetime increases. When the number of iteration is lower than 1000, the curve of network lifetime is quadratic change. When the number of iteration is larger than 1000, network lifetime essentially converges to the optimal value.

Table 2: Simulation parameters
Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
Fig. 2: Node distribution when |V| = 10

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
Fig. 3: Convergence of network lifetime

Table 3: Transmission data amount among nodes
Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
The order of magnitude of transmission data amount is 108 bit, 1-9: Sensor nodes, 10: Sink node

Therefore, according to the analysis of theory and simulation, LMA_CWSN is convergence and has quadratic convergence rate.

Table 3 shows the routing scheme which can obtain optimal network lifetime. As shown in Table 3, each node transmits data to downstream neighbor nodes. When the nodes can not communicate directly with sink node (such as nodes 1-5), they tend to select the farthest downstream neighbor nodes. For example, node 1 is far away from sink node. To transmit the data to sink node, it tends to select the forwarding nodes 5 which is its neighbor node and is the nearest to sink node. It can reduce the energy consumption. When the nodes can directly communicate with sink node and there are several downstream neighbor nodes between them (such as nodes 6-7), to balance network lifetime and energy consumption, they also tend to select the downstream neighbor nodes. When the nodes are close to sink node (such as nodes 8-9), to save energy consumption of commutation, they directly transmit data to sink node in single hop.

In order to reflect the effectiveness of LMA_CWSN, LEACH (the probability which sensor node is selected to be cluster-head node is 0.25), PEGASIS, Ratio_w and LMA_CWSN are compared. The 10, 20, 30, 40, 50, 60 numbers of nodes (includes a sink node and other sensor nodes) are respectively selected.

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
Fig. 4: Total energy consumption of each nodes when |V| = 10

The related parameters in Table 2 are selected to calculate the network lifetime and total node energy consumption.

As |V| = 10 for example, the total energy consumption of each node is shown in Fig. 4 when the first node runs out of energy. The node energy consumption of LMA_CWSN distributes uniformly. Each node consumes about 1000 J and all nodes are almost simultaneous failure. The node energy consumption of Ratio_w and PEGASIS relates to the distance between itself and sink node. The nodes which are closer to sink node consumes more energy. And vice versa the energy consumption is lower. The node energy consumption of LEACH distributes unevenly. Node 5 and 9 consume more energy. Others consume lower energy. It is the reason that LMA_CWSN can find the optimal network lifetime and routing scheme and nodes make full use of its energy to improve network lifetime. In Ratio_w, nodes select the neighbor node with smallest link weight to transmit data. In PEGASIS, nodes select the nearest downstream neighbor node to transmit data. LEACH randomly selects cluster-head nodes to establish cluster. The three algorithms all focus on transmission path selection of network packet and propose various data routing schemes. But these schemes are not the optimal routing scheme. When the network is failure, some nodes still have much energy.

In the simulation of LEACH, PEGASIS, Ratio_w and LMA_CWSN, in order to facilitate the comparison, network lifetime is defined by the number of Data Gathering Cycle (DGC) from the time at which network starts to the time at which the first node runs out of energy. Where, a DGC represents the time all nodes sense 100 kbit data and transmit them to sink node. As shown in Fig. 5, the network lifetime of LMA_CWSN (the number of DGC) is larger than that of Ratio_w, PEGASIS and LEACH.

Image for - Lifetime Maximization Algorithm for Chain Wireless Sensor Networks
Fig. 5: Network lifetime comparison

It is optimal. The network lifetime of Ratio_w is second. The network lifetime of LEACH is the lowest. It is the reason that LMA_CWSN uses Newton method to maximize network lifetime and obtain optimal value. When the number of nodes increases, the difference in network lifetime between Ratio_w and LMA_CWSN is smaller. It is the reason that when the number of nodes increases, the transmission path selection of Ratio_w is reasonable and is relatively accordant with optimal routing scheme.

CONCLUSION


The network lifetime maximization algorithm for CWSNs is researched. Firstly, the lifetime maximization problem is transformed into network optimization model. Secondly, the Newton method is used to solve the optimization model. Nextly, the convergence of LMA_CWSN is theoretically analyzed, simulated and verified. The influence of node optimal routing scheme and the corresponding node energy consumption on network lifetime is simulated and analyzed. Finally, LEACH, PEGASIS, Ratio_w and LMA_CWSN are compared.

LMA_CWSN provides optimal value of network lifetime and optimal routing scheme, guides the data routing for CWSNs, tries to meet the optimal scheme when node transmission path and data amount are selected and provides reference to assess the performance of other routing algorithms. After further improvement, the algorithm can be applied to other types of WSNs. But the algorithm has large computation. Only when the energy consumption of data transmission is far greater than the energy consumption of optimal solution calculation, LMA_CWSN can work well.

ACKNOWLEDGMENTS


This project is supported by Zhejiang Provincial Natural Science Foundation of China under grant LQ12F03014, Zhejiang Provincial Public Service Technology Research and Industrial Project of China under grant 2012C21042 and a general project, Zhejiang Provincial Education Department of China under grant Y201225827.

REFERENCES


  1. Yick, J., B. Mukherjee and D. Ghosal, 2008. Wireless Sensor Network Survey. J. Comput. Network, 52: 2292-2330.
    CrossRefDirect Link

  2. Lindsey, S., C. Raghavendra and K.M. Sivalingam, 2002. Data gathering algorithms in sensor networks using energy metrics. IEEE Trans. Parallel Distrib. Syst., 13: 924-935.
    CrossRefDirect Link

  3. Heinzelman, W.R., A. Chandrakasan and H. Balakrishnan, 2000. Energy-efficient communication protocol for wireless micro sensor networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Volume 8, January 4-7, 2000, Maui, Hawaii, pp: 3005-3014.
    CrossRef

  4. Zhu, Y.H., D.D. Shen, W.D. Wu, Z.W. Shen and Y.P. Tang, 2009. Dynamic routing algorithms optimizing lifetime of wireless sensor networks. Acta Electron. Sinica, 37: 1041-1045.

  5. Shin, J. and C.J. Sun, 2011. CREEC: Chain routing with even energy consumption. J. Commun. Networks, 13: 17-25.

  6. Chen, K.H., J.M. Huang and C.C. Hsiao, 2009. CHIRON: An energy-efficient chain-based hierarchical routing protocol in wireless sensor networks. Proceedings of the Wireless Telecommunications Symposium, April 22-24, 2009, Prague, Czech Republic, pp: 1-5.
    CrossRef

  7. Chen, Y.L. and J.S. Lin, 2012. Energy efficiency analysis of a chain-based scheme via intra-grid for wireless sensor networks. Comput. Commun., 35: 507-516.
    CrossRef

  8. Wang, H., Y.H. Yang, M. Ma, J.H. He and X.M. Wang, 2008. Network lifetime maximization with cross-layer design in wireless sensor networks. IEEE Trans. Wireless Commun., 7: 3759-3768.
    CrossRef

  9. 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.
    CrossRefDirect Link

  10. Wei, E., A. Ozdaglar and A. Jadbabaie, 2010. A distributed Newton method for network utility maximization. Submitted to CDC 2010, LIDS Report, pp: 1-27.

  11. Ren, T.J., H.B. Yang and Y.R. Chen, 2012. Lifetime optimized algorithm with mobile sink node in wireless sensor networks. Chinese J. Sens. Actuat., 27: 683-690.

Leave a Comment


Your email address will not be published. Required fields are marked *

Useful Links

  • Journals
  • For Authors
  • For Referees
  • For Librarian
  • For Socities

Contact Us

Office Number 1128,
Tamani Arts Building,
Business Bay,
Deira, Dubai, UAE

Phone: +971 507 888 742
Email: [email protected]

About Science Alert

Science Alert is a technology platform and service provider for scholarly publishers, helping them to publish and distribute their content online. We provide a range of services, including hosting, design, and digital marketing, as well as analytics and other tools to help publishers understand their audience and optimize their content. Science Alert works with a wide variety of publishers, including academic societies, universities, and commercial publishers.

Follow Us
© Copyright Science Alert. All Rights Reserved