# Flying Real-Time Network to Coordinate Disaster Relief Activities in Urban Areas +
## 5 Real-Time Analysis
### Analysis of a Flying Real-Time Network
In this way, a message with one hop is transformed into two independent messages being sent by two nodes, but with release times and deadlines modified for each of them. In this way,  
Figure 10: Message propagation pipeline. message \(m_{i}\) going through node \(j\) to node \(k\) is seen as two independent messages, \(m_{i}^{i}\) and \(m_{i}^{j}\), that have equal transmission time, but different release times and deadlines. To accomplish this decoupling of the precedence relations, Chetto modifies the release times beginning from the first stage and the deadlines starting with the last one. Algorithms 2 and 3 present in pseudo-code the procedures for modifying the release times and deadlines, respectively. For modifying the release times:  
1. For any initial node of the precedence graph, set \(r_{i}^{*}=r_{i}\). 2. Select a message \(m_{i}^{j}\) such that its release time has not been modified, but the release times of all immediate predecessors \(m_{i}^{h}\) have been modified. If no such message exists, exit. 3. Set \(r_{i}^{j}=\max[r_{i},\max(r_{i}^{h}+C:m_{i}^{h}\prec m_{i}^{j})]\). 4. Return to step 2. For modifying the deadlines:
1. For any terminal node of the precedence graph, set \(d_{i}^{*}=d_{i}\)
2. Select a message \(m_{i}\) such that its deadline has not been modified, but the deadlines of all immediate success \(m_{k}\) have been modified. If no such message exists, exit. 3. Set \(d_{i}^{j}=\min[d_{i},\min(d_{i}^{k}-C:m_{j}\prec m_{k})]\). 4. Return to step 2  
As mentioned previously, in this proposal some drones are used as bridges, and therefore are in a fixed location, while others actually transport the messages between two nodes. This strategy introduces a delay that is not related with the transmission rate or computation power of the processor, but with the time needed by the UAV to transport the data between nodes \(i\) and \(j\), \(\Delta t_{ij}\). This delay can be considered constant and equal for every message between those two nodes. However, this delay affects the end-to-end transmission time and should be taken into account in the network analysis. The transportation delay must be subtracted from the deadline computed for that stage, as shown in Equation (5):  
\[d_{i}^{j}=d_{i}^{j}-\Delta t_{ij}. \tag{5}\]  
Once the message transmission has been broken into different stages, the real-time feasibility test can be performed in each node of the \"pipeline\". In order to do that, we use the demand bound function, \(dbf(t_{1},t_{2})\) introduced in [28]. This test computes the worst-case work demand, and then it compares that metric with the time available in the system for message transmissions. For each stage or intermediate node \(S_{i}\), if the available time is greater than the messages demand, the system is feasible in terms of real-time message delivery. Next, we formalize the definition of the \(dbf\) function for the interval \([t_{0},t_{1}]\), based on [28]:  
Definition 1: The demand function for stage \(S_{i}\), denoted by \(dbf_{i}(t_{0},t_{1})\), is the total time taken by all instances of the messages going through \(S_{i}\), having release time and deadline within \([t_{0},t_{1}]\). For periodic messages, the demand function can be computed as follows:  
\[dbf_{i}(t_{0},t_{1})\stackrel{{ def}}{{=}}\max(0,\sum_{m_{h}^{i} \in S_{i}}\left(\left\lfloor\frac{t_{1}-d_{h}^{i}}{P_{h}}\right\rfloor-\left \lceil\frac{t_{0}-r_{h}^{i}}{P_{h}}\right\rceil+1\right)C), \tag{6}\]  
where \(d_{h}^{i}\) represents the modified deadline in stage \(j\) using the [PERSON] algorithm and Equation (5). According to [28], for any interval of length \(t\), the \(dbf(t_{0},t_{0}+t)\) is defined as the maximum possible demand in any interval of length \(t\).