第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
联合流量分配，速率控制，路由和调度算法，可最大程度地提高无线网状网络的网络实用性.pdf
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI
10.1109/TVT.2015.2427091, IEEE Transactions on Vehicular Technology
1
Joint Traffic Splitting, Rate Control, Routing and
Scheduling Algorithm for Maximizing Network
Utility in Wireless Mesh Networks
Anfu Zhou, Min Liu, Zhongcheng Li, Eryk Dutkiewicz
Abstract—The existence of multiple gateways, as is a common
case in Wireless Mesh Networks (WMNs), brings the possibility
to improve network performance. However, previous studies,
including both heuristic-based works and theory-driven cross-
layer design works, cannot guarantee an optimal exploitation
of multiple gateways. In this paper, we focus on exploiting
multiple gateways optimally to achieve maximum network utility.
We first extend the current framework of cross-layer design
and formulate network utility maximization problem under
WMNs with multiple gateways as a constrained optimization
problem. Then by solving this optimization problem, we propose
a novel joint traffic splitting, rate control, routing and scheduling
algorithm called CLC DGS, which splits and distributes network
traffic into multiple gateways in an optimal way. We prove
that CLC DGS can achieve maximum network utility. Finally,
we run extensive simulations to demonstrate that compared
with the previous methods, CLC DGS significantly improves
the performance of WMNs under various network environments
including gateway heterogeneity, link heterogeneity and different
interference models.
Index Terms—Cross-layer design, dynamic gateway selection,
network utility maximization.
I. INTRODUCTION
A S an important form of network architecture, Wireless
Mesh Networks (WMNs) provide a convenient and
economical way for Internet access, and are widely used
in enterprise, campus and rural places. However, despite the
wide use of WMNs, they often confront severe performance
degradation, such as low throughput and unfairness [1]–[3],
[5], [6].
To improve the network performance of WMNs, research
efforts in the literature recognize one key characteristic of
WMNs that usually multiple gateways are deployed in WMNs,
and realize that the existence of multiple gateways provides
a new possibility for improving performance [7]–[9]. For
example, one can improve the throughput and reduce the delay
of a preferential flow by assigning a near and low-congested
gateway for the flow.
Copyright (c) 2015 IEEE. Personal use of this material is permitted. However,
permission to use this material for any other purposes must be obtained from
the IEEE by sending a request to pubs-permissions@ieee.org.
Anfu Zhou, Min Liu, Zhongcheng Li are with Institute of Computing
Technology,Chinese Academy of Sciences, Beijing, China, 100190. E-mail:
{zhouanfu,liumin,zcli}@ict.ac.cn
Australia. Email: eryk.dutkiewicz@mq.edu.au
Eryk Dutkiewicz is with Dept. of Elec. Engin Macquarie University, Sydney,
The work reported in this paper was supported in part by the National
Natural Science Foundation of China (61202410, 61132001, 61120106008,
61272475, 61272474, 61472404, 61472044 and 61472402).
Based on this realization, much effort is devoted to exploit
the potential of multiple gateways to enhance performance of
WMNs. For example, Lakshamannan et al. in [7] and Lenders
et al. in [8] propose anycast routing schemes in which wireless
mesh nodes simultaneously associate with multiple gateways
and forward packets to low-congested gateways. Ancillotti et
al. in [9] proposes a traffic-aware load balancer to enhance
network performance. Laufer et al. in [11] advances the study
to combine both anycast and anypath routing to further exploit
multiple gateways. Although these studies can improve network
performance to a certain extent, they are based on heuristics
and do not necessarily lead to optimal utilization of multiple
gateways.
In parallel, there are many cross-layer design works that
address the issue of optimally utilizing a network. In contrast
to heuristics-based approaches, cross-layer design provides a
systematic theory-driven framework to develop performance-
optimal data transmission control mechanisms for wireless
multihop networks including WMNs. Following the seminal
work of Tassiulas and Ephremides in [12], significant progress
has been made on cross-layer control algorithms [13]–[30].
It has been proven that cross-layer control algorithms can
fully explore the capacity region of a network so as to
guarantee maximum network utility1, that is, cross-layer control
algorithms can achieve maximal overall throughput and at the
same time ensure throughput fairness among different flows
[13]–[30]. However, previous cross-layer design works are
limited to a specific packet delivery model where the forwarding
destination of a flow is one and the only one pre-determined
node, and do not take into account the existence of multiple
gateways, therefore they lead to much loss of network utility
in WMNs with multiple gateways, as we will show in Section
VI.
The existence of multiple gateways provides an extra control
dimension and further complicates cross-layer design. In
particular, one first should consider how to optimally split
network traffic among different gateways, that is, how to
choose a right gateway for traffic and how to decide the exact
amount of traffic to the gateway, according to time-varying
network conditions (i.e., the loading level of gateways and
congestion level of the paths to gateways are changing all
the time). Moreover, to achieve maximum network utility, one
needs to integrate this traffic splitting strategy and other data
1Network utility is a widely-used performance metric that can measure both
aggregated throughput and fairness in a network. More explanation is given
in Section IV.
0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See
http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI
10.1109/TVT.2015.2427091, IEEE Transactions on Vehicular Technology
transmission control layers into a unified framework, because
all data transmission control layers (i.e., traffic splitting, rate
control, routing and scheduling) cooperate and interact with
each other tightly and they together decide the resulting network
utility.
Solving these challenges,
in this paper we incorporate
dynamic gateway selection into the cross-layer framework and
design a novel cross-layer control algorithm called CLC DGS
(Cross Layer Control with Dynamic Gateway Selection), which
is a joint traffic splitting, rate control, routing and scheduling
algorithm for maximizing network utility. We show that
CLC DGS can exploit the full potential of multiple gateways
so as to achieve maximum network utility. To the best of our
knowledge, CLC DGS is the first work that is proved to be
able to achieve network utility maximization for WMNs with
multiple gateways. In particular, the contributions of this paper
can be summarized as follows:
• We formulate network utility maximization for wireless
mesh networks with multiple gateways as an optimization
problem, which embodies the problems of selecting the
optimal gateway under the constraints of network capacity.
• By decomposing and solving the formulated optimization
problem, we propose a novel cross-layer control algorithm
called CLC DGS, which is a joint traffic splitting, rate
control, routing and scheduling algorithm that
takes
advantage of multiple gateways. CLC DGS splits and
distributes network traffic into multiple gateways in
an optimal way. We prove that CLC DGS guarantees
maximum network utility.
• We validate CLC DGS through extensive simulations.
Simulation results show that compared with previous
works, the aggregated throughput of all flows and fairness
among flows are significantly improved by CLC DGS.
The improvement ratio ranges from about 20% to 90%
under various network environments including link hetero-
geneity, gateway heterogeneity and different interference
models.
The rest of the paper is organized as follows. We discuss
related works in Section II. Section III describes the system
model. Section IV presents the CLC DGS algorithm. We
handle the practical implementation issues of CLC DGS in
Section V, and give evaluation methods and results in Section
VI. We conclude in Section VII.
II. RELATED WORKS
Performance Degradation of WMNs: Plenty of research
has revealed that WMNs often confront severe performance
degradation, and the reason is the mismatch between the data
transmission control mechanisms (including window based
congestion control of TCP, shortest path based routing and
IEEE 802.11 scheduling) used in WMNs and the network
environment of WMNs [30]. For example, the carrier sense
multiple access (CSMA)-based IEEE 802.11 Distributed Co-
ordination Function (DCF) has been widely used for medium
access control in WMNs. However, since IEEE 802.11 DCF
was originally designed for single-hop WLANs, the use of the
mechanism in multi-hop and topology-asymmetrical WMNs
2
TABLE I
DEFINITIONS
The set of mesh nodes
The set of links
The set of gateways
The set of flows
The amount of traffic of flow f
admitted into the network in time slot t
The long-term average amount of traffic of
flow f admitted into the network
The fraction of traffic of flow f
that has the forwarding destination of gateway d
The queue length of packets with
destination gateway d on node i in time slot t
The number of packets with destination
gateway d transmitted over link (i, j) in time slot t
The long-term average number of packets
with forwarding destination of
d transmitted over link (i, j)
The capacity region of a network
The capacity of link (i, j)
The packet delivery probability that
a packet transmission from node i
is successfully received by node j
E
GW
F
r(f )
s(f )(t)
r(f )
s(f )
y(f )
d
Q(d)
i
(t)
µ(d)
ij (t)
µ(d)
ij
⇤
cij (t)
pij (t)
often produces severe unfairness among competing flows and
even complete flow starvation [5], [6].
To solve the mismatch problem, many works are proposed
to optimize currently-used control mechanisms at different
network layers according to the characteristics of WMNs [1]–
[6]. For example, in terms of rate control, the work in [3]
extends TCP to deal with the specific neighborhood-congestion
problem in WMNs (instead of the common node-congestion
problem in wired or single-hop wireless networks).
In particular, plenty of works recognize a characteristic of
WMNs that usually there are multiple gateways deployed, and
in consequence focus on exploiting the potential of multiple
gateways to enhance performance of WMNs. For example, the
work of [7] lets wireless mesh nodes simultaneously associate
with many gateways and use multiple paths to forward packets.
The work in [8] takes into account the locations of the gateways
and forwards packets to the direction with higher gateway
density. The work in [9], [10] considers different service
requirements of Internet applications, and proposes a traffic-
aware routing architecture to balance traffic load over available
paths and gateways. PLASMA proposed in [11] advances the
study to combine both anycast and multiple path routing to
further exploit multiple gateways.
The works above can improve network performance to
a certain extent. However,
they are limited to heuristics-
based optimization under the existing framework, and operate
independently at each layer of the network stack. Recent
advancement in network theory reveals that to efficiently
utilize resources of networks, especially for multi-hop wireless
networks including WMNs, cross-layer cooperation of different
network layers is needed [13]–[30].
Cross-Layer Design Works:
to traditional
heuristics-based design method, cross-layer design is a system-
atic framework to develop theoretically-optimal data transmis-
sion control mechanisms. In cross-layer design, the network
In contrast
0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See
http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI
10.1109/TVT.2015.2427091, IEEE Transactions on Vehicular Technology
resource allocation problem is first formulated as a constrained
optimization problem. Then by solving the problem using
optimization and stochastic control theory methods, one can
design various data transmission control algorithms. In these
algorithms, control mechanisms including scheduling, routing
and rate control at different network layers are tightly coupled
and cooperate with each other, so this kind of algorithms is
called cross-layer control algorithms.
Since the seminal work of Tassiulas and Ephremides [12],
extensive studies have been made on cross-layer control
algorithms [13]–[30]. Earlier efforts [13]–[17] propose joint
rate control, routing and scheduling algorithms which are utility-
optimal. Recently much attention has been paid to the design
and analysis of simpler, low-complexity or distributed cross-
layer control algorithms [18]–[22]. There are also much effort
devoted to design low-delay cross-layer control algorithms [23]–
[27]. We also note some inspiring works on applying cross-layer
optimization in practical wireless network [28]–[30]. However,
as we noted before, these works do not consider the case of
multiple gateways in WMNs and lead to much loss of network
utility in WMNs with multiple gateways (shown in Section
VI), which motivates our work.
III. SYSTEM MODEL
The system model in this paper is almost the same with the
model in other cross-layer design works in literature [12]–[30],
expect that we consider the existence of multiple gateways,
while other works assume single gateway. One can refer to
Section 2 of [16] for a detailed and well organized introduction
of system model for cross-layer design. In the following, we
present the fundamental parts and denotations of the model,
which are required for understanding theoretical analysis later.
A. Assumptions
The assumptions of our system model are as follows,
1) Nodes in a network are synchronized using a time-slotted
structure, where each packet’s arrival and transmission
occurs at the beginning of a time slot of unit length, and
a typical time slot is denoted by t. Channel state during
a time slot is constant.
2) Nodes in a network have the ability to monitor their
channel state information. These information could
be collected together for computing intelligent control
decisions.
3) Nodes have buffers with infinite size.
4) Traffic on source nodes is saturated.
Note that these assumptions are made just for clearly present
the idea of cross-layer design, and cross-layer design could be
extended to scenarios without these assumptions, i.e., scenarios
such as asynchronous systems or systems where it is difficult
to obtain timely feedback about channel quality. Please refer to
Section 2.4 of [16] for a discussion of the first two assumptions,
[26] for the third assumption, and Section 5.4 in [16] for the
fourth assumption.
Besides, for better elaborating the basic idea of the proposed
CLC DGS, in the derivation process of CLC DGS (i.e., Section
IV.A, IV.B, IV.C, IV.D), we suppose that all gateways and links
3
have the same capacity of one packet per slot, and that link
transmissions will be successful once a feasible interference-
free schedule is decided. However, as we all know, practical
wireless networks are more complicated. For example, different
gateways often have different capacities, and link capacities
are usually different. Moreover, transmissions in a feasible
schedule may still fail due to external factors such as time-
varying signal-attenuation or user mobility [33]. Therefore,
in Section IV.E, we consider these problems and show that
CLC DGS can handle these problems after some adaptations.
B. Network Model
Here we represent a wireless mesh network with a graph
G = ( , E), where is the set of all mesh nodes (N = | |)
and E is the set of links (L = |E|). The set of mesh gateways
is denoted by GW .
Due to interference in wireless networks, neighboring links
cannot be active simultaneously. Here we denote a feasible
schedule by ~S where its lth component Sl = 1 if link l
is activated and Sl = 0 otherwise. The set of all feasible
schedules is denoted by . Note that is decided by the
underlying wireless interference model of the network. The one-
hop interference model is assumed in this paper for convenience,
unless otherwise specified. Under the one-hop model, any two
links with a common node cannot be active simultaneously. For
example, link 1 and link 2 in Fig. 1 cannot be simultaneously
active since they share the common node 2. Note that our work
could be applied to other interference models effortlessly, and
we do some simulations under the 2-hop interference model
in Section VI.C. We let cij(t) represent the capacity of link
(i, j), and let pij(t) (0 pij(t) 1) represent the packet
delivery probability that a packet transmission from node i is
successfully received by node j.
C. Traffic, Queueing Model and Network Capacity Region
i
i
i
traffic, it is assumed thatPf :s(f )=i r(f )
Traffic Model: We assume that the number of flows going
through the network is K, and let F = {1, 2, ...K} be the set
of these flows. Let r(f )
s(f )(t) be the amount of traffic of flow
f admitted into the network in time slot t, where s(f ) is the
source node of flow f. To limit the burstiness of the admitted
for 8i 2 ,
which means that traffic rate on a source node should not be
are chosen to be positive and
infinite. The constants Rmax
suitably large and will be used in later analysis. Note the the
traffic limit is reasonable in practice, since in practical network
environments, the amount of normal application traffic (such
as TCP traffic) is usually in a reasonable range, but not be
infinite.
(t) Rmax
A packet of flow f can be forwarded to any one of many
gateways. We use y(f )
to denote the fraction of flow f’s traffic
that has the forwarding destination of gateway d 2 GW , note
thatPd2GW y(f )
Queueing Model: Each node maintains multiple queues (one
queue per gateway). On any node i, we denote the queue
length for gateway d at the beginning of time slot t by Q(d)
(t).
Note that all queues at the destination for packets meant to
itself are set to be empty (i.e., Q(d)
ij (t) be
d (t) = 0). Let µ(d)
d = 1.
d
i
0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See
http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI
10.1109/TVT.2015.2427091, IEEE Transactions on Vehicular Technology
4
the number of packets with the forwarding destination of
gateway d transmitted over link l = (i, j) in time slot t. Note
that µ(d)
ij (t) = 1 if at t, the scheduling algorithm transmits
a packet with forwarding destination d over link (i, j), and
µ(d)
ij (t) = 0 otherwise. Then the queue evolution is as follows
[16] (specifically, eq.(4.3) in page 44 of reference [16]):
Q(d)
i
(t + 1) max[Q(d)
i
µ(d)
ib (t), 0]
(t) Xb2
+ Xf :s(f )=i
y(f )
d r(f )
i
(t) +Xa2
µ(d)
ai (t).
(1)
i
is
the
ib (t)
d r(f )
traffic out of node
where Pb2 µ(d)
Pa2 µ(d)
Pf :s(f )=i y(f )
thanPb2 µ(d)
i,
ai (t) is the traffic into node i from other nodes, and
(t) is the traffic generated by node i itself.
i
, the queue length in time t, may be smaller
i
ib (t) (i.e., the scheduled traffic out of node i is
more than the traffic in the queue). For this case, we use the
operation of max[Q(d)
Note that Q(d)
ib (t), 0].
Note that in the queueing model described above, we put
packets to be forwarded to the same gateway in the same queue
even if they belong to different flows. Here the queue is a
logical concept. For the algorithm to run, we only need to know
the number of packets to each gateway, and we don’t care
which specific queueing mechanism is actually implemented in
a node. In other words, We don’t have any extra requirement
on queueing mechanisms.
Network Capacity Region: A network is regarded as stable
if the time average of the sum of all the queue lengths in the
network is bounded, that is,
(t) Pb2 µ(d)
lim sup
t!1
1
t
t 1X⌧ =0 Xi2 ,d2GW
E{Q(d)
i
(⌧ )} < 1.
(2)
The capacity region of the network is defined as the set ⇤
consisting of all the arrival rates such that there exists a data
transmission control algorithm that ensures (2).
IV. CROSS-LAYER CONTROL WITH DYNAMIC GATEWAY
SELECTION
In this section, we first formulate the network utility
maximization problem for WMNs with multiple gateways
as a constrained optimization problem under the fluid traffic
model. Then we decompose and solve the optimization problem
to derive the CLC DGS algorithm. Finally, we prove that
CLC DGS achieves the maximum network utility.
A. Problem Formulation
s(1), ...r(K)
average rates of all the flows ~r= (r(1)
~r2 ⇤ if there exists {µ(d)
hold:
(i)
Given a flow set F and a traffic vector of the long-term
s(K)), we say that
ij } such that the following conditions
For any two-tuple (i 2 , d 2 GW ) such that d 6= i,
we have
(3)
µ(d)
y(f )
d r(f )
µ(d)
ib .
s(f ) =Xb2
Xa2
ai + Xf :s(f )=i
Note that 8f, we have
Xd2GW
y(f )
d = 1.
(4)
This condition is the flow conservation constraint,
which states that for any node i, the incoming and
outgoing traffic with forwarding gateway d should be
equal, that is, the sum of all traffic from upstream
ai , and the traffic generated on node i,
ib , the traffic
d r(f )
nodes,Pa2 µ(d)
Pf :s(f )=i y(f )
out of node i.
s(f ), is equal toPb2 µ(d)
µij = Xd2GW
µ(d)
ij .
For serving this traffic, the link should be activated
for a certain amount of time, that is
have
(5)
(ii) We denote all traffic on link (i, j) with µij, then we
µij = Xm:(i,j)2~Sm
⇡m.
(6)
Here ⇡m stands for the time fraction during which
the feasible schedule ~Sm is activated. Clearly, the
sum of the time fractions of all the feasible schedules
should be 1, that is,
⇡m = 1.
(7)
| |Xm=1
This condition is the capacity constraint, which states
that no matter how the traffic ~ris split among the
gateways and distributed in the network, it should be
obtainable.
Under the above constraints, our aim is to maximize the total
average rates of all the network flows and ensure fairness among
the flows. To this end, we first define a utility function g(f )(.)
(Note that we use a boldface to denote a function) for each
flow f, representing the satisfaction of the flow with respect to
its average rate r(f )
s(f ). Utility functions are generally assumed
to be increasing and concave, which is a conventional means
of measuring throughput and fairness (usually, g(f )(.) is set
to log(.) in literature). Then, following the literature [13]–[15],
[18], [19], [22], we formulate the Network Utility Maximization
(NUM) problem for WMNs with multiple gateways as:
max
~r Xf2F
s.t
(3), (4), (5), (6), (7).
g(f )(r(f )
s(f ))
(8)
We denote the solution of the above NUM problem by ~r⇤.
In previous works [13]–[15], [18], [19], [22], similar NUM
problems have been formulated and different joint rate control,
routing and scheduling algorithms (later referred to as CLC
algorithms) have been proposed. The achieved flow rates of
these algorithms are proved to be arbitrarily close to the
optimal solutions. However, as we noted before, these previous
algorithms do not consider the scenario of multiple gateways,
and consequently cannot exploit the potential of multiple
gateways.
In this paper, our objective is to extend the framework of
cross-layer design to incorporate dynamic gateway selection, so
as to improve network performance as far as possible through
the optimal use of multiple gateways in WMNs. In the above
NUM formulation, we have incorporated the gateway selection
problem into it (specifically, see (3) and (4)). Next we solve
the problem with a primal-dual method [16], [17] to derive a
0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See
http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI
10.1109/TVT.2015.2427091, IEEE Transactions on Vehicular Technology
5
novel Cross-Layer Control algorithm with Dynamic Gateway
Selection (CLC DGS), which will be able to achieve the
maximum network utility in WMNs with multiple gateways.
B. Dual Decomposition and Sub-Problem Solution
To solve the above NUM problem, we first define q(d)
to
be the Lagrange multiplier corresponding to the constraints in
(3). Appending the constraints in (3) to the objective in (8),
we can have a partial Lagrange dual function as follows:
i
max
~r, ~⇡ , ~µ
[Xf2F
g(f )(r(f )
q(d)
i
s(f )) Xi2 ,d2GW
+ Xf :s(f )=i
µ(d)
ai
(Xa2
s(f ) Xb2
y(f )
d r(f )
µ(d)
ib )]
(9)
subject to (4), (5), (6), (7). We then rearrange the terms of
(9) as follows,
max
~r, ~⇡ , ~µ
[Xf2F
g(f )(r(f )
s(f )) Xi2 ,d2GW
+ Xi2 ,d2GW
q(d)
i Xf :s(f )=i
(Xb2
q(d)
i
y(f )
d r(f )
s(f )
µ(d)
ib Xa2
µ(d)
ai )].
The second term will be zero for any i that is not a source
node. For such a i, there is no f such that s(f ) = i, so
s(f ) = 0. Given this, we can rewrite above
d r(f )
g(f )(r(f )
q(d)
s(f )y(f )
d r(f )
s(f )
s(f )) Xf2F,d2GW
+ Xi2 ,d2GW
q(d)
i
(Xb2
µ(d)
ib Xa2
µ(d)
ai )].
Then we merge the first and the second term of the above
equation, and have
equation as
Pf :s(f )=i y(f )
[Xf2F
max
~r, ~⇡ , ~µ
(g(f )(r(f )
q(d)
s(f )y(f )
d r(f )
s(f ))
max
~r, ~⇡ , ~µ
[Xf2F
s(f )) Xd2GW
+ Xi2 ,d2GW
q(d)
i
(Xb2
µ(d)
ib Xa2
µ(d)
ai )].
For maximizing the above equation, the first term is only related
to ~r, and the second terms is only related to ~⇡ and ~µ, so we
can separate the equation as the sum of two maximizations as
follows,
max
~r 0
[Xf2F
(g(f )(r(f )
s(f )) Xd2GW
[ Xi2 ,d2GW
+ max
~⇡ , ~µ 0
q(d)
s(f )y(f )
d r(f )
s(f ))]
q(d)
i
(Xb2
µ(d)
ib Xa2
µ(d)
ai )].
(10)
If the optimal values of the Lagrange multipliers q(d)
are
known, we can decompose the equation above into two sub-
problems.
1) Traffic Splitting and Rate Control: The first sub-problem
is the traffic splitting and rate control problem as follows:
i
max
~r 0 Xf2F
(g(f )(r(f )
s(f )) Xd2GW
q(d)
s(f )y(f )
d r(f )
s(f ))
(11)
subject to: (4).
By solving this problem, we derive the optimal flow rate
r⇤(f )
s(f ) for each flow as follows:
r⇤(f )
s(f ) =
1
q(d⇤)
s(f )
(12)
Recall that for each d 2 GW , there is a separate queue on
any i 2 . Then q(d⇤)
s(f ) in (12) stands for the smallest queue
length on node i and d⇤ is the corresponding gateway. The
detailed solution process is given in Appendix A.
2) Routing and Scheduling: The second sub-problem is the
routing and scheduling problem as follows:
max
~⇡ , ~µ 0 Xi2 ,d2GW
q(d)
i
(Xb2
µ(d)
ib Xa2
µ(d)
ai )
(13)
subject to (5), (6) and (7).
Note that the problem above has a similar form to the routing
and scheduling problem in cross-layer literature [13]–[19].
However, the organization of packets is essentially different.
In previous works, the packets are organized according to
different flows, without considering the existence of multiple
gateways. While in this work, we arrange packets into different
queues on a node according to different gateways. Under this
arrangement, we solve the routing and scheduling problem in
(13) as follows. First, for each link l = (i, j) the maximum
differential backlog of the link is computed as follows:
Then the feasible schedule ~S⇤ is decided as follows:
, 0}.
W ⇤l = max
j
d2GW{q(d)
i q(d)
S2 Xl2E
~S⇤ = arg max
SlW ⇤l .
(14)
(15)
is transmitted from node i to node j.
For each scheduled link l = (i, j) belonging to ~S⇤, one packet
from the queue corresponding to the maximum differential
backlog W ⇤l
Recall that the solving process of the two sub-problems
above both assumes that the Lagrange multipliers q(d)
are
known in advance. In practice, we can derive the value of q(d)
by iteration. As to each update of the Lagrange multipliers,
from (9) we have the first derivative of q(d)
as follows:
i
i
i
˙
q(d)
i = (Xa2
µ(d)
ai + Xf :s(f )=i
y(f )
d r(f )
s(f ) Xb2
µ(d)
ib )+.
(16)
Note that the evolution process of Lagrange multipliers q(d)
is the same as the evolution process of the queues Q(d)
in the
network. So here we can simply use the lengths of the per-flow
queues as the Lagrange multipliers, following the cross-layer
design literature [14], [15].
C. CLC DGS
i
i
In the above subsection, we have formulated and solved the
problem in the fluid model scenario. Motivated by the solution,
we now consider the stochastic network dynamics and present
the CLC DGS algorithm in Algorithm 1, and then prove its
utility optimality.
Remark 1: We now illustrate the operating process of
CLC DGS using a simple example. Consider the network
shown in Fig. 1, which has five nodes and five links. We set
two gateways (node 3 and node 4), and set one flow originating
from node 1. Each node i maintains two separate queues (i.e.,
Q(3)
) for the packets required to be delivered to the
two gateways. We assume that in this time slot, the lengths of
each queue are as shown in the figure. Note that all queues
at the destination for packets meant for itself are set to zero
(i.e., Q(3)
4 = 0). We plot these “virtual” queues
in dotted lines in the Fig. 1.
3 = 0 and Q(4)
and Q(4)
i
i
0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See
http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI
10.1109/TVT.2015.2427091, IEEE Transactions on Vehicular Technology
6
Algorithm 1 CLC DGS: Cross-layer Control algorithm
with Dynamic Gateway Selection
Traffic Splitting & Rate Control: At every time slot t, for
each flow f 2 F , the rate controller at its source node s(f )
first selects d⇤ as the gateway for the injecting traffic in this
time slot, where d⇤ is decided in the following way
s(f )(t).
d⇤ = argd2GW min Q(d)
(17)
That is, d⇤ is the gateway among all d 2 GW for which the
length of the queue Q(d)
s(f )(t) is the smallest. Then, the rate
controller injects an amount of traffic into the queue Q(d⇤)
s(f )(t),
and the amount of the traffic is equal to r⇤(f )
s(f ), which is decided
by the following equation:
r⇤(f )
s(f ) =
V
Q(d⇤)
s(f )(t)
.
(18)
Here V > 0 is a controlled constant parameter that affects
the tradeoff between network utility and total queue length of
the network. We will discuss more about it in remarks later.
Routing & Scheduling: First, at each time slot t, we compute
for each link l = (i, j) the maximum differential backlog of
the link as follows:
W ⇤l (t) = max
(t) Q(d)
j (t), 0}.
(19)
Then the feasible schedule ~S⇤ chosen is decided as follows:
(20)
~S⇤(t) = arg max
SlW ⇤l (t).
i
d2GW{Q(d)
S2 Xl2E
Note that is the set of all feasible schedules. For each
scheduled link l = (i, j) belonging to ~S⇤(t), one packet of
the queue corresponding to the maximum differential backlog
W ⇤l (t) is transmitted from node m to node n.
1
1
V
Q(4)
in this time slot.
1 Q(3)
We first explain the operation of traffic splitting and rate
control in this case. Since Q(4)
1 , CLC DGS decides the
chosen gateway to be node 4, that is, d⇤ = 4. Then CLC DGS
computes the amount of injecting traffic using (12), and the
result is
. If we set V = 10, then CLC DGS will put
2 = 5 packets into Q(4)
10
We then examine the operation of routing and scheduling
components of CLC DGS. As noted before, we assume one-
hop interference model where adjacent links cannot be active
at the same time. Under this interference model, the set of all
the feasible schedules is {{link 1, link 3}, {link 1, link 4},
{link 2, link 4}, {link 2, link 5}, {link 3, link 5}}. Using the
denotation of Algorithm 1, the first feasible schedule could be
denoted with {1 0 1 0 0} since link 1 and link 3 is selected.
Similarly, the second feasible schedule is {1 0 0 1 0}, the
third is {0 1 0 1 0}, the fourth is {0 1 0 0 1} and the fifth
is {0 0 1 0 1}. Then, given the queue status shown in the
figure, CLC DGS computes the maximum differential backlog
of each link using (19) and the results are {3 2 2 3 2} given in
Fig. 1. For example, the maximum differential backlog of link
1 is the difference between Q(3)
2 . From these results
1
and using (20), we can easily compute the sum differential
backlog of each feasible schedule. Taking the first schedule as
example, the sum backlog is 1*3 + 0*2 + 1*2 + 0*3 + 0*2
and Q(3)
Node 1
(3)=
1
(4)=
1
Traffic splitting
Link 5
*=
5
Node 5
(3)=
5
(4)=
5
Link 4
*=
4
Node 4 (gateway)
Link 1
*=
1
Node 2
(3)=
2
(4)=
2
Link 2
*=
2
Node 3 (gateway)
(3)=
4
(4)=
4
Link 3
*=
3
(3)=
3
(4)=
3
to Q(4)
4
at node 4.
Illustration of the CLC DGS algorithm.
Fig. 1.
= 5. In this way, we finally verify that the sum backlog for
the five feasible schedule is {5 6 5 4 4}. Clearly, the chosen
schedule will be the second feasible schedule consisting of
link 1 and link 4, that is, node 1 transmits one packet from
queue Q(3)
to Q(3)
at node 2, and node 5 transmits one packet
1
2
from queue Q(5)
5
Remark 2: At first glance, the rate control of CLC DGS
algorithm is simple: it decides the flow traffic rate just based
on the queue length of the source node, and sets the forwarding
destination to be the gateway corresponding to the smallest
queue. Although CLC DGS is simple, we will prove its
efficiency of achieving the maximum utility of a network.
However, before presenting the rigorous proof, we first explain
in an intuitive way why CLC DGS is able to select the suitable
gateway so as to achieve the maximum network utility. In a
network with multiple gateways, when a gateway ˜d is not busy
(due to reasons such as a low workload) and network paths to
˜d are not congested (due to reasons such as low interference),
it can be expected that the packets forwarded to ˜d drain out
fast and in consequence the queue Q( ˜d)
s(f ) will become smaller.
In this situation, a reasonable idea is to put more traffic to
this gateway. From algorithm 1, we can see that CLC DGS
exactly realizes this idea, so it can efficiently use the network
resource.
D. Performance bounds of CLC DGS
V
Q(d⇤)
To show why the exact amount of the traffic is set to
s(f ) (t)
and whether such traffic splitting combined with routing and
scheduling in CLC DGS can achieve the maximum network
utility, we need a rigorous proof. In the following, we present
Theorem 1, the main result of this paper, which states the
utility-optimal property of CLC DGS, and then we prove the
theorem.
Theorem 1: The CLC DGS algorithm yields the following
time average queue and utility bounds:
lim sup
t!1
1
t
t 1X⌧ =0 Xi2 ,d2GW
lim inf
t!1 Xf2F
i
g(f )(r(f )
E{Q(d)
s(f )(t)) Xf2F
tPt
⌧ =0 E{r(f )
s(f )(t) , 1
where r(f )
rate of CLC DGS for flow f until t, and ~r⇤ = (r⇤(f )
s(f )(⌧ )} is the achieved average
s(f ) ) is the
(⌧ )}
B + V Gmax
2µsym
.
(21)
g(f )(r⇤(f )
s(f ) )
B
V
.
(22)
0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See
http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI
10.1109/TVT.2015.2427091, IEEE Transactions on Vehicular Technology
7
optimal solution of the NUM problem of (8), and µsym is a
constant (defined in the proof process in Appendix B), and B
and Gmax are constants defined as:
B ,
NXi=1
[(Rmax
i
+ µin
max,i)2 + (µout
max,i)2].
max,i , max
µout
µ(d)
ib .
where
(23)
(24)
(25)
~S2 Xb2 ,d2GW
~S2 Xa2 ,d2GW
]Xf2F
i Rmax
i
max
is the maximum transmission rate out of a given node i and
max,i , max
µin
µ(d)
ai .
is the maximum transmission rate into node i.
Gmax ,
[(r(f )
s(f ))|Pf2F r(f )
g(f )(r(f )
s(f )).
(26)
Proof: The proof is provided in Appendix B.
Remark 3: Clearly, Theorem 1 proves the utility-optimality
of the CLC DGS algorithm. Note that Theorem 1 holds for
all V > 0, hence we can choose a sufficiently big value of
V so that B
V is arbitrarily small and the achieved utility of
CLC DGS in (22) is arbitrarily close to optimal.
E. Extensions of CLC DGS
1) Handling link heterogeneity: in CLC DGS algorithm
and most previous cross-layer design works, it is assumed
that the capacities of wireless links are uniform, and that all
transmissions are fully reliable once a feasible link schedule
is chosen. Now we consider a more complicated and practical
situation of link heterogeneity, where the capacities of links
are different, and where transmissions may still fail due to
external factors such as environment changes or user mobility.
Consider the system model defined in Section III, here we
introduce two more notations to characterize a wireless link.
We let cij(t) represent the capacity of link (i, j), and let pij(t)
(0 pij(t) 1) represent the packet delivery probability that
a packet transmission from node i is successfully received by
node j. We find that, to handle link heterogeneity, we only
need to make a minor modification to the CLC DGS algorithm
as follows. First, we redefine the maximum differential backlog
of link l = (i, j) at time slot t as
W ⇤l (t) = max
d2GW
cij(t)pij(t){Q(d)
i
(t) Q(d)
j (t), 0}
(27)
is, we multiply link capacity and packet delivery
That
probability when we compute differential backlog of a link.
Then we replace equation (19) of CLC DGS in Algorithm
1 with equation (27), and keep other parts of CLC DGS
unchanged.
We have derived that CLC DGS with this minor modification
can achieve maximum network utility under link heterogeneity,
that is, Theorem 1 still holds. The derivation process is very
similar to the derivation of CLC DGS. In particular, we first re-
formulate the network utility maximum problem by considering
link heterogeneity in (6). To do this, we replace (6) with the
following equation
µij = cijpij Xm:(i,j)2~Sm
⇡m.
(28)
Then we proceed the derivation following the same procedures
in Section III.B, Section III.C and the Appendices. Since the
derivation process is straightforward on the basis of CLC DGS
(actually, the main work is merely to re-derive equations (48),
(49) and (50) in Appendix B under the new constraint of
(28)), we omit the details. The simulation results in Section V
validate the efficiency of CLC DGS under networks with link
heterogeneity.
2) Handling gateway heterogeneity:
in wireless mesh
networks, different gateways may have different outgoing
capacities to the wired network. This causes an extra difficulty
for distributing an appropriate amount of traffic to gateways
according to the capacities of these gateways. To handle this
problem, different schemes have been proposed to realize load
balancing among different gateways. For example, the algorithm
in [11] assigns a cost to each gateway according to its capacity,
and then uses the cost for route updates. Through this route, the
algorithm directs less traffic to gateways with lower-capacity
so as to realize load balancing.
We find that CLC DGS can handle gateway heterogeneity
naturally, that is, CLC DGS automatically achieves perfect load
balancing without requiring to know the capacities of gateways.
The reason for this is similar to the argument in Remark 2: if
a gateway ˜d has a larger capacity, it can be expected that the
packets forwarded to ˜d drain out fast and in consequence queue
Q( ˜d)
s(f ) will become smaller. From Algorithm 1, CLC DGS will
put more traffic to this gateway, hence CLC DGS achieves
load balancing. We can also understand this point from the
theoretical aspects. Note that in the problem formulation and
the derivation process of CLC DGS, the capacities of gateways
do not form any constraint and consequently will not affect the
result of the derivation. Therefore, Theorem 1 still holds when
gateways have different capacities. The simulation results in
Section VI also demonstrate that CLC DGS achieves maximum
network utility in networks with gateway heterogeneity.
V. IMPLEMENTATION ISSUES
A. Distributed CLC DGS
One may note that
inherited from the cross-layer de-
sign framework, the routing and scheduling component of
CLC DGS is essentially a weighted back-pressure algorithm,
which operates in a centralized way and has exponential
computational complexity. In addition, this centralized approach
also requires to collect the global network information (i.e., the
queue length of each network node), which incurs signaling
overhead and protocol design complexity.
To cope this problem, we use a distributed approach to
realize the routing/scheduling component of CLC DGS. In
particular, we adopt a fully distributed CSMA-based algorithm
to realize the optimal back-pressure algorithm. The optimal
distributed CSMA-based back-pressure is first proposed in
[18], [19] in single gateway scenarios. While in our work,
we incorporate it with CLC DGS and implement it in our
simulator for the multiple-gateway scenarios, and then we
compare its performance with that of CLC DGS with the
centralized routing/scheduling component.
In the implementation, we make the distributed CSMA-
based algorithm running on each node independently. The
algorithm only requires local queue information on the node
itself and its neighboring nodes. Neighboring nodes exchange
0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See
http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI
10.1109/TVT.2015.2427091, IEEE Transactions on Vehicular Technology
queue information through piggybacking. After getting the
local queue information, each node computes its channel
contention probability and then contends for the channel
access following the IEEE 802.11-like CSMA contention
mechanism. Specifically, the contention aggressiveness for
packets to gateway d on each node i at time slot t in the CSMA
contention, denoted by zd
i (t), is decided by the following
equation,
zd
i (t) =
max
j2 neighbors
of
i{Q(d)
i
(t) Q(d)
j (t), 0}.
(29)
node
Note that the equation is essentially a distributed back-pressure
scheduling algorithm. Similar to equation (19) and (20), links
with larger backlog will have a larger contention aggressiveness,
and hence larger probability to be chosen in the next scheduling.
After a period of time, the chosen link set will converge to the
optimal set [18]. We use (29) to replace equation (19) and (20)
in CLC DGS so as to realize a distributed scheduling, and
the simulation results in Section VI show that this distributed
CLC DGS still outperforms state-of-the-art works significantly.
B. Delay differentiation
As other cross-layer control algorithms, CLC DGS dis-
tributes packets belonging to the same flow over multiple paths.
In addition, the back-pressure routing/scheduling component
requires to maintain a certain amount of queue backlogs to
operate, which leads to large flow delays.
To solve this problem, we use the delay differentiation
approach [27] with CLC DGS, which is motivated by the
observation that flows usually have different requirements on
delay. Using delay differentiation, we can distribute delays
among flows, that is, to achieve low delays for delay-sensitive
flows at the expense of increasing the delays of other flows, and
simultaneously guaranteeing maximum network utility. The
basic idea is to set a higher delay priority to preferred flows,
and incorporate the priorities in the operation of CLC DGS.
Specifically, we assign pf (p(f ) > 0), the delay priority, to each
flow f. A higher p(f ) means that flow f requires a smaller
delay. We incorporate the delay priority in Algorithm 1 as
follows. First, the rate controller at its source node s(f ) selects
d⇤ through the following equation replacing of (17)
d⇤ = argd2GW min p(f )Q(f,d)
(30)
Correspondingly, the rate controller injects an amount of traffic
into queue Q(f,d⇤)
s(f ) (t), and the amount of the traffic is equal
to r⇤(f )
s(f ) decided by the following equation:
s(f ) (t).
r⇤(f )
s(f ) =
V
s(f ) (t)
p(f )Q(f,d⇤)
.
(31)
Similarly, we take into account of delay priority in the
routing/scheduling component by replacing (19) in Algorithm
1 with the following equation
W ⇤l (t) = max
f2F,d2GW{p(f )(Q(f,d)
m (t) Q(f,d)
n
(t)), 0}.
(32)
Except for these changes, the basic procedure of Algorithm
1 remains the same. In next section, our simulation results
show that CLC DGS with delay differentiation can effectively
reduce the delays of the preferred flows.
8
VI. EVALUATION
Here we validate the performance of the proposed CLC DGS
algorithm through simulations. We implement CLC DGS and
other two algorithms PLASMA and CLC in a Java-based
simulator for comparison [11], [14].
PLASMA is proposed in [11], which is a typical repre-
sentative of works that are based on heuristics. Similar to
CLC DGS, a PLASMA mesh node won’t be associated with
a single gateway but packets from the node can be delivered
to any of the available gateways. Packets are also forwarded
over many paths towards each gateway, thus taking advantage
of both multi-path and anycast routing [11]. However, the
routing/scheduling of PLASMA is still based on a shortest-path
like algorithm, and we will show that such routing/scheduling
cannot guarantee an optimal use of network resource. In
addition, there is no rate control in the original PLASMA
algorithm2.
In contrast, both the routing/schduling component
and the traffic splitting/rate control component of CLC DGS
are carefully designed, and they together have been proved to
achieve maximum network utility, as shown in Theorem 1.
CLC is the traditional cross-layer control algorithm proposed
in [14]. As we noted before, the CLC algorithm just uses one
gateway and does not consider the case of multiple gateways.
For a fair comparison, we modify the CLC algorithm and
enable it to use all gateways. Specifically, we let a source
node randomly choose a gateway for each operation of traffic
splitting and rate control.
i
In terms of the parameters setting for the simulations, we
assume that every flow has infinite traffic and the buffer size
on each node is infinite, following the literature on cross-layer
design [13], [16]. The flow controller that runs on each source
node controls the admitted rate of each flow into a network.
= 10,8i and V = 30 in our simulations3. For
We set Rmax
each setting, we run the simulations for 10 times, and each
simulation runs over 104 time slots. We plot the average of the
simulation results and the confidence intervals in the figures. In
all our simulations, the utility function is set to g(.) , log(.).
We first simulate a simple topology with the one-hop
interference model of Fig. 2. For clear presentation and
understanding of the effect of CLC DGS, we start simulating in
an ideal network environment and then we gradually add other
issues to complicate the network environment. In particular,
in Sec. VI.A we evaluate performance of the three algorithms
in the ideal setting where all links are reliable and have
equal capacity, and the gateways have equal capacity. In Sec.
VI.B, we set heterogeneous links with different link capacities
and packet delivery probabilities, and heterogeneous gateways
with different capacities. In Sec. VI.C, we use more random
topologies including a 8x8 grid topology shown in Fig. 3, and
run more random simulations under the 2-hop interference
2Here for a fair comparison, we use Poisson traffic with appropriate
traffic rates for PLASMA. To get appropriate arrival traffic rates, we do
trial experiments before the actual running of the PLASMA algorithm. In the
trial experiments, we increase the flow arrival rates step by step. When the
arrival rates are saturated and the resulting flow throughput becomes stable,
we use the corresponding arrival rates as the input traffic rates.
0018-9545 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See
http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
