Rescheduling algorithms for communication protocols

Řídicí technika a robotika

The growing complexity of distributed real-time embedded systems creates new challenges for scientific practices. These systems are expected to implement more and more complex features (mainly related to reliability and flexibility), while respecting strict non-functional constraints (e.g. response time and energy consumption [ZigBee2010]). Therefore, we are faced with an optimization problem, since these requirements are often in contrast. We assume that adaptive systems that are aware of resources and deadlines can provide an efficient way to cover these problems.

We define the adaptivity as a property of a computing component to adapt itself to (1) both the physical changes (power level, clock speed, communication bandwidth/latency) and the logical changes (network topology, software specifications, protocol requirements), (2) both the changes of application requirements and the variable performance of the resources, (3) both on-line changes, when it is performing its function, and off-line changes, prior to that.

The adaptivity of the schedule is often required by the nature of the application, but we are usually quite reluctant to change them, once they have proven to be correct. Therefore, a new schedule is often required to be similar to the original schedule (e.g. some tasks are at the same position).

Various resource reservation techniques have been integrated into modern communication protocols incorporating time-triggered schedules for high-critical messages (such as Profinet IO IRT, beacon enabled ZigBee, FlexRay, Wireless Hart, TTP, SAFEbus...). Following these protocols and their future extensions, we consider dynamic reconfiguration of the application at run-time. However, in order to make these technologies really applicable, it is necessary to develop appropriate rescheduling algorithms [Profinet2010]. One of the possible solutions is to extend the RCPS/TC (Resource Constrained Project Scheduling with Temporal Constraints) model so that it can be applied to the dynamic scenario while keeping the same representation of time and resource constraints.

  • [Profinet2010] Hanzalek, Z. - Burget, P. - Sucha, P.: Profinet IO IRT Message Scheduling with Temporal Constraints. IEEE Transactions on Industrial Informatics, Volume 6, Number 3, Pages 369 - 380, August 2010.
  • [ZigBee2010] Hanzalek, Z. - Jurčík, P.: Energy efficient scheduling for cluster-tree Wireless Sensor Networks with time-bounded data flows: application to IEEE 802.15.4/ZigBee. IEEE Transactions on Industrial Informatics. Volume 6, Number 3, Pages 438 - 450, August 2010.

Required skills: good background in scheduling.