Recent work has shown that adaptive CSMA algorithms can achieve throughput optimality. However, these adaptive CSMA algorithms assume a rather simplistic model for the wireless medium. Specifically, the interference is typically modelled by a conflict graph, and the channels are assumed to be static. In this work, we propose a distributed and adaptive CSMA algorithm under a more realistic signal-to-interference ratio (SIR) based interference model, with time-varying channels. We prove that our algorithm is throughput optimal under this generalized model. Further, we augment our proposed algorithm by using a parallel update technique. Numerical results show that our algorithm outperforms the conflict graph based algorithms, in terms of supportable throughput and the rate of convergence to steady-state.
- Instantaneous channel gains are assumed to be known at each time slot. - Channel statistics (such as average channel gains or distribution) are assumed to be known. A time-varying channel is considered between the transmitter of a link and its corresponding receiver in @cite_9 . However, the channel gains between the interfering links are assumed to be static. In @cite_12 , time varying channels are considered among all the links, and the interference is modelled by a conflict graph. However, the algorithm @cite_12 can support only a fraction of the achievable rate region. A SIR model is considered in @cite_6 to a propose conservative algorithm that is suboptimal. An adaptive Aloha based algorithm is proposed in @cite_14 under time-varying channels. However the algorithm can only maximize some utility functions and is not throughput optimal.
@cite_9 @cite_14 @cite_6 @cite_12
1977809285 1988969816 1998010325 2527221766
The stability of the Aloha random-access algorithm in an infinite-user slotted channel with multipacket-reception capability is considered. This channel is a generalization of the usual collision channel, in that it allows the correct reception of one or more packets involved in a collision. The number of successfully received packets in each slot is modeled as a random variable which depends exclusively on the number of simultaneously attempted transmissions. This general model includes as special cases channels with capture, noise, and code-division multiplexing. It is shown by drift analysis that the channel backlog Markov chain is ergodic if the packet-arrival rate is less than the expected number of packets successfully received in a collision of n as n goes to infinity. The properties of the backlog in the nonergodicity region are examined. > This paper was originally distributed informally as ARPA Satellite System Note 8 on June 26, 1972. The paper is an important one and since its initial limited distribution, the paper has been frequently referenced in the open literature, but the paper itself has been unavailable in the open literature. Publication here is meant to correct the previous gap in the literature. As the paper was originally distributed only to other researchers intimately familiar with the area covered by the paper, the paper makes few concessions to the reader along the lines of introductory or tutorial material. Therefore, a bit of background material follows. ALOHA packet systems were originally described by Abramson ("The ALOHA System--Another Alternative for Computer Communication," Proceedings of the AFIPS Fall Joint Computer Conference, Vol. 37, 1970, pp. 281--285). In an ALOHA a single broadcast channel is shared by a number of communicating devices. In the version originally described by Abramson, every device transmits its packets independent of any other device or any specific time. That is, the device transmits the whole packet at a random point in time; the device then times out for receiving an acknowledgment. If an acknowledgment is not received, it is assumed that a collision occured with a packet transmitted by some other device and the packet is retransmitted after a random additional waiting time (to avoid repeated collisions). Under a certain set of assumptions, Abramson showed that the effective capacity of such a channel is 1 (2e). Roberts in the present paper investigates methods of increasing the effective channel capacity of such a channel. One method he proposes to gain in capacity is to consider the channel to be slotted into segments of time whose duration is equal to the packet transmission time, and to require the devices to begin a packet transmission at the beginning of a time slot. Another method Roberts proposes to gain in capacity is to take advantage of the fact that even though packets from two devices collide in the channel (i.e., they are transmitted so they pass through the channel at overlapping times), it may be possible for the receiver(s) to "capture" the signal of one of the transmitters, and thus correctly receive one of the conflicting packets, if one of the transmitters has a sufficiently greater signal than the other. Roberts considers the cases of both satellite and ground radio channels. We derive the closed-form delay distributions of slotted ALOHA and nonpersistent carrier sense multiple access (CSMA) protocols under steady state. Three retransmission policies are analyzed. We find that under a binary exponential backoff retransmission policy, finite average delay and finite delay variance can be guaranteed for G<2S and G<4S 3, respectively, where G is the channel traffic and S is the channel throughput. As an example, in slotted ALOHA, S<(ln2) 2 and S<3(ln4-ln3) 4 are the operating ranges for finite first and second delay moments. In addition, the blocking probability and delay performance as a function of r sub max (maximum number of retransmissions allowed) is also derived. An innovative iterative process is proposed to acquire the dynamic process of multichannel slotted ALOHA (S-ALOHA). It reveals the direct relation between the number of contending devices that perform their jth random access (RA) attempt at the ith RA slot and the newly arrived devices before the ith RA slot. These results allow engineers to analytically derive the probability density function of RA delay of multichannel S-ALOHA, as well as its cumulative density function and average value. Under stable RA attempts assumption, simplified form of the above analysis is given, with which we prove the number of preamble transmissions follows truncated geometric distribution. Taking the two traffic models proposed for machine type communications as examples, numerical results are presented to verify the effectiveness of the proposed iterative process and the accuracy of its simplified form, and illustrate the delay characteristics of simplified long term evolution RA channel.