Abstract: To maximize the network lifetime, distributed network lifetime maximization with Newton method (DNLM-NM) in static wireless sensor networks was proposed. In the algorithm, the sensed constraint, transmission constraint and energy constraint were considered. The network lifetime maximization problem was formulated as optimization model. Nonnegative slack variables and logarithmic barrier functions were introduced. Then, the network optimization model was decomposed into node optimization models. Each node had its modified Newton optimization model with local information which received from neighbor nodes. Finally, initial solution vector and Newton step length were considered. The node executed the five steps to calculate its maximum lifetime with Newton method. Simulation results show that under different numbers of nodes and sensed rates, the DNLM_NM algorithm can find the optimal values and use multipath routing to maximize network lifetime. It is fit for the static wireless sensor networks.
INTRODUCTION
Wireless sensor networks (WSNs) are composed of many energy-constrained nodes which sense, compute and wireless communicate with each other. Recently, low-cost WSNs have been developed for many applications, such as surveillance, target tracking, environmental monitoring, farm management, smart home and others. It gets more and more attention from academia and industry (Akyildiz et al., 2002). The network lifetime which needs to be maximized is one of the non-standard metrics in WSNs. It is specifically indented for the networks whose nodes are mostly battery-powered and have limited energy. Once one node exhausts energy and is disabled, it may affect the network data gathering, even break up the network. Therefore, various algorithms of WSNs are required to reduce the energy consumption, maximize the network lifetime and save the huge cost of re-deployment (Xu and Cassandras, 2009).
At present, the researches on lifetime maximization problem have got some accomplishments. To maximize network lifetime, Xu and Cassandras (2009) researched on the optimal allocation of energy over all nodes, presented the kinetic battery model and solved the discrete time optimal control problem with optimization method. Fariborzi and Moghavvemi (2009) used graph theory and proposed a novel light-weight routing protocol, energy aware multi-tree routing (EAMTR) protocol. To balance the workload of data gathering, multiple trees were formed in the initialization phase and according to network traffic, each node selected the least congested route to the root node. Madan et al. (2006), Gatzianas and Georgiadis (2008) and He et al. (2009) researched on the lifetime maximization problem under different situations. Madan et al. (2006) assumed that all nodes were static. Gatzianas and Georgiadis (2008) researched on the problem when sink node was mobile. He et al. (2009) researched on the problem in wireless visual sensor network in which the encoding power consumption was considered. All the problems were formulated as linear programming models. Subgradient algorithm and dual decomposition were used to solve them in a distributed manner. But these methods suffered from slow convergent rate. The Newton methods for solving lifetime maximization problem were developed (Jadbabaie et al., 2009; Wei et al., 2010). Compared with subgradient algorithm, Newton method is second-order convergence and has faster convergent rate. Jadbabaie et al. (2009) presented the dual Newton direction as the solution of a discrete Poisson equation involving the graph Laplacian. Wei et al. (2010) used novel matrix splitting techniques, both primal and dual updated for the Newton step which could be computed using iterative schemes in a decentralized manner with limited information exchange. However, these Newton methods are complicated.
To simplify the computation and keep second-order convergent characteristic of Newton method for distributed solving the network lifetime maximization problem, this study proposed distributed network lifetime maximization with Newton method (DNLM_NM) in static wireless sensor networks. Each node has its modified Newton optimization model with local information which received from neighbor nodes. Through communication and calculation, all nodes use the local information and maximize its lifetime.
NETWORK OPTIMIZATION MODEL
In the research, assume that: sink node and other nodes are static with fixed location; Sensor nodes have the same performance (such as initial energy, energy consumption parameters, radio transmission power, communication radius); Sensor nodes have the same energy model; Sink node gathers data regularly and all sensor nodes sense and transmit data to sink node directly or in multi-hop way; Each sensor node’s energy is limited and sink node’s energy is not limited.
G(V, L) represents WSNs where V is a non-empty set of network nodes and L is a set of wireless links. G(V, L) is undirected connected graph. In WSNs, if node j lies in the communication range of node i, node j is the neighbor node of node i. Meanwhile, node i is the neighbor node of node j. Link (i,j) represents the link from node i to node j. N(i) is the neighbor nodes set of node i. |N(i)| is the number of neighbor nodes for node i.
Ti is the lifetime of node i. Si is the sensed rate. Fij is the transmission data amount from node i to node j in the whole network lifetime. F(i) is the transmission data amount in node i. It is composed of the sensed and received amount:
| (1) |
Because the bandwidth in the link (i,j) is limited, the total amount of transmission data is also limited. So the transmission constraint is as follow:
| (2) |
where, Rmax is the link maximum transmission rate.
In the network, transmission energy consumption ETx contains the electronic energy consumption of transmission circuit ETx-elec and energy consumption of signal amplifier ETx-amp. ETx-elec is fixed at kEelec, where k represents the transmission data amount, Eelec is constant and it represents the circuit electronic energy consumption when per-bit data is transmitted or received. ETx-amp relates to transmission distance d. Receiver only considers the electronic energy consumption kEelec. Therefore, the energy consumption of received data for node i is:
The energy consumption of transmission data for node i is:
where, ε is constant and it represents the electronic energy consumption when per-bit data is amplified, γ is the amplification factor. The total energy consumption of node i must be not larger than its initial energy Ei:
| (3) |
Therefore, according to the definition, network lifetime is:
| (4) |
The lifetime maximization problem is formulated as optimization model:
| (5) |
| (6) |
| (7) |
| (8) |
| (9) |
The optimization model is solved by Newton method to calculate the maximum network lifetime and transmission data amount Fij of all links.
DISTRIBUTED NETWORK LIFETIME MAXIMIZATION WITH NEWTON METHOD
As shown in Fig. 1a, if the network optimization model is solved directly with Newton method, because it is centralized algorithm and the sink node H needs to consider all the constraints of nodes such as A, B, C, D, E, F, G , its calculation amount is very large.
| Fig. 1: | Connected graph when H is sink node, (a) Network connected and (b) Node connected |
Therefore, the whole network is decomposed. Each node has its optimization model with local information. As shown in Fig. 1b, the node F communicates with its neighbor nodes such as C,D,E, obtains the received data amount FCF, FDF, FEF from neighbor nodes and has its optimization model. Newton method operates distributed in each node to calculate node maximum lifetime. Finally the network lifetime is defined as the minimum lifetime of nodes. The optimization model for node i is as follows:
| (10) |
s.t.: constraints of (6-9) for node i. |
The objective function Eq. 10 is not strictly concave for primal variables. Hence, the primal solution is not immediately available. Then it changes to min(-log Ti) which is strictly convex. The lifetime has maximum value. To use the Newton method, the inequation constraints are reformulated, by introducing nonnegative slack variables yij, ∀j ∈ N (I) and zi, such as:
| (11) |
| (12) |
Using the distributed method, each node monitors the information packets from neighbor nodes, calculates its lifetime with Newton method. The optimization model for node i is modified as follows:
| (13) |
s.t.: constraints of (6, 9, 11) and (12) for node
i |
And logarithmic barrier functions are used for nonnegative constraints. The new decision variable vector is:
| (14) |
The xi has 2|N(i)|+2 number of elements. The model can be rewritten as:
| (15) |
| |
where, θ is a nonnegative constant coefficient for the barrier functions. The matrix Ai and vectors ci are as follow:
| (16) |
| (17) |
The following vectors and matrices are defined.
Sensed constraint vector B1, |N(i)| for node i is:
| (18) |
Transmission constraint matrixes D|N(i)|, |N(i)| and G|N(i)|, |N(i)| are:
| (19) |
| (20) |
where, I|N(i)|, |N(i)| is unit matrix.
Node energy constraint vector J1, N(i) is:
| (21) |
The objective function for the optimization model is:
| (22) |
The Eq. 22 is separable, strictly convex, twice continuous
differentiable and has a positive diagonal Hessian matrix, so it is convex.
The model has minimum value and the network lifetime has maximum value. The
Newton method is used to find the optimal solution (Wei et
al., 2010). An initial solution vector
| (23) |
where,
| (24) |
where,
According to the Eq. 24, the solution of
| (25) |
| (26) |
where,
| (27) |
| (28) |
The Newton step length
If:
or
and
and
Realization and simulation
Feasible initialization: To initialize the
DNLM-NM algorithm, some feasible and strictly positive vector x0>0
is needed. For example, one possible scheme is given by:
| (29) |
| (30) |
| (31) |
| (32) |
Algorithm realization: When the network starts, nodes transmit the latest information packets to all neighbor nodes from time to time. The packet includes the information of node ID and transmission data amount Fji. Node receives the packets, acquires the distance to neighbor nodes and packet information and updates its information of neighbor nodes. The node executes the following steps to calculate its maximum lifetime.
| Step 1: | |
| Step 2: | According to the vector |
| Step 3: | If |
| Step 4: | The node informs neighbor nodes about the latest Fij. If the iteration number m<M, node waits and monitors the information of neighbor nodes Fji, else DNLM-NM algorithm is end. If Fji changes, m = m+1, go to step 2 and start calculation. |
| Step 5: |
| Fig. 2: | Simulation flow chart of DNLM_NM algorithm |
Simulation parameters and flow chart: In the simulation, the network lifetime is defined as the time until the first node depletes its battery energy. The nodes are randomly generated in the 500x500 m2 network simulation area. Electronic energy consumption constant Eelec is 50 nJ/bit. Amplifier energy consumption constant ε is 100 pJ/bit/m2. Amplification factor γ is 2. Node’s communication radius dmax is 200 m. Node’s initial energy Ei is 1000 J. The nonnegative constant coefficient θ is 1. The judgment constant p is 0.1. The iteration number M is 400.
Then the network lifetime is researched and compared under different numbers of nodes and sensed rates.
The simulation flow chart is shown in Fig. 2. Each node iteratively calculates its maximum lifetime with local information of neighbor nodes. After all nodes complete the number of iterations M, the loop is end and simulation results are added up. Finally the maximum network lifetime is obtained by Newton method.
Simulation results and analysis: First, the convergence of DNLM-NM algorithm is researched and simulated. In the simulation, the number of nodes is 20, the node sensed rate is 1000 bit min-1, the link maximum transmission rate is 20000 bit min-1 and the relevant parameters in above section are used. The routing schemes and maximum network lifetime are calculated 400 times. Then the maximum network lifetime values are normalized and the curve is shown in Fig. 3. The maximum network lifetime value increases as the number of iterations increases. When the number of iterations is less than 100, the curve of network lifetime is quadratic change. When the number of iterations is greater than 100, the maximum network lifetime value basically converges to the optimal value.
| Fig. 3: | Convergent curve of normalized maximum network lifetime |
So DNLM-NM algorithm is quadratic convergence. The network lifetime can convergent to the optimal value.
The node transmission data amount is normalized. It is divided into five orders of magnitude. Then the topology of 15-nodes data transmission in DNLM-NM algorithm is obtained. As shown in Fig. 4, midpoint (250, 250) is sink node. The link thickness between nodes represents the magnitude of transmission data amount. Each node has a main transmission path. Those paths consist of the backbone tree for network data transmission. In addition to the main transmission path, the node generally has some auxiliary transmission paths. Because many nodes have multiple transmission paths and the corresponding transmission data amount to guide routing, DNLM-NM algorithm can effectively balance node energy consumption, improve the maximum network lifetime.
| Fig. 4: | Topology comparison, (a) DNLM-N and (b) LORA-SPT algorithm when the number of nodes is 15 |
DNLM-NM algorithm can be used as a metric to evaluate other routing algorithms whether it is good or bad. For example, Fig. 4b is the topology of 15-nodes data transmission in LORA-SPT algorithm (Chen et al., 2012). As shown in Fig. 4a and b, some parts of the data transmission backbone paths in LORA_SPT algorithm are the same as that in DNLM_NM algorithm. It shows that LORA_SPT algorithm finds the key paths to improve the network lifetime. But there are some differences. Some nodes only transmit data to sink node along one path. It easily leads to form key nodes which consume more energy and are failure. So it shows that the network lifetime of LORA_SPT algorithm has further room for improvement.
Where, |V| represents the number of nodes. The influence of |V| on maximum network lifetime is researched.
| Fig. 5: | Lifetime computation under different numbers of nodes when sensed rate is 1000 bit min-1 and Rmax is 50000 bit min-1 |
In the simulation, 30, 40, 50, 60 nodes are selected, node sensed rate is 1000 bit min-1, the link maximum transmission rate is 50000 bit min-1 and the relevant parameters in above section are used. Maximum network lifetime of each iteration is simulated and calculated. As shown in Fig. 5, after 200 iterations, all lifetime curves converge to the optimal values. The optimal value of maximum network lifetime when |V|= 40 is maximum. The optimal value of maximum network lifetime when |V| = 30 is second. The optimal value of maximum network lifetime when |V| = 60 is minimum. It is reason that according to the same energy consumption model, energy consumption of data transmission is proportional to the transmission distance. Compared with the network when |V| = 40, the network when |V| = 30 has less number of nodes and fewer nodes transmission data amount. But due to the relative sparse distribution of nodes, nodes transmit data with longer distance. The energy consumption of per bit transmission consumers more energy and the optimal value of maximum network lifetime decreases. When |V| = 40, the node distribution in 500x500 m2 region is intensive and the energy consumption of per bit transmission is little difference. Because all nodes are required to transmit its sensed data to sink node, the transmission data amount increases as the number of nodes increases. The optimal value of maximum network lifetime decreases as the number of nodes increases.
The influence of sensed rate on maximum network lifetime is researched. In the simulation, the number of nodes is 50, the sensed rates 1000, 3000 and 5000 bit min-1 are selected, the link maximum transmission rate is 50000 bit min-1 and the relevant parameters in above section are used. Maximum network lifetime of each iteration is simulated and calculated. As shown in Fig. 6, after 100 iterations, all lifetime curves converge to optimal values.
| Fig. 6: | Lifetime computation under different sensed rates when the number of nodes is 50 and Rmax is 50000 bit min-1 |
As the sensed rate increases, the optimal value of maximum network lifetime decreases. The proportion of sensed rates is 1:3:5, the corresponding proportion of the optimal values is about 1:1/3:1/5. It is reason that all nodes sense and transmit their sensed data to sink node. When the sensed rates increase, each node needs to transmit more data and consume more energy, so the optimal value of maximum network lifetime decreases.
CONCLUSION
The DNLM_NM algorithm is used to maximize the network lifetime. First the lifetime maximization problem is cast into network optimization model. Next, the network model is decomposed into node optimization models. Each node has its optimization model with local information. The model is solved with Newton method. Finally the convergence and topology of DNLM_NM algorithm are simulated and analyzed. Maximum network lifetime under different numbers of nodes and sensed rates are compared and analyzed.
The optimal routing scheme and optimal value of maximum network lifetime are obtained with DNLM_NM algorithm. Under certain conditions, the optimal routing scheme can guide node routing. All nodes transmit data to sink node according to the optimal routing scheme. It also can be one metric to evaluate other routing algorithms. But DNLM_NM algorithm is only useful when the network nodes are static. The computation amount of DNLM_NM algorithm is large. Only when the energy consumption of data transmission is far greater than the energy consumption of optimal scheme calculation, DNLM_NM algorithm can work well. Therefore, the future research is needed to research on the low time complexity algorithm and solve the problem of mobile sink nodes.
ACKNOWLEDGMENTS
This project is supported by Zhejiang provincial public service technology research and industrial project of China under grant 2012C21042, Zhejiang provincial education department project of China under grant Y201225827 and Zhejiang provincial natural science foundation of China under grant LQ12F03014.