6.2 Design and Analysis of FSA
6.2.1 Design of FSA
The main objective of FSA is to achieve an agreement among multiple candidates with lower coordination delay than SA and CSA. At the same time, FSA must be robust enough to deal with potential collision and unnecessary retransmission. Since all the inefficiencies in SA and CSA are mainly due to the use of multiple ACKs, we adopt a single ACK in FSA, which will be sent by the highest priority candidate in the set of successful receivers. This single ACK plays two roles. On one hand, it informs the sender that reception has been successful, which is the same as SA and CSA; On the other hand, it suppresses all the other lower priority candidates' attempts to forward the data packet. This is different from the ACKs in SA and CSA schemes, which are to help candidates share the information about the reception status. Accordingly, we also choose to use the channel assessment technique to detect the appearance of ACK.
The FSA works as follows. Each candidate waits for 
before deciding whether it should broadcast ACK, where n is its priority order in the candidate set. So with a time delay of SIFS after the data packet was received, the highest priority candidate sends out an ACK. From that point in time, all the other candidates detect the channel for a 
time to tell whether they detect this ACK. If the answer is positive, they stop detecting the channel and simultaneously suppress their own attempts to send ACK and to forward the data packet. Otherwise, if they did not detect any signal within this period, they would think that the highest priority candidate missed the data packet. In that case, the second highest priority candidate takes the responsibility of sending ACK in the beginning of the second 
and all the remaining lower priority candidates continue to monitor this ACK within this time. The coordination process goes on like that until some successful receiver finally sends an ACK in the channel.
An example of a transmission with three candidate nodes is illustrated in Figure 6.3. During this one-hop transmission, candidate1 failed to receive the packet. Thus candidate2 and candidate3 detect nothing in the first 
time. Then candidate2 thinks that it is itself the highest successful receiver and sends ACK at the beginning of the second 
. candidate3 detects this ACK and immediately suppresses itself. The total coordination time for FSA with n candidates is: 
compared with SA and CSA's TSIFS + n × TACK. Since the 
is far less than TACK (for 802.11b, the former is 15 microseconds while the latter is more than 200 microseconds), FSA can significantly reduce the time cost for candidate coordination.
Figure 6.3 FSA with the first ACK missing. Reproduced by permission of © 2009 IEEE.
6.2.2 Analysis
The key difference of FSA from SA and CSA is that it only uses a single ACK to suppress other potential forwarders and acknowledge the sender. Fast slotted acknowledgment uses channel assessment technique to infer some raw information such as whether some packet is transmitting rather than more detailed information like the content of the packet. At first sight, it seems to be less reliable than SA and CSA. However, this is not true. On the contrary, because the information required by FSA is raw, it can be obtained more easily and reliably, which makes the whole scheme work well in a wireless environment, where the most distinct property is unreliability. Suppose one transmission with two candidates A and B where A possesses higher priority and both candidates got the data packet. If the link between A and B is not good when A is transmitting its ACK, then the ACK received by B may be corrupted. In SA and CSA coordination schemes, node B needs to get the ID of the highest priority successful recipient known to the ACK's sender (in the case where it is A itself) from the received ACK. However, with this corrupted ACK, B will fail to do that and will consider itself as forwarder, which leads to duplicate forwarding and unnecessary retransmissions. However, in FSA, B just needs to know that a transmission has happened instead of the detailed content within the received packet. Even if the ACK is corrupted, B may still be able to infer that there is an ACK transmission from higher priority node A. Thus FSA is more robust in this case.
Another apparent weakness of FSA is that a single ACK would not be reliable enough to ensure that the send would receive it correctly, because once this single ACK is lost the sender needs to retransmit the data packet unnecessarily. With multiple ACKs like SA and CSA, the sender would hear at least one clear ACK with high probability. However, it is also not true because of the following reasons. 1. If the data packet (which is generally longer than ACK and sent in higher rate) has already been received by the corresponding candidate successfully, the subsequent ACK sent along the reverse direction at a lower rate (1 mbps for 802.11b) will be received by the sender successfully with very high probability (Sang et al. 2007). 2. The other ACKs, except the first one in SA and CSA, are sent in relatively long intervals (several ACK slots) after receiving the data packet. The link states may have already changed at that time. Then the following ACKs may not be able to be received correctly by the sender. So the added reliability by those extra ACKs is quite limited. In other words, a single ACK is already strong enough and multiple ACKs are dispensable.
The real potential vulnerability of FSA is its dependence on the precision of the channel assessment technique. For example, if the detecting node considered other interference to be ACK sent by some higher priority candidate, it will falsely suppress itself from forwarding the packet. It is also possible that, in some situations, the detecting node fails to sense the transmission of ACK from higher priority candidate and then sends its own ACK, which will collide with the transmitting one. However, this dependence problem can be greatly alleviated through careful design. For the first case, we make the whole coordination process highly synchronized and also introduce more precise channel-assessment technique (see details in following subsection). Thus such a probability will be constrained at a rather low level. Even if this scenario indeed happens, the consequence is just that those lower priority candidates suppress themselves “overcautiously” and cause the sender to retransmit the packets unnecessarily. This will make opportunistic routing behave like traditional routing. For the second case, as we described at the beginning of this section, this possibility will be very low because the forwarding candidates are usually in each other's carrier sensing ranges. If this case really happens, the consequence will be duplicate forwarding and unnecessary retransmission, which has serious impact on the performance of OR protocols. However, we should notice that this false detection results in the same consequences in the CSA scheme, which means that FSA will not introduce extra chance for duplicate forwarding in the worst case.
6.2.3 More on Channel Assessment Techniques
Carrier Sensing Multiple Access with Collision Avoidance (CSMA-CA) is the de facto medium access control protocol for 802.11 WLAN. It follows the LBT (Listen Before Talk) principle and works in a time-slots manner, which requires the sender to sense the channel status within one time slot before sending packets. Such a sensing mechanism is called clear channel assessment (CCA) (802.11b 1999 n.d.). Generally speaking, CCA performance could be characterized by a pair of detection and false alarm probabilities (Pd and Pfa) in which Pd refers to the probability of detecting the channel to be busy when the channel is indeed busy and Pfa refers to the probability of detecting the channel to be busy when the channel is actually idle. There is an inherent tradeoff between Pd and Pfa with the constraint of limited detection time (Zhen et al. 2008). The CCA module can be implemented in two ways:
1. Energy detection (ED). Energy detection based CCA is a simple noncoherent detection approach. It integrates the square of the incoming signal from the radio front end during the CCA window to get an average signal strength, then compares it with a predefined threshold level, which represents the normal background noise and makes a judgment. The main advantage of ED-based CCA is simplicity and the main disadvantage is relatively poor detection reliability (especially in 802.11b/g, which works on 2.4 GHZ, coexisting with other technologies such as microwave ovens and Bluetooth devices).
2. Preamble detection (PD). Preamble detection based CCA tries to use the correlation of well-known preambles with the received signal to detect the presence of a packet. It can be implemented by a crosscorrelation-based matched filter which is more complex as it can fully take advantage of the processing gain and thus has a more enhanced reliability. The main disadvantage of PD-based CCA is that it needs to run continuously and thus brings a relatively high energy cost.
Both detection methods are supported by most of the current wireless cards and can promise a Pd of no less than 99% with the CCA window specified by IEEE 802.11 standards (http://standards.ieee.org/). However, the PD-based CCA outperforms the ED-based CCA in Pfa, especially in noisy scenarios. Thus in FSA we choose the PD-based CCA technique. Another reason that we prefer PD-based CCA is that its main disadvantage can be avoided in the scenario of coordination in OR protocols because what we need to know is that if any ACK being sent during the CCA window and do not care the channel state that is out of this period. Thus we do not require the PD module running continuously and it can be turned on only when the MAC layer requires a CCA from the PHY layer, just as an ED module does.