number of packets in the system go to infinity in a different way: the number of sensors is kept finite, but the number of packets per sensor goes to infinity, while having . Then the sensors waste some finite time to coordinate and obtain tokens, but after that they are served in TDMA frames ad infinitum, where each frame has a duration of slots and has successful transmissions. Thus the throughput of this latter system is, asymptotically, 1 packet per slot, much better than 0.368.
The infinite population assumption contains an inherent paradox. When the total sensor population goes to infinity, then the size of the address of each sensor, requiring bits, also goes to infinity. This implies that the size of each slot should increase to infinity in order to accommodate the address. Hence, if we insist that each sensor provides its address in the request, then the slot size cannot be fixed. The paradox stems from the fact that the analysis of ALOHA looks at the packet as a single, atomic unit of communication, not taking into account its internal structure. It is thus clear that, when the model for access protocol is enriched to reflect the internal packet structure, one cannot straightforwardly use the infinite population assumption.
One way to circumvent the paradox of the infinite population was devised by Polyanskiy in 2017. Consider an application that includes a large number of sensors in a certain field and the base station needs to compute certain functions where the sensor identification is irrelevant. This could be, for example, the average value of the sensor readings in the field. This means that the packet size does not need to grow with the population size and one can work with the assumptions of an infinite population.
2.2 Probing
In trying to optimize the frame size for framed ALOHA, we have used some favorable statistical assumptions that allow us to approximate the actual number with the expected number of contending sensors. However, these statistical assumptions may not always be valid. Consider, for example, a large set of wireless sensors, in which upon occurrence of some event, an unknown number of sensors gets activated and each activated sensor attempts to send a data packet. Such an event might occur very rarely and the number of activated sensors may vary significantly. It would not be feasible to wait for a long time in order to make the number of activated sensors statistically predictable, since this would incur intolerable delay. We therefore need to find a method that can deal with the situation in which an unknown number of sensors are trying simultaneously to send a packet/request to Basil.
We make a slight digression to our dark room metaphor to illustrate the problem addressed by probing. The reader can refer to the cartoon from the beginning of this chapter. There are people in a dark waiting room that has a door through which only a single person can pass at a given time. The people do not know each other from before (otherwise some hierarchy could have been established) and therefore do not talk to each other. Walt stands outside the waiting room and he should ensure that each of the persons in the waiting room should eventually come out of the door. Which strategy should Walt use? Clearly, if Walt knows the names of the people that are in the room, the problem is trivial as he would call each of them by name and get them one by one out of the waiting room. If Walt does not know them, then he should start by saying “one of you come out of the room”; however, the people in the dark room cannot make a mutual agreement who should be that one and the arbitration is left to Walt. Hence, this is an another instance of a multiple access problem that requires some form of random access.
Going back to our original multiple access problem, let us assume that, at a certain time instant, the base station Basil starts a multiple access frame by sending a packet that invites reservation requests. In the single reservation slot that follows all active sensors transmit their requests. For this discussion, it will be useful to think that the packet sent by Basil is a polling packet, containing the address ALL. This is not an address of a particular sensor, but it 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
