Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Wireless Networks
Published in: Wireless Networks 5/2016

01-07-2016

MDP based link scheduling in wireless networks to maximize the reliability

Authors: Jun Xu, Jianfeng Yang, Yinbo Xie, Chengcheng Guo, Yinbo Yu

Published in: Wireless Networks | Issue 5/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper considers wireless networks where communication links are unstable and link interference is a challenge to design high performance scheduling algorithms. Wireless links are time varying and are modeled by Markov stochastic processes. The problem of designing an optimal link scheduling algorithm to maximize the expected reliability of the network is formulated into a Markov Decision Process first. The optimal solution can be obtained by the finite backward induction algorithm. However, the time complexity is very high. Thus, we develop an approximate link scheduling algorithm with an approximate ratio of \(2(N - 1)(r_{M}\Delta - r_{m} \delta ),\) where N is the number of decision epochs, r M is the maximum link reliability, r m is the minimum link reliability, Δ is the number of links in the largest maximal independent set and δ is the number of links in the smallest maximal independent set. Simulations are conducted in different scenarios under different network topologies.
previous article Priority based efficient data scheduling technique for VANETs
next article SEAD: A simple and efficient adaptive data dissemination protocol in vehicular ad-hoc networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Tassiulas, L., & Ephremides, A. (1992). 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.MathSciNetCrossRefMATH
2.
Wang, W., et al. (2006). Efficient interference-aware TDMA link scheduling for static wireless networks. In Proceedings of the 12th annual international conference on mobile computing and networking. ACM.
3.
Djukic, P., & Valaee, S. (2007). Distributed link scheduling for TDMA mesh networks. In International conference on communications (ICC ‘07).
4.
Djukic, P., & Valaee, S. (2009). Delay aware link scheduling for multi-hop TDMA wireless networks. IEEE/ACM Transactions on Networking, 17(3), 870–883.CrossRef
5.
Chakchouk, N., & Hamdaoui, B. (2011). Traffic and interference aware scheduling for multiradio multichannel wireless mesh networks. IEEE Transactions on Vehicular Technology, 60(2), 555–565.CrossRef
6.
Angelakis, V., et al. (2014). Minimum-time link scheduling for emptying wireless systems: Solution characterization and algorithmic framework. IEEE Transactions on Information Theory, 60(2), 1083–1100.MathSciNetCrossRef
7.
Zhenhua, Z., et al. (2012). Energy-efficient deadline-constrained maximum reliability forwarding in lossy networks. IEEE Transactions on Wireless Communications, 11(10), 3474–3483.CrossRef
8.
9.
Elliott, E. O. (1963). Estimates of error rates for codes on burst-noise channels. The Bell System Technical Journal, 42(5), 1977–1997.CrossRef
10.
Hong, S. W., & Moayeri, N. (1995). Finite-state Markov channel—A useful model for radio communication channels. IEEE Transactions on Vehicular Technology, 44(1), 163–171.CrossRef
11.
Shakkottai, S., & Srikant, R. (2002). Scheduling real-time traffic with deadlines over a wireless channel. Wireless Networks, 8(1), 13–26.CrossRefMATH
12.
Lei, Y., Murugesan, S., & Junshan, Z. (2011). Real-time scheduling over Markovian channels: When partial observability meets hard deadlines. In IEEE global telecommunications conference (GLOBECOM 2011).
13.
Ruogu, L., & Eryilmaz, A. (2012). Scheduling for end-to-end deadline-constrained traffic with reliability requirements in multihop networks. IEEE/ACM Transactions on Networking, 20(5), 1649–1662.CrossRef
14.
Hou, I. H., & Kumar, P. (2011). A survey of recent results on real-time wireless networking. In Proceedings of the real-time wireless for industrial applications.
15.
Laufer, R., et al. (2014). A cross-layer backpressure architecture for wireless multihop networks. IEEE/ACM Transactions on Networking, 22(2), 363–376.CrossRef
16.
Singh, C., Nedic, A., & Srikant, R. (2014). LP-relaxation based distributed algorithms for scheduling in wireless networks. In INFOCOM, 2014 Proceedings IEEE (pp. 1905–1913). IEEE.
17.
Le, L. B., Modiano, E., & Joo, C. (2010). Longest-queue-first scheduling under SINR interference model. In MobiHoc, pp. 41–50.
18.
Djukic, P., & Valaee, S. (2007). Link scheduling for minimum delay in spatial re-use TDMA. In 26th IEEE international conference on computer communications (INFOCOM 2007).
19.
Cappanera, P., et al. (2009). Link scheduling with end-to-end delay constraints in wireless mesh networks. In IEEE international symposium on world of wireless, mobile and multimedia networks and workshops (WoWMoM 2009).
20.
Jayachandran, P., & Andrews, M. (2010). Minimizing end-to-end delay in wireless networks using a coordinated EDF schedule. In Proceedings of the INFOCOM. IEEE.
21.
Bhattacharya, P. P., Tassiulas, L., & Ephremides, A. (1997). Optimal scheduling with deadline constraints in tree networks. IEEE Transactions on Automatic Control, 42(12), 1703–1705.MathSciNetCrossRefMATH
22.
Han, S., et al. (2011). Reliable and real-time communication in industrial wireless mesh networks. In Real-Time and Embedded Technology and Applications Symposium (RTAS), 2011 17th IEEE (pp. 3–12). IEEE.
23.
Sheng, Z., et al. (2013). A highly reliable link scheduling strategy for WirelessHART networks. In International conference on advanced technologies for communications (ATC).
24.
Neely, M. J., & Supittayapornpong, S. (2013). Dynamic Markov decision policies for delay constrained wireless scheduling. IEEE Transactions on Automatic Control, 58(8), 1948–1961.MathSciNetCrossRef
25.
I-Hong, H., Borkar, V., & Kumar, P. R. (2009). A theory of QoS for wireless. In INFOCOM 2009.
26.
Hou, I. H., & Kumar, P. (2009). Admission control and scheduling for QoS guarantees for variable-bit-rate applications on wireless channels. In MobiHoc ‘09, pp. 175–184.
27.
I-Hong, H., & P. R. Kumar. (2010). Scheduling heterogeneous real-time traffic over fading wireless channels. In Proceedings of the INFOCOM, 2010. IEEE.
28.
Hou, I. (2013). Providing end-to-end delay guarantees for multi-hop wireless sensor networks. In IEEE global communications conference (GLOBECOM 2013).
29.
Marbach, P., Eryilmaz, A., & Ozdaglar, A. (2011). Asynchronous CSMA policies in multihop wireless networks with primary interference constraints. IEEE Transactions on Information Theory, 57(6), 3644–3676.MathSciNetCrossRef
Metadata
Title
MDP based link scheduling in wireless networks to maximize the reliability
Authors
Jun Xu
Jianfeng Yang
Yinbo Xie
Chengcheng Guo
Yinbo Yu
Publication date
01-07-2016
Publisher
Springer US
Published in
Wireless Networks / Issue 5/2016
Print ISSN: 1022-0038
Electronic ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-015-1049-2

Other articles of this Issue 5/2016

Wireless Networks 5/2016 Go to the issue

OriginalPaper

Performance analysis of threshold digital relaying M2M cooperative networks

OriginalPaper

FISCP: fine-grained device-free positioning system for multiple targets working in sparse deployments

OriginalPaper

Energy efficiency analysis of IEEE 802.15.6 based wireless body area networks in scheduled access mode

OriginalPaper

An adaptive routing algorithm considering position and social similarities in an opportunistic network

OriginalPaper

Security-embedded opportunistic user cooperation with full diversity

OriginalPaper

On minimizing the system information age in vehicular ad-hoc networks via efficient scheduling and piggybacking