In this paper, we study contention resolution protocols from a game-theoretic perspective. In a recent work, we considered acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. One of the main results of ESA2016 was that no acknowledgment-based protocol can be in equilibrium. In fact, it seems that many natural acknowledgment-based protocols fail to prevent users from unilaterally switching to persistent protocols that always transmit with probability 1. It is therefore natural to ask how powerful a protocol must be so that it can beat persistent deviators. In this paper we consider age-based protocols, which can be described by a sequence of probabilities of transmitting in each time step. Those probabilities are given beforehand and do not change based on the transmission history. We present a 3-player age-based protocol that can prevent users from unilaterally deviating to a persistent protocol in order to decrease their expected transmission time. It is worth noting that the answer to this question does not follow from the results and proof ideas of ESA2016. Our protocol is non-trivial, in the sense that, when all players use it, finite expected transmission time is guaranteed. In fact, we show that this protocol is preferable to any deadline protocol in which, after some fixed time, attempt transmission with probability 1 in every subsequent step. An advantage of our protocol is that it is very simple to describe, and users only need a counter to keep track of time. Whether there exist @math -player age-based protocols that do not use counters and can prevent persistence is left as an open problem for future research.
There are various game theoretic models of slotted ALOHA that have been studied in the literature, apart from the ones mentioned in the introduction; see for example @cite_14 @cite_19 @cite_10 . However, in most of these models only transmission protocols that always transmit with the same probability are considered. There has been also research on pricing schemes @cite_1 as well as on cases in which the channel quality changes dynamically with time and players must choose their transmission levels accordingly @cite_16 @cite_4 @cite_25 . An interesting game-theoretic model that lies between the contention and congestion model was studied in @cite_0 ; where decisions of when to submit is part of the action space of the players.
@cite_14 @cite_4 @cite_1 @cite_0 @cite_19 @cite_16 @cite_10 @cite_25
1482267514 2527221766 2165944385 1977809285
We study distributed choice of retransmission probabilities in slotted Aloha under power differentiation. We consider random transmission powers and further study the role of priorities (through power control) given either to new arriving packets or to backlogged ones. We study both the cooperative team problem in which a common objective is jointly optimized as well as the noncooperative game problem. We show that the new proposed schemes not only improve the average performances considerably but are also able in some cases to eliminate the bi-stable nature of the slotted Aloha. 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. Aloha [1] and its slotted variant [2] are commonly deployed Medium Access Control (MAC) protocols in environments where multiple transmitting devices compete for a medium, yet may have difficulty sensing each others presence. This paper models and evaluates the throughput that can be achieved in a system where nodes compete for bandwidth using a generalized version of slotted- Aloha protocols. We evaluate the channel utilization and fairness of these types of protocols for a variety of node objectives, including maximizing aggregate throughput of the channel, each node greedily maximizing its own throughput, and attacker nodes that attempt to jam the channel. If all nodes are selfish and greedily attempt to maximize their own throughputs, a situation similar to the traditional Prisoners Dilemma[3] arises. Our results reveal that under heavy loads, greedy strategies reduce the utilization, and that attackers cannot do much better than attacking during randomly selected slots. 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. >