Читать книгу Wireless Connectivity - Petar Popovski - Страница 19

Things get more complicated when the roles of the devices are not predefined. This is the situation in establishing ad hoc links between two devices that belong to the same hierarchical level, as in device-to-device (D2D) communication. For example, Zoya, Yoshi, and Xia can be three mobile phones that want to start communication, but have never communicated with each other before. The last assumption is important, since if Yoshi and Xia have already communicated in the past, they may have agreed who should be the one sending the invite packet next time they need to communicate. In the absence of such a context, it is impossible to predefine the roles. For example, if Zoya and Yoshi are predefined to be the ones sending invite packets, while only Xia is waiting to receive them, then Zoya and Yoshi cannot establish a link between them. The problem of first contact when devices are symmetric is exacerbated by the half-duplex nature of devices: if Zoya and Yoshi are continuously sending invitations to each other, then neither of them is able to receive the invitation from the other one.

Coin flipping again helps to resolve this situation. Let us assume that Zoya and Yoshi have a common time reference for a slotted channel, as in the case with Basil and Bastian. Achieving the required synchrony is harder to justify in this case, compared to the example in which a device establishes connection with a base station. Nevertheless, for the purpose of this example, one can assume that both Zoya and Yoshi have GPS receivers that can be used for clock synchronization. Let both Zoya and Yoshi be quiet in the th slot, see Figure 1.4. Before the start of the slot , Zoya and Yoshi flip a coin and randomly decide to either send or listen for an invite packet. In the example in Figure 1.4, Zoya decides to transmit. Note that in the th slot Zoya must be in the “listen” state, since she should receive a invite_accepted packet in case Yoshi received Zoya's invite packet.

Figure 1.4 Rendezvous protocol for Zoya and Yoshi where both of them use half-duplex devices and their roles in the protocol are not predefined.

But what if Zoya and Yoshi are not synchronized in using the slotted channel; can that help or make things even more difficult? In fact, the synchronous case can be seen as the worst case: if both Zoya and Yoshi decide to transmit in a certain slot, then their packets are completely overlapping. On the other hand, the lack of synchronism can be helpful in breaking the symmetry between Zoya and Yoshi. For example, we can have the situation in which both Zoya and Yoshi decide to transmit, but the transmission slot of Yoshi starts slightly later than Zoya's slot. Yoshi starts to receive the invite packet and postpones his transmission in order to complete the reception of Zoya's packet. In this example, Yoshi adjusts its clock to Zoya and, after the invite packet is received, Yoshi sends back a reply using Zoya's slot timing. It can be seen that, when the devices are not in synchrony, the symmetry can be broken without using randomization, as some form of randomization is already embedded in the asynchronism. However, recalling our discussion on a proper protocol design and controlled randomness, asynchronism can facilitate the rendezvous protocol, but it should not be the definitive solution; the protocol should always have the opportunity to rely on an intentional randomized choice.

Through the problem of first contact and link establishment, we have introduced randomization as the key idea used in breaking the symmetry among different wireless devices that want to access the same shared medium. In the next chapter we will see that randomization can also be useful for efficient medium access after the links have been initially established.