Algorithms and performance evaluation methods for wireless networks

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
2006-09-29
Major/Subject
Teletraffic theory
Teleliikenneteoria
Mcode
Degree programme
Language
en
Pages
74, [70]
Series
Report / Helsinki University of Technology, Networking Laboratory, 5/2006
Abstract
The performance of wireless networks depends fundamentally on the characteristics of the radio resource. In this thesis we study methods that can be used to improve performance of wireless networks. We also study methods that can be used to analyze the performance of such networks. In the first part of the thesis, we propose algorithms for multicast routing and max-min fair link scheduling in wireless multihop networks. The multicast routing problem is to find a minimum-cost sequence of transmissions which delivers a message from a given source node to a set of destination nodes. We propose three efficient multicast routing algorithms for certain common instances of the problem. The first algorithm assumes fixed transmission costs and constructs an efficient multicast tree in a centralized fashion. The second algorithm can be used to minimize only the number of transmissions in the multicast tree, but it has a distributed implementation. The last algorithm is applicable in scenarios where the network nodes can control their transmission range and the objective is to minimize the power consumption of the multicast tree. In the max-min fair link scheduling problem one attempts to assign transmission rights to flows in a wireless multihop network so that the long-term flow rates become max-min fair. We present a low-complexity, low-overhead distributed algorithm for the problem. The second part comprises of the flow-level performance analysis of elastic data traffic in wireless networks. The network is modeled in a dynamic setting, in which flows (e.g., file transfers) arrive stochastically and depart upon completion. We discuss how a recently introduced resource allocation concept, balanced fairness, can be applied to wireless networks and devise an efficient computational scheme for solving the resulting joint problem of scheduling and resource allocation. Additionally, we propose an alternative method to approximate the flow throughput under balanced fairness in arbitrary networks. Finally, we adapt balanced fairness to a model where flows are indexed by a continuous variable. The model can capture, e.g., location-dependent features of flows.

Langattomien verkkojen suorituskyky riippuu olennaisesti radiokanavan ominaisuuksista. Tässä väitöskirjassa tutkitaan menetelmiä, joilla verkkojen suorituskykyä pystytään parantamaan. Toisaalta tutkitaan myös menetelmiä, jotka mahdollistavat verkkojen suorituskyvyn analysoimisen. Väitöskirjan ensimmäisessä osassa esitetään algoritmeja ryhmälähetysten reititykseen ja max-min-reiluun linkkien vuoronjakoon langattomissa monihyppyisissä verkoissa. Ryhmälähetysten reititysongelmassa etsitään joukkoa perättäisiä lähetyksiä, jotka välittävät viestin lähettäjältä joukolle vastaanottajia siten, että lähetyskustannusten summa minimoituu. Esitämme kolme tehokasta reititysalgoritmia tiettyihin ryhmälähetysongelman erikoistapauksiin. Ensimmäisessä algoritmissa oletamme lähetyskustannusten olevan mielivaltaiset, joskin kiinnitetyt, ja pyrimme keskitetysti minimoimaan lähetyspuun kokonaiskustannusta. Toinen algoritmi soveltuu pääasiassa lähetysten lukumäärän minimoimiseen, mutta se voidaan toteuttaa hajautetusti. Kolmas algoritmi on sovellettavissa tilanteissa, joissa verkon solmut voivat säätää lähetyssädettään ja tavoitteena on minimoida lähetyspuun tehonkulutus. Max-min-reilussa linkkien vuoronjako-ongelmassa pyritään jakamaan lähetysvuoroja verkossa oleville voille siten, että voiden pitkän aikavälin siirtonopeudet toteuttavat kyseisen reiluuskriteerin. Esitämme vähän kontrolliliikennettä vaativan, hajautetun algoritmin ongelman ratkaisemiseksi. Väitöskirjan toinen osa koostuu ns. elastisen dataliikenteen vuotason suorituskykyanalyysistä langattomissa verkoissa. Verkko on mallinnettu dynaamisessa tilassa, missä voita (esim. tiedostonsiirtoja) saapuu verkkoon satunnaisen prosessin mukaisesti ja ne poistuvat verkosta siirron päättyessä. Käsittelemme kuinka vastikään kehitetty resurssienjakomenetelmä, tasapainotettu reiluus (balanced fairness), voidaan mukauttaa langattomiin verkkoihin ja kehitämme tehokkaan laskennallisen menetelmän mukautuksen vaatimaan lähetysvuoronjaon ja resurssienjaon yhteisoptimointiin. Tämän lisäksi esitämme vaihtoehtoisen tavan approksimoida voiden läpäisyä mielivaltaisissa verkossa tasapainotetun reiluuden mukaisen resurssienjaon voimassaollessa. Lopuksi sovellamme tasapainotetun reiluuden konseptia mallissa, jossa vuot on indeksoitu jatkuvalla muuttujalla. Tämä malli mahdollistaa esimerkiksi voiden paikkariippuvien ominaisuuksien mallintamisen.
Description
Supervising professor
Virtamo, Jorma; Prof.
Keywords
wireless communication networks, ad hoc networks, multicast routing, link scheduling, elastic traffic, performance, balanced fairness, langattomat tietoverkot, ad hoc -verkot, ryhmälähetysten reititys, lähetysvuoronjako, elastinen liikenne, suorituskyky, tasapainotettu reiluus (balanced fairness)
Other note
Parts
  • Aleksi Penttinen. Minimum cost multicast trees in ad hoc networks. In Proceedings of the 2006 IEEE International Conference on Communications (ICC 2006), June 2006. 6 pages. [article1.pdf] © 2006 IEEE. By permission.
  • Aleksi Penttinen. Efficient multicast tree algorithm for ad hoc networks. In Proceedings of the 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2004), pages 519-521, October 2004. [article2.pdf] © 2004 IEEE. By permission.
  • Aleksi Penttinen and Jorma Virtamo. Improving multicast tree construction in static ad hoc networks. In Proceedings of the 28th Annual IEEE Conference on Local Computer Networks (LCN 2003), pages 762-765, October 2003. [article3.pdf] © 2003 IEEE. By permission.
  • Aleksi Penttinen, Iordanis Koutsopoulos, and Leandros Tassiulas. Low-complexity distributed fair scheduling for wireless multi-hop networks. In Proceedings of the 1st Workshop on Resource Allocation in Wireless Networks (RAWNET 2005), April 2005. 6 pages. [article4.pdf] © 2005 by authors.
  • Aleksi Penttinen and Jorma Virtamo. Performance of wireless ad hoc networks under balanced fairness. In Proceedings of Networking 2004, pages 235-246, May 2004. [article5.pdf] © 2004 Springer Science+Business Media. By permission.
  • Aleksi Penttinen, Jorma Virtamo, and Riku Jäntti. Performance analysis in multi-hop radio networks with balanced fair resource sharing. Telecommunication Systems, 31: 315-336, 2006. [article6.pdf] © 2006 Springer Science+Business Media. By permission.
  • Juha Leino, Aleksi Penttinen, and Jorma Virtamo. Flow level performance analysis of wireless data networks: A case study. In Proceedings of the 2006 IEEE International Conference on Communications (ICC 2006), June 2006. 6 pages. [article7.pdf] © 2006 IEEE. By permission.
  • Thomas Bonald, Aleksi Penttinen, and Jorma Virtamo. On light and heavy traffic approximations of balanced fairness. In Proceedings of ACM SIGMETRICS/Performance 2006, pages 109-120, June 2006.
Citation
Permanent link to this item
https://urn.fi/urn:nbn:fi:tkk-008136