**Funding**

**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.

- One objective of the proposed study is to extend the optimization of the routing algorithms to the dynamic setting where both the traffic needs of the nodes as well as their locations change. The problem will be approached within the framework of the theory of Markov decision processes (MDP's). The MDP theory has been successfully applied in many infinite time horizon optimization problems in telecommunications, including optimal routing problems [7], admission control [8], and load balancing [9]. Finding an appropriate Markovian model for the mobility aspect of the network, however, poses a challenge to be addressed in the project.
- Another objective is to study the capacity of ad hoc networks and how this is related to the characteristics of the traffic demands (such as locality properties of the demands) and the network architecture. Particular attention will be given to the trade-off between the capacity and the reliability or robustness of the network, expressed in terms of its degree of connectivity, i.e. how many separate, node disjoint paths exist between the sending node and the recipient node. Methods and results of stochastic geometry [4], [5] will be exploited to the greatest extent. A sub-problem in this context is the power control the nodes, i.e. the question of determining the transmission ranges in such a way that the desired connectivity is obtained but that non-communicating nodes interfere with each other as little as possible. The capacity of an ad hoc network may be increased by a hierarchical network architecture, when appropriate. Architectures of this kind and their optimization will be a further topic of research.

[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 ] |