To view PDF files

You need Adobe Reader 7.0 or later in order to read PDF files on this site.
If Adobe Reader is not installed on your computer, click the button below and go to the download site.

Regular Articles

Compressed Sensing Technology for Flexible Wireless System

Doohwan Lee, Takayuki Yamada, Hiroyuki Shiba,
Yo Yamaguchi, and Kazuhiro Uehara

Abstract

We are developing a flexible wireless system (FWS) in response to the rapid development of and changes to wireless radio environments. FWS is a unified wireless platform that simultaneously receives various types of wireless signals at distributed remote stations and performs signal processing at the central station by transferring the received radio wave data via the wired access line. As a partial fulfillment of our system, we have applied compressed sensing technology as a radio wave data compression technology for FWS. Compressed sensing is a new framework for solving an ill-posed inverse problem of a sparse signal. Direct translation of compressed sensing in the sense of wireless technology is as follows: radio wave data can be received, transmitted, and reconstructed using sub-Nyquist rate information without aliasing if the original radio wave is sparse. To provide a full understanding of our approach, this article first reviews basic knowledge about compressed sensing and then describes the application scenario of compressed sensing in FWS.

PDF
NTT Network Innovation Laboratories
Yokosuka-shi, 239-0847 Japan

1. Introduction

The rapid development of and changes to wireless radio environments require a unified platform that can flexibly deal with various wireless radio systems [1]. To satisfy this requirement, we are developing a flexible wireless system (FWS), which is composed of flexible access points and a flexible signal processing unit [2].

The concept of FWS is illustrated in Fig. 1. Multiple wireless signals are simultaneously received by flexible access points, which can receive a wide variety of wireless signals with frequencies ranging from several hundred megahertz to several gigahertz. The received radio wave data is transferred to the flexible signal processing unit through a broadband wired access line. The flexible signal processing unit performs multiple types of signal analysis by software exploiting software defined radio and cognitive radio technologies [3]. If necessary, previously stored data at servers can also be used.


Fig. 1. Concept of a flexible wireless system.

The huge bandwidth necessity for transferring the received radio wave data motivated us to develop a highly flexible and efficient radio wave data compression technology. To accomplish this goal, we applied recently developed compressed sensing technology.

Compressed sensing is a new framework for solving an ill-posed inverse problem of a sparse signal [4]. Direct translation of compressed sensing in the sense of wireless technology is as follows: radio wave data can be received, transmitted, and reconstructed using sub-Nyquist rate information without aliasing if the original radio wave is sparse.

In relation to FWS, compressed sensing has two advantages. First, it provides universality in wireless signal reception regardless of system types. This provides flexible signal reception because all types of signals can be received by a unified signal reception method. Furthermore, no modifications are necessary even when new wireless systems are introduced. Second, it enables signal reception and reconstruction at a lower rate than the Nyquist rate. This reduces the burden of data transfer between flexible access points and the flexible signal processing unit.

The remainder of this article is organized as follows: Section 2 reviews basic knowledge about compressed sensing, section 3 describes our compression method, and section 4 concludes with a brief summary of the main points and a mention of future work.

2. Compressed sensing

2.1 Basic concept

A simplified explanation of compressed sensing is as follows: A signal projected linearly onto a lower-dimensional space can be used to reconstruct the original higher-dimensional signal with high probability if the signal is sparse (explained in section 2.2) and the projection matrix satisfies the restricted isometry property (RIP, explained in section 2.4).

In a mathematical sense, compressed sensing can be stated as an ill-posed inverse problem. Normally, the solution of an ill-posed inverse problem is not uniquely determined because the number of equations is smaller than the number of variables. However, the solution of an ill-posed inverse problem can be uniquely determined by investigating all possible cases provided that the signal is sparse. Moreover, if an ill-posed inverse problem satisfies RIP and the signal is sparse, the unique solution can be found with a practical degree of complexity.

For an intuitive understanding of compressed sensing, consider the following simple ill-posed inverse problem.

Find m, n, and k such that

m + 3n - 2k = 1

-mn + k = -1

Normally, the solution is not uniquely determined because the number of equations is smaller than the number of variables. However, if vector [m k n] has only one nonzero element, the unique solution can be obtained by investigating all possible cases, as below.

case 1) m≠0, n=k=0 -> m=1 (unique solution)

case 2) n≠0, m=k=0 -> impossible

case 3) k≠0, m=n=0 -> impossible

Although the unique solution is available, this is an NP-hard problem for which all possible cases must be investigated. Consequently, it becomes impractical as the number of dimensions of the signal increases.

This impracticality is overcome if the equation vector [1 3 -2; -1 -1 1] satisfies RIP. The core achievement of compressed sensing is that the above NP-hard problem can be cast into an l1-norm minimization problem (explained in section 2.5) if the signal is sparse and RIP is satisfied. L1-norm minimization problems can be solved by linear programming, which is a well established convex optimization method, with practical complexity O(n3) [5], [6].

Considering the above example, the following two statements can be made: First the sparsity of the signal assures the unique solution for compressed sensing. Second, RIP assures a practical degree of complexity for finding the unique solution for compressed sensing.

2.2 Sparse signal

A signal is called sparse when it is represented by a small number of nonzero coefficients in any convenient domain. More specifically, N¡ß1 signal X is called S-sparse if X is represented by the multiplication of any N¡ßN transform matrix Ψ and N¡ß1 coefficient vector s, and s has only S nonzero coefficients. The definition of sparsity is not limited to the orthogonal transform domain (i.e., Fourier transform or wavelet transform). If a signal is represented in a non-orthogonal domain, including any user-defined domain, the signal is also called sparse [7].

2.3 Measurement

For a given N¡ß1 signal X, measurement is defined as the linear projection of X onto M¡ß1 signal Y. The M¡ßN matrix Φ that casts X onto Y is called the measurement matrix. Matrix description is given by Y=ΦX. If X is represented by N¡ß1 coefficient vector s in the N¡ßN transform domain Ψ , it is expressed as Y=ΦΨs.

The number of measurements is the number of rows in the measurement matrix (M), which is also equivalent to the number of dimensions of the output signal. Therefore, the compression rate increases as the number of measurements increases. Numerous studies have been performed to investigate the minimum bound of the necessary number of measurements for a given signal sparsity [8 and references therein]. It has been shown that S•log(N/S) measurements are enough for the reconstruction of an S-sparse signal when measurement matrix Φ consists of random ensembles [9].

2.4 RIP

The most outstanding achievement of compressed sensing is the fact that RIP casts an NP-hard problem onto an l1-norm minimization method [10], [11].

When an M¡ßN measurement matrix Φ and a N¡ßN transform domain matrix Ψ satisfy the following inequality for all S-sparse vectors, matrix Θ(=ΦΨ) is said to obey RIP of order S with δ.

(1-δ)||s||22 ≤||ΦΨs||≤(1+δ)||s||22

where ||s||2i si2 and δ(0 ≤δ <1) is the smallest constant that satisfies the above inequality.

An intuitive explanation of RIP is as follows: the Euclidian distance between any two N¡ß1 S-sparse vectors is approximately preserved after the measurement as long as Θ obeys RIP.

It has been proven that RIP is satisfied if measurement matrix Φ consists of random ensembles, which yields the following surprising result: any unknown sparse signals can be reconstructed by random measurement [10]. This property provides flexibility for the compression of an unknown signal because signal-independent measurement is possible by the random measurement as long as the signal is sparse.

2.5 Reconstruction

Reconstruction of the compressed sensing refers to finding N¡ß1 S-sparse vector s from known M¡ß1 measurement output matrix Y, M¡ßN measurement matrix Φ, and N¡ßN transform matrix Ψ when Y=ΦΨs (S<M<<N). Reconstruction of the original signal s can be found via the l1-norm minimization problem, as described below, as long as RIP is satisfied.

min||sˆ||1 subject to Y=ΦΨsˆ, sˆRN,

if RIP satisfies sˆ=s,

where ||sˆ||1=|s1|+|s2|+...|sN| and RN is the set of N¡ß1 vector.

The l1-norm minimization problem finds sˆ that minimizes the l1-norm subject to Y=ΦΨsˆ among all possible S-sparse vectors. This seems to be an NP-hard problem, but it can be cast into a convex optimization problem and solved by the linear programming method. Furthermore, if RIP is satisfied, sˆ is identical to the original vector s with high probability [10], [11].

If the measurement matrix consists of random ensembles, flexible reconstruction is possible. In the case that signal X is proved to be more sparsely represented in another basis matrix Ψ’, surprisingly, one does not need to conduct the measurement again since the l1-norm minimization problem can be solved with Y and a new Θ’(=ΦΨ’). This indicates that once the projection has been performed, the reconstruction can be performed with any convenient basis matrix.

There are other approaches to the reconstruction of compressed sensing such as an orthogonal matching pursuit algorithm, which uses a greedy iterative algorithm [12].

2.6 Comparison between conventional compression and compressed sensing

The difference between the conventional compression and compressed sensing is shown in Fig. 2. The conventional sample-then-compress method compresses the signal by the signal-specific compression method, which yields the optimal compression (S dimensions). On the other hand, compressed sensing conducts a signal-independent linear projection of the original signal onto a lower-dimensional space (M-dimensional, S<M<<N), which yields poor compression performance. Therefore, it can be stated that the conventional compression method is superior to compressed sensing for the known signals in terms of compression performance.


Fig. 2. Comparison between conventional compression and compressed sensing.

However, compressed sensing has the following advantages compared with the conventional compression method. First, it is suitable for dealing with an unknown sparse signal. Second, it is robust to the introduction of new types of wireless systems. When new types of wireless systems are introduced, receivers (flexible access points in Fig. 1) do not need to be modified because the signal-specific processing burden is moved from the receivers to the server (flexible signal processing unit in Fig. 1). Third, it reduces the burden on receivers. For example, consider a sparse signal of unknown frequency. In the case of the conventional sampling method, receivers must conduct both a fast Fourier transform and a search for nonzero coefficients. On the other hand, in the case of compressed sensing, receivers only need to conduct a linear projection.

3. Application of compressed sensing for FWS

This section describes two radio wave data compression methods that utilize compressed sensing. Both methods try to exploit the flexibility of compressed sensing by utilizing prior information. One method uses a random sparse measurement matrix based on random sampling [13] (or equivalently, random discard from all of the sampled data). The other uses a random dense measurement matrix that conducts a full linear projection of sampled data [14].

3.1 Combined Nyquist and compressed sampling

The goal of this sampling method is to achieve Nyquist-rate sampling of the known signal (hereinafter called the decoding signal) and compressed-rate sampling of the unknown signal (hereinafter called the sensing signal) in a single analog-to-digital converter. To achieve this goal, the following processes are carried out.

At each flexible access point, multiple signals are simultaneously received, filtered, and down-converted to the intermediate frequency (IF) band. In particular, decoding signals are converted to a lower center frequency band than sensing signals, as shown in Fig. 3. Signal down-conversion is done by tunable local oscillators and mixers. All down-converted signals are sampled by our method and transferred to the flexible signal processing unit.


Fig. 3. Example of frequency alignment of multiple signals.

Details of the combined Nyquist and compressed sampling method are as follows. Suppose that L decoding signals and M sensing signals are aligned in the IF band, and the total bandwidths of these signals are represented by Bdec and Bsens, respectively. For the convenience of the explanation, Bgrid and BNyq are defined as (4Bdec+2Bsens) and (2Bdec+Bsens), respectively. The purpose of the above setting is to achieve (1) Nyquist-rate sampling of the decoding signals without aliasing from the sensing signals and (2) compressed-rate sampling of the sensing signals in a single analog-to-digital converter simultaneously.

The detailed procedure of our method is as follows. First, Bgrid-rate sampling is conducted. Second, only some of the even (odd) samples are randomly discarded while all of odd (even) samples are preserved. The locations of randomly discarded samples, which are determined by the random sequences generator, can be known to the flexible signal processing unit if the initial seed of the random sequence generator is shared. Hereinafter, all the odd samples and the remaining even samples are called fixed samples and random samples, respectively. They are transferred to the flexible signal processing unit via the wired access line.

The mathematical description of our method is as follows. For simplicity, we consider multiple sparse signals in the frequency domain. The IF band signal X=(Ψs) is sparsely represented in the frequency domain. The basis matrix Ψ is an N¡ßN inverse Fourier transform, and s is the N¡ß1 coefficient vector of X in the frequency domain. Note that s has sequential nonzero values in the lower frequency region and randomly sparse nonzero values in the higher frequency region (e.g., s=[1111100100010001]). The K¡ßN projection matrix Φ has the following sparse representation.

Note that each column indicates a sample point of the signal. Every odd sample is preserved while some of the even samples are randomly discarded.

Then, the compressed sensing matrix Θ(=ΦΨ) becomes a K¡ßN matrix consisting of every odd row and randomly selected even rows of the inverse Fourier transform matrix. Projection vector Y is represented by Θs and signal reconstruction becomes the inverse problem of s =Θ-1Y. This inverse problem is solvable as an l1-norm minimization problem because s is sparse and Θ consists of randomly selected rows of the inverse Fourier transform matrix*.

Using transferred fixed and random samples from flexible access points, the flexible signal processing unit conducts the decoding and sensing process as follows.

First, the decoding signals are decoded using only fixed samples, which is equivalent to BNyq-rate sampling. Note that aliasing of the sensing signals occurs because the sampling rate is insufficient. However, it does not cause interference with the decoding signals. Therefore, the decoding signals can be decoded by using conventional decoding algorithms without aliasing. An example of fixed samples in the frequency domain is shown in Fig. 4. Although the aliasing of the sensing signals occurred owing to the insufficient sampling rate, the decoding signal parts are intact. Consequently, Nyquist-rate decoding performance is achieved for the decoding signals. Second, the decoding signal is subtracted from both the fixed and random samples. Third, the sensing signals are reconstructed using both fixed and random samples, whose decoding signals have been subtracted. The reconstruction is done by solving the l1-norm minimization problem. An example of the reconstructed signal in the frequency domain is shown in Fig. 5. Note that only sensing signals are reconstructed because the decoding signals have been removed. Fourth, the sensing signals are identified in the reconstructed signal by a conventional spectrum sensing algorithm such as energy detection.


Fig. 4. Frequency domain representation of fixed samples.


Fig. 5. Frequency domain representation of sensing signals reconstructed from fixed and random samples after subtraction of the decoding signal.

Some experimental results are shown in Figs. 6 and 7. Experiments were performed on 310-MHz-band frequency shift keying (FSK) signals transmitted by radio frequency identification (RFID) tags. The RFID tag bandwidth and the total bandwidths of decoding signals and sensing signals were 0.3, 1.73, and 6.54 MHz, respectively. The channel between the RFID tags and a flexible access point was a non-fading additive white Gaussian noise channel.


Fig. 6. Symbol error rate comparison.


Fig. 7. Probability of detection success.

Figure 6 compares the theoretical and experimental symbol error rates for the decoding signal in terms of Es/No (energy per symbol per noise power spectral density). In the experiment using the conventional method, only the down-converted decoding signal was sampled at the Nyquist rate. In the experiment using our method, the decoding signal and the sensing signals were combined in the IF band and sampled by using our method. The performance curve for our method matches those for the theoretical and conventional methods well, which shows that our sampling method guarantees Nyquist-rate decoding performance for the decoding signal.

The detection success rate is shown in Fig. 7. All curves show relatively poor performance at a low compression ratio. This is because reconstruction fails if the number of samples is insufficient. However, Pd (detection success rate) increases with the compression ratio. Approximately, 70% of the compression ratio can be achieved when Es/No is higher than 17.5 dB.

* Compressed sensing theory has proved that randomly permutated Fourier ensembles satisfy RIP. Therefore, we can use randomly selected rows of an inverse Fourier transform matrix as a sensing matrix because Fourier ensembles and inverse Fourier ensembles have identical statistical characteristics.

3.2 Compressed sensing with weighted measurement matrix

Our goal for the weighted measurement matrix generation is to reduce the required number of measurements by using prior knowledge of the signal.

A block diagram of compressed sensing with weighted measurement matrix generation is shown in Fig. 8. The weighted measurement matrix is generated by multiplying the random measurement matrix and weight matrix, where the weight matrix is generated taking into consideration prior knowledge such as the signal’s history. Note that identical weighted and random measurement matrices are generated by both the flexible access points and the signal processing unit for the reconstruction. If the weight needs to be updated, necessary parameters are transmitted from the signal processing unit to the flexible access points.


Fig. 8. Block diagram of compressed sensing with weighted measurement matrix generation.

To verify the efficiency of this method, we conducted an experiment using an RFID signal consisting of a periodically transmitted FSK signal. The total bandwidth and the received signal bandwidth were 5 and 0.6 MHz, respectively. The time occupancy rate of the received signal was 0.25. Therefore, the time-frequency domain signal sparsity was 0.03. The time and frequency domain weights were set to 2.0 and 1.5 using the signal reception history. The detection success rates for the conventional method and our method are compared in Fig. 9. The compression rates needed for perfect signal detection were 0.13, 0.12, 0.09, and 0.08, respectively, when the applied weights were no weight, time domain weight, frequency domain weight, and time-frequency domain weight. These results confirm that enhanced compression is achieved by our method.


Fig. 9. Probability of detection success.

4. Conclusion

To satisfy the requirement for a unified wireless platform, we are developing a flexible wireless system. As a partial fulfillment of such as system, this article described a highly efficient radio wave data compression method based on currently developed compressed sensing technology. It also described two radio wave data compression methods utilizing compressed sensing technology. Experiments results verified that a compression rate that is slightly higher than the Nyquist rate of the original sparse signal can be achieved. Our future research will include developing further enhanced data compression methods in terms of realtime operation and practical processing burden using compressed sensing technology.

References

[1] N, Takahashi, K. Akabane, M. Matsuo, M. Ohta, M. Harada, and K. Okada, “Technologies Towards Networked Objects and Events in the Real World,” NTT Technical Review, Vol. 7, No. 5, 2009.
https://www.ntt-review.jp/archive/ntttechnical.php?contents=ntr200905sf5.html
[2] H. Shiba, K. Akabane, T. Yamada, and K. Uehara, “A Unified Wireless Platform Architecture for a Wide Variety of Wireless Systems,” Proc. of SDR’09 Technical Conference, Dec. 2009.
[3] K. Uehara, K. Araki, and M. Umehira, “Trends in Research and Development of Software Defined Radio,” NTT Technical Review, Vol. 1, No. 4, pp. 10–14, 2003.
https://www.ntt-review.jp/archive/ntttechnical.php?contents=ntr200307010.pdf
[4] E. J. Candes and M. B. Wakin, “An Introduction to Compressive Sampling,” IEEE Signal Processing Mag., Vol. 25, No. 2, pp. 21–30, Mar. 2008.
[5] E. J. Candes and T. Tao, “Decoding by Linear Programming,” IEEE Trans. Inf. Theory, Vol. 51, No. 12, pp. 4203–4215, Dec. 2005.
[6] E. J. Candes and J. Romberg, “l1-magic: Recovery of Sparse Signals via Convex Programming,” available online at
www.l1-magic.org. Oct. 2005.
[7] A. Cohen, W. Dahmen, and R. Devore, “Compressed Sensing and Best k-term Approximation,” Journal of the American Mathematical Society, Vol. 22, No. 1, pp. 211–231, Jan. 2009.
[8] E. J. Candes, J. Romberg, and T. Tao, “Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information,” IEEE Trans. Inf. Theory, Vol. 52, No. 2, pp. 489–509, Feb. 2006.
[9] E. J. Candes, “The Restricted Isometry Property and Its Implications for Compressed Sensing,” Comptes Rendus Mathematique, Vol. 346, No. 9-10, pp. 589–592, May 2008.
[10] J. A. Tropp and A. C. Gilbert, “Signal Recovery from Random Measurement via Orthogonal Matching Pursuit,” IEEE Trans. Inf. Theory, Vol. 53, No. 12, pp. 4655–4666, Dec. 2007.
[11] E. J. Candes and T. Tao, “Near Optimal Signal Recovery from Random Projections: Universal Encoding Strategies?” IEEE Trans. Inf. Theory, Vol. 52, No. 12, pp. 5406–5245, Dec. 2006.
[12] R. Berinde and R. Indyk, “Sparse Recovery Using Sparse Random Matrices,” preprint, 2008.
[13] D. Lee, T. Yamada, H. Shiba, Y. Yamaguchi, and K. Uehara, “Combined Nyquist and Compressed Sampling Method for the Wireless Multiband Receiver,” IEICE Trans. Commun., Vol. E93-B, No. 12, Dec. 2010.
[14] D. Lee, T. Yamada, H. Shiba, Y. Yamaguchi, and K. Uehara, “Time-frequency Domain Weighted Measurement Matrix Generation Method for Compressed Sensing,” IEICE Society Conference, Sep. 2010.
Doohwan Lee
Postdoctoral Research Engineer, Wireless Systems Innovation Laboratory, NTT Network Innovation Laboratories.
He received the B.S. degree and completed the M.S. course in electrical engineering from Seoul National University, Seoul, Korea, in 2004 and 2006, respectively. He received the Ph.D. degree in electrical engineering and information systems from the University of Tokyo in 2009. He is currently working at NTT Network Innovation Laboratories as a postdoctoral researcher. His research interests include compressed sensing, flexible wireless systems, software defined radio, and cognitive radio. He received a Japanese government scholarship (Monbusho) during his Ph.D. studies.
Takayuki Yamada
Research Engineer, Wireless Systems Innovation Laboratory, NTT Network Innovation Laboratories.
He received a B.E. degree from the Department of Electronics, Faculty of Engineering of Doshisha University, Kyoto, in 2005 and the M.E. degree in communications and computer engineering from the Graduate School of Informatics of Kyoto University in 2007. Since joining NTT Network Innovation Laboratories in 2007, he has been engaged in research on flexible wireless systems. He is a member of IEEE.
Hiroyuki Shiba
Senior Research Engineer, Wireless Systems Innovation Laboratory, NTT Network Innovation Laboratories.
He received the B.E. and M.E. degrees from Gunma University in 1995 and 1997, respectively. Since joining NTT Wireless Systems Laboratories (now NTT Network Innovation Laboratories) in 1997, he has been engaged in research on software defined radio and cognitive radio technologies. He received the Young Engineer’s Award from the Institute of Electronics, Information and Communication Engineers (IEICE) and the 18th Telecom System Technology Award from the Telecommunications Advancement Foundation in 2001 and 2003, respectively.
Yo Yamaguchi
Senior Research Engineer, Wireless Systems Innovation Laboratory, NTT Network Innovation Laboratories.
He received the B.S. and M.S. degrees in chemistry from Osaka University and the Dr.Eng. degree in communication engineering from Tokyo Institute of Technology in 1989, 1991, and 2010, respectively. In 1991, he joined NTT Radio Communication Systems Laboratories, where he engaged in R&D of MMICs. From 1999 to 2001, he was an Associate Manager at STE Telecommunication Engineering Co., Ltd., where he served as a technical consultant on wireless communications. He took up his current post in 2001. He is a member of IEEE and IEICE.
Kazuhiro Uehara
Senior Research Engineer, Supervisor, Group Leader, Wireless Systems Innovation Laboratory, NTT Network Innovation Laboratories.
He received the B.E., M.E., and Ph.D. degrees from Tohoku University, Miyagi, in 1987, 1989, and 1992, respectively. In 1992, he joined NTT and engaged in research on array antennas, active antennas, and indoor propagation in the millimeter-wave and microwave frequency bands. From 1997 to 1998, he was a Visiting Associate at the Department of Electrical Engineering, California Institute of Technology, USA. From 2003 to 2010, he was a part-time lecturer at the Department of Electrical Engineering, Tohoku University. His current interests include R&D of software defined radio and cognitive radio systems and millimeter-wave multi-gigabit wireless systems. He is currently serving as Chair of the Technical Committee on Software Radio, IEICE Communication Society. He is a General Co-Chair of the 6th International Conference on Cognitive Radio Oriented Wireless Networks and Communications, CrownCom, May 2011. He was a Guest Editor-in-Chief of the Special Section on Wireless Distributed Networks, IEICE Transactions on Communications, December 2010. He received the Young Engineer’s Award and Excellent Paper Award from IEICE in 1995 and 1997, respectively, the 1st YRP Award in 2002, and the 18th Telecom System Technology Award from the Telecommunications Advancement Foundation in 2003, respectively. He is a senior member of IEEE and IEICE.

↑ TOP