Petar Popovski - Wireless Connectivity

In many cases the rendezvous problem can be solved by relying on a pre-established hierarchy or context. For example, in a conversation Basil can be the boss and Zoya an employee in a company that follows a (ridiculously) strict hierarchy. In that case, both of them know that Basil should start speaking and Zoya should listen before making any attempt to talk. Translating this idea of pre-established hierarchy into a wireless communication setting, Zoya can be a device/phone that wants to connect to the base station Basil. Then the phone can be preprogrammed to be in receiving mode and wait for an invite packet from a base station. Note that in this case the context breaks the symmetry between Zoya and Basil and thus pre-assigns the role that a device will have in trying to access the wireless medium. Basil can label the invite packet with his name or unique address, such that Zoya knows who sends the invite packet and can decide whether she wants to respond and connect to Basil.

In a more involved case, Zoya may be also in the communication range of another base station, named Bastian, see Figure 1.3(a). This second base station serves as an alternative to which Zoya can connect to in order to get access to the overall wired infrastructure and the internet. But what if Basil and Bastian send the invitation packets simultaneously? Then, following the rules of the collision model, Zoya experiences collision and she does not receive anything useful. An easy fix could be to have both Basil and Bastian to be part of a the same communication infrastructure, which makes it viable to assume that they can communicate and coordinate over a wired channel and thus agree not to send the invite packets simultaneously.

However, there may be cases in which Basil and Bastian cannot coordinate through the wired connection, since, for example, they belong to networks with different owners. Hence, the problem of collision over a shared medium remains. If both Basil and Bastian go on to persistently send invitation packets over regular time intervals, then it can happen that they are synchronized in an unfortunate way. This is illustrated in Figure 1.3(b), where it can be seen that Zoya will not ever receive an invitation. One quasi-solution that Zoya might contemplate would be the following. The clocks of Basil and Bastian cannot be perfectly synchronized, so if Zoya patiently waits, at some point in the future the regular packet transmissions from Basil and Bastian will avoid overlapping. We dedicate space to this quasi-solution in order to show why is it not a usable one and thereby illustrate an important engineering point. Namely, a good algorithmic design cannot rely on randomization that is not controlled in any way by the participants in the system. Instead, the (pseudo-)random choice used in the protocol should be deliberately invoked by the participating actors in the system. In this example, imperfect synchronization is due to random deficiency in the production process of the clocks and it thus represents an uncontrolled random factor.

Figure 1.3 The problem of first contact when the mobile device Zoya is in the range of two base stations, Basil and Bastian. (a) Illustration of the scenario. (b) The invite packets of Basil and Bastian are persistently colliding. (c) Solution of the problem of collision between Basil and Bastian by using randomization.

Let us now assume that the clocks of the two base stations are perfectly synchronized and they are both dividing the time into identical slots , as in Figure 1.3(c), where each slot is sufficient to send an invitation packet or receive a packet termed invitation_accepted from Zoya. Before the start of a slot, each base station flips a coin and decides randomly to transmit or stay silent in that slot. As shown in Figure 1.3(c), some invite packets will still collide, but some will be sent free of collision. Hence, the use of coin flipping leads to randomization of the transmission time between two invite packets. This randomization is the key to finalize the establishment of a contact, with high probability, within a reasonably short time.

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.