Schlüsselwörter
(Englisch)
|
Evolving Graphs; Network Design; Routing Algorithms; Network Modelling; Complex Networks
|
Forschungsprogramme
(Englisch)
|
COST-Action 293 - Graphs and algorithms in communication networks
|
Kurzbeschreibung
(Englisch)
|
The emergence of new mobile and nomadic networking services demands the understanding and handling of complex communication networks in evolving environments. Their high dynamic behavior engenders new design and routing prob-lems under changing conditions in such networks.As a matter of fact, the variations in network topology arehard to be ef-fectively captured in a classical graph model. This naturally motivates the study on modelling and designing algorithms that take topology variations into account.This project aims at developping theoretical models and algorithms that capture the evolution of connections in dynamic networks. We plan to use the Evolving Graph model, which is a simple, computationnaly measurable, and efficient model: the formulation of problems related to network design or to the establishment of communications remains small within this model. That is not the case when considering other strong theoretic models such as time expanded graphs which usually involve a non measurable, or otherwise a huge input. We propose to study the complexity of routing problems such as distributed routing problems, energy aware routing problems, routing with finite prediction problems and error recovery routing problems. Network design issues arise also naturally even in networks that seem at first sight unorganized or randomly deployed. Such issues include local network optimization by moving, adding, altering the course or otherwise modifying one or several nodes in the network; global network optimization by assigning sleep phases in radio networks, organizing the nodes into hierarchical groups in mesh networks, and generally structuring communications into predefined patterns.
|
Weitere Hinweise und Angaben
(Englisch)
|
Full name of research-institution/enterprise: Université de Genève Faculté des Sciences, Département d'Informatique Battelle, Bât. A
|
Partner und Internationale Organisationen
(Englisch)
|
BE, CH, DE, DK, ES, FR, GR, HR, HU, IL, IT, NL, NO, PL, SE, SI, SK, UK
|
Abstract
(Englisch)
|
The emergence of new mobile and nomadic networking services demands the understanding and handling of complex communication networks in evolving environments. Their high dynamic behavior engenders new design and routing problems under changing conditions in such networks. As a matter of fact, the variations in network topology are hard to be effectively captured in a classical graph model. This naturally motivates the study on modelling and designing algorithms that take topology variations into account. This project aims at developping theoretical models and algorithms that capture the evolution of connections in dynamic networks. We plan to use the Evolving Graph model, which is a simple, computationnaly measurable, and efficient model: the formulation of problems related to network design or to the establishment of communications remains small within this model. That is not the case when considering other strong theoretic models such as time expanded graphs which usually involve a non measurable, or otherwise a huge input. We propose to study the complexity of routing problems such as distributed routing problems, energy aware routing problems, routing with finite prediction problems and error recovery routing problems. Network design issues arise also naturally even in networks that seem at first sight unorganized or randomly deployed. Such issues include local network optimization by moving, adding, altering the course or otherwise modifying one or several nodes in the network; global network optimization by assigning sleep phases in radio networks, organizing the nodes into hierarchical groups in mesh networks, and generally structuring communications into predefined patterns.
|
Datenbankreferenzen
(Englisch)
|
Swiss Database: COST-DB of the State Secretariat for Education and Research Hallwylstrasse 4 CH-3003 Berne, Switzerland Tel. +41 31 322 74 82 Swiss Project-Number: C06.0013
|
