infinite, and each new request comes from a new sensor, which also means that each sensor has only one request. Such a hypothetical scenario represents the most difficult case for coordination among the sensors. In the following we provide the reasoning behind the choice of the infinite-size sensor population.
Instead of active sensors, each with a single request, we consider sensors, where each sensor has packets. The total number of packets to be sent in the system is , which makes the overall traffic load equal to the case with single-packet users. The following protocol is run by each sensor. The sensor Zoya applies the framed ALOHA protocol until it successfully sends her first request. After succeeding, Zoya records (a) the number of sensors that sent their first requests successfully before Zoya, which she learns from Basil's feedback; (b) puts on hold her access until the remaining sensors have sent their first requests successfully. Note that, after this randomized contention is finalized, Zoya has a unique number , where . Since every sensor applies the same protocol, each sensor has a unique token, which is a number between 1 and . After contending to send the first request and obtaining the token, the sensors no longer need to contend, but they are served through a TDMA frame with slots, where, for example, the slot number is allocated to Zoya. This is reminiscent of the use of random access as a technique for initial access, after which the transmissions are coordinated and scheduled.
When there are sensors with a single request each and goes to infinity, the system throughput is packets per slot, since the sensors need to contend indefinitely. Let now the 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
infinite, and each new request comes from a new sensor, which also means that each sensor has only one request. Such a hypothetical scenario represents the most difficult case for coordination among the sensors. In the following we provide the reasoning behind the choice of the infinite-size sensor population.
