1.
3k .4.
«suave.-
efinzfx; .

“qr.
a!
. 1.
:4.“

(4 T tn: 3
I .25.
“an. .

 

 

 

I??? h...

 

ta: ‘
(its... 1. ..
2.5331.

.

¢-’<

shun
, 3..
,. 3

19 RI

m n...

i 33':
€11.19

;
2v." ‘ u? .11“;
_ 532%.? iii:
.114 : . ‘32:; . {um
twr; . . . I... mfimmfi .
. . A . . . gihrflita “m

y . n
r. f
a. {Attic}
1.2.3.11. .8 M
5M3»... .
3. aura 1.36."..- J me
. . ‘ in [$1. .
. ‘5. fig-
.. ..!th..-%h..%|yh.fl.1kh~d

mmfixiék:

n'til"’.‘

V}. w.

Ag?

,|:a ,300

m I115...

3.53. i. .

3:11.er

gaunli
s ‘-

 

\. (511.231

1. 3 5"! .3. . l \ .1, \
htt- Ltnifiltt f I {‘2

1111.5. .7352 I 5:!!!

xz.,4.r.azz\tit)§.

'1‘- . I); ,

.4 ail»...

.3
2x -
3.2.
R..i§..«u
:x

 

 

This is to certify that the
dissertation entitled

Advanced Approaches in lnfonnation Transmission and
Access Control for Wireless Communication Networks

presented by

HUAHUI WANG

has been accepted towards fulfillment
of the requirements for the

PhD. degree in Electrical Engineering

 

 

 

 

Major rofessor’s Signature

//25 /.>ov{

Date

MSU is an Affinnative Action/Equal Opportunity Institution

 

 

LIBRARY
Michigan State
University

 

.-.-u-o-0-.-o-o-O-D-o-u-c-I-o-o-o-n-I---I-.-u-o-o-0-n-o-o-o-l-o--o-o-o-o--s---o-I.

-.—.-o---o-o-o—n—.—-— —.A-

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE

DATE DUE

DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2/05 p:IC|RC/DateDue.indd-p.1

 

”-4.- ......

ADVANCED APPROACHES IN
INFORMATION TRANSMISSION AND
ACCESS CONTROL FOR WIRELESS
COMMUNICATION NETWORKS

By

Huahui Wang

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Electrical and Computer Engineering

2006

ABSTRACT

ADVANCED APPROACHES IN
INFORMATION TRANSMISSION AND
ACCESS CONTROL FOR WIRELESS
COMMUNICATION NETWORKS

By

Huahui Wang

Over the last two decades, wireless communication has seen tremendous growth
and has been demonstrated as a robust voice and data transport mechanism. New
wireless communication methods and services are enthusiastically adopted by people
throughout the world. Driven by the ever increasing demand on high speed wireless
multimedia services, development of highly reliable and more efficient wireless com-
munication networks has become the ultimate goal of the research community. In this
dissertation, we focus on efficient information transmission and medium access con-
trol (MAC) in wireless networks. More specifically, we aim to improve the reliability
and efliciency of the wireless networks through the following research thrusts:

First, we investigate the channel tracking scheme in time-varying environments.
Accurate channel estimation is essential in ensuring reliable information transmis-
sion. However, both time and frequency dispersions in mobile wireless channels cause
significant challenges in channel estimation. Conventionally, for time-varying chan-
nels, pilot (training) signals are periodically transmitted to achieve accurate channel
estimation. Such a scheme is not spectrally efficient due to the considerable overhead
signals. In this dissertation, we propose a semi-blind approach to efficiently estimating
fast fading channels and jointly detecting transmitted signals. The proposed scheme
is shown to have high spectral efficiency and performance reliability. Additional ef-
forts are devoted to studying the extreme case when there are unpredictable abrupt

changes in the channel. We propose algorithms to detect such abrupt changes and

suppress the possible error propagation. The proposed algorithms are demonstrated
to be effective through simulations.

Next, we explore the MAC protocol design by taking into account the physi-
cal (PHY) layer channel capability. In conventional medium access control protocol
designs, the physical layer is simply characterized using a binary collision model.
Although the model provides a tractable path for network performance analysis, it
fails to reflect the physical layer channel capability. Cross-layer medium access con-
trol protocol design, which exploits the physical layer signal processing capabilities
for MAC performance improvement, has attracted considerable research attention.
In this dissertation, taking a mutually interactive perspective, we propose to design
an MAC protocol, named hybrid ALOHA, which is in favor of the physical layer,
and the improved physical layer, in turn, improves the MAC performance in terms
of throughput, stability and delay behavior. Both theoretical and simulation results
show that significant performance improvement can be achieved by hybrid ALOHA,
in comparison with traditional ALOHA.

Finally, from a mixed analog-digital perspective, we investigate a system with
analog inputs and propose a source—aware information transmission scheme to min-
imize the average input-output distortion. After sampling and source coding, the
digital bits could have different levels of significance, i.e., some bits could be more
important than others. Such non-uniformity in source coding then calls for non—
uniform information transmission to improve system performance. An unequal error
protection scheme is proposed to minimize the average distortion. Simulation results
demonstrate its effectiveness. Furthermore, a joint quantization-constellation design
is investigated under the criterion of distortion minimization. The proposed method
generalizes the concept of constellation design from the perspective of joint source-
channel coding. The simplicity and power efficiency of the proposed schemes make
them particularly attractive for systems with tight power constraints, such as wireless

sensor networks and space communications.

Copyright © by
Huahui Wang
2006

Dedicated to my family

ACKNOWLEDGMENTS

I would like to take this opportunity to express my gratitude to my advisor, Dr.
Tongtong Li, for her constant support, guidance and encouragement throughout the
years. She makes her best endeavors to help me in every issue, giving me advice not
only in doing great research but also in personal growth.

I want to thank Dr. Hassan K. Khalil and Dr. Fathi M. Salem from Department
of Electrical and Computer Engineering, and Dr. Jonathan I. Hall from Department
of Mathematics for serving as my committee. I am deeply indebted to them for their
kind support, either in classes or in all thoughtful correspondences. I also want to
thank Dr. J ian Ren for valuable discussions and the help in various technical issues.

I am grateful to a lot of friends who make my life so enjoyable at Michigan State
University. Thanks go to my lab-mates Weiguo Liang, Qi Ling and Leonard Lightfoot,
for the valuable discussions on research and for the advice on the daily life in the
United States. Thanks also go to Jun Yang, Feng Wei, Xiaoyong Li, Xiangrong Guo,
Liyong Wu, Yun Liu, Yingying Shi, Qionghua Qiang, and Keke Yang for being my
tennis parters and for all the fun we have together.

Last, but not the least, I would like to thank my parents, my sister, and my
brother-in-law for their love and ceaseless support. Special thanks go to my lovely
little niece, Junlin, who always talked to me over the phone using her sweetest voice,
“It is nearly noon here. That means midnight in your place. Do you want to go to

bed now?” It is really a great comfort to receive such concerns from a 6-year old girl.

vi

TABLE OF CONTENTS

LIST OF FIGURES x
1 Introduction
1.1 Challenges, Motivations and Proposed Research Directions ...... 1
1.1.1 Major Challenges in Wireless Communications ......... 1
1.1.2 Information Transmission and Access Control in Wireless Com-
munications ............................ 3
1.2 Relationship with Existing Work .................... 5
1.2.1 Channel Estimation and Signal Detection in Time-Varying En-
vironment ............................. 5
1.2.2 PHY-Aware MAC Protocol Design ............... 6
1.2.3 Source-aware Non-uniform Transmission for Minimum Distortion 7
1.3 Overview of the Dissertation ....................... 8
2 Channel Tracking and Signal Detection over Time-Varying Chan-
nels 11
2.1 Introduction ................................ 11
2.2 System Model ............................... 13
2.2.1 'Ii'ansmitter Structure ...................... 13
2.2.2 Channel Model .......................... 15
2.2.3 Received Signal .......................... 16
2.3 Joint Channel Estimation and Signal Detection ............ 18
2.3.1 Initial Channel Estimation .................... 18
2.3.2 Joint Channel Estimation and Signal Detection ........ 20
2.4 Detection and Tracking of Abrupt Channel Changes .......... 21
2.4.1 Detection of Abrupt Channel Changes ............. 21
2.4.2 Extraction and Tracking of the Abrupt Channel ........ 24
2.5 Simulation Results ............................ 26
2.5.1 Performance under the Jakes’ Model with No Abrupt Changes 28
2.5.2 Performance under the J akes’ Model with Abrupt Changes . . 30
2.6 Summary ................................. 35
3 Mutually Interactive Random Access Control for Wireless Networks 36
3.1 Introduction ................................ 37
3.2 The Hybrid ALOHA Protocol ...................... 41
3.2.1 System Model ........................... 41
3.2.2 Hybrid ALOHA .......................... 42

vii

3.3 Throughput Calculation ......................... 43
3.4 Stability of Hybrid ALOHA ....................... 48
3.4.1 Stability Region for N = 2 .................... 48
3.4.2 Sufficient Condition of Stability for N > 2 ........... 53
3.5 Special Case: Stability Inner Bound for N = 3 ............. 56
3.5.1 Inner Bound Characterization .................. 56
3.5.2 Analysis of the Kernel K (:r, y) .................. 60
3.5.3 Reduction to the Riemann-Hilbert Problem .......... 62
3.5.4 Solution to the Riemann-Hilbert Problem (3.48) ........ 63
3.6 Delay Performance for N = 2 ...................... 66
3.6.1 Exact Delays for the General Case ............... 66
3.6.2 Delay Bounds for the Symmetric Case ............. 67
3.7 An Illustrative Example ......................... 70
3.7.1 System Set-up ........................... 70
3.7.2 Evaluation of Channel Estimation Error ............ 72
3.7.3 Probabilities of Successful Signal Receptions .......... 73

3.7.4 Throughput of Hybrid ALOHA with Imperfect Channel Esti-
mation ............................... 75

3.7.5 Stability Regions and Delay Bounds with Imperfect Channel
Estimation ............................. 77
3.8 Summary ................................. 81
4 Source-Aware Non-Uniform Transmission for Minimum Distortion 82
4.1 Introduction ................................ 82
4.2 Problem Formulation ......................... '. . 84
4.3 Joint Source Index Assignment And Constellation Code Design . . . 86
4.4 Source-Aware Non-Uniform Transmission Design ............ 90
4.4.1 Non-Uniform 'II‘ansmission Based on Gray-Code Constellations 90
4.4.2 Source-Aware Constellation Design ............... 96
£1.E5 Eitirrirrizairyr ................................. SJSI
5 Conclusions and Future Work 100
5.1 Conclusions ................................ 100
5.2 Future Work ................................ 101
APPENDICES 103
A Alternative Proof of Proposition 3.1 for M = 2. 104
B Proof of Lemma 3.1. 108
C Proof of Proposition 3.2. 110

viii

D Proof of Proposition 3.4.

E Formulation of Functional Equation (3.27)
F Proof of Lemma 3.2

G Proof of Lemma 3.3

H Proof of Proposition 3.7.

BIBLIOGRAPHY

ix

112

114

116

118

119

123

2.1
2.2

2.3

2.4

2.5

2.6

2.7

3.1

3.2

3.3
3.4
3.5
3.6

3.7

LIST OF FIGURES

Transmitter structure in an uplink MC-CDMA system. ........
BER performance under the Jake’s model with no abrupt changes,
K = 8, P = 16. ..............................
MSE performances of the proposed channel estimation at different SNR
levels. ...................................
Impact of timing errors on the BER performance, S N R = 25dB: inde-
pendent ofl'sets means that users have independent timing errors uni-
formly distributed within interval [0,0.25]ns, common ofisets means
that all users experience the same timing shift ..............
Accumulated channel deviation ¢k when user k (k = 1, 2, 3, 4) is iden-
tified to be subjected to abrupt channel changes, while user 1 is the
true user whose channel undergoes abrupt changes and other users’
channels are “smooth”. K = 8, P = 16 ..................
Channel estimates (only real part of the channel is shown) with the
proposed error propagation control: SN R = 20dB, K = 8, P = 16,
user 1 undergoes abrupt channel changes. Only results of 4 out of 8
users are presented .............................
BER performances of the system over channels with and without
abrupt changes. Here “perfect CS ” means that the channel state
information is perfectly known at the receiver, including information
on abrupt changes. ............................

Mutual interaction of MAC layer and PHY layer to achieve perfor-
mance optimization. ...........................
Illustration of the hybrid ALOHA slot structure for M = 2, in the
case that two users (N = 2) transmit their training sequences at non-
overlapping pilot sub-slots .........................
Throughput comparison between hybrid ALOHA and traditional slot-
ted ALOHA .................................
Stability regions for different protocols in the two-user case. .....
Delay bounds for the system with different parameters. ........
Throughput comparison of different schemes under the specific system
settings, SNR = 10dB, c = 6dB, 53, = 0.01, 5.32 = 0.06. ......
Numerical values of T achieving equilibrium points and Topt maximizing
the throughput of hybrid ALOHA . ...................

14

27

29

30

32

33

34

39

43
47
50
69
76

78

3.8

3.9

4.1
4.2
4.3
4.4

4.5
4.6
4.7

Comparison of stability regions of different schemes, SN R =
10dB, 6 = 6dB, 63, = 0.01, 632 = 0.06. ................

Comparison of delays of different schemes, SN R = 10dB, fl =
6dB, 661 = 0.01, 532 = 0.06, p = 0.75. ................

System Model ...............................
Mapping of quantized values to the 16-QAM constellation. ......
Symmetric 16—AM constellation ......................
(a) Asymmetric 16-QAM, all > d2; (b) Symmetric 16-QAM with Gray
codes. ...................................
MSE for different transmission schemes: Uncoded System. ......
MSE for different transmission schemes: Coded System (A = d2/d1). .
Example 3: (a) Source distribution (b) Normalized MSE under differ-

79

85
88
89

ent SN R levels, uniform 4-AM versus the proposed source-aware 4—AM. 98

“Images in this dissertation are presented in color”

CHAPTER 1

Introduction

1.1 Challenges, Motivations and Proposed Re-

search Directions

Over the last two decades, wireless communication has seen tremendous growth and
has been demonstrated as a robust voice and data transport mechanism. New wireless
communication methods and services are enthusiastically adopted by people through-
out the world. Driven by the ever increasing demand on high speed wireless multime-
dia services, development of highly reliable and more efficient wireless communication

networks has become the ultimate goal of the research community.

1.1.1 Major Challenges in Wireless Communications

Compared with its wirelined counterpart, the major challenges in wireless commu-
nication system design are caused by the unpredictable distortion and interference
in the wireless environment, and by the limitation of the precious spectrum which is

always in shortage. ‘

Information Transmission over Time-Varying Wireless Channels The fun-
damental limitations on the performance of wireless communications are placed by
the unpredictable distortion and interference over wireless channels. Unlike wirelined
channels which are generally stationary and predictable, wireless channels are time-
variant and totally random. Due to high user mobility and the fact that there is no

physical boundary in wireless environment, wireless channels are influenced by many

physical factors including mobile radio propagation, the relative motion between the
transmitter and the receiver, motions of surrounding objects and diversity in the sig-
nal transmission (e.g., time/frequency/space diversity). Effective time-varying chan-
nel tracking and efficient transmission schemes play the key roles in increasing the

information capacity over wireless channels.

Spectrum Efficiency in Multiple Access Environment Spectrum is precious
in wireless communications. In wirelined communication, new and additional band-
width requirement can often be granted by adding another line between the trans-
mitter and receiver. In wireless environment, however, different services and different
users have to share the total available bandwidth. Along with advances in radio fre-
quency (RF) technology, the available spectrum has become much larger than ever
before, but the demand on wireless services has also increased enormously. Take
the mobile phone as an example. Mobile communication was commercialized in late
1970s and early 19803. At that time, the mobile phones relied on analog techniques,
only voice service was available and few people had access to the mobile network.
This is referred to as the first generation wireless communications. In early 1990s,
digital communications gradually replaced their analog counterparts and became the
dominant transmission technique in wireless communications. In addition to pure
voice service, data services, such as short messages and FAX, became available and
many more users could be accommodated by the wireless network. This is referred to
as the 2nd generation wireless communications. Today, while we are moving to the
3G (3rd generation) era, the number of worldwide wireless subscribers is approach—
ing two billion. High speed multimedia wireless services, such as wireless internet
access, wireless electronic commerce, are coming into reality. Spectrum, therefore,
has become the most valuable resource. Spectrally efficient wireless system design in

multiple access environment has become the impetus in wireless communication area.

1.1.2 Information Transmission and Access Control in Wire-

less Communications

In wireless communications, users first access the wireless network through the ran-
dom access channel to build up a handshake with the mobile switch center through
one or more base stations, and then start the pay-load information transmission. In I
this dissertation, rooted in physical layer (PHY) transmitter—receiver design, we will
focus on efficient information transmission and PHY-aware medium access control
(MAC) in wireless networks. More specifically, we plan to improve the reliability and

efficiency of wireless networks through the following research thrusts:

Time-Varying Channel Tracking Accurate channel estimation is essential in
ensuring reliable information transmission. In wireless communication, the time-
varying wireless channel has both time dispersion (frequency selective fading caused
by multipath fading) and frequency dispersion (Doppler spread caused by relative
motion between the transmitter and receiver). This raises significant challenges in
channel estimation. On the one hand, pilot signals (training bits or symbols) have
to be inserted frequently to achieve accurate channel estimation. On the other hand,
we need to minimize the overhead bits for the sake of spectral efficiency.
Conventionally, channel estimation in wireless communications is performed
through the following procedure. First, divide the time axis into very short time
slots. Secondly, approximate the time-varying channel using a time invariant channel
in each short slot. Finally, carry out channel estimation by inserting pilot signal in
each slot. This method is acceptable in slow-varying environment, but would fail to
deliver satisfying performance when fast fading is present. To track the time-varying
wireless channels closely, we go back to the analytical characterization of doubly se-
lective channels. Mathematically, a time-varying channel is characterized by h(t,1'),
which denotes the channel response at time instant t to the unit impulse at t — 1'.
Therefore, instead of carrying out one-dimensional channel estimation as in the con-
ventional method, we put it into a two-dimensional framework and perform channel

estimation in the time-frequency domain. Semi-blind approaches are exploited to

minimize the overhead bits and therefore increasing the spectral efficiency.

PHY-Aware MAC Design Conventionally, random access control protocols are
designed disjointly by characterizing the underlying physical layer using a binary
collision model. Briefly speaking, this means that when two users attempt to access
the random channel simultaneously, a collision occurs, and we then say that both are
failed; a transmission is successful if and only if one single user transmits.

More recently, researchers started to realize that although it provides a tractable
path for network performance analysis, the collision model fails to reflect the physical
layer channel capability. Cross-layer medium access control protocol design, which
exploits the physical layer signal processing capabilities for MAC performance im-
provement, has attracted considerable research attention. In this dissertation, taking
a mutually interactive perspective, we propose to design an MAC protocol which is in
favor of the PHY layer, and the improved physical layer, in turn, improves the MAC

performance in terms of throughput, stability as well as delay behavior.

Source-Aware Information Transmission The meeting ground for analog and
digital signals is the A/ D conversion. In today’s most communication systems, after
sampling and source coding, all the bits are treated uniformly. According to the infor-
mation theory, when entropy coding is applied, then all the bits carry an equal amount
of information. However, as the a priori statistics of the input signals are generally
unavailable, non-entropy coding is widely used in practical systems. This implies that
some bits are more important than others. This universal existence of non-uniformity
in source coding therefore calls for non-uniform information transmission.

In the literature, without taking quantization optimization into consideration, bit-
level unequal error protection schemes have been proposed to provide more protection
to the most significant bits. Our research on non-uniform information transmission
is motivated by the observation that: when the inputs are analog, the ultimate goal
of the communication system is to minimize the average input-output distortion,

and a communication system that minimizes the bit-error-rate does not necessarily

minimize the average distortion. Taking a joint source-channel coding perspective,
we propose to minimize the average distortion through joint quantization design and

constellation index assignment.

1.2 Relationship With Existing Work

In this section, we discuss the relationship between the existing and the proposed

work.

1.2.1 Channel Estimation and Signal Detection in Time-

Varying Environment

In dynamic time-varying environments, traditional channel estimation techniques for
time-invariant models are no longer applicable. To track time-varying channels, a
widely used approach is to transmit pilot signals periodically such that the receiver
can update the channel estimates timely. Such a method results in considerable
overhead bits in fast fading channels and costs excess bandwidth.

To improve spectral efficiency, joint channel estimation and signal detection ap-
proaches have been proposed to reduce the overhead bits [FC91, KV94, RSAA97,
Moh98, AGR98,VD98, WP99]. The main idea is to use the estimated symbols as
pseudo-pilot signals for channel estimation, and then improve the subsequent sig-
nal detection based on the refined channel estimates. For time-varying channels,
joint channel/signal estimation based on Kalman filtering has been representative
[Ilt90,IF91,KI02]. As is well known, Kalman filtering results in the optimal minimum
variance estimator for channels characterized by the first-order autoregressive (AR)
model [AM79], provided the model parameters are known to the receiver. In most of
the existing work utilizing Kalman filtering [Ilt90,IF91, K102,VT95, RPT95,WP98],
time-varying channels are modeled as AR processes with known parameters, and no
efforts are taken to estimate them. To bridge this modeling gap, [TGZ96] derives

a method for estimating the model parameters. In more general cases when chan-

nel model parameters are too complicated to obtain, adaptive receivers have been
developed in [KSP03, WP98].

In this dissertation, an alternative joint channel estimation and signal detection
scheme is proposed in time-varying environment. The scheme is advantageous in that
it has very high bandwidth efficiency while not requiring any model fitting process
to obtain channel model parameters. In addition, algorithms are proposed to detect
and track abrupt channel changes and thus are capable of suppressing possible error

propagations.

1.2.2 PHY-Aware MAC Protocol Design

Regarding cross-layer design, there has been a line of work focusing on performance
improvement from joint MAC-PHY perspective. The prevalent design is to exploit
the PHY information, e.g., the channel state information (CS1), in random access
to achieve optimal system performance in terms of throughput and delays, etc. The
pioneering work was carried out by Knopp and Humblet in [KH95], where the CSI
is incorporated in random access for ALOHA systems. It was shown that, under the
average power constraint, maximizing the sum-rate leads to scheduling the best user
to transmit. In [T399], decentralized use of the CSI was investigated by Telatar and
Shamai. It was shown in [TH98] that multiuser diversity is induced when exploit-
ing the CSI, and the maximum sum-rate could be improved with the increase of the
number of users. In [QBOl], Qin and Berry used the CSI to control the transmis-
sion probability in ALOHA. The effect of multiuser diversity on the throughput was
analyzed as well.

The schemes discussed above adopted the well-known ideal collision model: when
only one user transmits, the packet arrives at the receiver error free. The model is
over-simplified in terms that it overlooks the channel effects such as fading and noise,
and it also ignores the possibility of successful packets reception in the presence of
simultaneous transmissions. A more realistic model, called multipacket reception
(MPR) model, was proposed by Ghez et al. in [GV888]. The proposed MPR model

is symmetric in the sense of indistinguishable users in the network, while it offers the

generalization that when there are simultaneous transmissions, the reception can be
described by conditional probabilities. A more general asymmetrical MPR model was
proposed in [NMT05], and the performances in terms of system stability and delay
behavior for ALOHA networks were investigated.

These cross-layer designs share a common feature that they take into account
the PHY-MAC interaction yet in a “one way” fashion. That is, only the impact
of the PHY layer information on the MAC layer design is considered, and no effort
has been taken to study how the MAC protocol design would influence the PHY
layer information transmission. In this dissertation, the MPR model is adopted to
analyze the system performance of a proposed ALOHA protocol. The study takes
a mutually interactive MAC-PHY perspective to design an MAC protocol that is in
favor of the PHY layer information transmission, while the improved PHY layer can
in turn improve the overall system performance. Details of the analysis are referred

to Chapter 3.

1.2.3 Source-aware N on-uniform It'ansmission for Minimum

Distortion

In [ZG93], with no specifications on the modulation schemes, Zeger proposed a locally
optimal index assignment (source coding) solution for minimum input-output distor-
tion, known as pseudo-Gray coding, by using iterative binary switching. Pseudo-Gray
coding provided an effective approach in reducing the average distortion of a vector
quantized system by rearranging the positions of code vectors in a given codebook.
Various channel-optimized quantizers, multistage vector quantizers have been studied
in [FV87, PFM93,WF94].

On the other hand, assuming that source index assignment has been done sepa-
rately, and with the observation that the bits coming out of the source encoder are gen-
erally non-uniform (i.e. have different levels of significance), Masnick, Wolf [MW67]
and Cover [Cov72] introduced non-uniform modulation (index mapping) schemes,

known as unequal error protection codes, for which the more important bits have lower

error rate than other bits. Stemmed from [MW67, Cov72], unequal error protection
schemes through both symmetric and asymmetric constellation designs have been fur-
ther developed in [ROUV93], [MZFLIOOa] and [MZFLIOOb]. It should be pointed out
that the resulted constellation codeword design in [ROUV93, MZFLIOOa, MZFLIOOb]
may no longer be Gray codes.

In this dissertation, taking a mixed analog-digital perspective, we consider aver-
age input-output distortion minimization through joint optimization of source index
assignment and modulation design. Based on the fact that Gray code ensures mini-
mum bit error rate (BER) when the channel error probability is sufficiently small, a
source-aware information transmission approach is proposed by exploiting the non-

uniformity in Gray-coded constellations to achieve unequal error protection.

1.3 Overview of the Dissertation
In the dissertation, we address the following specific questions:

0 In time-varying environments, how to design efficient channel estimation and

signal detection techniques to cope with channel dynamics?

0 Ffom the joint MAC-PHY perspective, how can the cross-layer design improve

the wireless network performance in terms of throughput, stability and delay?

0 Considering data non-uniformity from source coding, how to employ unequal

error protection to minimize average input-output distortion?

The dissertation is structured as follows.

Chapter 2 presents a joint channel estimation and multiuser detection method
over time-varying channels for multicarrier code division multiple access (MC-CDMA)
systems. The general Jakes’ model is adopted without any assumption about the
channel model parameters. Only one pilot symbol is required at the beginning of
each data frame for initial channel estimation. Based on the fact that the channel co-

efficients of two successive symbols are highly correlated, subsequent channel tracking

and signal detection are carried out iteratively. An effective error control approach
is proposed to track abrupt channel changes and extract the user whose channel
suffers from such changes. With this process, error propagation can be successfully
suppressed and all users channel estimates can be updated accurately.

Chapter 3 goes beyond the PHY layer design to improve overall system per-
formance by considering cross-layer medium access control (MAC) design in wireless
networks. Taking a mutually interactive MAC-PHY perspective, we aim to design an
MAC protocol that is in favor of the PHY layer information transmission, and the
improved PHY, in turn, can improve the MAC performance. Motivated by the fact
that as long as good channel estimation can be achieved, advanced signal processing
does allow effective signal separation given that the multiuser interference is limited
to a certain degree, we propose a novel MAC protocol, named hybrid ALOHA, which
allows conditional collision-free channel estimation and makes it possible for simul-
taneous multiuser transmission. More specifically, short idle sections are introduced
into the structure of the traditional ALOHA slot, so that different users could trans-
mit their training sequences in non-overlapping training slots, whereby collision-free
channel estimation could be achieved. Relying on the general multipacket reception
(MPR) model, in this chapter, quantitative analysis is conducted for the proposed
hybrid ALOHA protocol in terms of throughput, stability as well as delay behavior.
Both theoretical derivation and simulation examples demonstrate that significant per-
formance improvement can be achieved by hybrid ALOHA, in comparison with the
traditional ALOHA protocol.

Chapter 4 considers average input-output distortion minimization through joint
optimization of source index assignment and modulation design. First, the general
optimization criterion is derived. Secondly, source-aware non-uniform information
transmission is proposed by utilizing the inherent non-uniformity in Gray coded con-
stellations, both symmetric and asymmetric. It is found that when channel coding is
involved, the proposed scheme delivers significantly better performance in comparison
with existing unequal error protection schemes with non-Gray codewords. Further,

joint quantization-constellation design is considered under the criterion of distortion

minimization. The proposed method generalizes the concept of constellation design
from the perspective of joint source-channel coding. The simplicity and power effi-
ciency of the proposed scheme make it particularly attractive for systems with tight
power constraints, such as wireless sensor networks and space communications.
Chapter 5 discusses conclusions and possible extensions of the work covered in

this dissertation.

10

CHAPTER 2

Channel Tracking and Signal
Detection over Time-Varying

Channels

In this chapter, a joint channel estimation and multiuser detection method is pre-
sented for uplink MC-CDMA systems in time-varying environment. Unlike the con-
ventional channel tracking schemes which generally need to insert pilot bits in every
OFDM symbol, in the proposed approach, only one pilot symbol is required at the
beginning of each data frame. Based on the fact that the channel coefficients of two
successive symbols are highly correlated, subsequent channel tracking and signal de-
tection are carried out iteratively. A major contribution of the proposed approach
is that it enables robust error propagation control, and is capable of detecting and
tracking abrupt channel changes effectively. Simulation examples demonstrate the

robustness of the proposed algorithms.

2.1 Introduction

Multicarrier code division multiple access (MC-CDMA) [YLF93,HP97], which amal-
gamates the advantages of both orthogonal frequency division multiplexing (OFDM)
and CDMA, has been identified as a major technique for high speed wireless com-
munications. However, good performance for MC-CDMA is only guaranteed with
accurate channel state information (CSI) and effective demodulation. As wireless

communication at higher frequency bands is becoming possible, relative motion be-

11

tween the mobile, the base station and the surrounding objects introduces significant
frequency dispersions. 'Ifaditional channel estimation techniques for time-invariant
models are no longer applicable.

To track the time-varying channels, a widely used approach is to insert pi-
lot bits (also referred to as “pilot-carriers” in literature) in each OFDM symbol,
and to estimate the channel coefficients utilizing filtering in the frequency domain,
see [ChoOO,CMSOl] for example. In [HKR97] and [KH97], a two-dimensional (2-D)
pilot grid is designed to insert pilot bits in both the frequency dimension and the
time dimension, based on the 2—D sampling theorem. These pilot-aided techniques
yield good performance in fast fading scenarios but result in a considerable amount
of overhead bits.

To improve spectral efficiency, joint channel estimation and signal detection ap—
proaches have been proposed to reduce the overhead bits [FC91, KV94, RSAA97,
Moh98, AGR98, VD98, WP99]. The main idea is to use the estimated symbols as
pseudo-pilot signals for channel estimation, and then improve the subsequent sig-
nal detection based on the refined channel estimates. For time-varying channels,
joint channel/signal estimation based on Kalman filtering has been representative
[Ilt90,IF91,K102]. As is well known, Kalman filtering results in the optimal minimum
variance estimator for channels characterized by the first-order autoregressive (AR)
model [AM79], provided the model parameters are known to the receiver. In most of
the existing works utilizing Kalman filtering [Ilt90,IF91,K102,VT95,RPT95,WP98],
time-varying channels are modeled as AR processes with known parameters, and no
efforts are taken to estimate them. To bridge this modeling gap, [TGZ96] derives
a method for estimating the model parameters. In more general cases when chan-
nel model parameters are unknown, adaptive receivers exploiting least mean square
(LMS) and recursive least square (RLS) algorithms are developed for synchronous
MC—CDMA systems [KSP03,WP98]. Moreover, in [SMMO4], channel estimation is
performed using LMS for a quasi-synchronous MC-CDMA system, with the assump-
tions that the channel is invariant within the the training period, and the number of

the training blocks are greater than or equal to the number of active users.

12

In this chapter, assuming a practical quasi-synchronous MC-CDMA framework,
we propose a novel joint channel estimation and multiuser detection scheme over fast-
fading channels. Instead of assuming a known AR model, we use the general Jakes’
model [J ak74], making no assumptions on the knowledge of the channel model param-
eters. Targeting on higher spectral efficiency, the proposed approach requires only
one pilot symbol for initial channel estimation. A coarse estimate of the subsequent
symbol is obtained utilizing the CSI of the previous symbol, and then refined through
an iterative process. The reliability of such a detection method is based on the fact
that, although the channel may vary fast and become uncorrelated over some period,
the channel coefficients for two successive multicarrer (MC) symbols are highly cor-
related. Multiple access interference (MAI) can then be reconstructed and canceled
out from the composite signal using parallel interference cancelation (PIC) [VA91],
hence improve the accuracy of signal detection.

Under circumstances when the channel undergoes unpredictable abrupt changes,
joint channel estimation and signal detection schemes are generally subjected to sig-
nificant error propagation. The major contribution of the proposed scheme is that,
while achieving higher spectral efficiency, it is capable of detecting and tracking abrupt
channel changes, and thus can ensure robust error propagation control.

The rest of the chapter is organized as follows. Section 2.2 describes the MC-
CDMA system as well as the time-varying channel model. Section 2.3 introduces
the proposed algorithm for joint channel estimation and signal detection. Section
2.4 is focused on error propagation control for channels subjected to abrupt changes.

Simulation results are presented in Section 2.5 and we conclude in Section 2.6.

2.2 System Model

2.2.1 Transmitter Structure

Consider an uplink MC—CDMA system with K users. The transmitter structure of
user It is illustrated in Figure 2.1. The input binary stream is first mapped to BPSK

13

or QPSK symbols and then grouped into J-symbol blocks. The ith block for user It
is denoted as dkfl'. Each block of data is spread into N = PJ chips using the user’s
specific pseudo-random spreading codes {cm-(n), n = 0, 1, N — 1}. Here, P is the
spreading factor.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

d . -_-
Binary Data > Mapper ~> Grouping ~ » J“ v Spreading rN—PJ;
XL: ,
........................... E I S .
5: Interleaving , SIP :N IFFT /> P/S > OF -»""~~k >
y

 

 

 

 

 

 

Figure 2.1. Transmitter structure in an uplink MC-CDMA system.

Before the spread signals are modulated on different OFDM subcarriers, a P x J
block interleaver is employed to maximize the diversity and hence reduce the risk that
all these chips suffer severe fades at the same time. At the receiver, a corresponding
.1 X P deinterleaver is employed to reshape the signals. Interleaving plays an important
role in improving the system performance, while for simplicity of notation, they are
omitted in the subsequent description. In the simulations, however, their effects are
taken into account.

The spread/ interleaved signals modulated on OFDM subcarriers are saved in a
vector x,”- = [arm-(0), - -- ,$k,i(N — 1)]T. The output of the IF FT block is parallel-
to—serial converted, and appended with cyclic prefix (CP) at the beginning of the
modulated symbol. To prevent intersymbol interference (131), the length of the CP
is assumed to be equal to the maximum channel order L. Following the notations

in [WGOO], the extended OFDM symbol, which is referred to as an MC symbol, can

14

be described by a transformation given by
Sk,i = Tchxkfl', (2.1)

where T6,, = [IT,171(,]T, Icp represents the last L rows of an N x N identity matrix
I N, and F is the IF FT matrix defined as

0 N—l
WRIO . . . WN( )
F _ _1_ : - :
— N , . )
(N—1)0 (N—1)(N—-1)
WN WN

with W173," = eflmk/N.

2.2.2 Channel Model

The baseband equivalent channel is generally characterized using a multipath time-

varying response [Ste92, LJ S98],

W. T) = 271(050 - 71(0), (22)

l
where 6(3) denotes the Dirac delta function, n(t) and 71(t) are the delay and the
complex amplitude of the lth path at time instant t, respectively. The channel’s

frequency response with respect to 1' at time t is given by
H0. f) = Emma—9'2” ’1“). (2.3)
l

71(t)’s are usually considered to be wide-sense stationary (WSS) and independent for
different paths. Hence the time-varying correlation function of H (t, f), defined as
RHfAt, AI) = E[H(t+At, f+ Af)H*(t, f)], can be decomposed as the product of a
time-domain correlation function Rt(At) and a frequency-domain correlation function
Rf(Af) [LJSQS]:

RHfAta Af) = Rt(At)Rf(Af)- (2-4)

15

For an MC-CDMA system with symbol duration T and tone spacing Af, the corre-

lation function for different MC symbols and different tones can be written as
RH(iT, nAf) = Rt(iT)Rf(nAf). (2.5)
For the Jakes’ model [Jak74], the time correlation function can be expressed as
12,037“): J0(27rfdi7‘) (2-6)

where Jo (at) is the zeroth-order Bessel function of the first kind and fd is the maximum
doppler shift caused by frequency dispersion.

In practical systems, unpredictable, abrupt channel changes may occur due to
sudden changes in the transmission environment. These changes can no longer be
fully characterized using a WSS model. In this chapter, channels with or without
abrupt changes are both considered. Abrupt channels are generated by imposing

sudden, random changes to channels obtained from the J akes’ model.

2.2.3 Received Signal

Sampling the received signal at t = mT/Ns (chip rate), where N, = N + L, we obtain

r(m)=

—Ak) )+ 'w(m), (2.7)

LTD/1x

where rk(m — Ak) is the received signal for user k, which is the convolution of the
transmitted signals and the corresponding channel coeflicients, w(m) is the additive
white Gaussian noise (AWGN) with zero mean and double-sided power spectral den-
sity of No/ 2. Ak denotes the kth user’s propagation delay. As in [SMMO4], we
consider a quasi-synchronous system where Ak is uniformly distributed within the
CP. The quasi-synchronization can be realized by providing each user a global posi-
tioning system (GPS) based receiver [IM96]. At this stage, for notation simplicity,

we assume that Ak is known at the receiver. However, simulation result with timing

16

error will be presented in Section 2.5.

After the CP removal, the ith symbol input to the kth user’s FFT demodulator,
which is synchronized with user It, is saved in vector 2;“- = [r(iN3+L+Ak), - - - ,r((i+
1)N3 + Ak — 1)]T. Separating the desired signal and the MAI components, zkfi- can

be expressed as

zuzzk1)+ Z zgf i),+wk,-, i=0,1,-~ (2.8)

J'= —1.j¢k
where 2(0) =[r (iNs + L), r((i + 1)N — 1)]T is the desired si nal for user It
ki k k 3 g a

zg-Ii)= [rj( (iNs + L + Ak — A j), ,rj((i + 1)N3 + Ak — Aj — 1)]T represents the
interference from user j, and w,”- is the AWGN noise. After the FFT demodulation,

the kth user’s signal can be written as

K
was = 1""st = Xk,in,i + 2 13,1 + View (29)
i=1J¢k
where the superscript i denotes Hermitian transpose, Xk,i = diag(xk,,-) is the desired
signal, v,”- = Flwa- is the noise term, 113,- : Flzgi) is the interference from user j.
H,”- = [Hm-(0), - -- ,Hk,,-(N — 1)]T represents the frequency domain channel coeffi-
cients of the N subcarriers. If the channel order is L, the corresponding time domain

coefficient hkfi- = [hm-(0), - -- ,hk,,-(L)]T is related to H,”- by

h i = [FlL+IHk,it (2°10)

where [F] L+1 means that only the first L + 1 rows of the matrix F is retained.

17

2.3 Joint Channel Estimation and Signal Detec-
tion

In this section, the proposed approach for joint channel estimation and multiuser
detection is presented. Instead of setting aside pilot carriers in each MC symbol, only
one pilot symbol is needed at the beginning of each data frame. For each symbol,
PIC is exploited to suppress MAI and improve system performance. The proposed

algorithm is outlined below:

1. At the beginning of each data frame of user k (k = 1, - - - , K), one pilot symbol

xk,0 is transmitted to obtain an initial channel estimate fikp;

2. For the ith (i > 0) symbol, based on the channel information estimated from
the previous symbol, i.e., fik,i_1, a rough coherent detection is performed to

obtain a tentative symbol estimate 52kg;

3. With the tentative signal ikn’ and the channel information fin-4,
(k = 1, - -- ,K), MAI is reconstructed and canceled out from the composite
signal; a more accurate channel estimate for the ith symbol, film”, is obtained

and then utilized to get a more accurate estimate of the ith symbol, denoted as
files;

4. Step 3 can be performed iteratively to achieve better performance by feeding

)2,”- back to further refine the channel estimation and signal detection;

5. fika' is used as the channel information for the next symbol and Step 2 to Step

4 are repeated to process each symbol recursively in the rest of the data frame.

Details of the algorithm are presented in the following subsections.

2.3.1 Initial Channel Estimation

The initial channel estimation is performed in an OFDMA fashion as below. Suppose

the maximum channel order is L, then M (L < M < N) subcarriers are chosen to

18

transmit pilot bits for each user. For simplicity, assume N / M = Q is an integer. The

pilot symbol for user k is then given by

aIic,o(n) = i1’ n e 8’“ (2.11)
0, elsewhere,

where :L-l means the pilot bit is randomly chosen from {+1, —1}, 9]: defines a set of
uniformly Q—spaced subcarriers for user It (1 S k S K), given by 9k = {0 S n S
N—1 In =(k—L%le—1)+m-Q, m = 0,--- ,M—l}, where [a] is the maximum
integer less than or equal to 2:. If the number of total active users K is not greater
than Q, then 91: Fl 61 = 0, V1 3 k,l S K,k aé I, that is, the users transmit their
pilot bits in non-overlapping subcarrier groups. In this case, MAI is mitigated at the

training stage, resulting in accurate initial channel estimation.

Remark 2.1 Note that increasing M improves the performance of channel estima-
tion in the single-user case. However, it reduces the value of Q at the same time.
In the case when K > Q, more than one user need to transmit pilots on the same
subcarriers. The resulting MAI degrades the channel estimation quality. To accom-
modate more users and perform MAI-free initial channel estimation, one can increase
the value of N, yet it requires more bandwidth. An alternative solution is to allocate

more M C symbols for initial channel estimation and distribute users ’ pilots in a time-

frequency grid, which mimics a TDMA-FDMA scheme.

Denoting yk,0(n) as the received signal on subcarrier n, the least-squares (LS)

estimate of the channel frequency response on subcarrier n is given by

ch,0(n) = yk,0(n)/ III/c001), ’1 E 616- (2-12)

Stack the M elements PIk’0(n), n E 8k into one vector Hek =
[Hk’0(n1),- ~- ,I:Ik,0(nM)]T, where ni E 8,, for i = 1, - -- ,M. The channel estimate
in the time domain fik,0 = [hk,0(0), - - - ,hk,0(L)]T can be obtained by

fik,0 = [FlL+1,ekfiek, (2-13)

19

where [F] L+1,8 k is part of the IF FT matrix with the first L +1 rows and the columns
with indices belonging to set 6,, retained.

Augmenting the channel coefficients h“) to be hfio = [h£0,0£_L_1]T, where
ON—L—l is an all-zero vector of dimension (N — L — 1) x 1, the channel response of
user k in the frequency domain, Hkfl = [Hk,0(0), - -- ,Hk,0(N — 1)]T, is then given
by

1‘1“, = Fihfio. (2.14)

2.3.2 Joint Channel Estimation and Signal Detection

Relying on high correlation between the channel coefficients of two successive symbols,
we use flk,5_1 as the coarse CSI for the detection of the ith symbol. When the tentative
decision dkfl: is obtained based on flk,¢_1, MAI is reconstructed and PIC is performed

to cancel the interference. The “cleaner” signal for user k is then given by

K
5k,i(") = 1(le + A}: + n) - Z 123-(n + Ak — Aj), O S n S N3 - I, (2.15)
15111.76,“

where the reconstructed signal for user j, fj(n + A): — Aj), is a function of d”-
and hj,,-_1. It involves a convolution operation which requires (L + 1) complex mul-
tiplications and L complex additions. Hence the computational complexity of the
MAI cancelation in (2.15) is 0[KN3(L + 1)], which is slightly larger than that of the
matched filter (MF) bank, 0[2K N].

After the FFT demodulation, the output is given by
K ~
S’Im' = Xk,in,i + Z 1332' + Vk,z'~ (2-16)
i=1J¢k

The major difference between (2.16) and (2.9) is that MAI has now been reduced to

residual interference, and hence more accurate channel estimation can be achieved.

20

Estimate of HkJ- is then given by

A

Hi..- = We]... (2.17)

where K = diag(xk,,-) with 52,”- originating from the tentative decision d“. Due to
the diagonalmatrix of K, the channel estimation procedure only requires N complex
divisions.

With the updated channel coefficients, more accurate MAI can be reconstructed
and canceled out. An even “cleaner” signal can be obtained and only single user
detection (SUD) is required to obtain d“, which is the final estimate of the original
data dk,i- As discussed above, this PIC refinement procedure takes roughly twice as

many arithmetic operations as that of the MF bank.

2.4 Detection and Tracking of Abrupt Channel
Changes

The proposed scheme in the previous works well under the Jakes’ model, as will be
demonstrated in the simulation examples. However, when channels experience unpre-
dictable abrupt changes, severe error propagation could occur, resulting in significant
performance degradation. To achieve tight error propagation control, in this sec-
tion, simple but robust algorithms are proposed for effective detection and tracking

of abrupt channel changes.

2.4.1 Detection of Abrupt Channel Changes

We assume channels are uncorrelated and no channel suffers abrupt changes simulta-
neously with any other channels. Without loss of generality, the time domain channel

coefficients for user I at time i, hln' = [hm-(0), . - - ,hl,i(L)]T, can be expressed as

hl,i = hl,i—l + Ahjfl', (2.18)

21

where Ah” is the deviation from the channel coefficient hl’i__1. If we assume user v

is the user whose channel undergoes abrupt changes at time i, then

|lAhv,z'|| >> llAhm'll, for l 75 v. (2-19)

 

where ”Aha“ = \/ 21:0 IAhz’i(k)|2. In the extreme case when the channels are
invariant, ”Aha” = 0.
The channel response of user 1 in the frequency domain is then given by

9

= Hl,i—1 + AH”, 1 S 1 S K, (230)

where AH” is the frequency response of Ahf‘i = [Athi’ON— L_1]T. According to
Parseval’s Theorem, it is also true that IIAHW-II >> llAngll, for l 7e v.
At the receiver end, if it is noiseless, after passing the FFT demodulator, the

overall signal at subcarrier n is given by

K
min) = Z Hl,i(")$l,i(n)a (2.21)
l=1

where flu-(n) and mj,i(n) denote the channel coefficient and the transmitted signal
on subcarrier n, respectively.
Following the PIC procedure, after the cancelation of the reconstructed MAI, the

“cleaner” signal for user I, le-(n), is given by

311,4") = M”) - Z Hj,i—1(n)57j,i(”)v (232)
j?“

where Hj,,~_1(n) and :Ej,,-(n) are the estimates of H j,,-_1(n) and syn-(n), respectively.

If the estimates are error-free, i.e., stj,,-(n) = rj,,-(n) and Hj,,-_1(n) = Hj,,-_1(n), then

me.) = llj,,-(n.):rj,,-(n) + Z Amy-(1015,00. (2.23)
#1

22

The estimate of the channel coefficient at time i is then given by
yl,i(n)
1‘1, if")

)9: (n)
H,,-(n )+§AHJ-,(n )rr:_::—(n)' (2.24)
.7

HM”) =

If I = v, then AHj,,t(n) z 0 for any j 75 1 since there are no abrupt changes in these
channels by assumption. As a result, the second term on the right—hand side of (2.24)

is approximately 0, and we obtain

A

 

 

 

Hv,i(n) z Hv,i(n) = Hui—101)+ AHv,i(n)' (2'25)
Ifl gé v,
H _ . $v,i(n) _ ' $j,i(n)
l,i(n) " Hl,i(n) + AHv,i(n) . + Z AH],t(n) .
$1,201) #1,” 551,101)
e H1201 ) + AH. .(n )ijfz)’ . (2.26)

Since we utilize constant envelope modulation such as BPSK or QPSK, (2.26) can be

rewritten as

Him) z Hz,i(n)+ej6‘”(n)AHv,i(n)
z Hz,.-_1(n)+ejalvlnlAHv,.-(n). taév, (2.27)

where 01,,(n) is the phase difference between arm-(n) and :rw-(n). Horn (2.25) and
(2.27), it is clear that for any I (1 g l S K),

muff") — Hl,i—1(n)l z lAHv,i(n)l- (238)

That is, when one user’s channel is subjected to a sudden change, the channel esti-
mates of all other users present a similar abrupt deviation. This finding leads to the

following algorithm.

23

Proposition 2.1 An abrupt channel change is considered to have occurred at time

instant i, if any one of the following K inequalities holds:

7v' 1N: |H,,-(n)— —1ir,,,-_1(n)|2 > A, 1 g l s K, (2.29)
n=0

where /\ is a “toleration threshold” which satisfies

N-l N—l
1 1
max{— E : (Aim-(nu?) < .\ < — E 3 (611,471))? (2.30)
laév ":0 N ”:0

Justified by Parseval’s Theorem, in practice, the algorithm can be carried out
in the time domain. The “toleration threshold” A is obtained through a recursive
process. Assuming the abrupt change occurs at time i, it can be detected if any one

of the following inequalities holds:

L
1 . . . . ,
L +, Zlhz,i(1)- new)? > A0), 1 _<_ z s K, (2.31)
i=0

where /\(i) is recursively obtained by
A0) = max{—— L +Z|h1u 10)— —izz,.--2(j)l2} + e. (2.32)

When the channels are “smooth”, |h1,,-_1(j) — ill,i_2(j)l2 does not deviate very much

for different i’s. e is a small empirical value larger than such deviation.

2.4.2 Extraction and Tracking of the Abrupt Channel

When the receiver detects the abrupt change at time i, it should identify which user’s

channel is subjected to the change. From (2.10) and (2.25), the channel estimate for

24

A

user v at time i, f1,”- = [hm-(0), - - - hv,,-(L)]T, is given by

flux : [FlL+IHv.i
hat = hv,i—1 + Ahm- (2-33)

I?

Similarly, from (2.10) and (2.27) the channel estimate for user I (94 v) is given by

flu = [FlL+1fil,i
= hl,i—1+Afil,ia (234)

where Ahm- deviates greatly from Ah” due to the phase term ejalvm) in (2.27).

In (2.33), fivn‘ approximates hm' due to the reason that the reconstructed signals
of other users are well approximated. While in (2.34), {hm-J 79 v} deviate from hid
since they are corrupted by the strong interference from user v. It is then natural that
we use fivfi to reconstruct user v’s signal and resort to {file—1: l aé v} to reconstruct
other users’ signals.

If user v has been correctly identified, the “cleaner” signal for user I (1 ;£ v) is

then given by

2,3,0.) = r(iN3 + A, + n) — 2.,(n + A, — A.) — Z 2,-(n + A, - A,), (2.35)
J’s‘hv
where Mn + A; — Av) is the reconstructed signal for user v, being a function of
fiw’ instead of hug-4. Following the analysis in Section 2.4, it can be seen that after
extracting the reconstructed signal of user v, the channel estimate of user l (l 75 v),
fizi, can be given by

hlii 25 hl,i—l + All”. (2.36)

Hence, if user v has been identified correctly and its reconstructed signal using hw-
has been extracted, then III-12’,- - flu--1" z ||Ahj,,-|| is a small value. However, if the
abrupt channel is incorrectly identified to be user k (# v), the channel estimate of

user I (l 75 v, k), Eli, deviates from hl’i_1 significantly because, as shown in (2.34),

25

significant interference is introduced when f1)”- is used to reconstruct the signal of
user k.

Therefore, the value of “hi; — fil,i_1” (1 7t k) is only minimized when the user
who experienced abrupt channel changes is correctly identified, i.e., when k = v. The

algorithm is analytically presented below.

Proposition 2.2 If the abrupt channel change at time instant i has been detected,

user v, whose channel undergoes the abrupt change, can be identified through:

v = arg :31an ”Eli.- — fan—1H}. (2.37)
k 1,4):

wherer={k:1SkSK}.

Remark 2.2 An optimal solution to perform joint abrupt channel identification and

signal detection is given by

(v. {&m,.-}) = arg min {2 ”Eli.- — flu—ill}: (2.38)
kvfld ,7“,

where 9d = {dm,,-|dm,,- E {-1,1}J, 1 S m S K} for BPSK, and 9d = {de-Idmg 6
{i1 :1: j }J , 1 S m S K} for QPSK. The complexity of this optimal algorithm grows
exponentially with the number J K , making it only applicable to some small systems.
However, suboptimal solutions could be found when antenna arrays are employed at
the base station. When the antennas are employed to minimize the channel correlation
between each other, it is then possible to obtain reliable {dm,,-, 1 S m S K} through

the channels over which no abrupt changes occur.

2.5 Simulation Results

In this section, performance of the proposed algorithm is illustrated through simula-
tion examples. In the simulations, QPSK is adopted as the modulation scheme. The

entire channel bandwidth is 8MHz and divided into N = 128 subchannels, which im-

26

plies that the informative part of an MC symbol has a duration of 16us. All channels
are fast-fading, and are characterized using an 8-ray multipath model with exponen-
tial power delay profiles. The extended MC symbol has a CP of lus to eliminate
the 181. The system is quasi-synchronous with the initial transmission delays being
uniformly distributed within [0, 1] ,us. We assume that the carrier frequency is 2GHz,
and the maximum Doppler shift is 200H z, which corresponds to a vehicle speed of
110km / h. For diversity, two receive antennas are employed at the base station. They
are assumed to be far apart enough such that the channels are uncorrelated with each
other. The spreading factor is P = 16 and the system is half loaded with the number

of active users being K = 8.

 

 

 

10° ........................................................... . .......
+ProposedScheme 33
’gj‘fij'ffiILillifijijiiililllilififll +Pilot-aided,33%trainin i:
.. ...... i ............. ....... . —8—-P|CwithKnownChannel..

 

BER

 

 

 

 

Eb/No (dB)

Figure 2.2. BER performance under the Jake’s model with no abrupt changes, K = 8,
P = 16.

27

2.5.1 Performance under the Jakes’ Model with No Abrupt
Changes

Bit error rate (BER) performance of the system under the Jake’s model is illustrated
in Figure 2.2, where no abrupt change is introduced. In this simulation example,
M = P = 16 subcarriers are used for transmitting each user’s pilot bits, K = 8 users
transmit their pilot bits on different subcarriers following the pattern described in Sec-
tion 2.3.1. Only one iteration is performed for channel update. It is found through
simulations that one iteration is good enough to provide near-optimum channel up-
date, and additional iterations can barely improve the system performance. In Figure
2.2, the circled line corresponds to the method using PIC with perfect CSI knowl-
edge, which serves as the benchmark for BER comparison. It is demonstrated that
the proposed scheme approaches the ideal case when SN R increases.

Performance of the pilot-aided scheme is illustrated in Figure 2.2 as well. In the
fast fading environment, the pilot-aided schemes require that the pilots be inserted
frequently to guarantee good performance. In this comparison, the training signals
occupy 33% of the total data length and the linear interpolation technique [CEPBO2]
is exploited for channel interpolation. It is shown that the proposed scheme delivers a
significantly better performance than the pilot-aided schemes when the SNR is larger
than 12 dB. The underlying reason is that the proposed channel update in high SNR
regions becomes more accurate and thus improves the overall system performance.
This argument is further justified by the results shown in Figure 2.3, where the mean-
squared error (MSE) performances of the proposed channel estimation at different
SN R levels are plotted. It is shown that for the SN R at 20dB, the channel estimation
MSE is much smaller than that of the initial estimates, while for the SNR at 12dB,
the MSE is roughly at the same level with the initial estimates.

Figure 2.4 shows the BER performances of the proposed scheme for systems with
imperfect time synchronization. Two scenarios are considered: (i) All users have the
same timing shift, referred to as “common ofiset”; (ii) The users have independent

timing errors uniformly distributed within a certain interval, referred to as “inde-

28

 

0.016 I l I I
0.014 - -
0 012 SNR=12dB

0.01 r -

0.008 - -

0.006 - ‘

Normalized MSE

0004 _ SNR=20dB .

0.002 - 4

 

 

0 1 l 1 I
0 10 20 30 40 50

symbol index

 

Figure 2.3. MSE performances of the proposed channel estimation at different SNR
levels.

29

pendent offsets”. It is observed that the more active users in the system, the more
sensitive the system is to timing errors. As can be seen from Figure 2.4, the half loaded
system works well when the timing error is insignificant. However, as expected, when

timing jitters get worse, performance degradation is no longer negligible.

 

 

 

 

1o ................. ,,
—alr—|ndependentoffsets éiiii???iiiiiiiiiiéiiiiiiiiiiiiiiiiii
—e—Commonoffset,0_25ps :§:::::::::::::l:l:l:::.:::::l:::::::

10-2 +C°mmon°fiset'°-125llséésziéiézaéééiéfiézzjézééééiéiéiééiisg
*B—Perfectlysynchronized iiiiiiéiiiiiiiiiiiigiiiéiiééiii:ziéii

 

 

....................................................................

.....................................................................
....................................................................
.......................................

..................................................................

.................................................................

E
8

...................................................................
....................................................................
....................................................................

............

 

10-6r.if33335if:33if}Eifjé‘ffff535335E555}:EEEEESSEEEESEEEE553333533323535353
;;;:;:;;;;;;:;.-:eé?:i:s252235:52:35s:33223225333232222522152sizassazsszzssa
I22/35.“:Ill:iiiiliiiiiilUNIX:i.1}::::.:::::::::..Z::::31:31::
10-7 1 1 1
4 5 6 7 8

number of users

Figure 2.4. Impact of timing errors on the BER performance, SN R = 25dB: indepen-
dent offsets means that users have independent timing errors uniformly distributed
within interval [0, 0.25]us, common offsets means that all users experience the same
timing shift.

2.5.2 Performance under the Jakes’ Model with Abrupt
Changes

In the case when abrupt changes occur, significant performance degradation could

happen due to error propagation. Therefore, special efforts need to be taken to track

30

these unpredictable changes. In the simulation example, we introduce the abrupt

change based on the following model:

gv,i = 5th,”: + Wv,ia (2'39)

where hvn' is user v’s channel response at time instant i. It is generated from the
Jakes’ model and is normalized with E[||h,,,,-||2] = 1. gm- is the new channel response
with the abrupt change introduced by 6: and WW, where 5: = diag(a). oz and Wm
are two (L + 1) x 1 complex Gaussian vector with zero mean and covariance matrices
of 0311,.” and 03,1 L+1r respectively.

In the simulations, we assume that the channels are uncorrelated. User 1 under-
goes abrupt channel changes at the first receiver antenna, while the channel at the
second antenna is “smooth”. Hence the detected signal at the second antenna can
assist the channel update procedure at the first antenna. Specifically, the parameters
for the abrupt channel model introduced above are of, = 0.06 and 0,2,, = 0.5. The
channels of the other users are assumed to be “smooth”. Under the above settings, the
abrupt channel can be successfully detected with the value of e in (2.32) empirically
set to be 0.2.

Suppose the system is half loaded with K = 8. By varying k from 1 to K in
(2.37), we have different evaluation of the term ¢k = 2,7,), “hf, — flu-4”, which
corresponds to the accumulated channel deviation when user k is identified to be
subjected to abrupt channel changes. It is shown in Figure 2.5 that 4’]: is minimized
when k = v = 1, i.e., when the right user has been identified. Only results of 4 out
of 8 users are presented, and the rest of the “smooth” users are omitted for clearer
illustration.

In the simulation example, it has been assumed that a burst of abrupt changes
appear in user 1’s channel. As can be seen from Figure 2.6, accuracy of channel
estimation is greatly improved after the abrupt channel is correctly identified. It
is shown in Figure 2.7 that with effective abrupt channel tracking, disastrous error

propagation is avoided, and the signal detection performance (BER) in systems with

31

 

0.14 l l I l l
k=1. channel of user 1 changes abruptly
— — k=2. channel of user 1 changes abruptly
o_12 — —*— k=3, channel of user 1 changes abruptly —
k=4, channel of user 1 changes abruptly l

\ fl
l l

 

 

 

 

 

 

 

 

 

0 1 ~ I ‘ l| -
C - l l
.9 A ll 1
o-t \ |
.91 \ . I
5 0.08 ~ ~’ ’
“D l \ , 1 l
l\/
8 6-“ l , . /
E l \ \, ‘ I
3 0.06 — r-
g k\ \I / N ’ \
\

s . /
< \

0.04 - -

0.02 - l

o I l l l l
0 5 10 15 20 25 30
number of runs

Figure 2.5. Accumulated channel deviation 45k when user k (k = 1, 2, 3, 4) is identified
to be subjected to abrupt channel changes, while user 1 is the true user whose channel
undergoes abrupt changes and other users’ channels are “smooth”. K = 8, P = 16.

32

 

1.5 a fi .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

' true channel 0 2 , true channel
1 + estimated channel , ' estimated channel
g g 0.1 ’ 1
0.5 ’ 4d .
B 1! iv . W . . . ‘5 ‘1 .
t o A 'l Vm‘. 5M p t o ‘5‘ N y A !/*\‘ h 1 f '
§ . i l S l “A”? T’W‘ift~fi sci—Labs”
-0.5 r i ii
- -0.2*
_1 I ‘ . . 1 1
0 10 20 30 40 0 10 20 30 40
symbol index of user 1 symbol index of user 2
0.4 - -0.1 $ - . .
~—- true channel 1‘ \ —— true channel
0 3 "*4"— estimated channel 73325 '0-15 ' -- ~r—~ estimated channel
.. - t x’
o 1' (3.6; 3
g f)“ )4 f E
‘5 0'2 ' /i f ‘3 p. .
6 . . 6 "t. a:
t _. 1}./3" t W ‘1, 1,
3 0.1 t , ’5‘; ii a \lV/ g": 1
'5 fly 3 -0 35- i l\*&\P i
e %"i ‘ - l l K‘ ‘V
0 V" I), i» ‘ \‘f N/ x,"
‘t -0.4 r ‘ ~ l
-0.1 ‘ ‘ ‘ -O.45 * ‘ ‘
0 10 20 30 40 0 10 20 30 40
symbol index of user 3 symbol index of user 4

Figure 2.6. Channel estimates (only real part of the channel is shown) with the
proposed error propagation control: SN R = 20dB, K = 8, P = 16, user 1 undergoes
abrupt channel changes. Only results of 4 out of 8 users are presented.

33

 

 

 
 
 

 

 

10 " -O- Proposedscheme.withabruptchanges
d -------- . ------- . ------- ——9— Proposed scheme. no abrupt changes
, —A— Perfect CSI knowledge, with abrupt changes
1 ------- """ -——-—i- - Perfect CSI knowledge, no aerpt changes
10 ::::::::I:::::::'.':::::::.~\zz::I:::::::i:::::::I:::::::5:::::::l:::::::'.'::::::1

10'

BER

........................................................................

 

 

 

10'3
i g >
........................................ - ‘ El
10.4 1 1 1 1 1 1 1 1 1 NIT
5 6 7 8 9 10 11 12 13 14 15
Eb/N0(dB)

Figure 2.7. BER performances of the system over channels with and without abrupt
changes. Here “perfect CSI” means that the channel state information is perfectly
known at the receiver, including information on abrupt changes.

34

abrupt changes is comparable with that of systems with no abrupt changes.

2.6 Summary

In this chapter, a recursive approach is proposed for joint channel estimation and sig—
nal detection of quasi-synchronous MC—CDMA systems over time-varying channels.
Only one pilot symbol is needed for initial channel estimation. Subsequent signal de-
tection and channel update are carried out by exploiting the channel information from
the previous symbol. The proposed scheme hence possesses much higher spectral effi-
ciency than conventional pilot-aided methods. Furthermore, for channels subjected to
unpredictably sudden changes, effective abrupt channel tracking algorithms have been
proposed to ensure tight error propagation control. Simulation results demonstrated

the effectiveness and robustness of the proposed algorithms.

35

CHAPTER 3

Mutually Interactive Random
Access Control for Wireless

Networks

This chapter considers cross-layer medium access control (MAC) protocol design in
wireless networks. Taking a mutually interactive MAC-PHY perspective, we aim to
design an MAC protocol that is in favor of the PHY layer information transmission,
and the improved PHY, in turn, can improve the MAC performance. Motivated by
the fact that as long as good channel estimation can be achieved, advanced signal pro-
cessing does allow effective signal separation given that the multiuser interference is
limited to a certain degree, we propose a novel MAC protocol, named hybrid ALOHA,
which allows conditional collision-free channel estimation and simultaneous multiuser
transmission. More specifically, short idle sections are introduced into the structure of
the traditional ALOHA slot, so that it is possible for different users to transmit their
training sequences in non-overlapping training slots, whereby collision-free channel
estimation could be achieved. Relying on the general multipacket reception (MPR)
model, quantitative analysis is conducted for the proposed hybrid ALOHA protocol
in terms of throughput, stability as well as delay behavior. Significant performance
improvement can be achieved in comparison with the traditional ALOHA protocol

based either on the collision model or the MPR model.

36

3.1 Introduction

Over the past decades, studies on medium access control (MAC) have largely relied
on the “collision” model: a packet is successfully received if and only if there are no
concurrent transmissions [Rob72, Gal85, EH98]. MAC protocols such as traditional
ALOHA [Abr70,Rob72], the tree algorithms [Cap79], the window random-access al-
gorithm [PPK89] and a number of adaptive MAC schemes [HG81,H1u82,KY78], have
all been developed by assuming that the physical (PHY) layer is characterized as an
idealized collision model [ZT03b]. Although it is convenient for analysis, the colli-
sion model fails to represent all the characteristics of the PHY layer. As pointed out
by Tong et al. in [TNV04], the model is optimistic as it ignores the channel effects
such as fading and noise on reception, whereas the model is also pessimistic since it
overlooks the possibility that the packets may be successfully decoded even in the
presence of simultaneous multiuser transmissions.

Going beyond the collision model and assuming a multiuser PHY layer, Ghez,
Verdi’i and Schwartz proposed the multipacket reception (MPR) model in [GV888,
GV889], where the reception of packets is characterized by conditional probabili-
ties instead of deterministic failures or successes. The MPR model provides a more
realistic interface between the PHY layer and the MAC layer, and prepels the re-
search on cross-layer MAC design. In [Met76, RSG87,HK889, Zor95], the impact of
MPR on the performance of slotted ALOHA is studied by investigating the capture
model, which, being a subclass of the MPR, assumes that at most one user’s packet
can be successfully decoded when multiple users transmit at the same time. More
examples on protocol design for networks in the presence of capture can be found
in [LPK89,YD00,AD01,SC85]. Based on the general MPR model beyond the cap-
ture channel, in [ZT03b] and [ZT03a], a multi-queue service room (MQSR) protocol
and a simpler dynamic queue protocol have been developed to adaptively grant chan-
nel access to users, respectively.

One limitation with the MPR model of Ghez et a1. is that it assumes a sym-

metric model with indistinguishable users. To differentiate users in a multimedia

37

networks where each user may have his own rate, in [N MT05], N aware, Mergen and
Tong introduced a more general, asymmetric MPR model as the interfaces between
the MAC layer and the PHY layer. Based on the generalized MPR model, their
study [N MT05] on the stability and delay of slotted ALOHA leads to an interesting
result: if the PH Y layer is reasonably reliable, then slotted ALOHA with transmission
probability 1 is optimal in the sense that the stability region coincides with the MAC
capacity region. Hence, there is no need for sophisticated MAC protocols when the
optimality is achieved. Here, the MAC capacity region is defined as the maximum
throughput achievable by any MAC protocols without considering queue stability
[GT02, MT05,NMT05]. The stability region of a particular MAC protocol is defined
to be the set of arrival rates for which there exists retransmission probabilities that
make the probability of buffer overflow arbitrarily small [Szp94, LE99,NMT05]. Gen-
erally, the stability region is contained in the capacity region. The result in [NMT05]
implies that the burden at the MAC layer can be reduced significantly if we can
ensure a reasonably good PHY layer.

As is well known, being an important characteristic that directly influences the
quality of the PHY layer, the channel state information (CSI) plays a critical role
in signal detection and estimation. The more accurate the CSI estimation is, the
more likely that the signal can be recovered at the receiver, and hence the stronger
the MPR capability. There has been a line of work studying the effect of CSI on
resource allocation, e.g., [AT05,TH98,SV01,TE93]. Assumptions are usually made
that either transmitters or receivers can track the channel state, and the knowledge
of such information is employed to improve the network capacity. In other words,
existing works have been focused on improving the MAC performance by exploiting
the PHY layer transmission capability. Here, we turn to examine the effect of the
MAC protocol design on the PHY layer performance, and study how the mutual
MAC-PHY interaction will influence the overall system capacity. More specifically,
as illustrated in Figure 3.1, taking a mutually interactive MAC-PH Y perspective,
we aim to design an MAC protocol that is in favor of the PH Y layer information

transmission, and the improved PH Y layer, in turn, can improve the performance in

38

the sense of throughput, stability and delay.

 

MAC Layer

 

Performance
Optimization

 

PHY Layer

 

Figure 3.1. Mutual interaction of MAC layer and PHY layer to achieve performance
optimization.

In this chapter, we propose a hybrid ALOHA random access protocol which
makes collision-free channel estimation possible and allows simultaneous multiuser
data transmission, based on the fact that as long as good channel estimation can
be achieved, advanced signal processing does allow effective signal separation given
that the multiuser interference is limited to a certain degree. In the hybrid ALOHA
protocol, idle sections are inserted to each slot to make it possible for different users
to transmit their training sequences at nonoverlapping sub-slots, therefore allowing
collision-free channel estimation.

The hybrid ALOHA protocol is evaluated in terms of throughput, stability and

delay behaviors. The major results are outlined as follows:

0 Throughput Hybrid ALOHA allows conditional simultaneous transmission.
Depending on whether the training sequences collide or not, the quality of CSI
estimation varies, resulting in varying MPR capabilities. Relying on the exis-
tence of collision-free channel estimation, the increased MPR capability com-

pensates for the bandwidth cost of the idle sections in the protocol and leads

39

to significant improvement in the system throughput.

Stability region We characterize the stability region for the two-user system
and derive the sufficient condition for the stability of the general finite-user
system. Stability inner bound for the special three-user system is also charac-
terized, which turns out to be solving a Riemann-Hilbert Problem. Study in
the two-user case shows that when the MPR capability reaches a certain critical
level, hybrid ALOHA has a convex stability region identical to that of a TDMA
scheme, which possesses a frame guard time of the same length with the idle sec-
tion of hybrid ALOHA. In the cases when the MPR capabilities are beyond the
critical level, hybrid ALOHA outperforms TDMA by containing the stability
region of the latter as a subset. The convexity of the stability region shows the

optimality of the protocol in terms of its coincidence with the capacity region.

Delay behavior Based on the general MPR model, we study the delay perfor-
mance for the two—user system. The “exact” delays for the asymmetric system,
and the upper and lower bounds of the average delay for the symmetric case
are derived. It is shown that in the circumstances when the MPR channels are
sufficiently strong, the difference between the upper and lower bounds becomes
trivial and the actual delay can be roughly determined. When the MPR model
is reduced to the capture model, the two bounds merge and we obtain the exact

delay, which coincides with the result of [N MT05].

The rest of the chapter is organized as follows. In Section 3.2 the system model and

the proposed hybrid ALOHA protocol are presented. In Section 3.3, the throughput

of the system is analyzed. In Section 3.4 the stability region is derived for the two-

user case. In addition, the suflicient condition for stability is derived for the general

finite-user system. Section 3.5 studies exclusively the stability inner bound of the

specific three-user system. The solution is found to be that of a Riemann-Hilbert

boundary value problem. The delay behavior is studied in Section 3.6. To provide

in-depth insights into the problem, an illustrative example is presented in Section 3.7.

We conclude in Section 3.8.

40

3.2 The Hybrid ALOHA Protocol

3.2.1 System Model

Consider a wireless network with a set N of users, N = {1,2, - - - , N}, communicating
with a common access point. Each user is equipped with an infinite buffer for storing
arriving and backlogged packets. The packet arrival processes are assumed to be
independent from user to user. The channel is slotted in time, with slot period
larger than the packet length. When the buffer of the ith (i E N) user is nonempty,
he tosses a coin to determine whether to transmit in the current slot or not. The
probability of transmission of the ith user at each slot is assumed to be p,. Packets
are assumed to be of equal size for all users and composed of two parts: the first part
is the training sequence for channel estimation, and the second part is the information
data. The length of the training sequence is typically much smaller than that of the
information data. The arrivals of the ith user are assumed to be independent and
identically distributed (i.i.d) Bernoulli random variables from slot to slot, with the
average number of arrivals being A, packets per slot. If this arrival rate is measured
in packets per unit time, we then use A,- to denote it. Throughout the paper, we use
the slot length of traditional ALOHA as the reference time unit and denote it as 1.
Note that the slot length is protocol-dependent and may not always be 1.

We adopt the general MPR model in [N MT05] where the multiuser PHY layer is
characterized by a set of conditional probabilities. For any subset S Q N of users
transmitting in a slot, the marginal probability of successfully receiving packets from

users in R Q 8, given that users in S transmit, is defined as

(IRIS: 2 gas (3-1)
UfRQUQS

where guy; is the conditional probability of reception defined as

(121,8 = Pr{only packets from U are successfully received I users in S transmit}, Ll Q S.

(3.2)

41

In the two-user case, for example, N = {1,2}, for i = 1, 2,

in} = Pr{user i is successful I only user i transmits},
qu} = Pr{user i is successful I both users transmit},
q{1,2},{1,2} = Pr{both users are successful | both users transmit} (3.3)

and the marginal probabilities

this} = qty}, qi|{1,2} = qi,{1,2} + Q{1,2},{1,2}- (34)

Clearly, (IRIS depends on the quality of the PHY layer.

Assume that at the end of each slot, the receiver gives an instantaneous feedback
of all the packets that were successfully received to all the users. The users remove
successful packets from their buffers while unsuccessful packets are retained. Let Nit
denote the queue length of the ith user at the beginning of time slot t, the queue
evolution function for the ith (i E {1,2, - - - ,N}) queue is given by [Szp94,NMT05]

1v,t+1 = [N,t — Y,‘]+ + flf. (3-5)

where 6: is the number of arrivals during the ith slot to the ith user with E (Bf) =
A,- < 00, Y: is the Bernoulli random variable denoting the number of departures from

queue i in time slot t, and [:r]+ = max(0,:r).

3.2.2 Hybrid ALOHA

The proposed hybrid ALOHA protocol aims at improving MPR capability by allowing
conditional collision-free channel estimation and simultaneous transmission. In hybrid
ALOHA, each slot contains sub-slots including training sections, data sections and idle
sections. Idle sections are introduced to make it possible for different users to transmit
their training sequences at non-overlapping sub-slots, whereby collision-free channel

estimation could be achieved. We assume that the physical layer can accommodate

42

M users, that is, given reasonably accurate channel estimation, the user’s packet can
be successfully decoded if and only if there are no more than M simultaneous users.
In hybrid ALOHA, M — 1 idle sections are inserted to each traditional ALOHA slot,
such that collision-free channel estimation is made possible for each user. Note that
in the proposed hybrid ALOHA, each slot has multiple pilot sub-slots, and each user

can randomly select a pilot sub-slot to transmit his training sequence.

 

 

 

 

 

 

 

 

Training Idle Information Data User 1
Idle Training lnforrnation Data User 2
«—— T —><—— 2' >4 1-2' 4,

 

 

Figure 3.2. Illustration of the hybrid ALOHA slot structure for M = 2, in the case
that two users (N = 2) transmit their training sequences at non-overlapping pilot
sub-slots.

Figure 3.2 illustrates the slot structure of hybrid ALOHA in the case of M = 2, i.e.,
successful transmission is possible only when there are no more than two simultaneous
users. Each slot has M + 1 = 3 sub-slots. The preceding two sub—slots, each having
a length of r, are the “pilot sub-slots” reserved for training sequences. When a user
is involved in a transmission, we assume that the selection of the pilot sub-slots is
of equal probability. The information data is always transmitted in the last sub—slot
referred to as the “data sub-slot”. We assume that the length of the data sub-slot is
1 — r with r << 1. Recall that the length of the traditional ALOHA slot is used as
the reference time unit, denoted as 1, which consists of a training sub-slot of length

r and a data sub—slot of length 1 — r.

3.3 Throughput Calculation

As a figure of merit, the throughput of the system, which is a function of r and

denoted here as u(r), is calculated below. The throughput is determined by finding

43

the average traffic successfully getting through the channel, i.e., E [T t], where E [] is
the expectation operator and T, denotes the number of packets successfully getting
through the channel during slot t. Let A be the overall arrival rate to the system, in
the unit of number of packets per unit time. The average traffic per slot is R(r) =
A(Mr + 1 — r). Let A5 be the event that users in 8 transmit, and A? the event that
only users in R succeed given that users in S transmit. The throughput for a general

MPR model is given by

12(7)

’3th]

= Z EthlAsl - Pr{As}
SEN

Z Z E[T,|A§] - Pr{Ajg} - Pr{AS}
SSA/RES

= Z Z defies-ems}. (36>

SEN RES

Here IR] and I8] denote the number of elements in sets R and 8 respectively, and it
follows from equation (3.2) Pr{Azgz} = 911,19

For the symmetric MPR model where users are indistinguishable, a more tractable
form can be obtained. Denote A K as the event that K users transmit in one slot and

denote A} as the event that exactly i out of K users succeed in transmission, then

11(7) = Ethl
M
= ZEthl/IKI‘PTMK}
K=1
M K i .
= H(r)ZZR—Pr{A‘K|AK}Pr{AK}, (3.7)
K=1i=1

where Pr{AjKIAK} is determined by the MPR capability of the system, whereas
Pr{AK} relies on the packet arrival model. We have assumed that the packet ar-
rivals for the users follow the Bernoulli processes, and the overall arrival rate is A. If

the number of users in the system is sufficiently large, the binomial distribution can

44

be closely approximated using the Poisson distribution [Fis63]. The closed-form ex-
pression of Pr{AK} can be obtained by assuming that the packets arrival follows the
Poisson distribution with parameter 12(7) 2 MM 7+ 1 —- 7). The result is summarized

in the following prOposition.

Proposition 3.1 Under the symmetric MPR model, as well as the Poisson approxi-
mation with parameter 12(7) 2 A(M 7+ 1 — 7), the throughput 11(7) of hybrid ALOHA,
measured in packets per hybrid ALOHA slot, is given by

M K i _ R(T)K—le-—R(7)
11(7) = [2(7) 2 ZRPflAzKlAK} (K _1)! . (3.8)
K=l i=1

 

To further simplify the expression of V(T), we assume that users colliding in pilot sub-
slots fail in transmission, whereas those who have collision-free channel estimation
survive, given that there are no more than M users transmitting simultaneously in
one slot. This simplified model is called the Simplistic Assumption. Evaluation of
the throughput under this assumption is carried out in the following. When M = 1,
Eq. (3.8) results in 11(7) = R(7)e‘R(T), which corresponds to the traditional slotted
ALOHA system. For M = 2, assuming users are symmetric, it is then easy to know

that Pr{A]|A1} = 1, Pr{AyAg} = 0 and Pr{AglAg} = 1/2. Thus,

12(7) = 3(7)]e-RIT1Pr—{AflA1}+n(r)s-R(Tl(—;~Pr{A§|A2}+Pr{Angzn]
= [R(r)2/2+R(r)le"R(”- (39)

Similarly, when M = 3, we have u(7) = R(7)e"R(T) [1 + §R(7) + §R(7)2].

An alternative proof for the M = 2 case is provided in Appendix A, where we
calculate the throughput of the system based on the Bernoulli arrivals model. The
result coincides with that in (3.9) and demonstrates the validity of the Poisson ap-

proximation in Proposition 3.1.

Remark 3.1 Clearly, the throughput of the system is a function of 7. Increasing

7 allows a longer training sequence, hereby resulting in better channel estimation.

45

More specifically, as will be shown in Section 3. 7, the mean-squared error of channel
estimation is inversely proportional to 7. Hence, increasing 7 will result in improved
MPR capability, which is desirable to improve the overall system performance. On the
other hand, however, a larger 7 also implies longer idle periods, leading to spectral
inefl‘iciency. Therefore, a tradeoff should be made on the design of 7 for different

applications. Please refer to Section 3.7 for a specific example.

Figure 3.3 presents the throughput comparison of the schemes for M = 1, 2, 3,
respectively. Here we choose 7 = 0.05. The reference time unit is 1, which is the length
of one slot in the case of M = 1, corresponding to the traditional ALOHA scheme.
Note that in Proposition 1, the throughput is measured in the unit of “packets” per
“hybrid ALOHA slot”, with slot length [1 + (M — 1)7]. For throughput comparison
with traditional ALOHA, we need to normalize the throughput of hybrid ALOHA
by the slot length. In other words, the throughput is normalized to “number of
packets per unit-time”, which is 11(7) / [1 + (M — 1)7]. It is shown that when M = 2,
the proposed scheme has a 46% gain over traditional ALOHA (M = 1) in terms
of maximum throughput, and the gain doubles for the M = 3 case. That is, the
throughput tends to increase as M increases. At the point where the maximum
throughput is achieved, the proposed protocol has an expected number of attempting
transmissions approximately 1.4 and 1.95 for M = 2 and M = 3, respectively, much
larger than that of traditional slotted ALOHA which takes on the value 1. This
can be intuitively understood as: the larger the value of M, the stronger the MPR
capability. As will be seen in Section 3.7, due to the small length of 7, the cost of
extra bandwidth can be compensated for by the improved MPR capability.

Without loss of generality, in what follows, the stability regions and the delay
performance of the hybrid ALOHA system are derived for the specific case of M = 2,
that is, at most two simultaneous users can transmit in one slot in order for successful

reception.

46

 

  
 
 

-— Hybrid ALOHA, M=3
- - ' - ' Hybrid ALOHA, M=2
- - - Traditional ALOHA, M=1

.0
N
I

 

 

 

0.4

Throughput (packets/unit time)

 

 

 

O
.—
1-
i-
h-
i—

Attempting rate R(‘t)

Figure 3.3. Throughput comparison between hybrid ALOHA and traditional slotted
ALOHA.

47

3.4 Stability of Hybrid ALOHA

We study the stability performance of hybrid ALOHA in this section.

Definition 3.1 [Szp94] A multidimensional stochastic process Nt = (Nf, - -- ,va)
is said to be stable if for x E NN the following holds

lim Pr{Nt < x} = F(x) and lim F(x) = 1, (3.10)
t—ioo X-*OO

where F (x) is the limiting distribution function.

For an N -user slotted ALOHA system, the stability region (6 ALOHA) is defined
as the set of arrival rate A = [A1, A2, - -- ,AN] for which there exists a transmission
probability vector p = [p1,p2, - - . , p N] such that the queues in the system are stable.
In literature, studies on the stability conditions of ALOHA systems were mainly
based on the collision model, see [TM79, RE88, Ana91, Szp94, LE99], for example.
In [NMT05], the stability analysis of slotted ALOHA based on the general MPR
model is investigated. In this section, under the Simplistic Assumption, we first
analyze the stability region of hybrid ALOHA for the two-user case and then derive
the sufficient condition for stability of hybrid ALOHA in the case of N > 2.

3.4.1 Stability Region for N = 2

When N = 2, suppose the arrival rates for the two users are A1 and A2 (packets per
slot), and their transmission probabilities are p1 and p2, respectively. We have the

following result.

Lemma 3.1 Under the Simplistic Assumption, for a fixed transmission probability

vector p = [p1, p2], the stability region of hybrid ALOHA is given by

 

 

A
*1 S P1 - 212131. for *2 S P2 - P1P2/2a (3-11)
and
A
A2 S P2 — 2p: 1 i for AI S p1 - P1P2/2i (3'12)

48

where A1 and A2 are the arrival rates for the two users in the unit of packets per slot.

Proof: Please referred to Appendix B.
Let 6 H— A L0 H A(p) be the stability region of hybrid ALOHA for a fixed p, then
the overall stability region of hybrid ALOHA can be characterized as

GH—ALOHA= U 5H-AL0HA(P)~ (3-13)
p6[0,l]N

By taking the closure of all the regions as p varies over [0,1]2, we can obtain the
stability region of the proposed scheme. In [N MT05], an alternative approach is
used to find the stability region by solving a corresponding constrained optimization

problem. The approach is adopted here to obtain the following result.

Proposition 3.2 Under the Simplistic Assumption, the stability region of hybrid
ALOHA coincides with that of TDMA and is characterized by the region below

GH—ALOHA = {(AitA2) I (Alt/\2) .>. (0.0),(A1J2) lies below the “”6
A1+ 1;, =1, 0 g A, 31}, (3.14)

where A1 and A2 are the arrival rates for the two users in the unit of packets per slot.

Proof: Please refer to Appendix C.

Recall that in this chapter, the length of the traditional ALOHA slot is assumed
to be 1. Due to insertion of the idle sections, the slot length in hybrid ALOHA is
larger than 1. For fair comparison, let A,- denote the number of arrivals per unit
time when the arrival rate for user i is A,- packets per hybrid ALOHA slot, that is,
A,- = Ai[1 + (M — 1)7]. Figure 3.4 portrays the stability regions of four different
protocols in the two—user case. The stability region for hybrid ALOHA is bounded
by the curve A1 + A2 = 1/(1 + 7). In other words, the maximum arrival rate for each
user is limited by 1/(1 +7). This can be understood in the extreme case when there is

only one user transmitting. In this circumstance the maximum stable arrival rate is

49

A2 (packets/unit time)

Figure 3.4. Stability regions for different protocols in the two-user case.

0.9

0.8

0.7 -

0.6

0.5 ~

0.4 -

0.3 r

0.2 r

0.1 -

 

   
  
 

 

TDMA without guard time

\> / A1+A2=1

Hybrid ALOHA, or
TDMA with guard time i

A1+A2=1/(1 +1)

Traditional
\/ ALOHA \ - \
A11/2+A21/2_1

 

 

0.2 0.4 0.6 0.8
A1 (packets/unit time)

50

 

one packet per slot, corresponding to 1/ (1 + 7) packets per unit time. It can be seen
that the stability region of hybrid ALOHA is identical to that of the TDMA protocol
where a guard time of 7 is present, and contains the stability region of traditional
ALOHA as a subset except in the extreme case when only one user transmits.

A heuristic explanation to the stability coincidence of the hybrid ALOHA protocol
and the TDMA protocol with guard times is that for hybrid ALOHA, under the Sim-
plistic Assumption, the probability for both two simultaneous users to be successful
is 1 / 2, since the chance that their training sequences are transmitted in two different
pilot sub-slots is 50%. Such time multiplexing feature produces the same effect as
TDMA in terms of stability.

The capacity region of a system is defined as follows.

Definition 3.2 [NM T05] Capacity region is the closure of the set of all achievable
rates, where a rate A = (A1, - ~ ,AN) is called achievable if there exists a scheduling
policy (3*) with delivery rate greater than A, i.e.,

T—ioo

T—l
lim infl 2: 1(16 RS*(t)) 2 A5 V1 (1.8. (3.15)
T t=0

where R3(t) is the set of successful transmissions when the set of users 83(t) transmit
in slot t under scheduling policy S. Capacity region (6) is the closure of the set of

all achievable rates.

If we define 6 as the union of the stability regions over all MAC protocols, then
6 provides the set of stable arrival rates with all MAC protocols. Generally, 6 Q Q:
[VNT04], and then we have the relation: 6 H .11 L0 H A C; 6 Q Qt. However, it has been
proved in [NMT05] that when the MPR capacity of an MAC protocol reaches a critical
level such that its stability region becomes convex, then the stability region coincides
with the capacity region. As pointed out in [TNV04], the capacity defined here
mimics the Shannon capacity limit, but is bounded by straight lines since successful

transmission is measured in the unit of packets instead of bits.

Remark 3.2 The result in Proposition 3.2 states that under the Simplistic As-

51

sumption, the MPR capability of hybrid ALOHA reaches a critical level that makes
the stability region 6 H .ALOH A convex. Following the above discussion, we have
6 H _ALOH A = 6 = Q. This implies that under the Simplistic Assumption, hybrid
ALOHA is optimal in the sense that it can stabilize all rates that can be stabilized
by any centralized or decentralized MAC protocols. The optimality is achieved with
the transmission probabilities p = [1, 1], that is, both users always transmit packets if
their queues are not empty, and no transmission control is required. This can be seen
by letting p = [1, l] in Lemma 3.1, where the resultant stability region coincides with

the result given in Proposition 3.2.

Remark 3.3 Beyond the Simplistic Assumption, in the case when the collision of
the training sequences does not necessarily lead to reception failure(s), stronger MPR
capability could be achieved. The convexity of the stability region remains and hybrid
ALOHA can outperform the TDMA scheme. More details can be found in Section
3. 7.

For the general reception model, the stability of slotted ALOHA is derived in
[N MT05] using the marginal probabilities of success. Similar derivations apply to the
proposed hybrid ALOHA, resulting in the same result as in [N MT05], which is stated

below.

Proposition 3.3 If Q1 = q1|{1} - q1|{1,2} Z 0 and Q2 = q2|{2} — q2|{1’2} Z 0,
then the stability region of hybrid ALOHA for the general reception model is given by
61 n 62 where

61 = {(A1,/\2) : (A1,/\2) 2 (0,0), (A1,/\2) lies below the curve
A2 = f()\1; €11|{1}.qz|{2}.Q1.Qz)}, (316)

and

62 = {(A1,z\2) : (A1,/\2) 2 (0,0), (A1,/\2) lies below the curve
/\1 = f(/\2; 42|{2},q1|{1},Q2.QI)}, (3-17)

52

where

. (5 fl _ 633.347» ’\ E II!
f(’\a arfir 79 ) = £m_m22 A 6 1'2 (3.18)
'7 ’ °
with 2 2
11 = [0, W] and 12 = [Eggs—7L, 36g]. (3.19)

If either Q1 or Q2 equals zero, then we assume (I) = 00 and the result still holds.

Proof: Please refer to [N MT05].

3.4.2 Sufficient Condition of Stability for N > 2

In the case of N > 2, stability regions are difficult to obtain for general ALOHA
systems even under the collision model. However, in literature, stability conditions
for a fixed transmission probability vector p have been developed under various mod-
els. Szpankowski [Szp94] derived a sufficient and necessary condition for stability
of the ALOHA system with the collision model. In [NMT05], Naware, Mergen and
Tong provides the sufficient condition for stability of the ALOHA system under the
generalized MPR model. The stochastic dominance1 [RE88] and the Loynes Theo—
rem [Loy62] were the keys to these derivations, which, associated with the Simplistic
Assumption, are adopted here to derive the sufficient condition for stability of hybrid
ALOHA.

Under the Simplistic Assumption, it is easy to verify that the departure process

Y: in (3.5) can be written as

2
Y.‘ = le—xuzfipluiaj-(l— Z Ric,jX(N1t¢))+
i=1 keN\{j}
-[(2— Z R5,,3x(Nt))+—(1— Z Rt,;x(Nt>)+1}. (3.20)

keN\{j} Ice/WU}

where j is the index of the pilot sub—slot and 5 = {1, 2}\{ j}; pm- is the transmission

 

1A real random variable X is said to stochastically dominate a real random variable Y if V2 6 IR,
Pr{X > z} 2 Pr{Y > z}. This dominance is denoted by X 2“ Y.

53

probability of the training sequence at sub-slot j for user i, hence the transmis-
sion probability of user i in one slot is given by p, = 23:1 1913]" Rid is the i.i.d
Bernoulli(p,-,j) random variable for 1 S i S N, indicating the “coin tossing” out—
comes that determine the transmission attempts. For hybrid ALOHA, since one user
cannot transmit in both pilot sub-slots, R2,}. = 1 - Rio” The function x(k) is defined

as
0, k=0,

1, k>0.

x(k) =

We construct a modified system as follows. Let 'P = {8,11} be a partition of N
such that users in S 75 N work exactly in the same manner as in the original system,
while users in u persistently transmit dummy packets even if their queues are empty.
Users in U are called persistent and those in S nonpersistent. Such modified system
is denoted by GP. Let N3, = (N t ’NltJ) denote the queue lengths in 8‘P and it can
be proved that N3, stochastically dominates N t of the original system provided that
the initial conditions are identical [TM79,Szp86].

By the construction above, the process N3 is an ISI-dimensional Markov chain
that mimics the behavior of the original system. Note that the system consisting of
users in 8 forms a smaller copy of the original system with modified reception prob-
abilities. Generally, for any 8’ Q S and i E 5’, the modified reception probabilities

for the smaller system consisting of the stand-alone nonpersistent set S are given

by [NMT05]

qlls’= XXI-[193' H 13043431”. (3.21)

791 jeT keU\T
Induction arguments can then be applied to establish the stability conditions. We
further assume that the Markov chain Nfs is stationary and ergodic. We denote

the stationary version as N99 to indicate that the process starts from the stationary

distribution.

Let Yit('P) be the departure process from the ith queue in the dominant system

54

87), then we have

2

me) = XII-mime ll 2 RM <Nt>+ Z Rid-=01
j=1keS\{i} keu\{i}
1[ Z Rk .X(N,§)+ 2 £236,331]. (3.22)
k€8\{i} keU\{z‘}

Given that YflP) is stationary, we denote PguccCP) = E {Y} (’P)] the probability of a

successful transmission from the ith user in system 97’, which is given by

Pisa?) = p.- H (l—m.) Z (Pr{x(N*.’s>=zs} H (l—pkrk

keu\{i} 256w 1}|S| keS\{i}

+(Zpij Z [Pkd' H (1 _Pk’)l) '

j=1 keu\{i} k’eu\{i.k}

2 (Pr{X(Ns)=Zs} H (l-Pka)

zS€{0,1}IS| 1668“”
+ H( (1— Pkl(ZPi,j Z Pr{xmg‘) = Zs}'
keu\{i} i=1 236{O,1}l5|
-[ Z 1(2). = 0191.5 H (1 - Pelzk'l)’
keS\{i} k’68\{i,lc}

(3.23)

where mg.) = (x(N‘.-’,),~~ «(Ni-15,) with h. e s for all h = 1.-~ .ISI- The

first term of the right-hand side of (3.23) represents the probability of successful
transmission of user i when no one else transmits. The second and third terms
represent the probabilities of successful transmission of user i when there is another
user involved in transmission. The second term corresponds to the case when the
extra user belongs to U, and the third term corresponds to the case when the extra
user belongs to 8.

Under the partition ’P = (8,11), let 6N and 63 denote the stability regions for

the whole system GP and the system consisting of nonpersistent users 8 , respectively.

55

Define a region

EN = URN = (11,”. ,AN} : Ak < Pfuccw) Vk e u and A5 6 63}, (3.24)
p

then we have the following result.

Proposition 3.4 For a fixed transmission probability vector p, under the Simplistic

Assumption, if AN 6 SN, then the hybrid ALOHA system is stable, i.e., 6N Q

GH-ALOHA(P)-

Proof: Please refer to Appendix D.

In the proof, mathematical induction is used to reduce the dimensionality of the
problem and then the Loynes Theorem is applied to the isolated general queue. For
partition P = {8,11 }, since I8 I < N, by induction A5 6 65 is sufficient for stability
of the system 8. This makes the departure process in 11 stationary and ergodic.
Moreover, by the Loynes Theorem, queues in 11 are stable with Ak < Pfucc(P),Vk E
11. The conditions are then sufficient for 67) to be stable. With the property of the
stochastic dominance of 979 over the original system, the conditions are also sufficient

for hybrid ALOHA to be stable.

3.5 Special Case: Stability Inner Bound for N = 3

3.5.1 Inner Bound Characterization

Recall that P = {8,11} is a partition of N. Consider the three partitions P.- =
{8,11} = {N}, {i}}, where JV,- = N\{i}, i = 1,2,3. Define the other three partitions
P; = {8,11} = {{i},N,-}. From (3.23) it is easy to verify that Pguw(P;) < Pgucc(Pz-)
for any i. Hence it follows from Proposition 3.4 that the stability inner bound R is
the sum of three regions R,- corresponding to P,, i = 1,2, 3, respectively. In what
follows, we inspect in details the region R3 corresponding to P3 = {{1, 2}, {3}}. The

other two regions R1 and R2 can be easily obtained through the similar procedures.

56

27—13:;

 

 

 

Let N: and [3: denote respectively the queue length and the number of arriving
packets of user i (i = 1,2) in time slot t. Let F3(x,y) be the moment generating

function of the joint arrival process for user 1 and 2. Thus, for |x| S 1, |y| S 1, t E N
fit at _ _
F3($.y) = E($ 1y 2) = (M1 + AMI/A2 + *2). (3-25)

where Xi=1— A,, for i = 1,2.

The investigated system model implies that (N t, Né) is an irreducible, aperiodic
Markov chain. Hence the stability of the system is equivalent to existence of a unique
stationary (limiting) distribution. Let G3(x,y) be the moment generating function

of the joint stationary queue process, viz.,
. Nt Nt
G3(x, y) = tllm E(x 1y 2). (3.26)
—+00
In Appendix E we derive the following functional equation:

K(x.y)03(x.y) = a(:r.1/)Gs(0.y) +b($.y)G3(x.0) +C(x.y)03(0.0). (3-27)

 

 

 

 

with
K(1: 1,) = _ 1 _ _ 191132(1 -p3/2) _ 122151(1-p3/2)
' h ($’\1 +_/\1)(1//\2 + *2) x y
_191211253 - [1 - (1 - p3/2)(p1132 + 151122) - 121122133/2]. (3.28)

121192(1- 123/2) + p1132(1- 123/2) _ 121172153
y x 2xy

+1)1(1 - p3/2)(1 - 2P2) + 111192133/2. (3-29)

 

 

0(1. 11) =

 

 

1- 2 ' 1— 2 -
b($.y) _ P1P2( x 193/ )+P2P1( y 193/ )_P121;253

+P2(1 - 193/2)(1 - 2131) + P1P2133/2. (3-30)

57

 

 

 

191112133 _ 191192(1- 193/2) _ 191192(1- 193/2) + 191192(3 - 193)

.1
2xy y x 2 ’(33)

C(917.11) =

In (3.27), taking y = 1, divided by x — 1 and then taking 1' = 1, we have

1
->\1 + 519112 '- (P2 + 193)] =

1
512.12 -(192 +193)le(0.1)- 3153203110) + p—lzfiaaws). (3.32)
Exchanging the roles of x and y and repeating the above operations, we have

I
-)\2 + 519212 — (P1 + 193)] =

1
-EZQG3(0.1)+ 512212 — (m + 1131103110) + Bap-3010.0). (333)

Note that in deriving these equations we exploit the facts that F3(1, 1) = 1 and
)1,- = E(fif) for i = 1,2.

Define P3(z1, 22) i Pr{x(1V1) = 21, x(1\72) = z2} with user 3 being the persistent
one. Then from (E.4)-(E.7) we have

P3(010) = G3(010);

P3010) = G3(1.0)-G:9.(0.0);

P3““) = G3(011)-Ga(0.0);

P3(1,1) = 1+G3(0,0)—G3(0,1)—G3(1,0).

Using these relations and (3.23) and assuming pm- = pi/2 for i = 1,2,3, j = l, 2, we

58

can easily have the following results.

Piucc(P3) = 191133 [1 - (1 - 03(110l192)] + (191,1193,2 + 191,2193,1) [1 - (1 - G3(l.0))192]
+133 [(191,11922 + P1,2P2,1)(P3(011) + P3(1. 0))]

= 191[1- $193 - $192(1- 0301(0)]

19.21.4103) = 12211.1[1 — (1 - 03(o.1)m)] + (12,2131 + 1121131) [1 — (1 - 63(0, 1))11]
+153[(192,1191,2 + 192,2P1,1)(P3(011) + P3(110))]

= 192[1- $193 - $191(1- 03(0.1))]

133.112..) = P3[P3(010)+(1-$P1)P3(110)+(1- $1211.11)

+(1-é-191-é-192)P3(1.1)]

= 193[1--;-191(1- 0331.1» — $1120 — Ga<1.0))] (3.34)

Stability region 723 can then be characterized by R3 = {M < Pgucc(P3),i = 1, 2,3}.
The other two regions R1 and R2 can be similarly calculated and the following result

is then readily in form.

Proposition 3.5 For N = 3, hybrid ALOHA is stable in the region R = ufi=1 72),,
with
R1 =11.- < P1...(P1).1=1.2.3). (3.35)

where Pguw(Pk) for k = 3,i = 1,2,3, are shown in (3.34), and it can be calculated

in the same manner for k = 1,2,i = 1,2,3.

It is seen from (3.34) that the probability of success Pslucc(Pk) depends explicitly
on Gk(1,0) and Gk(0,1). These functions are generally nonlinear functions of the
input rates. It will be shown in the sequel that explicit expression of these functions
can be found by solving a general Riemann-Hilbert problem. The analysis follows the

procedures given in [F179,Nai85].

59

3.5.2 Analysis of the Kernel K (x,y)

The analysis of the kernel K (x, y) is the key to solving the functional equation (3.27).
For description simplicity, in what follows we omit the subscript of the function
Gg(x,y). Since G(x,y) is analytic in |x| < 1, |y| < land continuous in |x| 3 1, |y| S 1,
the right-hand side of the equation (3.27) must vanish whenever the “kernel” K (x, y)
vanishes for |x| _<_ 1, |y| g 1.

Solving for x the equation K (x, y) = 0, we shall have a root :1: = fx(y) satisfying
A(y)x2 + 13(y)1 + C(y) = 0, (3.36)
where. by defining A = 1 - (1 — 193/ 2)(191152 + 171192) - P1192133/2. we have

A(y) = 111511920 - P3/2)(/\2 + 53/2) + A(1112 + 312)]: (3-37)

3(1)) = [/\1191152(1 - 193/2) + 511A](y9\2 + 12) +

 

 

 

+[ilhlmu - 113/2)+ 1312213102 + 5372) — 1. (3.38)

0(1) = 9111111320—133/2)(y/\2+:\2)+511p122fi302+%)- (3.39)
Therefore,

My) = _B(y;;yv)0(yl. (3.40)

with 0(11) = B(y)2 - 4A(11)C (1)) Defining t(y.¢>) = -B('y) - 2COS(<19) A(y)C(1/).

we have the following lemma.

Lemma 3.2 For (f) 6 [0,211], the equation t(y,¢) = 0 has exactly two real roots
y = r1(¢) and y = r2(¢) which satisfy 0 < r1(¢) < 1 < r2(¢).

Proof: Please refer to Appendix F.

60

Since D(y) = t(y,0)t(y,1r), it is readily shown that y1 = r1(rr),y2 = r1(0),y3 =
r2(0),y4 = r2(rr) are the four zeros of D(y) (branch points of fx(y)) satisfying
0 < y1 < y2 < 1 < y3 < y4. This result is evidently valid for the branch points

x1, x2, x3, $4 of the function fy(x). The following lemma then holds.

Lemma 3.3 The equation K (x, y) = 0 has one root 2‘ = k(y) which is an analytic al-
gebraic function of y in the whole complex plane cut along [y1, y2] U [y3, y4]. Moreover,
|k(1/)| S 1f0T|y|=1-

Similar propositions apply to fy(x): i.e., there exists y = h(x) such that
K(x,h(x)) = 0 with |h($)| S 1 for [x] = 1.

Proof: Please refer to Appendix G.
Defining

p(¢) 5 (X1 [P1P2(1 _ p3/2)7'1 ((1)) + PIPQP3/2ll)l/2, (341)

AilAT1(¢) + 131192(1 - 193/ 2)]

we then have the following result.
Lemma 3.4 k(r1(q"))) = p(¢)ei¢ for (b E [0, 271'].

Proof: From Lemma 3.3, fx(y) = k(y) is the algebraic branch of K (x,y) = 0 such
that |x(y)| S 1 for |y| = 1. Denote kc(y) as the other root of equation K (x, y) = 0. It
is shown that for y E C\[y1, y2]U [y3, y4], the minus and plus signs in (3.40) correspond
to k(y) and kc(y), respectively (compute k(1) and kc(1)).

Observe that y = r1 (d1) sweeps twice the cut [y1,y2] as q) traverses the interval

[0, 2r], then k(r1(¢)) and kc(r1(¢)) are two conjugate complex numbers satisfying

_(___7‘1C (11>)

) 2
147—” ((15)) =|P(¢)| - (3-42)

k(9‘1(¢))kc(7‘1(¢))=

From the definition of the algebraic branch, it is shown that k(r1(¢)) = p(¢)ei¢, d) 6
[0, 211]. C1

The image of the cut [y1,y2] under the mapping x = k(y) is then denoted as
La; i- {x E C : x = p(¢)ei¢, 45 E [0, 211]}, which is a smooth closed contour enclosing
0.

61

3.5.3 Reduction to the Riemann-Hilbert Problem

It will be shown in this subsection that the problem of finding out the expressions of
function G (x, 0) and G (0, y) reduces to solving a general Riemann-Hilbert boundary

value problem.

Riemann-Hilbert Problem Let L+ be a finite or infinite region, bounded by a
smooth contour L. It is required to find a function (19(2), holomorphic in L+ and

continuous in 14+ U L, satisfying the boundary condition
§R[U(z)<I>(z)] = V(z) on L, (3.43)

where U (z), V(z) are continuous functions given on L.
The formulation of the boundary value problem is illustrated below.

For pairs (x,y) satisfying K (x, y) = 0 and |x| 3 1, |y| S l, we should have
am, new. .1) + 111:. was. 0) + err.( new, 0) = o. (3.44)

Defining D = {y E C = |y| _<_ 1. |k(y)| S 1} and De = {y E C=|y|311|k(y)l>1},we
have for y E D

a(k(1/). 11)G (0. y) + b(’€(y). y)G (11(1). 0) = -C(k(y), y)G(0. 0)- (3-45)

G(0,y) and G(x,0) are analytic in D\[y1,y2]. When |y| S 1, h(y) is in the region
containing the curve Lx. Then (3.45) can be used to continue G (x, 0) as a meromor-
phic function up to L3. The eventual poles of C(x, O) are the zeros of b(k(y), y) for
y 6 Dc.

Since for y E [y1, y2], the power series expansion of C(O, y) has positive coefficients,

it is easily seen that §R{iG(0, y)} = 0 for y E [y1, yg]. Hence it follows that

ib(x, h(x))
a(x, h(x))

—ic(x, h(x))

11{ aha/1(1))

G(x,0)} = §R{ G(0,0)}, for x 6 L3. (3.46)

62

Suppose xa is the eventual zero of a(x, h(x)) on Lx. We reformulate (3.46) into

ib(x, h(x))(x — x0)“
a(x, h(x))

x, h(x))(x — xa)

3% a(x, h(x))

 

 

C(x, 0)} = 111V“ 00(0,0)} (3.47)

where a = 0 when the zero xa does not exist and a = 1 otherwise.

Similarly, denote .13), as an eventual root of b(x, h(x)) = 0 on L3. Let

 

1 z 111.1(1))11 - 1.)“
U" ’) a(x. h(x))(x — 11m"

where ’y = 0 when the root does not exist and 7 = 1 otherwise. Furthermore, let

—ic(x, h(x))(LE — 1130)
a(x, h(x))

 

V(x) = 11{ 00(1), 0)}.

The problem then reduces to finding a function C(x) which is analytic in L; , con-

tinuous in Lx U L}; and satisfies
§R{iU(x)G(x)} = V(x). (3.48)

Consequently, from (3.47), we have

C(17)

G(1€,O) = m.

(3.49)

This is typically a Riemann-Hilbert boundary value problem. The function C(O, y)

can be obtained in the same manner.

3.5.4 Solution to the Riemann-Hilbert Problem (3.48)

The solution of (3.48) can be directly obtained as in [Mus53, pp. 99-107] whenever the
contour L3, is a unit circle. The problem is more complicated when L3 is arbitrary.
Fortunately, Riemann’s mapping theorem guarantees the existence of a conformal
mapping which maps L5,; conformally onto the unit circle. Such a mapping can be

fulfilled at the aid of the Theodorsen’s procedure [CB83, pp. 70-73], which performs

63

the inverse mapping from the unit circle to La; and is stated in the following lemma.

Lemma 3.5 [CB83] The conformal mapping f0 of the unit circle z = eit,t 6 [0,271]
onto the curve L3; = {x : x = p(¢)ei¢,¢ E [0,211]} is defined as

10112“) = p(¢(t))el"’(‘). (3.50)

where f0 is assumed to be normalized by f0(0) = 0 and f6(0) > 0. For |z| < 1, f0(z)

is uniquely determined by

 

1 211 it
fo(z) = zexp[§;/O log p(¢(t)) :it t :dt], for |z| < 1, (3.51)
where ¢(t) satisfies:
1 2‘" 1
¢(t) = t — —/ logp(¢(w)) cot -(w — t)dw, 0 _<_ t g 211. (3.52)
211 0 2

This is Theodorsen’s integral equation for ¢(t); it is a nonlinear, singular integral

equation.

The details of solving the equations in Lemma 3.5 can be found in [CB83] and
will not be discussed in this chapter. We denote f (2) as the inverse of fo(z). Using
Lemma 3.5 and the methods in [CB83, pp. 68—69] and [Mus53, pp. 99-107], we can
find the solution to the Riemann-Hilbert problem (3.48) as below.

Define the index of the non-homogeneous Riemann-Hilbert boundary value prob-

lem (3.48) as

1. = Twit/(1)1161... (3.53)

where arg[U (~13)le Lx is the variation of the argument of the function U (:1) when :1:

moves along the contour L5,; in the positive direction.

64

We present the solution to (3.48) for K. 2 0 as below. The function G (x) = H (f (x))

where

 

_ 2111:1(2) t-KV(t)dt _ V(t)dt
”(2) - "271 /|t|=1 U(1)F+(t)t {[11:1U(t)F+(t)(t-z)+

 

 

 

 

 

n t""‘V(t)dt F(z)
+2 ‘/|t|=1 U(t)F+(t)(t — 2)} 271 ° (3.54)
In the above equation,
F(z) = 0.121(2), (3.55)
‘where C is a nonzero constant and
_ i log[t""J(t)]dt
- 2711 Al=1 t — z , (3.56)
with .
J (t) = 158 . (3.57)
and
_ l9(f0(t). h(f0(t)))(f0(t) - Iva)”
U“) ‘ 1100(1). 100(0))(100) — 2:1.)1' (3'58)

 

a(fo(1).h(f0(1)))

For to E L, F+(t0) is defined to be the limit when t approaches to along any path,

which remains, however, on the left of L, i.e.,

F+(10) = lim F(t). (3.60)
t—1t0,tEL+

Applying the Plemelj-Sokhotski formulas [CB83, pp. 32], it is shown that in (3.54)

1 11(1)

1
(7+ _ F + __ __ , . 1

65

Finally, G(x, 0) is obtained through (3.49).
On the other hand, G (0, y) can be computed through the similar procedures, and

consequently the stability bound in Proposition 3.4 is explicitly determined.

3.6 Delay Performance for N = 2

We consider to study the delay performance of hybrid ALOHA in this section. Based
on the collision model, the “exact” delays in the two-user slotted ALOHA systems
with symmetric and asymmetric arrival rates and transmission probabilities are cal—
culated in [$883] and [N ai85], respectively. In [N MT05], the average delay is com-
puted for the capture model in a symmetrical two-user system. It is hard to get
the exact delay for N > 2, but bounds on the average delay have been obtained

in [TM79,Szp86,EZ87] for the collision model, and in [8300] for the capture model.

3.6.1 Exact Delays for the General Case

In this section, we derive the “exact” delay for the general asymmetric N = 2 hybrid
ALOHA system.

It can be verified that in the N = 2 case, we still have the functional equation
(3.27), with the exceptions that probability p3 should be set to 0 and that the sub-
script of function G3(x, y) should be dropped. As discussed in the previous section,
through this functional equation and by means of solving the reduced Riemann-
Hilbert problem, we can obtain the explicit expressions of G(x, 0) and G(O, y). Con—
sequently, the derivatives iciggllx=l i G; and #5:] i G; can be computed,

and the following proposition holds:

Proposition 3.6 For the N = 2 hybrid ALOHA system, under the Simplistic As-
sumption, when the system is stabile with A,- < p,- — pipg/ 2, where i = {1, 2}\{i} and
1': 1,2, the exact delays 0,, i = 1,2, are given by

I
_= 2’\i(1 " Ai) ' PiPEG,‘
' 211091 - 191191/2 - Ail

 

. 1‘ = 1. 2. (3.62)

66

Proof: It can be easily known from (3.34) that if A,- < p, — pipg/ 2, the system is
stable. The queue length for either user can then be calculated as below.
Take y = 1 in the functional equation (3.27). Differentiating both sides of the

equation twice in the variable x, and making x = 1, we have user 1’s queue length

N1 é (1%?)le as below.

 

N1 = 2(191- 1112/2 __ ,1) {1111121011. 0) — 010.0) — 0'11
+1112 — 3112mm. 1) — 211+ 1112 — 122)}. (3.63)

In (3.27), taking y = 1, divided by x — 1 and making x = 1, we have
191(2 - 3192)G(0. 1) + 191192[G(1.0) - G(O. 0) = 2A1 - 121(2 - 192) (364)
Therefore, from (3.63) and (3.64),

I
N1: 2111(1- 11) “19119201
2(191 - 191192/2 - /\1)

 

(3.65)

a . d0 1, . . .
User 2 s queue length N2 = —(]y—y2|y—_—1 can be Similarly obtained.
The exact delay 0, of the ith user (i = 1, 2) can then be obtained by applying
Little’s theorem, i.e.,

Di = Ni/A‘l’ i=1,2. (3.66)

This completes the proof of Proposition 3.6. D

3.6.2 Delay Bounds for the Symmetric Case

The exact delays can be obtained yet they are hard to calculate. For numerical results,
we derive the upper and lower bounds for the symmetric two-user system based on
the MPR model. We assume that each user has an infinite buffer to store arriving
and backlogged packets. The arrivals to the ith user are i.i.d. Bernoulli with mean

A,- in every slot, and the arrivals are independent across users.

67

Let A1 = A2 = A be the arrival rate measured in packet per hybrid ALOHA slot
and p the transmission probability of both users. If we denote qll {1} = q2|{2} = a,
q1.{1.2} = 92.0.2} = b and q{112}|{112} = c, the bounds of the delay are given by the

following proposition.

Proposition 3.7 If the system is stable, i.e., A < pa + p2(b + c — a), the lower and
upper bounds of the average delay for either user are given by
1a(1— A) +p(b + c — a)(1 — A/2)

D =—
Lower a[ pa+p2(b+c—a)—A

 

1, (3.67)

and
P340 - (b + 0)]
2ar[pa+p2(b+c— a) — A].

 

DUpper = DLower '1' (3'68)

Proof: Please refer to Appendix H.

When the arrival rate A is low (e.g. A < 0.1), the given upper bound is quite loose,
as illustrated in Figure 3.5. However, if the MPR capability of the system is strong
enough, for small A’s we can approximate the desired average delay with the lower
bound. Intuitively, if the arrival rate A is small and the MPR capability is strong
enough to handle all the packet deliveries, then the probability that the two queues are
empty at the steady sate tends to be 1, which, known from Appendix H, is equivalent
to limt_.00 E(1[N{ = 0, N5 = 0]) = 1. Therefore, limt_.oo E(1[N] > 0, N; > 0]) = 0,
and the analysis in Appendix B shows that the two bounds merge and become the
exact average delay.

For moderate A’s, if the MPR capability is relatively strong with b + c getting
close to a, or if the transmission probability p is relatively small, the two bounds get
very close to each other, as shown in Figure 3.5(a) and Figure 3.5(b). In these cases,
the actual delay of the system can be roughly determined, e.g., by taking the average
of the two bounds. Note that when the MPR model reduces to the capture model,
q{1,2}l{1,2} = c = 0, the two delay bounds merge, and we obtain the “exact” delay
which coincides with the result in [NMT05].

Corollary 3.1 For a symmetric two-user hybrid ALOHA system with arrival rates

68

Average delay (D. in slots)

Average delay (D. in slots)

Figure 3.5. Delay bounds for the system with different parameters.

30 1 I I T I

 

 

 

 

 

 

 

 

 

 

 

0.7

 

 

 

 

 

 

 

 

 

 

 

- — - Delay upper bound '
25 _ Delay lower bound : .
1
1
20 _ .
15 - -
10 ~ .
5 1 1
1 .
0 J 1 l l l L
0 0.1 0.2 0.3 0.4 0.5 0.6
Arrival rate (r)
(a) p =1, a = 0.8, b = 0.4, c = 0.2.
25 I I I I I I I I
- - — Delay upper bound
Delay lower bound 1
20 -
15 -
10 ~
5 ~ \
\
o l l 1 l 1 1 1 l
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4
Arrival rate (r)

(b) p=0.7, a= 1, b=0.3, c=0.2.

69

0.45

A1 = A2 = A and transmission probabilities p1 = p2 = p, under the Simplistic
Assumption, when the system is stable with A < p - p2 / 2, the lower and upper bounds

of the average delay are given by

2(1— A) — p(l — 1/2)

 

 

D = , . 9
3
DU = DL + p . (3.70)
ppe‘r 011.187. 8Alp _ p2/2 - A]

3.7 An Illustrative Example

In this section, we provide an example to illustrate the performance of the proposed
protocol. The example is no longer limited by the Simplistic Assumption. The channel
estimation in the presence of noise is considered, and the possibility that two training
sequences collide in the same pilot sub-slot is also taken into account. The throughput,
stability and delay performances of hybrid ALOHA are evaluated and compared with
that of traditional ALOHA based on the collision model as well as the MPR model.

3.7 .1 System Set-up

Consider a two-user system. Both users communicate with the base station which
employs an P-element linear antenna array. The signals of the two users arrive at the
array with spatial angles 0 = [01,92] with respect to the array normal. Suppose the
array elements are uniformly spaced with a distance of one wavelength. The array

response matrix V(6l) is then given by

1 1312100801 ej2W(P-1)cosfil
V(9)= , l ’

1 6327100362 ej2rr(P—1)c0502

70

The two users access the system based on hybrid ALOHA and the time slots are

assumed to be synchronized. The received signal at the base station y is given by
y = V(6)Hs + n, (3.71)

where H = diag[h1, M] is the diagonal matrix containing the channel fading param-
eters for the two users. For simplicity we assume flat fading with each 11.;(2 = 1, 2)
being a zero mean complex Gaussian random variable of unit variance, i.e., E [11,-] = 0
and E[|h,-|2] = 1; s = [51, 32]T, where s, = 1 or —1 denotes the symbol transmitted
by user i in a particular symbol interval (no intemymbol interference is considered in
this example). n is the additive white Gaussian noise with zero mean and variance
0,2,I p, and the noise is assumed to be independent of the information sequence.

We assume that the channel fading is independent for two users. Furthermore, the
fading is i.i.d from slot to slot yet remains unchanged during each slot. At the base
station, the pilot symbol assisted channel estimate h,- differs from the actual channel

11,- by an independent complex Gaussian random variable Ahi, i.e.,
h,- = h,- + Ah,, 1: 1, 2, (3.72)

where Ah,- are i.i.d with zero mean and variance 0% from slot to slot. Thus hgs are
complex Gaussian random variables with zero mean and variance (“12 = 1 + 03. The

actual channel h,- can be written in terms of h,- as [GL03]
hi = phi + hi1 (3.73)

where p = 1/ (1 + 03), hgs are i.i.d complex Gaussian random variables with zero
mean and variance 62 = 0’3/(1-1- 03), and E'[h,-h;] = 0 for i,j = 1,2.
Considering coherent reception, signal processing at the receiver produces the
output
2 = H*wy = H*WV(0)Hs + H*Wn, (3.74)

71

where 11: denotes the complex conjugate operator, PI = diag[}l1, 17:2] contains the esti-
mated channel coefficients for the two users, W represents the beamforming weight
matrix. The ith row of W, wi, represents the weight vector for the ith user.
If we denote the ith column of V(B) as v,, (3.74) can be rewritten as
z = z1 = wlvlhlh’f w1v2h2h'f sl + :i'wln . (3.75)
22 w2v1h1h§ w2v2h2h; 32 h§w2n
Assuming that the data source is i.i.d., and without loss of generality considering
the case when 51 = 1 (results for 31 = -—1 can be similarly obtained), from (3.73) and
(3.75), it is easy to see
ElZilllll = W1V1P|111|21 (3-75)

Valei|llil = l111|2(|‘1V1V1|25'2 + IWIV2|2 + Wlwiiaglh (3-77)

Given the estimate of the channel, the signal to interference plus noise ratio (SIN R)

is then given by

 

E[SINR|h1] = I p I2 .
62 + _szw v + —L2w1w 02
|W1V1| |W1V1| "

If the interference from user 2 is not present, then only the noise accounts, and we

(3.78)

 

have 2 . 2
. h
E[SNR|h1] = p 1 11H (3.79)
62+ wlw 02
|w1v1| n

3.7 .2 Evaluation of Channel Estimation Error

Suppose user 1 transmits a pilot symbol s1 in one of the pilot sub-slots, and it is
contaminated by the interference 52 from user 2 and the noise. The received composite
signal is given by

y = vlhlsl + v2h252 + n. (3.80)

72

Regardless of the existence of user 2, the “brute force” estimation of h1 is given by

 

1., = ny_ = V¥V2h232 v11!" . (3.81)
lvqullsl |V¥V1|81 V(IV181
The mean—squared error of the estimation is
H 2 2
A v v
03 = Ellhl - h1|21= ———| 1 2' a” (3.82)

 

|V¥Vfl2 IVFVHI

If L(r) pilot symbols are transmitted, where L(r) is proportional to r, then by av-
eraging, the mean—squared error of the channel estimation is reduced by a factor of

1/L(T), i.e.,

 

 

H 2 2
l v v
6210— ' 1 2' a"

_ . (3.83)
L(r) |v{7{v1|2 |v¥v1|)

In the absence of user 2, the channel estimation error is only introduced by the noise,

 

hence 2
1 o
—2 n
o r = . 3.84

3.7 .3 Probabilities of Successful Signal Receptions

With the derivations above, we can then adopt the SIN R threshold model [ZR94] for
packet reception. Under this model, user 1’s packet is assumed to be successfully
received if E[SINR|h1] > )6, where )6 is the predetermined threshold required by
system QoS.

When only user 1 transmits, we have

 

2 f 2
q. 1 =Pr1 0"" >11). (3.85)
|{} 2 “,le 2
5 +
1 |W1V1| n

where p? = 1/ (1 +621), 6% = 621 / (1 +621), and 631 is the variance of the collision-free

channel estimation error given by (3.84).

73

Since Ihll2 ~ exp(1/o2), the above probability is given by

qllill = “i2/002 Wle 2 28—33:]:
a ..
5(0 +W0nl/P
= 8Xp{-/5[Uel+(1+081)|w11:V11|20 071]} (3°86)

Similarly, the probability of user 1’s packet being successfully received when two
users stagger the training sequences in two pilot sub-slots, 51|{1.2}1 is given by

2 ‘ 2
- P lhil
qi|{1,2} = Fri 1 > H}

2 H
-2 [w v | “’1‘" 2
+ 42-2 + —L20
1 lw |W1V1l ”

1V1|

 

 

 

1w vI ww”
= expl—flla§1+(1+9§1)(lw lef|2+lw1v )2 an») 1187)

Consider the more practical case beyond the Simplistic Assumption, there is a
probability that both users succeed even if their training sequences collide in one pilot
sub-slot. Let 5,, {1,2} correspond to the probability of user 1’s packet being successfully
received when two users’ training sequences collide. Equation (3.87) applies to obtain
the value of 51|{1»2}' Nevertheless, the collision-free channel estimation error 021
should be replaced by the estimation error with collision, 032, which is calculated
using (3.83).

In Section 3.3, we have assumed that the user transmits the training sequence
in either pilot sub-slot with equal probability. Hence, given that two users trans-
mit packets concurrently in one time slot, the probability that user 1 is successfully

received is
1 1 ~
(111(12): 5911(1,2}+ 291({12} (388)

Similarly, under the assumption that two users are symmetric, the probability

that both packets are correctly received when two users transmit in one time slot,

74

q{112}|{112}’ is given by

1 2
411211112) = §e><p{- 211[agal+(1+ gl)(IWW1V2I w_1__’:w1
Iw

 

02H} +

ml2 IW1V1|2 0"

62)”. (3.89)

IW 1V1|2 IWWII2 "

1Vz|2 W11”?

 

 

l
§CXD{—2f3[082+(1+0’82)(

Other probabilities can be obtained through similar calculations, and we can now
obtain the throughput, stability region and the delay bounds of the proposed protocol.
In the sequel, we assume that at the base station, the linear antenna array has
P = 5 elements, and the impinging signals are relatively close with 6 = [54°,64°].
The front-end processing exploits matched filter with the beamforming weight matrix
W = VH (0). Furthermore, we assume the packets are of small size containing 40

symbols per packet, with a training length of 2 symbols corresponding to r = 0.05.

3.7 .4 Throughput of Hybrid ALOHA with Imperfect Chan-

nel Estimation

Under these settings, Figure 3.6 presents the overall throughput of hybrid ALOHA
with M = 2, as well as the throughput of traditional ALOHA based on both the
collision model and the MPR model. Note that in the scheme of traditional ALOHA
based on MPR model, simultaneous packet receptions are possible: successful signal
decoding can be achieved as long as the SINR of the user’s signal is beyond the
threshold required by (208. As shown in (3.85)-(3.87), the probabilities of successful
transmissions are related to r and are dependent on the noise power, interference
level, and channel estimation accuracy. Following Proposition 3.1, the normalized
throughput of hybrid ALOHA, VHALOHA(T)1 and that of hybrid ALOHA based
on the MPR model, 11 A L0 H A(r), can be evaluated through these probabilities. The
results presented in Figure 3.6 show that hybrid ALOHA outperforms traditional
ALOHA due to the improved MPR capability.

As we have mentioned in Remark 1, the training length 1 should be designed

according to specific system requirements. In this example, the optimal 1' maximizing

75

.0
N

 

 

 

 

Hybrid ALOHA with

0.6 v MPR model _
A Traditional ALOHA
3 with MPR model
3': 0.5 _ ,
:‘é’
3 ______
1550» ,”” ~.-“\ .
x . ‘
U ./
(U 0/
3 _/ / , _____ R \ \
§03r ///// \ \\\\\
e 0.2- f .
'5 / “ Traditional ALOHA

o1 . with collision model

0 1 1 L

Attempting rate R(r) (packets/slot)

Figure 3.6. Throughput comparison of different. schemes under the specific system
settings, SNR = 10dB, 13 = 6dB, 53, = 0.01, 532 = 0.06.

76

the throughput of hybrid ALOHA V}; _A L0 H A(T) can be obtained as:

Topt = my glgg{I/H_AL0HA(T)}1 (390)

where Q = {T | 0 < T < 1, L(T) E N}, L(T) is the number of training symbols
defined in Section 3.7.2. The general closed-form expression of Topt is difficult to find.
However, the numerical result can be obtained through computer programming. In
Figure 3.7, the dashed line (red color) represents the optimal T against the arrival rates
of each (symmetric) user under the system settings mentioned above. In addition, an
“equilibrium” curve (defined as the value of T such that ”H .A L0 H A(T) = u A L0 H A(T))
is also presented in Figure 3.7, below which the throughput of hybrid ALOHA is
always higher than that of traditional ALOHA with the same training length 7'.
Beyond the equilibrium curve, the increment of 1' would degrade the spectral efficiency
compared to that of the traditional ALOHA. Note that the staircase-like shapes in
both curves reflect the constraint that the training sequence should contain integer
number of symbols, i.e., L(T) E N.

In Figure 3.7, it is as expected that when arrival rates are very low, equilibrium
values do not exist. This is because the insertion of idle sections under the circum-

stances of rare collisions makes hybrid ALOHA inferior to traditional ALOHA.

3.7 .5 Stability Regions and Delay Bounds with Imperfect

Channel Estimation

Figure 3.8 shows the stability regions for hybrid ALOHA under the aforementioned
system settings. The arrival rates are in the unit of packets per unit time. For
moderate arrival rates hybrid ALOHA is shown to have the best performance due
to the MPR improvement. On the other hand, in the casas when the arrival rate
of one user is at the low end while that of the other user is at the high end, the
stability region for hybrid ALOHA is contained in that of traditional ALOHA, and
this degradation reflects the impact of idle sections. Refer to Figure 3.4, it can be
seen that within certain ranges, the stability region of hybrid ALOHA contains that

77

 

      

I

0'5 Equilibrium

values \

P
.5
I

Length of r
O
u

 

 

 

 

0.2 1 Optimal .
values
0.1 r a
__________________ l _
0 1 1 1 1
0 0.2 0.4 0.6 0.8 1

Arrival rate A (packets/unit time)

Figure 3.7. Numerical values of T achieving equilibrium points and Topt maximizing
the throughput of hybrid ALOHA .

78

of TDMA as well, even for the scheme without any guard time.

0.9 I I I I I I I I

 

    
   
 

0.8 Hybrid ALOHA «

. with MPR model

  
  
 

0.7

Traditional ALOHA
\ \ with MPR model ‘
/

\

0.6

0.5 r

0.4 r

A2(packets/unit time)

0.3 -

 
  
 
   

I

/

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
A1(packets/unit time)

0.1}

 

 

 

Figure 3.8. Comparison of stability regions of different schemes, S N R = 10dB, fl =
6dB, 03, = 0.01, 113, = 0.06.

Figure 3.9 illustrates the delays (bounds) of three different schemes as a function
of the arrival rate for fixed transmission probability p = 0.75. Hybrid ALOHA results
in the smallest delay among the three schemes for moderate rates, while the trend is
reversed when the rates are small. The gains over traditional ALOHA with the MPR
model seem relatively minor from the figure. One of the reasons is that the system
contains only a small number of users (N = 2), which limits the possible improvement
range. Much larger gap could be observed in systems with more users, which deserves

further investigation.

79

30 I I I I I I I I

l 32:? 1933:3523
i y with MPR model , ,
Traditional ALOHA
_ Exact delay of with MPR model
traditional ALOHA
with collision model

 

 

 

 

N
01

  
   

[’0

Average delay (time unit)
8 a

”4.51

 

 

l l l

0 I l l I l
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45
Arrival rate A (packets/unit time)

 

Figure 3.9. Comparison of delays of different schemes, S N R = 10dB, )6 = 6dB, 631 =
0.01, 532 = 0.06, p = 0.75.

80

 

3.8 Summary

In this chapter, taking a cross-layer (MAC and PHY) perspective, we propose a
novel MAC protocol named hybrid ALOHA for wireless networks. Idle sections are
introduced into the traditional ALOHA slot to make it possible for collision-free
channel estimation in multiple access environment. Improved channel estimation
increases the MPR capability and results in better system performances in terms
of throughput, stability and delay. The major results can be briefly summarized
as follows. First, we simplify the analysis by adopting the Simplistic Assumption,
in which a transmission is successful if and only if collision-free channel estimation
can be achieved, given that the noise and the interference is limited within a certain
degree. Under the simplified model, the throughput of the system is obtained. The
performance demonstrates a monotonicity with the increase of the MPR capability.
Secondly, we characterize the stability region of hybrid ALOHA in the two-user case,
and derive the sufficient condition for system stability in the more general finite-user
case. Characterization of the stability inner bound for the special N = 3 case is
present. It is shown in the two-user case that, under the Simplistic Assumption, the
hybrid ALOHA system reaches a critical MPR capability such that it has an identical
stability region with that of the TDMA scheme. The characterization of the stability
inner bound for the N = 3 case can be reduced to solving a general Riemann-Hilbert
problem. Thirdly, we study the delay performance for the two-user system under
the general MPR model. The “exact” delays for the asymmetric system and the
upper and lower bounds of the average delay for the symmetric case are derived. It is
shown that when the MPR channel reduces to the capture channel, the two bounds
merge and we get the “exact” delay of the system which coincides with the result
in [NMT05]. Finally, beyond the Simplistic Assumption, the effectiveness of the
hybrid ALOHA protocol is demonstrated through a practical example using array

signal processing.

81

CHAPTER 4

Source-Aware Non-Uniform
Transmission for Minimum

Distortion

This chapter considers average input-output distortion minimization through joint
optimization of source index assignment and modulation design. First, the general
optimization criterion is derived. Secondly, source-aware non-uniform information
transmission is proposed by utilizing the inherent non-uniformity in Gray coded con—
stellations, both symmetric and asymmetric. It is found that when channel coding
is involved, the proposed scheme delivers significantly better performance in com-
parison with existing unequal error protection schemes with non-Gray codewords.
Furthermore, joint quantization-constellation design is investigated under the crite-
rion of distortion minimization. The proposed method generalizes the concept of
constellation design from the perspective of joint source-channel coding. The simplic-
ity and power efficiency of the proposed schemes make them particularly attractive
for systems with tight power constraints, such as wireless sensor networks and space

communications.

4.1 Introduction

Given a source with rate R bits/ second and a channel with capacity C bits/ second,
Shannon’s well known channel capacity theorem says that if R < C, then there exists

a combination of source and channel coders such that the source can be communicated

82

over the channel with fidelity arbitrarily close to perfect. This theorem essentially im-
plies that the source coding and channel coding are fundamentally separable without
loss of performance for the overall system.

Following the “separation principle”, in most modern communication systems,
source coding and channel coding are treated independently. In other words, source
representation is designed disjointly from information transmission. After A / D con-
version of analog source signals, the bit streams are then uniformly encoded and
mapped to symbols prior to transmission, uniform bit-error—rate (BER) has been
serving as one of the most commonly used performance measures. However, for sys-
tem with analog input, the ultimate goal of the communication system is to minimize
the overall input-output distortion. While BER plays the dominant role in distortion
minimization, a communication system that minimizes the BER does not necessarily
minimize the overall input-output distortion. Therefore, novel system design that can
achieve simultaneous BER and distortion minimization is highly desirable.

In [ZG93], with no specifications on the modulation schemes, Zeger proposed
a locally optimal index assignment (source coding) solution for minimum input-
output distortion, known as pseudo-Gray coding, by using iterative binary switching.
Pseudo-Gray coding provided an effective approach in reducing the average distor-
tion of a vector quantized system by rearranging the positions of code vectors in
a given codebook. Various channel-optimized quantizers, multistage vector quan-
tizers have been studied in [FV87, PFM93, WF94]. On the other hand, assuming
source index assignment has been done separately, and with the observation that
the bits come out of the source encoder are generally non-uniform (i.e. have dif-
ferent levels of significance), Masnick, Wolf [MW67] and Cover [Cov72] introduced
non-uniform modulation (index mapping) schemes, known as unequal error protec-
tion codes, for which the more important bits have lower error rate than other bits.
Stemmed from [MW67, Cov72], unequal error protection through both symmetric
and asymmetric constellations have been further developed in [ROUV93], [MZFLIOOa]
and [MZFLIOOb]. It should be pointed out that the resulted constellation codeword
design in [ROUV93, MZFLIOOa, MZFLIOOb] may no longer be Gray codes.

83

In this chapter, taking a mixed analog-digital perspective, we consider average
input-output distortion minimization through joint optimization of source index as-
signment and modulation design. First, we derive the general optimization criterion,
and obtain that the necessary condition for simultaneous minimization of BER and
distortion is that the quantization codebook and the modulation constellation should
have the same dimensionality. Secondly, based on the fact that Gray code ensures min-
imum BER when the channel error probability is sufliciently small, we propose a novel
sourceaware information transmission approach by exploiting the non-uniformity in
Gray-coded constellations. It is shown that when there is no channel coding, the
proposed approach has comparable performance with existing modulation schemes
in [ROUV93, MZFLIOOa, MZFLIOOb]. But when channel coding is involved, our de-
sign outperforms the existing schemes with big margin. The underlying argument is
that after channel coding, BER dominates the distortion minimization as the original
geometric structure of the quantization codebook can no longer be maintained. The
simplicity and power efficiency of the proposed scheme make it particularly attractive
for systems with tight power constraints, such as wireless sensor networks and space

communications.

4.2 Problem Formulation

Consider a digital communication system with analog input, as shown in Figure 4.1.
Let xk be the discrete—time analog input vector resulted from uniform sampling of a
continuous signal x(t).

xk is first fed into a quantizer Q, which is a mapping of n-dimensional Eu-
clidean space R" to a finite set P C R", given by Q : R" —t P, where P =
{P0, P1, - -- ,PM_1} is the quantization codebook with P,- E R" for O S i _<_ M — 1.
We assume that the size of P is |P| = M = 2'", where m 2 0 is an integer. Let
yk = Q(xk) denote the quantization value of xk. yk is coded into a binary sequence
through an index assignment function 7r, and is then fed into a source-aware digital

channel encoder and a modulator, i.e., the most significant bits (MSB) and least sig-

84

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

, Index MSBs ' Source-aware '. , g
_55, Quagtlzer Y1 Assignment ’5 Channel : § Tx
rr flLSBs ' Encoding 'r——’ §
AWGN
Channel
———————— U
5, Inverse Index s—MS—Bs—i Ch I ' 3
‘—‘ Assesses 1 09.33:; i, e Rx
" ‘ LSBs L________! g

 

 

 

Figure 4.1. System Model

nificant bits (LSB) will be treated distinctly. Let 9,, denote the receiver output, which
is an estimate of the quantization value yk, the averaged input-output distortion is

then given by
Do = E{d(xka$’k)}1 (4-1)

where d : R" x R" —t R is a non-negative function that measures the distance
between two vectors in R".

Consider the widely used mean-square distortion function d(x, y) = “x — y||2. In
this case, the optimal quantizer satisfies the well-known nearest neighbor and centroid
conditions [ZG93, ZG88], then the overall distortion D0 can be decomposed into two
parts, namely, the distortion due to quantization noise, and the distortion due to

channel noise [Mes79], denoted as nq and nc, respectively. That is,

XI: - S’k = (XI: 'Yk)+()’k -$’k)
nq no

When the quantizer satisfies the centroid condition, E{nq} = 0. Note that the

quantization noise and the channel noise are independent, we have E{nqn§ } =

85

E{ncn51} = 0. It then follows that

00 = E{|lnqll2} + E{I|ncl|2}
= E{IIch — MHZ} + EUIYk - 91.12}. (4.2)

When the quantizer is optimal, the distortion due to quantization error is minimized.
Minimization of DO is thus reduced to minimizing the distortion only due to the

channel noise

D = E{d(Yk1$’k)}- (4-3)

In the sequel, we will discuss joint source index assignment and constellation codeword
design for minimum distortion, as well as non-uniform transmission based on Gray-

coded constellations.

4.3 Joint Source Index Assignment And Constel-

lation Code Design

In this section, we consider to minimize the distortion D = E {”Yk — yk||2} through

joint design of source index assignment and index mapping.

Write yk as
Yk = in: + ell: (4-4)
where yk, S’k E P = {P0,P1,--- ,PM_1}, and ek is the estimation error. For
0_<_iSM—1,define
Eizipi-PjiOSjSM‘ll- (4.5)

86

It then follows that

D = Eillyi. —i1.ll2}

M-1 M—1
= Z 2: “Pi — lel2 F(S’lc = leYk = Pi) F(Yk = Pi)
i=0 j=0
M—l
= Z F(Yk = Pi) Z ”ekll2 F(ek). (4.6)
i=0 ekEEi

Here p(a:) denote the probability that :1: occurs.

For efficient transmission, each quantizer output yk is first coded to a binary
sequence then mapped to a symbol in a constellation Q. When the signal-to-noise
ratio (SN R) is reasonably high, as it is for most useful communication systems, each
transmitted symbol is more likely to be mistaken for one of its neighbors than for far
more distant symbols. Therefore, to minimize the distortion D, the optimal index as-
signment and constellation codeword design should map the neighboring quantization
vectors from the quantization codebook P to neighboring symbols in constellation 0.
More specifically, the optimal 1-1 mapping S : P —+ 9 should satisfy the following

condition:

(C1) Let Pi,Pj,P,-,Pj E P, then d(Pi,PJ-) S d(Pi,PJ-) if and only if
d(S(Pi)15(Pj)) S d(5(13i)15(13j))-

That is, ideally, an isomorphic mapping that reserves the geometric structure should
exist between the quantization codebook P and the constellation Q. When the quan-
tizer is optimal, and the constellation is Gray coded, condition (01) ensures the
equivalence between minimizing the BER and minimizing the average distortion D.

Next we look at the necessary conditions for the existence of S that satisfies (C1).
First, assume that the size of the constellation IQI = |P| = M, and then look at the
case when Ifll < |P|.

We start with systems equipped with scalar quantizers and two-dimensional con-

stellations. Consider a system with a 4-bit uniform scalar quantizer and a 16-QAM

87

constellation, see Figure 4.2. Since P = {P0, P1, - ~ , P15} C R, without loss of gen-
erality, assume P0 < P1 < - - - < P15. As can be seen, each P,- has at most two nearest
neighbors, but a symbol in a 16—QAM constellation can have as many as 4 nearest

neighbors. It is then impossible to find an S : P —-> (I that satisfies (C1).

 

1}
A11 A12 A13 A14
e,‘ e ~~ ,e e
I
{P14 P15
\\‘ I
I
I
\\\ II
\‘ I
A21 A22 ’1’ A23 A24
' ‘e _.._ 1' O ’9
‘ s i, I,
\ I I
I I
I I
I ’I
\‘ I I
\ l I
\‘ I I
l 1 ~' 1 l L
l l .' \ l ’ 1 r
I \ ’
I I
I I
l’ ‘\ I”
A31 A32 '1’ II,»\’\A33 A34
0 e ,1’ ~— ' b, e
I, 1” “\
I I
I
I
I \\
I \
p, ’l ‘\‘
I 1 \
A41 Ad! A43 \f’w
O ‘ ~— 0 ~e
P0 P1

 

Figure 4.2. Mapping of quantized values to the 16—QAM constellation.

In fact, assuming there is an S : P —t fl that satisfies (C1), then we should have

d(S(P0)15(P15)) = xllggéndfiiimh (4-7)
d(5(P0)1-5'(P1)) = d(S(P14)13(P15)) =$min€nd($11$2)1 (4-8)

I

d(S(P1).S(P14)) > Pinexp{d(S(Pi).S(Pj))}. 1.1 79 0,1,14,15. (4.9)

2’ J
Without loss of generality, assume S(P0) = A41, S (P15) = A14, as illustrated in
Figure 4.2. Now consider the pair P1 and P14. For (4.8) to be satisfied,, P1 and P14
should be mapped to the nearest neighbors of P0 and P15 respectively. Without loss
of generality, assume S(P1) = A42. Since d(A42,A13) > d(A42,A24), according to

88

(C1), we should have S(P14) = A13. However, this violates (4.9), since d(A42, A13) <
d(A11,A44) but A11,A44 will correspond to points from {Phi 95 0,1,14,15}. This
implies that, to satisfy (4.9), P1 and P14 should be mapped to the pair A11 and A44.
Clearly, this violates (4.8). Therefore, an S that satisfies (C1) does not exist.

More generally, we have:

Lemma 4.1 For systems utilizing scalar quantizer with codebook P and a symmetric
(two-dimensional) rectangular or square constellation Q with IQI = |P| = 2'", m > 1,

there is no 1-1 mapping S : P —t 9 that satisfies (0]).

For the 4—bit scalar quantizer discussed above, instead of 16—QAM, consider the
one-dimensional constellation 16—AM with Gray code, see Figure 4.3. Still denoting

Figure 4.3. Symmetric 16—AM constellation.

the constellation with It, clearly the 1-1 mapping S : P —t (2 defined by S (P,) =
A,, 0 S i S 15, satisfies (C1), and it minimizes the BER and the distortion D

simultaneously.

Remark 4.1 Our discussions in the one-dimensional case imply that: simultaneous
minimization of BER and distortion D essentially requires that there exists a 1-1
mapping S : P —> (to which satisfies condition (01), where (20 Q Q is a a real subset
of Q or Q itself. This result provides another demonstration to the well known fact
that: the essence to obtaining larger coding gain is to design codes in a subspace of
signal space with higher dimensionality, as a larger minimum distance can be obtained
with the same signal power. For example, two-dimensional constellation such as QAM
would be a natural choice for two-dimensional vector quantizers. For multidimensional

vector quantizers, multidimensional constellations would fit best [FW89/. In the case

89

when IQI < |P|, more than one constellation symbols are needed to represent one
quantization value. Again, the multidimensional signal constellation obtained from

the Cartesian product (ZN should be ezploited and is currently under investigation.

Due to lack of a priori statistical information of the input signal, non-entropy
coding is widely used for various sources in practice. That is, in each quantization
codeword, some bits are more significant than other bits, and an error in a significant
bit will result in large distortion than that in a less significant bit. This universal
existence of non-uniformity in source coding calls for non-uniform information trans-
mission, also known as unequal error protection, in which the most significant bits
have lower bit-error—rates than other bits. In the following, we consider source-aware
non-uniform transmission design along the line of joint source index assignment and

constellation design.

4.4 Source-Aware Non-Uniform Transmission De-
Sign

4.4.1 N on—Uniform Transmission Based on Gray-Code Con-

stellations

Non-uniformity exists in most constellations except BPSK and QPSK, either they
are asymmetric or even if they are perfectly symmetric.

Asymmetric constellations, see Figure 4.4(a) for example, were originally devel-
oped for multiresolution (MR) broadcast in Digital HDTV [Cov72, ROUV93], and
further analyzed in [MZFLIOOb]. The asymmetric constellations were designed to
provide more protection to the more significant bits by grouping bits into clouds
leading by the most significant bits, and the minimum distance between the clouds
is larger than the minimum distance between symbols within a cloud.

For symmetric constellations, an unequal error protection scheme based on block

partitioning is provided in [MZFLIOOa], which is a generalization of the Ungerboeck’s

90

1 6'QAMI bob1bzb3

 

 

 

 

~~~~~~~~~~~ , 1
{100.00 01110,‘ {,4 090 10 .1 a,
i i 1 .3
\0001 0011/ \1001 1011.1'
T ‘3 3" *9. 3"
d1 i Jl i i >
{01.00 01.1 01‘ g_ {:1 1.00 1 1; 0
d2 I‘ I} I‘ I":
l 91.01 01.1}. + 11.01 1 1 11 ,1
ledzet— 11—1
(at)
16'QAMI bob1b2b3
4)
00.10 01.10 _ 11.10 101.0
0011 0111 1111 1011
T O O — O 0
d1 i i i i 5
0001 0101 1101 1001
e e _ e 0
d2
i 0000 0100 1100 1000
O O —* O 0
l1— 112 + 111—1

(b)

Figure 4.4. (a) Asymmetric 16—QAM, d1 > d2; (b) Symmetric 16—QAM with Gray

codes.

91

mapping by set partitioning. With block partitioning, the number of nearest neigh-
bors is minimized for each bit level b,-. It turns out that the resulted codeword design
coincide with that of the MR scheme with (11 = d2. As can be seen, constellations
resulted from either block partitioning or the MR scheme may no longer be Gray-
coded.

As is well known, Gray codes are developed to minimize the bit-error-rate, in which
the nearest neighbors correspond to bit groups that differ by only one position. Here,
we revisit the non-uniformity in constellations with Gray codes, and introduce a non-
uniform transmission scheme based on Gray-coded constellations. In the following,
we illustrate the idea through Gray coded 16-QAM constellation shown in Figure
4.4(b).

In 16-QAM, each codeword has the form b0b1b2b3. If we go through the 16 symbols
in Figure 4.4(b), there are altogether 24 nearest neighbor bit changes, among which
b0 and b2 each changes 4 times, and b1 and b3 each changes 8 times. Note that when
channel probability error is sufficiently small, a bit error corresponding to each bit
location b,- is most likely to occur when the nearest neighbor has a different value in
that specific bit location, i.e., among neighboring pairs where a change occurs. Let
Pe denote the error probability, then this implies that when SN R is reasonably high,
Pe(b0) = Pe(b2) = %P3(b1) = §Pe(b3). Our analysis coincides with the theoretical
results in [LLCL99, YHOO, CY02].

We propose to minimize the average distortion by exploiting the inherent non-
uniformity in Gray-coded constellations, that is, to map the more significant bits
from the source encoder to bit locations with lower error probability in constellations
with Gray codes. For example, consider a 4-bit quantizer and a 16-QAM constellation
as in Figure 4.4(b), the two MSBs will be mapped to b0 and b2, while the two LSBs
be mapped to b1 and b3.

The proposed approach can be applied to both symmetric and asymmetric
constellations. To illustrate the performance, we compare the proposed Gray-
code based non-uniform transmission scheme with the block partitioning based ap-

proaches [MZFLIOOa,MZFLIOOb] for both coded and uncoded systems (note that the

92

MR scheme [ROUV93] is only for asymmetric constellations and coincides with the
block partitioning based method in the asymmetric case [MZFLIOOa, MZFLIOOb]).
Example 1 The source is assumed to be analog with the amplitude uniformly
distributed within [0,100], quantized using a 12-bit uniform quantizer. We con-
sider various 16-QAM constellations, both symmetric and asymmetric. First,
each 12-bit quantization output b0b1~~b11 is partitioned into three 4-bit strings:
b0b1b6b7, b2b3b8b9, b4b5b10b11, then mapped to both symmetric and asymmetric
16-QAM constellations based on the block partitioning (BP) scheme or the pro—
posed Gray-code based non-uniform transmission scheme. By random index assign-
ment, we mean that no distinction is made on MSBs and LSBs, and the strings are
mapped to the Gray coded constellation based on their original bit arrangements
b0b1b2b3, b4b5b5b7, bgbgblobll. The result is shown in Figure 4.5.

Example 2 In this example, impact of channel coding is investigated for both
systematic and non-systematic coding schemes. Using the same source as in Example
1, a lO-bit uniform quantizer is connected with a source-aware channel encoder, for
which the first 4 MSBs are fed to a rate 1 / 3 convolutional (or Turbo) encoder and the
rest 6 bits are fed to a rate 1 / 2 convolutional(or Turbo) encoder, respectively. The
channel coding output are then mapped to l6-QAM constellations non-uniformly
based on the block partitioning approach and the proposed mapping scheme. The

result is shown in Figure 4.6.

Remark 4.2 As demonstrated by the simulation results, while the proposed approach
has comparable performance with existing unequal error protection methods for un-
coded systems (i.e. when there is no channel coding), the Gray-code based non-uniform
transmission outperforms the non-Gray-coded methods (i.e., the MR method and the
block partitioning based approach) with big margins when channel coding is involved.
The underlying arguments are: (i) Channel coding may change the geometric struc-
ture of the uncoded symbols; (ii) When SNR is reasonably high, BER of the more
significant bits vanishes, and BER of the less significant bits dominates the overall

distortion, and hence Gray coded constellations result in much better performance.

93

Normalized MSE (dB)

'4 I I l l l

 

-6- . \\

-8

     
 

-12 _. . . . . . . . . . \
_ _ _ Random index assignment. Gray code. d2/d1=1

 

—e.— Proposed mapping. Gray code. d2/d1=1
-14 —111— Block partitioning, Non-Gray. 112/d 1=1
‘9 Proposed mapping. Gray code. d2/d1=0.8
+ MR mapping. Non-Gray, dZ/d1=0.8

 

 

 

 

1 2 3 4 5 6
Symbol SNR (dB)

Figure 4.5. MSE for different transmission schemes: Uncoded System.

94

 

 

 

-*- Block partitioning. Non-Gray. A=O.8. Conv.
A -A- , Block partitioning, Non-Gray,1=1. Conv.
’25?" x \ ' ' -O- , Block partitioning, Non-Gray, k=1. Turbo
13—. : ;\‘1 ~25: \ —*— Proposed mapping. Gray code. 330.8, Conv,
._3o(.;\“~~ "C" * " r 1 i ‘33? x + Proposed mapping. Gray code. 71:1. Conv.
7‘“?— ‘‘‘‘‘‘‘‘‘‘‘ Q ‘ \ 1:. 31;; —e— Proposed mapping, Gray code. 1:1, Turbo

Normalized MSE(dB)
1'.
01

 

 

 

 

 

-50 l- —1
—55 t 1
-60 ._ .1
-65 — _ , a
_70 l l l l l l l l
5 6 7 8 9 10 11 12 13 14
Symbol SNR(dB)

Figure 4.6. MSE for different transmission schemes: Coded System ()1 = d2 / d1).

95

4.4.2 Source-Aware Constellation Design

In literature, constellation design has largely been separated from quantizer design. In
this section, we consider joint quantizer-constellation design for minimum distortion.

Following our discussions in Section 4.3 and Section 4.4.1, we propose to incor-
porate the source information reflected in optimal quantizer design into constellation
design. Note that the optimal quantizers minimize the average distortion between
the original sampled values and the quantization values, when considering memory-
less AWGN channels, optimal quantizers can be exploited directly for constellation
design. We illustrate this idea through the following example.

Consider a non-uniform scalar quantizer with four possible quantization values.
Assuming the quantization code book is P = {P1, - -- ,P4}, where P,- < Pi.” for
i = 1,2,3 and each P,- occurs with probability p(P,-) = p,- for i = 1, - ~- ,4. Define
Dij = |P,- — Pj|2. Along the lines of Lemma 4.1, we consider the design of a 4-AM
constellation fl = {A1, - - . ,A4} and assume that the 1-1 map S : It —> P is designed
to satisfy condition (C1). We further assume that the quantizer is optimal, that is,
it satisfies the nearest neighbor rule and the centroid criterion. Define dij = |P,- - le
for i,j = 1, - -- ,4, d,- = |A,-—A,~+1| fori = 1,2,3, and let Di be the average distortion
corresponding to symbol Ai for i = 1, - - - ,4. Consider a memoryless AWGN channel,

for which the noise is zero mean and with variance 02, then we have

 

 

Di = diz [mg—1-Q(2d—1—2——:d2)]'l'd41Q(2d1+2:2+d3)+
dis [my—3:442) — 0(2‘“ + 3:2 + d3 )] . (4.10)
02 = dizQ(g—;)+d§3[Q(:—: —o(2—,—"2+d3>]+d @2012L—2Zd3). (4.11)

96

d3 d2+2d d1+2d +2d
D4 = (134 [Q(§; —Q(——2;'—3)] +df4Q( 2: 3)+

d2 + 2(13 (11 + 2d2 + 2(13 )]

 

 

) - Q( (4-13)

2
d2“ [Q( 20 2o

2 . .
where Q(x) = 712; ff e“ /2dt. The overall average distortion can be written as

4
D = ZpiDz'. (4.14)
i=1

Defining ’71 = do 1 72 = 3%, ’73 = 5:11, the problem of optimal constellation design for
minimum average distortion is reduced to finding 71, 72, '73 such that D is minimized,

subjected to a power constraint, that is

min D, subjected to PSSC, (4.15)
71172173

where P, is the average symbol power and C is a constant. The method used in this
example can be extended directly to more general cases. We illustrate the proposed
approach through an example.

Example 3 Consider a source consists of two Gaussian distributed random processes
centered at :l:5 with variance 02 = (3)2, as shown in Figure 4.7(a). Using a 4-level
optimal quantizer with codebook P = {—6.40,-3.86,3.69,6.2}, normalized MSE
under different SN R levels is shown in Figure 4.7(b) for both uniform 4-AM and the
proposed source-aware 4-AM.

From the simulation result, it can be seen that while symmetric constellations
are optimal for uniformly distributed sources, asymmetric constellations reduce the
average distortion significantly for sources that require non-uniform quantization.
Compared with the asymmetric constellations originally designed for multiresolu—
tion broadcasting [Cov72,ROUV93], the proposed joint quantizer-constellation design
scheme generalizes the concept of non-uniform constellation design from the perspec-

tive of joint source-channel coding.

97

(n

 

18

Figure 4.7. Example 3: (a) Source distribution (b) Normalized MSE under different

 

 

 

 

1 l 1 1_ J 1 1

 

 

5 6 7 8 9 10 11 12
SNR per bit (dB)

(b)

SNR levels, uniform 4—AM versus the proposed source-aware 4—AM.

98

 

4.5 Summary

In this chapter, we studied joint optimization of source index assignment and mod-
ulation design for overall input-output distortion minimizations in communication
systems. Taking a joint source-channel coding perspective, distortion minimization
was carried out through Gray-code based non-uniform mapping and joint quantizer-
constellation design. The power efficiency of the proposed source-aware non-uniform
transmission scheme makes it attractive for any digital systems with analog inputs,
particularly for systems with tight power constraints such as wireless sensor networks

and space communications.

99

CHAPTER 5

Conclusions and Future Work

5. 1 Conclusions

In this dissertation, we explore reliable information transmission and efficient medium
access issues in wireless communication networks.

Specifically, in Chapter 2 we investigate at the physical layer the channel esti-
mation and signal detection problem for time-varying channels, with the objective
to improving spectral efficiency with satisfying reliability. We reveal that channel
correlation can be exploited in a very simple way to jointly estimate channel response
and detect transmitted signals. High spectral efficiency can be achieved with sat-
isfying information transmission reliability, in terms of bit error rate and channel
tracking accuracy. Additional efforts are devoted to studying the extreme case when
the channel correlation is lost due to some abrupt changes. We propose an algorithm
to detect such abrupt changes and suppress the possible error propagation. The
proposed algorithms are demonstrated to be effective through simulations.

Next, going beyond the physical layer, we inspect in Chapter 3 the medium
access control problem yet in a fashion of joint MAC-PHY optimization. A novel
MAC protocol named hybrid ALOHA is proposed, where the slots are purposely
structured in order to improve network performance. Idle sections are introduced
to make it possible for collision-free channel estimation even when multiple users
transmit simultaneously in one slot. Improved channel estimation increases the MPR
capability and results in better system performances in terms of throughput, stability
and delay. It is demonstrated that as the length of the idle section is small compared

to that of the data section, the bandwidth cost introduced by the idle sections can be

100

compensated for by the increased MPR capability, and the throughput of the network
is greatly increased.

We then characterize in the stability region of hybrid ALOHA in the two-user
case and derive the sufficient condition for stability for the general finite-user case.
Characterization of the stability inner bound for the special N = 3 case is also present,
which is reduced to solving a general Riemann-Hilbert problem. Delay performance
for the two-user system is also studied under the general MPR model. We obtain the
”exact” delays of the asymmetric case, as well as the upper and lower delay bounds
for the symmetric system. The two bounds could be fairly close to each other under
certain conditions such as a strong MPR capability. When the MPR channel reduces
to the capture channel, the two bounds merge and we have the “exact” delay of the
system which coincides with the result in [N MT05].

Lastly, in Chapter 4, we studied joint optimization of source index assignment
and constellation design for overall input-output distortion minimizations in digital
wireless systems with analog inputs. It turns out that when systems which minimizes
the BER does not necessarily minimize the input-output distortion, non-uniform map-
ping to constellation with Gray codes plays a dominant role in source-aware non—
uniform information transmission. An unequal error protection scheme is proposed
and investigated in the uncoded and coding systems. Simulation results demonstrate
its effectiveness. Further, joint quantization-constellation design is considered un-
der the criterion of distortion minimization. The proposed method generalizes the
concept of constellation design from the perspective of joint source-channel coding.
The simplicity and power efliciency are two major features of the proposed schemes,
making them particularly attractive for systems with tight power constraints, such

as the wireless sensor networks.

5.2 Future Work

We propose the following extensions to the work presented in the dissertation.

101

Extensions in PHY-Aware MAC Design

0 In Chapter 3, we characterize the stability region and the delay performance for
the simplest cases. General results for arbitrary users system deserve further

investigation.

0 We have derived the delays of the two-user system for given transmission prob-
abilities. Future work can be concentrated on finding the optimal transmission

probabilities which minimize the delays.

0 As the proposed hybrid ALOHA slot is structured in time domain, extension to
the frequency domain could lead to interesting results. The problem reduces to
the medium access control design under the OF DMA framework and deserves

thorough investigation.

Further Directions in Joint Source-Channel Coding Design

0 In Chapter 4, performance of the proposed information transmission scheme can
be further studied under more complicated channel conditions. Exploitation
of space and frequency diversities can be investigated. One further research
direction is the analysis of the relationship between source rate, transmit power
and average distortion. The specifically interesting topic is how to distribute
power among different classes of bits to minimize the average distortion, when
the source rate is fixed and the average power is constrained. Information

theoretic analysis is expected to be largely involved.

102

APPENDICES

103

APPENDIX A

Alternative Proof of Proposition

3.1 for M = 2.

In this section, we calculate the throughput of the hybrid ALOHA system for M = 2,
based on the Bernoulli arrivals model.

According to the system model in Section 3.2, the behavior of hybrid ALOHA
can be modeled as a discrete-time Markov chain. Taking the number of backlogged
packets at the beginning of each hybrid ALOHA slot as the state, and the beginning
of each time slot as the transition time of the states [BG92], the throughput of the
system for M = 2 based on the Bernoulli arrivals model can be obtained as below.

Suppose there are m users. Let n be the number of backlogged users at the
beginning of a given time slot. Assume the users, either backlogged or unbacklogged,
transmit the training sequences independently. Let pb be the probability that the
backlogged user transmits the training sequence in either one of the M = 2 pilot sub-
slots. Let pu be the probability that each of the m — n unbacklogged users transmits
in either pilot sub-slot. Here we have assumed the transmissions in pilot sub—slots are
of equal probability, i.e., Pb = %.

Let Pu(n, i) be the probability that i unbacklogged users transmit packets in a
given pilot sub-slot, and Pb(n, i) be the probability that i backlogged users transmit

[BG92], then according to the assumptions above, the probabilities are given by

are 2') = (m ,- ")p:'.(1 — pu)(m_"_i)1 1.1.1)

aw) = (2)1110 — pom-i). (11.2)

104

Based on the Simplistic Assumption, the probability of successful transmission for

one user in one of the time slots is given by

also) = Pu(n11)Pu(n10)Pb(n10)2 + 13110110131101.1)P11(n10)2
+P,,(n, 0)2Pb(n, 1)Pb(n, 0) + 13,,(11, 0)2Pb(n, 0)Pb(n, 1)
= 2[Pu(n, 1)Pu(n, 0) Pb(n, 0)2 + 1),,(n, 0)2Pb(n, 1)Pb(n, 0)]
= 2 [(m — 1111110 — pui2<m"">*‘(1 - p1)?"

+n<1 wire-"bill -19b)2"’1]. (11.3)

where Pu(n, 1)Pu(n, 0)Pb(n, 0)2 represents the probability that only one unbacklogged
user transmits the training sequence in the first pilot sub-slot, and no one else, either
unbacklogged or backlogged, transmits in the same time slot. Other terms in the
above equation can be interpreted similarly.

The probability of successful transmission for exactly two users in one of the time

slots can be obtained as

Psucc(2) = P1101, 1)Pu(n1 0)P1(n1 0)P1(n1 1) + P1101. O)Pu('n1 1)Pb(n1 1)P11(n. 0)
+Pu(n,1)2Pb(n,0)2 + 13,,(11, 0)2Pb(n, 1)2
= 219,01, 1)Pu(n, 0)Pb(n, 0)Pb(n, 1) + 19.,(11, 1)2Pb(n, 0)2
+Pu(n, 0)2Pb(n, 1)2
= 2(m - n)npu(1 - pu)2(m’”)‘lpb(1 - 1202""
+(m — 11121230 — pure-">411 — 11)?"

+0 — pom-"M21120 — 1112"”. (11.4)

The average number of successfully transmitted packets per slot can then be calcu-

105

lated as

3...... = 1 - 13.1.00) + 2 . 10.11.12)
= <1 — pure-"WI — it)?“ [2(m — 10111.11 — p.011 - 121,)2
+2n(1 - 1210219110 - Pb) + 4(m - n)npupb(1 - Pu)(1 - Pb)
+2<m — 11121130 — m2 + 21121130 - 11.12]. (11.5)

For small x, the approximation (1 — x)("'1) z (1 — x)" z 12"”: holds. By
neglecting the higher order terms of the probabilities, Esucc can be approximated as

Esucc 2 e—[2(m-n)pu+2npb] ><

[2(m — n)2p,2, + 2n2pg + 4(m - n)npupb + 2(m — n)pu + 2npb].(A.6)
Let R(n) = 2(m — n)pu + 2npb, then
Esucc 2 e'Rinlénm)? + R(n)]. (A7)

where R(n) can be interpreted as the expected number of attempting transmissions
at state 11 of the Markov chain. The first term in R(n) is the attempting transmission
from unbacklogged users, and the second term corresponds to the attempts from
backlogged ones. As can be seen, the result coincides with that of (3.9).

When m —t 00 and the probabilities of the transmissions are small. The Poisson
approximation applies and the result in Proposition 3.1 can be alternatively obtained
as below.

Since 2p.“ is the total probability that unbacklogged users transmit in a given time
slot, assuming the packets arrival follows the Poisson process with overall arrival
rate of A packets per unit time, it is easy to know 2pu = 1 — e‘A(1+T)/m, where

e‘MHrl/m is the probability that no packets arrive during the previous time slot.

:13

Under the infinite-user model, i.e., m -> 00, using the approximation e" a: 1 — x,

106

 

and assuming p), is small, R(n) can be approximated as a function of r: R(r) %
A(1 + T) + 2npb z A(1 + r). The departure rate (i.e., the expected departures per
slot) is then given by

W) = 12...... = [Ref/2 + R(rile‘R“). (11.8)

which is identical to (3.9).

107

APPENDIX B

Proof of Lemma 3.1.

The proof is carried out by using the stochastic dominance argument. Let S denote
the original system of queues. To resolve the interactions between the queues, as
in [RE88, NMT05], we construct a hypothetical dominant system S’, in which one of
the queues continues to transmit dummy packets when the queue is empty. 8' domi-
nates 3 since the queue sizes in S’ are not necessarily smaller than those in S, given
that the two systems are identical in terms of arrivals and attempted transmissions.

Suppose user 1 in S’ transmits dummy packets when his queue is empty, then user
2 always sees a probability of success given by ug = pgp‘l q2|{2} + p1 pngum}. Under
the Simplistic Assumption, it is easy to have 92'] {,1} = 1 and qi|{1,2} = 0.5, i = 1,2.
Hence the probability of success for user 2 is 712 = p2p‘1 + p1p2/2 = p2 — p1 p2 / 2. The
probability of success for user 2 in S’ is always lower than that in system S, where
the probability of success for user 2 oscillates between p2 - p1p2/2 and p2, depending
on whether queue l is empty or not. Suppose the arrival rate for user 2 is A2. It is
easy to know that user 2 operates as a discrete-time M/M/l system and is stable if

and only if
A2 5 p2 - p1P2/2- (13.1)

If queue 2 is stable, according to the M / M / 1 formula, queue 2 is nonempty with a
probability of A2/‘tt2 = A2/ (p2 — p1 p2 / 2). And it is empty with probability 1— A2/U2.
User 1 sees a probability of success of p1 qlll = p1 when queue 2 is empty, and
P15291|1+P1P2€11|{1,2} = 191 — p1p2/2 when queue 2 is nonempty. It is shown in [RE88]

that a sufficient condition for the stability of queue l is that, the arrival rate of user

108

1, A1, be less than the average probability of success, which is given by

P1A2
2-m

 

P1(1 - /\2/U2) + (P1 - P1P2/2)(/\2/U2) = P1 - 1 (13-2)

i.e., user 1 is stable when

 

A
.1, 3 p1 - 2p: 31' (13.3)

Therefore, the dummy packet system is stable (with the possible exception of bound-

ary points) if and only if

/\
A1:SIH.-’;p1 2

 

1, A2 _<. 102 - P1P2/2- (B-4)

Exchanging the roles of user 1 and user 2 in the dominance system S’ , i.e., user 2
transmits dummy packets when the queue is empty, the stability conditions for 5’

become

A
A2 5 p2 — {fiz- A1 3 p1 — rum/2- (13.5)

By stochastic dominance, when S’ is stable, S is also stable. Hence (B4) and (B5)
are sufficient conditions for S to be stable.

On the other hand, these are also necessary conditions. The proof follows the
argument that as long as the queues in the systems are not empty, the dominant
system S’ and the original system S are “indistinguishable” [RE88]. Therefore, when
the conditions to maintain a stable S’ are violated, system S also becomes unstable.
Consequently, the conditions given in Lemma 3.1 are then necessary for stability as

well.

109

APPENDIX C

Proof of Proposition 3.2.

From Lemma 3.1, the stability region for a fixed transmission probability vector p
is known. To find the union of all the stability regions as p varies over [0,1]2, a
constrained optimization problem is formed as below. Under the constraints (BA)
and (B5), we fix one rate, say A1, and maximize the other rate A2 as p varies over
[0,1]2. Hence a stability region 61 is obtained. Exchanging the roles of A1 and A2,
another stability region 62 can be obtained. 61 O 62 produces (‘3 H .A L0 H A-

Write the boundary given by (B4) and (B5) as

101/\2

 

 

/\1=P1-2_p11OSA2SP2-P1P2/2- (C-I)
/\
/\2 = 192 - 219:1:2’ 0 _<_ x\1 S p1- P1P2/2- ((12)

In (C2), fixing A1 and differentiating A2 with respect to p2, we have

d/\2 _ 2A1

a— W (03’

Since 0 S A1 3 p1(1— p2/2), then 0 S 2A1/(2 — pg)2 5 pl/(2 — p2). Under the
constraint that 0 5 p1, pg 5 1, it is easy to know Elf-2% Z 0. Hence A2 is a monotonic
non-decreasing function with respect to p2. Since in (G2), p2 is maximized at p2 =

2(1— A1) for 0 _<_ A1 3 1/2, and at 1 for 1/2 g A131, we then have

)‘2,max =1’ ’\11 for 0 _<_ Al S L (0'4)

110

Similarly, the maximization for (Cl) gives

)‘l,max =1“ A21 for 0 S /\2 31- (C-5)

(O4) and (0.5) represent two overlapping regions, and the stability region for the
proposed protocol is then given by

GH—ALOHA = {(A1,/\2) : (A1,/\2) 2 (0,0), (A1, A2) lies below the line
/\1+/\2= l, OSAl $1}. (0.6)

111

APPENDIX D

Proof of Proposition 3.4.

Mathematical induction on N = |M| is applied to prove the claim. Assuming that
one transmits the training sequence in either pilot sub-slot with equal transmission
probability, we can easily see that the region given by (3.24) is the stability region
for N = 2 characterized in Section 3.4. Suppose M = {1,2} and ’P = {8,11} =
{{2}, {1}}. If P231 = 121,2 = %p,', then from (3.23) we have

Ps2ucc(pl = 1920 - 191) + (p2,1p1,2 + p2,2p1,1) = 192 - P1P2/21 (13-1)

and

Plume) = 111 [Pr{xtfi‘l) = 01+ (1 — pziPrixlfi‘l) = 1}]

+lP1,1P7‘{XUT/{2)) = ”We +P1,2PT{X(N(2)) = 1}P2,ll- (D3)

Let u2 = p2 — p1p2 / 2, then for A2 < P326479), the probability Pr{Ng Z 1} = Ag/ug.
We have

A2 1 A2

A
1 _ __2 _ _ _ _
Psucc(P) — p1[(1 ”2+0 172),,2 +2101192u2

— - “A? (0.3)

 

Hence we obtain the stability condition identical to (3.11). Similarly, the condition
of (3.12) can be obtained by performing the partition as 'P = {8,11} = {{1}, {2}}.
The union of the regions under these two partitions characterizes the stability region

given in Lemma 3.1. And this proves Proposition 3.4 in the case of N = 2.

112

Now apply induction on N and assume that the claim is true for hybrid ALOHA
systems with number of users less than N. We consider the dominant system 813
under the partition P = {SJJ}, and concentrate on proving the stability condition
for the system represented by N3; = (N2, N2). It is easy to know from the induction
arguments that N; is stable for A5 6 65, where A5 = (Ail, - - - ’Ailsl) with ik 6 S
for 1 S k g IS | Note that in the dominant system Op, the set of users restricted
to 8 are “decoupled” from those in LI, and they appear to be a smaller copy of the
original system with modified reception probabilities given by (3.21). Since IS I < N,
then by the induction hypothesis, the queues in 8 are stable if A3 6 63.

Let A3 6 63, then we know N2 is stationary and ergodic. Since the coin tosses
and packet reception events are independent from slot to slot, it follows from (3.22)
that if the process N35 is initialized from its unique stationary distribution, then for
any i G Ll, the process Y: (P) is also stationary and ergodic. By the Loynes Theorem,
it is shown that the persistent queue i is stable in GP when A,- < E[Y,-t(P)] =
33mm, where Pgucc(P) is given by (3.23).

Therefore, if A5 6 63 and i < P§W(P) for all i 6 LI, each queue in the dominant
system 67’ is stable. This implies the stability of the process N39 from Lemma 5
in [Szp94]. By virtue of the stochastic dominance, the original system is then also
stable. Since the partition P is arbitrary, the final condition for stability is the union

over all the partitions.

113

APPENDIX E

Formulation of Functional

Equation (3.27 )

Let 010(t) be a binary-valued random variable that takes value 1 if Nf > 0, N5 = 0

and the departure from queue 1 is successful. Similarly, D01 (t) is a binary-valued

random variable that takes value 1 if Ng > 0, Nf = 0 and the departure from queue

2 is successful. In the situation when both queues are nonempty, the binary-valued

variables Bil“) for i = 1, 2 take value 1 when departure from queue i is successful.

The recursive equations for Nit are given as

/1{+ Nf — 011(1),

t
[311
t+l _
N1 — t
fllr
and
[33.
Nt+l _ 'BE’
2 __

flé + N5 - 13100).
16% + Né "’ 0%“):

114

Nf =0,N§ = 0;
hit > 0, Nt =0;
1 2 (E1)
Nf =0, N5 > 0;
Nf > 0, N3 > 0.
N1 =0, N5 = 0;
Nt > 0, Nt = 0;
1 2 (13.2)
Nf =0, N5 > 0;

Nf >O,N.f,>0.

If a persistent user 3 exists, i.e., we investigate the partition P3, then from (El) and

(E2) we have

Ethi+lyN3+1> = 1311:"i y”5>{E(11Ni = 0. Nt = 0]) +
+E(2Ni1[Nf > 0, N5 = 0]) - [% +1 — A1] +
+E(yNit[Nf = 0,1115 > 0])-1%?- +1— A2] +
+E(xNIyN2t’1[Nf > 0, N5 > 0])

— — — — — — E.
Xlx+ +xy+1 A3 A4 A51}. (3)

where 1[] is the indicator function and

A1 = p1(fi3€1{1},{1}+P3‘1{1}I{1,3});
A2 = p2(133Q{2},{2}+P34{2}|{2,3})i
A3 = 191(13213361{1},{1}+P2173<I{1},{1,2} +5293q{1}|{113});
A4 = p2(fi1fi3¢1{2},{2} +P1173€I{2},{1.2} +1317’3‘1{2}|{2J‘3});

A5 = p1P2fi3¢1{1,2}.{1.2}'

Note that
03(00) = tlirn E(1[Nf = 0, N5 = 0]), (153.4)
—too
t
C3(x,0) — 03(00) = tlim E(eN11[N{ > 0, N5 = 0]), (13.5)
#00
t
C3(O,y) — 03(00) = tlim h(yNzuNf = 0. N; > 0]), (E6)
—too

t t
Gate.y)+03(o.0)—Gete.0)—Geto.y) =tlggoElxN11/N211Ni > 0. Nt > 01). (E7)

Assuming the Simplistic Assumption, from (E.3), it follows that
I{(1%100306.31) = a(x1y)03(0.y) + b(1r..1/)Gs(ar.0) + C(I.y)03(010)1 (153-8)

where K(x, y), a(x, y), b(x, y) and C(x, y) are given in (3.28).

115

APPENDIX F

Proof of Lemma 3.2

When y —+ 0",

AW) ~ [A1fi1P2(1-P3/2)l()\2+%);
Bron ~ l—A1a1psll—ps/2i—A1p—1—pgflloe+55);

- - :1
010+) ~ [A1E%2fll(x\2+72)-

 

 

(F.1)
Hence
t(0+,¢>) = —B(0+)—2cos¢\/A(O+)C(O+)
< -{[/\1131P2(1- 193/2) + Mag-2E]
+21/[A1151P2(1 - 123/2)] ' [Alwflflz + 3272-)
z —00, (F2)
that is, t(0+,¢) = —oo.
When y = 1, then
A(1) = A1ll—p1132(1—p3/2)-’3—1p22—fi31.
3(1) = on - 1)lP152(1- 123/21+ ”5%9-‘21 - 1,,
0(1) = 7\1[P1fi2(1-p3/2)+£1p22—fi§l- (11.3)
It can be easily seen that -B(1) = A(1) + C(l), hence t(1,¢) = —B(1) —

116

2 cos ¢1/A(1)C(1) > 0.

As y —+ 00,
140/) ~ /\1/\2Ay1
30!) ~ ”11011520 - 193/2) + :\1Al/\2y.
(30/) ~ :\1/\2P1132(1 — P3/2ly1 (R4)
then

t(y.¢) < -B(y) + 2\/2‘1(l/)C(y)
= -yA2{A1P1fi2(1 - P3/2) + :\1A - 21/(/—\1A)[/\1191172(1 - 103/2H}

= -yz\2(\mp1fiz(1 - 193/2) - my (R5)

 

 

Hence, t(oo,¢) < 0.

Consequently, t(y,¢) = 0 has at least two real roots r1(¢) and r2(¢) satisfying
0 < r1(¢) < 1 < r2(<,/>). Since y2t(y,¢)t(y,¢ + 1r) is a polynomial of degree four in
the variable y, it can be deduced that t(y,¢) has exactly two real roots, and this

completes the proof.

117

APPENDIX G

Proof of Lemma 3.3

The first part of the lemma results from the general theory of polynomials of two
complex variables.
The second assertion is proved by using Rouche’s theorem as below:

K (x, y) can be rewritten as

 

 

 

Ivy — xyF($1y)g(x1y)
K x, = , G.1
( y) xyF(x,y) ( )
where
’ 1— 2 - 1— 2 -
9(x1y) = p1p2( p3/ ) +p2191( ps/ ) +p1p2p3 + A. (G2)
:1: y 2xy

F0r|y|=1andy9é11lxl=L

libs/F(x. y)g(x. y)| = |(x/\1 + X1)(y/\2 + 7\2)[P1fi2(1 - p3/2)y
+p2r1(1 — 103/2n + @E + +Axyll
g 1
= Ixyl- ((3.3)

Based on Rouche’s theorem, this implies that for |y| = 1, y 71$ 1, there exists exactly
one 1:, |x| < 1 such that xy — xyF(x, y)g(x,y) = 0 and hence K(x, y) = 0.
For y =1, K(x,1)= 0 reduces to

:\1lP1132(1 - 173/?) + P1P - 2133/2]
All - 1911320 - 103/2) - p11) - 2133/2]

 

(x —1)(x — )= 0. (G4)

When A1 < p1p2(1 — p3/2) +p1p2p3/2 as implied by (3.34), x = 1 is the only root. Cl

118

APPENDIX H

Proof of Proposition 3.7.

Let N: denote the queue length of user i (i = 1, 2) at time slot t. Let 6: denote the
number of packets that arrive at the ith user’s queue in time slot t. Let F (x, y) be the
moment generating function of the joint arrival process. Thus, for lxl S 1, |y| 5 1,
t E N
fit fit .. _
F(sail) = EC": 131 2) = (Iv/\+/\)(y/\+/\), (Hi)

where A = 1 — A. From the queue evolution equation (3.5), it can be seen that

t+l t+1
Elle 1N2 ) = F(z.y)lE(1[Ni = 01Nt= 01)
t
#2: +1 — pa)E($N11[Ni > 01 N5 = 0])
t
a? +1 - pa)E(yN211Nf = 0. Ni > 0])

2
+<<pa +1120 — a))(-:-+ 51+ 3,; +1 — 201a + 112(1) — a» — 11%))

t t
xE(s~N1yN21[Nf > 0, N5 > 0])], (H2)

where 1[] is the indicator function. According to Lemma 1 in [NMT05], if A <
pa+p2(b+c—a), then the system is stable. Since (N f, N5) is an irreducible, aperiodic
Markov chain, stability is equivalent to existence of a unique stationary (limiting)
distribution. Let G(x, y) be the moment generating function of the joint stationary

queue process, viz,

t t
G(m) = tlim E(xN1yN2). (H.3)
—*00
Note that
G(0,0) = tlim E(1[Nf = 0, N5 = 0]), (11.4)
—*00

119

G(x, 0) -— G(O, 0) 31111.10 E(xNi1[Nf > 0, N5 = 0]), (11.5)

G(O, y) — G(O, 0) = £11310 E(yNi1[N{ = 0, N; > 0]), (11.6)

C(x,y) + G(0,0) — G(x,0) — G(O, y) = 3120 E(leyN51[Nf > 0, N; > 0]). (11.7)
From (H.2), it follows that

G(x, y) = F(x1y){0(x1y)[G(xsi/) + G(010) - G(x10) - G(O1y)l
+B(x. y)[G(0. y) - G(010)] + A(xiyllG($10) - G(010)] + G(O1O)IH.8)

where

A($,y) = %+1—pa1
303.11) = $+1-pa.

2C
C(m) = [pa + 112(1) — a)](-:- + 5) + i—y +1 — 21,111 + 112(1) — 0.)] — 1121;. (11.9)

Using the symmetry property of G(x,y), we have C(1,1) = 1 and C(1,0) = C(0,1).
In (H.8), let y = 1 and take derivative with respect to x at both sides and then let
x = 1, we find

(20 — pa)C(1,0) — (l9 — pa)G(0,0) = 9 — A, (H.10)

where 0 = pa + p2(b + c — a). Furthermore, (H.8) can be rewritten as

_ F(w1y) _ _
G(x1y)— 1-F(x1y)C(x.y) >< {C(x1v)[G(010) G(rr10) G(0.y)l+

B(x, y)[C(O,y) — C(O, 0)] + A(x, y)[C(x, 0) - C(O, 0)] + C(0,0)}H.11)

 

Let Gl(x,y) E dC(x,y)/dx. In (H.11), letting y = 1, taking the derivative with
respect to x and then letting it = 1, we obtain

p2(b + c — a)G’1(1,0) + AA

01011): 9_)\

 

(11.12)

120

Based on (H.11), a more tedious calculation will lead to the following result.

 

 

 

 

 

G(x,:r)| _ 2A+(20—pa)01(1,0) A2+2A —4A9+p2c
d2: “‘1‘ 9—) 2(0—A)
2 1
p c[G(1,0) — 20(0,0)]
0 _ ,\ . (H.13)
If we use the fact that
G(jf)lx=1= 01(1,1)+ 02(1, 1) = 201(1, 1), (11.14)

and associate with the result from (H.12), we can solve for Gl(l,0) and 01(1, 1) to

obtain

2A0 - A2pa — A20 p3c(b + c — a)[G(1, 1) + G(0,0) — G(1,0) — G(0,1)]
2pa(0 — A) " 20(0 — A) '
(H.15)

Since 630, 1) is equal to the mean queue length of the users, applying Little’s The-

01(1, 1) =

 

orem [Lit61], we have the average delay D as

 

_ G1(1,1)_1a(1 — A) +p(b+c— a)(1 — A/2)
D— A —a[ pa+p2(b+c—a)—A 1+¢’ (H.165)
where
¢ ___ _p3c(b + c — a)[G(1, 1) + G(0,0) — G(1,0) — G(0,1)]. (11.17)

 

2ar(pa + p2(b + c — a) - A)
Since G(1,1) + G(0,0) — G(1,0) - G(O, 1) = limtsoo E(1[Nf > 0,1v5 > 0] (as (11.7)

implies), associated with b + c — a < O and A < pa + 132(1) + c — a), we then conclude

 

 

that 3
—p C(b + c — a)

0 < < . H.18
_¢_2ar[pa+p2(b+c—a)-A] ( )

Therefore, the average delay is lower bounded by

1a(1— A) +p(b+ c — a)(1 — A/2)

D = — , H.19
Lower al pa+p2(b+c—a)—A ] ( )

121

and upper bounded by

p3c(b + c — a)
2ar[pa + p2(b + c — a) — A].
(11.20)

D _1[a(1—A)+p(b+c—a)(l—A/2)
Upper—a pa+p2(b+c—a)—A

 

]_

 

From the analysis above, we see that the bounds become the exact delay of the system

when G = 0 or 11111,...)O E(1[Nf > 0, N5 > 0]) = 0.

122

BIBLIOGRAPHY

123

[Abr70]

[ADOl]

[AGR98]

[AM79]

[Ana91]

[ATO5]

[BG92]

[Cap79]

[CB83]

[CEPBO2]

[ChoOO]

BIBLIOGRAPHY

N. Abramson. The aloha system - another alternative for computer
communications. In Proc. Fall Joint Comput. Conf., AFIPS Conf, vol-
ume 44, pages 281- 285, Montvale, NJ, 1970.

D. E. Ayyildiz and H. Delic. Adaptive random-access algorithm with
improved delay performance. Int. J. Commun. Syst., 14:531m539, Jun
2001.

P. D. Alexander, A. J. Grant, and M. C. Reed. Iterative detection in
code division multiple access with error control coding. European Trans.
Telecommun., 924191425, Sept/ Oct 1998.

B. D. 0. Anderson and J. R. Moore, editors. Optimal filtering. Prentice
Hall, NJ, 1979.

V. Anantharam. Stability region of the finite user slotted ALOHA pro-
tocol. IEEE Trans. Inform. Theory, 37:535-540, May 1991.

S. Adireddy and L. Tong. Exploiting decentralized channel state infor-
mation for random access. IEEE Tinns. Inform. Theory, 512537561,
Feb 2005.

D. Bertsekas and R. Gallager. Data Networks. Prentice Hall, Upper
Saddle River, NJ, 2nd edition, 1992.

J. I. Capetanakis. Tree algorithms for packet broadcast channels. IEEE
Trans. Inform. Theory, 25:505 515, Sept 1979.

J. W. Cohen and O. J. Boxma. Boundary value problems in queueing sys-
tem analysis. North-Holland mathematics studies, 79. North-Holland,
New York, Oxford, 1983.

S. Coleri, M. Ergen, A. Puri, and A. Bahai. Channel estimation tech-
niques based on pilot arrangement in OFDM systems. IEEE Trans.
Broadcasting, 48:223~229, 2002.

J. Choi. Channel estimation for coherent multi-carrier CDMA systems
over fast fading channels. In Proc. IEEE Vehicular Technology Confer-
ence (VTC'), volume 1, pages 400-404, Tokyo, Japan, May 2000.

124

[011301]

[Cov72]

[CYO2]

[EH98]

[EZ87]

(ch1}

[F179]

[F1363]

[FV87]

[FW89]

[Ga185]

[GL03]

J. Cai, J. W. Mark, and X. Shen. Fast fading channel estimation in
multicarrier-CDMA systems. In Proc. IEEE Global Telecommunica-
tions Conference (GLOBECOM), volume 5, pages 3135~3139, November
2001.

T. M. Cover. Broadcast channels. IEEE Trans. Inform. Theory, IT-
18:2—14, Jan 1972.

K. Cho and D. Yoon. On the general BER expression of one- and two-
dimensional amplitude modulations. IEEE Trans. Commun, 50:1074
1080, Jul 2002.

A. Ephremides and B. Hajek. Information theory and communication
networks: An unconsummated union. IEEE Trans. Inform. Theory,
44:2416—2434, Oct 1998.

A. Ephremides and R. Z. Zhu. Delay analysis of interacting queues with
an approximate model. IEEE Trans. Commun, COM-35:194—~201, Feb
1987.

M. Peder and J .A. Catipovic. Algorithms for joint channel estimation
and data recovery - application to equalization in underwater communi-
cations. IEEE Journal of Oceanic Engineering, 16:42~55, January 1991.

G. F ayolle and R. Iasnagorodski. Two coupled processes: The reduc-
tion to a riemann-hilbert problem. In Z. Wahrscheinlichkeitstheorie,
volume 47, pages 325—351, 1979.

M. Fisz. Probability theory and mathematical statistics. Wiley publica-
tions in statistics. New York, Wiley, 3rd edition, 1963.

N. Farvardin and V. Vaishampayan. Optimal quantizer design for noisy
channels: an approach to combined source-channel coding. IEEE Trans.
Inform. Theory, 35:827—838, Nov 1987.

G. D. Fomey and Lee-Fang Wei. Multidimensional constellations - Part
I: Introduction, figures of merit, and generalized cross constellations.
IEEE Trans. Inform. Theory, 7:877- 892, Aug 1989.

R. Gallager. A perspective on multiaccess channels. IEEE Trans. 1n-
forrn. Theory, IT-31:124~142, Mar 1985.

D. Gu and C. Leung. Performance analysis of transmit diversity scheme
with imperfect channel estimation. Elect. Lett., 39:42(P403, Feb 2003.

125

[cm]

[Gvsss]

[ovss9]

[HG81]

[HKR97]

[HK889]

[Hlu82]

[HP97]

[IF91]

[11190]

[IM96]

[Jak74]

M. Grossglauser and D. Tse. Mobility increases the capacity of wireless
adhoc networks. IEEE/ACM Trans. networking, 10:477 -486, Aug 2002.

S. Ghez, S. Verdu, and S. Schwartz. Stability properties of slotted
ALOHA with multipacket reception capability. IEEE Trans. Automat.
Cont., 33:640~649, Jul 1988.

S. Ghez, S. Verdfi, and S. Schwartz. Optimal decentralized control in
the random access multipacket channel. IEEE Trans. Automat. Cont,
34:1153~-1163, Nov 1989.

M. G. Hluchyj and R. G. Gallager. Multiaccess of a slotted channel
by finitely many users. In Proc. Nat. Telecommunications Conf., pages
D4.2.1—D4.2.7, New Orleans, LA, Aug 1981.

P. Hoeher, S. Kaiser, and P. Robertson. Two-dimensional pilot-symbol-
aided channel estimation by Wiener filtering. In Proc. IEEE Int. Conf.
on Acustics, Speech and Signal Processing (ICASSP), volume 3, pages
1845* 1848, April 1997.

I. M. I. Habbab, M. Kavehrad, and C. E. W. Sundberg. ALOHA with
capture over slow and fast fading radio channels with coding and diver-
sity. IEEE J. Select. Areas Commun, 7:79 788, Jan 1989.

M. G. Hluchyj. Multiple access window protocol: Analysis for large
finite populations. In Proc. IEEE Conf. Decision and Control, pages
589- 595, New York, 1982.

S. Hara and R. Prasad. Overview of Multicarrier CDMA. IEEE Com-
mun. Mag., 3521267 133, December 1997.

R. A. Iltis and A. W. Fuxjaeger. A digital DS spread-spectrum receiver
with joint channel and Doppler shift estimation. IEEE Trans. Commun,
39:1255 1267, August 1991.

R. A. Iltis. Joint estimation of PN code delay and multipath using the
extended Kalman filter. IEEE Thans. Commun., 38:1677 11685, October
1990.

R. A. Iltis and L. Mailaender. Multiuser detection of quasi-synchronous
CDMA signals using linear decorrelators. IEEE Trans. Commun,
44:1561 1571, November 1996.

W. C. Jakas, editor. Microwave Mobile Communications. IEEE Piscat-
away, New York, 1974.

126

[KH95]

[KH97]

[K102]

[KSP03]

[KV94]

[KY78]

[LE99]

[Lit61]

[LJS98]

[LLCL99]

[Loy62]

[LPK89]

R. Knopp and P. Humblet. Information capacity and power control
in single cell multi-user communications. In Proc. Intl. Conf. Comm,
pages 331 335, Seattle, WA, Jun 1995.

S. Kaiser and P. Hoeher. Performance of multicarrier CDMA with chan-
nel estimation in two dimensions. In Proc. IEEE int. Symp. on Personal,
Indoor and Mobile Radio Communications (PIMRC), pages 115419,
1997.

K. Kim and R. A. Iltis. Joint detection and channel estimation algo—
rithms for QS—CDMA signals over time-varying channels. IEEE Trans.
Commun., 50:845-855, May 2002.

D. N. Kalofonos, M. Sto j anovic, and J. Proakis. Performance of adaptive
MC—CDMA detectors in rapidly fading Rayleigh channels. IEEE Trans.
Wireless Commun., 2:229—239, March 2003.

G. K. Kaleh and R. Vallet. Joint parameter estimation and symbol

detection for linear or nonlinear unknown channels. IEEE Trans. Com-
mun., 42:2406 2413, 1994.

L. Kleinrock and Y. Yemini. An optimal adaptive scheme for multiple
access broadcast communications. In Proc. Int. Conf. Communications,
pages 7.2.1—7.2.5, Jun 1978.

W. Luo and A. Ephremides. Stability of N interacting queues in random-
access systems. IEEE Trans. Inform. Theory, 45:1579-1587, Jul 1999.

J. D. C. Little. A proof for the queueing formula L = AW. 0p. Res. 9,
pages 383—387, 1961.

Y. Li, L. J. Cimini. Jr., and N. R. Sollenberger. Robust channel esti-
mation for OFDM systems with rapid dispersive fading channels. IEEE
Trans. Commun., 462902-915, July 1998.

J. Lu, K. B. Letaief, J. C-I Chuang, and M. L. Liou. M-PSK and
M-QAM BER computation using signal-space concepts. IEEE Trans.
Commun., 47:181—184, Feb 1999.

R. M. Loynes. The stability of a queue with non-independent inter-
arrival and service times. Proc. Cambridge Philos. Soc., 58:497 520,
1962.

D. F. Lyons and P. Papantoni—Kazakos. A window random access algo-
rithm for environments with capture. IEEE Trans. Commun., 37:766-
770, Jul 1989.

127

[Mes79]

[Met 76]

[Moh98]

[MT05]

[Mus53]

[MW67]

[MZFLIOOa]

[MZFLIOOb]

[Nai85]

[NMT05]

[PFM93]

[PPK89]

D. G. Messerschmitt. Accumulation of distortion in tandem communi-
cation links. IEEE Trans. Inform. Theory, IT—25z692—698, Nov 1979.

J. L. Metzner. On improving utilization in ALOHA networks. IEEE
Trans. Commun., COM—24:447—448, Apr 1976.

M. Moher. An iterative multiuser decoder for near-capacity communi-
cations. IEEE Trans. Commun., 46:870~880, July 1998.

G. Mergen and L. Tong. Stability and capacity of regular wireless net-
works. IEEE Trans. Inform. Theory, 51:1938~1953, Jun 2005.

N. I. Mushkelishvili. Singular integral equation. Noordhoff, Groningcn,
1953.

B. Masnick and J. Wolf. On linear unequal error protection codes. IEEE
Transactions on Information Theory, 13:600—607, October 1967.

R. H. Morelos—Zaragoza, M. P. C. Fossorier, S. Lin, and H. Imai. Mul-
tilevel coded modulation for unequal error protection and multistage

decoding .i. symmetric constellations. IEEE Trans. Commun., 48:204
213, Feb 2000.

R. H. Morelos-Zaragoza, M. P. C. Fossorier, S. Lin, and H. Imai. Mul-
tilevel coded modulation for unequal error protection and multistage

decoding. ii. asymmetric constellations. IEEE Trans. Commun., 48:774—
786, May 2000.

P. Nain. Analysis of a two node ALOHA network with infinite capacity
buffers. In Proc. Int. Sem. Computer Netwkg., pages 2.2.1—2.2.16, Tokyo,
Japan,1985.

V. Naware, G. Mergen, and L. Tong. Stability and delay of finite user
slotted ALOHA with multipacket reception. IEEE Trans. Inform. The-
ory, 51:2636—2656, Jul 2005.

N. Phamdo, N. Farvardin, and T. Moriya. A unified approach to tree
structured and multistage vector quantization for noisy channels. IEEE
Trans. Inform. Theory, 39:835—850, May 1993.

M. Paterakis and P. Papantoni-Kazakos. A simple window random-
access algorithm with advantageous properties. IEEE Trans. Inform.
Theory, 35:112411130, Sept 1989.

128

[Q3011

[RE88]

[Rob72]

[ROUV93]

[RPT95]

[RSAA97]

[RSG87]

[8085]

[SMMO4]

[8883]

[SSOO]

[Ste92]

X. Qin and R. Berry. Exploiting multiuser diversity in wireless ALOHA
networks. In Proc. Allerton Conf. Communication, Control and Com-
puting, pages 793—794, Allerton, IL, Oct 2001.

R. Rao and A. Ephremides On the stability of interacting queues in
a multi-access system. IEEE Trans. Inform. Theory, 34:918—930, Sept
1988.

L. G. Roberts. Aloha packet system with and without slots and cap-
ture. Stanford Research Institute, Advanced Research Projects Agency,
Network Information Center, 1972. ASS Note 8.

K. Ramchandran, A. Ortega, K. M. Uz, and M. Vetterli. Multiresolution
broadcast for digital HDTV using joint source/ channel coding. IEEE J.
Select Areas Commun., 11:6—-23, Jan 1993.

R. Raheli, A. Polydoros, and C. Tzou. Per-survivor processing: A gen-
eral approach to MLSE in uncertain environments. IEEE Trans. Com-
mun., 43:354-364, Feb/Mar/Apr 1995.

M. C. Reed, C. B. Schlegel, P. D. Alexander, and J. A. Asenstorfer.
Iterative multiuser detection for DS-CDMA with FEC. In Proc. Int.
Symp. Turbo Codes and Related Topics, pages 162—165, Brest, France,
1997.

B. Ramamurthi, A. M. Saleh, and D. J. Goodman. Perfect capture
ALOHA for local radio communications. IEEE J. Select. Areas Com-
mun., SAC-5:806—813, Jun 1987.

M. Sidi and I. Cidon. Splitting protocols in presence of capture. IEEE
Trans. Inform. Theory, IT-3lz295—301, Mar 1985.

L. Sanguinetti, M. Morelli, and U. Mengali. Channel estimation and
tracking for MC-CDMA signals. European Trans. Telecommun, 15:249--
258, May 2004.

M. Sidi and A. Segall. Two interfering queues in packet-radio networks.
IEEE Trans. Commun., COM-31:123—129, Jan 1983.

J. Sant and V. Sharma. Performance analysis of a slotted-ALOHA pro-
tocol on a capture channel with fading. Queueing Systems, Theory and
Applications, 34:1135, 2000.

R. Steel. Mobile Radio Communications. IEEE press, New York, 1992.

129

[svm]

[Szp86]

[Szp94]

[TE93]

[TGZ96]

[TH98]

[TM79]

[TNVO4]

[T899]

[VA91]

[VD98]

S. Shamai and S. Verdu. The impact of frequency-flat fading on the
spectral efficiency of CDMA. IEEE Trans. Inform. Theory, 47:1302---
1327, Sept 2001.

W. Szpankowski. Bounds for queue lengths in a contention packet broad-
cast system. IEEE Trans. Commun., pages 1132—1140, Nov 1986.

W. Szpankowski. Stability conditions for some multiqueue distributed
systems: buffered random access systems. Adv. Appl. Probab., 26:498--
515, Jun 1994.

L. Tassiulas and A. Ephremides. Dynamic server allocation to paral-
lel queues with randomly varying connectivity. IEEE Trans; Inform.
Theory, 3924667478, Mar 1993.

M. K. Tsatsanis, G. B. Giannakis, and G. Zhou. Estimation and equal-
ization of fading channels with random coefficients. In Proc. IEEE Int.
Conf. on Acustics, Speech and Signal Processing (ICASSP), volume 2,
pages 10934096, May 1996.

D. N. C. Tse and S. V. Hanly. Multiaccess fading channels. i. polyma-
troid structure, optimal resource allocation and throughput capacities.
IEEE Trans. Inform. Theory, 44:2796w2815, Nov 1998.

B. S. Tsybakov and V. A. Mikhailov. Ergodicity of slotted ALOHA
system. Problems of Information Transmission, 15:73 87, Mar 1979.

L. Tong, V. Naware, and P. Venkitasubramaniam. Signal processing in
random access. IEEE Signal Processing Magazine, pages 2939, Sept
2004.

I. E. Telatar and S. Shamai. Some information theoretic aspects of
decentralized power control in multiple access fading channels. In Proc.
Inform. Theory and Networking Workshop, pages 23—23, Piscataway,
NJ, 1999.

M. K. Varanasi and B. Aazhang. Near-optimum detection in syn-
chronous code division multiple access systems. IEEE Trans. Commun.,
39:725fi736, May 1991.

M. C. Valenti and B. D.Woerner. Iterative multiuser detection for con-
volutionally coded asynchronous DS—CDMA. In Proc. IEEE Int. Symp.
Personal, Indoor, and Mobile Radio Communications (PIMRC), pages
213—217, Boston, MA, Sept 1998.

130

[VNT04]

[VT95]

[WF94]

[wc00]

[WP98]

[WP99]

[YDOO]

[YHOO]

[YLF93]

[zoss]

[ZG93]

[Zor95]

[ZR94]

G. Mergen V. Naware and L. Tong. Stability and delay of finite user
slotted ALOHA with multipacket reception. Tech. Rep. ACSP-TR—08-
04-01, Cornell Univ., Ithaca, NY, 2004.

G. M. Vitetta and D. P. Taylor. Maximum likelihood decoding of un-
coded and coded PSK signal sequences transmitted over Rayleigh flat—
fading channels. IEEE Trans. Commun., 43:2750—2758, November 1995.

M. Wang and T. R. Fischer. Trellis-coded quantization designed for
noisy channels. IEEE Trans. Inform. Theory, 40:1792~1802, Nov 1994.

Z. Wang and G. B. Giannakis. Wireless multicarrier communications:
where Fourier meets Shannon. IEEE Signal Processing Mag., 17:29—48,
May 2000.

X. Wang and H. V. Poor. Adaptive joint multiuser detection and channel
estimation in multipath fading CDMA channels. Wireless Networks,
42453470, 1998.

X. Wang and H. V. Poor. Iterative (turbo) soft interference cancellation
and decoding for coded CDMA. IEEE Trans. Commun., 47:1046—1061,
1999.

B. Yucel and H. Delic. Mobile radio window random-access algorithm
with diversity. IEEE Trans. Veh. Technol., 49:2060—2070, Nov 2000.

L. Yang and L. Hanzo. A recursive algorithm for the error probability
evaluation of M-QAM. IEEE Commun. Lett., 4:304~306, Oct 2000.

N. Yee, J-P. Linnartz, and G. Fettweis. Multi-carrier CDMA in in-
door wireless radio networks. In Proc. IEEE int. Symp. on Personal,
Indoor and Mobile Radio Communications (PIMRC), pages 109- 113,
Yokohama, Japan, Sept 1993.

K. Zeger and A. Gersho. Vector quantization design for memoryless
noisy channels. In Proc. IEEE Int. Conf. Commun., pages 1593—1597,
Philadelphia, PA, Jun 1988.

K. Zeger and A. Gersho. Pseudo-gray coding. IEEE Trans. Commun.,
38(12):2147—2158, Dec 1993.

M. Zorzi. Mobile radio slotted ALOHA with capture and diversity.
Wireless Networks, 1:227—239, May 1995.

M. Zorzi and R.R.Rao. Capture and retransmission control in mobile
radio. IEEE J. Select. Areas Commun., SAC-12:1289—1298, 1994.

131

[ZT03a] Q. Zhao and L. Tong. A dynamic queue protocol for multiaccess wireless
networks with multipacket reception. IEEE Trans. Wireless Commun.,
11:12.5: 137, Feb 2003.

[ZT03b] Q. Zhao and L. Tong. A multiqueue service room MAC protocol for
wireless networks with multipacket reception. IEEE/ACM Trans. Net-
working, 11.125437, Feb 2003.

132

 

 

   

["[[]]]][]][]][[1]]