Algorithms and performance evaluation methods for wireless networks

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Penttinen, Aleksi
dc.date.accessioned 2012-02-17T07:59:11Z
dc.date.available 2012-02-17T07:59:11Z
dc.date.issued 2006-09-29
dc.identifier.isbn 951-22-8331-X
dc.identifier.issn 1458-0322
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/2748
dc.description.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. en
dc.description.abstract 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. fi
dc.format.extent 74, [70]
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Helsinki University of Technology en
dc.publisher Teknillinen korkeakoulu fi
dc.relation.ispartofseries Report / Helsinki University of Technology, Networking Laboratory en
dc.relation.ispartofseries 5/2006 en
dc.relation.haspart 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.
dc.relation.haspart 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.
dc.relation.haspart 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.
dc.relation.haspart 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.
dc.relation.haspart 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.
dc.relation.haspart 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.
dc.relation.haspart 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.
dc.relation.haspart 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.
dc.subject.other Electrical engineering en
dc.title Algorithms and performance evaluation methods for wireless networks en
dc.title Algoritmeja ja suorituskykyarvioinnin menetelmiä langattomille verkoille fi
dc.type G5 Artikkeliväitöskirja fi
dc.description.version reviewed en
dc.contributor.department Department of Electrical and Communications Engineering en
dc.contributor.department Sähkö- ja tietoliikennetekniikan osasto fi
dc.subject.keyword wireless communication networks en
dc.subject.keyword ad hoc networks en
dc.subject.keyword multicast routing en
dc.subject.keyword link scheduling en
dc.subject.keyword elastic traffic en
dc.subject.keyword performance en
dc.subject.keyword balanced fairness en
dc.subject.keyword langattomat tietoverkot fi
dc.subject.keyword ad hoc -verkot fi
dc.subject.keyword ryhmälähetysten reititys fi
dc.subject.keyword lähetysvuoronjako fi
dc.subject.keyword elastinen liikenne fi
dc.subject.keyword suorituskyky fi
dc.subject.keyword tasapainotettu reiluus (balanced fairness) fi
dc.identifier.urn urn:nbn:fi:tkk-008136
dc.type.dcmitype text en
dc.programme.major Teletraffic theory en
dc.programme.major Teleliikenneteoria fi
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.type.ontasot Doctoral dissertation (article-based) en
dc.contributor.supervisor Virtamo, Jorma; Prof.
dc.opn Borst, Sem; Prof.
dc.contributor.lab Networking Laboratory en
dc.contributor.lab Tietoverkkolaboratorio fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account