Go to page
 

Bibliographic Metadata

Title
Mobile resource allocation / submitted by Björn Feldkord ; [Reviewers: Prof. Dr. Friedhelm Meyer auf der Heide, Paderborn University, Dr. habil. Marcin Bieńkowski, Wrocław University]
AuthorFeldkord, Björn
ParticipantsMeyer auf der Heide, Friedhelm ; Bienkowski, Marcin
PublishedPaderborn, 2020
Edition
Elektronische Ressource
Description1 Online-Ressource (83 Seiten) : Diagramme
Institutional NoteUniversität Paderborn, Dissertation, 2020
Annotation
Tag der Verteidigung: 23.01.2020
Defended on2020-01-23
LanguageGerman
Document TypesDissertation (PhD)
URNurn:nbn:de:hbz:466:2-36272 
DOI10.17619/UNIPB/1-869 
Files
Mobile resource allocation [0.7 mb]
Links
Reference
Classification
Abstract (German)

Die vorliegende Arbeit behandelt Ressourcenallokationsprobleme für Anwendungen, welche hauptsächlich von mobilen Nutzern ausgeführt werden.Ressourcen werden dabei nah am Nutzer platziert, wie beispielwiese in den Basisstationen des mobilen Netzwerkes. Die Performanz von Anwendungen für den Benutzer hängt unter anderem von Latenzen ab, welche durch eine entsprechende Platzierung gewährleistet werden müssen. So muss die Konfiguration der Ressourcen einerseits stetig angepasst werden, andererseits müssen die entsprechenden Änderungen leicht berechenbar und schnell dürchführbar sein um eine hohe Qualität des entsprechenden Services zu gewährleisten. Wir behandeln zwei grundlegende Modelle, die sich mit der Platzierung mobiler Ressourcen beschäftigen: In unserem Mobile Server Problem untersuchen wir eine fixe Anzahl Ressourcen welche vor Beantwortung einer eintreffenden Anfrage über eine kurze Distanz verschoben werden können. Wir geben für dieses Problem Online Algorithmen an, welche auf vorhandenen Methoden zu ähnlichem Problemen wie k-Server und Page Migration aufbauen, und kompetitive Faktoren asymptotisch nah an einem optimalem Ergebnis erreichen. Unser zweites Problem ist eine Erweiterung des Online Facility Location Problems, in welchem wir dem Online Algorithmus erlauben, die Positionen seiner Facilities über die Zeit zu korrigieren. Dabei limitieren wir die Korrektur sowohl durch damit verbundene, proportionale Kosten, also auch durch eine fest Schranke pro Zeitschritt. Wir geben Online Algorithmen an, welche einen kompetitiven Faktor unabhängig von der Anzahl der Zeitschritte bzw. der Anfragen erreichen und asymptotisch optimal auf der Linie sind.

Abstract (English)

This thesis covers the topic of resource allocation problems that are tailored to scenarios primarily involving mobile users. The resources are placed close to the users, e.g., at the base stations of a mobile network. The performance of applications accessed by the users depends, among other things, on latencies which have to be guaranteed by a suitable placement of the resources. This implies that the configuration of resources must be continuously adapted. However, these changes must be easily computable and quickly applicable to maintain a high service quality. We propose two basic models, which deal with the placement of mobile resources: Our first model is called the Mobile Server problem, where we are concerned with the placement of a fixed number of resources. These resources can be moved over a short distance before answering an incoming request. For this problem, we propose online algorithms based on the methods used in similar problems such as the k-Server and Page Migration problems, and prove asymptotically almost optimal competitive ratios. The second problem is an extension of the Online Facility Location problem, where we allow an online algorithm to correct its positions of the facilities over time. The movement distance is limited implicitly through a cost proportional to the distance as well as directly through a fixed upper bound per time step. We propose online algorithms that achieve competitive ratios independent of time and the number of clients. The results are asymptotically optimal on the line.

License
CC-BY-NC-ND-License (4.0)Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License