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

Dynamic Control Policy for Delay Guarantees in Multi-hop Wireless Networks

  • Published:
Wireless Personal Communications Aims and scope Submit manuscript

Abstract

This paper considers the dynamic control of stochastic networks for the guaranteed delay with network utility maximization in multi-hop wireless networks. On contrary to single hop case, the delay is difficult to predict in multi-hop scenarios due to their unpredictable traffic pattern and variable queuing time in intermediate nodes. We present here a control policy for joint flow control and scheduling which can achieve high network utility and guarantees delay constraints. In addition, we derive the capacity region of the network under a given delay condition. Simulation results show that the proposed policy achieves near optimal network utility with delay guaranteed compare to exiting algorithms.

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

Access this article

Log in via an institution

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.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Bobarshad, H., van der Schaar, M., Aghvami, A., Dilmaghani, R., & Shikh-Bahaei, M. (2012). Analytical modeling for delay-sensitive video over wlan. IEEE Transactions on Multimedia, 14(2), 401–414.

    Article  Google Scholar 

  2. Georgiadis, L., Neely, M. J., & Tassiulas, L. (2006). Resource allocation and cross-layer control in wireless networks. Foundations and Trends in Networking, 1(1), 1–144.

    Article  Google Scholar 

  3. Eryilmaz, A. (2005). Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control. In: Proceedings of IEEE INFOCOM ’05, pp. 1794–1803.

  4. Stolyar, A. L. (2005). Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm. Queueing Systems: Theory and Applications, 50(4), 401–457.

    Article  MATH  MathSciNet  Google Scholar 

  5. Tassiulas, L., & Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transaction on Automatic Control, 37(12), 1936–1948.

    Article  MATH  MathSciNet  Google Scholar 

  6. Pham, N. T., Enkhbat, R., & Hwang, W. J. (2011). Delay-guaranteed scheduling and flow control for new generation mobile networks. IEICE Transactions on Communication, 94–B(6), 1556–1564.

    Article  Google Scholar 

  7. Ostovari, P., Khreishah, A., & Wu, J. (2013). Broadcasting with hard deadlines in wireless multihop networks using network coding. Wireless Communications and Mobile Computing.

  8. El-Gendy, M., Bose, A., Wang, H., & Shin, K. G. (2003). Statistical characterization for per-hop QoS. In Proceedings of the 11th international conference on quality of service.

  9. Joseph, V., & Chapman, B. (2009). Deploying QoS for Cisco IP and next generation networks: The definitive guide. Los Altos, CA: Morgan Kaufmann.

    Google Scholar 

  10. Kelly, F., Maulloo, A., & Tan, D. (1998). Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49, 237–252.

    Article  MATH  Google Scholar 

  11. Chiang, M. (2005). Balancing transport and physical layers in wireless multihop networks: Jointly optimal congestion control and power control. IEEE Journal on Selected Areas in Communications, 23(1), 104–116.

    Article  Google Scholar 

  12. Chiang, M., Low, S., Calderbank, A., & Doyle, J. (2007). Layering as optimization decomposition: A mathematical theory of network architectures. Proceedings of the IEEE, 95(1), 255–312.

    Article  Google Scholar 

  13. Shah, D., Tse, D., & Tsitsiklis, J. (2011). Hardness of low delay network scheduling. IEEE Transactions on Information Theory, 57(12), 7810–7817.

    Article  MathSciNet  Google Scholar 

  14. Gopalan, A., Caramanis, C., & Shakkottai, S. (2012). Low-delay wireless scheduling with partial channel-state information. In Proceedings IEEE INFOCOM, pp. 1071–1079.

  15. Neely, M. (2011). Opportunistic scheduling with worst case delay guarantees in single and multi-hop networks. In: INFOCOM, 2011 Proceedings IEEE, pp. 1728–1736.

  16. Neely, M. (2006). Energy optimal control for time-varying wireless networks. IEEE Transactions on Information Theory, 52(7), 2915–2934.

    Article  MATH  MathSciNet  Google Scholar 

  17. Le, L. B., Modiano, E., & Shroff, N. (2012). Optimal control of wireless networks with finite buffers. IEEE/ACM Transactions on Networking, 20(4), 1316–1329.

    Article  Google Scholar 

  18. Giaccone, P., Leonardi, E., & Shah, D. (2007). Throughput region of finite-buffered networks. IEEE Transaction of Parallel Distributed System, 18(2), 251–263.

    Article  Google Scholar 

  19. Khodaian, A., & Khalaj, B. (2010). Delay-constrained utility maximisation in multi-hop random access networks. IET Communications, 4(16), 1908–1918.

    Article  MATH  MathSciNet  Google Scholar 

  20. Li, Y., Chiang, M., Calderbank, A., & Diggavi, S. (2007). Optimal rate-reliability-delay tradeoff in networks with composite links. Proceedings of IEEE INFOCOM, 07, 526–534.

    Article  Google Scholar 

  21. Wang, Y., Vuran, M. C., & Goddard, S. (2012). Cross-layer analysis of the end-to-end delay distribution in wireless sensor networks. IEEE/ACM Transactions on Networking, 20(1), 305–318.

    Article  Google Scholar 

  22. Xue, D., & Ekici, E. (2012). Delay-guaranteed cross-layer scheduling in multihop wireless networks. IEEE/ACM Transactions on Networking, 21(6), 1696–1707.

  23. Huang, P.-K., Lin, X., & Wang, C.-C. (2011). A low-complexity congestion control and scheduling algorithm for multihop wireless networks with order-optimal per-flow delay. Proceedings IEEE INFOCOM, pp. 2588–2596.

  24. Kar, K., Luo, X., & Sarkar, S. (2009). Delay guarantees for throughput-optimal wireless link scheduling. In: Proceedings of IEEE INFOCOM ’09, pp. 2331–2339.

  25. Wang, Y., & Boyd, S. (2009). Performance bounds for linear stochastic control. Systems & Control Letters, 58(3), 178–182.

    Article  MATH  MathSciNet  Google Scholar 

  26. Zhang, Zhi, Moola, Sudhir, & Edwin K.P., Chong. (2010). Opportunistic fair scheduling in wireless networks: An approximate dynamic programming approach. Mobile Networks and Applications, 155, 710–728.

    Article  Google Scholar 

  27. Warren B., Powell. (2007). Approximate dynamic programming: Solving the curses of dimensionality (Wiley series in probability and statistics). New York: Wiley-Interscience.

    Google Scholar 

  28. Low, S., & Lapsley, D. (1999). Optimization flow control. I. Basic algorithm and convergence. IEEE/ACM Transactions on Networking, 7(6), 861–874.

    Article  Google Scholar 

  29. Mo, J., & Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking, 8(5), 556–567.

    Article  Google Scholar 

  30. Modiano, E., Shah, D., & Zussman, G. (2006). Maximizing throughput in wireless networks via gossiping. SIGMETRICS Performance Evaluation Review, 34, 27–38.

    Article  Google Scholar 

  31. Eryilmaz, A., Asuman, O., & Modiano, E. (2007). Polynomial complexity algorithms for full utilization of multi-hop wireless networks. Proceedings of INFOCOM, 2007, 499–507.

    Google Scholar 

  32. Sanghavi, S., Bui, L., & Srikant, R. (2007). Distributed link scheduling with constant overhead. SIGMETRICS Performance Evaluation Review, 35, 313–324.

    Article  Google Scholar 

  33. Jung, K., & Shah, D. (2007). Low delay scheduling in wireless network. IEEE International Symposium on Information Theory, 2007, 1396–1400.

    Google Scholar 

  34. Chaporkar, P., Kar, K., Luo, X., & Sarkar, S. (2008). Throughput and fairness guarantees through maximal scheduling in wireless networks. IEEE Transactions on Information Theory, 54(2), 572–594.

    Article  MathSciNet  Google Scholar 

  35. Liu, J., Stolyar, A., Chiang, M., & Poor, H. (2009). Queue back-pressure random access in multihop wireless networks: Optimality and stability. IEEE Transactions on Information Theory, 55(9), 4087–4098.

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

This research was supported by the MSIP (Ministry of Science, ICT and Future Planning), Korea, under the Global IT Talent support program (NIPA-2014-H0904-14-1006) supervised by the NIPA (National IT Industry Promotion Agency).

Author information

Author notes

  1. Ngoc-Thai Pham

    Present address: SVMC, Samsung Electronics, Hanoi, Vietnam

Authors and Affiliations

  1. Department of Information and Communication System, HSV-TRC, Inje University, Gimhae, Korea

    Thong Huynh, Ngoc-Thai Pham & Won-Joo Hwang

  2. Department of Information Security, Tongmyong University, Pusan, Korea

    Suk-Hwan Lee

Authors
  1. Thong Huynh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ngoc-Thai Pham
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Suk-Hwan Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Won-Joo Hwang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Won-Joo Hwang.

Appendix

Appendix

1.1 Proof of Proposition 1

We have following basic inequalities

$$\begin{aligned} y^{(c)} (t + 1)&\leqslant y^{(c)} (t) + q^{(c)} (t + 1) \leqslant y^{(c)} (t) + q^{(c)} (t) + 1 \\ q^{(c)} (t + 1)^2&\leqslant 2\sum \limits _{(a,i) \in L^{(c)} } {q_{a,i}^{(c)} (t + 1)^2 } \end{aligned}$$

Squaring both sides of Eqs. (1) and (3), and using above inequalities yields

$$\begin{aligned}&y^{(c)} (t + 1)^2 \leqslant y^{(c)} (t)^2 + (d_e^{(c)} )^2 \mu ^{(c)} (t)^2 + q^{(c)} (t + 1)^2 \\&\qquad - 2y^{(c)} (t)\left( {d_e^{(c)} \mu ^{(c)} (t) - (q^{(c)} (t) + r^{(c)} (t) - \mu ^{(c)} (t))} \right) \\&\quad \leqslant y^{(c)} (t)^2 + (d_e^{(c)} )^2 \mu ^{(c)} (t)^2 + 2\sum \limits _{(a,i) \in L^{(c)} } {q_{a,i}^{(c)} (t + 1)^2 } \\&\qquad - 2y^{(c)} (t)\left( ({d_e^{(c)}+1)\mu ^{(c)} (t) - q^{(c)} (t) - r^{(c)} (t)} \right) \\&q_i^{(c)} (t + 1)^2 y^{(c)} (t + 1) \leqslant q_i^{(c)} (t + 1)^2 (y^{(c)} (t) + q^{(c)} (t) + 1)\\&q_i^{(c)} (t + 1)^2 \leqslant q_i^{(c)} (t)^2 + \mu _{a,i}^{(c)} (t)^2 + \mu _{b,i}^{(c)} (t)^2 \\&\qquad \qquad \quad \qquad - 2q_i^{(c)} (t) \left( {\mu _{a,i}^{(c)} (t) - \mu _{i,b}^{(c)} (t)} \right) \end{aligned}$$

Summing over all queues and flows, noting that if \(i = s(c)\) then \(\mu _{a,i}^{(c)} (t) = r^{(c)}(t)\) and

$$\begin{aligned}&\sum \limits _c {\left( {q_{s^{(c)} }^{(c)} (t)q^{(c)} (t)} \right) r^{(c)} (t) } \\&\qquad -\sum \limits _c {\sum \limits _{(a,i)} {\mu _{a,i}^{(c)} (t)\left( {q_i^{(c)} (t) - q_a^{(c)} (t)} \right) q^{(c)} (t)} } \\&\quad \leqslant \sum \limits _c {\left( {q_{s^{(c)} }^{(c)} (t)q^{(c)} (t)} \right) r_{\max } + \sum \limits _c {\sum \limits _{(a,i)} {\mu _{a,i}^{(c)} (t)q_i^{(c)} (t)q^{(c)} (t)} } } \\&\quad \leqslant \sum \limits _c {\left( {q_{s^{(c)} }^{(c)} (t)q^{(c)} (t)} \right) r_{\max } + \sum \limits _c {\sum \limits _{(a,i)} {q_i^{(c)} (t)q^{(c)} (t)} } }, \end{aligned}$$

we obtains (6).

1.2 Proof of Theorem 1

To begin the proof, we first consider following lemma.

Lemma 1

A queue with arrival rate \(\lambda ^{(c)} = E\{ r^{(c)}_{in} (t)\}\) and departure rate \(\mu ^{(c)} =\lambda ^{(c)} +\varepsilon ^{(c)} \) has queue length bound by \(\frac{E\{ r^{(c)}_{in} (t)^{2}\} -2(\lambda ^{(c)})^{2} +\lambda ^{(c)} }{2\varepsilon ^{(c)} }\).

To begin the proof, we first compute bound of a queue with arrival rate \(\lambda ^{(c)} \) and departure rate \(\mu ^{(c)} =\lambda ^{(c)} +\varepsilon ^{(c)} \). Consider Lyapunov function \(L(y^{(c)} (t))=y^{(c)} (t)^{2} \) of dynamic evolution of the given queue. The drift of the Lyapunov function is defined as \(\varDelta L(y^{(c)} (t))=y^{(c)} (t+1)^{2} -y^{(c)} (t)^{2} \). Squaring both sides of the queueing evolution and rearranging, we have:

$$\begin{aligned} \varDelta L(y^{(c)} )=\bar{B}^{(c)} -2E\{ q^{(c)} (t)(\mu ^{(c)} (t)-r^{(c)}_{in} (t))\} \end{aligned}$$

where \(\bar{B}^{(c)} =E\{ (\mu ^{(c)} (t)-r^{(c)}_{in} (t))^{2} \} \).

Using the facts that \(E\{ (\mu ^{(c)})^{2} \} =E\{ \mu ^{(c)} \} \) and \(E\{ \mu ^{(c)} \} =\lambda ^{(c)} \) under the stability condition we obtain:

$$\begin{aligned} \bar{B}^{(c)} =E\{ r^{(c)}_{in} (t)^{2} \} -2(\lambda ^{(c)})^{2} +\lambda ^{(c)} . \end{aligned}$$

Using \(\mu ^{(c)} =\lambda ^{(c)} +\varepsilon ^{(c)} \) in (17) yields

$$\begin{aligned} \varDelta L(y^{(c)} )=\bar{B}^{(c)} -2\varepsilon ^{(c)} E\{ q^{(c)} (t)\} . \end{aligned}$$

Using Lemma 4.2 from [2] with the above condition, the following is obtained:

$$\begin{aligned} q^{(c)} = E\{ q^{(c)} (t)\} \le \frac{E\{ r^{(c)}_{in} (t)^{2}\} -2(\lambda ^{(c)})^{2} +\lambda ^{(c)} }{2\varepsilon ^{(c)} } . \end{aligned}$$
(17)

The proof of Theorem shows that (11) is sufficient condition for stability of the network with delay constraints. More specifically, it proves that Lyapunov of L(S(t)) is negative when \(y(t)\) is sufficiently large. We rewrite (7) as following

$$\begin{aligned} \varDelta L_e (S(t + 1))&= L_e (S(t + 1)) - L_e (S(t)) \nonumber \\&\leqslant + B_e(t) + \sum \limits _{c \in C} {(M^{(c)}(t) + 2q^{(c)} (t))y^{(c)} (t)} \nonumber \\&\quad + 2\sum \limits _{c \in C} {\left( {q_{s^{(c)} }^{(c)} (t)\left( {y^{(c)} (t) + 3} \right) + y^{(c)} (t)} \right) r^{(c)} (t)} \nonumber \\&\quad - 2\sum \limits _{c \in C} {\sum \limits _{(a,i) \in L^{(c)} } {q_i^{(c)} (t)} \left( {\mu _{i,b}^{(c)} (t) - \mu _{a,i}^{(c)} (t)} \right) \left( {y^{(c)} (t) + 3} \right) } \nonumber \\&\quad - 2\sum \limits _{c \in C} {\sum \limits _{(a,i) \in L^{(c)} } {q_i^{(c)} (t)} \mu _{s(c),i}^{(c)} (t)\left( {y^{(c)} (t) + 3} \right) } \nonumber \\&\quad - 2\sum \limits _{c \in C} {y^{(c)} (t)(d_e^{(c)} + 1)} \mu ^{(c)} (t) \end{aligned}$$
(18)

Following inequality hold for the optimal rate in (10) due to \(\alpha \le 1\)

$$\begin{aligned} r^{(c)*} (t)Q(t)&\leqslant \left( \frac{2}{V}\right) ^{ - \frac{1}{\alpha }} Q^{(c)} (t)^{ - \frac{1}{\alpha }} Q^{(c)} (t) \nonumber \\&\quad = \left( \frac{2}{V}\right) ^{ - \frac{1}{\alpha }} Q^{(c)} (t)^{\frac{{\alpha - 1}}{\alpha }} \nonumber \\&\leqslant \left( \frac{2}{V}\right) ^{ - \frac{1}{\alpha }} \end{aligned}$$
(19)

Plug flow control vector \(r^{(c)*} (t)\) into (18) and using (19) we have

$$\begin{aligned} \varDelta L_e (S(t + 1))&\leqslant B_e(t) + C\left( \frac{2}{V}\right) ^{ - \frac{1}{\alpha }} \\&\quad + \sum \limits _{c \in C} {(M^{(c)}(t) + 2q^{(c)} (t))y^{(c)} (t)} \\&\quad - 2\sum \limits _{c \in C} {\sum \limits _{(a,i) \in L^{(c)} } {q_i^{(c)} (t)} \left( {\mu _{i,b}^{(c)} (t) - \mu _{a,i}^{(c)} (t)} \right) \left( {y^{(c)} (t) + 3} \right) } \\&\quad - 2\sum \limits _{c \in C} {\sum \limits _{(a,i) \in L^{(c)} } {q_i^{(c)} (t)} \mu _{s(c),i}^{(c)} (t)\left( {y^{(c)} (t) + 3} \right) } \\&\quad - 2\sum \limits _{c \in C} {y^{(c)} (t)(d_e^{(c)} + 1)} \mu ^{(c)} (t) \end{aligned}$$

It is well-known that the dual control [2, 3]

$$\begin{aligned} r^{(c)*} (t) = \min \left( {(U'_c)^{ - 1} \left( \frac{2}{V}q^{(c)}_{s(c)} \right) ,r_{\max } } \right) \end{aligned}$$

obtains the maximum stability region \(\varLambda \). Since \(q^{(c)}_{s(c)} \le Q^{(c)}(t)\), DFSE flow control always admits smaller rate than the one of the dual control. Thus \(\lambda = \left\{ {\bar{r}^{(c)*} (t)} \right\} _{c \in C} \in \varLambda \) regardless the scheduling policy.

Since \(\lambda \in \varLambda \) there exist \(\varepsilon =\{ (N^{(c)}-1)\varepsilon ^{(c)} \} _{c \in C } >0\) such that \(\lambda = \left\{ {\bar{r}^{(c)*} (t)} \right\} _{c \in C} + \varepsilon \in \varLambda \). According to the Corollary 3.9 in [2], for this \(\lambda \), there exist a randomized algorithm that allocated \(\mu (t)\) such that on each node of flow \(c\) we have \(E\left\{ {\mu _{a,i}^{(c)} (t)} \right\} = E\left\{ {\mu _{i,b}^{(c)} (t) } \right\} + \varepsilon ^{(c)}\) and \(E\left\{ {\mu ^{(c)} (t)} \right\} \geqslant \lambda ^{(c)}\). According to Lemma 1, every queue \(q^{(c)}(t)\) is bounded under the randomized algorithm. Let \(\bar{B}_e\) the upper bound of \(B_e(t)\), hence \(B_e(t) \le \bar{B}_e\). Moreover, since elements of \(M^{(c)}(t)\) are bounded, \(\bar{M}^{(c)}\) are also bounded. Thus under the randomized algorithm we have expectation of \(\varDelta L_e (S(t + 1))\) is bounded as follows

$$\begin{aligned} E\left\{ {\varDelta L_e (S(t + 1))} \right\}&\leqslant \bar{B}_e + C\left( \frac{2}{V}\right) ^{ - \frac{1}{\alpha }} \nonumber \\&\quad + \sum \limits _{c \in C} {(\bar{M}^{(c)} + 2q^{(c)} (t))y^{(c)} (t)} \nonumber \\&\quad - 2\sum \limits _{c \in C} {\epsilon ^{(c)}\sum \limits _{(a,i) \in L^{(c)} } {q_i^{(c)} (t)} \left( {y^{(c)} (t) + 3} \right) } \nonumber \\&\quad - 2\sum \limits _{c \in C} {\sum \limits _{(a,i) \in L^{(c)} } {q_i^{(c)} (t)} \mu _{s(c),i}^{(c)} (t)\left( {y^{(c)} (t) + 3} \right) } \nonumber \\&\quad - 2\sum \limits _{c \in C} {y^{(c)} (t)(d_e^{(c)} + 1)}\lambda ^{(c)} \end{aligned}$$
(20)

Since the scheduling in DFSE minimizes over all possible choice of \(\mu (t)\) at every time slot, including the randomized algorithm, (20) is also held for DFSE scheduling. Note that \(q^{(c)} (t) = \sum \limits _{(a,i) \in L^{(c)} } {q_i^{(c)} (t)}\), (20) is then rewritten as follows

$$\begin{aligned}&E\left\{ {\varDelta L_e (S(t + 1))} \right\} \leqslant \bar{B}_e + C(\frac{2}{V})^{ - \frac{1}{\alpha }} \\&\qquad +\sum \limits _{c \in C} {(\bar{M}^{(c)} + 2(1 - \varepsilon ^{(c)} )q^{(c)} (t) - (d_e^{(c)} + 1)\lambda ^{(c)} )y^{(c)} (t)}\\&\qquad - 2\sum \limits _{c \in C} {\sum \limits _{(a,i) \in L^{(c)} } {q_i^{(c)} (t)} \mu _{s(c),i}^{(c)} (t)\left( {y^{(c)} (t) + 3} \right) } \\&\qquad - 6\sum \limits _{c \in C} {\epsilon ^{(c)} q^{(c)} (t)} \end{aligned}$$

It is clear that if (21) holds, the queueing system is stable since large \(y^{(c)}(t)\) leads to negative drift of the Lyapunov function \(L_e (S(t + 1))\) (Lemma 4.2 in [2, 3]). We now shows that condition (11) of Theorem 1 is sufficient condition of (21).

$$\begin{aligned} \bar{M}^{(c)} + 2(1 - \varepsilon ^{(c)} )q^{(c)} (t) - (d_e^{(c)} + 1)\lambda ^{(c)} \le 0 \end{aligned}$$
(21)

We first calculate the upper bound of \(q^{(c)} (t)\) under the randomized algorithm. According to Lemma 1, for the first node in flow \(c\) we have

$$\begin{aligned} q_{s(c)}^{(c)} (t) \le \frac{E\{ r^{(c)} (t)^{2}\} -2(\lambda ^{(c)})^{2} +\lambda ^{(c)} }{2\varepsilon ^{(c)} } . \end{aligned}$$

For intermediate node, since \( E\{ r^{(c)}_{in} (t)^{2}\} = E\{ r^{(c)}_{in} (t)\} = \lambda , ^{(c)}\)

$$\begin{aligned} q_{i}^{(c)} (t) \le \frac{\lambda ^{(c)}-(\lambda ^{(c)})^{2} }{\varepsilon ^{(c)} } . \end{aligned}$$

Hence, \(q^{(c)}(t)\) of flow \(c\) with \(N^{(c)}\) nodes on the path is bounded as follows

$$\begin{aligned} q^{(c)} (t)&\le \frac{{E\{ r^{(c)} (t)^2 \} - 2(N^{(c)}-1)(\lambda ^{(c)} )^2 + (2N^{(c)}-3)\lambda ^{(c)} }}{{2\varepsilon ^{(c)} }} \\&=q_{0}^{(c)}. \end{aligned}$$

Thus given (11), (21) holds for all \(q^(c)(t)\). Theorem 1 holds.

1.3 Proof of Theorem 2

Proof technique of Theorem 2 is similar with the one of Theorem one. Here are the sketch of the proof. Lyapunov drift of \(L_{h}(S(t))\) is defined as follows

$$\begin{aligned} \varDelta L_{h}(S(t))&= L_{h}(S(t + 1)) - L_{h}(S(t)) \\&\le B_h(t) + \sum \limits _{c} {\sum \limits _{(a,i)} {2q_i^{(c)} (t)z_i^{(c)} (t)}}\nonumber \\&\quad - \sum \limits _{c} {\sum \limits _{i} {z_i^{(c)} (t)\left( {(d_h^{(c)} + 1)\mu _{i,b}^{(c)} - \mu _{a,i}^{(c)} } \right) } } \nonumber \\&\quad - \sum \limits _{c} {\sum \limits _{i} {q_i^{(c)} (t)\left( {\mu _{i,b}^{(c)} - \mu _{a,i}^{(c)} } \right) } } \nonumber \\&\quad + \sum \limits _{c} {r^{(c)} {\left( {z_{s(c)}^{(c)} (t) + q_{s(c)}^{(c)} (t)} \right) } } \nonumber \end{aligned}$$
(22)

Applying DFSH flow control and randomized algorithm into (22), noting that \(E\left\{ \mu _{i,b}^{(c)} (t)\right. \left. - \mu _{a,i}^{(c)} (t) \right\} = \lambda ^{(c)*} + \varepsilon \) and \(E\left\{ {\mu ^{(c)} (t)} \right\} \geqslant \lambda ^{(c)*}\) we obtain

$$\begin{aligned} E\{\varDelta L_{h}(S(t))\}&\le B_h(t) + C\left( \frac{2}{V}\right) ^{ - \frac{1}{\alpha }} - 2\epsilon \sum \limits _{c} {\sum \limits _{i} {q_i^{(c)} (t)} } \\&\quad + 2\sum \limits _{c} {\sum \limits _{(a,i)} {q_i^{(c)} (t)z_i^{(c)} (t)}}\\&\quad - 2\sum \limits _{c} {\sum \limits _{i} {z_i^{(c)} (t)\left( {d_h^{(c)} (\lambda ^{(c)} + \epsilon ) + \epsilon } \right) } } \end{aligned}$$

This is equivalent to

$$\begin{aligned} E\{\varDelta L_{h}(S(t))\}&\le B_h(t) + C\left( \frac{2}{V}\right) ^{ - \frac{1}{\alpha }} - 2\epsilon \sum \limits _{c} {\sum \limits _{i} {q_i^{(c)} (t)} } \\&\quad + 2\sum \limits _{c} {\sum \limits _{i} {z_i^{(c)} (t)\left( q_i^{(c)} (t) - {d_h^{(c)} (\lambda ^{(c)} + \epsilon ) - \epsilon } \right) } } \end{aligned}$$

Thus, sufficient condition for the stability of the system under DFSH is

$$\begin{aligned} q_i^{(c)} (t) - {d_h^{(c)} (\lambda ^{(c)} + \epsilon ) - \epsilon } \le 0 \end{aligned}$$
(23)

Condition (16) guarantees that (23) holds for every \(q_i^{(c)} (t)\). Thus (16) is sufficient condition for (23). Theorem 2 holds.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Huynh, T., Pham, NT., Lee, SH. et al. Dynamic Control Policy for Delay Guarantees in Multi-hop Wireless Networks. Wireless Pers Commun 80, 647–670 (2015). https://doi.org/10.1007/s11277-014-2033-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11277-014-2033-3

Keywords

Search

Navigation