These Oudidi
These Oudidi
These Oudidi
N dordre attribu :
THSE
pour obtenir le grade de Docteur en Sciences Appliques
Spcialit : Informatique
Prpare au laboratoire : Systmes dInformation Multimdia et Mobile lEcole
Nationale Suprieure dInformatique et dAnalyse des Systmes
Prpare par :
Kamal OUDIDI
TITRE:
PES lENSIAS
Pr.
Pr.
Pr.
Pr.
Pr.
PES l ENSIAS
PES lINPT
PES lENSIAS
PES la FSTS
PES lENSIAS
Prsident
Rapporteur
Rapporteur
Rapporteur
Examinateur
Directeur de thse
Remerciements
On parvient rarement ses fins par ses propres moyens ; il faut toujours
compter sur quelqu'un d'autre
Du diable au cur, Marie-Claude Bussires-Tremblay.
En premier lieu, je remercie le Bon Dieu de mavoir donn la force et le courage pour
accomplir ce travail et qui ma procur ce succs.
Ce travail a t ralis au sein du Laboratoire Laboratoire Systmes d'Information
Multimdia et Mobile (SI2M) de lEcole Natinale dInformatique et dAnalyse des
Systmes de Rabat entre Jnavier 2007 et Mars 2010 sous la direction du professeur
Mohammed El Koutbi.
Mes premiers remerciements iront Mohammed El Koutbi, pour mavoir soutenu
durant mon stage de DESA et mes trois annes de thse. Jaimerais lui adresser mes plus
vifs remerciements pour tout son dynamisme et ses comptences scientifiques qui m'ont
permis de mener bien cette tude. Ce travail naurait jamais pu aboutir sans lui, qui a
toujours su me consacrer des moments de son temps, me guider et me conseiller, et me
tmoigner son soutien et sa confiance. Je souhaite lui transmettre l'expression de ma
reconnaissance et ma plus profonde gratitude.
Je remercie tout particulirement les membres de mon jury de thse, qui ont accept
de juger ce travail et de participer au jury. Mohamed Dafir ECH-CHERIF EL KETTANI,
Najib NAJA et Mostafa BELKASMI, mes rapporteurs, ont eu la patience et lnergie
ncessaire la lecture de ce manuscrit et je les en remercie vivement. Leurs remarques et
le recul ainsi apport mont t bnfique. Jadresse aussi mes trs sincres
remerciements Abdelhak MOURADI de me faire lhonneur de sintresser ce travail
et davoir prsid le jury. Je remercie vivement Abdelkrim HAQIQ
pour lintrt quil a bien voulu porter ce travail, pour avoir accept de faire partie de
jury, et pour les temps quil a passs dans nos discussions si fructueuses.
Ces annes de travail nauraient pas t les mmes sans la prsence de tant de
personnes agrables ctoyer au laboratoire, commencer par tous les membres de
lquipe SI2M, mais aussi les membres des autres laboratoires et le personnel
administratif. Totalement en vrac, merci donc vous tous. Je leur exprime ma profonde
sympathie et leur souhaite beaucoup de bien et de bonne chance.
Durant ma thse, et paralllement mes activits professionnelles, jai pu avoir le
plaisir de dcouvrir les joies de travail Maroc Telecom. Mes amis de travail mont
ouvert lesprit et offert de trs bons moments. Il sagit donc dune exprience sans prix.
Jadresse bien videmment mes remerciements ma famille, mes parents, mes frres,
mes surs, mais aussi mes amis qui ont tous su me soutenir sans insister et sinformer
de ltat davancement de mes travaux sans tre trop curieux.
Je ne pourrais clturer ces remerciements sans me retourner vers les tres qui mes sont
le plus chers, qui ont eu un rle essentiel et continu pendant ma russite, et qui sans eux
aucune russite naurait t possible. Jadresse de tout mon coeur mes remerciements
mes chrs parents qui furent toujours mon seul exemple, je suis infiniment reconnaissant
pour leurs amours, leurs soutiens morals malgr la distance. Et plus que a, leurs
encouragements tre toujours le meilleur. Je veux leur dire que leurs beaux sourires
seront toujours ma source d'espoir et m'inciteront toujours penser amliorer chaque
lendemain. Quils trouvent dans ce travail le fruit de leur travail. Je ne connais pas de
terme assez fort pour remercier ma merveilleuse pouse. Je te remercie Fouzia pour ton
humanisme, tes encouragements, et ton soutien aux moments les plus difficiles. Je te
remercie aussi pour mavoir toujours pouss en avant, faisant fin de mes doutes et mes
objections.
Oudidi
Ddicace
Je ddie ce travail mes parents. Aucun mot nest assez fort pour leur exprimer la
reconnaissance sincre que je leur porte pour la richesse de leurs enseignements.
Merci du fond du coeur.
II Contribution................................................................................................. 50
4 Nouvelle approche pour la mesure de la mobilit dans les Manets
51
Introduction .....................................................................................................................51
4.1 Modles de mobilit...................................................................................................51
4.2.1 Les modles de mobilit d'entit. .........................................................................53
4.2.2 Modle de mobilit de groupe. ............................................................................58
4.2.3 Discussion sur les modles de mobilit................................................................63
4.5 Les mtriques de mobilit : ........................................................................................66
4.5.1 Les mtriques directes .........................................................................................66
4.5.2 Les mtriques drives ........................................................................................67
4.5.3 Nouvelle Mtrique pour la mesure de la mobilit.................................................69
4.5.4 Simulations et rsulats .........................................................................................74
Conclusion.......................................................................................................................84
5 Mobilit et Routage dans les Manets
86
Introduction .....................................................................................................................87
5.1 Les indicateurs de mesure des performances rseau....................................................88
5.2 Amlioration de la version standard du protocole OLSR ............................................88
5.2.1 Lalgorithme standard de selection des MPRs......................................................89
5.2.2 Nouvelles mtriques pour la selection des MPR ..................................................90
5.2.3 Simulation et resultats .........................................................................................94
5.3 Evaluation des performance du protocole Modifi (MobOLSR) .................................95
Conclusion.......................................................................................................................99
6 Nouvelle mtrique compose pour la Qos dans les Manets
100
Introduction ...................................................................................................................101
6.1 Routage avec Qualit de service ...........................................................................102
6.2 Contraintes du routage avec QoS..........................................................................104
6.3 Nouvelles Mtriques composes pour la Qos dans les Manets ..............................107
6.4 Simulations et rsultats.............................................................................................112
6.4.1 Simulation 1 ......................................................................................................112
6.4.2 Simulation 2 ......................................................................................................113
Conclusion.....................................................................................................................123
7 Conclusion et perspectives
122
Conclusion & perspectives.............................................................................................123
III Annexes
A Simulateur NS2 ..................................................................................... 130
B Language AWK....................................................................................... 139
C Codes sources ...................................................................................... 142
D Bibliographies....................................................................................... 149
Chapitre
Introduction
Friedrich Hegel Rien de grand ne s'est accompli dans le monde
sans passion.
Extrait d' Introduction la philosophie de l'histoire
Aloha1 ! cest avec cette exclamation exotique que Norman Abramson est accueilli
en 1970 Hawa. Abramson travaille sur une architecture rseau permettant la
communication et la coordination des rservations htelires sur les diffrentes les. Aprs
quelques mois, les travaux dAbramson aboutissent au systme ALOHA [1], qui fut lune
des premires architectures rseau et surtout la premire architecture sans fil base sur la
commutation de paquets. Loriginalit rside dans la simplicit du mcanisme de partage
du mdium unique utilis entre les utilisateurs du rseau au lieu de lattribution dune
frquence chaque transmission afin dviter le problme des collisions.
Le rseau ALOHAnet [2] fut dploy ds la fin de lanne 1970 luniversit de
Hawaii. En 1972, il devint le premier rseau tre connect un autre rseau
particulirement connu dans lhistoire informatique : ARPANET [5,6].
En 1972, une volution de ce protocole, Slotted Aloha [7] amliore les performances
des transmissions radiofrquences. Le dveloppement des rseaux en mode paquet cessera
de prendre de lampleur, donnant naissance en 1980 la norme Ethernet [3,4] encore
largement utilise ce jour.
Dautres travaux raliss cette priode ainsi que des annes plus tard sont tout aussi,
voire plus importants que ce qua ralis Abramson.
En France, ds 1850, le physicien cossais James Clerk Maxwell (18311879) publie,
sans le savoir, les bases des tlcommunications modernes grce aux clbres quations
diffrentielles dcrivant la nature des champs lectromagntiques.
Heinrich
Rudolph
Hertz
(18571894),
physicien
allemand,
dmontre
exprimentalement lexistence des ondes de Maxwell en 1877 au moyen de loscillateur de
Hertz. En 1893, Nikola Tesla, inventeur de la radiocommunication, montre que des
courants haute frquence peuvent etre utiliss pour tablir des communications
distance.
Introduction
Baran et Kleinrock ont tous deux introduit les principes de la commutation de paquets
au dbut des annes 1960 [8] et Kleinrock a en outre normment contribu la cration
dARPANET en 1969 [9]; Cerf et Kahn ont dvelopp TCP/IP partir de 1973 [11] ;
Berners- Lee a invent le World Wide Web en 1990 [12], ce qui a t le dclencheur de la
popularit dInternet.
Sil nest pas lunique pionnier, Abramson fait nanmoins partie de ce groupe de
chercheurs qui a rvolutionn les rseaux. Alors mme que les rseaux constituaient un
nouveau domaine de recherche, il sest intress au cas des rseaux sans fil avec toutes les
contraintes quils impliquent. Et trente ans plus tard, le Wi-Fi [13] est apparu et a permis la
dmocratisation des rseaux sans fil.
Au Maroc, le secteur des tlcommunications a dmarr, en 1883, par linstallation de
la premire ligne tlphonique Tanger. Lanne 1907 a t marque par lintroduction du
Tlgraphe Sans Fil (TSF) et la Cration de la Socit Marocaine des Tlgraphes (SMT).
En 1914, le Dahir du 22 fvrier du Sultan Moulay Youssef a adopt la Cration de lOffice
de la Poste, du Tlgraphe et du Tlphone (PTT), premier tablissement public des
Postes des Tlgraphes et des Tlphones. La Cration du Ministre des Postes,
Tlgraphes et Tlphones a t dcid en 1956 par le Dahir N1-56-269 du 28 octobre du
Roi Mohammed V-1927-1961).
A partir de 1997, les tlcommunications ont connu une grande volution, par
ladoption de la loi 24-96 amorant la rforme du secteur de la Poste et des
Tlcommunications. La rforme visait louverture du march aux initiatives prives et aux
promoteurs nationaux et internationaux. En remplacement de lOffice Nationale des Postes
et Tlcommunications , la loi 24-96 a cre la socit anonyme Itissalat Al Maghrb et
confi les missions de rgulation une nouvelle entit : LAgence Nationale de Rgulation
des Tlcommunications (ANRT). En 1999 le secteur des tlcommunications a entam
concrtement sa libralisation avec loctroi de la 2me licence GSM. Larrive de Wana en
juin 2008 a galement suscit un boom dans le parc de la tlphonie Mobile1 Marocain. Le
Maroc comptait au 30 juin 1999, 158270 abonns GSM. Ils sont estims aujourdhui
27 046 milliers (Mars2010) avec un taux de pntration gal 85,82 % [14].
Selon les chiffres de la GSA (Global mobile Suppliers Association). Les technologies
mobiles issues de la branche GSM et qui englobent les technologies GPRS, EDGE et
WCDMA/HSPA, continuent de progresser sur le march mondial et le font savoir. La GSA
estime 4.2 milliards le nombre d'abonnements mobiles GSM/WCDMA/HSPA [15] (sur
environ 4.6 milliards), soit une part du march de 90 % (contre 84.6 % en 2007). 97 % des
rseaux 3G ont volu vers l'amlioration HSDPA (High Speed Downlink Packet Access)
dite aussi 3G+ , avec un dbit thorique de 14 Mb/s.
La 4G LTE (Long Term Evolution) est une norme de rseaux sans fil qui est bien
suprieure aux dbits des normes actuelles qui sont la 3G, le HSDPA. La technologie LTE
doit remplacer l'horizon 2010 les rseaux HSPA en cours de dploiement. Avec les
premiers dploiements prvus en 2010, au Japon notamment, ces rseaux mobiles pourront
fournir des dbits de 100 Mb/s en lien descendant et 50 Mb/s en lien montant [16], avec
des temps de latence encore plus courts et ouvrant la voie de nouveaux usages. La
tlvision, internet, ainsi que les applications utilisant le streaming vont prendre un second
souffle.
1
Le parc du mobile regroupe les abonns aux services de la tlphonie mobile utilisant les rseaux 2G et 3G.
Introduction
Le domaine de recherche dans les rseaux mobiles sans fil est toujours aussi actif.
Introduction
routeur et dun terminal en mme temps. Pour cela, un protocole de routage distribu est
ncessaire.
Plusieurs protocoles de routage ont t proposs pour les rseaux mobiles ad hoc. Ces
protocoles de routage peuvent tre classifis, suivant la manire de cration et de
maintenance des routes lors de l'acheminement, selon plusieurs critres. Le groupe de
travail MANET (Mobile ad hoc NETwork) de l'IETF (Internet Engineering Task Force) se
proccupe de la normalisation des protocoles ad hoc fonctionnant sous IP. Dans ce cadre,
AODV, OLSR, DSR sont actuellement lobjet dun RFC grce leurs caractristiques
intressantes, ces protocoles fonctionnent en mode best effort. Cependant, ils ne permettent
pas de garantir une qualit de service (QoS).
Pour certaines applications telles que les applications multimdias ou temps rels le
service best effort nest pas du tout suffisant. De telles applications exigent des garanties
en terme de certains critres de qualit de service (un minimum de bande passante, un dlai
max ne pas dpasser, etc.). En effet, il semble important dadapter les MANETs pour
supporter un certain niveau de QoS dans le but de dploiement des applications exigeantes.
Toutes ces exigences crent un nouveau cadre dtude pour les rseaux ad hoc, et cest
dans cette perspective o sinscrivent les travaux effectus pendant cette thse.
Introduction
2 Confrences Internationales
6- K.oudidi, A.Hajami and M.Elkoutbi QoS Routing Using OLSR Protocol in proceedings
of the IASTED International Conference on Wireless and Optical Communications
(WC2010, Alberta Banff, Canada, July 14-15, 2010. (ActaPress)
7- A.Hajami, K.oudidi and M.Elkoutbi An enhanced algorithm for MANET clustering
based on Multi hops and Network Density In proceedings of NOTERE. May 2010 (to
appear)
8- K.oudidi, A.Hajami and M.Elkoutbi A New Composite Metric For QoS Satisfying Both
Mobility And Bandwidth Constraints In Manets In proceedings of African Conference on
Research in Computer Science and Applied Mathematics CARI10, Yamoussoukro- 2010,
Rabat, Cte d'Ivoire. (to appear)
9- K.oudidi, A.Hajami and M.Elkoutbi Towards a QoS Aware Routing protocol
For MANETs in Proceedings of the International Conference Next Generation Networks
(NGNs10) , Mararkech, Maroc, 2010 (to appear)
10- K.Oudidi, M.Elkoutbi A Mobility Based Metric For Qos In Mobile Ad Hoc Netwoks
Proceedings of the IASTED International Conference on Wireless and Optical
Communications (WOC09), ISBN: 978-0-88986-793-2 Banff, Canada, July 6-8, 2009
pp11-18 (published at ActaPress)
11- K.Oudidi, M.ElKoutbi,Une mtrique de QoS Contraintes Multiples pour les MANETs
in Proceedings of the International Conference Next Generation Networks (NGNs09) ,
Rabat, Maroc June 04 06, 2009 pp 74-82
12- K.oudidi, N.enneya, A. Loutfi, and M.Elkoutbi Mobilit et Routage OLSR, In
proceedings of African Conference on Research in Computer Science and Applied
Mathematics CARI08, pp. 646-657, October 2008, Rabat, Morocco.
13- N.enneya, K.oudidi, and M.Elkoutbi, A New Mobility Metrics for MPRs Selection in the
OLSR Protocol, In Proceedings of African Conference on Research in Computer Science
and Applied Mathematics CARI08, pp 639-646, October 2008, Rabat, Morocco.
14- N. Enneya, K. Oudidi, M. El Koutbi, Network Mobility in Ad hoc Networks, In
Proceedings of IEEE International Conference on Computer and Communication
Engineering ICCCE08, pp. 969-973, 13-15 May 2008, Kuala Lumpur, Malaysia.
15- K. Oudidi, N. Enneya, and M. ElKoutbi, Une Mesure Intelligente de la Mobilit dans les
Rseaux Ad Hoc, In Proceedings du 5me confrence sur les systmes intelligents :
Thories et applications SITA08, INPT, 05-07 Mai, 2008, Rabat, Maroc.
16- N. Enneya, K. Oudidi, and M. ElKoutbi, Network Mobility Behavior in Mobile Ad-hoc
Networks, In Proceedings of Workshop Next Generation Networks NGN08, Fez,
Morocco.
17- K. Oudidi, A. Mouchtaki, A. Hajami, N. Enneya, M. ElKoutbi, Vers une amelioration du
protocole de routage AODV, 1st International Workshop on Mobile Computing and
Applications, NOTERE, June 4th, 2007, Marrakech, Morocco.
3 Confrences Nationale
18- K. Oudidi, A.Hajami et M. ElKoutbi, SC-LEACH: Modle de scurit lger pour la
communication dans les rseaux de capteur sans fils bass sur les clusters WorkShop
sur les Technologies de l'Information et de la Communication.WOTIC09. 24-25 dec 2009 Agadir Maroc
19- K. Oudidi, A.Ouacha et M.El Koutbi Une Mtrique de QoS base sur la mobilit et
lnergie pour les MANETs Proceeding de la Premires Journes Doctorales en
Technologies de l'Information et de la Communication (JDTIC 2009) , Rabat, Maroc, 1618 juillet 2009
20- K.oudidi, N.enneya et M.Elkoutbi, " Vers une amlioration du protocole de routage
OLSR", 2me dition des Journes dInformatique et Mathmatiques Dcisionnelles
JIMD2, ENSIAS, Rabat, 3-5 juillet 2008.
21- N.enneya. K.oudidi, and M.Elkoutbi, A Realistic Mobility Measure for Mobile Ad hoc
Networks, 2me dition des Journes dInformatique et Mathmatiques Dcisionnelles
JIMD2, ENSIAS, Rabat, 3-5 juillet 2008.
22- N.enneya K.oudidi and M.Elkoutbi Enhancing Performance of the OLSR Protocol, In
Proceedings du Workshop sur les technologies de linformation et de la communication,
WOTIC07, ENSIAS, 5-6 Juillet, 2007, Rabat, Maroc.
23- K.oudidi, N.enneya and M.Elkoutbi, Mesure de la mobilit dans les rseaux Ad hoc, In
Proceedings du Workshop sur les Technologies de lInformation et de la Communication,
WOTIC07, ENSIAS, 5-6 Juillet, 2007, Rabat, Maroc
Premire partie
tat de lart
Chapitre
Introduction
prsentation globale de la norme 802.11. Nous allons voir les classifications principales
des rseaux sans fil et les diffrentes technologies utilises dans chaque catgorie et nous
introduisons le concept des rseaux mobiles ad hoc et certaines de leurs proprits, sur
lesquelles nous reviendrons plus en dtail par la suite. Les notions lies au routage dans ce
type de rseaux mobiles et une tude du protocole OLSR qui est au centre des travaux de ce
mmoire seront abordes la fin de ce chapitre servant ainsi dintroduction aux garanties
de la Qos dans ces rseaux.
2.1 Ethernet
Ethernet a t standardis sous le nom IEEE 802.3 [3,4]. C'est maintenant une norme
internationale : ISO/IEC 8802-3. Ethernet est un standard de transmission de donnes pour
rseau local. Historiquement, ses crateurs ont tir leur inspiration dALOHA [1], et
certaines ressemblances entre les deux spcifications permettent den attester. Il sagit
dsormais de la norme de rseau filaire sans conteste la plus rpandue, et ce, depuis plus de
vingt ans.
Le cble sur lequel est branche une interface Ethernet constitue un mdium partag par
toutes les interfaces prsentes sur ce cble. Il convient donc de disposer dun protocole
daccs au canal, qui est ici CSMA/CD (Carrier Sense Multiple Access / Collision
Detection). CSMA/CD permet de dtecter une collision sur le mdium ; lorsque cest le cas,
un mcanisme de rsolution de la collision utilisant un algorithme dattente exponentiel par
calcul binaire (binary exponential backoff) est utilis. Ni CSMA/CD ni cet algorithme ne
seront dtaills ici, pour des raisons de concision.
Alors quinitialement Ethernet supportait un dbit de 10 Mb/s, la norme a t modifie
pour permettre des 100 Mb/s avec Fast Ethernet, puis des 1000 Mb/s avec Gigabit Ethernet
sur cuivre. Les cblages utiliss ont eux aussi volu dans le temps. Le succs rencontr
par Ethernet sexplique relativement naturellement : il sagit dune technologie simple,
facile mettre en place, fiable et peu coteuse. Aucune configuration particulire ne
savre ncessaire. En outre, la norme a volu afin de rpondre aux attentes grandissantes
en terme de dbit, tout en gardant une compatibilit descendante, permettant de conserver
le matriel dj dploy.
Ethernet a nanmoins un inconvnient assez visible : la ncessit dun cble pour relier
deux stations. Or, le cble rend toute mobilit extrmement complexe. Cet inconvnient
ntait pas majeur il y a quelques annes, mais lapparition des rseaux sans fil a chang le
mode de vie des utilisateurs. Ainsi, de nombreuses personnes considrent-elles dsormais
quun cble est une contrainte importante[92].
2.2 802.11
Lorsquil est apparu quil existait une demande pour les rseaux sans fil locaux, de
nombreuses solutions ont t mises sur le march. Les problmes de compatibilit ne
pouvant quempcher une dmocratisation des technologies sans fil, un processus de
standardisation a eu lieu et a abouti la norme 802.11 [20], connue galement sous le nom
de Wi-Fi. Les dbits atteints vont de 1 Mb/s 54 Mb/s, et bientt 248 Mb/s suivant les
techniques et les ventuelles extensions de la norme employes. Les portes prvues
varient entre quelques dizaines et quelques centaines de mtres en fonction de la vitesse
choisie et de lenvironnement.
11
La norme originelle 802.11 date de 1997. Elle dcrit les couches physiques et MAC
pour un dbit allant jusqu 2 Mbit/s en radio, dans la bande des 900MHz. Des extensions
ont t publies depuis. Celles-ci viennent lui ajouter des amliorations et des modes de
fonctionnement plus performants.
Plus dune dizaine damendements ont t approuvs ou sont sur le point de ltre ; les
diffrents amendements varient entre amliorations en terme de dbit (802.11a [21],
802.11b [22], 802.11g [23], 802.11n [24]) et meilleurs mcanismes de scurit (802.11i
[25]), en passant par des spcificits lies aux rgulations de diffrents pays (802.11d [26],
802.11h [27], 802.11j [28]) ou encore lintgration de mcanismes de qualit de service
(802.11e [29]). La frquence trs importante de ces amendements a cependant tendance
crer une certaine confusion.
Cette technologie est dsormais extrmement rpandue, car la majorit des ordinateurs
portables en sont quips. En outre, tous les appareils un tant soit peu mobiles commencent
disposer dinterfaces 802.11; on peut notamment constater cette tendance sur les
tlphones portables.
Le tableau (2.1) reprsente les principales drives de la norme 802.11 et leurs
caractristiques :
Normes
802.11
802.11a
802.11b
Caractristiques
- Date de normalisation : 1997
- Bande de frquence : 2.4Ghz
- Dbit thorique = 2Mb/s, Rel < 1Mb/s
- Porte thorique : 100m
- Date de normalisation : 1999
- Bande de frquence : 5Ghz
- Dbit thorique = 54Mb/s, Rel=30Mb/s
- Porte thorique : 50m
- Spcificit : 8 canaux radio
- Date de normalisation : 1999
- Bande de frquence : 2.4Ghz
- Dbit thorique = 11Mb/s, Rel=6Mb/s
- Porte thorique : 100m
- Spcificit : 3 canaux radio
802.11e
802.11f
802.11g
802.11h
802.11i
802.11n
802.11k
802.11r
12
Dun point de vue technique, 802.11 est vu par les couches hautes de la pile rseau de la
mme faon quEthernet. Nanmoins, la couche physique, qui ne sera pas dtaille ici, est
extrmement complexe et la couche MAC fonctionne diffremment de celle dEthernet.
Cette dernire peut utiliser deux modes : DCF (Distributed Coordinated Function, fonction
de coordination distribue) ou PCF (Point Coordinated Function, fonction de coordination
par point daccs). PCF tant optionnel, cest gnralement DCF qui est mis en oeuvre.
DCF se base sur CSMA/CA (Carrier Sense Multiple Access / Collision Avoidance) [30].
Lamendement 802.11e [29] introduit un nouveau mode HCF (Hybrid Coordinated
Function), avec deux mthodes : EDCA (Enhanced Distributed Channel Access) et HCCA
(HCF Controlled Channel Access), cette seconde mthode tant optionnelle ; ces deux
mthodes dfinissent des classes de trafic, ce qui permet de modifier le comportement de
laccs au mdium en fonction de la priorit du trafic. Toujours pour des raisons de
concision, ces fonctions ne seront pas tudies plus en dtail ici.
Couche2 OSI
Couche liaison de
donnes
Couche1 OSI
Couche physique
FHSS DSSS IR
Wi-Fi
802.11b
Wi-Fi5
802.11a
...
13
La technologie 802.11 souffre de problmes qui ne lui sont pas spcifiques, mais qui
touchent toute technologie sans fil dans une mesure plus ou moins importante[43].
Consommation dnergie
Les signaux radio ont une puissance limite qui diminue avec la distance, mais aussi
avec les obstacles de lenvironnement tels que les murs. Des rglementations
gouvernementales participent en outre la limitation des puissances utilises. Il en rsulte
une porte relativement courte des donnes mises.
Interfrences
Deux communications sans fil simultanes peuvent interfrer entre elles et donc rendre
leurs signaux mutuels incomprhensibles. Il est donc ncessaire dviter dans la mesure du
possible toute communication simultane, et cest ce que ralise 802.11 avec CSMA/CA
[30]. Nanmoins, des facteurs extrieurs tels que dautres technologies sans fil ou des
appareils lectriques peuvent aussi contribuer des interfrences dans le cas o la bande de
frquences nest pas rserve cet usage. Ainsi, 802.11 et Bluetooth partagent tous deux la
bande de frquence de 2.4 GHz et lutilisation des deux technologies peut poser problme
[31].
Scurit
Par la nature mme du mdium utilis, il nest pas possible de contrler celui qui peut
couter les communications. Il faut donc supposer que toute donne transmise peut tre
intercepte, et un chiffrement peut savrer ncessaire. En outre, sans authentification, on
ne peut sassurer que les donnes reues nont pas t mises par une station tierce.
Un aspect plus problmatique de la scurit des rseaux sans fil est quil est
extrmement simple pour une station de bloquer totalement le rseau en mettant en
permanence des donnes afin de brouiller toute communication.
2.2.2 Problmes spcifiques 802.11
Au-del des difficults inhrentes toute technologie sans fil, 802.11 connait aussi des
problmes spcifiques lis la norme elle-mme. Ceux-ci peuvent tre dvoils dans le cas
14
En raison des algorithmes utiliss dans la couche MAC, une anomalie dans le
comportement de 802.11 existe et peut avoir un impact important sur les performances en
terme de dbit des stations [32]. En effet, des stations configures avec un taux de transfert
lev voient leur dbit diminuer lorsquune station utilise un taux de transfert plus bas.
Cela sexplique par le fait que la rpartition du temps doccupation du canal nest dans ce
cas pas quitable : toutes les stations ont autant de chance daccder au canal pour
lmission dune trame, mais une station avec un faible taux de transfert occupe le canal
plus longtemps, crant ainsi un dsquilibre.
Le problme des nuds cachs
Le problme des stations caches [33] est li au fait que la porte du signal nest pas
toujours suffisante pour permettre toutes les stations pouvant interfrer avec une mission
dtre informes de celle-ci.
Dans un rseau ad hoc bas sur 802.11, tous les mobiles devront travailler sur la mme
frquence sils veulent permettre une connectivit complte du rseau. De ce fait, les
situations de nuds cachs vont tre beaucoup plus nombreuses et plus frquentes. Une
illustration trs simple de ce problme est possible avec seulement trois stations A, B et C
positionnes comme dans la figure 2.2. A ne peut pas entendre C lorsquelle met vers B,
et donc A considre pouvoir utiliser le canal. En cas dmission de A, des collisions au
niveau de B seront donc causes.
15
Le problme des stations exposes [35] est, en quelque sorte, linverse du problme des
stations caches. Dans le cas des stations exposes, lmission dune station peut bloquer
lmission dune autre station alors que les deux destinations auraient pu recevoir les deux
trames sans difficult.
(((
(((
(
Position
Par exemple, avec le rseau illustr par la figure 2.3, si les nuds B et C voudraient
mettre respectivement vers A et D. En suivant le mcanisme de la DCF, celui qui a tir le
plus petit backoff va accder au canal et envoyer son paquet, alors que lautre dtectera la
porteuse du premier, et entrera en priode de defering. Pourtant, si B et C mettaient en
mme temps, le signal de B au niveau de A serait largement suprieur celui de C et
suffisant pour une rception correcte. La situation serait linverse au niveau du nud D,
qui recevrait correctement le paquet de C, malgr le lger bruit venant de B. Dans cette
situation, la DCF limite donc inutilement la bande passante totale du rseau. On peut noter
que certains travaux sintressent au problme, notamment [36] qui propose lutilisation
dun mcanisme de paralllle RTS pour le rsoudre en partie.
La zone grise
Lenvoi de trames en diffusion dans 802.11 est ralis un taux de transfert plus bas
que celui utilis pour les autres trames. Par exemple, 802.11b utilise des vitesses de
transmissions de 1 ou 2 Mbit/s pour les paquets quil diffuse (ex. les paquets Hello ou
RouteRequest) pour construire un certain nombre de routes dans le rseau, alors que les
paquets envoys en unicast (ex. paquets de donnes) peuvent atteindre jusqu 11 Mbit/s
sur ces routes.
Or, plus un taux de transfert est bas, plus la porte est importante, il est possible que des
mobiles pourtant porte des paquets de routage lents soient trop loin pour les paquets de
donnes rapides. Il en dcoule que les routes construites avec les paquets diffuss ne sont
pas forcement exploitable des dbits plus levs. La zone concerne (la soustraction de la
zone rapide la zone lente plus large) est appele zone grise et ce problme avait t
relev thoriquement et exprimentalement dans [37].
16
2.3.1 Modlisation
Un rseau mobile ad hoc peut tre modlis par un graphe Gt(Vt ,Et ) o :
17
Vt: reprsente l'ensemble des nuds (i.e. les units ou les htes mobiles) du rseau.
Et : modlise l'ensemble des connexions qui existent entre ces nuds. (Figure 2.5).
Si e = (u, v) Et , cela veut dire que les nuds u et v sont en mesure de
communiquer directement l'instant t [39].
18
High Performance Local Area Network type 1 (HiperLan 1) [41] est un standard de
lEuropean Technical Standard Institute (ETSI). Il dcrit le fonctionnement dquipements
travaillant dans la bande des 5.15-5.30 GHz et permettant datteindre des dbits de 23.5
Mbit/s sur une distance denviron 50 mtres. Larchitecture est totalement dcentralise. Il
ny a pas de notion de point daccs, mais les nuds HiperLAN 1 peuvent cependant avoir
des rles de passerelles. Les caractristiques les plus marquantes dHiperLAN 1 sont :
Le mcanisme daccs au mdium, qui gre les priorits. Il est possible dobtenir des
garanties de qualit de service, particulirement utiles pour les flux multimdias par
exemple ;
la possibilit dtendre le rseau au-del de la porte radio, par sauts successifs
(fonctionnement en cela trs semblable aux rseaux ad hoc, des nuds jouant le rle
dintermdiaires entre ceux qui sont trop loin pour communiquer directement).
Les fonctionnalits dHiperLAN 1 sont organises comme prsentes sur la figure 2.6.
Nous nentrerons pas dans les dtails de cette norme complexe, mais nous pouvons
remarquer nanmoins que le mcanisme daccs au mdium EY-NPMA (Elimination
19
Yield-Non Preemptive Multiple Access) est au coeur du systme. Cest lui qui permet en
particulier la gestion des priorits. Le fonctionnement de EY-NPMA est particulirement
intressant puisquil est prvu pour fonctionner dans un contexte ad hoc. Nous allons donc
le dcrire plus en avant. Il fonctionne en trois phases et un exemple est donn sur la figure
2.7 :
La phase de priorit : Cinq niveaux de priorit sont dfinis par la norme (de 0 pour le
plus prioritaire 4) et la phase de priorit est donc divise en cinq slots. Au dbut dun
nouveau cycle de transmission, tous les nuds qui veulent accder au canal vont envoyer
un burst de signalement, dont la date de dbut dpend de la priorit du paquet. Plus la
priorit est leve, plus le burst commence tt. Sur la figure, les nuds A, C et D ont une
priorit de 2, et le nud B a une priorit de 3. Lide est dcouter le canal tant que notre
priorit nous interdit dmettre notre propre burst de signalement. Si lon dtecte de
lactivit avant davoir pu mettre, cest que quelquun est plus prioritaire que nous, et lon
abandonne lide de transmettre pour ce cycle. Cest le cas du nud B sur la figure 2.2.
La phase dlimination : Il se peut que plusieurs nuds veulent mettre en mme
temps des paquets de priorits identiques. Il faut donc les dpartager. Pour cela, chaque
nud va poursuivre lenvoi de son burst de signalement pendant un nombre alatoire de
slots. Ce sera celui qui aura tir le plus grand nombre qui lemportera. Ds que lmission
de notre burst est termine, nous coutons le canal. Si nous y dtectons de lactivit, cest
quun autre nud a tir un plus grand nombre que nous, et nous abandonnons pour ce
cycle. Sur la figure, cest le cas du nud C .
La phase dcoute : Si toutefois il reste plusieurs nuds en lice, alors llimination va
se terminer dans la troisime phase. Un nombre alatoire de slots est choisi. Cest celui qui
aura tir le plus petit qui pourra transmettre. Chaque nud attend pendant la dure quil a
determine, en coutant le canal. Sil dtecte de lactivit alors quil na pas fini dattendre,
il sait que quelquun a tir un plus petit nombre que lui et nmettra pas durant ce cycle. Si
son attente se termine alors que le canal est toujours libre, alors il met. Sur la figure, cest
le nud D qui lemporte. Il faut noter que si le paquet est envoy en point point, il sera
acquitt par son rcepteur (ici le nud E).
Avec HiperLAN type 1, un mcanisme de routage multisauts est implant. Les nuds
envoient des paquets hello qui leur permettent de connatre leur voisinage. Ces
informations de voisinage sont propages dans tout le rseau et permettent ainsi un nud
den reconstruire la topologie.
Cest un protocole tat de lien qui utilise un systme de relais multipoints pour
optimiser les diffusions dinformations.
20
ou
te
at
se
d
c
im
in
Ph
a
se
Ph
a
Ph
a
se
de
d
l
pr
io
rit
io
n
Figure 2.6 Optimisation dun Hiperlan1 Figure 2.7 Laccs au canal avec EY-NPMA
2.4.2 HiperLAN 2
Bluetooth [19] est une technologie pour les communications sans fil courte distance.
La version 1.1 de la spcification a t standardise par lIEEE en 802.15.1, mais le
21
Bluetooth SIG [19] a continu dvelopper cette technologie et la version actuelle est la
version 2.1. De trs nombreux types dappareil peuvent disposer dune connectivit
Bluetooth : tlphones portables, ordinateurs, imprimantes, appareils photo numriques,
rcepteurs GPS, claviers et souris, consoles de jeu, etc. Les puces Bluetooth cotent peu
la fabrication. Par consquent, cet aspect conomique a contribu la large adoption de
cette technologie.
De par son cahier des charges, cette technologie est peu consommatrice dnergie. Le
revers de cette faible consommation est la courte porte des communications trois
classes existent, avec pour porte respectivement 10 m, 20 m et 100 m, la premire classe
tant gnralement celle utilise pour les puces et le faible dbit disponible jusqu 3
Mb/s. Une nouvelle version de Bluetooth est prvue, promettant un dbit pouvant atteindre
100 Mb/s. Les transmissions radio ont lieu sur la bande de frquence de 2.4 GHz, qui a
lavantage dtre mondialement disponible.
2.4.3.1 Piconet et scatternet
Toute communication entre deux priphriques Bluetooth a lieu dans un piconet [43]. Il
sagit dun rseau qui est cr automatiquement lorsque plusieurs priphriques se situent
porte lun de lautre ; un piconet est donc un rseau ad hoc. Lespace dadressage dans un
piconet est sur trois bits et il ne peut donc pas y avoir plus de huit membres dans un tel
rseau. Les communications dans un piconet ont lieu directement sur la couche 2 et IP
nest pas utilis.
Dans un piconet, un des priphriques joue le rle de matre, contrlant le rseau, et les
autres deviennent donc des esclaves. Tous les priphriques ont une horloge synchronise
sur celle du matre ; en outre, deux esclaves ne peuvent pas communiquer directement
entre eux et donc toute communication a lieu entre le matre et un esclave. Deux esclaves
peuvent ventuellement communiquer par lintermdiaire du matre.
Plusieurs piconets peuvent tre connects et former ainsi un scatternet, ce qui permet de
saffranchir de la limite de taille des piconets. Linterconnexion de deux piconets est
possible grce lintermdiaire dun membre des deux rseaux qui joue le rle de pont ;
celui-ci ne peut nanmoins tre matre que dans un piconet. Lutilisation dun scatternet
permet deux priphriques Bluetooth de communiquer malgr une distance importante
rendant impossible toute communication directe entre eux. Les scatternets restent
cependant limits au cadre de la recherche pour linstant, car Bluetooth ne spcifie pas
comment le routage est effectu dans un scatternet, et donc peu dimplmentations
existent.
2.4.3.2 Rseau local personnel
un rseau utilisant une autre technologie que Bluetooth typiquement, un rseau local
filaire. Ce membre, appel le point daccs, joue le rle de pont ou de routeur entre le
rseau Bluetooth et le second rseau, permettant aux autres membres du piconet daccder
au second rseau.
Rseau ad hoc : des utilisateurs PAN peuvent former spontanment un rseau ad hoc,
sans aucune infrastructure extrieure. Ils peuvent communiquer librement entre eux - une
communication entre deux esclaves passe toujours par le matre -, mais nont accs aucun
autre rseau. Le rseau ad hoc est donc limit au piconet.
Connexion entre deux utilisateurs PAN : une connexion point point entre deux
priphriques est ralise pour permettre une communication directe. Il sagit en ralit de
simuler lutilisation dun cble pour relier directement deux stations.
En pratique, il est relativement rare davoir plus de deux priphriques Bluetooth
communicant par IP dans une mme zone. La principale utilisation des PANs consiste
donc en une connexion entre deux priphriques afin quils communiquent par IP, lun des
deux priphriques jouant gnralement le rle de point daccs vers un autre rseau.
Conclusion
Ce chapitre a t ax sur le concept des environnements mobiles et l'utilisation de la
technologie de communication sans fil. L'volution rapide qu'a connue la technologie sans
fil rcemment, a facilit la mise en uvre dapplications mobiles et ne supportant pas
dinfrastructure prexistante (telles que les applications militaires) et a permis l'apparition
de nouveaux systmes de communication qui offrent plus d'avantages par rapport aux
systmes classiques. Les nouveaux systmes n'astreignent plus l'usager une localisation
fixe, mais lui permet une libre mobilit.
La comprhension parfaite de la communication utilise dans le nouvel environnement,
ncessite la comprhension des notions de base de la technologie sans fil comme
l'utilisation des ondes radio, la notion de bande passante, la rutilisation des frquences, la
porte d'une unit mobile, etc. Le but de ce chapitre a t de donner un aperu gnral sur
cette technologie qui ne cesse de crotre.
Les environnements mobiles sont caractriss par de frquentes dconnexions et des
restrictions sur les ressources utilises, surtout si tous les usagers du systme sont mobiles
ce qui est le cas pour les rseaux ad hoc. Ces limitations transforment certains problmes,
ayant des solutions videntes dans l'environnement classique, en des problmes complexes
et difficiles rsoudre. Parmi ces problmes figure le problme de routage que nous allons
discuter dans le deuxime chapitre.
23
Chapitre
Algorithmes et architectures de
routage
Introduction
Le routage par inondation [43] est probablement la mthode de routage la plus triviale :
chaque routeur recevant un paquet le rmet sur toutes les interfaces si le routeur nest pas la
destination du paquet. Afin que la fin de linondation soit garantie, plusieurs techniques
peuvent tre employes.
Une premire solution est dutiliser un champ de dure de vie (time to live) dans les
paquets transmis, champ qui est dcrment chaque retransmission du paquet. Lorsque la
valeur du champ est nulle, alors le paquet nest pas retransmis. Une difficult pour lmetteur
est alors dtablir quelle valeur initiale choisir pour atteindre la destination sans surcharger le
rseau; une valeur arbitraire est gnralement choisie. Le protocole IP possde un tel champ
qui a pour valeur maximale 255.
Une seconde approche, qui peut complmenter la premire, consiste viter denvoyer une
seconde fois les paquets dj retransmis. Chaque paquet doit donc disposer dun identifiant
il sagit gnralement de ladresse de la source couple avec un numro de squence
incrment chaque paquet mis par la source que les routeurs utilisent afin de dterminer
si le paquet a dj t reu et retransmis.
Un paquet avec un identifiant connu sera donc ignor, et il ny aura pas de duplication
inutile des paquets dans le rseau.
Figure 3.1 mission dun paquet dans le cas du routage par inondation
Une des premires approches non triviales qui a t dveloppe pour le routage dans les
rseaux informatiques est celle du routage par vecteur de distance [49]. Elle se base sur
lalgorithme de Bellman-Ford distribu.
Chaque routeur possde une table de routage qui consiste en un couple de donnes pour
chaque destination : le routeur par lequel on passe pour atteindre cette destination et le cot
24
associ selon une mtrique dfinie. Ces informations sont transmises priodiquement tous
les voisins, et donc chaque routeur reoit ces informations de ses voisins. Il en rsulte que,
pour un routeur, toute destination existant dans la table de routage dun voisin devient connue
et donc accessible par ce routeur. Le tableau 3.1 illustre lvolution des tables de routage des
routeurs pour le rseau de la figure 3.2.
On peut noter que linformation relatant lapparition dun routeur est propage assez
rapidement, ce qui rend cet algorithme de routage ractif lapparition de nouveaux routeurs.
Gnralement, la mtrique utilise pour cet algorithme est le nombre de sauts, mais
dautres mtriques peuvent tre utilises. Lavantage de la mtrique base sur le nombre de
sauts est quelle ne ncessite aucun traitement supplmentaire, la distance entre deux routeurs
voisins restant toujours 1.
Routeur
tat Initial
Vers A : 0
Vers B : 0
Vers C : 0
Vers D : 0
Aprs un
change
Vers A : 0
Vers B : 1
Vers A : 1
Vers B : 0
Vers C : 1
Vers B : 1
Vers C : 0
Vers D : 1
Vers C : 1
Vers D : 0
Aprs deux
changes
Vers A : 3
Vers B : 0
Vers C : 1
Vers A : 1
Vers B : 0
Vers C : 1
Vers D : 2
Vers A : 2
Vers B : 1
Vers C : 0
Vers D : 1
Vers B : 2
Vers C : 1
Vers D : 0
Aprs trois
changes
Vers A : 0
Vers B : 1
Vers C : 2
Vers D : 3
Vers A : 1
Vers B : 0
Vers C : 1
Vers D : 2
Vers A : 2
Vers B : 1
Vers C : 0
Vers D : 1
Vers A : 3
Vers B : 2
Vers C : 1
Vers D : 0
Tableau 3.1 volution des distances dans les tables de routage de A, B, C et D: fig 3.2
Figure 3.3 Problme de la rupture de lien dans le routage par vecteur de distance
Un des problmes de cette mthode est que linformation dune rupture de lien se propage
trs lentement. La figure 3.3 et le tableau 3.2 illustrent ce problme : on considre que les
25
tables de routage sont correctement remplies et que le routeur A disparait brusquement. Les
routeurs B et C schangent alors tous les deux une information errone en supposant que
lautre routeur possde une route vers A, ce qui nest pas le cas. chaque tape, la distance
vers A sincrmente donc doucement.
La notion dhorizon coup a t introduite afin de limiter cette incrmentation et de la
considrer comme une rupture de lien: lorsque la distance est suprieure une certaine valeur,
alors elle est considre comme infinie, et la route est donc supprime. La valeur utilise pour
lhorizon coup ne peut cependant pas tre trop faible car elle limite de fait le diamtre
maximal du rseau. La prise en compte de la disparition dun routeur ncessite donc une
phase de convergence lente.
Cet algorithme forme le coeur du protocole RIP [46, 47], qui fut utilis au dbut dInternet.
En raison du problme majeur quest la convergence des informations de routage en cas de
rupture de lien et parce quil tait plus adapt des rseaux de taille limite, le routage par
vecteur de distance a t assez rapidement abandonn au profit du routage par tat de lien
[48].
Routeur
Etat Initial
Vers A : 1
Vers B : 0
Vers B : 1
Vers A : 2
Vers B : 1
Vers B : 0
Aprs un
change
Vers A : 3
Vers B : 0
Vers B : 1
Vers A : 2
Vers B : 1
Vers B : 0
Aprs deux
changes
Vers A : 3
Vers B : 0
Vers B : 1
Vers A : 4
Vers B : 1
Vers B : 0
Aprs trois
changes
Vers A : 5
Vers B : 0
Vers B : 1
Vers A : 4
Vers B : 1
Vers B : 0
,,,
,,,
Le principe de base du routage par tat de lien est que la connaissance de la topologie
complte du rseau permet de calculer aisment une route de toute source vers toute
destination. Il convient donc de faire en sorte que chaque routeur connaisse la topologie du
rseau. Cette construction dune reprsentation de la topologie se fait en deux tapes : chaque
routeur effectue une dcouverte de ses voisins et informe lensemble du rseau des
informations quil a collectes. On peut remarquer quil y a tout dabord un processus local
visant obtenir une vision locale du rseau, et ensuite un processus global consistant
partager toutes les visions locales du rseau pour crer une vision globale, et donc la topologie
du rseau.
Pour dcouvrir ses voisins, un routeur envoie un message HELLO sur chacune de ses
interfaces. Chaque routeur recevant un tel message envoie une rponse, ce qui permet au
routeur initial de savoir qui a reu le message, et incidemment quels sont ses voisins. Cette
tape est rpte rgulirement afin de dtecter lapparition de nouveaux voisins ou la
26
disparition danciens voisins. La mesure du cot dun lien entre deux routeurs fonctionne
comme pour le routage par vecteur de distance : il peut sagir du simple nombre de sauts, ou
dune autre mtrique prenant en compte, par exemple, le dbit atteignable sur les liens.
Ensuite, chaque routeur rassemble lensemble des informations quil possde sur ses
voisins et sur les cots des liens qui le relient ceux-ci dans un paquet dtats de lien, et
transmet ce paquet en diffusion tout le rseau. Ce processus est rpt priodiquement, mais
il est possible dutiliser une frquence faible et de gnrer un tel paquet sans attendre la fin
dun intervalle lorsquun vnement tel que lapparition ou la disparition dun voisin a lieu.
Cela permet une ractivit plus forte au changement de topologie. La diffusion des paquets
dtats de lien seffectue par inondation, comme dcrite dans la partie 3.1.1.
Une fois la topologie du rseau connue, et que celle-ci tant couple avec lensemble des
cots des liens existant dans la topologie, un routeur dispose de toutes les informations
ncessaires pour le routage. Il met en application lalgorithme de Dijkstra [50] et dtermine le
plus court chemin vers tous les autres routeurs existant dans le rseau ; ce plus court chemin
dfinit la route utiliser.
Par rapport au routage par vecteur de distance, le routage par tat de lien ncessite donc
des ressources en mmoire et en puissance de calcul plus important, ainsi quun trafic rseau
plus soutenu mais stable mme dans le cas dun changement de topologie afin de garder
une image valide de la topologie dans chaque routeur. Cette complexit offre videmment
certains avantages : chaque routeur connaissant la topologie du rseau, une analyse plus fine
peut tre ralise de manire individuelle. Il est par exemple possible de connatre dautres
chemins que le meilleur chemin, ce qui peut savrer utile lorsquil y a dysfonctionnement sur
une route. Une utilisation avance peut consister connatre la topologie couple avec deux
mtriques distinctes, permettant de disposer de deux meilleurs chemins, chacun plus adapt
un type de trafic.
Le routage par tat de lien est utilis dans le protocole de routage interne le plus rpandu
actuellement, OSPF [51, 52]. Un autre protocole de routage par tat de lien est IS-IS [53].
27
La mobilit des nuds rsulte en une topologie qui peut varier au cours de temps, sans
schma prdfini, et aussi dans la ncessaire prise en compte de la gestion de l'nergie ; les
nuds mobiles ne disposent en effet gnralement pas d'une source d'nergie, et doivent donc
optimiser leur fonctionnement. L'utilisation d'une technologie sans fil, le plus souvent 802.11,
a pour consquence une bande passante limite, qui n'est pas comparable ce qui existe dans
un rseau filaire ; le fait que le mdium est partag ne contribue pas amliorer cette situation
et les congestions sont donc considres plus frquentes que dans le cas filaire[92]. Enfin,
l'accs au mdium tant facilit, des problmes de scurit se posent et ne doivent pas tre
oublis.
Des protocoles de routage ont t proposs pour prendre en compte les spcificits des
rseaux MANET. Une contrainte forte impose par le groupe de travail a t l'utilisation d'Ip
de manire traditionnelle, sans connexion. Les protocoles de routage doivent en outre tre
distribus en raison de l'absence d'infrastructure, et sans boucle de routage afin d'viter tout
problme majeur dans le rseau. La bidirectionnalit des liens est considre comme la norme
pour faciliter l'laboration des protocoles.
Deux approches sont possibles pour un protocole de routage MANET. L'approche ractive,
afin d'adapter le protocole au trafic existant pour minimiser les ressources consommes, ou
l'approche proactive dans le but de minimiser le dlai de mise en place des communications.
D'ventuelles approches hybrides sont aussi envisageables.
2.3.1 Classification des protocoles de routage
Le principal but de toute stratgie de routage est de mettre en uvre une bonne gestion
dacheminement qui soit robuste et efficace. Dune manire gnrale, toute stratgie de
routage repose sur des mthodes et des mcanismes que lon peut regrouper en trois grandes
classes : les protocoles de routage proactifs, les protocoles de routage ractifs et les protocoles
de routage hybrides.
2.3.1.1 Les protocoles de routage proactifs
Dans cette mthode, chaque nud garde une vision de toute la topologie du rseau, et ce,
par lintermdiaire des requtes priodiques portant sur ltat des liaisons avec les nuds
voisins [97]. En effet la mise jour dans cette mthode se fait pour chaque nud diffusant
ltat des liens des nuds voisins dans le rseau. Cette opration est aussi faite en cas de
changement dans ltat des liens.
b. La mthode du vecteur de distance ("Distance Vector")
Dans cette mthode par contre, chaque nud diffuse ses nuds voisins sa vision des
distances qui le sparent de tous les htes du rseau. En se basant sur les informations reues
28
par tous ses voisins, chaque nud de routage fait un certain calcul pour trouver le chemin le
plus court vers n'importe quelle destination. Le processus de calcul se rpte, s'il y a un
changement de la distance minimale sparant deux nuds, et cela jusqu' ce que le rseau
atteigne un tat stable.
3.3.1.2 Les protocoles de routage ractifs ( la demande)
Ce sont des protocoles [96]dans lesquels la mise jour ou le contrle des routes se fait la
demande, c'est--dire lorsquune source veut transmettre des paquets de donnes vers une
destination. Dans ce cadre plusieurs politiques peuvent tre adoptes, les plus importantes
sont :
a- La Technique dapprentissage en arrire
Dans cette technique, le nud source dtermine toute la liste des nuds par lesquels doit
transiter le message, ainsi le nud metteur inclut dans lentte du paquet une route source.
En effet, afin de construire la route, le nud source doit prciser les adresses exactes des
nuds par lesquels le message transitera jusqu' atteindre le destinataire. Ainsi, le nud
source transmet le paquet au premier nud spcifi dans la route.
Notons que chaque nud par lequel le paquet transite supprime son adresse de lentte du
paquet avant de le retransmettre. Une fois que le paquet arrive sa destination, il sera dlivr
la couche rseau du dernier hte.
Plusieurs protocoles de routage ractifs existent dont lAODV, TORA, DSR, etc.
3.3.1.3 Les Protocoles de routage hybrides
Les protocoles hybrides [40,56] combinent les deux ides : celle des protocoles proactifs et
celle des protocoles ractifs. Ils utilisent un protocole proactif pour avoir des informations sur
les voisins les plus proches (au maximum les voisins deux sauts). Au-del de cette zone
prdfinie, le protocole hybride fait appel aux techniques des protocoles ractifs pour chercher
des routes.
Ce type de protocoles sadapte bien aux grands rseaux, cependant, il cumule aussi les
inconvnients des protocoles ractifs et proactifs en mme temps (messages de contrle
29
priodique, le cot douverture dune nouvelle route). Plusieurs protocoles hybrides existent
dont le CBRP et le ZRP (Zone Routing Protocol).
De nombreux critres d'valuation existent, tel que le dbit de bout en bout, le temps
d'acheminement de la source la destination, le temps de dcouverte d'une route ou encore
l'impact des messages du protocole de routage sur les performances du rseau.
Une mthodologie complte d'valuation a donc t dveloppe afin de juger de la qualit
des diffrentes propositions. Parmi les trs nombreuses propositions de protocoles envoyes
au groupe de travail, l'attention s'est vite porte sur un nombre limit d'entre elles afin de les
standardiser. Dans la suite de cette section, les principaux protocoles MANET seront donc
prsents.
3.2.2 Quelques protocoles de routage
Dans ce qui suit, on va dcrire quelques protocoles de routage, les plus conus pour les
rseaux ad hoc:
3.2.2.1 DSR
DSR [57] (Dynamic Source Routing) est un des premiers protocoles de routage pour les
rseaux sans fil ad hoc qui a t propos. Aprs de nombreuses annes, il a t normalis sous
la forme de la RFC 4728 [58]. Il s'agit d'un protocole ractif qui a la particularit de s'appuyer
sur un routage par la source. En effet, lorsqu'un paquet est mis, celui-ci contient toutes les
informations qui sont ncessaires son acheminement jusqu' la destination. Le protocole se
dcompose en deux grandes phases la dcouverte de route et la maintenance de route.
Figure 3.4 mission d'un paquet dans le cas du routage par la source
Le routage par la source fonctionne en incluant dans chaque paquet la liste des nuds par
lesquels doit passer le paquet pour atteindre la destination. Une optimisation visant rduire
la surcharge de donnes transmises consiste utiliser un routage par la source implicite [59].
a- Dcouverte de route
Lorsqu'un nud cherche mettre un paquet vers une destination pour laquelle il n'a pas
de route en cache, le nud initie une dcouverte de route vers la destination, appele alors la
cible, et met le paquet dans un tampon. Ce dernier sera automatiquement vid aprs un dlai
sans rponse.
30
Lorsque le nud initiateur reoit une rponse ROUTE REPLY, la route fournie est mise en
cache afin de pouvoir tre rutilise ultrieurement. Les paquets mis en tampon pour la cible
sont finalement mis.
Diffrentes optimisations sont possibles. La plus importante est probablement la possibilit
pour un nud recevant un message ROUTE REQUEST pour une cible pour laquelle il
possde une route en cache d'envoyer directement au nud initiateur une rponse ROUTE
REPLY contenant la route en cache concatne la liste des nuds parcourus par le message
ROUTE REQUEST.
Une seconde optimisation consiste mettre en cache toute route qui est apprise de manire
inopine afin d'viter une ventuelle dcouverte de route pour la destination. Ainsi, tout nud
intermdiaire acheminant une rponse ROUTE REPLY peut disposer gratuitement d'une route
vers la cible ayant mis cette rponse, mais aussi vers les nuds entre le nud intermidiare et
la cible.
b- Maintenance de route
31
l'a reu envoyer le paquet vers le nud suivant sur la route, alors le paquet est considr
comme acquitt ; une approche plus directe consiste demander explicitement un
acquittement par l'envoi d'un simple message. Dans un tel cas, il est possible de considrer
l'acquittement comme valide pour un temps limit et de ne pas requrir d'acquittement pour
les prochains paquets mis dans cet intervalle de temps.
Si un paquet n'est pas acquitt lors d'un saut, alors toute route dans le cache passant par le
nud suivant est invalide et un message ROUTE ERROR est mis destination des nuds
utilisant le nud suivant dans une de leurs routes afin de les prvenir que celles-ci ne sont
plus valides.
Une opration appele sauvetage des paquets peut aussi tre effectue dans le cas o le
nud dtectant un lien bris dispose d'une route alternative vers la destination du paquet.
L'opration consiste utiliser cette route en remplacement de la route spcifie par l'metteur
du paquet. Le message ROUTE ERROR est toujours transmis.
c- valuation
DSR est un protocole qui a l'avantage d'tre relativement simple, tout en fournissant de
bons rsultats. L'approche ractive et l'absence de messages priodiques lis au routage
permettent de ne pas avoir d'impact majeur en terme de charge sur le rseau, mais aussi
d'nergie consomme. Les nuds par lesquels aucune route ne passe ne consomment pas non
plus d'nergie pour le bon fonctionnement du rseau, sauf durant la phase de dcouverte de
route. Un dernier aspect intressant de DSR est li au routage par la source ; chaque nud
intermdiaire ne fait alors que retransmettre btement le paquet sur une route choisie dans
son ensemble par la source. La source peut donc effectuer diffrents choix de routage qui
seront respects.
Le protocole n'est pas pour autant exempt de dfauts. L'approche ractive cre videmment
un certain dlai avant toute communication. En outre, l'utilisation intensive de caches pour les
routes pose des questions quant la validit dans le temps de ces caches, notamment par les
nuds qui obtiennent les routes de manire indirecte et qui peuvent donc ne pas tre informs
d'erreurs lors de la phase de maintenance des chemins. Enfin, le routage par la source cre
videmment une surcharge au niveau de chaque paquet transmis en raison des informations
supplmentaires qui sont ncessaires.
3.2.2.2 AODV
Un second protocole de routage pour les rseaux MANET est AODV [60] (Ad-hoc Ondemand Distance Vector), qui a t normalis avec la RFC 3561 [61]. AODV a fait l'objet de
nombreux travaux. Comme DSR, il s'agit d'un protocole ractif, et donc il existe des
similitudes importantes entre les deux protocoles. Nanmoins, AODV n'utilise pas de routage
par la source, et utilise des numros de squence afin de dterminer si un message est plus
rcent ou ancien que l'information dj connue. En outre, une mtrique est utilise afin de
pouvoir utiliser une meilleure route si elle devient disponible; il s'agit d'une mtrique
comptant simplement le nombre de sauts. Ce protocole est donc proche du routage par vecteur
de distance vu dans la partie 3.1.2.
a- Dcouverte de route
Un nud souhaitant communiquer avec une destination pour laquelle il n'a pas de route
32
dans sa table de routage met une requte RREQ en inondation. Cette requte contient un
identifiant de la requte, le nombre de sauts parcourus, ainsi que le numro de squence de la
source et le dernier numro de squence connu de la destination.
Un nud recevant une requte RREQ vrifie d'abord que celle-ci n'a pas dj t reue : si
l'identifiant de la requte est connu, alors elle est ignore. Si le nud ne connait pas de route
pour la destination demande, alors les informations lies la requte, dont le numro
squence de la source, sont enregistres localement de manire temporaire afin de pouvoir
faire suivre une ventuelle rponse RREP vers l'metteur de la requte sur la route inverse. En
particulier, si un message est reu avec un numro de squence correspondant au nud
initiateur plus rcent que le numro de squence enregistres dans ce cache, alors les
informations sont mises jour pour disposer de la route inverse plus rcente.
Lorsque la requte RREQ parvient un nud disposant d'une route vers la destination, ou
la destination elle-mme, une rponse RREP est envoye sur la route inverse. Si le nud
recevant la requte n'est pas la destination, il vrifie d'abord que le numro de squence de sa
route vers la destination est suprieur ou gal au numro de squence destination inclus dans
la requte: si ce n'est pas le cas, cela signifie que le nud initiateur de la requte ignorera la
rponse et donc celle-ci ne doit pas tre mise, et la requte doit tre retransmise. Une rponse
RREP contient l'adresse du nud initiateur de la requte, l'adresse de la destination de la
requte, le numro de squence de la destination de la requte, le nombre de sauts parcourus
par la requte. La rponse RREP est mise sur la route inverse de celle parcourue par la
requte, destination de l'initiateur de la requte.
Chaque nud recevant une rponse RREP met jour sa table de routage vers la destination
s'il n'y avait pas d'entre, si le numro de squence destination de la rponse est plus grand
que le numro de squence enregistr dans la table de routage, ou si la mtrique est meilleure
dans le cas o les deux numros des squences sont gaux. S'il s'agit de la premire rponse
reue pour cette destination (donc si la table de routage n'avait pas d'entre pour cette
destination), alors la rponse est retransmise sur les chemins inverses qui ont t gards en
mmoire pour cette destination lors de la rception des requtes RREQ.
Le nud initiateur finit par recevoir une rponse RREP, et peut ainsi mettre les paquets
vers la destination.
b- Maintenance de route
De mme que pour DSR, une maintenance de route est effectue, notamment pour dtecter
la rupture de liens. Le fonctionnement est nanmoins diffrent.
Un premier but est de garantir qu'un lien est toujours bidirectionnel. Si cela est possible, la
couche MAC est utilise cette fin grce aux acquittements MAC. Dans le cas contraire, un
mcanisme simple de messages HELLO priodiques est mis en uvre. Ces messages sont
envoys tous les voisins par un nud pour signaler son existence. Un message HELLO
contient la liste de tous les nuds connus par l'metteur ; en vrifiant qu'il est prsent dans un
message HELLO reu de son voisin, un nud peut ainsi vrifier que le lien entre lui et le
voisin est bidirectionnel.
Les messages HELLO sont aussi utiliss afin de dcouvrir une rupture de lien. Les nonrceptions conscutives de plusieurs messages de ce type sont interprtes ainsi. Quand une
rupture de lien apparait, le nud l'ayant dcouverte envoie une rponse RREP non sollicite
33
avec une mtrique infinie et un numro de squence destination incrmente tous ses voisins
qui utilisaient ce lien. Cette rponse sera alors retransmise de nud en nud pour informer
tous les nuds utilisant le lien dans une route. Si un nud source reoit une telle rponse
RREP, il peut dcider de lancer nouveau une dcouverte de route dans l'ventualit o il a
toujours du trafic envoyer.
Un autre aspect de la maintenance est la suppression des routes inutilises. Pour cela,
chaque paquet retransmis en utilisant une route revalide la route, ce qui la garde active. Aprs
un dlai d'inactivit sans paquet, la route est supprime.
Enfin, si une rponse RREP est reue pour une destination dj prsente dans la table de
routage, alors celle-ci est utilise pour changer la route seulement si le numro de squence
destination est plus grand que celui prsent dans la table de routage ou, dans le cas o les
deux numros de squence sont gaux, si la mtrique de la route offerte par la rponse RREP
est meilleure.
c- Gestion des numros de squence
Il n'y a pas de numro de squence unique pour le rseau, car il serait impossible de
dterminer en permanence sa valeur de manire distribue. Chaque nud possde donc son
propre numro de squence permettant de dater les informations provenant de lui et de lui
seul. Un numro de squence est incrment dans les cas suivants :
Avant d'envoyer une rponse RREP, le nud met jour son numro de squence
en utilisant le maximum du numro de squence actuel et de celui indiqu comme
numro de squence destination dans la requte RREQ reue ;
En cas de rupture d'un lien, pour chaque route passant par le lien, le numro de
squence associ la destination de la route est incrment avant d'envoyer la
rponse RREP informant de la rupture du lien .
d- valuation
Comme tout protocole ractif, AODV souffre d'un dlai lors de l'envoi des premiers
paquets vers une destination non connue. L'utilisation des numros de squence cre aussi une
certaine complexit, mais a l'avantage de permettre de fortement limiter les retransmissions
inutiles. Ajouter au fait que l'approche ractive du protocole ne pse que peu sur la charge du
rseau, il en rsulte qu'AODV n'a que peu d'impact sur celle-ci. Les messages HELLO
priodiques restent cependant ncessaires.
Une diffrence majeure d'AODV par rapport DSR est le fait qu'un nud intermdiaire sur
une route peut modifier la route d'une source une destination. C'est notamment le cas si un
lien est rompu et que le nud intermdiaire parvient trouver une route alternative ou si une
meilleure route devient disponible entre le nud intermdiaire et la destination. On peut
parler de rparation locale du lien et d'optimisation locale de la route car ces informations
n'ont pas tre remontes jusqu' la source. Cette diffrence fait qu'AODV est plus adapt que
DSR dans le cas d'une mobilit importante des nuds [62]. Le routage par la source de DSR
reste nanmoins intressant de par le fait qu'il permet la source de contrler exactement
quelle route est utilise; cela permet notamment chaque source de choisir une route en
fonction de critres qui lui sont propres, comme une mtrique particulire ou encore le choix
34
la diffrence de DSR et d'AODV, OLSR [63] (Optimized Link State Routing) est un
protocole de routage pour les rseaux MANET proactif. Il se base sur le routage par tat de
lien comme dcrit dans la partie 3.1.3, mais optimise celui-ci en minimisant le trafic
ncessaire pour que chaque nud connaisse la topologie du rseau grce aux relais multipoints [64]. OLSR a lui aussi t formalis sous la forme de la RFC 3626 [65].
a- Les Relais multipoints (MPR)
L'objectif des relais multipoints est de limiter localement le nombre de retransmissions lors
d'une inondation : chaque nud dispose d'un ensemble de relais multipoints choisis parmi ses
voisins et seuls ces relais multipoints peuvent retransmettre les paquets mis par le nud. Les
paquets sont toutefois reus par tous les voisins. Si l'ensemble des relais multipoints est plus
petit que l'ensemble des voisins, il en rsulte immdiatement une rduction du trafic
retransmis; en outre, plus cet ensemble est petit, plus la rduction du nombre de
retransmissions est efficace.
Pour savoir s'il peut retransmettre un paquet reu, chaque nud doit donc maintenir la liste
des nuds qui l'ont choisi comme relai multipoints. Ces derniers sont les slectionneurs multipoints du nud.
Lensemble des MPRs pour un nud i, not MPR(i), est un sous-ensemble minimal choisi
parmi ses voisins symtriques un saut qui satisfont les proprits suivantes :
Chaque nud parmi les voisins deux sauts de i doit avoir un lien symtrique avec
au moins un lment du sous-ensemble MPR(i);
La figure 3.5, montre un exemple doptimisation des MPRs. Comme illustr dans la figure,
le nud S na besoin de choisir que quatre nuds parmi ses voisins un saut pour que tous
les nuds voisins deux sauts puissent communiquer avec lui.
35
De manire priodique, chaque nud envoie un message HELLO tous ses voisins. Ce
message contient trois listes de nuds:
la liste des adresses des voisins pour lesquels le nud a reu un paquet HELLO;
la liste des adresses des voisins qui sont accessibles par un lien bidirectionnel;
la liste des adresses des voisins que le nud a choisis comme relais multipoints.
Lorsqu'un nud reoit un message HELLO d'un voisin, alors il place le voisin dans la
premire liste. Si en outre, son adresse est dans la premire liste du message reu, alors il
considre que le lien entre lui et le voisin est bidirectionnel; il place donc le voisin dans la
seconde liste. Enfin, si son adresse est dans la troisime liste, cela signifie que le voisin est un
de ses slectionneurs multipoints; le nud sait ainsi qu'il doit retransmettre les paquets en
diffusion de ce voisin.
Avec l'aide des messages HELLO de ses voisins, un nud peut calculer la liste de tous ses
voisins deux sauts il s'agit de l'ensemble des voisins de ses voisins qu'il ne connait pas
directement. Il possde alors toutes les informations requises pour slectionner un ensemble
de voisins qui formeront ses relais multipoints. Lors de l'envoi du prochain message HELLO,
cette liste sera transmise aux voisins et donc aux relais multi-points qui seront ainsi informs
de leur rle. L'ensemble des relais multi-points doit tre recalcul lorsque l'ensemble des
voisins change ainsi que lorsque l'ensemble des voisins deux sauts change.
Le processus de slection des relais multipoints fait que les liens entre un nud et ses
relais multi-points sont tous bidirectionnels. Cette caractristique permet de ne pas souffrir de
problmes lis des liens unidirectionnels dans le routage.
Chaque nud envoie rgulirement en diffusion un message TOPOLOGY CONTROL
destination de l'ensemble du rseau afin de dclarer l'ensemble de ses slectionneurs multirelais. L'utilisation des relais multi-points pour l'envoi par inondation d'un tel message permet
de limiter le nombre de retransmissions inutiles du message, tout en garantissant que tous les
nuds du rseau reoivent le message.
La rception de ces messages permet chaque nud de construire une topologie du rseau
base sur les relais multi-points. L'algorithme de Dijkstra [66] est ensuite mis en oeuvre pour
trouver une route pour chaque nud.
Une consquence du fait que seuls les slectionneurs multi-points sont transmis dans les
messages TOPOLOGY CONTROL est que les routes sont toutes une suite de relais multipoints, de la source la destination. Une dmonstration formelle montre que ces routes
formes uniquement de relais multipoints sont les plus courts chemins et sont donc optimales
[63].
c- valuation
OLSR est un protocole de routage efficace, car il garantit l'optimalit des routes en terme
de sauts, et ne souffre pas de problme de dlai pour l'mission des premiers paquets comme
c'est le cas pour les protocoles ractifs. Indpendamment du protocole lui-mme, la notion de
relai multi-points est particulirement intressante car elle permet d'optimiser le mcanisme
de diffusion en effectuant une inondation dans le rseau avec un impact moins important
36
Par exemple, les paquets doivent tre intercepts afin de dclencher le mcanisme de
dcouverte de route puis rmis lorsqu'une route est disponible. Cette tape, similaire au
mcanisme employ pour ARP, interfre avec le fonctionnement de la pile rseau au niveau 3
car une telle interception des paquets n'est pas prvue.
3.3.1 LUNAR
LUNAR [67] (Lightweight Underlay Network Ad-hoc Routing) propose une approche
inhabituelle pour rsoudre le problme du routage dans les rseaux sans fil ad hoc. Le but
initial de LUNAR est d'explorer de nouvelles stratgies, et pour cela il a t prfr de garder
un protocole relativement simple. Ce protocole est bas sur SelNet [68, 69], qui fournit une
abstraction permettant l'acheminement au niveau 2.5. L'utilisation de SelNet permet de faire
apparatre tout nud du rseau comme un voisin, recrant ainsi la vision d'un rseau local
pour les couches hautes.
Une restriction non ngligeable est place sur la taille des rseaux ad hoc considrs
l'origine, LUNAR se limite des rseaux de trois sauts de largeur maximum, car les auteurs
estiment que ce cas atteint dj les limites des cartes 802.11 en terme de connectivit, que la
qualit des informations disponibles dans un rseau multisauts plus grand n'est pas suffisante
en raison de l'ge que le temps de transport sur toute la largeur du rseau implique, et que la
dcouverte et la maintenance de routes ont un impact ngatif trop important par rapport
l'intrt d'un bon fonctionnement purement local. Cette restriction est cependant purement
arbitraire, et LUNAR peut fonctionner sur des rseaux plus grands.
LUNAR utilise un protocole de routage similaire celui d'AODV, dcrit dans la partie
3.2.3. Ainsi, des requtes RREQ sont envoyes en inondation sur le rseau et les nuds
intermdiaires gardent les informations ncessaires pour acheminer une ventuelle rponse
RREP. Les messages RREQ et RREP sont transmis l'aide de SelNet sous la forme de
messages XRP.
Une diffrence est l'intgration avec la pile rseau. La dcouverte de route est ici lance
lorsqu'une requte ARP est mise pour une destination par la couche IP. D'une certaine faon,
la dcouverte de route se traduit donc par un mcanisme d'extension d'ARP aux multisauts.
Les messages RREP ont, outre le rle d'informer de la route, celui de crer un chemin sur
la route en utilisant les slecteurs SelNet. A chaque saut, un nouveau slecteur est cr
localement et est li l'opration consistant faire suivre le paquet vers le nud suivant dans
38
la route avec le slecteur dfini dans la rponse RREP reue. Ce nouveau slecteur est plac
dans la rponse RREP qui est envoye au nud prcdent dans la route. Ainsi, le nud source
pourra ds la rception de la rponse RREP utiliser ce chemin pour l'acheminement au niveau
2.5 des paquets vers la destination.
La gestion des paquets de diffusion est plus surprenante puisqu'un mcanisme diffrent de
l'inondation est utilis : un arbre de diffusion est en effet construit par l'metteur. Pour cela,
un mcanisme similaire celui utilis pour la dcouverte de route est utilis :
Le nud metteur envoie une requte RREQ dans un message XRP;
Chaque nud recevant une telle requte rmet la requte RREQ s'il ne l'a pas dj
reue et envoie une rponse aprs un dlai ; le dlai permet de mettre en place la suite de
l'arbre ;
La rception des rponses permet de connatre quels nuds le paquet devra tre
retransmis.
Aprs avoir reu les rponses de ses voisins, le nud metteur peut envoyer le paquet de
diffusion dans l'arbre ainsi construit.
Le cot initial de construction de l'arbre est important, mais permet d'envoyer plus
efficacement un nombre important de paquets de diffusion. Le nud metteur ne connait pas
l'arbre dans son ensemble.
Afin de prendre en compte tout ventuel changement de topologie, les chemins
d'acheminement construits sont rendus invalides aprs six secondes. Pour viter les
interruptions de connexion, chaque chemin est donc reconstruit toutes les trois secondes.
Cette approche permet de se passer de toute signalisation pour la maintenance des chemins.
3.3.2 SelNet
SelNet (Selector Network) est une nouvelle abstraction qui se place entre la couche IP et la
couche MAC. SeiNet introduit la notion de slecteur pour un paquet lorsqu'un nud reoit un
paquet marqu par un slecteur, une opration dfinie par le slecteur est effectue.
L'opration peut consister en l'envoi du paquet vers un autre nud avec un autre slecteur ou
encore en l'mission du paquet sans slecteur pour le rintroduire dans la pile rseau standard.
L'utilisation de SelNet ncessite que des slecteurs soient mis en place sur les diffrents
nuds, et connus par les nuds voulant communiquer entre eux l'aide de ces slecteurs. Des
messages de type XRP (Extensible Resolution Protocol) peuvent tre utiliss cette fin.
SelNet en tant que tel ne dfinit pas comment sont utiliss ces messages, mais permet une
couche plus haute de les utiliser afin de dcider de la mise en place des slecteurs. LUNAR est
un exemple d'une telle couche place au-dessus de SelNet et utilisant les messages XRP.
Pour l'acheminement des paquets l'aide des slecteurs, un second type de message SAPF
(Simple Active Packet Format) est dfini. Un message SAPF est plus spcifique que les
messages XRP car il ne possde qu'un en-tte rduit au strict ncessaire pour l'acheminement,
savoir le slecteur. SelNet traite donc directement un tel message et effectue
automatiquement l'opration associe au slecteur que contient le message.
D'une certaine faon, SelNet est trs proche de MPLS. La principale diffrence est que
SelNet intgre directement des messages XRP pour la communication entre les nuds au
39
Ananas [70,71] est une proposition d'architecture qui a pour but de faciliter le
fonctionnement d'un rseau ad hoc en crant l'illusion, pour la couche IP de chaque nud, que
tous les nuds sont sur le mme rseau local, cachant ainsi l'aspect multi-sauts du rseau et
toute les difficults que cela implique. Pour cela une interface virtuelle est cre sur chaque
station, qui a pour but d'tre une abstraction de toutes les interfaces physiques prsentes sur le
nud; c'est par cette interface virtuelle que tous les paquets IP passent pour tre mis sur le
rseau. Chaque nud est identifi dans le rseau par l'adresse ad hoc de son interface
virtuelle. Le rseau ad hoc multi-sauts est ainsi relgu au niveau de cette interface virtuelle
pendant que pour la couche IP, le rseau apparait simplement comme un rseau local.
L'interface virtuelle se place entre la couche IP et la couche MAC et reprsente logiquement
une couche 2.5.
D'un point de vue architectural, il existe donc trois niveaux d'abstraction:
Le niveau ad hoc: c'est ce niveau qu'existe le rseau ad hoc, compos de tous les
nuds du rseau. A ce niveau, un nud ne possde pas plusieurs interfaces physiques,
mais seulement une interface virtuelle configure avec une adresse ad hoc unique dans
le rseau. S'agissant d'un rseau ad hoc habituel, les communications ce niveau
peuvent tre multi-sauts;
Le niveau IP: le rseau n'est, ce niveau, plus qu'un rseau local dans lequel tous les
nuds sont directement accessibles travers une unique interface l'interface virtuelle.
Une communication IP ne semble donc consister qu'en un seul saut pour le paquet.
L'insertion du niveau ad hoc comme couche 2.5 permet le fonctionnement normal d'IP sans
modification, notamment pour des outils habituellement difficiles mettre en oeuvre sur un
rseau ad hoc. Par exemple, dans le cas de DHCP, mme si un nud ne possde pas encore
d'adresse IP, il peut recevoir la rponse grce son adresse ad hoc qui joue un rle quivalent
celui de l'adresse MAC dans un rseau local.
Aucun protocole de routage n'est dfini par Ananas car cet aspect est indpendant de
l'architecture gnrale. Donc des protocoles tels que DSR, AODV ou OLSR peuvent tre
utiliss aprs une lgre adaptation. En effet, le protocole de routage est utilis pour faire le
routage sur les adresses ad hoc, et non sur les adresses IP. Si l'on se place du point de vue de
la couche IP, avec l'illusion cre par l'interface virtuelle, aucun routage n'entre en jeu, car
tous les nuds sont directement accessibles sur le rseau local. Le routage a donc lieu au
niveau 2.5 et c'est galement ce niveau qu'existe la table de routage.
L'acheminement des paquets tant purement bas sur les adresses ad hoc, et notamment
celle de la destination, il en rsulte que l'adresse IP de la destination doit tre convertie en
adresse ad hoc destination avant l'mission du paquet. Il est donc ncessaire d'utiliser une
table de traduction d'adresses qui fonctionne exactement comme une table ARP dans la pile
rseau habituelle. Le remplissage de cette table est coupl avec le mcanisme de dcouverte
de route du protocole de routage.
40
valuation
source vers une destination. Nous retiendrons cette dfinition et plus formellement nous
dfinissons la Qualit de Service comme lensemble des mcanismes mis en oeuvre dans un
rseau afin de satisfaire les besoins explicites des applications lors de lacheminement des
flux de donnes
Suivant le type de lapplication, les besoins de QoS sont diffrents. Par exemple, pour les
applications temps rel, comme la voix et la vido, le dlai de bout en bout dun paquet doit
tre born, autrement le paquet est inutile. Les applications non temps rel, comme le transfert
de fichiers ou la messagerie, quant elles se focalisent sur la fiabilit des communications
[40].
Les mcanismes classiques de qualit de service dans les rseaux filaires sont totalement
ou partiellement inadapts dans un environnement ad hoc. En effet, la plupart de ces
mthodes reposent sur la connaissance dinformations prcises quant ltat du rseau (la
bande passante utilise, le dlai, la gigue de phase, etc.). Dans un contexte sans fil, ces
informations sont difficiles valuer notamment cause des phnomnes propres aux
transmissions sans fil [92](versatilit du lien radio, interfrences, attnuation du signal, etc.) et
peuvent tre amenes varier trs rapidement, en fonction de la mobilit.
Un tat de lart sur la QoS dans les rseaux ad hoc, a t propos dans [75], classifiant les
solutions de QoS en quatre grandes catgories :
Les modles de QoS dfinissent des architectures globales dans lesquelles des
garanties peuvent tre fournies.
Les protocoles daccs au mdium cherchent ajouter des fonctionnalits aux couches
basses du modle OSI afin de pouvoir offrir des garanties.
Les protocoles de routage avec qualit de service recherchent les routes ayant
suffisamment de ressources disponibles pour satisfaire une requte.
42
Cette classification trs souvent utilise permet didentifier les diffrentes briques mettre
en oeuvre pour assurer une certaine qualit de service. Dans [28,85], les auteurs proposent une
classification diffrente : ils distinguent les approches de qualit de service statistique des
approches avec garanties quantitatives. Dans les approches de qualit de service statistiques,
lide est doffrir plus de ressources aux trafics prioritaires compars aux trafics moins
prioritaires, sans nanmoins assurer de garanties quantitatives. La norme IEEE 802.11e
[76,77] fait partie de cette approche. Dans un contexte ad hoc, lordre des priorits reste
nanmoins difficile respecter de part la difficult de reporter des politiques locales de
voisinage en voisinage. Pour des applications strictes comme la diffusion de vido, les
approches avec garanties quantitatives nous semblent plus appropries.
Parmi les approches avec garanties quantitatives, les auteurs de [76,77] distinguent les
approches posteriori des approches priori. Les approches posteriori peuvent tre bases
sur nimporte quel protocole de routage et ne cherchent qu rguler lenvironnement afin
doffrir des garanties aux applications le ncessitant. A loppos, les approches priori vont
se baser sur un routage avec qualit de service. Le principe du routage avec qualit de service
est de rechercher un chemin entre deux nuds satisfaisant certaines contraintes. Plusieurs
mtriques peuvent tre utilises telles que le dlai, la bande passante, la gigue ou encore le
taux de perte.
Un trs grand nombre de protocoles de routage de QoS ont t proposs. On retrouve la
dichotomie classique entre protocoles ractifs et proactifs. Ainsi, le routage avec qualit de
service ajoute en gnral ces protocoles de routage usuels un contrle dadmission afin de
slectionner parmi les routes disponibles celles qui satisfont les contraintes spcifies par
lapplication. Le contrle dadmission est une tape trs importante dans le routage QoS : il
sagit plus prcisment de dterminer si les conditions du rseau permettent de transmettre les
flux avec les garanties requises. Ladmissibilit des flux est faite en fonction de deux
paramtres :
La quantit de ressources exige par lapplication : les applications doivent tre en mesure
de quantifier leur besoin en terme de ressources, par exemple la quantit de bande passante
dont elles ont besoin. Ceci fait apparatre une spcificit du routage avec QoS : lligibilit
dune route doit tre dtermine flux par flux et non plus destination par destination. Il est
tout fait envisageable dutiliser des routes diffrentes pour des flux ayant des contraintes
diffrentes. Le routage par flux permet par ailleurs dassurer un contrle plus fin des
ressources du rseau. On peut par exemple imaginer la dcomposition dun flux en plusieurs
petits sous-flux, chacun empruntant une route diffrente.
Lestimation des ressources rsiduelles ou disponibles le long des chemins qui doit tre
connue priori avant lenvoi des flux QoS. Cest un point critique, car plusieurs protocoles de
routage QoS se concentrent davantage sur la partie routage que sur la partie estimation des
ressources rsiduelles. Cette estimation des ressources est rendue plus complexe dans un
contexte ad hoc o contrairement aux rseaux filaires, les liens entre mobiles sont versatiles,
peu fiables, et partags inquitablement.
Pour rsumer, le routage avec QoS est un processus dtablissement et de maintenance des
routes satisfaisant un ensemble de critres quant la qualit de la transmission des donnes.
Nous pensons que le point critique de ce processus reste lestimation des ressources
disponibles travers le rseau, car la prcision du contrle dadmission dpend fortement de
cette estimation.
43
Les exemples illustrs dans la figure 3.9 montrent la diffrence entre un protocole
classique et un protocole avec QoS ; dans le premier, la route choisie est celle passe par les
nuds B, C et F est au lieu du plus court chemin pass par D, E car elle satisfait le besoin de
la QoS de la bande passante <BP> demande. Dans le deuxime, la route choisie est B E F car
elle satisfait le besoin du dlai.
Certains protocoles de routage supposent que cette estimation est connue et ne repose pas
sur une technique dvaluation des ressources spcifiques. Cest le cas par exemple du
protocole CEDAR [78].
Dautres protocoles en revanche proposent leur propre technique dvaluation des
ressources. MRTG [81] (Multi Router Traffic Grapher), cprobe [82], [83] TOPP (Train of
Packet Pair) et ABE (Available Bandwdith Estimation) [80]. Dans [84], les auteurs proposent
un rsum dtaill des techniques dvaluation de la bande passante rsiduelle dans le monde
filaire.
Par ailleurs, et dans le but de palier aux contraintes cls spcifiques aux Manets et den
tirer profit, de nouvelles recherches se sont concentres sur les techniques de mesure et
destimation du degr mobilit relative dun nud (voire dun rseau) dautres se sont
orientes vers le contrle des mouvements des nuds. Ces diffrentes techniques seront
dtailles dans le chapitre suivant.
Nous pensons quune bonne matrise de la mobilit du rseau permettra de fournir des
garanties de qualit de service dans les rseaux sans fil.
3.4.2 Protocoles de routage avec QoS
Plusieurs protocoles de routage avec QoS ont t proposs par la communaut scientifique
pour les MANETs faisant face aux contraintes spcifiques de ces rseaux. La plupart des
solutions existantes sont des extensions des protocoles best effort existant. En gnral un
contrle d'admission est impos afin de selectionner parmi les routes disponibles celles qui
satisfont les contraintes du flux. Le principal problme de ce type de protocole est le surcout
engendr.
Le tableau 3.3 dcrit quelques protocoles de routage avec QoS reprsentatifs avec les
diffrentes caractristiques et techniques de fournir la qualit de service au niveau de la
couche rseau. Chacun de ces protocoles aborde les problmes de lestimation de la bande
44
45
Proprits
Dcouverte de
route
Rservation
des
ressources
Prise en
compte de
l'tat des
liens
Architecture
Mtrique de QoS
Estimation de
dlai/bande
passante
CEDAR
Hirarchique
Bande Passante
Non
Proactive/Ractive
Oui
Non
Non
Non
Ticket based
Plate
Bande passante /
dlai
Non
Ractive
Oui
Non
Non
Oui
OLSR based
Hirarchique
Bande Passante
Oui
Proactive
Non
Non
Non
Non
AQOR
Plate
Bande passante /
dlai
Oui
Ractive
Oui
Non
Non
Non
ADQR
Plate
Bande Passante
Non
Ractive
Oui
Oui
Non
Oui
TDR
Plate
Bande Passante
Non
Ractive
Oui
Oui
Non
Non
BEQR
Plate
Bande Passante
Oui
Ractive
Non
Non
Non
Non
QOLSR
Hirarchique
Bande passante /
dlai
Oui
Proactive
Non
Non
Non
Non
Protocoles
46
Prise en
Route
compte de
redondante
la mobilit
Conclusion.
Le routage est une des fonctions de base essentielles au bon fonctionnement des rseaux. Il
s'agit donc d'un sujet qui a fait l'objet de trs nombreuses recherches, et seule une infime
partie de ces recherches a t prsente ici.
On peut observer que les mthodes de routage traditionnelles ont aujourd'hui encore une
influence importante, et ceci est particulirement visible quand on s'intresse plus
particulirement au problme du routage dans les rseaux MANET.
Nous avons prsent quelques protocoles de routage du groupe MANET qui ont t
proposs pour assurer le service de routage dans les rseaux mobiles ad hoc et nous avons
dcrit leurs principales caractristiques et fonctionnalits afin de comprendre les stratgies
utilises dans l'acheminement des donnes entre les diffrents nuds. Le groupe de travail
MANET (Mobile ad hoc NETwork) de l'IETF (Internet Engineering Task Force) se proccupe
de la normalisation des protocoles ad hoc fonctionnant sous IP. Dans ce cadre, AODV, OLSR,
DSR sont actuellement lobjet dune RFC grce leurs caractristiques intressantes, ces
protocoles fonctionnent en mode best effort. Cependant, ils ne permettent pas de garantir une
qualit de service (QoS).
Les spcifications et implmentations des premiers protocoles de routage taient fortement
lies, les protocoles de routage MANET ont principalement t dvelopps l'aide de
simulations. Mme si quelques implmentations de protocoles tels qu'AODV et OLSR sont
apparues, celles-ci ne sont pas devenues le moteur de l'volution de ces protocoles et n'ont eu
qu'un impact limit, les simulations restant prfres aux exprimentations. Ce manque
d'ancrage dans le monde rel pour la recherche ralise par la communaut MANET est
critiqu dans [7].
L'mergence de propositions bases sur un niveau 2.5 est un phnomne relativement
rcent. Celles-ci ont pour point commun de chercher prsenter la couche IP un rseau qui
s'tend sur plusieurs liens comme un unique rseau local.
Par ailleurs, lavantage essentiel que reprsentent les systmes de communication radiomobiles par rapport aux rseaux fixes est la mobilit. Aussi, le grand succs que connaissent
les nouvelles gnrations de rseaux (3G, 3G+,Wimax et LTE) et laffluence de nouveaux
consommateurs a impos aux oprateurs une amlioration rapide de leurs rseaux pour
garantir, lutilisateur final, une meilleure qualit de service nimporte o et nimporte quand.
Ainsi, il semble important dadapter les MANETs pour supporter un certain niveau de QoS
dans le but de dploiement des applications exigeantes.
Aprs avoir fait une tude sur les protocoles de routage, nous prsentons dans le prochain
chapitre, diffrents types et mtriques de mobilit utiliss dans le domaine de recherche
associs aux environnements ad hoc. Cette tude nous amnera proposer une nouvelle
mtrique pour quantifier ou mesurer la mobilit dun nud (voire dun lien et dun rseau).
La mtrique propose sera mise lpreuve par une srie de tests pour statuer dune part sur
sa validit et dautre part sur les performances des protocoles de routages dans les rseaux
mobiles ad hoc.
47
Deuxime partie
Contribution
Chapitre
Introduction
Un protocole doit tre examin dans des conditions ralistes prenant en compte une zone
de transmission variable en raison d'une possible prsence d'obstacles, l'espace mmoire
limit pour le stockage des messages, des modles de trafic de donnes, et des mouvements
ralistes des nuds mobiles. Il existe plusieurs modles de mobilit que reprsentent les
nuds mobiles dont les mouvements sont indpendants les uns des autres (modles de
mobilit dentit) et plusieurs modles reprsentant les nuds mobiles dont les mouvements
dpendent les uns des autres, appels modles de mobilit de groupe.
Ce chapitre prsente les modles de mobilit existants, utiliss pour l'valuation des
performances d'un protocole de routage Adhoc. La section 4.2.1 prsente des mobilits de
mobilit d'entit, tandis que la section 4.2.2 prsente les modles de mobilit de groupe. Tous
ces modles sont illustrs par des figures. Enfin, une discussion sur ces modles est prsente
la fin de la section 4.2. ainsi qu'un tableau rcapitulatif des caractristiques de ces modles.
51
Les modles de traces sont les modles de mobilit qui sont observs dans les systmes
rels. Les traces fournissent des informations prcises, particulirement quand elles
impliquent un grand nombre de participants pendant une longue priode d'observation.
Cependant, de nouveaux environnements de rseaux (par exemple rseaux Adhoc) ne sont pas
facilement modliss si les traces n'ont pas t encore cres. Dans ce type de simulation, il
est ncessaire dutiliser les modles synthtiques qui essaient de reprsenter les
comportements des nuds mobiles sans l'utilisation des traces.
Un modle de mobilit doit essayer d'imiter les mouvements des vrais nuds mobiles. Les
changements de vitesse et de direction doivent se produire dans des temps raisonnables. Par
exemple, nous ne voudrions pas quun nud mobile se dplace sur des lignes droites vitesse
constante au cours de la simulation tout entire, car les vrais nuds mobiles ne se
dplaceraient pas d'une faon si restreinte. Les sept modles synthtiques de mobilit d'entit
pour le rseau Adhoc qui seront prsents sont:
Modles de mobilit de promenade alatoire: un modle de mobilit simple qui
choisit des directions et des vitesses de faon alatoire.
Modles de mobilit de promenade alatoire avec pause: un modle qui inclut des
pauses entre les changements de direction et de vitesse.
Modles de mobilit de direction alatoire: un modle qui force les nuds mobiles
se dplacer vers les bords du secteur de simulation avant de changer direction et
de vitesse.
Le modle de mobilit dans une rgion de simulation illimite: un modle qui
convertit un secteur 2D rectangulaire de simulation en secteur de simulation en
forme de tore.
Le modle de mobilit de Gauss-Markov: un modle qui utilise un paramtre
d'accord pour changer l'aspect alatoire dans le modle de mobilit.
La version probabiliste du modle de promenade alatoire: un modle qui utilise un
ensemble de probabilits pour dterminer la prochaine position d'un nud mobile.
Le modle de mobilit des sections de ville: un secteur de simulation qui reprsente
les rues dans une ville.
Pour simuler un rseau Adhoc, il existe aussi des modles de mobilit de groupe ( group
mobility model) qui permettent de simuler des situations o les dcisions des nuds
dpendent des autres nuds mobiles du mme groupe. Voici quelques-uns de ces modles:
Le modle exponentiel alatoire corrl: c'est un modle de mobilit de groupe qui
utilise une fonction mathmatique pour gnrer les mouvements de faon corrle.
Le modle de mobilit de colonne: c'est un modle o l'ensemble des nuds
mobiles forment une colonne et se dplacent uniformment en avant dans une
direction particulire.
Le modle de mobilit de communaut nomade: dans ce modle, un ensemble de
nuds mobiles se dplacent ensemble d'un endroit un autre.
Le modle de mobilit de poursuite: un modle o un ensemble de nuds mobiles
suivent une cible particulire.
52
Cette section prsente les sept modles de mobilit d'entit qui ont t proposs pour
l'valuation des performances d'un protocole de rseaux Adhoc. Les deux premiers modles
prsents, le modle de promenade alatoire et le modle de mobilit de promenade alatoire
avec pause sont parmi les plus utiliss actuellement.
4.2.1.1 Le modle de mobilit de promenade alatoire
Le modle 2D RWMM est un modle largement rpandu et utilis. Il est connu parfois sous
le nom du mouvement brownien. Pour son utilisation, le modle est parfois simplifi. Ce
modle est sans mmoire, car la vitesse et la direction courantes des nuds mobiles sont
indpendantes des vitesses et des directions prcdentes. Ceci peut produire des mouvements
peu ralistes tels que des arrts soudains et des retours angle aigu. D'autres modles, tels que
le modle de mobilit de Gauss -Markov reprsent la section 4.2.1.5 peut corriger ces
anomalies.
4.2.1.2 Le modle de mobilit de promenade alatoire avec pause
Modle de mobilit de promenade alatoire avec pause not RWpMM (Random Waypoint
Mobility Model) [87] inclut des temps de pause entre les changements de direction et/ou de
53
vitesse. Un nud mobile commence, en attendant, dans un endroit pendant une certaine
priode de temps (temps de pause)
Une fois la priode de temps expire, le nud mobile choisit une destination alatoire et
une vitesse distribue dans [ minspeed.. maxspeed ].
Le nud se dplace alors vers la nouvelle destination choisie avec la vitesse choisie.
l'arrive, il fait une pause pendant une priode de temps dfinie, avant de recommencer le
processus.
La figure 4.2 illustre le dplacement d'un nud mobile suivant le modle RWpMM. Le
modle RWpMM ressemble au modle RWMM si le temps est nul et minspeed= speedmin et
maxspeed = speedmax. RWpMM est galement un modle largement rpandu. Il est souvent
utilis pour l'valuation des performances des algorithmes et des protocoles de routage. Dans
la majorit des tests de performance qui utilisent le modle RWpMM, les nuds mobiles sont
d'abord distribus alatoirement dans le secteur de simulation.
4.2.1.3 Le modle de mobilit de direction alatoire
illustrent l'arrive du nud la frontire o, aprs avoir fait une pause, il choisit une nouvelle
direction.
Il existe aussi une version modifie du modle RDMM dans laquelle les nuds continuent
choisir des directions alatoires, mais ils ne sont plus forcs de se dplacer vers la frontire
du secteur de simulation avant de s'arrter et de changer de direction. Pour viter cela, le
nud choisit une direction alatoire et un endroit quelque part dans cette direction du
dplacement. Le nud fait alors une pause cet endroit avant de choisir une nouvelle
direction alatoire. Cette modification du modle RDMM produit des modles de mouvement
qui pourraient tre stimuls par le modle RWMM en y ajoutant des temps de pause.
4.2.1.4 Le modle de mobilit dans une rgion de simulation illimite
Dans le modle de mobilit dans une rgion de simulation illimite not BSAMM
(Boundless Simulation Area Mobility Model) [87], la direction et la vitesse courantes du
mouvement dpendent des directions et des vitessses prcdentes du nud mobile. Un
vecteur de vitesse v = (v, ) est utilis pour dcrire le dplacement. La position du nud est
reprsente comme par les coordonnes (x,y). Le vecteur de vitesse et la position sont mis
jour aprs chaque t unit de temps selon les formules suivantes:
v(t + t ) = min[max(v(t ) + v,0), V max]
(1)
(t + t ) = (t ) +
(2)
(3)
y (t + t ) = y (t ) + v(t ) sin (t )
(4)
55
Initialement, une vitesse et une direction sont assignes chaque nud mobile.
intervalle de temps fixe, un mouvement se produit qui met jour la vitesse et la direction de
chaque nud. Plus prcisment, la valeur de la vitesse et la direction au nime intervalle de
temps sont calcules en fonction des valeurs de la vitesse et de la direction du (n-1) ime
intervalle de temps et dune variable alatoire, en utilisant les quations suivantes :
_
s n = .s n 1 + (1 ). s + (1 ) s n 1
_
d n = .d n 1 + (1 ). d + (1 )d n 1
56
(5)
(6)
P = P (1, 0 )
P ( 2 ,0 )
P ( 0 ,1 )
P (1,1 )
P ( 2 ,1 )
P ( 0 , 2 )
P (1 , 2 )
P ( 2 ,2 )
(9)
o chaque lment P(a,b) reprsente la probabilit quun nud mobile passe de l'tat a
l'tat b.
Les valeurs de cette matrice sont utilises pour la mise jour de l'ensemble des positions x
et y du nud. La figure 4.6 donne un exemple de trajectoire du placement d'un nud mobile
57
utilisant ce modle. Ce modle est peu raliste par rapport au modle RWpMM ou RWMM car
les mouvements produits sont probabilistes et pas alatoires comme cest plutt le cas dans la
pratique.
4.2.1.7 Le modle de mobilit des sections de ville
Dans le modle de mobilit des sections de ville not CSMM (City section mobility model)
[87] le secteur de simulation est un rseau routier qui reprsente une section dune ville o on
veut tablir un rseau Adhoc. Les rues et les limites de vitesse sont dpendantes de la ville
que lon simule. Par exemple, les rues peuvent former une grille dans le centre ville avec une
route grande vitesse prs de la frontire du secteur de simulation pour reprsenter une
boucle autour de la ville. Chaque nud commence la simulation un point dfini sur une
certaine rue et choisit alors alatoirement une destination, galement reprsente par un point
sur une rue quelconque (figure 4.7).
L'algorithme du mouvement, de la destination courante la nouvelle destination, localise
un chemin correspondant au temps de voyage le plus court entre les deux points. En outre, on
peut considrer d'autres caractristiques telles qu'une limite de vitesse et une distance
minimum entre deux nuds. Aprs l'arrive la destination, le nud mobile effectue une
pause pendant une priode de temps dfinie, puis il choisit alatoirement une autre destination
et rpte le processus.
Ce modle fournit les mouvements ralistes pour une partie d'une ville puisquil limite
fortement le comportement de dplacement des nuds mobiles. Dans la pratique, les nuds
n'ont pas la capacit de se dplacer librement si on prend en considration les obstacles et les
rglements du trafic. En outre, les gens tendent se dplacer dans des modles semblables
la ville en marchant travers un campus. Le fait dobliger tout nud mobile suivre des
chemins prdfinis augmentera la moyenne du nombre de sauts dans les simulations.
La section 4.2.1 prsente le modle de mobilit qui simule les nuds dont les
comportements sont compltement indpendants. Cependant, dans un rseau Adhoc, il y a
beaucoup de situations o il est ncessaire de modliser le comportement des nuds quand ils
se dplacent ensemble. Par exemple, dans un scnario militaire un groupe de soldats peut
effectuer une mission, dans une partie de terrain, afin de dtruire des mines antipersonnel,
capturer des ennemis assaillants ou travailler simplement ensemble de faon cooprative pour
58
accomplir une tche commune. Afin de modliser de telles situations, un modle de mobilit
de groupe [95,102]est ncessaire pour simuler cette caractristique cooprative.
Cette section prsente cinq modles de mobilit de groupe. Quatre d'entre eux, dont le plus
gnral est le modle de la mobilit de groupe avec point de rfrence (RPGM), sont
troitement lis. En effet, les modles de mobilit de colonne, de communaut nomade et de
poursuite peuvent tre mis en uvre en tant que cas spciaux du modle RPGM.
4.2.2.1 - le modle exponentiel alatoire corrl.
b ( t + 1) = b ( t ) e
+ (
(1 ( e
)) r
(10)
Le modle de mobilit de colonne not CMM (Column Mobility Model) [87,90] s'avre
utile pour modliser une recherche sur le terrain. Ce modle reprsente un ensemble de nuds
mobiles qui se dplace globalement en parallle devant un axe donn. (Par exemple, une ligne
de soldats marchant ensemble vers leur ennemi ou des oprations de recherche pour
dsactiver des mines antipersonnel). Une lgre modification du modle CMM permet aux
nuds mobiles de se suivre ( par exemple un groupe de marcheurs en file indienne). Pour
l'implantation de ce modle, une premire grille de rfrence (formant une colonne de nuds
mobiles) est dfinie.
Ensuite, chaque nud (figure 4.8) est plac par rapport son point de rfrence dans la
grille de rfrence ; on permet alors aux nuds mobiles de se dplacer alatoirement autour
de son point de rfrence utilisant un des modles de mobilit dentit reprsents dans la
section 4.2.1 (dans la littrature, on propose dutiliser le modle de mobilit de promenade
alatoire RWMM prsent dans la section 4.2.1.1). Le nouveau point de rfrence pour un
nud mobile est dfini comme :
(11)
59
Comme les nomades qui se dplacent dun endroit un autre, le modle de la communaut
nomade NCMM (Nomadic community Mobiity Model) [88] reprsente des groupes de nuds
mobiles qui se dplacent ensemble dun point lautre. Dans chaque communaut, les
individus maintiennent leur propre espace personnel o ils se dplacent de manire alatoire.
De nombreuses applications existent pour ce type de scnario, par exemple, un groupe
d'individus en train de visiter un muse.
Dans le modle CNMM , chaque nud utilise un des modles de mobilit dentit
prsents dans la section 4.2.1, autour d'un point de rfrence donn. Quand le point de
rfrence change, tous les nuds mobiles dans le groupe se dplacent vers le nouveau secteur
dfini par le point de rfrence et commenceront errer autour du nouveau point de rfrence
(figure 4.9). Les paramtres pour le modle de mobilit d'entit dfinissent quelle distance
un nud mobile peut errer autour du point de rfrence.
Compars au modle de mobilit de colonne CMM o chaque nud un point de
rfrence individuel, les nuds dans le modle de mobilit nomade NCMM partagent un point
de rfrence commun.
60
Le modle de mobilit de poursuite, not PMM ( Purse Mobility Model) [90] essaie de
reprsenter, comme son nom lindique , des nuds mobiles qui suivent une cible particulire.
Ce modle consiste en une quation de mise jour simple pour la nouvelle position de nud :
New_position = old_position + acceleration(target old-position) + random_vector (12)
Le modle de mobilit d'un groupe avec point de rfrence not RPGM (Rfrence Point
Group Mobility Model) reprsente le mouvement alatoire d'un groupe de nuds aussi bien
que le mouvement alatoire de chaque nud individuellement dans le groupe. Les
mouvements du groupe sont bass sur le chemin parcouru par un centre du groupe qui est
utilis pour calculer le mouvement du groupe par l'intermdiaire d'un vecteur de mouvement
qui peut tre choisi alatoirement ou tre prdfini.
Le mouvement du centre du groupe caractrise compltement le mouvement de son groupe
(la direction et la vitesse) . Les nuds individuels se dplacent alatoirement par apport
leurs propres points de rfrence prdfinis, dont les mouvements dpendent du mouvement
du groupe.
La figure 4.11 illustre le mouvement de trois nuds utilisant le modle RPGM. Ainsi,
linstant t, les trois points noirs reprsentent des points de rfrence, RP(t), pour les trois
nuds. Le modle RPGM utilise le vecteur
pour calculer les nouveaux points de
rfrence, RP(t+1), l'instant t+1.
61
La nouvelle position de chaque nud est alors calcule par la somme vectorielle du
vecteur
La longueur de RM est uniformment distribue dans un disque qui a pour centre RP(t+1).
Tandis que sa direction est uniformment distribue dans [ 0 , 2 ].
Le modle RPGM [90]a t conu pour faire face des scnarios tels qu'une avalanche
aprs laquelle une quipe de secours se composant dhumains et de chiens travaillent
cooprativement. Les guides humains (centres des groupes) tendent dfinir un chemin
gnral puisqu'ils connaissent habituellement l'endroit approximatif des victimes. Chacun des
chiens cre son propre chemin alatoire autour du secteur gnral choisi par leurs guides
humains.
4.2.2.6 Le modle de mobilit avec obstacles
Le modle de mobilit avec obstacle a t conu pour modliser le mouvement des nuds
mobiles dans les terrains qui ressemblent des topographies relles. Des objets modlisent les
btiments et d'autres structures qui empchent les mouvements des nuds, ainsi que leur
transmission sans fil. En modlisant un tel terrain, un utilisateur peut dfinir les positions, les
formes et les tailles de ces objets. Ce modle peut manipuler des formes de positions
arbitraires pour les objets, permettant de modliser beaucoup de terrains rels.
Le deuxime composant du modle de mobilit est un graphe de mouvement qui
reprsente les dplacements des nuds. Ce graphe planaire est le diagramme de Voronoi des
coins des obstacles ( les arrtes sont des segments qui sont d'une distance gale des deux coins
dun obstacle). Ainsi, ce modle est bas sur l'intuition que les chemins tendent se dfinir a
mi- distance entre les btiments adjacents. Ce modle permet galement le mouvement par
l'intrieur des btiments.
Le troisime composant du modle est le choix des routes. Les nuds utilisent les chemins
les plus courts (en terme de longueur euclidienne) pour se dplacer entre deux points du
graphe du mouvement, c'est--dire quils suivent le chemin le plus court dans le diagramme
de Voronoi. Le placement des objets et des chemins les reliant sont calculs au dbut de la
simulation et ne changent pas pendant toute la simulation. Les nuds sont distribus au
hasard le long des chemins, ils choisissent une destination est puis se dplacent vers cette
destination en suivant le chemin le plus court partir de sa position courante.
62
Ainsi, chaque nud calcule le chemin le plus court entre le graphe cre par les chemins et
puis se dplace vers cette destination en utilisant le chemin calcul. Lorsqu'il atteint sa
destination, le nud fait une pause pour une certaine priode de temps. Il choisit alors une
nouvelle destination, calcule le chemin le plus court pour l'atteindre, et reprend le mouvement.
Les nuds peuvent se dplacer l'intrieur des btiments car le plus court chemin entre deux
endroits peut exiger le passage par l'intrieur d'un btiment.
4.2.3 Discussion sur les modles de mobilit
63
Cependant, cette version est identique au modle de mobilit de promenade alatoire, RWMM,
en y ajoutant des temps de pause.
Le modle de mobilit dans une rgion de simulation illimite, BSAMM, fournit deux
modles de mouvement auxquels on pourrait s'attendre dans la ralit. En outre, ce modle est
le seul qui permet aux nuds mobiles de se disperser dans le secteur, en liminant les effets
de la frontire sur l'valuation des performances. Cependant, les effets secondaires qui se
produiraient en permettant aux nuds mobiles de se dplacer autour d'un tore pourraient tre
considrables. Par exemple, un nud mobile qui se dplace dans la mme direction vers un
nud statique deviendra son voisin plusieurs reprises.
Le modle de mobilit Gauss-Markov fournit des modles de mouvement auxquels on
pourrait s'attendre dans la ralit si des paramtres appropris sont choisis. En outre, la
mthode utilise pour forcer les nuds partir loin des bords du secteur de simulation
(vitant ainsi les effets du bord de secteur) est intressante.
Mme si le modle probabiliste de promenade alatoire, PRWMM, fournit des mouvements
auxquels on pourrait s'attendre dans la ralit, le choix des paramtres appropri pour sa
matrice de probabilit peut tre difficile.
Le modle de mobilit des sections de ville, CSMM, semble crer des mouvements
ralistes pour une section dune ville , puisqu'il limite svrement le comportement des
dplacements des nuds mobiles. Ces nuds n'ont pas la capacit derrer librement sans se
soucier des obstacles et dautres rglements de trafic.
Concernant les cinq modles synthtiques de mobilit de groupe pour les rseaux adhoc,
on pourrait dire que le modle exponentiel alatoire corrl, ECRMM, semble dcrire
thoriquement tout autre modle de mobilit. Cependant, le choix des valeurs appropries
pour les paramtres est presque impossible. Les modles de colonne, de la communaut
nomade et de poursuite sont des modles utiles pour des scnarios ralistes spcifiques. Les
modles de mouvement qu'ils fournissent peuvent tre obtenus en changeant les paramtres
lies au modle d'un groupe avec point de rfrence (RPGM). Enfin, un modle de mobilit
d'entit doit tre conu non seulement pour manipuler le mouvement d'un groupe de nuds
mobiles, mais aussi le mouvement des nuds individuellement l'intrieur du groupe.
La table 4.1 prsente de manire compacte les principales caractristiques, comme la
vitesse, la direction et la nature (raliste ou pas) des modles de mobilit.
64
ENTITE
Modles de
mobilit
Nom
Direction alatoire
Raliste
oui
oui
oui
mouvement
brownien
RWpMM
oui
oui
oui
WLAN
RDMM
oui
oui
peu
WLAN- WMAN
BSAMM
oui
oui
oui
WLA - WMAN
non
non
peu
PCS
PRWMM
oui
non
peu
WLAN
CSMM
oui
non
oui
ECRMM
oui
non
non
NCMM
oui
non
oui
visite touristique
RPGMM
oui
oui
oui
situation de secours
65
Type d'application
RWMM
Gauss-Markov
GROUPE
Vitesse alatoire
rgulation du trafic
----
Les mtriques de mobilit directes , comme la vitesse maximale ou moyenne, sont des
mthodes de mesure directes, souples et faciles utiliser. Il sagit des mesures prleves des
mouvements des nuds. Mais gnralement, elles ne refltent pas exactement la mesure relle
de la mobilit.
Diffrentes mtriques appartenant cette catgorie utilisent dautres paramtres comme la
vitesse relative moyenne [105], le degr de dpendance spatiale et/ou temporelle [97] que
nous dtaillerons dans la suite.
Pour le modle de mobilit RandomWaypoint [101, 104], lutilisation temps de pause
pour reflter la mobilit des nuds est propre au modle de mobilit RandomWaypoint
(RWP). Ce modle est devenu un modle standard dans la recherche sur les rseaux sans fil et
il semble crer des modles de mobilit ralistes. Dans ce modle, plus le temps de pause est
grand, plus la mobilit est faible.
La vitesse moyenne est dfinie [107] en fonction de la vitesse relative de toutes les paires
de nuds du rseau comme suit :
Supposons que P(m,t) et P(n,t) sont respectivement les positions des nuds m et n
linstant t. La vitesse relative entre m et n est dfinie comme :
V (m, n, t ) =
d ( P(m, t ) P(n, t ))
dt
(13)
1
=
T
t0 +T
t0
| V (m, n, t ) | dt
(14)
Si on note par Mm,n la vitesse moyenne relative entre la paire de nuds (M,N). La vitesse
relative moyenne, note M, du rseau est ainsi dfinie comme tant la moyenne sur toutes les
paires de nuds du rseau comme :
66
M=
N
N
1
1
M m ,n =
M m, n
N ( N 1) / 2 m ,n
N ( N 1) / 2 m=1 n = m+1
(15)
(16)
gnralement utilises dans le cas des problmes physiques dont aucune mthode directe nest
connue, il sagit des mesures issues des observations physiques suivies dune modlisation
mathmatique.
Les mtriques drives intgrent des paramtres provenant des modles de la thorie des
graphes ainsi que d'autres modles mathmatiques. Ces mtriques dduites des modles de
graphes font appel aux paramtres caractrisant ltat des liens, savoir : le taux de
changement des tats de lien [108,111], la dure du lien [97,109] et la dure moyenne du
chemin [97].
La mtrique de mobilit propose dans [89][112] est une mtrique qui drive des modles
probabilistes. Les auteurs de [108,111] se sont bass sur le paramtre de taux de changement
dtat de lien comme un indicateur de changement de la topologie. Si un lien entre deux
nuds est tabli ou rompu en raison dun dplacement de nuds , nous considrons que l'tat
de ce lien a chang. Le taux de changement dtat de lien reprsente le nombre total des
vnements de changement des tats des liens par unit de temps.
La mtrique de la moyenne de la dure dun lien [97,111] est dfinie comme la
moyenne des dures des liens entre les paires de nuds qui se trouvent chacun dans la porte
de transmission de l'autre. Autrement dit, La dure de lien est l'intervalle de temps pendant
lequel chacun des nuds est dans la porte de transmission de l'autre.
Pour tous les couples source-destination du rseau, la dure moyenne du chemin [109] est
dfinie comme la moyenne des dures de tous les liens (tronons) qui constituent le chemin.
La dure moyenne du chemin est l'intervalle de temps pendant laquelle tous les liens sur un
chemin ( partir d'une source une destination) existent.
La Mesure de mobilit aborde dans [107] drive de la vitesse relative moyenne.
Lapproche fait appel la notion de fonction distance et apparait beaucoup plus signifiante
dans le cas de deux nuds qui ont des zones de transmission chevauches. La relation est
dfinie comme une fonction distance entre deux nuds et satisfait les conditions suivantes:
elle croit de 0 1 (monotone). La drive de la fonction distance vaut 0 ltat initial. Elle
croit en fonction de la distance et atteint son maximum la frontire de la transmission, puis
diminue pour des valeurs de distance plus grandes, et s'approche de la valeur 0 linfini.
La mesure de la mobilit est dfinie ainsi comme la moyenne de la drive des fonctions
distances de toutes les paires de nuds du rseau.
Plusieurs travaux ont t mens pour tudier la relation entre les mtriques de mobilit
directes et drives. Ces recherches ont essay de rpondre deux questions majeures:
Comment valuer les diffrents modles de mobilit en utilisant les mtriques drives ? Et
quel point les mtriques de mobilit refltent les performances de routage ?
Les auteurs de [113] montrent que le taux de changement dtat de lien varie linairement
en comparaison avec la vitesse. (si la vitesse augmente, le taux de changements dtat des
liens augmente). Par ailleurs, les mmes auteurs ont montr, travers les simulations, que
pour des modles de mobilit diffrents, la diffrence du taux de changement dtat des liens
est petite. Ceci explique que le taux de changement dtat des liens ne permet pas de
diffrencier parfaitement les modles de mobilit.
68
T t
Ax (t ) Ax (t + t )
t =0
T t
(17)
Enfin, la distance moyenne Ax (t ) dun nud x linstant t, dans un rseau donn, est la
moyenne des distances dist( n x , ni ) le sparant de chaque nud i du rseau:
dist (n x , ni )
(18)
n 1
i =1
Aprs avoir expos les diffrents modles de mobilit et expliqu la ncessit des
mtriques de mobilit dans la simulation des rseaux, la section suivante sera rserve la
prsenttaion de nos techniques de mesure de la mobilit dans les Manets. Notre mtrique
choisie sera teste pour confirmer sa validit et ses points forts.
n
Ax (t ) =
Dans cette optique, nous avons envisag deux types de tests : dabord, voir si notre
mtrique reflte le taux de changement dtat des liens dans le rseau et ensuite valuer son
comportement vis--vis ds paramtres rseau savoir : densit du rseau, porte des nuds,
vitesse des nuds,etc.
4.5.3 Nouvelle Mtrique pour la mesure de la mobilit
Un rseau ad hoc mobile, est un systme autonome de nuds mobiles relis par des liens
sans fil. Les nuds doivent donc collaborer pour organiser lchange dinformations de
contrle et permettre lacheminement du trafic. Ces rseaux doivent possder la capacit de
sautoconfigurer, sans intervention humaine.
69
Les nuds sont libres de se dplacer arbitrairement ( tout moment, des nuds peuvent
joindre le rseau, comme dautres peuvent le quitter), ce qui fait que la topologie du rseau typiquement multisaut - peut changer alatoirement et rapidement n'importe quand. Ceci
induit la rupture de quelques liaisons ou la construction de nouvelles liaisons
(unidirectionnelles et bidirectionnelles).
Par consquent, chaque nud dans le rseau peut se trouver dans lun des quatre tats
suivants : Le nud se dplace et ses voisins sont fixes, le nud est stable et ses voisins se
dplacent, le nud et ses voisins sont en mouvement, le nud et ses voisins sont immobiles.
Ces quatre tats sont lorigine des changements de ltat des liens entre les nuds du rseau.
En se basant sur ce constat simple et frquent, nous dfinissons notre mesure de la mobilit
qui reprsente le degr de mobilit des nuds dans le rseau. Cette mesure n'a pas dunit et
ne dpend pas du modle de mobilit sous-jacent. Son valuation se fait des intervalles de
temps discrets et rguliers.
4.5.3.1 Mobilit dun nud
Linstant t-1
linstant t instantt+1
Mob( A, t ) =
NbrofNodesIn(t ) + NbrOfNodesOut (t )
NbrOfNodes (t 1)
(19)
o,
NbreOfNodesIn(t) : reprsente le nombre de nuds qui ont joint la zone de couverture du
nud A pendant lintervalle de temps de dure t.
NbrOfNodesOut(t) : reprsente le nombre de nuds qui ont quitt la zone de couverture du
nud A pendant lintervalle de temps de dure t.
70
Le degr de mobilit peut tre employ aussi pour extraire des informations significatives de
la mobilit du rseau entier, comme la dtection des secteurs basse, moyenne et lev
mobilit et mme les frontires entre ces secteurs.
Nuds avec 15% et 20% constituent une frontire entre deux zones de mobilit (lev et basse)
Cette quantification a plusieurs avantages. Dabord, chaque nud peut valuer de manire
autonome et automatique son degr de mobilit dans des intervalles de temps rguliers (tandis
quil y a un change de message hello).
Le calcule du degr de mobilit est rapide et n'exige pas assez de consommation des
ressources.
Application
EQ
AODV diffuse une requte de route (RREQ) dans le but de crer un chemin vers une certaine
destination. Par consquent le message RREQ emprunte plusieurs chemins vers la destination.
Dans le processus ordinaire de dcouverte de route, une fois le premier message RREQ est
reu, la destination rpond par un message de rponse de route (RREP) et ignore toutes les
autres requtes qui ont la mme mtrique et qui proviennent de la mme source. Cette
dmarche ignore les routes avec une qualit de service meilleure que le premier chemin
choisi. Il est propos de faire adapter le protocole AODV pour quil tienne en compte des
informations de mobilit lors du processus de dcouverte de route en choisissant les routes les
plus stables.
71
De ce fait, nous pouvons considrer que les chemins possibles (qui ont la mme mtrique en
nombre de sauts) entre la source et la destination comme des variables alatoires relles
discrtes de mme longueurs. En statistique et probabilit, la mobilit de chaque chemin sera
donc caractrise par deux paramtres statistiques: sa mobilit et sa variance. La variance est
une mesure arbitraire servant caractriser la dispersion des degrs de mobilit mesurs au
niveau des nuds constituant le chemin (quation 21).
avrroute
varroute
D +1
i =1
qi
(20)
D +1
D +1
i =1
(qi avrroute )
(21)
D +1
o :
qi est le degr de mobilit du nud i
D est le nombre de sauts entre la source et la destination
De mme, nous proposons damliorer le processus de maintenance des routes en utilisant
toujours les informations de mobilit mesures au niveau de chaque nud.
R
EQ
72
M i (t ) =
NodesOuti (t )
NodesIni (t )
+ (1 )
Nodesi (t )
Nodesi (t )
(22)
o,
NodesOut(t) : Le nombre des nuds qui ont quitt la zone de couverture de A pendant
lintervalle de temps [t,t+t].
NodesIn(t)
Nodes(t)
Plusieurs simulations ont t effectues [114] pour statuer sur la valeur optimale de .
Le rsultat des simulations montrent quune valeur proche de 0.75 maximise les performances
des protocoles de routage.
La figure 4.17 illustre un exemple de quantification de la mobilit propose.
73
Sur ltat de la figure 4.17(a), le nombre des voisins du nud A est 11. Supposons que
pendant la priode t, son voisinage a subi les changements suivants : Quatres nuds (en
bleu) quittent sa zone de couverture, et deux autres (en rouge) joignent sa zone (figure
4.17(b)). En consquence, aprs la priode de temps t, le nud A se trouvera dans l'tat de la
figure 4.17(c) avec cinq changements.
la fin de chaque intervalle de temps, le nud pourra faire une valuation du changement
de son voisinage reprsente par la mobilit relative prcite, qui est dans notre exemple gale
:
M 1 / 2 = 0. 5
4
2
+ (1 0.5) 29%
11
9
(23)
La quantification de la mobilit de nud n'a pas dunit, sa valeur est comprise entre 0 et
1, et ne dpend pas du modle de mobilit utilis [116]. Chaque nud dans le rseau ad-hoc
peut faire une valuation autonome et automatique de son degr de mobilit dans des
intervalles de temps rguliers (ex. lintervalle de transmission des messages Hello). Ainsi, le
calcul priodique de la mobilit est simple, et n'exige pas assez de ressources en terme de
mmoire et unit de traitement et de calcul (CPU).
b- Mobilit du rseau
Nous dfinissons la mesure moyenne, dans le temps, de la mobilit rseau M dans des
intervalles rguliers de temps comme suit :
1
Mob ( t ) =
N
N 1
M i ( t )
i =0
(24)
t
Mob (k )
T k
(25)
et T le temps de simulation
Dans un premier temps et afin de valider notre approche, la section suivante sera rserve
la validation du comportement de la mobilit du rseau prcdemment dfinie. Ce
comportement sera mesur en changeant les paramtres cls caractrisant les environnements
MANET.
4.5.4 Simulations et rsultats
74
RWP).Ceci permet dimposer lors des simulations les mmes conditions de mobilit
(autrement la mme faon de mesure de la mobilit).
Afin dvaluer le gain apport par lutilisation de la mtrique propose sur les
performances des protocoles de routage de la famille MANET, il est ncessaire d'tudier son
comportement dans diffrentes configurations. Ainsi, la mtrique est mise lpreuve
travers plusieurs exprimentations : valuer son comportement vis--vis des paramtres
rseau comme (modles de mobilit, la densit du rseau,etc.) et ceux qui caractrisent les
nuds (comme la vitesse, la porte,)
Pour ceci, nous avons considr deux types de scnarios rseau qui sont lis aux deux
types de modles de mobilit tudis dans la section 4.2 (mobilit entit, et des modles de
mobilit de groupe). Pour chaque type de modle de mobilit, nous avons gnr une varit
de scnarios de rseau tels que rsums dans les tableaux 1 et 2. Le premier type correspond
aux modeles de mobilit dentit et value le cas des modles RWP et modles RGM. Le
deuxime scnario concerne les modles de mobilit de groupe et sera reprsent par le
modle RPGM.
Chaque scnario a ses propres paramtres qui le caractrisent des autres. Par exemple, les
paramtres du modle RWP sont : les dimensions de la rgion, le nombre de nuds N, et le
temps de pause. Pour le modle de RGM, les paramtres sont les dimensions de la rgion, et le
nombre de nuds N .
Aussi, pour garantir un environnement plus raliste nous avons considr des scnarios
dans le pire des cas, en supposant que la vitesse maximale des nuds est gale Vmax = 40m / s
et la vitesse minimale est gale V min = 0m / s . Pour le modle RGM, et pour imposer un
environnement trs dynamique, la vitesse et la direction sont mises jour chaque t =2,5
secondes, avec V max = 0.5 et max = 0.125 .
Le tableau 4.2, reprsente le premier type de scnario rseau, simule un groupe de nuds
qui se dplacent alatoirement dans une rgion carre. titre d'exemple, le scnario S1 relatif
au modle RWP considre 30 nuds qui se dplacent arbitrairement dans une superficie de
800m avec un temps de pause gal 0 seconde. Le scnario G1 relatif au modle RGM
prvoit 50 nuds se dplaant dans une rgion carre de 700m .
Le deuxime type de scnarios de rseau (modle de mobilit de groupe) est reprsent par
le tableau 4.3. Il utilise le modle RPGM impose aux nuds de se dplacer dans une rgion
carre 1000m. Le centre logique de chaque groupe se dplace selon le modle RWP .
Pour rendre les simulations plus ralistes, nous imposons ce scnario des conditions
strictes, en exigeant une vitesse maximale du centre logique de 40m/s, un temps de pause est
gal 0 et un intervalle de mise jour du vecteur vitesse gale = 1 .
Le scnario P1 contient 5 groupes de 10 nuds (au total 50 nuds). L'un des points de
rfrence des nuds est situ au centre logique de chaque groupe, et les 9 autres points de
rfrence sont situes aux sommets d'un hexagone rgulier de ct gal 0.25m, centr au
centre logique. La longueur du vecteur de vitesse a une distribution uniforme entre 0 et
Rmax=0.25. Tous les points de rfrence des 5 nuds sont situs au centre logique de chaque
groupe. Le Scnario P2 assure un mouvement intragroupe plus important par rapport au
scnario P1 ( R max = 0.25 ).
75
Dimension rseau
S1
800X800
S2
800X800
S3
Temps de
pause
30
Dimension Rseau
G1
700X700
50
40
G2
800X800
50
800X800
50
G3
900X900
50
S4
600X600
50
G4
800X800
20
S5
700X700
50
G5
800X800
30
S6
800X800
50
G6
800X800
40
S7
800X800
50
10
Comme notre mtrique dpend du paramtre , nous avons tudi sa relation avec le taux
de changement dtat des liens. Les valeurs de considres sont: = 0.00, 0.25, 0.50, 0.75,
et 1.00. En outre, et pour assurer le mme environnement pour toutes les simulations, le temps
de la simulation est 500s et la porte radio pour tous les scnarios est gale 150m . Enfin, et
pour plus de prcision, notons que chaque mesure dans le reste du prsent document
reprsente une moyenne sur un chantillon de 30 mesures.
Scnario Pi
Details
P1
P2
P3
P4
P5
P6
Comme la mobilit des nuds est fortement lie aux taux de changement dtat des liens,
la validation de notre mtrique requiert une forte relation avec le taux de changement des tats
des liens. Pour ceci, nous avons procd cette comparaison. Etant donn que notre mtrique
est normalise par N (nombre total de nuds ), il est judicieux de normaliser le taux de
changement des tats de liens par N(N-1)/2. Ce nombre reprsente le nombre maximum de
liens dans un rseau contenant N nuds.
76
En outre, comme ltat des liens change dans le temps, le recours la contrainte temporelle
demeure ncessaire. Pour plus de simplicit, on suppose que le rseau est en tat dquilibre
la fin de chaque intervalle de mesure. Ceci permet de contourner les problmes lis
limplmentation des paramtres temporels.
Pour tous les scnarios, le calcul de chaque mesure est donc valu par quantification des
intervalles de temps rguliers et discrets. Le pas de quantification choisi (pour deux mesures
conscutives) est gal t = 0.05s . Ce choix est fait de manire avoir une meilleure
estimation du taux de changement dtat des liens.
Pour calculer la dure moyenne normalise du taux de changement dtat des liens, nous
dfinissons la fonction L (t) comme tant le nombre de changements dtat des liens qui s'est
produit lintervalle de mesure.
Si on note par l(t) la fonction qui reprsente le nombre de changements dtat des liens
dans lintervalle du temp [0,t], alors:
l( t ) =
L( t )
= ( t tk )
t
k
(26)
l=
2 l (t )
t
T k N (t ) N (t 1)
(27)
l=
2t
L( T )
N( N 1 ) T
(28)
Les rsultats des simulations effectues montrent que la moyenne de la mobilit rseau
varie linairement avec le taux moyen normalis de changement dtats de lien pour les deux
types de scnarios de rseaux. .
Les Figures 4.18 (a) et 4.18 (b) illustrent les rsultats des simulations correspondant au
premier type de modles de mobilit (modles de mobilit dentit) pour diffrentes valeurs
de . On constate que la variation de la moyenne normalise du taux de changement dtat de
lien est linaire par rapport M pour lensemble des scnarios rseaux prcits.
Cette relation est maintenue pour toutes les valeurs de ( = 0.00, 0.25, 0.50, 0.75, 1.00).
Par contre, on remarque que ces valeurs ont un impact sur les tangentes obtenues.
77
Figure 4.18 Taux de changement dtat des liens vs. Mobilit du rseau
Figure 4.19 Taux de changement de ltat des liens vs. Modle de groupe.
En rsum, notre approche pour la mesure de la mobilit dpend fortement de ltat des
liens. Les rsultats des simulations confirment que notre mtrique reflte exactement le taux
de changement dtat des liens dans un rseau adhoc, indpendamment du modle de mobilit
sous-jacent.
Pour comparaison, considrons le cas de ltude [3]. Ses auteurs ont trouv une relation
entre le concept de distance et le taux de changement de ltat des liens. Ainsi, ils
dfinissent une fonction de distance entre deux nuds comme une relation de dispersion. La
fonction distance doit satisfaire les exigences suivantes : Elle doit tre monotone et croissante
de 0 1, sa drive sannule pour une distante gale 0, atteint son maximum la frontire de
la porte de communication, puis dcrot pour des valeurs suprieures et tend vers 0 linfini.
Leur estimation de la mobilit est dfinie comme tant la moyenne de la drive de la
fonction distance entre toutes les paires de nuds du rseau. Plusieurs fonctions de distance
qui satisfont les conditions prcites existent. Par consquent, les mesures retournes
dpendront des fonctions distances choisies. D'autre part, ces fonctions distance sont
gnralement complexes et font intervenir des oprations et fonctions difficiles pnalisant les
environnements de simulation rseau (en terme de ressources mmoire et CPU). En effet, les
fonctions distance dfinies ( ce jour) pour la mesure de la mobilit font intervenir des
oprations complexes et coteuses en terme de mmoire et CPU (telles que les fonctions
drivation, intgration, produit itratif, etc.). Chose qui peut saturer les ressources et paralyser
le fonctionnement du rseau.
Aussi, et dans un environnement rel, le cas de deux nuds voisins sans aucun lien radio
entre eux est couramment prsent (ex: prsence d'un obstacle: mur). Par consquent, la notion
de distance, dans un rseau ad hoc, ne peut pas reflter exactement les taux de changement
dtat des liens et donc la linarit ne peut pas tre garantie.
79
Ainsi, En effet, et par construction, notre mesure de mobilit M , value des temps
discrets, peut tre considre comme une solution alternative simple pour la mesure de la
mobilit, contrairement la mesure de mobilit, temps continu, propose dans [113]. En
outre, elle est triviale et simple implmenter
Application
Une premire tentative pour une exprimentation relle de notre approche est propose dans
[122.]. Lexprience propose dutiliser un rseau de portes programmables FPGA (fieldprogrammable gate array,) pour former un systme mobile intelligent (appel MIS, Mobile
Intelligent System) capable dauto-collaborer dans des situations critiques (de sauvetage en
cas de feu, tremblement). Les FPGAs sont des circuits intgrs trs haut niveau
d'intgration. Ils sont entirement re-configurables ce qui permet de les reprogrammer
volont afin d'acclrer notablement certaines phases de calculs.
L'avantage de ce genre de circuit est sa grande souplesse qui permet de les rutiliser volont
dans des algorithmes diffrents en un temps trs court.
Dans le but de mesurer quel point notre mesure de mobilit est impacte par les
paramtres rseau, il est ncessaire de savoir comment ces paramtres rseau peuvent
impacter notre mesure mobilit. Autrement, il sagit dvaluer le comportement de notre
mesure propose lorsque les paramtres du rseau changent. Les principaux paramtres, objet
de lvaluation, sont: le nombre de nuds, les dimensions du rseau, la porte des nuds et le
scnario de mouvement des nuds.
Pour ceci, nous avons considr un rseau adhoc de 50 nuds. Ces derniers se dplacent
arbitrairement dans une superficie de 1000m selon le modle RWP. Les simulations se
droulent sur une priode de 500s. est gale 0.50 (pour donner la mme chance aux
nuds entrants et sortants de quitter ou de joindre la zone de couverture, mutuellement) et le
pas de quantification est de 0.005 seconde.
A chaque fois, on change les paramtres rseau et on observe le comportement de la
mobilit du rseau.
Densit du rseau
Un point crucial pour les MANETs est la manipulation d'un grand nombre de nuds. Plus
le nombre de nuds est important plus la comptition est importante et la gestion du rseau
devient complexe. Plusieurs travaux [121,122] ont montr limpact de la densit du rseau sur
les performances des protocoles de routage dans les rseaux MANETs.
80
Afin de mesurer l'effet de la densit du rseau sur la mobilit du rseau. Nous avons
considr un rseau avec les configurations suivantes : 50, 100, 150 et 200 nuds. Aussi,
nous avons suppos que tous les nuds ont une porte de 100 m et se dplacent en utilisant le
modle alatoire RWP [96,103], avec une vitesse maximum de 144 km/h (mobilit leve).
Le graphe de la figure 4.20 montre que la densit du rseau affecte sa mobilit. Ainsi, si le
nombre de nuds dcrot, la mobilit du rseau crot considrablement. Ceci explique que les
MANET deviennent trs sensibles au changement d'tat des liens dans le cas o le nombre de
nuds diminue.
Effet de la vitesse
La plupart des tudes effectues pour mesurer le degr de mobilit sont limites.
Lutilisation de la moyenne ou de la vitesse maximale comme une mesure de mobilit pose un
problme dans le sens o le mouvement relatif entre les nuds n'est pas reflt par une telle
mesure; aussi, lutilisation de la moyenne ou de la vitesse maximale avec diffrents modles
de mobilit ou dans un rseau avec des dimensions diffrentes induit gnralement une
variation du taux de changement dtat des liens.
81
travers les simulations, nous remarquons que la mobilit du rseau est fortement lie
avec la vitesse des nuds. Pour ceci, nous avons considr un rseau MANET avec 50 nuds
avec une porte de 100 m chacun puis nous avons chang la vitesse maximale des nuds dans
la simulation entre 0ms et 60ms (par pas de 20ms).
Le schma 3 indique clairement que l'augmentation de la vitesse implique
automatiquement une augmentation de la mobilit du rseau. En effet, quand les nuds se
dplacent avec une grande vitesse, leur voisinage change (des nuds joignent et/ou quittent
leurs zones de couverture). Ceci induit un changement important dtat des liens avec leurs
voisins.
Effet de la porte des nuds
La porte des nuds joue un rle dterminant et principal pour les performances des
protocoles de routage dans rseaux ad hoc [100,123]. Ainsi, autant la porte est grande autant
le nombre de sauts entre la source et la destination est petit. Aussi, la connectivit globale de
rseau samliore et le taux de paquets livrs avec succs augmente.
Si la porte des nuds est assez grande, un grand nombre de nuds se trouveront dans la
zone de couverture dun voisin donn, chose qui rduit le taux de changements de ltat des
liens avec ce nud.
Dans le but de dduire la relation entre la porte et la mobilit du rseau, nous supposons,
pour la simulation, un rseau de 50 nuds avec une mobilit trs leve (la vitesse maximum
des nuds est de 40ms). La porte prendra successivement les valeurs : 50m, 100m, 150m et
200m.
82
Daprs la figure 4.22, nous dduisons que la mobilit varie inversement avec le porte.
Ainsi, la mobilit devient importante si nous avons des nuds dont la porte est petite. En
effet, dans le cas d'une petite valeur de porte, les nuds voisins qui se dplacent rapidement
ont plus de chance pour joindre et quitter rapidement la porte de leurs voisins. En
consquence, le taux de changement de ltat des liens devient important.
Effet des modles de mobilit
Les modles de mobilits utiliss [87-90,105] lors des simulations de rseau ad-hoc font
partie intgrante de celle-ci, au mme titre que les modles de propagation ou les protocoles
quon simule. La diversit des modles dcrits et implments offre la possibilit de choisir le
modle de mobilit le plus appropri selon le type de simulation quon veut entreprendre.
Ce paragraphe a pour but danalyser et de comparer le comportement de la mobilit vis-vis des principaux modles de mobilit utiliss lors des simulations. Pour ceci, nous avons
choisi les modles : random waypoint model, manhattan model et reference point group
model. Une description dtaille de ces modles est donne dans la section 4.2 .
La figure 4.23 montre que la mobilit du rseau dpend du modle de la mobilit utilis.
Pour le modle Random WayPoint[96,103], la moyenne et la variance de la mobilit sont
stables durant toute la simulation. Le modle de Manhattan, prsente le mme comportement.
Ce comportement est produit gnralement quand les nuds sont au voisinage dune
intersection de routes.
83
Enfin, la mesure de mobilit dans le modle de groupe avec point de rfrence est
gnralement gale 0, mais elle change dramatiquement. Ce changement rapide se produit
quand les groupes sapprochent l'un de l'autre.
Conclusion
Du fait des progrs observs en matire de reprsentation de lenvironnement, de
modlisation des objets et de leurs comportements, le recours la simulation est devenu un
moyen trs accessible pour amliorer les performances tout en rduisant les cots.
Les missions confies la simulation sont de natures varies, de lapprentissage initial la
gestion de situations complexes. Lobjectif commun est une amlioration de la capacit
oprationnelle par rduction des dlais de conception et des risques, notamment humains, en
limitant limpact sur les cots dentretien.
Ce que tous les modles de mobilit prsents prcdemment ont en commun est que les
modles quils crent ne sont pas ncessairement comparables aux mouvements dans la
ralit. En particulier, les gens sur des campus universitaires ou dans des centres
commerciaux ne se dplacent gnralement pas en directions alatoires. Ils tendent choisir
une destination spcifique et suivre un chemin bien dfini pour atteindre cette destination.
Le choix du chemin est influenc par les voies et les obstacles prsents.
84
Nous avons dcrit les spcifications de notre solution relative qui permet de mesurer la
mobilit dun nud (voire dun lien et dun rseau) dans un environnement ad hoc. La
mtrique propose est mise lpreuve par des tests de base pour statuer sur sa validit et son
comportement vis--vis des autres paramtres rseau.
Les rsultats obtenus montrent que notre mtrique dpend fortement des paramtres rseau
(densit du rseau, porte des nuds, modle de mobilit utilis, vitesse des nuds, etc.) et
reflte le taux de changement de ltat des liens dans le rseau. Ainsi, nous pensons que son
utilisation permettra damliorer davantage les performances des protocoles de routage dans
les environnement Manets.
Le prochain chapitre sera consacr aux amliorations apportes sur le rouatge. Ainsi, la
solution propose est intgre au protocole OLSR (Optimized Link State Routing) et dfinit,
avec la mtrique du nombre de sauts, une mtrique plus adapte.
85
Chapitre
Un fait n'est rien par lui-mme, il ne vaut que par l'ide qui s'y rattache
ou par la preuve qu'il fournit.
Introduction lEtude de la Mdecine
Exprimentale , Claude Bernard.
Certains points de convergence entre les rseaux MANETs et WiFi tels que lauto
organisation et la spontanit motivent le croisement des deux domaines. Dautres en revanche,
laissent penser quun tel choix nest pas fond. En effet, la non-fiabilit des liens, la volatilit des
nuds et la charge importante de signalisation mettent en doute lefficacit de tels systmes.
Cette problmatique a t dj traite et plusieurs solutions ont t proposes [120,121,122]. Les
approches prsentes proposent des systmes complets intgrant les deux domaines. Toutefois,
lvaluation de tels systmes restent le plus souvent base sur les techniques de simulation ou,
rarement, sur des exprimentations relles dans des rseaux de tailles trs rduite.
nous nous intressons lanalyse de l'impact de la mobilit des nuds sur les
Manets dans le but dexploiter les informations de mobilit pour amliorer les performances des
protocoles de routage dans ce type denvironnement.
Dans ce travail,
Pour les exprimentations, nous avons choisi le protocole de routage OLSR (Optimized Link
State Routing Protocol) [98] car cest le protocole qui se prte le mieux lincorporation de
lamlioration que nous proposons. Par ailleurs, ce choix a t renforc par le fait que ce
protocole t le plus clbre dans la famille des protocoles de routage dans les Manets.
Toutefois, lapproche est indpendante et peut tre adapte pour tout protocole de routage de la
famille ad hoc.
87
La charge des parquets de contrle (NRL): Il reprsente le rapport entre le nombre des
paquets de contrle envoys dans le rseau, par rapport au nombre des paquets de donnes
reues par les nuds destination. Cet indicateur reflte l'efficacit des protocoles de
routage en terme de paquets de contrle gnrs.
Le taux de livraison des paquets avec succs (PDF): Il s'agit du nombre total des
paquets de donnes livrs avec succs divis par le nombre total de paquets de donnes
transmis dans le rseau. Cette mtrique nous donne une ide sur la fiabilit du protocole
en termes de garanties de livraison des paquets.
Dlai moyen de bout en bout (Moy-End-to-End): C'est le dlai moyen pour les paquets
de donnes transmis de la source vers la destination. Ce paramtre est calcul en
soustrayant le temps o le premier paquet a t transmis par la source du temps de
rception du premier paquet de donnes reu par la destination". Cela inclut tous les
retards ventuels causs par les files dattente et de latence lors du processus de
dcouverte de route, les retards de retransmission au niveau de la couche MAC, la
propagation et les temps de transfert.
88
OLSR a t largement tudi [97,98,100], mis en uvre et dploy [99]. Les rsultats des tests
rels de performance effectus [98,100] sur un rseau maquette ont confirm que le protocole
souffre d'une forte instabilit qui dpend du nombre de sauts, le degr de changement de la
topologie et la nature de trafic transporter.
Les travaux mens dans [101] analysent les performances de l'algorithme standard de slection
des MPR utilis dans le protocole OLSR. Tandis que [102] prsente quelques problmes dans le
traitement des paquets OLSR, pour diffrentes implmentations, impactant la convergence
l'algorithme de slection MPR en cas de changement de ltat des liens.
De ce fait, nous pensons que la bonne gestion des informations de la mobilit (des nuds et du
rseau) pourrait complter le protocole OLSR. Nous proposons ainsi un nouveau mcanisme pour
la selection des MPRs en se basant sur ces informations additionnelles.
5.2.1 Lalgorithme standard de slection des MPRs
Le concept principal utilis dans le protocole est celui des relais multipoints (MPRs). Les
MPRs sont des nuds choisis qui expdient des messages de diffusion pendant le processus
d'inondation. Par consquent, le bon choix des MPRs permettra de mieux optimiser et fiabiliser
les changes dans le rseau. En effet, l'information d'tat des liens est produite seulement par des
nuds lus comme MPRs et ne contient aucune information sur la stabilit des liens (indique
seulement si le lien est actif ou pas). Ainsi, une optimisation est propose en imposant la
diffusion des informations relative au degr de stabilit des liens (en terme de mobilit).
Algorithme standard
Pour un nud x du rseau, N(x) est dfini comme lensemble constitu des voisins un saut
du nud x et ayant un lien symtrique avec ce dernier. Un saut correspond tous les voisins qui
89
(a)
(b) U U N ( w)
(c) MPR ( x) MPR ( x) {w}
5.
return MPR( x)
Ce choix a pour objectif de rduire considrablement le recalcul des MPRs, et par consquent
l'optimisation des ressources du nud (processeur, mmoire et nergie). De plus, ce choix aura
une influence sur la qualit des liens avec les nuds deux sauts. En effet, le nud ayant un
degr de mobilit gal 10% aura plus de chance que ses liens avec les nuds voisins deux
sauts soient plus stables.
En outre, nous pouvons dfinir un seuil de mobilit pour chaque nud (Threshold _Node)
dans le rseau qui permet de classifier sa mobilit (faible, moyenne ou leve). Ce seuil peut tre
utilis comme une alarme pour prvenir les dfaillances des liens. Chose qui permettra dassurer
une fiabilit des routes. En effet, chaque nud qui estime perdre son lien avec son voisin deux
sauts (sa mobilit est suprieure THRESHOLD_Node) peut apporter une correction au niveau
local (choix dun autre chemin parmi ses voisins un et deux saut) sans initier un nouveau
processus pour la dcouverte de route. Pour plus de prcision, prenons le cas de la figure 5.4 qui
utilise le protocole OLSR comme protocole de routage. Lorsque le nud N dtecte une perte de
lien deux sauts par l'intermdiaire du MPR(N) (on suppose que le nud rouge se dplace avec
une grande vitesse vers la zone des MPRs voisins), avant dinitier un nouveau processus pour le
calcul des MPRs, il excute le processus de correction au niveau local et de relier ce nud, la
MPR (N)_R ou la MPR (N)_L
Figure 5.4 Alternative du processus dinitiation dun nouveau recalcul des MPRs
91
M L ( A,B )
M A (t ) + M B (t )
=
2
(29)
Cette valuation du degr de mobilit du lien n'est pas significative, car on peut avoir une
valeur normale du degr de mobilit du lien alors que l'un des nuds constituant le lien a un
degr de mobilit lev. De ce fait, nous avons introduit un nouveau paramtre pour mesurer le
degr de dpendance entre les mobilits de deux nuds concerns.
La dpendance entre la mobilit des nuds d'un lien l'instant t peut tre vue comme la
probabilit de la perte du lien L (A, B) et peut tre dfinie comme suit :
PL( A, B ) (t ) =| M A (t ) M B (t ) |
(30)
Par consquent, nous dfinissons un lien symtrique fiable en terme de mobilit comme tant
un lien satisfaisant les deux conditions suivantes :
1- La mobilit moyenne du lien L (i, j) est infrieure un seuil Threshold_Link qui dpend des
caractristiques du rseau sans fil (densit du rseau, mobilit rseau, les dimensions du rseau,
etc.) :
92
(31)
PL(i , j ) (t ) 0
(32)
Le choix d'un lien rpondant ces deux conditions permet de garantir une forte dpendance
entre les nuds concerns tout en assurant une faible mobilit du lien .
5.2.2.3 Critres de mobilit proposs
Dans ce paragraphe, trois nouveaux critres pour la slection des MPRs seront prsents. Les
trois critres seront soumis lpreuve pour dcider du critre le plus performant. Le premier
critre (quation 33) est directement bas sur la mobilit des nuds voisins. Les deux autres
critres sont bass sur l'estimation de la qualit des liens en terme de mobilit entre les voisins
un saut et deux sauts (Figure 5.6). La qualit du lien est mesure par le degr de dpendance du
lien. Un lien est fiable si son paramtre de dpendance sapproche de 0. Ainsi, le processus de
slection des MPRs doit faire un compromis entre le nombre de liens vers les nuds deux sauts
et la fiabilit de ces liens prsente par la dpendance de la mobilit de ces liens. La slection
d'un nud voisin en tant que nud MPR peut tre considre comme une opration de
maximisation du critre de slection. Le deuxime critre propos est bas sur la somme
(quation 35) et le troisime est bas sur le produit (quation 34). Les principaux avantages de
ces critres sont la facilit du calcul, et la faible consommation des ressources (mmoire et CPU).
Figure 5.6 valuation des critres bass sur la mobilit des liens.
(33)
(34)
SUM CRITERIA(w) = 1
(35)
i =1
i =1
93
M L( w,i ) (t )
N
Figure 5.7 Comparaison des critres proposs par rapport lalgorithme standard
utilis par OLSR pour la slection des MPR
Daprs la figure 5.7, on peut conclure que le nombre moyen des MPRs lu pour le critre
bas sur la somme (47,4%) dpasse largement le nombre enregistr pour le protocole standard
(31, 9%). Par ailleurs, nous remarquons que les critres simple et produit convergent en terme de
cot. En effet, les critres simple et produit ont presque la mme valeur moyenne des MPRs
(respectivement 32,4% et 31,94%) et qui sapproche de la valeur enregistre par le protocole
standard. Cela veut dire que la surcharge rseau engendre pour les critres simple et produit sera
galement la mme que celle produite par le protocole standard.
Dautre part, et vu que les critres proposs choisissent comme MPRs les nuds les plus
94
1000m x 1000m
50
0, 50, 100, 150, 200, 250, and 300s
1 m/s respect 40 m/s
10
CBR / 512 octets
0, 0.25, 0.5, 0.75, 1
Rsultats:
Les figures 5.8, 5.9 et 5.10 illustrent lvolution des indicateurs de performances (dlai, pdf,
dbit) pour les valeurs de =0, 0.25, 0.5, 0.75 et 1. Pour chaque valeur de on compare les
performances du protocole modifi avec celles enregistres par le protocole standard OLSR
95
Dlai
OLSR standard
Dlai
OLSR standard
0.3
0.35
0.3
0.25
0.25
Dlai
Dlai
0.2
0.15
0.2
0.15
0.1
0.1
0.05
0.05
0
0
50
100
150
200
250
300
50
100
150
200
250
300
250
300
Temps de pause
Temps de pause
Dlai
OLSR s tandard
Dlai
OLSR standard
0.4
0.35
0.35
0.3
0.28
Dlai
Dlai
0.25
0.21
0.2
0.15
0.14
0.1
0.05
0.07
0
50
100
150
200
250
300
Temps de pause
100
150
Temps de pause
200
Delai
average-mob00
Dlai
OLSR standard
50
average-mob-0,25
average-mob-0,5
0.3
average-mob-0,75
average-mob-1
average-standard
0.25
0.38
0.33
0.28
0.15
Dlai
Dlai
0.2
0.1
0.23
0.18
0.05
0.13
0.08
0
50
100
150
Temps de pause
200
250
300
50
100
150
Pause Time
200
250
300
Figure 5.8 valuation des performances du protocole modifi : dlai de bout en bout
Les rsultats des simulations effectues, montrent que le dlai de bout en bout, pour les deux
96
D bit
OLSR s tandard
D bit
OLSR s tandard
31000
32000
29000
30000
28000
27000
26000
24000
23000
Dbit
D bit
25000
21000
22000
20000
18000
19000
16000
17000
14000
15000
12000
10000
13000
50
100
150
200
250
50
100
300
150
200
250
300
200
250
300
Tem ps de pause
Te m ps de paus e
D bit
OLSR s tandard
31000
31000
29000
29000
27000
27000
25000
25000
23000
23000
Dbit
Dbit
Dbit
OLSR s tandard
21000
21000
19000
19000
17000
17000
15000
15000
13000
13000
0
50
100
150
200
250
300
50
100
trouphput-m ob00
D bit
OLSR s tandard
150
Tem ps de pause
Tem ps de pause
Troughput - OLSR
troughput-m ob0,25
trouphput-m ob-0,5
31000
average-m ob-0,75
average-m ob-1
Dbit
29000
average-s tandard
27000
29500
25000
27500
23000
25500
21000
23500
19000
21500
17000
19500
17500
15000
15500
13000
0
50
100
150
Te m ps de pa use
200
250
300
13500
0
50
100
150
Paus e Tim e
200
97
250
300
OLSR standard
100.00%
100.00%
90.00%
90.00%
80.00%
80.00%
Taux en % %
Taux en % u
OLSR Standard
70.00%
70.00%
60.00%
60.00%
50.00%
50.00%
40.00%
40.00%
0
50
100
150
200
Tem ps de pause
250
300
50
100
150
200
250
300
Tem ps de pause
OLSR Standard
OLSR standard
100.00%
90.00%
90.00%
100.00%
Taux en % x
80.00%
70.00%
60.00%
80.00%
70.00%
60.00%
50.00%
50.00%
40.00%
0
50
100
150
200
250
300
40.00%
Tem ps de pause
50
100
150
200
Temps de pause
Mobilit 1
Mobilit 0.75
Mobilit 0.50
Mobilit 0.25
Mobilit 0
standard
100.00%
90.00%
80.00%
70.00%
60.00%
50.00%
40.00%
0
50
100
150
200
250
300
Pause tim e
98
250
300
Conclusion
Le choix de dvelopper un nouveau protocole qui tient en compte des paramtres de mobilit a
permis de confirmer, dans un environnement ad hoc rel, lamlioration apporte par notre
mtrique propose dans le chapitre 4. Les difficults matrielles quimpliquent des
exprimentations sont nanmoins la cause de restrictions sur celles-ci. Les exprimentations
effectues permettent nanmoins de montrer clairement le gain apport par lutilisation de notre
approche ainsi que de mesurer le faible impact que cette dernire induit sur le rseau en terme de
collision.
Enfin, les tests effectus au fur et mesure du dveloppement pour vrifier le bon
fonctionnement du protocole modifi et des paramtres des simulations ont permis de confronter
la thorie la ralit et de dcouvrir certains problmes qui peuvent tre complexes rsoudre en
pratique. Le problme de garantie de la qualit dans ce type de rseau est par exemple un
problme qui existe ds quon pense aux exigences actuelles des utilisateurs, et pourtant
extrmement peu de propositions utilisant la qualit de service, dans les Manets, abordent ce
sujet. Ceci nous amne penser dexploiter davantage ces rsultats pour amliorer la qualit de
service dans ce type de rseaux. Le prochain chapitre expose une nouvelle mtrique, base sur la
mobilit, qui permet doptimiser les ressources de bande passante tout en tenant compte des
contraintes cls des environnements Manets savoir : la mobilit et dnergie.
99
Chapitre
Introduction
Le routage avec qualit de service peut tre dfini comme tant le processus dtablissement et
de maintenance de routes optimales (pour la paire communicante comme pour le rseau)
satisfaisant un certain nombre de critres sur la qualit de la transmission des donnes. Si lon
peut considrer que cet objectif sera bientt atteint dans les rseaux locaux filaires, les rseaux
ad-hoc prsentent un grand nombre de spcificits qui conduisent des performances limites
cause des contraintes de bande passante et de la topologie dynamique des rseaux MANETs
(Mobile Ad Hoc Networks). En effet, la mobilit des nuds provoque des changements frquents
de la topologie du rseau, de mme que les interfrences sur les liens radio, aboutissent la
cration ou la disparition de certaines routes.
Plusieurs protocoles de routage ont t proposs pour les rseaux mobiles ad hoc. Ces
protocoles de routage peuvent tre classifis suivant la manire de cration et de maintenance de
routes lors de l'acheminement qui se font selon plusieurs critres. Le groupe de travail MANET
(Mobile ad hoc NETwork) de l'IETF (Internet Engineering Task Force) se proccupe de la
normalisation des protocoles ad hoc fonctionnant sous IP. Dans ce cadre, AODV, OLSR, DSR
sont actuellement lobjet dune RFC grce leurs caractristiques intressantes. Ces protocoles
fonctionnent en mode best effort. Cependant, ils ne permettent pas de garantir une qualit de
service (QoS).
Pour certaines applications telles que les applications multimdias ou temps rel, le service
best effort nest pas du tout suffisant. De telles applications exigent des garanties en terme de
certains critres de qualit de service (un minimum de bande passante, un dlai max ne pas
dpasser.etc...). En effet, il semble important dadapter les MANETs pour supporter un certain
niveau de QoS dans le but de dploiement des applications exigeantes.
Ce chapitre aborde les diffrentes approches utilises pour assurer la QoS dans les MANETs
et propose une extension de notre mtrique propose dans le chapitre 4. La mtrique propose est
une mtrique compose qui tient en compte la mobilit des nuds comme tant un paramtre
primordial pour la QoS dans les MANETs. Les rsultats des simulations sur le protocole OLSR
seront exposs.
6.1 Routage avec Qualit de service
Les travaux publis concernant le routage avec qualit de service reposent beaucoup sur les
protocoles de routage du groupe Manet. Un certain nombre de recherches ont t menes dans le
domaine du routage avec qualit de service ddi aux rseaux ad hoc.
Dans [125,133], il a t prouv que le problme de trouver un chemin avec des contraintes
multiples est NP-Complet. Nanmoins, plusieurs propositions ont t prsentes pour rsoudre ce
problme. Ces propositions peuvent tre classifies suivant cinq catgories :
102
Ying et al [132] ont propos des amliorations qui permettent au protocole OLSR de trouver le
chemin de bande passante maximum. Ils se sont bass uniquement sur la bande passante comme
contrainte de la qualit de service de routage et ont rvis lalgorithme de la slection des MPR.
Le concept cl de la version rvise de lalgorithme est que le lien, offrant une bande passante
lev, ne devrait jamais tre omis.
La deuxime approche est base sur la minimisation dun paramtre de QoS sujet une
deuxime contrainte. Salama [129,131] a propos un algorithme heuristique distribu pour le
problme de Delay-Constrained Unicast Routing. Cet algorithme utilise le cot et le dlai
calculs par un protocole vecteur de distance. Le point ngatif de cet algorithme est que des
boucles pourraient se former pendant le processus de dcouverte et de maintenance de route. Une
version amliore de lalgorithme de Salama appel Delay Constrained Routing (DCR) a t
propose, permettant dliminer les boucles de routage.
La troisime approche pour le routage avec QoS consiste construire le chemin sous deux
contraintes simultanment (gnralement dlai et cot). Chen [134] a prsent deux algorithmes
Delay-Cost- Constrained drivs des algorithmes du plus court chemin Dijkstra et Bellman-Ford.
Jaff a propos une heuristique polynomiale pour rsoudre le problme avec deux contraintes
[142]. Les chemins forms par cet algorithme sont les chemins optimiss sous les contraintes de
QoS.
Le groupe de recherche l'INRIA [139] propos un schma de qualit de service pour le
protocole OLSR. Leur technique prend en compte les informations de dlai et de la bande
passante pour le calcul de la table de routage. Ces paramtres sont inclus sur chaque table de
routage d'entre correspondant chaque destination.
103
(37)
Concave:
(38)
104
b- Antisymtrique : si m R m alors m R m
c- Transitive : si m R m et m R m alors m R m
d- Totale : si pour tout m et m M on a m R m ou m R m ou m = m
Notons que la relation (infrieure <) dfinie sur les lensemble des entiers naturels satisfait les 4
relations.
Aussi, chaque valeur de m M doit satisfaire la condition suivante : pour toute valeur m M , il
existe une srie, non vide, de poids w1 , w2 , , wk (wi W) et une srie de valeur de mtrique
m1 , m2 , , mk ( mi W) telles que :
m1 = mr
m2 = Met(m1 , w1 )
.
.
.
mk = Met( mk , wk )
Si une valeur de la mtrique ne satisfait pas la condition prcite alors, elle peut tre supprime
de lensemble M.
Arbre mtrique maximizable : Un arbre couvrant-minimal T spanning tree du rseau N
est dit arbre mtrique maximizable ( par rapport une mtrique donne) si chaque chemin dans
105
T prsente la mtrique maximale. Autrement dit, chaque nud obtient sa mtrique maximale sur
le chemin dans larbre mtrique maximale.
Mtriques bornes: Une mtrique de routage (M, W, wf, mr, met, R ) est borne si la condition
suivante est vrifie pour tout poids w W et tout m M.
Met (m,w) R m Met(m,w) = m
(39)
Mtriques monotones : Une mtrique (M, W, wf, mr, met, R ) est dite monotone si la condition
suivante est vrifie pour tout poids w W et tout m, m M :
m R m (Met (m,w) R Met (m,w) Met(m,w) = Met (m,w))
(40)
La mtrique est dite strictement monotone si :
m R m Met (m,w) R Met (m,w)
(41)
Les thormes suivants annoncent les conditions ncessaires et suffisantes pour quune mtrique
de routage soit monotone et borne [136]. Ces rsultats seront utiliss pour la constitution de
notre mtrique compose.
Thorme1 :
Si un rseau N admet un arbre couvrant minimal pour une mtrique dfinie, alors la mtrique est
borne.
Thorme2 :
Si un rseau N admet un arbre couvrant minimal pour une mtrique dfinie, alors la mtrique est
monotone.
Thorme 3 :
Si une mtrique de routage est choisie pour un rseau N et si cette mtrique est monotone et
borne, alors N admet un arbre couvrant minimal pour la mtrique choisie.
Exemple :
Il est facile de vrifier que la mtrique de dbit (en prenant R = <) et mtrique de
distance (en prenant R = >) sont monotones et bornes.
Preuve : les dmonstrations sont disponibles [135].
Thorme 4:
Si les deux mtriques de routage suivantes sont bornes,
- (W1,Wf1 M1, mr1, met1, R1 )
- (W2,Wf2, M2, mr2, met2, R2 )
Alors la mtrique compose suivante est borne.
(W1xW2,<Wf1/Wf2>,M1xM2,<mr1/mr2>,<met1/met2>,R)
o, R=< R1/R2> est une relation de squence dduite de R1 et R2.
(42 )
Thorme 5:
Si les deux mtriques de routage suivantes sont monotones,
- (W1,Wf1 M1, mr1, met1, R1 )
- (W2,Wf2, M2, mr2, met2, R2 )
Et si la premire mtrique est strictement monotone Alors la mtrique compose (quation (42 ))
monotone. o, R=< R1/R2> est une relation de squence dduite de R1 et R2.
106
BW ( w' )
M ( w' )
(42)
(43)
K1
* BW ( w' ) + K 2 * (1 M ( w' ))[K 3 * E ( w' )] (44)
Generalized _ metric) = K 0 +
M ( w' )
107
o :
BW dsigne la bande passante disponible en kilobits par seconde et E est lnergie rsiduelle du
nud en joule
Les constantes K0, K1, K2 seront fixes par l'administrateur selon lenvironnement rseau. Par
exemple, dans un environnement trs dynamique, et pour donner plus d'importance la mobilit
des nuds, on peut fixer K0, K1 1et K2 10.
La constante K3 est non nulle. Elle est utilise pour indiquer si l'environnement prend en compte
l'nergie des nuds ou non. Ainsi, une valeur importante de K3 indique que l'nergie est
importante dans le processus de routage.
La mtrique propose reflte un environnement dynamique rel o les nuds ont des ressources
limites en nergie et o la contrainte de bande passante est essentielle (application de
streaming).
Ce choix est fait de sorte que les liens, srs et stables, offrant une bande passante optimale ne
doivent jamais tre omis.
6.3.1 Proprits des mtriques proposes
Dans ce paragraphe nous allons dmontrer que chacun des paramtres individuels satisfait aux
conditions requises par la thorie de constitution des mtriques maximizable (c..d monotones
et bornes) puis nous gnralisons sur la mtrique propose.
6.3.1.1 Nud et Lien de la bande passante disponible :
= TL * Cmax
(45)
Si on note Bav (i, j ) la bande passante disponible au niveau du lien (i,j). Bav (i, j ) peut tre dfinie
comme suit :
108
(46)
Aussi, si on dsigne par Wi , j le poids du lien L(i,j) (relatif la mtrique de bande passante). Wi , j
peut tre estim partir de la relation suivante :
1
Wi , j =
(47)
Bav (i, j )
La proprit borne implique que, tout au long du chemin, partir de la racine, la mtrique
nest pas croissante. La mtrique est donne par: met (m, W (i, j)).
Si on dsigne par m la valeur de la mtrique pour le nud racine, il est vident que la bande
passante satisfait les conditions prcites : monotone et borne . La bande passante disponible
est toujours positive, donc pour n'importe quel nud situ une distance "d" de la racine W(i, j)
serait toujours infrieure ou gale la valeur de la mtrique de la racine.
6.3.1.2 Mobilit et nergie
La mtrique de mobilit reprsente le taux de changement du nombre des voisins d'un nud
l'instant t par rapport l'tat antrieur. Dans un travail prcdent [135,136], nous avons dfinit le
degr de mobilit d'un nud mobile i un instant t par la formule suivante:
M i ( t ) =
NodesOut( t )
NodesIn( t )
+ (1 )
Nodes( t t )
Nodes( t )
o:
NodesIn(t )
NodesOut (t ) : Le nombre de nuds qui ont quitt la porte de communication du nud i durant
lintervalle [t t , t ] .
Nodes (t )
Pour statuer sur la valeur optimale du paramtres relatif lenvironnement utilis pour nos
simulations (en faisant vari les paramtres du modle de mobilit RWP, le nombre, direction et
vitesse des nuds, etc.), plusieurs simulations ont t labores. Les rsultats des simulations
effectues pour diffrentes valeurs de ( = 0, 0,25, 0,5, 0,75, 1) [114] montrent que, pour =
0,75 les performances du rseau sont performants (en terme de dlai, livraison des paquets avec
succs et dbit). Pour cette raison, nous considrons = 0,75 dans le reste de cet ouvrage.
109
Lintegration de notre approche dans NS2 [19] require la dfinition des poids imposs par
lutilisation de chaque lien (dpendamment de sa mobilit, nergie et bande passante). Ainsi,
dfinissons les poids correspondants come suit :
Soit Wi , j = M L ( i , j ) le poids impos sur le lien L(i, j) (relatif la mtrique de mobilit). La
mobilit du lien reliant les deux nuds A et B est dfinie comme la moyenne de la mobilit des
nuds concerns (voir Figure 6.1), comme indiqu dans l'quation suivante:
M L( A , B ) =
M A (t ) + M B (t )
2
M L ( A; B ) = 45%
Comme la mobilit des nuds reflte la probabilit de pertes de donnes sur un rseau,
elle peut tre considre comme une mtrique de fiabilit [135,136]. Et parce que la mtrique de
fiabilit est borne et strictement monotone, elle peut tre squence partiellement en prservant
les caractres born et monotone.
En outre, la fonction reprsentant la variation de l'nergie rsiduelle est monotone et
borne. En effet, sa valeur diminue (en fonction de l'tat du nud: mission / rception, le
passage en mode veille, etc.) d'une valeur maximale (ex 200) 0. Aussi, elle reflte la manire
dont elle est susceptible de faire augmenter le taux de perte ou corruption des donnes. Par
consquent, elle peut tre squence partiellement en prservant la proprit borne et monotone.
Dans notre travail, nous avons personnalis le modle de consommation dnergie dfini dans
NS2 [19] et qui est comme suit:
Pt_consume = 1,320 (~ 3.2W de perte pour la transmission dun paquet); Pr_consume =
0,8 (2,4 W perte pour la rception dun paquet); P_idle = 0,07, 06 = P_sleep; P_transition = 0,5,
P_Mob = Mob(i)/2 (puissance perdue cause du mouvement du nud i est gale la moiti de
son degr de mobilit)
Pour valider l'efficacit des paramtres proposs, nous avons dvelopp quatre modles :
bandwidth , mobility, sum_bandwidth-mobility , prd_bandwidth-mobility et bandwidth-energymobility .
La mtrique associe chaque modle sert comme cot pour transmettre un paquet.
Dans OLSR, les paramtres seront utiliss comme critre dans lalgorithme de slection
de MPR. En changeant des messages Hello, chaque nud calcule son cot en se basant sur
les informations mesures et reues par ses nuds voisins.
110
Ainsi, nous avons besoin de dfinir une estimation de lnergie et de la bande passante
dun lien. Pour ceci, si on dsigne par Eij le poids lu lien L(i, j) (relatif la mtrique dnergie) .
Ei,j peut tre estime partir de la relation suivante (voir figure 6.2):
Eij = Min( Ei , E j )
(48)
o Ei dsigne l'nergie disponible pour le nud i . la valeur Ei = 0 signifie que le nud a puis
son nergie. Ainsi, le protocole de routage doit carter un tel nud dans le processus de
construction de route.
Pour chacun des cinq modles, les fonctions cots (F(i)) associes aux modles cits cidessous sont dfinies par les formules 49,50,51,52 et 53.
Soit i un nud du rseau et F(i) le cot gnral qui lui est associ.
On note par :
Ei
son nergie rsiduelle
BWi la bande passante disponible au niveau du nud i
M i son degr de mobilit
Les fonctions cot relatives aux modles prcits sont dfinies comme suit :
Bandwidth model :
F(i)= BWi
(49)
F(i) = M i
(50)
Mobility model :
Sum_Bandwidth_mobility model :
F(i)= DefaultMetric1= [K 0 * BWi + K 2(1 M i ]
Prd_bandwidth_mobility model :
BWi
F(i) = DefaultMetric2= K 0 + K1
Mi
Bandwidth_energy_mobility model:
111
(51)
(52)
K1
* BWi + + K2 * (1 - M i ) [K 3 + Ei ]
F(i)= K 0 +
Mi
(53)
Pour motiver les nuds afin de rvler leur cot exact lors de la slection des MPR, un
mcanisme d'incitation bas sur la rputation, en utilisant le mcanisme VCG (Vickrey, Clarke,
and Groves) pourrait tre utilis [138]. Les nuds qui participent fidlement ces processus vont
voir leur rputation augmenter. Ainsi et vu que les services rseau sont offerts en fonction de la
rputation des nuds, il encouragera les nuds participer honntement.
Dans un premier temps et afin dvaluer la performance de notre mtrique composite, nous avons
implment un algorithme en java et nous avons compar sa performance avec la mtrique de
bande passante utilise dans QOLSR [139]. Pour la simulation, nous avons utilis le schma de la
figure 6.4 et nous avons gnr 10,000 valeurs alatoires dans lintervalle [0,1] pour la bande
passante, la mobilit et lnergie.
Les rsultats des simulations effectues montrent que le pourcentage de trouver un chemin entre
les nuds 0 et 7 pour les deux mtriques est denviron 11%. Cependant, en tenant compte des
contraintes dnergie, les chemins bass sur notre mtrique composite offrent un dbit optimal
(par rapport la premire mtrique) assurant des chemins stables. Ainsi, on constate une
augmentation de dbit denviron 16%. Cependant, la mobilit des chemins bass sur notre
mtrique enregistre une lgre augmentation. Cette augmentation est justifie par le fait que la
mtrique propose favorise les nuds ayant des ressources dnergie importante (impose par
112
lopration de multiplication dans la formule). Sur lensemble des chemins choisis par les deux
mtriques, seulement 30% des chemins sont communs.
6.4.2 Simulation 2
Dans cette section, nous allons prsenter les rsultats de comparaison des performances de la
version standard du protocole OLSR par rapport aux protocoles modifis relatifs aux modles
susmentionns, savoir : le modle relatif la mtrique de bande passante (QOLSR), le modle
relatif au paramtre de mobilit (MobOLSR), les modles qui combinent (par une fonction
somme ou par une fonction produit) la mobilit et la bande passante sum_bandwidth-mobility
respect prd_bandwidth-mobility (Sum-OLSR et PRD-OLSR) et le modle gnralis qui combine
la bande passante, la mobilit et lnergie (EN-OLSR).
Rappelons que les versions MobOLSR, Sum-OLSR et PRD-OLSR et ENOLSR correspondent
aux protocoles OLSR modifi. Contraitrement au protocole standard OLSR qui, dans le
processus de selection des MPRs, choisi un ensemble minimale des voisins un saut de telle
sorte couvrir tous les voisins deux sauts. MobOLSR choisi les nuds les plus stables. SumOLSR et PRD-OLSR cherchent choisir les nuds les plus stables offrant une bande pasasnte
optimale. Quant au protocole ENOLSR, il choisi les nuds les plus stables, nergie importante
et qui offrent une banda passante optimale.
6.4.2.1 Prsentation de la solution
Notre dmarche est comme suit : Si la bande passante est un facteur important et exig par
lutilisateur final, la mobilit et l'nergie constituent gnralement un dfi indit face aux
garanties de cette ressource et particulirement dans les environnements Adhoc. Jusqu' prsent,
la majorit des protocoles de routage ont montr leurs faiblesses face aux environnements
dynamiques et lpuisement soudain des ressources nergtiques dans le rseau.
Notre objectif consiste grer positivement la bande passante du rseau tout en tenant compte
des contraintes d'nergie et de mobilit, afin d'amliorer les performances des protocoles de
routage et de prolonger la dure de vie des rseaux Manets.
113
Au dpart, nous commenons par donner les rsultats de comparaison de notre approche base
uniquement sur les paramtres de mobilit. Ainsi, nous valuons le protocole de notre premire
version du protocole OLSR modifie (que nous appelons Mob-OLSR). MobOLSR utilise la
mtrique de mobilit propose dans [114,115]. A ce sujet, Mob-OLSR sera compare la version
standard du protocole OLSR (sans extension de QoS) et QOLSR (la plus connue du protocole
OLSR avec des extensions de QoS).
Les rsultats obtenus nous ont logiquement amens penser utiliser les paramtres de
mobilit pour rpondre aux exigences de qualit de service. Par consquent, nous nous sommes
concentrs sur la maximisation de la bande passante en tenant compte des contraintes de mobilit.
cet gard, deux mtriques sont proposes. La premire est base sur la somme et la seconde est
fonde sur le produit. Les deux mtriques seront mises lpreuve aprs leurs intgrations dans le
protocole original OLSR.
cause de son surcot gnr (par rapport au critre bas sur le produit) en terme de PDF,
nous avons limin le critre bas sur la somme. Toutefois, il est important de mentionner que ce
dernier a de bonnes performances en comparaison avec le protocole QOLSR.
Dans un deuxime temps, et afin de maximiser la bande passante, tout en tenant compte des
contraintes de mobilit et d'nergie, une nouvelle mtrique gnralise est prsente.
La mtrique gnralise sera intgr au protocole OLSR et compare aux diffrents protocoles
proposs PRD-OLSR et Mob OLSR et QOLSR
Il est signaler que ce travail est parmi les premiers efforts visant exploiter les contraintes de
mobilit et dnergie des nuds dans les MANETs.
Pour simuler la version standard du protocole OLSR et les versions modifies lies nos
critres prsents prcdemment, nous avons utilis la version du protocole OLSR adapt la
version 2.33 du simulateur rseau NS2 [123-124 ].
A cet gard, nous utilisons un rseau compos de 50 nuds mobiles. Ces nuds se dplacent
alatoirement dans une superficie de 800x 600m selon le modle de mobilit RWP. En outre, et
pour assurer un environnement trs dynamique (le pire des cas), nous avons considr le modle
de mobilit RWP avec un temps de pause gal 0. Les nuds peuvent se dplacer arbitrairement
avec une vitesse maximale de 140km/h. Le temps des simulations est de 100s.
Nous avons utilis un modle de trafic alatoire distribu de type CBR (Constant Bit Rate)
pour permettre chaque nud du rseau d'tre une source et/ou une destination potentielle de
trafic. La taille des paquets CBR est fixe 512 octets. chaque connexion, les sources
transmettent un taux de 10 paquets par seconde. Toutes les connexions (sources destination)
commencent des moments rpartis uniformment entre 5 et 90 secondes. Le nombre total des
connexions est de 8 et chaque simulation dure 100s.
Pour chaque point reprsentatif prsent, 40 scnarios alatoires sont gnrs. Les indicateurs
des simulations sont ensuite statistiquement prsents par la moyenne des valeurs obtenues. Cela
rduit les chances que les observations soient domines par certains scnarios qui favorisent un
protocole sur l'autre.
114
Comme nous nous intressons aux environnements trs dynamiques ( forte mobilit), et pour
permettre la mise jour rapide de la base de donnes de topologie, nous avons rduit l'intervalle
de transmission des messages Hello et TC sont 0.5seconde et 3secondes, respectivement.
En outre, nous avons valu le comportement des indicateurs pour diffrents niveaux de
mobilit en faisant varier la vitesse maximale des nuds entre 0 km/h (pas de mobilit) et 140
km/h (forte mobilit).
6.4.2.2 Comparaison du protocole MobOLSR avec OLSR et QOLSR
La Figure 6.7 montre que les protocoles modifis Mob-OLSR et QOLSR assurent de bonnes
performances en termes de dlai par rapport la version standard du protocole OLSR, et ce pour
toutes les valeurs de la vitesse.
Prcisment, pour un environnement forte mobilit, le dlai enregistr par les protocoles
QOLSR et MobOLSR est d'environ 1,25 secondes (amlioration de 0,4 seconde) en comparaison
avec le protocole standard. Dans le cas statique, le dlai diminue 1,25 seconde (amlioration de
0.1seconde par rapport OLSR original).
Pour le protocole standard OLSR le dlai obtenu est de deux fois plus important et dpasse 2,1
secondes pour un environnement forte mobilit et atteint 1,4 seconde lorsque la mobilit est
rduite.
Pour les vitesses intermdiaires (de 40m/s 100m/s) une lgre diffrence entre MobOLSR et
QOLSR est remarque (amlioration par 0.1seconde pour MobOLSR par rapport QOLSR pour
une vitesse maximale (0m/s et 30m/s)). Cela nous permet de conclure que MobOLSR se comporte
mieux que QOLSR pour les vitesses intermdiaires.
Selon la Figure 6.8, le protocole OLSR original et le protocole MobOLSR assurent dans
l'ensemble le mme taux de livraison des paquets avec succs (PDF) pour toutes les vitesses
maximales avec une lgre amlioration pour le protocole OLSR original pour toutes les vitesses
maximales.
OLSR
QOLSR
MOBOLSR
De lay
2.5
delay (s)
1.5
1
0
20
40
60
80
100
pause time(s)
Figure 6.7 Comparaison du dlai pour les trois versions du protocole OLSR.
115
En effet, on peut constater que le nombre de paquets perdus sur le chemin est semblable pour
toutes les vitesses maximales qui sont d'environ 45%, au pire des cas pour OLSR original et
MobOLSR et de 35% pour QOLSR.
OLSR
QOLSR
MOBOLSR
90
rate (%)
75
60
45
30
0
20
40
60
80
100
pause time
En outre, le ratio est encore dgrad pour un rseau en constante volution (c'est dire trs
grande vitesse) que pour des conditions de rseau statique, car le nombre des dfauts des liens
augmente avec la mobilit. Cependant, il est intressant de noter que mme dans des conditions
de topologie statique, les nuds metteurs nassurent pas une livraison des paquets 100%, mais
seulement une livraison de 85% 89%. Cela montre clairement l'impact de la congestion du
rseau et l'interfrence des paquets qui augmentent la charge dans le rseau. En outre, lorsque l'on
compare MobOLSR et OLSR original par rapport QOLSR, le protocole QOLSR prsente une
dgradation remarquable sur le PDF pour toutes les vitesses maximales. C'est parce que QOLSR
ne tient pas compte de l'tat des liens dans le processus de slection des MPRs. En rsum, nous
pouvons dire que le protocole MobOLSR est mieux adapt tous les niveaux de mobilit de 0m/s
(pas de mobilit) 40m / s ( trs forte mobilit).
La figure 6.9, montre le dbit moyen pour les trois versions du protocole. Les protocoles
OLSR original et MobOLSR assurent dans l'ensemble le mme dbit moyen pour toutes les
vitesses maximales qui sont d'environ 125 kbits/s au plus pire des cas.
La plus faible valeur du ratio saffiche pour les rseaux en constante volution que pour des
rseaux statiques. En outre, il est intressant de noter que, mme avec des conditions de topologie
statique, le dbit moyen du rseau ne parvient pas la capacit du canal (5 Mb/s), mais seulement
230 kbps. Cela montre clairement l'impact de la congestion du rseau et l'interfrence des
paquets ; ce qui augmente la charge dans le rseau.
116
Avg Throughput
230
200
170
140
110
0
20
40
60
pause time (s)
80
100
Figure 6.9 Comparaison du dbit pour les trois versions du protocole OLSR
Ainsi, QOLSR assure une amlioration de 10kb/s par comparaison MobOLSR et OLSR
original pour toutes les vitesses maximales.
La figure 6.10 illustre la charge de routage normalise (NRL : normalized routing load)
introduite dans le rseau pour les trois versions du protocole OLSR, o le nombre de paquets de
routage est rationalis par rapport aux paquets de donnes envoys. Une surcharge assez stable
des messages de contrle serait une proprit souhaitable si lon considre que les performances
indiquent que la surcharge du trafic de contrle augmente linairement avec la vitesse maximale
des nuds en raison du nombre de messages ncessaires pour tablir et maintenir la connexion.
Le protocole OLSR original et le protocole MobOLSR produisent la plus faible quantit NRL par
rapport au protocole QOLSR pour toutes les valeurs de vitesse maximale. En outre, le protocole
OLSR original et le protocole MobOLSR produisent les mmes charges de routage pour toutes les
vitesses maximales.
OLSR
QOLSR
MOBOLSR
NRL
2.5
rate (%)
1.5
0.5
0
0
20
40
60
pause time (s)
80
100
Figure 6.10 Comparaison du NRL pour les trois versions du protocole OLSR
Dans le pire des cas ( la valeur maximale de la vitesse de 40m / s), le NRL arrive jusqu
2,1% pour le protocole QOLSR et 1,3% pour le protocole OLSR original. Prcisment, par
117
rapport au protocole QOLSR, les protocoles MobOLSR et OLSR originaux produisent deux fois
moins de paquets de routage. C'est ce qui explique que notre critre propos la base du
paramtre de mobilit, demande moins de paquets de routage pour tablir et maintenir les routes
dans le rseau.
OLSR
QOLSR
MOBOLSR
Collision
35000
30000
Nbre (#)
25000
20000
15000
10000
5000
0
0
20
40
pause time
60
80
100
Figure 6.11 Comparaison des collisions pour les trois versions du protocole OLSR
Les collisions sont un phnomne commun dans un mdia partag. Les collisions des paquets
peuvent entraner la perte de l'intgrit des paquets. Elles nuisent la performance du rseau et en
particulier la qualit de service perue par l'utilisateur final. Les interfrences et la qualit de
service (QoS) sur des environnements radios sont deux critres qui doivent tre abords lors de
l'laboration des normes des prochaines gnrations de rseau sans fils.
La figure 6.11, montre que le protocole OLSR original produit la plus faible quantit de
paquets en collision par rapport MobOLSR et QOLSR. Cependant, nous remarquons que notre
protocole propos MobOLSR assure une amlioration de 56% par rapport QOLSR, le clbre
protocole OLSR avec des extensions de QoS pour les MANETs.
Le nombre moyen de paquets en collision pour QOLSR (respectivement MobOLSR et le
protocole OLSR original) est de 30000 (respectivement 17000, et 11000) pour toutes les vitesses
maximales.
6.4.2.3
La figure 6.12 illustre le dlai moyen de bout en bout pour les protocoles proposs
(OLSRMet1, OLSRMet2, MobOLSR et QOLSR). En comparaison avec QOLSR, il est intressant
de noter que nos protocoles proposs MobOLSR et OLSRMet2 offrent de bons rsultats dans une
topologie dynamique (amlioration de 0,5 s pour une vitesse maximale de 40m/s 80m/s).
En outre, nous pouvons voir (Figure 6.13) que OLSRMet2 se comporte bien en termes de
PDF, par rapport aux autres protocoles proposs (OLSRMet1, MobOLSR et QOLSR) pour toutes
les vitesses maximales. Prcisment, pour OLSRMet2 le dlai devient deux fois plus faible que
pour QOLSR.
Une lgre dgradation du dbit moyen pour le protocole OLSRMet2 par rapport QOLSR est
118
De lay
2.5
delay (ms)
1.5
1
0
20
40
60
80
100
pause time(s)
Figure 6.12 Comparaison des trois versions du protocole OLSR en termes de dlai.
QOLSR
MobOLSR
OLSRMet1
OLSRMet2
90
rate (%)
75
60
45
30
0
20
40
60
80
100
pause time
Figure 6.13 Comparaison des trois versions du protocole OLSR en termes de PDF
Cependant, nous remarquons que OLSRMet2 se comporte mieux que MobOLSR et OLSRMet1.
C'est parce que OLSRMet2 slectionne des chemins stables offrant une bande passante optimale.
Ceci est confirm par l'amlioration constate dans le paramtre PDF.
QOLSR
MobOLSR
OLSRMet1
OLSRMet2
Avg Throughput
230
200
170
140
110
0
20
40
60
pause time (s)
80
100
Figure 6.14 Comparaison des trois versions du protocole OLSR en termes de dbit
119
Le protocole MobOLSR produit la plus faible charge de routage (NRL) par rapport aux
protocoles OLSRMet1 et OLSRMet2 durant toutes les valeurs de vitesse maximale (Figure 6.15).
En outre, nous remarquons que les protocoles OLSRMet1 et OLSRMet2 produisent moins de
quantit de NRL par rapport QOLSR pour toutes les vitesses maximales.
QOLSR
MobOLSR
OLSRMet1
OLSRMet2
NRL
2.5
rate (%)
1.5
0.5
0
0
20
40
60
pause time (s)
80
100
Figure 6.15 Comparaison des trois versions du protocole OLSR en termes de NRL
C'est ce qui explique que notre critre propos, qui se base sur des paramtres de mobilit,
demande moins de paquets de routage pour tablir et maintenir les routes dans le rseau.
La figure 6.16, montre que le protocole QOLSR produit le plus de paquets en collision par
rapport aux autres protocoles proposs.
La moyenne des paquets en collision pour QOLSR (respectivement OLSRMet1 et OLSRMet2)
est de 33000 (respectivement 25000) pour toutes les vitesses maximales. En resum,
QOLSR produit un environnement interfr en comparaison avec nos protocoles proposs.
QOLSR
MobOLSR
OLSRMet1
OLSRMet2
Collision
35000
30000
Nbre (#)
25000
20000
15000
10000
5000
0
0
20
40
pause time
60
80
100
120
ENOLSR utilise la mtrique compose avec des contraintes d'nergie; partir de la figure 6.17
nous notons que ENOLSR trouve un compromis entre la bande passante, l'nergie et la mobilit.
Notre protocole propos slectionne les routes stables offrant une bande passante optimale
tout en prolongeant la dure de vie du rseau. OLSR fournit le plus grand dlai par rapport aux
protocoles proposs. Prcisment, le dlai de QOLSR et ENOLSR est denviron 1,65 secondes
(amlioration de 0,3 seconde par rapport OLSR original) avec un taux de mobilit lev (vitesse
maximale gale 140 kilomtres par heure) et diminue prs de 1,25 seconde (amlioration de
0.1sec par rapport OLSR original) dans une topologie statique. Cela nous permet de conclure
que les protocoles ENOLSR et QOLSR assurent dans l'ensemble le mme dlai. Toutefois, il est
intressant de noter que tous les protocoles proposs donnent de bons rsultats que le protocole
OLSR original en terme de dlai. Une dgradation tolrable dans le dbit est remarque pour
notre protocole propos par rapport au protocole QOLSR. Ceci est justifi par l'amlioration
perue dans le paramtre PDF. En effet, durant le processus d'apprentissage de routes, notre
protocole permet d'viter les nuds avec une mobilit leve et de faible nergie rsiduelle,
mme sils offrent une bande passante leve.
Le protocole QOLSR fournit la plus grande valeur de NRL par rapport aux autres protocoles.
ENOLSR assure un NRL optimal. Il dpasse le NRL induit par le protocole OLSR et MobOLSR et
reste infrieur celui de QOLSR. Dans le pire des cas ( la valeur de la vitesse maximale de 40
m/s), le NRL augmente jusqu 2,1% pour le protocole QOLSR, 1,3% pour le protocole OLSR
original et 1,6% pour ENOLSR, MobOLSR, OLSRMet1 et OLSRMet2.
Collision
35000
30000
25000
20000
15000
10000
5000
0
0
20
40
60
80
100
pause time
OLSR
QOLSR
MOBOLSR
MET1
MET2
EN_OLSR
En outre, QOLSR assure un taux bas de PDF par rapport aux protocoles proposs. Une
amlioration de 10% est remarque (respectivement de 65%) en comparaison avec le protocole
OLSR Original (respectivement par rapport MobOLSR ).
121
De lay
2.5
90
2
delay
75
60
1.5
45
30
1
0
20
40
60
80
100
20
40
OLSR
QOLSR
MOBOLSR
60
80
100
pause time
pause time
MET1
MET2
OLSR
EN_OLSR
QOLSR
MOBOLSR
MET1
MET2
EN_OLSR
Avg Throughput
NRL
2.5
230
2
200
1.5
170
1
140
0.5
110
20
40
60
80
100
20
40
pause time
OLSR
QOLSR
MOBOLSR
60
80
100
pause time
MET1
MET2
EN_OLSR
OLSR
QOLSR
MOBOLSR
MET1
MET2
EN_OLSR
6.4.2.4
Dans un environnement mobile, les nuds gostes peuvent avoir un impact majeur sur les
performances des solutions prsentes dans la section 6.3. Dans certains cas extrmes, ces nuds
malveillants peuvent causer de srieux dnis de service. Le principal problme vient du fait que
les MPRs et les chemins de rseau optimaux sont slectionns sur la base dinformations prives
rvles par les nuds. Les nuds gostes peuvent rvler de fausses informations, si ce
comportement peut conomiser leur nergie et leur degr de mobilit. En outre, l'un des
principaux inconvnients du protocole OLSR classique est l'utilisation malveillante des messages
TC. Un nud malveillant compromis peut inonder le rseau avec de faux messages TC.
Afin d'augmenter la dure de vie du rseau, le protocole ENOLSR utilise l'nergie rsiduelle
du nud dans le processus de routage (quation 1).
En particulier, pour les sous-sections suivantes, la simulation sexcute pour 70 secondes. Les
nuds se dplacent de faon alatoire selon le modle de mobilit Random Waypoint (RWP)
[96,101]. La vitesse peut atteindre 40 m/s et le temps de pause est gal 10sec. Nous avons
choisi le modle dnergie dfinie dans NS2 pour modliser la consommation d'nergie dans les
nuds avec (Pt_consume = 3; Pr_consume = 2; P_idle = 0,07, P_sleep = 06; P_transition = 0,5).
L'nergie initiale des nuds est fixe 160. A titre de comparaison, nous avons mesur l'nergie
moyenne des nuds dans MPRSet pour les deux protocoles OLSR et ENOLSR
122
OLSR
MPR_Set Avg_Residual_energy
EN_OLSR
180
150
energy
120
90
60
30
60
64.3
56.3
51.1
49.5
47.7
42.6
38.5
39.7
32.1
28.4
23.9
24.5
17.2
12.7
19.9
5.72
27
time
La figure 6.19 montre que la consommation d'nergie pour le protocole OLSR original est
linaire. Pour le protocole ENOLSR, la dure de vie du rseau est prolonge. En effet, pour le
protocole OLSR original (respectivement pour ENOLSR) le premier nud dcde aprs 17sec
(respectivement 43s). C'est parce que pendant le processus normal de slection des MPR utilis
par le protocole OLSR standard, les MPRs sont slectionns sur la base des paramtres
daccessibilit (nombre de nuds accessibles deux sauts: voisins 2 sauts). Ceci induit une
perte d'nergie pour les nuds qui ont t lus plusieurs reprises en tant que MPR.
Le gain apport apparat clairement dans un environnement o les nuds sont intelligents et
ne rvlent donc pas linformation relle au cours du processus de slection MPR, de peur qu'ils
perdent leur nergie. Ainsi, le critre gnralis est conu pour faire face aux nuds gostes.
Conclusion
Rpondre des exigences de qualit de service de trafic dans les MANETs sont les principales
fonctions de transmission requises pour les applications multimdias. Dans ce chapitre, nous
avons discut des diffrentes approches utilises pour fournir une fonctionnalit de QoS dans
OLSR. Notre mtrique propose est une tentative de faire usage des ressources disponibles et de
trouver le chemin le plus optimal en fonction de plusieurs paramtres en tenant compte des
paramtres de mobilit et d'nergie. La mtrique propose slectionne le chemin le plus stable, en
se basant sur la mobilit et l'information d'nergie et sur les exigences de qualit de service sur la
bande passante. Nos approches proposes sont bases, totalement ou partiellement, sur le degr
de mobilit, l'nergie rsiduelle et la bande passante disponible qui sont quantifis et valus dans
le temps par chaque nud mobile dans le rseau.
La mtrique propose est cense supporter efficacement le trafic multimdia en temps rel
avec diffrentes exigences de qualit de service. Les rsultats de simulation montrent que les
protocoles proposs offrent de bons rsultats par rapport au protocole QOLSR qui est bien connu
comme une extension de QoS du protocole OLSR.
123
Lobjectif initial de cette thse tait dtudier les paramtres permettant damliorer la qualit de
service dans les rseaux sans fil Wifi. Il est rapidement apparu quil tait intressant de cibler
plus le cadre et de sintresser aux rseaux mobiles ad hoc. Ceci est justifi par lomniprsence de
tels rseaux autour de nous, que ce soit dans un btiment, un tage, au travail ou chez soi. Ces
rseaux conceptuellement locaux sont quotidiennement utiliss de manire sous optimale et
ncessitent trop de configuration de la part des utilisateurs, alors quils devraient tre transparents
et faciliter lutilisation des diffrents services existants.
De nombreux protocoles de routage ont ainsi t dvelopps dans le cadre des rseaux ad hoc,
particulirement dans le groupe de travail MANET. Quelques annes plus tard, des approches
diffrentes sont apparues avec des ambitions plus importantes que le simple routage, et intgrant
dautres aspects qui taient auparavant dvelopps sparment. Ces approches se basent sur un
niveau 2.5 pour proposer de nouvelles architectures. Nanmoins, rares sont les solutions qui
sintressent la qualit de services dans ce type de rseaux.
Afin de dterminer les besoins prcis auxquels devrait rpondre une solution de qualit de
service, dans ce type de rseaux, nous avons dans un premier temps dfini plus prcisment leur
nature. Cela nous a permis didentifier les paramtres cls qui les caractrisent (la dynamique) et
proposer par la suite une nouvelle mtrique pour la mesure de la mobilit dans ce type de
rseaux. Le choix dun couplage dun fonctionnement orient mobilit et routage apparat comme
un point central dans cette approche.
Cela semble nanmoins comme un choix paradoxal, car les deux notions semblent se contredire.
Centrer le travail, pour la premire fois, sur une nouvelle approche pour la mesure de la mobilit
est une dcision qui peut aller jusqu choquer dans le monde de la recherche, car cela peut
voquer un retour en arrire. Nous avons cependant montr que cette solution originale permet de
garantir un bon fonctionnement du rseau et que les bonnes performances sont prserves, voire
amlior dans la plupart des cas.
Trouver un chemin satisfaisant plusieurs contraintes (bande passante, pdf, dlai,..), utiliser des
mtriques diffrentes et optimiser le calcul au niveau des nuds (surtout dans un contexte
dynamique) constitue un vritable handicap contre les garanties de la qualit dans ces rseaux.
Une part considrable du travail effectu a consist en la proposition dune mtrique compose
dans le but de surmonter ces contraintes qui pnalisent le fonctionnement et dtriorent les
performances des MANETs.
Se plonger dans le concret de cette manire change ncessairement le point de vue par rapport au
travail effectu, et ce nouvel angle apporte une touche particulire lapproche initiale: prendre
la mesure des difficults quon peut rencontrer en implmentant la mtrique, mais aussi pendant
les tests de celui-ci, a un impact sur les ides quon cherche concrtiser.
Le travail ralis au cours de cette thse a permis de dcouvrir comment exploiter les contraintes
et les faire agir en notre faveur, avec tous les problmes qui se posent chaque nouvelle tape
passe. Le rsultat est cohrent, avec une philosophie particulire, qui se place dans le cadre des
rseaux spontans. Nanmoins, entrer dans les dtails et parvenir rpondre aux questions a aussi
eu pour effet douvrir de nouvelles pistes explorer. Alors que certaines de ces pistes peuvent
apparatre, probablement tort, comme des sujets relativement simples autoconfiguration sur
un rseau multisauts, exprimentations pour observer les problmes des implmentations 802.11
, dautres entrent immdiatement dans la catgorie des sujets particulirement ambitieux
scurit dans les rseaux spontans ou encore architecture pour les rseaux sans fil tendus.
Lexprience acquise pendant la thse aide prendre la mesure de ltendue du travail quil reste
raliser dans le monde vaste des rseaux.
Enfin, avoir travaill sur les niveaux 2 et 3 amne naturellement se poser des questions sur le
fonctionnement actuel des rseaux. La pile rseau actuelle fonctionne parfaitement dans le cadre
dutilisation qui existe aujourdhui, mais nest elle pas non plus un frein linnovation? Garder la
compatibilit avec lensemble des applications utilises aujourdhui est en effet souvent devenu
un des critres essentiels pour toute proposition se voulant srieuse. Sortir du modle ouvre des
perspectives nouvelles encore plus importantes, et la gestion de la mobilit pose la question de la
remise plat des couches comme base de rflexion pour un nouveau modle complet.
Perspectives
La mesure propose dans notre travail, utilise une approche trs simple. Elle se base sur un
calcul priodique, au niveau de chaque nud, des diffrents paramtres entrants en jeu. Pourtant,
il est certain que plus les paramtres sont importants plus la complexit de calcul devient
importante et limplmentation de la solution devient coteuse en termes de ressources CPU,
mmoire, nergie.. (voire impossible). Lide de penser calculer facilement les mtriques
individuelles et dimposer un contrle dadmission au niveau MAC savre intressante.
Aussi, ltude mene dans cet ouvrage suppose, cause de la limitation de loutil de
simulation, que quelques paramtres (porte, capacit des interfaces) sont identiques pour tous les
nuds du rseau; chose qui nest pas vrai dans la ralit. Tenir en compte de ces paramtres
savre complexe, mais elle apparat beaucoup plus pertinente, si on arrive modliser
rellement ces rseaux.
126
Un nouveau type dapplication pour les rseaux ad hoc est le rseau de capteurs. Son principe
est qu il dploy dans lhabitation et forme un environnement, dit environnement pervasif. Son
but est de fournir toutes les informations ncessaires aux applications de confort, de scurit et de
maintenance dans lhabitat. Les capteurs sont des capteurs de prsence, de son, ils peuvent mme
tre quips de camras. Dans la littrature 3G, Ils prennent dautres formes femtoCell et ont
dautres objectifs comme la dtection/gnration des signaux (pour les trous couverture) et
lamlioration de la qualit de service pour lutilisateur final. Un tel rseau dploy doit permettre
de crer une maison intelligente capable de comprendre des situations suivant le comportement
des occupants et den dduire des actions.
Un des problmes majeurs pour le contexte des rseaux de capteurs est que la plupart de ces
techniques ne prennent pas en compte les proprits non fonctionnelles comme la consommation
dnergie. Nous pensons que lextension de notre mtrique ce type de rseaux permettra
damliorer davantage leurs performances.
Le problme de la scurit dans le domaine des rseaux est un problme essentiel, car les
donnes transmises sont potentiellement sensibles et il est souvent ais de les intercepter ou de les
manipuler, notamment dans un rseau possdant une composante sans fil, ou pour lequel tout
nud peut tre routeur. Deux aspects sont ici importants : la scurit du routage et la scurit des
donnes transmises.
Comme la majorit des travaux rseaux dans ce domaine, larchitecture propose actuellement
prsuppose que tous les nuds cooprent et sont de bonne foi . Cette dcision est, en quelque
sorte, culturelle, car la scurit est souvent considre comme auxiliaire dans un premier temps,
et ajoute par la suite. Il est en partie possible dintgrer certains aspects de scurit dans
larchitecture propose dans le cadre de ces travaux.
Il est possible de considrer que la scurit dans un rseau de bordure spontan est plus ou
moins quivalente celle existant dans un rseau normal ou sur Internet. Cest effectivement en
partie vrai puisque les mmes applications sont utilises de la mme faon. Pourtant, ajouter un
nud au rseau est beaucoup moins complexe dans un rseau de bordure spontan, car le rseau a
pour but de grer facilement lapparition des nouveaux nuds. Une premire piste serait donc le
contrle daccs au rseau. La contrainte de non-centralisation peut nanmoins rendre cet aspect
assez difficile, puisque la dcision doit tre distribue et prise en prenant en compte la scurit.
En ce qui concerne le routage proprement dit, les diffrents problmes pouvant tre rencontrs
sont :
Labsence de coopration dun nud : ce cas nest pas particulirement grave, mais il
peut sapparenter au cas suivant ;
Un nud qui cherche tromper dautres nuds pour maximiser ses capacits sur le
rseau : il est tout dabord important de savoir comment caractriser un tel comportement,
car rien ne peut tre fait si aucun autre nud ne sen rend compte. Pour minimiser le
problme, il est possible de sinspirer de la thorie du jeu, et notamment du dilemme
rpt du prisonnier . La stratgie il pour il , qui consiste reproduire le
comportement de lautre : si ladversaire coopre, alors il faut cooprer avec lui et sil ne
coopre pas, il ne faut pas cooprer avec lui. Ou le mcanisme d'incitation bas sur la
127
rputation en utilisant le mcanisme VCG. Dans de dernier, les nuds qui participent
fidlement ces processus vont voir leur rputation augmenter ; ainsi et vu que les
services rseau sont offerts en fonction de la rputation des nuds, il encouragera les
nuds participer honntement. Transposer ces stratgies dans les rseaux est une
solution qui peut mriter une tude approfondie;
Un nud qui nest pas intress par utiliser le rseau, mais qui cherche simplement
empcher son utilisation : il convient probablement ici de disposer dun mcanisme de
rputation permettant dviter de tels nuds. Cependant, si le rseau est en partie sans fil,
il est ais dutiliser le mdium en permanence et de bloquer la partie sans fil du rseau. Il
ny a pas de relle solution dans ce cas.
La scurit des donnes transmises pourrait tre garantie en intgrant une signature garantissant
lintgrit des donnes et lauthentification de lmetteur, et si besoin est, un chiffrement des
donnes. Il sagit dun sujet dtude extrmement complexe, car la moindre erreur peut
supprimer toute scurit.
Les approches qui essayent dappliquer les mcanismes de la micro-conomie ou les mta
heuristique d'optimisation, sur les rseaux adhoc sont dactualit. Les thories de : VCG,
algorithmes de colonies de fourmis, fourmie, L'optimisation par essaims particulaires, etc. (qui
s'appuient eux aussi sur le concept d'auto-organisation) constituent de nouvelles pistes pour
organiser, scuriser et mieux optimiser le fonctionnement de ces rseaux dans le but damliorer
leurs performances.
Comme le montrent les quelques ides exposes dans cette partie, imaginer des pistes suivre
pour les rseaux sans fil ne constitue pas une relle difficult. Mais dvelopper les pistes pour
rsoudre chaque problme soulve chaque fois de nouveaux problmes et constitue un dfi
majeur.
128
Troisime partie
Annexes
Annexe
Network Simulator 2
A.1 Prsentation de Network Simulator 2
NS2 (Network Simulator 2) est un simulateur vnements discrets dvelopp dans un but de
recherche. Il fournit un environnement assez dtaill permettant entre autre de raliser des
simulations dIP, TCP, du routage et des protocoles multicast aussi bien sur des liens filaires que
sans fil .
NS-2, est aujourdhui le simulateur de rseau probablement le plus utilis par la Communaut
scientifique des rseaux. Il a t le fruit de la collaboration entre luniversit de Berkeley, USC
(University of Southern California) et Xerox PARC dans se cadre du projet VINT (Virtual Inter
Network Testbed). Ce projet est soutenu par le DARPA(Defense Advanced Research Projects
Agency). NS-2 est un outil de recherche trs utile pour le design et la comprhension des
protocoles. Il sert aussi bien dans ltude des protocoles de routage qu ltude des rseaux
mobiles ou les communications par satellites.
NS-2 permet lutilisateur de dfinir un rseau et de simuler les communications entre les
noeuds. Le simulateur utilise le langage orient objet OTCL driv de TCL pour la description
des conditions de simulation sous forme de script. Dans le script lutilisateur fournit la topologie
du rseau, les caractristiques des liens physiques, les protocoles utilis, le type de trafic gnr
par les sources, les vnements, etc.
Si le script crit en OTCL permet une utilisation (dition, modification des simulations)
facilite du simulateur, les routines sont elles crites en C++ pour avoir une plus grande
puissance de calculs. Le rsultat dune simulation est un fichier texte contenant tous les fichiers
vnements de la simulation. Un traitement ultrieur de ce fichier permet den soustraire
linformation souhaite. Par ailleurs, le simulateur permet la cration dun fichier danimation
(dextension .tr), permettant de visualiser la simulation sur linterface graphique NAM. Cette
visualisation fournit une reprsentation du graphe du rseau sur laquelle on peut voir les paquets
circuler, suivre le niveau des files dattente et observer le dbit courant des liaisons. La figure A1
prsente une simple utilisation de NS-2.
NS-2 est conu initialement pour fonctionner sur les systmes d'exploitation Unix et Linux,
mais il existe un moyen pour son installation sur un systme Windows 2000/XP; il s'agit de
l'mulateur Cygwin qui offre un environnement Linux sous Windows. Cygwin est tlchargeable
partir d'Internet dans l'url: http:// www.cygwin.com. Le simulateur NS-2 est fourni sous forme
d'un paquetage qui regroupe tous les fichiers ncessaires son installation. On le trouve sous le
nom : ns-allinone-version.tar.gz. (ns-allinone-2.33.tar.gz est utilis dans notre simulation).
A.2.1 Installation de NS-2 sous Windows
Avant de commencer installer NS-2, il faut tout d'abord installer cygwin. Pour ce faire suivre
les tapes suivantes :
A.2.1.1 Installation de cygwin
1. Tlcharger cygwin partir de son emplacement sur internet.
2. lancer l'installation on cliquant sur le bouton suivant.
3. choisir le chemin a partir de quel il s'installe: install from local directory.
4. choisir le chemin d'installation.
5. choisir Next.
6. slectionner les packages installer en activant install.
7. choisir Next.
8. terminer l'installation on cliquant sur terminer.
9. choisir OK.
La liste des principaux composants actuellement disponible dans NS-2 sont reprsents par
catgorie dans le tableau suivant :
.
A.4 Les langages utiliss dans NS-2
NS-2 utilise deux langages parce quil ralise deux types de choses. Dune part, le simulateur
doit tre efficace dans la manipulation de bytes, de paquets et denttes et dans lapplication
dalgorithmes sur de grandes quantits de donnes. Dans ce cas la vitesse dexcution est
primordiale et prend le pas sur le temps de compilation, lutilisation du C++ simpose. Dautre
part, lutilisateur souhaite changer rapidement ses scnarios de simulation, dans ce cas OTCL
offre une bonne solution.
NS-2 permet lutilisateur de dfinir un rseau et de simuler les communications entre les
noeuds. Le simulateur utilise le langage orient objet OTCL driv de TCL pour la description
des conditions de simulation sous forme de script.
Dans le script lutilisateur fournit la topologie du rseau, les caractristiques des liens
physiques, les protocoles utiliss, le type de trafic gnr par les sources, les vnements, etc. Si
le script crit en OTCL permet une utilisation (dition, modification des simulations) facilite du
simulateur, les routines sont elles crites en C++ pour avoir une plus grande puissance de calculs.
Un grand nombre de classes sont prdfinies et mettent en uvre plusieurs types de protocoles,
de files dattentes, de sources et algorithmes de routage.
A.5 Architecture de NS-2
A.5.1 Arborescence des classes compiles
TclObject : Cest la racine de toutes les autres classes la fois dans l'arborescence compile et
interprte. La classe TclObject constitue donc la classe de base de la plupart des autres classes.
Tous les objets du modle de simulation sont des instances de la classe TclObject. Cette classe
sert aux objets dont la cration est initie par l'interprteur. Elle possde les interfaces ncessaires
aux liaisons entre les variables qui doivent tre visibles la fois en C++ et OTcl. Elle dfinit la
fonction command ( ) qui est trs utile pour ajouter des commandes l'interprteur. La classe
TclObject ainsi que les autres sources du rpertoire tclcl sont partages entre NS-2 et le projet
MASH de Berkeley. Dans la hirarchie des classes OTcl, le nom de la classe racine se nomme
autrement et porte le nom de SplitObject.
NsObject : cest une sous-classe de la classe TclObject mais reste cependant une superclasse
aux autres classes. La principale diffrence avec la classe TclObject tient ce qu'elle soit capable
de recevoir des paquets et traiter des vnements. Elle hrite de la classe Handler.
Cette classe constitue la principale racine des objets dans NS-2. Elle contient les fonctions
communes ncessaires au simulateur et dfinit la fonction virtuelle : void recv (Packet *,
Handler* callback =0)=0; Cette fonction est une fonction gnrique utilise par tous les objets
drivs de NsObject pour recevoir un paquet. Elle est rellement dfinie par les sousclasses:
-
Node : un noeud peut tre une machine, un switch, un routeur, une passerelle, etc.
Aprs le droulement de la simulation, NS-2 donne un fichier trace qui est un fichier texte
contenant tous les vnements de la simulation. Le traitement de ce fichier permet den soustraire
linformation souhaite. Chaque vnement est reprsent dans le fichier trace avec une ligne qui
contient douze champs. Le tableau A.2 donne une vision des la structure dune ligne du fichier
trace sous NS-2 :
1. Action effectue sur le paquet. Un + signifie que le paquet est reu dans une file, un -
signifie que le paquet quitte la file, un s signifie que le paquet est envoy un d signifie
que le paquet est jet (drop et un r signifie que le paquet est rceptionn par un agent.
2. Instant o laction est effectue.
3. Noeud de dpart du lien concern
4. Noeud darrive du lien concern
5. Type de paquet.
6. Taille du paquet en bytes.
7. Flags.
8. Identificateur de flux.
9. Agent de dpart.
10. Agent darrive.
11. Numro de squence.
12. Identificateur unique pour chaque paquet.
La figure A4 illustre un exemple dtaill dune ligne dun fichier trace sous NS-2 :
En plus des fichiers traces quoffre le simulateur NS-2, il permet de visualiser les
vnements de la simulation travers une interface graphique NAM (figure A5) :
La figure A6 dcrit la structure dun noeud sans fil dans NS-2. Elle montre le travail interne du
flux dans le noeud sans fil. Le noeud reoit toujours des paquets l'entre du noeud. Le paquet
passe par le classificateur o son champ d'adresse est examin Les agents sont les connecteurs.
Quand les connecteurs reoivent les paquets, ils excutent certaines fonctions et livrent les
paquets vers leurs voisins ou les ignorent. Il existe plusieurs types de connecteurs effectuent
diffrentes fonctions, par exemple, l'agent, Link Layer, couche MAC et d'interface rseau.
Puisque les rseaux ad hoc (MANET) sont souvent analyss par des simulations, leurs rsultats
dexcution dpendent lgrement des paramtres de rseau de simulation. Ainsi, lvaluation
dun protocole de routage ad hoc dpend de choisir soigneusement un modle de mobilit pour
illustrer les mouvements ralistes des utilisateurs. Les modles de mobilit dentit reprsentent
les noeuds mobiles dont les mouvements sont indpendant lun de lautre. Dautre part, les
modles de mobilit de groupe reprsentent les noeuds mobiles dont les mouvements dpendent
lun de lautre et ils tendent tre plus ralistes dans les applications impliquant la
communication de groupe.
Ce modle est dvelopp pour imiter un mouvement imprvisible. Un noeud mobile dans ce
modle se dplace de son endroit courant un nouvel endroit en choisissant alatoirement une
direction et une vitesse suivant lesquelles il se dplace. La nouvelle vitesse et direction toutes les
deux sont choisies dans des gammes prdfinies, [speedmin, speedmax] et [0, 2]
respectivement. Un noeud mobile atteignant la frontire e de simulation, rebonds avec langle
dtermin par la direction entrante et puis continue le long du nouveau chemin.
Conclusion
Dans cette partie, nous avons prsent une brve description de l'outil de simulation NS-2. Nous
avons dcrit les langages utiliss dans ce simulateur, citons tcl et OTcl. Puis nous avons dcrit
l'architecture gnrale de son utilisation, l'arborescence et la hirarchie des diffrentes Classes
existantes. Un point important est visualis c'est l'tude et la cration des Environnements
mobiles dans ce simulateur ainsi l'extraction et le traitement des rsultats.
Annexe
Langage AWK
B.1 Prsentation
AWK est un outil qui permet d'effectuer des recherches, simples ou complexes, dans des fichiers
textes. C'est un langage de programmation datant de 1977, date de son apparition dans le monde
Unix. Il tire son nom des trois programmeurs qui l'ont dvelopp: Alfred V. Aho, Peter J.
Weinberger et Brian W. Kernighan. Cette utilitaire a t cr dans le but de remplacer les
commandes grep et sed. Sa grande souplesse lui a permis de connaitre un succs immdiat. Et de
nouvelles versions sont apparues au fil du temps : nawk et gawk. Aujourd'hui encore, cet
utilitaire est toujours utilis du fait de sa ressemblance avec le langage C, de sa souplesse et de sa
prsence sur la majorit des systmes d'exploitation Unix. Il est encore utilis en administration
systme et dans les scripts Shell en tant que commande. Awk fonctionne en lisant des donnes.
Ces donnes peuvent tre ainsi traites par Lutilisateur. Utilisateur qui peut choisir de lire des
donnes provenant de fichiers ou du canal de l'entre standard. Par consquent, awk a pour but
premier de jouer un rle de filtre bien qu'il ne se limite pas qu' cela.
B.2 Syntaxe gnrale d'un programme awk
Language AWK
Annexe
Codes source
C.1 script Tcl
# A simple example for wireless simulation
#=====================================================================
# Define options
#=====================================================================
set val(chan) Channel/WirelessChannel ;# channel type
set val(prop) Propagation/TwoRayGround ;# radio-propagation model
set val(netif) Phy/WirelessPhy ;# network interface type
set val(mac) Mac/802_11 ;# MAC type
set val(ifq) Queue/DropTail/PriQueue ;# interface queue type
set val(ll) LL ;# link layer type
set val(ant) Antenna/OmniAntenna ;# antenna model
set val(ifqlen) 50 ;# max packet in ifq
set val(nn) 2 ;# number of mobilenodes
set val(rp) DSDV;# routing protocol
#=====================================================================
# Main Program
#=====================================================================
#
# Initialize Global Variables
#
set ns_ [new Simulator]
set tracefd [open simple.tr w]
$ns_ trace-all $tracefd
# set up topography object
set topo [new Topography]
156 ANNEXE
$topo load_flatgrid 500 500
#
# create-god
#
create-god $val(nn)
#
# Create the specified number of mobilenodes [$val(nn)] and "attach" them to the channel.
# Here two nodes are created : node(0) and node(1)
# configure node
$ ns_ node-config -adhocRouting $val(rp) n
Codes Sources
-llType $val(ll) n
-macType $val(mac) n
-ifqType $val(ifq) n
-ifqLen $val(ifqlen) n
-antType $val(ant) n
-propType $val(prop) n
-phyType $val(netif) n
-channelType $val(chan) n
-topoInstance $topo n
-agentTrace ON n
-routerTrace ON n
-macTrace OFF n
-arpTrace OFF n
-movementTrace OFF
for {set I 0} {$i < $val(nn)} {incr i} { set node_($i) [$ns_ node]
$node _($i) random-motion 0 ;# disable random motion }
#
# Provide initial (X,Y, for now Z=0) co-ordinates for mobilenodes
#
$node_(0) set X_ 5.0
$node_(0) set Y_ 2.0
$node_(0) set Z_ 0.0
$node_(1) set X_ 390.0
$node_(1) set Y_ 385.0
$node_(1) set Z_ 0.0
#
# Now produce some simple node movements Node_(1) starts to move towards node_(0)
#
$ns_ at 50.0 "$node_(1) setdest 25.0 20.0 15.0"
$ns_ at 10.0 "$node_(0) setdest 20.0 18.0 1.0"
# Node_(1) then starts to move away from node_(0)
$ns_ at 100.0 "$node_(1) setdest 490.0 480.0 15.0"
# Setup traffic flow between nodes
# TCP connections between node_(0) and node_(1)
set tcp [new Agent/TCP]
$tcp set class_ 2
set sink [new Agent/TCPSink]
$ns_ attach-agent $node_(0) $tcp
$ns_ attach-agent $node_(1) $sink
$ns_ connect $tcp $sink
set ftp [new Application/FTP]
$ftp attach-agent $tcp
$ns_ at 10.0 "$ftp start"
#
# Tell nodes when the simulation ends
#
for {set i 0} {$i < $val(nn) } {incr i} {
$ns_ at 150.0 "$node_($i) reset";
}
$ns_ at 150.0 "stop"
$ns_ at 150.01 "puts N S EXITING...;
$ns_ halt" proc stop {} {
global ns_ tracefd
$ns_ flush-trace
close $tracefd
}
puts "Starting Simulation..."
$ns_ run.
Codes Sources
Codes Sources
# strip leading and trailing _from node
sub(/_*/, "", node);
sub(/_*$/, "", node);
if ( time < simulation_start || simulation_start == 0 ) simulation_start = time;
if ( time > simulation_end ) simulation_end = time;
if ( reason == "COL" ) total_collisions++;
//////////////////////////////////////////////////1
if (( event == "s" || event == "f") && (type == "RTR") && ($35 == "OLSR" ))
routing_packets++;
//////////////////////////////////////////////////1
if ( type == "AGT" ) {
nodes[node] = node; # to count number of nodes
if ( time < node_start_time[node] || node_start_time[node] == 0 )
node_start_time[node] = time;
if ( time > node_end_time[node] )
node_end_time[node] = time;
if ( event == "s" ) {
flows[node] = node; # to count number of flows
if ( time < first_packet_sent || first_packet_sent == 0 )
first_packet_sent = time;
if ( time > last_packet_sent )
last_packet_sent = time;
# rate
packets_sent[node]++;
total_packets_sent++;
# delay
pkt_start_time[packetid] = time; }
else if ( event == "r" ) {
if ( time > last_packet_received )
last_packet_received = time;
# throughput
packets_received[node]++;
total_packets_received++;
# delay
pkt_end_time[packetid] = time; }
else if ( event == "d" )
total_packets_dropped++; }
} END {
number_flows = 0;
for (i in flows)
number_flows++;
# find dropped packets
if ( total_packets_sent != total_packets_received ) {
# printf("*** ATTENTION *** Dropped Packets! nn nn");
for ( packetid in pkt_start_time ) {
if ( 0 == pkt_end_time[packetid] ) {
total_packets_dropped++; } } }
for (i in nodes) {
if ( packets_received[i] > 0 ) {
end = node_end_time[i];
start = node_start_time[i-1];
runtime = end - start;
if ( runtime > 0 ) {
throughput[i] = packets_received[i]*8000 / runtime; } }
# rate - not very accurate
if ( packets_sent[i] > 2 ) {
end = node_end_time[i];
start = node_start_time[i];
runtime = end - start;
Codes Sources
if ( runtime > 0 ) {
rate[i] = (packets_sent[i]*8000) / runtime; } } }
# delay
for ( pkt in pkt_end_time) {
end = pkt_end_time[pkt];
start = pkt_start_time[pkt];
delta = end - start;
if ( delta > 0 ) {
delay[pkt] = delta; } }
# offered load
total_runtime = last_packet_sent - first_packet_sent;
if ( total_runtime > 0 && total_packets_sent > 0)
load = ((total_packets_sent * 8 * 512)/total_runtime) / 2000000; # n=o overhead
printf(" RUN OFFERED PACKETS PACKETS PACKETS ROUTING AVERAGE AVERAGE
AVERAGE
nn FLOWS TIME LOAD SENT RECEIVED DROPPED PAQUET COLLISIONS DELAY
PDF THROUGHPUT TRAFFIC RATE NRL nn -
- - - - nn"); printf("%5d %5.1f %7.4f
%8d %8d %8d %8d %10d %10.4f %10.4f %10.4f %10.4f %10.4f nn",
number_flows,
total_runtime,
load,
total_packets_sent,
total_packets_received,
total_packets_dropped,
routing_packets,
total_collisions,
average(delay),
(float)((100*total_packets_received)/total_packets_sent),
average(throughput),
average(rate),
(float)(routing_packets/total_packets_received));
(float)total_packets_received);
(float)routing_packets);
}
Codes Sources
#!/bin/bash cd /home/simulation/Performance/OLSR/
i=0 while [ $i -lt 50 ] do
i=$(($i+1))
exec /usr/src/ns-allinone-2.29/ns-2.29/ns per_olsr.tcl &
sleep 4000
exec awk -f mesure.awk traOLSR.tr ./mesure/olsr-n50-v30-range250m.dat
sleep 50
done
Bibliographie
[1] N. Abramson. The ALOHA System - Another Alternative for Computer Communications. In
Proceedings of the AFIPS Conference, volume 37, 1970. pages 295298,.
[2] N. Abramson. Development of the ALOHANET. IEEE Transactions on Information Theory,
IT-31(2), March 1985.
[3] R. M. Metcalfe. PACKET COMMUNICATION. Technical report, Massachusetts Institute of
Technology, Cambridge, MA, USA, 1973.
[4] Robert Metcalfe et David Boggs. Ethernet : Distributed Packet Switching for Local Computer
Networks. Communications of the ACM, 19(7) : Juillet 1976. pages 395404,.
[5] L. G. Roberts. Multiple computer networks and intercomputer communication. In SOSP 67 :
Proceedings of the first ACM symposium on Operating System Principles, pages 3.13.6,
New York, NY, USA, 1967. ACM Press.
[6] L. Roberts. The Arpanet and computer networks. In Proceedings of the ACM Conference on
The history of personal workstations, New York, NY, USA, 1986. ACM Press. pages 5158,.
[7 ] Lawrence Roberts. Aloha packet system with and without slots and capture. Computer
Communications Review, 5(2) : Avril 1975. pages 2842,.
[8] L. Kleinrock. Information flow in large communication nets. Technical report, Massachusetts
Institute of Technology, July 1961.
[9] T. Tugend. Ucla to be first station in nation wide computer network. Technical report, UCLA
Press Release, July 1969.
[10] RFC Editor and et al. 30 Years of RFCs. RFC 2555, 1999.
[11] V. Cerf and R. Kahn. A Protocol for Packet Network Intercommunication. Communications,
IEEE Transactions on [legacy, pre - 1988], 22(5), 1974, pages637648.
[12] T. Berners-Lee and R. Cailliau. WorldWideWeb : Proposal for a HyperText Project.
Proposal, CERN, 1990.
[13] Wi-Fi Alliance. http://www.wi-fi.org/.
[14]Tableau
de
bord
trimestriel
du
march
Mobile
http://www.anrt.ma/fr/admin/download/upload/file_fr1888.pdf - Mars 2010
[15] GSA : (the Global
http://www.gsacom.com/
mobile
Suppliers
Association)
March
(04/05/2010).
report
2010
Bibliographie
GHz
band.
[22] 802.11b : Higher speed Physical Layer (PHY) extension in the 2.4 GHz band.
http://standards.ieee.org/getieee802/download/802. 11b-1999.pdf, 1999.
[23] 802.11g : Further Higher-Speed Physical Layer Extension in the 2.4 GHz Band.
http://standards.ieee.org/getieee802/download/802. 11g-2003.pdf, 2003.
[24] 802.11n : Enhancements for Higher Throughput, 2008 (expected).
[25]
802.11i
:
Medium
Access
Control
(MAC)
Security
http://standards.ieee.org/getieee802/download/802. 11i-2004.pdf, 2004.
Enhancements.
Domains.
[27] 802.11h : Spectrum and Transmit Power Management Extensions in the 5GHz band in
Europe. http://standards.ieee.org/getieee802/download/802. 11h-2003.pdf, 2003.
[28] 802.11j : 4.9 GHz5 GHz Operation in Japan.
http://standards.ieee.org/getieee802/download/802. 11j-2004.pdf, 2004.
[29] 802.11e : Medium Access Control (MAC) Quality of Service Enhancements.
http://standards.ieee.org/getieee802/download/802. 11e-2005.pdf, 2005.
[30] A. Colvin. CSMA with collision avoidance. In Computer Communications Techniques,
volume 6Butterworth & Co. (Publishers) Ltd., Oct 1983, pages 225235..
[31] D. Fumolari. Link performance of an embedded Bluetooth personal area network. In
Proceedings of IEEE ICC01, volume 8, june 2001, pages 25732577.
[32] M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda. Performance anomaly of
802.11b. In Proceedings of IEEE INFOCOM 2003, San Francisco, USA, March-April 2003.
Bibliographie
[33] F. A. Tobagi and L. Kleinrock. Packet switching in radio channels : part II the hidden
terminal problem in carrier sense multiple-access and the busy-tone solution. IEEE
Transactions on Communication, 23(12) :14171433, December 1975.
[34] C. L. Fullmer and J. J. Garcia-Luna-Aceves. Solutions to Hidden Terminal Problems in
Wireless Networks. In SIGCOMM, 1997 , pages 3949.
[35] V. Bharghavan, A. J. Demers, S. Shenker, and L. Zhang. MACAW : A media access
protocol for wireless LANs. In SIGCOMM, 1994, pages 212225.
[36] C. L. Hedrick. Routing Information Protocol. RFC 1058, 1988.
[37] G. Malkin. RIP Version 2. RFC 2453, 1998.
[38] S. Corson , J. Macker Mobile Ad hoc Networking (MANET) Network Working Group
January 1999.ftp://ftp.nordu.net/rfc/rfc2501.txt
[39] M.KHEMIS et H.TOUATI, Etude et simulation des protocoles de routage dans les rseaux
ad hoc .mmoire dingniorat 2002/2003, universit de TIZI OUZOU.
[40] Rabah MERAIHI : Gestion de la qualit de service et contrle de topologie dans les
rseaux ad hoc thse de doctorat, Ecole nationale suprieure des tlcommunications,
France. janvier 2005.
[41] ETS 300 652 High Performance Radio Local Area Network (HiperLAN) type 1 Functionnal Specification.
[42] ETS 101 475, ETS 101 761, ETS 101 762, ETS 101 493, ETS 101 763 : High Performance
Radio Local Area Network (HiperLAN) type 2.
[43] Vincent UNTZ : Les rseaux sans fil spontans pour lInternet Ambiant thse de
doctorat, LINP Grenoble Dec- 2007, France.
[44] Bluetooth Network Encapsulation Protocol. http://www.bluetooth.com/NR/rdonlyres/
89B2BA02-D3FB-4717-97A1-A5B10D90F795/912/ BNEPSpecification1.pdf, 2003.
[45] Personal Area Networking Profile (PAN). http://www.bluetooth.com/NR/rdonlyres/
279DC460-295E-42ED-8952-61B723620884/984/PAN_SPEC_V10.pdf, 2003.
[46] C. L. Hedrick. Routing Information Protocol. RFC 1058, 1988.
[47] G. Malkin. RIP Version 2. RFC 2453, 1998.
[48] J. M. McQuillan, I. Richer, and E. C. Rosen. The new routing algorithm for the ARPANET.
Innovations in Internetworking, 1988, pages 119127.
[49] Dominique Dhoutaut, Etude du standard IEEE 802.11 dans le cadre des rseaux ad hoc: de
la simulation l'exprimentation LInstitut National des Sciences Appliques de Lyon ,
Thse Dcembre 2003.
Bibliographie
[50] E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik,
1 :269271, 1959.
[51] J. Moy. OSPF specification. RFC 1131, 1989.
[52] J. Moy. OSPF Version 2. RFC 2328, 1998.
[53] R. W. Callon. Use of OSI IS-IS for routing in TCP/IP and dual environments. RFC 1195,
1990.
[54] IETF MANET Working Group. http://www.ietf.org/html.charters/manet-charter.html, 2000.
[55] S. Corson and J. Macker. Mobile Ad hoc Networking (MANET) : Routing Protocol
Performance Issues and Evaluation Considerations. RFC 2501, 1999.
[56] Tayeb LEMLOUMA Le Routage dans les Rseaux Mobiles Ad Hoc Universit des
Sciences et de la Technologie Houari Boumdiene, Septembre 2000.
[57] D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In
Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers,
1996.
[58] D. Johnson, Y.Hu, and D.Maltz. The Dynamic Source Routing Protocol (DSR) for Mobile
Ad Hoc Networks for IPv4. RFC 4728, 2007.
[59] Y.C. Hu and D. B. Johnson. Implicit source routes for on-demand ad hoc network routing. In
MobiHoc 01 : Proceedings of the 2nd ACM international symposium on Mobile ad hoc
networking & computing, , New York, NY, USA, 2001. ACM Press, pages 110.
[60] C. E. Perkins and E. M. Royer. Ad-hoc On-Demand Distance Vector Routing. In WMCSA
99 : Proceedings of the Second IEEE Workshop on Mobile Computer Systems and
Applications, page 90, Washington, DC, USA, 1999. IEEE Computer Society.
[61] C. Perkins, E. Belding-Royer, and S. Das. Ad hoc On-Demand Distance Vector (AODV)
Routing. RFC 3561, 2003.
[62] S. Ranjan Das, C. E. Perkins, and E. M. Royer. Performance Comparison of Two Ondemand Routing Protocols for Ad Hoc Networks. In INFOCOM (1), 2000, pages 312.
[63] P. Jacquet, P. Mhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot. Optimized
link state routing protocol for ad hoc networks. In Proceedings of the 5th IEEE Multi Topic
Conference (INMIC 2001), 2001.
[64] A. QAYYUM, L. VIENNOT and A. LAOUITI. Multipoint relaying for flooding broadcast
messages in mobile wireless networks. In Proceedings of the Hawaii International Conference
on System Sciences (HICSS 02), Big Island Hawaii, January 2002.
[65] Optimized Link State Routing Protocol (OLSR). RFC 3626, 2003.
Bibliographie
[66] E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik,
1, 1959. pages269271.
[67] C. Tschudin, R. Gold, O. Rensfelt, and O. Wibling. LUNAR : a Lightweight Underlay
Network Ad-hoc Routing Protocol and Implementation. In Proc. Next Generation Teletraffic
and Wired/Wireless Advanced Networking (NEW2AN04), 2004.
[68] C. Tschudin and R. Gold. SelNet : A Translating Underlay Network. Technical report,
Uppsala University, Department of Information Technology, 2001.
[69] R. Gold, P. Gunningberg, and C. Tschudin. A virtualized link layer with support for
indirection. In FDNA 04 : Proceedings of the ACM SIGCOMM workshop on Future
directions in network architecture, New York, NY, USA, 2004. ACM Press, pages 2834,.
[70] G. Chelius and E. Fleury. Ananas : An Ad hoc Network Architectural Scheme In Proc.
MWCN. IEEE, September 2002.
[71] N. Boulicault, G. Chelius, and E. Fleury. Ana4 : a 2.5 Framework for Deploying Real
Multi-hop Ad hoc and Mesh Networks. Ad Hoc & Sensor Wireless Networks : an
International Journal (AHSWN), to be published, 2005.
[72] N. Boulicault, G. Chelius, and E. Fleury. Ana4 : a 2.5 Framework for Deploying Real Multihop Ad hoc and Mesh Networks. Ad Hoc & Sensor Wireless Networks : an International
Journal (AHSWN), to be published, 2005.
[73] E. Crawley, R. Nair, B.Rajagopalan, and H. Sandick., A Framework for QoSbasedRouting
in the Internet, IETF RFC 2386, Aug. 1998. ftp://ftp.nordu.net/rfc/rfc2386.txt.
[74] Leila TOUMI : Algorithmes et mcanismes pour la qualit de service dans les rseaux
htrognes Thse de doctorat, Institut National Polytechnique de Grenoble, dcembre 2002
[75] K. Wu and J. Harms QoS Support in Mobile Ad Hoc Networks. Crossing Boundariesthe
GSA Journal of University of Alberta, Volume 1, n 1. Nouvembre 2001, pages 92- 106.
[76] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss. An architecture for
differentiated services. Internet Request For Comments RFC 2475, IETF, December1998.
ftp://ftp.nordu.net/rfc/rfc2475.txt.
[77] Ian and C.Castelluccia Differentiation mechanisms for IEEE 802.11. In to appear in IEEE
Infocom 2001, april 2001.
[78] P. Sinha, R. Sivakumar, and V. Bharghavan. CEDAR : a core extraction distributed ad hoc
routing algorithm. IEEE Journal on Selected Areas in Communications, special issue on
Wireless Ad Hoc Networks, 17(8) :, august 1999. pages1454-1465.
[80] Cheikh Sarr, Guillaume Chelius, Claude Chaudet, Isabelle Guerin-Lassous colloque: ABE
: Un protocole de rservation de bande passante pour les rseaux ad hoc bass sur IEEE
802.11 inria-00113738, version 1 - CFIP 2006
Bibliographie
[81] Oetiker, T. 1998. MRTG: The Multi Router Traffic Grapher. In Proceedings of the 12th
Conference on Systems Administration (December 06 - 11, 1998). USENIX Association,
Berkeley, CA, pages.141-148.
[82] R. L. Carter and M. E. Crovella. Dynamic Server Selection Using Bandwidth Probing in
Wide-Area Networks. Technical Report TR-96-007, Boston University Computer Science
Department, 1996.
[83] Andreas Johnsson On the Comparison of Packet Pair and Packet Train Measurements Swedish National Computer Networking Workshop, Arlandastad -2003.
[84] Cheikh Sarr, De lapport dune valuation prcise des ressources pour la Qualite de
Service des rseaux ad hoc bass sur IEEE 802.11 Thse de doctorat juillet 2007.
[85] WU K., HARMS J., QoS Support in Mobile Ad Hoc Networks , Crossing Boundariesthe GSA Journal of University of Alberta, novembre 2001.
[86] Lei Chen and Wendi B. Heinzelman (University de Rochester USA) A Survey of Routing
Protocols that Support QoS in Mobile Ad Hoc Networks, IEEE Network.
November/December 2007.
[87] F. BAI and A. HELMY. A survey of mobility models in wireless ad hoc networks. Chapter
2, book on Wireless Ad Hoc and Sensor Networks, June 2004.
[88] Piro Bracka, These de doctorat : une architecture de contrle de mobilit pour le routage
des message dans les rseaux adhoc de grande taille pages 42-63
[89] B. Liang and Z.Haas Predictive distance-based mobility management for pcs networks. In
Preceedings of the Joint Conference of IEEE Computer and communications Societies
(INFOCOM),1999
[90] M.Sanchez. Mobility models. http://www.disca.upv.es/misan/monmodel.htm
[91] V. Tolety. Load reduction in an ad hoc network using mobile servers. Master theis, Colorado
School of Mines, 1999
[92] F. BAI, N. SADAGOPAN and A. HELMY. Important: A framework to systematically
analyze the impact of mobility on performance of routing protocols for ad hoc networks. In
Proceedings of IEEE Infocom, April 2003.
[93] J. Boleng, W. Navidi, and T. Camp. Metrics to enable adaptive protocols for mobile ad hoc
networks, in Proceedings of the International Conference on Wireless Networks (ICWN02),
2002, pages 293298.
[94] X. HONG, T. KWON, M. GERLA, D. GU and G. PEI. A mobility framework for ad hoc
wireless networks. In Proceedings of ACM Second International Conference on Mobile Data
Management (MDM 2001), January 2001.
Bibliographie
[95] Jiun-Long HUANG and Ming-Syan CHEN. On the effect of group mobility to data
replication in ad hoc networks. IEEE Transactions on Mobile Computing, 5(5):, May 2006.
pages 492507.
[96] Geetha JAYAKUMAR and G. GOPINATH. Performance comparison of two on-demand
routing protocols for ad-hoc networks based on random way point mobility model. American
Journal of Applied Sciences, 5(6): 2008. pages 659664.
[97] M. JOA-NG and I. T. LU. A peer-to-peer zone-based two-level link state routing for mobile
ad roc networks. IEEE Journal on Selected Areas in Communications, 17(8):, August 1999
pages1115 1125.
[98] A. LAOUITI and C. ADJIH. Mesures des performances du protocole OLSR. In IEEE
SETIT2003, Tunisia, March 2003.
[99] C. F. Tschudin, H. Lundgren, and E. Nordstrm. Embedding MANETs in the Real World. In
Personal Wireless Communications, IFIP-TC6 8th International Conference, , September
2003, pages 578589.
[100] A. LAOUITI, P. MUHLETHALER, A. NAJID and E. PLAKOO. Simulation results of
the olsr routing protocol for wireless network. In 1st Mediterranean Ad-Hoc Networks
workshop (Med-Hoc-Net), Sardegna Italy, 2002.
[101] Geetha JAYAKUMAR and G. GOPINATH. Performance comparison of two on-demand
routing protocols for ad-hoc networks based on random way point mobility model. American
Journal of Applied Sciences, 5(6):, 2008. pages 659664.
[102] Vincent LENDERS, Jrg WAGNER and Martin MAY. Analyzing the impact of mobility
in ad hoc networks. In ACM/REALMAN, 2006
[103] C. Bettstetter and C.Wagner, The spatial node dis -tribution of the random waypoint
mobility model, Proc. 1s t German Workshop on Mobile Ad -Hoc Network (WMAN02), ,
Ulm, Germany, March 2002 pages.4158.
[104] T. Camp, J. Boleng, and V. Davies, A survey of mobility for ad hoc network research,
Wireless Communication (WCMC): Special issue on Mobile Ad Hoc Networking: Research,
Trends and Applications, 2002, pages.483502.
[105] D.Shukla, Mobility models in adhoc networks, Masters Thesis, FReSIT-ITT, Bombay,
Nov.2001
[106] D.S. Tan, S. Zhou, J. Ho, J.S. Mehta, and H. Tanabe, Design and evaluation of an
individually simulated mobility model in wireless ad hoc networks, Proc. Communication
Networks and Distributed Systems Modeling and Simulation Conference, San Antonio, TX,
2002.
[107] T.Larson and N.Hedman, routing Protocols in Wireleww Ad-Hoc Networks- A simulation
study, masters Thesis, computer science and engineering, Luela university of technology,
Bibliographie
Stockholm, 1998
[109] R. S. SISODIA, B. S. MANOJ and C. Siva Ram MURTHY. A preferred link-based routing
protocol for ad hoc wireless networks. Journal of Communications and Networks, 4(1):14
21, March 2002.
[110] B. S. Manoj, R. Ananthapadmanabha, and C. Siva Ram Murthy, Link Life Based Routing
Protocol for Ad Roc Wireless Networks, Proceedings of Tenth IEEE International
Conference Computer Communications and Networks (ICCCN), October 2001 pages. 573576.
[111] A. TONNESEN. Implementing and Extending the Optimized Link State Routing
Protocol. Master thesis, Department of Informatics, University of Oslo, August 2004.
[112] BRANZEI, RODICA, DIMITROV, DINKO, TIJS and STEF. Models in cooperative game
theory. In Lecture Notes in Economics 2nd ed., page XII-203. Hardcover, 2008.
[113] B.-J. KWAK, N.-O. SONG and L. MILLER. A standard mobility measure for mobile adhoc networks. IEEE Communications Letters, 7:379381, August 2003.
[114] K.oudidi, N.enneya, A. Loutfi, and M.Elkoutbi Mobilit et Routage OLSR, In
proceedings of African Conference on Research in Computer Science and Applied
Mathematics CARI08, October 2008, Rabat, Morocco.pages. 646-657,.
[115]K. Oudidi, N. Enneya, and M. ElKoutbi, Une Mesure Intelligente de la Mobilit dans les
Rseaux Ad Hocs, In Proceedings du 5me confrence sur les systmes intelligents :
Thories et applications SITA08, INPT, 05-07 Mai, 2008, Rabat, Maroc.
[116] N. Enneya, K. Oudidi, M. El Koutbi, Network Mobility in Ad hoc Networks, In
Proceedings of IEEE International Conference on Computer and Communication Engineering
ICCCE08, 13-15 May 2008, Kuala Lumpur, Malaysia pages. 969-973.
[117] N. Enneya, K. Oudidi, and M. ElKoutbi, Network Mobility Behavior in Mobile Ad-hoc
Networks, In Proceedings of Workshop Next Generation Networks NGN08, Fez, Morocco.
[118] N. Enneya, A. Baayer, and M. Elkoutbi, A New Criterion for MPR Selection in OLSR
Protocol, In Proceedings of IASTED Wireless and Optical Communications WOC07 30
May-1 June, 2007 , Montreal, Canada, pages 416-421.
[119] K.oudidi, N.enneya and M.Elkoutbi, Mesure de la mobilit dans les rseaux Ad hoc, In
Proceedings du Workshop sur les Technologies de lInformation et de la Communication,
WOTIC07, ENSIAS, 5-6 Juillet, 2007, Rabat, Maroc
[120] Thomas Fuhrmann, 'Combining Virtual and Physical Structures for Self-organized
Routing', IWSOS/EuroNGI 2006.
[121] Thomas Zahn and Jochen Schiller, 'MADPastry: A DHT Substrate for Practicably Sized
MANETs', In Proc. of ASWN. June 2005
Bibliographie
[122] Y. Charlie Hu, Saumitra M. Das, and Himabindu Pucha, 'Exploiting the Synergy between
Peer-to-Peer and Mobile Ad Hoc Networks', In Proc. HotOS IX Workshop, Lihue, HI, USA,
2003 pages 3742.
[123] The Network Simulator - ns-2. http://www.isi.edu/nsnam/ns/
http://dropzone.tamu.edu/~prajjwal/ns2/main.html
[124] NS2 installation instruction under windows operating SYSTEM. http://140.116.72.80/
smallko/ns2/setup-en.htm, visited on 2008.
[125] H. Badis, A. Munareto, K. A1 Agba, QoS for Ad Hoc Networking Based on Multiple
Metrics: Bandwidth and Delay The Fifth IEEE International Conference on Mobile and
Wireless Communications Networks (MWCN 2003) Singapore - October, 2003
[126] Yanxing Zheng, Turgay korkmaz, W.Dou, Two additive-constrained path selection in the
presence of inaccurate state information, In Computer Communications Journal, Vol. 30,
May 2007, pages. 2096-2112.
[127] F.A. Kuipers, T. Korkmaz, M. Krunz, P. Van Mieghem, Performance evaluation of
constraint-based path selection algorithms, IEEE Network 18 (5) (2004) pages1623.
[128] P. Sinha, R. Sivakumar, and V. Bharghavan. CEDAR : a core extraction distributed ad hoc
routing algorithm. IEEE Journal on Selected Areas in Communications, special issue on
Wireless Ad Hoc Networks, 17(8) :14541465, august 1999.
[129]H. Badis, A. Munareto, K. A1 Agba, QoS for Ad Hoc Networking Based on Multiple
Metrics: Bandwidth and Delay The Fifth IEEE International Conference on Mobile and
Wireless Communications Networks (MWCN 2003) Singapore - October, 2003
[130] S. Chen and K. Nahrstedt. Distributed quality-of-service routing in ad hoc networks. IEEE
Journal on Selected Areas in Communications, special issue on Wireless Ad Hoc Networks,
17(8) :1488 1505, august 1999.
[131]F. Salama, S. Reeves and Yannis Viniotis A Distributed Algorithm for Delay-Constrained
Unicast Routing Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of
the IEEE Computer and Communications Societies. Page: 84 1997
[132] Ying Ge Kunz, T. Lamont, L. Quality of service routing in ad-hoc networks using OLSR
Commun. Res. Centre, Ottawa, Ont., Canada; Proceedings of the 36th Annual Hawaii
International Conference on System Sciences, (HICSS03).
[133] M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of
NP-Completeness, Freeman, San Francisco, 1979.
[134] S. Chen and K. Nahrstedt, On finding multi-constrained paths, ICC98, Atlanta, Georgia,
June 7-11, 1998 pages.874-879.
[135] K.Oudidi, M.Elkoutbi A Mobility Based Metric For Qos In Mobile Ad Hoc Netwoks
Bibliographie