# Flying Real-Time Network to Coordinate Disaster Relief Activities in Urban Areas +
## 5 Real-Time Analysis
### Analysis of a Flying Real-Time Network  
In FRTNs we consider a set of periodic and independent messages sent by the nodes (SAR teams). For simplicity of presentation, all messages have the same length, that is, they have equal payloads. Formally, a message \(m_{i}\) originating in node \(i\) is described by the tuple \(\langle C,P,r,D\rangle\), where \(C\) is the time required to transmit a message, \(P\) is the period, \(r\) is the release time, and \(D\) is the relative deadline of the message. The absolute deadline is computed from the release time and relative deadline, \(d=r+D\). For simplicity, we consider that the time is divided in atomic units or slots. Events occur at the beginning of a slot. Time is denoted \(t=0,1,\ldots,n\). In the network, the messages are generated in nodes and go up through levels before reaching the IC. In the reverse path, a message sent by the IC should traverse the same levels to reach an SAR team. Therefore, the transmission path can be seen as a \"pipeline\", where each stage/level cannot process the message until it has been released by the previous one. Figure 10 shows the propagation model for a message considering that network topology. Each stage in the transmission process requires a proper scheduling algorithm, and for each level, the real-time feasibility conditions should be verified for the system. Therefore, we must consider the moment in which the message arrives to intermediate nodes, and the latest instant at which it should leave that node. Let us suppose that there is one hop between the source and destination node. A message has a total delay of \(x\) slots if it is transmitted alone in the network, and as soon as it arrives to the intermediate hop, it is sent again. Let us suppose that the delay from the source to the intermediate node is \(y\) slots. If the message is delivered at \(r=0\), it is not possible for that message to arrive before \(r=0+y\) to the intermediate node. In that case, the message should not leave the intermediate node after \(D-x-y\) in order to reach the destination node before its deadline. This means that the message should be processed in the intermediate node in at most \(D-x-y-r\). Considering the described scenario, we introduce the following notation to deal with the schedulability analysis in the intermediate nodes. For an intermediate node \(j\), the release time of message \(i\) coming from node \(i\) is denoted \(r_{i}^{j}\), the deadline is denoted \(D_{i}^{j}\), and the transmission time is denoted \(C_{i}^{j}\). Although there are several algorithms for message scheduling, among the most used ones are rate monotonic (RM) and earliest deadline first (EDF). In the first algorithm, priorities are assigned to messages based on the message period, with shorter periods given higher priorities. At each opportunity, the message with higher priority is dispatched. In the second case, the highest priority is given to the message with the closest deadline. In that way, whenever the node has the chance to transmit, it dispatches the message with the closest deadline, therefore EDF can reach a better utilization of the network. Even though a different policy can be employed at each hop in the path, for simplicity, we assume an EDF scheduling policy for all of the stages. It is known that EDF is optimal for scheduling a set of independent periodic messages within a network. However, in the problem proposed here, the message should traverse several hops before reaching its destination, and in each hop, a scheduling policy for message delivery is followed by the interim node. This affects the independent condition, as a message cannot be dispatched from node \(j\) if it has not left node \(i\) before. Thus, there is a dependency in the scheduling conditions of node \(j\) with respect to the scheduling conditions in node \(i\). To overcome this problem, we use the Chetto algorithm [27] that transforms a set of precedence-related messages into a set of independent ones.