Présentée pour obtenir le grade de Docteur en Sciences de l'Université d'Avignon et des Pays de Vaucluse France de l'Université Mohammed V Agdal Rabat Maroc

Eitan Altman

Description

Niveau: Supérieur, Doctorat, Bac+8

• dissertation

THÈSE Présentée pour obtenir le grade de Docteur en Sciences de l'Université d'Avignon et des Pays de Vaucluse France & de l'Université Mohammed V-Agdal Rabat - Maroc SPÉCIALITÉ : Informatique École Doctorale 166 « Information Structures Systèmes» Laboratoire d'Informatique d'Avignon (UPRES No 4128) MAC Protocols Design and a Cross-layered QoS Framework for Next Generation Wireless Networks par Essaïd Sabir Soutenue publiquement le 24 septembre 2010 devant un jury composé de : M. BOUYAKHF El-Houssine Professeur, LIMIARF/FSR, Rabat Président M. ALTMAN Eitan Directeur de recherche, INRIA, Sophia Antipolis Directeur M. EL-AZOUZI Rachid Maître de Conférences, LIA, Avignon Co-directeur M. CHAHED Tijani Professeur, Telecom SudParis, Paris Rapporteur M. ELKOUTBI Mohammed Professeur, ENSIAS, Rabat Rapporteur M. EL-OUAHIDI Bouabid Professeur, Université Mohammed V-Agdal, Rabat Rapporteur M. HAYEL Yezekael Maître de Conférences, LIA, Avignon Examinateur M. BELHADJ Abdenabi Responsable Veille Technologique, Maroc Telecom Invité Laboratoire LIA, Avignon Laboratoire LIMIARF, Rabat

• el-azouzi rachid


• sociate professor


• wireless networks


• go also


• tional support


• associate professor


• professor tijani


• grade de docteur en sciences

Sujets

• Dissertation
• Laboratoire Informatique d'Avignon
• École nationale supérieure d'informatique et d'analyse des systèmes
• Antipolis
• Belhadj

Informations

• Publié par: profil-feym-2012
• Publié le: 01 septembre 2010
• Nombre de lectures: 66
• Langue: Français
• Poids de l'ouvrage: 6 Mo

Extrait

THÈSE
PrésentéepourobtenirlegradedeDocteurenSciencesdel’Universitéd’Avignonet
desPaysdeVaucluseFrance&del’UniversitéMohammedV AgdalRabat-Maroc
SPÉCIALITÉ: Informatique
ÉcoleDoctorale166«InformationStructuresSystèmes»
Laboratoired’Informatiqued’Avignon(UPRESNo4128)
MACProtocolsDesignandaCross layeredQoS
FrameworkforNextGenerationWirelessNetworks
par
EssaïdSabir
Soutenuepubliquementle24septembre2010devantunjurycomposéde:
M. BOUYAKHFEl Houssine Professeur,LIMIARF/FSR,Rabat Président
M. ALTMANEitan Directeurderecherche,INRIA,SophiaAntipolis Directeur
M. EL AZOUZIRachid MaîtredeConférences,LIA,Avignon Co directeur
M. CHAHEDTijani Professeur,TelecomSudParis,Paris Rapporteur
M. ELKOUTBIMohammed Professeur,ENSIAS,Rabat
M. EL OUAHIDIBouabid Pr,UniversitéMohammedV Agdal,Rabat
M. HAYELYezekael MaîtredeConférences,LIA,Avignon Examinateur
M. BELHADJAbdenabi ResponsableVeilleTechnologique,MarocTelecom Invité
LaboratoireLIA,Avignon LaboratoireLIMIARF,Rabat2Preface
TheresearchworkofthisdoctoralthesishasbeencarriedoutintheLaboratoired’Informatique
Mathématiques Intelligence Artificielle et Reconnaissance de Formes (LIMIARF), Uni
versityofMohammedV Agdal,Rabat,MoroccoandLaboratoireInformatiqued’Avignon
(LIA),UniversityofAvignon,France;Duringtheyears2007 2010.
Iamprofoundlythankfultomyadvisors,ProfessorEl HoussineBouyakhfandAs
sociateProfessorRachidEl Azouzi. Iwillalwaysbeindebtedforallthesupport,guid
ance, encouragement, their friendly mood that makes it enjoyable to work with them,
and understanding they have given me throughout these years. It was a real pleasure
toworkwithsomeonessohighlymotivated,smart,enthusiastic,andpassionateabout
their work. Many thanks go to my co advisors Professor Eitan Altman and Associate
ProfessorYezekaelHayelfortheirguidancethathelpedmecontinuemyresearchinthe
rightdirectionandtheinvaluablesuggestions,discussions,andwonderfulfeedback. It
isagreathonortoworkwithyou.
I am most grateful to my reviewers Professor Bouabid El Ouahidi (Faculty of sci
ences, Rabat), Professor Mohammed El Koutbi (ENSIAS, Rabat), and Professor Tijani
Chahed(TelecomSudParis,France)fortheirthoroughexaminationofthedissertation.
My thanks go also Doctor Abdenabi Belhadj (R&D, Maroc Télécom). Their detailed
commentssignificantlyimprovedthequalityofthisthesis.
IthankallpastandpresentcolleaguesattheLIAandLIMIARFLabs. forthejoyful
andpleasantworkingenvironment. Inparticular,IwouldliketothankNabil,Lahcen,
Khalil,Abdellatif,Amar,Tembiné,Sihame,Raïss,Baslam,Tania,Julio,Solan,Oussama,
Mohammed, Ralph, Thierry, and Sujit. To the great staffs of LIA and LIMIARF, I am
verythankfultoallofthem.
IwouldliketothankmywifeSihameMerchaforherunconditionalsupportthrough
outthesethreeyears,especiallyduringallthedifficulttimeswewentthroughwhilewe
hadtoliveapartfromeachotherinaforeigncountryforsolong. Inspiteofalldifficul
ties, I am extremely proud of all we have accomplished together in this long journey.
Forsure,thisdoctoratewouldhavenotbeenpossiblewithouthertremendousencour-
3agement,love,patience,companionshipanddeeptrustinme.
Most importantly, my deepest gratitude also goes to my parents Fatima Badri and
Mohammed Sabir who have always filled my life with generous love, and uncondi
tional support. This doctorate is truly theirs! My thanks go also to my lovely sisters
and brothers, my uncle Saleh Sabir and all my family for their endless moral support
throughoutmycareer. TothemIdedicatethisthesis.
Finally, I want to thank the financial support I have received from the Moroccan
FrenchcooperationdrivenbythePôledeCompétencesenSciencesetTechnologiesde
l’InformationetdelaCommunication(STIC).Iwouldalsothankthefinancialsupport
oIhavereceivedfromtheMarocTélécomR&Dprojectundergrant N 10510005458.06PI
andtheEuropeanWINEMproject.
Rabat,September24,2010
EssaïdSabir.
4Abstract
The present dissertation deals with the under utilization problem of medium access
control in wireless collision channels and other closely related problems known in
wireless networks. It deals with the design of random access protocols for wireless
systems and provides a mathematical framework for performance evaluation of multi
hopbasedheterogeneouswirelessnetworks. Anewmodelingframeworkisalsointro
ducedfortheanalyticalstudyofMACprotocolsoperatinginmultihopwirelessadhoc
networks, i.e., wireless networks characterized by the lack of any pre existent infras
tructure and where participating devices must cooperatively provide the basic func
tionalitiesthatarecommontoanycomputernetwork. Toshowtheapplicabilityofour
modelingframework,wemodelwirelessadhocnetworksthatoperateaccordingtothe
IEEE802.11standard. Toaccomplishthis,wepresentacomprehensiveanalyticalmod
eling of the IEEE 802.11 and the derivation of many performance metrics of interest,
suchasdelay,throughput,andenergyconsumption.
The rest of this dissertation is divided into three parts. The first part comprises
Chapters 1, 2 and 3. We first propose and evaluate four new power control enabled
algorithms of slotted aloha with priority and capture effect. Both team problem (com
monobjectivefunctionismaximized)andgameproblem(eachusermaximizesitsown
objective)werediscussed. Extensivesimulationswereimportanttounderstandthebe
havior of such a system and the real impact of involved parameters (transmit power,
transmit rate, arrival rate). Next, we present a new hierarchical slotted aloha version.
Indeed,weconsidertwoclassesofusers(leadersandfollowers)andcomputetheStack
elberg equilibrium of the constructed game. Introducing hierarchy seems to provide
many promising improvement without (virtual controller) or with a low amount of
external/common information (the case of several leaders). Later we analyzed a colli
sionchannelsystemwhereeachuserhassomethroughputdemandtofulfillinorderto
maintainitsservice. Consideringnonsaturatedusers,weshowedexistenceofinfinitely
manyNashequilibria. Anotherinterestingfeatureisthatthestabilityregioncoincides
with the Nash equilibria region. In this context and regarding the energy investment,
weshowedexistenceofanefficientNashequilibriumforallactiveusers. Later,wepro
posed two distributed algorithms to converge to the best Nash equilibrium point. The
firstalgorithmisderivedfromthebestresponsestrategy, whereasthesecondlearning
algorithmisfullydistributedandusesonlytheuser’sowninformation.
ThesecondpartcomprisingChapters4and5,isdevotedtoissuesrelatedtoperfor-
5mance evaluation of heterogeneous wireless networks composed of a cellular system
extended by a multi hop ad hoc network. We based our study on an analytical model
that takes into account topology, routing, random access in MAC layer, forwarding
probabilityandafiniteretriesperpacketperpath. Wedistinguishthreekeyfeaturesof
thenetworkmodelthatmakeourcontributioninthisthesisnovelwhenconsideredall
together. First, packet scheduling in the network layer. Using a Weighted Fair Queue
ing, wemainlyaddressedthecooperationeffectandthestabilityregionofforwarding
probabilities. Second,theasymmetryofthemulti hopheterogeneousnetworkinterms
of topology, traffic and nodes intrinsic parameters. Lastly, we built a cross layer ar-
chitecture that makes important information available to concerned layers and allows
to benefit from this latter. The case of a homogeneous ad hoc network study is also
presentedtoderivethedistributionofdelay,itcouldbestraightforwardlyextendedto
heterogeneousnetworks.
In a spirit similar to that of part 2, the third part presents a more realistic cross
layered model. We indeed developed a new analytical modeling of the IEEE 802.11e
DCF/EDCF in the context of multi hop ad hoc networks. We formulated two cou
pled systems for the NETWORK and the MAC layers. The attempt rate and collision
probabilities are now functions of the traffic intensity, of topology and of the routing
decision. For more generality, we also considered a finite retries per packet per path.
Ononehand,thislatterisresponsibleofasymmetricqueueservicerateandthereforeof
servicetimedistribution. Ontheotherhand,ithasadirectimpactontheperformance
of a loaded network. Finally, we showed how to take benefit from the interaction be
tweenNETWORK,MACandPHYlayers. Extensivesimulationsandnumericalresults
are carried out to assist and confirm our work. A Fountain code based MAC layer
is also proposed to improve the throughput and establish better fairness properties.
Our scheme aims also to reduce the expected number of retransmissions per packet
and takes benefit from incremental redundancy of previous received copies of a given
packet. Throughseveralsimulations,weshowedthatusingFountaincodesinthecon
text of multi hop ad hoc networks improves the throughput of paths that suffer from
bad channel conditions, i.e., high collision probability. It may nevertheless decrease it
onotherpaths. Howeverthislatterschemeachievesbetterfairnessindex(Jain’sindex)
inthewholenetwork,soathroughput/fairnesstradeoffcanbeefficientlydefined.
6Résuméetorganisationdelathèse
Mots clés : WiMAX, UMTS,