LIMITED SENSING RANDOM ACCESS ALGORITHMS
by
Oluwapelumi. A. Idowu
B.S., Oral Roberts University, 2010
A Thesis submitted to the
Faculty of the Graduate School of the
University Of Colorado in partial fulfillment
of the requirement for the degree of
Master of Science
Electrical Engineering
2013
This thesis for the Master of Science degree
has been approves for the
Electrical Engineering Program
by
Dr. Titsa Papantoni, Advisor
Dr. Yiming Deng
Dr. Jan T. Bialasiewicz
Date : April 19th 2013.
Idowu Oluwapelumi (M.S., Electrical Engineering)
Limited Sensing Random Access Algorithm
Thesis Directed by Professor Titsa Papantoni
ABSTRACT
This project presents the properties of a class of Limited Sensing Random Access
algorithms. The operations and properties of the algorithms are presented in detail and
compared with the ALOHA protocol. In particular, the performance of the algorithms in
the presence of the limit Poisson user model is investigated and compared with that of the
ALOHA protocol. In addition, performance evaluation of these algorithms and
comparison with the ALOHA protocol are also performed in environments where
admission delay constraints are imposed.
The form and content of this abstract are approved. I recommend its publication.
Approved: Dr. Titsa Papantoni
in
DEDICATION
This thesis is dedicated to my family, who has been of tremendous support from
the time I started my program at University of Colorado Denver, even to this very point. I
am forever grateful. Also to my friends who encouraged me when I needed it and also to
my friend Prince, who helped out with the coding aspect of my project, I am thankful for
all your support through this process. Last and definitely not the least, I would like to
thank my husband, Eric, who has been with me every step of the way. His encouraging
words and also assistance during my project have given the strength that I need to be able
to get this far. Thanks a lot.
IV
ACKNOWLEDGMENT
I would like to give my sincere thanks to my advisor, Dr Titsa Papantoni. I had the
opportunity to take some classes such as Computer Communication, which is the
foundation for my thesis. I would like to thank her for her relentless discipline in wanting
me to work hard and achieve the very best. I would also like to thank all the professors I
have had the opportunity to sit in their classes and learn from them things I believe would
help me in my career pursue.
v
TABLE OF CONTENTS
Figures.......................................................................viii
Tables..........................................................................ix
Chapter
1. Introduction..................................................................1
2. Fundamental Concepts and Outline of Analytical Approaches ....................4
2.1 Throughput Computation of a Given RAA........................................5
3. The ALOHA Random Access Algorithm.............................................7
3.1 Throughput Analysis for M independent Users Generating Memoryless Packet.....7
3.2 Throughput Analysis for Varying Number of Users............................10
3.3 Throughput of the Exponential Backoff ALOHA Modification..................11
4. The Binary Split Random Access Alogorithm....................................12
5. The Limited Sensing Stack Random Access Alogorithm...........................15
5.1 The Limited Sensing Initialization Process for the Limit Poission Population.17
5.2 Throuughput Analysis for the Limit Poission Population......................20
5.3 Computation of the Expected CRI Length for 2 Cell Stack RAA (K= 2)...........22
5.4 Delay Analysis for the Limit Poission Population............................24
5.5 Sensitivity to Feedback Errors..............................................26
6. Evaluation in the PresenceAdmission,Delay Constraints, Conclusion and Future.28
6.1 Conclusion..................................................................30
6.2 Future Work ...............................................................31
Appendix
A. TwoCell Stack .............................................................32
B. ThreeCell Stack ...........................................................34
C. ALOHA Protocol Stack .......................................................36
vi
Bibliography
LIST OF FIGURES
Figure
3.1 The ALOHA Throughput as a Function of the number M of users.............10
5.1 Expected Delays in Slot Units...........................................26
6.1 Expected Delays (Admission Delays 80 slots).............................29
6.2 Rejection Rates (Admission Delays 80 slots).............................29
6.3 Expected Delays (Admission Delays 200 slots)............................29
6.4 Rejection Rates (Admission Delays 200 slots)............................29
6.5 Expected Delays (Admission Delays 400 slots)............................30
6.6 Rejection Rates (Admission Delays 400 slots)............................30
viii
LIST OF TABLES
Table
5.1 Stability Regions and Optimal Windows for Stack RAAs........................24
5.2 Throughputs in the Presence of Feedback Errors...............................27
IX
1. Introduction
This thesis focuses on the randomaccess approach, for the accessing of a single,
errorless, slotted channel, by independent, identical, packet transmitting, bursty users. The
global properties of the user/channel model considered are as follows: All transmitted
packets have identical length each requiring the length of a single slot for transmission;
the transmission by all users is synchronous, where they are allowed to start transmission
only at the beginning of some slot; and there are no propagation delays in the channel
feedback information obtained by the users. Also, if at least two packets attempt
transmission within the same slot, a collision occurs and such an event is initially the only
cause for faulty transmissions; that is, a slot occupied with a single packet results in
successful transmission. A collision results in complete loss of the information carried by
the collided packets; thus, retransmission of such packets is then necessary. The outcome
per slot possibly accessible by the usersnamed feedback level is binary, distinguishing
Collision (C) versus Non Collision (NC), or ternary, distinguishing between collisions
(C), versus emptiness (E) versus success (S). It is noted that a NC event corresponds to a
slot that is either empty or occupied with a single packet transmission, while an S event
corresponds to a slot occupied with a single packet whose transmission is then successful.
The accessibility of the feedback level outcomes by the users named channel sensing is
a characteristic of each Random Access Algorithm (RAA) and specifies the time instants
(in slots) when each user is required to sense the feedback level outcomes (accessible by
either channel sensing or broadcasting). Based on channel sensing requirements, the
existing RAAs may be classified as members of one of the three distinct channel sensing
classes below:
1
Minimal Sensing RAA Class: Each user is required to sense the feedback level outcome
of only those slots within which it transmits.
Limited Sensing RAA Class: Each user is required to sense continuously the feedback
level outcomes of all slots contained in time periods within which any of its packet is in
the system; that is, from the slot within which the packet is generated to that within which
this packet is successfully transmitted.
Full Sensing RAA Class: Each user is required to know the overall feedback history of
the channel, from the beginning of time and even before the user became part of the
system.
In regards to user population models, the following distinction will be necessary,
Known User Population Model: The identities of all users are distinct and known to the
system. This class model implies finite member.
Unknown User Population Model: The identities of the users are unknown to the system,
usually due to timevarying user characteristics. These class members may be finite or
infinite members.
Limit Poisson User Population Model: Infinitely many identical Bernoulli users,
comprising an aggregate Poisson packet generating process, where each packet is a
separate user. This is a special case of the unknown user population model.
Historically, the RAA evolution started with Abramsons ALOHA algorithm, which
belongs in the Minimal Sensing RAA class, it assumes the availability of C versus NC
2
feedback outcomes and is unstable, attaining throughput zero in the presence of the Limit
Poisson User Population Model.
The developed algorithms in the Full Sensing RAA class provided valuable insight.
While the algorithms in this class (Full Sensing) are nonimplementable in environments
with unknown user models, due to the requirement that all users know the overall
feedback history of the channel, the algorithmic studies in it led to implementable
algorithms in the Limited Sensing RAA class. The first such algorithm was developed by
Tsybakov and Mikhailov [1], where the feedback level is C versus NC, where each packet
arrival accesses freely the infinite cell stack in the presence of the Limit Poisson
Population model, the throughput of the algorithm is 0.134. Later, a class of RAA named
Limited Sensing Stack RAAs was developed by Tsybakov and Likanov [2], Vvedeskaya
and Tsybakov [3], Georgiadis et al [4], Paterakis et al [5] and Burrell et al [6], A stack
with finite cells, where for C versus NC feedback level and in the presence of the Limit
Poisson Population model, the maximum attained throughput is 0.429, can depict the
collision resolution process of these Limited Sensing stack RAAs. Error sensitivity studies
of the latter stack algorithms were performed by Vvedeskaya and Tsybakov [3], by
Georgiadis et al [4], by Paterakis et al [5] and by Burrell et al [6], In general class is
characterized by low sensitivity to feedback errors. Finally, Georgiadis et al [7] modified
the algorithm in and for Limited Sensing operation, at the expense of increased
operational complexity; the modified Limited Sensing algorithm maintains 0.4872
throughput in the presence of the Limit Poisson Population model, while, it also
maintains its high sensitivity to feedback errors.
3
2. Fundamental Concepts and Outline of Analytical Approaches
Random Access Algorithms (RAAs) are deployed when the user population is
unknown. In the study of RAAs, the fundamental concepts arising, that also characterize
their performance, are: system stability and induced delays. Given some RAA and user
population, we define:
Throughput: This is the maximum aggregate packet traffic rate X* for which the
user/RAA system is stable. Then, (0, X*) is named the stability region of the system.
Per Packet Delay: The distance, in slot units, between the arrival instant of a packet
arrival and the instant when its transmission has been completed.
Regarding user/RAA system stability in the presence of independent users that
generate memoryless packet streams, the existing developed RAAs induce a sequence
{Tn}n>o of time instants when consecutive Collision Resolution Intervals (CRIs) intervals
occur, where the packet backlogs {Sn}n,o at the instants {Tn J n 0 form an irreducible and
aperiodic Markov Chain. Thus, system stability corresponds then to the ergodicity of the
Markov Chain {Sn}n,o. On the other hand, Paterakis et al proved that as the size of the
above user population increases, the stability region of any of the existing RAAs is that
corresponding to the Limit Poisson Population model. Therefore, the throughput of any
one of the existing RAAs in the presence of the Limit Poisson Population model is a lower
bound to the throughput attained by the RAA in the presence of independent users that
generate memoryless packet streams. At the same time, the throughput of such an RAA in
the presence of the Limit Poisson Population model is then the highest rate for which the
4
Markov Chain (Sn}nois ergodic, where this chain also induces then infinitely many states.
The theories and results developed by Kaplan [8], Spankowkii [9], Spankowski et al [10],
Pakes [11] and Tweedie [12] were applied to provide a general approach to the
computation of the throughput of the existing RAAs, in the presence of the Limit Poisson
Population model. This approach is also applicable to finite independent user populations
that generate memoryless traffic streams, and it is summarized by the following steps:
2.1 Throughput Computation of a Given RAA
(a) Given the user model, identify appropriate measure of system backlog.
(b) Consider the beginnings A and B of two consecutive CRIs, where A precedes B,
and let SAand Sb denote the backlogs at A and B, respectively.
(c) Require that the conditional expected backlog E{Sb/Sa=s } be less than s, for all
values of s that are larger than some finite number d determined by the RAA
operation. Derive the throughput expression imposing this requirement, which
represents negative expected backlog drift across consecutive CRIs.
(d) In the throughput expression in (c), the computation of the expected length of a
CRI is required. Derive the tight bounds that may be needed in this computation.
(e) Use the result from step (d) to compute the value of the throughput.
The study of packet delays within the stability region of any of the existing
The study of packet delays within the stability region of any of the existing
RAAs recruits results from the regenerative theory, as found in Cohen [13], Kantorovich
5
et al [14] and Stidman [15], Indeed, in the presence of the user models considered above,
each such RAA generates time instants when the algorithm restarts independently from its
past. Then, the number of generated packets from the beginning of time to the point when
such a time instant occurs constitutes a renewal process, where the delays determine a
regenerative process with respect to the former renewal process and where the time
instants of algorithmic restarts constitute then renewal points. This allows for the
computation of the expected per packet delays as a ratio of the expected aggregate packet
delays between consecutive renewal points, over the expected number of packets
transmitted between these points, as discussed in detail by Georgiadis et al [16], where the
computation of delay bounds is also necessary in the process.
6
3. The ALOHA Random Access Algorithm
The ALOHA Random Access Algorithm operates with binary NC vs. C feedback
level outcomes and belongs in the Minimal Sensing RAA class. Given a user population,
its operations are described below.
Operations
(a) All the users deploy a common transmission probability p in the system.
(b) Each user has its generated packets queued, where these packets are transmitted
on the first comefirst serve basis, with the head packet being the oldest in the
queue.
(c) Within each slot, each user whose queue is nonempty transmits the head packet
in its queue with probability p. A user that actually transmits within the slot,
subsequently observes the resulting NC vs. C feedback outcome: if the outcome
is NC, the user concludes that its packet is successfully transmitted; if the
outcome is, instead, C, the user repeats the process within the next slot, by
retransmitting its head packet with probability p.
Next, I will proceed with the throughput analysis of the ALOHA RAA, when deployed
by M independent users, each generating memoryless packet streams.
3.1 Throughput Analysis for M Independent Users Generating Memoryless Packet
Streams
Given M users, we will measure the backlog at the beginning of some slot t, as the total
number k of packets queued by all the users. Then, due to the memoryless property of the
7
traffics generated by the users, in conjunction with the memoryless characteristic of the
ALOHA operations, the backlog at the beginning of slot t+1 depends only on the value k
and the common transmission probability p. In other words, if {Tn}n,0 denotes here the
sequence of consecutive beginnings of slots and if {Sn}n,o is then the sequence of the
corresponding backlogs at these beginnings, then, {Sn}n,o constitutes an aperiodic and
irreducible Markov Chain.
Let us define:
B: The set containing all aggregate backlogs, such that at least one packet per user is
included.
E{Sn+i / Sn= k 8 B) : The expected aggregate backlog at the time instant Tn+i, given that
the backlog at the time instant Tn equals k and is such that at least one packet per user is
included.
X : The aggregate packet rate in expected number of packets per slot. Then,
E{ Sn+i / Sn = k = k + X Mp(lp)M_1 (1)
where, Mp(lp)M_1 equals the probability of a successful transmission per slot, as well as
the expected number of successfully transmitted packets per slot, when all M users are
active, as is the case when the backlog k is a member of the set B. The ergodicity theory
for aperiodic and irreducible Markov Chains, induces here the following theorem.
8
Theorem 1
The ALOHA RAA is stable iff the Markov Chain {Sn}n,o is ergodic. In turn, the
Markov Chain is ergodic, iff:
E{ Sn+i / Sn = k 8 B) k <0 ; for all k in B
which in view of (1) gives that the necessary and sufficient condition for ALOHA
stability is:
X < M p (1p ) M_1 = X* (p M) (2)
The quantity X*(p,M)in Theorem 1 is the ALOHA throughput for M independent users
generating memoryless packet streams, when the common transmission probability is p.
The corresponding stability region is then
(0, X*(p,M)). The rates in the stability region are expected aggregate number of packets
generated per slot.
Maintaining the number of users M fixed, the throughput in (2) can be maximized
with respect to the value p. The latter maximum is easily found to equal (11/M)m_1 and
attained for p = 1/M. It is also straight forward to conclude that the quantity (1 1/M)xm is
monotonically decreasing with increasing M, converging asymptotically to the value 1/e.
The latter result led to the unfortunate early conclusion that the throughput of ALOHA for
infinite users (or the Limit Poisson Population) is 1/e, where the fact that this meaningless
result can be only attained when the transmission probability is zero (limit of 1/M for M
>o) was ignored.
9
3.2 Throughput Analysis for Varying Number of Users
To study meaningfully the ALOHA throughput as the number of users increases, I
fixed the transmission probability p to a strictly positive value and study the X*(p,M)
expression in (2), as M increases. Figure 1 exhibits the behavior of X*(p,M) as a function
of M. From the figure, we observe that as M increases, the throughput X*(p,M) converges
to zero. As a consequence to this observation, in the presence of the Limit Poisson
Population, the ALOHA throughput is zero.
Figure 3.1: The ALOHA Throughput as a Function of the Number M of Users
The Probability of Transmission is p > 0.
1
In(lp)
# of Users Attaining Maximum Throughput:
M* = arg max(Mjp(l p)Ml~',M2p(l p)M2_1)
Mr
1
ln(lp)
M,
Maximum Throughput: X* (p) = max M p (1 P) M_1 = M*p (1 p) M 1
M
10
3.3 Throughput of the Exponential Back Off ALOHA Modification
Current applications in Cellular and Sensor technologies deploy an ALOHA
modification, where after each unsuccessful transmission attempt, a user defers
retransmission by a number of slots which grows exponentially with the number of its
unsuccessful attempts. This operation has been named exponential back off. Since the
modification also deploys packet abortion after the number of retransmissions exceeds a
given limit, the number of back offs is bounded. In addition, in a straight forward fashion,
the exponential back offs can be equivalently modeled by varying transmission
probabilities per slot, whose possible nalues are then finite. Let q and r denote
respectively the largest and smallest among these values. Then, for the model of M
independent users whose packet traffics are memoryless, the throughput of the exponential
back off ALOHA modified algorithm is bounded from above by the expression Mq(lr)M'
\ Fixing the q and r values and allowing the latter bound to vary with the M value, we
observe a behavior qualitatively identical to that in Figure 3.1. Thus, the throughput of the
ALOHA exponential back off modification converges to zero as the number of users
increases. As a consequence, in the presence of the Limit Poisson Population, the
throughput of the exponential back off ALOHA modification is zero.
11
4. The Binary Split Random Access Algorithm
The binary split algorithm belongs in the full sensing RAA class, since user
synchronization with the algorithmic operations requires knowledge of the overall system
feedback history, as well as continuous feedback monitoring until successful transmission.
The algorithm utilizes binary NC vs. C feedback outcomes per slot and its operations may
be described by an initialization and a collision resolution processes, where initialization
refers to the initially selected set of packet arrivals that are successfully transmitted during
the collision resolution process; the time period (in slot units) that the latter process lasts is
named Collision Resolution Interval (CRI). The nondynamic and the dynamic versions
of the algorithm differ only in the initialization part, while their collision resolution
processes are identical. In the nondynamic version, all the waiting packet arrivals are
selected for participation in the CRI, while, in the dynamic version, only a subset of these
packets are selected, instead. We will proceed by first stating the algorithmic operations
during a CRI.
Operations During a CRI
During a CRI, each involved packet/user is required to observe slot feedbacks
continuously until successful transmission. The first slot of a CRI is occupied with
simultaneous transmissions from the total set of packets selected during the initialization
part of the algorithm. If the latter set contains at most one packet, the CRI lasts one non
collision (NC) slot, during which the initially selected set of packets is successfully
transmitted. If the set of arrivals selected during the initialization process contains at least
two packets, instead, then the first CRI slot is a collision (C) slot and a collision
resolution process begins. The algorithmic steps of this process may be described in two
12
ways: (1) as viewed by an imaginary outside observer and (2) as implemented
independently by each packet involved in the process. We provide both descriptions
below, where time is measured in slot units, where slot t occupies the time interval (t1, t]
and where xt denotes the feedback outcome of slot t (NC vs. C).
(1) Operations as Viewed by an Outside Observer
As viewed by an outside observer, the operations during a CRI that starts with a C
slot may be described via a stack containing infinite cells indexed by i, where i = 1,2,....
The lowest cell 1 in the stack is the transmission cell; that is, the packets transmitted in
slot t are those placed in cell 1 at the same slot. The remaining cells in the stack are
withholding cells, such that increased cell index implies lower withholding priority. The
cell transitions during the CRI are described as follows:
(a) At the first slot of the CRI, all packets in the initialization set are placed in cell 1.
(b) If x t = NC, then ,
The packet (if any) that was in cell 1 at t is successfully transmitted within slot t.
The packets (if any) that were in cell i; i > 2 at slot t, move to cell i 1 at slot
t+1.
(c) If x t = C then,
Each packet that was in cell 1 at slot t, stays in cell 1 at slot t+1; with probability
0.5 or moves to cell 2 at slot t+1; with probability 0.5.
The packets (if any) that were in cell i; i > 2 at slot t, move to cell i + 1 at slot
t+1.
13
(2) Independent Implementation per Packet/User
The CRI operations may be implemented independently by the packets/users, via the
use of a counter whose values may be any one of the positive integers. Let then c t denote
the counter value of some packet at slot t, where c t = 1,2,.... The packet is transmitted in
slot t if and only if c t= 1. The algorithmic operations during a CRI for any involved
packet are then described by transitions of its counter values, as follows:
(a) Ifx t = NC and c t= 1, then the packet is successfully transmitted within slot t.
(b) If x t = NC and cts= 2, then ct+i = Ct 1.
(c) Ifx t = C and c t 2, then ct+i = Ct + 1.
(d) If x t= C and c t = 1, then, Ct+i = 1; with probability 0.5 or ct+i = 2; with
probability 0.5.
14
5. The Limited Sensing Stack Random Access Algorithm
In Limited Sensing, if the collision resolution process can be modified to induce
distinct CRI endings, then a user arriving in the system may be synchronized with the
algorithmic operations without the need to know the overall system feedback history; thus,
allowing for algorithmic implementability.
The Limited Sensing Stack RAAs were developed from a modification of the Window
Binary Split RAA, via an initial imposed limitation on the size of the stack which
represents the collision resolution process. Thus, the feedback outcomes utilized per slot
are binary NC vs.C and each involved packet/user is required to observe slot feedbacks
continuously until transmission, while the collision resolution process during a CRI, as
viewed by an imaginary outside observer, may be described via the use of a stack
containing K cells. The same process, as implemented independently by each involved
packet/user, may be described via the use of a counter. We provide both descriptions
below, where, slot t represents the time interval (t1, t] and xt denotes the NC vs.C
feedback outcome of slot t.
(1) Operations as Viewed by an Outside Observer
The stack contains K >2 cells indexed from 1 to K. Cell 1 is the transmission cell;
that is, packets contained in cell 1 at slot t are transmitted within the same slot, while the
cells above it are withholding cells representing various withholding priorities. The cell
transitions during a CRI are described as follows:
(a) At the first slot of the CRI, all packets contained in the initialization set are placed
in cell 1.
(b) If x t= NC then ,
15
The packet (if any) that was in cell 1 at t is successfully transmitted within slot t.
The packets (if any) that were in cell i; i > 2 at slot t, move to cell i 1 at slot
t+1.
(c ) If x t = C then,
Each packet that was in cell 1 at slot t, places itself in cell i; i = 1,... ,K, with
probability 1/K at
slot t+1.
The packets (if any) that were in cell i; i > 2 at slot t, remain in cell i at slot
t+1.
(2) Independent Implementation per Packet/User
The CRI operations are carried independently by each involved packet/user via the
use of a counter. Let c t denote the counter value of a packet at slot t. This value may be
one of the positive integer numbers 1 to K, where the packet is transmitted within slot t iff
c t = 1. The transition of the counter values during a CRI are as follows:
(a) If x t = NC and c t= 1, then the packet is successfully transmitted within slot t.
(b) If x t = NC and c ts= 2, then ct+i = ct 1.
(c ) If x t = C and c t > 2, then Ct+i = Ct.
(c) If x t= C and c t = 1, then, Ct+i = i; i = 1,..,,K with probability 1/K.
As concluded from the above collision resolution operations, after a collision
within which it is involved, a packet places itself in either one of the transmission vs.
16
withholding states with equal probability, while after a collision within which the packet is
not involved, it maintains its existing state.
After careful observation of the collision resolution process described above, it is
concluded that each CRI that starts with a collision ends with the unique pattern of K
successive NC slots. In other words, for a CRI that starts with a collision, K successive
slots can not occur somewhere in the middle its process, while, at the same time, they
characterize uniquely its end. Taking now into consideration trivial CRIs that last a single
slot (those resolving at most one packet), and finally it is concluded that the observation of
K successive NC slots may lead to one of the following two assessments: either a CRI that
started with a collision ended or K successive trivial (a single slot lasting) CRIs occurred.
In either case, if a newly arrived user in the system waits until it observes K successive
NC slots, it is assured that at the end of the Kth such slot a CRI has ended. This leads to
the limited sensing initialization process described below for the Limit Poisson Population
model.
5.1 The Limited Sensing Initialization Process for the Limit Poisson Population
The patterns of K successive NC slots explained above allow for the implementation of
the stack algorithm without the need of the overall feedback history knowledge. Such
implementation is reflected by the initialization process, named Limited Sensing, which
imposes the requirement that each packet arrival observe continuously the slot
feedbacks, from the slot within which it arrives to the slot within which it is successfully
transmitted. Specifically, in the presence of the Limit Poisson Population, where each
packet is an independent user, a packet that arrives at time instant xi located within slot ti,
17
follows the process described below before entering a CRI, where a window of size A is
utilized.
(a) Starting with the slot ti of its arrival, the packet observes slot feedbacks passively,
until the first occurrence of K successive NC slots ending with slot t2. At the end
of slot t2, the packet is synchronized with the algorithmic collision resolution
process, being in the position to recognize all CRI endings after t2 (including those
of the trivial CRIs).
(b) kAt the end of slot t2, the packet checks its arrival instant xi against the arrival
interval (t2K + 1 A, t2K + 1):
(i) If xl 8 (t2 K + 1 A, t2 K + 1), the packet participates in the CRI that
begins with slot t2 + 1 and is successfully transmitted during its process.
(ii) If, instead, xi < t2 K + 1 A the packet updates its arrival instant to X2 =
xi + A and continues observing slot feedbacks sequentially and passively, until the
end slot t3 of the next CRI, when it repeats step (b) for t2 substituted by t3.
(c) In general, if t k is the ending slot of the (kl)th CRI after the packets arrival
and the packet has not yet participated in a CRI, the packets arrival instant update
at t k equals Xki = xi + (k1) A. The packet checks then Xki against the arrival
interval (tkK + 1 A, tkK + 1) and:
18
(i) If Tki is contained in (tkK + 1 A, tkK + 1), the packet participates in
the CRI that begins with slot t k + 1 and is successfully transmitted during its
process.
(ii) If, instead, in < tkK + 1 A, the packet updates its arrival instant
update to t k= xi+kA and continues observing slot feedbacks sequentially until the
next CRI end.
Regarding the initialization process described above, we make the following
observations: (1) The Limited Sensing initialization has lastcome first serve
characteristics. (2) While at the initialization state, a packet generates a sequence of
arrival instant updates, where each such update is generated at the beginning of each CRI
which the packet does not participate in. The updates are responses to the fact that a CRI
which does not include the packet resolves a length A interval which contains later (than
the packets arrival) packet arrivals. As a result, each update advances the arrival instant
of the packet by A. (3) The arrival instant update iki at the end t kof the (kl)thCRI is
checked against a length A arrival interval (t k K + 1 A, t k K + 1), whose right edge
lies Kl slots to the left of t k, where this is because packets that arrived within the latter
Kl slots have not yet observed the necessary for algorithmic synchronization and
possible nextCRI participation initial K successiveNC slots. This arrival interval (tkK
+ 1 A, t k K + 1) is named examined interval, where a sequence of such intervals is
generated during the initialization process. (4) A packet participates in the first CRI whose
examined interval its arrival instant update falls in.
19
5.2 Throughput Analysis for the Limit Poisson Population
In the throughput analysis, the specific location of the examined intervals has no effect;
only their length A does. Thus, the only algorithmic characteristics involved in this
analysis are the statistical properties of the generated CRIs, as induced by the collision
resolution process and the window size A. As with the Window Binary Split RAA, the
Limited Sensing Stack RAA induces a sequence of consecutive CRIs which, in the
presence of the Limit Poisson Population resolve arrival intervals. The backlogs {Sn}n,o at
the beginnings {Tn}n>0 of consecutive CRIs are measured by arrival intervals. In addition,
in the presence of the Limit Poisson Population, the sequence {Sn}n,o is an irreducible and
aperiodic Markov Chain whose ergodicity conditions determine the algorithmic
throughput. Theorem 2 in Section 4 applies directly here, where the only difference lies in
the computation of the conditional expected CRI lengths {Lk} k>o For completeness, we
restate the theorem here, as applied to the Limited Sensing Stack RAAs, where lag in this
case is defined as the composite total unexamined arrival interval. Considering window
size A, let us define:
X : The acting Limit Poisson rate, in expected number of packets per slot.
E{Sn+i / Sn = / > A }: The expected lag at the beginning of the (n+l)th CRI, given that the
lag at the beginning of the nth CRI equals / and is not less than A.
fix): The expected length of a CRI that resolves the arrivals within a size A arrival
interval, when the rate of the Limit Poisson process is X.
20
x = XA
The ergodicity theory of irreducible and aperiodic Markov Chains induces then the
following theorem.
Theorem 3
The Limited Sensing Stack RAA is stable iff the Markov Chain { Sn}n,o is ergodic. In
turn, the latter Markov Chain is ergodic iff:
E{Sn+i/Sn=/>A}/ = X/x) x < 0
Thus, the Limited Sensing Stack RAA is stable iff:
X < x//x)
If x maximizes the ratio x / /(x), then X* = x* //(x*) is the throughput of the
algorithm and is attained by a window size A* = x* / X*.
Defining by L k the expected CRI length, given that the CRI resolves a k multiplicity
collision, that the expected CRI length/(x) is given by the following expression:
/(x) =
k!
(3)
It is noted that as the number of cells K increases from the value two to infinity, a
class of RAAs arises which contains the Binary Split RAA. The members of this class
which may be implementable in the limited sensing environment are only those
corresponding to bounded K values. As with the Binary Split RAA, for any given finite K
value, the computation of the expected CRI length/(x) requires the development of
recursive expressions and bounds on the conditional expected CRI lengths {L k} k> o I
will present such recursions and bounds for the case of K =2; that is, for the Limited
21
Sensing Stack RAA whose stack contains two cells. The complexity of such recursions
increases with increasing number K of cells in the stack.
5.3 Computation of the Expected CRI Lengths for the 2 cell stack RAA (K = 2)
Let us define:
L k: The expected length of a CRI which starts with a k multiplicity collision.
L(k m ): The expected remaining length of a CRI which is at the state of containing k
packets in cell 1 and m packets in cell 2. Then, the following initial conditions and
relationships are clear.
L k = L(k, 0 ) L o = L(0,0 ) = L i = L(1,0) = 1
where the algorithmic operations during a CRI induce the following transitions of the L(k ,
m) quantities:
For all m > 1; L(0 m) = L(l, m) = 1 + L(m 0 )
For k > 2 ;
L(k,m) = l + 2 k
+ m i) =
= 1 + 2_iL(k,m) + 2k
L(i,k + mi')
Rearrangement of terms in the last equation leads to the following expression which,
for fixed sum k + m is recursive with respect to k.
For k > 2 ;
L(k,m) = 2k
L(i,k + mi)
22
For fixed k + m sum value, the recursive computation is repeated for increasing k
values, while this repeated recursive computation is performed sequentially for increasing
k + m sum values. The end result of this process is the recursive computation of the
quantities in the set (L k } k> o As with the Binary Split RAA, the cardinality of the latter
set is infinite, requiring the development of tight upper and lower bounds for large k
values. Such bounds were developed by J.C Huang and T.Berger [17], where, in contrast
to the Binary Split RAA case, their form is quadratic here. That is, for specifically found
a, P and y constant values, we have :
Fork>13; Lk~ ak2+pk + y (4)
In view of the expression in (15), the expected CRI length/(x) in (13) may be written
as,
/(x) Y(ak2 +fik + y) e' +
U k!
Lk ak2 Pky
0
k!
= ax2 + (a+ P)x + y + \ [Lkak2pky^ x (5)
0M3 k!
where the { L k} 0
Results for Varying K Values
For given K value, the computation of the expected CRI length ( as in (5) for K = 2),
in conjunction with the statements in Theorem 3 lead to the computation of the throughput
X* and the optimal examined interval length A* that attains it. In Table 1 below, we show
these computed values for the Stack RAAs with K = 2 and K = 3 cells.
23
5.1: Stability Regions and Optimal Windows for Stack RAAs
Stack RAA with K = 2 : X* = 0.4295 ~ 0.43 A* = 2.33
Stack RAA with K = 3: X* = 0.4295 ~ 0.43 A* = 2.5599
Window Binary Split RAA: X* = 0.4295 ~ 0.43 A* = 2.677
Common stability region: Xe (0,0.43 )
It may be conjectured that, as the size K of the stack increases, from 2 to infinity,
the RAA throughput remains unchanged, while, as viewed from Table 1, the optimal
length of the examined interval increases. Thus, the K value does not affect the
throughput, but does affect implementability, delays and sensitivity to feedback errors.
As compared to the ALOHA RAA, in the presence of the Limit Poisson
Population, the class of Limited Sensing Stack RAAs attain throughput 0.43, while
ALOHAs throughput is then zero. This is at the expense of increased, but reasonable and
implementable feedback sensing. Indeed, the Limited Sensing Stack RAAs require that
each packet/user sense the per slot feedback outcomes continuously, from the time it is
generated to the time that it is successfully transmitted. In contrast, ALOHA requires
sensing of feedback outcomes only for slots within which the packet is transmitted, but its
throughput rapidly converges to zero when the user population increases.
5.4 Delay Analysis for the Limit Poisson Population
The analysis of the delays induced by the Limited Sensing Stack RAAs, the renewal
theory is utilized again, where the algorithm induces regenerative points with respect to
24
the delay process. In the presence of the Limit Poisson Population and for given K, the
renewal points are the beginnings of CRIs whose initial lag is K slots long. For given K
value and some given rate X in the stability region, the per packet delay is then computed
as the ratio of the aggregate delays between consecutive renewal points, over the
aggregate number of packet arrivals between the same points. In Figure 2, we plot
computed expected delays as functions of the rate X, for the 2Cell Stack, the 3Cell Stack
and the Binary Split RAAs. It can be seen that for very light traffic (X near zero), a packet
is delayed only due to the initial algorithmic synchronization requirement, since no
collisions occur then. The latter requirement is 2 slots; for the 2Cell Stack RAA, 3 slots;
for the 3Cell Stack RAA and 0 slots for the Binary Split RAA. Adding to these numbers
the 0.5 slot accounting for the delay due to the midpoint average arrival instant of the
packet within its arrival slot, we finally obtain that for very light traffic, the expected
delays induced by the 2Cell Stack, the 3Cell Stack and the Binary Split RAAs are
approximately 1.5, 2.5 and 0.5 slots, respectively. As the rate X approaches the
throughput value 0.43, the expected delays of all three RAAs approach asymptotically
high values, while the expected delay of the Binary Split RAA remains uniformly lower
than that induced by the other two algorithms. Comparing the 2Cell Stack RAA with the
3Cell Stack RAA in terms of expected delays, we note that the 2Cell Stack RAA
outperforms the 3Cell Stack RAA for low traffic rates, while the outperforming is
reversed when traffic rates are relatively high. Finally the lastcome firstserve
characteristic of the limited sensing 2Cell Stack and 3Cell Stack RAAs induces higher
variances of the delay distributions, as compared to that induced by the Binary Split RAA.
25
Figure 5.1: Expected Delays in Slot Units
For the 2Cell, 3Cell and Binary Split RAAs
5.5 Sensitivity to Feedback Errors
Insensitivity to feedback errors, commonly caused by channel noise, is a
significant attribute to consider in the performance evaluation of RAAs. The specific issue
or interest is the throughput degradation when feedback errors cause misperception of NC
feedbacks, where sure instability results from C feedbacks misperceptions. We will draw
from the results when the throughputs of the 2Cell Stack, the 3Cell Stack and the Binary
Split RAAs were computed when empty or occupied with a single packet transmission slots
may be perceived as collision slots. Let us define:
26
8 : The probability that an empty slot may be perceived as a collision slot.
5 : The probability that a slot occupied with a single packet transmission may be perceived
as a collision slot.
In Table 5.2 below we include the throughputs attained by the 2cell, 3cell and Binary
Split RAAs for different values of the s and 8 probabilities. We observe the graceful
decline of throughputs when feedback errors are present, while the feedback error
resistence of the 2cell algorithm is evident, as compared to the remaining two other
algorithms.
Table 5.2: Throughputs in the Presence of Feedback Errors
Â£ 5 2Cell Stack RAA 3Cell Stack RAA Biuarv Split RAA
0.00 0.01 0.424 0.410
0.00 0.20  0.312 
0.00 0.40 0.255  0.262
0.00 0.50 0.363 0.156 
0.10 0.00 0.408  0,401
0.10 0.10 0.363 0.332 
0.20 0.00 0.377  0.355
0.20 0.10 0.328 0.254 
0.20 0.20 0.279 0.175 0.266
0.30 0.10 0.261 0.192
27
6. Evaluations in the Presence of Admission Delay Constraints, Conclusions and
Future Work
This section compares the performances of the 3cell and 2cell algorithms with
the ALOHA protocol, in the presence of admission delay constraints and the limit Poisson
user model. We note that in the presence of admission delay constraints the concept of
throughput is void, since then a percentage of the traffic is always rejected. In the
presence of admission delay constraints, the concept of throughput is substituted by the
concept of traffic success rate, which equals one minus the traffic rejection rate. Thus, in
the presence of admission delay constraints, the performance metrics computed for the 3
cell, 2 cell and the ALOHA algorithms were traffic rejection rates and expected per
packet delays, for the nonrejected traffic.
We considered admission delays of 80, 200 and 400 slots. Our results are
exhibited in Figures 6.1 to 6.6. From these figures, we observe that the ALOHA
algorithm does better than the 3cell and 2cell algorithms in terms expected delays of
those packets which were transmitted successfully, but is the worst in terms of rejection
rates. Also, as admission delay constraints become looser, the ALOHA algorithm becomes
worse in terms of expected delays and rejection rates, as compared to the 2cell and 3cell
algorithms.
28
Admission Delay 80 Slots
Admission Delay for 80
Figure 6.1:Expected Delays
Admission Delay 80 Slots.
Figure 6.2:Rejection Rates
Admission Delay 80 Slots.
Figure 6.3:Expected Delays
Admission Delay 200 Slots
Figure 6.4:Rejection Rates
Admission Delay 200 slots
29
Admission Delay 400 slots
Admission Delay 400 Slots
0.5.11.1 ,
0.4S \ 
* Two Cell
Three Cell l .
ALOHA I
035  i
S3 0.3 /
fi 0.25
8
a u^ 0.15 
0.1 0.05 .
CM
0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.
Rate (Lambda)
Figure 6.6:Rejection Rates
Admission Delay 400 slots
6.1 Conclusion
The class of window limited sensing random access algorithms was introduced,
whose collision resolution process can be depicted by a stack with finite number of cells.
All algorithms in the class are stable and implementable, possess relatively high
throughput, are robust in the presence of channel feedback errors and exhibit good delay
characteristics. In view of the ALOHA instability in the presence of increasing user
populations, the Limited Sensing Stack Random Access Algorithms (RAAs) are especially
attractive for deployment in various applications exemplified by cellular and clustered
sensor topologies. The latter algorithms are stable in the presence of increasing user
populations, attaining a throughput lower bound 0.43, they induce good delay
characteristics and are robust in the presence of channel errors. In environments where
ALOHAbased algorithms are presently deployed, the Limited Sensing Stack RAAs may
provide superior performance, well outbalancing the increased (as compared to ALOHA)
30
feedback sensing they require. We compared the above class with the ALOHA protocol,
in the presence of admission delays. We found that as the Poisson traffic rate and its
admission delay increase, the ALOHA protocol collapses (rejecting almost all traffic),
while the protocols in the introduced class maintain high standards.
6.2 Future Work
The limited sensing random access algorithms precsented and evaluated in this thesis
may be deployed in various environments, such as sensor environments that incorporate
high priority traffic. We plan to study such deployment of the algorithms, to apply
pertinent operational adjustments and evaluate their subsequent performance.
31
APPENDIX
APPENDIX A: TwoCell Stack
clear all
%{
collision(1, i)
collision(2 i)
collision(3, i)
collision,
collision(4 i)
%}
is position in time
is number of packets generated in position
is delay Or number of steps it took to resolve
is 1 if rejection or 0 if no rejection,
lambdaArray = zeros(2,9);
counter = 1;
for lambda = 0:0.05:0.4 % arrival rate
Tmax=80; % maximum time
AdmissionDelay = 5;
collision = zeros (4,10);
T(1)=random('Exponential',lambda);
i=l;
while i < Tmax
T(i+1)= T(i) + random('Exponential',lambda);
i=i+l;
end
for i=l:numel(T)
numberOfCollisionsAtTime = 0
delay = 0
for j=l:numel(T)
if floor(T(j)) == i1
numberOfCollisionsAtTime = numberOfCollisionsAtTime + 1
collision(1,i) = i1;
collision(2,i) = numberOfCollisionsAtTime;
end
end
%lambda = ( x ./ times);
if numberOfCollisionsAtTime == 1
delay = 1;
collision(3,i) = delay;
elseif numberOfCollisionsAtTime > 1
%cell = zeros(l,2);
% transq(i) = x;
cell(2) = numberOfCollisionsAtTime;
isResolved = 0;
while isResolved == 0
%get the module of cell 2
mymod = mod(cell(2),2) ;
%divide equally into 2 if number of packets are even
if mymod == 0
temp = cell(2)/2;
cell(2) = temp;
cell(l) = cell(l) + temp;
%send packet if cell 2 has 1
elseif cell(2) == 1
cell(2) = cell(1);
cell(1) = 0;
else
%divide contents of cell 2 and add half to cell 1
divided = cell(2) mymod;
cell(2) = divided/2;
cell(l) = divided/2 + mymod + cell(l);
end
fprintf('[ %d  %d ] \n',cell(1),cell(2));
delay = delay + 1;
if AdmissionDelay < delay
isResolved = 1;
collision(4,i) = 1;
collision(3,i) = delay;
elseif cell(l) == 0 && cell(2) == 0
isResolved = 1;
collision(3,i) = delay;
fprintf('\n');
end
end
else
end
end
k = sum(collision,2);
lambdaArray(1,counter) = lambda;
lambdaArray(2,counter) = k(3,l);
lambdaArray (3,counter)= k (4,1)
counter = counter + 1;
end
row = lambdaArray(1,:); %Lambda
col= lambdaArray(2,:); %Expected delay
tan = lambdaArray(3,:); %Rejection Rates
R= polyval (row,col );
R= R/100000000000000000000000;
plot(row, R, '*');
plot(row, R, 'r');
xlabel('Rate (Lambda)');
ylabel('Expected Delay (Slots)');
title ('Admission Delay 80')
hold on
i = i+1;
33
APPENDIX B: ThreeCell Stack
*{
collision(1, i)
collision(2 i)
collision(3, i)
collision,
collision(4 i)
%}
is position in time
is number of packets generated in position
is delay Or number of steps it took to resolve
is 1 if rejection or 0 if no rejection,
lambdaArray = zeros(2,9);
counter = 1;
for lambda = 0:0.05:0.4 % arrival rate
Tmax=80; % maximum time
AdmissionDelay = 4;
collision = zeros(4,10);
T(1)=random('Exponential',lambda);
i=l;
while i < Tmax
T(i+1)= T(i) + random('Exponential',lambda);
i=i+l;
end
for i=l:numel(T)
numberOfCollisionsAtTime = 0;
delay = 0;
for j=l:numel(T)
if floor(T(j)) == i1
numberOfCollisionsAtTime = numberOfCollisionsAtTime + 1;
collision(1,i) = i1;
collision(2,i) = numberOfCollisionsAtTime;
end
end
%lambda = ( x ./ times);
if numberOfCollisionsAtTime == 1
delay = 1;
collision(3,i) = delay;
elseif numberOfCollisionsAtTime > 1
%cell = zeros(l,3);
% transq(i) = x;
cell(3) = numberOfCollisionsAtTime;
cell(3)
isResolved = 0;
while isResolved == 0
%get the module of cell 3
mymod = mod(cell(3),3) ;
%divide equally into 3 if number of packets are divisible by 3
34
0
if cell(l) > 0 && cell(2) == 0 && cell(3) ==
if cell(1) == 1
cell(3) = 1;
cell(1) = 0;
elseif cell(l) == 2
cell(3) = 1;
cell(1) = 0;
cell(2) = 1;
else
cell(3) = cell(1);
cell(1) = 0;
end
elseif mymod == 0 && cell(3) ~= 0
temp = cell(3)/3;
cell(3) = temp;
cell(2) = cell(2) + temp;
cell(l) = cell(l) + temp;
%send packet if cell 3 has 1
elseif cell(3) == 1
cell(3) = cell(2);
cell(2) = cell(1);
cell(1) = 0;
else
%divide contents of cell 2 and add half to cell 1
divided = cell(3) mymod;
cell(3) = divided/3;
cell(2) = divided/3 + cell(2);
cell(l) = divided/3 + mymod + cell(l);
end
fprintf('[ %d
^d ] \n ,cell(1),cell(2),cell ( 3)) ;
delay = delay + 1;
if AdmissionDelay < delay
isResolved = 1;
collision(4,i) = 1;
collision(3,i) = delay;
elseif cell(l) == 0 && cell(2) == 0 && cell(3) == 0
isResolved = 1;
collision(3,i) = delay;
fprintf('\n');
end
end
else
end
end
k = sum(collision,2);
lambdaArray(1,counter)
lambdaArray(2,counter)
lambdaArray(3,counter)
counter = counter + 1;
lambda;
k(3,1) ;
k(4,l);
35
end
row = lambdaArray(1,:); %Lambda
col = lambdaArray(2,:);%Expected Delay
tan = lambdaArray(3,:); %Rejection Rate
R= polyval (row,col);
R= R/100000000000000000000000;
plot(row, R, 'o');
plot(row, R, 'b');
xlabel('Rate (Lambda)');
ylabel('Expected Delay (Slots)');
title ('Admission Delay 80');
i = i+1;
APPENDIX C: ALOHA Protocol Code
%SIMULATION PARAMETERS %simulation for slotted Aloha protocol
%total simulation time in seconds
runtime=0.2;
%total number of stations
nstation=10;
%transmission throughput of the media in bits per second
netthrou=10e6;
%frame size in bits
fsize=400;
%avarage frame arrival rate per second for each station %
frate=5;
for frate=l:5:150
^average frame arrival rate per simulation iteration
trh=frate/10000;
^random wait window
wwind=100;
%EVENTS VARIABLES
%transmit active
tr=zeros(1,nstation);
%transmit queue
tq=zeros(1,nstation)
%transmit progress counter
tcnt=zeros(1,nstation);
%collision keeper
colis=zeros( 1,10000 *runtime);
%collision station index
colin=zeros(1,nstation);
^random wait after collision
rwait=zeros(1,nstation);
%transmit keeper
trkeep=zeros(nstation, 10000 *runtime);
%packet arrival keeper
pakeep=0;
for i=l:10000*runtime
for j=l:nstation
%check if the transmitter is active
36
if tr(j)==l trkeep(j,i)=1;
end
%check if the packet has been sent
if tent(j)>0
tent(j)=tcnt( j ) 1;
if tent(j)==0
tr(j)=0;
%check if the transmission is collision free
if colin(j)==1
rwait(j)=ceil(wwind*rand(1,1));
tq(j)=tq(j)+l; colin(j)=0;
end
end
else if tq(j)>0 && rwait(j)==0 && mod(i,8)==0
tr(j)=1;
tcnt(j)=ceil(fsize/netthrou*10000);
tq(j)=tq(j)l;
end
end
%check if a new packet has arrived
pa=rand(1,1);
if pa
pakeep=pakeep+l;
%if the transmit is ready
if tr(j)==0 && rwait(j)==0 && mod(i,8)==0
tr(j)=1;
tcnt(j)=ceil(fsize/netthrou*10000);
else
tq(j)=tq(j)+l;
end
end
^decrease random waiting count
if rwait(j)>0
rwait(j)=rwait(j)1;
end
end
%check for collision
if sum(tr)>l colis(i)=l;
for k=l:nstation
if tr(k)==1
colin(k)=1;
end
end
end
end
px2(frate)=(pakeepsum(tq));
py2(frate)=pakeep;
end
g2=[0:0.01:1.2] ;
s2=g2.*exp(g2);
%figure(1)
37
%plot(px2 *400/runtime,py2 *400/runtime,'x',s2*le7,g2*le7,)
%plot(px2,py2,'x',s2,g2,'')
%grid
plot(s2,g2*40,'g');
xlabel('Rate (Lambda)')
ylabel('Expected Delay (Slot)')
title ('Admission Delay for 80')
38
BIBLIOGRAPHY
[1] B.S. Tsybakov and V.A. Mikhailov, Free Synchronous Packet Access in a Broadcast
Channel with Feedback", Problemy Peredachi Informatsii, 1978, Vol. 14, No. 4, pp. 259
280.
[2] B. S. Tsybakov and N. B. Likanov, Some New Random Multiple Access Algorithms,
Problems of Information Transmission, 1985, Vol. 21, No. 2, pp. 134154.
[3] N. D. Vvedenskaya and B. S. Tsybakov, Random Multiple Access of Packets to a
Channel with Errors, Probl. Peredachi Inf., vol. 19, no. 2, pp. 5268, 1982.
[4] L. Georgiadis and P. PapantoniKazakos, Limited Feedback Sensing Algorithms for
the Broadcast Channel, IEEE Trans. Inform. Theory, Special Issue on Random Access
Communications, 1985, IT31, No. 2, pp. 280294.
[5] M. Paterakis and P. PapantoniKazakos, A Simple Window Random Access Algorithm
with Advantageous Properties, IEEE Transactions on Information Theory, 1989, vol. 35,
pp. 11241130.
[6] A.T. Burrell and P. PapantoniKazakos, A Class of Limited Sensing Random Access
Algorithms with Resistance to Feedback Errors and Effective Delay Control, Journal of
Communications and Networks, 2006, Vol. 8, No. 1.
[7] L. Georgiadis and P. PapantoniKazakos, A 0.487 Throughput Limited Sensing
Algorithm, IEEE Transactions on Information Theory, 1987, vol. 33, pp. 233237.
[8] M. Kaplan, A Sufficient Condition for Nonergodicity of a Markov Chain , IEEE
Transactions on Information Theory, 1979, vol. 25, pp. 470471.
[9] W. Szpankowski, Stability Conditions for Multidimensional Queueing Systems with
Computer Applications, Operations Research, 1988, vol. 36, pp. 944957.
[10] W. Szpankowski and V. Rego, Some Theorems on Instability with Applications to
MultiAccess Protocols, Operations Research, 1988, vol. 36, pp. 958966.
[11] A. G. Pakes, Some Conditions for Ergodicity and Recurrence of Markov Chains
,Operations Research, 1969, vol. 17, pp. 10581061.
[12] R. L. Tweedie, Criteria for Classifying General Markov Chains , Advances in
Applied Probability, 1976, vol. 8, pp. 737771.
[13 J.W. Cohen, On Regenerative Processes in Queueing Theory, New York: Springer
Verlag, 1976.
[14] L. V. Kantorovich and V. I. Krylov, Approximate Methods of Higher Analysis, New
York: Interscience, 1958.
39
[15] S. Stidman, Jr., Regenerative Processes in the Theory of Queues with Applications
to the Alternating Priority Queue , Adv. Appl. Prob., 1972, Vol. 4, pp. 542577.
[16] L. Georgiadis, L. Merakos and P. PapantoniKazakos, A Method for the Delay
Analysis of Random Multiple Access Algorithms Whose Delay Process is Regenerative ,
IEEE Journal on Selected Areas in Communications, 1987, vol. 5, pp. 10511062.
[17] J.C. Huang and T. Berger, Delay Analysis of 0.487 Contention resolution
Algorithm, IEEE Trans. Commun., Vol. COM34, pp. 916926, Sept. 1986.
[19] Anthony Burrell and Titsa P. Papantoni, Random Access Algorithms in Packet
Networks A Review of Three Research Decades. Pp. 117.
40

PAGE 1
LIMITED SENSING RANDOM ACCESS ALGORITHMS by Oluwapelumi. A. Idowu B.S., Oral Roberts University, 2010 A Thesis submitted to the Faculty of the Graduate School of the University Of Colorado in partial fulfillment of the requirement for the deg ree of Master of Science Electrical Engineering 2013
PAGE 2
! "" This thesis for the Master of Science degree has been approves for the Electrical Engineering Program by Dr. Titsa Papantoni Advisor Dr. Yiming Deng Dr. Jan T. Bialasiewicz Date : April 19 th 2013.
PAGE 3
! """ Idowu Oluwapelumi (M.S., Electrical Engineering) Limited Sensing Random Access Algorithm Thesis Directed by Professor Titsa Papantoni ABSTRACT This project presents the properties of a class of Limited Sensing Random Access algorithms. The operations and properties of the algorithms are presented in detail and comp ared with the ALOHA protocol. In particular, the performance of the algorithms in the presence of the limit Poisson user model is investigated and compared with that of the ALO HA protocol. In addition performance evaluation of these algorithms and comparison with the ALOHA protocol are also performed in environments where admission delay constraints are imposed. The form and content of this abstract are approved. I recommend its publication. Approved: Dr. Titsa Papantoni
PAGE 4
! "# DEDICATION This thesis is dedicated to my family, who has been of tremendous support from the time I started my program at University of Colorado Denver, even to this very point. I am forev er grateful. Also to my friends who encouraged me when I needed it and also to my friend Prince, who helped out with the coding aspect of my project, I am thankful for all your support through this process. Last and definitely not the least, I would like t o thank my husband, Eric, who has been with me every step of the way. His encouraging words and also assistance during my project have given the strength that I need to be able to get this far. Thanks a lot.
PAGE 5
! # ACKNOWLEDGMENT I would like to gi ve my sincere thanks to my advisor, Dr Titsa Papantoni. I had the opportunity to take some classes such as Computer Communication, which i s the foundation for my thesis. I would like to thank her for her relentless discipline in wanting me to work hard an d achieve the very best. I would also like to thank all the professors I have had the opportunity to sit in their classes and learn from them things I believe would help me in my career pursue.
PAGE 6
! #" TABLE OF CONTENTS Figures . ........viii Tables.. ........ix Chapter 1. Introduction .....1 2. Fundamental Concepts and Outline of Analytical Approaches .....4 2.1 Throughput Computation o f a Given RAA........5 3. The ALOHA Random Access Algorithm.......7 3.1 Throughput Analysis for M independent Users Generating Memoryless Packet......7 3.2 Throu ghput Analysis for Varying Number of Users....... ...10 3.3 Throu ghput of the Exponential Back off ALOHA Modification......11 4. The Binary Split Random Access Alogorithm...........12 5. The Limited Sensing Stack Random Access Alogorithm.............15 5.1 The Limited Sensin g Initialization Process for the Limit Poission Population....17 5.2 Throuughput Analysis for the Limit Poission Population .......20 5.3 Computation of the Expected CRI Length for 2 Cell Stack RAA (K= 2) ....22 5.4 Delay Analysis for the Limit Poission Population ..........24 5.5 Sensitivity to Feedback Errors ............26 6. Evaluation in the PresenceAdmission,Delay Constraints, Conclusion and Future.......28 6.1 Conclusion ..... .........30 6.2 Future Work ...............31 Appendix A. Two Cell Stack ...................32 B. Three Cell Stack .....................34 C. ALOHA Protocol Stack ..... ................36
PAGE 7
! #"" Bibliography .......................39
PAGE 8
! #""" LIST OF FIGURES Figure 3.1 The ALOHA Throughput as a Function of the number M of users .10 5.1 Expected Delays in Slot Units ..26 6.1 Expected Delays (Admission Delays 80 slots) . 29 6.2 Rejection Rates (Admission Delays 80 slots) ... 29 6.3 Expected Delays (Admission Delays 200 slots) ....29 6.4 Rejection Rates (Admission Dela ys 200 slots) .....29 6 .5 Expected Delays (Admission Delays 400 slots) ... 30 6 .6 Rejection Rates (Admission Delays 400 slots) ..... 30
PAGE 9
! "$ LIST OF TABLES Table 5 .1 Stability Regions and Optimal Windows for Stack RAAs24 5 .2 Throughputs in the Presence of Feedback Errors.. .. 27
PAGE 10
! % 1. Introduction This thesis focuses on the "random access" approach, for the accessing of a single, errorless, slotted channel, by independent, ident ical, packet transmitting, bursty users. The global properties of the user/channel model considered are as follows: All transmitted packets have identical length each requiring the length of a single slot for transmission; the transmission by all users is synchronous, where they are allowed to start transmission only at the beginning of some slot; and there are no propagation delays in the channel feedback information obtained by the users. Also, if at least two packets attempt transmission within the same slot, a collision occurs and such an event is initially the only cause for faulty transmissions; that is, a slot occupied with a single packet results in successful transmission. A collision results in complete loss of the information carried by the collid ed packets; thus, retransmission of such packets is then necessary. The outcome per slot possibly accessible by the users named feedback level is binary, distinguishing Collision (C) versus Non Collision (NC), or ternary, distinguishing between collisions (C) versus emptiness (E) versus success (S). It is noted that a NC event corresponds to a slot that is either empty or occupied with a single packet transmission, while an S event corresponds to a slot occupied with a single packet whose transmission is then successful. The accessibility of the feedback level outcomes by the users named channel sensing is a characteristic of each Random Access Algorithm (RAA) and specifies the time instants (in slots) when each user is required to sense the feedback lev el outcomes (accessible by either channel sensing or broadcasting). Based on channel sensing requirements, the existing RAAs may be classified as members of one of the three distinct channel sensing classes below:
PAGE 11
! & Minimal Sensing RAA Class : Each user is required to sense the feedback level outcome of only those slots within which it transmits. Limited Sensing RAA Class : Each user is required to sense continuously the feedback level outcomes of all slots contained in time periods within which any of its packet is in the system; that is, from the slot within which the packet is generated to that within which this packet is successfully transmitted. Full Sensing RAA Class : Each user is required to know the overall feedback history of the channel, from the beginning of time and even before the user became part of the system. In regards to user population models, the following distinction will be necessary, Known User Population Model : The identities of all users are distinct and known to the system. This class model implies finite member. Unknown User Population Model : The identities of the users are unknown to the system, usually due to time varying user characteristics. These class members may be finite or infinite members. Limit Poisson User Pop ulation Model : Infinitely many identical Bernoulli users, comprising an aggregate Poisson packet generating process, where each packet is a separate user. This is a special case of the unknown user population model. Historically, the RAA evolution st arted with Abramson's ALOHA algorithm, which belongs in the Minimal Sensing RAA class, it assumes the availability of C versus NC
PAGE 12
! feedback outcomes and is unstable, attaining throughput zero in the presence of the Limit Poisson User Population Model. The developed algorithms in the Full Sensing RAA class provided valuable insight. While the algorithms in this class (Full Sensing) are non implementable in environments with unknown user models, due to the requirement that all users know the overall feedb ack history of the channel, the algorithmic studies in it led to implementable algorithms in the Limited Sensing RAA class. The first such algorithm was developed by Tsybakov and Mikhailov [1] where the feedback level is C versus NC, where each packet ar rival accesses freely the infinite cell stack in the presence of the Limit Poisson Population model, the throughput of the algorithm is 0.134. Later, a class of RAA named Limited Sensing Stack RAAs was developed by Tsybakov and Likanov [2] Vvedeskaya and Tsybakov [3] Georgiadis et a l [4] Paterakis et al [5] and Burrell et al [6] A stack with finite cells, where for C versus NC feedback level and in the presence of the Limit Poisson Population model, the maximum attained throughput is 0.429, can depict the collision resolution process of these Limited Sensing stack RAAs. Error sensitivity studies of the latter stack algorithms were performed by Vvedeskaya and Tsybakov [3 ] by Georgiadis et al [ 4 ] by Paterakis et al [ 5 ] and by Burrell et al [ 6 ] In gene ral class is characterized by low sensitivity to feedback errors. Finally, Georgiadis et al [ 7 ] modified the algorithm in and for Limited Sensing operation, at the expense of increased operational complexity; the modified Limited Sensing algorithm mainta ins 0.4872 through put in the presence of the Limit Poisson Population model, while, it also maintains its high sensitivity to feedback errors.
PAGE 13
! ( 2. Fundamental Concepts and Outline of Analytical Approaches Random Access Algorithms (RAAs) are deployed whe n the user population is unknown. In the study of RAAs, the fundamental concepts arising, that also characterize their performance, are: system stability and induced delays. Given some RAA and user population, we define: Throughput: This is the maximum aggregate packet traffic rate for which the user/RAA system is stable. Then, (0, *) is named the stability region of the system. Per Packet Delay: The distance, in slot units, between the arrival instant of a packet arrival and the instant when its tr ansmission has been completed. Regarding user/RAA system stability in the presence of independent users that generate memoryless packet streams, the existing developed RAAs induce a sequence {T n } n 0 of time instants when consecutive Collision Resolution Intervals (CRIs) intervals occur, where the packet backlogs {S n } n 0 at the instants {T n } n 0 form an irreducible and aperiodic Markov Chain. Thus, system stability corresponds then to the ergodicity of the Markov Chain {S n } n 0 On the other hand, Paterak is et al proved that as the size of the above user population increases, the stability region of any of the existing RAAs is that corresponding to the Li mit Poisson Population model. Therefore, the throughput of any one of the existing RAAs in the presence of the Limit Poisson Population model is a lower bound to the throughput attained by the RAA in the presence of independent users that generate memoryless packet streams. At the same time, the throughput of such an RAA in the presence of the Limit Poisso n Population model is then the highest rate for which the
PAGE 14
! ) Markov Chain {S n } n 0 is ergodic, where this chain also induces then infinitely many states. The theories and results developed by Kaplan [ 8 ] Spankowkii [9 ], Spankowski et al [10 ] Pakes [11 ] and Tweedie [ 12 ] were applied to provide a general approach to the compu tation of the throughput of the existing RAAs in the presence of the Limit Poisson Population model. This approach is also applicable to finite independent user populations that generate memoryless traffic streams, and it is summarized by the following steps: 2.1 Throughput Computation of a Given RAA (a) Given the user model, identify appropriate measure of system backlog. (b) Consider the beginnings A and B of two consecutive CRIs, where A prec edes B, and let S A and S B denote the backlogs at A and B, respectively. (c) Require that the conditional expected backlog E{S B /S A =s } be less than s, for all values of s that are larger than some finite number d determined by the RAA operation. Derive the thr oughput expression imposing this requirement, which represents negative expected backlog drift across consecutive CRIs. (d) In the throughput expression in (c), the computation of the expected length of a CRI is required. Derive the tight bounds that may be ne eded in this computation. (e) Use the result from step (d) to compute the value of the throughput. The study of packet delays within the stability region of any of the existing The study of packet delays within the stability region of any of the existin g RAAs recruits results from the regenerative theory, as found in Cohen [13 ], Kantorovich
PAGE 15
! et al [ 14 ] and Stidman [15 ] Indeed, in the presence of the user models considered above, each such RAA generates time instants when the algorithm restarts independe ntly from its past. Then, the number of generated packets from the beginning of time to the point when such a time instant occurs constitutes a renewal process, where the delays determine a regenerative process with respect to the former renewal process an d where the time instants of algorithmic restarts constitute then renewal points. This allows for the computation of the expected per packet delays as a ratio of the expected aggregate packet delays between consecutive renewal points, over the expected n umber of packets transmitted between these points, as discussed in detail by Georgiadis et al [16 ] where the computation of delay bounds is also necessary in the process.
PAGE 16
! + 3. The ALOHA Random Access Algorithm The ALOHA Random Access Algorithm operates with binary NC vs. C feedback level outcomes and belongs in the Minimal Sensing RAA class. Given a user population, its operations are described below. Operations (a) All the users deploy a common transmission probability p in the system. (b) Each user has its generated packets queued, where these packets are transmitted on the first come first serve basis, with the head packet being the oldest in the queue. (c) Within each slot, each user whose queue is non empty transmits the head packet in its queue with probability p. A user that actually transmits within the slot, subsequently observes the resulting NC vs. C feedback outcome : if the outcome is NC the user concludes that its packet is successfully transmitted; if the outcome is, instead, C the user rep eats the process within the next slot, by retransmitting its head packet with probability p. Next, I will proceed with the throughput analysis of the ALOHA RAA, when deployed by M independent users, each gener ating memoryless packet streams. 3.1 Thr oughput Analysis for M Inde pendent Users Generating Memory less Packet Streams Given M users, we will measure the backlog at the beginning of some slot t, as the total number k of packets queued by all the users. Then, due to the memoryless property o f the
PAGE 17
! traffics generated by the users, in conjunction with the memoryless characteristic of the ALOHA operations, the backlog at the beginning of slot t+1 depends only on the value k and the common transmission probability p. In other words, if {T n } n 0 de notes here the sequence of consecutive beginnings of slots and if {S n } n 0 is then the sequence of the corresponding backlogs at these beginnings, then, {S n } n 0 constitutes an aperiodic and irreducible Markov Chain. Let us define: B : The set containing a ll aggregate backlogs, such that at least one packet per user is included. E{S n+1 / S n = k # B } : The expected aggregate backlog at the time instant T n+1 given that the backlog at the time instant T n equals k and is such that at least one packet per u ser is included. : The aggregate packet rate in expected number of packets per slot. Then, E{S n+1 / S n = k # B } = k + Mp(1 p) M 1 (1) where, Mp(1 p) M 1 equals the probability of a successful transmission per slot, as wel l as the expected number of successfully transmitted packets per slot, when all M users are active, as is the case when the backlog k is a member of the set B The ergodicity theory for aperiodic and irreducible Markov Chains, induces here the following t heorem.
PAGE 18
! Theorem 1 The ALOHA RAA is stable iff the Markov Chain {S n } n 0 is ergodic. In turn, the Markov Chain is ergodic, iff: E{S n+1 / S n = k # B } k < 0 ; for all k in B which in view of (1) gives that the necessary and sufficient condition for ALOHA stability is: < M p (1 p ) M 1 $ (p M) (2) The quantity (p,M) in Theorem 1 is the ALOHA throughput for M independent users generating memoryless packet streams, when th e common transmission probability is p. The corresponding stability region is then (0, (p,M) ). The rates in the stability region are expected aggregate number of packets generated per slot. Maintaining the number of users M fixed, the throughput in ( 2) can be maximized with respect to the value p. The latter maximum is easily found to equal (1 1/M) M 1 and attained for p = 1/M. It is also straight forward to conclude that the quantity (1 1/M) M 1 is monotonically decreasing with increasing M, convergin g asymptotically to the value 1/e. The latter result led to the unfortunate early conclusion that the throughput of ALOHA for infinite users (or the Limit Poisson Population) is 1/e, where the fact that this meaningless result can be only attained when th e transmission probability is zero (limit of 1/M for M % & ) was ignored.
PAGE 19
! %. 3.2 Throughput Analysis for Varying Number of Users To study meaningfully the ALOHA throughput as t he number of users increases, I fix ed the transmission probability p to a stric tly positive value and study the (p,M) expression in (2), as M increases. Figure 1 exhibits the behavior of (p,M) as a function of M. From the figure, we observe that as M increases, the throughput (p,M) converges to zero. As a consequence to this observation, in the presence of the Limit Poisson Population, the ALOHA throughput is zero. !"#$%&'()*+ The ALOHA Throughput as a Function of the Number M of Users The Probability of Transmission is p > 0. # $ # = % p) ln(1 1 M 1 ! # # $ = % p) ln(1 1 M 2 # of Users Attaining Maximum Throughput : ( ) ) p) p(1 M p p(1 M max arg M 1 M 2 1 M 1 2 1 ! ! = Maximum Throughput : 1 M 1 M M * p) (1 p M P) (1 p M max (p) ! = =
PAGE 20
! %% 3.3 Throughput of the Exponential Back Off ALOHA Modification Current applications in Cellular and Sensor technologies deploy an ALOHA modification, where after each unsuccessful transmission attempt, a user defers retransmission by a number of slots which grows exponentially with the number of its unsuccessful attempts. This operation has been named exponential back off. Since t he modification also deploys packet abortion after the number of retransmissions exceeds a given limit, the number of back offs is bounded. In addition, in a straight forward fashion, the exponential back offs can be equivalently modeled by varying transm ission probabilities per slot, whose possible nalues are then finite. Let q and r denote respectively the largest and smallest among these values. Then, for the model of M independent users whose packet traffics are memoryless, the throughput of the expo nential back off ALOHA modified algorithm is bounded from above by the expression Mq(1 r) M 1 Fixing the q and r values and allowing the latter bound to vary with the M value, we observe a behavior qualitatively identical to that in Figure 3. 1. Thus, the throughput of the ALOHA exponential back off modification converges to zero as the number of users increases. As a consequence, in the presence of the Limit Poisson Population, the throughput of the exponential back off ALOHA modification is zero.
PAGE 21
! %& 4 The Binary Split Random Access Algorithm The binary split algorithm belongs in the full sensing RAA class, since user synchronization with the algorithmic operations requires knowledge of the overall system feedback history, as well as continuous feedback monitoring until successful transmission. The algorithm utilizes binary NC vs. C feedback outcomes per slot and its operations may be described by an initialization and a collision resolution processes, where initialization refers to the initially selected set of packet arrivals that are successfully transmitted during the collision resolution process; the time period (in slot units) that the latter process lasts is named Collision Resolution Interval (CRI). The non dynamic and the dynamic version s of the algorithm differ only in the initialization part, while their collision resolution processes are identical. In the non dynamic version, all the waiting packet arrivals are selected for participation in the CRI, while, in the dynamic version, onl y a subset of these packets are selected, instead. We will proceed by first stating the algorithmic operations during a CRI. Operations During a CRI During a CRI, each involved packet/user is required to observe slot feedbacks continuously until suc cessful transmission. The first slot of a CRI is occupied with simultaneous transmissions from the total set of packets selected during the initialization part of the algorithm. If the latter set contains at most one packet, the CRI lasts one non collisi on ( NC) slot, during which the initially selected set of packets is successfully transmitted. If the set of arrivals selected during the initialization process contains at least two packets, instead, then the first CRI slot is a collision (C ) slot and a collision resolution process begins. The algorithmic steps of this process may be described in two
PAGE 22
! %' ways: (1) as viewed by an imaginary outside observer and (2) as implemented independently by each packet involved in the process. We provide both descript ions below, where time is measured in slot units, where slot t occupies the time interval (t 1, t] and where x t denotes the feedback outcome of slot t ( NC vs. C ). (1) Operations as Viewed by an Outside Observer As viewed by an outside observer, th e operations during a CRI that starts with a C slot may be described via a stack containing infinite cells indexed by i, where i = 1,2,. The lowest cell 1 in the stack is the transmission cell; that is, the packets transmitted in slot t are those placed in cell 1 at the same slot. The remaining cells in the stack are withholding cells, such that increased cell index implies lower withholding priority. The cell transitions during the CRI are described as follows: (a) At the first slot of the CRI, all packet s in the initialization set are placed in cell 1. (b) If x t = NC then The packet (if any) that was in cell 1 at t is successfully transmitted within slot t. The packets (if any) that were in cell i ; i 2 at slot t, move to cell i 1 at slot t+1. (c) If x t = C then, Each packet that was in cell 1 at slot t, stays in cell 1 at slot t+1; with probability 0.5 or moves to cell 2 at slot t+1; with probability 0.5. The packets (if any) that were in cell i ; i 2 at slot t, move to cell i + 1 at slot t+1.
PAGE 23
! %( (2) Independent Implementation per Packet/User The CRI operations may be implemented independently by the packets/users, via the use of a counter whose values may be any one of the positive integers. Let then c t denote the counter value of some packet at slot t, where c t = 1,2,. The packet is transmitted in slot t if and only if c t = 1. The algorithmic operations during a CRI for any involved packet are then described by transitions of its counter values, as follows: (a) If x t = NC and c t = 1, then the packet is successfully transmitted within slot t. (b) If x t = NC and c t 2, then c t+1 = c t 1. (c) If x t = C and c t 2, then c t+1 = c t + 1. (d) If x t = C and c t = 1, then, c t+1 = 1; with probability 0.5 or c t+1 = 2; with probability 0.5.
PAGE 24
! %) 5. Th e Limited Sensing Stack Random Access Algorithm In Limited Sensing, if the collision resolution process can be modified to induce distinct CRI endings, then a user arriving in the system may be synchronized with the algorithmic operations without the need to know the overall system feedback history; thus, allowing for algorithmic implementability. The Limited Sensing Stack RAAs were developed from a modification of the Window Binary Split RAA, via an initial imposed limitation on the size of the stack which represents the collision resolution process. Thus, the feedback outcomes utilized per slot are binary NC vs.C and each involved packet/user is required to observe slot feedbacks continuously until transmission, while the collision resolution proces s during a CRI, as viewed by an imaginary outside observer, may be described via the use of a stack containing K cells. The same process, as implemented independently by each involved packet/user, may be described via the use of a counter. We provide bot h descriptions below, where, slot t represents the time interval (t 1, t] and x t denotes the NC vs.C feedback outcome of slot t. (1) Operations as Viewed by an Outside Observer The stack contains K !2 cells indexed from 1 to K. Cell 1 is the transmis sion cell; that is, packets contained in cell 1 at slot t are transmitted within the same slot, while the cells above it are withholding cells representing various withholding priorities. The cell transitions during a CRI are described as follows: (a) A t the first slot of the CRI, all packets contained in the initialization set are placed in cell 1. (b) If x t = NC then
PAGE 25
! %* The packet (if any) that was in cell 1 at t is successfully transmitted within slot t. The packets (if any) that were in cell i ; i 2 at slot t, move to cell i 1 at slot t+1. (c ) If x t = C then, Each packet that was in cell 1 at slot t, places itself in cell i; i = 1,,K, with probability 1/K at slot t+1. The packets (if any) that were in cell i ; i 2 at slot t, remain in cell i at slot t+1. (2) Independent Implementation per Packet/User The CRI operations are carried independently by each involved packet/user via the use of a counter. Let c t denote the counter value of a packet at slot t. This value may be one of the positive integer numbers 1 to K, where the packet is transmitted within slot t iff c t = 1. The transition of the counter values during a CRI are as follows: (a) If x t = NC and c t = 1, then the packet is successfully transmitt ed within slot t. (b) If x t = NC and c t 2, then c t+1 = c t 1. (c ) If x t = C and c t 2, then c t+1 = c t (c) If x t = C and c t = 1, then, c t+1 = i; i = 1,,K with probability 1/K. As concluded from the above collision resolution operations, after a c ollision within which it is involved, a packet places itself in either one of the transmission vs.
PAGE 26
! %+ withholding states with equal probability, while after a collision within which the packet is not involved, it maintains its existing state. After caref ul observation of the collision resolution process described above, it is concluded that each CRI that starts with a collision ends with the unique pattern of K successive NC slots. In other words, for a CRI that starts with a collision, K successive slot s can not occur somewhere in the middle its process, while, at the same time, they characterize uniquely its end. Taking now into consideration trivial CRIs that last a single slot (those resolving at most one packet), and finally it is concluded that the observation of K successive NC slots may lead to one of the following two assessments: either a CRI that started with a collision ended or K successive trivial (a single slot lasting) CRIs occurred. In either case, if a newly arrived user in the system waits until it observes K successive NC slots, it is assured that at the end of the K th such slot a CRI has ended. This leads to the limited sensing initialization process described below for the Limit Poisson Population model. 5.1 The Limited Sensing In itialization Process for the Limit Poisson Population The patterns of K successive NC slots explained above allow for the implementation of the stack algorithm without the need of the overall feedback history knowledge. Such implementation is reflect ed by the initialization process, named Limited Sensing which imposes the requirement that each packet arrival observe continuously the slot feedbacks, from the slot within which it arrives to the slot within which it is successfully transmitted. Specif ically, in the presence of the Limit Poisson Population, where each packet is an independent user, a packet that arrives at time instant 1 located within slot t 1
PAGE 27
! %, follows the process described below before entering a CRI, where a window of size # is util ized. (a) Starting with the slot t 1 of its arrival, the packet observes slot feedbacks passively, until the first occurrence of K successive NC slots ending with slot t 2 At the end of slot t 2 the packet is synchronized with the algorithmic collision resolu tion process, being in the position to recognize all CRI endings after t 2 (including those of the trivial CRIs). (b) kAt the end of slot t 2 the packet checks its arrival instant 1 against the arrival interval (t 2 K + 1 #, t 2 K + 1): (i) If "1 $ (t2 K + 1 #, t2 K + 1), the packet participates in the CRI that begins with slot t2 + 1 and is successfully transmitted during its proce ss. (ii) If instead, 1 < t 2 K + 1 # the packet updates its arrival instant to 2 = 1 + # and continues observing slot feedbacks sequentially and passively, until the end slot t 3 of the next CRI, when it repeats step (b) for t 2 substituted by t 3 (c) In general, if t k is the ending slot of the (k 1) th CRI after the packet's arrival and the packet has not yet participated in a CRI, the packet's arrival instant update at t k equals k 1 = 1 + (k 1) #. The packet checks then k 1 against the arrival interval (t k K + 1 #, t k K + 1) and:
PAGE 28
! %! (i) If k 1 is contained in (t k K + 1 # t k K + 1), the packet participates in the CRI that begins with slot t k + 1 and is successfully transmitted during its process. (ii) If, instead, k 1 < t k K + 1 #, the packet updates its arrival instant update to k = 1 +k # and continues observing slot feedbacks sequentially until the next CRI end. Regarding the initialization process described above, we make the following observations: (1) The Limited Sensing initialization has last come first serve characteristics. (2) While at the initialization state, a packet generates a sequence of arrival instant updates, where each such update is generated at the beg inning of each CRI which the packet does not participate in. The updates are responses to the fact that a C RI which does not include the packet resolves a length # interval which contains later (than the packet's arrival) packet arrivals. As a result, each update advances the arrival instant of the packet by #. (3) The arrival instant update k 1 at the end t k of the (k 1) th CRI is checked against a length # arrival interval (t k K + 1 # t k K + 1) whose right edge lies K 1 slots to the left of t k where this is because packets that arrived within the latter K 1 slots have not yet observed the nece ssary for algorithmic synchronization and possible next CRI participation initial K successive NC slots. This arrival interval (t k K + 1 #, t k K + 1) is named examined interval where a sequence of such intervals is generated during the initializa tion process. (4) A packet participates in the first CRI whose examined interval its arrival instant update falls in.
PAGE 29
! &. 5.2 Throughput Analysis for the Limit Poisson Population In the throughput analysis, the specific location of the examined interva ls h as no effect; only their length # does. Thus, the only algorithmic characteristics involved in this analysis are the statistical properties of the generated CRIs, as induced by the collision resolution process and the window size #. As with the Window Bi nary Split RAA, the Limited Sensing Stack RAA induces a sequence of consecutive CRIs which, in the presence of the Limit Poisson Population resolve arrival intervals. The backlogs {S n } n 0 at the beginnings {T n } n 0 of consecutive CRIs are measured by arr ival intervals. In addition, in the presence of the Limit Poisson Population, the sequence {S n } n 0 is an irreducible and aperiodic Markov Chain whose ergodicity conditions determine the algorithmic throughput. Theorem 2 in Section 4 applies directly her e, where the only difference lies in the computation of the conditional expected CRI lengths {L k } k 0 For completeness, we restate the theorem here, as applied to the Limited Sensing Stack RAAs, where lag in this case is defined as the composite total unexamined arrival interval. Considering window size #, let us define: : The acting Limit Poisson rate, in expected number of packets per slot. E{S n+1 / S n = l }: The expected lag at the beginning of the (n+1) th CRI, given that the lag at the beg inning of the n th CRI equals l and is not less than f (x) : The expected length of a CRI that resolves the arrivals within a size arrival interval, when the rate of the Limit Poisson process is
PAGE 30
! &% x $ The ergodicity theory of irreducible and a periodic Markov Chains induces then the following theorem. Theorem 3 The Limited Sensing Stack RAA is stable iff the Markov Chain {S n } n 0 is ergodic. In turn, the latter Markov Chain is ergodic iff: E{S n+1 / S n = l } l = f (x) x < 0 Thus, the Limited Sensing Stack RAA is stable iff: < x / f (x) If x maximizes the ratio x / f (x) then = x / f (x ) is the throughput of the algorithm and is attained by a window size = x / Defining by L k the expected CRI length, given that the CRI resolves a k multiplicity col lision, that the expected CRI length f (x) is given by the following expression: # = 0 k k x k k! x e L (x) f (3) It is noted that as the number of cells K increases from the value two to infinity, a class of RAAs arises which contains the Binary Split RAA. The members of this class which may be implementable in the limited sensing environment are only those corresponding to bounded K values. As with the Binary Split RAA, for any given finite K value, the computation of the expected CRI length f (x) re quires the development of recursive expressions and bounds on the conditional expected CRI lengths {L k } k 0 I will present such recursions and bounds for the case of K =2; that is, for the Limited
PAGE 31
! && Sensing Stack RAA whose stack contains two cells. The complexity of such recursions increases with increasing number K of cells in the stack. 5.3 Computation of the Expected CRI Lengths for the 2 cell stack RAA (K = 2) Let us define: L k : The expected length of a CRI which starts with a k multiplicity col lision. L(k m ): The expected remaining length of a CRI which is at the state of containing k packets in cell 1 and m packets in cell 2. Then, the following initial conditions and relationships are clear. L k = L(k, 0 ) L 0 = L(0 0 ) = L 1 = L(1 0) = 1 where the algorithmic operations during a CRI induce the following transitions of the L(k m) quantities: For all m 1; L(0 m) = L(1, m) = 1 + L(m 0 ) For k 2 ; = + ! # $ $ % & + = ( ( ) i) m k L(i, i k 2 1 ) m k L( k i 0 k `) i m k i, L( i k 2 m) L(k, 2 1 1 k i 0 k + ! # $ $ % & + + = ( ( ) ) k Rearrang ement of terms in the last equation leads to the following expression which, for fixed sum k + m is recursive with respect to k. For k 2 ; [ ] [ ] ) i m k i, L( i k 1 2 1 2 2 m) L(k, 1 k i 0 1 k 1 k k + ! # $ $ % & + = ( ) ) '
PAGE 32
! &' For fixed k + m sum value, the recursive computation is repeated for incr easing k values, while this repeated recursive computation is performed sequentially for increasing k + m sum values. The end result of this process is the recursive computation of the quantities in the set {L k } k 0 As with the Binary Split RAA, th e cardinality of the latter set is infinite, requiring the development of tight upper and lower bounds for large k values. Such bounds were developed by J.C Huang and T.Berger [ 17 ] where, in contrast to the Binary Split RAA case, their form is quadratic here That is, for specifically found % & and constant values, we have : For k 13; L k ( % k 2 + & k + (4) In view of the expression in (15), the expected CRI length f (x) in (13) may be written as, [ ] ! " # $ # # # + + + % 13 k 0 k x 2 k 0 k x 2 k! x e k k # L k! x e ) k # ( (x) k k f & [ ] " # # # + + + + = 13 k 0 k x 2 k 2 k! x e k k # L x ) ( # x # (5) where the { L k } 0 ) k ) 13 values in (16) are computed precisely in a recursive fashion. Results for Varying K Values For given K value, the computation of the expected CRI length ( as in (5) for K = 2), in con junction with the statements in Theorem 3 lead to the computation of the throughput and the optimal examined interval length that attains it. In Table 1 below, we show these computed values for the Stack RAAs with K = 2 and K = 3 cells.
PAGE 33
! &( 5 .1 : Stability Regions and Optimal Windows for Stack RAAs Stack RAA w ith K = 2 : = 0.4295 ( 0.43 = 2.33 Stack RAA with K = 3: = 0.4295 ( 0.43 = 2.5599 Window Binary Split RAA: = 0.4295 ( 0.43 = 2.677 Common stability region: $ (0 0.43 ) It may be conjectured that, as the size K of the stack increases, from 2 to infinity, the RAA throughput remains unchanged, while, as viewed from Table 1, the optimal length of the examined interval increases. Thus, the K value does not affect the throughput but does affect implementability, delays and sensitivity to feedback errors. As compared to the ALOHA RAA, in the presence of the Limit Poisson Population, the class of Limited Sensing Stack RAAs attain throughput 0.43, while ALOHA's throughput is then zero. This is at the expense of increased, but reasonable and implementable feedback sensing. Indeed, the Limited Sensing Stack RAAs require that each packet/user sense the per slot feedback outcomes continuously, from the time it is generated to the tim e that it is successfully transmitted. In contrast, ALOHA requires sensing of feedback outcomes only for slots within which the packet is transmitted, but its throughput rapidly converges to zero when the user population increases. 5.4 Delay Analysis for the Limit Poisson Population The analysis of the delays induced by the Limited Sensing Stack RAAs, the renewal theory is utilized again, where the algorithm induces regenerative points with respect to
PAGE 34
! &) the delay process. In the presence of the Limit Poisson Population and for given K, the renewal points are the beginnings of CRIs whose initial lag is K slots long. For given K value and some given rate in the stability region, the per packet delay is then computed as the ratio of the aggregate delays between consecutive renewal points, over the aggregate number of packet arrivals between the same points. In Figure 2, we plot c omputed expected delays as functions of the rate *, for the 2 Cell Stack, the 3 Cell Stack and the Binary Split RAAs. It can be seen that for very light traffic (* near zero), a packet is delayed only due to the initial algorithmic synchronization require ment, since no collisions occur then. The latter requirement is 2 slots; for the 2 Cell Stack RAA, 3 slots; for the 3 Cell Stack RAA and 0 slots for the Binary Split RAA. Adding to these numbers the 0.5 slot accounting for the delay due to the mid point average arrival instant of the packet within its arrival slot, we finally obtain that for very light traffic, the expected delays induced by the 2 Cell Stack, the 3 Cell Stack and the Binary Split RAAs are approximately 1.5, 2.5 and 0.5 slots, respectively As the rate approaches the throughput value 0.43, the expected delays of all three RAAs approach asymptotically high values, while the expected delay of the Binary Split RAA remains uniformly lower than that induced by the other two algorithms. Comp aring the 2 Cell Stack RAA with the 3 Cell Stack RAA in terms of expected delays, we note that the 2 Cell Stack RAA outperforms the 3 Cell Stack RAA for low traffic rates, while the outperforming is reversed when traffic rates are relatively high. Finally the last come first serve characteristic of the limited sensing 2 Cell Stack and 3 Cell Stack RAAs induces higher variances of the delay distributions, as compared to that induced by the Binary Split RAA.
PAGE 35
! &* Figure 5.1: Expected Delays in Slot Units For th e 2 Cell, 3 Cell and Binary Split RAAs 5.5 Sensitivity to Feedback Errors Insensitivity to feedback errors, commonly caused by channel noise, is a significant attribute to consider in the performance evaluation of RAAs. The specific issue or interest is the throughput degradation when feedback errors cause misperception of NC feedbacks, where sure instability results from C feedbacks' misperceptions. We will draw from the results when the throughputs of the 2 Cell Stack, the 3 Cell Stack and the Bina ry Split RAAs were computed when empty or occupied with a single packet transmission slots may be perceived as collision slots. Let us define:
PAGE 36
! &+ $ : The probability that an empty slot may be perceived as a collision slot. + : The probability that a slot o ccupied with a single packet transmission may be perceived as a collision slot. In Table 5.2 below we include the throughputs attained by the 2 cell, 3 cell and Binary Split RAAs for different values of the $ and + probabilities. We observe the grac eful decline of throughputs when feedback errors are present, while the feedback error resistence of the 2 cell algorithm is evident, as compared to the remaining two other algorithms. Table 5 .2 : Throughputs in the Presence of Feedback Errors
PAGE 37
! &, 6 E valuations in the Presence of Admission Delay Constraints, Conclusions and Future Work This section compares the performances of the 3 cell and 2 cell algorithms with the ALOHA protocol, in the presence of admission delay constraints and the limit Poisson user model. We note that in the presence of admission delay constraints the concept of throughput is void, since then a percentage of the traffic is always rejected. In the presence of admission delay constraints, the concept of throughput is substituted by the concept of traffic success rate, which equals one minus the traffic rejection rate. Thus, in the presence of admission delay constraints, the performance metrics computed for the 3 cell, 2 cell and the ALOHA algorithms were traffic rejection rate s and expected p er packet delays, for the non rejected traffic. We considered admission delays of 80, 200 and 400 slots. Our results are exhibited in Figures 6.1 to 6.6. From these figures, we observe that the ALOHA algorithm does better than the 3 ce ll and 2 cell algorithms in terms expected delays of those packets which were transmitted successfully, but is the worst in terms of rejection rates. Also, as admission delay constraints become loos er, the ALOHA algorithm becomes worse in terms of expected delays and rejection rates, as compared to the 2 cell and 3 cell algorithms.
PAGE 38
! &! !!!!!!!!!!!!!! !!! ! !"#$%&', .1: Expected Delays Fig $%&', .2: Rejection R ates Admission Delay 80 Slots. Admission Delay 80 Slots. !!!!!!!!!!! !!!!!!! ''''''''''''''' !"#$%&', .3: Expected Delays !"#$%&', .4: Rejection Rates Admission Delay 200 Slots Admission Delay 200 slots
PAGE 39
! '. 6.1 Conclusion The class of window limited sensing random access algorithms was introduced whose collision resolution process can be depicted by a stack with finite number of cells. All algorithms in the class are stable and implementable, possess relatively high throughput, are robust in the presence of channel feedback errors and exhibit good delay characteristics. In view of the ALOHA instability in the p resence of increasing user populations, the Limited Sensing Stack Random Access Algorithms (RAAs) are especially attractive for deployment in various applications exemplified by cellular and clustered sensor topologies. The latter algorithms are stable in the presence of increasing user populations, attaining a throughput lower bound 0.43, they induce good delay characteristics and are robust in the presence of channel errors. In environments where ALOHA based algorithms are presently deployed, the Limited Sensing Stack RAAs may provide superior performance, well outbalancing the increased (as compared to ALOHA) !!!!!!!! !"#$%&', .5: Expected Delays !"#$%&', .6: Rejection Rates Admission Delay 400 slots Admission Delay 400 slots
PAGE 40
! '% feedback sensing they require. We compared the above class with the ALOHA protocol, in the presence of admission delays. We found that as the Poi sson traffic rate and its admission delay increase, the ALOHA protocol collapses (rejecting almost all traffic), while the protocols in the introduced class maintain high standards. 6.2 Future Work The limited sensing random access algorithms precsent ed and evaluated in this thesis may be deployed in various environments, such as sensor environments that inc orporate high priority traffic. We plan to study such deployment of the algorithms, to apply pertinent operational adjustments and evaluate their subsequent performance.
PAGE 41
! '& APPENDIX APPENDIX A: Two Cell Stack clear all %{ collision(1,i) is position in time collision(2,i) is number of packets generated in position collision(3,i) is delay Or number of steps it took to resolve collision, collision(4,i) is 1 if rejection or 0 if no rejection, %} lambdaArray = zeros(2,9); counter = 1; for lambda = 0:0.05:0.4 % arrival rate Tmax=80; % maximum time AdmissionDelay = 5; collision = zeros (4,10); T(1)=rand om( 'Exponential' ,lambda); i=1; while i < Tmax T(i+1)= T(i) + random( 'Exponential' ,lambda); i=i+1; end for i=1:numel(T) numberOfCollisionsAtTime = 0 delay = 0 for j=1:numel(T) if floor(T (j)) == i 1 numberOfCollisionsAtTime = numberOfCollisionsAtTime + 1; collision(1,i) = i 1; collision(2,i) = numberOfCollisionsAtTime; end end %lambda = ( x ./ times); if numberOfCollisionsAtTime == 1 delay = 1; collision(3,i) = delay; elseif numberOfCollisionsAtTime > 1 %cell = zeros(1,2); % transq(i) = x; cell(2) = numberOfCollisionsAtTime; isResolved = 0; while isResolved == 0 %get the module of cell 2 mymod = mod(cell(2),2) ; %divide equally into 2 if number of packets are even if mymod == 0 temp = cell(2)/2;
PAGE 42
! '' cell(2) = temp; cell(1) = cell(1) + temp; %send packet if cell 2 has 1 e lseif cell(2) == 1 cell(2) = cell(1); cell(1) = 0; else %divide contents of cell 2 and add half to cell 1 divided = cell(2) mymod; cell(2) = divided/2; cell(1) = divided/2 + mymo d + cell(1); end fprintf( '[ %d  %d ] \ n' ,cell(1),cell(2)); delay = delay + 1; if AdmissionDelay < delay isResolved = 1; collision(4,i) = 1; collision(3,i) = delay; el seif cell(1) == 0 && cell(2) == 0 isResolved = 1; collision(3,i) = delay; fprintf( \ n' ); end end else end end k = sum(collision,2); lambdaArray(1,counter) = lambda; lambdaArray(2,counter) = k (3,1); lambdaArray (3,counter)= k (4,1) counter = counter + 1; end row = lambdaArray(1,:); %Lambda col= lambdaArray(2,:); %Expected delay tan = lambdaArray(3,:); %Rejection Rates R= polyval (row,col ); R= R/100000000000000000000000; plot(row, R, '^' ); plot(row, R, 'r' ); xlabel( 'Rate (Lambda)' ); ylabel( 'Expected Delay (Slots)' ); title ( 'Admission Delay 80' ) hold on i = i+1;
PAGE 43
! '( APPENDIX B: Three Cell Stack %{ collision(1,i) is position in time collision(2,i) is number of packets generated in position collision(3,i) is delay Or number of steps it took to resolve collision, collision(4,i) is 1 if rejection or 0 if no rejection, %} lambdaArray = zeros(2,9); counter = 1; for lambda = 0:0.05:0.4 % arrival rate Tmax=80; % maximum time AdmissionDelay = 4; collision = zeros(4,10); T(1)=random( 'Exponential' ,lambda); i=1; while i < Tmax T(i+1)= T(i) + random( 'Exponential' ,lambda); i=i+1; end for i=1:numel(T) numberOfCollisionsAtTime = 0; delay = 0; f or j=1:numel(T) if floor(T(j)) == i 1 numberOfCollisionsAtTime = numberOfCollisionsAtTime + 1; collision(1,i) = i 1; collision(2,i) = numberOfCollisionsAtTime; end end %lambda = ( x ./ times); if numberOfCollisionsAtTime == 1 delay = 1; collision(3,i) = delay; elseif numberOfCollisionsAtTime > 1 %cell = zeros(1,3); % transq(i) = x; cell(3) = numberOfCollisionsAtTime; cell(3) isResolved = 0; while isResolved == 0 %get the module of cell 3 mymod = mod(cell(3),3) ; %divide equally into 3 if number of packets are divisible by 3
PAGE 44
! ') if cell(1) > 0 && cell(2) == 0 && cell(3) == 0 if cell(1) == 1 cell(3) = 1; cell(1) = 0; elseif cell(1) == 2 cell(3) = 1; cell(1) = 0; cell(2) = 1; else cell(3) = c ell(1); cell(1) = 0; end elseif mymod == 0 && cell(3) ~= 0 temp = cell(3)/3; cell(3) = temp; cell(2) = cell(2) + temp; cell(1) = cell(1) + temp; %send packet if ce ll 3 has 1 elseif cell(3) == 1 cell(3) = cell(2); cell(2) = cell(1); cell(1) = 0; else %divide contents of cell 2 and add half to cell 1 divided = cell(3) mymod; cell(3) = divided/3; cell(2) = divided/3 + cell(2); cell(1) = divided/3 + mymod + cell(1); end fprintf( '[ %d  %d  %d ] \ n' ,cell(1),cell(2),cell(3)); delay = delay + 1; if AdmissionDelay < delay isResolved = 1; collision(4,i) = 1; collision(3,i) = delay; elseif cell(1) == 0 && cell(2) == 0 && cell(3) == 0 isResolved = 1; collision(3,i) = dela y; fprintf( \ n' ); end end else end end k = sum(collision,2); lambdaArray(1,counter) = lambda; lambdaArray(2,counter) = k(3,1); lambdaArray(3,counter) = k(4,1); counter = counte r + 1;
PAGE 45
! '* end row = lambdaArray(1,:); %Lambda col = lambdaArray(2,:);%Expected Delay tan = lambdaArray(3,:); %Rejection Rate R= polyval (row,col); R= R/100000000000000000000000; plot(row, R, 'o' ); plot(row, R, 'b' ); xlabel( 'Rate (Lambda)' ); ylabe l( 'Expected Delay (Slots)' ); title ( 'Admission Delay 80'); i = i+1; APPENDIX C: ALOHA Protocol Code %SIMULATION PARAMETERS %simulation for slotted Aloha protocol %total simulation time in seconds runtime=0.2; %total number of stations nstation=1 0; %transmission throughput of the media in bits per second netthrou=10e6; %frame size in bits fsize=400; %avarage frame arrival rate per second for each station % frate=5; for frate=1:5:150 %average frame arrival rate per simulation iteration t rh=frate/10000; %random wait window wwind=100; %EVENTS VARIABLES %transmit active tr=zeros(1,nstation); %transmit queue tq=zeros(1,nstation) %transmit progress counter tcnt=zeros(1, nstation); %collision keeper colis=zeros(1,10000*runtime); %collision station index colin=zeros(1,nstation); %random wait after collision rwait=zeros(1,nstation); %transmit keeper trkeep=zeros(nstation,10000*runtime); %pac ket arrival keeper pakeep=0; for i=1:10000*runtime for j=1:nstation %check if the transmitter is active
PAGE 46
! '+ if tr(j)==1 trkeep(j,i)=1; end %check if the packet has been sent if tcnt(j)>0 tcnt(j)=tcnt(j) 1; if tcnt(j)==0 tr(j)=0; %check if the transmission is collision free if colin(j)==1 rwait(j)=ceil(wwind*rand(1,1)); tq(j)=tq(j)+1; colin(j)=0; end end else if tq(j)>0 && rwait(j)==0 && mod(i,8)==0 tr(j)=1; tcnt(j)=ceil(fsize/netthrou*10000); tq(j)=tq(j) 1; end end %check if a new packet has arrived pa=rand(1,1); if pa0 rwait(j)=rwait(j) 1; end end %check for collision if sum(tr)>1 colis(i)=1; for k=1:nstation if tr(k)==1 colin(k)=1; end end end end px2(frate)=(pakeep sum(tq)); py2(frate)=pakeep; end g2=[0:0.01:1.2]; s2=g2.*exp( g2); %figure(1)
PAGE 47
! ', %plot(px2*400/runtime,py2*400/runtime,'x',s2*1e7,g2*1e7,' ') %pl ot(px2,py2,'x',s2,g2,' ') %grid plot(s2,g2*40, 'g' ); xlabel( 'Rate (Lambda)' ) ylabel( 'Expected Delay (Slot)' ) title ( 'Admission Delay for 80' ) ! ! ! ! ! ! ! ! !
PAGE 48
! '! "#"$#%&'()*+ [ 1 ] B.S. Tsybakov and V.A. Mikha ilov Free Synchronous Packet Access in a Broadcast Channel with Feedback ", Problemy Peredachi Informatsii, 1978, Vol. 14, No. 4, pp. 259 280. [2] B. S. Tsybakov and N. B. Likanov Some New Random Multiple Access Algorithms ", Problems of Information Tra nsmission, 1985, Vol. 21, No. 2, pp. 134 154. [3] N. D. Vvedenskaya and B. S. Tsybakov "Random Multiple Access of Packets to a Channel with Errors ," Probl. Peredachi Inf., vol. 19, no. 2, pp. 52 68, 1982. [4] L. Georgiadis and P. Papantoni Kazakos "Li mited Feedback Sensing Algorithms for the Broadcast Channel," IEEE Trans. Inform. Theory, Special Issue on Random Access Communications, 1985, IT 31, No. 2, pp. 280 294. [5] M. Paterakis and P. Papantoni Kazakos, A Simple Window Random Access Algorithm w ith Advantageous Properties", IEEE Transactions on Information Theory, 1989, vol. 35, pp. 1124 1130. [6] A.T. Burrell and P. Papantoni Kazakos "A Class of Limited Sensing Random Access Algorithms with Resistance to Feedback Errors and Effective Delay Con trol", Journal of Communications and Networks, 2006, Vol. 8, No. 1. [7] L. Georgiadis and P. Papantoni Kazakos, A 0.487 Throughput Limited Sensing Algorithm", IEEE Transactions on Information Theory, 1987, vol. 33, pp. 233 237. [8] M. Kaplan, A Suffi cient Condition for Non ergodicity of a Markov Chain", IEEE Transactions on Information Theory, 1979, vol. 25, pp. 470 471. [9] W. Szpankowski, Stability Conditions for Multidimensional Queueing Systems with Computer Applications", Operations Resea rch, 1988, vol. 36, pp. 944 957. [10] W. Szpankowski and V. Rego, Some Theorems on Instability with Applications to Multi Access Protocols", Operations Research, 1988, vol. 36, pp. 958 966. [11] A. G. Pakes, Some Conditions for Ergodicity and Recurre nce of Markov Chains ", Operations Research, 1969, vol. 17, pp. 1058 1061. [12] R. L. Tweedie, Criteria for Classifying General Markov Chains ", Advances in Applied Probability, 1976, vol. 8, pp. 737 771. [13 J.W. Cohen, On Regenerative Processes in Queueing Theory, New York: Springer Verlag, 1976. [14] L. V. Kantorovich and V. I. Krylov Approximate Methods of Higher Analysis New York: Interscience, 1958.
PAGE 49
! (. [15 ] S. Stidman, Jr ., Regenerative Processes in the Theory of Queues with Applications to the Alternating Priority Queue" Adv. Appl. Prob., 1972, Vol. 4, pp. 542 577. [16] L. Georgiadis, L. Merakos and P. Papantoni Kazakos, A Method for the Delay Analysis of Random Multiple Access Algorithms Whose Delay Process is Regenerative", IEEE J ournal on Selected Areas in Communications, 1987, vol. 5, pp. 1051 1062. [17 ] J.C. Huang and T. Berger Delay Analysis of 0.487 Contention resolution Algorithm", IEEE Trans. Commun., Vol. COM 34, pp. 916 926, Sept. 1986. [19 ] Anthony Burrell and Titsa P Papantoni, "Random Access Algorithms in Packet Networks A Review of Three Research Decades." Pp. 1 17.
