Method of Modulation Recognition Based on Combination Algorithm of K-Means Clustering and Grading Training SVM

Faquan Yang, Ling Yang＊, Dong Wang, Peihan Qi Haiyan Wang

1 School of Electrical and Information Engineering, Foshan University, Foshan 528000, China

2 Xinhua College of Sun Yat-sen University, Guanzuo 523133, China

3 State Key Laboratory of Integrated Service Networks, Xidian University, Xian 710071, China

Abstract: For the existing support vector machine, when recognizing more questions,the shortcomings of high computational complexity and low recognition rate under the low SNR are emerged. The characteristic parameter of the signal is extracted and optimized by using a clustering algorithm, support vector machine is trained by grading algorithm so as to enhance the rate of convergence, improve the performance of recognition under the low SNR and realize modulation recognition of the signal based on the modulation system of the constellation diagram in this paper. Simulation results show that the average recognition rate based on this algorithm is enhanced over 30%compared with methods that adopting clustering algorithm or support vector machine respectively under the low SNR. The average recognition rate can reach 90% when the SNR is 5 dB, and the method is easy to be achieved so that it has broad application prospect in the modulating recognition.

Keywords: clustering algorithm; feature extraction; grading algorithm; support vector machine; modulation recognition

I. INTRODUCTION

Modulation recognition is widely used in signal detection, information interacting, interference query and some aspects in wireless communication of military and civil use, and is a basic problem for spectrum sensing in cognitive radios. Therefore, how to extract the characteristic value and the continuous innovation of classifier algorithm becomes the important parts in the research of modulation recognition [1-2].

Clustering algorithms based on density such as DBSCAN, OPTICS, and DENCLUE,and based on distance such as K-MEANS,K-MEDOIDS, and CLARANS have been proposed [3-4]. By directly using these clustering algorithms, the feature of the signal can be extracted so that modulation recognition of the communication signals can be achieved, but these methods of modulation recognition have lower recognition rate under the condition of serious noise interference.

Regarding the problem existing in the modulation recognition, the references [5-6]indicate high computational complexity exists if using the modulation recognition method based on the conventional support vector machine (SVM). Especially under the low SNR,the recognition rate of the modulation signal is low. In the references [7-8], the methods of modulation recognition utilizing neural network classifier based on BP algorithm were discussed. Improved algorithms of BP are adopted on the purpose of overcoming the drawbacks that the convergence rate of BP algorithm is low and BP algorithm is easy to have local minimum point. The modulation recognition rate is obviously improved under the low SNR, but the effect is still unsatisfied.In this paper, the combination of a k-means clustering algorithm and SVM is adopted in order to extract the feature of signal. The constellation diagram of the signal is rebuilt by using the clustering algorithm. The relating characteristic parameters under different clustering centers are calculated by applying validity function and the SVM classifier is trained by using grading algorithm [9-11].

This paper firstly summarizes clustering algorithm which are used in the eigenvalue extraction and optimization, and some disadvantages when conventional SVM classifier is applied in modulation recognition. Thus, a new combined method of clustering algorithm and SVM is important to be proposed in signal modulation recognition.

In Section 2 and 3, clustering algorithm and SVM classification method are briefly introduced respectively. In Section 4, the principle of combining modulation recognition method by using clustering algorithm and grading algorithm SVM is to be submitted. All kinds of modulation recognition simulation results and comparative analysis are presented in Section 5. Finally, conclusion is achieved in Section 6.

Combined algorithms of modulation recognition based on clustering and grading algorithm SVM is proposed in this paper.

II. ALGORITHM OF CLUSTERING

Clustering algorithm can be directly used in the extraction of the characteristic values of a signal, which makes the modulation recognition of communication signals achieved[12-13]. Meanwhile, SVM can be combined with the clustering algorithm so as to achieve modulation recognition of signals. Regarding to the received signal which is waited for recognition, it is reprocessed at first,then is done frequency conversion through carrier, low-pass filtered, sampled and other preprocesses for the signal, which make the value of cophase component and quadrature component of the received signal obtained.Let the sample point sign of the received observed signals expressed by the data set as:X ={x1,x2,…xn}, where n is the number of elements of data set and sample point express by 2d vector xj=[xji, xjq]T, where xjiis cophase component of the received sign and xjqis quadrature component of the received sign so that all received signal sample can be regarded as received constellation diagram which is made up by the signal of 2d vector.Center of clustering and membership of the class center in each sample can be obtained by optimizing objective functions, which can make the membership of the sample decided.

III. SUPPORT VECTOR MACHINE

SVM is developed based on statistical learning theory, the basic idea can be summarized as follows: firstly, by nonlinear transforming the input space into a high dimensional space, and then the optimal linear classification hyperplane can be obtained in the new space. The given training data:

So the SVM learning goal is to construct a discriminant function, and separated the two kinds of mode as correctly as possible. Then the constructed decision function finally can be turned into a typical quadratic programming (QP) problem, namely in the constraint condition presented as following:

Then the minimum value of following functions under the above conditions can be obtained.

So the optimal separating hyperplane can be obtained [14-15].

The SVM method is essentially a nonnegative quadratic optimization problem and it is able to get the analytical solution of the global optimal in theory. Thus, there is no local optimized problem for the SVM. Compared with the neural network classifier which is easy to result the insufficient learning or promotion ability due to the strong influence from the complexity of the network structure and sample size, SVM have excellent learning ability and generalization ability for the analysis of small sample data, and can be effectively applied in pattern recognition, function estimation, and modulation recognition. In order to overcome the shortcoming of high computation complexity when the conventional SVM is used in identify different kinds of problem,grading algorithm is adopted in training for SVM so as to improve the convergence speed and system identification performance [16-17].

IV. THE PRINCIPLE OF COMBINING MODULATION

Aiming at the MPSK/MQAM modulating signal based on constellation diagram modulation system, the modulation recognition method based on combining the clustering and grading algorithm SVM is adopted, which makes modulation recognition of signal achieved, recognition system model is shown in Figure 1.

The system is composed of four parts which are the signal preprocessing, the extraction feature value using clustering algorithm, the training of SVM and modulation recognition using classifier of SVM.

At first, the received signal is reprocessed.Then the clustering algorithm such as k-means clustering is utilized to reconstruct the signal constellation graph. After that, validity function is applied to calculate different function values in different clustering center so that these function values can be regarded as the input characteristic parameters of SVM. In this system, utilizing the k-means clustering,reconstructing the signal constellation diagram, and extracting the feature parameters are particularly important.

4.1 Signal preprocessing

The process of preprocessing the received signal is mainly the frequency conversion through carrier, low-pass filtered, sampled and other preprocesses for the signal, which makes the value of cophase component and the quadrature component of the received signal obtained.

4.2 Extraction feature values using clustering algorithm

After preprocessing the signal for obtaining the data set X, the clustering algorithm of the data set of sample points such as k–means clustering can be executed. K-means clustering algorithm can be automatically used to classify data objects, the clustering center and the degree of membership which each sample point is subordinate to the class-center is obtained by optimizing the objective function,thus determining the belonging of the sample points. K–means clustering problem can be expressed as the following mathematical programming problem, the objective function is:

Fig. 1. Recognition system model.

Where N is the number of the elements in the data set X, k is the number of the center of clustering, signals to be recognized are 2PSK,4PSK, 8PSK, 16QAM, 32QAM, 64QAM et al, its modulation orders are 2n(n =1,2,… 6)respectively, let the number of center of clustering K=2n(n=1,2,3,4,5,6),and made clustering algorithm according to six kinds of the circumstances respectively. Algorithm is realized in the following iteration calculation

STEP1: Define standard of iterative ε＞0,matrix of initialized classification V(0),n=0:

STEP2: Calculating matrix of update iterative U(n)

STEP3: Calculating center clustering matrix V(n+1)

STEP4: Comparing V(n+1)and V(n)by norm of matrixlet

Then iteration will be stopped, otherwise let n=n+1, turn to step 2.

Through the above iterative process, the objective function in the type (4) can be optimized so that the optimized center of clustering and the membership matrix of each sample point to the center of clustering can be obtained by the iteration of the objective function optimized above. For the signal of different modulation order, in order to obtain the characteristic parameter of different modulation system which can be distinguished, its best number of center of clustering is different. The result of clustering is carried on efficiency analysis for different number of center of clustering k, whether it is reasonable or not to divide signal location into k which made the validity function value obtained and different modulating signal can be distinguished.

Let the number of clustering center k is2, 4, 8, 16, 32 and 64 respectively, in other words, the clustering algorithm is carried out for the received signal point under the 6 different number of clustering center and the valid function value under different k is calculated respectively as the characteristic parameter which can distinguish different modulation type. Under different SNR and the number of clustering center, the characteristic parameter T2, T4, T8, T16and T32of six modulation ways are calculated respectively. They can be shown in the table I.

Table I. Characteristic parameter of six modulation ways under different SNR and the number of clustering center.

As can be observed in the table I, the characteristic value T2of the modulating signal is obviously higher than other five modulation systems under different SNR. Thereby, BPSK can be distinguished from other modulation systems by characteristic parameter T2. Similarly, under different SNR, the characteristic parameter T4of QPSK is obviously higher than other four modulation system; the characteristic parameter T8of 8PSK is obviously higher than other three modulation system;the characteristic parameter T16of 16QAM is obviously greater than other two modulation system; the characteristic parameter T32of 32QAM is obviously higher than the 64QAM modulation system. Thereby, QPSK, 8PSK,16QAM and 32QAM can be classified respectively by T4, T8, T16, and T32which makes modulation recognition of six signals achieved.

4.3 Grading training of SVM

In order to improve the performance of the modulation recognition system, SVM is trained by the new combination of six characteristic parameters extraction by a using the algorithm of clustering as the input of SVM.Then six modulation systems based on a constellation diagram are recognized. Meanwhile,in order to overcome the shortcoming of high computation complexity when the conventional SVM is used in identify different kinds of problem, and meet the setting requirements of precision, grading algorithm is adopted in this paper to train the SVM (shown in Figure 2).

In Figure 2, the SVM training has 5 grades.For the first grade, the characteristic vector group which consists of clustering center values T2under the conditions of different SNR(see table 1).

the SVM can be trained by using (9) type characteristic vector group so that 2PSK can be identified; Successively, the 2nd, 3rd, 4th,5th grade SVM can be respectively trained by characteristic vector groups which consists of clustering center values T4, T8, T16, T32under different SNR so as to achieve the recognition of 4PSK, 8PSK, 16QAM, 32QAM and 64QAM signal modulation modes. However,for the conventional non-grading SVM training algorithm, as simultaneously using (10),the characteristic vector groups which consist of T2, T4, T8, T16, T32under different SNR (-2,0, 2, 4, 6, 8, 10) training.

Through comparing between (9) and (10),it can be seen that the computational complexity is much bigger, training function has long convergence time, and even error phenomenon sometimes appears if not using the grading training algorithms.

Fig. 2. Classifier of grading algorithm SVM.

4.4 Modulation recognition of SVM classifier

After training SVM, regarding to an unknown modulation signal, when modulation recognition are executed based on combined algorithm of clustering and SVM which are proposed in this paper, the process should be executed as following:

STEP1: a data set X of signal which contains cophase component and the orthogonal component is obtained after preprocess.

STEP2: the membership matrix of clustering center in each signal point is obtained by k-means clustering algorithm for data set X.

STEP3: the characteristic parameters vectors which can distinguish different modulation systems are obtained by applying valid function to conduct the membership matrix.

STEP4: the characteristic parameters are regarded as input to be sent to SVM which has trained. Modulation type of unknown signal can be obtained from the output of SVM,which makes the automatic recognition of modulation achieved.

V. SIMULATION AND PERFORMANCE ANALYSIS

The computational complexity and convergence are simulated when SVM adopts grading training algorithm, the conventional training algorithm and the classifier uses MLP by BP algorithm respectively. Modulation recognition of six modulating signal which contain BPSK, QPSK, 8PSK, 16QAM, 32QAM, and 64QAM are simulated by adopting clustering method, SVM algorithm regularly, combined modulation recognition algorithm of clustering and Grading Training SVM respectively under the situation that the simulation parameters is given as follow: the frequency of main carrier is 4MHz, frequency of sampling is 120MHz,The symbol rate is 106baud, the data length is 2048 and the SNR is: -2dB,0dB,4dB,8d-B,10dB respectively, The statistic of correct recognition rate is obtained when each situation is experimented for 1000 times. Meanwhile, the average recognition rate which system recognized for various modulations is calculated under different SNR when the probability of each modulation is same.

1) Compared with the conventional training algorithm and MLP by BP algorithm, there is a simulation showing the computation complexity of the grading training algorithm used in SVM shown in table 2.

According to the simulation data (in table II), the duration of SVM grading training algorithm which is applied in this paper is 338.57 seconds. This duration is obviously lower than the duration of the conventional SVM training algorithm (589.65 seconds) and the duration of the MLP by BP algorithm (578.59 seconds)which shows the computation complexity of the algorithm used in this paper is lower than the conventional SVM algorithm and MLP by BP algorithm.

2)The simulation of convergence performance

In Figure 3, SVM is trained by using grading algorithm, then its convergence performance is better than the training convergence performance of conventional SVM, MLP by BP algorithm respectively and it can reach thedemand of design for targeted function when setting error of mean square is 0.011 by only iteration 280 steps.

3)The simulation of modulation recognition

The simulation of modulation recognition rate related to the fuzzy k-means algorithm,SVM classifier and combined modulation recognition algorithm is shown in Figure 4,Figure 5, and Figure 6 respectively.

The correct rate of modulation recognition of six kinds of signal has a small difference when modulation recognition which use of SVM classifier, MLP classifier respectively and the correct recognition rate are not high also under the condition of low SNR in Figure 5 and Figure 6.

In Figure 7, compared with Figure 4, Figure 5, Figure 6 respectively, the recognition rate of algorithm put forward in this paper is obviously enhanced compared with the clustering algorithm or SVM classifier or MLP classifier which is adopted alone under different SNR.For example, when the SNR is -2dB, by using the method proposed in this paper, the average recognition rate for six signals is 59%, which is higher than those by using the clustering algorithm(30%) or SVM classifier(22%) or MLP classifier(28%). The recognition rate of four modulation systems consisted of 2PSK,4PSK, 8PSK and16QAM is closer is to 90%when SNR is 4dB. The modulation recognition rate of 32QAM and 64QAM is obviously enhanced, and the modulation recognition rate of 32QAM under SNR=6dB can reach 98%.The modulation recognition rate of 64QAM under SNR=2dB can reach 70% which is far higher than the recognition rate of clustering or SVM classifier based on which is adopted alone. Main reasons for improving the performance of system modulation identification are that: first of all, characteristic value extracted from the signal went to identify is optimized treating by using clustering algorithm. Secondly, the combining modulation recognition algorithm of k-means clustering and graded training SVM is applied in this paper, which overcomes the shortcoming of high computa-tion complexity when the conventional SVM is used in identify different kinds of problem,improves the convergence speed, and greatly improves modulation recognition rate under the condition that SNR of the signal is low.

Fig. 3. The simulation diagram of SVM training convergence performance.

Fig. 4. The simulation of modulation recognition rate related to the fuzzy k-means algorithm.

Fig. 5. The simulation of modulation recognition rate related to conventional SVM classifier.

Fig. 6. The simulation of modulation recognition rate related to neural network classifier based on BP algorithm.

Fig. 7. The simulation of modulation recognition rate based on combined algorithm of clustering and Grading Training SVM.

VI. CONCLUSIONS

Combined algorithms of modulation recognition based on clustering and grading algorithm SVM is proposed in this paper. Selection of several typical communication system based on the modulation method of constellation graph: 2 PSK, 4 PSK, 8 PSK and 16 QAM, 32 QAM and 64 QAM. Clustering algorithm and its validity function is utilized to extract six kinds of characteristic parameters which have a significant difference between the reflecting the modulation type and these parameters are regarded as the input of the SVM classifier.The SVM is trained by grading algorithm in order to improve the system modulation recognition performance. The simulation results show that compared with using clustering algorithm or conventional SVM classifier for modulation recognition respectively, there is significant increase in system recognition rate because of the combined modulation recognition algorithm which is put forward in this paper and based on clustering and SVM.

ACKNOWLEDGEMENTS

The authors wish to thank my classmates and friends in our laboratory such as Zhongxian Pan, Dr. Jie Zheng et al. This work was supported in part by the National Natural Science Foundation of China under Grand No.61871129 and No. 61301179, the Projects of Science and Technology Plan Guangdong Province under Grand No. 2014A010101284.