mnt dos dossiers these dev publications jdir07 JDIR07

Description

Equite´ pour re´seau ad hoc Wi-fiFanilo Harivelo Pascal AnelliIREMIA, Universite´ de La Re´union IREMIA, Universite´ de La Re´unionBP 7151, 15 Avenue R. Cassin BP 7151, 15 Avenue R. Cassin97715 Saint Denis Messag 9, France 97715 Saint Denis Messag 9, FranceEmail: [e-mail] Email: [e-mail]— La norme IEEE 802.11 est devenue un standard de la solution inde´pendante de la topologie, auto-configurable etla technologie sans fil. Cependant, son utilisation dans les re´seaux simple dans sa mise en œuvre. Le principe est d’ajouter unad hoc pose des proble`mes de performance et en particulier, en canal de signalisation hors bande. Ce canal est exploite´ selonterme d’e´quite´ d’acce`s. Cet article pre´sente une me´thode d’acce`sun mode tonalite´ d’occupation (busy tone) [3]. FWM utilise lee´quitable (FWM : Fair Wireless MAC) qui est une extension decanal de signalisation pour informer les voisins d’une commu-l’applicabilite´ de la me´thode d’acce`s de 802.11 aux re´seaux adhoc. Pour cela, un me´canisme de type tonalite´ d’occupation est nication ou tentative de communication. Ce canal est inte´gre´couple´ a` la de´tection de la porteuse afin de synchroniser les dans la proce´dure d’e´coute de la porteuse. Les e´valuations dee´tats des noeuds adjacents a` une communication. En e´tendant cette solution ont montre´ qu’une ine´quite´ perdurait a` cause desla connaissance du voisinage des noeuds, la re´solution desinstants ...

Informations

• Publié par: Vion
• Nombre de lectures: 27
• Langue: Français

Extrait

Equit ´ e

pour

r ´ eseau

Fanilo Harivelo IREMIA,Universite ´ deLaR ´ eunion BP 7151, 15 Avenue R. Cassin 97715 Saint Denis Messag 9, France Email: [e-mail]

Abstractnorme IEEE 802.11 est devenue un standard de— La la technologie sans fil. Cependant, son utilisation dans les re´seaux adhocposedesprobl ` emesdeperformanceetenparticulier,en termed'e ´ quite ´ d'acc ` es.Cetarticlepre ´ senteunem ´ ethoded'acc ` es ´ equitable(FWM:Fair Wireless MAC) qui est une extension de l'applicabilit ´ edelam ´ ethoded'acce ` sde802.11auxr ´ eseauxad hoc.Pourcela,unme ´ canismedetypetonalit ´ ed'occupationest couple ´ a ` lad ´ etectiondelaporteuseafindesynchroniserles ´ etatsdesnoeudsadjacents ` aunecommunication.Ene ´ tendant la connaissance du voisinage des noeuds, la re´solution des contentions de 802.11 peut de nouveau s'appliquer efficacement . L'ine´quite´ due a` la transmission sans fil est e´galement traite´e parFWM.Lasolutionpropose ´ eesttir ´ eedel'analysedescauses d'in ´ equit ´ ede802.11dansunr ´ eseauadhoc.FWMseracompar ´ e auxsolutionsdetypetonalite ´ d'occupation.L'appr ´ eciationde lasolutionpropos ´ eeestfaiteaveclesimulateurNS-2surdes situationspr ´ esentantdesph ´ enome ` nesd'ine ´ quit ´ e. I. I NTRODUCTION L'e ´ quit ´ ed'acce ` saucanalestunobjectifimportantpour lesr ´ eseauxsansfil.Lepartagedusupportdansunr ´ eseau ad hoc repose sur les conditions de trafic et e´galement sur la position relative des nœuds les uns par rapport aux autres. Pr ´ ecis ´ ement,certainsnœudspeuvent ˆ etreensituationde famine au vu de la position ge´ographique qu'ils occupent vis- ` a-visdeleursvoisins.L'acce ` sausupportleurestdevenu quasimentimpossible.Ildevientalorstr ` esdifficiledansces conditionsd'envisageruncontro ˆ ledesressources.Cecontr ˆ ole est particulie`rement important lorsque l'on souhaite diversifier lesservicesdecommunicationsurdesr ´ eseauxpourlesquels les capacite´s sont faibles et dont la qualite´ du canal varie significativementdansletemps.L'objectifd' ´ equite ´ d'acce ` sau support est une des principales proprie´te´s que doit offrir une m ´ ethoded'acce ` s. Enfait,l'ine ´ quite ´ d'acc ` esentredesnœudsphysiquement voisinsprovientd'unem ´ econnaissanceduvoisinage.Surun lien sans fil, pour qu'une communication par la m e´thode IEEE 802.11Distributed Coordination Function(DCF) [1] se de´roule correctement, celle-ci ne´cessite que les deux extre´mite´s se coordonnent. DCF comporte un me´canisme de synchronisationentrelasourceetladestinationmais ` acause desdiff ´ erencesdeport ´ eeentred ´ etectionettransmission[2], elleperdenefficacite ´ .Leprobl ` emed'ine ´ quit ´ eprovientdu fait que DCF fonctionne imparfaitement en mode ad hoc. L'approche ´ etudie ´ esouslenomdeFWM(Fair Wireless MAC) s'inscrit dans la continuit e´ de DCF. Elle la rend ope´rante dans lessituationsine ´ quitables.FWMpr ´ esentel'avantagederendre

ad

hoc

Wi-fi

Pascal Anelli IREMIA, Universite´ de La Re´union BP 7151, 15 Avenue R. Cassin 97715 Saint Denis Messag 9, France Email: [e-mail]

la solution inde´pendante de la topologie, auto-configurable et simple dans sa mise en œuvre. Le principe est d'ajouter un canal de signalisation hors bande. Ce canal est exploite´ selon un mode tonalite´ d'occupation ( busy tone) [3]. FWM utilise le canal de signalisation pour informer les voisins d'une comm u- nicationoutentativedecommunication.Cecanalestint ´ egre ´ danslaproce ´ dured' ´ ecoutedelaporteuse.Lese ´ valuationsde cettesolutionontmontr ´ equ'unein ´ equit ´ eperdurait ` acausedes instantsded ´ emarragedelaproce ´ dured'acce ` sausupport.Ces instants restaient diffe´rents entre les nœuds. Par conse´quent, FWMint ` egreunm ´ ecanismedesynchronisationdud ´ emarrage delaproc ´ edured'acce ` sausupportpourles ´ emetteurs.Cette synchronisationestr ´ ealis ´ eeparl'e ´ missiond'unsignalparla station de´synchronise´e sur un deuxie`me canal de signalisation. Lesprobl ` emesd'ine ´ quit ´ eenre ´ seauadhocpassentenpre- mierlieuparl'acce ` sausupport.Aussi,l' ´ etudeseconcentresur lescommunicationsdirectes.Ellepourraensuite ˆ etre ´ etendue sur les communications indirectes. Lesm ´ ecanismesa ` basedetonalit ´ ed'occupationBTMA[3] et DBTMA [4] traitent les proble`mes de station cache´e et stationexpos ´ ees.FWM ´ etendcesm ´ ecanismesparlar ´ esolution du proble`me de re´ception de l'acquittement (ACK) et le supportd' ´ equit ´ e.Leprobl ` emedere ´ ceptiondel'ACKapparaı ˆ t lorsquedeuxstationsexpos ´ ees ´ emettentsimultane ´ ment.Si la premie`re station termine plus toˆ t sa transmission que la deuxie ` mestation,sare ´ ceptiondel'ACKva ˆ etrecorrompuepar l'e ´ missiondeladeuxie ` mestation.Lapremi ` erestationvaalors conclurea ` unecollisionetaccentuerleme ´ canismed' ´ evitement decollision.Celaapourcons ´ equencelade ´ gradationdud ´ ebit total. Lasuitedecedocumentestorganise ´ edelamani ` ere suivante : la section II rappelle quelques notions sur la me´thode DCF et identifie les causes de l'acc e`s ine´quitable surre ´ seauxadhoc;lasectionIIIpr ´ esentelaconception d'unesolutionproprea ` r ´ esoudrelesproble ` mesd'ine ´ quit ´ e; lasectionIV ´ evaluelasolutionpropose ´ edansdessituations caracte´ristiques ; la section V met en perspective le pre´sent travail par rapport aux autres e´tudes dans ce domaine.

II. P ROBL ` EMES D ' INE ´ QUITE ´ DE DCF SUR RE ´ SEAUX AD HOC La me´thode d'acc e`s DCF repose sur le principe de CSMA/CA (Carrier Sense Multiple Access with Collision Avoidancealparsont ´ educan) ´ eade ` stsionicquivitca'lrenimret

e ´ coute.L'activit ´ educanalestde ´ duiteparlade ´ tectiond'une ondeporteuseeffectu ´ eeauniveauphysiquemaise ´ galement par une onde porteuse virtuelle faite au niveau de la couche MAC.Auniveauphysique,lapr ´ esenced'uneondeestdue a` l' e´mission d'un nœud. Au niveau logique, la porteuse est de ´ duitedeladur ´ eedelatransmissionencoursquia ´ et ´ ean- nonce ´ edansl'en-te ˆ tedelatrame.Lesnœuds ` alar ´ eceptionde cette information l'enregistrent dans leur vecteur d'allo cation r ´ eseau(NAV:Network Allocation Vector ). La dure´e comprend un temps inter-trame (SIFS :Short Inter-Frame Space) et le temps de transmission d'un ACK. Un nœud souhaitant e´mettre une trame doit ve´rifier que le canal est reste´ inoccupe´ pendant unep ´ eriodeaumoinse ´ gale ` aunde ´ laiappel ´ eDIFS(DCF Inter Frame Space ). Si le canal est occupe´ ou devient occupe´, le nœud doit retarder sa transmission jusqu' a` ce que le support redeviennelibrependantunedur ´ eedeDIFS.Leretardest de ´ termin ´ eparletiraged'unevaleural ´ eatoireappele ´ ed ´ elai debackofftseice ´ ddeC.ale ´ tsanelelactqueetanent ´ r ´ em inoccupe ´ etarr ˆ ete ´ d ´ esqueceluiredevientactif.Quandled ´ elai debackoffa atteint la valeur nulle, le nœud peut entamer sa transmission.Letirageal ´ eatoiredubackoffefectstefansu ´ ed un intervalle appele´ feneˆtre de contention (CW : Contention Windowrenomb.)aLat ˆ eenefttcedeleiludnoitcnoftseert detentativesdetransmission.Satailleestdoubl ´ ee ` achaque tentativeinfructueuse.Chaque ´ echecindiquequel'e ´ talement desdemandesdansletempsn'apas ´ et ´ eassezimportant.Le tirage doit se faire sur un intervalle plus important. Une fois latrame ´ emiseetled ´ elaiSIFS(Short Inter Frame Space) ´ ecoule ´ ,l'e ´ metteurdoitrecevoirunACK.Autrement,latrame dedonn ´ ees ´ emiseestconsid ´ ere ´ ecommeperdue,lenombrede tentativeestincre ´ mente ´ etlaproc ´ eduredebackoffest reprise. Une des caracte´ristiques de la transmission sans fil provient del'att ´ enuationdusignalenfonctiondeladistance.Lesignal peute ˆ trerec¸usanspourautant ˆ etrede ´ code ´ auniveautrame.Ce casd ´ efinitunezonedede ´ tectiondontlaport ´ eeestnote ´ er s . La zonedetransmissioncorrespond ` auner ´ eceptioncorrectede la trame dont la porte´e est note´e r t ettcdae ´ oinLapo.edelrt ´ e est supe´rieure a` celle de transmission ( r s > r t ). DCF prend encomptel'att ´ enuationdusignalparl'introductiondude ´ lai EIFS (Extended Inter-Frame Space). Quand un nœud rec¸oit une trame dont il peut de´coder l'ent eˆte au niveau physique maisqu'ilnepeutd ´ ecoderauniveauMAC,ilsemeten retraitpourunep ´ eriodeEIFSafindenepasinterf ´ ererdans la transmission en cours. La pe´riode EIFS est environ 7 fois pluslonguequelap ´ eriodeDIFS. Ensupposantl'homoge ´ ne ´ it ´ edese ´ quipementsr ´ eseauxen termedecapacit ´ eetd' ´ energie,lessituationsd'ine ´ quite ´ dans unr ´ eseauadhocpeuventser ´ esumer ` a2situations(Fig.1). Danschaquesituation,lespairesdenœudssont ` aunedistance d > r t l'une de l'autre. La figure 1(a) montre une organisation de re´seau en 3 paires de nœuds. Cette situation illustre une situation de contention d ´ es ´ equilibre ´ edanslaquelleunoulesdeuxnœudsd'unflot ont un niveau de contention plus important que les nœuds des autres flots. Dans la figure 1(a), le nœudS 1 neattne ` dlafaious inactivite´ de S 0 etS 2 pour acque´rir le support. Alors que les

nœudsS 0 etS 2 n'ont pas connaissance de l'un et de l'autre, ilspeuventacqu ´ erirplussouventlesupport.Laconcurrence poureuxestbeaucoupplusfaible[5].Lafigure1(b)pr ´ esente le proble`me bien connu de la station cache´e dans lequel la r ´ eceptionduflot0estperturb ´ eeparl'e ´ missiondunœudS 1 . Ce dernier n'a pas connaissance de la communication entre S 0 etD 0 deduittprocneenead ´ dpeetnieennountonlfiocti, nombreuses collisions au niveau deD 0 tPeo]v.i[ ´ 6eurerc genre de situation, DCF fournit un protocole d' e´change de tramesdecontr ˆ oleRTS/CTS.L'e ´ metteurenvoieavantses donn ´ eesunetrameRequest to Send (RTS) a` la destination. Tous les nœuds recevant cette trame se retirent de la contention pour la dure´e de la communication. Quand la destination rec¸oit le RTS, celui-ci accuse re´ception avec une trame Clear to SendsmmcoicunioatLen.astnalud ´ reeedal(CTS)enpr ´ eci nœudsrecevantleCTSsebloquentpournepasinterf ´ erer avec la communication. L' e´metteur des donne´es commence sa transmission a` la re´ception du CTS. Cependant, ce protocole est inefficace dans une configuration comme la figure 1(b) car les nœuds ne sont pas en mesure de de´coder les trames de contr ˆ oles. Afind'appre ´ cierl'inefficacit ´ e,lesdeuxsituationssont e ´ value ´ esparsimulation.L'e ´ valuationdel'e ´ quit ´ ea ` l'acce ` sest mesure ´ eautraversdud ´ ebite ´ coul ´ eparchaquesourcedeflot. Touslesflotssontidentiquesetsont ´ emis ` ade ´ bitconstant.Au niveau du re´cepteur, l'effet de capture du canal est inexistant. Cela signifie que la superposition de deux signaux au niveau d'un ´ emetteurestconside ´ r ´ eecomme ´ etantunecollisionsans prise en compte de leur puissance. La me´thode d' e´valuation repose sur la simulation faite avec l'outil NS-2. Le d e´bit de chaque flot prend la valeur de l'interface r e´seau (c'est- a`-dire qu'ilg ´ ene ` re ` aunde ´ bitmaximal).Ainsiunseulflotestsuffisant pourchargerlelien.Lafigure2montrel' ´ evaluationpources deux situations. Nous voyons tre`s bien dans la situation de la contentiond ´ es ´ equilibr ´ ee(Fig.1(a))quel'e ´ metteurduflot1 (le nœudS 1 fuosderf).elbatiremeli ` e ´ equntincce ` u'anitucpsra Il doit attendre que les nœudS 0 etS 2 soient au repos en m ˆ emetempspouracce ´ derausupport.Lasituationdela stationcach ´ eemontre ´ egalementunein ´ equit ´ ed'acc ` escomme pr ´ ec ´ edemmentindique ´ e.Cettesituationestm ˆ emepirecar,le flot 0 a disparu. En effet, le nœudS 0 tente de moins en moins souvent l'acc e`s au support du fait de rencontrer chaque fois une ´ chec.Lessituationsdecontentiond ´ es ´ equilibr ´ eeetdela station cache´e sont issues d'une connaissance incompl e`te des activit ´ esduvoisinage.Danslasectionsuivantenousallons e ´ tudieruneextension ` alam ´ ethodeDCFpourcorrigerlede ´ faut d'in e´quite´.

III. FWM : U N ME ´ CANISME D ' ACC ` ES ´ EQUITABLE POUR RE ´ SEAUX AD HOC Une solution au proble`me d' e´quite´ consisterait a` con- cevoirunenouvelleme ´ thoded'acc ` esquisoitpropreaux caract ´ eristiquesdesre ´ seauxadhoc.Cependantlame ´ thode DCFde802.11be ´ n ´ eficied'unelargediffusion.Ilaune certainematurite ´ entermedestabilite ´ etd'interop ´ erabilit ´ e. Ila ´ et ´ ed ´ emontr ´ equelam ´ ethodedereprisedescontentions