nach oben

vorheriger Artikel Cross-layer speculative architecture for end sy...

nächster Artikel A sustainable heuristic QoS routing algorithm f...

Tipp

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

Zeitschrift:: Wireless Networks > Ausgabe 6/2010

Autoren:: Peng Wang, Stephan Bohacek

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.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Jetzt einloggen Kostenlos registrieren

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Alekseev, V. E., & Lozin, V. V. (2000). Augmenting graphs for independent sets. Rutgers Center of Operations Research, Tech. Rep. 59-2000.

Arikan, E. (1984). Some complexity results about packet radio networks. IEEE Transactions on Information Theory, 30, 681– 685. MATHCrossRefMathSciNet

Bertsekas, D. P. (2003). Nonlinear programming. Belmont, MA: Athena Scientific.

Bohacek, S., Sridhara, V., & Kim, J. UDel models. Available at: http://www.udelmodels.eecis.udel.edu/.

Bohacek, S., & Wang, P. (2007). Toward tractable computation of the capacity of multihop wireless networks. In IEEE infocom (pp. 2099–2107).

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).

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).

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

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.

Wang, P. (2009). Throughput optimization of urban wireless mesh networks. Ph.D. dissertation, University of Delaware, available at: http://www.udelmodels.eecis.udel.edu.

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.

Wang, P., & Bohacek, S. (2007). Practical computation of optimal schedules in multihop wireless networks. submitted 2007, available at http://www.udelmodels.eecis.udel.edu.

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

Titel: Computational aspects of optimal schedules with power control and multiple bitrates selection in multihop wireless networks
Autoren:: Peng Wang
Stephan Bohacek
Publikationsdatum: 01.08.2010
DOI: https://doi.org/10.1007/s11276-009-0219-5
Verlag: Springer US
Zeitschrift: Wireless Networks The Journal of Mobile Communication, Computation and Information
Ausgabe 6/2010
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196

Springer Professional

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Abstract

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 6/2010

Optimal scheduling for dynamic channel allocation in wireless LANs

Location dependent key management in sensor networks without using deployment knowledge

A context-constrained authorisation (CoCoA) framework for pervasive grid computing

Real-time detection of traffic anomalies in wireless mesh networks

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

A novel learning based solution for efficient data transport in heterogeneous wireless networks