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.

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).

Fig. 2: Algorithm for the Estimation of Collision Multiplicities

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

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 y

y

where m is the number of samples per snapshot. The signal vectors s

The estimation of the collision multiplicity K is based on the eigenvalue decomposition of the SCM R

det(R

where R

Fig. 3: Properties of the Largest Noise Eigenvalue

In the signal-free case, no user is transmitting (K=0), so m x R

R

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

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)

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 λ

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

- B. Escrig : "Model Order Selection for Collision Multiplicity Estimation," IEEE International Symposium on Personal, Indoor, and Mobile Radio Communication (PIMRC), Sydney, Austalia, september 2012.
- 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).
- B. Escrig : "Random Matrix Theory applied to the
Estimation
of Collision Multiplicities," International
Journal On
Advances in Networks and Services (Invited Paper), dec.
2012.

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

[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.