Optimal and Fair Transmission Rate Allocation Problem in Multi-Hop Cellular Networks
Optimal and Fair Transmission Rate Allocation Problem in Multi-Hop Cellular Networks
Optimal and Fair Transmission Rate Allocation Problem in Multi-Hop Cellular Networks
Introduction
Multihop Cellular Network preserves the benet of conventional single-hop cellular networks where the service infrastructure is provided by xed bases, and
also incorporates the exibility of ad-hoc networks where wireless transmissions
through mobile stations in multiple hops is allowed [1].
In ad-hoc networks, nodes communicate with each other in a peer-to-peer
way and no infrastructure is required. If direct communication is not feasible,
the simplest solution is to replace a single long-range link with a chain of short
range links by using a series of nodes between the source and the destination:
this is known as multi-hop communication [2]. The cooperation between these
two networks can be interesting as ad-hoc networks can expand the covered area
whitout the high cost of cellular networks infrastructure.
We address in this paper a bottleneck problem that summarizes the situation
of many multi-hop cellular networks, as illustrated in Figure 1. In our work, a
gateway - or base station (BS) - has entire access to the rest of the world and
provides this service in a more privileged way to some specic nodes, the relay
nodes (the white ones in Figure 1). Those nodes are themselves relaying the
service to the nodes in the free zone, called the terminal nodes (the gray ones in
Figure 1). It can happen that nodes in the free zone relay one another to get the
nal service. In our model, the relay nodes and the gateway form a single-hop
cellular network (the critical zone) that constrains the system.
C. Gomes is funded by CAPES, Brazil. This work has been partially supported by
European project ist/fet aeolus and is part of the CRC CORSO with Orange
Labs.
P.M. Ruiz and J.J. Garcia-Luna-Aceves (Eds.): ADHOC-NOW 2009, LNCS 5793, pp. 327340, 2009.
c Springer-Verlag Berlin Heidelberg 2009
328
Critical zone
Critical zone
(BS)
(BS)
Each node has a utility function representing its degree of satisfaction based on
the assigned rate transmission. The whole system is governed by the optimization
of the sum of utility functions over all the nodes, as in [3,4]. We give a model that
allows to transform the multi-hop network (Figure 1) into a single-hop network
(Figure 2), by eventually modifying the utility functions on the relay nodes, as
depicted in Figure 1.
The rest of this paper is organized as follows. In the next section we discuss
the related works. In section 3, we dene the problem, the adopted notation and
the considered hypotheses. The section 4 shows how the problem can be reduced
to a single-hop network. That is how the complete network utility functions can
be replaced by a small set of dierent functions assigned to the relay nodes, in
the context of a fair and optimal optimization. We push forward our results in
section 5 by applying them to specic cases of fairness.
Related Work
This described scenario occurs in multi-hop networks as considered in [1,2]. Indeed, it is observed that often in these networks the bandwidth is constrained
specically by a bottleneck around the gateway [5,6], conrming the fact that
it is a representative area. Many real networks deal with this situation. For instance, using UMTS technology for the single-hop network [7,4,8], while the free
zone is covered by WiFi or Bluetooth systems.
We show that there exists a set of utility functions that can be assigned to
the relay nodes replacing the complete set of utility functions. It is due to the
fact that the problem is convex under some conditions that are often met.
Convex optimization techniques are important in engineering applications because a local optimum is also a global optimum in a convex problem. Rigorous
329
optimality conditions and a duality theory also exist to check the solution optimality. Consequently, when a problem is cast into a convex form, the structure
of the optimal solution, which often reveals design insights, can often be identied. Furthermore, powerful numerical algorithms exist to solve convex problems
eciently.
We are interested in Pareto-optimal solutions, that is solutions where the
utility of an individual cannot be improved without decreasing the utility of one
or more other nodes. The fairness is a key issue in wireless networks, since the
medium is shared among the nodes. In our problem, it implies that each ow
going through a bottleneck receives a fair share of the available bandwidth. Our
work admits the generalized fairness criterion as dened in [3] that can assume
several criteria (see section 5 for more details), for example, the proportional
fairness one.
The proportional fairness has been studied in the context of the Internet ow
due the similarity to the congestion control mechanism of the TCP/IP protocols,
where each TCPs throughput is adapted as a function of the congestion. The
work in [9] addresses the question of how the available bandwidth within the
network should be shared between competing streams of elastic trac1 .
Model Definition
We distinguish here three main types of nodes. The BS that is unique in our
case, the relay nodes in R that have a limited link to the BS and the terminal
nodes in Tr that are connected to the BS through an unique relay node r at
the single-hop network. Note that multi-hops are allowed as long as connections
between terminal nodes are given for free, that is the relay node has bandwidth
enough for itself and its relayed terminals. The terminal nodes are considered
sparsely distributed around the cell, thus interference is not a problem at the
free zone.
We focus on the downlink channel (from the BS to the relay nodes) considering a given xed bandwidth. Let r be the rate of the downlink channel from
the BS to relay node r. Let t be the downlink rate at each node t Tr . We
consider the following hypotheses.
Hypothesis 1. All terminal nodes in Tr use an unique relay node r R.
Hypothesis 2. We only consider interferences between the relay nodes in R.
Note that the rst hypothesis allows multiple hops and routes in the free zone
but imposes to gather all the trac of an individual node to a unique relay in
the critical zone. The second hypothesis means also that the bandwidth is not
limited in the free zone.
1
The elastic trac tolerates packet delays and losses and permits the nodes to adjust
their rates in order to ll available bandwidth.
330
R
and
p
KNo . A vector of
r No +gb,r
r
b,r
rR
p
s=r b,s
rates is an optimal rate allocation if it is a solution to the following model on
variables and p:
Problem (P)
max
rR
Ur (r )
(1)
331
subject to
pb,r gb,r
, r R
No + gb,r s=r pb,s
pb,r KNo .
r
(2)
(3)
rR
r
gb,r (No
pb,r =
pb,r gb,r
, r R
No + gb,r s=r pb,s
+ gb,r
s=r
pb,s ), thus
r
(No + gb,r
pb,s gb,r pb,r ), r R.
gb,r
(4)
sR
Moreover, increasing all the powers by the same factor allows to tighten constraints (3) while relaxing constraints (2). By optimality we have
pb,r = KNo
rR
r
which, put into equation (4) gives pb,r = gb,r
(No (1 + gb,r K) gb,r pb,r ) and we
obtain:
r No (1 + Kgb,r )
pb,r =
, r R.
(5)
gb,r (1 + r )
r (1+Kgb,r )
gb,r (1+r )
= dr . As
rR
dr
dr gb,r
, r R.
(1 + gb,r (K dr ))
Ur
rR
dr gb,r
(1 + gb,r (K dr ))
(6)
subject to
rR dr K
dr 0, r R.
(7)
332
In this section, the problem is how to dene the cumulative utility functions
Ur (r ) for each relay node r R in a way to represent the utility functions
Ut (t ) of all nodes t Tr . Moreover, the available bandwidth of each relay node
has to be shared with fairness among the nodes in Tr .
Indeed, we prove that there exists a set of utility functions Ur (r ) (cumulative
functions) that can be assigned to the relay nodes replacing the complete set of
utility functions and, it can be expressed analytically in most cases. Moreover,
we show
that for any xed available bandwidth r at each relay node, if the
sum tTr Ut (t r ) is maximized it converges to a fairness equilibrium. Thus,
it is always possible to share r fairly among the nodes in Tr . The fairness
equilibrium point is dened by the utility function adopted. We consider the
following technical assumption.
Technical Assumption 1. The nodes utility functions Ut (.) are assumed to
be strictly increasing concave functions and satisfy the condition Ut (x) 1
x2 .
As said before the particular utility function Ur (r ) is dened as follows:
Problem (Pr )
Ur (r ) = max
Ut (t )
(8)
tTr
subject to
r =
t , r R.
(9)
tTr
We need the following lemma regarding how the rate r assigned to a relay
r R can be shared by all terminals it relays. Our objective is that given r we
can assign a fraction t of r for each terminal t Tr in a fair way.
Lemma 1. Given the vector = (1 , ..., |Tr | ) being the optimal solution for
the problem Pr , we consider a variable t [0, 1], a fixed feasible relay rate r
and we define t = r t . We obtain
t
r ,
Problem (Pr )
max
Ut (t r )
(10)
tTr
subject to
t 0, t Tr
tTr t = 1.
(11)
333
We can say that it is a local version of the problem Pr , in a way that an optimal solution for Pr considering the optimal value for r = arg maxr Ur (r )
can be translated into a locally optimal solution for Pr . We can rewrite the
constraints as:
t 0, t Tr
t 1
(12)
tTr
tTr t 1
Based on [10], the Lagrangian of this subproblem can be written as follow:
L() =
Ut (t r )
tTr
t (t )
tTr
t 1
tTr
t + 1
tTr
r|
with the lagrange multipliers i 0, 0 and 0. As = ( tr , ..., |T
r ) is
necessarily a vector of optimal solutions for the Lagrangian. So it veries KKTs
L
= 0 in , t Tr , which gives
optimality conditions:
t
r Ut (t r ) + t + = 0, t Tr .
334
Ur (r ) =
Ut ht h1
r (r ), r R.
tTr
Results
In this section we show some results using our model for the problem P . To
solve the model, we use a software library for nonlinear optimization of continuous systems, the Interior Point OPTimizer (IPOPT) that is part of the
COIN-OR project. We used the modeling environment AMPL (A Mathematical
Programming Language).
We show examples of utility functions and their cumulative representations
conrming the validity of our proof experimentally. For the sake of simplicity,
our examples consider a small network with 5 nodes: 2 relays and 3 terminals,
as shown in Figure 3.
2
3
1
4
5
Ut (t ) = ct ln(t )
ct
t
= y t , t =
ct
Ut
ct
yt .
Relay 1
Relay 4
0.06
Rate transmission fraction
335
0.05
0.04
0.03
0.02
0.01
0
0
Gain
tTr
tTr
ct ln
ct
tTr ct
Node 1 (ct=3)
Node 2 (ct=4)
Node 3 (ct=5)
Node 4 (ct=1)
Node 5 (ct=2)
Relay 1
Relay 4
0.06
Rate transmission fraction
ct ln(r ) +
0.05
0.04
0.03
0.02
0.01
0
0
Gain
Ur (r ) =
tTr
ct ln
1
r
Ut (t ) = ct t
ct
tTr
ct
c2
tTr
tTr
Ut (t ) and Ut (t ) = ct ln(t )
ct ln(r )+
tTr
c2
ct ln
ct
tTr
ct
Ut (t ) =
ct
t
2 r
tTr
ct
336
Relay 1
Relay 4
0.06
0.05
0.04
0.03
0.02
0.01
0
0
tTr
c2t r
Gain
Node 1 (ct=3)
Node 2 (ct=4)
Node 3 (ct=5)
Node 4 (ct=1)
Node 5 (ct=2)
Relay 1
Relay 4
0.06
Rate transmission fraction
0.05
0.04
0.03
0.02
0.01
0
0
Gain
tTr
Ut (t ) and Ut (t ) = ct t
Ut (t ) = c2t = yt , t = yctt . So, ht (yt ) = t = yctt . Consider x = hr (y) =
t
2
ct
tTr
1
c
that
implies
y
=
= h1
t
r (x). It gives the cumutT
y
x
r
lative utility
function:
ct
= ( tTr ct )2 1r .
Ur (r ) = tTr
ct
tTr
r
ct
Relay 1
Relay 4
0.06
Rate transmission fraction
337
0.05
0.04
0.03
0.02
0.01
0
0
Gain
tTr
ct )2 1r
Node 1 (ct=3)
Node 2 (ct=4)
Node 3 (ct=5)
Node 4 (ct=1)
Node 5 (ct=2)
Relay 1
Relay 4
0.06
Rate transmission fraction
0.05
0.04
0.03
0.02
0.01
0
0
Gain
tTr
Ut (t ) and Ut (t ) =
ct
t
1
t
(14)
1
This function is interesting because it generalizes all the following important
cases of fairness:
The globally optimal allocation: when = 0, that is max tTr t .
The harmonic mean fairness: when = 2.
The MaxMin fairness: when , max mintTr t .
1
t
The proportional fairness: when 1, max tTr lim1 1
=
(1)
e
ln(t )
1+(1)ln(t )
, that is max tTr ln(t ).
tTr lim1
tTr
1
1
It is equivalent to max tTr t that in a convex framework represents the
Nash Equilibrium.
Ut (t ) = ct
338
Relay 1
Relay 4
0.035
0.03
0.025
0.02
0.015
0.01
0.005
0
0
0.5
1.5
2.5
3.5
4.5
k at (10)
Fig. 10. Cumulative function Ur (r ) =
0.04
tTr ct
x1
1
Node 1 (ct=3)
Node 2 (ct=4)
Node 3 (ct=5)
Node 4 (ct=1)
Node 5 (ct=2)
Relay 1
Relay 4
0.035
Rate transmission fraction
0.03
0.025
0.02
0.015
0.01
0.005
0
0
0.5
1.5
2.5
3.5
4.5
k at (10)
tTr
Ut (t ) and Ut (t ) = ct
1
t
1
The previous utility functions are in fact the utility function in (14) with a
given (respectively = 1, = 12 and = 2). Considering directly the
1
t
1 ,
we have: Ut (t ) = ct
= yt , t = yctt . So,
t
1
1
tTr ct
ht (yt ) = t = yctt . Consider x = hr (y) =
h
=
that im1
t
tTr
y
1
1
1
c
c
tTr t
ct
t
plies h1
. Thus Ur (r ) =
=
1
r (x) =
tTr 1
x
function Ut (t ) = ct
tTr ct
1
ct
tTr 1 ct
tTr ct
x
Ur (r ) =
ct
tTr
x1
.
1
339
(15)
We show an example of our problem using the utility function in (14) for all
nodes considering dierent values of .
Figures 10 and 11 show the obtained rate t varying (with xed channel
gain gb,r = 2, r). Figure 10 shows the rates considering the cumulative function
in (15). Figure 11 shows the rates of all the nodes using the utility function in
(14), note that each node has a dierent value for the constant ct . The gures
in this section show that we obtain the same graph for the relay nodes in both
approaches as we proved.
We have considered in this paper the transmission rate allocation problem for
multi-hop cellular networks in a way to reach an optimal and fair solution. We
show that it can be reduced to a single-hop problem by only changing the utility
functions. We conrm the validity of our proof experimentally.
Reducing multi-hop problems into problems with an unique cell (single-hop)
has many advantages for the optimization problem. First we can reuse techniques
that were designed basically for the one-cell case [7,4,11]. Second, we can identify
bottlenecks, and in particular see if a congestion is due to the particular situation
of a relay node, or to the specic utility function of the terminals it relays.
Of course the question on implementing distributed algorithms based on those
results remains open. We can wonder if a pricing strategy is achievable. Another
question is what kind of intermediate capacity restrictions on the second (or
more) hop(s) can be added if we want to keep the same good properties.
References
1. Lin, Y.-D.J., Hsu, Y.-C.: Multihop cellular: A new architecture for wireless communications. In: INFOCOM, pp. 12731282 (2000),
http://citeseer.ist.psu.edu/lin00multihop.html
2. Fitzek, F., Katz, M. (eds.): Cooperation in Wireless Networks: Principles and Applications Real Egoistic Behavior is to Cooperate! Springer, Heidelberg (2006)
3. Mo, J., Walrand, J.: Fair end-to-end window-based congestion control. IEEE/ACM
Transactions on Networking 8, 556567 (2000)
4. Altman, E., Galtier, J., Touati, C.: Fair power and transmission rate control in
wireless networks. In: Proc. of IEEE GlobeCom 2002, Taipei, Taiwan (November
2002)
5. Bermond, J.-C., Galtier, J., Klasing, R., Morales, N., Perennes, S.: Hardness
and approximation of gathering in static radio networks. Parallel Processing Letters 16(2), 165184 (2006)
6. Gomes, C., Prennes, S., Rivano, H.: Bottleneck analysis for routing and call
scheduling in multi-hop wireless networks. In: 4th IEEE Workshop on Broadband
Wireless Access (BWA), December 4 (2008)
340
7. Yun, L., Messerschmitt, D.: Power control for variable QoS on a CDMA channel.
In: IEEE MILCOM, vol. 1, pp. 178182 (1994)
8. Price, J., Javidi, T.: Leveraging downlink for regulation of distributed uplink cdma.
In: GLOBECOM (2006)
9. Kelly, F.P., Maulloo, A., Tan, D.: Rate control in communication networks: shadow
prices, proportional fairness and stability. Journal of the Operational Research
Society, Statistical Laboratory 49, 237252 (1998)
10. Hiriart-Urruty, J.-B., Lemarchal, C.: Fundamentals of Convex Analysis. Springer,
Heidelberg (2001)
11. Galtier, J.: Adaptive power and transmission rate control in cellular CDMA networks. In: Globecom (2006)