Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Queueing Systems
Erschienen in: Queueing Systems 3-4/2012

01.12.2012

On distributed scheduling with heterogeneously delayed network-state information

verfasst von: Akula Aneesh Reddy, Siddhartha Banerjee, Aditya Gopalan, Sanjay Shakkottai, Lei Ying

Erschienen in: Queueing Systems | Ausgabe 3-4/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study the problem of distributed scheduling in wireless networks, where each node makes individual scheduling decisions based on heterogeneously delayed network state information (NSI). This leads to inconsistency in the views of the network across nodes, which, coupled with interference, makes it challenging to schedule for high throughputs.
We characterize the network throughput region for this setup, and develop optimal scheduling policies to achieve the same. Our scheduling policies have a threshold-based structure and, moreover, require the nodes to use only the “smallest critical subset” of the available delayed NSI to make decisions. In addition, using Markov chain mixing techniques, we quantify the impact of delayed NSI on the throughput region. This not only highlights the value of extra NSI for scheduling, but also characterizes the loss in throughput incurred by lower complexity scheduling policies which use homogeneously delayed NSI.
Vorheriger Artikel Editorial introduction
Nächster Artikel Towards a queueing-based framework for in-network function computation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
This assumption is to ensure that the system state Markov chain (defined in Sect. 3.2) is irreducible and aperiodic, by suitably augmenting the state space.
 
2
These assumptions are to ensure that the system state Markov chain (defined in Sect. 3.2) is irreducible and aperiodic, by suitably augmenting the state space.
 
Literatur
1.
Reddy, A., Banerjee, S., Gopalan, A., Shakkottai, S., Ying, L.: Wireless scheduling with heterogeneously delayed network-state information. In: Proc. Ann. Allerton Conf. Communication, Control and Computing (2010)
2.
Tassiulas, L., Ephremides, A.: Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control, 1936–1948 (1992)
3.
Andrews, M., Kumaran, K., Ramanan, K., Stolyar, A.L., Vijayakumar, R., Whiting, P.: CDMA data QoS scheduling on the forward link with variable channel conditions. Bell Labs Tech. Memo (2000)
4.
Tassiulas, L., Ephremides, A.: Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Trans. Inf. Theory 39, 466–478 (1993) CrossRef
5.
Shakkottai, S., Stolyar, A.: Scheduling for multiple flows sharing a time-varying channel: the exponential rule. Ann. Math. Stat. 207, 185–202 (2001)
6.
Stolyar, A.: Maximizing queueing network utility subject to stability: greedy primal–dual algorithm. Queueing Syst. 50, 401–457 (2005) CrossRef
7.
Eryilmaz, A., Srikant, R., Perkins, J.: Stable scheduling policies for fading wireless channels. IEEE/ACM Trans. Netw. 13, 411–424 (2005) CrossRef
8.
Neely, M.J., Modiano, E., Rohrs, C.E.: Power and server allocation in a multi-beam satellite with time varying channels. Proc. IEEE INFOCOM 3, 1451–1460 (2002)
9.
Neely, M.J., Modiano, E., Li, C.: Fairness and optimal stochastic control for heterogeneous networks. Proc. IEEE INFOCOM 3, 1723–1734 (2005)
10.
Lin, X., Rasool, S.: Constant-time distributed scheduling policies for ad HocWireless networks. In: Proc. Conf. on Decision and Control (2006)
11.
Joo, C., Shroff, N.: Performance of random access scheduling schemes in multihop wireless networks. Proc. IEEE INFOCOM (2007)
12.
Rajagopalan, S., Shin, J., Shah, D.: Network adiabatic theorem: an efficient randomized protocol for contention resolution. In: Proc. Ann. ACM SIGMETRICS Conf. (2009)
13.
Jiang, L., Walrand, J.: A distributed CSMA algorithm for throughput and utility maximization in wireless networks. In: Proc. Ann. Allerton Conf. Communication, Control and Computing (2008)
14.
Liu, J., Yi, Y., Proutiere, A., Chiang, M., Poor, H.V.: Maximizing utility via random access without message passing. Microsoft Research Technical Report (2008)
15.
Rajagopalan, S., Shah, D., Shin, J.: Network adiabatic theorem: an efficient randomized protocol for contention resolution. In: Proc. Ann. ACM SIGMETRICS Conf., pp. 133–144 (2009)
16.
Ni, J., Tan, B., Srikant, R.: Q-CSMA: Queue-length based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks. In: Proceedings of IEEE INFOCOM Mini-Conference (2010)
17.
Ahmad, S., Mingyan, L., Javidi, T., Zhao, Q., Krishnamachari, B.: Optimality of myopic sensing in multichannel opportunistic access. IEEE Trans. Inf. Theory 55, 4040–4050 (2009) CrossRef
18.
19.
Chang, N., Liu, M.: Optimal channel probing and transmission scheduling for opportunistic spectrum access. In: ACM Int. Conf. on Mobile Computing and Networking (MobiCom) (2007)
20.
Gopalan, A., Caramanis, C., Shakkottai, S.: On wireless scheduling with partial channel state information. IEEE Trans. Inf. Theory (2011)
21.
Chaporkar, P., Proutiere, A., Asnani, H., Karandikar, A.: Scheduling with limited information in wireless systems. In: ACM Mobihoc, pp. 75–84 (2009) CrossRef
22.
Pantelidou, A., Ephremides, A., Tits, A.: Joint scheduling and routing for ad-hoc networks under channel state uncertainty. In: Intl. Symposium on Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks (WiOpt), pp. 1–8 (2007) CrossRef
23.
Kar, K., Luo, X., Sarkar, S.: Throughput-optimal scheduling in multichannel access point networks under infrequent channel measurements. In: Proceedings of IEEE INFOCOM (2007)
24.
Chen, J., Berry, R.A., Honig, M.L.: Limited feedback schemes for downlink OFDMA based on sub-channel groups. IEEE J. Sel. Areas Commun. 26, 1451–1461 (2008) CrossRef
25.
Ouyang, M., Ying, L.: On scheduling in multi-channel wireless downlink networks with limited feedback. In: Proc. Ann. Allerton Conf. Communication, Control and Computing, pp. 455–469 (2009)
26.
Ouyang, M., Ying, L.: On optimal feedback allocation in multichannel wireless downlinks. In: ACM Mobihoc (2010)
27.
Ying, L., Shakkottai, S.: On throughput optimality with delayed network-state information. Technical report (2008)
28.
Ying, L., Shakkottai, S.: Scheduling in mobile ad hoc networks with topology and channel-state uncertainty. In: Proc. IEEE INFOCOM, pp. 2347–2355 (2009)
29.
Billingsley, P.: Probability and Measure. Wiley, New York (1994)
30.
Asmussen, S.: Applied Probability and Queues. Springer, New York (2003)
Metadaten
Titel
On distributed scheduling with heterogeneously delayed network-state information
verfasst von
Akula Aneesh Reddy
Siddhartha Banerjee
Aditya Gopalan
Sanjay Shakkottai
Lei Ying
Publikationsdatum
01.12.2012
Verlag
Springer US
Erschienen in
Queueing Systems / Ausgabe 3-4/2012
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-012-9312-z

Weitere Artikel der Ausgabe 3-4/2012

Queueing Systems 3-4/2012 Zur Ausgabe

BriefCommunication

Controlled mobility in stochastic and dynamic wireless networks

BriefCommunication

Towards a queueing-based framework for in-network function computation

BriefCommunication

Distributed caching over heterogeneous mobile networks

BriefCommunication

Scheduling with pairwise XORing of packets under statistical overhearing information and feedback

BriefCommunication

Asymptotically tight steady-state queue length bounds implied by drift conditions

News

Editorial introduction

Premium Partner

    Bildnachweise