Wireless Connectivity. Petar Popovski

Communication model used in this chapter, referred to as a collision model. (a) Simplified dependence between the data rate and the distance, denoting a communication range . (b) An example topology with possible wireless links among devices. The distance between two connected devices is at most . (c) Collision model at work for the topology in (b).

The assumptions of fixed-length packets and always-destructive collisions are weakening the analogy with a conversation. If we think to relate a packet to a spoken word, then not all words have the same length and missing some letters of a word may still not destroy its comprehensibility. In fact, the collision model is rather pessimistic. In reality, one expects a certain continuity in comprehensibility/correctness of a packet: if the packets and from Figure 1.1 have only a tiny overlap, then both would have to be received correctly by Yoshi. So, why are we not accounting for such a phenomenon and remain pessimistic about the collision? This is for pedagogical reasons in order to have a gradual path to system design and optimization. At the first step, make a system that works when every collision is identical and deemed destructive. In the next step, pose the question: what if not all collisions are identical? This leads to a refinement of the communication model by entering “inside the collision” and analyzing the different types of collision, which we will do in the later chapters. Notably, some types of collision will not be destructive and some collided packets can be received correctly, which sets the basis for optimizing the protocols further.

      1.1.3 Trade-offs in the Collision Model

      The basis of any good engineering is identification of the trade-off points that exist in a system: which benefits versus which costs are associated with given decisions on a system design. Even before discussing concrete techniques for accessing the shared medium, we can try to assess the limitations and the opportunities for protocol designs offered by the collision model. In that sense, it is at first instructive to look at the engineering trade-offs by contrasting the collision model with a model for wired communication.

      For the problem of establishing and maintaining links, the obvious advantage offered in the wireless setting is that the communication is untethered and links can be established flexibly between any two nodes that come into spatial proximity. The price of this flexibility is twofold:

       Resources (time, battery) need to be consumed in order to establish the link between two nodes.

       The link is not exclusively reserved for use between the two nodes, as a third nearby node may transmit on the same channel and thus cause interference.

      In contrast, in a wired model Zoya and Yoshi are connected by a dedicated cable. Precisely the lack of flexibility gives an advantage to the wired setting in certain scenarios. For example, consider the case in which Zoya and Yoshi are static devices and need to be able to reliably exchange extremely secure data, such as control data pertaining to a power plant. Then an investment in such a cable may be fully justified, despite the fact that the cable may be severely underutilized due to only occasional transmission of critical data.

The collision model captures the two essential wireless features, broadcast and interference. In Figure 1.2(a), Zoya, Yoshi, and Xia communicate with the base station (sometimes shortened to BS) named Basil. A base station can be seen as an entry point to an infrastructure through which Zoya, Yoshi, and Xia are connected to their communication peers. For example, consider the case in which Zoya wants to communicate with Walt. Zoya is in the range of the Basil, while Walt is in the range of a different base station, named Bastian. Then, Basil and Bastian are interconnected, most likely through a wired networking infrastructure, which allows transfer of data from Zoya to Walt and vice versa. In the sequel we will implicitly consider the fact that our users may want to communicate to their peers that are in the range of other base stations, but our focus will be on the communication between the users and a single base station.

Figure 1.2 Illustration of two essential wireless features captured by the collision model. (a) Broadcast. (b) Interference.

If Basil wants to send the same information to all three devices, a single transmission would suffice, since the three devices are within a distance smaller than . By contrast, if there were a wire between each device and Basil, then Basil should have sent each packet three times. Hence, wireless broadcast is cheap and this feature has been termed the wireless broadcast advantage. When we want to emphasize that the same message is sent to several devices, we will sometimes use the term multicast¹. Clearly, if Basil has different information for each device, the broadcast advantage disappears, at least in our simple communication model.

      When the communication takes part in the opposite direction, Figure 1.2(b), then the wireless broadcast advantage of the shared medium turns into a problem of interference. If the three devices transmit simultaneously, collision occurs and Basil does not receive anything useful. Therefore the devices should be coordinated in order not to transmit simultaneously and avoid collisions. This incurs certain coordination cost, spent on exchanging metadata. By contrast, the coordination cost is absent if each device has a dedicated wire to Basil, since he receives each signal over the wire. However, when calculating the grand total of costs, one has to account for the capital expenses incurred by installing the wires and, of course, the lack of flexibility inherent to a wired connection.

In summary, in the collision model broadcast can be an advantage, as all nodes in the range will perfectly receive the packet, while interference is always a disadvantage. In later chapters we will enhance the communication model by taking a magnifying glass and look what happens inside a collision. This will lead to a somewhat surprising conclusion that interference can be very useful.

1.2 The First Contact

      Back 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