NAPS — Subproject Algorithmics

The project works on fundamental topology control and routing problems in ad hoc networks, using tools from modern algorithmics. The project is part of the Networking and Architecture in Proactive Systems (NAPS, 2003–2005) consortium.

Background

Modern algorithmics has developed a sophisticated set of tools for tasks such as approximate solution of hard combinatorial optimization problems, efficient computation of network flows and other digraph characteristics, speeding up algorithms by randomization, and the design and analysis of computational methods in an “online” setting where the input stream unfolds as the computation proceeds.

While traditional sequential algorithm design is already a rather mature discipline, the novel requirements of the proactive environment – especially in systems such as mobile ad hoc networks – place heavy emphasis on many design parameters that have only recently begun to be addressed in the literature. Firstly, the computation and communication substrata change in this setting from the traditional centralized, stable, and reliable models to being distributed, mobile, and susceptible to faults. Secondly, new system design objectives and constraints arise from the properties of the participating nodes, when e.g. their mobility, or the limitations on their battery life and signal strength need to be taken into account. In addition to the response time and throughput of a system one now needs to consider also its fault-tolerance, energy-intensity and signal-locality characteristics. Furthermore, the computation nodes may be noncollaborative and distrustful of each other.

Research

Some research topics are:

• Topology control to maximize network lifetime

  By increasing the transmission power of the nodes, more nodes can be reached within one hop. On the other hand, this increase will imply that more energy is used and the time until the buttery runs out of power will be shorter. The question we have studied is how to dynamically adjust the transmission powers, in order to keep the network fully connected as long as possible.

• Node placement in sensor networks

  Sensor networks may be used, for instance in environmental applications to send measured data to processing nodes (data gathering). The research question is how to place the relaying and destination nodes optimally, taking into account the limited energy supply at the sensor and relaying nodes.

• Clustering for hierarchical networks

  In order to have a more practical management structure, the ad hoc network can be divided into smaller subnetworks, clusters, that can be efficiently controlled. The research problem is how to perform the clustering so as to optimize the workings for the network, also taking mobility into account.

Teaching

The following seminar was undertaken at the Department of Computer Science, University of Helsinki: Algorithms for ad hoc networking, autumn 2003.

The following course and seminar were undertaken at the TCS lab of Helsinki University of Technology: Algorithmics of Sensor Networks, spring 2005; Distributed Algorithms, autumn 2002.

People

The research groups at the Basic Research Unit (BRU) of the Helsinki Institute for Information Technology HIIT (Floréen) and the Laboratory for Theoretical Computer Science at the Helsinki University of Technology (Orponen) will work collaboratively on the topics of the project, thus effectively forming a single group spanning two universities.

At HIIT/BRU:

• Doc. Patrik Floréen (group leader)
• Researcher Jukka Kohonen
• Researcher Jukka Suomela
• Researcher Petteri Nurmi

At HUT/Lab. TCS:

• Prof. Pekka Orponen (group leader)
• Researcher Heikki Haanpää
• Researcher Petteri Kaski
• Researcher Antti Autere

Publications

Topology control:

• P. Floréen, P. Kaski, J. Kohonen and P. Orponen, “Multicast time maximization in energy constrained wireless networks.” Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing (DIALM-POMC 2003, San Diego, Calif., September 2003) at MobiCom 2003, ACM, 2003, 50–58.
• P. Kaski, “Packing Steiner trees with identical terminal sets.” Information Processing Letters 91, 1 (July 2004), 1–5.
• P. Floréen, P. Kaski, J. Kohonen and P. Orponen, “Lifetime maximization for multicasting in energy-constrained wireless networks.” IEEE Journal on Selected Areas in Communications 23(2005)1(Jan), 117–126, IEEE, 2005.

Clustering:

• S. E. Virtanen and P. Nikander, “Local clustering for hierarchical ad hoc networks.” Proc. Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt 2004, Cambridge, UK, March 2004), IEEE, 2004, 404–405.

Routing and data gathering:

• E. Falck, P. Floréen, P. Kaski, J. Kohonen and P. Orponen, “Balanced data gathering in energy-constrained sensor networks.” Proc. 1st Intl. Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors 2004, Turku, Finland, July 2004). Lecture Notes in Computer Science 3121. Springer-Verlag, Berlin, 2004, 59–70.
• P. Nurmi, “Modelling routing in wireless ad hoc networks with dynamic Bayesian games.” Proc. 1st IEEE Intl. Conference on Sensor and Ad Hoc Communications and Networks (IEEE SECON, Santa Clara, Calif., Oct 2004), IEEE, 2004, 63–70.
• A. Autere, “New online power-aware algorithms in wireless networks.” Proc. 12th International Conference on Software, Telecommunications and Computer Networks (SoftCOM 2004, Split, Dubrovnik, Venice, Oct 2004), 439–443.
• J. Kohonen, “Data gathering in sensor networks.” Proactive Computing Workshop (PROW 2004, Helsinki, Nov 2004), Helsinki University Press, 2004, 32–36.
• P. Floréen, P. Kaski, J. Kohonen and P. Orponen, “Exact and approximate balanced data gathering in energy-constrained sensor networks.” Theoretical Computer Science 344 (2005), 30–46.
• J. Suomela, “Computational complexity of relay placement in sensor networks.” Proc. 32nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2006, Měřín, Czech Republic, Jan 2006). Lecture Notes in Computer Science 3831. Springer-Verlag, Berlin, 2006, 521–529.
• J. Suomela, “Approximating relay placement in sensor networks.” Proc. 3rd ACM International Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN, Torremolinos, Spain, October 2006). ACM Press, New York, NY, 2006, 145–148.