Читать книгу Wireless Connectivity - Petar Popovski - Страница 37

The question of choosing the optimal cannot be answered without providing additional elements of the model in which random access is used. To start with, we have not specified the random process that describes the way the sensors attempt to send their packets. The way to model this is to assume a random process that describes whether a sensor device has something to transmit in a given frame. In order to shed light on these issues, we can formulate a simpler problem that is still relevant for making the optimized choice of . Let there be active sensors with data to send among the population of sensors. Each active sensor is trying to send a reservation packet in one of the slots. It is important to state that the sensors are not mutually coordinated in any way before starting the random access process.

Having said that, there is a certain (dark room) symmetry in the problem: all the sensors look equal to the receiver and each of the reservation slots looks equal to each sensor. This means that, if a particular sensor Zoya needs to pick a single reservation slot, then each of the reservation slots should have an equal chance to be picked, with probability . Considering this, the probability that Zoya will have a successful transmission of her reservation packet in a particular slot is

(2.1)

which is the probability that Zoya sends in that slot and that none of the other sensors chose it for transmission.

The probability that there is a successful transmission in that slot by any of the sensors is:

(2.2)

It can be shown that the latter expression is maximized when . Hence, the best way is to choose the number of reservation slots to be equal to the number of active sensors that are contending via random access (framed ALOHA), such that the probability of successful reception in a given slot is:

(2.3)

Clearly, this requires knowledge of the number of active sensors in the total population of sensors.

Let us see the implications that this has on our system. Before the frame starts, Basil knows that there will be sensors that will be contending with each other in order to request access, but he does not know the identities of these sensors. Note that this is the crucial assumption in the problem setup for random access, since if Basil knows which sensors will require access, then there is no need for randomized contention: namely, Basil can simply set and allocate one data slot to each sensor. Although this observation seems trivial, it is very often overlooked when random access is considered in practical systems. Basil sets , but the number of sensors that successfully send reservation requests is random. This implies that the number of allocated slots is also random. The expected value of is , and one can use (1.8) to calculate the expected goodput in a frame.

Another observation is that decreases with and it reaches as the number of users goes to infinity. The engineering insight from is that, when the users are contending in smaller groups, then the probability of successful transmission experienced by an individual user is higher.

The assumption that Basil knows the exact value of is rather artificial. On the other hand, Basil may know some statistics about the random process according to which the sensors send reservation requests. In that case, it can be reasonable to conclude that Basil knows the expected value of . Although not mathematically rigorous, Basil can work with the expected value as if it is the exact value and use the following approach. At the start of th frame the expected number of sensors that require access, denoted by , is given by:

(2.4)

where is the expected number of new requests generated from new sensors in the previous, th frame. is the expected number of sensors that tried to send request in the previous frames, but did not succeed due to collision. If a frame becomes sufficiently long, then we can apply the law of large numbers, by which the expected values can be approximated as the exact values. For this to be true, the random arrival process of the requests from the sensors should satisfy certain conditions, which we will not discuss in detail here. It suffices to say that, for example, Poisson arrivals of requests over a sufficiently long interval would work. Going back to (2.4), we remove the averaging bar and recast the same equation as . Using the previous analysis on the probability of successful transmission of a request, we can express , but since is large, we can write , which leads to:

(2.5)

Hence, if Basil uses long frames and applies the law of large numbers, then he can have a good guess at the number of contending sensors and practically choose the reservation frame size in an optimal way.

The equation (2.5) can give us further very important insights into the random access protocols. Let us, for a moment, put aside the frame structure considered until now, in which Basil first lets the sensors contend using short reservation frames and then allocates data slots to the successful contenders. Instead, consider the following situation. A very large population of sensors is synchronized to Basil. A periodic frame of data slots and duration of is used, without any additional overhead at the frame start, since all sensors and Basil are assumed to be perfectly synchronized and thus have a perfect knowledge about the moment at which a frame starts. Each sensor that got data to send before the start of the th frame, chooses a random number between 1 and and sends its data in the th slot of the th frame. At the end of the frame, all sensors that sent data successfully receive feedback from Basil. This feedback is assumed to be sent extremely quickly, taking practically zero time. The sensors that did not send the data successfully, treat their data packet as a newly arrived one during the th frame and try again in the th frame. Looking again at the equation (2.5), we can interpret it as follows: if the number of newly arrived requests during each frame of duration is , then this number is equal to the number of successfully sent requests in a frame. Hence, the system is in equilibrium in the sense that each arrived request eventually gets served. Therefore the throughput of this system is, calculated in number of requests (packets) per unit time, is:

(2.6)

Note that, due to the absence of overhead, here the throughput is equal to the goodput. If we take , then the throughput is conveniently expressed in packets per slot and we arrive at the well known formula for maximal throughput of a slotted ALOHA system equal to packets per slot.

However, what does this theoretical value of the ALOHA throughput mean for a practical system? The randomized protocol coordinates the sensor transmissions, such that each sensor eventually transmits its request successfully. The presented analysis captures the following extreme case: the total population of sensors is very large, practically 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.