should be interpreted as if Basil is inviting any sensor that has a data to send, to transmit in the slot that follows. This is certainly different from the framed ALOHA, where Basil assumes that there are active sensors and pre-emptively asks them to try to avoid the collisions by selecting randomly one of the multiple slots in a frame. If there is no sensor to transmit and , then Basil perceives an idle slot and he does not need to take action, except sending again a frame header at a future point in time. If then there is a single transmitting sensor, Basil receives the request successfully and sends acknowledgement (ACK). If , then Basil observes a collision. More importantly, Basil now knows that there are two or more sensors attempting to communicate with him, since in our model we assume that a collision is detected perfectly. The objective of Basil is to resolve this collision by running a protocol that will enable each of the sensors involved in this initial collision to send the data packet successfully at some later point in time.
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.2 only 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.2 can 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.2 has 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.2 have 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
should be interpreted as if Basil is inviting any sensor that has a data to send, to transmit in the slot that follows. This is certainly different from the framed ALOHA, where Basil assumes that there are 