Faculté des sciences

Information lookup and distribution in mobile ad hoc networks

Kummer, Raphaël ; Kropf, Peter (Dir.) ; Felber, Pascal (Codir.) ; Konstantas, Dimitri (Codir.) ; Olivera, Rui (Codir.)

Thèse de doctorat : Université de Neuchâtel, 2010.

Dans cette thèse, nous proposons deux nouveaux algorithmes: un algorithme de recherche pour table de hachage distribuée (DHT) et un algorithme construisant des arbres de multicast. Ces algorithmes ont été spécifiquement conçus pour tirer avantage des caractéristiques principales des réseaux mobiles ad-hoc (MANETs) telles que la communication par diffusion, les ressources limitées (en... Plus

Ajouter à la liste personnelle
    Résumé
    Dans cette thèse, nous proposons deux nouveaux algorithmes: un algorithme de recherche pour table de hachage distribuée (DHT) et un algorithme construisant des arbres de multicast. Ces algorithmes ont été spécifiquement conçus pour tirer avantage des caractéristiques principales des réseaux mobiles ad-hoc (MANETs) telles que la communication par diffusion, les ressources limitées (en particulier l'énergie), la proximité physique ou encore les communications nécessitant plusieurs sauts. Ces particularités ne sont généralement pas prises en compte ou considérées comme des facteurs limitatifs dans les solutions conçues pour la recherche et la distribution d'informations dans les MANETs. Notre algorithme de recherche pour DHT est adapté aux spécificités des MANETs. La proximité physique des noeuds, la communication par diffusion et le mécanisme de routage des messages sont utilisés pour trouver des raccourcis dans l'espace logique de la DHT. Ces raccourcis permettent une convergence rapide vers le noeud responsable pour les données recherchées (une clé dans l'espace logique.) L'algorithme de multicast fonctionne au-dessus de la DHT. Il construit des arbres de multicast dans les MANETs qui limitent le nombre de relais et de transmissions. La structure ainsi générée est ajustée à la topologie physique du réseau et s'adapte en continu lorsque les noeuds se déplacent. L'efficacité des algorithmes ainsi que leur capacité de passage à l'échelle ont été évaluées au moyen de simulations dans des réseaux de tailles et de configurations diverses. Finalement, nous présentons Adcast, le logiciel où sont implémentés nos algorithmes. Il s'exécute sur des PDAs fonctionnant sous Windows Mobile et des ordinateurs sous Windows. Adcast a rendu possible des tests dans des environnements réseaux ad hoc réels et simulés.
    Summary
    In this thesis, we propose two novel algorithms, a lightweight distributed hash table (DHT) lookup algorithm and a multicast tree building algorithm, specifically designed to take advantages of the major characteristics of mobile ad-hoc networks (MANETs) like broadcast communication, limited resources (particularly energy) physical proximity or multi-hop communication that are often put aside or considered as restrictive factors in proposed information lookup and distribution solutions. Our DHT lookup algorithm is adapted to MANETs specificities. The physical proximity of nodes, the broadcast communication and the message relaying process used to route the messages are exploited to find shortcuts in the DHT logical space. These shortcuts are then used to quickly converge to the node responsible for the searched data (i.e., key in the logical space). The multicast tree building algorithm operates on top of the lightweight DHT. It builds efficient multicast trees in MANETs that strives to limit the number of relay nodes and the number of required transmissions. The so build content distribution structure fits the physical network topology and adapts when node are moving. The algorithmic efficiency and scalability are evaluated by the means of simulations with various network sizes and configurations. The obtained results demonstrate that both algorithms behave well in MANETs. Finally, we detail the Adcast software implementing our both algorithms. It runs on Windows mobile powered PDAs and Windows computers. Adcast allows to evaluate the algorithms in real and simulated ad-hoc networks.