Bachelor Thesis BCLR-2022-14

BibliographySauter, Simon: Independent colorful vertex sets in large dynamic vertex colored conflict graphs.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 14 (2022).
35 pages, english.

Time-Sensitive Networks are a substantial part of the Industrial Internet of Things. Extensive computation is required to generate sufficient schedules, in order to allow for real-time communication within them. This is due to a time-constraint that each communication has. These communications can vary from various logistical operations to heavy machinery. As such, not meeting these time-constraints can incur financial costs, or even human harm. Most existing solutions for this problem are ill-suited for the dynamic scenario which often appears in real-life. Modern factories are rarely static, since changes to devices, and therefore their communications, occur as new ones are added, or old ones are modified. We built upon a previous approach, using a vertex colored conflict graph model and searching for an independent colorful set, to solve the time-triggered flow scheduling problem. Specifically, we introduce two new algorithms that dynamically generate an independent colorful set, and do so in a fraction of the time. We compare our algorithms to the original one, concluding that a combined approach might lead to the best outcome in terms of runtime and resulting scheduling quality.

Full text and
other links
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Geppert, Heiko
Entry dateMay 31, 2022
   Publ. Computer Science