# Distributed Optimal Power and Rate Control in

Authors: Meiqin Tang; Jianyong Bai; Jing Li; Yalin Xin
Journal: The Scientific World Journal
 (2014)

---

## Abstract

With the rapid development of wireless sensor networks, reducing energy consumption is becoming one of the
important factors to extend node lifetime, and it is necessary to adjust the launching power of each node because
of the limited energy available to the sensor nodes in the networks. This paper proposes a power and rate control
model based on the network utility maximization (NUM) framework, where a weighting factor is used to reflect
the influence degree of the sending power and transmission rate to the utility function. In real networks, nodes
interfere with each other in the procedure of transmitting signal, which may lead to signal transmission failure
and may negatively have impacts on networks throughput. Using dual decomposition techniques, the NUM problem is
decomposed into two distributed subproblems, and then the conjugate gradient method is applied to solve the
optimization problem with the calculation of the Hessian matrix and its inverse in order to guarantee fast convergence
of the algorithm. The convergence proof is also provided in this paper. Numerical examples show that the proposed
solution achieves significant throughput compared with exiting approaches.


---

## Body

## 1. Introduction

In recent years, with the consistent development of wireless sensor networks, they have been extensively applied in environmental monitoring, volcano monitoring, forest fire prevention, military facilities, and other fields [1]. A wireless sensor network is composed of a large number of microsensors which are capable of sensing, data processing, and transmission. It transmits signals through the self-organization form of networks and the cooperation among nodes. The energy of sensor nodes is very limited, and generally the battery of nodes is not non-renewable or its’ updating is costlywhich results in an energy-constrained problem. Data transmission consumes most energy of sensor nodes. Therefore, how to control transmission power has become a key problem in the research of wireless sensor networks for low-energy consumption in data transmission under the premise of quality of services.In wireless sensor networks, power control is to continuously adjust the transmission power of network nodes through a reasonable design. It can ensure the network connectivity and reduce the mutual interference among nodes to extend the lifetime of the whole sensor network. We consider the power and rate control problem based on the network utility framework, which has been introduced in wired [2, 3] and wireless networks [4–11] since the publication of the seminal paper [2] by Kelly et al. in 1998. In the past few years, a great deal of research effort has been made on the energy conservation in wireless sensor networks. One important perspective is to maximize the network lifetime [4, 5] while guaranteeing the required traffic rate. However, since sensor nodes are assumed to have fixed source rates, it is likely that the network cannot sustain the rate for the given system resource constraints. To this end, rate allocation in wireless sensor networks has been studied in recent years [6, 7]. In [6], the use of lexicographical max-min rate allocation was advocated for the nodes and a polynomial-time algorithm was developed for exploiting the parametric analysis technique from linear programming. The rate maximization problem in [7] was formulated as a concave utility maximization and a subgradient algorithm was proposed to solve it distributively. Game theory was applied to the power control problem based on the network utility maximization (NUM) framework in wireless sensor networks [8, 9]; the appropriate transmission power was selected to improve the network topology, reduce the collisions, increase good-put, and confirm the network connectivity. In [10], two algorithms were presented to compute the transmission power of each node with the objectives of minimizing the total transmission power and the total interference, respectively. But the time-varying wireless environment was not considered in the paper. The energy-constrained nature of nodes limits the operational lifetime of the network since energy is dissipated in both sensing and communicating data across the network. There is an intrinsic tradeoff between network lifetime maximization and rate allocation in wireless sensor networks. In [11], this tradeoff was characterized by considering a cross-layer design problem in a wireless sensor network with orthogonal link transmissions, and then the dual theory was used to solve the optimization problem. A priced-based distributed power and rate control algorithm was proposed in [12]; it can simulate the cooperation of power control and rate adaptation among the nodes. A joint source-channel maximum likelihood (SCML) decoding framework is proposed in wireless sensor networks (WSNs) [13], and prediction likelihood tree (PLT) approach is applied to exploit the spatiotemporal narrowband properties of the sensor data for sequence detection.Considering the time-varying rate constraint, this paper presents a power and control algorithm based on the NUM framework which is similar to the algorithm proposed in [11, 12]. We adopt the probability to the constraint, which is more suitable for the varying wireless environment. The target function is decomposed into two optimization subproblems using dual decomposition methods to reduce the complexity of the solution for the large-scale network. We solve the optimization problem using the conjugate gradient method without the calculation of the Hessian matrix and its inverse. This can guarantee fast convergence of the algorithm.The rest of the paper is organized as follows. The system model is described in Section2. The proposed algorithm is formulated in Section 3. We give the convergence of the proposed algorithm in Section 3, numerical results are provided in Section 4, and Section 5 concludes.


## 2. Formulation of Power Optimization

### 2.1. System Description

Considering a wireless sensor network that consists of a set ofN sensor nodes and a set of L wireless communication links, we assume that the link exists only when the nodes communicate directly. The transmission rate of node s is defined as x
s, where s
∈
N and x
s
≥
0 is satisfied. Let p
s denote the transmission power of node s with 0
≤
p
s
≤
p
max
⁡, where p
max
⁡ is the maximum power. In the production and design of wireless sensor nodes, the survival time is generally designed to be not less than a constant value T
0. Assuming that most of the energy is consumed in the process of signal transmission and the other part of the energy loss is ignored, the energy of wireless sensor network nodes is stored as a constant value E, and then p
max
⁡ is given by
(1)
p
max
⁡
=
E
T
0
.Assume there exists a linkl (l
∈
L) which is connected with the other and can be modeled as a an additive white Gaussian noise (AWGN) channel with a noise spectral density N
0. The channel capacity c
l of link l can be given by Shannons theory [14]:
(2)
c
l
(
p
l
)
=
w
lo
g
2
(
1
+
p
l
K
d
l
-
α
N
0
w
)
,
where w is the fixed bandwidth, the transmission distance between the transmitter and receiver on link l is d
l, K is a constant that depends on the transmission frequency, and α is the path-loss exponent, and therefore we have the following restriction condition:
(3)
∑
s
‍
x
s
≤
c
l
(
p
l
)
.Since the node may produce mutual influence and interference when transmitting the signal, the transmission of signals between adjacent nodes is not always successful.q
s is assumed to be the probability of the successful signal transmission between adjacent nodes. We can give the following improved constraint condition:
(4)
∑
s
‍
q
s
x
s
≤
c
l
(
p
l
)
.Now we describe the calculating procedure of probabilityq
s. The number of the nodes in link l which may compete with the node s is n
s  (
n
s
∈
N
). In the case of competition, node s is to measure how much probability of q
s denotes the transmit success probability of node s. Given that the success transmitting gain is u
s, which is related to the utilization ratio of energy for the node, the failure transmitting gain is u
c and the gain that the node does not transmit is u
i. Obviously, we can get u
c
<
u
i
<
u
s since the utilization ratio of energy for the node is low when the node transmission fails, while the ratio is high when the node transmission succeeds. Consequently, the transmit success probability of node s is (
1
-
q
s
)
n
s, the transmission failure probability of node s is 1
-
(
1
-
q
s
)
n
s, and the transmission signal gain u
t of node s can be given by
(5)
u
t
=
(
1
-
q
s
)
n
s
u
s
+
[
1
-
(
1
-
q
s
)
n
s
]
u
c
.When the node does not transmit the signal, the signal gainu
w is
(6)
u
w
=
u
i
.Each node can choose to transmit the signal or not. There are two cases for transmission: success and failure. If one of the nodes successfully transmits the signal, the other nodes are all in transmission failure state or no transmission state. In order to prolong the lifetime of the whole system, the gain of the nodes needs to be balanced. Supposeu
t
=
u
ω, and we get
(7)
q
s
=
1
-
(
u
i
-
u
c
u
s
-
u
c
)
1
/
n
s
.We can find that the success transmission probability is related not only to the node number but also to the gain of the transmission success, transmission failure, and no transmission. The gains are always defined as(8)
u
s
=
ω
1
p
s
log
⁡
⁡

p
s
,
u
c
=
ω
2
p
s
log
⁡
⁡

p
s
,
u
i
=
0
,
where ω
1 and ω
2 are constants. Submitting (8) into (7), we can get
(9)
q
s
=
1
-
(
w
2
w
2
-
w
1
)
1
/
n
s
.The utility functionU
s based on the NUM framework denotes the satisfaction degree of the user, which is continuously differentiable while increasing. Taking into account the transmission rate and transmission power, the total utility function based on the network utility function is defined as
(10)
α
∑
s
‍
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
∑
s
‍
U
s
2
(
p
l
)
,
where α is the weight which can reflect the influence degree of the utility function to the transmission power and rate, and it satisfies 0.05
≤
α
≤
0.95.We can observe that a given encoding distortion can be guaranteed by controlling both the source rate and the encoding power. When simply adjusting the source rate or the encoding power to a very low or very high level, the encoding distortion will inevitably become large while the total power consumed at the sensor node will increase fast. In this paper, we consider the power and rate control problem with the power and rate constraints. The optimization problem for resource control is formulated as(11)
max
⁡
α
∑
s
‍
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
∑
s
‍
U
s
2
(
p
l
)
s
.
t
.
∑
s
‍
q
s
x
s
≤
c
l
(
p
l
)
,
l
=
1,2
,
…
,
L
1111111111111.1111111
0
≤
p
l
≤
p
max
⁡
1111111111111.1111111
0.05
≤
α
≤
0.95
,
11111111111111.111111
x
s
≥
0
.


### 2.2. Dual Decomposition of the Proposed Algorithm

Two Lagrange multipliersλ
l and μ
l are introduced to the Lagrangian dual function of the primal problem (11), and the corresponding Lagrangian dual function can be expressed as
(12)
L
(
x
s
,
p
l
,
λ
l
,
μ
l
)
=
α
∑
s
‍
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
∑
s
‍
U
s
2
(
p
l
)
+
∑
l
‍
λ
l
[
c
l
(
p
l
)
-
∑
s
‍
q
s
x
s
]
+
∑
l
‍
μ
l
(
p
max
⁡
-
p
l
)
=
∑
s
‍
[
α
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
-
q
s
x
s
∑
l
‍
λ
l
]
+
∑
l
‍
λ
l
c
l
(
p
l
)
+
∑
l
‍
μ
l
(
p
max
⁡
-
p
l
)
.The dual problem is then given by(13)
min
⁡
D
(
λ
,
μ
)
s
.
t
.
λ
≥
0
,
μ
≥
0
.We can get the dual function as follows:(14)
D
(
λ
,
μ
)
=
max
⁡
∑
s
‍
[
α
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
-
q
s
x
s
∑
l
‍
λ
l
]
+
∑
l
‍
[
λ
l
c
l
(
p
l
)
+
μ
l
(
p
max
⁡
-
p
l
)
]
.The dual function can be decomposed into two subproblems, which are evaluated separately for the nodes, and then the dual function can be rewritten as(15)
D
(
λ
,
μ
)
=
max
⁡
α
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
-
q
s
x
s
∑
l
‍
λ
l
+
λ
s
c
l
(
p
s
)
+
μ
s
(
p
s
max
⁡
-
p
s
)
.The subproblem of optimization withx
s as the variable is
(16)
max
⁡
α
U
s
1
(
x
s
)
-
q
s
x
s
∑
l
‍
λ
l
s
.
t
.
x
s
≥
0
.The subproblem of optimization withp
l as the variable is
(17)
max
⁡
-
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
+
λ
l
c
l
(
p
l
)
+
μ
l
(
p
max
⁡
-
p
l
)
s
.
t
.
0
≤
p
l
≤
p
max
⁡
.According to the dual theory, we can get the following equation for the rate suboptimization problem from (16):
(18)
min
⁡
q
s
x
s
∑
l
‍
λ
l
-
α
U
s
1
(
x
s
)
s
.
t
.
x
s
≥
0
.And the power suboptimization problem as described in (17) can be rewritten as
(19)
min
⁡
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
-
λ
l
c
l
(
p
l
)
-
μ
l
(
p
max
⁡
-
p
l
)
s
.
t
.
0
≤
p
l
≤
p
max
⁡
,
where f
(
x
s
) and f
(
p
l
) are twice continuously differentiable. We used the conjugate gradient method mentioned before to calculate, which has many advantages. It only needs to seek the function of the first order derivative, which not only alleviates the slow convergence characteristic of the steepest descent method, but also avoids the storage and computation of Hessian matrix and its inverse features in Newton’s method. Besides, the program compilation is relatively simple and the computational complexity is relatively small. It is the most effective solution of a large number of linear equations and nonlinear unconstrained optimization problems.For (16), we obtain the guiding function through the derivation of λ
l, μ
l:
(20)
∂
∂
λ
l
(
(
1
-
α
)
U
s
1
(
x
s
)
-
q
s
x
s
∑
l
λ
l
)
=
-
q
s
x
s
.For (17), we get the guiding function through the derivation of λ
l, μ
l:
(21)
∂
∂
λ
l
(
(
α
-
1
)
∑
l
‍
U
s
2
(
p
l
)
+
λ
l
c
l
(
p
l
)
+
μ
l
(
p
max
⁡
-
p
l
)
)
=
c
l
(
p
l
)
(22)
∂
∂
μ
l
(
(
α
-
1
)
∑
l
‍
U
s
2
(
p
l
)
+
λ
l
c
l
(
p
l
)
+
μ
l
(
p
l
max
⁡
-
p
l
)
)
=
p
l
max
⁡
-
p
l
.According to (20) and (21), the step iterative algorithm of λ
l is
(23)
λ
l
(
k
+
1
)
=
[
λ
l
(
k
)
+
γ
(
k
)
[
c
l
(
p
l
)
-
q
s
x
s
]
]
+
.According to (22), the step iterative algorithm of μ
l is
(24)
μ
l
(
k
+
1
)
=
[
μ
l
(
k
)
+
κ
(
k
)
(
p
max
⁡
-
p
l
)
]
+
,
where γ
(
k
) and κ
(
k
) are the step length.The principle and the procedure of powerp
l and rate x
s optimal algorithm are similar, which are all optimized based on the conjugate gradient method. And we used decomposition theory to decompose the two algorithms into one separately and they are connected by the Lagrange multipliers to be combined to one problem to assure the total utility is to be maximized. The steps of the optimization algorithm based on the conjugate gradient method for x
s are as follows.Step 1.
Given an initial value ofp
l
(
0
), μ
l
(
0
), and μ
l
(
0
), where the error ɛ
>
0, calculate f
(
0
) as follows:
(25)
f
(
0
)
=
f
(
p
l
(
0
)
)
,
and then set
(26)
d
(
0
)
=
-
Δ
f
(
p
l
(
0
)
)
,
k
=
0
.Step 2.
If(27)
∥
f
(
p
l
(
k
)
)
∥
≤
ɛ
is satisfied, stop the calculation; otherwise, go to Step 3.Step 3.
Calculate step length factorζ
k through the linear search method, where ζ
k satisfies the strong Wolfe linear search criteria:
(28)
f
(
p
l
(
k
)
)
+
ζ
k
d
k
=
min
⁡
ζ
>
0
f
(
p
l
(
k
)
+
ζ
(
k
)
d
(
k
)
)
.
Assume
(29)
p
l
(
k
+
1
)
=
p
l
(
k
)
+
ζ
k
d
k
,
λ
l
(
k
+
1
)
=
[
λ
l
(
k
)
+
γ
(
k
)
[
c
l
(
p
l
)
-
q
s
x
s
]
]
+
,
μ
l
(
k
+
1
)
=
[
μ
l
(
k
)
+
κ
(
k
)
(
p
max
⁡
-
p
l
)
]
+
.Step 4.
Calculate(30)
χ
k
=
∥
∇
f
(
p
l
(
k
+
1
)
)
∥
2
∥
∇
f
(
p
l
(
k
)
)
∥
2
,
d
k
+
1
=
-
∇
f
(
p
l
(
k
+
1
)
)
+
χ
k
d
k
.Step 5.
Consider(31)
k
=
k
+
1
;
then, go to Step 2.In the algorithm, we must guarantee the direction is decreased, which requires(32)
(
∇
f
(
p
l
(
k
)
)
,
d
(
k
)
)
=
(
∇
f
(
p
l
(
k
)
)
,
-
∇
f
(
p
l
(
k
)
)
)
=
-
∥
∇
f
(
p
l
(
k
)
)
∥
2
<
0
.So we use the strong Wolfe linear search criteria to calculate the step length factorζ
k, and the direction of d
k is definitely the descent direction.The steps of the optimization algorithm based on the conjugate gradient method forx
s are similar to p
l.Step 1.
Given an initial value ofx
s
(
0
), μ
l
(
0
), and μ
l
(
0
), where the error ɛ
′
>
0, calculate f
′
(
0
):
(33)
f
′
(
0
)
=
f
′
(
p
l
(
0
)
)
,
and then set
(34)
d
′
(
0
)
=
-
Δ
f
(
p
l
(
0
)
)
,
k
′
=
0
.Step 2.
If(35)
∥
f
′
(
p
l
(
k
)
)
∥
≤
ɛ
′
is satisfied, stop the calculation; otherwise, go to Step 3.Step 3.
Calculate the step length factorζ
k
′ through the linear search method, where ζ
k
′ satisfies the strong Wolfe linear search criteria:
(36)
f
′
(
x
s
(
k
)
)
+
ζ
k
′
d
k
′
=
min
⁡
ζ
′
>
0
⁡
f
′
(
x
s
(
k
)
+
ζ
′
(
k
)
d
′
(
k
)
)
.
Assume
(37)
x
s
(
k
+
1
)
=
x
s
(
k
)
+
ζ
k
′
d
k
′
,
λ
l
(
k
+
1
)
=
[
λ
l
(
k
)
+
γ
(
k
)
[
c
l
(
p
l
)
-
q
s
x
s
]
]
+
,
μ
l
(
k
+
1
)
=
[
μ
l
(
k
)
+
κ
(
k
)
(
p
max
⁡
-
p
l
)
]
+
.Step 4.
Calculate(38)
χ
k
′
=
∥
∇
f
′
(
x
s
(
k
+
1
)
)
∥
2
∥
∇
f
′
(
x
s
(
k
)
)
∥
2
,
d
k
+
1
′
=
-
∇
f
′
(
p
l
(
k
+
1
)
)
+
χ
k
′
d
k
′
.Step 5.
Consider(39)
k
=
k
+
1
,
and then go to Step 2.In the algorithm, we must guarantee the direction is decreased, which requires(40)
(
∇
f
′
(
x
s
(
k
)
)
,
d
(
k
)
)
=
(
∇
f
′
(
x
s
(
k
)
)
,
-
∇
f
′
(
x
s
(
k
)
)
)
=
-
∥
∇
f
′
(
x
s
(
k
)
)
∥
2
<
0
.


## 2.1. System Description

Considering a wireless sensor network that consists of a set ofN sensor nodes and a set of L wireless communication links, we assume that the link exists only when the nodes communicate directly. The transmission rate of node s is defined as x
s, where s
∈
N and x
s
≥
0 is satisfied. Let p
s denote the transmission power of node s with 0
≤
p
s
≤
p
max
⁡, where p
max
⁡ is the maximum power. In the production and design of wireless sensor nodes, the survival time is generally designed to be not less than a constant value T
0. Assuming that most of the energy is consumed in the process of signal transmission and the other part of the energy loss is ignored, the energy of wireless sensor network nodes is stored as a constant value E, and then p
max
⁡ is given by
(1)
p
max
⁡
=
E
T
0
.Assume there exists a linkl (l
∈
L) which is connected with the other and can be modeled as a an additive white Gaussian noise (AWGN) channel with a noise spectral density N
0. The channel capacity c
l of link l can be given by Shannons theory [14]:
(2)
c
l
(
p
l
)
=
w
lo
g
2
(
1
+
p
l
K
d
l
-
α
N
0
w
)
,
where w is the fixed bandwidth, the transmission distance between the transmitter and receiver on link l is d
l, K is a constant that depends on the transmission frequency, and α is the path-loss exponent, and therefore we have the following restriction condition:
(3)
∑
s
‍
x
s
≤
c
l
(
p
l
)
.Since the node may produce mutual influence and interference when transmitting the signal, the transmission of signals between adjacent nodes is not always successful.q
s is assumed to be the probability of the successful signal transmission between adjacent nodes. We can give the following improved constraint condition:
(4)
∑
s
‍
q
s
x
s
≤
c
l
(
p
l
)
.Now we describe the calculating procedure of probabilityq
s. The number of the nodes in link l which may compete with the node s is n
s  (
n
s
∈
N
). In the case of competition, node s is to measure how much probability of q
s denotes the transmit success probability of node s. Given that the success transmitting gain is u
s, which is related to the utilization ratio of energy for the node, the failure transmitting gain is u
c and the gain that the node does not transmit is u
i. Obviously, we can get u
c
<
u
i
<
u
s since the utilization ratio of energy for the node is low when the node transmission fails, while the ratio is high when the node transmission succeeds. Consequently, the transmit success probability of node s is (
1
-
q
s
)
n
s, the transmission failure probability of node s is 1
-
(
1
-
q
s
)
n
s, and the transmission signal gain u
t of node s can be given by
(5)
u
t
=
(
1
-
q
s
)
n
s
u
s
+
[
1
-
(
1
-
q
s
)
n
s
]
u
c
.When the node does not transmit the signal, the signal gainu
w is
(6)
u
w
=
u
i
.Each node can choose to transmit the signal or not. There are two cases for transmission: success and failure. If one of the nodes successfully transmits the signal, the other nodes are all in transmission failure state or no transmission state. In order to prolong the lifetime of the whole system, the gain of the nodes needs to be balanced. Supposeu
t
=
u
ω, and we get
(7)
q
s
=
1
-
(
u
i
-
u
c
u
s
-
u
c
)
1
/
n
s
.We can find that the success transmission probability is related not only to the node number but also to the gain of the transmission success, transmission failure, and no transmission. The gains are always defined as(8)
u
s
=
ω
1
p
s
log
⁡
⁡

p
s
,
u
c
=
ω
2
p
s
log
⁡
⁡

p
s
,
u
i
=
0
,
where ω
1 and ω
2 are constants. Submitting (8) into (7), we can get
(9)
q
s
=
1
-
(
w
2
w
2
-
w
1
)
1
/
n
s
.The utility functionU
s based on the NUM framework denotes the satisfaction degree of the user, which is continuously differentiable while increasing. Taking into account the transmission rate and transmission power, the total utility function based on the network utility function is defined as
(10)
α
∑
s
‍
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
∑
s
‍
U
s
2
(
p
l
)
,
where α is the weight which can reflect the influence degree of the utility function to the transmission power and rate, and it satisfies 0.05
≤
α
≤
0.95.We can observe that a given encoding distortion can be guaranteed by controlling both the source rate and the encoding power. When simply adjusting the source rate or the encoding power to a very low or very high level, the encoding distortion will inevitably become large while the total power consumed at the sensor node will increase fast. In this paper, we consider the power and rate control problem with the power and rate constraints. The optimization problem for resource control is formulated as(11)
max
⁡
α
∑
s
‍
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
∑
s
‍
U
s
2
(
p
l
)
s
.
t
.
∑
s
‍
q
s
x
s
≤
c
l
(
p
l
)
,
l
=
1,2
,
…
,
L
1111111111111.1111111
0
≤
p
l
≤
p
max
⁡
1111111111111.1111111
0.05
≤
α
≤
0.95
,
11111111111111.111111
x
s
≥
0
.


## 2.2. Dual Decomposition of the Proposed Algorithm

Two Lagrange multipliersλ
l and μ
l are introduced to the Lagrangian dual function of the primal problem (11), and the corresponding Lagrangian dual function can be expressed as
(12)
L
(
x
s
,
p
l
,
λ
l
,
μ
l
)
=
α
∑
s
‍
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
∑
s
‍
U
s
2
(
p
l
)
+
∑
l
‍
λ
l
[
c
l
(
p
l
)
-
∑
s
‍
q
s
x
s
]
+
∑
l
‍
μ
l
(
p
max
⁡
-
p
l
)
=
∑
s
‍
[
α
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
-
q
s
x
s
∑
l
‍
λ
l
]
+
∑
l
‍
λ
l
c
l
(
p
l
)
+
∑
l
‍
μ
l
(
p
max
⁡
-
p
l
)
.The dual problem is then given by(13)
min
⁡
D
(
λ
,
μ
)
s
.
t
.
λ
≥
0
,
μ
≥
0
.We can get the dual function as follows:(14)
D
(
λ
,
μ
)
=
max
⁡
∑
s
‍
[
α
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
-
q
s
x
s
∑
l
‍
λ
l
]
+
∑
l
‍
[
λ
l
c
l
(
p
l
)
+
μ
l
(
p
max
⁡
-
p
l
)
]
.The dual function can be decomposed into two subproblems, which are evaluated separately for the nodes, and then the dual function can be rewritten as(15)
D
(
λ
,
μ
)
=
max
⁡
α
U
s
1
(
x
s
)
-
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
-
q
s
x
s
∑
l
‍
λ
l
+
λ
s
c
l
(
p
s
)
+
μ
s
(
p
s
max
⁡
-
p
s
)
.The subproblem of optimization withx
s as the variable is
(16)
max
⁡
α
U
s
1
(
x
s
)
-
q
s
x
s
∑
l
‍
λ
l
s
.
t
.
x
s
≥
0
.The subproblem of optimization withp
l as the variable is
(17)
max
⁡
-
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
+
λ
l
c
l
(
p
l
)
+
μ
l
(
p
max
⁡
-
p
l
)
s
.
t
.
0
≤
p
l
≤
p
max
⁡
.According to the dual theory, we can get the following equation for the rate suboptimization problem from (16):
(18)
min
⁡
q
s
x
s
∑
l
‍
λ
l
-
α
U
s
1
(
x
s
)
s
.
t
.
x
s
≥
0
.And the power suboptimization problem as described in (17) can be rewritten as
(19)
min
⁡
(
1
-
α
)
∑
l
‍
U
s
2
(
p
l
)
-
λ
l
c
l
(
p
l
)
-
μ
l
(
p
max
⁡
-
p
l
)
s
.
t
.
0
≤
p
l
≤
p
max
⁡
,
where f
(
x
s
) and f
(
p
l
) are twice continuously differentiable. We used the conjugate gradient method mentioned before to calculate, which has many advantages. It only needs to seek the function of the first order derivative, which not only alleviates the slow convergence characteristic of the steepest descent method, but also avoids the storage and computation of Hessian matrix and its inverse features in Newton’s method. Besides, the program compilation is relatively simple and the computational complexity is relatively small. It is the most effective solution of a large number of linear equations and nonlinear unconstrained optimization problems.For (16), we obtain the guiding function through the derivation of λ
l, μ
l:
(20)
∂
∂
λ
l
(
(
1
-
α
)
U
s
1
(
x
s
)
-
q
s
x
s
∑
l
λ
l
)
=
-
q
s
x
s
.For (17), we get the guiding function through the derivation of λ
l, μ
l:
(21)
∂
∂
λ
l
(
(
α
-
1
)
∑
l
‍
U
s
2
(
p
l
)
+
λ
l
c
l
(
p
l
)
+
μ
l
(
p
max
⁡
-
p
l
)
)
=
c
l
(
p
l
)
(22)
∂
∂
μ
l
(
(
α
-
1
)
∑
l
‍
U
s
2
(
p
l
)
+
λ
l
c
l
(
p
l
)
+
μ
l
(
p
l
max
⁡
-
p
l
)
)
=
p
l
max
⁡
-
p
l
.According to (20) and (21), the step iterative algorithm of λ
l is
(23)
λ
l
(
k
+
1
)
=
[
λ
l
(
k
)
+
γ
(
k
)
[
c
l
(
p
l
)
-
q
s
x
s
]
]
+
.According to (22), the step iterative algorithm of μ
l is
(24)
μ
l
(
k
+
1
)
=
[
μ
l
(
k
)
+
κ
(
k
)
(
p
max
⁡
-
p
l
)
]
+
,
where γ
(
k
) and κ
(
k
) are the step length.The principle and the procedure of powerp
l and rate x
s optimal algorithm are similar, which are all optimized based on the conjugate gradient method. And we used decomposition theory to decompose the two algorithms into one separately and they are connected by the Lagrange multipliers to be combined to one problem to assure the total utility is to be maximized. The steps of the optimization algorithm based on the conjugate gradient method for x
s are as follows.Step 1.
Given an initial value ofp
l
(
0
), μ
l
(
0
), and μ
l
(
0
), where the error ɛ
>
0, calculate f
(
0
) as follows:
(25)
f
(
0
)
=
f
(
p
l
(
0
)
)
,
and then set
(26)
d
(
0
)
=
-
Δ
f
(
p
l
(
0
)
)
,
k
=
0
.Step 2.
If(27)
∥
f
(
p
l
(
k
)
)
∥
≤
ɛ
is satisfied, stop the calculation; otherwise, go to Step 3.Step 3.
Calculate step length factorζ
k through the linear search method, where ζ
k satisfies the strong Wolfe linear search criteria:
(28)
f
(
p
l
(
k
)
)
+
ζ
k
d
k
=
min
⁡
ζ
>
0
f
(
p
l
(
k
)
+
ζ
(
k
)
d
(
k
)
)
.
Assume
(29)
p
l
(
k
+
1
)
=
p
l
(
k
)
+
ζ
k
d
k
,
λ
l
(
k
+
1
)
=
[
λ
l
(
k
)
+
γ
(
k
)
[
c
l
(
p
l
)
-
q
s
x
s
]
]
+
,
μ
l
(
k
+
1
)
=
[
μ
l
(
k
)
+
κ
(
k
)
(
p
max
⁡
-
p
l
)
]
+
.Step 4.
Calculate(30)
χ
k
=
∥
∇
f
(
p
l
(
k
+
1
)
)
∥
2
∥
∇
f
(
p
l
(
k
)
)
∥
2
,
d
k
+
1
=
-
∇
f
(
p
l
(
k
+
1
)
)
+
χ
k
d
k
.Step 5.
Consider(31)
k
=
k
+
1
;
then, go to Step 2.In the algorithm, we must guarantee the direction is decreased, which requires(32)
(
∇
f
(
p
l
(
k
)
)
,
d
(
k
)
)
=
(
∇
f
(
p
l
(
k
)
)
,
-
∇
f
(
p
l
(
k
)
)
)
=
-
∥
∇
f
(
p
l
(
k
)
)
∥
2
<
0
.So we use the strong Wolfe linear search criteria to calculate the step length factorζ
k, and the direction of d
k is definitely the descent direction.The steps of the optimization algorithm based on the conjugate gradient method forx
s are similar to p
l.Step 1.
Given an initial value ofx
s
(
0
), μ
l
(
0
), and μ
l
(
0
), where the error ɛ
′
>
0, calculate f
′
(
0
):
(33)
f
′
(
0
)
=
f
′
(
p
l
(
0
)
)
,
and then set
(34)
d
′
(
0
)
=
-
Δ
f
(
p
l
(
0
)
)
,
k
′
=
0
.Step 2.
If(35)
∥
f
′
(
p
l
(
k
)
)
∥
≤
ɛ
′
is satisfied, stop the calculation; otherwise, go to Step 3.Step 3.
Calculate the step length factorζ
k
′ through the linear search method, where ζ
k
′ satisfies the strong Wolfe linear search criteria:
(36)
f
′
(
x
s
(
k
)
)
+
ζ
k
′
d
k
′
=
min
⁡
ζ
′
>
0
⁡
f
′
(
x
s
(
k
)
+
ζ
′
(
k
)
d
′
(
k
)
)
.
Assume
(37)
x
s
(
k
+
1
)
=
x
s
(
k
)
+
ζ
k
′
d
k
′
,
λ
l
(
k
+
1
)
=
[
λ
l
(
k
)
+
γ
(
k
)
[
c
l
(
p
l
)
-
q
s
x
s
]
]
+
,
μ
l
(
k
+
1
)
=
[
μ
l
(
k
)
+
κ
(
k
)
(
p
max
⁡
-
p
l
)
]
+
.Step 4.
Calculate(38)
χ
k
′
=
∥
∇
f
′
(
x
s
(
k
+
1
)
)
∥
2
∥
∇
f
′
(
x
s
(
k
)
)
∥
2
,
d
k
+
1
′
=
-
∇
f
′
(
p
l
(
k
+
1
)
)
+
χ
k
′
d
k
′
.Step 5.
Consider(39)
k
=
k
+
1
,
and then go to Step 2.In the algorithm, we must guarantee the direction is decreased, which requires(40)
(
∇
f
′
(
x
s
(
k
)
)
,
d
(
k
)
)
=
(
∇
f
′
(
x
s
(
k
)
)
,
-
∇
f
′
(
x
s
(
k
)
)
)
=
-
∥
∇
f
′
(
x
s
(
k
)
)
∥
2
<
0
.


## 3. Convergence Analyses

For the general function, the conjugate gradient method under certain conditions is convergent, and the convergence speed is generally superior to that of the steepest descent method. Thep
l’s convergence will be proved as follows. It is similar to x
s.Proposition 1.
Assume thatf
(
p
l
) is in the bounded set
(41)
L
=
{
p
l
∈
R
∣
f
(
p
l
)
≤
f
(
p
l
(
0
)
)
}
,
which is continuously differentiable and has a lower bound; then, the sequence obtained by the conjugate gradient method {
p
l
} converges to p
l
*, which is the stagnation point of f
(
p
l
).Proof.
Given that{
p
l
(
k
)
} is a finite sequence of number, according to the algorithms termination conditions, the last p
l
* must meet
(42)
g
(
p
l
*
)
=
0
,
so p
l
* is the stagnation point of f
(
p
l
).
If{
p
l
(
k
)
} is an infinite series, then for all k,
(43)
∇
f
(
p
l
(
k
)
)
≠
0
.
Since
(44)
d
k
=
-
∇
f
(
p
l
(
k
)
)
+
χ
k
d
k
-
1
,
we get
(45)
(
∇
f
(
p
l
(
k
)
)
,
d
k
)
=
-
∥
∇
f
(
p
l
(
k
)
)
∥
2
<
0
,
where d
k is the decline direction. Since {
f
(
p
l
(
k
)
)
} is the lower bound of the sequence and is monotonically decreasing,
(46)
f
(
p
l
(
k
)
)
⟶
f
(
p
l
*
)
.
The convergence analysis ofx
s
* is similar to p
l
*.


## 4.  Numerical Example

We simulate a network which consists of nine sensor nodes and one sink node. The sensor nodes will transmit their sensing data to the sink node, and all the nodes are randomly deployed in an area of 100 m × 100 m. The utility function is set to be in thelog
⁡ form; for example, U
1 is set to be log
⁡
2
(
x
) and U
2
=
-
p. The fixed bandwidth w is set to 5 MHz and the maximum of p is set to be 1 mW for all links. The path-loss exponent σ is set to 2. We will show the network performance with different α values.First, we show the convergence figures for the optimal rates and power. The maximum iteration of the algorithm is set to be 200. Figures1 and 2 show the optimal video rates for sensor nodes when α is set to 0.05 and 0.95, respectively, from which we can find that the proposed algorithm can converge within 20 iteration steps. We also find the located rates of some nodes are large, while the others are small. This is because these nodes transmit the data to the sink node directly, which will not relay the data and will transmit the data more efficiently. In wireless sensor networks, the available energy is limited, and Figures 3 and 4 show the consumed video power of the nodes, from which we can also indicate the proposed algorithm can get to the optimum efficiently and quickly. From these four figures, we can find that the proposed algorithm can get higher throughput and uses less energy.Figure 1
The optimal video rates for sensor nodes whenα is set to 0.05.Figure 2
The optimal video rates for sensor nodes whenα is set to 0.95.Figure 3
The consumed video power of the nodes whenα is set to 0.05.Figure 4
The consumed video power of the nodes whenα is set to 0.95.In Figure5, we find that when we set α to 0.95, the utility is large, but the value of lifetime is small; when the α is set to 0.05, the value of lifetime is large, while the network utility is small. For this reason, we can find that there is apparently a tradeoff between network utility and network lifetime in energy-limited wireless networks. Different values can be set according to actual need.Figure 5
The tradeoff between network utility and network lifetime.In order to verify the performance of the proposed algorithm, we compared it with previous works in [11, 12], and the network setup is the same. Tables 1 and 2 give the data rate comparison with different values. From these two tables we can find that the proposed algorithm can get higher utility than the algorithm in [12] and minUtility [11] and less power consumption than the algorithm in [12] and MaxUtility [11], because minUtility only seeks minimum energy consumption and while MaxUtility only seeks the maximum utility. Through adding the probability for the rate constraint, our algorithm can get higher data rate.Table 1
The data rate comparison with different methods forα = 0.05.
Method
Node 1
Node 2
Node 3
Node 4
Node 5
Node 6
Node 7
Node 8
The proposed algorithm
1.1256e + 05
1.4621e + 05
1.0543e + 05
1.2390e + 05
2.2111e + 05
1.5098e  + 05
1.5678e + 05
2.2567e + 05
The algorithm in [12]
1.1021e + 05
1.3609e + 05
0.9763e + 05
1.1907e + 05
1.8798e + 05
1.3142e + 05
1.3988e + 05
2.0995e + 05
MaxUtility [11]
1.26e + 05
1.4569e + 05
1.1314e + 05
1.3086e + 05
1.9209e + 05
1.7142e + 05
1.6678e + 05
1.8765e + 05
MinEnergy [11]
92
89.21
98.74
99.2356
101.48
99.672
96.32
102.54Table 2
The data rate comparison with different methods forα = 0.95.
Method
Node 1
Node 2
Node 3
Node 4
Node 5
Node 6
Node 7
Node 8
The proposed algorithm
4.4123e + 05
4.6678e + 05
4.321e + 05
4.5009e + 05
6.3457e + 05
4.8914e + 05
4.9562e + 05
6.1209e + 05
The algorithm in [12]
4.2265e + 05
4.4324e + 03e + 05
4.5616e + 05
4.3190e + 05
4.4999e + 05
6.2008e + 05
4.81998e + 05
4.785e + 05
MaxUtility [11]
4.5532e + 05
4.7121e + 03e + 05
4.35143e + 05
4.590e + 05
4.8654e + 05
4.2672e + 05
4.996e + 05
4.9867e + 05
MinEnergy [11]
104.56
105.32
102.78
103.45
128.9
107.8
103.81
127.65Tables3 and 4 show the power of the different algorithms, for which we can see that the proposed algorithm get less power consumption than the algorithm proposed in [12] and MaxUtility [11], which shows the proposed algorithm is very efficiently.Table 3
The data power comparison with different methods forα = 0.05.
Method
Node 1
Node 2
Node 3
Node 4
Node 5
Node 6
Node 7
Node 8
The proposed algorithm
0.6321e −6
0.6102e −6
0.6198e −6
0.6218e −6
0.5187e −6
0.6018e −6
0.5989e −6
0.5266e −6
The algorithm in [12]
0.7112e −6
0.7426e + 03e −6
0.7002e −6
0.7221e −6
0.6789e −6
0.7108e −6
0.7685e −6
0.6351e −6
MaxUtility [11]
0.9168e −05
0.9041e −05
0.9908e −05
0.9127e −05
0.8873e −05
0.9162e −05
0.9092e −05
0.8904e −05
MinEnergy [11]
0.8465e −09
0.8169e −09
0.83287e −09
0.8658e −09
0.1099e −10
0.8365e −09
0.8102e −09
0.1214e −10Table 4
The data rate comparison with different methods forα = 0.95.
Method
Node 1
Node 2
Node 3
Node 4
Node 5
Node 6
Node 7
Node 8
The proposed algorithm
0.3214e − 6
0.3189e − 6
0.3102e − 6
0.3336e − 6
0.1765e − 6
0.3087e − 6
0.3096e − 6
0.1924e − 6
The algorithm in [12]
0.4219e − 6
0.4468e + 03e − 6
0.4097e − 6
0.4354e − 6
0.2176e − 6
0.4677e − 6
0.4781e − 6
0.2674e − 6
MaxUtility [11]
0.5532e − 05
0.5096e − 05
0.5989e − 05
0.5213e − 05
0.3786e − 05
0.5011e − 05
0.5124e − 05
0.3989e − 05
MinEnergy [11]
0.4107e − 09
0.4231e − 09
0.4358e − 09
0.4691e − 09
0.0519e − 10
0.4218e − 09
0.449e − 09
0.0627e − 10


## 5. Conclusion

This paper proposes a new power control method based on network utility maximization framework for wireless sensor networks, and a trade-off parameter for the utility and lifetime is introduced to the system. Considering the time varying environment, the probability is added to the rate constraint, which is natural in the context of various applications. Moreover, we put forward a new priced-based distributed algorithm using a gradient method. The algorithm is designed to keep acceptable throughput. Simulation studies show that the proposed algorithms are effective to solve the optimization problem and outperform the existing approaches in terms of throughput and energy efficiency since desired variables converge to the optimal point very quickly.



---

*Source: 580854-2014-05-08.xml*