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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Wireless Networks
Erschienen in: Wireless Networks 6/2010

01.08.2010

Computational aspects of optimal schedules with power control and multiple bitrates selection in multihop wireless networks

verfasst von: Peng Wang, Stephan Bohacek

Erschienen in: Wireless Networks | Ausgabe 6/2010

Einloggen

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

search-config
loading …

Abstract

A significant amount of research on optimal scheduling has focused on the case where links can transmit with only a single bit-rate and a single transmission power. This paper develops techniques to accommodate multiple bit-rates and multiple transmission powers as well as a continuum of transmission powers. Optimizing over a large number of bit-rates and transmission powers typically increases the computed throughput at the expense of increasing the computation time. This paper examines the trade-off between computed throughput and computation time, with emphasis on the case when the relationship between bit-rate and SINR is the same as it is for 802.11a/g. One finding of this paper is a progression of Pareto optimal schemes that increases the computed capacity. A second finding is that optimizing over two transmission powers and two or three bit-rates achieves nearly the same throughput as optimizing over a continuum of transmission powers and all supported bit-rates. However, optimizing over a continuum of transmission powers and all supported bit-rates is far more computationally complex than optimizing over two transmission powers and a few bit-rates.
Vorheriger Artikel Cross-layer speculative architecture for end systems and gateways in computer networks with lossy links
Nächster Artikel A sustainable heuristic QoS routing algorithm for pervasive multi-layered satellite wireless networks

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
Important exceptions include [12] and [13].
 
2
Note that 802.11 a supports eight bit-rates, and yet Fig. 1 only shows seven bit-rates, 9 Mbps is missing. The reason is that the relationships between SNR and PSP at 9 Mbps and at 12 Mbps are the same. Thus, there is no need to consider the 9 Mbps bit-rate.
 
3
Gateways have both wired and wireless interfaces, whereas wireless routers only have wireless interfaces.
 
Literatur
1.
Alekseev, V. E., & Lozin, V. V. (2000). Augmenting graphs for independent sets. Rutgers Center of Operations Research, Tech. Rep. 59-2000.
2.
Arikan, E. (1984). Some complexity results about packet radio networks. IEEE Transactions on Information Theory, 30, 681– 685.MATHCrossRefMathSciNet
3.
Bertsekas, D. P. (2003). Nonlinear programming. Belmont, MA: Athena Scientific.
4.
5.
Bohacek, S., & Wang, P. (2007). Toward tractable computation of the capacity of multihop wireless networks. In IEEE infocom (pp. 2099–2107).
6.
Brar, G., Blough, D. M., & Santi, P. (2006). Computationally efficient scheduling with the physical interference model for throughtput improvment in wireless mesh networks. In Mobicom (pp. 2–13).
7.
Bui, L., Eryilmaz, A., Srikant, R., & Wu, X. (2006). Joint asynchronous congestion control and distributed scheduling for multi-hop wireless networks. In IEEE infocom (pp. 1–12).
8.
Catrein, D., Imhof, L. A., & Mathar, R. (2004). Power control, capacity, and duality of uplink and downlink in cellular CDMA systems. IEEE Transactions on Communications, 52(10), 1777–1785.CrossRef
9.
Chen, G. H., Kuo, M. T., & Sheu, J. P. (1988). An optimal time algorithm for finding a maximum weight independent set in a tree. BIT, 23, 353–356.CrossRefMathSciNet
10.
Chen, L., Low, S.H., Chiang, M., & Doyle, J.C. (2006). Cross-layer congestion control, routing and scheduling design in ad hoc wireless networks. In IEEE infocom (pp. 1–13).
11.
Chen, L., Low, S.H., & Doyle, J.C. (2005). Joint congestion control and media access control design for wireless ad hoc networks. In Proceedings of IEEE INFOCOM (pp. 2212–2222), March.
12.
Chiang, M. (2005). Balancing transport and physical layers in wireless multihop networks: Jointly optimal congestion control and power control. IEEE Journal of Selected Areas on Communications, 23, 104–116.CrossRef
13.
Cruz, R., & Santhanam, A. (2003). Optimal routing, link scheduling and power control in multi-hop wireless networks. In IEEE infocom (pp. 702–711), March.
14.
Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematicas, 17, 449–467.MATHMathSciNet
15.
ElBatt, T., & Ephremides, A. (2004). Joint scheduling and power control for wireless ad-hoc networks. IEEE Transactions on Wireless Communications, 3(1), 74–85.CrossRef
16.
Fang, Z., & Bensaou, B. (2004). Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks. In IEEE infocom (pp. 1284–1295).
17.
Gronkvist, J., & Hansson, A. (2001). Comparison between graph-based and interference-BAsed STDMA scheduling. In MobiHoc.
18.
Grotschel, M., Lovasz, L., & Schrijver, A. (1993). Geometric algorithms and combinatorial optimization. Berlin: Springer.
19.
Halldórsson, M. M., (2004). Approximations of independent sets in graphs. In Approximation algorithms for combinatiorial optimization (pp. 24–45). Berlin/Heidelberg: Springer.
20.
Hastad, J. (1996). Clique is hard to approximate within n 1-ε. In Proceedings of the 37th annual Symposium on foundations of computer science (pp. 627–636).
21.
Jain, K., Padhye, J., Padmanabhan, V., & Qiu, L. (2003). Impact of interference on multi-hop wireless network performance. In Proceedings of ACM MobiCom (pp. 66–80). San Diego, CA, September.
22.
Jung, E.S., & Vaidya, N.H. (2002). A power control MAC protocol for ad hoc networks. In ACM MobiCom (pp. 36–47).
23.
Kako, A., One, T., Hirata, T., & Halldorsson, M. M. (2005). Approximation algorithms for the weighted independent set problem. In Proc. of graph-theoretic concepts in computer science, 31st international workshop, WG 2005, June 2005, pp. 341–350. Available at: http://​www.​hi.​is/​~mmh/​papers/​WIS_​WG.​pdf.
24.
Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller, & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum Press.
25.
Kashyap, A., Sengupta, S., Bhatia, R., & Kodialam, M. (2007). Two-phase routing, scheduling and power control for wireless mesh networks with variable traffic. In SIGMETRIC (pp. 85–96).
26.
Kawadia V., & Kumar, P. R. (2003). Power control and clustering in ad hoc networks. In IEEE infocom (pp. 459–469).
27.
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.MATH
28.
Kelly, F. P. (1997). Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8, 33–37.CrossRef
29.
Kim, D. (1999). Rate-regulated power control for supporting flexible transmission in future CDMA mobile networks. IEEE Journal of Selected Areas Communications, 17(5), 968–977.CrossRef
30.
Kim, S. W., & Lee, Y. H. (2000). Combined rate and power adaptation in DS/CDMA communications over nakagami fading channels. IEEE Transactions on Communications, 48(1), 162–168.CrossRef
31.
Kutner, M. H., Neter, J., Nachtsheim, C., Nachtsheim, C. J., & Neter, J. (2004). Applied linear regression models (4th ed.). New York: McGraw-Hill.
32.
Lin, X., & Shroff, N. B. (2006). The impact of imperfect scheduling on cross-layer congestion control in wireless networks. IEEE/ACM Transactions on Networking, 14(2), 302–315.CrossRef
33.
Low, S. H. (2003). A duality model of TCP and queue management algorithms. IEEE/ACM Transactions on Networking, 11, 525–536.CrossRef
34.
Matsui, T. (1998). Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In JCDCG (pp. 194–200).
35.
Minty, G. (1980). On maximal independent sets of vertices in claw-free graphs. Journal of Combinatorial Theory, B(28), 284–304.CrossRefMathSciNet
36.
Mo, J., & Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking, 8(5), 556–567.CrossRef
37.
Muqattash, A., & Krunz, M. (2005). POWMAC: A single-channel power-control protocol for throughput enhancement in wireless ad hoc networks. IEEE Journal on Selected Areas in Communications, 23(5), 1067–1084.CrossRef
38.
Narayanaswamy, S., Kawadia, V., Sreenivas, R. S., & Kumar, P. R. (2002). Power control in ad hoc networks: Theory, architecture, algorithm, and implementation of the COMPOW protocol. In European Wireless Conference (pp. 156–162).
39.
Nocedal, J., & Wright, S., (2000). Numerical optimization. Berlin: Springer.
40.
Radunovic B., & Boudec, J.-Y. L. (2004). When power adaptation is useless or harmful. EPFL, Tech. Rep. IC/2004/60.
41.
Sakai, S., Togasaki, M., & Yamazaki, K. (2003). A note on greedy algorithms for the maximum weighted independent set problem. Discrete Applied Mathematics, 126, 313–322.MATHCrossRefMathSciNet
42.
Sridhara, V., & Bohacek, S. (2007). Realistic propagation simulation of urban mesh networks. The International Journal of Computer and Telecommunications Networking Computer Networks and ISDN Systems (COMNET), 51(12), 3392–3412.MATH
43.
Subramanian, A., & Sayed, A. H. (2005). Joint rate and power control algorithms for wireless networks. IEEE Transactions on Signal Process, 53(11), 4204–4214.CrossRefMathSciNet
44.
Valiente, G. (2003). A new simple algorithm for the maximum-weight independent set problem on circle graphs (Vol. 2906, pp. 129–137). Berlin: Springer.
45.
Wang B., & Mutka, M. (2008). QoS-aware fair rate allocation in wireless mesh networks. Computer Communications, 31, 1276–1289.CrossRef
46.
47.
Wang, P., & Bohacek, S. (2008). Communication models for capacity optimization in mesh networks. In ACM PE-WASUN 2008, Vancouver, Canada.
48.
Wang, P., & Bohacek, S. (2008). On the practical complexity of solving the maximum weighted independent set problem for optimal scheduling in wireless networks. In WICON.
49.
50.
Wu, C. C., & Bertsekas, D. P. (2001). Distributed power control algorithms for wireless networks. IEEE Transactions on Vehicular Technology, 50, 504–514.CrossRef
51.
Xiao, M., Shroff, N. B., Chong, E. K. P. (2003). A utility-based power-control scheme in wireless cellular systems. IEEE/ACM Transactions on Networking, 11(2), 210–221.CrossRef
52.
Yates, R., & Huang, C. (1995). Integrated power control and base station assignment. IEEE Transactions on Vehicular Technology, 44, 638–644.CrossRef
Metadaten
Titel
Computational aspects of optimal schedules with power control and multiple bitrates selection in multihop wireless networks
verfasst von
Peng Wang
Stephan Bohacek
Publikationsdatum
01.08.2010
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 6/2010
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-009-0219-5

Weitere Artikel der Ausgabe 6/2010

Wireless Networks 6/2010 Zur Ausgabe

OriginalPaper

Addressing deafness and hidden terminal problem in directional antenna based wireless multi-hop networks

OriginalPaper

Creating templates to achieve low delay in multi-carrier frame-based wireless data systems

OriginalPaper

Utility-based power control with QoS support

OriginalPaper

Lower bounds on lifetime of ultra wide band wireless sensor networks

OriginalPaper

Location dependent key management in sensor networks without using deployment knowledge

OriginalPaper

A sustainable heuristic QoS routing algorithm for pervasive multi-layered satellite wireless networks

Neuer Inhalt

    Bildnachweise