Routing and Scheduling in Multihop Wireless Networks with Time-Varying Channels Matthew Andrews Abstract We study routing and scheduling in multihop wireless networks. When data is transmitted from its source node to its destination node it may go through other wireless nodes as intermediate hops. The data transmission is node constrained, i.e. every node can transmit data to at most one neighboring node per time step. The transmission rates are time varying as a result of the changing wireless channel conditions. In this paper we assume that the data arrivals and transmission rates are governed by an adversary. The power of the adversary is limited by an admissibility condition which forbids the adversary from overloading any wireless node a priori. The node constrained transmission and the time-varying nature of the transmission rates make our model different from and harder than the standard adversarial queueing model which relates to wireline networks. For the case in which the adversary specifies the paths that the data must follow, we design scheduling algorithms that ensure network stability. These algorithms try to give priority to data that is closest to its source node. However, at each time step only a subset of the data queued at a node is eligible for scheduling. One of our algorithms is fully distributed. For the case in which the adversary does not dictate the data paths, we show how to route the data so that the admissibility condition is satisfied. We can then schedule data along the chosen paths using our stable scheduling algorithms. We conclude by discussing the performance of distributed load balancing algorithms for combined routing and scheduling. 1 Intro duction Lisa Zhang hop paths through other wireless nodes in the network. Wireless multihop networks are expected to become increasingly popular since they allow for wireless communication in extremely dynamic environments without the need for any wireline connections between antennas. In contrast to wireline networks, the transmission rate between two wireless nodes is determined by the ever-changing channel condition between them. For example, as two nodes move away from each other or the interference increases, the channel condition suffers; as two nodes move towards each other or the interference decreases, the channel condition improves. In addition, issues such as Rayleigh fading introduce other fluctuations in the channel conditions. Therefore, the transmission rates between wireless nodes are time varying. Most previous work on wireless scheduling assumes that the channel conditions can be modeled as a stationary stochastic process such as an ergodic Markov chain. However, mobility can destroy any type of stationarity. In this paper we assume that the channel conditions and data arrivals are arbitrary and are governed by an adversary. The focus of our paper is on designing routing and scheduling algorithms for the purpose of stability, i.e. we wish to keep the amount of data in the network bounded whenever this is feasible. Routing selects paths for data to traverse from source to destination. Given routes, scheduling determines the order of data transmission in case of contention. 1.1 The Mo del. We consider a wireless multihop network of n nodes where each node acts as both a transmitter and a receiver. Time is divided into fixed slots. We use rij (t) to denote the amount of data that node i can transmit to node j at time t, and we refer to rij (t) as the transmission rate. Without loss of generality we assume the transmission rate is defined over all node pairs since we can set rij (t) to zero if nodes i and j are too far away from each other to communicate. We assume that an adversary controls the transmission rates, i.e. we make no statistical assumptions. We define two distinct models for transmission, the We study routing and scheduling data in a multihop wireless network, e.g. a mobile ad hoc network (MANET). In such a network, a wireless node (i.e. mobile) communicates directly with other nodes within its wireless communication range. Nodes that are beyond direct reach communicate with one another using multiLaboratories, 600-700 Mountain Avenue, Murray Hill, NJ 07974. {andrews,ylz}@research.bell-labs.com. Bell Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 1031 link constraint model and the node constraint model. In the link constraint model, node i can transmit rij (t) data to al l of its neighbors j in time step t. In the node constraint model node i can transmit to one neighbor only at time step t. That is, if node i decides to transmit to node j it can transmit rij (t) data to node j but it must transmit zero data to all its other neighbors. This model matches Qualcomm's High Data Rate (HDR) system [13] in which a transmitter is allowed to transmit to only one receiver at a time. We focus on the node constraint model since it more closely models a wireless system. For results on the link constraint model see [10]. We remark that the introduction of the node constraint appears to make scheduling significantly harder. In addition to transmission rates, the adversary also governs data arrivals, i.e. it specifies the data size, injection time, source and destination nodes for every piece of data. In Section 2 the adversary also specifies the routing path from source to destination that the data must follow. In Section 3 the adversary specifies no routing paths and we must solve a combined routing and scheduling problem. We assume that data is fluid-like. Fractions from several pieces of data may be transmitted along one link in one time step. In addition, in the routing problem one piece of data can be routed along multiple paths. However, we stress that in the node constraint model, each node can only transmit to one neighbor per time step. It cannot split service between multiple neighbors. The power of the adversary is limited to ensure that the network is not overloaded a priori. More specifically, we require that the adversary satisfies the following admissibility condition. Let Iij (t) represent the total amount of data that the adversary injects at time t and has link ij on its path. For the link constraint model we say that the data injections are (w, 1 - ) admissible for window size w and load 1 - 1 if, (1.1) +w-1 t = If the data paths are specified by the adversary our job is to design scheduling algorithms to resolve the node contention. If the adversary does not specify paths we only require that there exist paths such that constraints (1.2) hold. Our job is to find admissible routing paths in order to apply our scheduling algorithms. Our overall ob jective is to achieve stability, i.e. we wish to keep the amount of data in the network bounded whenever the injections are admissible. 1.2 Our Results. In this paper we study the node constraint model and present algorithms for three types of scenarios that differ in how much information is shared among nodes. Let ri (t) = (ri1 (t), ri2 (t), . . . , rin (t)) denote the rate vector at node i at time t. In all scenarios, each node i always knows the vector ri (t). This assumption agrees with the HDR system in which each receiver continually advertises to transmitters the rates at which it can receive data. We say that an algorithm is centralized if each node knows al l rate vectors in the network as well as the injections at each time step. We say that an algorithm is path distributed if we allow for some state information to be exchanged between the source node and all the nodes on the path of the data. We say that an algorithm is ful ly distributed if each node only knows about injected data when the data actually arrives at the node. 1. In Section 2 we study the problem in which the paths are fixed. We present a set of algorithms that we collectively call wireless-Nearest-to-Source (wNTS) that tend to give priority to data that is close to its source. We first present a centralized version and a path distributed version of wNTS that are stable under all admissible injections. We then prove stability for a fully distributed version of wNTS under a natural condition on the "correlation" between the burstiness of the data arrivals and the rate vectors. 2. In Section 3 we turn our attention to combined routing and scheduling. We give a simple path distributed routing algorithm in which each source node chooses routes for the injected data so that the admissibility condition is satisfied everywhere in the network. The algorithm works by routing along shortest paths with respect to a congestion function defined at each node. This congestion function is updated whenever data is routed through the node. Since the admissibility is satisfied for the chosen paths, we can use wNTS to schedule the data in order to achieve stability. 3. In Section 4 we examine whether or not there is a fully distributed algorithm for combined routing Iij (t) (1 - ) +w-1 t = rij (t), ij, . For the node constraint model we say that the injections are (w, 1 - ) admissible for window size w and load 1 - 1 if there exist fractions xij (t) such that, j xij (t) = 1, i, t +w-1 t = Iij (t) (1 - ) +w-1 t = xij (t)rij (t), ij, t (1.2) (We can view the xij (t) as representing fractional scheduling decisions made by the adversary.) 1032 and scheduling. A natural candidate is the load balancing algorithm of Aiello et al. [1] for routing and scheduling in wireline networks. We first show that the wireline analysis is no longer valid in the wireless context. We then present a different load balancing algorithm that is stable so long as we have a certain type of lower bound on the amount of data injected between a source node and a destination node. 1.3 Comparison to wireline mo del. We use the term wireline model to refer to the "standard" adversarial queueing model [9] for wireline networks in which the transmissions are link constrained and the transmission rates are one in each time step. The scheduling algorithm wNTS is based on the Nearest-to-Source (NTS) algorithm for the wireline model that always gives priority to the data that is closest to its source. We note however that in order to deal with the node constraint we need some new techniques. The wireline model also has other stable algorithms such as Longest-in-System (that always gives priority to the data that has been in the system longest) and Shortest-in-System (that always gives priority to the data that has been in the system shortest). In addition, [2] presents a more complex algorithm that has a polynomial bound on the amount of data queued in the system. However, all the algorithms just mentioned have the property that their stability analysis works by bounding the amount of time that data spends in the system. We remark that such an analysis cannot work in the wireless context since the adversary can "trap" data for an arbitrarily long period of time in the network by setting the appropriate transmission rates rij (t) to zero. The analysis for NTS can be adapted since it directly works on bounding the amount of data in the system. We note that we can also define a set of algorithms collectively called wFTG that give priority to the data that is furthest from its destination. The analysis for wNTS works directly for wFTG. 1.4 Previous work. The case of a single basestation transmitting to a set of mobiles over time-varying channels has been studied in a number of papers. If the channel conditions are governed by stationary stochastic processes then a number of algorithms are known to provide stability. (See [4, 3, 15, 17, 18]). One popular algorithm always transmits data to the user for which the queue size multiplied by the transmission rate is maximum. This algorithm is sometimes known as Max-Weight. For adversarial channels a stable algorithm that attempts to "track" the adversary's sched1 ule was presented in [5]. If all the queues are infinitely backlogged a number of papers (e.g.[14, 19, 22]) aim to maximize system throughput whilst maintaining some fairness between the users. For multihop wireless networks Borodin, Ostrovsky and Rabani [10] consider the link constraint model and show that NTS is stable. They also present an example for which Longest-in-System is unstable. (We remark that this instability example can be adapted to show that Longest-in-System is also unstable in the node constraint model). Awerbuch et al. [8] and Anshelevich et al. [7] present stable routing and scheduling algorithms for the special case in which the algorithm can choose the paths, all data is destined for the same destination, we are in the link constraint model and all rates are 0 or 1. In [20], Tassiulas and Ephremides consider a generalized version of the Max-Weight algorithm for multihop wireless networks with stationary stochastic channel conditions. However, this algorithm requires centralized control. A similar algorithm was presented in [16]. The problem of maintaining fairness between flows was studied by Tassiulas and Sarkar in [21]. Information theoretic results about the capacity of multihop wireless networks can be found in [11, 12]. 2 Scheduling for Stability In this section we focus on scheduling admissible data in the node constraint model when the paths are given. We show how to achieve stability using a set of protocols collectively known as wireless-Nearest-to-Source (wNTS) that aim to give priority to data that is close to its source. These protocols are an adaptation of the Nearest-to-Source (NTS) protocol that is known to be stable in the wireline model. Let R be the set of rates that the adversary can use. We assume that R is bounded from above and we let Rsup = sup{r : r R}. We also let Rinf = inf {r : r R and r = 0}. (Note that membership of 0 in R does not affect the value of Rinf .) For most of this section we work with a finite rate set. At the end of the section we discuss issues that arise when the rate set is infinite. The general strategy of wireless-Nearest-to-Source is as follows. Among the data queued at node i at time t, wNTS first declares some data to be eligible for service and some data to be ineligible for service. (The exact definition of eligibility will be given later.) Let Sij (t) be the eligible data that wishes to traverse link ij at time t. If |Sij (t)| is less than rij (t) then link ij transmits no data at time t. Otherwise, let sij Sij be the set of data of total size rij (t) that is closest to its source. Suppose every piece of data in sij is at most kj hops away from its source and let j = argminj kj . The wNTS protocol transmits rij amount of data from node i to node j 033 along link ij during step t. Node that node i only transmits to one neighbor and so the node constraint is satisfied. To assist our analysis we introduce the notion of the scaled size of a piece of data. If data of actual size d is injected at time t and link ij is along its data path, then its scaled size with respect to node i is sd /rij (t). We emphasize that the scaled size of a piece of data is dependent both on the node of interest and on the injection time of the data. Using the terminology of scaled size, the node admissibility condition of (1.2) effectively says that there exists an assignment of xij (t) such that the total scaled size of the data injected during a time step that wishes to pass through node i is on average at most 1 - . For any set S of data we use |S |s to denote the total scaled sized of the data in S . We begin by analyzing the simple situation in which the rates rij (t) do not change over time. We then analyze the more general case in which the transmission rates are time-varying. We present a centralized version of wNTS, a path distributed version and a fully distributed version. 2.1 Constant rates. Suppose that the transmission rates rij (t) stay constant (though not necessarily one) over time. In this case all data queueing at node i at time t is declared to be eligible for service at t. In the following analysis we omit the dependence on t and denote the rate as rij . Theorem 2.1. For constant transmission rates, wireless-Nearest-to-Source is stable under any (w, 1 - ) node admissible injections, where 0. Proof. Let Xk,i (t) be the set of data queued at node i at time t where node i is at most k th node that the data traverses. We write Xk,i (t) = Xk,ij (t) where Xk,ij (t) is the subset Xk,i (t) consisting of data queued for link ij . Consider the last time t before t that |Xk,ij (t )| is less than rij (t ) for all links ij emanating from node i. Note that for any data in Xk,i (t) that is not in Xk,i (t ), it has either not yet been transmitted by its (k - 1)st node at time t or else it was injected after time t . For any time step t between t and t, the total amount of scaled data transmitted by node i is one. Meanwhile the injection of data that wishes to pass through node i is restricted by the admissibility condition. If t - t is an integer multiple of w then the total scaled amount of data injectted along a path that traverses ij is at most (1 - ) t xij ( ). Here the scaling is with resp ect to node i. The total scaled amount of data injected along any path that passes through node i is at most (1 - )(t - t ). If t - t is not a multiple of w then the total scaled amount of data injected for node i is at most (1 - )(t - t + w). Inductively, let us assume we have an upper bound ak-1 on the actual amount of data that has yet to be transmitted by its (k - 1)st node. We have, |Xk,i (t)|s |Xk,i (t )|s + n+ ak-1 + w. Rinf ak-1 + (1 - )(t - t Rinf + w ) - (t - t ) Summing over all nodes i and undoing the scaling so as to bound the actual size of the data, we have ak i |Xk,i (t)|s · Rsup nak-1 · Rsup + nRsup (n + w). Rinf This implies ak is bounded and hence wNTS is stable. 2.2 Time-varying rates. For time-varying transmission rates we now present a centralized version of wNTS, a path distributed version and a fully distributed version. The essential idea in all three algorithms is that data is "filtered" according to the rate vectors. Roughly speaking, data is only eligible for service at node i when a particular rate vector appears. This allows us to treat the situation as if the transmission rates are constant over time. For the centralized version of wNTS, every node knows the network state, i.e. the rate vectors {ri }1in at all nodes. With this global knowledge, we partition the time steps according to the network state. Data is eligible for service if and only if the network is in the same state that it was in when the data was injected. Within each piece of the partition the rate vectors do not vary over time and we use the wNTS protocol for the constant transmission rates. Theorem 2.1 implies that the outstanding data with respect to each network state is bounded. Since the number of network states is bounded by nn |R|n , the total amount of outstanding data in the network is also bounded. Hence, Theorem 2.2. The above centralized wireless-Nearestto-Source protocol is stable under any (w, 1 - ) node admissible injections, where 0. For the path distributed version of wNTS, when data is injected by the adversary along a path, every node along the data path is informed about the injection. In this way, in any window of w time steps each node i is able to compute the values of xij (t), for which the node admissibility condition (1.2) holds. We use these values to introduce the notion of pseudo-injection times for the data injected during the window. For each time t in the window, node i allocates pseudo-injection time 1034 t to data of size (1 - )xij (t)rij (t) that wishes to pass through link ij . (By the admissibility condition all data is allocated a pseudo-injection time.) We emphasize that since the pseudo-injection times are defined by each node separately, one piece of data may have different pseudo-injection times at different nodes. From now on, each node schedules data as if it were injected at its pseudo-injection time. This does not affect stability since at each time t there is a bounded amount of data in the network whose pseudo-injection time after t. Lemma 2.1. We can assign pseudo-injection times to any (w, 1 - )-admissible injections so that the injections are (1, 1 - ) node admissible with respect to the pseudoinjection times. At each time step wNTS determines data eligibility as follows. If a piece of data has pseudo-injection time t0 then it is eligible for service at node i only at times t when ri (t) = ri (t0 ). The scaled size of data is also defined in terms of pseudo-injection times. Namely, data d queueing at node i has scaled size sd /rij (t) where t is the pseudo-injection time of d. The proof of the following theorem is included in the appendix. Theorem 2.3. The above path distributed version of the wireless-Nearest-to-Source protocol is stable under al l (w, 1 - ) node admissible injections, where 0. We now present a ful ly distributed version of wNTS. For this version to be stable we require an admissibility condition that is somewhat different from (1.2). In particular, we assume that the burstiness of the data injections is not "correlated" with the transmission rates. That is, we do not want bursts of data for node i to always be injected when the rate vector ri (t) has one particular value. More precisely, for any rate vector r let Tia (r) = {t1 , . . . tw } consist of the w time steps for which tk is the (a + k )th time that r appears as the rate vector at node i. We now say that the data injections are (w, 1 - ) admissible if there exist fractions xij (t) such that, j xij (t) = 1, i, t t Iij (t) (1 - )wrj a Ti (r) needs to carry its injection time and each node only needs to know its own rate vectors in the past. The stability proof is similar to that of Theorem 2.3. Theorem 2.4. The ful ly distributed wireless-Nearestto-Source protocol is stable for al l injections admissible under condition (2.3). 2.3 Maintaining finite state. As described above, wNTS has the drawback that it potentially needs to store an infinite amount of state. In order to decide which data is eligible node i needs to remember what its rate vector was at all times in the past. However, we can dispense with this requirement. Consider time step t at node i. Suppose that t is the last time before t that for all neighbors j of i, there was less than rij (t ) data queued for link ij at node i. We say that time t is the start of the current busy period at node i. It is not hard to see that all the above analyses still hold if node i only remembers its rate vector back to time t . If data that was injected before time t arrives at node i then we say that it is eligible regardless of what the current rate vector is. If > 0 then in all versions of wNTS, busy periods have finite length. This is because at each time step during a busy period, node i serves data of scaled size 1 and data of scaled size at most 1 - is injected that wishes to pass through node i. Hence in finite time we must reach a time step t such that there is less than rij (t) data queued for all links ij . Hence each node needs to remember a finite amount of state. 2.4 Dealing with infinite rate sets. We have assumed throughout this section that the rate set is finite. If the rate set is infinite, > 0 and Rinf > 0 then we can discretize the rate set by simply rounding each rate down to the nearest factor of 1 - /2. It is not hard to show that our analyses still hold. (For more details on this discretization see [6].) In our analysis of the amount of data in the network the factor |R| is simply replaced by log1-/2 Rsup /Rinf . We note that if either = 0 or Rinf = 0 then we cannot hope for stability since examples were presented in [6] (for a single transmitter) for which no online algorithm is stable. 3 Combined Routing and Scheduling t xij (t) ij, r, Tia (r) a Ti (r) (2.3) (Note that if w = 1 then the conditions (1.2) and (2.3) are equivalent.) At each time step t data d is eligible for service at node i if ri (t) = ri (t0 ) where t0 is the actual injection time of d. To make the eligibility decision data only We now focus on the combined routing and scheduling problem that arises when the data paths are not given a priori. Whenever the adversary injects a piece of data it specifies its injection time, source node, destination node and the data size, but the adversary does not dictate the routing paths. However, the injections are restricted in that there must exist data paths such that 1035 the admissibility conditions (1.2) are satisfied. We would like to obtain a path-distributed routing protocol. We assume that control information is communicated instantaneously.1 Whenever a source node is trying to choose a path, we assume that it knows congestion information at every node along a candidate path. Whenever a path is chosen for a piece of data, we assume that the nodes along the path are informed of this choice. Hence, as long as we can find paths that meet the admissibility condition (1.2), we can achieve stability by using the wNTS protocol to schedule the data. We aim to derive a combined routing and scheduling protocol for the node constraint model since that is the more complex model. Our algorithm is based on a routing algorithm for wireline networks presented in [2] which is in turn based on a algorithm of Garg and K¨nemann for maximum concurrent flow. However, the o fact that we have to deal with varying transmission rates together with node constraints makes the wireless problem significantly more complicated. Routing Algorithm. Consider all data injected in a window of w time steps. At the end of this window we run the procedure defined in Figure 1 to find paths for the data. The path p for a piece of data d consists of a collection of pairs (ij, t) where ij is a link along p and t is the pseudo-injection time of d at node i. The pseudo-injection time is defined in Section 2 and is used to determine the eligibility of d when node i makes scheduling decisions. Let sd be the size of data d. We define a congestion function c(·) on each nodetime pair (i, t) where n = 1, . . . , n and t = 1, . . . , w. Initially, c(·) is set to . For each piece of data d we repeatedly find the shortest path with respect to ( c(i,t) c(i,t) ij,t)p rij (t) . Along rij (t) , i.e. the path p minimizes path p we route s amount of data along p where s is the minimum of the remaining data size sd and the ¯ minimum rij (t) along p. For every (ij, t) in the chosen p, we also update c(i, t) to c(i, t)(1 + rijs(t) · µ). We repeat until all the sd data is routed. (See Line 5 of Figure 1.) We carry out this process for a total of K iterations and therefore we route a total of K sd data for each d. We show that if the data routed along each path p found by our routing protocol is scaled down by a factor K , then the admissibility condition is satisfied with a full load factor of one2 if we use the following 1 However, it is easy to adapt our arguments to the case where control information is communicated in a fixed finite amount of time. 2 We note that by cho osing slightly different values of µ, and K we can obtain a load factor of 1 - for any 0 < < . definitions of µ, and K . Here, n is the number of nodes and = 1 - is the load factor of the data injected during the window. (3.4) (3.5) (3.6) µ K = 1 - 1/3 1/µ 1 - µ = wn 1 + - µ 1 - µ = ln 1 µ nw For notational simplicity let us assume from now on that each of the K iterations finds exactly one path for each piece of data d, i.e. Line 5 of Figure 1 is executed once for each d. We also denote the K paths as pd (1), . . . , pd (K ). Theorem 3.1. For al l data injected during one window, if we route 1/K fraction of each piece of the data along each of the K paths found by our routing protocol, then the injections along these paths are (1, 1) admissible so long as the scheduling algorithm views data as being injected at its pseudo-injection time (as opposed to its real injection time). Analysis. To prove Theorem 3.1 let us examine a linear program formulation for routing the data injected during a window of w steps. Let Pd be a set of paths that d can be routed on and let variable yd (p) be the fraction of d that is routed along p. As mentioned before, each path p Pd consists of a collection of (ij, t) where ij is a link along p and t is the pseudo-injection time of d. Since the injections during this window are (w, 1 - ) admissible, Lemma 2.1 implies that the following LP is feasible and has an optimal solution 1. Primal max s.t. d p Pd ( y d (p) sd · yd (p) · rij (t) · xij (t) ij,t)p j xij (t) = 1 yd (p) 0 xij (t) 0 Pd p d ij, t i, t d, p Pd ij, t. Dual min s.t. ( i ,t c(i, t) d, p Pd ij, t i, t ij, t d · bij (t) zd zd 1 c(i, t) · rij (t) · bij (t) c(i, t) 0 bij (t) 0 zd 0 s ij,t)p d d For any nonnegative congestion function c(·), we i define D = ,t c(i, t) to b e the total congestion. For 1036 Find routes. 1 Initialize c(i, t) = , for all node i, for t = 1, . . . , w 2 Repeat K iterations 3 for all data d injected during t = 1, . . . , w 4 Initialize sd = sd , the size of data d ¯ 5 while (sd > 0) ¯ 6 p shortest path with respect to c(i, t)/rij (t) 7 s min{sd , min(ij,t)p rij (t)} ¯ 8 s d sd - s ¯ ¯ 9 c(i, t) c(i, t)(1 + rijs(t) · µ), for all (ij, t) p Figure 1: Procedure to find routes for packets injected during one window. a piece of data ( d let qd be the path that minimizes the quantity ij,t)p c(i, t)/rij (t) over all paths p in d ( c(i,t) Pd . Let = sd ij,t)qd rij (t) . It is not hard to show via complementary slackness that the following optimization problem with null constraints is equivalent to the dual LP. Dual Alternative min -1 · D/. c scaled data routed through ij during the K iterations in our routing protocol. We have, dp sd hij (t) = (3.7) . rij (t) d (k ):(ij,t)pd (k ) The congestion c(·) defined at the end of the k th iteration by the protocol in Figure 1 defines a valid solution to the dual alternative. We first show in Lemma 3.1 that D remains smaller than one for our choice of µ, K and . The fact that D is small implies that the congestion c(i, t) is small. Since c(i, t) is increased for every path routed through it, we upper bound the amount of data routed through each node and each link thereby proving Theorem 3.1. The proof of Lemma 3.1 is included in the appendix. Lemma 3.1. D 1 at the end of K iterations. We now prove Theorem 3.1. Pro of of Theorem 3.1: The routing protocol in Figure 1 finds K paths, pd (1), . . . , pd (K ), for every piece of data d injected. (See Line 6 of Figure 1.) Each path not only specifies a set of links but also the pseudoinjection times associated with d on these links. We send a 1/K fraction of d along each path pd (k ). In the following we show that under these chosen routes and pseudo-injection times, the injections are (1, 1) admissible for every time step. Consider a node-time pair (i, t). If a path pd (k ) contains (ij, t), the value of c(i, t) is increased by a factor of 1 + risdt) · µ. (See Line 9 of Figure 1.) Hence, whenever j( the total scaled data routed through i accumulates to 1, the value of c(i, t) is increased by a factor of at least 1+µ. More precisely, let hij (t) represent the total amount of c(i, t) grows by a factor of at least (1 + µ) have, j hij (t) log1+µ 1/ (i, t). Initially, c(i, t) = . By Lemma 3.1, DK 1 and therefore c(i, t) 1 at the end of the protocol. Since j hij (t) , we By the definitions of µ, K and , the above quantity is at most K . For every (ij, t), letj us define xij (t) to be hij (t)/K . xij (t)d p1 from the analysis We have seen that sd /K , above. Also, xij (t)rij (t) = d (k ):(ij,t)pd (k ) which means xij (t)rij (t) equals the total data with pseudo-injection time t routed through link ij . Hence, the chosen paths are (1, 1) admissible. 4 Balancing Algorithms 4.1 Background. A number of papers (e.g. [1, 7, 8] have studied algorithms for combined routing and scheduling that are variants of a simple load balancing algorithm. It is natural to ask if these algorithms can be applied to our wireless model. For example, in [1] Aiello et al. consider an algorithm for undirected wireline networks in which for each possible packet destination b, each link ij maintains two queues for packets destined for node b, one at each end of the link. We denote these queues by b b Qbj and Qbi and we denote their size by qij and qj i . Let i j b b b b bij = argmaxb (qij - qj i ) and let bj i = argmaxb (qj i - qij ). i i i If qij j - qj ij > 0 then data is sent from Qijj to Qjij . If i j j j qj i i - qij i > 0 then data is sent from Qjji to Qij i . At i b b b b b b b b 1037 the end of this transfer step, for each node i and for each destination b, the queues Qbj corresponding to the i neighbors of i are rebalanced so that they all have approximately the same size. The analysis from [1] of this load balancing algorithm works as follows. The authors define a potential b b2 function L = ,i,j (qij ) and observe that the load balancing algorithm is trying to decrease L by as much as possible. In particular they show that in every window of w of steps the change in L can be bounded by b -f1 (maxb,i,j qij ) + f2 where f1 (·) is some positive unbounded function and f2 is some quantity that is independent of the queue sizes. Therefore if L is sufficiently large, then the size of the largest queue must be large enough so that the potential must decrease. Hence L cannot grow without bound and so we must have stability. A key component of the method used to bound the change in L is that if Qbj is a large queue in the network i then by examining the data served along any path from node i to node b, we must obtain a large decrease in potential. However, in the context of wireless networks this argument no longer holds. For a counter-example, suppose that we have a large amount of data queued at node i and no data queued anywhere else in the network. Suppose that in the next w time steps, we have rij (t) = 0 for all j and data is injected into other portions of the network. Note that no packets can leave node i during these time steps. Hence the potential due to the data queued at i does not change. Moreover, if some of the new data is still present at the end of the w time steps then we have a net increase in potential at these other nodes. Therefore, regardless of how much data is queued at node i at the beginning of the w steps, it is always possible that get a net increase in potential during the w time steps. Therefore the argument of [1] that holds in the wireline context cannot hold in the wireless context. We remark that [7, 8] present different analyses of the above algorithm that apply to the wireless link constraint model in which all data has the same destination. However, their techniques do not seem to apply to the node constraint model or the case of multiple destinations. 4.2 Lower-b ounded Traffic. We do not know any method to adapt the balancing algorithm so that it is stable in the general wireless model. However, if we impose a weak "boundedness" condition on the injected data then we can show that a different "path-based" balancing algorithm is stable. Suppose that in addition to the standard admissibility condition we assume that for any source-destination pair (a, b), either there is never any data injected from a to b or else in any window of w steps, the amount of data injected into the network is at least ab for some parameter ab > 0. Note that we are not making any extra assumptions on the rate vector. The adversary can specify arbitrary rate vectors as long as the basic admissibility condition is satisfied. Hence we can note that the analysis of the balancing algorithm presented in [1] still cannot be applied in this new wireless context since once again it is possible to isolate nodes where there is a large buildup of packets. The modification that we make in order to obtain stability is to have a separate queue at each node for each path through the network. For any path P that passes through node i, we denote this queue by QP and i P we let qi (t) be the size of the queue at time t. We use nP (i) to denote the next node after i on the path P . In addition, for each potential source-destination (a,b) pair (a, b) we have a special source queue Qa at the (a,b) source node a. We let Q be the size of this queue. When packets are injected that wish to travel from a to (a,b) b, they are first injected into the queue Qa . The algorithm works as follows. At each time t and at each node i, let P be the path that maxP P imizes rinP (i) (qi (t) - qnP (i) (t)). Node i transmits P P min{rinP (i) , qi (t) - qnP (i) (t)} data from queue QP to i queue QP(i) . Since each node is transmitting to at most n one neighbor, the node constraint is satisfied. (a,b) In addition, for each source queue Qa , we find P the path P from a to b for which qa (t) is smallest. If (a,b) (a,b) P P qa (t) is larger than qa (t) then qa (t) - qa (t) data is (a,b) P transferred from Qa to Qa . Since these two nodes are at the same point, this can be done without consuming any wireless resources. We can show that this algorithm is stable using a similar analysis to [1]. We omit the details for reasons of space. The key idea behind the path-based balancing algorithm is that the maximum queues in the network are the source queues. Moreover, our assumption on the packet injections ensures that in any window of w time steps, it is always possible a non-zero amount of data from any source queue to the corresponding destination. In this way we can ensure that the total potential in the network decreases whenever some queue becomes sufficiently large. 5 Conclusions In this paper we have presented algorithms for routing and scheduling in multihop wireless networks where the transmission rates are specified by an adversary. A number of open problems remain. For the scheduling problem in which the paths are specified by the adversary, it would be interesting to know if there is a stable 1038 fully distributed algorithm for the case in which admissibility condition (1.2) holds but admissibility condition (2.3) does not hold. We also note that our analysis gives bounds on the total amount of data in the network that are exponential in the size of the network. We believe that a challenging open problem is to derive a scheduling algorithm with a polynomial bound. For the routing and scheduling problem it would be interesting to know if there is a fully distributed algorithm that does not require the assumption on the input traffic defined in Section 4. We remark that there are other reasonable models in addition to our model in which the transmission rates are known on each link. We can think of our model as one in which all nodes transmit at full power. Therefore, the signal strength that a receiver receives together with the interference that it experiences are predetermined. However, there are other models in which the scheduling algorithm can choose the amount of power with which each node transmits. In this case the interference at the receivers are affected by the scheduling decisions and hence the transmission rates are affected by the scheduling decisions. It is fairly straightforward to transform our algorithms into centralized scheduling algorithms for this more general problem. It would be interesting to know what can be achieved with distributed algorithms in this setting. References [1] W. Aiello, E. Kushilevitz, R. Ostrovsky, and A. Rosen. Adaptive packet routing for bursty adversarial traffic. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 359 ­ 368, Dallas, TX, May 1998. [2] M. Andrews, A. Fernandez, A. Goel, and L. Zhang. ´ Source routing and scheduling in packet networks. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pages 168­177, Las Vegas, NV, October 2001. [3] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting. CDMA data QoS scheduling on the forward link with variable channel conditions. Bel l Labs Technical Memorandum, April 2000. [4] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting. Providing quality of service over a shared wireless link. IEEE Communications Magazine, February 2001. [5] M. Andrews and L. Zhang. Scheduling over a timevarying user-dependent channel with applications to high speed wireless data. In Proceedings of the 43nd Annual Symposium on Foundations of Computer Science, Vancouver, Canada, November 2002. [6] M. Andrews and L. Zhang. Scheduling over a timevarying user-dependent channel with applications to high speed wireless data. In Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, Vancouver, Canada, November 2002. [7] E. Anshelevich, D. Kempe, and J. Kleinberg. Stability of load balancing algorithms in dynamic adversarial systems. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, Canada, May 2002. [8] B. Awerbuch, P. Berenbrink, A. Brinkmann, and C. Scheideler. Simple routing strategies for adversarial systems. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pages 158 ­ 167, Las Vegas, NV, October 2001. [9] A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D. P. Williamson. Adversarial queueing theory. Journal of the ACM, 48(1):13­38, January 2001. [10] A. Borodin, R. Ostrovsky, and Y. Rabani. Stability preserving transformations: packet routing networks with edge capacities and speeds. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001. [11] M. Grossglauser and D. Tse. Mobility increases the capacity of ad-hoc wireless networks. In Proceedings of IEEE INFOCOM '01, pages 1360­1369, 2001. [12] P. Gupta and P. R. Kumar. The capcity of wireless networks. IEEE Transactions on Information Theory, 46(2):388 ­ 404, 2000. [13] A. Jalali, R. Padovani, and R. Panka j. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system. In Proceedings of the IEEE Semiannual Vehicular Technology Conference, VTC2000-Spring, Tokyo, Japan, May 2000. [14] H. Kushner and P. Whiting. Asymptotic properties of proportional-fair sharing algorithms. In 40th Annual Al lerton Conference on Communication, Control, and Computing, 2002. [15] M. Neely, E. Modiano, and C. Rohrs. Power and server allocation in a multi-beam satellite with time varying channels. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002. [16] M. Neely, E. Modiano, and C. Rohrs. Dynamic power allocation and routing for time varying wireless networks. In Proceedings of IEEE INFOCOM '03, San Francisco, CA, April 2003. [17] S. Shakkottai and A. Stolyar. Scheduling algorithms for a mixture of real-time and non-real-time data in HDR. In Proceedings of 17th International Teletraffic Congress (ITC-17), pages 793 ­ 804, Salvador da Bahia, Brazil, 2001. [18] S. Shakkottai and A. Stolyar. Scheduling for multiple flows sharing a time-varying channel: The exponential rule. Analytic Methods in Applied Probability, 2002. To appear. [19] A. Stolyar. Multiuser throughput dynamics under proportional fair and other gradient based scheduling 1039 algorithms. Submitted. [20] L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936 ­ 1948, December 1992. [21] L. Tassiulas and S. Sarkar. Maxmin fair scheduling in wireless networks. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002. [22] D. Tse. Forward-link multiuser diversity through rate adaptation and scheduling. In preparation. chosen for the data. We define Dk i Dk = ck (i, t) ,t in terms of ck (·). = = ( ck , -1 -1 (i, t) + ij,t)p / ( ck , ij,t)p -1 (i, t)(1 + sd · µ ) rij (t) Dk , + ( ck , -1 (i, t) · sd · ij,t)p µ rij (t) App endix Pro of of Theorem 2.3: Let Xk,i,r (t) be the set of data queued at node i at time t that satisfies the following two conditions. First, if the data has pseudoinjection time t0 then r(t0 ) = r(t). Second, node i is at most the k th node that the data traverses. As before, we define Xk,ij,r (t) as the subset of Xk,i,r (t) that is queueing at link ij . Let t be the last time before t that |Xk,ij,r (t )| is less than rij (t ) for all j . Once again it is clear that for all data in Xk,i,r (t) that is not in Xk,i,r (t ), either it has not yet been transmitted by its (k - 1)st node at time t or else its pseudo-injection time is after t . Injections with respect to the pseudo-injection times are (1, 1 - )-admissible by Lemma 2.1. Hence, between times t and t the total amount of scaled data that is injected along a path that passes through node i is at most (1 - )(t - t ). The total scaled amount of data transmitted by node i equals t - t . We have, |Xk,i,r (t)|s |Xk,i,r (t )|s + n+ ak-1 . Rinf ak-1 + (1 - )(t - t ) - (t - t ) Rinf By repeatedly applying the above recurrence and the observation that the congestion c(i, t) only increases, we have, (5.9) Dk Dk-1 + k · µ. Since the LP primal has an optimal solution 1 and ck (·) defines a feasible solution to the alternative dual, we have Dk /k by duality. Combining with (5.9) we have (5.8). By repeatedly applying (5.8) we have, DK nw nw = (1 - µ)K 1 - µ 1 µ + 1 - µ K -1 . Since 1 + x ex for x 0, we have, DK K nw µ(--1) e1 µ, 1 - µ which equals 1 by the definition of K in (3.6). Summing over all nodes i and all rate vectors r and undoing the scaling we obtain, ak i |Xk,i,r (t)|s · Rsup n|R|n ak-1 · ,r Rsup + n2 |R|n . Rinf Since ak is bounded, stability is implied. Pro of of Lemma 3.1: Let Dk be the value of D at the end of the k th iteration. By definition D0 is initialized to nw where n is the number of nodes. In the following we show that Dk is not much larger than Dk-1 . In particular, (5.8) Dk dk-1 /(1 - µ). Let ck (i, t) be the congestion function after routing th piece of data in the k th iteration and let p be the path 1040