## 3 Adaptive Real-Time Routing Protocol
### Adaptive QoS Routing Protocol  
An adaptive approach to QoS routing is taken according to \(DBP_{i}\) in \(S_{i}\) as well as \(DBP_{ObjID}\) in \(T_{ObjID}\) to meet the requirements of the (\(m\),\(k\))-firm in terms of both \(T_{ObjID}\) and \(S_{i}\). The QoS routing algorithm is presented in Algorithm 1. Algorithm 1 determines a suitable path for the next packets among multiple paths. To find the paths, the node sends a probing packet to identify the available paths and waits for the end-to-end delay from the sink. The probing packet is broadcasted in the same as the Route Request message (RREQ) and Route Response (RREP) in ad hoc on-demand multipath distance vector (AOMDV) [36]. The difference between the proposed and AOMDV comes from the deadline. If an intermediate node receives the packet with greater elapsed time than deadline, \(D_{i}\), it does not broadcast the packet any more. In addition, the sink node replies only when the end-to-end delay is bounded within \(D_{i}\). Multiple paths meeting the delay constraint are arranged in ascending order and are denoted by \(P_{i}^{1\ldots n}\). Based on the delay, the shortest path is denoted by \(P_{i}^{1}\). Each node has a different maximum number of available paths, \(n\). Initially, \(P_{i}^{n}\) is selected according to the longest-path-first strategy. After the initial stage, a path is selected by \(DBP_{i}\) in \(S_{i}\) as well as \(DBP_{ObjID}\) in \(T_{ObjID}\). The path selection is accomplished whenever a reply with the value of \(DBP_{ObjID}\) is received. **If the value of \(DBP_{ObjID}\) is positive (lines 5-13):** First, if \(DBP_{ObjID}\) is larger than 0, the application requirement is regarded to be met. So, it is important to examine the value of \(DBP_{i}\). If \(DBP_{i}\) is larger than 0, application and session requirement are met. Thus, this path is suitable and complies with the two requirements. Otherwise, it is necessary to consider a new path with shorter delay among multiple paths, denoted by \(P_{i}^{n-1}\) as in line 9. However, the current path needs to be maintained if no other available path remains, when \(n\gets 1\). As a result, if application requirement is met, a path is re-selected according to \(DBP_{i}\) in \(S_{i}\). **If the value of \(DBP_{ObjID}\) is negative (lines 14-29):** When the value of \(DBP_{ObjID}\) is negative at node \(i\), more complicated approaches than previous case are taken. This implies that additional options are taken into consideration to choose the path. That is, a new path is selected in aggressive way according to distance to positive status. To determine the distance to reach a positive status, we compute the absolute value with two DBP values. The larger value is obtained, the shorter path is taken. Similar to the previous case in which \(DBP_{i}\) was positive, an incremental approach is taken for path selection simply. On the other hand, if the value of \(DBP_{i}\) is also negative, we compare the absolute value with the threshold. If this value is larger than the threshold, the shortest path, \(P_{i}^{1}\), is selected because current path is not suitable at all. This is to turn negative DBP value to positive one by ensuring the shortest delivery time between node \(i\) and the sink. Otherwise, another path is selected by choosing the path number, \(n-t\), rather than \(n-1\) as in the previous case. By applying \(n-t\) rather than \(n-1\), it is possible to turn negative DBP to positive one in earlier than incremental approach. We assume that the a new event on next node, \(j\), happen after event time on node \(i\) is over. When the new node \(j\) detects the events, Algorithm 1 is initiated on a new node. However, the path selection algorithm takes some time to execute because multiple paths should be established through Path_Search_Probing(i,sink). To reduce the waiting time for a new path, node \(j\) temporarily sends packets directly to the previous node \(i\) until the new path is established. Node \(i\) transmits the corresponding packets along the path \(P^{1}_{i}\).