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

Performance Studies of Wireless Multihop Networks

Henri Koskinen

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 12th of May, 2006, at 12 o'clock noon.

Overview in PDF format (ISBN 951-22-8137-6)   [988 KB]
Dissertation is also available in print (ISBN 951-22-8136-8)

Abstract

Wireless multihop networks represent a fundamental step in the evolution of wireless communications, a step that has proven challenging. Such networks give rise to a wide range of novel performance and design problems, most of which are of a geometric nature. This dissertation addresses a selection of such problems.

The first part of this thesis presents studies in which the network nodes are assumed to receive signals sufficiently clearly only from within some fixed range of operation. Using this simple model, the first two problems addressed are to predict the probabilities that a network with randomly placed nodes is connected or completely covers a given target domain, respectively. These problems are equivalent to determining the probability distribution of the minimal range providing connectivity or coverage. Algorithms for determining these threshold ranges for a given set of network nodes are developed. Because of the complex nature of these problems in finite settings, they are both approached by empirically modeling the convergence of these distributions to their known asymptotic limits. Next, a novel optimization problem is presented, in which the task is to make a given disconnected network into a connected one by adding a minimal number of additional nodes to the network, and heuristic algorithms are proposed for this problem.

In the second part, these networks are studied in the context of a more realistic model in which the condition for successful communication between network nodes is expressed as an explicit minimum value for the received signal-to-noise-and-interference ratio. The notion of the threshold range for connectivity is first generalized to this network model. Because connectivity is now affected by medium access control (MAC), two alternative MAC schemes are considered. Finally, an infinite random network employing slotted Aloha is studied under this model. Since the probability of successful reception in a random time slot is a function of the locations of other nodes, this temporal probability is a random variable with its own probability distribution over different node configurations. Numerical approximations for evaluating both the mean and the tail probability of this distribution are developed. The accuracy of these approximations can be improved indefinitely, at the cost of numerical computations.

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

  1. Henri Koskinen. A simulation-based method for predicting connectivity in wireless multihop networks. Telecommunication Systems, 26 (2-4), pages 321-338, June 2004.
  2. Henri Koskinen. Quantile models for the threshold range for k-connectivity. In: Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems (MSWiM '04), pages 1-7, October 2004. ACM Press, New York, NY, USA. © 2004 Association for Computing Machinery (ACM). By permission.
  3. Pasi Lassila, Esa Hyytiä, and Henri Koskinen. Connectivity properties of Random Waypoint mobility model for ad hoc networks. In: Proceedings of the Fourth Annual Mediterranean Workshop on Ad Hoc Networks (Med-Hoc-Net), 10 pages, June 2005, printed proceedings to appear. © 2005 Springer Science+Business Media. By permission.
  4. Henri Koskinen. On the coverage of a random sensor network in a bounded domain. In: Proceedings of the 16th ITC Specialist Seminar, pages 11-18, August 2004. © 2004 by author.
  5. Henri Koskinen, Jouni Karvo, and Olli Apilo. On improving connectivity of static ad-hoc networks by adding nodes. In: Proceedings of the Fourth Annual Mediterranean Workshop on Ad Hoc Networks (Med-Hoc-Net), 10 pages, June 2005, printed proceedings to appear. © 2005 Springer Science+Business Media. By permission.
  6. Henri Koskinen. Generalization of critical transmission range for connectivity to wireless multihop network models including interference. In: Proceedings of the Third IASTED International Conference on Communications and Computer Networks (CCN 2005), pages 88-93, October 2005. © 2005 by author.
  7. Henri Koskinen and Jorma Virtamo. Probability of successful transmission in a random slotted-Aloha wireless multihop network employing constant transmission power. In: Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems (MSWiM '05), pages 191-199, October 2005. ACM Press, New York, NY, USA. © 2005 Association for Computing Machinery (ACM). By permission.

Errata of publication 7

Keywords: wireless multihop networks, ad hoc networks, sensor networks, connectivity, coverage, throughput, geometric random graphs, stochastic geometry

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