# Cross-Layer Control with Worst Case Delay Guarantees in Multihop Wireless Networks

Authors: Shu Fan; Honglin Zhao
Journal: Journal of Electrical and Computer Engineering
 (2016)

---

## Abstract

The delay guarantee is a challenge to meet different real-time requirements in applications of backpressure-based wireless multihop networks, and therefore, researchers are interested in the possibility of providing bounded end-to-end delay. In this paper, a new cross-layer control algorithm with worst case delay guarantees is proposed. The utility maximization algorithm is developed using a Lyapunov optimization framework. Virtual queues that ensure the worst case delay of nondropped packets are designed. It is proved through rigorous theoretical analyses and verified by simulations that the time average overall utility achieved by the new algorithm can be arbitrarily close to the optimal solution with finite queue backlogs. The simulation results evaluated with Matlab show that the proposed algorithm achieves higher throughput utility with fewer data dropped compared with the existing work.


---

## Body

## 1. Introduction

With the exponential increase in wireless multihop networks in the last two decades, increasingly sophisticated approaches that target resource allocation, congestion control, routing, and scheduling have been developed. Among the various policies that have been developed, the backpressure scheduling/routing policy, which was first proposed in the seminal work by Tassiulas and Ephremides [1], is a promising scheme because of its optimal throughput characteristic. Cross-layer algorithms that provide throughput utility optimal operation guarantees for different network structures can be designed by applying the Lyapunov optimization technique and by combining the backpressure scheme with flow control [2]. The flow controller at the transport layer ensures that the admitted rate injected into the network layer lies within the network capacity region. In recent works, spectrum sharing and pricing mechanisms [3], energy management [4], and social selfishness of users [5] have been considered in backpressure-based cross-layer algorithms. Cross-layer algorithms have also been combined with MAC (Media Access Control) layer [6], TCP (Transmission Control Protocol) layer [7], and application layers [8].Besides throughput utility, end-to-end delay is another important long-term performance metric of the backpressure style algorithms, and it is crucial to many essential applications. As applications with real-time requirements are being developed, it is necessary to design backpressure-based algorithms that provide bounded worst case delay guarantees. Backpressure algorithms usually bear poor delay performance mainly attributed to the following three reasons. First, the slow startup process to form a stable queue backlog gradient from the source to the destination causes large initial end-to-end delay. Second, unnecessarily long or looped paths form owing to the fluctuation of the queue backlog. Finally, the absence of consistent backpressure towards the destination can cause large latency in networks with short-lived or low-rate flows. In [9], average delay bounds are derived for one-hop wireless networks using maximal scheduling. In [10], the delay bounds in wireless ad hoc networks are studied using backpressure scheduling with either one-hop or multihop traffic flows. In [11], the authors propose a cross-layer algorithm providing average end-to-end delay guarantees. These prior works can only provide bounds on the overall average delay via Little’s Theorem, except for individual sessions. There are several works aiming to reduce end-to-end delay for individual sessions. In [12], a virtual queue-based gradient is established for nodes. In [13], the authors develop a delay-aware cross-layer algorithm using a novel link-rate allocation strategy and a regulated scheduling policy. A hop-count based queuing structure is used in [14] to provide a worst case hop count to the destination. However, these works fail to provide explicit end-to-end delay guarantees. Deterministic worst case delay guarantees are derived from the algorithm in [15] which uses explicit delay information from the head-of-line packet at each queue in one-hop networks. Considering both one-hop and multihop wireless networks, [16] designs an opportunistic scheduling scheme that guarantees a bounded worst case delay for each session. Our paper is mostly related to the study in [16]. However, different from [16], our algorithm consists of two phases and the persistent service virtual queue [16] is redesigned.The key contributions of this paper can be summarized as follows.(i)
The paper proposes a two-phase algorithm which can provide a bound on the worst case end-to-end delay of individual sessions by designing a novel virtual delay queue structure.
(ii)
By transforming the stochastic control problem into a deterministic optimization problem using the Lyapunov drift-plus-penalty technique, we design a joint congestion control, routing, and scheduling algorithm.
(iii)
The performance in terms of utility optimality and network stability of the algorithm is demonstrated with rigorous theoretical analyses. It is shown that the proposed algorithm can achieve a time average throughput utility that can be arbitrarily close to the optimal value, with queue backlogs being bounded by constants.The remainder of this paper is organized as follows. Section2 introduces the system model and problem formulation. In Section 3, the algorithm is designed using Lyapunov optimization. The performance analyses of the proposed algorithm are presented in Section 4. The simulation results are given in Section 5. Conclusions are provided in Section 6.


## 2. Network Model and Problem Formulation

### 2.1. Network Model

Consider a multihop wireless network consisting of several nodes. Let the network be modeled by a directed connectivity graphG
(
N
,
L
), where N is the set of nodes and (
i
,
j
)
∈
L represents a unidirectional wireless link between node i and node j which is in the transmission range of i. Let M be the set of unicast sessions m between source-destination pairs in the network. N
s is the set of source nodes s
m and N
d is the set of destination nodes d
m of session m. Packets from the source node traverse multiple wireless hops before arriving at the destination node.The system is assumed to run in a time-slotted fashion. Nodes in the network communicate using only one channel.a
n
j
(
t
)
∈
{
0,1
} is used to indicate whether link (
n
,
j
) is used to transmit packets in time slot t. a
n
j
(
t
)
=
1 implies that the link is scheduled. In this model, scheduling is subjected to the following constraints:(1)
∑
j
:
n
,
j
∈
L
α
n
j
t
+
∑
i
:
i
,
n
∈
L
α
i
n
t
≤
1
,
(2)
α
n
j
t
+
∑
k
∈
N
∑
l
α
k
l
t
≤
1
,where node l is in the transmission range of n and O
(
n
) denotes the set of nodes with (
n
,
i
)
∈
L. I
(
n
) denotes the set of nodes with (
j
,
n
)
∈
L. Constraint (1) implies that each node is equipped with only one radio, and thus, it can either transmit or receive data at any given time. Constraint (2) states that a node transmitting packets will interfere with the data receptions of the nodes in its transmission range.


### 2.2. Virtual Queue at the Transport Layer

A
m
t
∈
[
0
,
A
m
a
x
m
] denotes the arrival rate of session m injected into the transport layer from the application layer at the source node and A
m
a
x
m is the maximum arrival rate of session m. r
m
t
∈
0
,
A
m
t is the admitted rate of session m injected into the network layer. η
m
t
∈
0
,
A
m
a
x
m is an auxiliary variable known as the virtual input rate. The virtual queue at the transport layer of source node s
m of session m is denoted by Y
m that is updated as follows:(3)
Y
m
t
+
1
=
max
⁡
Y
m
t
-
r
m
t
,
0
+
η
m
t
.If each virtual queue Y
m is guaranteed to be stable, according to the necessity and sufficiency for queue stability [17], it is apparent that η
m
-
≤
r
m
-, where the time average value of time-varying variable x
(
t
) is denoted by x
-
=
lim
t
→
∞
⁡
1
/
t
∑
τ
=
0
t
-
1
E
(
x
(
τ
)
). Therefore, the lower bound of r
m
- can be derived from η
m
- which can be calculated.


### 2.3. Data Queue at the Network Layer

The data backlog queue for sessionm at the network layer of node n is denoted by Q
n
m
(
t
). In each slot t, the queue is updated as(4)
Q
n
m
t
+
1
=
max
⁡
Q
n
m
t
-
∑
i
∈
O
n
μ
n
i
m
t
-
D
n
m
t
,
0
+
∑
j
∈
I
n
μ
j
n
m
t
+
1
n
=
s
m
r
m
t
,where μ
n
i
m
(
t
) is the amount of data of session m to be forwarded from node n to i in time slot t. 1
{
n
=
s
m
} is an indicator function that denotes 1 if n
=
s
m and 0 otherwise. In addition, ∑
m
∈
M
μ
n
i
m
(
t
) must not be greater than μ
n
m
a
x
,
o
u
t. D
n
m
∈
[
0
,
D
m
a
x
] represents the number of packets of session m that are dropped by node n in slot t. The optimization of μ
n
i
m
(
t
) is the routing decision. As assumed in [18], in this paper, the transmission capacity of any link is set to be 1. Therefore, μ
n
i
m
(
t
) is either 0 or 1, and it can not be greater than Q
n
m
t, which is denoted as (5)
μ
n
i
m
t
∈
0
,
min
⁡
Q
n
m
t
,
1
,
∀
n
,
i
∈
L
,
n
≠
d
m
,
m
∈
M
,and ∑
m
∈
M
μ
n
i
m
(
t
)
=
α
n
i
(
t
), ∀
(
n
,
i
)
∈
L, can also be derived. The actual amount of packets of session m dropped in slot t can be defined as (6)
D
n
m
~
t
=
min
⁡
Q
n
m
t
-
μ
n
m
t
,
D
n
m
t
.


### 2.4. Persistent Service Virtual Queue

Theϵ-persistent service queue designed in [16] can ensure bounded worst case delay for general types of utility functions. We denote this queue by G
n
(
m
), and in each slot, the queue is updated as(7)
G
n
m
t
+
1
=
max
⁡
G
n
m
t
+
1
Q
n
m
t
>
0
·
ϵ
-
∑
i
∈
O
n
μ
n
i
m
t
-
D
n
m
t
-
1
Q
n
m
t
=
0
·
μ
n
m
a
x
,
o
u
t
,
0
.From the algorithm in [16] we find that G
n
(
m
) is used in decision of resource allocation and packet dropping. Since in most slots Q
n
m
t
>
0, G
n
(
m
) may increase fast. According to the packet drop decision algorithm, high value of ϵ-persistent service queue leads to serious packets drop. Therefore, the fast increase of G
n
(
m
) leads to dropping of packets and this results in a significant drop in throughput utility.In this paper, we redesign theϵ-persistent service queue that is denoted by Z
n
(
m
). In each slot t, the queue is updated as(8)
Z
n
m
t
+
1
=
max
⁡
Z
n
m
t
+
ϵ
1
·
1
Q
n
m
t
>
Q
n
,
s
t
a
n
d
a
r
d
m
+
ϵ
2
·
1
Q
n
m
t
≤
Q
n
,
s
t
a
n
d
a
r
d
m
-
D
n
m
t
-
∑
i
∈
O
n
μ
n
i
m
t
,
0
,where ϵ
1
>
ϵ
2
>
0. ϵ
1 and ϵ
2 are constants. Q
n
,
s
t
a
n
d
a
r
d
(
m
) is a constant value that is calculated in phase I of the algorithm which will be given in Section 3. Initial backlog Z
n
(
m
)
(
0
) is supposed to be 0.Q
n
,
s
t
a
n
d
a
r
d
(
m
) is the time average of length of queue of session m in node n. According to (8), Z
n
(
m
) increases fast only when Q
n
m
(
t
)
>
Q
n
,
s
t
a
n
d
a
r
d
(
m
), and thus Z
n
(
m
) should grow slower than G
n
(
m
). According to the packet drop decision algorithm, the number of packets dropped in our new algorithm should decrease and throughput should increase, compared with the algorithm in [16].Any algorithm that maintains boundedQ
n
m
t and Z
n
(
m
)
(
t
) ensures persistent service with bounded worst case delay, as shown in Theorem 1.Theorem 1 (worst case delay).
For all time slotst
∈
{
0,1
,
2
,
…
} and all sessions m
∈
M, suppose that the algorithm can ensure(9)
Q
n
m
t
≤
Q
n
m
,
max
⁡
,
Z
n
m
t
≤
Z
n
m
,
max
⁡
,where Q
n
m
,max and Z
n
m
,
max
⁡ are finite upper bounds for Q
n
m
t and Z
n
m
(
t
), respectively. Assuming First Input First Output (FIFO) service, the worst case delay of the nondropped data at node n is bounded by the constant W
n
m
,
max
⁡, which is given as(10)
W
n
m
,
max
⁡
=
Q
n
m
,
max
⁡
+
Z
n
m
,
max
⁡
ϵ
2
,where x denotes the smallest integer that is greater than or equal to x.Proof.
Fix any slott
≥
0, and let A
n
(
m
)
(
t
) represent the data that arrives at queue Q
n
(
m
) on slot t. As the service is FIFO, the data A
n
(
m
)
(
t
) is placed at the end of the queue Q
n
(
m
) on slot t
+
1. We want to prove that all of the data A
n
(
m
)
(
t
) departs queue Q
n
(
m
) on or before slot t
+
W
n
m
,
m
a
x. We prove this in three cases.
Case  1. If Q
n
m
(
τ
)
>
Q
n
,
s
t
a
n
d
a
r
d
(
m
) for all τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
}, the following can be derived(11)
Z
n
m
τ
+
1
≥
Z
n
m
τ
+
ϵ
1
-
∑
i
∈
O
n
μ
n
i
m
τ
-
D
n
m
τ
.Summing the above over τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
} yields(12)
Z
n
m
t
+
1
+
W
n
m
,
m
a
x
-
Z
n
m
t
+
1
≥
ϵ
1
·
W
n
m
,
m
a
x
-
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.For Z
n
m
t
+
1
+
W
n
m
,
m
a
x
≤
Z
n
m
,
m
a
x, (12) can be rearranged to yield(13)
ϵ
1
·
W
n
m
,
m
a
x
-
Z
n
m
,
m
a
x
≤
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.According to (10), W
n
m
,
m
a
x is the smallest integer that is greater than or equal to (
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
)
/
ϵ
2. Therefore, we can get W
n
m
,
m
a
x
≥
(
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
)
/
ϵ
2, and we can derive(14)
ϵ
1
·
W
n
m
,
m
a
x
-
Z
n
m
,
m
a
x
≥
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
-
Z
n
m
,
m
a
x
=
Q
n
m
,
m
a
x
.Then, the following can be derived:(15)
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
≥
Q
n
m
,
m
a
x
≥
Q
n
m
t
+
1
.Equation (15) means that all the data in queue Q
n
m on slot t
+
1 (including all of the data A
n
(
m
)
(
t
) which arrives at Q
n
m on slot t) can depart the queue on or before the slot t
+
W
n
m
,
m
a
x. Therefore, in the condition of Q
n
m
(
τ
)
>
Q
n
,
s
t
a
n
d
a
r
d
(
m
) for all τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
}, the worst case delay of nondropped data at node n is bounded by (16)
W
n
,
C
a
s
e
1
m
,
m
a
x
=
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
ϵ
2
.
Case  2. If Q
n
m
(
τ
)
≤
Q
n
,
s
t
a
n
d
a
r
d
(
m
) for all τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
}, the following can be derived:(17)
Z
n
m
t
+
1
+
W
n
m
,
m
a
x
-
Z
n
m
t
+
1
≥
ϵ
2
·
W
n
m
,
m
a
x
-
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.Similar to Case  1, the bound of the worst case delay of nondropped data at node n in Case  2 is derived as(18)
W
n
,
C
a
s
e
2
m
,
m
a
x
=
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
ϵ
2
.
Case  3. If Q
n
m
(
τ
)
>
Q
n
,
s
t
a
n
d
a
r
d
(
m
) in n
1 slots of τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
} and Q
n
m
(
τ
)
≤
Q
n
,
s
t
a
n
d
a
r
d
(
m
) in n
2 slots of τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
} and if we also have n
1
+
n
2
=
W
n
m
,
m
a
x, the following can be derived:(19)
Z
n
m
t
+
1
+
W
n
m
,
m
a
x
-
Z
n
m
t
+
1
≥
ϵ
1
·
n
1
+
ϵ
2
·
n
2
-
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.Let ϵ
∗
=
(
ϵ
1
·
n
1
+
ϵ
2
·
n
2
)
/
W
n
m
,
m
a
x; we can get(20)
Z
n
m
t
+
1
+
W
n
m
,
m
a
x
-
Z
n
m
t
+
1
≥
ϵ
∗
·
W
n
m
,
m
a
x
-
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.It is easy to derive ϵ
2
<
ϵ
∗
<
ϵ
1. Similar to Case  1, the bound of the worst case delay of nondropped data at node n in Case  3 is(21)
W
n
,
C
a
s
e
3
m
,
m
a
x
=
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
ϵ
2
.Considering the three cases above, the worst case delay of the nondropped data at node n is bounded by the constant W
n
m
,
m
a
x, which is given as(22)
W
n
m
,
m
a
x
=
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
ϵ
2
.


### 2.5. Throughput Utility Optimization Problem

Similar to the design of the utility function in [16], let U
m
(
·
) be strictly concave, twice differentiable, and nondecreasing utility function with U
m
(
0
)
=
0. r
-
=
(
r
m
-
,
m
∈
M
) denotes the throughput of the network. Λ is the capacity region of the network [17]. Then, the throughput utility maximization problem P
1 can be defined as follows:(23)
m
a
x
∑
m
∈
M
U
m
r
m
-
-
∑
m
∈
M
∑
n
∈
N
β
m
d
n
m
-
,
(24)
s
.
t
.
r
-
∈
Λ
,
(25)
1
,
2
,
5
,where d
n
(
m
)
- is the time average value of D
n
m
(
t
). β
m is the maximum slope of the utility function U
m
(
x
). Constraint (24) means that the network stability is guaranteed.


## 2.1. Network Model

Consider a multihop wireless network consisting of several nodes. Let the network be modeled by a directed connectivity graphG
(
N
,
L
), where N is the set of nodes and (
i
,
j
)
∈
L represents a unidirectional wireless link between node i and node j which is in the transmission range of i. Let M be the set of unicast sessions m between source-destination pairs in the network. N
s is the set of source nodes s
m and N
d is the set of destination nodes d
m of session m. Packets from the source node traverse multiple wireless hops before arriving at the destination node.The system is assumed to run in a time-slotted fashion. Nodes in the network communicate using only one channel.a
n
j
(
t
)
∈
{
0,1
} is used to indicate whether link (
n
,
j
) is used to transmit packets in time slot t. a
n
j
(
t
)
=
1 implies that the link is scheduled. In this model, scheduling is subjected to the following constraints:(1)
∑
j
:
n
,
j
∈
L
α
n
j
t
+
∑
i
:
i
,
n
∈
L
α
i
n
t
≤
1
,
(2)
α
n
j
t
+
∑
k
∈
N
∑
l
α
k
l
t
≤
1
,where node l is in the transmission range of n and O
(
n
) denotes the set of nodes with (
n
,
i
)
∈
L. I
(
n
) denotes the set of nodes with (
j
,
n
)
∈
L. Constraint (1) implies that each node is equipped with only one radio, and thus, it can either transmit or receive data at any given time. Constraint (2) states that a node transmitting packets will interfere with the data receptions of the nodes in its transmission range.


## 2.2. Virtual Queue at the Transport Layer

A
m
t
∈
[
0
,
A
m
a
x
m
] denotes the arrival rate of session m injected into the transport layer from the application layer at the source node and A
m
a
x
m is the maximum arrival rate of session m. r
m
t
∈
0
,
A
m
t is the admitted rate of session m injected into the network layer. η
m
t
∈
0
,
A
m
a
x
m is an auxiliary variable known as the virtual input rate. The virtual queue at the transport layer of source node s
m of session m is denoted by Y
m that is updated as follows:(3)
Y
m
t
+
1
=
max
⁡
Y
m
t
-
r
m
t
,
0
+
η
m
t
.If each virtual queue Y
m is guaranteed to be stable, according to the necessity and sufficiency for queue stability [17], it is apparent that η
m
-
≤
r
m
-, where the time average value of time-varying variable x
(
t
) is denoted by x
-
=
lim
t
→
∞
⁡
1
/
t
∑
τ
=
0
t
-
1
E
(
x
(
τ
)
). Therefore, the lower bound of r
m
- can be derived from η
m
- which can be calculated.


## 2.3. Data Queue at the Network Layer

The data backlog queue for sessionm at the network layer of node n is denoted by Q
n
m
(
t
). In each slot t, the queue is updated as(4)
Q
n
m
t
+
1
=
max
⁡
Q
n
m
t
-
∑
i
∈
O
n
μ
n
i
m
t
-
D
n
m
t
,
0
+
∑
j
∈
I
n
μ
j
n
m
t
+
1
n
=
s
m
r
m
t
,where μ
n
i
m
(
t
) is the amount of data of session m to be forwarded from node n to i in time slot t. 1
{
n
=
s
m
} is an indicator function that denotes 1 if n
=
s
m and 0 otherwise. In addition, ∑
m
∈
M
μ
n
i
m
(
t
) must not be greater than μ
n
m
a
x
,
o
u
t. D
n
m
∈
[
0
,
D
m
a
x
] represents the number of packets of session m that are dropped by node n in slot t. The optimization of μ
n
i
m
(
t
) is the routing decision. As assumed in [18], in this paper, the transmission capacity of any link is set to be 1. Therefore, μ
n
i
m
(
t
) is either 0 or 1, and it can not be greater than Q
n
m
t, which is denoted as (5)
μ
n
i
m
t
∈
0
,
min
⁡
Q
n
m
t
,
1
,
∀
n
,
i
∈
L
,
n
≠
d
m
,
m
∈
M
,and ∑
m
∈
M
μ
n
i
m
(
t
)
=
α
n
i
(
t
), ∀
(
n
,
i
)
∈
L, can also be derived. The actual amount of packets of session m dropped in slot t can be defined as (6)
D
n
m
~
t
=
min
⁡
Q
n
m
t
-
μ
n
m
t
,
D
n
m
t
.


## 2.4. Persistent Service Virtual Queue

Theϵ-persistent service queue designed in [16] can ensure bounded worst case delay for general types of utility functions. We denote this queue by G
n
(
m
), and in each slot, the queue is updated as(7)
G
n
m
t
+
1
=
max
⁡
G
n
m
t
+
1
Q
n
m
t
>
0
·
ϵ
-
∑
i
∈
O
n
μ
n
i
m
t
-
D
n
m
t
-
1
Q
n
m
t
=
0
·
μ
n
m
a
x
,
o
u
t
,
0
.From the algorithm in [16] we find that G
n
(
m
) is used in decision of resource allocation and packet dropping. Since in most slots Q
n
m
t
>
0, G
n
(
m
) may increase fast. According to the packet drop decision algorithm, high value of ϵ-persistent service queue leads to serious packets drop. Therefore, the fast increase of G
n
(
m
) leads to dropping of packets and this results in a significant drop in throughput utility.In this paper, we redesign theϵ-persistent service queue that is denoted by Z
n
(
m
). In each slot t, the queue is updated as(8)
Z
n
m
t
+
1
=
max
⁡
Z
n
m
t
+
ϵ
1
·
1
Q
n
m
t
>
Q
n
,
s
t
a
n
d
a
r
d
m
+
ϵ
2
·
1
Q
n
m
t
≤
Q
n
,
s
t
a
n
d
a
r
d
m
-
D
n
m
t
-
∑
i
∈
O
n
μ
n
i
m
t
,
0
,where ϵ
1
>
ϵ
2
>
0. ϵ
1 and ϵ
2 are constants. Q
n
,
s
t
a
n
d
a
r
d
(
m
) is a constant value that is calculated in phase I of the algorithm which will be given in Section 3. Initial backlog Z
n
(
m
)
(
0
) is supposed to be 0.Q
n
,
s
t
a
n
d
a
r
d
(
m
) is the time average of length of queue of session m in node n. According to (8), Z
n
(
m
) increases fast only when Q
n
m
(
t
)
>
Q
n
,
s
t
a
n
d
a
r
d
(
m
), and thus Z
n
(
m
) should grow slower than G
n
(
m
). According to the packet drop decision algorithm, the number of packets dropped in our new algorithm should decrease and throughput should increase, compared with the algorithm in [16].Any algorithm that maintains boundedQ
n
m
t and Z
n
(
m
)
(
t
) ensures persistent service with bounded worst case delay, as shown in Theorem 1.Theorem 1 (worst case delay).
For all time slotst
∈
{
0,1
,
2
,
…
} and all sessions m
∈
M, suppose that the algorithm can ensure(9)
Q
n
m
t
≤
Q
n
m
,
max
⁡
,
Z
n
m
t
≤
Z
n
m
,
max
⁡
,where Q
n
m
,max and Z
n
m
,
max
⁡ are finite upper bounds for Q
n
m
t and Z
n
m
(
t
), respectively. Assuming First Input First Output (FIFO) service, the worst case delay of the nondropped data at node n is bounded by the constant W
n
m
,
max
⁡, which is given as(10)
W
n
m
,
max
⁡
=
Q
n
m
,
max
⁡
+
Z
n
m
,
max
⁡
ϵ
2
,where x denotes the smallest integer that is greater than or equal to x.Proof.
Fix any slott
≥
0, and let A
n
(
m
)
(
t
) represent the data that arrives at queue Q
n
(
m
) on slot t. As the service is FIFO, the data A
n
(
m
)
(
t
) is placed at the end of the queue Q
n
(
m
) on slot t
+
1. We want to prove that all of the data A
n
(
m
)
(
t
) departs queue Q
n
(
m
) on or before slot t
+
W
n
m
,
m
a
x. We prove this in three cases.
Case  1. If Q
n
m
(
τ
)
>
Q
n
,
s
t
a
n
d
a
r
d
(
m
) for all τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
}, the following can be derived(11)
Z
n
m
τ
+
1
≥
Z
n
m
τ
+
ϵ
1
-
∑
i
∈
O
n
μ
n
i
m
τ
-
D
n
m
τ
.Summing the above over τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
} yields(12)
Z
n
m
t
+
1
+
W
n
m
,
m
a
x
-
Z
n
m
t
+
1
≥
ϵ
1
·
W
n
m
,
m
a
x
-
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.For Z
n
m
t
+
1
+
W
n
m
,
m
a
x
≤
Z
n
m
,
m
a
x, (12) can be rearranged to yield(13)
ϵ
1
·
W
n
m
,
m
a
x
-
Z
n
m
,
m
a
x
≤
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.According to (10), W
n
m
,
m
a
x is the smallest integer that is greater than or equal to (
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
)
/
ϵ
2. Therefore, we can get W
n
m
,
m
a
x
≥
(
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
)
/
ϵ
2, and we can derive(14)
ϵ
1
·
W
n
m
,
m
a
x
-
Z
n
m
,
m
a
x
≥
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
-
Z
n
m
,
m
a
x
=
Q
n
m
,
m
a
x
.Then, the following can be derived:(15)
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
≥
Q
n
m
,
m
a
x
≥
Q
n
m
t
+
1
.Equation (15) means that all the data in queue Q
n
m on slot t
+
1 (including all of the data A
n
(
m
)
(
t
) which arrives at Q
n
m on slot t) can depart the queue on or before the slot t
+
W
n
m
,
m
a
x. Therefore, in the condition of Q
n
m
(
τ
)
>
Q
n
,
s
t
a
n
d
a
r
d
(
m
) for all τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
}, the worst case delay of nondropped data at node n is bounded by (16)
W
n
,
C
a
s
e
1
m
,
m
a
x
=
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
ϵ
2
.
Case  2. If Q
n
m
(
τ
)
≤
Q
n
,
s
t
a
n
d
a
r
d
(
m
) for all τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
}, the following can be derived:(17)
Z
n
m
t
+
1
+
W
n
m
,
m
a
x
-
Z
n
m
t
+
1
≥
ϵ
2
·
W
n
m
,
m
a
x
-
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.Similar to Case  1, the bound of the worst case delay of nondropped data at node n in Case  2 is derived as(18)
W
n
,
C
a
s
e
2
m
,
m
a
x
=
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
ϵ
2
.
Case  3. If Q
n
m
(
τ
)
>
Q
n
,
s
t
a
n
d
a
r
d
(
m
) in n
1 slots of τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
} and Q
n
m
(
τ
)
≤
Q
n
,
s
t
a
n
d
a
r
d
(
m
) in n
2 slots of τ
∈
{
t
+
1
,
…
,
t
+
W
n
m
,
m
a
x
} and if we also have n
1
+
n
2
=
W
n
m
,
m
a
x, the following can be derived:(19)
Z
n
m
t
+
1
+
W
n
m
,
m
a
x
-
Z
n
m
t
+
1
≥
ϵ
1
·
n
1
+
ϵ
2
·
n
2
-
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.Let ϵ
∗
=
(
ϵ
1
·
n
1
+
ϵ
2
·
n
2
)
/
W
n
m
,
m
a
x; we can get(20)
Z
n
m
t
+
1
+
W
n
m
,
m
a
x
-
Z
n
m
t
+
1
≥
ϵ
∗
·
W
n
m
,
m
a
x
-
∑
τ
=
t
+
1
t
+
W
n
m
,
m
a
x
∑
i
∈
O
n
μ
n
i
m
τ
+
D
n
m
τ
.It is easy to derive ϵ
2
<
ϵ
∗
<
ϵ
1. Similar to Case  1, the bound of the worst case delay of nondropped data at node n in Case  3 is(21)
W
n
,
C
a
s
e
3
m
,
m
a
x
=
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
ϵ
2
.Considering the three cases above, the worst case delay of the nondropped data at node n is bounded by the constant W
n
m
,
m
a
x, which is given as(22)
W
n
m
,
m
a
x
=
Q
n
m
,
m
a
x
+
Z
n
m
,
m
a
x
ϵ
2
.


## 2.5. Throughput Utility Optimization Problem

Similar to the design of the utility function in [16], let U
m
(
·
) be strictly concave, twice differentiable, and nondecreasing utility function with U
m
(
0
)
=
0. r
-
=
(
r
m
-
,
m
∈
M
) denotes the throughput of the network. Λ is the capacity region of the network [17]. Then, the throughput utility maximization problem P
1 can be defined as follows:(23)
m
a
x
∑
m
∈
M
U
m
r
m
-
-
∑
m
∈
M
∑
n
∈
N
β
m
d
n
m
-
,
(24)
s
.
t
.
r
-
∈
Λ
,
(25)
1
,
2
,
5
,where d
n
(
m
)
- is the time average value of D
n
m
(
t
). β
m is the maximum slope of the utility function U
m
(
x
). Constraint (24) means that the network stability is guaranteed.


## 3. Dynamic Algorithm via Lyapunov Optimization

The Lyapunov optimization technique is applied to solveP
1. Q
n
(
m
) (∀
n
∈
N
,
m
∈
M), Y
m (∀
m
∈
M), and Z
n
(
m
) (∀
n
∈
N
,
m
∈
M) are used in the dynamic algorithm. Let Θ
(
t
)
=
[
Q
(
t
)
,
Y
(
t
)
,
Z
(
t
)
] be the network state vector in time slot t. Define the Lyapunov function as(26)
L
Θ
t
=
1
2
∑
m
∈
M
Y
m
t
2
+
∑
n
∈
N
∑
m
∈
M
Q
n
m
t
2
+
∑
n
∈
N
∑
m
∈
M
Z
n
m
t
2
.The conditional Lyapunov drift in time slot t is(27)
Δ
Θ
t
=
E
L
Θ
t
+
1
-
L
Θ
t
∣
Θ
t
.To maximize a lower bound for ∑
m
∈
M
U
m
r
m
-
-
∑
m
∈
M
∑
n
∈
N
β
m
d
n
(
m
)
-, the drift-plus-penalty function can be defined as(28)
Δ
V
Θ
t
=
Δ
Θ
t
-
V
E
∑
m
∈
M
U
m
η
m
t
-
∑
m
∈
M
∑
n
∈
N
β
m
D
n
m
t
∣
Θ
t
,where V is the weight of the utility defined by the user. The following inequality can be derived:(29)
E
Δ
V
Θ
t
≤
B
-
Ψ
1
t
-
Ψ
2
t
-
Ψ
3
t
-
Ψ
4
t
+
∑
n
∈
N
∑
m
∈
M
Z
n
m
·
ϵ
1
,where Ψ
1
t, Ψ
2
t, Ψ
3
t, and Ψ
4
t can be evaluated as follows:(30)
Ψ
1
t
=
∑
m
∈
M
V
·
U
m
η
m
t
-
Y
m
t
·
η
m
t
,
Ψ
2
t
=
∑
m
∈
M
r
m
t
·
Y
m
t
-
Q
n
m
t
·
1
n
=
s
m
,
Ψ
3
t
=
∑
n
∈
N
∑
m
∈
M
∑
i
∈
O
n
μ
n
i
m
t
·
Q
n
m
t
-
Q
i
m
t
+
Z
n
m
t
,
Ψ
4
t
=
∑
n
∈
N
∑
m
∈
M
D
n
m
t
·
Q
n
m
t
+
Z
n
m
t
-
V
·
β
m
.
B is a constant and satisfies(31)
B
≥
1
2
∑
m
∈
M
η
m
t
2
+
r
m
t
2
+
1
2
∑
m
∈
M
∑
n
∈
N
∑
j
∈
I
n
μ
j
n
m
t
+
1
n
=
s
m
r
m
t
2
+
∑
i
∈
O
n
μ
n
i
m
t
+
D
n
m
t
2
+
1
2
∑
m
∈
M
∑
n
∈
N
ϵ
1
-
∑
i
∈
O
n
μ
n
i
m
t
-
D
n
m
t
2
,according to 0
≤
η
m
t
≤
A
m
a
x
m, 0
≤
r
m
t
≤
A
m
a
x
m, μ
n
i
m
(
t
)
∈
{
0,1
}, and 0
≤
D
n
(
m
)
t
≤
D
m
a
x, and ϵ
1 is a constant value and the constant B must exist.The algorithm CCWD is based on the drift-plus-penalty framework [17] and the main design principle of the algorithm is to minimize the right-hand side of (29). The algorithm includes two phases.Phase I. Choose a sufficiently large T. From time t
=
0
,
…
,
T
-
1, run the algorithm proposed in [16] using Q
n
∗
m
(
t
) as the size of data queues. Set Q
n
,
s
t
a
n
d
a
r
d
(
m
) to be 1
/
T
∑
τ
=
0
T
-
1
Q
n
∗
m
τ
+
ρ, where ρ is a constant.Phase II. This phase includes five components.Source Rate Control. For each session m
∈
M at source node s
m, the admitted rate r
m
t is chosen to solve(32)
m
a
x
r
m
t
·
Y
m
t
-
Q
n
m
t
·
1
n
=
s
m
,
(33)
s
.
t
.
0
≤
r
m
t
≤
A
m
t
.Problem (32) is a linear optimization problem, and if Y
m
t
>
Q
s
m
m
(
t
), r
m
t is set to be A
m
t; otherwise it is set to be zero.Virtual Input Rate Control. For each session m
∈
M at source node s
m, the virtual input rate η
m
t is chosen to solve(34)
m
a
x
V
·
U
m
η
m
t
-
Y
m
t
·
η
m
t
,
(35)
s
.
t
.
0
≤
η
m
t
≤
A
m
a
x
m
.Since the utility function U
m
(
·
) is strictly concave and twice differentiable, (34) is a concave maximization problem with linear constraint. η
m
t can be chosen by(36)
η
m
t
=
max
⁡
min
⁡
U
m
′
-
1
Y
m
t
V
,
A
m
a
x
m
,
0
,where U
m
′
-
1
(
·
) is the inverse function of U
m
′
(
·
) that is the first-order derivative of U
m
(
·
). Since the utility function U
m
(
·
) is strictly concave and twice differentiable, U
m
′
(
·
) must be a monotonic function, and therefore, U
m
′
-
1
(
·
) must exist.Joint Routing and Scheduling. At the node n
∈
N, routing and scheduling decisions μ
n
i
m
(
t
) for each session m
∈
M can be made by solving the following: (37)
m
a
x
∑
n
∈
N
∑
m
∈
M
∑
i
∈
O
n
μ
n
i
m
t
·
Q
n
m
t
-
Q
i
m
t
+
Z
n
m
t
,
s
.
t
.
1
,
2
,
5
.First, for each link (
n
,
i
), the session m
∗ for link (
n
,
i
) can be chosen as(38)
m
∗
=
argmax
m
∈
M
⁡
Q
n
m
t
-
Q
i
m
t
+
Z
n
m
t
.The weight of link (
n
,
i
) is defined as w
n
i
=
Q
n
m
∗
(
t
)
-
Q
i
m
∗
(
t
)
+
Z
n
(
m
∗
)
(
t
). Therefore, the joint routing and scheduling problem can be reduced to the following:(39)
m
a
x
∑
n
∈
N
∑
i
∈
O
n
μ
n
i
m
∗
t
·
w
n
i
,
(40)
s
.
t
.
1
,
2
,
5
.Transmission rates μ
n
i
m
∗
(
t
) are chosen based on (39) which is a tough problem. The solution requires global knowledge and a centralized algorithm.Packet Drop Decision. For each session m
∈
M and each node n
∈
N, choose D
n
(
m
) to solve(41)
m
a
x
Q
n
m
t
+
Z
n
m
t
-
V
·
β
m
·
D
n
m
t
,
(42)
s
.
t
.
0
≤
D
n
m
t
≤
D
m
a
x
.Problem (41) is a linear optimization problem, and if Q
n
m
t
+
Z
n
m
t
>
V
·
β
m, D
n
(
m
)
(
t
) is set to be D
m
a
x; otherwise it is set to be zero.Update of Queues. Y
(
t
), Q
(
t
), and Z
(
t
) are updated using (3), (4), and (8) in each time slot.


## 4. Performance Analysis

Theorem 2 (bounded queues).
Assume thatD
max
⁡
≥
m
a
x
⁡
{
ϵ
1
,
A
max
⁡
m
+
μ
n
max,in
} holds, where μ
n
max,in denotes the maximal amount of packets that node n can receive from other nodes in one slot. Then under the algorithm CCWD, all queues are bounded for all t
≥
0 as follows:(43)
Q
n
m
t
≤
Q
n
m
,
max
⁡
,
Z
n
m
t
≤
Z
n
m
,
max
⁡
,
Y
m
t
≤
Y
m
,
max
⁡provided that these inequalities hold at t
=
0. The queue bounds are given by(44)
Y
m
,
max
⁡
=
V
·
β
m
+
A
max
⁡
m
,
Q
n
m
,
max
⁡
=
V
·
β
m
+
μ
n
max,in
+
1
n
=
s
m
·
A
max
⁡
m
,
Z
n
m
,
max
⁡
=
V
·
β
m
+
ϵ
1
.Proof.
The theorem is proved by induction.
(1) According to the induction principle, ifY
m
t
≤
Y
m
,
m
a
x holds for all t and supposing that Y
m
t
≤
Y
m
,
m
a
x for time slot t, it should also hold for time slot t
+
1. If Y
m
t
≤
V
·
β
m, then Y
m
t
+
1
≤
V
·
β
m
+
A
m
a
x
m
=
Y
m
,
m
a
x, because Y
m can increase by at most A
m
a
x
m in one slot. If V
·
β
m
<
Y
m
t
≤
Y
m
,
m
a
x, because β
m is the maximum slope of the utility function U
m
(
x
), we have(45)
V
·
U
m
η
m
t
-
Y
m
t
·
η
m
t
≤
V
·
U
m
0
+
V
·
β
m
·
η
m
t
-
Y
m
t
·
η
m
t
=
V
·
U
m
0
+
η
m
t
·
V
·
β
m
-
Y
m
t
≤
V
·
U
m
0
=
0with equality holding only if η
m
t
=
0
. Because η
m
t
=
0 when Y
m
t
>
V
·
β
m, Y
m
t can not increase in the next slot according to (3). Thus Y
m
(
t
+
1
)
≤
Y
m
(
t
)
≤
Y
m
,
m
a
x. Then Y
m
(
t
)
≤
Y
m
,
m
a
x for all t is proved.
(2) According to the induction principle, ifQ
n
m
(
t
)
≤
Q
n
m
,
m
a
x holds for all t and supposing that Q
n
m
(
t
)
≤
Q
n
m
,
m
a
x for time slot t, it should also hold for time slot t
+
1. If Q
n
m
(
t
)
≤
V
·
β
m, then(46)
Q
n
m
t
+
1
≤
Q
n
m
t
+
∑
j
∈
I
n
μ
j
n
m
t
+
1
n
=
s
m
r
m
t
≤
V
·
β
m
+
μ
n
m
a
x
,
i
n
+
1
n
=
s
m
·
A
m
a
x
m
=
Q
n
m
,
m
a
x
.If V
·
β
m
<
Q
n
m
(
t
)
≤
Q
n
m
,
m
a
x, D
n
(
m
)
(
t
) is set to be D
m
a
x according to the packet drop decision algorithm. Because D
m
a
x
≥
m
a
x
⁡
{
ϵ
1
,
A
m
a
x
m
+
μ
n
m
a
x
,
i
n
}, then(47)
Q
n
m
t
+
1
≤
Q
n
m
t
-
D
m
a
x
+
A
m
a
x
m
+
μ
n
m
a
x
,
i
n
≤
Q
n
m
t
≤
Q
n
m
,
m
a
x
.Then Q
n
m
(
t
)
≤
Q
n
m
,
m
a
x for all t is proved.
(3) According to the induction principle, ifZ
n
m
(
t
)
≤
Z
n
m
,
m
a
x holds for all t and supposing that Z
n
m
(
t
)
≤
Z
n
m
,
m
a
x for time slot t, it should also hold for time slot t
+
1. If Z
n
m
(
t
)
≤
V
·
β
m, then(48)
Z
n
m
t
+
1
≤
Z
n
m
t
+
ϵ
1
≤
V
·
β
m
+
ϵ
1
=
Z
n
m
,
m
a
x
.If V
·
β
m
<
Z
n
m
(
t
)
≤
Z
n
m
,
m
a
x, D
n
(
m
) is set to be D
m
a
x according to the packet drop decision algorithm. Because D
m
a
x
≥
m
a
x
⁡
{
ϵ
1
,
A
m
a
x
m
+
μ
n
m
a
x
,
i
n
}, then (49)
Z
n
m
t
+
1
≤
Z
n
m
t
-
D
m
a
x
+
ϵ
1
≤
Z
n
m
t
≤
Z
n
m
,
m
a
x
.Then Z
n
m
(
t
)
≤
Z
n
m
,
m
a
x for all t is proved.Theorem 3 (algorithm performance).
One hasφ
t
=
∑
m
∈
M
U
m
r
m
(
t
)
-
∑
m
∈
M
∑
n
∈
N
β
m
D
n
m
(
t
). Define φ
∗
t
=
∑
m
∈
M
U
m
r
m
∗
-
∑
m
∈
M
∑
n
∈
N
β
m
D
n
∗
(
m
) to be the optimal value of φ
t subject to constraints (1), (2), and (5), where r
m
∗ and D
n
∗
(
m
) are the solutions to maximize φ
t. One can have ∑
m
∈
M
U
m
r
m
-
-
∑
m
∈
M
∑
n
∈
N
β
m
d
n
m
-
≥
φ
∗
t
-
B
/
V.Proof.
The drift-plus-penalty function (28) satisfies(50)
Δ
Θ
t
-
V
·
E
∑
m
∈
M
U
m
η
m
t
-
∑
m
∈
M
∑
n
∈
N
β
m
D
n
m
t
∣
Θ
t
≤
B
-
V
·
E
∑
m
∈
M
U
m
η
m
t
-
∑
m
∈
M
∑
n
∈
N
β
m
D
n
m
t
∣
Θ
t
+
∑
m
∈
M
Y
m
t
·
E
η
m
t
-
r
m
t
∣
Θ
t
+
∑
m
∈
M
∑
n
∈
N
Q
n
m
t
·
E
∑
j
∈
I
n
μ
j
n
m
t
-
∑
i
∈
O
n
μ
n
i
m
t
+
1
n
=
s
m
r
m
t
-
D
n
m
t
∣
Θ
t
+
∑
m
∈
M
∑
n
∈
N
Z
n
m
t
·
E
ϵ
1
-
∑
i
∈
O
n
μ
n
i
m
t
-
D
n
m
t
∣
Θ
t
,where B is a constant value. According to Theorem  4.5 in [17] and Lemmas  5.6 and 5.7 in [19], the following inequality can be derived from (50):(51)
Δ
Θ
t
-
V
·
E
∑
m
∈
M
U
m
η
m
t
-
∑
m
∈
M
∑
n
∈
N
β
m
D
n
m
t
∣
Θ
t
≤
B
-
V
·
E
∑
m
∈
M
U
m
r
m
∗
-
∑
m
∈
M
∑
n
∈
N
β
m
D
n
∗
m
∣
Θ
t
-
δ
1
·
∑
m
∈
M
Y
m
t
-
δ
2
·
∑
n
∈
N
∑
m
∈
M
Q
n
m
t
-
δ
3
·
∑
n
∈
N
∑
m
∈
M
Z
n
m
t
,where δ
1, δ
2, δ
3
>
0. Inequality (51) can be transformed to the exact form specified by Theorem  5.4 in [19]. According to Theorem  5.4 in [19] and the condition η
m
-
≤
r
m
-, the following inequality can be derived:(52)
∑
m
∈
M
U
m
r
m
-
-
∑
m
∈
M
∑
n
∈
N
β
m
d
n
m
-
≥
∑
m
∈
M
U
m
η
m
-
-
∑
m
∈
M
∑
n
∈
N
β
m
d
n
m
-
≥
∑
m
∈
M
U
m
r
m
∗
-
∑
m
∈
M
∑
n
∈
N
β
m
D
n
∗
m
-
B
V
=
φ
∗
t
-
B
V
.Inequality (52) implies that the overall throughput utility achieved by the algorithm in this paper is within a constant gap from the optimum value.


## 5. Simulation

In the simulations, the commonly used greedy maximal scheduling (GMS) method is used for schedulable link set generation for each algorithm under comparison. This method is widely used for implementing backpressure-based centralized algorithms under sophisticated networks [20].


### 5.1. Simulation Setup

For simulations, a network with 20 nodes randomly distributed in a square of 1600 m2 is considered. A transmission is successful if a receiver is within the transmission range of its sender and outside the range of other concurrent senders. The transmission or interference range of a node is 15 m. There are four unicast sessions with randomly chosen sources and destinations. Data of each session is injected into the transport layer with the same rate in each slot at the source nodes. Parameter V is set as V
=
500
1000
1500
2000. The throughput utility function is U
(
x
)
=
log
⁡
(
x
+
1
). Simulations are run in Matlab R2014a. The simulation time of phase I lasts 30000 time slots. The simulation time of phase II lasts 50000 time slots. All initial queue sizes are set to be 0 and the default values are set as follows: D
m
a
x
=
3, β
m
=
1, A
m
a
x
m
=
2, μ
n
m
a
x
,
i
n
=
μ
n
m
a
x
,
o
u
t
=
1, ϵ
1
=
2, ϵ
2
=
1, and ρ
=
0.


### 5.2. Performance Comparison

In this section, the performance of CCWD is compared with that of an existing method called NeelyOpportunistic, which too can provide bounded worst case delay. NeelyOpportunistic is proposed in [16]. The throughput utilities and the time average number of dropped packets achieved by CCWD and NeelyOpportunistic are compared in Figures 1 and 2, respectively. V is set to be 1000. The data arrival rate is set to be from 0.2 packets to 1 packet per time slot. In Figure 1, the utility achieved by CCWD is higher than that of NeelyOpportunistic. Figure 2 shows that fewer packets get dropped using CCWD than with NeelyOpportunistic. According to the packet drop decision algorithm, high value of ϵ-persistent service queue leads to serious packets drop. As mentioned in Section 2.4, the virtual queue of CCWD being redesigned in this paper grows slower than the virtual queue of NeelyOpportunistic. Therefore, the virtual queue structure in NeelyOpportunistic leads to more serious packet drop and lower throughput utility.Figure 1
Throughput utility versus average data arrival rate.Figure 2
Time average number of dropped packets versus average data arrival rate.


### 5.3. Impact ofV

According to the analyses in Section4, with the increase of V, the utility achieved by CCWD can be arbitrarily close to the optimal value with an increase in the length of queues that is linear in V. The data arrival rate A
m
t is set to be 0.4 packets per time slot. Since the utility function is concave and nondecreasing, the optimal value of throughput utility should be N
s
e
s
s
i
o
n
·
log
⁡
(
1
+
A
m
t
)
⁡, where N
s
e
s
s
i
o
n is the number of sessions. N
s
e
s
s
i
o
n is 4 in this section. In this simulation, optimal throughput utility should be 1.34. Figure 3 shows that the utility value is increased with an increasing V. According to (44), it is easy to calculate Y
m
,
m
a
x, Q
m
,
m
a
x, and Z
m
,
m
a
x. In this section, since the maximum arrival rate A
m
a
x
m of each session is set to be 2 and the throughput utility function of each session is uniform, Y
m
a
x, Q
m
a
x, and Z
m
a
x can also be calculated using (44). In Figures 4, 5, and 6, V is increased from 500 to 2000 and on a log base 10 scale. From Figures 4, 5, and 6, we can learn that the time average sizes of Q, Y, and Z all increase approximately proportionally with the increase of V and are not larger than the bounds given in Theorem 2. The simulation results show a match between the simulations and the theoretical analyses.Figure 3
Throughput utility versusV.Figure 4
Time average size ofQ versus V.Figure 5
Time average size ofY versus V.Figure 6
Time average size ofZ versus V.


## 5.1. Simulation Setup

For simulations, a network with 20 nodes randomly distributed in a square of 1600 m2 is considered. A transmission is successful if a receiver is within the transmission range of its sender and outside the range of other concurrent senders. The transmission or interference range of a node is 15 m. There are four unicast sessions with randomly chosen sources and destinations. Data of each session is injected into the transport layer with the same rate in each slot at the source nodes. Parameter V is set as V
=
500
1000
1500
2000. The throughput utility function is U
(
x
)
=
log
⁡
(
x
+
1
). Simulations are run in Matlab R2014a. The simulation time of phase I lasts 30000 time slots. The simulation time of phase II lasts 50000 time slots. All initial queue sizes are set to be 0 and the default values are set as follows: D
m
a
x
=
3, β
m
=
1, A
m
a
x
m
=
2, μ
n
m
a
x
,
i
n
=
μ
n
m
a
x
,
o
u
t
=
1, ϵ
1
=
2, ϵ
2
=
1, and ρ
=
0.


## 5.2. Performance Comparison

In this section, the performance of CCWD is compared with that of an existing method called NeelyOpportunistic, which too can provide bounded worst case delay. NeelyOpportunistic is proposed in [16]. The throughput utilities and the time average number of dropped packets achieved by CCWD and NeelyOpportunistic are compared in Figures 1 and 2, respectively. V is set to be 1000. The data arrival rate is set to be from 0.2 packets to 1 packet per time slot. In Figure 1, the utility achieved by CCWD is higher than that of NeelyOpportunistic. Figure 2 shows that fewer packets get dropped using CCWD than with NeelyOpportunistic. According to the packet drop decision algorithm, high value of ϵ-persistent service queue leads to serious packets drop. As mentioned in Section 2.4, the virtual queue of CCWD being redesigned in this paper grows slower than the virtual queue of NeelyOpportunistic. Therefore, the virtual queue structure in NeelyOpportunistic leads to more serious packet drop and lower throughput utility.Figure 1
Throughput utility versus average data arrival rate.Figure 2
Time average number of dropped packets versus average data arrival rate.


## 5.3. Impact ofV

According to the analyses in Section4, with the increase of V, the utility achieved by CCWD can be arbitrarily close to the optimal value with an increase in the length of queues that is linear in V. The data arrival rate A
m
t is set to be 0.4 packets per time slot. Since the utility function is concave and nondecreasing, the optimal value of throughput utility should be N
s
e
s
s
i
o
n
·
log
⁡
(
1
+
A
m
t
)
⁡, where N
s
e
s
s
i
o
n is the number of sessions. N
s
e
s
s
i
o
n is 4 in this section. In this simulation, optimal throughput utility should be 1.34. Figure 3 shows that the utility value is increased with an increasing V. According to (44), it is easy to calculate Y
m
,
m
a
x, Q
m
,
m
a
x, and Z
m
,
m
a
x. In this section, since the maximum arrival rate A
m
a
x
m of each session is set to be 2 and the throughput utility function of each session is uniform, Y
m
a
x, Q
m
a
x, and Z
m
a
x can also be calculated using (44). In Figures 4, 5, and 6, V is increased from 500 to 2000 and on a log base 10 scale. From Figures 4, 5, and 6, we can learn that the time average sizes of Q, Y, and Z all increase approximately proportionally with the increase of V and are not larger than the bounds given in Theorem 2. The simulation results show a match between the simulations and the theoretical analyses.Figure 3
Throughput utility versusV.Figure 4
Time average size ofQ versus V.Figure 5
Time average size ofY versus V.Figure 6
Time average size ofZ versus V.


## 6. Conclusions

This paper proposed a two-phase throughput utility maximization algorithm which provides worst case delay guarantees using a newϵ-persistent virtual queue for multihop wireless networks. Throughput utility optimality of the algorithm is demonstrated with rigorous theoretical analyses. This algorithm ensures that queues are bounded by constants. Compared with existing works, the algorithm presented in this paper performs better in terms of utility and data dropped. The plan for the future work is to combine this proposed algorithm with applications requiring limited delay.



---

*Source: 5762851-2016-10-10.xml*