discussion so far leads to the observation that the gain that carrier sensing brings in a multi-hop setting is not straightforward. This is because collisions can still occur and each collision is expensive, as the medium is wasted for at least one packet duration. In order to see the worst case, consider the hidden terminal problem in Figure 2.6(a). Let Zoya start to send to Yoshi and, just before that transmission ends, Xia starts to send to Walt. According to the collision model, both packets are lost and the time for which the wireless medium has been wasted corresponds to a time that can go up to the sum of the duration of the two packets.
2.4.1 Use of Reservation Packets in Multi-Hop
In order to make the collisions less expensive, we can reuse the concept of a reservation packet from Section 1.4.2. The main idea is to constrain the collisions to occur only for packets that are short. First we look at the simplest setting for hidden terminals from Figure 2.6(b). If Zoya has a data packet for Yoshi, then she sends a short request-to-send (RTS) packet. The RTS packet should contain information about the originator (Zoya) and how long the transmission from Zoya will last. Assume that Xia does not transmit while Zoya transmits an RTS. Then Yoshi receives the RTS from Zoya correctly, and he acknowledges it by sending a short clear-to-send (CTS) packet to Zoya. The CTS should contain the address of Zoya, but it also repeats the information about how long Zoya will need to send her packet to Yoshi. The latter information from the CTS is intended for the terminals that are hidden from Zoya, such as Xia, and the CTS blocks their transmissions while Zoya transmits. If Zoya receives the CTS, then she starts to transmit her data and, at the end of the transmission, she receives an ACK from Yoshi. Note that Xia is in the range of Yoshi, such that she gets inhibited by the carrier sensing mechanism in the case when Yoshi has something to send to Zoya, be it a CTS or an ACK. Recalling from the previous section the use of idle slots for packet prioritization, both control packets CTS and ACK that are sent as responses to other packets can use an idle slot that is shorter compared to an RTS packet. With this, when Yoshi sends a CTS packet, Xia senses a busy medium and is thus prevented from sending an RTS packet.
To see the other effects of the RTS/CTS mechanism, consider the exposed terminal problem in Figure 2.6(d). Zoya sends an RTS, Yoshi sends a CTS; Xia receives the RTS, but not the corresponding CTS. This is an indication for Xia that the intended receiver of Zoya is outside Xia's range and Xia can freely initiate a transmission to Walt. The only problem is that, after Yoshi receives Zoya's packet and sends an ACK to Zoya, Xia may be still transmitting and Zoya will not receive the ACK. Therefore, in this simple form, an RTS/CTS does not completely solve the exposed terminal problem and the reader is encouraged to think what other amendments can be done to the protocol in order to address this problem. We should also note that the utility of an RTS/CTS decreases if the range for carrier sensing is larger than the communication range.
2.4.2 Multiple Hops and Full-Duplex
We look briefly into the changes required when full-duplex devices operate in a multi-hop setting. Recall from the previous section that the receiver, upon detecting collision, can send a busy tone to the transmitters, such that they can interrupt their transmissions and shorten the time wasted in a collision. Consider the hidden terminals Zoya and Xia from Figure 2.6(c) and assume there is no RTS/CTS mechanism in place. With half-duplex devices, the time that can be consumed by collision can go up to two packet durations; the extreme case is when Xia starts transmission just before Zoya's packet ends and both packets are wasted. With full-duplex devices, the time consumed by a collision is at most a single packet duration, as Zoya and Xia interrupt transmission immediately after a busy tone is sent to them. If the RTS packet is much shorter than the data packet, then it is still useful to limit the maximal duration of the collision to be short, even if the devices have full-duplex capability. Full-duplex operation can also be beneficial to address the exposed terminal problem, Figure 2.6(d). As discussed above, Xia can start to transmit after receiving an RTS from Zoya and no CTS from Yoshi. When Zoya has finished transmitting, she sends a signal to issue a command to Xia to temporarily switch off her transmission, until Zoya receives an ACK from Yoshi. If Xia has a full-duplex device, then while still transmitting to Walt, Xia can detect the command sent by Zoya, suspend her transmission while Zoya receives an ACK, and continue transmitting afterwards.
2.5 Chapter Summary
In this chapter we have used the dark room analogy to depict a situation in which the same wireless channel needs to be used for coordination and control of transmissions, as well as for the transmission of the actual data. This problem is addressed through the broad class of random access protocols. Two different paradigms for random access have been presented: protocols based on ALOHA and the tree-splitting protocols based on probing. By extending the communication model to introduce minislots, we have introduced the widely used mechanism of carrier sensing. Finally, the chapter presented some challenges and possible solutions to random access problems applied in a wireless multi-hop setting.
2.6 Further Reading
The history of random access protocols is very rich, but also surprisingly vital in identifying new models, aspects and associated problems, for example related to the recent developments in massive communication for the IoT. It has started with the paper on ALOHA Abramson [1970], while the paradigm based on probing and splitting tree was introduced later on in Hayes [1978], Tsybakov and Mikhailov [1978] and Capetanakis [1979]. Detailed analysis of random access protocols can be found in Bertsekas and Gallager [1992] and Rom and Sidi [2012]. A beautiful example of modeling and analysis of random access protocols can be found in Bianchi [2000].
2.7 Problems and Reflections
1 Random access over multiple channels. Let us consider a scenario in which a number of devices attempt to communicate with the base station Basil through random access. Assume that there are available communication channels. At a given instant a device or Basil can be active (transmit or receive) on only one channel. All devices and Basil are half-duplex. Propose a design of random access protocols for the following two cases:All channels are used for data transmission.Part of the channels are reserved for random access and coordination of the devices, while the remaining channels are used for data transmission.
2 The room is not dark. In problem 1(b) it seems that we are departing from the dark room analogy, as there is a dedicated channel for reservation/signaling. Compare this to a classroom in which the students reserve a speech channel by raising a hand through the visual channel. Hence, this classroom scenario has different channels. Explain how the model from assignment 1. should be changed in order to represent correctly the communication model in the classroom.
3 Detecting packet multiplicity. Consider an ALOHA type protocol with a single channel, but let us upgrade the communication model by assuming that, when more than one device transmits simultaneously and there is a collision, Basil can perfectly detect how many packets are present in the collision, but he cannot decode the packets. Propose a random access protocol that can utilize this upgraded model to improve the overall throughput when:Basil knows only the number of the packets involved in the collision, but not the identities of the devices that transmitted the packets.For each collision, Basil knows the identities of the devices that have transmitted the packets that constitute the observed collision.
4 Errors beyond collisions. In order to make the collision model more realistic, let us assume that even when Zoya is the single device that transmits to
