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

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.