# Cross-Layer Cooperative Power Control in Heterogeneous Multihop Networks

Authors: Feng Tian; Dapeng Li; Xuejun Zhang; Zhen Yang
Journal: Mobile Information Systems
 (2016)

---

## Abstract

This paper investigates how to perform optimal cooperative power control for the coexistence of heterogeneous multihop networks. Although power control on the node level in multihop networks is a difficult problem due to its large design space and the coupling relationship of power control with scheduling and routing, we formulate a multiobjective optimization problem for the total power consumption of the two heterogeneous multihop networks with discretized power level. We reformulate the nonlinear constraint (relationship between power and capacity) into the linear one by piecewise linearization procedure and offer an in-depth study of cooperative power control in terms of its optimal power—the minimum power consumption with discretized power level for both heterogeneous multihop networks. Through a novel approach based on adaptive weighted-sum method, we transform the multiobjective optimization problem into a single-objective optimization problem and find the set of Pareto-optimal points iteratively. Using the Pareto-optimal points, we construct the minimum power curve. Using numerical results, we demonstrate that it can save more energy with cooperative power control than the case without cooperative power control.


---

## Body

## 1. Introduction

The ever-increasing number of wireless systems leads to the scarcity of available spectrum. It is necessary to enable highly efficient spectrum sharing among diverse wireless networks [1]. Most of them are heterogeneous in hardware and software capabilities, physical layer technologies, or network protocol standards and are expected to be deployed in the same region and overlapped with each other in time, frequency, and space. Some examples of existing and future radio devices/networks that need cooperative power control include IEEE 802.11 (Wi-Fi), 802.15.4 (ZigBee), 802.16 (WiMAX), and Bluetooth in the ISM bands and IEEE 802.22 (WRAN) and IEEE 802.11af (WLAN) in the TV white space [2–5]. Often, there is no central administration or planning for the coexistence of such networks. In order to avoid interference and achieve optimal network performance under the paradigm of spectrum sharing, it inevitably leads to cooperative power control between multiple heterogeneous multihop networks, which is based on the node level.As a fundamental problem for wireless networks, power control is challenging because it directly affects upper layers scheduling and routing. Meanwhile, when each node in multiple heterogeneous multihop networks is allowed to perform power control, the problem becomes even more difficult due to its large optimization space. In [6], the authors developed a formal mathematical model for a joint per-node based power control, scheduling, and flow routing problem. And they explored a unified solution procedure based on branch-and-bound framework and convex hull relaxation that guarantees (
1
-
ε
) optimal solution, where ε is a small prespecified error tolerance parameter. In [7], the authors investigated the network capacity problem for multihop CRNs in the SINR model. They considered how to maximize the rates of sessions with a mathematical model combining power control, frequency band scheduling, and flow routing. And they formulated a mixed-integer nonlinear program (MINLP) problem to be solved by an algorithm also based on the branch-and-bound and (
1
-
ε
) optimal solution. Although these works are solid for power control on the node level, they only involve a single objective in one single network and their approximate optimal algorithm is rather complex.Beyond power control on the node level in one single homogeneous wireless network [6, 7], the authors mainly focused on power control in heterogeneous cellular networks rather than heterogeneous multihop networks [8–12]. Although the joint optimization of power, bandwidth allocation, and interference alignment was explored in [13–18], they only consider the single-objective function without the cooperative interaction between multiple heterogeneous networks. In this paper, we consider the total power consumption minimization of two heterogeneous multihop networks with discretized power level through cooperative power control, respectively, to formulate a multiple optimization problem to be amultiobjective mixed-integer nonlinear programming (MO-MINLP) one. By the aid of piecewise linearization procedure, we reformulate the nonlinear constraint (relationship between power and capacity) into the linear one and obtain a multiobjective mixed-integer linear programming (MO-MILP) problem and offer an in-depth study of cooperative power control in terms of its optimal power curve—the minimum power consumption for both heterogeneous multihop networks. Through a novel approach based on adaptive weighted-sum method, we transform the multiobjective optimization problem into a single-objective optimization problem, that is, mixed-integer linear programming (MILP) solved by commercial software (e.g., CPLEX), and find the set of Pareto-optimal points iteratively. With these Pareto-optimal points, we finally construct the minimum power curve with discretized power level. And by applying the solution procedure on two heterogeneous multihop networks generated randomly, we validate this solution procedure and offer additional insights into the behavior of cooperative power control in heterogeneous multihop networks. The main motivation of the two heterogeneous networks is to enable the cooperation between two independent and colocated networks on the power plane, such as the example of coexistence of ZigBee and Z-Wave in Smart Home Networking but not limited to this application in practice. For the case of more heterogeneous networks coexistence, we can extend our proposed approach to achieve the similarly optimal results.The remainder of this paper is organized as follows. In Section2, we develop a mathematical model of cooperative power control on the node level, scheduling, and flow routing for two heterogeneous multihop networks. In Section 3, we formulate a multiobjective cross-layer optimization problem and reformulate it into a MO-MILP problem. Section 4 describes a solution procedure based on adaptive weighted-sum method to this cross-layer optimization problem. In Section 5, we use numerical results to validate the efficacy of the solution procedure. Section 6 concludes this paper.


## 2. Mathematical Modeling

In this section, we develop a mathematical model for simultaneously optimizing the total power consumption for both heterogeneous networks (i.e., Network 1 and Network 2). DenoteN as the combined set of nodes consisting of both the set of Network 1’s nodes N
1 and the set of Network 2’s nodes N
2; that is, N
=
N
1
∪
N
2. In the combined network, denote T
j
t as the set of nodes (including nodes from two heterogeneous networks) located within node j’s transmission range on time slot t with t
∈
τ under full power P, where j can be a node from either Network 1 or Network 2 (i.e., j
∈
N). Denote I
j
t as the set of nodes (including nodes from two heterogeneous networks) located within node j’s interference range on time slot t with t
∈
τ under full power P, where j can be a node from either Network 1 or Network 2 (i.e., j
∈
N). Denote L
^ and L as the set of active Network 1’s and Network 2’s sessions, respectively.


### 2.1. Power Control, Scheduling, and Their Relationship

In this paper, we consider scheduling in the time domain in the form of time slots since scheduling for transmission at each node in the primary and secondary networks can be done in either time domain or frequency domain and these two scheduling schemes are equivalent in terms of achievable rate region.Now, we formalize a mathematical model for the joint relationship between each node of two heterogeneous networks based on power control and scheduling as shown in Figure1. For example, there are two links “1
→
2” and “3
→
4” in Network 1 and two links “5
→
6” and “7
→
8” in Network 2, which are all active due to cooperative power control on the node level between two heterogeneous networks. For the first case without cooperative power control between two heterogeneous networks, node 7 unilaterally increases its transmission power as node 5 to be the maximum power, and then links “1
→
2” and “3
→
4” are all inactive. For the second case without cooperative power control between two heterogeneous networks, nodes 1 and 3 simultaneously increase their transmission power and keep links “1
→
2” and “3
→
4” in Network 1 active, but links “5
→
6” and “7
→
8” in Network 2 are all inactive. Obviously, we find that the four links in the two heterogeneous networks can simultaneously become active with cooperative power control between two heterogeneous networks, which achieves the best performance for the two networks.Figure 1
Two 2-link heterogeneous networks with cooperative power control on the node level.Denote(1)
x
i
j
t
=
1
i
f
n
o
d
e
i
t
r
a
n
s
m
i
t
s
d
a
t
a
t
o
n
o
d
e
j
o
n
t
i
m
e
s
l
o
t
t
,
0
o
t
h
e
r
w
i
s
e
.As mentioned above, we consider scheduling in the time domain and thus once a time slot is used by node i for transmission to node j, this time slot cannot be used again by node i to transmit to a different node. That is,(2)
∑
j
∈
T
i
t
x
i
j
t
≤
1
.Denote byp
i
j
[
t
] the transmission power from node i to node j in time slot t. For transmission from node i to node j, a simple model for path attenuation loss g
i
j is(3)
g
i
j
=
d
i
j
-
n
,where d
i
j is the physical distance between nodes i and j and n is the path loss index. Similar to the assumption in [6], we assume data transmission from node i to node j is successful only if the received power at node j exceeds a threshold γ
T. Denote the transmission range at node i under p
i
j
[
t
] as R
T
(
p
i
j
[
t
]
). Then, based on g
i
j
R
T
(
p
i
j
[
t
]
)
≥
γ
T and (2), we can calculate the transmission range of this node as follows:(4)
R
T
p
i
j
t
=
p
i
j
t
γ
T
1
/
n
.Since the receiving node j must be physically within the transmission range of node i, we have(5)
d
i
j
≤
p
i
j
t
γ
T
1
/
n
.Similarly, we assume that interference is nonnegligible only if it exceeds a threshold, say γ
I at a receiver. Denote the interference range of node k (k
∈
N, k
≠
i) under p
k
h
[
t
] as R
I
(
p
k
h
[
t
]
), where h is the intended receiving node of transmitting node k. Similarly, we can obtain the interference range of node k as R
I
(
p
k
h
[
t
]
)
=
(
p
k
h
[
t
]
/
γ
I
)
1
/
n. Since the receiving node j must not fall in the interference range of any other node k that is transmitting in the same time slot, we have(6)
d
j
k
≥
p
k
h
t
γ
I
1
/
n
.Denote byR
T
m
a
x the maximum transmission range of a node when it transmits at full power P. Then, based on (4), we have R
T
m
a
x
=
R
T
(
P
)
=
(
P
/
γ
T
)
1
/
n. Thus, we have γ
T
=
P
/
(
R
T
m
a
x
)
n. Then, for a node transmitting at power p
i
j
[
t
]
∈
[
0
,
P
], its transmission range is (7)
R
T
p
i
j
t
=
p
i
j
t
γ
T
1
/
n
=
p
i
j
t
R
T
m
a
x
n
P
1
/
n
=
p
i
j
t
P
1
/
n
R
T
m
a
x
.Similarly, denote by R
I
m
a
x the maximum interference range of a node when it transmits at full power P. Then, following the same token, we have R
I
m
a
x
=
R
I
(
P
)
=
(
P
/
γ
I
)
1
/
n and γ
I
=
P
/
(
R
I
m
a
x
)
n. For a node transmitting at power p
i
j
[
t
]
∈
[
0
,
P
], its interference range is (8)
R
I
p
i
j
t
=
p
i
j
t
P
1
/
n
R
I
m
a
x
.Remember thatT
j
t denotes the set of nodes to which node can transmit on time slot t under full power P. More formally, we have T
i
t
=
{
j
:
d
i
j
≤
R
T
m
a
x
,
j
≠
i
,
t
∈
τ
}. Similarly, denote by I
j
t the set of nodes that can make interference on node j on time slot t under full power P; that is, I
i
t
=
k
:
d
j
k
≤
R
I
m
a
x
,
t
∈
τ. Note that the definitions of T
j
t and I
j
t are both based on full transmission power P. When power level p
i
j
[
t
] is below P, the corresponding transmission and interference ranges will be smaller. As a result, it is necessary to keep track of the set of nodes that fall in the transmission range and the set of nodes that can produce interference whenever transmission power changes at a node. From the two constraints (5) and (6) for successful transmission from node i to node j and (7) and (8), respectively, we have(9)
d
i
j
≤
R
T
p
i
j
t
=
p
i
j
t
P
1
/
n
R
T
m
a
x
,
(10)
d
j
k
≥
R
I
p
k
h
t
=
p
k
h
t
P
1
/
n
R
T
m
a
x
,
k
∈
I
j
t
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
.Based on the above two constraints, we have the following requirements for the transmission link i
→
j and interfering link k
→
h:(11)
p
i
j
t
∈
d
i
j
R
T
m
a
x
n
P
,
P
i
f
x
i
j
t
=
1
,
=
0
i
f
x
i
j
t
=
0
,
p
k
h
t
≤
d
k
j
R
I
m
a
x
n
P
i
f
x
i
j
t
=
1
,
P
i
f
x
i
j
t
=
0
,
k
∈
I
j
m
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
.Meanwhile, these requirements can also be rewritten as (12)
p
i
j
t
∈
d
i
j
R
T
m
a
x
n
P
x
i
j
t
,
P
x
i
j
t
,
p
k
h
t
≤
P
-
1
-
d
k
j
R
I
m
a
x
n
P
x
i
j
t
,
k
∈
I
j
m
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
.Additionally, for successful scheduling in time domain, the following two constraints must also hold:(a)
For a time slott
∈
τ that is available at node j, this time slot cannot be used for both transmission and receiving. That is, if time slot t is used at node j for transmission (or receiving), then it cannot be used for receiving (or transmission).
(b)
Similar to constraint (2) on transmission, node j cannot use the same time slot t to receive from two different nodes.Therein, (a) can be viewed as “self-interference” avoidance constraint where, at the same nodej, its transmission to another node h on time slot t interferes in its reception from node i on the same time slot. It turns out that the above two constraints are mathematicallyembedded in (12). That is, once (12) are satisfied, then both constraints (a) and (b) are satisfied. This result can be similarly proved with Lemma 1 [6].


### 2.2. Flow Routing and Link Capacity

We assume there is a set ofL
^
∪
L active user communication (unicast) sessions in the combined heterogeneous networks. Denote by s
(
l
) and d
(
l
) the source and destination nodes of session l
∈
L
^
∪
L and r
(
l
) the rate requirement (in b/s) of session l. We consider the most general case of multipath routing; that is, we allow flow splitting between a source node and its destination node.Mathematically, this can be easily modeled based on flow balance at each node. Denote byf
i
j
(
l
) the data rate on link (
i
,
j
) that is attributed to session l, where i
∈
N,  i
≠
d
(
l
),  j
∈
T
i
=
⋃
t
∈
τ
T
i
t,  j
≠
s
(
l
). If node i is the source node of session l, that is, i
≠
s
(
l
), then(13)
∑
j
∈
T
i
f
i
j
l
=
r
l
.If node i is an intermediate relay node for session l, that is, i
≠
s
(
l
) and i
≠
d
(
l
), then(14)
∑
j
∈
T
i
j
≠
s
l
f
i
j
l
=
∑
k
∈
T
i
k
≠
d
l
f
k
i
l
.If node i is the destination node of session l, that is, i
≠
d
(
l
), then(15)
∑
k
∈
T
i
f
k
i
l
=
r
l
.It can be easily verified that once (13) and (14) are satisfied, (15) must also be satisfied. As a result, it is sufficient to have (13) and (14) in the formulation.Except for the above flow balance equations at each nodei
∈
N for session l
∈
L
^
⁡
∪
L, the aggregated flow rates on each radio link cannot exceed this link’s capacity. Under p
i
j
[
t
], we have(16)
∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
≤
∑
t
=
1
τ
c
i
j
t
=
∑
t
=
1
τ
W
log
2
⁡
1
+
g
i
j
n
0
W
p
i
j
t
,where n
0 is the ambient Gaussian noise density and l
∈
L
^
∪
L.


## 2.1. Power Control, Scheduling, and Their Relationship

In this paper, we consider scheduling in the time domain in the form of time slots since scheduling for transmission at each node in the primary and secondary networks can be done in either time domain or frequency domain and these two scheduling schemes are equivalent in terms of achievable rate region.Now, we formalize a mathematical model for the joint relationship between each node of two heterogeneous networks based on power control and scheduling as shown in Figure1. For example, there are two links “1
→
2” and “3
→
4” in Network 1 and two links “5
→
6” and “7
→
8” in Network 2, which are all active due to cooperative power control on the node level between two heterogeneous networks. For the first case without cooperative power control between two heterogeneous networks, node 7 unilaterally increases its transmission power as node 5 to be the maximum power, and then links “1
→
2” and “3
→
4” are all inactive. For the second case without cooperative power control between two heterogeneous networks, nodes 1 and 3 simultaneously increase their transmission power and keep links “1
→
2” and “3
→
4” in Network 1 active, but links “5
→
6” and “7
→
8” in Network 2 are all inactive. Obviously, we find that the four links in the two heterogeneous networks can simultaneously become active with cooperative power control between two heterogeneous networks, which achieves the best performance for the two networks.Figure 1
Two 2-link heterogeneous networks with cooperative power control on the node level.Denote(1)
x
i
j
t
=
1
i
f
n
o
d
e
i
t
r
a
n
s
m
i
t
s
d
a
t
a
t
o
n
o
d
e
j
o
n
t
i
m
e
s
l
o
t
t
,
0
o
t
h
e
r
w
i
s
e
.As mentioned above, we consider scheduling in the time domain and thus once a time slot is used by node i for transmission to node j, this time slot cannot be used again by node i to transmit to a different node. That is,(2)
∑
j
∈
T
i
t
x
i
j
t
≤
1
.Denote byp
i
j
[
t
] the transmission power from node i to node j in time slot t. For transmission from node i to node j, a simple model for path attenuation loss g
i
j is(3)
g
i
j
=
d
i
j
-
n
,where d
i
j is the physical distance between nodes i and j and n is the path loss index. Similar to the assumption in [6], we assume data transmission from node i to node j is successful only if the received power at node j exceeds a threshold γ
T. Denote the transmission range at node i under p
i
j
[
t
] as R
T
(
p
i
j
[
t
]
). Then, based on g
i
j
R
T
(
p
i
j
[
t
]
)
≥
γ
T and (2), we can calculate the transmission range of this node as follows:(4)
R
T
p
i
j
t
=
p
i
j
t
γ
T
1
/
n
.Since the receiving node j must be physically within the transmission range of node i, we have(5)
d
i
j
≤
p
i
j
t
γ
T
1
/
n
.Similarly, we assume that interference is nonnegligible only if it exceeds a threshold, say γ
I at a receiver. Denote the interference range of node k (k
∈
N, k
≠
i) under p
k
h
[
t
] as R
I
(
p
k
h
[
t
]
), where h is the intended receiving node of transmitting node k. Similarly, we can obtain the interference range of node k as R
I
(
p
k
h
[
t
]
)
=
(
p
k
h
[
t
]
/
γ
I
)
1
/
n. Since the receiving node j must not fall in the interference range of any other node k that is transmitting in the same time slot, we have(6)
d
j
k
≥
p
k
h
t
γ
I
1
/
n
.Denote byR
T
m
a
x the maximum transmission range of a node when it transmits at full power P. Then, based on (4), we have R
T
m
a
x
=
R
T
(
P
)
=
(
P
/
γ
T
)
1
/
n. Thus, we have γ
T
=
P
/
(
R
T
m
a
x
)
n. Then, for a node transmitting at power p
i
j
[
t
]
∈
[
0
,
P
], its transmission range is (7)
R
T
p
i
j
t
=
p
i
j
t
γ
T
1
/
n
=
p
i
j
t
R
T
m
a
x
n
P
1
/
n
=
p
i
j
t
P
1
/
n
R
T
m
a
x
.Similarly, denote by R
I
m
a
x the maximum interference range of a node when it transmits at full power P. Then, following the same token, we have R
I
m
a
x
=
R
I
(
P
)
=
(
P
/
γ
I
)
1
/
n and γ
I
=
P
/
(
R
I
m
a
x
)
n. For a node transmitting at power p
i
j
[
t
]
∈
[
0
,
P
], its interference range is (8)
R
I
p
i
j
t
=
p
i
j
t
P
1
/
n
R
I
m
a
x
.Remember thatT
j
t denotes the set of nodes to which node can transmit on time slot t under full power P. More formally, we have T
i
t
=
{
j
:
d
i
j
≤
R
T
m
a
x
,
j
≠
i
,
t
∈
τ
}. Similarly, denote by I
j
t the set of nodes that can make interference on node j on time slot t under full power P; that is, I
i
t
=
k
:
d
j
k
≤
R
I
m
a
x
,
t
∈
τ. Note that the definitions of T
j
t and I
j
t are both based on full transmission power P. When power level p
i
j
[
t
] is below P, the corresponding transmission and interference ranges will be smaller. As a result, it is necessary to keep track of the set of nodes that fall in the transmission range and the set of nodes that can produce interference whenever transmission power changes at a node. From the two constraints (5) and (6) for successful transmission from node i to node j and (7) and (8), respectively, we have(9)
d
i
j
≤
R
T
p
i
j
t
=
p
i
j
t
P
1
/
n
R
T
m
a
x
,
(10)
d
j
k
≥
R
I
p
k
h
t
=
p
k
h
t
P
1
/
n
R
T
m
a
x
,
k
∈
I
j
t
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
.Based on the above two constraints, we have the following requirements for the transmission link i
→
j and interfering link k
→
h:(11)
p
i
j
t
∈
d
i
j
R
T
m
a
x
n
P
,
P
i
f
x
i
j
t
=
1
,
=
0
i
f
x
i
j
t
=
0
,
p
k
h
t
≤
d
k
j
R
I
m
a
x
n
P
i
f
x
i
j
t
=
1
,
P
i
f
x
i
j
t
=
0
,
k
∈
I
j
m
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
.Meanwhile, these requirements can also be rewritten as (12)
p
i
j
t
∈
d
i
j
R
T
m
a
x
n
P
x
i
j
t
,
P
x
i
j
t
,
p
k
h
t
≤
P
-
1
-
d
k
j
R
I
m
a
x
n
P
x
i
j
t
,
k
∈
I
j
m
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
.Additionally, for successful scheduling in time domain, the following two constraints must also hold:(a)
For a time slott
∈
τ that is available at node j, this time slot cannot be used for both transmission and receiving. That is, if time slot t is used at node j for transmission (or receiving), then it cannot be used for receiving (or transmission).
(b)
Similar to constraint (2) on transmission, node j cannot use the same time slot t to receive from two different nodes.Therein, (a) can be viewed as “self-interference” avoidance constraint where, at the same nodej, its transmission to another node h on time slot t interferes in its reception from node i on the same time slot. It turns out that the above two constraints are mathematicallyembedded in (12). That is, once (12) are satisfied, then both constraints (a) and (b) are satisfied. This result can be similarly proved with Lemma 1 [6].


## 2.2. Flow Routing and Link Capacity

We assume there is a set ofL
^
∪
L active user communication (unicast) sessions in the combined heterogeneous networks. Denote by s
(
l
) and d
(
l
) the source and destination nodes of session l
∈
L
^
∪
L and r
(
l
) the rate requirement (in b/s) of session l. We consider the most general case of multipath routing; that is, we allow flow splitting between a source node and its destination node.Mathematically, this can be easily modeled based on flow balance at each node. Denote byf
i
j
(
l
) the data rate on link (
i
,
j
) that is attributed to session l, where i
∈
N,  i
≠
d
(
l
),  j
∈
T
i
=
⋃
t
∈
τ
T
i
t,  j
≠
s
(
l
). If node i is the source node of session l, that is, i
≠
s
(
l
), then(13)
∑
j
∈
T
i
f
i
j
l
=
r
l
.If node i is an intermediate relay node for session l, that is, i
≠
s
(
l
) and i
≠
d
(
l
), then(14)
∑
j
∈
T
i
j
≠
s
l
f
i
j
l
=
∑
k
∈
T
i
k
≠
d
l
f
k
i
l
.If node i is the destination node of session l, that is, i
≠
d
(
l
), then(15)
∑
k
∈
T
i
f
k
i
l
=
r
l
.It can be easily verified that once (13) and (14) are satisfied, (15) must also be satisfied. As a result, it is sufficient to have (13) and (14) in the formulation.Except for the above flow balance equations at each nodei
∈
N for session l
∈
L
^
⁡
∪
L, the aggregated flow rates on each radio link cannot exceed this link’s capacity. Under p
i
j
[
t
], we have(16)
∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
≤
∑
t
=
1
τ
c
i
j
t
=
∑
t
=
1
τ
W
log
2
⁡
1
+
g
i
j
n
0
W
p
i
j
t
,where n
0 is the ambient Gaussian noise density and l
∈
L
^
∪
L.


## 3. Problem Formulation

In the two combined heterogeneous networks, our goal is to offer guaranteed support for all the sessions (each with a given rate requirement) while simultaneously minimizing the total power consumption of both networks, that is, a multiobjective optimization problem. Putting together the constraints and requirements discussed in this section, we have the following formulation:(17)
min
⁡
∑
i
∈
N
1
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
min
⁡
∑
i
∈
N
2
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
.


### 3.1. Discrete Levels of Transmission Powers

Transmission power is allowed to adjust between 0 andP so that we achieve power control. In practice, the transmission power should be tuned into a finite number of discrete levels from 0 to P. We introduce an integer parameter Q that represents the total number of power levels for discrete version of power control, to which a node can be adjusted, that is, 0
,
(
1
/
Q
)
P
,
(
2
/
Q
)
P
,
…
,
P
. Denote by q
i
j
[
t
]
∈
{
0,1
,
2
,
…
,
Q
} the integer power level for p
i
j
[
t
]; that is, p
i
j
[
t
]
=
(
q
i
j
t
/
Q
)
P. Then, (12) can be rewritten as follows:(18)
q
i
j
t
∈
d
i
j
R
T
m
a
x
n
Q
x
i
j
t
,
Q
x
i
j
t
,
q
k
h
t
≤
Q
-
1
-
d
k
j
R
I
m
a
x
n
Q
x
i
j
t
,
k
∈
I
j
t
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
,
∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
≤
∑
t
=
1
τ
W
log
2
⁡
1
+
g
i
j
n
0
W
p
i
j
t
.


### 3.2. Formulation

Combining the objective function with all the constraints for power control on the node level, scheduling, and flow routing, we have the following formulation:MO-MINLP:(19)
min
⁡
∑
i
∈
N
1
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
min
⁡
∑
i
∈
N
2
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
(20)
s.t.
∑
j
∈
T
i
t
x
i
j
t
≤
1
,
i
∈
N
,
t
∈
τ
,
(21)
q
i
j
t
-
d
i
j
R
T
m
a
x
n
Q
x
i
j
t
≥
0
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
i
,
(22)
q
i
j
t
-
Q
x
i
j
t
≤
0
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
,
(23)
q
k
h
t
≤
Q
-
1
-
d
k
j
R
I
m
a
x
n
Q
x
i
j
t
,
k
∈
I
j
t
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
,
(24)
∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
≤
∑
t
=
1
τ
W
log
2
⁡
1
+
g
i
j
n
0
W
p
i
j
t
,
i
∈
N
,
j
∈
T
i
t
,
l
∈
L
^
∪
L
,
(25)
∑
j
∈
T
i
f
i
j
l
=
r
l
,
i
≠
s
l
,
l
∈
L
^
∪
L
,
(26)
∑
j
∈
T
i
i
≠
s
l
,
d
l
,
j
≠
s
l
f
i
j
l
-
∑
k
∈
T
i
i
≠
s
l
,
d
l
,
k
≠
d
l
f
k
i
l
=
0
,
i
∈
N
,
l
∈
L
^
∪
L
,
(27)
x
i
j
t
∈
0,1
,
q
i
j
t
∈
0,1
,
2
,
…
,
Q
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
,
f
i
j
l
≥
0
,
i
∈
N
,
i
≠
d
l
,
j
∈
T
i
,
j
≠
s
l
,
l
∈
L
^
∪
L
,
whereW, g
i
j, R
T
m
a
x, R
I
m
a
x, P, n
0, τ, r
(
l
), and Q are all constants and x
i
j
[
t
], q
i
j
[
t
], and f
i
j
l are all optimization variables.This optimization problem is in the form of amultiobjective mixed-integer nonlinear program (MO-MINLP), which is NP-hard in general [19]. For the small discretized power level Q in our formulation, we can simply obtain exact results at these power levels with point-by-point calculation. However, if the power level Q is large or continuous and if not all the discretized power level is Pareto-optimal, it is necessary to adopt a piecewise linear approximation procedure since the computational amount for our approach with piecewise linear approximation with small segments is smaller than point-by-point calculation. Hence, in general, we develop a piecewise linearization procedure to transform the nonlinear constraint (24) into the linear one and analyze the approximation errors.


### 3.3. Reformulation and Approximation Error Analysis

In this section, for the nonlinearl
o
g term (24) in the constraint of MO-MINLP, we develop a piecewise linearization procedure [20–22], to transform it into linear term with guaranteed performance as shown in Figure 2. Note that whatever the value t selects from 1 to τ, we all have that p
i
j
L
[
t
]
=
0 and p
i
j
U
[
t
]
=
P are the same lower and upper bounds for p
i
j
[
t
], respectively. It is a similar case for c
i
j
[
t
] and q
i
j
[
t
]. Hence, for simplicity, we omit “[
t
]” term in p
i
j
[
t
], c
i
j
[
t
], and q
i
j
[
t
] and rewrite them as p
i
j, c
i
j, and q
i
j.Figure 2
An illustration of the maximum approximation errors for piecewise line segment.The goal of linear approximation ofc
i
j
=
W
log
2
⁡
(
1
+
(
g
i
j
/
n
0
W
)
p
i
j
) is to replace c
i
j
=
W
ln
⁡
1
+
g
i
j
/
n
0
W
p
i
j
/
ln
⁡
2 with a series of linear segments such that the difference between any point on c
i
j and its corresponding linear segment is within η. Based on η and the approach of linear segmentation, we can further find the difference between any point on p
i
j
=
n
0
W
(
e
ln
⁡
2
c
i
j
/
W
-
1
)
/
g
i
j and its corresponding linear segment is within ε.Although there are many approaches to find a linear approximation, we are only interested in a linear approximation with the minimum number of linear segments. Similar to an approach proposed in [23], we also adopt the piecewise linearization that optimally divides the intervals by finding an optimal slope of each segment to guarantee the given approximation error.DenoteK
i
j as the minimum number of line segments such that each segment meets the error requirements (i.e., η and ε). Denote by p
i
j
0
,
p
i
j
1
,
…
,
p
i
j
K
i
j values on the x-axis for the end points of these K
i
j segments, with p
i
j
0
=
p
i
j
L
=
0
,
…
,
p
i
j
k
,
…, and p
i
j
K
i
j
=
p
i
j
U
=
P.The minimum number of line segmentsK
i
j can be found with the following iterative process. We start from p
i
j
0 to calculate the slope of the first segment, which must ensure that this segment satisfies the error requirements η and ε. After finding this slope, we can find the right-side end point of the first segment. From this point, we repeat the same process for the second segment and so forth, until the last segment exceeds p
i
j
U.In particular, we denote slope of thekth linear segment as β
i
j
k; that is,(28)
β
i
j
k
=
c
i
j
k
-
c
i
j
k
-
1
p
i
j
k
-
p
i
j
k
-
1
.Denotey
i
j
k
(
p
i
j
) as the kth linear segment that approximates c
i
j. Then, we have(29)
y
i
j
k
p
i
j
=
β
i
j
k
p
i
j
-
p
i
j
k
-
1
+
c
i
j
k
-
1
,for p
i
j
k
-
1
≤
p
i
j
≤
p
i
j
k.Referring to Figure2, for any point p
i
j within the kth segment, we denote its approximation error as δ. Then, it is easy to see that the point on the tangential line (parallel to the linear segment) that intersects the l
o
g curve c
i
j has the maximum approximation error. Denote this maximum approximation error on the linear segment as δ
∗ and the x-coordinate of this point as p
i
j
∗. Then, we have(30)
δ
=
c
i
j
-
y
i
j
p
i
j
≤
max
p
ij
k
-
1
≤
p
ij
≤
p
ij
k
⁡
c
i
j
-
y
i
j
p
i
j
=
c
i
j
∗
-
y
i
j
p
i
j
∗
=
δ
∗
.Since the slope of tangential line (withδ
∗) for c
i
j is d
c
i
j
/
d
p
i
j
=
W
g
i
j
/
ln
⁡
2
(
n
0
W
+
g
i
j
p
i
j
), then β
i
j
k
=
W
g
i
j
/
ln
⁡
2
(
n
0
W
+
g
i
j
p
i
j
∗
) or p
i
j
∗
=
(
W
g
i
j
-
ln
⁡
2
β
i
j
k
n
0
W
)
/
ln
⁡
2
β
i
j
k
g
i
j, where β
i
j
k is the slope of the linear segment y
i
j
k
(
p
i
j
). The maximum approximation error δ
∗ for this linear segment can be calculated as follows:(31)
δ
∗
=
c
i
j
∗
-
y
i
j
p
i
j
∗
=
W
ln
⁡
2
ln
⁡
g
i
j
ln
⁡
2
n
0
β
i
j
k
-
β
i
j
k
W
ln
⁡
2
β
i
j
k
-
n
0
W
g
i
j
-
p
i
j
k
-
1
-
c
i
j
k
-
1
=
η
.Similarly, we can calculate the maximum approximation error of the linear segment to the curvep
i
j; that is, p
i
j
∗
-
y
i
j
-
1
(
c
i
j
∗
)
=
W
/
ln
⁡
2
β
i
j
k
ln
⁡
(
g
i
j
/
ln
⁡
2
n
0
β
i
j
k
)
-
(
W
/
ln
⁡
2
β
i
j
k
-
n
0
W
/
g
i
j
-
p
i
j
k
-
1
)
-
c
i
j
k
-
1
/
β
i
j
k
=
ε. Obviously, we can find that β
i
j
k
=
η
/
ε.Therefore, we have the following equation:(32)
W
ln
⁡
2
β
i
j
k
ln
⁡
g
i
j
ln
⁡
2
n
0
β
i
j
k
-
W
ln
⁡
2
β
i
j
k
-
n
0
W
g
i
j
-
p
i
j
k
-
1
-
c
i
j
k
-
1
β
i
j
k
-
ε
=
0
.For a given error boundε, the values of p
i
j
0
,
p
i
j
1
,
…
,
p
i
j
K
i
j and slopes β
i
j
1
,
β
i
j
2
,
…
,
β
i
j
K
i
j can be found iteratively through the following piecewise linearization algorithm:Initialization: setk
←
0 and p
i
j
k
←
p
i
j
L.
While (p
i
j
k
<
p
i
j
U) {
k
←
k
+
1
.
Find slopeβ
i
j
k of the kth segment based on (32).
Computep
i
j
k with β
i
j
k, via (28).
}
K
i
j
←
k and p
i
j
k
←
p
i
j
U.
Recalculateβ
i
j
K
i
j via (28).The values ofβ
i
j
k in (32) and p
i
j
k in (28) can be solved by numerical methods such as bisection method or Newton’s method as in [23].Lemma 1.
The maximum approximation error within each linear segment as defined by the method of piecewise linearization is no more thanη for the curve c
i
j and ε for the curve p
i
j.Proof.
The proof is based on the above construction. We omit its discussion here to conserve space.Through the piecewise linearization procedure, we can approximate thel
o
g term c
i
j with a series of linear segments, each with an approximation error no more than η. And the corresponding approximation error of the linear segment to the curve p
i
j is no more than ε. Since p
i
j
=
(
P
/
Q
)
q
i
j, the approximation error of the linear segment to the curve q
i
j is no more than ε
Q
/
P. Note that q
i
j is defined as an integer variable in our formulation. With the consideration of “round-off” operation or calculation for our formulation, if we set ε
Q
/
P
<
0.5, it can be guaranteed that the final optimal output of q
i
j is an integer without any approximation error to its true value. Hence, the final optimal value of objective function that is the sum of q
i
j
[
t
] for different i
,
j, and t can be guaranteed to be its true value without approximation error.For anyq
i
j
[
t
], denote y
i
j
(
q
i
j
[
t
]
) as the approximation of c
i
j
[
t
] on the linear segment. Then, the constraint ∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
-
∑
t
=
1
τ
W
l
o
g
2
(
1
+
(
g
i
j
P
/
n
0
W
Q
)
q
i
j
[
t
]
)
≤
0 in MO-MINLP can be replaced by the following linear constraints:(33)
∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
-
∑
t
=
1
τ
y
i
j
q
i
j
t
≤
0
,
i
∈
N
,
j
∈
T
i
t
,
l
∈
L
^
∪
L
,
y
i
j
q
i
j
t
≤
β
i
j
k
t
P
Q
q
i
j
t
-
p
i
j
k
-
1
t
+
c
i
j
k
-
1
t
,
k
=
1,2
,
…
,
K
i
j
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
.The original MO-MINLP is reformulated into a new optimization problem, which we denote as follows:MO-MILP:(34)
min
⁡
U
=
∑
i
∈
N
1
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
min
⁡
V
=
∑
i
∈
N
2
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
s.t.
constraints
((
20
)–(
23
))
,
((
25
)-(
26
))
,
33
,
x
i
j
t
∈
0,1
,
q
i
j
t
∈
0,1
,
2
,
…
,
Q
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
,
f
i
j
l
≥
0
,
i
∈
N
,
i
≠
d
l
,
j
∈
T
i
,
j
≠
s
l
,
l
∈
L
^
∪
L
,
whereW, g
i
j, R
T
m
a
x, R
I
m
a
x, P, n
0, τ, r
(
l
), β
i
j
k
[
t
], p
i
j
k
[
t
], c
i
j
k
[
t
], and Q are all constants and x
i
j
[
t
], q
i
j
[
t
], y
i
j
(
q
i
j
[
t
]
), and f
i
j
l are all optimization variables. It is in the form ofmultiobjective mixed-integer linear programming (MO-MILP), which remains NP-hard in general.


## 3.1. Discrete Levels of Transmission Powers

Transmission power is allowed to adjust between 0 andP so that we achieve power control. In practice, the transmission power should be tuned into a finite number of discrete levels from 0 to P. We introduce an integer parameter Q that represents the total number of power levels for discrete version of power control, to which a node can be adjusted, that is, 0
,
(
1
/
Q
)
P
,
(
2
/
Q
)
P
,
…
,
P
. Denote by q
i
j
[
t
]
∈
{
0,1
,
2
,
…
,
Q
} the integer power level for p
i
j
[
t
]; that is, p
i
j
[
t
]
=
(
q
i
j
t
/
Q
)
P. Then, (12) can be rewritten as follows:(18)
q
i
j
t
∈
d
i
j
R
T
m
a
x
n
Q
x
i
j
t
,
Q
x
i
j
t
,
q
k
h
t
≤
Q
-
1
-
d
k
j
R
I
m
a
x
n
Q
x
i
j
t
,
k
∈
I
j
t
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
,
∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
≤
∑
t
=
1
τ
W
log
2
⁡
1
+
g
i
j
n
0
W
p
i
j
t
.


## 3.2. Formulation

Combining the objective function with all the constraints for power control on the node level, scheduling, and flow routing, we have the following formulation:MO-MINLP:(19)
min
⁡
∑
i
∈
N
1
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
min
⁡
∑
i
∈
N
2
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
(20)
s.t.
∑
j
∈
T
i
t
x
i
j
t
≤
1
,
i
∈
N
,
t
∈
τ
,
(21)
q
i
j
t
-
d
i
j
R
T
m
a
x
n
Q
x
i
j
t
≥
0
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
i
,
(22)
q
i
j
t
-
Q
x
i
j
t
≤
0
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
,
(23)
q
k
h
t
≤
Q
-
1
-
d
k
j
R
I
m
a
x
n
Q
x
i
j
t
,
k
∈
I
j
t
,
k
≠
i
,
h
∈
T
k
t
,
t
∈
τ
,
(24)
∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
≤
∑
t
=
1
τ
W
log
2
⁡
1
+
g
i
j
n
0
W
p
i
j
t
,
i
∈
N
,
j
∈
T
i
t
,
l
∈
L
^
∪
L
,
(25)
∑
j
∈
T
i
f
i
j
l
=
r
l
,
i
≠
s
l
,
l
∈
L
^
∪
L
,
(26)
∑
j
∈
T
i
i
≠
s
l
,
d
l
,
j
≠
s
l
f
i
j
l
-
∑
k
∈
T
i
i
≠
s
l
,
d
l
,
k
≠
d
l
f
k
i
l
=
0
,
i
∈
N
,
l
∈
L
^
∪
L
,
(27)
x
i
j
t
∈
0,1
,
q
i
j
t
∈
0,1
,
2
,
…
,
Q
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
,
f
i
j
l
≥
0
,
i
∈
N
,
i
≠
d
l
,
j
∈
T
i
,
j
≠
s
l
,
l
∈
L
^
∪
L
,
whereW, g
i
j, R
T
m
a
x, R
I
m
a
x, P, n
0, τ, r
(
l
), and Q are all constants and x
i
j
[
t
], q
i
j
[
t
], and f
i
j
l are all optimization variables.This optimization problem is in the form of amultiobjective mixed-integer nonlinear program (MO-MINLP), which is NP-hard in general [19]. For the small discretized power level Q in our formulation, we can simply obtain exact results at these power levels with point-by-point calculation. However, if the power level Q is large or continuous and if not all the discretized power level is Pareto-optimal, it is necessary to adopt a piecewise linear approximation procedure since the computational amount for our approach with piecewise linear approximation with small segments is smaller than point-by-point calculation. Hence, in general, we develop a piecewise linearization procedure to transform the nonlinear constraint (24) into the linear one and analyze the approximation errors.


## 3.3. Reformulation and Approximation Error Analysis

In this section, for the nonlinearl
o
g term (24) in the constraint of MO-MINLP, we develop a piecewise linearization procedure [20–22], to transform it into linear term with guaranteed performance as shown in Figure 2. Note that whatever the value t selects from 1 to τ, we all have that p
i
j
L
[
t
]
=
0 and p
i
j
U
[
t
]
=
P are the same lower and upper bounds for p
i
j
[
t
], respectively. It is a similar case for c
i
j
[
t
] and q
i
j
[
t
]. Hence, for simplicity, we omit “[
t
]” term in p
i
j
[
t
], c
i
j
[
t
], and q
i
j
[
t
] and rewrite them as p
i
j, c
i
j, and q
i
j.Figure 2
An illustration of the maximum approximation errors for piecewise line segment.The goal of linear approximation ofc
i
j
=
W
log
2
⁡
(
1
+
(
g
i
j
/
n
0
W
)
p
i
j
) is to replace c
i
j
=
W
ln
⁡
1
+
g
i
j
/
n
0
W
p
i
j
/
ln
⁡
2 with a series of linear segments such that the difference between any point on c
i
j and its corresponding linear segment is within η. Based on η and the approach of linear segmentation, we can further find the difference between any point on p
i
j
=
n
0
W
(
e
ln
⁡
2
c
i
j
/
W
-
1
)
/
g
i
j and its corresponding linear segment is within ε.Although there are many approaches to find a linear approximation, we are only interested in a linear approximation with the minimum number of linear segments. Similar to an approach proposed in [23], we also adopt the piecewise linearization that optimally divides the intervals by finding an optimal slope of each segment to guarantee the given approximation error.DenoteK
i
j as the minimum number of line segments such that each segment meets the error requirements (i.e., η and ε). Denote by p
i
j
0
,
p
i
j
1
,
…
,
p
i
j
K
i
j values on the x-axis for the end points of these K
i
j segments, with p
i
j
0
=
p
i
j
L
=
0
,
…
,
p
i
j
k
,
…, and p
i
j
K
i
j
=
p
i
j
U
=
P.The minimum number of line segmentsK
i
j can be found with the following iterative process. We start from p
i
j
0 to calculate the slope of the first segment, which must ensure that this segment satisfies the error requirements η and ε. After finding this slope, we can find the right-side end point of the first segment. From this point, we repeat the same process for the second segment and so forth, until the last segment exceeds p
i
j
U.In particular, we denote slope of thekth linear segment as β
i
j
k; that is,(28)
β
i
j
k
=
c
i
j
k
-
c
i
j
k
-
1
p
i
j
k
-
p
i
j
k
-
1
.Denotey
i
j
k
(
p
i
j
) as the kth linear segment that approximates c
i
j. Then, we have(29)
y
i
j
k
p
i
j
=
β
i
j
k
p
i
j
-
p
i
j
k
-
1
+
c
i
j
k
-
1
,for p
i
j
k
-
1
≤
p
i
j
≤
p
i
j
k.Referring to Figure2, for any point p
i
j within the kth segment, we denote its approximation error as δ. Then, it is easy to see that the point on the tangential line (parallel to the linear segment) that intersects the l
o
g curve c
i
j has the maximum approximation error. Denote this maximum approximation error on the linear segment as δ
∗ and the x-coordinate of this point as p
i
j
∗. Then, we have(30)
δ
=
c
i
j
-
y
i
j
p
i
j
≤
max
p
ij
k
-
1
≤
p
ij
≤
p
ij
k
⁡
c
i
j
-
y
i
j
p
i
j
=
c
i
j
∗
-
y
i
j
p
i
j
∗
=
δ
∗
.Since the slope of tangential line (withδ
∗) for c
i
j is d
c
i
j
/
d
p
i
j
=
W
g
i
j
/
ln
⁡
2
(
n
0
W
+
g
i
j
p
i
j
), then β
i
j
k
=
W
g
i
j
/
ln
⁡
2
(
n
0
W
+
g
i
j
p
i
j
∗
) or p
i
j
∗
=
(
W
g
i
j
-
ln
⁡
2
β
i
j
k
n
0
W
)
/
ln
⁡
2
β
i
j
k
g
i
j, where β
i
j
k is the slope of the linear segment y
i
j
k
(
p
i
j
). The maximum approximation error δ
∗ for this linear segment can be calculated as follows:(31)
δ
∗
=
c
i
j
∗
-
y
i
j
p
i
j
∗
=
W
ln
⁡
2
ln
⁡
g
i
j
ln
⁡
2
n
0
β
i
j
k
-
β
i
j
k
W
ln
⁡
2
β
i
j
k
-
n
0
W
g
i
j
-
p
i
j
k
-
1
-
c
i
j
k
-
1
=
η
.Similarly, we can calculate the maximum approximation error of the linear segment to the curvep
i
j; that is, p
i
j
∗
-
y
i
j
-
1
(
c
i
j
∗
)
=
W
/
ln
⁡
2
β
i
j
k
ln
⁡
(
g
i
j
/
ln
⁡
2
n
0
β
i
j
k
)
-
(
W
/
ln
⁡
2
β
i
j
k
-
n
0
W
/
g
i
j
-
p
i
j
k
-
1
)
-
c
i
j
k
-
1
/
β
i
j
k
=
ε. Obviously, we can find that β
i
j
k
=
η
/
ε.Therefore, we have the following equation:(32)
W
ln
⁡
2
β
i
j
k
ln
⁡
g
i
j
ln
⁡
2
n
0
β
i
j
k
-
W
ln
⁡
2
β
i
j
k
-
n
0
W
g
i
j
-
p
i
j
k
-
1
-
c
i
j
k
-
1
β
i
j
k
-
ε
=
0
.For a given error boundε, the values of p
i
j
0
,
p
i
j
1
,
…
,
p
i
j
K
i
j and slopes β
i
j
1
,
β
i
j
2
,
…
,
β
i
j
K
i
j can be found iteratively through the following piecewise linearization algorithm:Initialization: setk
←
0 and p
i
j
k
←
p
i
j
L.
While (p
i
j
k
<
p
i
j
U) {
k
←
k
+
1
.
Find slopeβ
i
j
k of the kth segment based on (32).
Computep
i
j
k with β
i
j
k, via (28).
}
K
i
j
←
k and p
i
j
k
←
p
i
j
U.
Recalculateβ
i
j
K
i
j via (28).The values ofβ
i
j
k in (32) and p
i
j
k in (28) can be solved by numerical methods such as bisection method or Newton’s method as in [23].Lemma 1.
The maximum approximation error within each linear segment as defined by the method of piecewise linearization is no more thanη for the curve c
i
j and ε for the curve p
i
j.Proof.
The proof is based on the above construction. We omit its discussion here to conserve space.Through the piecewise linearization procedure, we can approximate thel
o
g term c
i
j with a series of linear segments, each with an approximation error no more than η. And the corresponding approximation error of the linear segment to the curve p
i
j is no more than ε. Since p
i
j
=
(
P
/
Q
)
q
i
j, the approximation error of the linear segment to the curve q
i
j is no more than ε
Q
/
P. Note that q
i
j is defined as an integer variable in our formulation. With the consideration of “round-off” operation or calculation for our formulation, if we set ε
Q
/
P
<
0.5, it can be guaranteed that the final optimal output of q
i
j is an integer without any approximation error to its true value. Hence, the final optimal value of objective function that is the sum of q
i
j
[
t
] for different i
,
j, and t can be guaranteed to be its true value without approximation error.For anyq
i
j
[
t
], denote y
i
j
(
q
i
j
[
t
]
) as the approximation of c
i
j
[
t
] on the linear segment. Then, the constraint ∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
-
∑
t
=
1
τ
W
l
o
g
2
(
1
+
(
g
i
j
P
/
n
0
W
Q
)
q
i
j
[
t
]
)
≤
0 in MO-MINLP can be replaced by the following linear constraints:(33)
∑
l
s
l
≠
j
,
d
l
≠
i
f
i
j
l
-
∑
t
=
1
τ
y
i
j
q
i
j
t
≤
0
,
i
∈
N
,
j
∈
T
i
t
,
l
∈
L
^
∪
L
,
y
i
j
q
i
j
t
≤
β
i
j
k
t
P
Q
q
i
j
t
-
p
i
j
k
-
1
t
+
c
i
j
k
-
1
t
,
k
=
1,2
,
…
,
K
i
j
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
.The original MO-MINLP is reformulated into a new optimization problem, which we denote as follows:MO-MILP:(34)
min
⁡
U
=
∑
i
∈
N
1
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
min
⁡
V
=
∑
i
∈
N
2
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
s.t.
constraints
((
20
)–(
23
))
,
((
25
)-(
26
))
,
33
,
x
i
j
t
∈
0,1
,
q
i
j
t
∈
0,1
,
2
,
…
,
Q
,
i
∈
N
,
j
∈
T
i
t
,
t
∈
τ
,
f
i
j
l
≥
0
,
i
∈
N
,
i
≠
d
l
,
j
∈
T
i
,
j
≠
s
l
,
l
∈
L
^
∪
L
,
whereW, g
i
j, R
T
m
a
x, R
I
m
a
x, P, n
0, τ, r
(
l
), β
i
j
k
[
t
], p
i
j
k
[
t
], c
i
j
k
[
t
], and Q are all constants and x
i
j
[
t
], q
i
j
[
t
], y
i
j
(
q
i
j
[
t
]
), and f
i
j
l are all optimization variables. It is in the form ofmultiobjective mixed-integer linear programming (MO-MILP), which remains NP-hard in general.


## 4. Pareto-Optimal Power Curve

### 4.1. Background

For the optimization problem MO-MILP, we want to minimize the power consumption with discretized power level in both heterogeneous networks. Since the two objective functions,U and V, are conflicting with each other, we pursuePareto-optimal solutions [19]. For ease of exposition, we define α
=
{
x
,
y
,
q
,
f
} as a feasible solution to MO-MILP, where x, y, q, and f represent the set of x
i
j
[
t
], y
i
j
(
q
i
j
[
t
]
), q
i
j
[
t
], and f
(
l
), for i
∈
N, j
∈
T
i
t, t
∈
τ, and l
∈
L
^
∪
L. For a feasible solution α, we denote U
(
α
) and V
(
α
) as(35)
U
α
=
∑
i
∈
N
1
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
V
α
=
∑
i
∈
N
2
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
.Then, MO-MILP can be rewritten as follows:MO-MILP:(36)
min
⁡
U
α
min
⁡
V
α
s.t.
α
=
x
,
y
,
q
,
f
,
constraints
((
20
)–(
23
))
,
((
25
)-(
26
))
,
33
and
35
.For a Pareto-optimal solutionα
†, the corresponding objective pair (
U
†
,
V
†
) is called aPareto-optimal point. For a Pareto-optimal point (
U
†
,
V
†
), there does not exist another feasible solution α with objective pair (
U
,
V
) such that U
≤
U
† and V
<
V
†, or U
<
U
† and V
≤
V
†. This means that it is impossible to further decrease any one objective while holding up the other. For a feasible solution α
∗ with corresponding objective pair (
U
∗
,
V
∗
), if there does not exist any other solution α with its objective pair (
U
,
V
) such that U
<
U
∗ and V
<
V
∗, then solution α
∗ is called aweakly Pareto-optimal solution and (
U
∗
,
V
∗
) is called aweakly Pareto-optimal point. From this definition, it is obvious that a Pareto-optimal point is also a weakly Pareto-optimal point, while a weakly Pareto-optimal point is not always Pareto-optimal.To find all the Pareto-optimal points for MO-MILP, we can combine the two objectives into a single criterion. In the standard weighed sum method, the objective is defined as a nonnegative linear combination of the two objective functions through a weight0
≤
λ
≤
1:(37)
min
⁡
λ
U
α
+
1
-
λ
V
α
.This method is the simplest approach and probably the most widely used classical method. Although it is simple to find a Pareto-optimal point for a given weight λ, it is difficult to findall Pareto-optimal points using this method. This is because there are an infinite number of λ values in [
0,1
] and it is impossible to check out all these values or Pareto-optimal points because the standard weighted-sum method cannot find nonconvex solutions [19].


### 4.2. Adaptive Weighted-Sum Algorithm

In order to overcome the drawbacks of standard weighted-sum method, we consider a new approach based on adaptive weighted-sum (AWS) method in [24–26], to effectively find the Pareto-optimal solutions, even the nonconvex solutions. AWS is a methodology that is capable of finding Pareto-optimal solutions by changing the weights adaptively. Different from standard weighted-sum method, the weight in AWS is not predetermined but evolves according to the nature of Pareto curve. By updating the weight adaptively, AWS focuses on unexplored regions where no solution is obtained by standard weighted-sum method. Therefore, it is able to extract new Pareto-optimal solutions in these regions and generate all the Pareto-optimal points to construct an optimal curve.Based on the adaptive weighted-sum method in [24–26], we propose a new adaptive weighted-sum algorithm which circumvents the two abovementioned power consumption minimization problems and can effectively solve multiobjective optimization problems that have nonconvex regions for minimum power curve.Our new adaptive weighted-sum algorithm is shown as follows.Step 1.
Normalize the objective functions in the objective space. Whenα
U
∗ is the optimal solution for the single-objective optimizations of U
(
α
) and α
V
∗ is the optimal solution for the single-objective optimizations of V
(
α
), the normalized objective functions U
-
(
α
) and V
-
(
α
) are obtained as(38)
U
-
α
=
U
α
-
U
I
=
U
α
-
U
α
U
∗
,
V
-
α
=
V
α
-
V
I
=
V
α
-
V
α
V
∗
,where (
U
I
,
V
I
) is defined as the ideal point. Hence, the MO-MILP can be transformed into the form ofmixed-integer linear program (MILP) as follows:MILP:(39)
min
⁡
λ
U
-
α
+
1
-
λ
V
-
α
,
s.t.
α
=
x
,
y
,
q
,
f
,
0
≤
λ
≤
1
,
constraints
((
20
)–(
23
))
,
((
25
)-(
26
))
,
33
,
35
,
37
,
38
.
Although a MILP remains NP-hard in general, we find that it can be solved by CPLEX.Step 2.
Perform multiobjective optimization by the standard weighted-sum approach with a small number of divisions,m
0, where the uniform step size of weight λ is satisfied with Δ
λ
=
1
/
m
0. The preliminary Pareto-optimal solutions are obtained.Step 3.
Compute the vertical distance, horizon distance, and the length between all the neighboring Pareto-optimal points(
U
†
,
V
†
). Delete overlapping points. It occurs often that several identical points are obtained when the standard weighted-sum method is used. Since U and V are both integer variables, we will adopt a larger number of divisions rather than m
0 in per-feasible region where the vertical distance and horizon distance between two neighbor points are both more than 1.Step 4.
Determine the number of further refinements in per-feasible region. That is, the longer the segment, the more the refinement needed. Decreasing the step size,Δ
λ, in Step 2 can help in achieving higher resolution of the segmented regions. We have Δ
λ
=
1
/
m
i
=
1
/
r
o
u
n
d
(
A
(
l
i
/
l
a
v
g
)
) for the ith segment, where m
i is the number of further refinements for the ith segment, l
i is the length of the ith segment, l
a
v
g is the average length of all the segments, and A is a constant of the algorithm. The function round rounds off to the nearest integer.Step 5.
Force additional inequality constraints and suboptimize by using the standard weighted-sum method in per-feasible region. This can be achieved by utilizing the step size,Δ
λ, in Step 4 and the distance between the Pareto-optimal points (
U
1
†
,
V
1
†
) and (
U
2
†
,
V
2
†
). Therein, we set the offset distances of U and V as δ
1
=
1 and δ
2
=
1, respectively, because U and V are both integer variables. Hence, we can restate the optimization problem in the following generic form for per-feasible region:MILP:(40)
min
⁡
λ
U
-
α
+
1
-
λ
V
-
α
,
s.t.
α
=
x
,
y
,
q
,
f
,
U
≤
U
2
†
-
δ
1
=
U
2
†
-
1
,
V
≤
V
1
†
-
δ
2
=
V
1
†
-
1
,
0
≤
λ
≤
1
,
constraints
((
20
)–(
23
))
,
((
25
)-(
26
))
,
33
,
35
,
37
,
38
.Step 6.
Similar to Step3, compute the vertical distance, horizon distance, and the length between all the new neighboring Pareto-optimal points (
U
†
,
V
†
) and delete overlapping points. If all the vertical distances or horizon distances between the neighboring points are equal to 1 or no new point can be found between any two neighboring Pareto-optimal points, the optimization procedure is terminated. Otherwise, go to Step 4 and iterate.


### 4.3. Construct a Minimum Power Curve

Through iterations, we can find a set of all Pareto-optimal points by the aid of adaptive sum algorithm above, which guarantees a minimum power curve with discretized power level to be constructed. By connecting two consecutive Pareto-optimal points with “¬”-shape line segments in the set, we can find the Pareto-optimal curve, that is, minimum power curve. Except for achieving the small power consumption for each heterogeneous network, minimum power curve with cooperative power control offers a complete landscape of necessary power for each of them. For the case of more heterogeneous networks coexistence, we can change the objectivemin
⁡
λ
U
(
α
)
+
(
1
-
λ
)
V
(
α
) in formula (37) into min
⁡
∑
i
λ
i
U
i
(
α
) with ∑
i
λ
i
=
1 and appropriately modify our algorithm to extend the proposed approach to more than two heterogeneous networks. Also, the pursued minimum power curve in our paper can be extended to minimum power surface in three heterogeneous networks or more complex multidimensional space models in multiple heterogeneous networks.


## 4.1. Background

For the optimization problem MO-MILP, we want to minimize the power consumption with discretized power level in both heterogeneous networks. Since the two objective functions,U and V, are conflicting with each other, we pursuePareto-optimal solutions [19]. For ease of exposition, we define α
=
{
x
,
y
,
q
,
f
} as a feasible solution to MO-MILP, where x, y, q, and f represent the set of x
i
j
[
t
], y
i
j
(
q
i
j
[
t
]
), q
i
j
[
t
], and f
(
l
), for i
∈
N, j
∈
T
i
t, t
∈
τ, and l
∈
L
^
∪
L. For a feasible solution α, we denote U
(
α
) and V
(
α
) as(35)
U
α
=
∑
i
∈
N
1
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
,
V
α
=
∑
i
∈
N
2
∑
j
∈
T
i
t
∑
t
∈
τ
p
i
j
t
.Then, MO-MILP can be rewritten as follows:MO-MILP:(36)
min
⁡
U
α
min
⁡
V
α
s.t.
α
=
x
,
y
,
q
,
f
,
constraints
((
20
)–(
23
))
,
((
25
)-(
26
))
,
33
and
35
.For a Pareto-optimal solutionα
†, the corresponding objective pair (
U
†
,
V
†
) is called aPareto-optimal point. For a Pareto-optimal point (
U
†
,
V
†
), there does not exist another feasible solution α with objective pair (
U
,
V
) such that U
≤
U
† and V
<
V
†, or U
<
U
† and V
≤
V
†. This means that it is impossible to further decrease any one objective while holding up the other. For a feasible solution α
∗ with corresponding objective pair (
U
∗
,
V
∗
), if there does not exist any other solution α with its objective pair (
U
,
V
) such that U
<
U
∗ and V
<
V
∗, then solution α
∗ is called aweakly Pareto-optimal solution and (
U
∗
,
V
∗
) is called aweakly Pareto-optimal point. From this definition, it is obvious that a Pareto-optimal point is also a weakly Pareto-optimal point, while a weakly Pareto-optimal point is not always Pareto-optimal.To find all the Pareto-optimal points for MO-MILP, we can combine the two objectives into a single criterion. In the standard weighed sum method, the objective is defined as a nonnegative linear combination of the two objective functions through a weight0
≤
λ
≤
1:(37)
min
⁡
λ
U
α
+
1
-
λ
V
α
.This method is the simplest approach and probably the most widely used classical method. Although it is simple to find a Pareto-optimal point for a given weight λ, it is difficult to findall Pareto-optimal points using this method. This is because there are an infinite number of λ values in [
0,1
] and it is impossible to check out all these values or Pareto-optimal points because the standard weighted-sum method cannot find nonconvex solutions [19].


## 4.2. Adaptive Weighted-Sum Algorithm

In order to overcome the drawbacks of standard weighted-sum method, we consider a new approach based on adaptive weighted-sum (AWS) method in [24–26], to effectively find the Pareto-optimal solutions, even the nonconvex solutions. AWS is a methodology that is capable of finding Pareto-optimal solutions by changing the weights adaptively. Different from standard weighted-sum method, the weight in AWS is not predetermined but evolves according to the nature of Pareto curve. By updating the weight adaptively, AWS focuses on unexplored regions where no solution is obtained by standard weighted-sum method. Therefore, it is able to extract new Pareto-optimal solutions in these regions and generate all the Pareto-optimal points to construct an optimal curve.Based on the adaptive weighted-sum method in [24–26], we propose a new adaptive weighted-sum algorithm which circumvents the two abovementioned power consumption minimization problems and can effectively solve multiobjective optimization problems that have nonconvex regions for minimum power curve.Our new adaptive weighted-sum algorithm is shown as follows.Step 1.
Normalize the objective functions in the objective space. Whenα
U
∗ is the optimal solution for the single-objective optimizations of U
(
α
) and α
V
∗ is the optimal solution for the single-objective optimizations of V
(
α
), the normalized objective functions U
-
(
α
) and V
-
(
α
) are obtained as(38)
U
-
α
=
U
α
-
U
I
=
U
α
-
U
α
U
∗
,
V
-
α
=
V
α
-
V
I
=
V
α
-
V
α
V
∗
,where (
U
I
,
V
I
) is defined as the ideal point. Hence, the MO-MILP can be transformed into the form ofmixed-integer linear program (MILP) as follows:MILP:(39)
min
⁡
λ
U
-
α
+
1
-
λ
V
-
α
,
s.t.
α
=
x
,
y
,
q
,
f
,
0
≤
λ
≤
1
,
constraints
((
20
)–(
23
))
,
((
25
)-(
26
))
,
33
,
35
,
37
,
38
.
Although a MILP remains NP-hard in general, we find that it can be solved by CPLEX.Step 2.
Perform multiobjective optimization by the standard weighted-sum approach with a small number of divisions,m
0, where the uniform step size of weight λ is satisfied with Δ
λ
=
1
/
m
0. The preliminary Pareto-optimal solutions are obtained.Step 3.
Compute the vertical distance, horizon distance, and the length between all the neighboring Pareto-optimal points(
U
†
,
V
†
). Delete overlapping points. It occurs often that several identical points are obtained when the standard weighted-sum method is used. Since U and V are both integer variables, we will adopt a larger number of divisions rather than m
0 in per-feasible region where the vertical distance and horizon distance between two neighbor points are both more than 1.Step 4.
Determine the number of further refinements in per-feasible region. That is, the longer the segment, the more the refinement needed. Decreasing the step size,Δ
λ, in Step 2 can help in achieving higher resolution of the segmented regions. We have Δ
λ
=
1
/
m
i
=
1
/
r
o
u
n
d
(
A
(
l
i
/
l
a
v
g
)
) for the ith segment, where m
i is the number of further refinements for the ith segment, l
i is the length of the ith segment, l
a
v
g is the average length of all the segments, and A is a constant of the algorithm. The function round rounds off to the nearest integer.Step 5.
Force additional inequality constraints and suboptimize by using the standard weighted-sum method in per-feasible region. This can be achieved by utilizing the step size,Δ
λ, in Step 4 and the distance between the Pareto-optimal points (
U
1
†
,
V
1
†
) and (
U
2
†
,
V
2
†
). Therein, we set the offset distances of U and V as δ
1
=
1 and δ
2
=
1, respectively, because U and V are both integer variables. Hence, we can restate the optimization problem in the following generic form for per-feasible region:MILP:(40)
min
⁡
λ
U
-
α
+
1
-
λ
V
-
α
,
s.t.
α
=
x
,
y
,
q
,
f
,
U
≤
U
2
†
-
δ
1
=
U
2
†
-
1
,
V
≤
V
1
†
-
δ
2
=
V
1
†
-
1
,
0
≤
λ
≤
1
,
constraints
((
20
)–(
23
))
,
((
25
)-(
26
))
,
33
,
35
,
37
,
38
.Step 6.
Similar to Step3, compute the vertical distance, horizon distance, and the length between all the new neighboring Pareto-optimal points (
U
†
,
V
†
) and delete overlapping points. If all the vertical distances or horizon distances between the neighboring points are equal to 1 or no new point can be found between any two neighboring Pareto-optimal points, the optimization procedure is terminated. Otherwise, go to Step 4 and iterate.


## 4.3. Construct a Minimum Power Curve

Through iterations, we can find a set of all Pareto-optimal points by the aid of adaptive sum algorithm above, which guarantees a minimum power curve with discretized power level to be constructed. By connecting two consecutive Pareto-optimal points with “¬”-shape line segments in the set, we can find the Pareto-optimal curve, that is, minimum power curve. Except for achieving the small power consumption for each heterogeneous network, minimum power curve with cooperative power control offers a complete landscape of necessary power for each of them. For the case of more heterogeneous networks coexistence, we can change the objectivemin
⁡
λ
U
(
α
)
+
(
1
-
λ
)
V
(
α
) in formula (37) into min
⁡
∑
i
λ
i
U
i
(
α
) with ∑
i
λ
i
=
1 and appropriately modify our algorithm to extend the proposed approach to more than two heterogeneous networks. Also, the pursued minimum power curve in our paper can be extended to minimum power surface in three heterogeneous networks or more complex multidimensional space models in multiple heterogeneous networks.


## 5. Numerical Results

### 5.1. Network Setting

In this section, we consider two randomly generated 10-node heterogeneous networks (i.e., Network 1 and Network 2) with each node located in a50
×
50 area. For ease of exposition, we normalize all units for distance, bandwidth, rate, and power with appropriate dimensions. An instance of network topology is given in Figure 4 with each node’s location randomly generated. Within this network, we assume there are 2 sessions for Network 1 and Network 2, respectively. The source node and destination node of each session are randomly selected and the rate of each session is 5. Table 1 specifies an instance of the source node, destination node, and rate requirement for the 4 sessions in the two heterogeneous networks. We assume there are τ
=
8 time slots in the combined networks and the frequency band has a bandwidth of W
=
10.Table 1
Source node, destination node, and rate requirement of the two heterogeneous networks’ session.
Network
Session
Source node
Destination node
Rate requirement
Network 1
L
^
=
1
F
9
F
4
5
L
^
=
2
F
6
F
10
5
Network 2
L
=
1
S
4
S
9
5
L
=
2
S
8
S
7
5Assume thatR
T
m
a
x
=
20, R
I
m
a
x
=
40, and the path loss index n
=
4. The threshold γ
T is assumed to be γ
T
=
n
0
W
=
10
n
0. Thus, we have γ
I
=
(
R
T
m
a
x
/
R
I
m
a
x
)
n
γ
T
=
(
10
/
16
)
γ
T
=
(
100
/
16
)
n
0 and the maximum transmission power P
=
(
R
T
m
a
x
)
n
γ
T
=
1.6
×
1
0
6
n
0. We assume the noise spectral density n
0
=
1
0
-
6 and the power level Q
=
5. We set ε
=
0.1, which guarantees that the approximation error of q
i
j
[
t
] is less than 0.5; that is, ε
Q
/
P
=
0.3125
<
0.5, for i
∈
N,  j
∈
T
i
t,  t
∈
τ. Hence, the final obtained q
i
j
[
t
], for i
∈
N,  j
∈
T
i
t,  t
∈
τ, should be its true integer value without approximation error by CPLEX. Further, the optimal objective value of U
(
α
) and V
(
α
), or the optimal objective value of combination of U
(
α
) and V
(
α
), which are the sum of q
i
j
[
t
], can be guaranteed to be its true value without approximation error.


### 5.2. Minimum Power Curve with Power Control

For the above network setting, we will apply our new adaptive weighted-sum algorithm to MO-MILP and find a sequence of Pareto-optimal points for power consumption of the two heterogeneous networks with discretized power level. We first set the weightλ
=
0,1, and we find the two end Pareto-optimal points as (
3,18
) and (
17,2
), respectively. Hence, we can obtain the ideal point (
3,2
). Through adaptive weighted-sum algorithm, we can iteratively find all Pareto-optimal points and construct a minimum power curve with cooperative power control as Figure 3 shows.Figure 3
Minimum power curve with cooperative power control for two heterogeneous networks (Q
=
5).Figure 4
Scenario of power control, scheduling, and routing for Pareto-optimal point(
14,4
).Considering a Pareto-optimal point(
14,4
) randomly selected on minimum power curve in Figure 3, we show the cross-layer scenario of power control, scheduling, and routing for it in Figure 4.For transmission power, we have the power levelq
i
j
[
t
] for Network 1 as follows: (41)
q
F
5
,
S
10
3
=
2
,
q
F
6
,
S
6
4
=
1
,
q
F
9
,
S
5
1
=
1
.And we have the power levelq
i
j
[
t
] for Network 2 as follows:(42)
q
S
1
,
F
5
2
=
1
,
q
S
4
,
S
1
4
=
1
,
q
S
4
,
F
4
1
=
1
,
q
S
5
,
S
8
8
=
3
,
q
S
6
,
F
10
8
=
1
,
q
S
8
,
S
1
6
=
2
,
q
S
8
,
S
4
7
=
2
,
q
S
10
,
S
7
7
=
1
,
q
S
10
,
S
9
5
=
2
.Hence, we can find thatV
(
α
†
)
=
q
F
5
,
S
10
[
3
]
+
q
F
6
,
S
6
[
4
]
+
q
F
9
,
S
5
[
1
]
=
4 and U
(
α
†
)
=
q
S
1
,
F
5
[
2
]
+
q
S
4
,
S
1
[
4
]
+
q
S
4
,
F
4
[
1
]
+
q
S
5
,
S
8
[
8
]
+
q
S
6
,
F
10
[
8
]
+
q
S
8
,
S
1
[
6
]
+
q
S
8
,
S
4
[
7
]
+
q
S
10
,
S
7
[
7
]
+
q
S
10
,
S
9
[
5
]
=
14. Obviously, we can find that the results coincide with our theoretical analysis and algorithm.For the scheduling, we have the results for Network 1 as follows:(43)
x
F
5
,
S
10
3
=
1
,
x
F
6
,
S
6
4
=
1
,
x
F
9
,
S
5
1
=
1
.And we have the results for Network 2 as follows:(44)
x
S
1
,
F
5
2
=
1
,
x
S
4
,
S
1
4
=
1
,
x
S
4
,
F
4
1
=
1
,
x
S
5
,
S
8
8
=
1
,
x
S
6
,
F
10
8
=
1
,
x
S
8
,
S
1
6
=
1
,
x
S
8
,
S
4
7
=
1
,
x
S
10
,
S
7
7
=
1
,
x
S
10
,
S
9
5
=
1
.For the flow routing topology shown in Figure4, we have the flow rates for Network 1 as follows: (45)
f
F
9
,
S
5
L
^
=
1
=
5
,
f
S
5
,
S
8
L
^
=
1
=
5
,
f
S
8
,
S
4
L
^
=
1
=
5
,
f
S
4
,
F
4
L
^
=
1
=
5
,
f
F
6
,
S
6
L
^
=
2
=
5
,
f
S
6
,
F
10
L
^
=
2
=
5
.And we have the flow rates for Network 2 as follows:(46)
f
S
4
,
S
1
L
=
1
=
5
,
f
S
1
,
F
5
L
=
1
=
5
,
f
F
5
,
S
10
L
=
1
=
5
,
f
S
10
,
S
9
L
=
1
=
5
,
f
S
8
,
S
1
L
=
2
=
5
,
f
S
1
,
F
5
L
=
2
=
5
,
f
F
5
,
S
10
L
=
2
=
5
,
f
S
10
,
S
7
L
=
2
=
5
.The flow rates are all satisfied with the rate requirements.


### 5.3. Comparison to Minimum Power Curve without Power Control

In this section, we set the power levelQ
=
1 and apply the new adaptive weighted-sum algorithm to find the Pareto-optimal points to construct another minimum power curve as shown in Figure 5, where Q
=
1 means that there is no cooperative power control in two heterogeneous networks. We also set Q
=
20 and construct the third minimum power curve as shown in Figure 6. Comparing the curves with Q
=
1,5
,
20 in Figure 7, we can find that the power consumption with Q
=
1 (i.e., without cooperative power control) is larger than the one with Q
=
5 and Q
=
20 (i.e., with cooperative power control). It shows that cooperative power control can save more energy than the case without power control for two heterogeneous networks. And the power consumption with Q
=
20 is smaller than the one with Q
=
5, which shows the impact of discretized power level on energy saving. And minimum power curve offers a complete landscape of necessary power for each heterogeneous multihop network.Figure 5
Minimum power curve without cooperative power control for two heterogeneous networks (Q
=
1).Figure 6
Minimum power curve with cooperative power control for two heterogeneous networks (Q
=
20).Figure 7
Comparison between minimum power curves with and without cooperative power control (Q
=
20, 5, and 1).


## 5.1. Network Setting

In this section, we consider two randomly generated 10-node heterogeneous networks (i.e., Network 1 and Network 2) with each node located in a50
×
50 area. For ease of exposition, we normalize all units for distance, bandwidth, rate, and power with appropriate dimensions. An instance of network topology is given in Figure 4 with each node’s location randomly generated. Within this network, we assume there are 2 sessions for Network 1 and Network 2, respectively. The source node and destination node of each session are randomly selected and the rate of each session is 5. Table 1 specifies an instance of the source node, destination node, and rate requirement for the 4 sessions in the two heterogeneous networks. We assume there are τ
=
8 time slots in the combined networks and the frequency band has a bandwidth of W
=
10.Table 1
Source node, destination node, and rate requirement of the two heterogeneous networks’ session.
Network
Session
Source node
Destination node
Rate requirement
Network 1
L
^
=
1
F
9
F
4
5
L
^
=
2
F
6
F
10
5
Network 2
L
=
1
S
4
S
9
5
L
=
2
S
8
S
7
5Assume thatR
T
m
a
x
=
20, R
I
m
a
x
=
40, and the path loss index n
=
4. The threshold γ
T is assumed to be γ
T
=
n
0
W
=
10
n
0. Thus, we have γ
I
=
(
R
T
m
a
x
/
R
I
m
a
x
)
n
γ
T
=
(
10
/
16
)
γ
T
=
(
100
/
16
)
n
0 and the maximum transmission power P
=
(
R
T
m
a
x
)
n
γ
T
=
1.6
×
1
0
6
n
0. We assume the noise spectral density n
0
=
1
0
-
6 and the power level Q
=
5. We set ε
=
0.1, which guarantees that the approximation error of q
i
j
[
t
] is less than 0.5; that is, ε
Q
/
P
=
0.3125
<
0.5, for i
∈
N,  j
∈
T
i
t,  t
∈
τ. Hence, the final obtained q
i
j
[
t
], for i
∈
N,  j
∈
T
i
t,  t
∈
τ, should be its true integer value without approximation error by CPLEX. Further, the optimal objective value of U
(
α
) and V
(
α
), or the optimal objective value of combination of U
(
α
) and V
(
α
), which are the sum of q
i
j
[
t
], can be guaranteed to be its true value without approximation error.


## 5.2. Minimum Power Curve with Power Control

For the above network setting, we will apply our new adaptive weighted-sum algorithm to MO-MILP and find a sequence of Pareto-optimal points for power consumption of the two heterogeneous networks with discretized power level. We first set the weightλ
=
0,1, and we find the two end Pareto-optimal points as (
3,18
) and (
17,2
), respectively. Hence, we can obtain the ideal point (
3,2
). Through adaptive weighted-sum algorithm, we can iteratively find all Pareto-optimal points and construct a minimum power curve with cooperative power control as Figure 3 shows.Figure 3
Minimum power curve with cooperative power control for two heterogeneous networks (Q
=
5).Figure 4
Scenario of power control, scheduling, and routing for Pareto-optimal point(
14,4
).Considering a Pareto-optimal point(
14,4
) randomly selected on minimum power curve in Figure 3, we show the cross-layer scenario of power control, scheduling, and routing for it in Figure 4.For transmission power, we have the power levelq
i
j
[
t
] for Network 1 as follows: (41)
q
F
5
,
S
10
3
=
2
,
q
F
6
,
S
6
4
=
1
,
q
F
9
,
S
5
1
=
1
.And we have the power levelq
i
j
[
t
] for Network 2 as follows:(42)
q
S
1
,
F
5
2
=
1
,
q
S
4
,
S
1
4
=
1
,
q
S
4
,
F
4
1
=
1
,
q
S
5
,
S
8
8
=
3
,
q
S
6
,
F
10
8
=
1
,
q
S
8
,
S
1
6
=
2
,
q
S
8
,
S
4
7
=
2
,
q
S
10
,
S
7
7
=
1
,
q
S
10
,
S
9
5
=
2
.Hence, we can find thatV
(
α
†
)
=
q
F
5
,
S
10
[
3
]
+
q
F
6
,
S
6
[
4
]
+
q
F
9
,
S
5
[
1
]
=
4 and U
(
α
†
)
=
q
S
1
,
F
5
[
2
]
+
q
S
4
,
S
1
[
4
]
+
q
S
4
,
F
4
[
1
]
+
q
S
5
,
S
8
[
8
]
+
q
S
6
,
F
10
[
8
]
+
q
S
8
,
S
1
[
6
]
+
q
S
8
,
S
4
[
7
]
+
q
S
10
,
S
7
[
7
]
+
q
S
10
,
S
9
[
5
]
=
14. Obviously, we can find that the results coincide with our theoretical analysis and algorithm.For the scheduling, we have the results for Network 1 as follows:(43)
x
F
5
,
S
10
3
=
1
,
x
F
6
,
S
6
4
=
1
,
x
F
9
,
S
5
1
=
1
.And we have the results for Network 2 as follows:(44)
x
S
1
,
F
5
2
=
1
,
x
S
4
,
S
1
4
=
1
,
x
S
4
,
F
4
1
=
1
,
x
S
5
,
S
8
8
=
1
,
x
S
6
,
F
10
8
=
1
,
x
S
8
,
S
1
6
=
1
,
x
S
8
,
S
4
7
=
1
,
x
S
10
,
S
7
7
=
1
,
x
S
10
,
S
9
5
=
1
.For the flow routing topology shown in Figure4, we have the flow rates for Network 1 as follows: (45)
f
F
9
,
S
5
L
^
=
1
=
5
,
f
S
5
,
S
8
L
^
=
1
=
5
,
f
S
8
,
S
4
L
^
=
1
=
5
,
f
S
4
,
F
4
L
^
=
1
=
5
,
f
F
6
,
S
6
L
^
=
2
=
5
,
f
S
6
,
F
10
L
^
=
2
=
5
.And we have the flow rates for Network 2 as follows:(46)
f
S
4
,
S
1
L
=
1
=
5
,
f
S
1
,
F
5
L
=
1
=
5
,
f
F
5
,
S
10
L
=
1
=
5
,
f
S
10
,
S
9
L
=
1
=
5
,
f
S
8
,
S
1
L
=
2
=
5
,
f
S
1
,
F
5
L
=
2
=
5
,
f
F
5
,
S
10
L
=
2
=
5
,
f
S
10
,
S
7
L
=
2
=
5
.The flow rates are all satisfied with the rate requirements.


## 5.3. Comparison to Minimum Power Curve without Power Control

In this section, we set the power levelQ
=
1 and apply the new adaptive weighted-sum algorithm to find the Pareto-optimal points to construct another minimum power curve as shown in Figure 5, where Q
=
1 means that there is no cooperative power control in two heterogeneous networks. We also set Q
=
20 and construct the third minimum power curve as shown in Figure 6. Comparing the curves with Q
=
1,5
,
20 in Figure 7, we can find that the power consumption with Q
=
1 (i.e., without cooperative power control) is larger than the one with Q
=
5 and Q
=
20 (i.e., with cooperative power control). It shows that cooperative power control can save more energy than the case without power control for two heterogeneous networks. And the power consumption with Q
=
20 is smaller than the one with Q
=
5, which shows the impact of discretized power level on energy saving. And minimum power curve offers a complete landscape of necessary power for each heterogeneous multihop network.Figure 5
Minimum power curve without cooperative power control for two heterogeneous networks (Q
=
1).Figure 6
Minimum power curve with cooperative power control for two heterogeneous networks (Q
=
20).Figure 7
Comparison between minimum power curves with and without cooperative power control (Q
=
20, 5, and 1).


## 6. Conclusions

In this paper, we explored the optimal power curve with discretized power level for multiple heterogeneous multihop networks. The curve addresses the minimum power consumption for two heterogeneous multihop networks. We formulated a multiobjective optimization problem based on power control on node level and developed a novel approach based on adaptive weighted-sum method. Our approach is able to find a set of all Pareto-optimal points through the iterations. We further showed that the power curve (by connecting two consecutive Pareto-optimal points via “¬”-shape line segments) is optimal with discretized power level. Using numerical results, we demonstrate that the power region (the area under the power curve) with power control is substantially smaller than that without cooperative power control. In addition to demonstrating the small power consumption with cooperative power control, minimum power curve offers a complete landscape of necessary power for each heterogeneous multihop network.



---

*Source: 9720256-2016-05-16.xml*