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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Wireless Networks
Erschienen in: Wireless Networks 8/2017

21.05.2016

Link scheduling for throughput maximization in multihop wireless networks under physical interference

verfasst von: Yaqin Zhou, Xiang-Yang Li, Min Liu, Zhongcheng Li, Xiaohua Xu

Erschienen in: Wireless Networks | Ausgabe 8/2017

Einloggen

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

search-config
loading …

Abstract

We consider the problem of link scheduling for throughput maximization in multihop wireless networks. Majority of previous methods are restricted to graph-based interference models. In this paper we study the link scheduling problem using a more realistic physical interference model. Through some key observations about this model, we develop efficient link scheduling algorithms by exploiting the intrinsic connections between the physical interference model and the graph-based interference model. For one variant of the problem where each node can dynamically adjust its transmission power, we design a scheduling method with O(g(E)) approximation to the optimal throughput capacity where g(E) denotes length diversity. For the other variant where each node has a fixed but possible different transmission powers for different nodes, we design a method with O(g(E))-approximation ratio when the transmission powers of all nodes are within a constant factor of each other, and in general with an approximation ratio of \(O(g(E)\log \rho )\) where \(\log \rho\) is power diversity. We further prove that our algorithm for fixed transmission power case retains O(g(E)) approximation for any length-monotone, sub-linear fixed power setting. Furthermore, all these approximation factors are independent of network size .
Vorheriger Artikel A comprehensive survey of network coding in vehicular ad-hoc networks
Nächster Artikel Anomaly based intrusion detection for 802.11 networks with optimal features using SVM classifier

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

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!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Other constant approximation algorithms on the MWISD problem are also applicable, depending on the desired tradeoff between computation complexity and approximation ratio. For example, we can also use other algorithms with lower complexity and smaller constant approximation ratios.
 
2
For convenience, we let \(3^{\kappa } > \sigma\), but we do not necessarily assume \(3^{\kappa } > \sigma\), we later show that the lemma also holds when \(3^{\kappa } \le \sigma\).
 
Literatur
1.
Li, X.-Y., & Wang, Y. (2006). Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks. Journal of Parallel and Distributed Computing, 66, 515–530.CrossRefMATH
2.
Sharma, G., Mazumdar, R., & Shroff, N. (2006). On the complexity of scheduling in wireless networks. In Proceedings of the ACM MobiCom (pp. 227–238).
3.
Halldórsson, M., & Wattenhofer, R. (2009). Wireless communication is in APX. In Proceedings of the 36th international colloquium on automata, languages and programming (pp. 525–536).
4.
Le, L.-B., Modiano, E., Joo, C., & Shroff, N. B. (2009). Longest-queue-first scheduling under SINR interference model. In Proceedings of the ACM Mobihoc (pp. 41–50).
5.
Tassiulas, L., & Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE/ACM Transactions on Automatic Control, 37, 1936–1948.MathSciNetCrossRefMATH
6.
Xu, X.-H., Tang, S.-J., & Wan, P.-J. (2010). Maximum weighted independent set of links under physical interference model. In LNCS (vol. 6221, pp. 68–74). Heidelberg: Springer.
7.
Halldórsson, M. M., & Mitra, P. (2012). Wireless capacity and admission control in cognitive radio. In Proceedings of the IEEE Infocom (pp. 855–863).
8.
Zhou, Y. Q., Li, X.-Y., Liu, M., Li, Z. C., Tang, S. J., Mao, X. F., et al.(2012). Distributed link scheduling for throughput maximization under physical interference model. In Proceedings of the IEEE Infocom (pp. 2691–2695).
9.
Xu, X. H., Tang, S. J., & Li, X.-Y. (2011). Stable wireless link scheduling subject to physical interferences with power control, manuscript.
10.
Wan, P.-J., Frieder, O., Jia, X.-H., Yao, F., Xu, X.-H., & Tang, S.-J. (2011). Wireless link scheduling under physical interference model. In Proceedings of the IEEE Infocom (pp. 838–845).
11.
Pei, G., & Vullikanti, A. (2012). Low-complexity scheduling for wireless networks. In Proceedings of the ACM MobiHoc’12 (pp. 35–44). ACM.
12.
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.CrossRefMATH
13.
Halldórsson, M. (2009). Wireless scheduling with power control. In Algorithms—ESA (vol. 5757, pp. 361–372).
14.
Sanghavi, S., Bui, L., & Srikant, R. (2007). Distributed link scheduling with constant overhead. In Proceedings of the ACM SIGMETRICS (pp. 313–324).
15.
Tang, S.-J., Li, X.-Y., Wu, X., Wu, Y., Mao, X., Xu, P., et al. (2009). Low complexity stable link scheduling for maximizing throughput in wireless networks. In Proceedings of the IEEE SECON (pp. 1–9).
16.
Modiano, E., Shah, D., & Zussman, G. (2006). Maximizing throughput in wireless networks via gossiping. In Proceedings of the ACM SIGMETRICS (pp. 27–38).
17.
Lin, X., & Rasool, S. B. (2006). Constant-time distributed scheduling policies for ad hoc wireless networks. In Proceedings of the IEEE CDC (pp. 1258–1263).
18.
Joo, C., & Shroff, N. B. (2009). Performance of random access scheduling schemes in multi-hop wireless networks. IEEE/ACM Transactions on Networking, 17, 1481–1493.CrossRef
19.
Joo, C., Lin, X., & Shroff, N. B. (2008). Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks. In Proceedings of the IEEE Infocom (pp. 1103–1111).
20.
Tassiulas, L., & Ephremides, A. (1998.) Linear complexity algorithms for maximum throughput in radio networks and input queued switches. In Proceedings of the IEEE Infocom (pp. 533–539).
21.
Chaporkar, P., Kar, K., & Sarkar, S. (2008). Throughput and fairness guarantees through maximal scheduling in wireless networks. IEEE/ACM Transactions on Information Theory, 54, 572–594.MathSciNetCrossRefMATH
22.
Wu, D., Bao, L., & Liu, C. H. (2013). Scalable channel allocation and access scheduling for wireless internet-of-things. IEEE Sensors Journal, 13(10), 3596–3604.CrossRef
23.
Wu, D., Yang, S.-H., Bao, L., & Liu, C. H. (2014). Joint multi-radio multi-channel assignment, scheduling, and routing in wireless mesh networks. Wireless Networks, 20(1), 11–24.CrossRef
24.
Chafekar, D., Kumar, V., Marathe, M., Parthasarathy, S., & Srinivasan, A. (2008). Arrpoximation algorithms for computing capacity of wireless networks with SINR constraints. In Proceedings of the IEEE Infocom (pp. 1166–1174).
25.
Asgeirsson, E., Halldórsson, M., & Mitra, P. (2012). A fully distributed algorithm for throughput performance in wireless networks. In Information sciences and systems (CISS) (pp. 1 –5).
26.
Ryu, J., Joo, C., Kwon, T. T., Shroff, N. B., & Choi, Y. (2010). Distributed SINR based scheduling algorithm for multi-hop wireless networks. In Proceedings of the ACM MSWIM (pp. 376–380).
27.
Asgeirsson, E. I., Halldórsson, M. M., & Mitra, P. (2012). Wireless network stability in the sinr model. CoRR, abs/1210.4446.
28.
Lee, H.-W., Modiano, E., & Le, L. B. (2009). Distributed throughput maximization in wireless networks via random power allocation. In Modeling and optimization in mobile, ad hoc, and wireless networks (WiOPT) (pp. 1 –9).
29.
Halldórsson, M. M., & Mitra, P. (2011). Wireless capacity with oblivious power in general metrics. In Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms (pp. 1538–1548).
30.
Kesselheim, T. (2011). A constant-factor approximation for wireless capacity maximization with power control in the SINR model. In Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms (pp. 1549–1559).
31.
Wan, P.-J., Chen, D. C., Dai, G. J., Wang, Z., & Yao, F. (2012). Maximizing capacity with power control under physical interference model in duplex mode. In Proceedings of the IEEE Infocom (pp. 415–423).
32.
Pei, G., & Kumar, V. S. A. (2012). Distributed algorithms for maximum link scheduling under the physical interference model. CoRR, abs/1208.0811.
33.
Halldórsson, M. M., Holzer, S., Mitra, P., & Wattenhofer, R. (2012). The power of non-uniform wireless power. CoRR, abs/1210.3371.
34.
Blough, D. M., Resta, G., & Santi, P. (2010). Approximation algorithms for wireless link scheduling with SINR-based inteference. IEEE/ACM Transactions on Networking, 18, 1701–1712.CrossRef
35.
Xu, X., Cao, J., & Li, X.-Y. (2012). Mlls: Minimum length link scheduling under physical interference model. CoRR, abs/1208.0627, 2012.
36.
Goussevskaia, O., Oswald, Y., & Wattenhofer, R. (2007). Complexity in geometric SINR. In Proceedings of the ACM Mobihoc (pp. 100–109).
37.
Lin, X., & Shroff, N. B. (2005). The impact of imperfect scheduling on cross-layer rate control in multihop wireless networks. In Proceedings of the IEEE Infocom (pp. 1804–1814).
38.
Wan, P., Ma, C., Tang, S., & Xu, B. (2011). Maximizing capacity with power control under physical interference model in simplex mode. Wireless Algorithms, Systems, and Applications, 6843, 84–95.
39.
Metadaten
Titel
Link scheduling for throughput maximization in multihop wireless networks under physical interference
verfasst von
Yaqin Zhou
Xiang-Yang Li
Min Liu
Zhongcheng Li
Xiaohua Xu
Publikationsdatum
21.05.2016
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 8/2017
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-016-1276-1

Weitere Artikel der Ausgabe 8/2017

Wireless Networks 8/2017 Zur Ausgabe

OriginalPaper

Resource management for symmetrical applications over heterogeneous services in IEEE 802.16

OriginalPaper

Mobile anchor-assisted localization over android

OriginalPaper

Network selection in heterogeneous wireless networks using multi-criteria decision-making algorithms: a review

OriginalPaper

Surrogate modeling based cognitive decision engine for optimization of WLAN performance

OriginalPaper

A non-iterative resource allocation strategy for device-to-device communications in underlaying cellular networks

OriginalPaper

A comprehensive survey of network coding in vehicular ad-hoc networks

Neuer Inhalt

    Bildnachweise