University of Ghana http://ugspace.ug.edu.gh
UNIVERSITY OF GHANA
Large Deviations of the Throughput in Multi-Channel Medium-Access Protocols
A thesis Submitted to the
Department of Statistics and Actuarial Science, School of Physical and Mathematical
Sciences, College of Basic and Applied Sciences, University of Ghana
Charles Kwofie
(10281223)
In partial fulfilment of the Requirement for the Award of
Doctor of Philosophy
in
Statistics
April, 2022
University of Ghana http://ugspace.ug.edu.gh
Declaration
I declare that the entirety of the work contained therein is my own, original work towards
the award of the PhD degree and that, to the best of my knowledge, it contains no material
previously published by another person nor material which had been accepted for the award
of any other degree of the university, except where due acknowledgement had been made in
the text.
Charles Kwofie            Kw.o. .f. .i.e. . .C. . .h.a. .r. .l.e. .s. 2.6. . O. .c. .to. .b.e. .r,. .2.0. .2.2
Student Signature Date
Prof. Dr. Wolfgang König . . . . . . . . . . . . . . . . . . . . . .2.6.  .O. .c. t.o.b. .e.r. .2.0. .2.2
Supervisor Signature Date
Prof. Kwabena Doku-Amponsah . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Supervisor Signature Date
October 26, 2022
Dr. Louis Asiedu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Supervisor Signature Date
ii
University of Ghana http://ugspace.ug.edu.gh
ABSTRACT
This thesis considers Aloha and slotted Aloha protocols as medium access rules for a multi-
channel message delivery system. Users decide randomly and independently with a minimal
amount of knowledge about the system at random times to make a sending attempt. The
system has a fixed number of available channels; equivalently, interference constraints make
the delivery of too many messages at a time impossible. We derive probabilistic formulas
for the most important quantities like the number of successfully delivered messages and the
number of sending attempts, and we derive large-deviation principles for these quantities in
the limit of many participants and many sending attempts. We analyse the rate functions
and their minimizers and derive laws of large numbers. In particular, we are interested in
questions like “if the number of successfully delivered messages is significantly lower than
the expectation, was the reason that too many or too few sending attempts were made?”.
The main tools are from the theory of large deviations.
University of Ghana http://ugspace.ug.edu.gh
Acknowledgments
I would like to thank God Almighty and everyone who contributed to the success of this the-
sis. More specifically, I thank Prof. Dr. Wolfgang König for his mentorship and direction.
I thank him for giving me the opportunity to work under his supervision for three years in
Berlin, Germany while providing the funding for my stay. I also do thank Prof. Kwabena
Doku-Amponsah and Dr. Louis Asiedu for their direction and dedication throughput this
thesis. I will also like to thank the BANGA-AFRICA project team for the Ph.D support.
iv
University of Ghana http://ugspace.ug.edu.gh
Contents
1 Introduction 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Objectives of the study . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Reseach questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Literature review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5.1 Interference constraint in telecommunication networks . . . . . . . 5
1.5.2 Capacity Constraints in Communication Networks . . . . . . . . . 6
1.5.3 Computing the expected number of transmitters in a wireless network 6
1.5.4 Throughput Properties of Telecommunication Networks . . . . . . 7
1.5.5 Medium access protocols . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.5.1 Aloha . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.5.2 Slotted Aloha . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.6 Applications of large deviations in wireless networks . . . . . . . . 12
1.5.7 Conclusion from literature review . . . . . . . . . . . . . . . . . . 13
v
University of Ghana http://ugspace.ug.edu.gh
1.6 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6.1 General overview of large deviations . . . . . . . . . . . . . . . . . 14
1.6.2 Cramér’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6.3 Contraction principle . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6.4 Sanov theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.5 Poisson Point Process . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.5.1 Standard Poisson Point Process . . . . . . . . . . . . . . 17
1.6.5.2 Random thinning of Poisson Point process . . . . . . . . 18
1.6.6 Legendre transformation . . . . . . . . . . . . . . . . . . . . . . . 18
1.6.7 Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . 19
1.6.8 Aloha/Slotted Aloha with interference constraint . . . . . . . . . . 20
1.7 Motivation and goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.9 Organisation of thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Large deviation for the joint probability of throughput in Slotted Aloha 26
2.1 Description of the models . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.1 Quantities and questions of interest . . . . . . . . . . . . . . . . . 28
2.2 Large deviation results for throughput . . . . . . . . . . . . . . . . . . . . 28
2.3 Proofs of the LDPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.1 Proof of Theorem 2.2.1 for l = 2 . . . . . . . . . . . . . . . . . . . 31
2.3.2 Proof of Theorem 2.2.1 for l = 1 . . . . . . . . . . . . . . . . . . . 36
vi
University of Ghana http://ugspace.ug.edu.gh
2.3.3 Identification of the rate function in Theorem 2.2.1 for l = 1 . . . . 38
2.4 Analysis of the rate functions . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.1 Description of the minimizer(s) a,s,r . . . . . . . . . . . . . . . . 40
3 Optimisation result for the throughput probability parameter (p) in Aloha/Slotted
Aloha 43
3.1 Optimal p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Conditioning the number of attempts on the number of successes . . . . . . 44
3.3 Optimizing p 7→ sp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4 Conditioning on successes . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4 Summary, conclusion and recommendations 52
4.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Recommendations for future research . . . . . . . . . . . . . . . . . . . . 54
4.3.0.1 Trajectory of messages . . . . . . . . . . . . . . . . . . 55
vii
University of Ghana http://ugspace.ug.edu.gh
List of Figures
1.1 Realisation of a Poisson Point Process. Source (Jahnel and König, 2020) . . 17
1.2 Device X j transmits to Xi with interference from other devices transmitting
to Xi. Source (Jahnel and König, 2020) . . . . . . . . . . . . . . . . . . . . 21
viii
University of Ghana http://ugspace.ug.edu.gh
Chapter 1
Introduction
1.1 Overview
The probabilistic analysis of large telecommunication systems is one of the cornerstones
of research towards developing new technologies in the telecommunication industry. In this
thesis, we consider capacity and connectivity of network protocols, where we consider users
located in space who intend to transmit messages to some intended receivers. The ubiqui-
tous questions are about connectivity and capacity, the two most important characteristic
quantities of telecommunication systems.
For many years, probabilistic tools with the help of random point processes and stochastic
geometry have been used successfully for the theoretical analysis of spatially distributed
wireless networks. However, in spite of these ideas, which obviously has a great potential
for technical progress, such kind of networks have hardly been established in reality yet. It
seems as though the precise set-up that makes the idea successful has not yet been identified.
A number of new questions arise for such kind of systems. The most obvious questions are
about connectivity, interference and capacity which are much more prominent problems.
One has to admit that the functionality of an ad-hoc multi-hop network has not yet been
1
University of Ghana http://ugspace.ug.edu.gh
sufficiently understood in terms of its consequences and properties.
There is not yet a sufficient understanding of the influence of the decisive parameters on the
performance qualities of telecommunication systems. In particular, sufficient reliable rigor-
ous research and resulting rules of thumbs are currently missing or have not yet been devel-
oped. Questions about the most important quantities like connectivity under the influence
of interference, network capacity under restrictions of storage size of the user equipments,
reach of message trajectories, algorithms for finding optimal routings, dependence on the
environment and more, still gives ample room for rigorous scientific research, notably for
mathematical research. In particular, research in the field of large deviations and stochas-
tic geometry are necessary. The seminal paper Gupta and Kumar (2000) (from the field of
information science), which is the first (to our best of knowledge) rigorous investigation of
capacity in a multi-hop system with unbounded number of steps and under the influence of
interference; provoked a lot of successive works in the sequel. In the use of large deviations
for analysing connectivity, not much has been done. Engineers who work in this area rely
mostly on simulations for drawing conclusions.
1.2 Problem statement
In telecommunication networks, specifically in the newly introduced 5G networks where
mobile and other devices are used as transmitters instead of base stations, many advantages
together with some disadvantages arise. There is the advantage of reducing cost when using
device to device (D2D) transmissions as it is not heavily dependent on costly infrastructure
installations. The question of connectivity however comes into play. This is due to the fact
that network connection depends on the availability of enough active devices in a vicinity.
There is also the question of how many hops should a typical trajectory make from a trans-
mitter to an intended receiver in comparison to Euclidean distance. There is also the problem
2
University of Ghana http://ugspace.ug.edu.gh
of optimal sending probability that network devices should allocate to individual devices in
order to achieve maximum throughput.
In addressing these issues, several researchers have looked at medium access protocols.
Some of these protocols are Aloha and its slotted versions, Carrier sense medium access
(CSMA) and other protocols that control how messages are sent out. In Ganti and Haenggi
(2009), it is assumed that network nodes form a Poisson Point Process (PPP) on a plane.
Time is divided (slotted) and at every time slot, each node transmits with probability p.
Further it is assumed that a node x can transmit to a node y only if B(y,β |x− y|) for β > 0
contain no other transmitting node. Here B(y,r) represents a ball centered around y with
a radius of r. Like many other research, Aloha models considered allow messages to be
transmitted independently with probability p without considering interference and capacity.
However, most messages fail to be transmitted due to interference or capacity constraints.
It is therefore important to consider the introduction of interference or capacity constraints
in these models hence computing the network connectivity metrics using appropriate math-
ematical tools in order to assess the quality of the protocol/strategy. It is clear that, due to
interference constraints or restricted availability of communication channels, the task can
be successfully managed only if a suitable rule is enforced that will regulate which of the
many messages is gaining access to the medium at a given time. Clearly, this rule should be
as simple as possible, and it should not require much infrastructure.
To this end, this research seeks to introduce capacity constraint into the ALOHA and slot-
ted ALOHA models and study their connectivity metrics using large deviations. A similar
constraint was introduced by König and Tóbiás (2019) in the Gibbsian model with the sim-
plicity that the interference/capacity constraint is only present at the first hop of message
transmission (Also see Munari et al., 2013). This research however, looks at a more re-
alistic fact that at every hop there is an interference/capacity constraint which should be
managed.
3
University of Ghana http://ugspace.ug.edu.gh
1.3 Objectives of the study
The main objective of the thesis is to study probabilistic random protocols for message tra-
jectories in telecommunication networks with capacity constraints. The specific objectives
are;
• Propose random protocols/strategies for describing message hops in wireless net-
works under capacity constraint.
• Derive large deviation principles for the proposed random protocols/strategies.
• Derive minimisers for the large deviation rate functions.
• Describe and analyse the conditions for attaining maximum throughput and the unique-
ness of the throughput probability parameter.
1.4 Reseach questions
The following are the research questions;
• What probabilistic models could provide us strategies to describe message hops in
wireless networks under capacity constraint?
• To what rates and rate functions would the probabilistic models be satisfying large
deviation principle (LDP)?
• What are the minimisers for the rate functions?
• Is there an optimal throughput probability parameter? If any, is it unique?
4
University of Ghana http://ugspace.ug.edu.gh
1.5 Literature review
1.5.1 Interference constraint in telecommunication networks
The study of interference using large deviations was championed by Torisi and co-authors
under different network settings (see for example, Ganesh and Torrisi, 2008; Torrisi and
Leonardi, 2012; Leonardi and Torrisi, 2013).
Interference limits the capacity of networks thereby resulting in many frustrated users. Ca-
pacity of wireless networks which is the focus of this thesis is a form of interference which
limits the number of messages that can be transmitted (throughput) at any point in time.
There has been efforts in literature to study the behavior of interference with respect to dif-
ferent point process which determines how nodes of a network are distributed. Throughput
probability in networks is influenced by the mutual interference among simultaneous trans-
missions over the same physical channel (See for example, Hunter et al., 2008; Torrisi and
Leonardi, 2012)
Leonardi and Torrisi (2013) studied the tail behaviour of interference in networks whose
nodes are distributed according to a Ginibre process over a bounded region in a plane. They
assumed different distributional assumptions for the fading variable. Their results shows
that, the dependence of interference on network nodes depends heavily on the distribution
of the fading variable. Ganesh and Torrisi (2008) studied the behaviour of interference in
wireless networks using large deviations. They described the network nodes by homogenous
Poisson point process with random transmission powers (a combination of fading and path
loss function).
These studies made different assumptions for the fading variable and leaves it open for a
more general fading or power variable. Also, the distribution of network nodes can be
extended to several other processes like the Matern process, the Cox point process and
5
University of Ghana http://ugspace.ug.edu.gh
others. It could also be studied for a more general point process. In this thesis, network
nodes form a Poisson point process.
1.5.2 Capacity Constraints in Communication Networks
With limited resources notwithstanding, the performance of communication networks are
required to operate at optimum levels. Capacity constraints in communication networks
has received maximum attention in relation to how to optimize resources and maximize the
utility of transmission Li et al. (2017). Capacity crunch, which is associated with commu-
nication networks has shown to perform at a constrained capacity due to the exponentially
increasing traffic demands. According to Ellis et al. (2016), communication networks need
modest changes and optimisation solutions. In the study of Frank and El-Bardai (1969), they
investigated the problem of finding best possible message routings that minimize network
losses subject to network capacity constraints.
There is a general consensus on the need to find optimisation solutions to improve network
capacity without necessarily expanding infrastructure due to budget constraints.
1.5.3 Computing the expected number of transmitters in a wireless
network
It is believed that interference/capacity constraint is a performance-limiting factor in wire-
less networks. One-shot scheduling of wireless network capacity has been a major problem
in network protocols. In computing the expected number of transmitters that will maximize
wireless network capacity, Dinitz (2010) developed a technique from machine learning and
game theory. Their method saw some improvement in network protocols but still lacked a
lot of randomness and could have some problems with implementation.
Multi-channel wireless Networks are known to have connectivity and capacity constraint
6
University of Ghana http://ugspace.ug.edu.gh
problems. In identifying and addressing performance of multi-channel network under chan-
nel constraints, Bhandari and Vaidya (2007) analysed capacity and connectivity metrics
of a wireless network. Key was assessing the optimal number of transmitters for optimum
throughput. However, the network structure they studied comprised of n randomly deployed
nodes with only single channel or interface. This thesis, studies a slightly different regime
with multiple channels each having an upper bound for number of allowable messages that
can be transmitted at a given time.
1.5.4 Throughput Properties of Telecommunication Networks
Improving transmission efficiency within wireless telecommunication by avoiding trans-
mission collision has been a research need (Dumas et al., 2021; Khan et al., 2021). Aloha
protocol was developed to transmit data packets to nodes but usually results in collision.
According to Khan et al. (2021), the efficiency of Aloha is twice less than slotted Aloha.
According to (Dumas et al. (2021)), slotted Aloha was introduced because of the challenges
identified with the Aloha protocol. Slotted Aloha defines slots of packets transmission to
improve transmission efficiency .
1.5.5 Medium access protocols
Medium Access Protocols such as Aloha are very important in the successful deployment
of wireless networks. In most protocols users manage resources in a decentralized manner
(Haykin, 2005; Neel et al., 2002). There are several papers on designs of medium access
protocols and how the existing ones can be improved to increase connectivity. The most
basic protocol is the Aloha with its existing extensions such as the slotted Aloha. Different
tools have been used to study connectivity properties such as expected number of successful
transmissions, optimal transmission probability and number of collisions.
7
University of Ghana http://ugspace.ug.edu.gh
1.5.5.1 Aloha
Aloha is known to be the first random access protocol that was developed for communication
networks (Médard et al., 2004). The quest to raise the performance of Aloha led to the
design of slotted Aloha. In analyzing the performance metrics of Aloha and slotted Aloha,
different flexible versions have be proposed and some attempts have been made to compute
closed form expressions for their connectivity properties. However, in most cases engineers
rely on simulations to study network metrics such as throughput.
Several papers have looked at different variants of the Aloha model under varying network
assumptions. In Błaszczyszyn and Mühlethaler (2015), mobile ad-hoc network nodes com-
prising of transmitters and receivers are fixed and only the Medium access control (MAC)
status evolves over time. Also, in Blaszczyszyn et al. (2012) receivers and transmitters are
nearest neighbours forming a Poisson process with a key assumption that locations of the
nodes are static.
Baccelli and Singh (2013) also studied spatial Aloha in which the medium access probability
(MAP) of nodes is adapted to the local topology of their local environment. Achir et al.
(2016) compared the performance of CSMA and spatial Aloha by computing their spatial
throughput using stochastic geometry. In carrying out the comparison, both schemes are
optimized by adjusting their parameters. The transmission probability for spatial Aloha is
said to be adapted, whereas for spatial CSMA a suitable carrier sense threshold was found.
Xu et al. (2018) considered a maximization of the so called α-fair utility in a spatial Aloha
network. This network consisted of multiple transmitter-receiver (TR) pairs each forming a
bipolar Poisson process. Communication is possible between pairs if signal to interference
ratio criteria holds. They then try to optimize the medium access probability of each pair.
They claim the model results in an optimization problem which is not straight forward to
solve.
8
University of Ghana http://ugspace.ug.edu.gh
1.5.5.2 Slotted Aloha
Ma et al. (2008) used the slotted Aloha MAC protocol in implementing a system where
transmission in a slot is dependent on the success of a nodes prior transmission. Using
Markov chains, the throughput of the model was then studied. Jakovetić et al. (2014) con-
sidered the so called framed slotted Aloha. In this model, base stations collaborate to receive
messages from some users. Within a communication radius r, transmitted messages are de-
coded by all base stations at each time frame.
Also, Gau (2006) considered slotted Aloha in interference induced network. He argued that
an interference dominating network is a network that can simultaneously receive a number
of messages from several transmitters, as long as the Signal to Noise and Interference Ratio
(SINR) condition is satisfied. He employed discrete-time Markov chain for the analysis.
Li and Dai (2015) studied the performance of slotted Aloha networks. They considered a
slotted Aloha model in which n nodes transmit to a single receiver with a perfect feedback
after each transmission.
Some papers also focused on situations where the medium access probability adapts to the
environment of the transmitting node. Hsu et al. (2012) worked on channel state informa-
tion (CSI) in slotted Aloha where users are aware of their CSI. This model consist of N
homogenous users who transmit messages to a common base station. Messages at one time
slot are sent and the CSI is the SINR that is received. Users know their own CSI and as such
adjust their transmission probability at the beginning of each time slot.
Lee et al. (2017) also studied spatial slotted-Aloha protocol in wireless networks. They
proposed a slotted-Aloha medium access protocol with optimal transmission probability
where each member of the network had its own transmission probability.
Coupechoux et al. (2004) analysed throughput of a multihop wireless network, where nodes
transmit according to a slotted ALOHA protocol. They derived formulas for throughput
9
University of Ghana http://ugspace.ug.edu.gh
given that n messages are transmitted in a given neighbourhood with a receiver only able to
decode k messages at a time. This is similar to the objectives of this study with the major
difference being the mathematical tool and the quantities of interest used.
Using slotted Aloha as the medium access control and choosing an optimal transmission
probability, the downward and upward link transmissions were studied using stochastic ge-
ometry. The proposed scheme ensured that the transmission probability depended on each
transmitter in a group. Poisson point process was used to obtain network connectivity met-
rics for downward and upward links (Lee et al., 2017).
Several designs of slotted Aloha has indeed been proposed in literature. Bajović et al.
(2014), made use of the slotted Aloha protocol. At each slot, network devices attempt to
transmit their messages with some given probability. They analysed slotted and framed
aloha in multiple base station and multiple-access systems. They analysed how at each slot,
devices independently transmit messages with a certain probability. At a distance r, the
messages can be intercepted by base stations. They designed it such that base stations and
users are placed uniformly at random. This thesis also adopts a similar concept where users
and time slots are uniformly distributed. Result of the performance metric of this study is
based on simulations.
Yavascan and Uysal (2021) studied a modified version of slotted Aloha called threshold-
Aloha where each terminal suspends its transmissions until the number of senders reach a
certain threshold. Once number of senders reaches the threshold, transmission attempts are
made with a constant probability in each slot, as in standard slotted Aloha. They then studied
the performance metrics of this modified threshold slotted Aloha using Markov chains.
Munari et al. (2013) introduced and analysed a simple variation of the Slotted Aloha. The
modification they did was to add multiple receivers in a way that several messages can be
transmitted by a user in one slot similar to the concept in this thesis. However, for each node,
the transmitted messages in each slot are assumed to be subject to only one-off independent
10
University of Ghana http://ugspace.ug.edu.gh
fading. They now compute closed form expressions for throughput and arbitrary number of
users. They also demonstrated through simulations that this method produces better output
than the standard slotted Aloha under similar conditions.
Given the massive interest in improving the efficiency of protocols with multiple users,
Munari et al. (2020) analysed the potential of a simple slotted Aloha by assuming that there
are multiple users. They characterized the performance matrix of this approach using the
binomial theorem and simulations. In Yang et al. (2015), similar to the concept in this thesis,
messages were allowed to be simultaneously transmitted in each time slot. They analysed
the performance of such an approach by generalizing the tree based approach. However, the
conclusions of the study relied on simulations.
Fereydounian et al. (2019), studied the Coded Slotted Aloha (CSA) by analysing its perfor-
mance in the non-asymptotic regime. Here they assumed that number of users and frame
length are finite. They established scaling laws and non-asymptotic relationship between
the channel load, probability of error and the number of users. Umehara et al. (2018) also
proposed a variant of slotted Aloha they called non-persistent slotted Aloha (SAloha). They
showed that some tweaks in the standard Aloha could produce better performance and en-
hance connectivity in wireless networks.
Umehara et al. (2018), studied the advantages of the so called enhanced Slotted aloha which
is known to reduce the probability of collision by 0.90 over other old versions of slotted
Aloha. This clearly shows how there exist different version of the slotted Aloha and as such
the renewed interest in research on mathematical formulations for such protocols.
Eroğlu and Onur (2021) proposed a version of the Slotted ALOHA Protocol called the den-
sity aware Slotted Aloha. This protocol ensures that the network density dictates a certain
dynamic random access probability for each of the nodes in accessing network channels.
Using Monte-Carlo simulations, they compared the performance of this approach to other
existing variants of slotted Aloha. These other versions are the stabilized Slotted Aloha and
11
University of Ghana http://ugspace.ug.edu.gh
the standard Slotted Aloha.
1.5.6 Applications of large deviations in wireless networks
Several research papers have used large deviation theory in studying rare events. In wireless
networks were this thesis is applied, there are different sub-areas such as malware propaga-
tion and other host of applications. Malware propagation is one area in wireless networks
that is also gaining momentum.
The main motivation to discuss applications of large deviations in relation to wireless net-
works is its importance in analysing of rare events (example bad system quality which rarely
happens). That is, events of the form Yn ∈ B on which, for example, there is too much inter-
ference or bad connectivity. Such an event is known as a frustration event and it is of great
importance in telecommunication theory. Similarly, situations where there is often good
events can also be analyzed. Hence, in most fields and wireless networks which is the focus
of this thesis, one is faced with typical questions like:
• what is the typical behaviour of Yn on this event?
• what is the size of the probability of this event?
Question two investigates the behavior of Yn under the conditional measure P(.|Yn ∈ B). The
most obvious reaction is to first guess that on the set B, Xn should converge to the minimizer
of I(rate function). Interestingly, this assertion is true in several instances. However, the
correct formulation will require further assumptions on B. Usually, proofs for cases like this
differ from situation to situation under different assumptions. The most obvious and typical
technique would be to first show that I has just one minimizer yn on B (Jahnel and König
(2020)).
12
University of Ghana http://ugspace.ug.edu.gh
1.5.7 Conclusion from literature review
The question of cost comes into play as we may want to reduce cost as much as possible.
Hence designing protocols that do not rather lead to increase in number of base stations
while maintaining high throughput is of utmost importance.
Connectivity properties of wireless networks have been widely studied by engineers who
rely heavily on simulations for drawing conclusions. Quite recently, mathematicians and
statisticians have taken keen interest in deriving more tractable formulas for understanding
the connectivity properties of medium access protocols using large deviations. For example,
König and Tóbiás (2017) and Hirsch et al. (2016) used large deviations to study frustration
probabilities in wireless networks. In a similar fashion, this thesis which is a motivation
from the work of König and Tóbiás (2017) and Munari et al. (2013), this research uses
large deviation to extend the notion in the paper to situations where interference/capacity
constraint is analysed in a more realistic fashion.
1.6 Methodology
The mathematical concepts used in this research are described in this section. In particular,
large deviation theorems and Poisson point processes are presented. The proof of Theorem
2.2.1 relies both on the Cramér and the Sanov theorem hence they are discussed in detail in
this section. The contraction principle that is utilised in one of the proofs in section 2 and
3 is also discussed. The chapter begins with a formal definition of large deviation principle
and then the most relevant theorems used in the study are presented.
13
University of Ghana http://ugspace.ug.edu.gh
1.6.1 General overview of large deviations
Definition 1.1. A rate function I is a lower semicontinuous mapping I :X → [0,∞] such
that for all α ∈ [0,∞), the level sets ΨI(α) = {x : I(x)≤ α} is a closed subset ofX .
Definition 1.2. A sequence ofX -valued random variables YN with law PN satisfies a large
deviation principle with rate function I, if for any open subset G and closed subset F ofX
( )
1
limsup logPN YN ∈ F ≤−infI, (1.6.1)
N→∞ N ( ) F
1
liminf logPN YN ∈ G ≥−infI. (1.6.2)
N→∞ N G
(Zeitouni and Dembo, 1998). This statement is the definition of large deviation principle
in a more general setting and can be adapted in a variety of ways similar (For example the
definition presented in Chapter 2 ). Below are the relevant theorems that were used in the
analysis of the network protocols presented in Chapter 2 and 3.
1.6.2 Cramér’s theorem
The Cramer theorem which forms the basis of the proofs presented in Theorem 2.2.1 is
discussed below.
Let the i.i.d random variables Y1,Y2, · · ·Yn with Y1 distributed according to the probability
law µ be given. One can then define the mean of n of these random variables, where n ∈N,
as S 1 nn = n ∑k=1Yk. Let µn be defined as µn(A) = P[Sn ∈ A] where A ∈B(R) and (P) is a
probability measure onB.
To introduce the Cramér theorem, the Fenchel-Legendre transform and the cumulant gener-
ating function (CGF) is briefly introduced. Now let, the CGF associated with the probability
14
University of Ghana http://ugspace.ug.edu.gh
measure µ be define as:
Λ(λ ) := logM(λ ) := logE[eλY1] (1.6.3)
Definition 3.2. The Fenchel-Legendre transform of Λ (defined in (1.6.3)) is given as
Λ∗ : R−→ R∪{∞}, Λ∗(y) = sup{λy−Λ(λ )} (1.6.4)
λ∈R
for all y ∈ R
Theorem 1.6.1. (Cramer’s theorem). Let X be a topological space and (Yn)n∈N be a
sequence of X -valued i.i.d random variables. (µn)n∈N which is a sequence of measures
satisfies an LDP with convex rate function Λ∗(.) such that;
1. For any open set G ⊂X
1
liminf log µn(G)≥− inf Λ∗(x) (1.6.5)n−→∞ n y∈G
2. For any closed set F ⊂X ,
1
limsup log µ (F)≤− inf Λ∗(y) (1.6.6)
n−→∞ n
n
y∈F
1.6.3 Contraction principle
The contraction principle is mentioned in the proof presented in Section 2.3.3 of the alter-
native proof presentation of l = 1 for Theorem 2.2.1.
Theorem 1.6.2. (Contraction principle). Let ψ : A −→ B be continuous where A and B are
Polish spaces. Let the finite measures µn on A satisfy an LDP with good rate function J and
speed sn. Then µ ◦ψ−1n (the image measures) also satisfies an LDP with speed sn and good
15
University of Ghana http://ugspace.ug.edu.gh
rate function I given by
I(y) = inf J(x) (y ∈ B), (1.6.7)
x∈ψ−1({y})
where infx∈0/ J(x) := ∞
1.6.4 Sanov theorem
The proof of the alternative formulation for Theorem 2.2.1 found in section 2.3.3 is based
on the Sanov theorem below.
Theorem 1.6.3 (Sanov’s theorem). Let the random variables (Xk)k≥0 be independent and
identically distributed taking values in a Polish space A, with common law µ . Further let
1 n
Mn := δn ∑ Xkk=1
with n≥ 1 be the empirical laws of the random variables (Xk)k≥0. Hence, the laws P(Mn ∈ .)
satisfy a large deviation principle with rate function H(.|µ) and speed n. Where, P(Mn ∈ .)
is a probability law on the Polish space M1(A). M1(A) are probability measures on A,
equipped with the weak convergence topology.
Proof of the Cramer theorem, Sanov theorem and the contraction principle can be found
in several standard large deviation books such as (Zeitouni and Dembo, 1998). Hence the
proof are not presented in this thesis.
1.6.5 Poisson Point Process
Poisson point process (PPP) is a random point process with intensity measure µ (consider-
ing µ to be a measure on B) such that, for any m ∈ N and any measurable pairwise disjoint
16
University of Ghana http://ugspace.ug.edu.gh
subsets A1, · · · ,Ak of B having finite µ measure, the counts Φ(A1), · · · ,Φ(Am) of the ran-
dom points in the respective sets A1, ....,Am are independent Poisson random variables with
µ(A1), · · · ,µ(Ak) as parameters respectively, i.e., if for all n1, · · · ,nm ∈ N0.
m [ ]
· · · ∏ −µ(A ) µ(Ai)
ni
P(Φ(A1) = n1, ,Φ(Am) = n ) = e ik . (1.6.8)
i=1 ni!
The standard Poisson point process briefly discussed below is referred to in the proof of
Lemma 2.3.1.
1.6.5.1 Standard Poisson Point Process
The standard Poisson point process corresponds to B = Rd with intensity measure λdx and
intensity λ ∈ (0,∞). The measure dx is stationary, with an underlying random point pro-
cess which is also stationary and often referred to as a homogeneous PPP. Every stationary
Poisson point process has a shift invariant measure. Additionally the distribution of this
process is isotropic. This means that it is rotationally invariant. This is a very important
characteristics of Poisson point process which makes it easier and friendly to work with.
Figure 1.1: Realisation of a Poisson Point Process. Source (Jahnel and König, 2020)
17
University of Ghana http://ugspace.ug.edu.gh
1.6.5.2 Random thinning of Poisson Point process
Let µ be the intensity measure of the Poisson point process Φ = (Xi)i∈I . Given Φ and
with probability 0 ≤ p ≤ 1, a subset of the points Xi can be independently selected. Once
the selection is done independently, the selected points of Xi also form a PPP with pµ as
intensity measure . A prove of this assertion is quite straight forward and can be found
in for instance (Jahnel and König, 2020). The proof will not be presented here. Now, in
relation to telecommunications and particularly, the ALOHA protocol (discussed in 2.3.1
), devices independently chooses to transmit at a given time instant hence the property of
point processes is not lost. Network devices are assumed to be identically distributed hence
device positions can be seen to form a Poisson Point Process as the thinning property is
preserved.
1.6.6 Legendre transformation
Legendre transforms are important in large deviations theory. They describe the rate func-
tions using moment generating functions. Definition of Legendre function can be found in
Definition 3.2. Below is a description of the legendre transform of the Poisson distribution.
The rate function of the Poisson distribution was directly used in the proofs presented in
Section 2.3.
• Poisson distribution. Given that Y is a Poisson distribution with parameter λ , then
we have that the moment generating function of Y is given by M(θ θ) = ee λ−λ . Then
the associated Legendre transform is given as
θ
I(b) = sup (bθ − (ee λ−λθ ))
We obtain the optimal θ ∗ = log(b/λ ) and I(b) = b log(b/λ )− (b−λ ) after setting
18
University of Ghana http://ugspace.ug.edu.gh
the derivative of I(b) with respect to θ to zero for b > λ . Hence large derivations
would predict that on the exponential scale,
∑
P( 1≤i≤n
Yi
> b)≈ e−(b log(b/λ )−b+λ )n
n
For the Possion distribution also, one can explicitly compute the large deviations probability.
Even for the sum Y1 + · · ·+Yn of Poisson random variables, one can still compute the large
deviation probability easily since the sum is also Poisson with parameter λn. That is,
( )
∑ (λn)
m
P yi > an = ∑ e−λn
1≤i≤n m>bn m!
It is still a bit tedious to infer explicit rate of decay of certain distributions but they can be
used as and when needed. In this research, the rate function of the Poisson distribution and
the binomial distribution are quoted and used in proves.
1.6.7 Law of Large Numbers
Law of large numbers was derived using the minimisers of the large deviation rate functions
(See corollary 2.2.2).
Theorem 1.6.4. Let Y1,Y2, · · · ,Yn be independent trials, with finite expectation µ = E(Yj)
and finite variance σ2 =V (Yj). Let Sn = Y1 +Y2 + · · ·+Yn. Then for any ε > 0.
( )
|SP n −µ| ≥ ε → 0, as n → ∞.
n
Equivalently, ( )
P |Sn −µ|< ε → 1 as n → ∞.
n
Proof for the above theorem can be found in standard statistical textbooks hence the proof
19
University of Ghana http://ugspace.ug.edu.gh
is left out.
1.6.8 Aloha/Slotted Aloha with interference constraint
In the classical ALOHA protocol each sender flips a coin and with probability p decides
to send independently of all other users. The message success depends on the interference
constraint. A message from transmitter Xi is successfully sent to receiver y in a reference
time slot if;
ℓ(∥Xi − y∥)SINR(Xi,y,X) = ≥ τ (1.6.9)N0 +∑ j∈I\{i} ℓ(∥X j − y∥)
and unsuccessful if SINR(Xi,y,X) < τ . Where X is the set of attempting participant at
a time instant with Bernoulli probability p. The function ℓ(∥.|) is the path loss function
that describes how the signal strength of transmission decreases with distance. The term
in (1.6.9) is the quotient of the strength of the signal transmitted from Xi received at y and
the sum of the strengths of all the signals sent out by any user received at y. An example
of ℓ is ℓ(r) = r−α for some α > d. Thorough treatment of interference through the SINR
constraint can be found in (Jahnel and König, 2020).
This thesis looks at a transformation of the SINR constraint into a simple capacity constraint
that a message is successfully sent if the number of attempting transmitters at a time instant
is ≤ 1/τ = κ .
The figure below demonstrates how interference can be caused by neighbouring devices and
as such sabotage the transmission of a transmitted message.
The precise choice of the interference term for any hop is not fixed, as there are some
options, depending on the situation that one wants to model. For example, it is discussable
to use the interference caused by all the users in the system (as in ((1.6.9)), rather than all
the messages sent out (this does not have to be identical) or even all the single hops that
occur at the same time. These are variants of the of network capacity/interference constraint
20
University of Ghana http://ugspace.ug.edu.gh
Figure 1.2: Device X j transmits to Xi with interference from other devices transmitting to
Xi. Source (Jahnel and König, 2020)
models can be addressed under any of the medium access protocols.
Figure 1.2 shows how neighbouring devices can cause interference when a device decides
independently to transmit a message.
1.7 Motivation and goals
In communication networks, where many messages are to be transmitted via a bounded
number of channels, the choice of the medium access protocol is ubiquitous and decisive.
It is clear that, due to interference constraints or due to restricted availability of commu-
nication channels, the task can be successfully managed only if a suitable rule is in force
that regulates which of the many messages is gaining access to the medium at a given time.
Clearly, this rule should be as simple as possible, and it should not require much infrastruc-
ture nor previous investigations.
Ideal for this is a probabilistic ansatz in which all decisions about making sending attempts
are made randomly and independently of each of the participants and with a minimimal
21
University of Ghana http://ugspace.ug.edu.gh
knowledge about the current state of the system. In the models discussed in this research,
only the number of participants and the number of available channels should play a role in
the decision, and each decision is made with a certain fixed probability. In such a system,
there may and will be also unsuccessful decisions made. The operator’s task is to deter-
mine the decisive parameters optimally, i.e., in such a way that the number of successes
(to mention an important quality measure) will be, on a long term, as large as possible. A
probabilistic way to determine this is in terms of a law of large numbers, one of the tools
used in this thesis. Another one is the analysis of events of large deviations from the usual
behaviour.
There are a number of options for medium access protocols that satisfy the above criteria.
In this research, the two most fundamental ones, the (discrete-time) Aloha protocol, where
new messages get access at a given time instant to a channel without knowing whether
or not it is busy or idle, and a variant called the slotted Aloha protocol, where first every
participant chooses whether to make an attempt and then the starting times of the message
transmissions are allocated to certain slots. Slotted Aloha ensures that all network nodes are
perfectly synchronized to some time slots and transmit messages according to a certain rule.
Furthermore, in this thesis we restrict to discrete-time models, since all message at a given
time instant (or, equivalently, in a given fixed time slot) are under a certain upper-bound
constraint: if too many make a sending attempt in a slot, all fail.
In all such protocols, the use of stochasticity and a high degree of independence of the
decisions turns out to be extremely helpful. Each of the messages is equipped with its
own decision making algorithm, based on randomness, and involving only a small set of
parameters that may depend on the current situation. In the situation(s) that this thesis
focuses on, it is assumed that the current number of messages that are to be transmitted is
known to every user equipment involved, and that there is an upper bound κ ∈ N for the
number of messages that can be successfully transmitted at any given time. The reason
22
University of Ghana http://ugspace.ug.edu.gh
for this upper bound may be either a restriction of the number of available channels or an
interference constraint.
The main system parameter is the probability parameter p, the medium access probability
(MAP), with which each of the messages tries randomly to gain access to the system. If p
is too large, then it is likely that the system exceeds the upper bound κ , which results into
failures of many message transmissions. On the other hand, if p is too small, then a part of
the possible capacity is not exhausted, and the system underachieves. Similar arguments can
for example be found in Baccelli and Błaszczyszyn (2009). One of the goals is to quantify
an optimal choice of p. The main quantity for this criterion is the throughput, the number of
successfully transmitted messages per time unit. This thesis also analyses other quantities
like the number of message attempts.
For any of these protocols, we are interested in the large-scale performance of the system,
i.e., in a large number of messages during a large number of time instances. We decided to
consider just one time interval [0,1] and to assume that a successful message transmission
requires a very short time of length 1/N, where N ∈ N is a scale parameter that is propor-
tional to the number of messages. We will calculate and analyse the distribution of the main
quantities in the limit N → ∞. An important aspect of this research is that, focus is not
merely on calculating expectations, but on the asymptotics of probabilites of large devia-
tions, i.e., events that deviate from the expected behaviour, like the event that the number
of successfully delivered messages has a lower linear rate than the expectation. It is also
an interesting and important question to get some useful information about ‘bad’ events of
that sort, and to characterise this event. The main methods used in this thesis consist of
combinatorics large-deviation theory from asymptotic probability theory.
23
University of Ghana http://ugspace.ug.edu.gh
1.8 Contribution
This thesis proposes simple and easy to implement protocols in wireless networks. The
theorems in chapter four and their proofs are a result of the extension of the work of (König
and Tóbiás, 2019). The results also serve as a natural extension to most works that mainly
analyse single message transmissions in multi-hop network channels. This is because the
results generalises the single hop message transmissions in many channels to κ number
of messages. This thesis also provides a much stronger newer approach to deriving large
deviation results which is a much stronger statement than the usual LDP. The result also
shows that, one can, for example, use a cutting argument to bypass some technicalities in
contraction principle.
This thesis also leaves room for several open problems that can be further researched. For
instance, it will be interesting to analyse the case where κ → ∞ in a multi-channel network.
Some of these open problems are further discussed in Chapter four.
1.9 Organisation of thesis
There are four chapters in this thesis. Chapter one is the introduction and this is mainly
made up of the background of the study which briefly introduces the subject matter. It also
contains the problem statement, objectives and relevance of the study. It also consist review
of literature. It presents some articles related to the subject matter. It also briefly discusses
the applications of large deviation theory which is the mathematical tool used in analysing
the models. Lastly, it contains the methodology. Here, the main tools that were adopted and
used for the proofs are discussed. Sanov and Cramer’s Theorems were used hence they are
presented in detail. Law of large numbers and signal to interference and noise ratio (SINR)
are also discussed.
24
University of Ghana http://ugspace.ug.edu.gh
Chapters two and three are the contribution of the thesis. These chapters introduce and
analyse the models in the thesis. Large deviation results are presented in Chapter two and
optimisation results are presented in Chapter three.
Chapter four contains the conclusion, summary and recommendations of the thesis. One
detailed model that can be implemented and analysed in the future is also briefly presented.
25
University of Ghana http://ugspace.ug.edu.gh
Chapter 2
Large deviation for the joint probability
of throughput in Slotted Aloha
2.1 Description of the models
We now introduce the models that were analysed in this research. Each of the models has a
large parameter N ∈ N. Each successful transmission of a message requires precisely 1/N
time units. We consider a reference time interval, which we pick as [0,1]; hence the system
can manage the delivery of ≍ N messages during this time interval. To ease the notation,
the integer-part brackets is waived. Assume that a large number bN (where b ∈ (0,∞) is
the message number parameter) of messages of unit size are to be transmitted. The number
of messages that can be transmitted at a given time is bounded by κ ∈ N (This is e.g. due
to interference constraints or to the fact that only κ channels are available.). Each of the
messages makes attempts at random times to be admitted to the communication system.
According to certain rules (to be specified below), the attempt is admitted or not, and if the
upper bound rule is not violated, then it is successfully delivered 1/N time units later. In
this case, we say that this messages has gained access to the medium.
26
University of Ghana http://ugspace.ug.edu.gh
We write [k] = {1, . . . ,k} for k ∈ N. The medium access protocols that we consider are the
following:
(1) Slotted Aloha: At each time in {0, 1 , 2N N , . . . ,
N−1
N }, any message decides with prob-
ability p/N, independently over all the messages and over all the times, whether to
make an immediate sending attempt or not. For any j ∈ [N], if not more than κ of all
the messages decided at time ( j−1)/N to do so, then all these messages are success-
fully delivered during the time slot [ 1N ( j−1),
j
N ), otherwise all are cancelled.
(2) Organized Aloha: At the beginning of the time stretch [0,1], any of the messages
decides with probability p whether to make an attempt during [0,1], independently
over all messages. In a second step, all these attempts are made during the time
stretch [0,1] at random times, independently and uniformly distributed over [0,1]. In
each time slot [ 1 jN ( j−1), N ) with j ∈ [N], all messages that have been assigned to this
interval are successfully delivered if they are not more than κ , otherwise they will all
be cancelled.
Both protocols are effectively in discrete time as we are only interested in the number of
sending attempts and of successful emissions in the time slots [ 1 ( j−1), jN N ) with j ∈ [N].
In protocol (2), any participant has only at most one chance during [0,1], while in protocol
(1), every message has an unbounded number of trials and can be successful several times.
We assume that each message has an unbounded number of packeges to be sent, i.e., it
makes successively an unbounded number of sending attempts. Protocol (2) has a two-step
random strategy, at first each message randomly decides whether to attempt a transmission,
and then picks randomly a microscopic time slot. Here the number of random variables
that need to be sampled is much smaller than in protocol (1), and the probability parameter
is of finite order in N, in contrast to protocol (1). We therefore see substantial practical
advantages in protocol (2) over protocol (1).
27
University of Ghana http://ugspace.ug.edu.gh
There are three parameters in these simple models:
• p > 0 the message emission attempt probability parameter,
• b ∈ (0,∞) the rate of messages that would like to be transmittted during [0,1],
• κ ∈ N the threshold for the success criterion.
Note that p is indeed a probability (i.e., lies in [0,1]) in protocol (2), while it can be any
positive number in protocol (1).
2.1.1 Quantities and questions of interest
The quantities that we are interested in are the following.
• AN = the number of message sending attempts,
• SN = number of successfully sent messages,
• RN = number of successful micro slots, that is, slots (
j−1
N ,
j
N ] in which all messages
are successfully transmitted, each during the entire interval [0,1].
The most important quantity is the throughput, the number of successfully sent messages
per time unit, which is SN/N in our model. But we find it also important to consider the
number of unsuccessful sending attempts, in order to be able to say something about the
frustration of the participants of the system.
2.2 Large deviation results for throughput
The first main result is on the asymptotics as N → ∞ of the joint distribution of (SN ,AN ,RN),
both in the sense of a law of large numbers and a large-deviation principle. We denote by
P(l)N the probability measures for the two models according to protocol (l) for any l ∈ {1,2}.
28
University of Ghana http://ugspace.ug.edu.gh
The following are introduction of objects that are necessary for formulating the results of
the study. Introduce, for x ∈ [0,∞),
( zi) ( )
− ∑ e − ∑ e
zi
I≤κ(x) = sup xz log and I>κ(x) = sup xz log
z∈R i∈N : i≤κ i!0 z∈R i∈N : i>κ i!0
(2.2.1)
and
( ) ( )
Fκ(a,s,r) = r logr+(1− r) log(1− r)+ rI s≤κ r +(1− r)I
a−s
>κ 1−r . (2.2.2)
Then our main result is as follows.
Theorem 2.2.1 (LDP for 1N (AN ,SN ,RN)). Fix the model parameters b, p > 0 and κ ∈ N,
where we assume p ≤ 1 for Model (2). Fix a,s ∈ [0,b] satisfying s ≤ a and fix r ∈ [0,1].
Pick sequences a 1N ,sN ,rN ∈ NN0 such that aN → a, sN → s and rN → r as N → ∞. Then for
l ∈ {1,2},
( )
I(l)
1
(a,s,r) =− lim logP(l) A = Na ,S = Ns ,R = Nr
→ N N N N N N N N
(2.2.3)
N ∞
exists, and the rate function I(l) = I(l)p,b,κ is given by
I(l)(a,s,r) = J(l)b,p(a)+a−a loga+Fκ(a,s,r), (2.2.4)
where
a
J(1)b,p(a) = pb−a+a log , (2.2.5)pb
(2) a − b−aJb,p(a) = a log +(b a) log −b logb. (2.2.6)p 1− p
29
University of Ghana http://ugspace.ug.edu.gh
There is the following alternative representation for I(1):
{ }
I(1)(a,s,r) = inf H(µ|Poibp) : µ ∈M1(N0), ∑ f (k)µk = (a,s,r) (2.2.7)
k∈N0
where H(µ|Poi µkbp) = ∑k∈N0 µk log q denotes the entropy of µ with respect to the Poissonk
distribution with parameter bp, where q = e−pbk (pb)k/k!, and f (k) = (k,k1l{k ≤ κ},1l{k ≤
κ}).
The proof of Theorem 2.2.1 for l = 2 is in Section 2.3.1 and for l = 1 in Section 2.3.3. In
Section 2.3.3 a proof of the representation in (2.2.7) is presented.
It turns out in Theorem 2.2.1 that the difference between protocol (1) and (2) is only in
the rate function for the number of sending attempts. Indeed, this number is bino(mia)l with
parameters bN and p in case (2) (and J(2)b,p(a) is the negative exponential rate of
bN
aN ), but
a sum of N independent binomials with parameters Nb and p/N (approaching the Poisson
distribution Poibp) in case (1) (with J
(1)
b,p being the rate function for the average of N Poibp-
distributed random variables). Both rate functions have an infinite slope at a ↓ 0, but only
J(2)b,p has for a ↑ b.
It is now a technical task to derive from Theorem 2.2.1 that 1N (AN ,SN ,RN) satisfies large-
deviation principles (LDPs) with rate functions I(l) under P(l)N , which says that for any open
set G ⊂ [0,b]× [0,b]× [0,1] and closed set F ⊂ [0,b]× [0,b]× [0,1],
(
1 1 ( ) )
limsup logP(l)N( (AN ,SN ,RN) ∈ F) ≤ −infI
(l),
N→∞ N N F
1
liminf logP(l)
1
N A ,S ,R ∈ G ≥ −infI
(l).
N→∞ N N N N N G N
It is a standard conclusion from the LDP that, if the rate function has a unique minimizer
at (ap,sp,rp), a law of large numbers (LLN) follows, i.e., 1N (AN ,SN ,RN) → (ap,sp,rp) in
P(l)N -probability with exponential decay of the probability of being outside a neighbourhood
30
University of Ghana http://ugspace.ug.edu.gh
of (ap,sp,rp). Hence, the following statement implies two LLNs.
Corollary 2.2.2 (LLN for the throughput). For l ∈ {1,2}, the rate function I(l) is strictly
convex and possesses the same unique minimizer (ap,sp,rp) given by ap = pb and
(bp)i κ−1 (bp)i
sp = e−bp ∑ i = E [X1l{X ≤ κ}] = bpe−bpPoibp ∑ , (2.2.8)
i∈N0 : i≤κ i! i=0 i!
(bp)i
r = e−bpp ∑ = Poibp([0,κ]). (2.2.9)
i∈N0 : i≤κ i!
Another standard corollary of Theorem 2.2.1 is an LDP for the number SN of successes,
which follows directly from the contraction principle (see Theorem 1.6.2); indeed 1N SN
satisfies an LDP under P(l)N with rate function s 7→ infa,r I(l)(a,s,r). There is no closed form
for this rate function; only for l = 1, we can write inf I(l)a,r (a,s,r) = inf{H(µ|Poibp) : µ ∈
M κ1(N0),∑k=0 kµ(k) = s}. This variational formula is analysed as a by-product of the proof
of Lemma 2.3.1 below.
2.3 Proofs of the LDPs
2.3.1 Proof of Theorem 2.2.1 for l = 2
In this section, we work under protocol (2), i.e., at the beginning of the time stretch [0,1],
each of the bN message holders chooses with probability p whether to make a sending at-
tempt during any of the N time slots in [0,1], and then all those who do this are uniformly
independently distributed over all the N micro time slots. In each micro slot, all the mes-
sages are successfully transmitted if their number is ≤ κ , otherwise all are unsuccessful.
For any k ∈N, we write [k] for the set {1, . . . ,k}. Let Xi ∈ {0,1} for i ∈ [bN] be the indicator
on the event that the i-th message chooses to attempt to send, then (Xi)i∈[bN] is a family of
31
University of Ghana http://ugspace.ug.edu.gh
independent Bernoulli variables with parameter p. Let
AN = {i ∈ [bN] : Xi = 1}
be the set of those that attempt, i.e., AN = |AN |. For i ∈AN let Yi ∈ [N] be the index of the
microscopic interval that is assigned to the i-th message for the sending instant, then, given
AN , (Yi)i∈AN is a family of independent UN-distributed random variables, where UN is the
uniform distribution on [N] = {1, . . . ,N}. Let K j = ∑i∈AN 1l{Yi = j} denote the number of
attempts in the j-th time slot for j ∈ [N]. By
RN = { j ∈ [N] : K j ≤ κ}
we denote the set of indices of all the ‘successful micro slots’, i.e., of the intervals in which
not more than κ of the messages make a transmission attempt and will therefore be suc-
cessfully transmitted. Clearly RN = |RN |. Then the number of successful messages is equal
to
SN = ∑ K j = #{i ∈AN : KYi ≤ κ}.
j∈RN
Fix parameters a,s ∈ [0,b] satisfying s ≤ a, and r ∈ [0,1] and sequences a = aN ,s = sN ,r =
rN ∈ 1NN0 such that aN → a, and sN → s and rN → r as N → ∞. The goal is to find the
logarithmic asymptotics of
qN = PN(AN = NaN ,SN = NsN ,RN = NrN).
Note that the number AN of messages that attempt to send is binomially distributed with
parameters bN and p. Conditional on the event {AN = NaN}, the joint distribution of
(Yi)i∈AN is equal to U
⊗NaN
N (the exchangeability property of Xi ensures this), and we may
32
University of Ghana http://ugspace.ug.edu.gh
take AN = [NaN ] as the index set. Hence for N large enough,
qN = P(N(AN)= NaN)PN(SN = NsN ,RN =(NrN |AN = NaN) )
bN
= pNaN (1− p)bN−NaN( U
⊗NaN
Na N
RN = NrN , )∑ K j = NsNN ∈ (2.3.10)j RN
N J(2)= e [ b,p(a)+o(1)]U ⊗NaNN RN = NrN , ∑ K j = NsN , N → ∞,
j∈RN
where J(2)b,p is defined in (2.2.6). In the third equality we have used the Stirling’s approxima-
tion to the factorial of a large enough positive integer.
We turn to the last term on the right of (2.3.10). We need to decomposeRN into the part of
those j such that K j ≤ κ and the others. Hence,
( )
U ⊗NaNN RN = NrN , ∑ K j = N(sNj∈RN )
= ∑ U ⊗NaN( N B = { j : K j ≤ κ}, ∑ K j = NsN (2.3.11)B⊂[N] :)|B|=NrN ( j∈B )
N
= U ⊗NaNN [NrN ] = { j : K j ≤ κ}, ∑ K j = Ns ,Nr NN j∈[NrN ]
where we took without loss of generality RN as the set [NrN ] = {1, . . . ,NrN}. In the next
step, we make explicit the set of indices i with cardinality NsN such that Yi ∈ [NrN ]:
( )
U ⊗NaNN [NrN ] = { j : K j ≤ κ}, ∑ K j = NsN
j∈[N(rN ] )
= ∑ U ⊗NaN( ) (N D = {i ∈ [NaN ] : Yi ∈ [NrN ]}, [NrN ] = { j : K j ≤ κ}D⊂[NaN ] : |D|=NsN )
NaN
= ( )U ⊗NaNNs NN
Na (
[NsN ] = {i ∈ [NaN ] : Yi ∈ [NrN ]}, [NrN ])= { j : K j ≤ κ}
N
= U ⊗NsNN Y1(, . . . ,YNsN ∈ [NrN ],K j ≤ κ ∀ j ∈ [NrNs N ]N )
× ⊗(NaN−Ns )U N c cN YNsN+1, . . . ,YNaN ∈ [NrN ] ,K j > κ ∀ j ∈ [NrN ] ,
(2.3.12)
33
University of Ghana http://ugspace.ug.edu.gh
where we took [NsN ] as the set of indices i such that Yi ∈ [NrN ], and we recall that K j =
∑NsNi=1 1l{Yi = j} in the first probability term, and analogously K
NaN−NsN
j = ∑i=1 1l{Yi = j} in
the second. The complement is taken within the set [N] = {1, . . . ,N}.
Now we make a change of measure from the uniform distribution on [N] to the uniform
distribution on [NrN ] respectively on [Nr ]cN , and we use that all these probabilities depend
only on the cardinality of [NrN ]. Hence, substituting in (2.3.10), we see that we have
( ) ( )( )( ) ( )
bN N Na Nr NsN N −Nr NaN−NsN
q pNaN 1− p Nb−NaN N N NN = ( )NaN ( ) NrN NsN ( N N )
⊗NsN K ≤ κ ∀ j ∈ Nr ⊗(NaN−Ns )UNr j , [ N ] U
N
N−Nr K j > κ,∀ j ∈ [N −Nr ] .N N N
(2.3.13)
Now we evaluate the large deviations of each of the two last terms. Recall the two functions
I≤κ and I>κ from (2.2.1).
Lemma 2.3.1. Suppose sN → s > 0, and aN → a > 0 and rN → r ∈ [0,1], then for N large
enough,
(NsN)!
U ⊗NsNNr (K j ≤ κ ∀ j ∈ [NrN ]) = Ns e
−NrI≤κ (s/r)eo(N), (2.3.14)
N (NrN) N
and
⊗(NaN−NsN) (N(a − s ))!U (K > κ ∀ j ∈ N −Nr N N[ ]) = e−N(1−r)I>κ ((a−s)/(1−r)) o(N)N−Nr j N e .N (N(1− rN))N(an−sN)
(2.3.15)
Proof. We prove only (2.3.14); the proof of (2.3.15) is analogous.
Let us identify the joint distribution of K1, . . . ,KNrN underU
⊗NsN
Nr in terms of standard Pois-N
son point process (see definition in 1.6.5.1) with parameter one on [0,NrN ]. Conditional on
having precisely NsN Poisson points in that interval, their distribution is i.i.d. and uniform.
Then the distribution of Y , . . . ,Y under U ⊗NsN1 NsN Nr is equal to that of the integer up roundedN
values of these conditional Poisson points. Hence, the distribution of K j is the distribution
34
University of Ghana http://ugspace.ug.edu.gh
of the number of these Poisson points that fall into [ j−1, j]. Summarizing, the joint distri-
bution of K , . . . ,K ⊗NsN1 NrN underUNr is equal to that of NrN i.i.d. Poisson distributed randomN
variables with parameter one conditioned on having their sum equal to NsN . Hence, writing
Poi = Poi1,
( Nr )N
U ⊗NsN ⊗NrNNr (K j ≤ κ,∀ j ∈ [NrN ]) = Poi K j ≤ κ ∀ j ∈ [NrN ( N
], ∑ 1K j = Ns
j=1 )N PoiNrN (NsN)NrN
Nr ⊗NrN 1 ∑ sN r N (Ns )!= Poi([0,κ]) N Poi N N≤κ KNr j = eN Ns ,Nj=1 rN (NrN)
(2.3.16)
where Poi≤κ is Poi, conditioned on [0,κ]. Now we can use Cramér’s theorem (see Theorem
1.6.1) for the second term on the right-hand side. Indeed, the average of the K1, . . . ,KNrN
satisfies an LDP with speed rN and rate function equal to the Legendre transform (see, 1.6.6
and 1.6.4) of z →7 logE zK≤κ [e 1] , where E≤κ is the expectation with respect to Poi≤κ , and
K1 is a corresponding random variable. It is only a small technicality to see that the negative
exponential rate of the second term on the right-hand side of (2.3.16) on the scale rN is
equal to
( ) ( zi)s s e
sup z− logE [ezK≤κ 1] = sup z− log ∑ e−1 + logPoi([0,κ])
z∈R r z∈R r i∈N0 : i≤κ i!
= 1+ I s≤κ( r )+ logPoi([0,κ]).
Note that the first and the third term on the right-hand side of this cancel the third and the
first term, respectively, on the right-hand side of (2.3.16), on the exponential scale. This
directly implies (2.3.14). □
Substituting (2.3.14) and (2.3.15) into (2.3.13), we obtain
( )
(Na )! N
q = Bin N(Na ) e−NrI≤κ (s/r)e−N(1−r)I>κ ((a−s)/(1−r)) o(N)N bN,p N Na e (2.3.17)N N NrN
Using Stirling’s approximation n!=(n/e)neo(n) and the facts aN → a, and sN → s and rN → r
35
University of Ghana http://ugspace.ug.edu.gh
as N → ∞, we arrive at the assertion. This finishes the proof of Theorem 2.2.1 for l = 2.
2.3.2 Proof of Theorem 2.2.1 for l = 1
We present a proof of Theorem 2.2.1 for l = 1 using Crámer’s theorem. We are working
for protocol (1), where in each of the micro slots ( j−1 jN , N ], j ∈ [N], the sending decision
is made with probability p/N, independently for all the message holders and all the micro
time slots. Each time slot is successful, i.e., all its messages are successfully transmitted,
if and only if the number of transmission attempts in that slot is ≤ κ . Hence, all the three
quantities under interest, SN , AN and RN , are equal to sums of N i.i.d. random quantities.
Here it is assumed that any message can attempt any number of times. There are j ∈ [N]
micro time slots. Again, we write [k] = {1, . . . ,k} for any k ∈ N.
For i ∈ [bN] and j ∈ [N], we let X ( j)i ∈ {0,1} be the indicator on the event that the i-th
message chooses to attempt to send a message in the j-th time slot. Let
A( j) = ∑ 1l{X ( j)N i = 1}, R( j)N = 1l{A( j)N ≤ κ}, S( j)N = A( j)N 1l{A( j)N ≤ κ}.
i∈[bN]
Then A( j)N is the number of transmission attempts, R
( j)
N the indicator on the event that the j-th
micro slot is successful and S( j)N is the number of successfully sent messages during that time
slot. Hence, A = ∑N ( j) N ( j) N ( j) (1) (N)N j=1 AN , RN = ∑ j=1 RN and SN = ∑ j=1 SN . Furthermore, AN , . . . ,AN
are i.i.d., and each of them is binomially distributed with parameter bN and p/N, hence
converges towards the Poisson distribution (Poibp) with parameter pb as N → ∞. Again, the
goal is to find the logarithmic asymptotics of
( )
dN = PN AN = NaN ,SN = NsN ,RN = NrN .
36
University of Ghana http://ugspace.ug.edu.gh
One short proof, which uses a lot of the proofs given in Section 2.3.3, is via the conditioning
dN = P(AN = NaN)P(SN = NsN ,RN = NrN |AN = NaN)
and noting that the second term is identical to the corresponding one for protocol (2), i.e.,
equal to the second term on the right-hand side of the first line of (2.3.10). The only differ-
ence between the two protocols is the first term, which was identified as BinbN,p(NaN) in
(2.3.10). Here, however, it is identified as the probability that the sum of bN independent
BinbN,p/N-distributed variables is equal to NaN . The logarithmic asymptotics of the latter
can be identified in terms of the well-known large-deviation rate function, J(1)b,p, for the sum
of i.i.d. Poibp-distributed variables. The only point that is left to do is to check whether the
approximation of Poibp by BinbN,p/N , due to the Poisson limit theorem, is good enough for
deducing that AN/N satisfies the same LDP.
Nevertheless, we provide another, independent proof. Distinguishing the rNN micro slots
with ≤ κ message attempts, we observe that
( ) ( )
N
d = ( j) ( j)N r N(P AN ≤ κ ∀ j ∈ [rN], ∑ AN = sNNN j∈[rNN] ) (2.3.18)
×P A( j) ( j)N > κ ∀ j ∈ [(1− rN)N], ∑ AN = (aN − sN)N
j∈[(1−rN)N]
where we used the fact that, micro slots with not more than κ messages are independent
of slots with more than κ messages and hence we can use independence. Hence, we can
proceed with
( ) ( )
N
d = Bin ([0,κ])rNN
1
N r N bN,p/N
P≤κ (r N ∑
s
A( j) NN =
N N j∈ r N r[ ] NN ) (2.3.19)
× 1 a − sBin κ ∞ (1−rN)NP ∑ A( j) N NbN,p/N(( , )) >κ (1− r )N N = ,N j∈[(1−rN)N 1− r] N
where P≤κ is the probability with respect to independent BinbN,p/N-distributed variables,
37
University of Ghana http://ugspace.ug.edu.gh
conditioned on being ≤ κ , and P>κ is defined analogously.
Now we again use the Poisson limit theorem to see that for N large enough BinbN,p/N([0,κ])rNN =
[Poi ([0,κ])]rNeo(N)pb and the analogous statement for the other probability term. The aver-
age of A( j)N under P≤κ satisfy the same LDP as the average of i.i.d. Poibp-distributed random
variables, conditioned on being ≤ κ (analogously with > κ instead of ≤ κ). The latter
do satisfy an LDP, according to Cramér’s theorem (see Theorem 1.6.1), with rate function
equal to the Legendre transform of y 7→ logE yXbp,≤κ [e 1 ], where Ebp,≤κ is the expectation
with respect to Poibp restricted to [0,κ] , and X1 is a corresponding random variable. Hence
we have that
( ) ( )
− 1 1lim logP ∑ A( j) s s≤κ N = = r sup y− logEbp,≤κ [eyX1] .N→∞ N rN j∈[rN r] y∈R r
This, together with the negative large-N logarithmic asymptotics of the probability term in
the first line of (2.3.19), give the term
( ) ( )
s s (eybp)i
r sup y− logE [eyX1bp,≤κ ] − r logPoipb([0,κ]) = rbp+ r sup y− log
y∈R r r
∑
y∈R i∈N0 : i≤κ i!
= rbp− s log(bp)+ rI≤κ( sr ),
as the substitution ez = bpey, i.e, y = z− log(pb), gives. Hence, this is the negative expo-
nential rate of the two last terms on the first line of (2.3.19). An analogous formula holds
for the two terms in the second line. Summarizing and using Stirling’s approximation for
the binomial term implies the assertion of Theorem 2.2.1 for l = 1.
2.3.3 Identification of the rate function in Theorem 2.2.1 for l = 1
Here we again work under the protocol (1) as in Section 2.3.2. We will present another
large-deviation approach using Sanov’s theorem instead of Cramér’s theorem. This does
38
University of Ghana http://ugspace.ug.edu.gh
not only give an alternate proof of the LDP in Theorem 2.2.1, but also an alternate formula
for the rate function, which will be used later.
We use the same notation as in Section 2.3.2. We introduce the empirical measure
1 N
µN := δN ∑ A( j),j=1 N
which is a random member of the set M1(N0) of probability measures on N0. We denote
by H(µ|ν) = ∑k∈N0 µ log
µk
k ν the entropy of µ ∈M1(N0) with respect to ν ∈M1(N0).k
Furthermore, we abbreviate qk = Poibp(k) = e−pb(pb)k/k! and q = (qk)k∈N0 .
If A( j)N would be exactly Poibp-distributed, then Sanov’s theorem would imply that (µN)N∈N
satisfies an LDP with rate function µ 7→ H(µ|Poibp). However, it is not difficult by explicit
calculation to see that the empirical measure of A(1)N , . . . ,A
(N)
N and the empirical measure of N
independent Poibp-distributed random variables are exponentially equivalent as N → ∞ and
therefore satisfy the same LDP.
We introduce
( )
f : N0 → N0 × [κ]×{0,1}, f (a) = a,a1l{a ≤ κ},1l{a ≤ κ} .
Note that the triple under interest, (AN ,RN ,SN), is nothing but N⟨ f ,µN⟩, i.e., the image of
µN under the map µ 7→ ⟨ f ,µ⟩. Hence, if this map would be continuous in the weak topology
onM1(N0), then the contraction principle (see Theorem1.6.2) immediately would give the
LDP of Theorem 2.2.1 for l = 1 with rate function I(1) given as in (2.2.7). However, clearly
f is not bounded, hence the map µ 7→ ⟨ f ,µ⟩ is not continuous in the weak topology on
M1(N0). Hence we cannot directly apply the contraction principle. However, it is clear
that the second and third argument in the function are bounded. It is clear that a sufficient
39
University of Ghana http://ugspace.ug.edu.gh
truncation argument is required by proving that
1
lim limsup logPN(AN >CN) =−∞. (2.3.20)
C→∞ N→∞ N
It is easy to see that (2.3.20) is true, using the exponential Chebyshev inequality (PN(AN >
CN) ≤ e−CαNE [eαAN N ] for α > 0) and that AN is a sum of N independent BinbN,p/N-
( j) αA(1) αdistributed random variables AN and that E[e N ]→ epb(e −1) as N → ∞.
2.4 Analysis of the rate functions
2.4.1 Description of the minimizer(s) a,s,r
We now prove Corollary 2.2.2. We rewrite the function defined in (2.2.1), for x ∈ R, as
( ) i
I≤κ(x) = sup x logy−
y
log f≤(y) with f≤(y) = ∑ . (2.4.21)
y∈(0,∞) i∈N0 : i≤κ i!
The following lemma implies Corollary 2.2.2.
Lemma 2.4.1. For l ∈ {1,2}, the rate function I(l) defined in (2.2.4) is convex and has
precisely one minimiser (a,r,s), depending on (b, p,κ). It is characterized by
f≤(a) a f
′ (a) a f ′ (a)
a = pb, r = ≤ ≤a , s = r = a . (2.4.22)e f≤(a) e
Proof. Let us first argue the convexity. There is a simple standard proof, based on (2.2.7),
that shows the convexity of I(1), since the entropy H(µ|ν) is convex in µ and the constraint
is linear in µ . Now observe that I(2)− I(1) is also convex; indeed it depends only on a:
(2) b(1− p)H(a) = I (a,s,r)− I(1)(a,s,r) = a− pb− (b−a) log , (2.4.23)
b−a
40
University of Ghana http://ugspace.ug.edu.gh
and one easily calculates that H ′′(a) = 1b−a > 0 for any a∈ (0,b). The existence and unique-
ness of a minimizer hence follows from the uniqueness of zeros of the gradient of I(1), which
we will show now.
The maximizer Y≤(x) in (2.4.21) is characterized by f ′≤(Y≤(x))Y≤(x) = x f≤(Y≤(x)) and
satisfies I≤κ(x) = x logY≤(x)− log f≤(Y≤(x)).
We write I>κ in a similar manner, i.e., I>κ(x) = x logY>(x)− log f>(Y>(x)), and Y>x is
i
characterized by f ′>(Y>(x))Y>(x) = x f>(Y>(x)), where f>(y) = ∑
y
i∈N0 : i>κ i! .
In order to characterize the minimizer of I = I(1), we equate its gradient in (a,s,r) to zero
and obtain
∂ I(a,s,r) − p(b−a)
(a− s)
0 = = log + lo(gY>( )) , (2.4.24)∂a 1− p 1− r
s
∂ I(a,s,r) r f≤ Y≤ r
0 = = log − log ( ( )) , (2.4.25)
∂ r 1− r f Y a−s> > 1−r
∂ I(a,s,r) (s) (a− s)
0 = = logY≤ − logY> . (2.4.26)∂ s r 1− r
From (2.4.24) and (2.4.26), we have that
( ) ( )
Y s = Y a−s = p(b−a)≤ r > 1−r 1−p . (2.4.27)
We abbreviate c = p(b−a) (a−p)c s1−p , i.e., a = b− p , then we have c = Y≤( r ). Using the defining
property of Y≤(x) from above, we get that f ′≤(c)c =
s
r f≤(c).
Substituting (2.4.27) into (2.4.25) yields
r
f≤(c) = f>(c) = (ec −
r
f≤(c)) , (2.4.28)1− r 1− r
that is, f≤(c) = rec and f>(c) = (1− r)ec. Combining this with f ′≤(c)c = sr f≤(c) from
41
University of Ghana http://ugspace.ug.edu.gh
above, we see that a = c and therefore a = pb.
From (2.4.27) we also have that
f ′ ′≤(c) = f>(c)s/(a− s) (2.4.29)
and analogously f ′ (c) = s ec and f ′ (c) = a−s c≤ a > a e .
Also from the characterisation of Y≤(.), we have that
f ′≤(c)/ f≤(c) = s/r (2.4.30)
Altogether, we arrive at (2.4.22). This ends the proof of the Lemma 2.4.1. □
42
University of Ghana http://ugspace.ug.edu.gh
Chapter 3
Optimisation result for the throughput
probability parameter (p) in
Aloha/Slotted Aloha
3.1 Optimal p
A natural and important question is about that value of p that maximizes the expected
throughput per micro slot, sp. It is clear that the optimal value should be such that bp
is smaller than κ , since otherwise the number of attempts per time slot is larger than the
success threshold. But the question is how much below κ should one go in order not to
underachieve more than necessary.
Let us call the optimal value p(l)∗ . Recall that it is the same function sp that is to be optimized
for both l = 1 and l = 2, but the domain for p(2)∗ is restricted to [0,1]. The map k 7→ Poia(k)
increases on [0,a]∩N0 and decreases on [a,∞)∩N0. Hence we expect that the optimal value
of a = a κ∗ ∈ (0,∞) for a 7→ ∑k=0 kPoia(k) = sa/b will be smaller than κ . Indeed, it is even
smaller than κ −1:
43
University of Ghana http://ugspace.ug.edu.gh
Lemma 3.1.1 (Optimal p). For l = 1, there is precisely one p = p(1)∗ ∗ ∈ (0,∞) that maximizes
the map (0,∞) ∋ p →7 sp. It is characterised by
(a )κ∗ ∑ (a
i
∗)
= , a∗ = bp∗, (3.1.1)
(κ −1)! i∈N0 : i≤κ−1 i!
and it satisfies bp∗ < κ −1 and bp∗ ∼ κ as κ → ∞. Furthermore, p →7 sp strictly increases
in [0, p ] and strictly decreases in [p ,∞). Hence, p(2)∗ ∗ ∗ = min{p∗,1}.
The proof of Lemma 3.1.1 is in Section 3.3.
3.2 Conditioning the number of attempts on the number
of successes
In this section we discuss an interesting question that can be answered with the help of
large-deviation theory, combined with an analysis of the rate functions: What is the most
likely reason for a deviation event of the form that the throughput is below the theoretically
optimal one? Is it that too few attempts have been made or too many?
In order to formalize this question, we write P(l)N,p for the probability measure of the protocol
l with parameter p, pick some 0 < s ≤ a, then it is clear that
1 ( ∣ )
lim logP(l)N,p AN = ⌊aN⌋ ∣S = ⌊Ns⌋ =− inf I(l)N p (a,s,r)+ inf I(l)p (ã,s,r).N→∞ N r ã,r
From this, we see that
( ) ( )
(l) A
∣
lim E N ∣N,p ∣SN = ⌊Ns⌋ = argmin inf I(l)p (a,s,r) .N→∞ N a r
Given s, we now define ap(s) as a minimizer of the map a 7→ inf I(l)r p (a,s,r), i.e., the typical
44
University of Ghana http://ugspace.ug.edu.gh
number of sending attempts, conditional on having ≈ sN successes. It will turn out that
ap(s) is well-defined at least in a neighbourhood of ap(sp) if p is close enough to p∗, where
we recall that s is the minimizer that is established in Corollary 2.2.2, and p∗p is the maxi-
mizing p for p →7 sp characterized by (3.1.1). In terms of these quantities, the question now
reads: Given s < sp , is it true that ap(s)< ap(sp)?
Theorem 3.2.1. For l = 1, fix κ . Then, for any p ∈ (0,∞) and for any s in some neighbour-
hood of sp, we have
[ ] [ ]
p < p∗ =⇒ [s < sp ⇒ ap(s)< ap(sp)]and [s > sp ⇒ ap(s)> ap(sp)], (3.2.2)
p > p∗ =⇒ s < sp ⇒ ap(s)> ap(sp) and s > sp ⇒ ap(s)< ap(sp) . (3.2.3)
Furthermore, for p = p∗, for any s ∈ [0, p∗b]\{sp∗}, we have ap∗(s)> ap∗(sp∗).
The proof is in Section 3.4. Theorem 3.2.1 says that, for non-optimal p, if s sufficiently
close to the optimal sp, then the attempt number ap(s) deviates to the same side of ap(sp) as
s is with respect to sp, while in the optimal p∗, the typical attempt number for non-optimal
success number is always larger than the optimal one. The latter means that, for the optimal
choice p = p∗, the event of non-optimal throughput alway comes with overwhelming prob-
ability from too many attempts. Apparently, here the conditional probability for having too
many attempts is much larger than the one for having too few.
3.3 Optimizing p →7 sp
In this section, we prove Lemma 3.1.1, that is, we analyse the maximizer of the map p 7→ sp,
the optimal throughput, for both protocols (1) and (2), the only difference being that the
domain for protocol (1) is p ∈ [0,∞) and for (2) it is p ∈ [0,1].
Let us first consider optimization over (0,∞). The analytic function g(a)= s = ae−a ∑κ−1 a
i
a/b i=0 i!
45
University of Ghana http://ugspace.ug.edu.gh
is positive in (0,∞) with limits 0 at a ↓ 0 and a → ∞, hence it has at least one maximizer a∗,
i
which is characterised by g′(a∗) = 0. We see that (with f (a) = ∑κ a≤ i=0 i! )
d ( ) [ ](bp)i (bp)κ
sp = be−ap f ′≤(ap)+ap f
′′ ′
≤(ap)−ap f≤(ap) = be−bp ∑ − , p> 0.dp i≤κ−1 i! (κ −1)!
(3.3.4)
Hence, (3.1.1) characterizes p(1)∗ .
Using elementary calculus, we see that a solution a∗ to (3.1.1) exists since the polynomial
f (a) =−(κ−1)!be−a d s = aκ −∑ ai (κ−1)!dp p i≤κ−1 i! starts with f (0)< 0 and satisfies f (a)→
∞ as a → ∞. Note that, for any a > 0, we have
( )i κ κ
f (a)≥ aκ − ∑ ai(κ −1)κ−1−i = aκ − − κ−1 ∑ a (κ −1) −a(κ 1) = aκ +
i≤κ−1 i≤κ−1 κ −1 a− (κ −1)
aκ(a−κ)+(κ −1)κ
= ,
a− (κ −1)
and the latter is positive for any a > κ −1. Hence, we even have that a∗ ≤ κ −1. Further-
more, there is only one solution, since f ′(a) = κaκ−1 −∑ ai (κ−1)! + aκ−1i≤κ−1 i! for any a,
and for any solution a∗ we see that f ′(a∗) = (κ + 1)aκ−1 − aκ = aκ−1∗ ∗ ∗ [κ + 1− a∗], which
is positive. Hence, f has precisely one zero in [0,∞). It is negative left of a∗ and positive
right of it. Accordingly, p →7 sp is increasing in [0, p∗] and decreasing in [p∗,∞). We obtain
a lower bound for a∗ by
( )
≤ κ − i (κ −1)!f (a) a a < ai aκ−i − (i+1)κ−i−1 , a > 0, i ∈ {0, . . . ,κ −1}.
i!
This upper bound is zero for a = (i+1)1−1/(κ−i), hence a ≥ maxκ−1∗ i=0 (i+1)1−1/(κ−i). Tak-
√ √
ing i = κ − κ −1/2gives a ≥ (κ − κ)1−κ∗ = κ(1+o(1)) as κ → ∞.
46
University of Ghana http://ugspace.ug.edu.gh
3.4 Conditioning on successes
In this section, we prove Theorem 3.2.1. Recall that we conceive the maximal throughput
per micro slot, s = sp, as a function of p. Recall from Lemma 3.1.1 that the maximal p∗ for
p 7→ sp is characterized by
aκ κ−1 ip ap
= , a = bp. (3.4.5)
(κ −1)! ∑ i! pi=0
Furthermore recall that a(l)(s) denotes the minimising a for the map a 7→ inf I(l)p r (a,s,r) for
l ∈ {1,2}, and note that ap = ap(s ) = a(1)p p (s ) = a(2)p p (sp) = bp. Here we answer the question
of the reason for few number of successes. The following lemma proves Theorem 3.2.1 for
l = 1.
Lemma 3.4.1. Let us consider the rate function for the protocol l = 1. Then, for any p ∈
(0,∞), we have (a(1)p )′(s (1) ′p)< 0 for p < p∗ and (ap ) (sp)> 0 for p > p∗. In particular, for s
in a neighbourhood of sp, (3.2.2) and (3.2.3) hold.
Furthermore, for p = p∗, we have a(1)p∗(s)> a
(1)
p∗(sp∗) = bp∗ for any s ∈ [0,b]\{bp∗}.
Proof. Let us first analyse inf (l)r Ip (a,s,r) for fixed a,s. We benefit from the representation
in (2.2.4): We have that
inf I(1)p (a,s,r) = inf i{nf{H(µ|Poipb) : ⟨ f ,µ⟩= (a,s,r)}r r ∞ κ }
= inf{H(µ|Poipb) : ∑ kµk = a, ∑ kµk = sk=0 k=0 }
= inf H(µ|Poipb) : ⟨µ, id⟩= a,⟨µ, id|≤κ⟩= s ,
where id is the identity function on N0 and id|≤κ(k) = k1l[0,κ](k); and we used the notation
⟨µ, f ⟩ for the integral of a function f with respect to a measure µ . Now we apply standard
variational calculus. Consider a minimizer µ of the last formula. A standard argument
47
University of Ghana http://ugspace.ug.edu.gh
shows that µk > 0 for any k. Fix some γ : N0 → R satisfying γ⊥1l,γ⊥id and γ⊥id|≤κ .
Then, for any ε ∈ R with sufficiently small |ε|, the measure µ + εγ is admissible. From
minimality, we deduce that
( ) 〈 〉
0 = ∂ε |
µ γ µ
ε=0H(µ + εγ|Poipb) = ∑ γ log k µ kk + k = γ, log ,
k qk µk q
where we put q = Poi (k). Hence, log µk pb q is a linear combination of 1l, id and id|≤κ . That
is, there are A,B,C ∈ R such that
eCk for k ≤ κ,µ = q eAeBkk k × k ∈ N0. (3.4.6)1 for k > κ,
We note that A,B and C are well-defined functions of a and s, since 1l, id and id|≤κ are
linearly independent.
Now using that ⟨µ,1l⟩= 1 and ⟨µ, id⟩= a and ⟨µ, id|≤κ⟩= s, and introducing the notation
( κ )
ϕ(B,C) := log ∑ q e(B+C)k + ∑ q Bkk ke , B,C ∈ R, (3.4.7)
k=0 k>κ
we see that B = B(a,s) and C =C(a,s) are characterised by
∑ kq e(B+C)kk + ∑ kqkeBk
a k≤κ k>κ= = ∂Bϕ(B,C), (3.4.8)
∑ q e(B+C)kk + ∑ qkeBk
k≤κ k>κ
∑ kqke(B+C)k
s k≤κ= = ∂ ϕ(B,C), (3.4.9)
∑ q e(B+C)k + ∑ q Bk
C
k ke
k≤κ k>κ
while A(a,s) =−ϕ(B(a,s),C(a,s)). Furthermore,
inf I(1)
µk
p (a,s,r) = ∑µk log = Ba+Cs−ϕ(B,C). (3.4.10)r
k qk
48
University of Ghana http://ugspace.ug.edu.gh
This finishes the characterisation of inf I(1)r p (a,s,r) for any fixed a,s.
Now we optimise over a with s fixed. We recall that a(1)p (s) denotes the minimizing a of
infr I
(1)
p (a,s,r). Recalling that B and C are functions of a and s, we differentiate (3.4.10)
with respect to a and use it for a = a(1)p (s) to obtain
( )
0 = a((1)
d
p (s)−∂Bϕ(B(a(1)p (s),s),C(a(1)p (s),)s)) B(a(1)p (s),s)ds
+ s−∂ ϕ(B(a(1)(s),s),C(a(1) dC p p (s),s)) C(a(1)p (s),s)+B(a(1)p (s),s) (3.4.11)ds
= B(a(1)p (s),s),
also using (3.4.8) and (3.4.9). Differentiating this with respect to s produces
∂ (1)
a(1) ′ s − s
B(ap (s),s)
( p ) ( ) = 1 . (3.4.12)∂aB(a( )p (s),s)
A tedious calculation, starting from differentiating both (3.4.8) and (3.4.9) both with respect
to a and to s, gives, for B = B(a,s) and any a and s,
∂ 2ϕ ∂ ∂ ϕ
∂ C B CaB = 2 and ∂ B =−∂Bϕ∂ 2 2
s
Cϕ − (∂C∂Bϕ) ∂ 2Bϕ∂ 2Cϕ − (∂C∂Bϕ)2
and hence
(1) ′ ∂B∂Cϕ(B,C)(ap ) (s) = 2 with B = B(a
(1)
p (s),s) = 0 and C =C(a
(1)
p (s),s). (3.4.13)∂Cϕ(B,C)
49
University of Ghana http://ugspace.ug.edu.gh
First we show that the denominator is positive:
( ) ( )2
∑ k2q e(B+C)k ∑ q (B+C)k Bk (B+C)kk ( ke + ∑ qke − ∑ kqke∂ 2ϕ B C k≤κ k≤κ k>κ ) k≤κC ( , ) = 2
∑ q e(B+C)k( )( k +) ∑(qke
Bk
k≤κ k>κ )2
∑ k2q e(B+C)k ∑ q e(B+C)kk ( k − ∑) kq
(B+C)k
ke
≥ k≤κ k≤κ k≤κ2 > 0, B,C ∈ R,
∑ q e(B+C)k + ∑ q eBkk k
k≤κ k>κ
as a standard symmetrisation shows. Next we consider the numerator in (3.4.13):
( )−2
∂B∂Cϕ(0,C) = [∑ q e
Ck
k + ∑ qk
k≤κ k>(κ ) ( ) ]
∑ k2q Ck Ck Ck Ckke ∑ qke + ∑ qk − ∑ kqke + ∑ kqk ∑ kqke .
k≤κ k≤κ k>κ k≤κ k>κ k≤κ
(3.4.14)
No we use the facts that ∑k≤κ qk +∑k>κ qk = 1 (since (qk)k∈N0 is a probability distribution)
and ∑ (1) (1)k∈N0 kqk = bp = ap = ap (sp) (see Corollary 2.2.2; (qk)k∈N0 = Poipb has expectation
pb). Furthermore, note that C(a(1)p (sp),sp) = 0 by optimality (which can be seen in the same
way as the fact that B(a(1)p (s),s) = 0 above). Then we get
(a(1) ′ 2p ) (sp) = ∂B∂Cϕ([0,0) = ∑ k qk −bp ∑ kqkk≤κ k≤κ ]
−bp ∑ (bp)
k (bp)k d
= bpe (k+1) −bp ∑ = p sp,
k≤κ−1 k! k≤κ−1 k! dp
as we see from (3.3.4). Recall that p∗ is the unique maximizer for p 7→ sp. According to
Lemma 3.1.1, this (and therefore (a(1) ′ ∗ ∗p ) (sp)) is positive if p < p and negative if p > p .
This implies all assertions of Lemma 3.4.1 for p ≠ p∗.
Now we consider the case p = p∗ characterised in (3.4.5). Here it will not be successful to
rely on the characterisation of a(1)p (s) by 0 = B(a
(1)
p (s),s) and to consider the derivative with
respect to s in s = sp∗ only, since ∂B∂Cϕ(0,0) = 0 for p = p∗. Instead, we use (3.4.8) and
50
University of Ghana http://ugspace.ug.edu.gh
explicitly look at the difference
∑ q eCk[k−a ∗]+
a (s)− ∑a (s ) = ∂ ϕ(0,C)−bp∗ k p= k≤κ k>κ
qk[k−ap∗]
p∗ p∗ p∗ B ∑ ≤ Ckk κ qke +∑k>κ qk (3.4.15)
∑k≤κ qk[eCk −1][k−ap∗ ]= ,
∑ ≤ q Ckk κ ke +∑k>κ qk
with C =C(a(1)p∗(s),s). We used in the last step that ∑k>κ kqk = ap∗−∑k≤κ kqk and ∑k∈N0 qk =
1. Note that C < 0 for s < sp∗ and C > 0 for s > sp∗ . Indeed, a similar calculation as in
(3.4.11) shows that
[
d d ( )]
inf I(1)(a,s,r) = sC(a(1)(s),s)−ϕ 0,C(a(1)(s),s) =C(a(1)p∗ p∗ p∗ p∗(s),s), s ∈ (0,∞).ds r,a ds
Now note that sp∗ is defined as the minimizer of the function s →7 inf I(1)r,a p∗ (a,s,r); hence it
is decreasing left of the minimal point and increasing right of it.
Write g(C) = ∑κk=1 qk[eCk −1][k−ap∗ ] for the numerator of the right-hand side of (3.4.15).
Clearly g(0) = 0. Recall from above that g′(0) = 0 and observe that, for any C < 0,
κ
g′(C) = ∑ kq Ck Cap Capke (k−ap∗)< e ∗ ∑ kqk(k−ap∗)+ e ∗ ∑ kqk(k−ap∗) = 0.
k=0 k≤ap∗ k : ap∗<k≤κ
Hence, g is strictly decreasing in (−∞,0] and hence positive in (−∞,0). An analogous
argument shows that g′(C)> 0 for C > 0:
κ
g′(C) = ∑ kqkeCk(k−ap∗)> ∑ kqk(k−ap∗)+ ∑ kqk(k−ap∗) = 0.
k=0 k≤ap∗ k : ap∗<k≤κ
Hence g is strictly increasing and positive in (0,∞). This implies that ap∗(s)> ap∗(sp∗) for
any s ̸= sp∗ and finishes the proof of the lemma. □
51
University of Ghana http://ugspace.ug.edu.gh
Chapter 4
Summary, conclusion and
recommendations
4.1 Summary
This research extended the general concept of considering interference/capacity constraint
only at the first instance a message attempts to makes a hop. An ideal and more realistic
approach is to consider interference/capacity constraint anytime a message makes a hop
until it gets to the intended receiver.
Each of the objectives outlined in Chapter one has been duly answered in this thesis. More
specifically,
• Objective one which seeks to propose a version of Aloha and slotted Aloha has been
duly described in Section 2.1. Both models have been described in relation to the
number of sending attempts, medium access probability and how messages are able
to access a communication channel. In both models, it is assumed each channel can
only transmit if there are not more than κ number of message.
52
University of Ghana http://ugspace.ug.edu.gh
• The goal of objective two was to derive large deviation results for the proposed models
described in Section 2.1. Theorem 2.2.1 shows the large deviation results for the two
models. The proof of Theorem 2.2.1 for l = 2 is in Section 2.3.1 and for l = 1 is in
Section 2.3.3. In Section 2.3.3 a proof of an alternative representation (2.2.7) for the
rate function of l = 1 can also be found.
• The goal of objective three was to derive minimisers for the large deviation rate func-
tions. Corollary 2.2.2 which is a consequence of the proof in Section 2.3.1 answers
this objective. This is the statement of Lemma 2.4.1 which has also been rigorously
proved.
• Objective four was duly answered in Section 3.2. A direct consequence of this ob-
jective is Lemma 3.1.1 and Theorem 3.2.1. This objective answers a very important
question. What is the most likely reason that the throughput is below the theoretically
optimal one? Is the reason due to too few or too many attempts? Theorem 3.2.1,
clearly answers this question using the large deviation results.
4.2 Conclusion
In the Aloha model it is assumed that messages decide independently with probability p
whether to transmit to an intended receiver or not. In the event that too many messages
are sent out with a high probability, this results in the failure of all the messages. A good
way to reduce this total cancellation of messages is the introduction of the slotted Aloha.
An important question of optimisation then is, what appropriate transmission probability p
should be chosen such that very large number of messages can be transmitted at a time. It
turns out that, the optimal value of p must be such that, the sending attempts bp is smaller
than κ . It is clear that Aloha and slotted Aloha can be described using large deviation
techniques. The result shows that there exist unique minimisers for the large deviation rate
53
University of Ghana http://ugspace.ug.edu.gh
functions. These are stated and proved in Chapter three. It was also possible to derive an
alternative representation of the results from the Cramer theorem using the Sanov theorem
by using a cutting argument.
The existence of a unique optimal message transmission p was also proved. This means that,
it is possible to choose a transmission probability that can ensure that maximum throughput
is realised. This optimal probability was also shown to be unique. From the result, one can
deduce tractable large deviation result for the number of successes SN for the case l = 1
using the alternative formulation of Theorem 2.2.1 for l = 1, but not for l = 2. Theorem
3.2.1 clearly shows that, for the optimal choice p = p∗, the event of non-optimal throughput
always comes with overwhelming probability from too many message attempts.
This research is different in many ways to other similar models which dealt with only one
channel. This is because most of these papers considered purely simulated results and com-
putation of expectations for even the simple case. No large deviation result has so far been
derived for the multichannel models using large deviations in the past.
4.3 Recommendations for future research
There is quite a number of discussable extensions to the models presented in this thesis. A
few options are itemized below;
• One can look at the case where the upper limit of the number of messages through
each channel is allowed to go to infinity.
• One can also look at the case where the κ number of messages is allowed to depend
on the spatial distribution of the network nodes. Meaning each κ can depend on how
many messages are at a particular place at a given time.
• One can also look at the case where instead of considering Poisson points, we extend
54
University of Ghana http://ugspace.ug.edu.gh
to the Cox process. This will add another layer of randomness to the model to make
it even more realistic.
• One could also extend the same ideas in this thesis to another protocol. Particu-
larly, the CSMA protocol, where each sending attempt requires some miniminal pre-
information like the existence of an idle channel.
• A continuous time version which I am currently working on could be applied to the
Aloha and the CSMA protocols.
• Another version could be, to directly look at interference constraints in the Aloha and
slotted Aloha models using large deviations.
• Theorem 3.2.1 for l = 2 could not be solved hence can be taken on as further research
topic.
Below I briefly describe another model that was brainstormed and could be adopted and
researched on using other large deviation theorems or techniques. This is a model of mes-
sage trajectories which like this research depends on message hops and as such has some
similarities with this current work.
4.3.0.1 Trajectory of messages
Define a trajectory of messages from Xi to Yi as Ti : Xi → Yi. Now for any i ∈ N, express the
vector of message trajectories from user Xi to Yi as
T (1)= (X ,T , ...,T ki−1 (s)i i i i ,Yi) = (Ti )s∈0,...,ki, ki ∈ N
such that T (s) T (s+1)i = i is possible where s is the time for a hop and ki is th length of the
ith trajectory. Each message has a function of relays and that only one message is sent out
at a time. Suppose we define the empirical measure of message hops from X to Y and also
55
University of Ghana http://ugspace.ug.edu.gh
the number of possible trajectories per unit time. A question such as the appropriate hop
length can also be analysed. We can now study the following empirical measure of messages
trajectories;
1 N
LN = ∑ ∑ δ (i) (4.3.1)N Tx,y i 1 x,y=
A natural question is, what is the large deviation behaviour of of this empirical measure un-
der different assumptions of the number of messages from X to Y . The number of messages
can be such that it is either deterministic or random depending on how complicated one
wants it to be. Several questions can be formulated and an attempt can be made at answer-
ing them using large deviations. Questions such as; what is the minimum hop for a typical
trajectory, the length of a typical trajectory and average number of trajectories conditioned
on the number of participants in the network can be investigated.
56
University of Ghana http://ugspace.ug.edu.gh
References
Achir, N., Bouchaala, Y., Muhlethaler, P., and Shagdar, O. (2016). Comparison of spatial
aloha and csma using simple stochastic geometry models for 1d and 2d networks. In 2016
23rd International Conference on Telecommunications (ICT), pages 1–7. IEEE.
Baccelli, F. and Błaszczyszyn, B. (2009). Stochastic geometry and wireless networks, vol-
ume 1. Now Publishers Inc.
Baccelli, F. and Singh, C. (2013). Adaptive spatial aloha, fairness and stochastic geometry.
In 2013 11th International Symposium and Workshops on Modeling and Optimization in
Mobile, Ad Hoc and Wireless Networks (WiOpt), pages 7–14. IEEE.
Bajović, D., Jakovetić, D., Vukobratović, D., and Crnojević, V. (2014). Slotted aloha for
networked base stations. In 2014 IEEE International Conference on Communications
Workshops (ICC), pages 520–526. IEEE.
Bhandari, V. and Vaidya, N. H. (2007). Connectivity and capacity of multi-channel wire-
less networks with channel switching constraints. In IEEE INFOCOM 2007-26th IEEE
International Conference on Computer Communications, pages 785–793. IEEE.
Błaszczyszyn, B. and Mühlethaler, P. (2015). Interference and sinr coverage in spatial non-
slotted aloha networks. annals of telecommunications-annales des télécommunications,
70(7):345–358.
Blaszczyszyn, B., Muhlethaler, P., and Achir, N. (2012). Vehicular ad-hoc networks using
57
University of Ghana http://ugspace.ug.edu.gh
slotted aloha: point-to-point, emergency and broadcast communications. In 2012 IFIP
Wireless Days, pages 1–6. IEEE.
Coupechoux, M., Lestable, T., Bonnet, C., and Kumar, V. (2004). Throughput of the multi-
hop slotted aloha with multi-packet reception. In IFIP Working Conference on Wireless
On-Demand Network Systems, pages 301–314. Springer.
Dinitz, M. (2010). Distributed algorithms for approximating wireless network capacity. In
2010 Proceedings IEEE INFOCOM, pages 1–9. IEEE.
Dumas, C., Salaün, L., Hmedoush, I., Adjih, C., and Chen, C. S. (2021). Design of coded
slotted aloha with interference cancellation errors. IEEE Transactions on Vehicular Tech-
nology, 70(12):12742–12757.
Ellis, A., Suibhne, N. M., Saad, D., and Payne, D. (2016). Communication networks beyond
the capacity crunch.
Eroğlu, A. and Onur, E. (2021). Revisiting slotted aloha: Density adaptation in fanets.
Wireless Personal Communications, pages 1–30.
Fereydounian, M., Chen, X., Hassani, H., and Bidokhti, S. S. (2019). Non-asymptotic coded
slotted aloha. In 2019 IEEE International Symposium on Information Theory (ISIT),
pages 111–115. IEEE.
Frank, H. and El-Bardai, M. (1969). Dynamic communication networks with capacity con-
straints. IEEE Transactions on Communication Technology, 17(4):432–437.
Ganesh, A. J. and Torrisi, G. L. (2008). Large deviations of the interference in a wireless
communication model. IEEE Transactions on Information Theory, 54(8):3505–3517.
Ganti, R. K. and Haenggi, M. (2009). Bounds on the information propagation delay in
interference-limited aloha networks. In 2009 7th International Symposium on Modeling
and Optimization in Mobile, Ad Hoc, and Wireless Networks, pages 1–7. IEEE.
58
University of Ghana http://ugspace.ug.edu.gh
Gau, R.-H. (2006). Performance analysis of slotted aloha in interference-dominating wire-
less ad-hoc networks. IEEE Communications Letters, 10(5):402–404.
Gupta, P. and Kumar, P. R. (2000). The capacity of wireless networks. IEEE Transactions
on information theory, 46(2):388–404.
Haykin, S. (2005). Cognitive radio: brain-empowered wireless communications. IEEE
journal on selected areas in communications, 23(2):201–220.
Hirsch, C., Jahnel, B., Keeler, P., and Patterson, R. I. (2016). Large deviation princi-
ples for connectable receivers in wireless networks. Advances in Applied Probability,
48(4):1061–1094.
Hsu, F.-T., Liu, C.-T., and Su, H.-J. (2012). Exploiting channel state information in slot-
ted aloha with sinr capture. In 2012 IEEE Wireless Communications and Networking
Conference (WCNC), pages 1675–1679. IEEE.
Hunter, A. M., Andrews, J. G., and Weber, S. (2008). Transmission capacity of ad
hoc networks with spatial diversity. IEEE Transactions on Wireless Communications,
7(12):5058–5071.
Jahnel, B. and König, W. (2020). Probabilistic Methods in Telecommunications. Springer.
Jakovetić, D., Bajović, D., Vukobratović, D., and Crnojević, V. (2014). Slotted aloha for
networked base stations with spatial and temporal diversity. In 2014 IEEE International
Symposium on Information Theory, pages 1578–1582. IEEE.
Khan, M. A. A., Ma, H., Aamir, S. M., and Jin, Y. (2021). Optimizing the performance of
pure aloha for lora-based esl. Sensors, 21(15):5060.
König, W. and Tóbiás, A. (2017). A gibbsian model for message routeing in highly dense
multihop networks. arXiv preprint arXiv:1704.03499.
59
University of Ghana http://ugspace.ug.edu.gh
König, W. and Tóbiás, A. (2019). Routeing properties in a gibbsian model for highly dense
multihop networks. IEEE Transactions on Information Theory, 65(11):6875–6897.
Lee, M., Kim, Y., and Lee, T.-J. (2017). A spatial slotted-aloha protocol in wireless net-
works for group communications. EURASIP Journal on Wireless Communications and
Networking, 2017(1):1–16.
Leonardi, E. and Torrisi, G. L. (2013). Large deviations of the interference in the ginibre
network model. preprint (arxiv: 1304.2234), pages 1–35.
Li, R., Xia, Y., and Chi, K. T. (2017). Optimal resource allocation with node and link
capacity constraints in complex networks. In 2017 IEEE International Symposium on
Circuits and Systems (ISCAS), pages 1–4. IEEE.
Li, Y. and Dai, L. (2015). Maximum sum rate of slotted aloha with capture. IEEE Transac-
tions on Communications, 64(2):690–705.
Ma, R. T., Misra, V., and Rubenstein, D. (2008). An analysis of generalized slotted-aloha
protocols. IEEE/ACM Transactions on networking, 17(3):936–949.
Médard, M., Huang, J., Goldsmith, A. J., Meyn, S. P., and Coleman, T. P. (2004). Capacity
of time-slotted aloha packetized multiple-access systems over the awgn channel. IEEE
Transactions on Wireless Communications, 3(2):486–499.
Munari, A., Clazzer, F., Liva, G., and Heindlmaier, M. (2020). Multiple-relay slotted aloha:
performance analysis and bounds. IEEE Transactions on Communications, 69(3):1578–
1594.
Munari, A., Heindlmaier, M., Liva, G., and Berioli, M. (2013). The throughput of slot-
ted aloha with diversity. In 2013 51st Annual Allerton Conference on Communication,
Control, and Computing (Allerton), pages 698–706. IEEE.
60
University of Ghana http://ugspace.ug.edu.gh
Neel, J., Buehrer, R. M., Reed, B., and Gilles, R. P. (2002). Game theoretic analysis of
a network of cognitive radios. In The 2002 45th Midwest Symposium on Circuits and
Systems, 2002. MWSCAS-2002., volume 3, pages III–III. IEEE.
Torrisi, G. L. and Leonardi, E. (2012). Simulating the tail of the interference in a poisson
network model. IEEE transactions on information theory, 59(3):1773–1787.
Umehara, D., Yamamoto, T., and Yuan, J. (2018). Success prioritized slotted aloha with
sleep function. In 2018 12th International Conference on Signal Processing and Com-
munication Systems (ICSPCS), pages 1–7. IEEE.
Xu, Y., Liang, B., Boudreau, G., and Seyedmehdi, S. H. (2018). Maximizing spatial alpha-
fairness in multi-tier multi-rate spatial aloha networks. IEEE Transactions on Communi-
cations, 67(3):2036–2051.
Yang, S., Chen, Y., Liew, S. C., and You, L. (2015). Coding for network-coded slotted
aloha. In 2015 IEEE Information Theory Workshop (ITW), pages 1–5. IEEE.
Yavascan, O. T. and Uysal, E. (2021). Analysis of slotted aloha with an age threshold. IEEE
Journal on Selected Areas in Communications, 39(5):1456–1470.
Zeitouni, A. D. O. and Dembo, A. (1998). Large deviations techniques and applications.
Applications of Mathematics, 38.
61