# Infrared image pedestrian target detection based on Yolov3 and migration
learning

Geng Shengqi
Chongqing University

###### Abstract

With the gradual application of infrared night vision vehicle assistance
system in automatic driving, the accuracy of the collected infrared images of
pedestrians is gradually improved. In this paper, the migration learning
method is used to apply YOLOv3 model to realize pedestrian target detection in
infrared images. The target detection model YOLOv3 is migrated to the CVC
infrared pedestrian data set, and Diou loss is used to replace the loss
function of the original YOLO model to test different super parameters to
obtain the best migration learning effect. The experimental results show that
in the pedestrian detection task of CVC data set, the average accuracy (AP) of
Yolov3 model reaches 96.35%, and that of Diou-Yolov3 model is 72.14%, but the
latter has a faster convergence rate of loss curve. The effect of migration
learning can be obtained by comparing the two models.

###### Index Terms:

Transfer learning, Infrared image ofpedestrians, Object detection, Yolo

##  I Introduction

In recent years, with the development of various industries towards
intelligent direction, autonomous driving has also become the key development
and transformation direction of the traditional automobile industry. In the
complex driving environment, automatic driving requires extremely high
accuracy and speed of pedestrian detection, otherwise it is easy to lead to
traffic accident tragedy. Therefore, finding the image detection method that
can effectively judge and locate pedestrian is the key task for the
development of automatic driving technology.

At present, pedestrian detection is mainly based on visible light imaging data
provided by vehicle-mounted optical imaging system. However, visible light
imaging is greatly influenced by environmental factors. In severe weather
conditions, such as heavy rain, heavy snow, thick fog, and extremely strong or
weak light, visible light images will lose some details. Meanwhile, it is also
limited by the need for pedestrian detection when driving at night. To solve
this problem, the adoption of night pedestrian identification technology using
far-infrared night vision camera [1] has significant advantages, and the
processing of infrared images collected ensures the accuracy of pedestrian
detection.

In this paper, I directly trained the CVC infrared data set on the basis of
the Yolov3 model by using the deep transfer learning method, trained the
marked CVC pedestrian data set on the basis of the pre-training weight
provided, and replaced the loss function of the original model with Diou loss.
Diou has the advantages of scale invariance and faster loss convergence, etc.,
which make up for the lack of slow convergence speed of the original loss
function. Based on Diou loss function YOLOV3 transfer learning solutions of
the model greatly accelerates the convergence speed and convergence degree of
loss, both before and after I will replace loss function through the
experiment model is applied to the infrared image at the same time the
pedestrian detection, and the two models after the experiment, comparing the
results of evaluation index proves that two models have their own advantages
and disadvantages.

##  II Related Work

At present, researches on infrared image pedestrian detection are mainly
divided into two categories: one is based on traditional machine vision
method, and the other is based on deep learning method. The application of the
latter in infrared image pedestrian detection technology is gradually maturing
and improving.

In the field of traditional machine vision, Ma Ye [2] proposed the background
subtraction method based on the improved Gaussian mixture model (GMM) to
segment human targets, and at the same time, he realized the correct detection
of human targets in complex scenes by using Support vector machine (SVM). Su
Xiaoqian [3] improved the three-frame difference method and adopted the three-
frame difference method based on regional estimation to realize pedestrian
detection in vehicle-mounted infrared images. Xu Ming [4] used the
significance detection principle based on frequency domain to generate the
region of interest graph, and trained the neural network to generate the
pedestrian target probability graph, thus realizing pedestrian detection.

With the development of target detection algorithms in the field of deep
learning, many algorithms are used to solve the problem of infrared pedestrian
detection. The SE-MSSD framework based on SSD improvement was proposed by Liu
Xue [5]. He used the deep separable coil product method and embedded SENet
module in the network, which was better than the original SSD algorithm. Li
Muskai [6] found that the target classification ability of YOLOv3 model was
not perfect, so he integrated the idea of weighted demarcation of features in
SENet into YOLOv3 to better describe pedestrian characteristics. The LenET-7
system proposed by Cui Shaohua [7], which contains 3 convolutional layers, 3
pooling layers and 1 output layer, solves the problem of miscellaneous
parameters of full convolutional neural network and improves the detection
rate of infrared pedestrian images.

##  III Math

###  III-A Introduction of yolov3 model

In the field of target detection, Yolov3 has advantages over other algorithms.
It was developed from Yolov2, yolov3, and improved on them, with significant
performance improvements. The key points of YOLOV3 model are mainly reflected
in the following three aspects: the use of the backbone network darknet53, the
introduction of Residual network and the adoption of DarknetConv2D structure
in Residual network.Yolov3 chose Darknet-53 as its backbone network, which
contains a large number of 3 $\times$ 3 and 1 $\times$ 1 convolutional layers,
eliminating the full connection layer and convolutional layer, which can well
avoid this shortcoming. Each of its convolution parts uses the unique
DarknetConv2D structure, and convolution is normalized before
BatchNormalization, followed by negative non-zero activation function
LeakyReLU.

Figure 1: DarknetConv2D structure

In addition, Residual blocks in Residual network skip connection in Residual
network no longer limit the increase depth of the neural network, so that the
accuracy can be improved and the optimization can be improved more easily.

Figure 2: Residual block structure

416*416*3 image was input into the Yolov3 model and three different scales of
prediction were output via the Darknet53 network. Each scale for each of the N
channels contains bracanchors for each grid and each size. So we have 13 times
13 times 3 plus 26 times 26 times 3 plus 52 times 52 times 3.Each prediction
corresponds to 85 dimensions, with 4 representing coordinate value, 1
representing confidence score and 80 representing coco categories. The input
and output block diagram of the whole Yolov3 is as follows

Figure 3: I/O block diagram of yolov3

###  III-B Use diou loss function

Yolov3 adopts iou loss, which consists of three parts: the intersection ratio
between the prediction frame bbox and the ground-truth is defined as iou, and
then the loss function is defined as

$L_{IoU}=1-\frac{|B\cup B^{gt}|}{|B\cap B^{gt}|}$ (1)

However, it can be seen from the definition that IoU loss is always 0 and IoU
loss will be constant in the case that the prediction box bbox and ground-
truth are non-intersecting. If the two boxes do not intersect, IoU loss is
always 0. In addition, the two boxes have the same intersection area and there
are many ways of intersection, so it is impossible to determine which way the
two boxes intersect, which will result in the failure to determine the
optimization direction. Although the Subsequent Giou proposed by Stanford
scholars made up for this deficiency. But there are still many shortcomings.
To solve these problems, Zheng et al. proposed Diouloss(Distance-IoU loss) in
2020 [8], and added the punishment term $R_{DIoU}$ on the basis of IOU, which
is defined as follows

$R_{DIoU}=\frac{\rho^{2}(b,b^{gt})}{c^{2}}$ (2)

Where, the center point of $B$ and $B^{gt}$ is represented by $b$ and
$b^{gt}$. $\rho(\cdot)$ is the diagonal distance. $c$ represents the minimum
diagonal distance of the outer rectangleas shown in the figure 5, so diou is
defined as

$L=1-IoU+R(B,B^{gt})$ (3)

Figure 4: iou loss

Figure 5: Diou loss

###  III-C Transfer learning of Yolov3 model based on Diou

The purpose of transfer learning is to apply the information learned in the
source domain to the learning process of the target domain [9].Pedestrian
detection, for example, if the training from the very beginning eventually
reach the purpose of infrared pedestrian detection needs a large number of
data sets, high force and time loss, but if you have in large data sets, such
as ImageNet migration training part of the model, model training beforehand
weight was applied to the infrared image pedestrian recognition field,
training on the basis of CVC infrared data sets, can quickly achieve the
pedestrian detection, and the precision can be guaranteed to a certain extent.

In this paper, the original YOLOV3 model was firstly migrated and learned.
However, iou loss, the boundary box regression loss function adopted by
YOLOV3, could not distinguish the optimization direction well under the
condition that the intersection between the real box and the prediction box
was 0 and multiple intersection were equal, and its application in infrared
image pedestrian detection had some shortcomings. Therefore, aiming at the
loss function problem of iou loss, this paper adopts the migration learning of
The Yolov3 model based on DIOU loss. Due to the adoption of DIOU loss, the
redundant prediction boxes are filtered out and the experimental results
before and after are compared. It is found that the loss curve declines faster
and converged faster, but the accuracy is not as good as the original model.

##  IV Experiment

###  IV-A Experimental environment and data set

The hardware and software configuration of the experimental environment is as
TABLE I

TABLE I: Hardware and software configuration of the experimental environment Name | The related configuration
---|---
The CPU memory |  | Intel(R) Core(TM)i5-10200H CPU
---
@2.4GHz(8 CPUs), $\sim$2.4GHz
GPU | GeForce GTX 1650 Ti
Accelerated environmental | CUDA10.1 CUDNN7.6.5
Operating system | Windows 10
data processing | Python
deep learning framework | Darknet-53

The purpose of this paper is to realize infrared image pedestrian target
detection, so a large number of infrared image pedestrian data sets from the
driving perspective are needed. This article from the Internet to download the
CVC - 09: FIRSequencePedestrianDataset [10] as migration study data sets. The
content is the infrared image taken by the vehicle infrared camera instrument
under the driving environment. The data set annotation file is in XML format,
with only a category label ”Person”. The label information includes the width
and height of the target box and the coordinates of the center point. In this
paper, 1080 images from the CVC data set are selected as the training set for
the migration learning training, and 120 images are selected as the test set
to detect the migration learning effect

Figure 6: Part of the training set Figure 7: Partial test set sample

###  IV-B Experimental evaluation index

In order to evaluate and compare the migration learning effects of the two
different models, considering that infrared pedestrian belongs to single-
target detection, this paper adopts the standard evaluation index AP of
single-type target detection to evaluate the detection accuracy after
migration learning training. AP is defined as: taking the recall rate of
infrared pedestrian as the abscissa and the accuracy rate of infrared
pedestrian as the ordinate, drawing a two-dimensional coordinate curve and
integrating it, and the result is AP. Accuracy is defined as

$Precision=\frac{TP}{TP+FP}$ (4)

Recall rate is defined as

$Recall=\frac{TP}{TP+FN}$ (5)

In Equations (4) and (5),TP represents the number of pedestrians identified on
the road,FP represents the number of pedestrians identified on other objects
such as vehicles and bicycles on the road, and FN represents the number of
pedestrians not identified.

###  IV-C Experimental process and result analysis

This experiment mainly idea is first super parameter of the experiment was
carried out, according to the results of the AP selection value using the
training effect of the best parameters, different Epoch number to freeze,
determine the best Freeze Epoch and Unfreeze Epoch migration study effect,
after use the same training set and testing set of YOLOV3 and migration
DIOU_yolov3 model training and testing, read the same weights training files,
finally compared to the average loss value curve of the two models and AP
values.

Figure 8: Experimental flow diagram

TABLE II shows the parameter test process. According to the results, in order
to train the network effectively and predict the results better, the network’s
super parameters need to be set reasonably. The values of momentum, iteration
times, batch size, and learning rate are set to optimize the hyperparameters
.The set of parameters that are used to train the network are listed in Table
II. Each set of values was used to train the network, and 100 images were used
to test the accuracy of each result. Finally, a set of values that can
maximize the quality of the network is selected as the final hyperparameter.

TABLE II: Parameter test table Parameter name | Parameter value
---|---
epoch | 25 50 100
Batch size | 1 2 4
learning-rate | 0.0001 0.001 0.005
momentum | 0.5 0.7 0.9

According to the accuracy of the training results of each group of parameters,
epoch is 100, Freeze Epoch is 50, Unfreeze Epoch is 50, Batch size is 1, and
learning-rate is 0.001 as the final parameters, which are applied to the
migration learning training of the two models at the same time. The result is
as Table III.

TABLE III: The value of the final selected parameter | Epoch(Freeze Epoch
---
and Unfreeze Epoch)
Batch size | learning-rate | momentum
100(50+50) | 1 | 0.001 | 0.9

After the training, the test set was predicted in batches, and the detection
results were obtained as follows. The Fig.11 shows the detection results of
YOLOV3 model. It can be seen that the detection accuracy of small targets on
the road is not high, there is the phenomenon of missing detection, and there
is the situation of repeated detection when pedestrians overlap. The Fig.12
shows the detection results of diou-Yolov3 model. It can be seen from the
detection results that, in the case of pedestrian overlap, two target boxes
are well separated, which solves the problem of repeated detection.

Figure 9: Yolov3 detection results Figure 10: Diou-Yolov3 detection results

Figure 11: Yolov3 Loss curve

Figure 12: Diou-Yolov3 Loss curve

In order to compare the advantages and disadvantages of the two loss functions
before and after the improvement, I plotted the loss function curves of the
two models on the same figure which is Fig.13. Through comparison, it can be
clearly seen that compared with the loss function before the improvement, the
improved DIou loss function declines faster, has better convergence and is
more stable.

Figure 13: Comparison of loss curves between two models

Table IV shows the test results of the two models. It can be seen from the
table that the detection results of the two models on 120 test images are
obtained, among which the AP of Yolov3 model reaches 96.35%, and a total of
416 target pedestrians are detected, among which 347 pedestrians are correctly
detected and the number of rows of error detection is 69. The AP of the
Diou_Yolov3 model reached 72.14%, and 273 target pedestrians were detected,
among which 261 rows were correctly detected and 12 were error detected. By
comparison, it was found that the detection accuracy of the improved model was
not as good as that of the original Yolov3 model. From the perspective of
accuracy, the migration learning effect of the improved model was not ideal.

TABLE IV: Comparison of performance indexes of two models Network model |  | Number of
---
predicted objects
TP | FP | AP/%
Yolov3 | 416 | 347 | 69 | 96.35
Diou_Yolov3 | 273 | 261 | 12 | 72.14

The following are the two model AP graphs after the program is run

Figure 14: Diou-Yolov3 Accuracy curve of the model

Figure 15: Yolov3 Accuracy curve of the model

##  V Conclusion

Based on autopilot in road pedestrian use infrared image targets detection
requirements, using the two models with Diou_yolov3 Yolov3 migration study, in
has trained a large number of data set of target detection for the weights
based on training, training their CVC data set, test of different parameters
in the process, and the freezing and thawing different Epoch, and adopt the
best parameters used in migration study training, and the freezing of
different Epoch will be the result of two kinds of model training has carried
on the contrast and analysis, Finally, it is concluded that the AP of the
original Yolov3 model can reach 96.35%, and the AP of the Diou_Yolov3 model is
72.14%. Although the loss function is improved, the detection accuracy is not
high, but the curve of the loss function has a faster convergence speed, and
the convergence result is lower and more stable. To sum up, the method of
migration learning is used to realize the detection of pedestrians in infrared
images.

## References

  * [1] Peng huanliang. Development of infrared focal plane thermal imaging technology [J]. Laser and infrared, 2006 (S1): 776-780
  * [2] Ma ye, Chang Qing, Hu Guifa. Research on infrared human target detection algorithm in complex background [J]. Infrared technology, 2017,39 (11): 1038-1044 + 1053
  * [3] Su Xiaoqian, sun Shaoyuan, Gorman, Qiao Shuai, Gu Xiaojing. Pedestrian detection and tracking technology of vehicle infrared image [J]. Laser and infrared, 2012,42 (08): 949-953
  * [4] Xu Ming, Yu Xiaosheng, Chen Dongyue, Wu Chengdong, Jia Tong, Ru Jingyu. Pedestrian detection in complex thermal infrared monitoring scene [J]. Acta Sinica, 2018,23 (12): 1829-1837
  * [5] Liu Xue, Li Fanming, Liu Shijian. Improved pedestrian detection algorithm for SSD infrared image [a] Shanghai Institute of Technical Physics, Chinese Academy of Sciences, Shanghai Society of infrared and remote sensing, Shanghai Society of sensing technology. Proceedings of the Symposium and interdisciplinary forum on infrared, remote sensing technology and application in 2019 [C]. Shanghai Institute of Technical Physics, Chinese Academy of Sciences, Shanghai Society of infrared and remote sensing, Shanghai Society of sensing technology: Shanghai Society of infrared and remote sensing, 2019:7
  * [6] Li Mukai, Zhang Tao, Cui Wennan. Research on infrared pedestrian small target detection technology based on yolov3 [J]. Infrared technology, 2020,42 (02): 176-181
  * [7] Cui Shaohua, Li Suwen, huangjinle, Shan Wei. An improved method for pedestrian detection in single frame infrared images by CNN [J]. Infrared technology, 2020,42 (03): 238-244
  * [8] Zheng Zhaohui, Wang Ping, Liu Wei, et al. DistanceIoU Loss: Faster and Better Learning for Bounding Box Regression. 2019:
  * [9] Guan Yin. Flower recognition system based on residual network transfer learning [J]. Computer engineering and application, 2019, 55
  * [10] CVC-14: Visible-FIR Day-Night Pedestrian Sequence Dataset – Elektra (uab.es)


ETH Zurich, Switzerlandhttps://orcid.org/0000-0002-2218-5750 TU Munich,
Germany TU Dresden, Germanyhttps://orcid.org/0000-0003-1450-2506German
Research Foundation (DFG) within the Emmy Noether project NextIoT (grant ZI
1635/2-1) ETH Zurich, Switzerlandhttps://orcid.org/0000-0003-0879-2455
University of North Carolina at Chapel Hill, United
Stateshttps://orcid.org/0000-0002-0503-6235 ETH Zurich,
Switzerlandhttps://orcid.org/0000-0001-6139-868XSwiss National Science
Foundation program "NCCR Automation" Romain Jacob, Licong Zhang, Marco
Zimmerling, Jan Beutel, Samarjit Chakraborty, and Lothar Thiele[500]Computer
systems organization Real-time system architecture [500]Computer systems
organization Sensors and actuators [500]Networks Sensor networks Prior 4-page
publication [jacob2018ttw]: https://doi.org/10.23919/DATE.2018.8342127 Project
webpage – TTW Artifacts – Authors’ Contributions (CRediT)Marcus Völp 1 32nd
Euromicro Conference on Real-Time Systems (ECRTS 2020) ECRTS 2020 ECRTS 2020
July 7–10, 2020 Virtual Conference 165 19

# The Time-Triggered Wireless Architecture

Romain Jacob  Licong Zhang  Marco Zimmerling  Jan Beutel  Samarjit Chakraborty
Lothar Thiele

###### Abstract

Wirelessly interconnected sensors, actuators, and controllers promise greater
flexibility, lower installation and maintenance costs, and higher robustness
in harsh conditions than wired solutions. However, to facilitate the adoption
of wireless communication in cyber-physical systems (CPS), the functional and
non-functional properties must be similar to those known from wired
architectures. We thus present Time-Triggered Wireless (TTW), a wireless
architecture for multi-mode CPS that offers reliable communication with
guarantees on end-to-end delays among distributed applications executing on
low-cost, low-power embedded devices. We achieve this by exploiting the high
reliability and deterministic behavior of a synchronous transmission based
communication stack we design, and by coupling the timings of distributed task
executions and message exchanges across the wireless network by solving a
novel co-scheduling problem. While some of the concepts in TTW have existed
for some time and TTW has already been successfully applied for feedback
control and coordination of multiple mechanical systems with closed-loop
stability guarantees, this paper presents the key algorithmic, scheduling, and
networking mechanisms behind TTW, along with their experimental evaluation,
which have not been known so far. TTW is open source and ready to use:
ttw.ethz.ch

###### keywords:

Time-triggered architecture, wireless bus, synchronous transmissions.

###### category:

##  1 Introduction

For decades, real-time distributed control systems have mostly relied on
fieldbuses like CAN, FlexRay, and PROFIBUS. Following the design principles of
the Time-Triggered Architecture (TTA) [kopetz2003TTA], these systems provide
predictability of functional and non-functional properties. Yet, wired systems
are increasingly reaching their limits as future cyber-physical systems (CPS)
demand higher flexibility and cost efficiency. Low-power wireless
communication promises to meet these demands by allowing for an unprecedented
degree of mobility and deployment flexibility, avoiding cable breaks or faulty
connections, and providing greater robustness to heat, humidity, abrasive
substances, and undamped vibrations. However, to be viable for mission-
critical CPS, a wireless system must feature timing predictability similar to
traditional wired systems. Moreover, short end-to-end delays (tens of
milliseconds), high reliability, and multiple years of battery lifetime are
required for many applications [akerberg2011Future].

The past years have seen significant progress in this direction. In
particular, the concept of _synchronous transmissions_ [ferrari2011Glossy] has
enabled highly reliable and efficient low-power wireless communication
protocols that are robust to the unpredictable dynamics of wireless systems.
As further detailed in [zimmerling2020Survey], this is because of two main
reasons: (_i_) synchronous transmissions enable the design of protocols whose
logic is _independent of the time-varying network state_ , which leads to a
highly deterministic protocol execution regardless of changes in the network;
(_ii_) synchronous-transmission-based communication protocols inherently
exploit _different forms of diversity_ , including sender and receiver
diversity as well as temporal and spatial diversity, leading to a reliability
as high as 99.9999 % in certain scenarios [ferrari2011Glossy]. In fact, since
its inception in 2016, all top three teams at the annual EWSN Dependability
Competition have built on synchronous transmissions, demonstrating dependable
multi-hop communication even in extreme wireless interference scenarios
[schuss2017Competition]. Building on this dependable base, protocols have been
designed that provide sub-microsecond network-wide time synchronization while
abstracting from the complexity of the underlying dynamic network topology,
thus allowing to reason about a low-power wireless network as if it were a
shared bus [ferrari2012LWB].

In light of this recent progress, we ask: _Is it possible to design a
reliable, adaptive, and efficient time-triggered architecture for low-power
wireless multi-hop networks with formal guarantees on end-to-end delays among
distributed application tasks?_ If so, it would take wireless systems a
decisive step closer to wired systems by providing similar abstractions and
guarantees as those researchers, engineers, and operators are used to, thus
enabling powerful new CPS applications in industry, healthcare, energy, and
many other domains.

Challenges. There are four key technical challenges standing in the way of a
time-triggered architecture for low-power wireless multi-hop networks.

  1. 1.

_Real-time communication in the face of radio duty cycling._ In a fieldbus, a
node can listen idly without incurring costs, allowing it to react immediately
to a request. In a low-power wireless bus [ferrari2012LWB], instead, a node
must turn its radio off whenever possible to save energy, which renders the
node unreachable until the next scheduled wake-up. To reduce energy costs due
to idle listening, wireless protocols schedule communication rounds, where all
nodes wake up, exchange messages, and go back to sleep (_e.g._ ,
[ferrari2012LWB, wirelessHART, jacob2019Baloo, watteyne2017Teaching]).
Deciding when rounds take place and which nodes can send messages in each
round to meet real-time deadlines at minimum energy costs is a complex
scheduling problem; for example, the allocation of messages to rounds
resembles combinatorial NP-hard bin packing [korte2006Combinatorial].

  2. 2.

_Coupling of communication and application tasks._ What ultimately matters in
a CPS are the real-time constraints among application tasks executing on
distributed devices. Hence, task executions and message exchanges over the
wireless network must be coupled to guarantee end-to-end deadlines. A common
approach for wired fieldbuses is to statically co-schedule all tasks and
messages [abdelzaher1999combined, ashjaei2017Designing, craciunas2016Combined]
to minimize delays by solving a satisfiability modulo theories (SMT)
[craciunas2014SMTbased, huang2012Static, steiner2010evaluation] or a mixed
integer linear programming (MILP) [azim2014Scheduling] problem. To apply this
approach to a wireless bus, we must embed the above-mentioned bin-packing
problem into the schedule synthesis. This, however, introduces non-linear
constraints that cannot be easily handled in a SMT or MILP formulation (see §
4.3).

  3. 3.

_Dependencies across modes._ Static co-scheduling lacks runtime adaptability.
This is often mitigated by enabling the system to switch at runtime between
multiple operation modes, each having a pre-computed scheduling table
[fohler1993changing]. The real-time guarantees that can be provided across
mode changes depend on the mode-change protocol [chen2018SafeMC] and how the
modes are scheduled. For example, if the periodicity of a task should be
preserved across a mode change, this task must have the same schedule in both
modes. A naïve approach to handle such dependencies across modes is a single
MILP formulation with a global objective function. However, the poor
scalability of the scheduling problem (NP-hard [jeffay1991nonpreemptive])
becomes a bottleneck for any realistic CPS scenario with many modes, while
holding no guarantee that the computed schedules perform efficiently in terms
of energy.

  4. 4.

_Worst-case communication time._ The synthesis of scheduling tables requires
an accurate model of the timing of all operations, including the worst-case
execution time of tasks _and_ the worst-case communication time of messages.
While staple methods exist for tasks [wilhelm2008worstcase], a predictable
protocol implementation is needed that yields accurate upper bounds on the
time required for exchanging messages across a multi-hop network.

Contributions. This paper presents Time-Triggered Wireless (TTW), a wireless
architecture for multi-mode CPS. By addressing all of the above challenges,
TTW provides: (_i_) highly reliable and efficient communication across dynamic
low-power wireless multi-hop networks; (_ii_) formal guarantees on end-to-end
delays among distributed application tasks; (_iii_) runtime adaptability
through mode changes that respect the tasks’ periodicity constraints. With
this, TTW does not only significantly advance the state of the art in real-
time wireless systems, but also represents a solid foundation for the design
of dependable wireless CPS.

l250.5ptb4.5pt\makebox(18.0,12.0)[]{}l157ptt88.5pt\makebox(12.0,12.0)[]{}l61ptt88.5pt\makebox(12.0,12.0)[]{}l61ptt54pt\makebox(18.0,12.0)[]{}l1ptt39pt\makebox(18.0,12.0)[]{}

Figure 1:  High-level overview of the Time-Triggered Wireless (TTW)
architecture.

As shown in Figure 1, TTW consists of two main components: a system-wide real-
time scheduler that executes offline and a communication stack called TTnet
that runs online on distributed low-power wireless devices. Based on the
application specification (_e.g._ , tasks, messages, modes) and system
parameters (_e.g._ , number of nodes, message sizes), the scheduler
synthesizes optimized scheduling tables for the entire system. These tables
are loaded onto the devices, and at runtime each device follows the table that
corresponds to the current mode. TTnet provides a generic interface to
implement different mode-change protocols [chen2018SafeMC].

Our design of the real-time scheduler uses concepts from network calculus
[leboudec2001Network] and novel heuristics to addresses challenges 1.–3.
Further, our design of TTnet addresses challenge 4. by exploiting synchronous
transmissions, in particular the deterministic behavior of Glossy floods
[ferrari2011Glossy]. As indicated for node N1 in the bottom right corner of
Figure 1, a Glossy flood sends a message to all nodes in a multi-hop network
with a reliability that can exceed 99.9 % in certain networks and challenging
conditions [ferrari2012LWB, schuss2017Competition], yet the time this process
takes can be confined to a time slot of known length. TTnet groups a series of
such time slots into rounds to save energy. This yields a highly timing-
predictable protocol execution for which we devise timing and energy models as
input for the TTW real-time scheduler.

We implement TTW on physical platforms and open-source our implementation
[repoTTW]. Using this implementation, we perform real-world experiments on 27
low-power wireless nodes of the FlockLab testbed [lim2013FlockLab]. The
results demonstrate that, for the settings we tested, our models are highly
accurate and provide accurate upper bounds for the schedule synthesis; for
example, our timing model overestimate the length of a round in TTnet by at
most 0.7 ms. The results also show that our scheduling techniques can
effectively reduce the energy cost of wireless communication in TTW and make
the scheduling problem tractable: the solving time for one mode on a standard
laptop PC ranges from a few seconds to a few minutes depending on the
complexity of the mode (_e.g._ , number of tasks and messages).

In addition, TTW already proved its utility for practical wireless CPS
representative of emerging applications, such as remote control in chemical
plants and cooperative robotics in smart manufacturing. Specifically, TTW was
essential in enabling fast and reliable feedback control and coordination of
multiple physical systems over low-power wireless multi-hop networks with
closed-loop stability guarantees despite mode changes and mobile nodes
[baumann2019TCPS, mager2019Feedback].111Public demo:
https://youtu.be/AtULmfGkVCE. Mobility experiment:
https://youtu.be/19xPHjnobkY. In these works, we integrated TTW with a mode-
change protocol and analyzed the worst-case end-to-end jitter; thanks to the
predictability of TTW, this jitter can be made negligible ($\leq
50\,\mu\text{s}$) for typical CPS applications, which we empirically validated
(see [baumann2019TCPS, mager2019Feedback] for details).

Difference to prior paper. This paper significantly extends a prior 4-page
publication [jacob2018ttw] by (_i_) incorporating mode changes in the system
model and the formulation of the scheduling problem, (_ii_) providing an
implementation of TTW on physical platforms, and (_iii_) using this
implementation to evaluate TTW and validate our models through real-world
experiments.

##  2 Related Work

TTW is most closely related to prior work on reliable and predictable
solutions for wireless sensor-actuator networks and real-ime distributed
control systems based on fieldbuses.

In the wireless domain, numerous standards and protocols have been proposed
for low-power multi-hop wireless networks, including WirelessHART, ISA100, and
TSCH [watteyne2017Teaching] from industry and several proposals from academia
(_e.g._ , [chipara2011InterferenceAware, saifullah2010RealTime, he2003SPEED]).
Closest to TTW is Blink [zimmerling2017Blink], which also builds on the
concept of synchronous transmissions, in particular the Low-Power Wireless Bus
(LWB) [ferrari2012LWB], to achieve adaptive real-time communication with
guarantees on packet deadlines. While certainly important and useful, the key
difference to TTW is that all these solutions consider only the network
resources. They do not take into account the scheduling of application tasks
on the distributed devices, and can therefore not influence the end-to-end
delays and jitter that ultimately matter from an application’s perspective.
The only prior work that has looked at this end-to-end problem is DRP
[jacob2016DRP]. To provide end-to-end guarantees on packet deadlines, DRP
decouples tasks and messages as much as possible, aiming for efficient support
of sporadic or event-triggered applications. Compared with TTW, which tightly
couples tasks and messages by co-scheduling them, DRP incurs significantly
higher worst-case delays, and is thus not suitable for demanding CPS
applications [akerberg2011Future].

In the wired domain, a lot of work has been done on time-triggered
architectures, such as the Time-Triggered Protocol (TTP) [kopetz1993TTP], the
static-segment of FlexRay [flexray2013ISO], and Time-Triggered Ethernet
[kopetz2005TimeTriggered]. Like TTW, many recent works in this area also use
SMT or MILP based methods to synthesize and/or analyze static (co-)schedules
for those architectures [ashjaei2017Designing, craciunas2016Combined,
steiner2010evaluation, tamas2012Synthesis, zhang2014Task]. The key difference
to TTW, however, is that these approaches assume that a message can be
scheduled at any point in time. While this is a perfectly valid assumption for
a wired system, it is not compatible with the use of communication rounds in a
wireless setting. LABEL:sec:ttw_evaluation_sched shows that using rounds
greatly reduces the energy consumed for communication, but it makes the
schedule synthesis more complex, as detailed in § 4.

##  3 Communication Stack

We introduce TTW, a time-triggered architecture that supports the design and
implementation of dependable wireless CPS. This section presents the design,
implementation, and analytical models of TTW’s communication stack called
TTnet. TTW’s real-time scheduler, described in § 4, uses these models to
synthesize optimized scheduling tables.

###  3.1 TTnet Design

To support a wide spectrum of CPS applications possibly involving control and
coordination of multiple physical systems over large distances, TTW requires a
low-power wireless stack that provides reliable many-to-all communication over
multiple hops. Further, the communication delays must be as short as possible
and tightly bounded to support fast physical systems (_e.g._ , mechanical
systems with dynamics of tens of milliseconds). Finally, network-wide time
synchronization is essential to reduce delays and achieve high performance and
efficiency.

TTnet addresses these requirements by taking inspiration from the Low-Power
Wireless Bus (LWB) [ferrari2012LWB] and improving latency and efficiency by
using a different scheduling strategy. The basic communication scheme is
illustrated on the right side of Figure 1, where distributed nodes are
wirelessly interconnected and communicate using a sequence of Glossy floods
[ferrari2011Glossy]. As shown for when node N1 sends its message, the flood
spreads like a wave through the multi-hop network (note the different colors)
so all nodes in the network can receive the message. During the flood, nodes
that receive the message at the same time also retransmit the message at the
same time. This technique, known as synchronous transmissions, is both fast
(it achieves the theoretical minimum latency for one-to-all flooding) and
extremely reliable [zimmerling2020Survey]. Theoretical and empirical studies
have shown that the few messages losses that do occur due to the vagaries of
wireless communication are largely decorrelated, which greatly simplifies
analytical modeling and control design [karschau2018Renormalization,
zimmerling2013modeling]. During a Glossy flood, the nodes also time-
synchronize themselves with sub-microsecond accuracy [ferrari2011Glossy].
Finally, since the protocol logic is independent of the network topology, it
is highly robust to changes inside the network (_e.g._ , due to mobile or
failing devices) and external interference.

As shown in Figure 1, TTnet performs multiple Glossy floods in consecutive
slots within a round; between two rounds all nodes have their wireless radio
turned off to conserve energy. The duration of the slots and rounds as well as
their associated energy costs can be accurately modeled (§ 3.3). Which nodes
get to send their messages in each slot is determined by TTW’s real-time
scheduler. The scheduler can abstract the entire multi-hop network with all
its complexities and dynamics as a single shared resource with a known
bandwidth, just like a wired fieldbus or a uniprocessor. This is because TTnet
nodes appear to share a common clock and every messages is distributed to all
nodes irrespective of the network topology.

TTnet exploits the fact that the schedules are computed offline to minimize
communication delays. Instead of letting a dedicated host node compute the
schedules between rounds and distribute them at the beginning of each round as
in LWB, the host in TTnet only needs to send the ID of the current round in a
short beacon (see Figure 1). The nodes can then use the ID to look up the
corresponding scheduling table in their local memory. As a result, the rounds
in TTnet are “more compact,” which minimizes delays and improves efficiency.

The beacons also contain all information required to reliably switch between
different operation modes at runtime. In addition to the round ID, each beacon
carries a mode ID and a trigger bit. Modes and rounds have unique IDs with a
known mapping of rounds to modes. By default, a beacon includes the current
mode ID and the trigger bit is set to $0$. A mode change happens in two
phases. First, the mode change is announced by a beacon with the new mode ID.
In a later round, the trigger bit is set to $1$, which triggers the mode
change; the new mode starts at the end of that round. This two-step procedure
lets the nodes prepare for an upcoming mode change; for example, by stopping
the execution of application tasks that are not present in the new mode.
Hence, TTnet provides a generic interface to implement different mode-change
protocols. The mode-change protocol itself is independent of TTnet and can be
freely designed or chosen among existing protocols [chen2018SafeMC].

Sending beacons in every round ensures a safe operation of TTnet: If a node
fails to receive one, it does not participate in the communication until it
receives again a beacon. Thus, it is guaranteed that all participating nodes
know the current round and mode IDs.

###  3.2 TTnet Implementation

We implement TTnet using Baloo [jacob2019Baloo], a design framework for
communication stacks based on synchronous transmissions. Baloo provides a
customizable round structure and allows the user to implement the high-level
logic of a communication stack via a programming interface based on callback
functions. Low-level operations such as time synchronization and radio control
are handled by a middleware layer integrated in Baloo.

Our TTnet implementation uses the static configuration mode of Baloo. The
beacons are implemented using the user-bytes field of Baloo’s control packets
with a payload size of 2 bytes. The implementation runs on any physical
platform supported by Baloo. Because of the need for timing predictability in
TTW, we focus on a platform that is based on the dual-processor platform (DPP)
architecture [beutel2019DPPdemo]. The DPP combines two arbitrary processors
with an interconnect called Bolt [sutton2015Bolt]. Bolt provides predictable
asynchronous message passing between two processors using message queues with
first-in-first-out (FIFO) semantics, one for each direction. This allows to
dedicate each processor to a specific task, execute these tasks in parallel,
and compared to traditional dual- or multi-core platforms the DPP offers
formally verified bounds on the interference between the processors
[sutton2015Bolt]. The specific platform we use is composed of a 32-bit ARM
Cortex-M4 based MSP432P401R running at 48 MHz and a 16-bit CC430F5147 running
at 13 MHz. The former is dedicated to the execution of application tasks
(_e.g._ , sensing, actuation, and control), while the latter is dedicated to
TTnet using a low-power wireless radio operating at 250 kbps in the 868 MHz
frequency band. Our implementation is open source and freely available; refer
to [repoTTW] for details.

###  3.3 TTnet Model

The real-time scheduler in TTW requires timing and energy models of TTnet’s
operation to synthesize the scheduling tables. These models must be tight
bounds to avoid delays and energy costs.

Figure 2: Detailed timings during a slot in TTnet. _At the slot level, the
colored boxes identify phases where the radio is on. In the idle phase, the
radio is off, but the duration depends on a node’s distance to the initiator
of the Glossy flood. To estimate the energy savings of rounds, we make the
pessimistic assumption that the radio is on for $T_{\mathit{flood}}$, as
specified in Equation 7. _

Let $T_{r}$ be the length of a TTnet round. A round consists of a beacon slot
plus up to $B_{\mathit{max}}$ regular slots, in which Glossy floods are
executed (see Figure 1). $T_{r}(L,B)$ denotes the length of a round with $B$
regular slots having the same payload size $L$. The structure of a slot is
illustrated in Figure 2. Accordingly, the length of a slot $T_{\mathit{slot}}$
can be decomposed as follows

$T_{\mathit{slot}}=T_{\mathit{wake-
up}}+T_{\mathit{start}}+T_{\mathit{flood}}+T_{\mathit{gap}}$ (1)

First, the nodes wake up ($T_{\mathit{wake-up}}$) and switch on their radio
($T_{\mathit{start}}$). Then, the Glossy flood executes ($T_{\mathit{flood}}$)
followed by a small gap time ($T_{\mathit{gap}}$) in which the nodes can
process the received packet. As explained in [zimmerling2015dissertation], the
total length of a flood $T_{\mathit{flood}}$ can be expressed by

$\displaystyle T_{\mathit{flood}}=(H+2N-1)*T_{\mathit{hop}}$ (2)

where $H$ is the network diameter and $N$ is the maximum number of times a
node transmits during a Glossy flood. Let $T_{\mathit{hop}}$ be the time
needed for one protocol step, that is, the duration of one (synchronous)
transmission during a flood. This quantity can be decomposed as

$\displaystyle
T_{\mathit{hop}}=T_{d}+T_{\mathit{cal}}+T_{\mathit{header}}+T_{\mathit{payload}}$
(3)

where $T_{d}$ is an initial radio delay, $T_{\mathit{cal}}$ is the time needed
to calibrate the radio clock (taking time equal to the transmission of
$L_{\mathit{cal}}$ bytes), and $T_{\mathit{header}}$ and
$T_{\mathit{payload}}$ are the times needed to transmit the packet header
consisting of $L_{\mathit{header}}$ bytes and the message payload consisting
of $L$ bytes. Using a radio with a transmit bitrate of $R_{\mathit{bit}}$, the
transmission of $L$ bytes takes

$\displaystyle T(L)=8L/R_{\mathit{bit}}$ (4)

We divide the length of a slot $T_{\mathit{slot}}$ into $T^{\mathit{on}}$ and
$T^{\mathit{off}}$, the times spent with the radio on and off, respectively.
To this end, we make the conservative assumption that the radio stays on for
the entirety of $T_{\mathit{flood}}$, as illustrated in Figure 2 and explained
in the caption.

$\displaystyle T_{\mathit{slot}}(L)$
$\displaystyle\,=\,T^{\mathit{off}}+T^{\mathit{on}}(L)$ (5) $\displaystyle
T^{\mathit{on}}(L)$
$\displaystyle\,=\,T_{\mathit{start}}+(H+2N-1)*\left(T_{d}+8(L_{\mathit{cal}}+L_{\mathit{header}}+L)/R_{\mathit{bit}}\right)$
(6) $\displaystyle T^{\mathit{off}}$ $\displaystyle\,=\,T_{\mathit{wake-
up}}+T_{\mathit{gap}}$ (7)

With this, the length of a round with $B$ regular slots and a common payload
size $L$ is

$T_{r}(L,B)=T_{\mathit{slot}}(L_{\mathit{beacon}})+B*T_{\mathit{slot}}(L)+T_{\mathit{preprocess}}$
(8)

where $L_{\mathit{beacon}}$ is the payload size of a beacon and
$T_{\mathit{preprocess}}$ is the time needed by our TTnet implementation to
prepare for an upcoming round (_e.g._ , retrieve messages from send queue).

In addition to the timings of a TTnet round, we derive a model for the
relative energy savings obtained by grouping multiple slots into the same
round. As discussed in § 3.1, sending beacons is necessary to ensure a safe
protocol operation. Without rounds, each regular message must still be
preceded by a beacon to provide the same guarantee. In this case, the
transmission time $T_{\mathit{wo/r}}$ for $B$ regular messages of size $L$ is
given by

$\displaystyle
T_{\mathit{wo/r}}(L,B)=B*(\,T_{\mathit{slot}}(L_{\mathit{beacon}})+T_{\mathit{slot}}(L)\,)$
(9)

The relative energy savings obtained by a round-based design thus amount to

$E=(T_{\mathit{wo/r}}^{\mathit{on}}-T_{r}^{\mathit{on}})/T_{\mathit{wo/r}}^{\mathit{on}}$
(10)

with
$T_{\mathit{wo/r}}^{\mathit{on}}=B*(\,T^{\mathit{on}}(L_{\mathit{beacon}})+T^{\mathit{on}}(L)\,)$
and
$T_{r}^{\mathit{on}}=T^{\mathit{on}}(L_{\mathit{beacon}})+B*T^{\mathit{on}}(L)$.

Figure 3: Example values of round length computed using the TTnet model for a
payload size of 16 bytes and $N=2$ transmissions during a Glossy flood. _Fewer
slots lead to shorter rounds (_e.g._ , 52 ms for $B=5$ slots across a 4-hop
network), which ultimately allows for shorter end-to-end delays. _

Using these expressions and the parameters measured for or used by our TTnet
implementation (detailed in [repoTTW]), we can determine the round length
$T_{r}$ and the energy savings $E$ for different number of slots per round
$B$, message payload sizes $L$, network diameters $H$, and number of
transmissions during a Glossy flood ($N$). For $L=16$ byte and $N=2$, Figure 3
plots the resulting round length $T_{r}$ for different network diameters and
slots per round. We can see, for example, that it takes less than 100 ms to
send 10 messages in a 4-hop network. Real-world experiments using 27
distributed wireless nodes on a public testbed demonstrate that these models
are very accurate (LABEL:subsec:ttnet_eval).

##  4 Real-Time Scheduler

Equipped with a timing-predictable implementation of the TTnet communication
stack and a corresponding model that provides accurate upper bounds, we now
turn to the second main component of TTW: the real-time scheduler. This
section first defines the system model and scheduling problem, then describes
the single-mode and multi-mode schedule synthesis.

###  4.1 System Model

Before we can formulate and solve the scheduling problem we face in TTW, we
provide a formal system model of all relevant hardware and software components
and their interactions.

Platform. Each node in the system is a _platform_ that executes tasks and
exchanges messages using TTnet. All tasks have a known worst-case execution
time (WCET) on that platform. Targeting state-of-the-art wireless CPS
platforms with two processors (_e.g._ , LPC541XX, VF3xxR, DPP
[beutel2019DPPdemo]), each node can simultaneously execute tasks and exchange
messages.

Figure 4: An example application and its precedence graph $\mathbb{P}$. _The
application execution starts with sensing tasks $\tau_{1}$ and $\tau_{2}$.
After messages $m_{1}$ and $m_{2}$ with the sensor readings are received by
the controller, actuation values are computed ($\tau_{3}$), sent to the
actuators ($m_{3}$), and applied ($\tau_{5}$ and $\tau_{6}$). _

Applications. Let $\mathcal{A}$ denote the set of distributed _applications_
in the system. An application is composed of _tasks_ and _messages_ , each
with a unique task or message $\mathit{id}$, that are coupled by precedence
constraints as described by a directed acyclic graph, where vertices and edges
represent tasks and messages, respectively. We denote by
$\mathit{a}$.$\mathbb{P}$ the _precedence graph_ of application $\mathit{a}$
(see Figure 4 for an example). Each application executes at a periodic
interval $\mathit{a}.p$ called the _period_. An application execution is
completed when all tasks in $\mathbb{P}$ have been executed. All tasks and
messages in $\mathit{a}$.$\mathbb{P}$ share the same period $\mathit{a}.p$. If
the same task belongs to applications with different periods, it can be
equivalently modeled as two different tasks. Applications are subject to real-
time constraints: an application _relative deadline_ , denoted by
$\mathit{a}.d$, represents the maximum tolerable _end-to-end delay_ to
complete the application execution. The deadline can be arbitrary, without a
specific relation to the period $\mathit{a}.p$. Some applications may require
to keep the same schedule (_e.g._ , the same task offsets) when switching
between different operation modes, for example, to guarantee the stability of
control loops under arbitrary mode switches [baumann2019TCPS]. We call these
_persistent applications_ and denote them by
$\mathcal{A}_{P}\subset\mathcal{A}$.

Tasks. We denote by $\mathcal{T}$ the set of all _tasks_ in the system. A node
executes at most one task at any point in time. Since interactions with the
physical world like sensing and actuation should not be interrupted, we
consider non-preemptive task scheduling. Each task $\tau$ is mapped to a given
node $\tau.map$ on which it executes with WCET $\tau.e$. The _task offset_
$\tau.o$ represents the start of the task execution relative to the beginning
of the application execution. A task can have an arbitrary number of preceding
messages, which must all be received before the task can start to execute.
$\tau.prec$ denotes the set of preceding message $\mathit{id}$s. Within one
application, each task is unique; however, the same task may belong to
multiple applications (_e.g._ , the same sensing task may source different
feedback loops). If so, we consider that these applications have the same
period.

Messages. Let $\mathcal{M}$ be the set of all _messages_. Every message $m$
has at least one preceding task, that is, a task that needs to finish before
the message can be transmitted. The set of preceding task $\mathit{id}$s is
denoted by $m.prec$. The _message offset_ $m.o$ relative to the beginning of
the application execution represents the earliest time message $m$ can be
allocated to a TTnet round for transmission (_i.e._ , after all preceding
tasks are completed). The _message deadline_ $m.d$ relative to the message
offset represents the latest time the message transmission must be completed
(_i.e._ , the earliest offset of subsequent tasks). The payload of all
messages is upper-bounded by $L_{\mathit{max}}$. Messages are not necessarily
unique: multiple edges of $\mathit{a}$.$\mathbb{P}$ can be labeled with the
same message $m$, which captures the case of multicast or broadcast
transmissions (see Figure 4). If a message belongs to multiple applications,
we consider that these applications have the same period.

Modes. We denote with $\mathcal{O}$ the set of operation _modes_. These modes
represent mutually exclusive phases in the system execution (_e.g._ , init,
normal, and failure modes), each having its own schedule. A mode has a unique
_priority_ $\mathit{M}$.$\mathit{prio}$. We write $\mathit{a}\in\mathit{M}$ to
denote that application $\mathit{a}$ executes in mode $\mathit{M}$. When
unambiguous, we use $\mathit{M}$ to denote the set of all applications that
execute in mode $\mathit{M}$. The _hyperperiod_ $\mathit{LCM}$ of mode
$\mathit{M}$ is the least common multiple of the periods of all applications
in $\mathit{M}$. Possible transitions between modes at runtime are specified
by the _mode graph_ $\mathbb{M}$ (see Figure 6). The mode graph is
undirectional, that is, a transition from $\mathit{M_{i}}$ to $\mathit{M_{j}}$
implies that it is also possible to switch from $\mathit{M_{j}}$ to
$\mathit{M_{i}}$.

Network and rounds. We denote with $\mathcal{N}$ the set of all _nodes_ in the
network. The following four network parameters must be specified by the user
of the TTW architecture:

  * •

$L$ the payload size of regular messages, in bytes;

  * •

$B_{\mathit{max}}$ the maximum number of slots in a TTnet round;

  * •

$N$ the maximum number of transmissions of a node during a Glossy flood;

  * •

$H$ the estimated diameter of the network, in number of hops.

As explained in § 3, communication over the network is scheduled in _rounds_
$r$. The schedule of mode $\mathit{M}$ has $R_{\mathit{M}}$ rounds. We
consider TTnet rounds as atomic, that is, they cannot be interrupted. Thus,
the ordering of messages in a round is irrelevant.

Round $r$ contains $B_{r}$ slots (at most $B_{\mathit{max}}$), each of which
is allocated to a unique message $m$. The _allocation vector_ $r.[B_{r}]$
contains the $\mathit{id}$s of the messages that are allocated to the slots in
round $r$, where $r.B_{s}$ denotes the allocation of the $s$-th slot. The
_starting time_ $r.t$ is the start of the round relative to the beginning of
the mode’s hyperperiod. Using the models from § 3.3, the length of a round and
its energy cost can be determined.

Table 1: Inputs and outputs of the scheduling problem we solve in TTW Inputs |  $\mathcal{N}$ |  Set of nodes in the system
---|---|---
$\mathcal{A}$, $\mathcal{A}_{P}$ |  Set of applications and persistent applications
(including periods, deadlines, and precedence graphs)
$\mathcal{O}$ |  Set of operation modes (including mode priorities)
$\mathbb{M}$ |  Mode graph
$\tau.p,\,m.p$ |  Task and message periods, inherited from the application
$\tau.\mathit{map}$ |  Mappings of tasks to nodes
$\tau.e$ |  Task worst-case execution time (WCET) given $\tau.\mathit{map}$
$B_{\mathit{max}}$ |  Maximum number of slots per round
$L_{\mathit{max}}$ |  Maximum message payload size
$H$ |  Network diameter (in number of hops)
|  $N$ |  Number of transmissions in a Glossy flood [ferrari2011Glossy]
Outputs |  $\tau.o$ |  Task offsets
$m.o,\,m.d$ |  Message offsets and deadlines
$r.t,\,r.[B_{\mathit{max}}]$ |  Round starting times and allocation vectors

###  4.2 Scheduling Problem

Based on our system model, we are now in the position to formally state the
scheduling problem we have to solve in TTW. Given all modes, applications,
task-to-node mappings, and WCETs, for each mode $\mathit{M}$ the remaining
variables define the _mode schedule_ $Sched(\mathit{M})$

$\displaystyle
Sched(\mathit{M})\,=\,\left\\{\begin{tabular}[]{c|l}$\tau.o,\,m.o,\,m.d$&$\forall\;\mathit{a}\in\mathit{M},\;(\tau,m)\in\mathit{a}.\mathbb{P}$\\\
$r_{k}.t,\,r_{k}.[B_{\mathit{max}}]$&$\forall\;k\in[1,\,R_{\mathit{M}}]$\end{tabular}\right\\}$

Table 1 lists all inputs and outputs of the scheduling problem in TTW. A
schedule for mode $\mathit{M}$ is said to be _valid_ if all applications
executing in mode $\mathit{M}$ meet their end-to-end deadlines. The scheduling
problem to solve thus consists of finding valid schedules for all modes
$\mathit{M}\in\mathcal{O}$ such that the following two objectives are met:

(O1)

The number of communication rounds is minimized, which results in minimizing
the energy required for wireless communication.

(O2)

All persistent applications $\mathcal{A}_{P}\subset\mathcal{A}$ seamlessly
switch between modes, that is, their schedules remain the same across all
possible mode changes.

###  4.3 Single-Mode Schedule Synthesis

TTW statically synthesizes the schedule of all tasks, messages, and
communication rounds by solving a MILP. We first look at the single-mode case,
effectively showing how to achieve objective (O1), whereas § 4.4 considers the
multi-mode case and thus objective (O2).

The schedule of a mode $\mathit{M}$ is computed for one hyperperiod, after
which it repeats itself. To minimize the number of rounds used while taming
computational complexity, we solve the problem sequentially as described in
Algorithm 1. Each MILP formulation considers a fixed number of rounds
$R_{\mathit{M}}$ to be scheduled, starting with $R_{\mathit{M}}=0$. The number
of rounds is incremented until a feasible solution is found or the maximum
number of rounds $R_{max}$ that fit into one hyperperiod is reached. So, even
without an explicit objective function, Algorithm 1 guarantees by construction
that if the problem is feasible, the synthesized schedule uses the minimum
number of rounds, thereby minimizing the communication energy costs.

mode $\mathit{M}$, $\mathit{a}\in\mathit{M}$, $\tau.\mathit{map}$, $\tau.e$,
$B_{\mathit{max}}$, $T_{o}$

$Sched(M)$

$LCM$ = hyperperiod($\mathit{M}$)

$R_{max}=floor(LCM/T_{o})$

$R_{\mathit{M}}=0$

while $R_{\mathit{M}}\leq R_{max}$ do

formulate the MILP for mode $\mathit{M}$ using $R_{\mathit{M}}$ rounds

( $Sched(M)$ , feasible ) = solve(MILP)

if feasible then return $Sched(M)$

end if

$R_{\mathit{M}}=R_{\mathit{M}}+1$

end while

return ’Problem infeasible’

Algorithm 1 Pseudo-code of the single-mode schedule synthesis

Each MILP formulation contains a set of classical scheduling constraints such
as: precedence constraints between tasks and messages must be respected, the
applications’ end-to-end deadlines must be satisfied, nodes process at most
one task simultaneously, communication rounds must not overlap, and rounds
must not be allocated more then $B_{\mathit{max}}$ messages. These constraints
can be easily formulated based on our system model. However, we must also
guarantee that the allocation of messages to rounds is valid. Specifically,

(C1)

messages must be served in rounds that start after their release time;

(C2)

messages must be served in rounds that finish before their deadline.

In other words, we must integrate the bin-packing problem that arises when
allocating messages to rounds within the MILP formulation. This is a non-
trivial challenge and a major difference compared with the existing approaches
for wired architectures (_e.g._ , [craciunas2016Combined]).

To address this challenge, we first formulate the constraints (C1) and (C2)
using _arrival_ , _demand_ , and _service_ functions—denoted by $\mathit{af}$,
$\mathit{df}$, and $\mathit{sf}$—inspired by network calculus
[leboudec2001Network] (see Figure 5 for an illustration). These three
functions count the number of message instances that are released, have passed
deadlines, and have been served since the beginning of the hyperperiod. It
must hold that

$\displaystyle\forall\,m_{i}\in\mathcal{M},\;\forall\,t,$
$\displaystyle\mathit{df}_{i}(t)\leq\mathit{sf}_{i}(t)\leq\mathit{af}_{i}(t)$
(11) with
$\displaystyle\mathit{af}_{i}:\;t\;\longmapsto\;\left\lfloor{\frac{t-m_{i}.o}{m_{i}.p}}\right\rfloor+1$
(12) and
$\displaystyle\mathit{df}_{i}:\;t\;\longmapsto\;\left\lceil{\frac{t-m_{i}.o-m_{i}.d}{m_{i}.p}}\right\rceil$
(13)

However, as the service function $\mathit{sf}$ stays constant between the
rounds, we can formulate constraints (C1) and (C2) as follows:
$\forall\,m_{i}\in\mathcal{M},\;\forall\,j\in[1..R_{\mathit{M}}],$

(C1) $\displaystyle\mathit{sf}_{i}(r_{j}.t+T_{r})\,$
$\displaystyle\leq\,\mathit{af}_{i}(r_{j}.t)$ (14) (C2)
$\displaystyle\mathit{sf}_{i}(r_{j}.t)\,$
$\displaystyle\geq\,\mathit{df}_{i}(r_{j}.t+T_{r})$ (15)

Figure 5: Example showing arrival ($\mathit{af}$), demand ($\mathit{df}$), and
service ($\mathit{sf}$) functions for message $m_{i}$. _The lower part of the
chart shows the five round, $r_{1}$ to $r_{5}$, that are scheduled within the
hyperperiod. Message $m_{i}$ is allocated a slot in the colored rounds, that
is, in rounds $r_{1}$, $r_{2}$, and $r_{4}$. Allocating $m_{i}$ to $r_{3}$
instead of $r_{2}$ would be invalid because $r_{3}$ does not finish before
$m_{i}$’s deadline, thus violating constraint (C2). By contrast, allocating
$m_{i}$ to $r_{5}$ instead of $r_{1}$ would be valid and result in
$r_{0}.B_{i}=0$._

The arrival and demand functions are step functions, which cannot be directly
used in a MILP formulation. However, we observe that

$\displaystyle\forall\;k\in\mathbb{N},\quad$
$\displaystyle\mathit{af}_{i}(t)=k\quad\Leftrightarrow\quad
0\,\leq\,t-m_{i}.o-(k-1)*m_{i}.p\,<\,m_{i}.p$ (16) and
$\displaystyle\mathit{df}_{i}(t)=k\quad\Leftrightarrow\quad
0\,<\,t-m_{i}.o-m_{i}.d-(k-1)*m_{i}.p\,\leq\,m_{i}.p$ (17)

This allows us to introduce, for each message $m_{i}\in\mathcal{M}$ and each
round $r_{j}$, $j\in[1..R_{\mathit{M}}]$, two integer variables $k^{a}_{ij}$
and $k^{d}_{ij}$ that we constrain to take the values of $\mathit{af}$ and
$\mathit{df}$ at the time points of interest, namely $r_{j}.t$ and
$r_{j}.t+T_{r_{j}}$. More formally, we can write

$\displaystyle 0\,\leq\,r_{j}.t$ $\displaystyle-
m_{i}.o-(k^{a}_{ij}-1)*m_{i}.p\,<\,m_{i}.p$ (18) $\displaystyle 0\,<\,r_{j}.t$
$\displaystyle+T_{r_{j}}-m_{i}.o-m_{i}.d-(k^{d}_{ij}-1)*m_{i}.p\,\leq\,m_{i}.p$
(19) Thus,
$\displaystyle\eqref{eq:ka}\quad\Leftrightarrow\quad\mathit{af}_{i}(r_{j}.t)=k^{a}_{ij}$
$\displaystyle\eqref{eq:kd}\quad\Leftrightarrow\quad\mathit{df}_{i}(r_{j}.t+T_{r_{j}})=k^{d}_{ij}$

Finally, we must express the service function $\mathit{sf}$, which counts the
number of message instances served by _the end_ of each round. Recalling that
$r_{k}.B_{s}$ denotes the $\mathit{id}$ of the message that is allocated to
the $s$-th slot of round $r_{k}$, we have that for any time
$t\in\;[\;r_{j}.t+T_{r_{j}}\,;\,r_{j+1}.t+T_{r_{j}}\;[$ the number of
instances of message $m_{i}$ served is

$\displaystyle\sum_{\begin{subarray}{c}k=1\end{subarray}}^{j}\;\;\sum_{\begin{subarray}{c}s=1\end{subarray}}^{B}\;r_{k}.B_{s}\quad
s.t.\quad B_{s}=i$

As visible in Figure 5, it can happen that $m.o+m.d>m.p$, resulting in
$\mathit{df}(0)=-1$ according to Equation 13. This situation arises when a
message is released at the end of a hyperperiod and thus has its deadline in
the _next_ hyperperiod. To account for this, we introduce for each message
$m_{i}$ a variable $r_{0}.B_{i}$ that is set to the number of such “leftover”
message instances at $t=0$. With this, for each $m_{i}\in\mathcal{M}$ and
$t\in\;[\;r_{j}.t+T_{r_{j}}\,;\,r_{j+1}.t+T_{r_{j}}\;[$,

$\displaystyle\mathit{sf}_{i}:\;t\;$
$\displaystyle\longmapsto\;\sum_{\begin{subarray}{c}k=1\\\\[2.0pt]
s.t.\;r_{k}.t+T_{r_{k}}\,<\,t\end{subarray}}^{j}\quad\sum_{\begin{subarray}{c}s=1\\\\[2.0pt]
s.t.\;B_{s}=i\end{subarray}}^{B}r_{k}.B_{s}-r_{0}.B_{i}$ (20)

Based on the above reasoning, we can express constraints (C1) and (C2) in the
MILP formulation using Equations 18 and 19 and the following two equations

$\displaystyle\eqref{eq:af_const}\quad\Leftrightarrow\quad\sum_{k=1}^{j}\sum_{\begin{subarray}{c}s=1\\\\[2.0pt]
s.t.\;B_{s}=i\end{subarray}}^{B}\;r_{k}.B_{s}-r_{0}.B_{i}\;\leq\;k^{a}_{ij}$
(21)
$\displaystyle\eqref{eq:df_const}\quad\Leftrightarrow\quad\sum_{k=1}^{j-1}\sum_{\begin{subarray}{c}s=1\\\\[2.0pt]
s.t.\;B_{s}=i\end{subarray}}^{B}\;r_{k}.B_{s}-r_{0}.B_{i}\;\geq\;k^{d}_{ij}$
(22)

###  4.4 Multi-Mode Schedule Synthesis

The multi-mode schedule synthesis is a multi-objective problem: As stated in §
4.2, the number of communication rounds in each mode should be minimized (O1),
while the schedule of all persistent applications should remain unchanged
across mode changes (O2). Objective (O2) induces dependencies between the
different modes, which cannot be handled by solving a set of independent
single-mode schedule synthesis problems.

A straightforward approach would be to synthesize the schedules of all modes
at once based on a single MILP formulation. This approach, however, has two
caveats. First, the resulting schedule synthesis problem is NP-hard
[jeffay1991nonpreemptive] and thus scales poorly as the number of modes
increases, which becomes a bottleneck for realistic CPS applications requiring
a high degree of system adaptability. Second, a global objective function must
be defined, such as minimizing the total number of rounds across all modes,
which still gives no guarantee that the corresponding communication energy
costs are effectively minimized: at runtime, if the system remains almost
always in a certain mode, it may be better to minimize the number of rounds in
that particular mode even if this implies a larger number of rounds overall.

Applications specification; modes specification; network parameters; system
parameters

{ $Sched(\mathit{M_{i}})$ for $\mathit{M_{i}}$ $\in$ $\mathcal{O}$ }

inheritance_constraints = $\emptyset$

for all $\mathit{M_{i}}$ $\in$ $\mathcal{O}$ in order of decreasing mode
priority $\mathit{M_{i}}$.$\mathit{prio}$ do

add inheritance_constraints to mode $\mathit{M_{i}}$

( $Sched(\mathit{M_{i}})$ , feasible ) =
single_mode_synthesis($\mathit{M_{i}}$)

if feasible then

add $Sched(\mathit{M_{i}})$ to inheritance_constraints

else

return ’Problem infeasible’

end if

end for

return { $Sched(\mathit{M_{i}})$ for $\mathit{M_{i}}$ $\in$ $\mathcal{O}$ }

Algorithm 2 Pseudo-code of the multi-mode schedule synthesis

To address these caveats, we solve the multi-mode schedule synthesis problem
sequentially using heuristics, as commonly done in related approaches
[joshi2017MultiDomain, pozo2015SMTbased, steiner2010evaluation]. Algorithm 2
summarizes our approach. The modes are scheduled based on their priority
$\mathit{M}$.$\mathit{prio}$. The mode with the highest priority (_i.e._ ,
$\mathit{M}.\mathit{prio}=1$) is scheduled first according to the single-mode
synthesis outlined in Algorithm 1. Then, the mode with the second-highest
priority (_i.e._ , $\mathit{M}.\mathit{prio}=2$) is considered; however, its
specification is first extended with _inheritance constraints_ to guarantee
that all persistent applications can seamlessly switch between all modes
considered so far. The process repeats until all modes are scheduled.

This sequential approach addresses the scalability of the multi-mode problem
and provides a reasonable heuristic for minimizing the number of executed
rounds and thus the communication energy costs. Indeed, these costs ultimately
depend on how much time the system spends in each mode. It is reasonable to
assume that an application domain expert knows in which modes the system
likely operates most of the time. These modes are assigned a higher priority
and therefore scheduled first by Algorithm 2. A mode with a lower priority is
subject to more inheritance constraints, so it may schedule more than the
minimal number of rounds to achieve (O2). This may lead to a sub-optimal
energy cost of lower-priority modes, which is nevertheless acceptable as the
system likely spends less time in these modes.

In the following, we address the problem of deriving the set of inheritance
constraints that are _necessary_ and _sufficient_ to guarantee objective (O2).
We first formalize the continuity constraints necessary to satisfy (O2) and
characterize how these constraints may lead to conflicts between the mode
schedules. Then we derive the minimally restrictive inheritance constraints
that are necessary and sufficient to prevent such conflicts while satisfying
(O2).

######  Example 4.1.

Let us consider the mode graph in Figure 6 and assume that all applications
are persistent. The modes are scheduled sequentially, starting with the
highest-priority mode $\mathit{M_{1}}$, which is freely scheduled. When mode
$\mathit{M_{2}}$ is scheduled, the schedule for application $\mathit{a_{2}}$
is inherited from mode $\mathit{M_{1}}$ to guarantee (O2) and the schedules
for applications $\mathit{a_{3}}$ and $\mathit{a_{4}}$ are synthesized without
constraints. In $\mathit{M_{3}}$, the specified applications $\mathit{a_{5}}$
and $\mathit{a_{6}}$ are new and can be scheduled without constraints. Then,
in mode $\mathit{M_{4}}$, the specified applications $\mathit{a_{1}}$ and
$\mathit{a_{5}}$ have been previously scheduled and thus must be inherited
(O2). However, as mode $\mathit{M_{3}}$ has been scheduled without constraint,
the schedule synthesized for $\mathit{a_{5}}$ may be incompatible with that of
$\mathit{a_{1}}$ from mode $\mathit{M_{1}}$. This leads to a conflict in
$\mathit{M_{4}}$ and thus renders the sequential synthesis of the multi-mode
problem infeasible, as illustrated in Figure 7.

Figure 6: Mode graph $\mathbb{M}$ for Examples 4.1 and 4.7. _Five modes are
depictd by circles and possible transitions between them by edges. Numbers
inside each circle indicate which of the six applications, $\mathit{a_{1}}$ to
$\mathit{a_{6}}$, execute in the corresponding mode, for example,
$M_{1}=\\{\mathit{a_{1}},\mathit{a_{2}}\\}$. Mode $\mathit{M_{i}}$ has
priority $i$._

(a) $\mathit{a_{5}}$ is scheduled in mode $\mathit{M_{3}}$ without considering
the previously computed schedule of $\mathit{a_{1}}$, which leads to a
conflict in mode $\mathit{M_{4}}$.

(b) $\mathit{a_{5}}$ is scheduled in mode $\mathit{M_{3}}$ considering the
schedule of $\mathit{a_{1}}$ as reserved. A compatible schedule for
$\mathit{a_{5}}$ is found, preventing a conflict in $\mathit{M_{4}}$.

Figure 7: Representations of the schedule of applications $\mathit{a_{1}}$ and
$\mathit{a_{5}}$ from Example 4.1. For sake of illustration, we consider that
all tasks are mapped to the same node. $\mathit{a_{1}}$ and $\mathit{a_{5}}$
are scheduled in modes $\mathit{M_{1}}$ and $\mathit{M_{3}}$, and must both be
inherited in mode $\mathit{M_{4}}$. In Figure 7(a), overlapping task schedules
result in a conflict, while in Figure 7(b) this was prevented by reserving
$\mathit{a_{1}}$’s schedule.

####  4.4.1 Continuity Constraints

The schedule synthesis returns the application schedules (_i.e._ , task and
message offsets, and message deadlines) and the round schedules (_i.e._ ,
starting times and allocation vectors). We represent an application schedule
through a scheduling function $s$ as defined below.

######  Definition 4.2 (Scheduling function).

The scheduling function $s$, defined over the set of applications
$\mathcal{A}$, returns for a given application $\mathit{a}$ all parameters
characterizing the schedule of $\mathit{a}$. The schedule of application
$\mathit{a}$ is denoted by $s(\mathit{a})$. $s_{\mathit{M}}(\mathit{a})$
denotes the schedule of application $\mathit{a}$ in mode $\mathit{M}$. The
scheduling function is extended to sets of applications as follows

$\forall\,S\subset\mathcal{A}\;,\quad s(S)=\bigcup_{\mathit{a}\in
S}s(\mathit{a})$

All persistent applications $\mathit{a}\in\mathcal{A}_{P}$ must keep the same
schedule across mode changes, which leads us to the definition of continuity
constraints.

######  Definition 4.3 (Continuity constraint).

The set of all continuity constraints is given by

$\forall\,\mathit{a}\in\mathcal{A}_{P},\,\forall\,(\mathit{M_{i}},\mathit{M_{j}})\in\mathcal{O}^{2},\,\mathit{a}\in\mathit{M_{i}}\,\wedge\,\mathit{a}\in\mathit{M_{j}}\
\wedge\,\mathbb{M}(\mathit{M_{i}},\mathit{M_{j}})=1\;\Rightarrow\;s_{\mathit{M_{i}}}(\mathit{a})=s_{\mathit{M_{j}}}(\mathit{a})$
(23)

######  Definition 4.4 (Schedule domains).

The schedule domains of an application are the possibly multiple subsets of
modes in which the application schedule must remain the same.

######  Corollary 4.5.

Two modes $\mathit{M_{i}}$ and $\mathit{M_{j}}$ belong to the same schedule
domain of an application $\mathit{a}\in\mathcal{A}_{P}$ if and only if (i)
$\mathit{a}$ is scheduled in both modes, that is,
$\mathit{a}\in\mathit{M_{i}}\;\wedge\;\mathit{a}\in\mathit{M_{j}}$, and (ii)
there is a possible transition between the two modes, that is,
$\mathbb{M}(\mathit{M_{i}},\mathit{M_{j}})=1$.

######  Proof 4.6.

Multiple modes belong to the same schedule domain because of a continuity
constraint. The formalization of the schedule domains directly follows from
Definition 4.3 ∎

The schedule domains of an application can be extracted from the mode graph
$\mathbb{M}$. One approach entails considering the sub-graph $\mathbb{G}_{A}$
of $\mathbb{M}$ that contains only the modes in which application $\mathit{a}$
is specified—every connected component of $\mathbb{G}_{A}$ is a schedule
domain of $\mathit{a}$.

Any non-persistent application that is present in multiple modes can be
replaced by a distinct application with the same parameters in the respective
modes. Similarly, any persistent application with multiple schedule domains
can be replicated into distinct applications having one scheduling domain each
(illustrated by Example 4.7). This leads us to consider in the following that
all applications are persistent and have a single schedule domain.

######  Example 4.7.

Consider again the mode graph in Figure 6. Application $\mathit{a_{6}}$ has
two schedule domains, $\\{\mathit{M_{3}}\\}$ and $\\{\mathit{M_{5}}\\}$. This
can also be modeled by two distinct applications $\mathit{a_{6.3}}$ and
$\mathit{a_{6.6}}$ executing in $\mathit{M_{3}}$ and $\mathit{M_{6}}$.
Application $\mathit{a_{1}}$ has only one schedule domain,
$\\{\mathit{M_{1}},\mathit{M_{4}}\\}$. If $\mathit{a_{1}}$ was not persistent,
the continuity constraint would not apply and $\mathit{a_{1}}$ could be
equivalently modeled by two distinct applications $\mathit{a_{1.1}}$ and
$\mathit{a_{1.4}}$ executing in $\mathit{M_{1}}$ and $\mathit{M_{4}}$.

Continuity constraints can cause conflicts leading to the failure of the
multi-mode synthesis although a solution may exist. In particular, if a given
mode $\mathit{M}$ belongs to the schedule domains of two different
applications, which have been independently scheduled in higher-priority
modes, there is a risk of conflict as the inherited schedules may be
incompatible. We now formalize the notions of (virtual) legacy applications
and conflicting modes. $\overline{X}=\mathcal{A}\setminus X$ denotes the
complement of $X$. For each mode $\mathit{M_{i}}$, we define four application
sets.

  * •

Known applications are the applications previously scheduled in higher-
priority modes. The set of known applications of mode $\mathit{M_{i}}$ is
denoted by $\mathit{K_{i}}=\cup_{j=1}^{i-1}\;\mathit{M_{j}}$.

  * •

Free applications are the newly scheduled applications in mode
$\mathit{M_{i}}$, that is, no higher-priority mode belongs to the schedule
domain of these applications. The set of free applications of mode
$\mathit{M_{i}}$ is denoted by
$\mathit{F_{i}}=\mathit{M_{i}}\;\cap\;(\mathcal{A}\setminus\mathit{K_{i}})=\mathit{M_{i}}\;\cap\;\overline{\mathit{K_{i}}}$.

  * •

Legacy applications are the applications previously scheduled in higher-
priority modes that must be scheduled in mode $\mathit{M_{i}}$. Since
applications have a single schedule domain, $\mathit{M_{i}}$ necessarily
belongs to the same schedule domain as these higher-priority modes and the
legacy application schedules must be inherited. The set of legacy applications
of mode $\mathit{M_{i}}$ is denoted by
$\mathit{L_{i}}=\mathit{M_{i}}\;\cap\;{\mathit{K_{i}}}$.

  * •

Virtual legacy applications are the applications previously scheduled in
higher-priority modes that are not scheduled in mode $\mathit{M_{i}}$. The set
of virtual legacy applications of mode $\mathit{M_{i}}$ is denoted by
$\mathit{VL_{i}}=(\mathcal{A}\setminus\mathit{M_{i}})\;\cap\;{\mathit{K_{i}}}=\overline{\mathit{M_{i}}}\;\cap\;{\mathit{K_{i}}}$.
The virtual legacy applications of $\mathit{M_{i}}$ are not executed in
$\mathit{M_{i}}$; they simply have been scheduled in higher-priority modes. As
illustrated in Example 4.1, it may be necessary to reserve the space for some
of these virtual legacy applications to avoid future inheritance conflicts.

The schedules of two applications $\mathit{A}$ and $\mathit{B}$ are said to be
in conflict if two tasks, one from $\mathit{A}$ and one from $\mathit{B}$, are
mapped to the same node and are scheduled in overlapping time intervals. We
denote by $s(\mathit{A})\cap s(\mathit{B})\not=\emptyset$ the property that
$\mathit{A}$ and $\mathit{B}$ are in conflict.

######  Definition 4.8 (Conflict-free).

A set of applications $S$ is said to be conflict-free when there is no
conflict between the schedules of the applications in $S$. We denote by
$\mathit{CF({S})}$ the property that $S$ is conflict-free, and
$\overline{\mathit{CF({S})}}$ denotes that the set $S$ is in conflict.
Formally,

$\mathit{CF({S})}\quad\Leftrightarrow\quad\bigcap_{A\in S}\;s(A)=\emptyset$

A mode is conflict-free if its legacy applications are conflict-free. In other
words, $\forall\mathit{M_{i}}\in\mathcal{O}$,

$\mathit{CF({\mathit{M_{i}}})}\quad\Leftrightarrow\quad\mathit{CF({\mathit{L_{i}}})}$

The schedule $Sched(\mathit{M_{i}})$ of mode $\mathit{M_{i}}$ is valid only if
$\mathit{CF({\mathit{M_{i}}})}$.

######  Corollary 4.9.

A valid schedule for mode $\mathit{M_{i}}\in\mathcal{O}$ can only exist if the
legacy applications of $\mathit{M_{i}}$ are conflict-free, that is,

$\mathit{CF({\mathit{L_{i}}})}\;\Leftarrow\;\text{``Sched($\mathit{M_{i}}$) is
feasible''}$