6.1 Existing Candidate Coordination Schemes
In this section, we review five state-of-the-art candidate coordination schemes: GeRaF collision avoidance MAC, ExOR batch-based MAC, contention-based forwarding (CBF), slotted acknowledgement and compressed slotted acknowledgement.
6.1.1 GeRaF Collision Avoidance MAC
The GeRaF collision-avoidance MAC-coordination scheme is proposed in (Zorzi and Rao 2003). This scheme applies to a sensor network scenario, where nodes wake up and go to sleep periodically. It is basically a geographic opportunistic routing, where each transmitter knows its own location information and that of its neighbors, and the destination. The transmitter node's location information as well as the destination node's location information are embedded in the ready-to-send (RTS) frame. It assumes that sensor nodes are equipped with two radios (Schurgers et al. 2002). Therefore, the data traffic and the wakeup signaling can be operated on two different channels simultaneously. That is, all messages exchange on the first “data” frequency while the busy tone is sent on the second frequency. We present this protocol from transmitter and receiver point of view as described in Zorzi and Rao (2003).
6.1.1.1 Transmitter Behavior
When a sleeping node has a packet to send, it wakes up and enters the active state and monitors both data and busy tone frequencies for τ seconds. If either frequency is busy, the node reschedules an attempt at a later time. If both frequencies are sensed idle during this entire time interval, the node broadcasts a RTS message that contains the location of itself and the intended destination. After sending the RTS, the transmitting node listens to the subsequent slots for clear-to-send (CTS) messages from potential forwarding candidates. In each of the CTS slots following the end of the RTS message, the transmitting node acts as follows:
1. If only one CTS message is received, it starts transmission of the data packet. The initial part of this packet acts as a CTS confirmation for the forwarding candidate which issued the CTS.
2. If it receives no CTSs, it sends a CONTINUE message and waits again for CTSs. It times out after Np empty CTS slots (which forces the transmitter to abort the handshake and to reschedule the transmission at a later time).
3. If it hears a signal but is unable to detect a meaningful message, it assumes that a CTS collision took place and will send a COLLISION message, which will trigger the start of a collision resolution algorithm and will wait again for CTSs.
Like the IEEE 802.11 protocol, an immediate ACK is expected after packet transmission. The node can go to sleep if the ACK is correctly received. If the transmitter does not correctly receive an ACK within a given time interval, it times out and considers the packet delivery failed. It will reschedule the same packet for future transmission. The transmitter will drop the packet after 
failed attempts, it will generate an error message for the higher layers. The transmitter transmits the busy tone to prevent interference from hidden terminals while listening for CTSs and ACK.
A problem with this scheme is that packet duplication cannot be completely avoided. Actually, it is a common problem of most of the existing opportunistic candidate coordination MAC protocols. After sending the ACK, the forwarding candidate becomes the actual forwarder and is in charge of the packet delivery. If the ACK is lost, the transmitter will not be aware of this fact and will retry the transmission of the same packet. This duplication might be exaggerated at the later hops if the same scenario happens. However, this duplication can be alleviated if intermediate node is able to remember the sequence numbers of the latest packets, and discard the duplicated ones. The destination node can also drop the duplicated packets. This inefficiency caused by packet duplication is expected to be limited, given the fact that losing an ACK when the packet transmission was successful is a low-probability event.
6.1.1.2 Receiver Behavior
When a node wakes up and is in the listening mode, it senses the channel to see if there is any transmission. If nothing is detected during the listening time interval, the node goes back to sleep. Otherwise, if the node detects the start of a transmission, it changes into the receiving state. Meanwhile, it activates the busy tone on the second frequency for a duration of TRTS (the time for RTS transmission). If no valid RTS is received, the node goes back to the listening state. On the other hand, if a valid RTS is received, the node reads the information in it (i.e. the location information of the transmitter and the destination) and determines its own priority as a forwarding candidate. This priority is based on the relative location of the node itself compared with the distance between the transmitter and the intended destination.
A relay priority assignment proposed in Zorzi and Rao (2003) is as follows. The portion of the coverage area of the transmitter that is closer to the destination than the transmitter itself is divided into Np regions R1, R2, …, and 
, such that all points in Ri are closer to the destination than all points in 
, i = 1, 2, …, Np − 1. After the RTS, all nodes in R1 will send a CTS message in the first CTS slot, whereas all others with lower priorities will keep silent. All nodes will then listen for the message from the transmitter in the latter part of the CTS slot.
If a data packet transmission (which contains the identification of the forwarding candidate which sent the CTS) is heard, only the designated forwarding candidate will continue to receive, whereas all others will go back to sleep to save energy.
If a CONTINUE message is heard in the second part of the first CTS slot, it means that there are no forwarding candidates in R1 and all forwarding candidates in R2 will contend in the second CTS slot.
If an ABORT message is received, it indicates that the transmitter has reached the maximum allowed number of CTS slots and the forwarding coordination is aborted.
If a COLLISION message is received, it means that more than one CTS frame was generated in the CTS slot. All forwarding candidates who did not transmit CTS will quit from the forwarding contention because they can infer that higher priority forwarding candidates are present. The forwarding candidates involved in the collision will start the collision-resolution mechanism. Each colliding forwarding candidate will decide whether or not to continue with a probability of 0.5 for each outcome. A candidate that decides to continue will send a CTS in the next slot. There are three possible events:
1. Only one forwarding candidate sends the CTS. Then the transmitter starts the packet transmission and all other forwarding candidates quit the contention.
2. More than one CTS frame is sent in the same slot. Then the transmitter sends a COLLISION message. Those forwarding candidates that did not send a CTS drop out, while those involved in the collision decide whether to continue as before until the collision is resolved.
3. No CTS is heard. A CONTINUE message is sent by the transmitter, and all forwarding candidates that did not select the current slot decide again independently whether to continue as before.
The above procedure have a high probability of terminating within a few slots. In order to force it to be terminated, the transmitter can send an ABORT message if the collision is not resolved within a maximum allowed number of CTS slots. Finally, any node that receives a message it does not understand quits the contention.
Nodes that heard the RTS correctly will follow the sequence of steps above and they are guaranteed to either become the actual relay node or to drop out at some point. In order to avoid the hidden terminal problem, each forwarding candidate involved in the above contention procedure will keep the busy tone active until it drops out or, if it wins the contention, until the whole data packet has been received.
6.1.2 ExOR Batch-Based MAC
ExOR is proposed for improving throughput in static multihop wireless networks (Biswas and Morris 2005). It assumes that each node knows the global information of the network, and each node can compute the shortest traditional single path to the destination in terms of ETX but only considering forward link quality. It operates on batches of packets and all packets are broadcast.
6.1.2.1 Source Behavior
The source node includes a list of forwarding candidates in the header of each packet, prioritized by the estimated ETX to the destination. The destination node ID is at the head of the list with the highest priority. In order to avoid overwhelming overheads in a network with a large number of nodes, only the neighbors whose link quality to the source is larger than 10% will be considered in the forwarder list. Then the source node broadcasts the first batch of packets. It moves to the next batch only if it infers that more than 90% of the packets in the current batch are received by higher priority forwarders or the destination.
6.1.2.2 Forwarder Behavior
When the neighbors of the source node receive the broadcast packet, they will check if they are in the forwarding candidate list. If they are not in the forwarder list they will drop the packets. If they are, they will buffer the successfully received packets and wait until the end of the batch.
The highest priority forwarding candidate then broadcasts the packets in its buffer as its own fragment of the batch. Each packet includes a copy of the sender's batch map containing the forwarding candidate's best guess of the highest priority node to have received each packet in the batch. Upon receiving a packet from a higher priority candidate, a forwarder updates its batch map by replacing its own guesses of the highest priority nodes for each packet with those indicated in the batch map of the received packet. Note that the destination node is a special case; when its turn comes it sends ten packets only with header but no data. In this way, this batch map serves as an acknowledgement that propagates back to the source, which is highly reliable as it has been accumulated several times by intermediate forwarders.
In addition, each packet includes a fragment size (the number of packets in the current fragment) and its fragment number (offset of itself in the current fragment). Each remaining forwarder then transmits in order to avoid collision. A transmission timer is set at each forwarder and upon the expiration of this timer the forwarder begins to transmit its fragment. Ideally, a lower priority forwarder should wait until all the forwarders with higher priority than itself finishes transmission. However in practice it is hard to estimate the time spent by each higher priority forwarder in transmission due to packet losses. Thus, in ExOR, rather than starting the transmission after each forwarder overhears the last packet sent by the forwarder before it, the forwarder estimates the transmission start time based on the fragment size and fragment numbers piggybacked in the overheard packets from the forwarder before itself, which is more reliable. When a node does not hear any forwarded packets from higher priority nodes, it simply assumes that each of them transmits five packets. Each forwarder sends only packets which were not acknowledged in the batch maps of higher priority nodes.
The forwarders continue to cycle through the priority list until the destination has 90% of the packets. The reason is that the last few packets in a batch would take the most overheads to send, which may overwhelm the benefit of OR. The remaining packets are transferred with traditional routing.
6.1.3 Contention-Based Forwarding (CBF)
Contention-based forwarding belongs to geographic routing and was proposed in Fussler et al. (2003). Traditional geographic routing requires a forwarding node to know all its neighbors' positions in realtime which is usually done using periodic beacon messages. This does not work well under high node mobility, since nodes' location information collected in this way is often outdated, which leads either to a significant decrease in the packet delivery ratio or to a drastic increase in load on the wireless channel. To this end, CBF proposes to perform position-based unicast forwarding without the help of beacons. The idea is to select the next hop using a distributed contention mechanism based on the actual positions of all current neighbors. In order to achieve this, in CBF the nodes that received a packet from a forwarding node set a biased timer based on their own positions. And to avoid packet duplication, the first node that is chosen suppresses the other nodes.
6.1.3.1 Timer-Based Contention
Next we briefly introduce the decentralized timer-based contention mechanism in CBF. In order to greedily maximize the remaining distance to the destination (hop progress) of each packet, the timer's runtime is set to be inversely proportional to the hop progress P:
6.1 
where P is defined as
6.2 
where f is the position of the forwarding node, z is the position of the destination, and n is the position of the neighboring node whose timer is set, “dist” stands for Euclidean distance between two positions and rradio is the nominal radio range.
The above timer runtime configuration inevitably incurs packet duplication in the situation where the best suited node has a hop progress of P1, and at the same time there exists at least one node with a hop progress of P, such that t(P) − t(P1) < δ, where δ stands for the minimum time interval needed for suppression. As shown by the analysis in Fussler et al. (2003), the probability of packet duplication decreases as the distance of a neighbor node to the forwarder increases, when all the nodes are uniformly distributed.
6.1.3.2 Suppression Techniques
There are three suppression techniques proposed in Fussler et al. (2003):
1. Basic Suppression. When a node's timer expires, it simply assumes that it is itself the next hop forwarding node and broadcasts the packet. When another node receives this broadcast and at the same time still has a timer running for the same packet, the timer is canceled and the node does not forward the packet. This method, although simple, will introduce duplicated transmissions in addition to those incurred by the time interval needed for suppression. That is, some nodes may not be able to hear the broadcast of the assumed next hop forwarder; they can be located outside of the transmission rage of the next hop forwarder. Using the basic suppression technique, it is shown that at most three packet duplications could happen in addition to those incurred by the suppression time interval.
2. Area-based Suppression. To solve the problem of basic suppression, area-based suppression is proposed. The basic idea is to artificially restrict the nodes that participate in the next hop forwarder contention process to those that lie within a smaller geographical area than before, such that every node will hear the transmission of any other node within this area (every node is in the transmission range of every other). That area is called a suppression area. A Reuleaux Triangle is adopted, which covers the area (from the forwarder to the destination and within the forwarder's transmission range) well with good forwarding progress. The Reuleaux Triangle trades off the number of nodes contained within the suppression area against the inclusion of better candidate forwarding nodes. In case that there are no nodes in the suppression area, two backup areas are used, in which a similar contention and suppression process is repeated in each of them.
3. Active Selection. The above two methods still cannot eliminate the duplicate transmissions caused by the suppression time interval. To this end, active selection prevents all kinds of packet duplications by introducing additional control message overhead at the forwarding node. Instead of sending the packet directly, the forwarding node first sends a request-to-forward (RTF) signal containing the forwarding node's location and the destination node's location. Each neighbor node that hears the RTF and with a positive hop progress sets a replay timer as in the basic suppression scheme. Upon the expiration of the reply timer, the node sends a clear-to-forward (CTF) packet and other nodes that received the CTF suppress themselves from forwarding. Finally, the forwarding node selects a node from the set of nodes that have sent a CTF, and transmits the packet to that node via unicast. This process resembles the request-to-send (RTS) and clear-to-send (CTS) mechanism in IEEE 802.11 MAC. In fact, the active selection method can be integrated with RTS/CTS schemes to avoid the “hidden terminal” problem. In active selection, the forwarding node has the ultimate authority over the selection of the next hop forwarder.
6.1.4 Slotted Acknowledgment (SA)
Slotted acknowledgment was is proposed by Biswas and Morris (2003). It applies a similar acknowledgment scheme to the one used in traditional 802.11. However, it requires each candidate who has received the data packet to broadcast an ACK in different time slots according to their priorities. Instead of only indicating the success of reception, each ACK contains the ID of the highest priority successful recipient known to the ACK's sender. All the candidates listen to all ACKs before deciding whether to forward the data packet in case a lower prioritized candidate's ACK reports a higher prioritized candidate's ID. In order to protect all the ACKs from being interrupted by other transmissions, SA extends the Network Allocation Vector (NAV) in the MAC header of the data packet to reserve the channel for longer time. Thus the total coordination time for SA with n candidates is n × (TSIFS + TACK), where SIFS is short interframe space (802.11b 1999 n.d.). This scheme has a serious vulnerability that makes it fail to work properly in some scenarios. Taking one transmission with three candidates as an example in Figure 6.1. Suppose that when the sender is transmitting, another node within the sender's transmission range, which is willing to transmit, does not hear the data packet clearly (for example, received a corrupted one that cannot get the NAV value from the MAC header). At the same time, the highest priority candidate also failed to receive the data packet. In this case, the first ACK is missing and the potential transmitter that does not update its NAV accordingly senses the channel to be clear for 2 × TSIFS + TACK, which is obviously greater than DIFS (Distributed Inter Frame Space), the idle time needed before sending packet in 802.11 protocols (802.11b 1999 n.d.). Thus it sends its own packet which will collide with the subsequent ACKs from candidate2 and candidate3 as illustrated in Figure 6.1. No one hears a clear ACK, the consequence is that both candidate2 and candidate3 will forward the packet, which results in duplication, and the sender will unnecessarily retransmit the packet. The scenario shown above is not rare, especially in networks under heavy traffic loads.
Figure 6.1 SA with first ACK missing. Reproduced by permission of © 2009 IEEE.
6.1.5 Compressed Slotted Acknowledgment (CSA)
Zubow et al. (2007) tried to alleviate the potential collision in SA by introducing the channel assessment technique and refine SA to a “compressed slotted acknowledgment”. The general idea is as follows: with a delay of SIFS after receiving the data packet, the highest priority candidate sends its ACK out. From this time point all other candidates that also successfully received the data packet sense the channel by received signal strength indicator (RSSI), a parameter in PHY layer. If the RSSI value increases significantly within the predefined detecting period determined by the priority, the ACK is considered as sent and they will continue to wait for their corresponding ACK slots before sending ACKs. Otherwise, if no such increase in signal strength is observed, the other candidates conclude that the highest priority candidate did miss the data packet. In that case, the second highest priority candidate prematurely sends its ACK to compress the channel's idle space to be smaller than DIFS. All the other candidates behave in the same way as before except that all subsequent events happen earlier. Figure 6.2 depicts a case with three candidates. The use of the channel assessment technique makes the SA's fixed ACK slots mechanism more flexible and enables the CSA to alleviate the potential collision more effectively. However, this detection-based scheme still requires multiple ACKs and thus suffers from the same high coordination delay as SA.
Figure 6.2 CSA with the first ACK missing where RX/TX is the turnaround time for radio to change from receive state to transmit state. Reproduced by permission of © 2009 IEEE.
