target="_blank" rel="nofollow" href="#ulink_850fcdb2-888e-502a-963a-222ca0a9b08b">Figure 2.2, Basil uses the full probe address each time, which is redundant. After initiating the process in slot 1, Basil only needs to send the last generated bit of the probe address, not the full address. This is because each sensor can track the outcomes and therefore the sensor knows what is its current position in the tree. For example, after the collision in slot 8, Basil sends only 0. The sensors know that the last received probe was addressed to 10, such that they append 0 and get the current probe address 100. After each receiving slot, Basil can send a feedback message to inform the sensors about the outcome in the previous slot, which can be collision (C), single (S), or idle (I). This is different from Figure 2.2, apart from the initial probe sent to all, where the probe sent by Basil tells who is eligible to transmit in the slot after the probe. It can be seen that usage of feedback instead of a probe leads to an equivalent result. For example, after the first slot, the feedback C denotes that there has been a collision and the next probe address is 0. As another example, the feedback messages received after the first four slots are C, C, S, C; this uniquely determines the next probe address to be 010.
The ideas behind random access with probing have led to the most efficient random access protocols that operate with the collision model, attaining throughput of more than 0.487 packets per slot. In practice, a limiting factor can be the feedback packet sent by Basil. For the explanation above we have assumed that the feedback is instantaneous, and it therefore does not affect the time efficiency/throughput of the random access protocol. On the other hand, probing algorithms use feedback messages very extensively and this must be taken into account when designing a practical random access/reservation protocol. Another remark is that each participant in a probing protocol should often switch between transmit and receive state. As mentioned in Chapter 1, such an operation may not be desirable, for example due to the fact that the switching takes time and therefore affects the throughput.
2.2.1 Combining ALOHA and Probing
One can easily think of creating new random access algorithms by combining the principles of ALOHA and probing. An advantage of framed ALOHA is avoidance of collisions and economic usage of feedback messages. ALOHA uses memoryless randomization: the random choice of a slot made to access at a given time is independent of the random choice made at another time. Contrary to this, probing or splitting tree algorithms create memory in the randomization process and utilize the history of collisions to resolve the set of colliding sensors more efficiently. Here is an example of what a hybrid ALOHA probing algorithm could look like. Basil sends a probe-to-all packet, which, instead of a single slot, is followed by a frame that has
2.3 Carrier Sensing
2.3.1 Randomization and Spectrum Sharing
Randomization is the key ingredient for solving the problem of uncoordinated access to a shared communication medium. We have seen its use in the rendezvous problem, where randomization helps to assign roles to two half-duplex devices that would like to talk to each other. In the random access algorithms from the previous section, randomization is used to resolve the conflict among devices that are transmitting to the same receiver.
The third case that requires use of randomized access over a shared wireless medium is depicted in Figure 2.3, where two independent links are in spatial proximity. Specifically, Zoya wants to transmit to Yoshi and Xia wants to transmit to Walt. This is often referred to as spectrum sharing, as it is necessary when the two collocated links use the same communication channel. Another common term to denote this situation is that both link operate at the same “frequency” or use the same “frequency channel”. The quotation marks are due to the fact that we have not yet introduced the concept of frequency, which will be done much later in Chapter 9. However, at this point it is sufficient to say that if the collocated links are using different frequency channels, then no channel is shared and there is no interference between the links. Contrary to this, the assumption for the scenario of Figure 2.3 is that all nodes used the same frequency channel and are in communication/interference range of each other. Furthermore, the scenario shows that communication happens in a specific direction, Zoya to Yoshi or Xia to Walt, while there is is no cross-communication between the devices that belong to different links, say Zoya and Xia. In Figure 2.3 there is no interfering line between Yoshi and Walt, although they are in range; the reason is that none of them acts as a transmitter. The bidirectional interference between Zoya and Xia does not mean that they simultaneously interfere with each other, but it shows the possible interference that can occur when one of them is transmitting and the other listening or receiving. If Zoya transmits, but Xia does not and is in listening mode, then Xia can overhear the signal and detect that there is a transmission. By reciprocity, the same happens when Xia transmits and Zoya listens.
The only way in which the two links Zoya–Yoshi and Xia–Walt can impact each other is through interference. In the framework of the collision model, if Zoya and Xia transmit simultaneously, then both Yoshi and Walt detect collisions and neither of them receives the desired packet correctly. The latter assumption is rather subtle, as if Zoya transmits and Xia is quiet, then Walt is able to overhear and receive the packet of Zoya correctly. Then why not use this overhearing to communicate coordinating messages between the two links? This is indeed possible, but in practice there can be collocated devices that are not logically connected and/or are not part of the same administrative network domain. It is thus viable to assume that data can be communicated only with a limited group of collocated nodes to which the observed node is networked, while all the other transmissions can be detected, but not used to extract data from them. However, it is important to note that if Walt is connected to Xia, but he overhears and detects packets from any arbitrary network nearby, then he may spend a substantial amount of battery energy to detect or receive packets he does not care about.
