## 6 Timing Constraints  
In this section, we define a set of timing boundary equations associated with the message response time, considering the supported set of message streams and the probabilistic behaviour of the CSMA-CA algorithm. Afterwards, these boundary equations are compared with the deadline of each message stream, in order to assess its schedulability. The main target of this set of boundary equations is to enable network designers to adjust the periodic message stream set and/or the protocol parameters of the cluster-tree network. As the proposed allocation schemes are intended to be used in probabilistic medium access networks, it is worth mentioning that target applications must be loss tolerant. Therefore, this response time analysis provides a probabilistic methodology to reduce the number of message drops due to buffer overflows and network traffic congestion. The work presented in this paper considers earlier work from [PERSON] et al. [22; 23] and [PERSON] et al. [44], which use similar approaches for the schedulability analysis of FlexRay and FDDI networks, respectively. The response time analysis calculations are based on earlier work presented by [PERSON] et al. [45], for the response time analysis of multi-task scheduling on mono-processors. For computing the boundary equation for the response time of a message stream, we consider a scenario where all messages streams are simultaneously generated just before the end of the cluster active period. In this case, all messages will be queued in the internal buffers of the nodes. Figure 9 illustrates this case, where the transmissions will only start in next active period scheduling, each one during its active period. In order to model a boundary equation for the response time (\(R_{i}\)) of a message stream \(S_{i}\), we derive its probabilistic response time (\(W_{i}\)), which corresponds to the response time analysis for a specific cluster of any depth, assuming the probabilistic worst-case scenario for message \(M_{i}^{k}\) of message stream \(S_{i}\), according to Figure 10.  
Note that, in a best-case scenario, this message will be transmitted to its parent cluster-head during the next cluster active period. This way, there is an initial delay \(\gamma_{i}\), during which the message must wait for the next active period of its cluster. This initial delay can be expressed as follows:  
\[\gamma_{i}=\sigma_{i}+(BI-SD_{j}), \tag{20}\]  
where \(\sigma_{i}\) corresponds to a time interval immediately smaller than the transmission time for one message \(M_{i}^{k}\) within the CAP and \((BI-SD_{j})\) corresponds to the inactive period of that cluster. Figure 10: Local worst-case response time for a message stream. Figure 9: Worst-case scenario for cluster-tree networks. This message can suffer an interference (\(\Theta_{i}\)) from the higher priority message streams located in the descendant nodes of cluster-head \(CH_{j}\) of the current active cluster \(j\). In the best-case scenario, this interference corresponds to the sum of the transmission times of the set of higher priority message streams. However, if this sum exceeds the superframe duration, the related interference from the subsequent superframe must also be considered. Thus, we define (\(\Theta_{i}\)) for message \(M_{i}^{k}\) as:  
\[\Theta_{i}^{1}(CH_{j})=T_{TXDi} +\left[ \begin{array}{c}\frac{\sum_{h\in\mathcal{S}_{bdow}^{j}} \ T_{TXDi}}{\sum_{h\in hp(i)}}\\ \frac{h\in hp(i)}{SD_{j}}\end{array} \right]\times(BI-SD_{j})+\sum_{ \begin{subarray} {c}h\in\mathcal{S}_{bdow}^{j}\\ h\in hp(i)\end{subarray} }T_{TXDh} \tag{21}\] \[\Theta_{i}^{w}(CH_{j})=T_{TXDi} +\left[ \begin{array}{c}\frac{\sum_{h\in\mathcal{S}_{bdow}^{j}} \left[\frac{\Theta_{i}^{w-1}(j)}{P_{h}}\right]\times T_{TXDh}}{\sum_{h\in hp( i)}}\\ \frac{h\in hp(i)}{SD_{j}}\end{array} \right]\times(BI-SD_{j})...\] (22) \[...+\sum_{ \begin{subarray}{c}h\in\mathcal{S}_{bdow}^{j}\\ h\in hp(i)\end{subarray}