Wireless Connectivity. Petar Popovski

address, as we did in the probing algorithm. If Basil observes a collision in slot , then he proceeds to resolve this collision recursively. At first, he sends a probe addressed to the sensors that have collided in the th slot or, equivalently, all sensors that have self-assigned the address . This probe is followed by a frame with slots. Hence, the generalization is that a probe can be followed by more than a single slot. This would require generalization of the tree structure used to describe the basic probing algorithm.

      

2.3 Carrier Sensing

      2.3.1 Randomization and Spectrum Sharing

      Randomization is the key ingredient for solving the problem of uncoordinated access to a shared communication medium. We have seen its use in the rendezvous problem, where randomization helps to assign roles to two half-duplex devices that would like to talk to each other. In the random access algorithms from the previous section, randomization is used to resolve the conflict among devices that are transmitting to the same receiver.

The third case that requires use of randomized access over a shared wireless medium is depicted in Figure 2.3, where two independent links are in spatial proximity. Specifically, Zoya wants to transmit to Yoshi and Xia wants to transmit to Walt. This is often referred to as spectrum sharing, as it is necessary when the two collocated links use the same communication channel. Another common term to denote this situation is that both link operate at the same “frequency” or use the same “frequency channel”. The quotation marks are due to the fact that we have not yet introduced the concept of frequency, which will be done much later in Chapter 9. However, at this point it is sufficient to say that if the collocated links are using different frequency channels, then no channel is shared and there is no interference between the links. Contrary to this, the assumption for the scenario of Figure 2.3 is that all nodes used the same frequency channel and are in communication/interference range of each other. Furthermore, the scenario shows that communication happens in a specific direction, Zoya to Yoshi or Xia to Walt, while there is is no cross-communication between the devices that belong to different links, say Zoya and Xia. In Figure 2.3 there is no interfering line between Yoshi and Walt, although they are in range; the reason is that none of them acts as a transmitter. The bidirectional interference between Zoya and Xia does not mean that they simultaneously interfere with each other, but it shows the possible interference that can occur when one of them is transmitting and the other listening or receiving. If Zoya transmits, but Xia does not and is in listening mode, then Xia can overhear the signal and detect that there is a transmission. By reciprocity, the same happens when Xia transmits and Zoya listens.

Figure 2.3 A simple scenario for sharing the wireless spectrum between two collocated links: Zoya–Yoshi and Xia–Walt. The assumption is that only Zoya and Xia can be transmitters.

      The only way in which the two links Zoya–Yoshi and Xia–Walt can impact each other is through interference. In the framework of the collision model, if Zoya and Xia transmit simultaneously, then both Yoshi and Walt detect collisions and neither of them receives the desired packet correctly. The latter assumption is rather subtle, as if Zoya transmits and Xia is quiet, then Walt is able to overhear and receive the packet of Zoya correctly. Then why not use this overhearing to communicate coordinating messages between the two links? This is indeed possible, but in practice there can be collocated devices that are not logically connected and/or are not part of the same administrative network domain. It is thus viable to assume that data can be communicated only with a limited group of collocated nodes to which the observed node is networked, while all the other transmissions can be detected, but not used to extract data from them. However, it is important to note that if Walt is connected to Xia, but he overhears and detects packets from any arbitrary network nearby, then he may spend a substantial amount of battery energy to detect or receive packets he does not care about.

Figure 2.4(a) depicts a possible method for randomized spectrum sharing between the links Zoya–Yoshi and Xia–Walt, respectively, by assuming that both systems are synchronized at the slot level. Specifically, Figure 2.4(a) illustrates an example of execution of a transmission protocol for a given pattern of arrival of packets to Zoya, denoted by , and Xia, (). Upon experiencing a collision, such as and in the third slot, both Zoya and Xia apply randomization in order to decide in which slot each of them will retransmit the packet and , respectively. In this example, Zoya stays idle for two slots and only after that retransmits .

      We can detect at least two inefficiencies created by the slotted structure:

       If a packet arrives after the start of the slot, then the node needs to postpone the first transmission of the packet until the start of the next slot, even if the previous slot is idle.

       Consider the collision between and . Although the packets have not arrived at the same time, both Zoya and and Xia need to wait until the start of the next slot. Thus, the slotted structure forces them to be sent at exactly the same time, which leads inevitably to a collision.

Figure 2.4 Illustration of randomized spectrum sharing between two interfering links, Zoya–Yoshi and Xia–Walt, respectively. Zoya and Xia are transmitters. The pattern of packet arrivals to Zoya () and Xia () is identical for both cases. (a) Slotted channel. (b) Carrier sensing solution, with a minislot duration being a third of the slot duration.

      2.3.2 An Idle Slot is Cheap

The key idea in overcoming these inefficiencies is to shorten the duration of the idle slot and introduce carrier sensing multiple access (CSMA). Figure 2.4(b) shows an example in which the idle slot duration is one third of the slot duration Скачать книгу