Petar Popovski - Wireless Connectivity

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.

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 slots. Each sensor selects randomly a slot to send its packet. We can now interpret as a self-assigned random address, as we did in the probing algorithm. If Basil observes a collision in slot , then he proceeds to resolve this collision recursively. At first, he sends a probe addressed to the sensors that have collided in the th slot or, equivalently, all sensors that have self-assigned the address . This probe is followed by a frame with slots. Hence, the generalization is that a probe can be followed by more than a single slot. This would require generalization of the tree structure used to describe the basic probing algorithm.

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.3is 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.3there 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.

Figure 2.3 A simple scenario for sharing the wireless spectrum between two collocated links: Zoya–Yoshi and Xia–Walt. The assumption is that only Zoya and Xia can be transmitters.

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.

Figure 2.4(a)depicts a possible method for randomized spectrum sharing between the links Zoya–Yoshi and Xia–Walt, respectively, by assuming that both systems are synchronized at the slot level. Specifically, Figure 2.4(a)illustrates an example of execution of a transmission protocol for a given pattern of arrival of packets to Zoya, denoted by , and Xia, ( ). Upon experiencing a collision, such as and in the third slot, both Zoya and Xia apply randomization in order to decide in which slot each of them will retransmit the packet and , respectively. In this example, Zoya stays idle for two slots and only after that retransmits .