Progress In Electromagnetics Research, PIER 87, 89103, 2008

CO CHANNEL INTERFERENCE CANCELLATION BY THE USE OF ITERATIVE DIGITAL BEAM FORMING METHOD M. Emadi and K. H. Sadeghi Department of Electrical Engineering Sharif University of Technology P.O. 11365-9363, Azadi St., Tehran, Iran A. Jafargholi Department of Electrical Engineering K. N. Toosi University of Technology P.O. Box: 16315-1355, Tehran, Iran F. Marvasti Department of Electrical Engineering Sharif University of Technology P.O. 11365-9363, Azadi St., Tehran, Iran AbstractThis paper deals with the possibilities of cancellation of unwanted signals by steering nulls of the pattern in the direction of arrival of signal while keeping the main beam to the desired direction. New iterative adaptive digital beam forming technique is presented here to enhance the conventional eectiveness of beam forming in common commercial application. Simulation and measurement results conrm that this algorithm can achieve eective Co-Channel Interference (CCI) suppression, while increasing the strength of the desired signal. 1. INTRODUCTION Adaptive beamforming techniques have been employed to enhance a desired signal while suppressing the interference, the jammer and the noise in an array of sensors [111]. With the thriving commercial wireless communication industry and the advancing microprocessor technologies, the adaptive beamforming techniques have found their

90

Emadi et al.

applications in commercial wireless communications, forming beams toward the desired signals while steering nulls to co-channel interferers. Thus, the system performance is optimized in terms of link quality and system capacity. Smart antennas have already been used in GSM and time-division multiple-access [12] and systems in the aim of replacing the conventional sector antenna by two or more closely spaced antenna elements [13]. Due to the system complexity, the fabrication cost and the operational expenditure, adaptive antennas are limited to base stations or military applications. Researchers are endeavoring to make low prole and low power consumption antennas for mobile terminals [14]. Some new approaches in adaptive beamforming techniques are proposed in [1519]. In this paper we propose a new low complexity iterative method to steering null to the CCI locations while forming beam to the desired direction without the use of temporal reference signal. In this paper iterative methods are used for the rst time in spatial reference beamforming area. In section two we review null steering concept in array processing, the iterative methods are introduced in section three. Section four shows the simulation results and the experimental results are shown in section ve. Finally we summarize the results in section six. 2. NULL STEERING BEAMFORMER In this section two null and beam steering methods known as constant and adaptive null steering are discussed. A null steering beam former is used to cancel a plane wave arriving from a known or un-known direction and thus produces a null in the response pattern of the plane waves direction of arrival. 2.1. Constant Null Steering Technique (Non-adaptive) One of the earliest schemes, referred to as DICANNE [20], achieves null steering by estimating the signal arriving from a known direction by steering a conventional beam in the direction of the source and then subtracting the output of this from each element. An estimate of the signal is made by delay-and-sum beam forming using shift registers to provide the required delay at each element, such that the signal arriving from the beam-steering direction appears in phase after the delay, and then sums these wave forms with equal weighting. This signal then is subtracted from each element after the delay. The process is very

Progress In Electromagnetics Research, PIER 87, 2008

91

eective for canceling strong interference and could be repeated for multiple interference cancellation. Although the process of subtracting the estimated interference using the delay-and-sum beam former in the DICANNE scheme is easy to implement for single interference, it becomes cumbersome as the number of interferences grows. A beam with unity response in the desired direction and nulls in interference directions may be formed by estimating beamformer weights using suitable constraints [20, 21]. Assume that s0 is the steering vector in the direction where unity response is required and that s1 , . . . , sk are k steering vectors associated with k directions where nulls are required. The desired weight vector is the solution of the following simultaneous equations: w H s0 = 1 w H si = 0 i = 1, . . . , k (1)

Using matrix notation, this becomes wH A = eT 1 (2) where A is a matrix with columns being the steering vectors associated with all directional sources including the look direction, that is, A = [s0 , s1 , . . . , sk ] (3) And e1 is a vector of all zeros except the rst element which is one, that is, e1 = [1, 0, . . . , 0]T (4) For k = L 1, A is a square matrix. When the numbers of required nulls are less than L 1, A is not a square matrix. A suitable estimate of weights may be produced using wH = eT AH (AAH )1 1 (5) Although the beam pattern produced by this beam former has nulls in the interference directions, it is not designed to minimize the uncorrelated noise at the array output. It is possible to achieve this by selecting weights that minimize the mean output power subject to above constraints. An application of a null steering scheme for detecting amplitudemodulated signals by placing nulls in the known interference directions is described in [22]. The use of a null steering scheme for a transmitting array employed at a base station is discussed in [23], which minimizes the interferences toward other co-channel mobiles. Most of the proposed methods intend to solve equation as simpler as possible with better performance. For example, in [24], Equation (2) was solved in a dierent manner and the results were interesting.

92

Emadi et al.

2.2. Optimal Beamformer (Adaptive Beam Former) The null steering scheme described in the previous section requires knowledge of the directions of interference sources, and the beam former using the weights estimated by this scheme does not maximize the output SNR. The optimal beam forming method described in this section overcomes these limitations and maximizes the output SNR in the absence of errors. It should be noted that the optimal beam former, also known as the minimum variance distortionless response (MVDR) beam former, described in this section does not require knowledge of directions and power levels of interferences as well as the level of the background noise power to maximize the output SNR. It only requires the direction of the desired signal as a spatial reference signal. Let an L-dimensional complex vector wH represent the weights of the beamformer that maximize the output SNR. For this array an expression for wH is given by [2527]: wH = R1 s0 N H R1 s s0 N 0 (6)

Where RN is the array correlation matrix of the noise alone, that is, it does not contain any signal arriving from the look direction. As the weights for the optimal beam former discussed above are computed using noise alone matrix inverse (NAMI), the processor with these weights is referred to as the NAMI processor. It is also known as the maximum likelihood (ML) lter [20], as it nds the ML estimate of the power of the signal source, assuming all sources as interference. It should be noted that RN may be not invertible when the background noise is very small. In this case, it becomes a rank decient matrix. In practice, when the estimate of the noise alone matrix is not available, the total array correlation matrix (signal plus noise) is used to estimate the weights and the processor is referred to as the SPNMI (signal-plus-noise matrix inverse) processor. An expression for the weights of the constrained processor for this case is given by [20]: wH = R1 s0 sH R1 s0 0 (7)

These weights are the solution of the following optimization problem: minimize wH Rw Hs = 1 when w 0 (8)

Thus, the processor weights are selected by minimizing the mean output power of the processor while maintaining unity response in the look direction.

Progress In Electromagnetics Research, PIER 87, 2008

93

It should be noted that the weights of the NAMI processor and the SPNAMI processor are identical; and in the absence of errors, the processor performs identically in both cases [20]. Most of the proposed methods intend to estimate R1 directly or indirectly. Some methods for optimal weight computation of an array antenna in the communications eld have been proposed in [28, 29]. In this paper, we propose a new method for olving equation (8) by the use of iterative methods; also we verify our results by simulation and experimental results. 3. ITERATIVE NULL STEERING According to Equation (7) we must solve this linear equation RwH = s0 (9)

For the unknown vector calculation of wH requires in general O(n3 ) operations (unless R has some special property that makes it easily invertible). Although it is possible to apply design an iteration that converges to the solution. Jacobi Theorem say that the solution to the linear system Ax = b can be obtained starting with x0 , and using iteration scheme xk+1 = M xk + C Where M = D 1 (L + U ) and C = D 1 b (11) (10)

where D, L and U are the diagonal, strictly lower triangular and strictly upper triangular parts of A respectively. If x0 is carefully chosen, a sequence {xk } is generated which converges to the suitable solution. A sucient condition for the method to be applicable is that A is strictly diagonally dominant or diagonally dominant and irreducible. The true sucient condition for Jacobi iteration to converge is that the spectral radius () of M = D 1 (L + U ) is less than 1. That is, the magnitude of the largest eigenvalue of M must be less than 1. Since the diagonal matrix is easily invertible, the Jacobi iteration has a particularly simple implementation. For our problem the Jacobi iteration corresponds to parallel interference method used in CDMA [3033] and Iterative Methods in Marvasti papers [3436] with ( = 1), Marvasti method also remove the linearity assumption of the modeling. Therefore when we have

94

Emadi et al.

nonlinear eects (receiver imperfections and nonlinearity) the proposed method works correctly. wk+1 = s0 (R I)wk For an initial guess of w0 = s0 , this corresponds to
k

(12)

wk =
i=0

(1)i (R I)i s0

(13)

The convergence of this iteration may be understood by considering the residual error in terms of the Taylor series expansion, R1 =

(1)i (R I)i ,
i=0

(R) < 2

(14)

This convergence occurs if the spectral radius of R will be lower than 2. In other words, the main idea of this algorithm is to rebuild the inverse of the system by iteration. If we dene I as the unity operator, we have: R1 = I I = R I E (15)

In this equation, we assume that E is the processing error. If the norm of the E was less than one (in linear case, this assumption is converted to the condition that spectral radius is lower than 2), then by using Taylor expansion for this function we have: R1 = I = I + E + E2 + E3 + E4 + . . . I E (16)

Now we dene the outputs in the ith and (i + 1)th iterations as follow: wi = (I + E + E 2 + . . . + E i1 )S0 wi+1 = (I + E + E 2 + . . . + E i )S0 According to the above equations, it could be easily shown that, wi+1 = (I R)wi + S 0 (18) (17)

This result is the same as the result of Jacobi Method. A simple generalization which improves on the Jacobi-style iteration is brought about by the introduction of a parameter or a sequence of parameters. By carefully selecting these parameters, the convergence speed of

Progress In Electromagnetics Research, PIER 87, 2008

95

the Jacobi method re-defeated, and the convergence speed can be improved [33]. A rst order iteration is given by: wi+1 = wi i (Rwi S 0 ) (19)

If R is symmetric positive denite, then the parameter that results in fastest convergence of the rst order stationary iteration is opt = 2 min + max (20)

where min and max are respectively the minimum and the maximum eigenvalues of R. A second order iteration, which depends on the two most recent estimates, is give by: wi+1 = i wi + (1 i )wi1 i (Rwi S 0 ) Where the best choice of and are, [33]: opt = 1+ opt = 1 2opt min + max 2
1min /max 1min /max 2

(21)

(22)

The Chebychev method is another iterative method in which the optimal k is known for a given number of iteration steps. The optimum value for k is given by [33]: iopt = max min cos 2 i 1/2 max + min + imax + 1 2 (23)

4. SIMULATION RESULTS For simulation, we used 4 ULA antennas with /4 distance, two interferences were located in 60 and 20 degrees and the beam was directed to the 20 degrees, the results were as follows. Figures 1 through 6, show that the simulated pattern versus iteration in Chebyshev and rst order stationary methods. 10 and 50 iterations of these methods are shown and the results are compared with optimum conventional beamformer. Simulations show that by use

96
Antenna pattern 20 10 0 -10 -20 [dB] -30 -40 -50 -60 -70 -80 -100 Conventional Optimum Beamformer First Order Iterative Method

Emadi et al.

-80

-60

-40

-20

20

40

60

80

100

azimuth angle [degrees]

Figure 1. Comparison between the conventional beamformer and rst order iterative method after 10 iterations.

Antenna pattern 20 10 0 -10 -20 [dB] -30 -40 -50 -60 -70 -80 -100 Conventional Optimum Beamformer First Order Iterative Method

-80

-60

-40

-20

20

40

60

80

100

azimuth angle [degrees]

Figure 2. Comparison between the conventional beamformer and rst order iterative method after 50 iterations.

Progress In Electromagnetics Research, PIER 87, 2008

97

-80

-60

-40

-20 0 20 40 azimuth angle [degrees]

60

80

100

Figure 3. Comparison between the conventional beamformer and second order iterative method after 10 iterations.
Antenna pattern 20 10 0 -10 -20 [dB] -30 -40 -50 -60 -70 -80 -100 Conventional Optimum Beamformer Second Order Iterative Method

-80

-60

-40

-20 0 20 40 azimuth angle [degrees]

60

80

100

Figure 4. Comparison between the conventional beamformer and second order iterative method after 50 iterations.

98
20 10 0 -10 -20 [dB] -30 -40 -50 -60 -70 -80 -100 Antenna pattern Conventional Optimum Beamformer Chebychev acceleration Met hod t

Emadi et al.

-80

-60

-40

-20 0 20 40 azimuth angle [degrees]

60

80

100

Figure 5. Comparison between the conventional beamformer and chebychev acceleration method after 10 iterations.
Antenna pattern 10 0 -10 -20 -30 [dB] -40 -50 -60 -70 -80 -200 Conventional Optimum Beamformer Chebychev acceleration Meth thod

-150

-100

-50 0 50 azimuth angle [degrees]

100

150

200

Figure 6. Comparison between the conventional beamformer and chebychev acceleration method after 50 iterations.

Progress In Electromagnetics Research, PIER 87, 2008

99

of only 50 iterations in Chebychev method the results will be better than conventional beamformer and there is no need for more iteration. In terms of the peak at 20 degrees and null at 20 and 60 degrees, the conventional optimum beamformer method achieves the best nulls but the worst peak. The Chebychev method performs best, both in terms of Null and peak and in terms of providing a fast convergence. According to the fact that there are not more than two or three jammers or interferences in military or civil wireless communications, it is not reasonable to use more than 6 elements. But according to the fact that the presented method is independent of the number of sources there is no need to simulate for a more complicated case. The simulation result for 25 element arrays is shown in Fig. 7.
Antenna pattern 20
Conventional Beamforming Chebychev Acceleration Method

Desired Nulls

-20

[dB ]

-40

-60

-80

-100 -100

-80

-60

-40

-20 0 20 azimuth angle [degrees]

40

60

80

100

Figure 7. Comparison between the conventional beamformer and Chebychev acceleration method after 50 iterations for 25 elements array. To compute the computational burden of this algorithm we computed the FLOPS of these algorithms. The results show that FLOPS of conventional optimum beamformer for a 1000-element array were approximately 2 109 but FLOPS of iterative method for 1000element arrays after 20 iterations were approximately 2 107 which is approximately order of the magnitudes less than the previous methods.

100

Emadi et al.

Figure 8. Experimental results from beamforming a target at 60 degrees.

10

[dB]

-10

-20

-30

-40 -80 -60 -40 -20 0 20 40 60

azimuth angle [degrees]

Figure 9. Antenna pattern for 4-element array, beam forming at 60 degrees. 5. EXPERIMENTAL RESULTS A simple receiver with four elements antenna array was implemented. There was a desired signal source at 60 degrees from the receiver array. In signal processing unit, 64 sec (16000 pulses) of the received data are processed coherently. To test the proposed beamforming algorithm, we have performed beamforming on signals in the [80 80] degrees, with steps of 5 degrees in the range of this source. As we can see from Fig. 8,

Progress In Electromagnetics Research, PIER 87, 2008

101

-150

-100

-50

50

100

150

200

azimuth angle [degrees]

Figure 10. Beam forming at 20 degrees using iterative method. the results show a peak in 60 degrees (according to the source). In order to validate the results, a simulation on the 4-element array antenna has been performed. Array antenna pattern with beamforming in 60 degrees is shown in Fig. 9. As can be seen in these two last gures, results from experimental and simulated data are in a good agreement. This proves the validity of beamforming method and the structure of the array. Then we used the results of this experiment and performed the iterative method mentioned in the previous sections to achieve a peak at 20 degrees. The result is shown in Fig. 10. In Fig. 10, we have achieved a null at 60 degrees where the source is placed and a peak at 20 degrees. It is obvious that the performance of this method is completely veried in this experiment. 6. CONCLUSIONS This paper presented a robust and computationally ecient iterative beamforming algorithm for rejecting spatially interferences. To simplify the implementation we have only used 4 elements but the results are correct for any number of elements. We only use Iterative methods to solve limits of the conventional inverse matrix calculation which isnt ecient when the matrix is ill-condition. The simulation and experimental results shows that this algorithm converges only after 20 iterations.

102

Emadi et al.

REFERENCES 1. Qu, Y., G. Liao, S.-Q. Zhu, X.-Y. Liu, and H. Jiang, Performance analysis of beamforming for MIMO radar, Progress In Electromagnetics Research, PIER 84, 123134, 2008. 2. Gu, Y. J., Z. G. Shi, and K. S. Chen, Robust adaptive beamforming for steering vector uncertainties based on equivalent DOAs method, Progress In Electromagnetics Research, PIER 79, 277290, 2008. 3. Dessouky, M. I., H. A. Sharshar, and Y. A. Albagory, A novel tapered beamforming window for uniform concentric circular arrays, Journal of Electromagnetic Waves and Applications, Vol. 20, No. 14, 20772089, 2006. 4. Zhang, X. and D. Xu, Deterministic blind beamforming for electromagnetic vector sensor array, Progress In Electromagnetics Research, PIER 84, 363377, 2008. 5. Jeong, Y.-S. and J.-H. Lee, Estimation of time delay using conventional beamforming-based algorithm for UWB systems, Journal of Electromagnetic Waves and Applications, Vol. 21, No. 15, 24132420, 2007. 6. Dessouky, M. I., H. A. Sharshar, and Y. A. Albagory, Improving the cellular coverage from a high altitude platform by novel tapered beamforming technique, Journal of Electromagnetic Waves and Applications, Vol. 21, No. 13, 17211731, 2007. 7. Babayigit, B., A. Akdagli, and K. Guney, A clonal selection algorithm for null synthesizing of linear antenna arrays by amplitude control, Journal of Electromagnetic Waves and Applications, Vol. 20, No. 8, 10071020, 2006. 8. Naghshvarian-Jahromi, M., Novel Ku band fan beam reector back array antenna, Progress In Electromagnetics Research Letters, Vol. 3, 95103, 2008. 9. Singh, A. K., P. Kumar, T. Chakravarty, G. Singh, and S. Bhooshan, A novel digital beamformer with low angle resolution for vehicle tracking radar, Progress In Electromagnetics Research, PIER 66, 229237, 2006. 10. Abdelaziz, A. A., Improving the performance of an antenna array by using radar absorbing cover, Progress In Electromagnetics Research Letters, Vol. 1, 129138, 2008. 11. Capineri, L., Estimation of relative permittivity of shallow soils by using the ground penetrating radar response from dierent buried targets, Progress In Electromagnetics Research Letters, Vol. 2, 6371, 2008.

Progress In Electromagnetics Research, PIER 87, 2008

103

12. Fakoukakis, F. E., et al., Development of an adaptive and a switched beam smart antenna system for wireless communications, Journal of Electromagnetic Waves and Applications, Vol. 20, No. 3, 399408, 2006. 13. Varlamos, P. K. and C. N. Capsalis, Electronic beam steering using switched parasitic smart antenna arrays, Progress In Electromagnetics Research, PIER 36, 101119, 2002. 14. Mouhamadou, M. and P. Vaudon, Smart antenna array patterns synthesis: Null steering and multi-user beamforming by phase control, Progress In Electromagnetics Research, PIER 60, 95 106, 2006. 15. Pedersen, K. I., P. E. Mogensen, and B. H. Fleury, A stochastic model of the temporal and azimuthal dispersion seen at the base station in outdoor propagation environments, IEEE Trans. Veh. Technol., Vol. 49, No. 2, 437447, 2000. 16. Vorobyov, S. A., A. B. Gershman, and Z. Q. Luo, Robust adaptive beamforming using worst-case performance optimization: A solution to the signal mismatch problem, IEEE Trans. Signal Processing, Vol. 51, No. 2, 313324, 2003. 17. Li, J., P. Stoica, and Z. Wang, On robust capon beamforming and diagonal loading, IEEE Trans. Signal Processing, Vol. 51, No. 7, 17021715, 2003. 18. Lorenz, R. G. and S. P. Boyd, Robust minimum variance beamforming, IEEE Trans. Signal Processing, Vol. 53, No. 5, 16841696, 2005. 19. Besson, O., A. A. Monakov, and C. Chalus, Signal waveform estimation in the presence of uncertainties about the steering vector, IEEE Trans. Signal Processing, Vol. 52, No. 9, 2432 2440, 2004. 20. Godara, L. C., Smart Antennas, CRC Press, 2004. 21. Assumpcao, D. and G. E. Mountford, An overview of signal processing for arrays of receivers, J. Inst. Eng. Aust. IREE, Aust., 1984. 22. Choi, S., T. K. Sarkar, and S. S. Lee, Design of two-dimensional Tseng window and its application to antenna array for the detection of AM signal in the presence of strong jammers in mobile communications, IEEE Signal Process., Vol. 34, 297310, 1993. 23. Chiba, I., T. Takahashi, and Y. Karasawa, Transmitting null beamforming with beam space adaptive array antennas, Proceedings of IEEE 44th Vehicular Technology Conference, 1498 1502, 1994.

104

Emadi et al.

24. Stuckman, B. E. and J. C. Hill, Method of null steering in phased array antenna systems, Electronic Letters, Vol. 26, No. 15, July 1990. 25. Applebaum, S. P., Adaptive arrays, IEEE Trans. Antennas Propagat., Vol. 24, 585598, 1976. 26. Reed, I. S., J. D. Mallett, and L. E. Brennan, Rapid convergence rate in adaptive arrays, IEEE Trans. Aerosp. Electron. Syst., Vol. 10, 853863, 1974. 27. Bresler, Y., V. U. Reddy, and T. Kailath, Optimum beamforming for coherent signal and interferences, IEEE Trans. Acoust. Speech Signal Process., Vol. 36, 833843, 1988. 28. Bertland, J. and P. Forster, Optimal weigths computation of an emitting antenna array The Obele algorithm, IEEE Trans. Signal Processing, Vol. 51, No. 7, July 2003. 29. Patel, P. and J. Holtzman, Analysis of a simple successive interference cancellation scheme in a DS/CDMA system, IEEE J. Select. Areas Commun., Vol. 12, No. 5, 796807, June 1994. 30. Kaul, A. and B. Woerner, Analytic limits on the performance of adaptive multistage interference cancellation, IEE Electron. Lett., Vol. 30, 20932094, Dec. 1994. 31. Varanasi, M. K. and B. Aazhang, Near optimum detection in synchronous code-division multiple-access systems, IEEE Trans. Commun., Vol. 39, No. 5, 725736, May 1991. 32. Rasmussen, L. K., Y. Ma, D. Guo, and T. J. Lim, Aspects on linear parallel interference cancellation in CDMA, IEEE Int. Symp. Inform. Theory, 37, Cambridge, USA, Aug. 1998. 33. Grant, A. and C. Schlegel, Iterative implementation for linear multiuser detectors, Department of Electrical Engineering, University of Utah, 1999. 34. Marvasti, F., An iterative method to compensate for the interpolation distortion, IEEE Trans. ASSP, Vol. 3, No. 1, 1617 1621, 1989. 35. Marvasti, F., Nonuniform Sampling: Theory and Practice, Kluwer Academic/Plenum Publishers, 2001. Trans. Med. Imag., Vol. 18, No. 11, Nov. 1999. 36. Marvasti, F., M. Analoui, and M. Gamshadzahi, Recovery of signals from nonuniform samples using iterative methods, IEEE Trans. ASSP, Vol. 39, No. 4, 872878, Apr. 1991.