to the dark room analogy, we ask the question: how do two people, who have never met before, start to communicate when placed in a dark room? Reformulating this question in terms of wireless communication, we can ask: how do two wireless devices start to communicate? Who speaks first and who listens first? This is an important issue when the devices operate in a half-duplex manner, since a device cannot transmit and receive simultaneously. Before a packet from Zoya is sent to Yoshi, each of them needs to know that Zoya is about to transmit and Yoshi is about to receive. This may sound trivial and indeed it is, provided that we somehow let Zoya know in advance that she should take the transmitter role and Yoshi should take the role of a receiver. For example, if they have communicated in the past, then they may agree that, next time they are placed together in a dark room, Zoya takes the role of the one that starts to talk first. But, how do they know the roles if they have never communicated before? Let us explore this problem of first contact or rendezvous between two wireless nodes.
1.2.1 Hierarchy Helps to Establish Contact
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.
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.
1.2.2 Wireless Rendezvous without Help
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
