NAPS - Networking and Architecture for Proactive Systems (NAPS) - Traffic management in ad hoc networks


Background

Funding

NAPS (Networking and Architecture for Proactive Systems) is a 3 year project (2003-2005) funded by the Academy of Finland. It is part of the research programme on Proactive Computing (PROACT). The research consortium of NAPS is coordinated by Helsinki Institute for Information Technology, Basic Reserch Unit, with subprojects at the Networking Laboratory (HUT) and the Laboratory for Theoretical Computer Science (HUT). NAPS consortium home page can be found here.

Motivation

Traffic management is an area where completely new problems arise in the setting of dynamically organized, wireless ad hoc networks. Two particular problems will be addressed in this sub-project, viz. the new type routing algorithms and capacity optimization problems.

The main task of a routing algorithm is to find a path across the network for delivering packets from the origin to the destination. Often a shortest path algorithm, such as the Dijkstra or Bellman-Ford algorithm, along with a simple path metric like hop count is used. A more complex situation arises when some additional optimization criteria are imposed. For instance, one may wish to minimize average delay of the packets or balance the load in the network, e.g., by minimizing the maximum link load.

In a battery powered ad hoc network, a new type of optimization objective is that of maximizing the life time of a set of connections in the network. These kinds of problems are increasingly receiving attention. The unicast case can be formulated as an LP problem. Also distributed algorithms have been proposed (e.g., Chang and Tassiulas, and Wieselthier et al. [1], [2]). Energy optimal routing of multicast traffic is even more difficult, and calls for solving minimum cost multicast trees, a generalization of the well-known Steiner tree problem in fixed networks. This problem has been addressed by the present research group. Until now a static traffic and network setting has been assumed, which may or may not be a realistic depending on the case.

Ad hoc networks are known to suffer from a low capacity per node with increasing number of nodes due to the amount of relay traffic that has to be carried [3]. This can be counteracted, when feasible, by hierarchical network architectures, assuming that at an upper hierarchy level there is a higher capacity transmission channel available which does not interfere with the lower level wireless transmissions (ultimately a wireline network).

A minimum requirement for an operational network is that it provides connectivity between the communicating nodes. Connectivity alone is an interesting problem when the locations of the nodes are random. These kinds of problems belong to the field of stochastic geometry [4], [5]; also the percolation problem in physics is closely related [6]. Often simple connectivity is not enough, but because of robustness requirements the degree of connectivity has to be higher.

Research objectives and methods

The following research topics are addressed in this subproject:

References

[1] J.-H. Chang and L. Tassiulas, Energy conserving routing in wireless ad-hoc networks, Proceedings of IEEE Infocom 2000, Tel Aviv, Vol. 3 (2000) pp. 22-31.

[2] J.E. Wieselthier, G.D. Nguyen, and A. Ephremides, On the construction of energy efficient broadcast and multicast trees in wireless networks, Proceedings of IEEE Infocom 2000, Tel Aviv, Vol. 2 (2000) pp. 585-594.

[3] P. Gupta and P.R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory, Vol. 46, No. 2 (2000) pp. 388-404.

[4] F. Baccelli, M. Klein, M. Lebourges, and S. Zuyev, Stochastic geometry and architecture of communication networks, J. Telecommunication Systems, Vol. 7 (1997) pp. 209-227.

[5] K. Tchoumatchenko, Modeling of communication networks using stochastic geometry, PhD thesis, University of Nice - Sophia Antipolis (1999).

[6] R. Meester and R. Roy, Continuum percolation, Cambridge University Press, Cambridge (1996).

[7] T.J Ott and K.R. Krishnan, Separable routing: A scheme for state-dependent routing in circuit switched telephone traffic, Annals of Operations Research, Vol. 35 (1992) pp. 43- 68.

[8] H. Rummukainen, J. Virtamo, Polynomial Cost approximations in Markov decision theory based call admission control, IEEE/ACM Transactions on Networking, Vol. 9, No. 6 (2001) pp. 769-779.

[9] J. van Leeuwaarden, S. Aalto, and J. Virtamo, Load balancing in cellular networks using first policy iteration, COST279 TD(02)23, May 2002.


Tietoverkkolaboratorio on nyt osa Tietoliikenne- ja tietoverkkotekniikan laitosta. Tällä sivulla oleva tieto voi olla vanhentunutta.

Tämän sivun sisällöstä vastaavat ja Webmaster.
Sivua on viimeksi päivitetty 29.01.2007 16:23.
URI: http://www.netlab.tkk.fi/tutkimus/naps/info.shtml
[ TKK > Sähkö- ja tietoliikennetekniikan osasto > Tietoverkkolaboratorio > Tutkimus ]