G.2.3 Applications (NEW)
Refine
Document Type
- Doctoral Thesis (1)
- Preprint (1)
Language
- English (2)
Has Fulltext
- yes (2)
Keywords
- Channel Hopping (1)
- Channel Scheduling (1)
- Congitive Radio Networks (1)
- On-line algorithm (1)
- competitive analysis (1)
- online optimization (1)
- scheduling (1)
Faculty / Organisational entity
In today’s computer networks we see an ongoing trend towards wireless communication technologies, such as Wireless LAN, Bluetooth, ZigBee and cellular networks. As the electromagnetic spectrum usable for wireless communication is finite and largely allocated for exclusive use by respective license holders, there are only few frequency bands left for general, i.e. unlicensed, use. Subsequently, it becomes apparent, that there will be an overload situation in the unlicensed bands, up to a point where no communication is possible anymore. On the other hand, it has been observed that licensed frequency bands often go unused, at least at some places or over time. Mitola combined both observations and found the term Cognitive Radio Networks [Mit00], denoting a solution for spectrum scarcity. In this concept, so called Secondary Users are allowed to also use licensed bands (attributed to a Primary User) as long as it is vacant.
In such networks, all obligations reside with Secondary Users, especially, they must avoid any interference with the Primary User. They must therefore reliably sense the presence of Primary Users and must decide which available spectrum to use. These two functionalities are called Spectrum Sensing and Spectrum Mobility and describe 2 out of 4 core functionalities of Cognitive Radio Networks and are considered in this thesis.
Regarding Spectrum Sensing, we present our own approach for energy detection in this thesis. Energy detection essentially works by comparing measured energy levels to a threshold. The inherent problem is on how to find such thresholds. Based on existing work we found in literature, we improve techniques and assert the effectiveness of our additions by conducting real world experiments.
Regarding Spectrum Mobility, we concentrate on the point, where the Primary User shows up. At this point, nodes must not use the current channel anymore, i.e. they also have no possibility to agree on another channel to switch to. We solve this problem by employing channel switching, i.e. we change channels proactively, following a schedule shared by all nodes of the network. The main contribution of this thesis is on how to synthesize those schedules to guarantee robust operation under changing conditions. For integration, we considered three dimensions of robustness (of time, of space and of channel) and, based on our algorithms and findings, defined a network protocol, which addresses perturbation within those dimensions. In an evaluation, we showed that the protocol is actually able to maintain robust operation, even if there are large drops in channel quality.
We study an online flow shop scheduling problem where each job consists of several tasks that have to be completed in t different stages and the goal is to maximize the total weight of accepted jobs.
The set of tasks of a job contains one task for each stage and each stage has a dedicated set of identical parallel machines corresponding to it that can only process tasks of this stage. In order to gain the weight (profit) associated with a job j, each of its tasks has to be executed between a task-specific release date and deadline subject to the constraint that all tasks of job j from stages 1, …, i-1 have to be completed before the task of the ith stage can be started. In the online version, jobs arrive over time and all information about the tasks of a job becomes available at the release date of its first task. This model can be used to describe production processes in supply chains when customer orders arrive online.
We show that even the basic version of the offline problem with a single machine in each stage, unit weights, unit processing times, and fixed execution times for all tasks (i.e., deadline minus release date equals processing time) is APX-hard. Moreover, we show that the approximation ratio of any polynomial-time approximation algorithm for this basic version of the problem must depend on the number t of stages.
For the online version of the basic problem, we provide a (2t-1)-competitive deterministic online algorithm and a matching lower bound. Moreover, we provide several (sometimes tight) upper and lower bounds on the competitive ratio of online algorithms for several generalizations of the basic problem involving different weights, arbitrary release dates and deadlines, different processing times of tasks, and several identical machines per stage.