Algorithms and performance evaluation methods for wireless networks
Aleksi Penttinen · Aaltodoc (Aalto University) · 2006
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.