A Theoretical Framework for MAC-layer Design in Wireless Networks [Elektronische Ressource] / Angela Feistel. Betreuer: Slawomir Stanczak

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2011
• Nombre de lectures: 17
• Langue: Deutsch

Extrait

A Theoretical Framework for MAC-layer
Design in Wireless Networks
vorgelegt von
Diplom-Ingenieurin
Angela Feistel
geb. Wiesjahn
aus Prenzlau
Von der Fakult¨at IV - Elektrotechnik und Informatik
der Technischen Universit¨at Berlin
zur Erlangung des akademischen Grades
Doktor der Ingenieurwissenschaften
Dr.-Ing.
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr. Anja Feldmann
Berichter: Dr. habil. S lawomir Stanczak´
Berichter: Prof. Dr. Dr. Holger Boche (TU Munc¨ hen)
Berichter: Prof. Dr. Tansu Alpcan
Tag der wissenschaftlichen Aussprache: 21.03.2011
Berlin, 2011
D83Zusammenfassung
Die vorliegende Arbeit besch¨aftigt sich mit einem Themengebiet an der Schnittstelle von
Kommunikationstheorie, Vernetzung und Algorithmendesign: Wie sollen die vorhande-
nen Ressourcen Leistung, Raum und Richtung, Zeit und Frequenz in einem verteilten
drahtlosen Netz mit einer allgemeinen Netztopologie den Nutzern zugewiesen bzw. von
ihnen verwendet werden? Bekanntermaßen kann die Performanz eines drahtlosen Net-
zes erheblich verbessert werden, indem man die Vorteile einer intelligenten Ressourcen-
allokation und eines intelligenten Interferenzmanagements ausnutzt. Unter Verwendung
eines mathematischen Frameworks untersuchen wir Probleme der Ressourcenallokation,
die auf einer gewichteten Summe von Nutzenfunktionen oder der Unterstutzung¨ von
QoS(Quality-of Service)-Anforderungen basieren bzw. beide Ans¨atze vereinen, und legen
einen Schwerpunkt auf den Entwurf verteilter Algorithmen. Unsere Resultate sind auf
drahtlose Netze mit verrauschten Kan¨alen und allgemeinen Leistungsbeschr¨ankungen an-
wendbar und k¨onnen mit einer beliebigen Routing- und/oder Scheduling-Strategie kom-
biniertwerden. NebendemEntwurfvonStrategienzurRessourcenallokation,derAbleitung
ihrer Eigenschaften sowie geeigneter Algorithmen gew¨ahren wir Einblicke in die Aspekte
der praktischen Implementierung.
ImHauptteildieserArbeitkonzentrierenwirunsaufModelledrahtloserNetze,indenen
InterferenzalsRauschenbehandeltwird. DieserTeilleisteteinenBeitragdazu,dieMecha-
nismen der Leistungskontrolle und des Beamformings sowie deren grundlegende Wechsel-
beziehungen und Abh¨angigkeiten besser zu verstehen. Zu Beginn identifizieren wir die
optimaleLeistungsallokation,welcheeineSummevongewichtetenNutzenfunktionenmaxi-
miert und gleichzeitig die durch SIR-Anforderungen repr¨asentierten QoS-Anforderungen
der Nutzer unterstutzt.¨ Dazu analysieren wir einen primal-dual Algorithmus, welcher auf
der dazugeh¨origen linearen Lagrangefunktion basiert, und zeigen, dass dieser Algorith-
mus effizient in einem verteilten Netz implementiert werden kann. Da jedoch die SIR-
Anforderungen fur¨ einige Kanalzust¨ande m¨oglicherweise nicht unterstutzbar¨ sind und um
m¨ogliche best-effort Nutzer zu beruc¨ ksichtigen, kombinieren wir das Problem der Nutzen-
funktionenmiteinerBarrier-Funktion,umdasursprunglic¨ heProblemm¨oglichstgutzuap-
proximieren. Wir beweisen wichtige Eigenschaften dieses Ansatzes und stellen zur L¨osung
einen verteilten rekursiven Algorithmus mit globaler Konvergenz bereit.
AnschließendwidmenwirunsdenAbh¨angigkeitenderLeistungenundderBeamformer,
indem wir das anspruchsvolle Problem der gemeinsamen Optimierung der Ressourcen
iSendeleistung und Empfangsbeamformer in einem verteilten Netz und fur¨ beide oben
genannten Ans¨atze n¨aher beleuchten. Leider ist nicht bekannt, fur¨ welche Klasse von
Nutzenfunktionen das entsprechende gemeinsame Optimierungsproblem in ein konvexes
Problem ub¨ erfuhrt¨ werden kann, so dass eine globale L¨osung in verteilten drahtlosen Net-
zen gefunden werden k¨onnte. Deswegen stellen wir eine alternative verteilte algorith-
mische L¨osung bereit, die zu einem station¨aren Punkt konvergiert. Wir untersuchen ihr
Verhalten in realen drahtlosen Netzen, in denen Messungen und Sch¨atzungen verrauscht
sind, unter Verwendung der stochastischen Approximation. Da der zweite typische Op-
timierungsansatz, der auf QoS-Anforderungen basierende relative Max-Min-Ansatz, nicht
differenzierbarist,scheintdiesesKonzeptmiteinerverteiltenL¨osungnichtvereinbar. Wir
vermuten jedoch, dass dieses gemeinsame relative Max-Min-Problem fur¨ ein Netz mit all-
gemeinen Leistungsbeschr¨ankungen optimal gel¨ost werden kann, u.z. unter Verwendung
der gewichteten Summe der Nutzenfunktionen. Die Verbindung zwischen beiden Proble-
men wird dabei durch die Wahl der Gewichte hergestellt. Der abgeleitete Algorithmus ist
zudem fast vollst¨andig verteilt implementierbar.
ImletztenTeilderArbeituntersuchenwirdasgemeinsameProblemdesSchedulingsund
der Leistungkontrolle in einem drahtlosen Netz mit orthogonalen Kan¨alen mit dem Ziel,
die gewichtete Summenrate zu maximieren. Da die Schedulingvariablen typischerweise
diskret sind, stellen wir mit Hilfe der Relaxation dieser Variablen eine obere Schranke
fur¨ das gestellte Problem bereit. Anschließend leiten wir interessante Eigenschaften des
ursprunglic¨ hen, diskreten Problems und eine heuristische L¨osung ab.
Zum Abschluss der Arbeit zeigen wir vielversprechende weiterfuhrende¨ Themen und
Problemstellungen auf.
iiAbstract
This thesis addresses a problem at the nexus of communication theory, networking and
algorithm design: how to allocate radio resources to users in distributed wireless networks
with a general network topology? We emphasize that the network performance can be
significantly improved by taking advantage of an intelligent resource allocation and inter-
ference management. Based on a mathematical framework we study resource allocation
problemswhichareutility-based,QoS(Quality-ofService)-basedoracombinationofboth,
with an emphasis on distributed algorithm design. Our results apply to networks with
noisy channels and general power constraints and can be combined with any fixed routing
and/or scheduling strategy. In addition to algorithmic solutions and their properties we
give insights into practical implementation issues.
Inthemainpartofthisthesiswefocusonmodelsofwirelessnetworkswhereinterference
is treated as noise. This is one step forward to a better understanding of the mechanisms
power control and beamforming as well as their interdependencies. First we combine the
QoS-based and utility-based power control approach by incorporating QoS support in
terms of minimum SIR targets into the utility-based power control problem. We analyze
a primal-dual algorithm that is used to find a stationary point of an associated linear
Lagrangian function and show that this algorithm can be efficiently implemented in a
distributed manner. Since the SIR requirements might be infeasible for some channel
states and in order to incorporate possible best-effort users we combine the traditional
utility function with a barrier function to closely approximate the utility-based power
control problem with QoS support. We prove relevant properties of optimal solutions and
propose a distributed recursive algorithm with global convergence.
After that, we address the challenging problem of jointly optimizing powers and receive
beamformers in distributed wireless networks. Unfortunately it is not known for which
class of utility functions such a joint utility-based problem can be converted into a convex
one such that a global solution can be found in distributed wireless networks. Neverthe-
less we reveal a distributed algorithmic solution that converges to a stationary point and
investigate its behaviour in real-world wireless networks using the framework of stochastic
approximation. Considering on the other hand the QoS-based approach, the main chal-
lenge is to solve the max-min SIR-balancing problem in a distributed manner. In order to
address this challenge, we solve the max-min SIR-balancing problem for a network with
general power constraints by instead maximizing a weighted sum of utilities. The con-
iiinection between both problems is provided by the weights of the utilities. We conjecture
that the algorithm derived converges to the optimal max-min SIR-balancing solution but
is semi-distributed due to some control data exchange which is required to calculate the
weights.
Finally we discuss a joint scheduling and power control problem in a wireless network
with orthogonal channels. The main objective is to maximize a weighted sum rate. First,
byrelaxingthediscreteschedulingvariablesandbysolvingtherelaxedproblemweprovide
an upper bound to the original discrete problem. Subsequently we analyze the original
discrete problem and derive a heuristic solution.
We conclude the thesis by highlighting topics of future interest.
ivAcknowledgement
During the last years I received support from many people; this thesis would not have
been possible without them. First of all I thank my advisors Dr. S lawomir Stanczak´ and
Prof. Holger Bochefor the possibilityto workin sucha stimulatingresearchenvironment,
for their guidance and support. My special thanks go to Dr. Stanczak´ and my room mate
Shuying Shi for sharing countless ideas and discussions. I am very grateful to Prof. Tansu
Alpcan, who dedicated his time and energy to act as second referee of this thesis. Thanks
for valuable discussions