An algorithm of channel estimation was proposed based on the theory of Compressive Sensing (CS) by analyzing the sparse characteristic of underwater acoustic channel for Orthogonal Frequency Division Multiplex (OFDM), Comparing with conventional Least Square (LS) estimation algorithm, the algorithm had good performance with less pilots, which improved the spectral efficiency of communication system. The result of simulation has analyzed the performance of the algorithm.
PDF Abstract XML References Citation
How to cite this article
Since the high spectrum efficiency and high endurance for multi-path fading, OFDM has a promising future in underwater acoustic communication (UWA). However, due to the high delay-spread and Doppler-spread of underwater acoustic channel , OFDM used in UWA also face several challenges: (1) The guard interval of OFDM must be greater than the delay spread (the delay of underwater acoustic channel can achieve dozens or even hundreds of milliseconds), which reduce the transmission efficiency of system, (2) OFDM is very sensitive to carrier frequency offset and Doppler effect, the orthogonality in subcarriers of OFDM system can be easily destructed by time-varying underwater acoustic channel. For above problems, an efficient solution is that estimate channel information accurately to correct and recover the received data. In order to estimate underwater acoustic channel more accurately, we should take advantage of the structure features of the channel. By analyzing the structure feature of underwater acoustic channel-most of the channel energy is localized around several delay-spread and Doppler-spread, in other words, there are lots of zero taps in the channel coefficients. So, underwater acoustic channel has sparse character. This property can be used to improve the algorithm.
Conventional underwater acoustic channel estimation method of OFDM mainly includes blind channel estimation and Pilot Symbol Assisted Modulation (PSAM). Considering the simple computation, fast convergence and easy implementation performance, PSAM has been widely applied. The method first uses Least Square (LS) (Chen et al., 2010) or mean square error (MMSE) (Zhang et al., 2008) acquires the channel impulse response of pilot symbol, which inserted in the transmitted signal, then recovers the whole channel impulse response by interpolating method. Since, the conventional method doesnt utilize the sparse character of underwater acoustic channel, the estimators have poor performance even with lots of pilot symbols, which lead to low spectral efficiency. For UWA, since the bandwidth is very low, the conventional method is unfavorable. Therefore, it is very important to propose a better channel estimation method to improve the spectral efficiency.
The new theory of compressive sensing improved in 2006 goes against the common wisdom in data acquisition. It can recover certain signals from far fewer measurements than traditional methods use, which make it successfully applied in various areas. Donoho (2006) and Baraniuk et al. (2008) introduced the theory of CS and its application. It is an important application in communication fields for CS that combining CS theory with channel estimation. In the case of same channel estimation performance, the pilot symbols are far fewer than the conventional method, which gives a new solution for sparse channel estimation.
In this study, we consider underwater acoustic channel estimation using a continuous time path-based channel model and utilizing CS recovery algorithms for channel estimation. Here, we used Orthogonal Matching Pursuit (OMP) algorithm and Compressive Sampling Matching Pursuit (CoSaMP) algorithm for recovery. The simulation results indicate that comparing with conventional LS algorithm, the proposed algorithm based on CS had good performance with less pilots, especially the CoSaMP algorithm and meanwhile improved the spectral efficiency of underwater acoustic communication.
COMPRESSIVE SENSING THEORY
CS theory is proposed by Candès, Romberg, Donoho and Tao, it goes against Nyquist sampling theorem and represents original signals at a rate significantly below the Nyquist rate, which reduces the pressure of transfer and storage.
To illustrate the principle of CS, consider a real-valued, finite-length, one-dimensional, discrete-time signal X, which can be viewed as Nx1 column vector with elements x [n], n = 1,2, , N.X can be represented in terms of an orthogonal basic of N×1 vectors:
where, α is the N×1 column vector of weighting coefficients αi = 〈X,φi〉 = φiT X, Ψ = [φ1, φ2, ...φN] is the NxN basic matrix. T denotes transposition. Clearly, Χ and α are equivalent representations of the signal in different domains, Χ in the time domain and α in the Ψ domain.
The signal Χ is k-sparse if only K (K<<N) of α coefficients in (1) are nonzero. For the K-sparse signal Χ, using an MxN matrix Φ, which has Restricted Isometry Property (RIP) (Ying and Zou, 2009), acquiring M (M<<N) measurements from N, then reconstructing the original signal X from M at the receiver. The process can be expressed by matrix:
where, Y is the Mx1 measurement vector, whose elements are the M measurements acquired from N. Φ is an NxM measurement matrix. The signal reconstruction is that utilize the M measurements in Y recover the length-N signal X by Eq. 2. Since, M<N (the unknown number is more than equations), this problem appears ill-conditioned. However, since X is K-sparse and K<M, the problem can trade-off get the signal's sparse coefficient vector α by sparse recovery algorithms, then, recover the original signal by Χ = Ψα.
OFDM CHANNEL MODEL
In this study, we adopt a continuous time path-based channel model, considering the OFDM system has K subcarriers, channel length is L. The channel impulse response in time domain can be expressed as:
Discrete sampling result of h (t) is:
where, τp is the time delay of pth, αp is the amplitude decay of pth, Τs is the sampling intervals of OFDM system, d describes the dominant physical multipath components, fc is the carrier frequency of underwater acoustic channel.
So, the received signal X obtained at the output with noisy and continuous time path-based channel h is given by:
where, X is an NxN diagonal matrix with the elements of user data and pilot symbols on its main diagonal, i.e., X = diag (x (0), x (1)), ...x (i), i = 0,1,...N-1 R = [r (0), r (1), ... r (N-1)] is the Nx1 vector of sampling values; H = Fh describes the channel frequency response vector by taking DFT transform of h. h = [h (0), h (1),...h (L-1)], which only have d (d<L) nonzero elements and reflects the sparse character of channel; F is an NxL DFT matrix:
Z is an N×1 vector of Gaussian white noise.
CHANNEL ESTIMATION ALGORITHM BASED ON CS
The principle of the algorithm is that the receiver uses sparse recovery algorithms recover the whole channel impulse response from the channel impulse response of pilot symbols, which inserted in the transmitted signal.
Sparse model based on pilot symbol: Consider S is a P×N selection matrix, which is used to select the position of pilot symbols from NxN identity matrix. For example, an OFDM symbol with 8 subcarriers, 4 pilot symbols, if the pilot symbols inserted uniformly, we can get S:
So, the received pilot symbols can be derived from Eq. 5:
where, Rp= SR is the P×1 vector of received pilot symbols; Xp = SXS is the P×P matrix with the elements of pilot symbols; Fp = SF is a P×N DFT matrix; Zp = SZ is the noise in the position of pilot symbols. Thus, Rp can be regard as the observation of h by measurement matrix T = XpF p, now, Rp, Xp, Fp, Zp are know, only h is unknown at the receiver, so, we can recover the h vector by recovery algorithms, then, get H by H = F h, the channel estimation of OFDM system is completed.
Channel estimation based on CS: According to the sparse model based on pilot symbol, this study utilizes OMP and CoSaMP algorithms to estimate the underwater acoustic channel.
OMP algorithm: OMP is a greedy pursuit algorithm, which invokes this idea iteratively to select the best matching column with the measurement vector from measurement matrix to approximate the sparse channel. The algorithm takes advantage of the sparsity of channel, avoids a NP-hard problem and improves the convergence rate.
Cai and Wang (2011) gave a short description of OMP algorithm:
|Initialize the set of non-zero elements as empty, the measurements are set as the residual, r = y
|Correlate all columns of measurement matrix T with the residual, THr, choose the largest element by magnitude and add its index to the set of nonzero elements
|With the constraint that only elements of h are nonzero that have been added to the set previously, find an estimate that using least-squares minimization
|Update the residual as
|Repeat steps 2-4 until either a known h is reached or the norm of residual |r|2 falls below a predetermined threshold
The algorithm has been popular mainly because it can be easily implemented and it never selects the same column twice since the residual is orthogonal to the columns that have already been chosen, which reduce the computational complexity.
CoSaMP: Tropp and Needell (2009) studied the CoSaMP algorithm to recover original signals, in the study, we will recover the sparse channel by this algorithm. The CoSaMP algorithm is at heart a greedy pursuit, but the difference to ordinary greedy pursuit is that the algorithm would find the largest k (k is the sparsity level) components to approximate the target signal at each iteration, while OMP algorithm finds the k components by many time iterations.
The sparse channel estimation based on CoSaMP uses an approach inspired by the RIP. Suppose the measurement matrix T has the RIP. For a k-sparse channel h, the vector u = T*T h can serve as a proxy for the channel h because the energy in each set of k components of u approximates the energy in the corresponding k components of h. In particular, the largest k entries of the proxy u point toward the largest k entries of the channel h. Since, the measurements have the form u = Th, we can obtain the proxy just by applying the matrix T* to the measurements.
During each iteration, the underwater acoustic channel based on CoSaMP performs the following major steps:
Initialization: The iteration time i = 0, residual r0 = y:
|Identify the large components of channel. Consider ui = T*ri is the proxy of the residual and locate the largest 2k components of the proxy, add their indexes to the set Ωp
Use LS algorithm computes the current channel estimators:
Choose the largest k estimators from the results of (9) and add their indexes to the set ΩLS:
|Merge the main components and add the indexes to the set Ωi, i.e., Ωi = Ωp∪ΩLS
|In the set Ωi from step 2, we estimate the channel use LS:
|where, T+ = (T*T)-1, T+ is the pseudo-inverse matrix of T.
|Retain only the largest k entries in Eq. 10 and set the others to zero. Use expresses the ith iteration channel impulse response estimator
|Update the residual as:
Those steps are repeated until the halting criterion is triggered.
Here, we presented present results based on numerical simulation. Both simulation parameters use the same OFDM system with the following specifications: Carrier frequency fc = 15 KHz, N = 256 subcarriers, channel length L = 60, sparsity level k = 6, 16 QAM modulation, the position of pilot symbols selected by selection matrix S, for convenient, the pilot symbols inserted uniformly. In this study, we compared the estimation performance of OMP and CoSaMP with the conventional LS algorithm. For LS algorithm, we consider the situation of p = 64 and p = 128 (p is the number of pilots symbols). For OMP and CoSaMP algorithms, we just consider the situation of P = 64.
Mean Squared Error (MSE) and the Bit Error Rate (BER) obtained with the three algorithms as a function of the SNR are shown in Fig. 1. The definition of MSE is:
As shown in Fig. 1 that for the three algorithms, the channel estimation MSE decreases linearly with the increasing values of SNR. For LS algorithm, the estimation performance is improved with the increase of the number of pilot symbols, but it still inferior to the sparse channel estimation algorithms based on CS. We find that both OMP and CoSaMP algorithms significantly outperform the LS estimator. Especially the CoSaMP algorithm, it can improve MSE about 10 dB, while OMP just improve 5 dB.
In Fig. 1b, it can see that the BER performance of OMP and CoSaMP significantly improved than LS, CoSaMP is ahead of the three algorithms. In more detail, when the SNR is below 10 dB, the BER of CoSaMP is similar to OMP and slightly less than LS, while when the SNR is larger than 10 dB, the performance outperforms OMP and LS more clearly with the increase of SNR. It is because OMP and CoSaMP take advantage of the sparse characteristics of underwater acoustic channel, avoid the meaningless taps estimation. So, the channel estimation based on CS can get better performance with fewer pilots than conventional LS algorithm. Moreover, the iteratively idea is used to estimate the nonzero taps in OMP and CoSaMP, allowing the estimation error caused by noise to be reduced. On the other hand, OMP only select an optimal atom to update the atom set at each iteration and once the atom added in the set will be kept all the time. While in the practical application, the atom is considered the best at this iteration cant promise always be the best at latter iterations, the atoms in the set should be removed and added freely.
|(a) MSE and (b) BER performance comparison of LS, OMP and CoSaMP algorithm
|Time comparison of three algorithms
CoSaMP can overcomes the shortcoming of OMP effectively, because its atoms selection principle invokes backtrack idea, the atoms realized removed and added freely, which promise the optimality of atom selection. In addition, the algorithm will select 2k atoms to update the set at each iteration, the estimation error is reduced by repeat iteration. So, the channel estimation performance is better than OMP.
Table 1 compares the computation time of three algorithms when the number of pilot symbols is 64.
From the table, we can see that the time of CoSaMP is the shortest, LS is the longest. Because both OMP and CoSaMP are greedy pursuit invoking this idea iteratively, which reduce the computational complexity. The difference between CoSaMP and OMP is that the CoSaMP algorithm would find the largest k components to approximate the sparse channel at each iteration, while OMP algorithm finds the k components by many time iterations.
In this study, we have introduced two channel estimation algorithms based on CS for underwater acoustic OFDM channel. The simulation results indicate that comparing with the conventional LS algorithm, both OMP and CoSaMP algorithms have lower computational complexity and the performance significantly improved, especially the CoSaMP algorithm. The proposed algorithms can get good performance with less pilots, which lead to high spectral efficiency. Therefore, the proposed algorithms are very suitable for the system with limited system band width and unlimited transmitted power.
The study was supported by Project of the Priority Academic Program Development of Jiangsu Higher Education Institutions, the National Natural Science Foundation of China (Grant No. 11204109) and the Natural Science Foundation of the Jiangsu Higher Education Institutions of China (Grant No.12KJB510003) and the graduate innovation fund of Jiangsu University of Science and Technology.
- Baraniuk, R.G., E. Candes, R. Nowak and M. Vetterli, 2008. Compressive sampling. IEEE Signal Process. Mag., 25: 12-13.
- Chen, W., L. Qi and F. Yanjun, 2010. An improved least square channel estimation algorithm for underwater acoustic OFDM systems. Proceedings of the 2nd International Conference on Future Computer and Communication, Volume 3, May 21-24, 2010, Wuhan, China, pp: 577-580.
- Donoho, D.L., 2006. Compressed sensing. IEEE Trans. Inform. Theory, 52: 1289-1306.
- Tropp, J.A. and D. Needell, 2009. CoSaMP: Iterative signal recovery form incomplete and inaccurate samples. Applied Comput. Harmonic Anal., 26: 301-321.
- Ying, L. and Y.M. Zou, 2009. Linear transformations and restricted isometry property. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, April 19-24, 2009, Washington, DC., USA., pp: 2961-2964.
- Zhang, Y., H. Sun, F. Xu and D. Wang, 2008. OFDM transform-domain channel estimation based on MMSE for underwater acoustic channels. Proceeding of the 2nd International Conference on Anti-Counterfeiting, Security and Identification, August 20-23, 2008, Guiyang, China, pp: 177-181.