Petar Popovski - Wireless Connectivity

Let us continue the example by taking and refer to Figure 2.2. For this example it is more convenient to denote the sensor devices as . After observing the initial collision, Basil sends again a packet to invite transmissions from the sensors. However, if Basil addresses the packet that invites all sensors to respond, the same collision will occur again. Therefore, randomization is needed and here is an idea of how it can be introduced. Basil now performs probing by sending a poll packet addressed to a sensor 0. Initially there is no sensor with address 0, entitled to respond to this packet. However, upon receiving the addressed polling packet from Basil, each of the eight sensors randomly tosses a coin, getting an outcome of 0 or 1, each with probability 0.5. For the example in Figure 2.2, the sensors obtained 0, while the rest obtained 1 as an outcome from the coin tossing. An interpretation of this random outcome is that each of the sensors randomly assigned to itself the address 0, while each of the other sensors randomly self-assigned address 1. In slot 2 in Figure 2.2only the sensors with address 0 are transmitting. Basil again observes collision, not knowing how many sensors are transmitting. For example, it could have happened that all eight of them toss coin 0, leading to a situation that is identical to that in slot 1. Yet, statistically speaking, with the first polling packet Basil manages to split the initial group of sensors into two approximately equal groups, such that the problem of resolving one large collision is divided into resolving two smaller collisions. This principle of using coin tossing to split a group of collided sensors into smaller groups can continue in a recursive fashion, until each group contains a single sensor (successful transmission) or no sensor (idle slot).

We continue with the example from Figure 2.2. Note that Basil's packet with address 0 is not exactly a poll packet, since there is no certainty that a sensor with self-assigned address 0 exists; this happens when all sensors have tossed 1. It is rather a probing packet or a probe , aiming to explore/learn about the set of contending sensors rather than letting the sensors transmit over a large interval in order to avoid collisions. The next probe sent by Basil has address 00, such that the sensors that have already generated address 0, and a coin toss is used in order to decide if the next bit of the address is 0 or 1. Now only the sensor has the address 00, such that it is the only one responding to the probe addressed with 00. The reader can continue to follow the full example in Figure 2.2. For example, there is no sensor that has a sequence of random outcomes 110, such that when the probe 110 is used in slot 12, Basil receives no response. The tree representation in Figure 2.2can be used to track the random outcomes based on the coin tossing. This is why these algorithms are sometimes referred to as splitting tree algorithms or simply tree algorithms.

Figure 2.2 An example of random access with probing. (a) Representation with a tree. The number in each circle is the time slot in which that tree node is visited. Each edge is labeled with the probe address that enables the next tree in the node. (b) Representation of the tree in time. Basil can receive three different outcomes: C (collision), S (single), I (idle). For each slot in which Basil receives, the set of transmitting sensors is put at the top. For example, in slot the sensors transmit and Basil receives collision (C).

The concept of probing does not need to be implemented by random coin tosses, it can also be run by using the actual addresses of the contending nodes, provided each node has a unique address. To see how this works, let us assume that each of the eight sensors from the example in Figure 2.2has a unique address and Basil knows that fact. Such an address, for example, can be hard-wired into the sensor and consists of a unique pattern of bits. Clearly, needs to be at least 3 for this example to work. The probes sent by Basil have the same content; however, now the sensor actions and the probe interpretation is different. For example, a probe with address 00 means “any sensor that has a unique address starting with 00 should transmit”.

An alternative view could be that the probing process creates temporary short addresses by which the nodes can be identified/polled within the communication process. For example, let each of the sensors in Figure 2.2have a unique, worldwide address that consists of 48 bits. Furthermore, let the sensors be in a sleep mode most of the time, such that the probing process is used to establish the initial contact with the sensors that have just woken up. In other words, the initial probe packet can be interpreted as “has anyone out there woken up”? After a sensor is awake, it may have multiple data exchanges within a short period. It should be noted that during the probing process, the sensors are allocated unique addresses: has the address 100, while has the address 11110. After the probing process, the base station can make the data exchange with the sensors by using these temporary addresses, which are much shorter than the unique 48 bit addresses.

We now look closer at the packets that need to be sent by Basil in order to run the splitting tree algorithm. In Figure 2.2, Basil uses the full probe address each time, which is redundant. After initiating the process in slot 1, Basil only needs to send the last generated bit of the probe address, not the full address. This is because each sensor can track the outcomes and therefore the sensor knows what is its current position in the tree. For example, after the collision in slot 8, Basil sends only 0. The sensors know that the last received probe was addressed to 10, such that they append 0 and get the current probe address 100. After each receiving slot, Basil can send a feedback message to inform the sensors about the outcome in the previous slot, which can be collision (C), single (S), or idle (I). This is different from Figure 2.2, apart from the initial probe sent to all, where the probe sent by Basil tells who is eligible to transmit in the slot after the probe. It can be seen that usage of feedback instead of a probe leads to an equivalent result. For example, after the first slot, the feedback C denotes that there has been a collision and the next probe address is 0. As another example, the feedback messages received after the first four slots are C, C, S, C; this uniquely determines the next probe address to be 010.