NAPS - site visit 2

Site visit in Espoo on 13 February 2004

The aim of the project is to develop fundamental networking infrastructure techniques and architecture to address problems arising in networks with a large number of intercommunicating devices (nodes), which in most of the purported applications will be mobile, energy-constrained, and prone to unexpected malfunctions.  The project consists of two subprojects: Algorithmics and Traffic Management.

The Algorithmics subproject has studied local clustering of hierarchic ad hoc net works (presentation by Satu Virtanen). Traffic routing with mobile nodes might be difficult. By local clustering, based on, e.g., the physical location of the nodes, the routing may be implemented differently within clusters and between clusters of nodes. Clustering adds some traffic to the network but routing may be simpler. In this study, a cluster is formed by nodes that are highly interconnected but as independent as possible from other clusters. The research group believes that distributed clustering can be performed effectively when the nodes make reasonable guesses of which cluster to join, based on some local information (who is the leader node, what is the number of nodes in the cluster, how well are the nodes in the cluster connected, how many connection goes outside the cluster). An open problem is to compute (exactly or approximately) how good such local clustering is.

In addition, the Algorithmics subproject has also looked into data gathering from balanced, energy-constrained sensor networks (presentation by Emil Falck). In the balanced data gathering model, the aim is to maximise the total amount of data received from the sensor network during its lifetime while requiring a sufficient coverage for all sensor locations. Furthermore, the group has  studied the effect of augmenting the network with a small number of auxiliary relay nodes with less stringent energy constraints. The subproject has also continued its work on maximising multicast time in energy-constrained wireless networks.

The Traffic Management subproject has continued to look into connectivity and coverage problems in ad hoc networks (presentation by Henri Koskinen). The area coverage of a sensor network is defined as the fraction of a given target area that is within the sensing range of one or more sensors. Assuming that the sensors are uniformly scattered over a bounded domain, the problem is to find out the distribution of the area coverage given a certain sensing range (for all sensors) and sensor density. The results show that only asymptotic analytical results exist but both connectivity and full coverage can be predicted using statistical models.

The group has also looked into the spatial distribution of nodes moving according to the Random Way Point (RWP) mobility model. In the RWP model, a node moves at constant speed in a zigzag path within a specified area. Each turning point is called a way point. At each way point, the node chooses a new destination way point randomly. The problem is to find the expression for the stationary distribution of the location of the node. The results help researchers to better understand the impact of mobility on node location distribution, e.g., in ad hoc networks.

 A third problem studied by the group is how to achieve full connectivity in an ad hoc network by adding nodes. Starting with a network where only some nodes are connected (forming unconnected clusters); we want to achieve connectivity or two-way connectivity throughout the network by adding as few connecting nodes as possible. An application example is an ad hoc network in some catastrophe area where data communication for the rescuers is necessary everywhere. One solution is to form the minimal spanning tree between the clusters of connected nodes. Nodes are added on the edges of the spanning tree, but the solution does not seem to be optimal, as in some cases nodes could be added in different locations to connect several clusters at a time. Another heuristic is to use Voronoi diagrams to represent the range of the nodes and add new nodes in the corners of the diagrams. In some tests, this heuristics reduces the number of added nodes with 30% compared with the minimal spanning tree heuristic.

For more information, please see the web pages of the project at http://www.cs.helsinki.fi/hiit_bru/projects/naps/and at this site. 

Some recent publications by the project:

• Floréen, Kaski, Kohonen, and Orponen: Multicast time maximization in energy constrained wireless networks. Proc. DIALM-POMC Joint Workshop on Foundations of Mobile Computing (MobiCom 2003).
• Floréen, Kaski, Kohonen, Orponen: Lifetime maximization in energy-constrained wireless networks. Submitted for publication.
• Kaski: Packing Steiner trees with identical terminal sets. Submitted for publication.
• Falck, Floréen, Kaski, Kohonen, and Orponen: Balanced data gathering in energy-constrained sensor networks. Submitted to conference.
• Virtanen, Nikander: Local clustering for hierarchical ad hoc networks. Accepted as poster to WiOpt04.
• H. Koskinen, Quantile models for the threshold range for k-connectivity, 2003, submitted for publication.
• H. Koskinen, On the coverage of a random sensor network in a bounded domain, 2003, submitted for publication.
• H. Koskinen, A simulation-based method for predicting connectivity in wireless multihop networks, 2003, to appear in Telecommunications Systems; special issue on wireless sensor networks.
• H. Koskinen, A simulation-based method for predicting connectivity in ad hoc networks, in Proceedings of INOC 2003, pp. 355-360, 2003.

In addition, the consortium has also organised some special courses on the themes of the project. Patrik Floréen held a seminar on Algorithms for ad hoc networking in the autumn of 2003 and Pekka Orponen is giving a seminar on algorithms and CS theory of sensor networks in the spring of 2005.

The consortium consists of the following units and researchers:

• Helsinki University of Technology, Networking Laboratory:
• Professor Jorma Virtamo, researchers Dr. Pasi Lassila, Jouni Karvo, Henri Koskinen, affiliated researchers Laura Nieminen, Aleksi Penttinen
• Helsinki University of Technology, Laboratory for Theoretical Computer Science:
• Professor Pekka Orponen, researchers Petteri Kaski, Emil Falck, Petteri Kaski, Satu Virtanen, affiliated researcher Antti Autere
• Helsinki Institute for Information Technology HIIT, Basic Research Unit:
• Senior Researcher Patrik Floréen, researchers Jukka Kohonen
• Affiliated research group: Helsinki University of Technology, Laboratory of Theoretical Computer Science: Professor Hannu Kari