Menu:

Estimating collision multiplicity using

eigenvalue statistics



The context: collision resolution approaches


Collisions in Wireless Networks
Figure 1: Collisions in Wireless Networks

The throughput of wireless networks highly depends on the number of collisions. A collision occurs when more than two nodes access the wireless channel simultaneously. The respective signals interfere with each other and the transmissions are lost. When the number of collisions increases, the amount of traffic allocated to collision resolution increases and hence, the data throughput decreases. This issue is of particular interest for random access networks. For instance, in Fig. 1, a scenario involving two nodes simultaneously transmitting toward an access point is presented.

In this context, several techniques such as the Multi-Packet Reception (MPR) techniques and the Collision Resolution Algorithms (CRAs) have been proposed. They intend to increase the capacity of wireless networks by allowing the recovery of data packets from collision signals [1]-[3]. In the capture effect, for instance, a user signal can be successfully decoded in the presence of other interfering signals when the received power of the user signal is significantly higher than the power of the other interfering signals. Recent advances in Multi-User Detection (MUD) also allow the processing of collision signals, so data packets from collided user terminals can be successfully decoded even when a collision occurs, provided that the Multi-User Interference (MUI) can be sufficiently removed.

Several of the MPR and CRA techniques start with the estimation of the Collision Multiplicity (CM), i.e., the number of signals involved in the collision. So the CM estimation is often the first step when implementing a MPR technique or a CRA.
 


The issue: estimation of the collision multiplicity


CM estimation techniques (CMETs) that are implemented in this context are all based on Model Order Selection (MOS) methods [4]. They all rely on eigenvalue statistics [5]-[7].

The typical approach works like this. First, observations (“snapshots”) are gathered and the Sample Covariance Matrix (SCM) of the observations is computed. Then, an eigenvalue decomposition of this SCM is performed and the well-known information criterion MDL (Minimum Description Length) is applied in order to perform the CM estimation (see Fig. 2).

Algorithm for the Estimation of Collision Multiplicities
 
Fig. 2: Algorithm for the Estimation of Collision Multiplicities

The use of current CMETs in the context of wireless networks raises two main issues.

The first issue deals with the distribution of signal samples. Current techniques rely on the assumption that signal samples are uniformly distributed over a finite alphabet, i.e., signal samples are PSK or QAM modulation symbols. This assumption is not consistent with the waveforms that are used in wireless network standards such as the IEEE 802.11, the IEEE 802.16, or the LTE standard, since these standards are based on Orthogonal Frequency Division Multiplex (ODFM) transmission, i.e., a transmission scheme for which signal samples are Gaussian distributed. Note that the Gaussian distribution assumption is widespread in the signal processing area [4] and in the domain of sensor networks [9]. Note also that the MPR protocols in [2][3] have been specially designed for IEEE 802.11 networks but they implement a blind separation of the colliding users that relies on a uniform distribution of signal samples [7].

The second issue deals with the number of observations (”snapshots”) T that is needed to perform the CM estimation. One of the main issues here is to minimize the number of observations. The point is that the performance of the CM estimation techniques improves with an increasing number of observations. But the time devoted to the generation of new observations is considered as signaling overhead and, as such, it should be minimized as much as possible. To tackle this issue, eigenvalue statistics can be used. Since signal eigenvalues are assumed to be much larger than noise eigenvalues, one can increase the number of observations and perform the eigenvalue decomposition of the SCM until the lowest eigenvalue is detected as being a noise eigenvalue (the eigenvalue is compared with a noise threshold) [5]. Hence, when the test is passed at step i, this means that the ith eigenvalue is a noise eigenvalue, and hence that there are i-1 signal eigenvalues, so there are i-1 colliding users, so K=i-1, where K denotes the CM. This way, the CM is estimated while the number of observations is minimized since T is not greater than K + 1. In [6], the previous method has been improved by applying an MDL criterion on the eigenvalues [8].
In [2][3], T is limited by the number of receive antennas at the access point, i.e., T <= 4 in typical implementations of IEEE 802.11 WLANs [10]. These settings are not in accordance with the settings that are used in typical source separation algorithms where T >> K [8][11][12]. The issue here is to decide whether current CMETs can still operate with a small number of snapshots in wireless networks, or not.

So the purpose of our research is threefold:
(a) to show that current CMETs do not perform well in the context of wireless networks,
(b) to propose new CMETs that work with Gaussian distributed samples,
(c) and to minimize the number of observations T.

Our works leverage recent advances in both information criterion design and Random Matrix Theory (RMT) to tackle these issues.
We propose a new criterion based on the distribution of noise eigenvalues to overcome these limitations. Our approach, denoted TWIT for Tracy-Widom Inference Test, is based on the property that noise eigenvalues are distributed according to a TW distribution whereas signal eigenvalues are Gaussian distributed.
More precisely, we design a hypothesis test to decide whether an eigenvalue is TW distributed or not. Our proposal outperforms typical MDL-based methods in the context of OFDM transmissions.

Table 1: Issues for the Estimation of Collision Multiplicities

Issues for the Estimation of Collision Multiplicities 

System Model


We consider the scenario where K users are simultaneously transmitting OFDM frames toward a destination node. This node can be a Base Station (BS) or an Access Point (AP) in an infrastructure-based wireless network. This node could also be a user node in an ad hoc or mesh network. The destination node and the user stations are equipped with a single antenna. We do not consider here the case of multiple antenna station (user stations or base stations). Each OFDM frame contains m symbols. The OFDM signal samples are Gaussian distributed and have a white power spectral density. The destination node can trigger retransmissions from the colliding users by transmitting a feedback frame. The signaling frame serves also as a synchronization flag for user transmissions, so we assume that the K users are coarsely synchronized in time. In this way, the destination node receives T snapshots. The scenario is similar to a source separation problem when K signals are impinging on a T sensor array. More precisely, each snapshot yi is a T x 1 vector

yi = H x si + wi   for   i=0,1,...,m

where m is the number of samples per snapshot. The signal vectors si are K x 1 complex Gaussian vectors with covariance matrix Rs and the noise vectors wi are T x 1 complex Gaussian vectors with noise covariance matrix Rw. The covariance matrix Rw is a T x T identity matrix, for the white noise case (with variance unity). The channel matrix H is a TK matrix with circularly symmetric Gaussian elements with power unity (Rayleigh fading). The coefficients in H have constant values during an OFDM block of m samples, and then change randomly from one block to another, i.e., a block-fading wireless channel is considered here. Hence, the channel matrix H can be considered as an unknown non-random matrix. We also define Ry as the covariance matrix of the observations.

The estimation of the collision multiplicity K is based on the eigenvalue decomposition of the SCM Rye, which denotes the estimation of the covariance matrix Ry. When the noise is not white and has covariance matrix Rw, we get a generalized eigenvalue problem

det(RyeRwe)=0

where Rwe denotes the SCM of the noise. This SCM can by computed provided that we can observe N noise-ondly samples.


Properties of SCM Eigenvalues 

and Tracy-Widom Inference Test



Noise Eigenvalue Properties
Fig. 3: Properties of the Largest Noise Eigenvalue

Signal-free Case


In the signal-free case, no user is transmitting (K=0), so m x Rye and N x Rwe are both complex Wishart distributed matrices. After appropriate centering and rescaling, the largest sample eigenvalue λ1 that satisfies the following eigenvalue equation is distributed according to a Tracy-Widom law

Rye x v = λ1Rwe x v

Note that the centering and rescaling depend on T, m, and N.

Signal-Bearing Case


When there are K signals, there are K signal eigenvalues and T-K noise eigenvalues. When there is no signal, noise eigenvalues are Tracy-Widom distributed. So is the largest noise eigenvalue in the signal-bearing case i.e., the (K+1)th eigenvalue is Tracy-widom distributed. The centering and rescaling must take into account that T should be replaced by T-K. This property holds provided that the sample eigenvalues that belong to the signal subspace are larger than a detectability threshold.

Tracy-Widom Inference Test


Assume that T snapshots are available at the destination node. The SCM of the whitened snapshots is computed first. Then, the eigenvalue decomposition of the SCM is performed and the eigenvalues are sorted. The estimate of the CM, K, is initialized to zero and incremented by one for each iteration as long as the eigenvalue λK+1 is not considered as being an eigenvalue of the noise subspace, i.e., as being Tracy-Widom distributed.


Contributions


The method has been applied to the context of wireless networks in these papers

  1. B. Escrig : "Model Order Selection for Collision Multiplicity Estimation," IEEE International Symposium on Personal, Indoor, and Mobile Radio Communication (PIMRC), Sydney, Austalia, september 2012.
  2. B. Escrig : "Estimation of Collision Multiplicities in IEEE 802.11-based WLANs," International Conference on Networks (ICN), Reunion Island, France, IARIA, february 2012 (Best Paper Award).
  3. B. Escrig : "Random Matrix Theory applied to the Estimation of Collision Multiplicities," International Journal On Advances in Networks and Services (Invited Paper), dec. 2012.
The TWIT has been compared to a statistical test based on the Exponential Embedded Family (EEF) in this paper

  1. B. Escrig : "Model Order Selection for Collision Multiplicity Estimation," Wireless Telecommunications Symposium (WTS), London, UK, april 2012.

REFERENCES

[1]    S. V. S. Ghez and S. Schwartz, “Stability Properties of Slotted Aloha with Multi-Packet Reception Capability,” IEEE Transactions on Automatic Control, vol. 33, no. 7, pp. 640–649, 1988.
[2]    P. X. Zheng, Y. J. Zhang, and S. C. Liew, “Multipacket Reception in Wireless Local Area Networks,” in Proc. IEEE International Conference on Communications (ICC), 2006.
[3]    W. L. Huang, K. B. Letaief, and Y. J. Zhang, “Cross-Layer Multi-Packet Reception Based Medium Access Control and Resource Allocation for Space-Time Coded MIMO/OFDM,” IEEE Transactions on Wireless Communications, vol. 7, no. 9, pp. 3372–3384, 2008.
[4]    P. Stoica and Y. Selèn, “Model-Order Selection : A review of information criterion rules,” IEEE Signal Processing Magazine, vol. 21, no. 4, pp.36–47, 2004.
[5]    R. Zhang, N. D. Sidiropoulos, and M. K. Tsatsanis, “Collision Resolution in Packet Radio Networks Using Rotational Invariance Techniques,”IEEE Transactions on Communications, vol. 50, no. 1, pp. 146–155, 2002.
[6]    B. Özgül and H. Delic¸, “Wireless Access with Blind Collision-Multiplicity Detection and Retransmission Diversity for Quasi-Static Channels,” IEEE Transactions on Communications, vol. 54, no. 5, pp.858–867, 2006.
[7]    S. Talwar, M. Viberg, and A. Paulraj, “Blind Separation of Synchronous Co-Channel Digital Signals Using an Antenna Array. Part I. Algorithms,” IEEE Transactions on Signal Processing, vol. 44, no. 5, pp.1184–1197, 1996.
[8]    M. Wax and T. Kailath, “Detection of Signals by Information Theoretic Criteria,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 33, no. 2, pp. 387–392, 1985.
[9]    M. Chiani, M.Z. Win, “Estimating the number of signals observed by multiple sensors”, 2nd International Worshop on Cognitive Information Processing (CIP), 2010, pp.:156-161.
[10]    “IEEE 802.11n standard, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Amendment 5: Enhancements for Higher Throughput,” IEEE Computer Society, Tech. Rep., 2009.
[11]    C. Xu and S. Kay, “Source Enumeration via the EEF Criterion,” IEEE Signal Processing Letters, vol. 15, pp. 569–572, 2008.
[12]    R. R. Nadakuditi and J. W. Silverstein, “Fundamental Limit of Sample Generalized Eigenvalue Based Detection of Signals in Noise Using Relatively Few Signal-Bearing and Noise-Only Samples,” IEEE Transactions on Signal Processing, vol. 4, no. 3, pp. 468–480, 2010.