## 4 Adaptive Fault-Tolerant Communication Scheme
### Resource Reservation Based on Priority Queue
(3) Finally, in the case of the total required bandwidth \(BW_{required}\)\(>\)\(B_{H}\)\(\times\)\(BW_{effective}\), if it can make enough space for the new reservation \(S_{add}\) by removing the bandwidth of sensors with lower priorities from \(Q_{reserved}\), then the new reservation \(S_{add}\) is accepted. Otherwise, it is rejected. In the process of removing the sensors from \(Q_{reserved}\), three situations may occur:  
* If all sensors with lower priorities than \(S_{add}\) in \(Q_{reserved}\) have been processed and the aggregate bandwidth of them (_i.e._, _Sum_) is still less than \(BW_{required}\)-\(B_{H}\)\(\times\)\(BW_{effective}\), then the new reservation of \(S_{add}\) is rejected and \(S_{add}\) is added into \(Q_{removed}\). * If the aggregate bandwidth (_Sum_) of the sensors (\(Q_{temp}\)) that may be removed from \(Q_{reserved}\) satisfies that \(Sum<\)\(BW_{required}\)-\(B_{H}\)\(\times\)\(BW_{effective}\), then the current sensor is added into the  
Figure 6: Bandwidth reservation requirements. Figure 7: Channel reservation decision-making. temporary queue \(Q_{temp}\), and the next sensor with lower priority than \(S_{add}\) in \(Q_{reserved}\) will be checked. * If the aggregate bandwidth of sensors (\(Q_{temp}\)) that may be removed from \(Q_{reserved}\) satisfies that \(Sum\geq BW_{required}\)-\(B_{H}\times BW_{effective}\), then the new reservation of \(S_{add}\) is acceptable; Sensors in \(Q_{temp}\) are removed from \(Q_{reserved}\) and added into \(Q_{removed}\); and \(S_{add}\) is added into \(Q_{reserved}\). For the sensors in \(Q_{removed}\), they are served by best-effort communications temporarily. However, in the following four situations, their bandwidths may be re-reserved: (1) the fault-tolerant priorities increase; (2) the fault-tolerant priorities of sensors in \(Q_{reserved}\) decrease; (3) the bandwidth requirements are reduced; (4) the effective bandwidth increases. ```
1:\(Q_{reserved}\), \(Q_{removed}\), \(S_{add}\), \(BW_{effective}\), \(BW_{required}\), \(B_{L}\), \(B_{H}\)
2:\(Q_{newreserved}\), \(Q_{newremoved}\)
3:if\(BW_{required}\)\(\leq B_{L}\)\(\times\)\(BW_{effective}\)then
4:\(Q_{newreserved}=Q_{reserved}\).add(\(S_{add}\))
5:\(Q_{newremoved}=Q_{removed}\)
6:return
7:else
8:if\(BW_{required}\)\(\leq B_{H}\)\(\times\)\(BW_{effective}\)then
9:if the priority of \(S_{add}\) is not higher than \(Q_{reserved}\).minPriority() then
10:\(Q_{newreserved}=Q_{reserved}\)
11:\(Q_{newremoved}=Q_{removed}\).add(\(S_{add}\))
12:return
13:else
14:\(Q_{newreserved}=Q_{reserved}\).add(\(S_{add}\))
15:\(Q_{newremoved}=Q_{removed}\)
16:return
17:endif
18:else
19:\(Sum\)=\(0\)
20:\(Iterator=Q_{reserved}\).begin()
21:while\(Iterator\)!= \(Q_{reserved}\).end() and the priority of \(Iterator\) is lower than \(S_{add}\).priority()
22:\(Q_{temp}\).add(\(Iterator\))
23:\(Sum+=Iterator\).bandwidth()
24:\(Iterator\)++
25:if\(Sum\)\(\geq BW_{required}\)-\(B_{H}\)\(\times\)\(BW_{effective}\)then
26:\(Q_{reserved}=Q_{reserved}\).remove(\(Q_{temp}\))
27:\(Q_{newreserved}=Q_{reserved}\).add(\(S_{add}\))
28:\(Q_{newremoved}=Q_{removed}\).add(\(Q_{temp}\))
29:return
30:endif
31:endif
32:endif
33:\(Q_{newreserved}=Q_{reserved}\).add(\(S_{add}\))

### Time Complexity Analysis

**Theorem 1:** The time complexity of AFTCS is \(T(n)=O(n\lg n)\), where \(n\) is the number of sensors in the system. **Proof. ** The fault-tolerant channel allocation algorithm based on the priorities mainly maintains two fault-tolerant priority queues: the reservation sensor queue \(Q_{\mathit{reserved}}\) and the queue \(Q_{\mathit{removed}}\) containing all sensors removed from the reservation queue. \(Q_{\mathit{reserved}}\) and \(Q_{\mathit{removed}}\) are maintained through minimum heap and maximum heap respectively. Suppose the number of sensors in the system is \(n\) and the number of sensors in \(Q_{\mathit{reserved}}\) is \(m\) (\(0\leq m\leq n\)), then the number of sensors in \(Q_{\mathit{removed}}\) is \(n\)-\(m\).