PHY-MAC dialogue with Multi-Packet Reception
1 2Marc Realp and Ana I. Pérez-Neira
12CTTC-Centre Tecnològic de Telecomunicacions de Department of Signal Theory and Communications
Catalunya Politechnic University of Catalonia (UPC)
Edifici Nexus Campus Nord-mòdul D5
C/Gran Capità, 2-4 C/Jordi Girona,1-3
Abstract.- Cross-layer design has been considered these probabilities can be obtained from bit error recently as a new approach when designing MAC rate and binomial distributions. Some MAC protocols in systems with diversity such as CDMA. algorithms are developed based on this MPR matrix This paper goes one step further in the cross layer and hence, PHY-MAC dialogue reduces to a BER design by proposing a PHY-MAC dialogue involving exchange. The work in  is perhaps the first to the exchange of parameters such as BER and active introduce the concept of MPR matrix. In this article, users. By means of this PHY-MAC dialogue, system modifications of the retransmission probability of performance can be improved. A two-stage receiver is the Aloha protocol are presented. In  and  new used at PHY level. The first stage tracks active users MAC proposals are shown. In , the Dynamic while the second stage is a data demodulator. The
Modified Dynamic Queue Protocol (MDQP) is Queue Protocol (DQP) is described. Assuming that proposed as the MAC protocol of our system. When each user has a probability q to have a packet the knowledge of active users is possible, it is waiting for transmission and considering the MPR demonstrated by simulations that MDQP outperforms matrix, an optimal user access set is obtained which DQP. minimises packet delay and maximises network throughput. Besides, QoS constraints are included I. Introduction in . An improved zero forcing estimator for In wireless random access channels, a CDMA is developed in . That is a two-stage common channel is shared by many users. The multi user detector based on traffic burstiness conventional assumption on the reception capability theory: i)In the first stage, active users are detected of the common channel is that when two or more by means of both power detection and traffic packets are transmitted simultaneously a collision information. ii)In the second stage, a zero forcing occurs and consequently, the information is lost. To estimator is implemented using the active users’ recover the information, the colliding packets have signature vectors only. to be retransmitted involving undesired effects on Our goal is to go one step further on the the throughput and packet delay of the network. cross-layer design in order to achieve even better Many current signal processing techniques performances. Basically, by means of PHY-MAC introduce multi-packet reception capability at dialogue, system performance can be improved. physical layer by means of spatial, time, frequency Since the problem of detecting active users or code diversity. The improvement in throughput in a dynamic CDMA system is not new ,,, performance when spatial or code diversity is we propose to use the knowledge of active users as introduced is demonstrated in ,,. However, an information parameter to improve MAC none of them consider cross-layer design, i.e., the efficiency. In our work, the first stage of the traffic-MAC techniques applied are still working under the aided multi user detector for CDMA presented in  conventional assumption of collision. The idea of is considered. Changes from CDMA to spatial cross-layer design is based on the interaction diversity systems are straightforward. between layers in order to improve system On the other hand, the DQP in  has been performance. modified and used as the reference MAC protocol Many articles in the literature make of our system to demonstrate the improvements reference to the physical layer packet reception achieved using PHY-MAC information. capability by using the so called multi packet The organisation of this paper is as follows. reception (MPR) matrix. Each element of this In the next section, the concept of the MPR matrix matrix is the probability of successfully receive k is described thoroughly and a PHY-MAC dialogue packets when n packets have been sent. Basically, is proposed. In section III the modified dynamic
MAC queue protocol is presented. Section IV gives some
simulations to show the improvements achieved by
means of PHY-MAC dialogue. Conclusions are Active N BER i given in section V. Users
II. Multi-Packet Reception PHY
The MPR matrix is the tool used to
Figure 1. PHY-MAC dialogue describe the capability of the receiver to detect
more than one packet simultaneously. Considering
a system with M users and that the channel is such (6) ！，arg(max)C;；that the probability of receiving k packets 0n，nM1,..,successfully when there are n transmissions depends only on the transmitted packets, the gives the number of packets that should be following probability can be defined, transmitted simultaneously to achieve channel capacity. CPk，[ packets are correctly received | nk,Since the MPR matrix entries depend on
the packet success probability and consequently on (1) n packets are transmitted]the bit error rate (BER), the BER exchange between 1(num. of users) ; 0；；；；nMknPHY and MAC is implicit when a MAC algorithm uses the MPR matrix . If the packet success probability (Ps(n)) of one On the other hand, by means of the first packet is independent of the others, C can be n,kstage of the receiver presented in , it is possible computed analytically as, to detect the active users in a slot. Assuming no error in the knowledge of the active users, this
additional information is used at MAC level to CBknPsn，(,,()) (2) nk,improve system performance. The Information flows between PHY and Where B(k,n,Ps(n)) denote de binomial distribution MAC layers of our system are described in figure 1. with probability Ps(n), i.e, Parameter N refers to the optimal size of the users i access set as described by the MDQP in section III. n~?The knowledge of the N at the physical layer could knk？i (3) (,,())()(1())BknPsnPsnPsn，？?，be used to focus the active users’ search on the N ik??polled users. In essence, it could be used to simplify MUD user codes selection in the second stage of Then, the MPR matrix can be defined as, the receiver in . However, we focused our work in the design of a more efficient MAC protocol by CC00~?means of the information obtained from the 1,01,1?，physical layer. CCC02,02,12,2?， ?，C， III. Modified Dynamic Queue Protocol ?， 0?，III.a MDQP Vs DQP ?， CC,0,MMM??We consider the DQP as the basis for the Modified DQP (MDQP). The DQP is described in If the expected number of correctly received . It is designed for a system with M users (or packets when n packets are sent is defined as, nodes) who transmit data to a central controller. The DQP divides the time axis in ntransmission periods (TP). In each TP, the packets (4) CkC，；nnk,generated in the previous TP are transmitted. A TP ，k1ends when all the M users of the system have been polled and the packets generated in the previous TP Then, the capacity of the channel is have been successfully received. An example is given in figure 2. (5) ！，maxC;；nP is defined as the probability of a node to ，1,..,nMgenerate a packet in a slot and qis the probability i of a node to have a packet waiting for transmission and consequently, at the beginning of the ith TP. Then,
buffers or their packets are lost due to collision. The Transmit Transmit Transmit MAC protocol polls nodes 1 and 5 again even packets packets packets though they have empty buffers. When all the generated generated generated
before 0 in (0,2] in (2,4] nodes polled in a slot have empty buffers then, the
central controller determines that non of the polled
nodes have a packet waiting to be transmitted.
Opposite to that, by means of the user
activity detector in the MDQP, the central First TP Second TP Third TP controller is able to determine that nodes 1 and 5 L1=2 L2=3 L3=5
have not transmitted a packet in the first slot and Figure 2. DQP Transmission Period
consequently they are processed and not polled
again. Since the time taken to transmit all the
packets with the MDQP is shorter, throughput and L i？1 (7) qP，？？1(1)ipacket delay are improved. where L is the length of the previous TP. i-1III.b The optimal size of the access set The basic structure of this protocol is a waiting queue where all users are processed in The procedure to determine the optimal groups of access set size (N). Based on q and the ii) is the same as in the DQP. size of the access set (NiMPR matrix, the value of N is chosen so that the iThe N for the ith TP is chosen so that the expected iexpected length for the ith TP is minimised. length of that TP is minimised. N is then, iWhen processing the received packets, the DQP assumes that the central controller is capable (8) NELqN，argmin[ | ,]iiito distinguish between empty slots and non-empty ，(，1,..,NMslots. In the case of a non-empty slot, the central controller is only capable to determine the users of where E[L|N] is the expected length of the ith TP ithe access set who have successfully transmitted when the size of the access is N. their packet in the current slot. On the contrary, in a It can be shown that a finite state discrete non-empty slot, the central controller is incapable to Markov chain can be formed with states (j,k). determine whether the remaining users in the access Where j (M ， j ，0) determines the number of set have transmitted a packet with a collision or unprocessed users at the beginning of one slot and k have not transmitted any packet. (N ， k ，0) determines the number of packets to be On the other hand, with the additional transmitted in that slot. information about users activity given by the The transition probability from state (j,k) physical layer of our system, the central controller to state (l,m) is different depending if we are is capable to distinguish users whose packets have dealing with the DQP protocol or with the MDQP. been transmitted successfully, users whose packets For the MDQP protocol that probability is given at have collided and users who have not transmitted. the bottom of this page. Consequently, the Hence, the assumptions made about the central transition probability matrix can be written as controller in DQP are no longer correct and must be modified. This is shown in figure 3. In that figure, I0~?the central controller sets Nopt to 3. In consequence, R，?，the users of the system are polled in groups of AN??three. For the DQP, the central controller can not distinguish whether node 1 and 5 have empty
Nwhere I denotes the transition probability from an
(10) E[Li|N] =(,,)(,)BkNqeMkabsorbing state to an absorbing state, i.e., the ；iidentity matrix (in our system the absorbing state is k=0
the state (0,0)), 0 is a null matrix representing the
Computing E[L|N] for all possible N, the transition probability matrix from an absorbing i
Nwhich accomplishes (8) is chosen as the state to a non-absorbing state, A is the transition i
optimum one. probability matrix with entries representing the
transition probability from a non-absorbing state to
IV. Simulations an absorbing state and finally, the transition
probabilities from non-absorbing states to non—
This section presents some numerical absorbing states are the entries of N. With that
results aimed to demonstrate the advantages in representation, the expected time until absorption
terms of throughput and packet delay given by the for the ith state is the sum of the ith row of the (I--1knowledge of the active users at MAC layer. For N) matrix. Hence, we can define a vector e with
this simulations, throughput is defined as the components e(j,k) representing the expected time
number of correctly received packets in one slot until absorption of the state j,k.
and packet delay is the average time (in slots) for a Besides, the initial state of this Markov
packet to be successfully transmitted in a TP. chain is always with j=M (M unprocessed users).
In the examples shown, the SNR at the Hence, the initial condition of this Markov chain is
receiver is always 10dB, data modulation is BPSK. given by
CDMA diversity is used and the user spreading
codes are obtained from different phases of an m-P[X0=(M,k)]=B(k,N,q)imsequence with length 2 – 1. The user activity (9)
for k=0,..,Ndetector is assumed to detect active users without
error and hence, only the active user codes are used
Since E[L|N] can be viewed as the for data demodulation. For the second stage of the i
expected time until absorption, E[L|N] is computed receiver, a bank of matched filters (MF) have been i
Dynamic Queue Protocol Modified Dynamic Queue Protocol
Non-empty slot. Non-empty slot. Node 3 packet Non-empty slot. Non-empty slot. Nodes 2 and 4 successfully Node 2 packet lost. Nodes 2 and 4 packets received. Node 3 packet packets successfully successfully Node 2 packet successfully received. received. received. lost. Node 1 empty Node 5 empty. empty slot Success. received packet
Packet Lost 3 3 4 4 2 2 2 2 Packet waiting for transmission
1 1 1 1 2 Empty buffer Nopt=3 2 2 2 4 5 3 4 3 5 4 5 4 5 5
Central controller do not know Central controller determines that whether packets from nodes 1 and 5 nodes 1 and 5 have empty buffers.
have collided or the buffers of these
nodes were empty.
Figure 3. DQP Vs. MDQP
DQP chosen to achieve channel capacity as described in
Access Figures 5 and 6 show differences in Set throughput and packet delay for a MF receiver
when using DQP and MDQP. For these simulations,
the gain factor is chosen to be 6, packet length
equal to 200 bits and an error correcting code is
used capable to correct up to 2 bits. It can be
noticed that throughput and packet delay
improvements are achieved at low and medium q itraffic. Furthermore, improvements have are shown
for M= 5, 10 and 15. In low and medium traffic, the Figure 4. Access Set Vs. User Packet Prob. user activity information is used to process users
with empty buffers when they are polled for the
first time. Hence, the TP length can be optimised.
At high traffic, the user activity information is less M=15 useful, i.e., almost all users are active and there are
no users with empty buffers to allow MDQP reduce
M=10 TP length. As shown in figure 4, access set is
Throughput chosen so that channel capacity is achieved.
This paper studies the possibility of using MDQP PHY-MAC dialogue for system performance M=5 DQP improvement. The considered flows of information
q between PHY and MAC layers go one step further i
in the cross-layer design.
The system considered is a CDMA system Figure 5. Throughput Vs. User Packet Prob.
with users sending data to a central controller. On
this basis, the receiver at the central controller is
composed by i)a user activity detector along with a M=15 data demodulator at the PHY level and ii)a MAC
protocol which uses user activity information.
Particularly, the MAC protocol used is a M=10 Packet modification of the DQP protocol. DQP protocol Delay already considers cross-layer design by means of
M=5 the MPR matrix. However, if only the MPR matrix
were considered by the MAC, the receiver
capabilities in terms of multi-packet reception MDQP would not be not fully exploited. Hence, a modified DQP DQP protocol which uses the additional knowledge
of active users have been presented. Simulations q idepicted system performance improvement in terms
of throughput and packet delay. Figure 6. Packet Delay Vs. User Packet Prob. References
Figure 4, depicts the value of N as a i James Ward and R.T. Compton, ―Improving the function of q for both, the DQP and the MDQP. iperformance of slotted ALOHA packet radio From this figure one can notice that at low traffic
network with an adaptive array‖, IEEE trans. the MDQP access set size is bigger than that for the
comm., vol. 40, NO. 2, Feb. 1992. DQP. This can be understood since at low traffic
 _, ―High throughput slotted ALOHA packet the number of users with a packet waiting for
radio networks with adaptive arrays‖, IEEE trans. transmission is low. In consequence, for the MDQP
on comm., vol. 41, NO. 3, Mar. 1993. it is preferable to poll a large number of users and
 S. Roy and H.Y. Wang, “Performance of discard those of them who are not willing to
CDMA slotted ALOHA multiple access with transmit in the first slot of the TP. Contrary, as the
multiuser detection”, Wireless Communications traffic increases, a lower N is preferable to avoid iand Networking Conference 1999, vol. 2, 1999 excessive collisions. At q=1, the access set is iPage(s): 839 -843.
 Sylvie Ghez, Sergio Verdú and Stuart C. Schwartz, ―Optimal decentralised control in the random access multipacket channel‖, IEEE trans. on automatic cont., vol. 34, NO. 11, Nov. 1989.  Qing Zhao and Lang Tong, ―The Dynamic Queue Protocol for spread spectrum random access networks‖, Military Communications Conference 2001, vol. 2, 2001, Page(s): 1024 –1028.
 Qing Zhao and Lang Tong, ―A multi-queue
service room MAC protocol for wireless networks with multipacket reception‖, submitted to ACM/IEEE trans. networking, Jan 2001.
 Biao Chen and Lang Tong, ―Traffic-aided
multiuser detection for random-access CDMA networks‖, IEEE trans. on signal proc., vol. 49, NO.
7, Jul 2001.
 K. W. Halford and M.Brandt-Pearce, ―New-
user identification in a CDMA system‖, IEEE trans. comm., vol. 46, Jan. 1998.
 U. Mitra and H. V. Poor, ―Adaptive decorrelating detectors for CDMA systems‖, J. wireless pers. comm., vol. 2, Dec. 1995  W. WU and K. Chen, ―Identification of active users in synchronous CDMA multiuser detection‖, IEEE J. select. areas comm., vol. 16, Dec. 1998.