Queue-proportional rate allocation with per-link information in multihop wireless networks

The backpressure scheduling algorithm for multihop wireless networks is known to be throughput optimal, but it requires each node to maintain per-destination queues. Recently, a clever generalization of processor sharing has been proposed which is also throughput optimal, but which only uses per-link queues. Here, we propose another algorithm, called Queue-Proportional Rate Allocation (QPRA), which also only uses per-link queues and allocates service rates to links in proportion to their queue lengths, and employs the Serve-In-Random-Order queueing discipline within each link. Through fluid limit techniques and using a novel Lyapunov function, we show that the QPRA algorithm achieves the maximum throughput. We demonstrate an advantage of QPRA by showing that, for the so-called primary interference model, it is able to develop a low-complexity scheduling scheme which approximates QPRA and achieves a constant fraction of the maximum throughput region, independent of network size.

1. Since we use fluid limit techniques, this assumption can be relaxed in many different ways at the cost of additional notation. In particular, we only need a Markovian description of the queueing system for our results to hold.

2. A sequence of functions \(\{f_n(\cdot )\}_{n\ge 1}\) is said to converge to a function \(f(\cdot )\) uniformly over compact (u.o.c.) intervals if, for all \(t\ge 0\), \(\lim _{n\rightarrow \infty }\sup _{0\le t'\le t}|f_n(t')-f(t')|=0\).

3. Locally Lipschitz continuity guarantees the existences of \(\frac{\mathrm{D}^+}{\mathrm{d}x^+}f(x)\) and \(\frac{\mathrm{D}^+}{\mathrm{d}x^+}f_i(x)\), \(i=1,2,\ldots ,K\) (see, for example, [6]).

4. In IEEE 802.11b standard, the total number of mini-slots M ranges between 32 and 1024, where each mini-slot lasts \(20\,\upmu \hbox {s}\).

We would like to thank the anonymous reviewers for their very helpful suggestions, and pointing out a minor error in the proof of Proposition 3 in the initial version of the paper. This work is supported in part by NSF grant CNS-1161404, ONR Grant N00014-13-1-003, and DTRA grants HDTRA1-13-1-0030 and HDTRA1-15-1-0003.

Authors and Affiliations

1. Coordinated Science Lab, University of Illinois at Urbana-Champaign, Urbana, IL, USA

   Bin Li

2. Coordinated Science Lab, Department of ECE, University of Illinois at Urbana-Champaign, Urbana, IL, USA

   R. Srikant

Corresponding author

Correspondence to Bin Li.

Appendix 1: Proof of Proposition 1

For any integer \(t\ge 1\), let \(R_l^{{\varSigma }}(t)\triangleq \sum _{\tau =0}^{t-1}R_{l}(\tau )\) be the total amount of service available to link l from time slot 0 to \(t-1\). Let \(H_l^{{\varSigma }}(t)\triangleq \sum _{\tau =0}^{t-1}H_{l}(\tau )\) be the cumulative number of packets departing from link l up to time slot \(t-1\). Let \(D_{l,r}^{{\varSigma }}(t)\triangleq \sum _{\tau =0}^{t-1}D_{l,r}(\tau )\) denote the cumulative number of route r packets departing from link l up to time slot \(t-1\). Further, let \(R_l^{{\varSigma }}(0)=H_l^{{\varSigma }}(0)=D_{l,r}^{{\varSigma }}(0)=0\). Then, the evolution of the queue length can be rewritten as

for all pairs (l, r). Here, we note that \(D_{l^{(r)}_{-},r}^{{\varSigma }}(t)=0\) if \(l=l_1^{(r)}\).

For the purposes of our analysis, we interpolate the values of \(A_{l,r}^{{\varSigma }}(t)\), \(R_l^{{\varSigma }}(t)\), \(H_l^{{\varSigma }}(t)\), and \(D_{l,r}^{{\varSigma }}(t)\) to all real number \(t\ge 0\) by linear interpolation between \(\lfloor t\rfloor \) and \(\lfloor t\rfloor +1\), where \(\lfloor t\rfloor \) denotes the largest integer no greater than t. Then we have the following lemma.

Lemma 5

Under the QPRA algorithm, with probability 1, for any positive sequence \(w_n\rightarrow \infty \) there exists a subsequence \(w_{n_j}\) with \(w_{n_j}\rightarrow \infty \) such that the following convergence holds uniformly over compact intervals of time t:

where the limiting functions \(\sigma _{l}^{{\varSigma }}(t), \phi _l^{{\varSigma }}(t), \mu _{l,r}^{{\varSigma }}(t), x_{l,r}(t),q_l(t)\) are Lipschitz continuous in \([0,\infty )\), which implies that these limiting functions are differentiable for almost all t. Let \(\mathcal {T}\) be the set of time instants where these functions are differentiable. Then the following equations hold for all \(t\in \mathcal {T}\):

where \(\mu _{l_{-}^{(r)},r}(t)=0\) if \(l=l_1^{(r)}\). Here, \(\varvec{\sigma }(t)=(\sigma _l(t))_{l\in \mathcal {L}}\) is the longest vector within the capacity region \(\varvec{\Lambda }\) that is in the same direction as \(\mathbf {q}(t)\) and \(\varvec{\mu }(t)=(\mu _{l,r})_{l\in \mathcal {L},r\in \mathcal {R}}\) satisfies

for any route \(r\in l,r'\in l'\) with \(x_{l,r}(t)>0\) and \(x_{l',r'}(t)>0\).

Thus, Eqs. (9), (11), and (12) immediately follow from Lemma 5. By combining (68), (69), and (70), we have

Since \(\frac{\mu _{l,r}(t)}{x_{l,r}(t)}=\frac{\mu _{l,r'}(t)}{x_{l,r'}(t)}\) for all \(r,r'\in l\) with \(x_{l,r}(t)>0\) and \(x_{l,r'}(t)>0\),

for any route \(r\in l\) with \(x_{l,r}(t)>0\). Therefore, if \(q_l(t)>0\), we have

Noting Eq. (74) and the convention \(0/0=0\), we have Eq. (10).

Proof of Lemma 5

Equation (61) follows from the functional strong law of large numbers if \(l=l_1^{(r)}\). If \(l\ne l_1^{(r)}\), then \(A_{l,r}^{{\varSigma }}(w_{n_j}t)=\lambda _{l,r}=0\) and thus Eq. (61) always holds.

Note that for any \(0\le t_1\le t_2\) we have

where we use the fact that each link l can at most transfer one packet in one time slot. Thus, the sequence of functions \(\{\frac{1}{w_{n}}R_{l}^{{\varSigma }}(w_{n}t)\}\) is uniformly equicontinuous, and since \(R_{l}^{{\varSigma }}(0)=0\), the sequence is also uniformly bounded. Similarly, the sequence \(\{\frac{1}{w_{n}}D_{l,r}^{{\varSigma }}(w_{n}t)\}\) is uniformly bounded and uniformly equicontinuous. Consequently, according to the Arzela–Ascoli Theorem, there must exist a subsequence of \(\{w_n\}_{n\ge 1}\) for which both (62) and (64) hold. Since

we have (63), (65) and (66) by taking limits as \(w_{n_j}\rightarrow \infty \).

Since the functions \(R_l^{{\varSigma }}(t)\), \(H_l^{{\varSigma }}(t)\), \(D_{l,r}^{{\varSigma }}(t)\), \(X_{l,r}(t)\), \(Q_l(t)\) are Lipschitz continuous, the Lipschitz continuity of \(\sigma _{l}^{{\varSigma }}(t)\), \(\phi _l^{{\varSigma }}(t)\), \(\mu _{l,r}^{{\varSigma }}(t)\), \(x_{l,~r}(t)\), \(q_l(t)\) also follows. Hence, these limiting functions are differentiable for almost all t. In the rest of proof we consider all \(t\in \mathcal {T}\), where \(\mathcal {T}\) is the set of time instants where the limiting functions are differentiable.

Next, we prove Eq. (67). \(\sigma _l(\mathbf {q}(t))\) is continuous with respect to \(\mathbf {q}\) when \(q_l>0\). Therefore, for any \(\epsilon >0\), there exists a \(u>0\) such that for all \(t'\in [t,t+u]\) we have

Since \(\frac{1}{w_{n_j}}\mathbf {Q}(\lfloor w_{n_j}t'\rfloor )\rightarrow \mathbf {q}(t')\) uniformly over compact intervals of time, and \(\sigma _l(a\mathbf {Q})=\sigma _l(\mathbf {Q})\) for any \(a>0\), we have \(\sigma _l(\mathbf {Q}(\lfloor w_{n_j}t'\rfloor ))\rightarrow \sigma _l(\mathbf {q}(t'))\) with probability 1. Thus, there exists an integer \(J>0\) such that for all \(j>J\) and \(t'\in [t,t+u]\),

Combining with (80), we have

By the definition of the limit in (62), for any \(t'\in [t,t+u]\) we have

Define the filtration \(\mathcal {F}_k, k=1,2,\ldots \), where \(\mathcal {F}_k\) is the \(\sigma -\)algebra generated by the random variables \(A_{l,r}^{{\varSigma }}(\lfloor w_{n_j}t\rfloor +k')\), \(R_{l}^{{\varSigma }}(\lfloor w_{n_j}t\rfloor +k')\), \(D_{l,r}^{{\varSigma }}(\lfloor w_{n_j}t\rfloor +k')\), \(X_{l,r}(\lfloor w_{n_j}t\rfloor +k')\) for all pairs (l, r) and for \(k'=0,1,2,\ldots , k-1\). Let

Therefore, \(\sum _{m=0}^{k-1}Y_m, k=1,2,\ldots \), is a martingale with respect to the filtration \(\mathcal {F}_k, k=1,2,\ldots \). Further, \(\mathbb {E}\left[ Y_k^2\right] \) is always bounded for all k. Hence, using a strong law of large numbers for martingales [5], we have

which implies that

(85)

By using (82), we have

for \(t'\in [t,t+u]\). Since we assume that \(\sigma _l^{{\varSigma }}(t)\) is differentiable at t (i.e., \(t\in \mathcal {T}\)), we have

Finally, since this is true for any \(\epsilon >0\), Eq. (67) follows. The proof of Eq. (68) follows a similar technique and is omitted here for brevity.

Next, we consider Eq. (69). If \(q_l(t)>0\), then there exists a positive u such that for all \(t'\in [t,t+u]\), \(q_l(t')>0\). This implies that for all sufficiently large j, the backlog \(Q_l(\lfloor w_{n_j}t'\rfloor )\) at link l is larger than 1 for all \(t'\in [t,t+u]\). Therefore, the available service to link l will be fully utilized between \(\lfloor w_{n_j}t\rfloor \) and \(\lfloor w_{n_j}(t+u)\rfloor \). We thus have

for all \(t\le t'\le t+u\). Dividing both sides by \(w_{n_j}\) and taking limits as \(w_{n_j}\rightarrow \infty \), we have

for all \(t\le t'\le t+u\), which implies \(\frac{\mathrm{d}}{\mathrm{d}t}\phi _l^{{\varSigma }}(t)=\frac{\mathrm{d}}{\mathrm{d}t}\sigma _l^{{\varSigma }}(t)\). By combining with (67), we have Eq. (69).

Equations (70) and (71) follow from the equation \(H_l^{{\varSigma }}(t)=\sum _{r:l\in r}D_{l,r}^{{\varSigma }}(t)\) and \(Q_{l}(t)=\sum _{r:l\in r}X_{l,r}(t)\) by taking limits as \(w_{n_j}\rightarrow \infty \), respectively.

Finally, by using the queue-evolution Eq. (60) and taking limits as \(w_{n_j}\rightarrow \infty \), we have

By utilizing Eq. (68), we have Eq. (72). \(\square \)

Appendix 2: Proof of Lemma 1

We prove it by contradiction. Assume

Then, for a sufficiently small \(\epsilon >0\), there exists a decreasing sequence \(\{u_k,k=1,2,\ldots \}\) with \(\lim _{k\rightarrow \infty }u_k=0\) such that

Note that \(f(x)=f_i(x),\forall i\in \mathcal {K}\). Since there are a finite number of locally Lipschitz continuous functions \(f_i(x), i=1,2,\ldots ,K\), there must exist a \(j\in \mathcal {K}\) and a decreasing subsequence \(\{u_{t_k},k=1,2,\ldots \}\) of \(\{u_{k},k=1,2,\ldots \}\) such that \(f_j(x+u_{t_k})=f(x+u_{t_k})=\max _{i=1,2,\ldots ,K}f_i(x+u_{t_k}), \forall k=1,2,\ldots \), which implies that

Therefore, we obtain the contradiction

Hence, we have the desired result.

Appendix 3: Proof of Lemma 2

(i) Assume that there exists a \(t_1>0\) and a \(\zeta >0\) such that \(g(t_1)=\zeta \). Since \(g(0)=0\), according to the continuity property of the function \(g(\cdot )\) there exists a \(t_2\in (0,t_1)\) such that \(g(t_2)=\zeta /2\) and \(g(t)\ge \zeta /2>0\) for any \(t\in (t_2,t_1]\). Since \(g(t)>0\) for any \(t\in [t_2,t_1]\) and \(\frac{\mathrm{D}^+}{\mathrm{d}t^+}g(t)\le 0\) whenever \(g(t)>0\), we have \(g(t_1)\le g(t_2)\), which contradicts that \(g(t_1)=\zeta >g(t_2)=\zeta /2\). Therefore, \(g(t)=0\) for all \(t\ge 0\).

(ii) Since \(\frac{\mathrm{D}^+}{\mathrm{d}t^+}g(t)\le -\gamma \) whenever \(g(t)>0\), the function \(g(\cdot )\) will first hit zero at time \(T=g(0)/\gamma \). Then, by using the technique in (i), we can show that \(g(t)=0\) for all \(t\ge T\).

Reprints and permissions