Wireless Connectivity. Petar Popovski

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 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.

      The ideas behind random access with probing have led to the most efficient random access protocols that operate with the collision model, attaining throughput of more than 0.487 packets per slot. In practice, a limiting factor can be the feedback packet sent by Basil. For the explanation above we have assumed that the feedback is instantaneous, and it therefore does not affect the time efficiency/throughput of the random access protocol. On the other hand, probing algorithms use feedback messages very extensively and this must be taken into account when designing a practical random access/reservation protocol. Another remark is that each participant in a probing protocol should often switch between transmit and receive state. As mentioned in Chapter 1, such an operation may not be desirable, for example due to the fact that the switching takes time and therefore affects the throughput.

      2.2.1 Combining ALOHA and Probing

One can easily think of creating new random access algorithms by combining the principles of ALOHA and probing. An advantage of framed ALOHA is avoidance of collisions and economic usage of feedback messages. ALOHA uses memoryless randomization: the random choice of a slot made to access at a given time is independent of the random choice made at another time. Contrary to this, probing or splitting tree algorithms create memory in the randomization process and utilize the history of collisions to resolve the set of colliding sensors more efficiently. Here is an example of what a hybrid ALOHA probing algorithm could look like. Basil sends a probe-to-all packet, which, instead of a single slot, is followed by a frame that has slots. Each sensor selects randomly a slot to send its packet. We can now interpret