The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Algorithms and Performance Evaluation Methods for Wireless Networks

Aleksi Penttinen

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Department of Electrical and Communications Engineering for public examination and debate in Auditorium S4 at Helsinki University of Technology (Espoo, Finland) on the 29th of September, 2006, at 12 o'clock noon.

Overview in PDF format (ISBN 951-22-8331-X)   [928 KB]
Dissertation is also available in print (ISBN 951-22-8329-8)

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.

This thesis consists of an overview and of the following 8 publications:

  1. 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. © 2006 IEEE. By permission.
  2. 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. © 2004 IEEE. By permission.
  3. 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. © 2003 IEEE. By permission.
  4. 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. © 2005 by authors.
  5. Aleksi Penttinen and Jorma Virtamo. Performance of wireless ad hoc networks under balanced fairness. In Proceedings of Networking 2004, pages 235-246, May 2004. © 2004 Springer Science+Business Media. By permission.
  6. 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. © 2006 Springer Science+Business Media. By permission.
  7. 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. © 2006 IEEE. By permission.
  8. 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.

Keywords: wireless communication networks, ad hoc networks, multicast routing, link scheduling, elastic traffic, performance, balanced fairness

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2006 Helsinki University of Technology

Last update 2011-05-26