Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

174 pages
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

Voir plus Voir moins

SPÉCIALITÉ: Informatique
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
myselfandallthosewithwhomIinteractedduringmyPh.D.studies. Withtheformer
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
ourinteraction. IwouldalsoliketothankmyCo-advisorDr. RachidEl-AzouziandDr.
SaraAlouffortheirsincereguidanceandhighlyusefuldiscussions. Iwouldalsoliketo
thankthedirectorofMaestrogroupDr. PhilippeNainforsupportingallmyendeavors
such as conference and workshop travels, course work etc. I would like to thank and
IamthankfultoProf. MarwanKrunzandProf. UriYechialiforcarefullyreviewing
mythesisandprovidingmewithimportantfeedbackonvariousaspects. Manythanks
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
1 2At INRIA and at LIA , my research work was carried out in a very lively and
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-
Finally, I wish to thank my family, my parents, and also my friends whose support
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-
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
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
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
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
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
Optimal Sleep Mode Control via Markov Decision Process: We study the problem
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
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
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-
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
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
Further, we also obtained the optimal transmission strategy which is tightly coupled
with the activation strategy. By using Pontryagin maximum principle we obtained the
EnergyandDelayTradeoffinDelayTolerantNetworks: Theperformanceofadelay
tolerant network has a strong dependence on the number of nodes participating in
datatransportation. Suchnetworksoftenfaceseveralresourceconstraintsparticularly
those related to energy. Energy is consumed not only in data transmission but also in
severalsignalingactivities. Oftenanactivenodespendsenergyforbeaconinginorder
toenhancetheperformance. Energydrainduetobeaconingsometimesresultsindeath
Flow Control in Network Routing Games: We study the routing game when each
formance and that of other users by controlling the routing of its given flow demand.
of cooperation ranging from selfish to altruistic behavior. We identify multiple Nash
demand and topology). Interestingly, we identified a Cooperation Paradox where seem-
ingly cooperative behavior leads to gain in users’ performance by reducing total cost.
Keywords: Queueingtheory,Markovdecisionprocess,Dynamicprogramming,Opti-

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin