[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

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

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  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}\).

References

  1. Bonald, T., Proutiere, A.: Insensitive bandwidth sharing in data networks. Queueing Syst. 44, 69–100 (2003)

    Article  Google Scholar 

  2. Borwein, J.M., Lewis, A.S.: Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer, Berlin (2000)

    Book  Google Scholar 

  3. Bramson, M.: Stability of queueing networks. Probab. Surv. 5, 169–345 (2008)

    Article  Google Scholar 

  4. Chiang, M.: Balancing transport and physical layers in wireless multihop networks: jointly optimal congestion control and power control. IEEE J. Sel. Areas Commun. Spec. Issue Nonlinear Optimiz. Commun. Syst. 23(1), 104–116 (2005)

    Article  Google Scholar 

  5. Chow, Y.S.: On a strong law of large numbers for martingales. Ann. Math. Stat. 38, 610 (1967)

    Article  Google Scholar 

  6. Clarke, F.: Optimization and Nonsmooth Analysis (Classics in Applied Mathematics). Society for Industrial Mathematics, Philadelphia (1987)

    Google Scholar 

  7. Dai, J.G.: On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Probab. 5, 49–77 (1995)

    Article  Google Scholar 

  8. Dai, J.G., Prabhakar, B.: The throughput of data switches with and without speedup. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Tel Aviv, Israel (2000)

  9. Eryilmaz, A., Srikant, R.: Joint congestion control, routing and MAC for stability and fairness in wireless networks. IEEE J. Sel. Areas Commun. Spec. Issue Nonlinear Optim. Commun. Syst. 14, 1514–1524 (2006)

    Article  Google Scholar 

  10. Eryilmaz, A., Srikant, R., Perkins, J.R.: Throughput-optimal scheduling for broadcast channels. In: Proceedings of ITCom (Modeling and Design of Wireless Networks), Denver, CO (2001)

  11. Hajek, B., Sasaki, G.: Link scheduling in polynomial time. IEEE/ACM Trans. Inf. Theory 34(5), 910–917 (1988)

    Article  Google Scholar 

  12. Hou, I.H., Borkar, V., Kumar, P.R.: A theory of QoS for wireless. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil (2009)

  13. Jaramillo, J.J., Srikant, R.: Optimal scheduling for fair resource allocation in ad hoc networks with elastic and inelastic traffic. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), San Diego, CA (2010)

  14. Ji, B., Joo, C., Shroff, N.B.: Throughput-optimal scheduling in multihop wireless networks without per-flow information. IEEE/ACM Trans. Netw. 21(2), 634–647 (2013)

    Article  Google Scholar 

  15. Joo, C., Shroff, N.B.: Performance of random access scheduling schemes in multi-hop wireless networks. IEEE/ACM Trans. Netw. 17(5), 1481–1493 (2009)

    Article  Google Scholar 

  16. Kar, K., Luo, X., Sarkar, S.: Throughput-optimal scheduling in multichannel access point networks under infrequent channel measurements. IEEE Trans. Wirel. Commun. 7, 2619–2629 (2008)

    Article  Google Scholar 

  17. Li, B., Li, R., Eryilmaz, A.: Throughput-optimal scheduling design with regular service guarantees in wireless networks. IEEE/ACM Trans. Netw. 23(5), 1542–1552 (2015)

    Article  Google Scholar 

  18. Li, B., Li, R., Eryilmaz, A.: On the optimal convergence speed of wireless scheduling for fair resource allocation. IEEE/ACM Trans. Netw. 23(2), 631–643 (2015)

    Article  Google Scholar 

  19. Li, B., Srikant, R.: Queue-proportional rate allocation with per-link information in multihop networks. In: Proceedings of ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), Portland, Oregon, USA (2015)

  20. Lin, X., Rasool, S.B.: Constant-time distributed scheduling policies for ad hoc wireless networks. IEEE Trans. Autom. Control 54(2), 231–242 (2009)

    Article  Google Scholar 

  21. Lin, X., Shroff, N.: The impact of imperfect scheduling on cross-layer rate control in multihop wireless networks. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Miami, FL (2005)

  22. Liu, S., Ekici, E., Ying, L.: Scheduling in multihop wireless networks without back-pressure. In: Proceedings of the Allerton Conference on Communications, Control and Computing, Monticello, IL (2010)

  23. Lu, S.H., Kumar, P.R.: Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Autom. Control 36(12), 1406–1416 (1991)

    Article  Google Scholar 

  24. Massoulie, L., Roberts, J.: Bandwidth sharing: objectives and algorithms. IEEE/ACM Trans. Netw. 10, 320–328 (2002)

    Article  Google Scholar 

  25. Mo, J., Walrand, J.: Fair end-to-end window-based congestion control. IEEE/ACM Trans. Network. 8(5), 556–567 (2000)

    Article  Google Scholar 

  26. Neely, M.J.: Energy optimal control for time varying wireless networks. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Miami, FL (2005)

  27. Neely, M.J., Modiano, E., Li, C.: Fairness and optimal stochastic control for heterogeneous networks. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Miami, FL (2005)

  28. Neely, M.J., Modiano, E., Rohrs, C.E.: Dynamic power allocation and routing for time varying wireless networks. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), San Francisco, CA (2003)

  29. Rybko, A., Stolyar, A.: Ergodicity of stochastic processes describing the operation of open queueing networks. Problemy Peredachi Informatsii 28(3), 3–26 (1992)

    Google Scholar 

  30. Shah, D., Shin, J.: Randomized scheduling algorithm for queueing networks. Ann. Appl. Probab. 22(1), 128–171 (2012)

    Article  Google Scholar 

  31. Shah, D., Walton, N., Zhong, Y.: Optimal queue-size scaling in switched networks. In: Proceedings of ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), London, United Kingdom (2012)

  32. Srikant, R., Ying, L.: Communication Networks: An Optimization, Control, and Stochastic Networks Perspective. Cambridge University Press, Cambridge (2014)

    Google Scholar 

  33. Stolyar, A.: Maximizing queueing network utility subject to stability: Greedy primal–dual algorithm. Queueing Syst. 50(4), 401–457 (2005)

    Article  Google Scholar 

  34. Tassiulas, L., Ephremides, A.: Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control 36, 1936–1948 (1992)

    Article  Google Scholar 

  35. Walton, N.: Concave switching in single and multihop networks. In: Proceedings of ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), Austin, Texas (2014)

  36. Wu, H., Lin, X., Liu, X., Zhang, Y.: Application-level scheduling with deadline constraints. In: Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Toronto, Canada (2014)

  37. Ying, L., Srikant, R., Eryilmaz, A., Dullerud, G.E.: Distributed fair resource allocation in cellular networks in the presence of heterogeneous delays. IEEE Trans. Autom. Control 52, 129–134 (2007)

    Article  Google Scholar 

Download references

Acknowledgments

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.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Bin Li.

Appendices

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

$$\begin{aligned} X_{l,r}(t)=X_{l,r}(0)+A_{l,r}^{{\varSigma }}(t)-D_{l_{-}^{(r)},r}^{{\varSigma }}(t)+D_{l,r}^{{\varSigma }}(t), \end{aligned}$$
(60)

for all pairs (lr). 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:

$$\begin{aligned}&\frac{1}{w_{n_j}}A_{l,r}^{{\varSigma }}(w_{n_j}t)\rightarrow \lambda _{l,r}t, \quad \forall (l,r), \end{aligned}$$
(61)
$$\begin{aligned}&\frac{1}{w_{n_j}}R_{l}^{{\varSigma }}(w_{n_j}t)\rightarrow \sigma _{l}^{{\varSigma }}(t), \quad \forall l\in \mathcal {L},\end{aligned}$$
(62)
$$\begin{aligned}&\frac{1}{w_{n_j}}H_{l}^{{\varSigma }}(w_{n_j}t)\rightarrow \phi _{l}^{{\varSigma }}(t), \quad \forall l\in \mathcal {L}, \end{aligned}$$
(63)
$$\begin{aligned}&\frac{1}{w_{n_j}}D_{l,r}^{{\varSigma }}(w_{n_j}t)\rightarrow \mu _{l,r}^{{\varSigma }}(t), \quad \forall (l,r),\end{aligned}$$
(64)
$$\begin{aligned}&\frac{1}{w_{n_j}}X_{l,r}(w_{n_j}t)\rightarrow x_{l,r}(t), \quad \forall (l,r),\end{aligned}$$
(65)
$$\begin{aligned}&\frac{1}{w_{n_j}}Q_{l}(w_{n_j}t)\rightarrow q_{l}(t), \quad \forall l\in \mathcal {L}, \end{aligned}$$
(66)

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}\):

$$\begin{aligned}&\frac{\mathrm{d}}{\mathrm{d}t}\sigma _{l}^{{\varSigma }}(t)=\sigma _l(t),\quad \forall l\in \mathcal {L}, \end{aligned}$$
(67)
$$\begin{aligned}&\frac{\mathrm{d}}{\mathrm{d}t}\mu _{l,r}^{{\varSigma }}(t)=\mu _{l,r}(t),\quad \forall (l,r), \end{aligned}$$
(68)
$$\begin{aligned}&\frac{\mathrm{d}}{\mathrm{d}t}\phi _{l}^{{\varSigma }}(t)=\sigma _l(t),\quad \forall l\in \mathcal {L},\quad \text { whenever } q_l(t)>0, \end{aligned}$$
(69)
$$\begin{aligned}&\phi _{l}^{{\varSigma }}(t)=\sum _{r:l\in r}\mu _{l,r}^{{\varSigma }}(t), \quad \forall (l,r), \end{aligned}$$
(70)
$$\begin{aligned}&q_{l}(t)=\sum _{r:l\in r}x_{l,r}(t), \quad \forall (l,r), \end{aligned}$$
(71)
$$\begin{aligned}&\frac{\mathrm{d}}{\mathrm{d}t}x_{l,r}(t)=\lambda _{l,r}+\mu _{l_{-}^{(r)},r}(t)-\mu _{l,r}(t),\quad \forall (l,r), \end{aligned}$$
(72)

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

$$\begin{aligned}&\mu _{l_{-}^{(r)},r}(t)=0,\quad \text {whenever } l=l_1^{(r)},\end{aligned}$$
(73)
$$\begin{aligned}&\mu _{l,r}(t)=0, \quad \text {whenever } x_{l,r}(t)=0,\end{aligned}$$
(74)
$$\begin{aligned}&\frac{\mu _{l,r}(t)}{x_{l,r}(t)}=\frac{\mu _{l',r}(t)}{x_{l',r}(t)}, \end{aligned}$$
(75)

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

$$\begin{aligned} \sigma _l(t)=\sum _{r:l\in r}\mu _{l,r}(t),\quad \text {if } q_l(t)>0, \end{aligned}$$
(76)

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\),

$$\begin{aligned} \frac{\mu _{l,r}(t)}{x_{l,r}(t)}=\frac{\sigma _l(t)}{q_l(t)}, \end{aligned}$$
(77)

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

$$\begin{aligned} \mu _{l,r}(t)=\frac{x_{l,r}(t)}{q_l(t)}\sigma _l(t), \quad \text {whenever } x_{l,r}(t)>0. \end{aligned}$$
(78)

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

$$\begin{aligned} 0\le \frac{1}{w_{n}}R_{l}^{{\varSigma }}(w_{n}t_2)-\frac{1}{w_{n}}R_{l}^{{\varSigma }}(w_{n}t_1)\le t_2-t_1, \end{aligned}$$
(79)

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

$$\begin{aligned}&\frac{1}{w_{n}}H_{l}^{{\varSigma }}(w_{n}t)=\sum _{r:l\in r}\frac{1}{w_{n}}D_{l,r}^{{\varSigma }}(w_{n}t), \nonumber \\&\frac{1}{w_{n}}X_{l,r}(w_{n}t)=\frac{1}{w_{n}}A_{l,r}^{{\varSigma }}(w_{n}t)-\frac{1}{w_{n}}D_{l_{-}^{(r)},r}^{{\varSigma }}(w_{n}t)+\frac{1}{w_{n}}D_{l,r}^{{\varSigma }}(w_{n}t),\nonumber \\&\frac{1}{w_{n}}Q_{l}^{{\varSigma }}(w_{n}t)=\sum _{r:l\in r}\frac{1}{w_{n}}X_{l,r}^{{\varSigma }}(w_{n}t), \end{aligned}$$

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

$$\begin{aligned} \left| \sigma _l(\mathbf {q}(t'))-\sigma _l(\mathbf {q}(t))\right| \le \epsilon . \end{aligned}$$
(80)

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]\),

$$\begin{aligned} \sigma _l(\mathbf {q}(t'))-\epsilon \le \sigma _l(\mathbf {Q}(\lfloor w_{n_j}t'\rfloor ))\le \sigma _l(\mathbf {q}(t'))+\epsilon . \end{aligned}$$
(81)

Combining with (80), we have

$$\begin{aligned} \sigma _l(\mathbf {q}(t))-2\epsilon \le \sigma _l(\mathbf {Q}(\lfloor w_{n_j}t'\rfloor ))\le \sigma _l(\mathbf {q}(t))+2\epsilon . \end{aligned}$$
(82)

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

$$\begin{aligned} \sigma _l^{{\varSigma }}(t')-\sigma _l^{{\varSigma }}(t)=\lim _{j\rightarrow \infty }\frac{1}{w_{n_j}}\sum _{k=\lfloor w_{n_j}t\rfloor }^{\lfloor w_{n_j}t'\rfloor -1}R_l(k). \end{aligned}$$
(83)

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 (lr) 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

$$\begin{aligned} \lim _{k\rightarrow \infty }\frac{1}{k}\sum _{m=0}^{k-1}Y_m=0, \quad \text {with probability } 1, \end{aligned}$$
(84)

which implies that

(85)

By using (82), we have

$$\begin{aligned} (t'-t)(\sigma _l(\mathbf {q}(t))-2\epsilon )\le \sigma _l^{{\varSigma }}(t')-\sigma _l^{{\varSigma }}(t)\le (t'-t)(\sigma _l(\mathbf {q}(t))+2\epsilon ), \end{aligned}$$

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

$$\begin{aligned} \sigma _l(\mathbf {q}(t))-2\epsilon \le \frac{\mathrm{d}}{\mathrm{d}t}\sigma _l^{{\varSigma }}(t)\le \sigma _l(\mathbf {q}(t))+2\epsilon . \end{aligned}$$
(86)

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

$$\begin{aligned} R_l^{{\varSigma }}(\lfloor w_{n_j}t'\rfloor )-R_l^{{\varSigma }}(\lfloor w_{n_j}t\rfloor )=H_l^{{\varSigma }}(\lfloor w_{n_j}t'\rfloor )-H_l^{{\varSigma }}(\lfloor w_{n_j}t\rfloor ), \end{aligned}$$

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

$$\begin{aligned} \sigma _{l}^{{\varSigma }}(t')-\sigma _{l}^{{\varSigma }}(t)=\phi _{l}^{{\varSigma }}(t')-\phi _{l}^{{\varSigma }}(t), \end{aligned}$$
(87)

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

$$\begin{aligned} \frac{\mathrm{d}}{\mathrm{d}t}x_{l,r}(t)=\lambda _{l,r}+\frac{\mathrm{d}}{\mathrm{d}t}\mu _{l_{-}^{(r)},r}^{{\varSigma }}(t)-\frac{\mathrm{d}}{\mathrm{d}t}\mu _{l,r}^{{\varSigma }}(t). \end{aligned}$$
(88)

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

Appendix 2: Proof of Lemma 1

We prove it by contradiction. Assume

$$\begin{aligned} \frac{\mathrm{D}^+}{\mathrm{d}x^+}f(x)>\max _{i\in \mathcal {K}}\left\{ \frac{\mathrm{D}^+}{\mathrm{d}x^+}f_i(x)\right\} . \end{aligned}$$
(89)

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

$$\begin{aligned} \frac{f(x+u_k)-f(x)}{u_k} \ge \max _{i\in \mathcal {K}}\left\{ \frac{\mathrm{D}^+}{\mathrm{d}x^+}f_i(x)\right\} +\epsilon , \quad \forall k=1,2,\ldots . \end{aligned}$$

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

$$\begin{aligned} \frac{f_j(x+u_{t_k})-f_j(x)}{u_{t_k}} \ge \max _{i\in \mathcal {K}}\left\{ \frac{\mathrm{D}^+}{\mathrm{d}x^+}f_i(x)\right\} +\epsilon , \quad \forall k=1,2,\ldots . \end{aligned}$$

Therefore, we obtain the contradiction

$$\begin{aligned} \frac{\mathrm{D}^+}{\mathrm{d}x^+}f_j(x)\ge \max _{i\in \mathcal {K}}\left\{ \frac{\mathrm{D}^+}{\mathrm{d}x^+}f_i(x)\right\} +\epsilon . \end{aligned}$$
(90)

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\).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, B., Srikant, R. Queue-proportional rate allocation with per-link information in multihop wireless networks. Queueing Syst 83, 329–359 (2016). https://doi.org/10.1007/s11134-016-9490-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11134-016-9490-1

Keywords

Mathematics Subject Classification

Navigation