Prise en compte du mouvement dans les systèmes de ... · prise en compte. Nous verrons qu’elle dépasse le cadre des systèmes adaptatifs. Mots-clé : mobilité, communications

Prise en compte du mouvement dans les systemes de

communication sans-fil

Arnaud Troel, Frederic Weis, Michel Banatre

To cite this version:

Arnaud Troel, Frederic Weis, Michel Banatre. Prise en compte du mouvement dans les systemesde communication sans-fil. [Rapport de recherche] RR-4720, INRIA. 2003. <inria-00071866>

HAL Id: inria-00071866

https://hal.inria.fr/inria-00071866

Submitted on 23 May 2006

HAL is a multi-disciplinary open accessarchive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come fromteaching and research institutions in France orabroad, or from public or private research centers.

L’archive ouverte pluridisciplinaire HAL, estdestinee au depot et a la diffusion de documentsscientifiques de niveau recherche, publies ou non,emanant des etablissements d’enseignement et derecherche francais ou etrangers, des laboratoirespublics ou prives.

https://hal.archives-ouvertes.fr

https://hal.inria.fr/inria-00071866

ISS

N 0

249-

6399

ISR

N IN

RIA

/RR

--47

20--

FR ap por t

de r ech er ch e

INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUE

Prise en compte du mouvement dans lessystèmes de communication sans-fil

Arnaud Troël, Frédéric Weis, Michel Banâtre

N˚4720

Fevrier 2003

THÈME 1

Prise en compte du mouvement dans les systèmes decommunication sans-fil

Arnaud Troël, Frédéric Weis, Michel Banâtre�

Thème 1 — Réseaux et systèmesProjet ACES

Rapport de recherche n˚4720 — Fevrier 2003 — 46 pages

Résumé : Fruits des progrès de l’informatique embarquée et des technologies decommunication sans-fil, des terminaux d’un nouveau type sont récemment apparus.Disposant d’une capacité de calcul non négligeable, ils peuvent de plus échangerdes informations directement avec leurs pairs ou bien par le biais d’un réseau relais.

La portée de communication dont ils disposent étant limitée, le mouvement deces terminaux joue un rôle immédiat dans le fonctionnement de leurs échanges. Laprise en compte de cette mobilité apparaît alors comme une perspective intéressanteà développer lors de l’élaboration de systèmes mettant en œuvre ces terminaux.

L’objectif de ce document est d’examiner et de classifier les différentes tech-niques employées afin de permettre aux systèmes informatiques d’effectuer cetteprise en compte. Nous verrons qu’elle dépasse le cadre des systèmes adaptatifs.

Mots-clé : mobilité, communications sans-fil, ubiquité numérique

(Abstract: pto)

�

{Arnaud.Troel, Frederic.Weis, Michel.Banatre}@irisa.fr

Unité de recherche INRIA RennesIRISA, Campus universitaire de Beaulieu, 35042 RENNES Cedex (France)

Téléphone : 02 99 84 71 00 - International : +33 2 99 84 71 00Télécopie : 02 99 84 71 71 - International : +33 2 99 84 71 71

Taking motion into account in wireless systems

Abstract: Recent advances in the fields of embedded computing and wirelesscommunications technologies have allowed to a new type of terminals to emerge.Taking advantage of fit capacities in terms of computing, they also can exchangedata both directly or through a specific network.

Because their communication range is limited, the motion of these terminals hasan immediate impact on how their exchanges work. Taking into account this motionseems to be an interesting perspective for systems employing such terminals.

The objective of this document is to investigate and classify the different waysin which this motion is taken into account by computing systems. We will see thatthis goes beyond adaptative systems.

Key-words: motion, wireless communications, ubiquitous computing

Prise en compte du mouvement dans les systèmes de communication sans-fil 3

Table des matières

1 Introduction 5

2 Mobilité et systèmes de communication sans fil 72.1 Mobilité physique : définition et détection . . . . . . . . . . . . . . 7

2.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1.2 Détection de la mobilité . . . . . . . . . . . . . . . . . . . 8

2.2 Systèmes mobiles de communication sans fil . . . . . . . . . . . . . 132.2.1 Les réseaux cellulaires . . . . . . . . . . . . . . . . . . . . 132.2.2 Les réseaux ad hoc . . . . . . . . . . . . . . . . . . . . . . 152.2.3 Les réseaux de personnes . . . . . . . . . . . . . . . . . . . 17

2.3 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Application aux approches adaptatives 203.1 Présentation de l’approche adaptative . . . . . . . . . . . . . . . . 203.2 Prise en compte spatiale de la mobilité . . . . . . . . . . . . . . . . 22

3.2.1 Réservation de ressources dans les réseaux cellulaires . . . . 223.2.2 Cas du protocole de routage ad hoc LAR . . . . . . . . . . 243.2.3 Cas du protocole de routage ad hoc DREAM . . . . . . . . 25

3.3 Prise en compte temporelle de la mobilité . . . . . . . . . . . . . . 273.3.1 Anticipation du handover dans les réseaux cellulaires . . . . 273.3.2 Durée de voisinage dans les réseaux ad hoc . . . . . . . . . 283.3.3 Messages de contrôle dans les réseaux ad hoc . . . . . . . . 303.3.4 Durée de voisinage dans les réseaux de personnes . . . . . . 31

3.4 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4 Application aux approches ubiquitistes 344.1 Présentation de l’approche ubiquitiste . . . . . . . . . . . . . . . . 344.2 Adressage dynamique par le mouvement . . . . . . . . . . . . . . . 35

4.2.1 Cooltown . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.2.2 Spread . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.3 Mouvement comme médium de communication . . . . . . . . . . . 374.4 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5 Conclusion 40

RR n˚4720

4 A. Troël, F. Weis, M. Banâtre

Table des figures

1 Accès par bornes à une infrastructure centralisée . . . . . . . . . . . 142 Réseau cellulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Réseau ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Réseau de personnes . . . . . . . . . . . . . . . . . . . . . . . . . 185 LAR: request zone et expected zone . . . . . . . . . . . . . . . . . 256 DREAM: calcul de l’angle de routage . . . . . . . . . . . . . . . . 267 calcul du temps d’expiration du lien dans les réseaux ad hoc . . . . 298 Prédiction de la durée de voisinage par régression . . . . . . . . . . 329 Système d’informations spatial . . . . . . . . . . . . . . . . . . . . 3710 Les différents échanges dans un réseau Pollen . . . . . . . . . . . . 3811 Taxonomie de la prise en compte du mouvement . . . . . . . . . . . 41

INRIA


1 Introduction

Les progrès technologiques conjoints dans des domaines tels que l’informatiqueembarquée, la communication sans fil et la consommation énergétique ont permisl’émergence de terminaux informatiques d’un nouveau type . D’une part, grâce aufaible encombrement qu’ils engendrent et la grande capacité d’autonomie dont ilsdisposent, ces terminaux sont aisément transportables par des piétons, des véhiculesautomobiles ou encore des robots. D’autre part, la présence d’une interface de com-munication sans fil leur apporte une autre spécificité essentielle, celle de pouvoiréchanger de l’information avec leurs pairs directement ou par le biais d’un réseaucellulaire. Les assistants personnels et les téléphones portables sont aujourd’hui desexemples très répandus de ce type de terminaux.

Les interfaces de communication qui équipent ces terminaux ont une portée li-mitée. Sans recourir à infrastructure supplémentaire pour relayer ses messages, unterminal ne peut communiquer qu’avec ses voisins directs, c’est-à-dire les entités setenant à sa portée. Or, étant à la fois portables et autonomes, ces terminaux subissentles mouvements de leur utilisateur. De ce fait, l’ensemble des entités voisines d’unterminal varie en fonction de leurs déplacements. Considérons, en guise d’illustra-tion, le domaine bien connu de la téléphonie mobile. L’usager dispose d’un terminalà l’aide duquel il doit pouvoir joindre un autre usager, par le biais du système detéléphonie. La portée d’un téléphone portable étant limitée, cet accès est réaliségrâce à d’un réseau d’antennes réparti dans la zone couverte par le système. Le dé-placement de l’usager peut, dès lors, induire des changements dans l’ensemble desentités voisines (les antennes à portée). L’accès au réseau doit donc être effectué viaune antenne dont le choix dépend de la localisation du terminal. Un mouvement desa part peut nécessiter une modification de point d’accès.

Ce constat de l’étroite relation existant entre mobilité et communication laisseentrevoir le rôle singulier que la mobilité physique joue inévitablement dans le fonc-tionnement des systèmes composés de ce genre de terminal. La prise en comptede leur mobilité physique apparaît alors comme une perspective intéressante dansl’élaboration de tels systèmes.

La prise en compte de la mobilité des terminaux par un système peut, parexemple, permettre à ce dernier de s’y adapter afin d’améliorer les services qu’iloffre. Cela renvoie à la problématique de l’adaptation du système informatiquevis-à-vis de la mobilité. Ces systèmes adaptatifs ont été étudiés de manière no-

RR n˚4720


table [14, 21, 9]. Cette prise en compte de la mobilité est également nécessairedans d’autres domaines, tels que celui de l’ubiquité numérique. Introduite par Wei-ser [47], son objectif principal est de rendre le recours par l’utilisateur aux moyensinformatiques plus intuitif et transparent. Pour cela, un ensemble de terminaux mo-biles et communiquants est généralement mis en œuvre [45, 22]. La prise en comptede leur mobilité est là encore très souvent nécessaire au fonctionnement du systèmeconsidéré.

Ce document propose d’examiner et de classifier les différentes techniques em-ployées afin de permettre aux systèmes informatiques de prendre en compte cettemobilité. Nous l’envisageons de manière générale, quitte à laisser de côté les pro-blèmes techniques relatifs à l’utilisation d’une technologie ou d’un réseau particu-lier. S’ils sont d’un intérêt indéniable, ils ont déjà été traités pour la plupart, ouapportent peu à l’étude proprement dite. Nous verrons ainsi que la prise en comptede la mobilité physique dans les systèmes de communication sans fil dépasse lesimple cadre adaptatif.

Dans un premier temps, nous présentons les domaines auxquels ce document faitréférence. Nous définissons ce que nous entendons par le terme mobilité et évoquonsbrièvement les différentes techniques permettant de la détecter au niveau informa-tique. Nous rappelons ensuite les principales catégories de réseaux de communi-cation sans fil dans lesquels les terminaux mobiles évoluent principalement. Dansle chapitre suivant, nous examinons les différentes méthodes de prise en comptede la mobilité dans une approche adaptative traditionnelle et montrons les apportsde ces techniques. Nous réservons au quatrième chapitre l’approche nouvelle parl’ubiquité numérique de la prise en compte de la mobilité, dans laquelle le mouve-ment joue un rôle essentiel dans les systèmes informatiques considérés. Enfin, nousconcluons en proposant une taxonomie originale des différentes méthodes de priseen compte de la mobilité dans les systèmes de communication sans fil.

INRIA


2 Mobilité et systèmes de communication sans fil

Ce chapitre permet de définir et de rappeler diverses notions dont il sera fait ré-férence dans la suite de document. La première partie est consacrée à ce nous avonsévoqué précédemment sous les termes de mobilité physique. Afin de lever toute am-biguïté sur cette notion, nous en donnons tout d’abord la définition. Nous évoquonsensuite les diverses méthodes permettant de la détecter. Le thème de la secondepartie est, quant à lui, celui des systèmes de communications sans-fil. Nous y pré-sentons les différentes formes sous lesquelles ces systèmes se déclinent et montronsplus précisément en quoi la mobilité des terminaux les composant peut y jouer unrôle non négligeable.

2.1 Mobilité physique : définition et détection

Dans cette partie, nous nous intéressons plus précisément à la notion de mobi-lité physique. Comme nous l’avons souligné dans le chapitre précédent, mobilité etcommunication sont fortement corrélées dans les systèmes sans fil. Afin d’offrir unservice de bonne qualité, il peut s’avérer judicieux de prendre en compte et d’ex-ploiter activement la mobilité des terminaux. Pour cela, il est nécessaire d’être enmesure de percevoir cette mobilité au niveau informatique. Après avoir tout d’aborddéfini précisément ce que nous entendons par mobilité physique, nous évoquons lesdifférentes technologies disponibles permettant de la détecter.

2.1.1 Définition

Le terme de mobilité est très utilisé dans le domaine informatique. Générale-ment, le concept de mobilité désigne une modification d’état, qu’il soit concret ouabstrait. Dans le domaine des agents mobiles, la mobilité est un phénomène quidésigne le saut d’un processus informatique (l’agent) d’une ressource informatiqueà une autre (par exemple, un navigateur Web qui passe d’un URI à un autre). Lamobilité est considérée exclusivement sous l’angle informatique. Les mécanismesde roaming renvoient, eux, au domaine des réseaux. Ils permettent à une machined’être mobile, c’est-à-dire de changer de réseau de manière transparente du pointde vue de l’adressage. La mobilité se manifeste, vis-à-vis du réseau, comme unemodification du système d’adressage.

RR n˚4720


Dans ce document, la notion de mobilité à laquelle nous faisons référence est lamobilité au sens commun, telle que nous la percevons tous les jours. Nous emploie-rons les termes de mobilité, mobilité physique ou encore plus simplement mouve-ment pour désigner cette notion.

Les terminaux envisagés sont des terminaux de taille réduite, facilement por-tables par un piéton ou par un véhicule. Dès lors, ces calculateurs, ou entités com-municantes, subissent directement les mouvements de l’entité physique qui les trans-porte. Cela leur confère de facto une mobilité physique. Par la suite, nous assimi-lerons entité physique et entité communicante en tant qu’entité, terminal, ou nœud.De ce fait, la mobilité du terminal est considérée comme une mobilité a priori,c’est-à-dire qu’elle lui est intrinsèque. C’est précisément la prise en compte de cettemobilité que nous proposons d’étudier.

Il est important de noter que la mobilité ne se limite pas à la simple localisation.Le mouvement est une notion cinématique, c’est-à-dire qu’il repose sur une relationentre le temps et l’espace. Une position ne suffit donc pas à le décrire. La descriptionminimum d’un mouvement est un historique de localisations datées.

2.1.2 Détection de la mobilité

Le besoin de la prise en compte au niveau informatique de la mobilité des ter-minaux est naturellement soulevé par l’étroite relation qui existe entre mobilité etcommunication. Toutefois, cette prise en compte nécessite au préalable une acqui-sition.

La nature de cette acquisition varie en fonction du système et des technologiesutilisées ainsi que de la richesse des informations requises. Lorsque cette acquisi-tion est accomplie directement par le système, elle n’implique alors pas de recoursà une infrastructure ou un système externe. Elle peut être qualifiée d’acquisition au-tonome. Dans le cas contraire, l’utilisation d’un système externe de localisation estrequise. L’acquisition est alors dite assistée.

Détection autonome

La détection autonome se limite souvent à détecter l’impact de la mobilité desterminaux plutôt que la mobilité en elle-même. Elle consiste à évaluer périodique-ment la composition du voisinage du terminal considéré. Pour détecter le mouve-

INRIA


ment en lui-même, il est nécessaire d’adjoindre aux terminaux les capteurs idoinestels qu’un tachymètre, un accéléromètre ou une boussole. Cela est d’ailleurs pro-posé dans [39]. Toutefois, par manque de repère fixe commun, l’acquisition de lamobilité ne permet pas de décorreler le mouvement propre du mobile et ceux de sesvoisins. Afin d’illustrer les mécanismes de détection autonome, nous envisageonsles trois technologies que

��, BlueTooth et le réseau GSM. Nous expliquons

les différents mécanismes actifs mis en œuvre pour assurer cette détection.

802.11b : Les réseaux locaux sans-fil [11], ou WLAN, permettent la mise enœuvre de communications sans-fil de moyenne portée. Deux terminaux équipésde cartes

�� peuvent communiquer entre eux lorsqu’ils sont au plus éloignés

d’environ 250 mètres. Le processus de communication repose sur une technologieà étalement de spectre. Il est de plus symétrique et très semblable à la manière dontethernet fonctionne : chaque carte dispose d’un identifiant lui permettant de savoir,lors de la réception d’une trame, si elle lui est destinée.

La technologie n’inclut pas de mécanisme actif permettant au système de dé-couvrir quels sont les terminaux voisins. Cela doit être réalisé de manière logiciellepar un protocole idoine. Généralement, les solutions proposées reposent sur l’en-voi régulier d’un paquet permettant aux terminaux voisins de détecter le terminalémetteur. La fréquence d’émission est fixée selon le type de mobilité envisagée afinde trouver un compromis entre réactivité de la découverte et utilisation de la bandepassante disponible.

BlueTooth : BlueTooth [18] est une technologie de communication sans-fil decourte portée. Deux terminaux sont à portée de communication lorsqu’ils sont éloi-gnés d’au plus une dizaine de mètres. Le médium de communication est partagéentre les terminaux par le biais d’un mécanisme en saut de fréquence. Cela en faitune technologie à faible consommation énergétique particulièrement intéressantepour les systèmes embarqués.

La communication entre les terminaux n’est pas symétrique. Elle repose en effetsur la notion de maître et d’esclave. Un terminal maître peut accueillir jusqu’à septterminaux esclaves au sein de ce que l’on appelle un piconet. Les échanges entreterminaux transitent nécessairement par le terminal maître. Un esclave d’un piconetpeut être accessoirement maître d’un autre piconet. Les deux piconets sont alorsinterconnectés et forment, selon la terminologie BlueTooth, un scatternet.

RR n˚4720


Contrairement à��

, BlueTooth dispose d’un mécanisme de découverte afinque les terminaux puissent détecter la présence de leurs pairs. Celui-ci repose surun mécanisme d’enquête. Pour être détecté par ses voisins, un terminal doit passerdans l’état Inquiry Scan. Toutes les

��

� �secondes, le terminal tente de recevoir un

paquet de découverte durant un centième de seconde sur une fréquence chaque foisdifférente. Lorsqu’il en reçoit un, il y répond après un délai aléatoire variant de 0 à�

�

��secondes. Pour le détecter, les autres terminaux doivent s’être placés en mode

Inquiry et émettre des paquets de découverte.Ce mécanisme permet aux terminaux de détecter régulièrement leurs voisins et

de s’adapter à leur mobilité relative. Du fait de la latence induite par ce mécanismede découverte, il s’avère assez pénalisant voire inadéquat pour des systèmes s’ap-puyant sur des terminaux disposant d’une mobilité trop importante.

GSM : Le réseau GSM [24] est un réseau cellulaire de téléphonie mobile parti-culière développé en Europe. Pour communiquer avec d’autres, chaque utilisateurdispose d’un téléphone portable ou station mobile. Cette station mobile commu-nique avec le réseau par le biais des stations de bases.

Lorsqu’un usager se déplace, il peut être nécessaire qu’il change de station debase parce que celle qu’il utilisait n’offre plus one qualité de transmission suffisante(à cause de l’éloignement, par exemple). Ce processus s’appelle transfert intercel-lulaire ou handover.

Pour cela, la station mobile effectue un contrôle régulier de la puissance dessignaux émis par un ensemble de stations de base dont la liste lui est fournie parcelle à laquelle elle est rattachée. C’est par ce contrôle que le terminal acquiert desinformations sur sa propre mobilité par rapport aux stations de base environnantes.

Pour décider s’il est nécessaire de demander un transfert au réseau, deux algo-rithmes sont communément utilisés. Le mobile peut d’une part augmenter sa puis-sance d’émission, dans les limites autorisées par la norme GSM, jusqu’à ce que celan’ait plus d’effet. À ce moment là, un tranfert est requis. Cet algorithme est celuide performance minimale. L’algorithme budget de puissance préfère au contraireprivilégier la demande de déclenchement du handover à l’augmentation de la puis-sance.

Les transferts intercellulaires peuvent aussi être déclenchés sur demande du ré-seau, par exemple dans un but d’équilibrage de charge.

INRIA


Acquisition assistée

L’acquisition assistée de la mobilité des terminaux nécessite l’utilisation d’unservice informatique supplémentaire. Elle permet souvent d’effectuer une acquisi-tion plus précise et offre des informations plus riches que celles qui sont délivréespar la détection autonome. Elle peut être classée en deux catégories selon qu’elleest mise en œuvre dans un lieu restreint (acquisition locale) ou bien à l’échelle pla-nétaire (acquisition globale). Ces deux types d’acquisitions peuvent être combinéspour permettre un fonctionnement correct en dépit de leurs limites respectives [26](par exemple en intérieur et en extérieur).

Acquisition globale : Le seul système permettant l’acquisition du mouvement demanière globale est actuellement le système Navstar 1, plus connu sous le nom deGPS 2 [12]. Il a pour objectif d’offrir un service de positionnement géographique enn’importe quel point du globe. Un échantillonnage régulier de la position permetd’en déduire des informations sur le mouvement du mobile (vitesse instantanée,cap, etc...)

Le système repose sur la mesure de la distance entre le mobile dont on dé-sire évaluer la position et au moins quatre satellites des vingt-quatre composant laconstellation Navstar. Les déplacements des satellites ont été calculés de manière àce qu’au moins quatre soient visibles depuis le globe terrestre pendant plus de 99%du temps.

Chaque satellite émet, chaque milliseconde, un message sur deux ondes radio-électriques sur les fréquences de

��

�et

��

�GHz. Lorsque le récepteur GPS ter-

restres reçoit un signal, il calcule la différence de temps entre l’heure d’émissiondu signal inscrite dans le message et l’heure actuelle. Il calcule alors la distance leséparant du satellite et en déduit une première sphère sur laquelle il se situe. En ef-fectuant ce calcul sur un deuxième satellite sa position se précise puisqu’elle se situesur un cercle, en l’occurence, l’intersection des deux sphères. Avec trois satellites,seuls deux points subsistent. Le quatrième calcul vient lever l’ambiguïté.

Ce système présente toutefois quelques limites. Il est tout d’abord nécessaireque l’horloge interne du récepteur soit synchronisée avec celles des satellites. Unécart d’une microseconde correspond à une erreur d’environ 300 mètres. D’autre

1. NAVSTAR : NAVigation System with Time And Ranging2. GPS : Global Positioning System

RR n˚4720


part, une ligne de vue directe entre le récepteur est le satellite est nécessaire aufonctionnement. Ce système est donc inopérant en intérieur. Enfin, la vitesse de dé-placement des mobiles vient, elle aussi, perturber les mesures de temps de parcours.

Les deux ondes émises par les satellites ont des fréquences différentes. Ellesn’évoluent pas de la même façon dans l’atmosphère. Des récepteurs évolués telsque les GPS géodésiques permettent de mesurer la différence de temps de parcoursentre les deux ondes et de corriger les aberrations induites par la vitesse du mobile.Les GPS différentiels permettent, quant à eux, de diminuer l’erreur mesurée enutilisant un réseau terrestre de points références dont la position est connue. Danstous les cas, un fonctionnement à l’intérieur de structures telles que des immeublesest compromis par la nécessité de disposer d’une ligne de vue avec les satellites.

Acquisition locale : L’acquisition locale de la mobilité repose très souvent surl’acquisition locale de la position. Tout comme avec l’acquisition globale, la mesurerégulière de la position permet de déduire des caractéristiques du mouvement tellesque la vitesse ou la direction. L’avantage principal de cette approche est qu’ellepermet d’obtenir la localisation là où le GPS est inopérant.

Le système Active Bat [46] offre un service local de positionnement. Il permetl’estimation de la distance entre un mobile et des bornes. Cette estimation reposesur l’exploitation de la différence de vitesse de propagation de deux ondes et res-semble à celle réalisée par les récepteurs géodésiques. Les deux ondes utilisées sontles ondes radioélectriques et les ultrasons. La mise en place d’un tel service néces-site toutefois un effort quant au déploiement des bornes et à leur interconnectionavec le système centralisé. De plus, cette méthode ne fonctionne qu’en intérieur carl’ultrason est très sensible aux perturbations.

Le système RADAR [3] offre lui aussi un système de localisation intérieure.Il repose sur la mesure de la puissance du signal émis par trois bornes

��

et reçu par le mobile. Il nécessite au préalable une phase d’apprentissage consé-quent qui consiste en l’échantillonnage de nombreuses positions de la zone cou-verte. Cela rend son déploiement ardu et nécessite que la zone couverte reste in-tacte. Par exemple, l’abatage d’une cloison de l’étage couvert d’un immeuble peutavoir des conséquences fatales sur le système.

La réponse au déploiement coûteux est apportée par [6]. Une grille de capteursformant un système distribué est répartie dans la zone de localisation à couvrir.Chaque capteur est situé à une position connue. La communication entre le mobile

INRIA


et les capteurs voisins permet, par le biais d’une modélisation des onde radios, d’es-timer la position du mobile. Toutefois, cette méthode n’est valable qu’en extérieur.En effet, la modélisation proposée ne peut tenir compte des phénomènes aléatoiresd’écho qui surviennent en intérieur.

2.2 Systèmes mobiles de communication sans fil

Dans la section précédente, nous avons défini la notion à laquelle renvoient lestermes de mobilité physique ou encore de mouvement. Nous avons, de plus, détailléles différentes méthodes de détection informatique de la mobilité des terminaux.Nous présentons à présent les différents types de systèmes de communication sansfil, dans lesquels ces terminaux évoluent traditionnellement. Parmi ces systèmes,on distingue trois principales familles que sont les réseaux cellulaires, les réseauxad hoc, et enfin les réseaux personnels 3. Ces systèmes de communication sans filproposent aux terminaux mobiles qui les composent un schéma particulier de com-munication. Pour chacun d’eux, nous mettons en avant la relation liant la mobilitéphysique des terminaux à leur modèle de communication.

2.2.1 Les réseaux cellulaires

Les réseaux cellulaires sont des systèmes de communication sans fil qui re-posent sur une infrastructure fixe. Les terminaux qui évoluent au sein de ces réseauxdoivent obligatoirement s’adresser à cette infrastructure pour pouvoir accéder auxservices qu’ils demandent (figure 1). Cet accès s’effectue en général par le biais debornes qui servent alors de passerelle entre le monde sans fil et le reste du système.

En fonction de la puissance de son émetteur, chaque borne couvre une certainezone géographique que l’on abstrait en cellule comme illustré dans la figure 2. C’estprécisément à cause de cette structuration en cellules que l’on dit que ces systèmesreposent sur des réseaux cellulaires. Généralement, on considère que deux cellulessont voisines lorsqu’il est possible pour un terminal mobile de passer de l’une àl’autre en se déplaçant physiquement, sans passer par une cellule intermédiaire etsans quitter la zone couverte.

L’arrangement spatial des bornes du système définit de facto sa zone de cou-verture (on suppose en général que l’impact moyen de l’environnement extérieur

3. PAN : Personal Area Networks

RR n˚4720


terminal

borneinfrastructure

FIG. 1 – Accès par bornes à une infrastructure centralisée

sur les communications sans fil est constant). Cette zone de couverture est souventconsidérée comme fixe dans l’espace car les bornes qui la définissent le sont aussi. Ilconvient donc de répartir judicieusement ces bornes afin que la zone géographiqueque l’on souhaite couvrir le soit effectivement dans son intégralité.

FIG. 2 – Réseau cellulaire

Lorsque le terminal se déplace à l’intérieur de la zone couverte par le réseaucellulaire, il est possible qu’il passe d’une cellule à une autre. Il doit alors changerde borne de référence pour continuer à accéder au réseau. C’est le mécanisme duhandover. Pour savoir à quelle borne se rattacher, la solution la plus commune estde choisir celle offrant la meilleure qualité de liaison.

Lorsque la continuité du service offert est requise, ce changement de borne doits’opérer de la manière la plus transparente possible pour les applications. Des méca-nismes doivent donc être mis en œuvre pour permettre la préparation et l’exécutiondu handover dans les meilleures conditions possibles. Nous reviendrons sur ce pro-

INRIA


blème qui illustre une façon dont le mouvement des terminaux peut se manifesterdans le système d’informations.

Un des domaines d’application le plus connu des réseaux cellulaires est la télé-phonie mobile (et les normes GSM [37] et GPRS [20] en Europe). La norme IEEE��

[11] des réseaux wi-fi permet, elle aussi, de mettre en œvre une telle archi-tecture réseau, avec une portée locale.

2.2.2 Les réseaux ad hoc

Un réseau ad hoc est, contrairement aux réseaux cellulaires, un réseau sans in-frastructure fixe, formé de terminaux mobiles leur permettant de communiquer lesuns avec les autres en dépit de leur éventuelle mobilité. Chaque terminal joue le rôled’un routeur à part entière et utilise son interface de communication sans fil pourcontribuer aux échanges du réseau.

La mobilité des terminaux est a priori non contrainte, tandis que leur portéede communication reste limitée. De ce fait, les mouvements des terminaux ont unimpact direct sur la topologie du réseau ad hoc dans lequel ils évoluent. Les routesdisponibles entre deux terminaux à un instant donné sont en effet susceptibles d’êtremodifiées à l’instant suivant, parce qu’un ou plusieurs nœuds intermédiaires ont puse déplacer et ainsi devenir inaccessibles. Pour permettre à deux terminaux d’échan-ger des données à travers le réseau de façon suffisamment robuste, il est donc néces-saire de mettre en place des algorithmes de routage capables de détecter les chan-gements topologiques et de s’y adapter. Le mouvement des terminaux est donc unélément important car il influe grandement sur la topologie du réseau.

lien radio

terminal

FIG. 3 – Réseau ad hoc

De manière générale, on distingue deux approches principales au problème duroutage dans les réseaux ad hoc : l’approche pro-active d’une part, et l’approche

RR n˚4720


dite réactive ou encore à la demande d’autre part. De nombreux protocoles ad hocsont décrits et classés par Feeney [13] selon des critères tels que le modèle de com-munication ou encore la répartition de l’information de routage. La description ex-haustive des divers protocoles ad hoc n’étant pas notre propos, le lecteur s’y référerapour de plus amples informations. Nous allons toutefois rappeler les principes gé-néraux des deux approches principales car nous y ferons référence dans la suite dece document.

L’approche pro-active : L’objectif des méthodes de routage pro-actives est demaintenir, à travers le réseau, des tables de routage permettant à chaque terminalde connaître à tout moment les routes disponibles dans le réseau de la même ma-nière que cela est réalisé dans les réseaux fixes plus classiques. Contrairement auxréseaux fixes, ces tables de routage sont régulièrement et automatiquement misesà jour, de façon à prendre en compte les modifications topologiques du réseau etde s’y adapter en continu. Pour ce faire, les terminaux échangent régulièrement desmessages de contrôle avec leur voisins, c’est-à-dire, les terminaux avec lesquels ilspeuvent communiquer directement sans passer par des nœuds relais.

L’avantage de ce type de protocoles est sans conteste le faible délai nécessairepour obtenir une route entre deux terminaux, ainsi que la rapide connaissance deshôtes inaccessibles. Toutefois, il faut aussi considérer qu’une partie non négligeabledes ressources du réseau est réservée à la mise à jour des tables de routage. De plus,une consommation excessive de ressources peut être observée car l’effort de main-tien des routes s’effectue que ces dernières soient effectivement utilisées ou non. Onnotera enfin que le maintien des routes est d’autant plus coûteux que les terminauxsont mobiles car les mises à jour des tables de routage doivent être d’autant plusfréquentes.

Les protocoles pro-actifs les plus classiques sont GSR [8] (Global State Rou-ting), DSDV [34] (Dynamic-Sequenced Distance-Vector) et WRP [31] (WirelessRouting Protocol).

L’approche réactive : Les méthodes réactives (ou à la demande) ne maintiennentpas de manière continue de tables de routage. Une route n’est établie que lors-qu’un nœud en fait expressément la demande. Une première phase de recherche deroute (route request) est alors effectuée pour atteindre le terminal destination. S’ilest trouvé, le terminal destination répond à l’initiateur de la recherche lors d’une

INRIA


seconde phase (route response). Lorsque la source reçoit la réponse, la route estconstruite et peut être exploitée.

L’avantage des protocoles à la demande est sans conteste la faible surconsom-mation de ressources réseaux qu’ils entraînent. Ils paraissent donc mieux conçuspour faire face à des changements fréquents de topologie. Toutefois, une fois uneroute établie doit être maintenue en dépit de la mobilité des routeurs qui la com-posent, ce qui entraîne là encore un coût en termes de ressources réseaux. D’autrepart, il est impossible pour un terminal de savoir a priori quels sont les hôtes qui luisont inaccessibles. Enfin, le délai d’établissement d’une route est non négligeableet, face à un réseau très dynamique, il peut encore poser des problèmes. En dépit deces limitations, les protocoles à la demande restent toutefois mieux adaptés que lesprotocoles pro-actifs aux réseaux dont la topologie varie de manière importante.

Les protocoles à la demande les plus classiques sont DSR [19] (Dynamic SourceRouting), AODV [35] (Ad hoc On-demand Distance Vector routing) et TORA [33](Temporally Ordered Routing Algorithm).

2.2.3 Les réseaux de personnes

Les réseaux cellulaires permettent une communication globale sans fil dès queles terminaux qui y participent évoluent au sein d’une zone de couverture. Les ré-seaux ad hoc offrent la possibilité à des terminaux d’échanger des informationsde proche en proche, par le biais de mécanismes de routage, en s’affranchissantd’une zone de couverture prédéfinie, dans la mesure où ils partagent un même voi-sinage local. Cette notion de voisinage commun à un ensemble de terminaux peutêtre réduite jusqu’à la considérer uniquement du point de vue d’un terminal. D’uneconception macroscopique du monde donnée par les réseaux cellulaires, on glisseainsi vers la conception microscopique des réseaux de personnes où les seuls nœudsconnus a priori sont les terminaux directement voisins (figure 4).

Cette microconnectivité est rendue possible par l’apparition de technologies decommunication à moyenne distance telles que

��[11] (environ 250 mètres)

puis surtout à courte distance telles que BlueTooth [18] (entre 1 m et 10 m) qui per-mettent d’envisager l’échange d’informations entre des terminaux mobiles physi-quement voisins. Ce type d’échanges se retrouve principalement dans les domainesde l’ubiquité numérique [47], de l’ambient computing [9] ou encore de l’informa-tique diffuse [4]. Ainsi, les assistants personnels sont destinés à profiter de ce type

RR n˚4720


inaccessible

voisin

terminal

voisin

voisin

limite du voisinage

lien radio

FIG. 4 – Réseau de personnes

de connectivité, afin de permettre à leurs utilisateurs de participer à ce que nousappelons des réseaux de personnes.

Dans un tel contexte, nous verrons que la mobilité des utilisateurs joue, là en-core, un rôle important dont il faudra savoir tirer parti.

2.3 Synthèse

Après avoir souligné que le terme mobilité renvoie, en informatique, à plusieursconcepts différents selon le domaine dans lequel il est employé, nous avons dé-fini la manière dont nous l’envisageons, à savoir, le mouvement du terminal. Nousavons ensuite explicité la manière dont cette mobilité était captée. Il s’avère quecette acquisition prend deux formes principales que sont la détection autonome et ladétection assistée. Nous avons de plus souligné que si la détection assistée demandele recours à un service externe supplémentaire, elle apporte aussi des informationsplus précises.

La deuxième partie de ce chapitre a été l’occasion de présenter les grandesclasses de systèmes de communication sans fil : les réseaux cellulaires qui disposentd’une infrastructure, et les réseaux qui en sont dépourvus. Parmi ces derniers, ondistingue les réseaux ad hoc, dans lesquelles un mécanisme de routage permet lacommunication entre des terminaux quelconques et les réseaux de personnes quin’autorisent la communication qu’entre terminaux immédiatement voisins.

INRIA


Dans les chapitres suivants, nous allons examiner comment, au sein des cessystèmes, le mouvement des terminaux peut être pris en compte ainsi que l’apportque l’on peut en attendre.

RR n˚4720


3 Application aux approches adaptatives

Dans le chapitre précédent, nous avons défini la notion de mobilité physiqueet donné brièvement les différents moyens techniques permettant sa détection auniveau informatique. Nous avons, de plus, rappelé les principaux types de systèmesde communication sans fil.

Nous entrons à présent au cœur de l’étude proprement dite. Dans cette partie,nous nous attachons à la principale approche au problème de la mobilité dans lessystèmes informatiques, à savoir l’approche adaptative. Après en avoir présenté lescaractéristiques importantes, nous examinons les différentes manières de prendre encompte la mobilité physique au sein de cette approche.

3.1 Présentation de l’approche adaptative

La première grande classe de mécanismes prenant en compte la mobilité phy-sique des terminaux est celle qui regroupe les méthodes dites adaptatives ou pallia-tives telles qu’elles sont décrites dans [9]. Dans ce genre de systèmes, la mobilitédes utilisateurs est perçue comme une source de perturbations entraînant de pos-sibles dégradations du service rendu. L’objectif de tels mécanismes palliatifs est depermettre au système de communication sans fil d’assurer la délivrance d’un serviceen dépit de cette mobilité. Si l’on prend l’exemple du système de téléphonie mobile,la mobilité d’un usager à travers le territoire est un problème car son terminal n’estpas toujours relié au système par le biais de la même station de base, comme c’est lecas dans un système de téléphonie filaire plus classique. Ce problème est exacerbélorsque l’usager, pendant qu’il téléphone, se déplace de entrainant aussi un hando-ver. Dans un souci de qualité et de continuité de service, le mécanisme doit êtretransparent pour l’utilisateur final, et ce, bien qu’un mécanisme de reconfiguration“au vol” soit nécessaire.

Cela nous amène à définir plus précisément les deux types de mobilité que sontmobilité physique et mobilité logique du terminal. La mobilité physique est simpleà concevoir, puisqu’elle renvoie directement au mouvement que le terminal effec-tue dans le monde réel. La mobilité logique, elle, dépend étroitement du systèmed’informations mis en œuvre et peut être définie comme l’impact de la mobilitéphysique au niveau du système. D’un point de vue plus géométrique, on peut consi-

INRIA


dérer la mobilité logique comme une sorte projection de la mobilité physique parrapport au système d’informations.

Ce parallèle, s’il peut paraître délicat, permet de mieux comprendre pourquoi detels systèmes adaptatifs ont besoin de prendre en compte la mobilité physique et nonpas seulement la mobilité logique, s’ils veulent fonctionner de manière fortementtransparente. En effet, il est difficile d’anticiper la mobilité logique, parce que beau-coup d’informations disponibles au niveau de la mobilité physique et utiles à cetteanticipation sont oubliées par le système d’informations lors de la projection. Celaest principalement dû au fait qu’elles ne sont pas a priori pertinentes par rapport auservice rendu par le système. Si nous reprenons l’exemple du téléphone mobile, lesmouvements de l’usager à l’intérieur d’une cellule ne sont pas perçus par le systèmede téléphonie car ils n’entraînent pas de modification du point de vue du système.Certes, ils entraînent une régulation des puissances de transmission entre téléphoneportable et station de base, mais cela ne dépend pas du système téléphonique enlui-même. Ils peuvent pourtant paraître intéressant à étudier si l’on désire anticiperun éventuel handover.

Il faut toutefois tempérer la remarque précédente par le fait qu’il existe des sys-tèmes de prédiction permettant de réagir par anticipation, uniquement en fonctionde l’historique de la mobilité logique de l’utilisateur. On trouvera, par exemple,dans [28] et [27], plus d’informations à ce sujet. Cela dépasse toutefois le cadre dece document qui tente d’explorer les différentes utilisations de la prise en comptede la mobilité physique des utilisateurs. Nous verrons d’ailleurs que cela va au-delàmême des mécanismes palliatifs dans le chapitre suivant.

Notons, d’une part, que la mobilité physique n’entraîne pas nécessairement unemobilité logique et que cela dépend du système considéré. D’autre part, la mobi-lité logique prend une forme différente, selon le type du système de communicationsans fil considéré. Ainsi, comme nous l’avons évoqué précédemment, le mouve-ment physique des terminaux se manifeste par un changement de cellule de réfé-rence dans les systèmes cellulaires. Dans les réseaux ad hoc, cette mobilité logiqueprend l’aspect d’un changement de la configuration des tables de routage. Dans lesréseaux de personnes, la mobilité logique correspond, pour un terminal donné, àun changement de l’ensemble de ses voisins. Le tableau 1 résume les différentesfaçons dont la mobilité physique des terminaux se manifeste suivant les systèmesconsidérés.

RR n˚4720


Système de communication Mobilité logiqueRéseau cellulaire Changement de cellule de référenceRéseau ad hoc Changement de la topologie du réseauRéseau personnel Changement de l’ensemble des voisins

TAB. 1 – Différents types de mobilité logique

L’implantation de mécanismes de prise en compte de la mobilité physique desterminaux mobiles portables se retrouve dans les principaux types de systèmes decommunication sans fil, à savoir les réseaux cellulaires, les réseaux ad hoc et lesréseaux de personnes. Cette prise en compte du mouvement revêt généralementdeux aspects principaux, que sont la prise en compte spatiale et la prise en comptetemporelle, que nous allons maintenant décrire.

3.2 Prise en compte spatiale de la mobilité

Une première technique de prise en compte du mouvement consiste à détecter lamobilité physique du terminal afin d’en déduire des zones de l’espace possédant de“bonnes” propriétés, au sens de l’application envisagée. Cette approche est utiliséedans les réseaux cellulaires pour permettre de réserver des ressources par anticipa-tion, ainsi que dans les réseaux ad hoc dans le but d’améliorer les performances desprotocoles de routage. Nous examinons par la suite la manière dont cette prise encompte spatiale est mise en œuvre au travers de trois exemples.

3.2.1 Réservation de ressources dans les réseaux cellulaires

L’un des principaux problèmes qui se posent dans le domaine des réseaux cel-lulaires est, pour un terminal donné, le transfert intercellulaire ou encore handover.Il survient typiquement lorsqu’un terminal se déplace de telle manière qu’il quittela cellule dans laquelle il évoluait pour entrer dans une autre. L’accès au réseaudoit alors être effectué par la station de base de la nouvelle cellule au détrimentde l’ancienne. Lorsque des applications à contraintes temporelles sont en jeu, ilest nécessaire que ce processus soit réalisé de façon transparente, c’est-à-dire, sansengendrer de rupture au niveau applicatif. Concrètement, si l’on considère une ap-

INRIA


plication telle que la téléphonie, il est important que la communication de l’usagerne soit pas interrompue lorsqu’il change de cellule.

Pour cela, il peut être judicieux de préparer ce changement en réservant lesressources nécessaires dans les cellules susceptibles d’accueillir le terminal. Uneméthode simple consiste à effectuer ces réservations dans toutes les cellules voi-sines. Elle toutefois induit un surcoût très important. En effet, lors du handover, leterminal n’arrivera que dans l’une des cellules voisines. Les autres auront réservéune partie de leurs ressources en pure perte, bloquant éventuellement d’autres en-trée de terminaux. Il est en fait possible d’améliorer ce mécanisme de réservationpar anticipation en s’appuyant sur le fait qu’en réalité, les terminaux ont rarementun mouvement totalement aléatoire. Ils se déplacent principalement le long de ruesou d’autoroutes. Il suffit alors de ne réserver des ressources que dans la ou les deuxcellules dont la probabilité d’accueil du terminal est maximale.

Ce genre de mécanisme a été étudié dans [41]. Un apprentissage préalable estnécessaire, afin que chaque station de base établisse une série de statistiques luipermettant de prédire la future destination d’un terminal en fonction des cellulesqu’il vient de traverser. Pour cela, chaque terminal préserve un historique (limité)des cellules qu’il a traversé récemment. Lorsqu’un changement de cellule intervient,la cellule destination en notifie la cellule source afin qu’elle mette à jour ses proprestatistiques. Une fois l’apprentissage effectué, les stations de base peuvent limiterla préréservation de ressources aux cellules destination les plus probables.

Les performances d’un tel mécanisme ont été mesurées par simulation dans unsystème de téléphonie mobile, en considérant la bande passante comme ressource.Les critères suivants ont été mesurés au regard de la charge maximum offerte parchaque cellule : probabilité d’impossibilité du handover, d’impossibilité de traite-ment d’un nouvel appel, probabilité de rupture de communication et utilisation dela bande passante. La réservation de la ou des deux meilleures cellules donnent desrésultats comparables. Elle offre d’autre part, une amélioration raisonnable de laqualité de service sans réservation excessive de bande passante par rapport aux poli-tiques extrêmes de réservation. Elle devrait, selon l’auteur, donner de bien meilleursrésultats lors d’une utilisation réelle.

RR n˚4720


3.2.2 Cas du protocole de routage ad hoc LAR

Le protocole LAR [23] (pour Location Aided Routing) est un protocole ad hocde routage à la demande s’appuyant sur la connaissance de paramètres cinématiquesdu mouvement des nœuds du réseau pour y découvrir des routes. LAR suppose quechaque nœud dispose des moyens de connaître de manière autonome ses coordon-nées absolues dans le plan. Il suppose en outre que les nœuds du réseau ont tous unevitesse du même ordre de grandeur dont on connaît la valeur moyenne.

LAR fait partie des protocoles ad hoc dits réactifs, dans lesquels les routes dis-ponibles dans le réseau ne sont pas connues à tout instant, contrairement au cas desprotocoles proactifs. Pour connaître les routes, les nœuds n’échangent pas de tablede routage de façon régulière. Au contraire, une route n’est établie que lorsqu’unterminal mobile en fait expressément la demande. Un mécanisme de constructionde route par inondation du réseau est alors déclenché. L’objectif de LAR est delimiter cette inondation à une zone géographique calculée en fonction des mouve-ments supposés des deux protagonistes de l’échange, afin de réduire le nombre demessages de contrôle inutiles.

LAR suppose que chaque nœud émet régulièrement ses propres coordonnéeset propose d’utiliser pour cela un piggybacking des messages de données émis.Lorsque qu’un nœud source � désire émettre un message � à un nœud destina-tion � , LAR définit l’expected zone comme la zone géographique dans laquelle �peut raisonnablement espérer trouver le terminal � . À partir de la vitesse moyenne

� du terminal et du temps � écoulé depuis la dernière mise à jour de la position de� dans les tables de � , l’expected zone est modélisée par le cercle de centre � etde rayon � � . Les auteurs évoquent aussi certaines optimisations de cette zone enfonction, par exemple, du cap de � .

Une fois cette zone construite, la request zone est calculée de manière à toujourscontenir l’expected zone tout entière, ainsi que le nœud source � . Cette zone géogra-phique est inscrite dans le message � afin d’être exploitée pour limiter l’inondationdu réseau lors de l’envoi de la requête de construction de la route : seuls les nœudscontenus dans cette zone prennent en compte le message de recherche de route etl’émettent à leur tour.

L’appartenance d’un nœud à la request zone est finalement le problème qui vadécider du système de routage. Deux politiques différentes sont proposées. La pre-mière, illustrée dans la figure 5 consiste à définir la zone comme le plus petit rec-

INRIA


S

expected zone

request zone

vtD

FIG. 5 – LAR: request zone et expected zone

tangle incluant l’expected zone et � . La seconde définit l’appartenance d’un nœudà la request zone par le fait que ce dernier doit être plus proche de � que le nœuddont il a reçu le message à convoyer. Cette hypothèse revient en fait à appliquer lapremière méthode à chaque maillon de la chaîne de recherche comme s’il était lenœud source.

Les performances de ce protocole ont été comparées à celles offertes par unprotocole classique fonctionnant par inondation. Pour chacun d’eux, le ratio entrele nombre de paquets relatifs au routage et le nombre de paquets de données pro-prement dites a été mesuré. Le ratio obtenu par LAR est toujours inférieur au ratiode référence. De plus, il s’accroît moins vite lorsque le nombre de nœuds présentsdans le réseau augmente. En outre, l’amélioration de ce ratio tend vers 25% lorsquela vitesse moyenne des nœuds augmente. Enfin, il se comporte mieux lorsque laconnectivité de réseau diminue.

3.2.3 Cas du protocole de routage ad hoc DREAM

Contrairement au protocole LAR qui est un protocole ad hoc à la demande, leprotocole DREAM [5] (pour Distance Routing Effect Algorithm for Mobility) est,quant à lui, un protocole proactif. Dans ce type de protocoles, les nœuds du réseauxéchangent de manière périodique leur table de routage. De fait, les routes dispo-nibles sont connues immédiatement. Ce protocole s’appuie sur la connaissance desmouvements des nœuds du réseau pour enrichir ses tables de routage, afin de di-minuer le surcoût réseau qu’il induit dans les communications. Ainsi, en supposantque chaque terminal dispose d’un moyen de connaître sa position et sa vitesse ins-

RR n˚4720


tantanée, le protocole propose une méthode de calcul continu des routes, tout enlimitant le volume des messages de contrôle nécessaires à leur maintien.

Pour ce faire, les messages de contrôle sont limités à une zone géographique,comme c’est le cas dans le protocole précédent. Toutefois, la méthode de calcul decette zone diffère quelque peu. Chaque nœud transmet à ses voisins ses caracté-ristiques cinématiques qui sont datées puis stockées dans la table de routage. Lors-qu’un nœud � doit envoyer un message à un nœud � , il consulte sa table de routageet calcule l’angle de sommet � dans lequel � doit se trouver. Il y cherche ensuiteses voisins et leur transmet le message. L’angle de routage (figure 6) est calculécomme suit :

A

α

v

θ

ρ

τB

FIG. 6 – DREAM: calcul de l’angle de routage

1. À l’aide des couples �� et �� , on calcule aisément �� , les co-ordonnées polaires de � dans un repère centré en �

2. Connaissant le temps écoulé � depuis la dernière mise à jour de l’entrée � dela table de routage de � ainsi que la vitesse � de � , on calcule le demi-angleau sommet � par �� !�"

Lorsque � est supérieur à un certain seuil # , l’information contenue dans la tablede routage est considérée comme obsolète. On se ramène alors au cas où l’informa-tion est absente et une procédure classique de recherche par innondation doit êtredéclenchée. De même, il n’est pas assuré que � trouve des voisins immédiats dansl’espace angulaire ainsi construit. Lorsque cela se produit, l’algorithme doit recourirà une méthode de recherche de secours par inondation totale du réseau.

Les gains apportés par cette approche ont été mesurés par simulation, pourdes réseaux ad hoc offrant une connectivité moyenne de 90% (c’est-à-dire lorsque

INRIA


moins de 10% des messages émis ne peuvent être acheminés parce qu’aucune routen’existe). Le recours à la procédure d’inondation n’a lieu que dans moins 20% descas. Le protocole a, de plus, été comparé au protocole ad hoc DSR. Du point de vuedu délai d’acheminement des messages, il apporte un gain de 25% au minimum et250% au maximum.

3.3 Prise en compte temporelle de la mobilité

Une seconde technique d’exploitation du mouvement consiste à déduire de lamobilité physique des informations de nature principalement temporelle. Là encore,comme c’est le cas dans les approches palliatives, l’objectif final est d’offrir unservice constant, en dépit de la mobilité des terminaux subie par le système.

La prise en compte temporelle du mouvement des terminaux conduit naturelle-ment à l’estimation des durées de voisinages entre eux et le reste du système d’in-formations. Cette approche est déclinée sous différentes formes dans les réseauxcellulaires (durée de vie du lien entre le terminal et la station de base), les réseauxad hoc (durée de voisinage entre les routeurs) et les réseaux de personnes (duréede vie du lien entre terminaux). Toutefois, nous verrons qu’elle ne se limite pas àcela, et qu’elle permet le calcul automatique d’autres paramètres temporels. C’estpar exemple le cas pour la fréquence d’émission et la durée de vie de messages decontrôle dans les réseaux ad hoc.

3.3.1 Anticipation du handover dans les réseaux cellulaires

Le handover, c’est-à-dire le passage d’un terminal d’une cellule à une autreconstitue, comme nous l’avons déjà souligné en 3.2.1, un problème difficile, no-tament au niveau de la réservation de ressources. Une amélioration complémentaireau traitement du handover consiste à prévoir le moment où il va se produire. Or,une station de base ne sait a priori pas quand, pour un terminal donné, le handoverva survenir et ne peut donc pas l’anticiper.

Pour cela, un mécanisme d’évaluation du temps minimum restant avant qu’unterminal ne quitte une cellule a été proposé [2, 32]. Cette technique s’appuie surla mesure de la puissance du signal lors de la réception par la station de base despaquets réseaux émis régulièrement par le terminal. Mobilité et puissance du signalsont en effet liées. Intuitivement, on conçoit aisément que, plus un émetteur et un

RR n˚4720


récepteur sont éloignés, plus le signal reçu sera de faible amplitude. Dans des condi-tions idéales (vide), cette amplitude est proportionnelle à l’inverse de la distance aucarré (

� �� ) pour de courtes distances (équation de Friss), puis s’écroule en� ��

pour des distances plus importantes (équation two-ray ground).L’obtention successive de tels échantillons permet de calculer le taux de varia-

tion du signal, c’est-à-dire le rapport entre la variation en amplitude et la variationen temps (i.e. la durée de l’historique). Connaissant ce taux ainsi que la valeur dela puissance du dernier signal reçu, il est simple de calculer le temps restant avantque la puissance du signal ne tombe sous un seuil critique au-dessous duquel onconsidère que le terminal est en train de quitter la cellule. Le handover doit alorsêtre préparé puis déclenché. Dans un environnement non parfait, il est importantd’ignorer les perturbations transitoires qui engendrent des variations à court termedes échantillons. Cela est traditionnellement réalisé avec l’aide d’un filtre passe bas.

La mise en œuvre d’un tel mécanisme permet de diminuer les ruptures lors deshandovers en instaurant une priorité de traitement.

3.3.2 Durée de voisinage dans les réseaux ad hoc

Le problème du handover est exacerbé dans les réseaux ad hoc puisqu’ils re-posent uniquement sur l’interconnexion automatique de routeurs mobiles. La mobi-lité de ces routeurs est a priori non contrainte. Pourtant, il est parfois raisonnable deconsidérer qu’elle n’est pas totalement aléatoire et, qu’au contraire, elle suit certainsmotifs reconnaissables. C’est le cas par exemple, si l’on considère un réseau ad hocurbain constitué de véhicules automobiles qui ont tendance à se déplacer la plupartdu temps en ligne droite le long des rues, et ne bifurquent que de temps à autre. Unautre exemple couramment évoqué pour décrire ce cas de figure est un ensemble devéhicules militaires répartis sur un champ de bataille.

En s’appuyant sur ces motifs non aléatoires du mouvement des terminaux, Supropose de prédire les durées de voisinages (Link Expiration Time) des nœuds duréseau [41]. Pour cela, chaque terminal transmet régulièrement à ses voisins sa vi-tesse, son cap et sa position, qu’il obtient par un service de localisation, tel quele GPS, par exemple. Chaque nœud peut ainsi maintenir une table contenant lescaractéristiques cinématiques datées de ses voisins. Il devient possible pour les ter-minaux de prédire le temps d’expiration du lien radio avec chacun de ses voisins,en supposant qu’ils garderont un cap et une vitesse constants à courte échéance.

INRIA


Les problèmes relatifs à la synchronisation des horloges sont supposés traités parun protocole idoine, par exemple NTP [30] ou GPS [12].

Considérons un nœud � et son voisin � . En supposant que les deux terminauxmaintiendront cap et vitesse constants, les équations du mouvement de chaque ter-minal sont les suivantes :

� ��

��

�� En soustrayant les deux équations, on exprime

� �� en fonction de � ,� �� ,

� �� et �� . En passant à la norme, on peut isoler � . La durée pendant laquelle les deuxnœuds resteront voisins correspond au moment où � et � seront au plus distants de� , portée de communication radio. Cette durée, exprimée à l’aide des coordonnées,des caps et des vitesses (obtenues via le système GPS et illustré dans la figure 7) estalors donnée par la formule suivante :

��

��

avec :� ��

AθA

Bv

Bθ

v

r A

B

FIG. 7 – calcul du temps d’expiration du lien dans les réseaux ad hoc

RR n˚4720


Su propose d’exploiter cette prédiction de la durée de voisinage afin d’améliorerles protocoles ad hoc proactifs [41], orientés flots [40], ou multicasts [25]. Pour cela,il calcule la durée de vie des routes comme le minimum des durée de vie des sautsqui la compose. Cela permet alors :

1. de choisir les routes les plus stables2. de prévoir les ruptures imminentes de routes3. d’établir des routes de remplacement avant les ruptures

Dans ses travaux [41], Su donne les gains apportés par l’utilisation de cette tech-nique. Par rapport à l’utilisation de protocoles ad hoc classiques ne prenant pas encompte la mobilité des routeurs, elle apporte aux réseaux ad hoc orientés flux unmeilleur débit. Le délai moyen reste raisonnable, tandis que l’overhead induit estnettement plus faible. Elle offre aux protocoles proactifs (par rapport à DSDV [34],par exemple) un plus haut taux de livraison de paquets. Enfin, en comparaison àd’autres protocoles ad hoc multicasts tels que ODMRP [16], elle permet une dimi-nution du nombre de messages de contrôle nécessaires en cas de faible mobilité etune meilleure utilisation de ces derniers en cas de mobilité soutenue.

3.3.3 Messages de contrôle dans les réseaux ad hoc

De manière plus générale, la connaissance pour un terminal de sa propre mobi-lité permet aussi de calculer automatiquement les paramètres temporels de certainesapplications. La fonction de ces paramètres peut varier et il peut s’agir, par exemple,de délais de garde, ou encore, de fréquences d’événements. Pour illustrer cette ap-plication de la prise en compte temporelle de la mobilité, nous proposons de revenirsur le protocole de routage DREAM, évoqué en 3.2.3. En effet, en plus de l’amé-lioration du processus de routage par confinement des messages de contrôle, lesauteurs mettent en avant le phénomène de Distance Effect et en proposent une ex-ploitation. Nous expliquons, par la suite, ce qu’est le Distance Effect ainsi que sonlien avec la mobilité. Nous montrons enfin son application au calcul automatique dela fréquence d’émission des messages et de leur durée de vie.

Si l’on considère deux terminaux mobiles et que l’on se place du point de vuede l’un d’eux, il semble que l’autre se déplace d’autant plus lentement qu’il estéloigné. D’un point de vue plus géométrique, ce phénomène provient de la propriétéangulaire selon laquelle la distance à parcourir pour balayer un angle donné est

INRIA


proportionnelle à la distance séparant le mobile du sommet de l’angle. D’autre part,les auteurs observent que plus un nœud du réseau se déplace rapidement, plus il doitfréquemment avertir ses voisins des nouvelles caractéristiques de son mouvement.

Ces observations effectuées, il est possible d’entrevoir certaines améliorationsau protocole de routage, du point de vue de la durée de vie des messages de contrôleainsi que du point de vue de leur fréquence d’émission. Ainsi, les entrées des tablesde routage d’un nœud donné peuvent-elles être mises à jour en fonction de la dis-tance le séparant des terminaux correspondants : plus la distance est grande, plusla fréquence de mise à jour peut être réduite, et ceci, sans affecter la validité de latable de routage. Chaque nœud peut, d’autre part, adapter dynamiquement la fré-quence d’envoi des messages de contrôle en fonction de sa mobilité, sans toutefoisdiminuer la précision des routes calculées à partir des tables de routage. En tenantcompte conjointement de ces deux propriétés, les auteurs proposent un mécanismede mise à jour des tables de routage à fréquence variable reposant sur deux types demessages de contrôle que sont les messages à courte durée de vie qui n’atteindrontque les voisins les plus proches du nœud émetteur et ceux à longue durée de vie qui,s’ils parcourront la totalité du réseau, seront émis moins souvent.

3.3.4 Durée de voisinage dans les réseaux de personnes

À la différence des réseaux ad hoc, les problèmes inhérents à la mobilité phy-sique dans les réseaux de personnes ne se posent pas en terme de routage. Le pro-blème principal posé par le mouvement des terminaux voisins dans les réseaux per-sonnels est que les communications souffrent d’une certaine volatilité. En effet, leurdurée de vie varie en fonction des mouvements des terminaux voisins, ainsi que dumouvement propre du terminal considéré.

Afin de limiter l’impact de cette volatilité des liens de voisinage, il peut être en-visagé de prendre en compte la mobilité des terminaux. Cela doit permettre d’antici-per les ruptures de communication et ainsi de mieux gérer l’ensemble des échangesayant lieu au sein du voisinage physique.

Pour ce faire, une architecture logicielle reposant sur l’estimation de la duréede voisinage a été proposée dans le cadre d’interactions de proximité [43]. Comptetenu que les terminaux considérés sont des assistants personnels standards, le re-cours à un service de localisation externe à été abandonné. Chaque terminal estimedonc, de manière autonome, la durée des voisinages auxquels il participe. Pour cela,

RR n˚4720


R

T

D

t

d

(a) régression linéaire

R

T

P

t

d

(b) régression non linéaire

FIG. 8 – Prédiction de la durée de voisinage par régression

on suppose qu’un paramètre évoluant en fonction de l’éloignement de deux termi-naux est accessible. Ce peut être la puissance des signaux reçus lors des échangesou bien directement la distance séparant les deux terminaux, si l’on dispose de latechnologie idoine. Ce paramètre est ensuite échantillonné et sauvegardé de manièrerégulière dans un historique de type fenêtre coulissante. Sa taille doit être établie, audépart, en fonction de la mobilité envisagée (mouvements de véhicules, de piétons,etc. . . ).

La prédiction de la durée de voisinage a alors lieu sur l’historique. Un appa-riement entre l’historique et un ensemble de courbes représentant des mouvementscaractéristiques est effectué par régression (linéaire ou non) pour trouver la courbelui convenant le mieux. Une fois cette courbe � trouvée et connaissant la portéemaximale � de l’interface de communication sans fil du terminal 4, il devient pos-sible d’estimer la durée � du lien de voisinage en résolvant l’équation � �� .Les figures 8(a) et 8(b) illustrent ce mécanisme de prédiction de la durée � en fonc-tion de la distance � , de manière linéaire (approche du nuage de mesures par unedroite lors d’un mouvement uniforme) ou non linéaire (approche du nuage parune parabole lors d’une accélération).

Cette technique autonome de prédiction est utilisée par un système d’ordonnan-cement de messages au sein du voisinage. Elle permet de donner la priorité à deséchanges dont on prévoit qu’ils ne seront pas interrompus. Ainsi, pour un même

4. La portée de l’interface de communication sans fil du terminal doit être exprimée selon leparamètre échantillonné.

INRIA


volume de données transmises, on constate une économie de la ressource réseau quipeut atteindre jusqu’à 50% dans les meilleurs cas.

3.4 Synthèse

Dans ce chapitre, nous avons étudié les différentes prises en compte de la mobi-lité physique des terminaux dans les systèmes adaptatifs. Nous avons montré com-ment cette mobilité physique se manifeste de manière logique au niveau du systèmed’informations et en quoi l’effort de détection du mouvement peut s’avérer rentableen ce qu’il apporte des informations supplémentaires sur les terminaux.

On distingue dans ces systèmes deux grandes approches de prise en comptedu mouvement : la prise en compte spatiale, d’une part, dont l’objectif est de dé-finir des zones géographiques disposant de “bonnes” propriétés pour le système(par exemple, pour le confinement des messages de contrôle) et la prise en comptetemporelle, d’autre part, permettant le calcul automatique de paramètres tels que ladurée de voisinage ou la fréquence d’émission des messages de contrôle.

Il convient toutefois de souligner que la mobilité est perçue par les systèmesadaptatifs comme une source de perturbations, dont il s’agit d’isoler les applica-tions afin qu’elles fonctionnent convenablement. En effet, les applications mises enœuvre dans ce type de systèmes ne sont pas, a priori, conçues pour intégrer la mobi-lité des terminaux. Si l’on considère, par exemple, la téléphonie mobile, la fonctionprincipale de l’application est la communication entre les terminaux, quelque soitleur éventuelle mobilité. Dès lors, les différentes prises en compte des mouvementsdes terminaux constituent toujours un effort supplémentaire à fournir de la part dusystème.

Ceci n’est toutefois pas obligatoire. Il existe en effet des applications non mar-ginales pour lesquelles cette prise en compte s’effectue sans engendrer de surcoûtet de manière naturelle. On trouve la plupart de celles-ci au sein d’un domaine qui arécemment émergé : l’ubiquité numérique. Nous lui consacrons le chapitre suivant.

RR n˚4720


4 Application aux approches ubiquitistes

Dans les systèmes mobiles de communication sans fil, les approches adapta-tives, ou encore palliatives permettent la délivrance d’un ou plusieurs services à desterminaux en dépit de leur mobilité. L’objectif commun de ces approches est la ré-duction de l’impact de cette mobilité physique au niveau des applications. Ceci estgénéralement réalisé par une couche système intermédiaire. Nous avons décrit, dansle chapitre précédent, comment la prise en compte du mouvement s’insère au seinde cette couche.

Parallèlement aux approches palliatives existent des approches nouvelles et radi-calement différentes, que l’on regroupe à présent sous le nom d’ubiquité numérique,ou encore informatique diffuse. Après en avoir rappelé les principales caractéris-tiques, nous présentons plusieurs exemples de prise en compte la mobilité physiquedes terminaux au sein des systèmes ubiquitistes.

4.1 Présentation de l’approche ubiquitiste

Les principes généraux de l’ubiquité informatique ont été décrits dans [47]. Sonobjectif principal est de parvenir à fondre le monde réel, dans lequel les utilisateursévoluent, et le monde informatique, auquel les terminaux appartiennent, afin depermettre un recours transparent à l’outil informatique. Cette fusion doit s’effectuerde la manière la plus intuitive possible du point de vue des utilisateurs car leurattention et leurs actions sont directement orientées vers le monde physique. C’estdonc à l’univers informatique qu’il incombe d’opérer la fusion.

Les premiers projets relatifs à l’ubiquité numérique ont été ParcTab [45], deRank Xerox, et Active Badge [44], conduit par Olivetti. Active Badge permet lalocalisation d’utilisateurs munis d’un badge signalant leur présence à une infra-structure de capteurs infrarouges au sein d’un bâtiment. De manière plus générale,ParcTab propose, aux utilisateurs, un accès distribué et transparent au système in-formatique par le biais d’un terminal et de liaisons infrarouges réparties à l’inté-rieur d’un bâtiment. Depuis, beaucoup d’études ont été menées sur le sujet. Il existed’ailleurs de nombreux articles dressant un état de l’art sur le sujet tels que [7]ou [42].

La prise en compte de la mobilité physique, parce qu’elle est fortement corréléeaux actions des utilisateurs, s’inscrit implicitement dans l’ubiquité numérique. De

INRIA


nombreuses études, telles que comMotion [29], Cyberguide [1] ou FieldNote [38],exploitent la localisation de l’utilisateur en tant que paramètre à part entière ducontexte, c’est-à-dire de l’ensemble des informations caractérisant une situation.Toutefois, comme nous l’avons souligné en 2.1.1, la localisation ne suffit pas àdécrire le mouvement physique et l’on constate finalement que peu nombreuses sontles applications ubiquitistes qui exploitent réellement le mouvement de l’utilisateur.

Dans les approches adaptatives, cette prise en compte, si elle s’avère parfois trèsefficace dans un objectif d’optimisation, n’apparaît que comme une aide supplé-mentaire au système et, de ce fait, n’entre pas réellement au cœur des applications.Ce raisonnement, poussé à l’extrême, permettrait d’affirmer que, sans cette priseen compte, les applications considérées fonctionneraient toujours, certes, avec desperformances moindres.

Les principes de l’ubiquité informatique doivent permettre de dépasser la priseen compte, dans un but exclusivement adaptatif, de la mobilité physique des termi-naux. Parce qu’elle tend vers la fusion des univers physique et informatique, l’ubi-quité numérique permet la conception d’applications d’un genre nouveau, dans les-quelles le mouvement de l’utilisateur trouve une place fondamentale, quand il devaitse contenter d’un rôle secondaire dans les approches palliatives. Nous allons mon-trer, au travers de deux études, en quoi cette mobilité physique peut trouver sa placedans la sémantique de certaines applications.

4.2 Adressage dynamique par le mouvement

De la même façon que des informations sont structurées dans une mémoire in-formatique, des systèmes d’informations existent implicitement dans le monde réel,structurés par la disposition spatiale des entités. C’est le cas, par exemple, dans lesbibliothèques, les supermarchés ou les villes.

S’il l’on dote les entités physiques d’une existence informatique et d’une inter-face de communication, il devient possible de les adresser dynamiquement : c’estl’utilisateur qui fait l’opération en se déplaçant dans le monde physique.

Cela constitue une conception de la mobilité physique radicalement différentede celle qui est traditionnellement abordée. Au lieu de proposer des solutions visantà s’accomoder de l’impact 5 de la mobilité physique dans les systèmes d’informa-tions, elle est directement inclue au sein du fonctionnement du système d’infor-

5. Voir la notion de mobilité logique dans le chapitre précédent

RR n˚4720


mations et est envisagée comme un mécanisme d’adressage. Nous décrivons par lasuite deux travaux proposant cet adressage dynamique.

4.2.1 Cooltown

Cooltown [36] est un projet mené par Hewlett Packard. Son objectif est d’asso-cier une représentation web aux objets de la vie courante. Cela est réalisé par le biaisde serveurs HTTP exploitant dans communications sans-fil directes. De ce fait, lemouvement est, dans cette étude, un moyen d’adresser dynamiquement les objetsrencontrés dans le monde réel.

Les serveurs HTTP peuvent fonctionner directement sur les entités dont ils as-surent la représentation web. Cela est, par exemple, envisageable pour des péri-phériques tels qu’une imprimante ou un vidéo-projecteur. Dans le cas contraire, leserveur est installé sur un ordinateur déployé spécialement. Une salle de musée peutainsi proposer une répresentation web des objets d’art qu’elle renferme.

4.2.2 Spread

Spread [10] est une étude dont l’objectif est de permettre la gestion informatiqued’un système d’informations reposant sur l’espace physique, de la même façon quecela est réalisé pour les processus classiques.

Pour cela, chaque entité physique (utilisateur ou simple objet) prenant part ausystème rayonne ses informations par le biais d’une interface de communicationsans fil au sein d’un volume 6 modélisé par d’une sphère dont le diamètre dépendde la portée d’émission. Toutes les entités dont la sphère de rayonnement couvreun point de l’espace sont accessibles en ce même point. En se déplaçant, une entitéphysique perçoit d’autre entités et peut ainsi adresser différentes informations. Dece fait, la mobilité physique d’un utilisateur contribue directement au mécanismed’adressage du système.

Ce mécanisme d’adressage seul est toutefois insuffisant car plusieurs entitéspeuvent être disponibles en un même endroit. Il est alors nécessaire de disposerd’un outil supplémentaire pour les différencier. Cela est réalisé par une approche

6. Dans l’absolu, ce volume peut être quelconque, mais la sphère est le volume le plus simple àapprocher

INRIA


par espace de tuples similaire à LINDA [15]. Cet espace de tuple permet, de plus,de typer les entités.

La figure 9 illustre le concept de système d’informations spatial et montre unconsommateur dans un magasin spécialisé. Il est au rayon “films français” et nevoit que trois films. Il peut les différencier en utilisant leur titre (Chacun chercheson chat, Au revoir les enfants et Quelques jours avec moi), fourni par l’espace detuples. S’il se déplace vers la droite, il atteindra le rayon “films étrangers” et pourraaccéder à Blade Runner pour en lire la fiche descriptive, par exemple.

<"Au revoir les enfants">

<"Quelques jours avec moi"><"Chacun cherche son chat">

<"Blade Runner">

FIG. 9 – Système d’informations spatial

4.3 Mouvement comme médium de communication

Dans un article intitulé Pollen: Using people as a communication medium [17],Glance, Snowdon et Meunier présentent un moyen original d’exploiter les déplace-ments des utilisateurs au sein d’une organisation. L’objectif de l’étude est la créationd’un nouveau type de réseau informatique dans lequel les communications ne sontplus exclusivement effectuées par le biais d’une infrastructure filaire, mais peuventaussi avoir lieu en s’appuyant sur les déplacements des personnes dotées de termi-naux mobiles tels que des téléphones ou des assistants personnels. Pour cela, lesobjets (livres, posters), les périphériques informatiques (imprimantes, fax, vidéo-projecteurs) et les différents lieux de passages (couloirs, restaurant, bureau, sallesde réunion) sont équipés d’interfaces de communication sans fil (smart-cards oui-buttons) avec lesquelles les terminaux mobiles des utilisateurs échangent de l’in-formation de manière spontanée et transparente.

Les auteurs comparent ce type de communication à la manière dont les abeillesdispersent le pollen des fleurs en en butinant le nectar. Les utilisateurs arpentent

RR n˚4720


durant leur journée différents lieux, consultent divers livres, ou encore utilisent desimprimantes par exemple. Ils chargent ainsi leurs assistants personnels d’informa-tions qui leur sont destinées d’une part, mais aussi d’informations diverses qu’ilstransmettent alors à d’autres utilisateurs ou à certains objets, sans avoir à se soucierdes échanges. En introduisant l’intelligence et le système de profilage nécessaires,il est de plus possible de contrôler les échanges de messages afin qu’ils atteignentleur cible dans les meilleurs délais. Une mémoire centrale optionnelle, ou ruche,présente sur le réseau câblé classique de l’organisation, peut en outre participer auxéchanges lorsque les terminaux sont reliés avec elle (par exemple, lorsque l’assistantpersonnel est posé sur son socle). Les échanges entre deux nœuds d’un réseau Pol-len peuvent ainsi avoir lieu de plusieurs manières, comme illustré sur la figure 10 :

1. directement entre la source et la destination2. via la ruche3. via des nœuds intermédiaires

terminal intermédiaire

terminal destination

terminal source

ruche

1

2

3

FIG. 10 – Les différents échanges dans un réseau Pollen

Deux classes d’applications semblent pouvoir tirer parti d’un réseau de type Pol-len. La première concerne les applications ubiquitistes, c’est-à-dire qui délivrent del’information contextuelle comme, par exemple, les guides interactifs ou les agen-das contextuels. Bien qu’elles ne dépendent pas d’un réseau, elles peuvent en béné-ficier. La seconde classe regroupe les applications qui réunissent plusieurs interac-tions réseau en vue d’accomplir une tâche globale telle que le diagnostic réseau oula messagerie.

Les principaux intérêts de ce type de réseaux sont leur faible coût en terme d’in-frastructure et de périphériques, leur extensibilité et leur configuration facile. Lesdéplacements des utilisateurs y sont un élément essentiel dans l’acheminement des

INRIA


messages et leur mobilité physique est ainsi prise en compte de manière fondamen-tale.

4.4 Synthèse

Au travers de l’étude de deux cas, nous avons remarqué que la prise en comptede la mobilité physique ne se limitait pas uniquement à la résolution d’un problèmetechnique, mais qu’elle pouvait aussi jouer un rôle fondamental dans le fonctionne-ment de certaines applications.

L’étude Pollen, tout d’abord, propose un nouveau type de réseau informatique.En s’appuyant sur des communications sans fil, il devient possible de faire dumouvement des utilisateurs de moyens informatiques des contributeurs actifs auxéchanges du réseau. Leur mobilité devient alors un medium supplémentaire descommunications.

Les approches de Spread et Cooltown proposent, quant à elles, un moyen d’adres-ser des entités ayant une existence informatique. L’espace physique y est envisagécomme un conteneur et la mobilité physique des utilisateurs y devient un moyend’adressage des informations.

Avec l’ubiquité numérique, la prise en compte de la mobilité pénètre au cœur desapplications et en devient un composant essentiel. Pourtant, elle se décline toutefoisau travers d’un nombre restreint d’applications. Deux raisons principales expliquentcela. L’informatique diffuse est, d’une part, un domaine relativement récent. Elle n’apas été aussi profondément étudiée que l’on été les approches adaptatives. D’autrepart, la nature même du domaine ralentit la production d’applications prenant encompte le mouvement des terminaux. La conception d’une application originale in-tégrant la mobilité au niveau sémantique reste, en effet, un exercice difficile. Ledomaine demeure cependant très attractif et devrait permettre la conception d’ap-plications offrant des perspectives résolument nouvelles.

RR n˚4720


5 Conclusion

Dans ce document, nous avons considéré des terminaux informatiques portables,mobiles et dotés d’une interface de communication sans fil. Au travers de plusieursétudes de cas, nous avons exploré les différentes techniques de prise en compte leurmouvement au niveau des systèmes d’informations. De cette étude se dégagent deuxapproches principales, que sont l’approche adaptative ou palliative et l’approcheubiquitiste.

La première catégorie regroupe l’ensemble des systèmes dans lesquels la mobi-lité physique des terminaux apparaît comme un phénomène dont il s’agit de limiterles répercussions au niveau informatique. La prise en compte de la mobilité est alorsune fonctionnalité supplémentaire du système permettant d’améliorer la qualité desservices qu’il délivre. Cette prise en compte peut être qualifiée de prise en compteauxiliaire. Elle nécessite toujours un effort logiciel et souvent un effort matérielsupplémentaires pour fonctionner. Cette prise en compte, qu’elle repose sur les pro-priétés spatiales ou temporelles du mouvement, revêt deux aspects principaux quesont la prédiction d’événements en relation avec le mouvement tels que la duréede voisinage et la configuration automatique de paramètres comme la fréquenced’émission de messages de contrôle, par exemple.

La seconde catégorie se retrouve principalement dans le domaine de l’ubiquiténumérique. Le mouvement n’est plus considéré comme une source de perturbationsdu fonctionnement du système, mais, au contraire, en devient un élément essentiel.Sa prise en compte peut être alors considérée comme fondamentale. Les aspectsspatiaux et temporels du mouvement ne peuvent être dissociés. C’est une réelle ex-ploitation qui est justifiée de facto par l’existence même du système d’information.Les problèmes soulevés sont généralement d’un autre niveau d’abstraction que ceuxexhibés par la prise en compte auxiliaire et la technique est rarement leur aspectprincipal. Cette approche est résolument nouvelle et se décline, pour le moment, defaçon moins prolifique. Ces principaux représentants sont Pollen, où la mobilité estun médium de l’information et Spread et Cooltown, dans lesquels le mouvement estenvisagé comme une méthode d’adressage des informations.

La figure 11 dresse un classement des différentes techniques de prise en compteinformatique du mouvement selon les critères évoqués précédemment en indiquant,dans les feuilles de l’arbre, les cas étudiés correspondant.

INRIA


spatialetemporelle

prediction

adressage communication

fondamentale

prediction configuration

Durée de voisinage (PAN)Durée de voisinage (ad hoc)Anticipation du handover DREAM LAR

Pollen

Prise en compte du mouvement

auxiliaire

DREAMRéservation de ressources

SpreadCooltown

FIG. 11 – Taxonomie de la prise en compte du mouvement

Il est important de noter que si les cas de prise en compte fondamentale restenten nombre limité, ils constituent aussi un véritable renouveau dans le domaine. Ilsdevraient d’ailleurs permettre la naissance d’applications radicalement novatrices etdevraient susciter, de ce fait, un intérêt important.

RR n˚4720


Références

[1] G. D. Abowd, C. G. Atkeson, J. Hong, S. Long, R. Kooper, and M. Pinkerton.Cyberguide: a Mobile Context-Aware Tour Guide. ACM Wireless Networks,3:421–433, October 1997.

[2] P. Agrawal, D.K. Anvekar, and B. Narendran. Optimal prioritization of hando-vers in mobile cellular networks. In Proceedings of the fifth international sym-posium on Personnal Indoor and Mobile Radio Communications (PIMRC’94),volume 4, pages 1393–8. IEEE, September 1994.

[3] Paramvir Bahl and Venkata N. Padmanabhan. Radar: An in-building rf-baseduser location and tracking system. In Proceedings of the Infocom 2000, vo-lume 2, pages 775–784. IEEE, March 2000.

[4] M. Banâtre and F. Weis. SIS: a new paradigm for mobile computer systems.In Proceedings of the Information Society Technologies Conference (IST’99),November 1999.

[5] Stefano Basagni, Imrich Chlamtac, R. Violet Syrotiuk, and Barry A. Wood-ward. A Distance Routing Effect Algorithm for Mobility. In Proceedings ofthe ACM/IEEE International Conference on Mobile Computing and Networ-king (MOBICOM), pages 49–64, Dallas, TX, USA, October 1998.

[6] N. Bulusu, J. Heidemann, and D. Estrin. Gps-less low cost outdoor locali-zation for very small devices. Personal Communications Magazine, SpecialIssue on Networking the Physical World, October 2000.

[7] G. Chen and D. Kotz. A Survey of Context-Aware Mobile Computing Re-search. Technical Report TR2000-381, Department of Computer Science,Dartmouth College, 2000.

[8] Tsu-Wei Chen and Mario Gerla. Global State Routing: A New RoutingScheme for Ad-Hoc Wireless Networks. In Proceedings of the Internatio-nal Conference on Communications (ICC’98), Atlanta, GA, USA, June 1998.IEEE.

[9] P. Couderc, A-M. Kermarrec, and M. Banâtre. Approches adaptatives en mo-bilité : une synthèse. Technical Report 1276, IRISA, November 1999.

[10] Paul Couderc. Mobilité contextuelle dans les systèmes d’information. PhDthesis, Université de Rennes 1, December 2001.

INRIA


[11] B. P. Crow, I. Widjaja, J. G. Kim, and P. T. Sakai. IEEE 802.11 Wireless LocalArea Network. IEEE Communications Magazine, 35(9):116–126, September1997.

[12] P. H. Dana. Global positioning system overview. Available athttp://www.colorado.edu/geography/gcraft/notes/gps/gps_f.html, 2000.

[13] Laura Marie Feeney. A Taxonomy for Routing Protocols in Mobile Ad HocNetworks. Technical Report T99/07, Swedish Institute of Computer Science,Sweden, October 1999.

[14] George H. Forman and John Zahorjan. The challenges of mobile computing.Technical Report TR-93-11-03, Computer Science and Engineering, Univer-sity of Washington, march 1994.

[15] David Gelernter. Generative communication in linda. ACM Transactions onProgramming Languages and Systems, 7(1):80–112, January 1985.

[16] Mario Gerla, G. Pei, Sung-Ju Lee, and C-C Chiang. On-Demand MulticastRouting Protocol (ODMRP) for Ad Hoc Networks. Internet Draft, draft-ietf-manet-odmrp-00.txt, November 1998.

[17] N. Glance, D. Snowdon, and J-L. Meunier. Pollen: Using people as a commu-nication medium. Computer Networks, 35(4):429–442, February 2001.

[18] J. Haartsen, M. Naghshineh, J. Inouye, O. Joeressen, and W. Allen. Bluetooth:Vision, Goals, and Architecture. Mobile Computing and Communications Re-view, 2(4):38–45, October 1998.

[19] David B. Johnson and David A. Maltz. Dynamic Source Routing in Ad HocWireless Networks. In Imielinski and Korth, editors, Mobile Computing, vo-lume 353. Kluwer Academic Publishers, 1996.

[20] R. Kalden, I. Meirick, and M. Meyer. Wireless Internet Access Based onGPRS. IEEE Personal Communications, 7(2):8–18, April 2000.

[21] Randy H. Katz. Adaptation and mobility in wireless information systems.IEEE Personal Communications, 1:6–17, 1994.

[22] T. Kindberg, J. Barton, J. Morgan, G. Becker, D. Caswell, P. Debaty, G. Gopal,M. Frid, V. Krishnan, H. Morris, J. Schettino, B. Serra, and M. Spasojevic.People, Places, Things: Web Presence for the Real World. In Proceedings ofthe Third Annual Workshop on Wireless and Mobile Computer Systems andApplications (WMCSA’2000), December 2000.

RR n˚4720


[23] Young-Bae Ko and Nitin H. Vaidya. Location-Aided Routing (LAR) in MobileAd Hoc Networks. In Proceedings of the ACM/IEEE International Conferenceon Mobile Computing and Networking (MOBICOM), pages 49–64, Dallas,TX, USA, October 1998.

[24] Xavier Lagrange, Philippe Godlewski, and Sami Tabbane. Réseaux GSM-DCS. 4ème edition, 1999.

[25] Sung-Ju Lee, William Su, and Mario Gerla. Ad Hoc Wireless Multicast withMobility Prediction. In Proceeding of IEEE ICCCN’99, pages 4–9, Boston,MA, USA, October 1999.

[26] Ulf Leonhardt. Supporting Location-Awareness in Open Distributed Systems.PhD thesis, Department of Computing - Imperial College of Science, Techno-logy and Medicine - University of London, May 1998.

[27] Ben Liang and Zygmunt J. Haas. Prediction Distance-Based Mobility Mana-gement for PCS Networks. In Proceedings of INFOCOM’99. IEEE, March1999.

[28] George Y. Liu and Gerald Q. Maguire Jr. A Class of Mobile Motion PredictionAlgorithms for Wireless Mobile Computing and Communications. MobileNetworks and Application, 1(2):113–121, 1996.

[29] N. Marmasse and C. Schmandt. Location-aware information delivery withcomMotion. In Proceedings of the Second Symposium on Handheld and Ubi-quitous Computing (HUC’2000), pages 157–171, September 2000.

[30] David L. Mills. Internet Time Synchronization: the Network Time Protocol.IEEE Transactions on Communications, 39(10):1482–1493, October 1991.

[31] Shree Murthy and J.J. Garcia-Luna-Aceves. An Efficient Routing Protocol forWireless Networks. Mobile Networks and Applications, 1(2):183–197, 1996.

[32] B. Narendran, P. Agrawal, and D.K. Anvekar. Minimizing cellular handoversfailures without channel utilization loss. In Proceedings of GlobeCOM’94,volume 3, pages 1679–85. IEEE, 1994.

[33] Vincent D. Park and M. Scott Corson. A highly adaptive distributed routingalgorithm for mobile wireless networks. In Proceedings of INFOCOM, Kobe,Japan, April 1997. IEEE.

[34] Charles E. Perkins and Pravin Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers. In Pro-

INRIA


ceeding of the Conference on Communications Architectures, Protocols andApplications (SIGCOMM’94), pages 234–244. ACM, 1994.

[35] Charles E. Perkins and Elizabeth M. Royer. Ad-hoc On-Demand DistanceVector Routing. In Proceedings of the 2nd Workshop on Mobile ComputingSystems and Applications, pages 90–100, New Orleans, LA, USA, February1999. IEEE.

[36] S. Pradhan, C. Brignone, J-H. Cui, A. McReynolds, and M. T. Smith. Websi-gns: Hyperlinking Physical Locations to the Web. IEEE Computer Magazine,34(8):42–48, August 2001.

[37] M. Rahnema. Overview Of The GSM System and Protocol Architecture. IEEECommunications Magazine, 31(4):92–100, April 1993.

[38] N. Ryan and J. Pascoe. FieldNote: a Handheld Information System for theField. In Proceedings of the First International Workshop on TeleGeoProces-sing (TeleGeo’99), May 1999.

[39] A. Schmidt and M. Beigl. There is more to context than location: Environmentsensing technologies for adaptive mobile user interfaces, 1998.

[40] William Su and Mario Gerla. IPv6 Flow Handoff in Ad Hoc Wireless Net-works Using Mobility Prediction. In Proceedings of IEEE GLOBECom’99,pages 271–275, Rio de Janeiro, Brazil, December 1999.

[41] William Wei-Lien Su. Motion Prediction in Mobile/Wireless Networks. PhDthesis, University of California, Los Angeles, CA, USA, 1999.

[42] David Touzet, Frédéric Weis, and Michel Banâtre. Accès à l’information enubiquité numérique. Technical Report 1460, IRISA, May 2002.

[43] Arnaud Troël, Michel Banâtre, Paul Couderc, and Frédéric Weis. PredictiveScheme for Proximate Interactions. In Proceedings of the International Work-shop on Smart Appliances and Wearable Computing (IWSAWC’01), pages235–239, Mesa, AZ, United States, April 2001.

[44] R. Want, A. Hopper, V. Falcão, and J. Gibbons. The Active Badge Loca-tion System. ACM Transactions on Information Systems, 10:91–102, January1992.

[45] R. Want, B. N. Schilit, N. I. Adams, R. Gold, K. Petersen, D. Goldberg, J. R.Ellis, and M. Weiser. An Overview of the ParcTab Ubiquitous ComputingExperiment. IEEE Personal Communications, 2(6):28–33, December 1995.

RR n˚4720


[46] A. Ward, A. Jones, and A. Hopper. A new location technique for the activeoffice. In Proceedings of Mobicom’97, September 1997.

[47] M. Weiser. Some Computer Issues in Ubiquitous Computing. Communica-tions of the ACM, 36(7):74–84, July 1993.

INRIA

Unité de recherche INRIA Lorraine, Technopôle de Nancy-Brabois, Campus scientifique,615 rue du Jardin Botanique, BP 101, 54600 VILLERS LÈS NANCY

Unité de recherche INRIA Rennes, Irisa, Campus universitaire de Beaulieu, 35042 RENNES CedexUnité de recherche INRIA Rhône-Alpes, 655, avenue de l’Europe, 38330 MONTBONNOT ST MARTIN

Unité de recherche INRIA Rocquencourt, Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY CedexUnité de recherche INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902 SOPHIA-ANTIPOLIS Cedex

ÉditeurINRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France)

http://www.inria.frISSN 0249-6399

Documents

Prise en compte du mouvement dans les systèmes de ... · prise en compte. Nous verrons qu’elle dépasse le cadre des systèmes adaptatifs. Mots-clé : mobilité, communications