présentée pour obtenir le grade de Docteur en Sciences de l Université d Avignon
174 pages
Français

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

présentée pour obtenir le grade de Docteur en Sciences de l'Université d'Avignon

-

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
174 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Supérieur, Doctorat, Bac+8
THÈSE présentée pour obtenir le grade de Docteur en Sciences de l'Université d'Avignon SPÉCIALITÉ : Informatique École Doctorale 166 « Information Structures Systèmes» Laboratoire d'Informatique d'Avignon (UPRES No 4128) Advances in Network Control and Optimization par Amar Prakash Azad Soutenue publiquement le 26 november 2010 devant un jury composé de : M. KRUNZ Marwan M. Professeur, University of Arizona, États-Unis(USA) Rapporteur M. YECHIALI Uri Professeur, University of Tel Aviv, Israël Rapporteur M. ALTMAN Eitan Directeur de recherche, INRIA, France Directeur M. EL-AZOUZI Rachid Maître de conférences, Université d'Avignon, France Co-directeur M. BERNHARD Pierre Directeur de recherches émérite, INRIA, France Examinateur M. MICHELON Philipe Professeur, Université d'Avignon, France Examinateur M. KUMAR Vinod Senior researcher, Alcatel-Lucent, France Examinateur

  • sistent support

  • rachid maître de conférences

  • support greatly

  • grade de docteur en sciences

  • directeur de recherche emérite


Sujets

Informations

Publié par
Nombre de lectures 50
Langue Français
Poids de l'ouvrage 3 Mo

Extrait

THÈSE
présentéepourobtenirlegradedeDocteurenSciencesdel’Universitéd’Avignon
SPÉCIALITÉ: Informatique
ÉcoleDoctorale166«InformationStructuresSystèmes»
Laboratoired’Informatiqued’Avignon(UPRESNo4128)
AdvancesinNetworkControlandOptimization
par
AmarPrakashAzad
Soutenuepubliquementle26november2010devantunjurycomposéde:
M. KRUNZMarwanM. Professeur,UniversityofArizona,États-Unis(USA) Rapporteur
M. YECHIALIUri Pr,ofTelAviv,Israël
M. ALTMANEitan Directeurderecherche,INRIA,France Directeur
M. EL-AZOUZIRachid Maîtredeconférences,Universitéd’Avignon,France Co-directeur
M. BERNHARDPierre Directeurderecherchesémérite,INRIA,France Examinateur
M. MICHELONPhilipe Professeur,Universitéd’Avignon,France
M. KUMARVinod Seniorresearcher,Alcatel-Lucent,Tomyparents,grandparentsandallteachers,professors
andcolleagueswhohaveimpartedknowledgeinme.Thought,knowledge,education,science,technologyandmoralvalues
aresuperiorthanallreligions,culturesandgeographies.
TheyenlightentheGodinManandkilltheevilinHim.4Preface
Iwouldliketoacknowledgetheco-existenceofcuriosityandignoranceinthemindsof
myselfandallthosewithwhomIinteractedduringmyPh.D.studies. Withtheformer
persistentlytryingtoeffacethelatter,everydayhasbeenastruggletotransformmyself
fromanamateurtoacarefulthinker.
I do not have enough words to gratefully acknowledge my advisor Dr. Eitan Alt-
man for giving me a privileged chance and fostering me as his Ph.D. student. I am
very thankful and indebted to him for providing all the opportunities that kept up a
stimulating and learning research environment. His guidance and advisory support
greatly helped me to steer through my Ph.D. I admire his intellectual thinking and
hardworkingcapabilitiesandhavebeentryingtoinstillthesameinmyselfthroughout
ourinteraction. IwouldalsoliketothankmyCo-advisorDr. RachidEl-AzouziandDr.
SaraAlouffortheirsincereguidanceandhighlyusefuldiscussions. Iwouldalsoliketo
thankthedirectorofMaestrogroupDr. PhilippeNainforsupportingallmyendeavors
such as conference and workshop travels, course work etc. I would like to thank and
acknowledgethesupportprovidedbyCEFIPRA,DAWN,BionetsandWinemprojects
forfinancingmyPhDandseveraltravelstoattendconferencesandseminars.
IamthankfultoProf. MarwanKrunzandProf. UriYechialiforcarefullyreviewing
mythesisandprovidingmewithimportantfeedbackonvariousaspects. Manythanks
goestoPierreBernard,VinodKumarandPhillipeMichelonforbeingpartofmyjury.
I am particularly honored to have been able to collaborate with Prof. Tamer Basar,
Prof. R. Srikant, Prof. George Kesidis and Prof. Vivek Borkar. My deep gratitude goes
to them for hosting me as a visiting scholar and for giving me a privileged chance to
haveenrichingandfruitfuldiscussionwiththem.
1 2At INRIA and at LIA , my research work was carried out in a very lively and
friendlyatmosphere.
I wish to thank all my colleagues who allowed me to discuss with them my ideas
and consistently provided me their useful feedback and more importantly keeping so
friendlyenvironment. I wouldlike tosay thanksto mycolleague Tembinefor hiscon-
sistentsupportduringmyentirePh.D.
Finally, I wish to thank my family, my parents, and also my friends whose support
andencouragementwasalwayswithmethroughoutthedurationofmythesis.
1InstitutNationaldeRechercheenInformatiqueetenAutomatique
2LaboratoireInformatiqued’Avignon
56Abstract
Following the current trend in the growth of wireless mobile applications, the gap be-
tween energy requirement and supply is narrowing down and becoming a stringent
issue. This calls for a research thrust towards energy conservation techniques besides
energy efficient design in wireless mobile technologies. Sleep mode is one of the well
known energy conservation techniques, widely used in several technologies such as
sensor networks [sle09]. Recently it has been provisioned in wireless access network
standards, e.g. IEEE 802.16e (Mobile WiMAX), UMTS, etc. The key idea is to enforce
the mobile devices to enter a dormant (sleep) state during idle periods. As a conse-
quence,ifanarrivaloccursduringthesleepperioditsserviceisdelayedtillthedevice
wakes up and gets ready. This is often called system response delay which is dictated by
a certain QoS requirement. One of the important challenges faced in such networks is
to deal with the tradeoff between energy conservation and system response delay. We
focus on some of the related research topics which are of high importance. We first
develop models for performance evaluation of any sleep policy. Later on, we propose
methodstoobtainoptimalsleeppoliciesundervarioussystemsettings.
Energy conservation is equally important in wireless ad hoc networks. In Delay
Tolerant Networks, data delivery rate is a measure of system performance which is
heavily influenced by the routing/forwarding policy along with the number of nodes
participating in the packet transportation. Since aggressive transmission/forwarding
causes faster battery drain, the lifetime of a node is tightly coupled with the rout-
ing/forwardingpolicy. Clearly,thefundamentaltradeoffbetweenenergyconservation
and the data delivery rate reappears. This calls for a joint design of both activation
and transmission policies. We resort to optimal control theory to obtain joint optimal
policies.
Routing control is another important aspect which governs the network perfor-
mance. In this thesis, we study routing games in a new paradigm of cooperation ex-
tending from Egoism to Altruism for a general network. On one hand a selfish user is
controllingitsflowtomaximizeitsutilitywhileanaltruisticusercaresonlyforthewel-
fareofotherusers. Besidesstudyingtheequilibriumbehavior,wealsoobserveanovel
paradoxical behavior of users. We identify a non-intuitive behavior of users where in-
creasing cooperation causes gain in user’s performance by reducing total cost; we call
"CooperationParadox".
Overall, in this thesis we identify three topics : i) Sleep mode control in wireless net-
7works, ii) Activation and Transmission control in Delay Tolerant Networks, and iii)
Routinggamesingeneralnetworks,focusingonthetwofundamentalideas: i)Energy
controlandii)Routingcontrol. Wediscussthefollowingdifferentsubproblems:
QueueingTheoreticApproachforSleepModeControl: Wechooseasimple M/G/1
queuewithrepeatedinhomogeneousvacationstomodelthesleepmode. Attheendof
each vacation a fixed listening period is used to discover if thereis any arrival waiting
to be served. If so, the sleep cycle is terminated. The theoretical model is applied
to the problem of power saving for mobile devices in which the sleep durations of a
device correspond to the vacation lengths of the server. Various system performance
metrics such as the frame response time and the economy of energy are derived and
illustratedusingaWiMAXexample. Aconstrainedoptimizationproblemisformulated
to maximize the energy economy under QoS constraints. Our analysis allows us not
onlytooptimizethesystemparametersforagiventrafficintensitybutalsotopropose
parametersthatprovidethebestperformanceunderworstcaseconditions.
Optimal Sleep Mode Control via Markov Decision Process: We study the problem
ofscheduling“wakingup”instancesinwhichaservercancheckwhethertheinactivity
period is over prior to waking up a node. We assign a cost proportional to the delay
fromthemomenttheinactivityperiodendsuntiltheserverdiscoversit, a(small)run-
ning cost while the server is away, and also a cost for waking up. Various standards
exist which impose specific waking-up scheduling policies at wireless devices. Using
ourformulationweidentifyoptimalpoliciesamongthem. Weshowthatperiodicfixed
vacation durations are optimal for Poisson arrivals and derive the optimal period. We
showthatthisstructuredoesnotholdforotherinactivitydistributionsandobtainsome
suboptimal solutions which perform strictly better than the periodic ones. We finally
obtain structural properties for optimal policies for the case of arbitrary distribution of
inactivityperiods.
Parametric Control of Sleep Mode: One basic question that arises in sleep mode is:
what policy performs best under a certain condition? Furthermore, what are the opti-
mal parameters for a given policy? To answer these questions, we formulate an opti-
mizationproblemwhichentailscostminimizationoveragivenclassofparameterized
policies. WeshowthattheconstantdurationpolicyisoptimalforPoissoninactivitype-
riods, but not for hyper-exponentially distributed inactivity periods. From the class of
policiesinwhichvacationsarei.i.d. exponentialrandomvariables,weanalyticallyde-
rivethe optimal policyas a function ofthe expected inactivity period. Our framework
allowsustocomparetheperformanceofseveraloptimalandsuboptimalpracticalpoli-
cieswiththatoftheIEEE802.16estandard.
Inchapter[5],weconsideredthejointoptimizationofnodeactivationandtransmis-
sioncontrolinDTNs. PerformanceofaDTNheavilydependsonthenumberofactive
nodes at any instant. Often an active node spends energy for beaconing to discover
the source node in order to enhance the performance. Energy drain due to beaconing
8sometimes results in death of a node before it participates in data transportation. We
obtainedtheoptimalactivationstrat

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents