This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.
Resource Allocation in Multi-Radio Multi-Channel Multi-Hop Wireless Networks
Simone Merlin
DEI, University of Padova Padova, Italy 35131 Email: simone.merlin@dei.unipd.it
Nitin Vaidya
University of Illinois at Urbana-Champaign Illinois, USA 61801 Email: nhv@uiuc.edu
Michele Zorzi
DEI, University of Padova Padova, Italy 35131 Email: michele.zorzi@dei.unipd.it
Abstract—A joint congestion control, channel allocation and scheduling algorithm for multi-channel multi-interface multihop wireless networks is discussed. The goal of maximizing a utility function of the injected traf?c, while guaranteeing queue stability, is de?ned as an optimization problem where the input traf?c intensity, channel loads, interface to channel binding and transmission schedules are jointly optimized by a dynamic algorithm. Due to the inherent NP-Hardness of the scheduling problem, a simple centralized heuristic is used to de?ne a lower bound for the performance of the whole optimization algorithm. The behavior of the algorithm for different numbers of channels, interfaces and traf?c ?ows is shown through simulations.
I. I NTRODUCTION New challenges in wireless network design refer to a more ef?cient bandwidth utilization and the use of new networking paradigms. The former goal is related to the growing bandwidth demand and the scarcity of available spectrum. The latter refers to the need for ?exible and easy deployment, self con?guration and adaptation to the working condition. Multihop wireless networks have been identi?ed as a valuable networking paradigm able to ful?ll the previous requirements. Examples of multi-hop wireless networks include ad hoc networks and mesh networks. Practical interest in multi-hop wireless networks is con?rmed by the recent development of standards which explicitly encompass the mesh paradigm, where the backhaul network is organized in an ad hoc topology. The IEEE 802.16 standard [3] is one example. In the context of 802.11 networks a special working group is dedicated to the mesh extension, which is referred to as 802.11s [4]. Other standardization efforts are focusing on the introduction of mesh-like support in their network architecture, such as 802.15.3/4, where the network architecture implicitly supports a mesh-like structure, and 802.15.5, which is working to de?ne a mesh structure for personal area networks. It is clear that a deep understanding and the ability to optimize the performance of multi-hop wireless networks will offer signi?cant bene?ts in these contexts. With the motivation of improving the performance of multihop wireless networks, in the last few years great attention has been devoted to networks where each node is provided with multiple radio interfaces and can operate on multiple channels [1]. This new degree of freedom has been proved to potentially allow for increased capacity with respect to
Research reported here is supported in part by U.S. National Science Foundation award CNS 06-27074, U.S. Army Research Of?ce grant W911NF05-1-0246 and “Ing. Aldo Gini” Foundation, Padova, Italy. Any opinions, ?ndings, and conclusions or recommendations expressed here are those of the authors and do not necessarily re?ect the views of the funding agencies.
single-channel single-interface networks [2]. This approach is particularly interesting if applied to 802.11 networks, since multiple channels are already available and devices provided with multiple wireless networking cards are being designed and already exist in some testbeds. A lot of effort has also been spent in the last few years to understand the challenges related to resource allocation in such networks, where the increased number of variables to be jointly optimized representes a big issue. The problem has been approached from different perspectives, ranging from heuristic and protocol oriented solutions [3], [4], [5], [6], whose performance is far from being exactly de?ned, to the determination of theoretical bounds [7], [8], [9], whose practical implementation is not straightforward. It is thus worth investigating an approach aiming at the design of practical algorithms based on a solid theoretical background, which can be analytically proved to guarantee some performance bounds [9]. The aim of this paper is to provide a simple and clear framework for investigating the performance of multi-channel multi-radio networks as a function of the number of channels, interfaces and concurrent end–to–end transmissions. We consider the problem of joint congestion control, channel allocation and scheduling for multi-hop wireless networks in a general communication and interference scenario. The problem is formulated as a joint optimization, which is then solved by a dynamic algorithm. A speci?c simpli?ed scenario is evaluated, where the scheduling is actually an inherently NPHard problem, and thus a heuristic is proposed. The channel loading and scheduling approach is somewhat similar to the one proposed in [9] but our paper focuses on a throughput optimal approach [10], is inherently multi-hop, and congestion control is also integrated in the framework. We build on past work on network utility optimization (discussed in Section III), by using the notion of virtual links to facilitate the analysis of multi-channel networks. The paper is organized as follows. The complete system model and the goal of the proposed analysis are presented in Section II. Related work is reviewed in Section III. The optimization problem is formulated in Section IV and the proposed solution is presented in Section V together with stability issues, addressed in Section VI. The scheduler is de?ned in Section VII and simulation results for the whole algorithm are in Section VIII. Conclusions end the paper. II. S YSTEM MODEL Our system model is derived from similar models used in past work [9], [10] with suitable modi?cations to capture the
1283
978-1-4244-2026-1/08/$25.00 ? 2008 IEEE
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.
availability of multiple channels, as described below.
Node n
λ1 n
+
P
1 jc rjnc
1 γn1 1 γnC
Ch. 1
1 {rnj1 }j
Ch. C
Commodity 1
1 {rnjC }j
λS n
+
P
S jc rjnc
1 γn1 S γnC
Ch. 1
S {rnj1 }j
Ch. C
Commodity S
S {rnjC }j
Fig. 1.
Node model
Consider a multi-hop wireless network. Each node in {n : n = 1, . . . , N} is provided with In half duplex wireless interfaces. At any given time, each interface can tune to any one of C channels {c : c = 1, . . . , C}. The channel used by an interface may change over time. For the algorithm de?nition, a general interference model is initially assumed (which can also encompass non-orthogonal channels). In Section VII, a simpli?ed interference model based on orthogonal channels, and communication and interference graphs, is used in order to de?ne a greedy heuristic. Traf?c ?ows are, in general, carried over multi-hop routes. Each set of ?ows with the same destination will be referred to as a single commodity in the following. Let {s : s = 1, . . . , S} be the commodities set. The input rate for commodity s at node n is λs . Let λ be the vector of all input rates. Each input n rate can assume values λs ∈ Λs . n n As a result of the proposed algorithm, each node n will s be provided with an input queue Un,in for each commodity s s, and C × S output queues, Un,c,out one for each channelcommodity pair. All the incoming traf?c for commodity s is s loaded on queue Un,in . Output queues for commodity s are s loaded using packets stored in queue Un,in , according to the policy described in the next sections. Inside each node, and for each commodity, a connection is de?ned between the input s s queue Un,in and each of the output queues Un,c,out on different channels, for the same commodity. Such connections will be s referred to as virtual links in the following. Let γn,c be the s rate at which data is transferred from the input queue Un,in to s the output queue Un,c,out , i.e., the rate of the associated virtual s link. Let γ denote the vector for all γn,c and Ψ its feasible set, which represents the rate region for the virtual links. The set Ψ will be de?ned in Section VI, based on a stability argument and in order not to modify the capacity region of the actual network. s Let ra,b,c be the transmission rate associated with the ?ow between nodes a and b on channel c, carrying traf?c for commodity s, and let r be the corresponding vector for all a,b and c. The physical layer capacity for the link between nodes a and b on channel c is denoted as wa,b,c . Let us denote by w
the vector consisting of wa,b,c for all nodes a, b and channel c. The feasible rate region, i.e., the set of all feasible w vectors, is denoted as W, which depends on the interference model, and, in general, is also constrained by the limited number of wireless interfaces at each node. The utility function for commodity s associated with each source node n is denoted by Gs (λs ). To allow the use of n n convex optimization techniques, all the utility functions are assumed to be strictly concave, and the rate vectors w will actually be considered as belonging to the convex hull of the set W, w ∈ Co(W). Similar assumptions have been made in past work as well [11], [10]. The goal of the proposed algorithm is to jointly de?ne ? congestion control ? routing ? channel loading ? interface binding and scheduling with provable properties in terms of stability (achieved P when the following property is satis?ed: s s limt→∞ E[ n,c,s (Un,c,out + Un,in )] < +∞) and network utility maximization. The use of multiple queues, similarly to [9], has been chosen in order to exploit multichannel weighted matching algorithms in the scheduling operation. The algorithm presented in [12], which is based on non-weighted matchings, can also be adapted to ?t in our framework. As will be clear in the following, in case C = I (e.g., OFDMA systems) the scheduling problem turns out to be decoupled along channels. Suboptimal heuristics could also take advantage of individual channel queue length information. In the following, a general formulation is presented in terms of an optimization problem on a network ?ow. A Lagrangian relaxation allows to de?ne a distributed utility maximization, channel loading and scheduling based on the concept of “backpressure” [10]. Our approach makes use of “virtual links” for loading the queues on each channel. A stability issue in the de?nition of virtual link rates is discussed below, and a Lyapunov argument is used to justify the solution. A heuristic way to solve the scheduling optimization is also discussed for the case of a simpli?ed transmission and interference model. A lower bound for the performance of the joint algorithm is also identi?ed later in the paper. III. R ELATED WORK The concept of “layering as optimization decomposition” has been investigated in the last few years as a powerful way to analytically de?ne cross layer optimization problems and at the same time design feasible algorithms for their solution [11]. In particular, joint algorithms for congestion control and transmission scheduling have been proposed [13], [14] which are able to jointly optimize source rate and link scheduling [10], [15], [16] including also the power control operation [17], [18]. The mathematical tools widely used in this new approach are essentially optimization problem decomposition by Lagrange relaxation, sub gradient algorithms and Lyapunov stability [19], [20]. The work presented in this paper is based on the decomposition of an optimization problem de?ned over the multi-channel network model. The solution is related to the general scheduling algorithm presented in [10], [17]. Given a set of input rates which lies
1284
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.
inside the capacity region of the system, this algorithm is able to guarantee stability (i.e., bounded queue lengths). The core of the scheduler is based on the maximization of a metric which depends on the rate allocated to each link, multiplied by the difference between the queue length at the link receiver side minus the queue length at the transmitter side (thus the name “backpressure”). In [10], a congestion controller is added on top of the scheduling algorithm which is proved to converge to a solution close to the optimum. The use of an imperfect scheduler in the joint scheduling and congestion control may in general lead to poor performance [21]. In case an imperfect scheduler is used, the joint algorithm presented in [10] is proved to be able to guarantee stability within a capacity region scaled by a factor which depends on the imperfect scheduler. This opens the way to the implementation of reduced complexity schedulers. In case a “protocol interference” model is considered, the scheduling, for a single channel scenario, becomes a weighted maximum independent set problem. The problem is in general NP-hard [22]. Clearly, a greedy centralized algorithm which selects at each step the link with the highest metric and discards all the interfering links can achieve a capacity region reduced by a factor of 1/K where K is the interference degree [21]. In [23], it is pointed out that such a greedy approach is optimal in graphs with particular structure. Algorithms based on a maximal independent set scheduler (non weighted) are known for single hop networks and are presented in [24], [25], but this approach can not be extended to the multihop case. In this case a different scheduler has to be used, which exploits additional information on the traf?c intensity or number of hops [26]. A novel approach for the scheduling problem is also proposed in [12], where a randomized algorithm is used. The problem of maximizing the backpressure function is converted to the problem of comparing the backpressure value obtained in subsequent random schedules. At each time slot, the backpressure achieved by a new random maximal matching is compared with the one achieved by the previous schedule. The best schedule is applied. A distributed algorithm is also presented. The closest work for multi-channel multi-radio wireless networks is the one in [9]. The authors propose a channel loading mechanism which, combined with a multi-channel maximal scheduler, is able to keep the network stable inside a subset of the capacity region. The network model is such that each node is provided with an input queue for each commodity and an output queue for each commodity-channel pair. A known traf?c rate is applied at each input queue for each node and, based on a metric accounting for the queue lengths of all interfering nodes, a channel loading policy is de?ned. A multi-channel maximal scheduler is then applied to schedule the backlogged links. This approach is extended to the multihop case only for the case where information on the source rate is available and a congestion control is not considered. An optimization approach is also used in [8], where an LP network ?ow problem is de?ned to model routing and channel loading. The solution is used to obtain an upper bound for the performance. A greedy scheduler based on the outcome of the previous LP solution is then applied for solving the actual resource allocation. A similar analysis is also found in [7].
In this paper, a network structure similar to the one in [9] is assumed, and the optimization approach is based on the decomposition presented in [11] and the argumentation in [10]. We propose an algorithm that works in a multihop scenario, and whose simple channel loading mechanism is based only on local information. The complexity is moved to the scheduling operation, which in general can be very complex. The proposed algorithm makes use of one input queue at each node for each commodity and one output queue for each channel–commodity pair at each node. The queue lengths are used, at each time step, to make dynamic decisions about congestion control, channel loading and transmission scheduling. In particular, “virtual links” are introduced in order to model the channel loading operation. The algorithm is analytically formulated and then tested by simulation in a simpli?ed communication and interference scenario. The impact of the number of channels, interfaces and commodities on the network performance is investigated. IV. F ORMULATION AS AN OPTIMIZATION PROBLEM The goal of the proposed algorithm is to solve the following optimization problem (see Table I for a summary of the symbol de?nitions): X max Gs (λs ) (1) n n
λ,r,w,γ n,s
X
i,c
s ri,n,c
+
λs n
≤
j
s γn,c ≤
X
s
s ri,n,c ≤ wi,n,c ?i, n, c
X
X
c
s γn,c
s.t.: ?n, s
(2) (3) (4) (5) (6) (7)
s rn,j,c ?n, c, s
In the previous model: (1) is the objective function ? (2) is the ?ow conservation constraint at the input of each node ? (3) is the ?ow conservation constraint at the output of each node ? (4) is the constraint that the aggregate ?ow on a link must not exceed the physical rate ? (5) is the constraint on the ?ow in the virtual links for the channel loading: this will be speci?ed to model different requirements. Note the convex hull operator. ? (6) is the feasible rate region for the actual links. ? (7) is the feasible set for the input rates. Based on the assumption on the utility functions and on the convexity of the domain, (1)-(7) is a convex optimization problem.
?
γ ∈ Co(Ψ) w ∈ Co(W) s λn ∈ Λs ?n, s n
V. N ETWORK FLOW OPTIMIZATION The solution of the optimization problem is obtained via its dual problem, relaxing all the constraints (2) and (3). The procedure is based on prior work in [20] and [10]. s s Let Uin = [Un,in ] and Uout = [Un,c,out ] be the vectors for all the Lagrange multipliers associated to constraints (2) and
1285
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.
Symbols: Gs (λs ) n n λ = [λs ] n s r = [ra,b,c ] s γ = [γn,c ] w = [wa,b,c ] Ψ W Λs n
Utility function Injected input rate Flows associated to channel-link-commodity connections Flows that load output channel-commodity queues Physical rates associated to physical channel-link Feasible “virtual rate region” for channel loading Feasible rate region for actual physical links Feasible input rates TABLE I S YMBOLS
(3) respectively. Let U = [Uin , Uout ] be the vector for all the Lagrange multipliers. Relaxing the constraints (2) and (3), the Lagrange dual function for the problem is: ( X
n,s
L(U) =
max
λ,r,w,γ
Gs (λs )+ n n X
j,c s rj,n,c ? λs + n
+
X
n,s
+
where the optimization variables λ, r, w, γ are still subject to constraints (4)-(7) (here, and in the following, constraints are omitted to simplify notation). The previous expression can be rewritten as: ( X
n,s
?? ? X X s s s Un,c,out ??γn,c + rn,j,c ? , ? s,c,n ?
j
s Un,in ??
?
X
c
s γn,c ? +
?
L(U) = max
λ
Gs (λs ) n n
Note how each maximization represents a different “layer” in the optimization task: ? (8) congestion control; ? (9) ?ow allocation, routing and physical rate allocation; ? (10) channel management (stability, channel loading, ... ) ? Let λ(U), r(U), w(U), γ (U) be the vectors of optimum ? ? ? values for a given set of Lagrange multipliers, that clearly depend on U. The optimizations in (8) and (10) can be carried out based only on local information, and are thus suitable for a distributed implementation. The optimization of r and w in (9) instead requires the knowledge of the feasible ? ? rate region W and could in general be solved by using a centralized algorithm, even though distributed solutions can be developed under particular interference assumptions, such as for example in [12]. In particular, in order to optimize (9), for each link between nodes i and j on channel c de?ne ?? s ?? s s? = arg maxs Uj,c,out ? Ui,in . The ?ow allocation is s? s given by setting ri,j,c = wi,j,c and ri,j,c = 0 for s 6= s? .
? ? ?X ? ? s ? s s Ui,c,out ? Uj,in ri,j,c + (9) + max r,w ? ? i,j,s,c ( ) X? ? s s s Un,in ? Un,c,out γn,c . (10) + max
γ s,n,c
s ? λs Un,in n
)
+
(8)
were each is a constant, which is set according to the stability and capacity preservation criterion discussed in Section VI. Under this assumption, the maximization in (10) requires that for ?? each node n and commodity s, ?? s s is chosen. If = arg maxc Un,in ? Un,c,out c? ? s ? s s Un,in ? Un,c? ,out > 0 then set γn,c? = Γs and all n s s γn,c = 0 for c 6= c? , else set all γn,c = 0 ?c (so that the summation is 0; otherwise the summation would be negative). This is essentially the backpressure based algorithm for the virtual links γ. The Lagrange function is convex, thus the multipliers can be computed using a sub gradient algorithm. It is known that a sub gradient for a given vector of Lagrange multipliers is the vector consisting of all multiplicative terms in the Lagrange function. Note that such multiplicative terms are the results of maximizations (8)–(10). With this choice, the Lagrange multipliers are computed using a sequential algorithm which, at each step, updates them based on the value of the local sub gradient. Let t be the iteration index, which can be associated with a time-slot in the system evolution. Thus the updating rules for each multiplier at time t + 1 are: h s s ? Un,in (t + 1) = Un,in (t) + α1 (λs (U(t))+ n ?+ X X rj,n,c (U(t)) ? ?s γn,c (U(t)))? ?s (11) + Γs n
j,c c
Once the ?ow to be potentially loaded on a physical link has been chosen, the following maximization has to be performed: nP o ? s? ¤ s? + w = arg maxw ? Ui,c,out ? Uj,in wi,j,c . This is the i,j,c backpressure algorithm [10]. In Section VII, an assumption about a speci?c feasible rate region will be discussed, and the design of a greedy algorithm to compute w will be presented, together with a lower bound ? performance index. Suppose for the moment that the only constraint imposed to the virtual link rates is: X s γnc < Γs n
c
In order to get a solution which converges to a stable value, α1 and α2 should be set to be small constants, whereas in the case α1 = α2 = 1 the solution will exhibit an oscillatory behavior around the convergence point. However if α1 = α2 = 1 the Lagrange multipliers obey the same dynamic equation as the queue lengths. This makes this case most interesting from a practical perspective, since the optimization can be performed by just measuring the queue lenghts and using these values directly in the algorithm. For this reason, we will focus on this case in the following. Note that at each time t a new sub gradient has to be computed, thus the optimizations (8)–(10) has to be repeated ? at each time slot. Let λ(t), r(t), w(t), γ (t) denote the vectors ? ? ?
1286
? s s γs Un,c,out (t + 1) = Un,c,out (t) + α2 (?n,c (U(t))+ ?+ X rn,j,c (U(t)))? . ?s ?
j
(12)
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.
Algorithm 1 Joint optimization
At each time step t, perform the following operations. 1) Congestion control. For each commodity s and node n: ? ? s ?n λs (t) = sup{λs ∈Λs } Gs (λs ) ? λs Un,in (t) n n n n n 2) Channel allocation. For each commodity s ?? node n: and ?? s = ? s c? ? arg maxc Un,in (t) ? Un,c,out (t) , s s if Un,in (t) ? Un,c? ,out (t) > 0 then ?s set γn,c? (t) = Γs and all γn,c (t) = 0 for c 6= c? ?s n else set all γn,c (t) = 0 ?c. ?s end if 3) Scheduling and routing. For each link between nodes i and j on channel c: ?? s ?? s s? = arg maxs ? Ui,c,out (t) ? Uj,in (t) . ? i+ h ? P s s? w = arg maxw ? Ui,c,out (t) ? Uj,in (t) wi,j,c i,j,c ? ? ? s s? if Ui,c,out (t) ? Uj,in (t) > 0 then
?
where B is a constant term depending on the r terms. According to Corollary 3.9 in [10], if the input rate λs n (which is loaded only on the input queue) is such that λs + ?n, s (for a small ) lies inside the capacity region, n then there exists a randomized scheduling r, w and γ, such ? ? ? that ? ? X X γn,c ? ?s ri,n,c ? = + λs ?n, s, c ?s E? n
c
? ?s set ri,j,c (t) = wi,j,c (t) and all ri,j,c (t) = 0 for s 6= s? ?s else set all ri,j,c (t) = 0 ?s ?s end if 4) Queues update: the queues are automatically updated according to the rules in (11) and (12) with α1 = α2 = 1.
and thus choosing a schedule r, w, γ according to the maxi? ? ? mization in (9) and (10), then (14) and (15) can be bounded leading to X s Un,in + ?(U(t)) ≤ B 0 ? 2 + ? X X
n,s c s γn,c
E?
?
i,c
X
j
rn,j,c ?s
?
γn,c ? ?s
?
= 0 ?n, s
!2
n,s
+
n,c,s
solutions of the optimization variables where the time index has been explicitly shown, whereas U is neglected to simplify notation. Based on the previous argumentation, the proposed algorithm for joint congestion control, channel allocation and scheduling is presented in Algorithm 1. VI. C HANNEL L OADING : S TABILITY BY LYAPUNOV DRIFT In the previous section the feasible rate set for the virtual links used for the channel loading has not been speci?ed. Here it is proved that a suf?cient condition for stability requires the aggregated rate of the virtual links, used for the channel loading, to be bounded. The stability of the system is derived using a Lyapunov argumentation. Consider the input rate for all commodities as ?xed (no congestion control) and assume it falls within the capacity region of the network. P s 2 PThe considered Lyapunov function is L = n,s (Un,in ) + s 2 n,s,c (Un,c,out ) and the proof is derived from the one in [10] Sec. 4.2. Consider the queue updating rules (11), (12) with α1 = α2 = 1. The drift associated to the Lyapunov function L is denoted with ?(U(t)) = E [L(U(t + 1)) ? L(U(t))|U(t)] and can be easily bounded as X s ?(U(t)) ≤ B + 2 Un,in (t)E [λs (t)] + (13) n ?2E ? ?2E ?
ns i,j,c,s
P P s P s Note that if n,s ( c γn,c )2 + n,c,s (γn,c )2 is bounded, the drift becomes negative as the queue lengths increase above a given threshold. Thus for instance we can de?ne the feasible P s s rate for the virtual link as Ψ = {γn,c : c γn,c < Γs ?s, n}, n with Γs suitable positive constants. The proposed network n model arti?cially adds the virtual links to the original network structure, thus we have to make sure the resulting network is able to provide the same capacity region as the original one. To guarantee such a property, a value for each Γs can be chosen n as the smallest value greater than the maximum possible output rate for a node (which is bounded). VII. S CHEDULING The scheduler de?ned in general terms in the previous section requires a centralized optimization. Here a speci?c communication and interference model is considered; each node can communicate with any other node within a distance Rc ; for a correct reception no concurrent transmissions are allowed within a distance Ri from the receiver and the transmitter. In this case, the problem of scheduling non interfering links while maximizing (8) is equivalent to ?nding the maximum weighted independent set in a weighted graph. Additional constraints imposed by the reduced number of interfaces have to be considered. Note that the maximum weighted independent set problem (de?ned for the single channel case) is known to be NP-Hard [22]. It is known [9], [21] that a greedy sequential and centralized algorithm that at each step selects the link with the highest metric and drops all the interfering links can reach at least a fraction β = 1/K of the maximum value in (9), where K is the maximum number of links that cannot be scheduled because a given link has already been scheduled. In fact, at each step at most K additional links with a weight equal to or smaller than the selected one could have been scheduled. Note that the constraint on the number of interfaces can cause a link activation to prevent the use of other links in different channels. Thus K depends on the topology and on the number of channels and interfaces. This greedy scheduler allows for
1287
X
s (γn,c )2 .
(17)
"
X
c,n,s
X
s s s ri,j,c [Ui,c,out (t) ? Uj,in (t)] | U(t)? + s s γn,c[Un,in (t) s ? Un,c,out (t)] |
? #
(14) (15) (16)
U(t) +
s (γn,c )2 ,
+
? X X
n,s c
s γn,c
!2
+
n,c,s
X
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.
the solution of the whole optimization problem to converge to the optimum referred to a capacity region scaled by a factor β [10]. The previous lower bound is very conservative and the actual performance of the greedy procedure is expected to be much better than stated above. Some reasons are listed below: i) the number of contending nodes is actually only the number of backlogged nodes with positive backpressure, thus, as long as the network is not heavily loaded, this number is much smaller than K; ii) the loss in optimality β is itself a lower bound, as it assumes that each time a link is scheduled, all the dropped links have a weight which is close to the one of the scheduled link; iii) the maximal scheduling is close to the maximum scheduling in most practical topologies [23]. In the following, the proposed cross layer algorithm has been tested using such a greedy centralized scheduler for a given topology. VIII. S IMULATION RESULTS In this section the whole algorithm is tested using the greedy centralized scheduler previously described. The presented framework allows for an extensive evaluation of the performance of a multi-channel multi-radio network as a function of several parameters, i.e., number of channels C, number of interfaces per node I, and number of commodities S. In particular, the number of interfaces is the most interesting parameter, since it represents the peculiar feature of this kind of networks, and has been the focus of previous theoretical results. In all the scenarios, the capacity of each interference free scheduled link is ?xed to 1/C for a fair comparison among scenarios with different numbers of channels. The utility function is the same for all the nodes and is de?ned as Gs (x) = log(x), which n implements a fairness based congestion control. Simulations have been performed by using Matlab. A. Comparison with optimum solution As previously stated, to ?nd the optimum solution of the scheduling problem is a very complex task. In Figure 2 the aggregated received throughput is shown both for the case of the optimum solution and for the heuristic one. The optimum solution is obtained by an exhaustive search on the solutions tree. The considered scenario is a regular linear deployment of 6 nodes, where each node communicates and interferes with the nearest neighbors. Two commodities are considered. Even in this simple scenario only a very small number of channels could be tested. In these simple but not trivial cases, the heuristic solution is able to reach a value very close to the optimum. B. Grid topology The algorithm has been simulated in a single network snapshot composed by N = 16 nodes, placed in a regular mesh with a distance of 0.2 units between adjacent nodes. In this scenario Ri = Rc = 0.3. The system has been tested with C ∈ {1, 2, 4, 8}, I ∈ {1, ..., C}, S ∈ {1, 2, 4}. As can be seen from Figure 3, in all cases the aggregated utility increases as the number of interfaces increases. Anyway, the additional utility gained adding a new card decreases as the number of cards increases. For instance, in case of C = 8, only 4 interfaces are enough for achieving the maximum utility. This is in accordance with the asymptotic analysis presented
Comparison: optimum, heuristic, randomized 0.7 0.65 0.6 0.55 0.5 Rate 0.45 0.4 0.35 0.3 0.25 0.2 1 1.5 2 # of interfaces 2.5 Optimum Heuristic 3
Fig. 2. Comparison between solutions with optimum and heuristic scheduler. Solid: optimum; dashed: heuristic
Aggregated utility 0 S=1 ?2 S=2 ?4 Utility
?6 S=4 ?8 C=1 C=2 C=4 C=8
?10
?12
1
2
3
4 5 # of Interfaces
6
7
8
Fig. 3. Total utility for different numbers of channels, interfaces and commodities.
in [2]. The utility is negative because a logarithmic function is used and, in the simulated scenario, a normalized bandwidth value has been considered. Moreover the utility decreases as the number of concurrent ?ows increases. This is due to the speci?c scenario where the rate experienced by a single ?ow decreases as the number of ?ows increases due to the sharing of the medium. Even though throughput maximization is not the main goal of the simulated algorithm, in Figure 4 the aggregated transmission rate of all commodities is shown. Similarly to the utility behavior, the aggregated rate increases as the number of interfaces increases and the maximum value is reached using a number of interfaces smaller than the number of channels. As the number of commodities increases, the aggregated rate increases, showing that the spatial reuse of the medium is exploited. In Figure 5 the average queue length in the stationary regime is shown as a function of the number of interfaces and channels. As the number of interfaces increases the average length decreases. This has an impact on the end-to-end delay,
1288
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.
Aggregated rate 0.9 0.8 0.7 0.6 Rate 0.5 S=1 0.4 0.3 0.2 0.1 C=1 C=2 C=4 C=8 S=2
S=4
1
2
3
4 5 # of Interfaces
6
7
8
Fig. 4. Aggregated transmission rate for different numbers of channels, interfaces and commodities.
number of channels or commodities increases. Our interpretation for this behavior is that, as the number of queues in the system increases, more time is required for all the queues to be served and thus reach a stable con?guration. This transient phase could be interpreted as a route discovery mechanism. Increasing the number of interfaces leads to a higher number of concurrent transmissions, which speeds up the convergence process. In some cases the time required for convergence is very long. This can limit the practical implementation of such an algorithm in an actual network. A reason for the slow convergence is related to the routing mechanism, which imposes no constraints on the feasible paths for the traf?c. The traf?c thus can travel in all directions until a stable con?guration is reached. It would be interesting to de?ne a policy for setting a reduced number of feasible paths for each commodity. Convergence delay also depends on the particular congestion controller. A detailed investigation is out of the scope of this paper and represents an open research issue as pointed out in [11].
Aggregated queues length Total queue length 150 100 50 0
which becomes smaller if a higher number of interfaces is used. The queue length decreases also as the number of channels increases. Note in particular that in all cases I = 4, C ∈ {4, 8} the maximum throughput is reached (see Figure 4). On the other hand a higher number of channels allows for a reduced queue length and thus a reduced delay.
Average queue lenght 1.6 C=1 C=2 C=4 C=6 C=8
0
2000
4000 6000 Time slots
8000
10000
Aggregated transmitted and received traffic 2 Data/slot 1.5 1 0.5 0 0 2000 4000 6000 Time slots 8000 10000 Received Transmitted
1.4
1.2 Queue length
1
0.8
0.6
Fig. 6. System time evolution. The curves shown are averaged over a moving window of 100 samples. C = 8, S = 4, I = 4.
0.4
0.2
1
2
3
4 5 # of interfaces
6
7
8
C. Random topology The algorithm has also been tested using random topologies where nodes are uniformly placed in a unit square area. The presented results are averaged over 10 random topologies. Only connected topologies are considered. As in the previous case, each node can potentially communicate with all neighbors within a distance of 0.3 and, when transmitting, it causes interference to neighbors within a distance of 0.3. The average number of nodes within the communication range is de?ned as D. As we are interested in the system behavior as a function of the number of interfaces, rather than in its absolute value, Figure 8 (Figure 9) shows the ratio between the experienced utility (rate) for a given set of parameters and the maximum utility (rate) achieved with the highest number of interfaces. Results are averaged over S ∈ {1, 2, 4} and 10 random topologies for each value of S. Two different node densities are considered, i.e., D = 3 and D = 7.
1289
Fig. 5. Average queue length for different numbers of channels and interfaces. S = 4.
The proposed algorithm has been proved to asymptotically converge to the solution of the joint resource allocation problem, but the proposed analysis gives no insight on the time required for the algorithm to converge. Figure 6 shows a typical trend for the time evolution of aggregated queue lengths, aggregated transmitted rate by the sources and aggregated received rate at the sinks. As can be seen, the convergence is reached after a relatively high number of iterations. A more exhaustive investigation of the convergence time is presented in Figure 7 where the time needed to reach a stationary condition is plotted for different number of interfaces, channels, and commodities. As can be seen, the convergence time decreases as the number of interfaces increases, and increases as the
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.
2.5
x 10
4
Convergence time 1 C=1 C=2 C=4 C=8 0.9 0.8 0.7
Fraction of maximum rate
2
Time slots
1.5 0.6 0.5 1 0.4 0.5 0.3 0.2 0 0.1 C=1 C=2 C=4 C=8 1 2 3 4 5 # of interfaces 6 7 8
1
2
3
4 5 # of interfaces
6
7
8
Fig. 7. Number of slots required for convergence, measured as the number of iterations needed to reach an aggregated queue length within 10% of its steady-state value. Dashed: S = 2; Dash-dotted: S = 4.
Negative fraction of maximum utility ?1
Fig. 9. Fraction of the maximum rate. Results are averaged over three different numbers of commodities S ∈ {1, 2, 4} and 10 random topologies. Dotted: D = 7, dashed: D = 3.
Fraction of single channel capacity 1 0.9 0.8 D=3 D=5 D=7
?1.2
?1.4 0.7 ?1.6 0.6 0.5 C=1 C=2 C=4 C=8 1 2 3 4 5 # of interfaces 6 7 8 0.4 0.3 0.2
?1.8
?2
?2.2
1
2
3 4 # of Channels / # of Interfaces
5
6
Fig. 8. Utility normalized with respect to the maximum utility attained with the maximum number of interfaces. The negative ratio is plotted in order to provide an easier comparison with Figure 9. Results are averaged over three different numbers of commodities S ∈ {1, 2, 4} and 10 random topologies. Dotted: D = 7, dashed: D = 3.
Fig. 10. Aggregated rate, normalized with respect to the single channel case, as a function of the ratio between the number of channels and the number of interfaces. Results are referred to C = 6, I ∈ {1, 2, 3, 4, 5, 6} and averaged over S ∈ {1, 2, 4} and 10 random topologies.
The behavior is similar to the one already described for the grid topology. It can be noted that a higher node density allows for a reduced number of interfaces needed to reach the same utility and rate values. Once again this is in accordance with the analysis in [2]. In Figure 10 the aggregated rate, normalized with respect to the single channel case, is plotted as a function of the ratio between the number of channels and the number of interfaces. The behavior is similar to the one described in [2]. D. Comparison with the results in [8] The scenario considered in [8] has been reproduced and a comparison between the performance of our algorithm and the one presented in [8] has been made. The algorithm in [8] formulates the resource allocation as a network ?ow problem and solves a linear program in order to de?ne an upper bound on the achievable performance. Then a greedy algorithm is
applied for the scheduling operations. All the sources have the same traf?c requirements (no congestion control) and the objective is to ?nd the maximum input rate for which a solution exists. Note that our algorithm aims at the utility maximization rather than at the maximization of the input rate. Nonetheless, assuming a logarithmic utility, fairness among different ?ows is enforced, thus pushing our input rate scenario toward the one de?ned in [8]. Note that the optimization in [8] uses a centralized LP solution, while our algorithm can be run in a fully distributed way, as long as a distributed scheduling mechanism is available. A grid 5×6 topology is considered; each node has at most 4 neighbors. Four sinks for the traf?c are considered (S = 4) and results are averaged using {5, 10, 15, 20, 25} traf?c sources. Each sink is placed on a different quadrant, and sources are connected to the closest sink. Results are shown in terms of the aggregate rate, normalized with respect to the single channel
1290
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2008 proceedings.
case. In this formulation each channel has a ?xed capacity, so that the total bandwidth is increasing with the number of channels. As [8] does not provide all the details of the considered scenario, in trying to reproduce it in our framework we had to make some assumptions on the positions of the source and sink nodes. Although this makes a detailed quantitative comparison dif?cult, it still allows to verify that the two approaches exhibit consistent behaviors. Figure 13 shows the rate gain in the two cases as a function of the number of channels and interfaces. It is clear from these results that the two approaches, though based on different techniques, have a qualitatively similar behavior. On the other hand, while the scheme in [8] is completely centralized and is more useful as a benchmark than as a practical solution, the features of our scheme can give some insight for practical implementation.
Rate gain w.r.t. the (I=1,C=1) case 4 3.5 3 2.5 2 1.5 1 0.5 I=1 I=2 I=3 I=4
The network performance has been evaluated as a function of the number of channels, interfaces and traf?c ?ows. The results are consistent with previous theoretical ?ndings, and con?rm the goodness of the approach. On the other hand, the speci?c features of our algorithm make it more suitable for practical implementation in a distributed setting. R EFERENCES
[1] P Kyasanur, J. So, C. Chereddi, and N. H. Vaidya. Multi-channel mesh networks: challenges and protocols. IEEE Wireless Communications, 13(2), 2006. Invited paper. [2] N.H. Vaidya and P. Kyasanur. Multi-channel wireless networks: capacity and protocols. Technical report, UIUC, 2005. [3] N. Jain and S. Das. A multichannel CSMA MAC protocol with receiver based channel selction for multihop wireless networks. In IC3N, 2000. [4] P. Kyasanur and N. Vaidya. Routing and link layer protocols for multichannel multi-interface ad-hoc wireless networks. Technical report, UIUC, 2005. [5] R. Draves, J. Padhye, and B. Zill. Routing in multi-radio, multi-hop wireless mesh networks. In ACM MobiCom, 2004. [6] A. Raniwala and T-C Chiueh. Architecture and algorithms for an IEEE 802.11 based multi-channel wireless mesh networks. In IEEE INFOCOM, 2005. [7] M. Alicherry, R. Bathia, and L. Li. Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In ACM MobiCom, 2005. [8] M. Kodialam and T. Nandagopal. Characterizing the capacity region in multi-radio multi-channel wireless networks. In ACM MobiCom, 2005. [9] S. Rasool and X. Lin. A distributed joint channel-assignment, scheduling and routing algorithm for multi-channel ad hoc wireless networks. In INFOCOM, 2007. [10] L. Tassiulas, L. Georgiadis, and M. J. Neely. Resource Allocation and Cross-Layer Control in Wireless Networks. Now Publishers Inc., 2006. [11] M. Chiang, S.H. Low, A.R. Calderbank, and J.C. Doyle. Layering as optimization decomposition: a mathematical theory of network architectures. Proceedings of the IEEE, 95(1):255–312, 2007. [12] A. Eryilmaz, A. Ozdaglar, and E. Modiano. Polynomial complexity algorithms for full utilization of multi-hop wireless networks. IEEE INFOCOM, 2007. [13] A.L. Stolyar. A tutorial on cross-layer optimization in wireless networks. IEEE JSAC, 24(8), 2006. [14] A. Eryilmaz and R. Srikant. Joint congestion control, routing, and MAC for stability and fairness in wireless networks. IEEE JSAC, 24(8):1514– 1524, 2006. [15] X. Lin and N.B. Shroff. Joint rate control and scheduling in multihop wireless networks. In IEEE CDC, 2004. [16] L. Chen, S. Low, M. Chiang, and J. Doyle. Cross layer congestion control, routing and scheduling design in ad-hoc wireless networks. In IEEE INFOCOM, 2006. [17] M. Neely, E. Modiano, and C. Rohrs. Dynamic power allocation and routing for time-varying wireless networks. IEEE JSAC, 23(1), 2005. [18] M. Chiang. Balancing transport and physical layer in wireless multihop networks: jointly optimal congestion control and power control. IEEE JSAC, 23(1), Jan 2005. [19] R. Srikant. The mathematics of internet congestion control. Birkhauser, 2003. [20] P. D. Palomar and M. Chiang. A tutorial on decomposition methods for network utility maximization. IEEE JSAC, 24(8), 2006. [21] X. Lin and B. Shroff. The impact of imperfect scheduling on cross-layer rate control in wireless networks. In IEEE INFOCOM, 2005. [22] G. Sharma and N. Shroff. Maximum weighted matching with interference constraints. In IEEE PerCom, 2006. [23] E. Modiano, G. Zussman, and A. Brzezinski. Enabling distributed throughput maximization in wireless mesh networks via local pooling. Technical report, MIT, 2006. [24] X. Wu, R. Srikant, and J. R. Perkins. Queue length stability of maximal greedy schedules in wireless networks. In ITA Workshop, 2006. [25] P. Chaporkar, K. Kar, and S. Sarkar. Achieving Queue Length Stability Through Maximal Scheduling in Wireless Networks. In ITA Workshop, 2006. [26] R. Srikant and X. Wu. Regulated maximal matching: a distributed scheduling algorithm for multi-hop wireless networks with node exclusive spectrum sharing. In IEEE CDC, 2005.
1
2
3
4 # of channels
5
6
7
Fig. 11. Rate gain factor with respect to the single channel case. Dotted: our algorithm. Line: copied from Figures 7 and 8 in [8]
IX. CONCLUSIONS A joint congestion control, channel allocation and scheduling algorithm for multi-channel multi-interface multi-hop wireless networks has been presented. The problem of maximizing a utility function of the source rate has been de?ned as an optimization problem and then solved by a dynamic algorithm. The algorithm decomposes the whole optimization in different functional sub-optimizations and uses the queue lengths as a way to allow a joint solution of different optimization tasks. A queue at the input of each node for each commodity and a queue at the output of each node for each channel-commodity pair have been used; a mechanism for loading the output queues on different channels has been de?ned introducing the notion of virtual links. The algorithm has been presented for a general communication and interference scenario. In order to test the behavior of the full algorithm, an instance of the problem, based on a simpli?ed communication and interference model, has been simulated using a greedy centralized scheduler.
1291