Localization algorithm for large-scale wireless sensor networks based on FCMTSR-support vector machine

Abstract

Sensor node localization is one of research hotspots in the applications of wireless sensor network field. A localization algorithm is proposed in this article which is based on improved support vector machine for large-scale wireless sensor networks. For a large-scale wireless sensor network, localization algorithm based on support vector machine faces to the problem of the large-scale learning samples. The large-scale training samples will lead to high burden of the training calculation, over learning, and low classification accuracy. In order to solve these problems, this article proposed a novel scale of training sample reduction method (FCMTSR). FCMTSR takes the training sample as point set, get the potential support vectors, and remove the non-boundary outlier data immixed by analyzing relationships between points and set. To reduce the calculation load, fuzzy C-means clustering algorithm is applied in the FCMTSR. By the FCMTSR, the training time is reduced and the localization accuracy is improved. Through the simulations, the performance of localization based on FCMTSR-support vector machine is evaluated. The results prove that the localization precision is improved 2%, the training time is reduce 55% than existing localization algorithm based on support vector machine without FCMTSR. FCMTSR-support vector machine localization algorithm also addresses the border problem and coverage hole problem effectively. Finally, the limitation of the proposed localization algorithm is discussed and future work is present.

Introduction

Wireless sensor network (WSN) is a multi-hop, self-organizing wireless communication network system by deploying a large number of cheap micro-sensor nodes in the monitoring region. Its purpose is to perceive, gather, and process the information detected by the tiny sensors in the coverage area and send the useful information to the observers and control centers. ¹ Localization is the key to many WSN applications, such as network management, environmental monitoring, target tracking, and routing. WSN node localization technology has gained wide attention and become one research hotpot of WSN.

There is a lot of work done in the field of localization in WSNs. WSN node localization can be divided into two major categories. One is the localization scheme in the centralized manner, such as semi-definite programming^2,3 and multidimensional scaling.^4,5 The other category is the localization scheme in the distributed manner, such as DV-Hop,^6,7 MDS-MAP,^8,9 and MDL. ¹⁰ The localization algorithm in distributed manner has lower computation and communication costs, so it is suitable for large-scale WSNs.

In recent years, many scholars proposed the localization algorithm based on machine learning.^11–16 In learning-based approaches, a model is built based on training data gathered from the network, and then each sensor node can estimate position itself using trained model. ¹⁷ Therefore, learning approaches can be used in a distributed manner, and each sensor can be localized independently from other sensor nodes.

Support vector machine (SVM) is a machine learning methods which evolved from the statistical learning theory. SVM has high generalization ability and good classification precision. Moreover, SVM can solve the overfitting problem effectively. So, SVM has been applied to a number of fields, such as classification and regression fields. There has been some localization algorithm based on SVM in Pan et al., ¹² Xu et al., ¹³ Kim et al., ¹⁴ Safa, ¹⁵ Mao et al., ¹⁶ and Huan et al. ¹⁷ But for a large-scale WSN, localization algorithm based on SVM faces to the problems of the large-scale learning samples. The large-scale learning samples will lead to high burden of the training calculation, over learning, and low classification accuracy. These problems will lead to localization algorithm impractical. In this article, we will try to improve the SVM training process to reduce training time, computation cost, and achieve more localization accurate.

The rest of this article is organized as follows. Section “Localization based on SVM” briefly introduces theories related to SVM and explains localization algorithm based on SVM. Section “Large-scale training samples reduction method (FCMTSR)” introduces our improved large-scale training sample reduction method for SVM (FCMTSR-SVM) to further modification of nodes’ positions and reduce training time. Section “Simulation of localization algorithm based on SVM-FCMTSR” shows the simulation results of localization algorithm based on FCMTSR-SVM. Section “Discussion” discusses the benefits and limitations of proposed localization algorithm. Finally, this article is concluded in section “Conclusion.”

Localization based on SVM

Basic theory of SVM

SVM is based on the principle of structural risk minimization. ¹⁸ The idea of SVM is to gain an optimal hyperplane in the feature space, and the hyperplane can separate the two-class data with largest interval. SVM is a machine learning algorithm, so it needs to be trained to build the model. SVM can solve linear and nonlinear classification. If the training samples are nonlinear, SVM maps the samples into a high-dimensional feature space by a nonlinear mapping function, where samples become linearly separable and the optimal classification hyperplane is constructed. To solve the problem of dimension disaster in high-dimension space, SVM introduces the kernel function.^19–21

According to idea of SVM, the hyperplane can not only separate the two-class data but also make classification interval largest. It is assumed that the linearly separable sample sets $({\mathrm{x}}_{\mathrm{i}},{\mathrm{y}}_{\mathrm{i}})$ , $\mathrm{i}=1,2,\dots ,\mathrm{n}$ , $\mathrm{x}\in {\mathrm{R}}^{\mathrm{d}}$ , and $\mathrm{y}\in \{+1,-1\}$ is the class number. The classification hyperplane in the d-dimensional space is expressed in equation (1)

$$\mathrm{\omega }·\mathrm{x}+\mathrm{b}=0$$

(1)

After the normalization, classification interval is described in equation (2)

$$\frac{|1-\mathrm{b}+1+\mathrm{b}|}{\Vert \mathrm{\omega }\Vert }=\frac{2}{\Vert \mathrm{\omega }\Vert }$$

(2)

The problem of searching optimal classification hyperplanes is converted into getting the minimum value by satisfying the conditions

$$\begin{array}{c}\underset{\mathrm{w},\mathrm{b}}{min}\frac{1}{2}\Vert \mathrm{w}{\Vert }^2+\mathrm{C}\sum _{i=1}^l{\mathrm{\xi }}_{\mathrm{i}}\hfill \\ \mathrm{s}.\mathrm{t}.{\mathrm{y}}_{\mathrm{i}}((\mathrm{\phi }({\mathrm{x}}_{\mathrm{i}})*\mathrm{w})+\mathrm{b})\ge 1-{\mathrm{\xi }}_{\mathrm{i}},{\mathrm{\xi }}_{\mathrm{i}}\ge 0,\mathrm{i}=1,\dots ,l\hfill \end{array}$$

(3)

where * is the inner product, w are the coefficient vectors, and ${\mathrm{\xi }}_{\mathrm{i}}$ are the slack variables. C is the penalizing parameter which is selected by the user. Equation (3) shows that the problem of searching for optimal hyperplane is translated into an optimization problem. The minimum can be evaluated by the Lagrange multipliers. Equation (4) describes transformed quadratic programming problem

$$\begin{array}{c}min\mathrm{Q}(\alpha )=min\{\sum _{i=1}^{\mathrm{n}}{\mathrm{\alpha }}_{\mathrm{i}}-\frac{1}{2}\sum _{\mathrm{i},\mathrm{j}=1}^{\mathrm{n}}{\mathrm{\alpha }}_{\mathrm{i}}{\mathrm{\alpha }}_{\mathrm{j}}{\mathrm{y}}_{\mathrm{i}}{\mathrm{y}}_{\mathrm{j}}\mathrm{K}({\mathrm{x}}_{\mathrm{i}},{\mathrm{x}}_{\mathrm{j}})\}\hfill \\ \mathrm{s}.\mathrm{t}.\sum _{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{y}}_{\mathrm{i}}{\mathrm{a}}_{\mathrm{i}}=0,0\le \alpha \le {\mathrm{C}}_{\mathrm{i}},\mathrm{i}=1,2,\dots ,\mathrm{n}\hfill \end{array}$$

(4)

where ${\mathrm{\alpha }}_{\mathrm{i}}$ are the Lagrange multipliers of ${\mathrm{x}}_{\mathrm{i}}$ , $\mathrm{K}({\mathrm{x}}_{\mathrm{i}},{\mathrm{x}}_{\mathrm{j}})=\mathrm{\phi }({\mathrm{x}}_{\mathrm{i}})·\mathrm{\phi }({\mathrm{x}}_{\mathrm{j}})$ is the kernel function, and $\mathrm{\phi }(\mathrm{x})$ is the mapping function. Kernel function simplifies inner product operation. So, even vectors are mapped into infinite-dimensional spaces, separating hyperplane can be obtained, and decision-making computation is practicable. Finally, the decision function is described in equation (5)

$$\mathrm{f}(\mathrm{x})=\mathrm{sgn}(\sum _{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{\alpha }}_{\mathrm{i}}^{*}{\mathrm{y}}_{\mathrm{i}}\mathrm{K}({\mathrm{x}}_{\mathrm{i}},\mathrm{x})+{\mathrm{b}}^{*})$$

(5)

where ${\mathrm{\alpha }}_{\mathrm{i}}$ are the Lagrange multipliers which satisfy $0<{\mathrm{\alpha }}_{\mathrm{i}}^{*}<\mathrm{C}$ , ${\mathrm{x}}_{\mathrm{i}}$ are the support vectors whose ${\mathrm{\alpha }}_{\mathrm{i}}$ is not 0, n is the number of support vectors, and ${\mathrm{b}}^{*}$ is the bias value. Equation (5) shows that decision function depends on support vectors. That means optimal hyperplane is constructed by these support vectors. The goal of training is to get these support vectors.

Localization based on SVM

It is assumed that we randomly deployed a WSN with n nodes {S₁, S₂, S₃, …, S_N} in a two-dimensional (2D) geographic area [0, D]² (D > 0). The communication range of each node is same. In the WSN, k nodes are beacon nodes which know their own location; other N−k nodes are non-beacon nodes which need to estimate their location. We divide the 2D area into M × M square cells. X-dimension and Y-dimension are both divided into M parts. Each cell can be seen as one class. So, x-coordinate has M = 2^m classes cx_i, and the y-coordinate has M = 2^m classes cy_i, where m is the number of SVM required to classification for each dimension. Each node resides in a cell, so it is assumed that each node exists in class [cx_i, cy_i] in 2D area. In other words, respectively, each node exists in [(i−1)D/M, iD/M) × [(j−1)D/M, jD/M) unit. If x-coordinate of the node is the D, the node belongs to [(i−1)D/M, iD/M]. If y-coordinate of the node is the D, the node belongs to [(j−1)D/M, jD/M].

The connectivity information would be gathered by beacon nodes from the WSN and would be sent to the head node (sink node or base station) where the SVM training algorithm is running. Suppose that the node N_i’s true coordinates are (x_i, y_i). The vector H_i = h(N_i, N₁), h(N_i, N₂), h(N_i, N_k) > is taken as feature vector of SVM to classify node N_i, where h(N_i, N_j) denotes the shortest path hop-count between nodes N_i and N_j. All beacons’ feature vectors {H_i} (i = 1→k) are composed of training sample set. Using this training sample set, the SVM will be trained to build a model that would be broadcasted to all the nodes even they are beacons or not. Each non-beacon node is classified into one unit by this SVM model. And then, the center of each unit with (x_i, y_i) is used as the predicted position. If the result of each classification is correct, the maximum localization error of each non-beacon node is $\mathrm{D}/(\mathrm{M}\sqrt{2})$ . Radial basis function can be chosen to be the kernel function as shown in formula (6)

$$\mathrm{K}({\mathrm{H}}_{\mathrm{i}},{\mathrm{H}}_{\mathrm{j}})={\mathrm{e}}^{-\gamma \Vert {\mathrm{H}}_{\mathrm{i}}-{\mathrm{H}}_{\mathrm{j}}{\Vert }_2^2}$$

(6)

Obviously, localization algorithm based on SVM described above is a multi-class problem, but SVM can only solve two-class problem. So, how to solve multi-class problem is the key to localization algorithm. In this article, decision tree is used to solve the multi-class problem.

Take X-dimension for example, X-dimension is divided into M parts, so x-coordinate has M−1 classes cx_i {cx₁, cx₂, …, cx_M−1}. Each class cx_i contains nodes with the x-coordinate greater or equal to iD/M. According to the decision-tree strategy, M−1 binary SVM need to be trained, and localization of each node needs log₂M binary classifications. For the Y-dimension, the processing method is the same as the X-dimension. Figure 1 shows that X-dimension is divided into 16 parts.

Figure 1.

Decision tree used for X-dimension classification (M = 16).

Large-scale training samples reduction method (FCMTSR)

The SVM has good generalization ability and high classification precision. But, for a large-scale WSN, localization algorithm based on SVM faces to the problem of the large-scale learning samples. The large-scale training samples result in slow learning speed and large storage demand. Moreover, if training sample data mingle with outlier data, the training result will lead to classification accuracy decline. These problems will directly hamper the SVM’s application in localization algorithm. So, before training the SVM, we need to preprocess the learning sample data to reduce the scale and remove the outlier data. This article proposed a large-scale training samples reduction method based on fuzzy C-means (FCM) which is called FCMTSR for short.

Issues to be considered

According to the basic theory of SVM described in section “Localization based on SVM,” SVM is formulated as Quadratic Programming (QP) problems; the training time and space complexities are O(n³) and O(n²), respectively, in which n is the number of training samples. Hence, reducing the size of training data can improve the training speed and lower the space demand.

From the basic theory of SVM, it is well known that the optimal hyperplane which determines the classification results are constructed by the support vectors. This means the other non-support vector samples are useless to training, and they do not impact the position of the optimal hyperplane. So, removing the non-support vector samples not only affects the classification accuracy but also speeds up training process. It is obvious that only those samples near the two-class border are likely to become support vectors. We call these samples near the border as potential support vectors. The performance of training will be better using potential support vectors as training sample set. Under the premise of ensuring classification accuracy, the training speed will be certainly improved to a certain extent. Because this strategy removes only the samples which are useless to SVM learning and keeps the potential support vectors which have greater effect on the optimal hyperplane. When sample aliasing exists between the two types of training data, we will obtain a wrong optimal hyperplane. So, at this situation, we should try to prune away these aliasing sample data to guarantee the accuracy.

The idea of training samples reduction method

Suppose that training data sets are expressed as Figure 2. The • represents the training sample data which belong to class +1, the Δ represents the training sample data which belong to class −1, H is the optimal hyperplane, and H₁ and H₂ are the planes which are constructed by respective support vectors. From above analysis, it is known that the potential support vectors must be near the border of each sample set. How to judge the relationship between sample data and sample set is the key to the reduction method.

Figure 2.

Training sample set.

Figure 2 shows that the data near the border are closer to the other sample set. So, one simple method of judging border data is that if data “S” belongs to class +1, and there exists sample data belong to class −1 in the neighbor of “S,”“S” can be considered as near the border. According to this idea, this article proposes flowing determine rule of the border data based on point set theory.

In FCMTSR, each training sample data are regarded as a point and training sample sets are regarded as point sets. Based on the point set theory, we give some definitions as follows.

Assume that there is a limited point set A in a space ${\mathrm{R}}^{\mathrm{n}}$ , where n is the dimension. There are three mutually exclusive relationships between A and any point S, which is in the space ${\mathrm{R}}^{\mathrm{n}}$ . (1) All neighboring points of the S are not in set A, (2) all neighboring points of the S are in set A, and (3) some of neighboring points of the S are in set A.

According to above assumption, we give the following definitions.

Definition 1

For the point S, if there exists one point set B which meet the condition that B is one neighborhood of S, B =  $\mathrm{U}(\mathrm{S})$ , and $\mathrm{B}\subset \mathrm{A}$ , we defined that S is the inner point of A.

Definition 2

For the point S, if any neighborhood point of S is not in A, $\forall \mathrm{U}(\mathrm{S})\not\subset \mathrm{A}$ , we defined that S is the outer point of A.

Definition 3

If S is not either inner point or outer point of A, that means in any neighborhood of S, a part of points belong to A, and other points belong to complementary set of A, we defined that S is the edge point of A.

We regard the training samples ${\mathrm{X}}_1=({\mathrm{x}}_1,\dots ,{\mathrm{x}}_{\mathrm{n}1})$ which belong to class +1 as point set A₁ and training samples ${\mathrm{X}}_2=({\mathrm{x}}_1,\dots ,{\mathrm{x}}_{\mathrm{n}2})$ which belong to class −1 as point set A_2. According to above definitions, there are three kinds of relationships between each point S in set A₁ and set A₂. The point S may be the inner point, outer point, or the edge point for A₂.

Assume that any point S is in the set A_1. If S is the outer point for set A₂, that means S must belong to class +1 and S is not at the edge of the two classes. At this situation, S is probably not the non-support vector; if S is the inner point for set A₂, that means S should belong to class −1, so S should be the outlier data mixed in set A₁ rather than the support vector; if S is the edge point for set A₂, that means S is probably at the edge of the two classes. At this situation, S is most likely a support vector. Similarly, the type of each point in set A₂ can be analyzed according to above method. Thus, to gain the potential support vectors, we just need to find the edge point of the two classes. And then, these potential support vectors are used as training samples. Thus, the scale of training samples is reduced and outlier data are removed.

FCMTSR

For judging the type of each sample point, the neighborhood points of each point need to be gained by calculating the distance of every paired points in high-dimensional space. Distance can be calculated by

$$\begin{array}{c}{\mathrm{d}}_{\mathrm{ij}}^2={|\mathrm{\varphi }({\mathrm{x}}_{\mathrm{i}})-\mathrm{\varphi }({\mathrm{x}}_{\mathrm{j}})|}^2\hfill \\ =\mathrm{\varphi }({\mathrm{x}}_{\mathrm{i}})·\mathrm{\varphi }({\mathrm{x}}_{\mathrm{i}})-2\mathrm{\varphi }({\mathrm{x}}_{\mathrm{i}})·\mathrm{\varphi }({\mathrm{x}}_{\mathrm{j}})+\mathrm{\varphi }({\mathrm{x}}_{\mathrm{j}})·\mathrm{\varphi }({\mathrm{x}}_{\mathrm{j}})\hfill \\ =\mathrm{K}({\mathrm{x}}_{\mathrm{i}},{\mathrm{x}}_{\mathrm{i}})-2\mathrm{K}({\mathrm{x}}_{\mathrm{i}},{\mathrm{x}}_{\mathrm{j}})+\mathrm{K}({\mathrm{x}}_{\mathrm{j}},{\mathrm{x}}_{\mathrm{j}})\hfill \end{array}$$

(7)

where $\mathrm{\varphi }(\mathrm{x})$ is the map function and $\mathrm{K}({\mathrm{x}}_{\mathrm{i}},{\mathrm{x}}_{\mathrm{i}})$ is the kernel function. Although the kernel function solves the problem of dimension disaster, its compute cost is too high at situation of large-scale training samples. Another problem is there is not a good method to decide which points are neighbor points. The distances between points and its neighbors are changing with change of training sample set. When the scale of WSN is too large, this method of judging point type is not practical. To solve this problem, a sample point type decision method based on FCM algorithm is proposed.

In the FCMTSR, the training samples are divided into c subclasses according to spatial similarity through clustering technology. Taking Figure 2 for example, after clustering, each type of training sample set is divided into five subclasses. Subclass “+A,”“+B,”“+C,”“+D,” and “+E” belongs to class +1, and subclass “−A,”“−B,”“−C,”“−D,” and “−E” belongs to class −1; it is shown in Figure 3. Clustering center of each subclass is used to represent all points which belong to respective subclass. Each clustering center must belong to one subclass definitely.

Figure 3.

Training sample set after clustering.

Each point’s membership degrees of belonging to every subclass are calculated. The membership degree represents the spatial similarity and is used to analyze the type of each point. Take points “a” and “b” in Figure 3 for example. Point “a” belongs to subclass “+A” and “b” belongs to subclass “+E.” The spatial position of “a” is more close to class −1 than “b.” So, the sum of spatial similarity between “a” and each subclass of class −1 must be bigger than “b.”

Suppose that the sum of membership degrees between any point “i” and each subclass of class −1 is ${\mathrm{S}}_{\mathrm{i}}^{-}$ , and the sum of membership degrees between any point “i” and each subclass of class +1 is ${\mathrm{S}}_{\mathrm{i}}^{+}$ . In the situation shown in Figure 3, formula (8) must be workable. It means that the data point is more close to border, and the value of “ ${\mathrm{S}}_{\mathrm{i}}^{+}-{\mathrm{S}}_{\mathrm{i}}^{-}$ ” is bigger

$${\mathrm{S}}_{\mathrm{b}}^{+}-{\mathrm{S}}_{\mathrm{b}}^{-}>{\mathrm{S}}_{\mathrm{a}}^{+}-{\mathrm{S}}_{\mathrm{a}}^{-}$$

(8)

Figure 4 shows the situation of outlier point existing. In Figure 4, point “m” is an outlier which should belong to class −1, but it is mixed into sample set “+1” wrongly. This error will affect the training result and cause classification hyperplane to deviate. So, point “m” should be removed before the training. According to spatial similarity, formula (9) must be workable. That means that the difference of membership degree of outlier data must be negative

$${\mathrm{S}}_{\mathrm{m}}^{+}-{\mathrm{S}}_{\mathrm{m}}^{-}<0$$

(9)

Figure 4.

Outlier point existing in training sample set.

According to the above theoretical analysis, a new method of sample data set reduction (FCMTSR) based on spatial similarity analysis and clustering technology is proposed.

FCM is a clustering algorithm that allows one piece of data to belong to two or more clusters. It provides many advantages, including implementation simplicity, rapidly converging, and high efficiency.^22–24

In the FCMTSR, the sample set including N vectors ${\mathrm{x}}_{\mathrm{i}}(\mathrm{i}=1,2,\dots ,\mathrm{n})$ is divided into c subclasses. Then, clustering center ${\mathrm{c}}_{\mathrm{i}}(\mathrm{i}=1,2,\dots ,\mathrm{c})$ of each class and membership degree is constantly updated through iterative until the value of objective function reach to minimum. Finally, the fuzzy membership matrix is obtained. Fuzzy partition is applied in the algorithm. The membership stands for spatial similarity which is used to decide each data point’s degree of belonging to each class. That means that one data point has a membership relative to each class, whose value is [0, 1], and the sum of each sample point’s membership is equal to 1

$$\sum _{\mathrm{i}=1}^{\mathrm{c}}{\mathrm{u}}_{\mathrm{ij}}=1,\forall \mathrm{j}=1,\dots ,\mathrm{n}$$

(10)

where ${\mathrm{u}}_{\mathrm{ij}}$ is the membership degree of x_j in cluster i.

The objective function is

$$\mathrm{J}(\mathrm{U},{\mathrm{c}}_1,\dots ,{\mathrm{c}}_{\mathrm{c}})=\sum _{\mathrm{i}=1}^{\mathrm{c}}{\mathrm{J}}_{\mathrm{i}}=\sum _{\mathrm{i}=1}^{\mathrm{c}}\sum _{\mathrm{j}}^{\mathrm{n}}{\mathrm{u}}_{\mathrm{ij}}^{\mathrm{m}}{\mathrm{d}}_{\mathrm{ij}}^2$$

(11)

where ${\mathrm{d}}_{\mathrm{ij}}=\Vert {\mathrm{x}}_{\mathrm{j}}-{\mathrm{c}}_{\mathrm{i}}\Vert$ is the distance between the sample data j and the clustering center i and $\mathrm{m}\in [1,\infty )$ is the weighting exponent.

Based on above FCM method, we can obtain the membership value of every training sample point for SVM. Then, we can decide the relationship of any sample point s in sample set A₁ (belong to class +1) with sample set A₂ (belong to class −1) through the following rules:

1. If ${\displaystyle \sum _{\mathrm{i}=1}^{{\mathrm{c}}_1}{\mathrm{u}}_{\mathrm{is}}}-{\displaystyle \sum _{\mathrm{i}=1}^{{\mathrm{c}}_2}{\mathrm{u}}_{\mathrm{is}}}\ge \lambda$ , $0<\lambda \le 1$ , s is the outer point for A_2. Point s is regarded as non-support vector.

2. If $\sum _{\mathrm{i}=1}^{{\mathrm{c}}_2}{\mathrm{u}}_{\mathrm{is}}-\sum _{\mathrm{i}=1}^{{\mathrm{c}}_1}{\mathrm{u}}_{\mathrm{is}}\ge \lambda$ , $0<\lambda \le 1$ , s is the inner point for A_2. Point s is regarded as the outlier point mixed in A₁.

3. If $\left|{\displaystyle \sum _{\mathrm{i}=1}^{{\mathrm{c}}_2}{\mathrm{u}}_{\mathrm{is}}}-{\displaystyle \sum _{\mathrm{i}=1}^{{\mathrm{c}}_1}{\mathrm{u}}_{\mathrm{is}}}\right|\mathrm{<}\lambda$ , $0<\mathrm{\lambda }\le 1$ , s is the edge point for A. Point s is regarded as potential support vector.

where ${\mathrm{c}}_1$ is the number of cluster which belongs to class +1, ${\mathrm{c}}_2$ is the number of cluster which belongs to class −1, and ${\mathrm{u}}_{\mathrm{is}}$ is the membership value of sample s in cluster i.

Realization of FCMTSR

According to the basic idea of proposed algorithm above, SVM-FCMTSR realization steps are as follows:

• Step 1. Suppose that the training sample set A₁ belongs to class +1, whose sample number is n₁. And training sample set A₂ belongs to class −1, whose sample number is n₂. We make the initial clustering center number m of each class as m = 2 (n₁ + n₂)/1000.

• Step 2. According to formula (12), the membership of each sample point in sample set ${\mathrm{E}}_1+{\mathrm{E}}_2({\mathrm{x}}_1,{\mathrm{x}}_2,\dots ,{\mathrm{x}}_{\mathrm{n}})$ is calculated as

$${\mathrm{u}}_{\mathrm{ij}}=\{\begin{array}{c}\begin{array}{cc}\frac{1}{\sum _{\mathrm{k}=1}^{\mathrm{c}}{\left(\frac{{\mathrm{d}}_{\mathrm{ij}}}{{\mathrm{d}}_{\mathrm{ik}}}\right)}^{2/(\mathrm{m}-1)}}\hfill & {\mathrm{d}}_{\mathrm{ij}}\ne 0\hfill \end{array}\hfill \\ \multicolumn{1}{c}{\begin{array}{cc}1\hfill & \begin{array}{c}{\mathrm{d}}_{\mathrm{ij}}=0,\mathrm{j}=\mathrm{k}\hfill \end{array}\hfill \end{array}}\\ \multicolumn{1}{c}{\begin{array}{cc}0\hfill & \begin{array}{c}{\mathrm{d}}_{\mathrm{ij}}=0,\mathrm{j}\ne k\hfill \end{array}\hfill \end{array}}\end{array}$$

(12)

where n is the total number of sample, c = 2 m, and ${\mathrm{d}}_{\mathrm{ij}}$ is the Euclidean distance between the sample point ${\mathrm{x}}_{\mathrm{i}}$ and sample point ${\mathrm{x}}_{\mathrm{j}}$ .

• Step 3. The objective function J is calculated. If its value reach to a local minimum or a saddle point, the final clustering center C, fuzzy membership matrix U, and the distance matrix D are obtained; the iteration stops and goes to step 5. Otherwise, go to step 4.

• Step 4. According to ${\mathrm{c}}_{\mathrm{i}}=\sum _{\mathrm{j}=1}^{\mathrm{n}}{\mathrm{u}}_{\mathrm{ij}}^{\mathrm{m}}{\mathrm{x}}_{\mathrm{j}}/\sum _{\mathrm{j}=1}^{\mathrm{n}}{\mathrm{u}}_{\mathrm{ij}}^{\mathrm{m}}$ , recount the clustering center ${\mathrm{c}}_{\mathrm{i}},\mathrm{i}=1,2,\dots ,\mathrm{c}$ , and go to step 2.

• Step 5. According to the k-neighbor decision rules (k = (h₁ + h₂)/20), decide that which class (+1 or −1) each clustering center belongs to. Remove the uncertain fuzzy clustering center which resets the row elements corresponding to these uncertain clustering centers in the membership matrix;

• Step 6. The fuzzy membership matrix is revised to ensure that the clustering center number of class +1 and −1 balances. The sum of membership of each point is still kept to 1. The principle of revision is as follows: separately count the class number signed for + 1 and −1 as $\mathrm{su}{\mathrm{m}}_1$ and $\mathrm{su}{\mathrm{m}}_2$ , if $\mathrm{su}{\mathrm{m}}_1\ne \mathrm{su}{\mathrm{m}}_2$ , according to formula (13), add membership matrix U for $|\mathrm{su}{\mathrm{m}}_1-\mathrm{su}{\mathrm{m}}_2|$ lines

$${\mathrm{u}}_{\mathrm{ij}}=min\{{\mathrm{u}}_{\mathrm{kj}}|{\mathrm{y}}_{\mathrm{ck}}=\mathrm{sgn}(\mathrm{su}{\mathrm{m}}_1-\mathrm{su}{\mathrm{m}}_2)\}\mathrm{i}=\mathrm{c}+1,\dots ,\mathrm{c}+|\mathrm{su}{\mathrm{m}}_1-\mathrm{su}{\mathrm{m}}_2|\mathrm{k}=1,\dots ,\mathrm{c}$$

(13)

where ${\mathrm{y}}_{\mathrm{ck}}$ is the class sign of the clustering center K by FCM. Finally, standardize the membership matrix as follows

$${\mathrm{u}}_{\mathrm{ij}}=\frac{{\mathrm{u}}_{\mathrm{ij}}}{\sum _{\mathrm{k}=1}^{\mathrm{c}+|\mathrm{su}{\mathrm{m}}_1-\mathrm{su}{\mathrm{m}}_2|}{\mathrm{u}}_{\mathrm{kj}}}$$

(14)

• Step 7. According to the relationship decision rules proposed in section “FCMTSR,” the non-support vector and the non-boundary mixed outlier are removed, and the potential support vectors are obtained.

Simulation of localization algorithm based on SVM-FCMTSR

We conducted the simulations on a network of 1000 sensor nodes randomly distributed in the 100 m × 100 m 2D area. In the network, the beacon nodes are randomly selected. Three different beacon populations were considered: 20% of the WSN size (n = 200 beacon nodes), 25% (n = 250 beacon nodes), and 30% (n = 300 beacon nodes). The communication range of each node is 10 m. The x-dimension and y-dimension are divided into 128 parts (M = 128). All simulation experiments are done on a PC machine with CPU-Intel Core2 Duo E7500, 2GB memory. The simulation platform is MATLAB 7.0, and LIBSVM software is used for SVM classification. The kernel of SVM is Radial Basis Function (RBF). FCMTSR proposed in section “Large-scale training samples reduction method (FCMTSR)” is used to preprocess the training sample set before training SVM. The parameter $\mathrm{\lambda }$ value is taken as 0.6 that proposed sample point relationship decision rules in section “FCMTSR.” The processes of implementation of all experiments are as follows:

• Step 1. The distribution area is a squared rectangle, whose vertex coordinates are (0, 0), (100, 0), (0, 100), and (100, 100). Coordinates (x_i, y_i) of 1000 nodes are randomly generated. Each coordinate is a random number between 0 and 100 which is generated by function rand( ) which is provided by MATLAB.

• Step 2. Randomly select a part of 1000 nodes as beacon nodes. In the following experiments, the number of beacon nodes is 200, 250, and 300.

• Step 3. Calculate the shortest path hop-count between each node and each beacon node according to communication range.

• Step 4. The x-dimension and y-dimension both are divided into 128 parts. So, for each dimension coordinate, 127 SVMs need be trained. The hop-count between each beacon node and other beacon nodes is used as training sample.

• Step 5. Preprocess the training sample set by FCMTSR. And then each SVM is constructed by training.

• Step 6. Estimate coordinates of each non-beacon node.

Effect of beacon population

We randomly selected three simulation results as shown in Figures 5–7; when the number of nodes is 1000, the beacon population is 20%, 25%, and 30% in the square-shaped network. The communication range is 10 m. The * represents the positions of beacon nodes, the Δ represents the positions of real non-beacon nodes, and the ○ represents the estimated positions of non-beacon nodes.

Figure 5.

Estimation result of 20% beacon nodes in the square-shaped network.

Figure 6.

Estimation result of 25% beacon nodes in the square-shaped network

Figure 7.

Estimation result of 30% beacon nodes in the square-shaped network.

The localization error is 2.6 m at the beacon nodes population 20%, 1.9 m at the population 25%, and 1.2 m at the population 30% in these three simulations. The localization error E is described as follows

$$\mathrm{E}=\frac{\sum _{\mathrm{i}=1}^{\mathrm{k}}\sqrt{{({\hat{\mathrm{x}}}_{\mathrm{i}}-{\mathrm{x}}_{\mathrm{i}})}^2+{({\hat{\mathrm{y}}}_{\mathrm{i}}-{\mathrm{y}}_{\mathrm{i}})}^2}}{\mathrm{k}}$$

(15)

where $({\hat{\mathrm{x}}}_{\mathrm{i}},{\hat{\mathrm{y}}}_{\mathrm{i}})$ denotes the estimated coordinates of i-th node and k stands for the number of non-beacon nodes.

The above results show that the localization error decreased with increasing beacon nodes. In order to make the result believable, every simulation was run for 10 times and the results were averaged. The results of the localization error are shown in Table 1.

Table 1.

Localization error of different beacon population in the square-shaped network.

Beacon population (%)	Minimum error (m)	Maximum error (m)	Average error (m)
20	2.6	3.4	2.8
25	1.5	2.3	1.7
30	0.7	1.3	1.0

Table 1 shows that increasing the number of beacon nodes results in decreasing the localization error. The accuracy of learning methods depends on the amount of training data. Since beacon nodes make training data, with more number of beacon nodes, there is more training data available. So, the localization algorithm can be trained with more accuracy. Then, in the localization phase, it has more accurate results.

FCMTSR-SVM versus SVM with different beacon population

We compared the localization algorithm based on SVM with using FCMTSR proposed in section “Large-scale training samples reduction method (FCMTSR)” and without using FCMTSR at different beacon population. The results are shown in Figure 8. The location accuracy by FCMTSR-SVM is higher than SVM. Since the outlier data immixed can be removed by FCMTSR. It results that generalization of SVM is improved. So, the position of nodes would be computed more accurately. From Figure 8, we can see that the average localization error by the FCMTSR-SVM is lower about 2% than by the SVM.

Figure 8.

Average localization error comparison of FCMTSR-SVM versus SVM.

Figure 9 shows the simulation results of FCMTSR-SVM versus SVM training time consumption. When the beacon population is 20%, 25%, and 30%, the FCMTSR-SVM training time is about 21.14, 39.44, and 47.33 s, the SVM training time is about 38.91, 71.68, and 86.05 s. The simulation results show that localization accuracy by FCMTSR-SVM is improved by 2%, and the total training time is reduced about 55%.

Figure 9.

Average training time comparison of FCMTSR-SVM versus SVM.

Border problem

The purpose of this simulation is to study the performance of the FCMTSR-SVM localization algorithm for the border problem. The border problem exists in many localization algorithms. It means that the sensor nodes near the edge of deployment area will obtain much lower localization accuracy than those near the center of deployment area. We investigate this problem for two sizes of beacon population (20% and 30%) and select 100 nodes closer to the edge. Figures 10 and 11 show the results of simulations. The localization error of 100 border nodes is between the minimum error and the maximum error. The results illustrate that in FCMTSR-SVM localization algorithm, the localization accuracy of sensor nodes near the edge is very close to those near the center. So, the proposed algorithm is pure of border problem. This property can be explained. The FCMTSR-SVM localization only depends on the beacon nodes, which is independent of other nodes. And the proposed FCMTSR does not affect the support vectors which are provided by beacon nodes. Therefore, the position of the sensor node does not have substantial effects on localization accuracy.

Figure 10.

Estimation result of 100 border nodes with beacon population 20%.

Figure 11.

Estimation result of 100 border nodes with beacon population 30%.

Coverage hole problem

The purpose of the simulations is to evaluate the performance of FCMTSR-SVM in the network with the coverage holes. The simulations are composed of two groups. One is in the C-shape network area and the other is the network with two holes. In the first group of simulations, 1000 sensor nodes are deployed randomly in the 100 m × 100 m C-shape network area. The communication range is 10 m. The node distribution is shown in Figure 12.

Figure 12.

Node distribution in C-shape network.

Table 2 shows the average localization error of FCMTSR-SVM in this C-shape network with beacon population 20%, 25%, and 30%. Comparing Table 1 with Table 2, it is shown that both average localization errors are consistent.

Table 2.

Localization error of different beacon population in the C-shape network.

Beacon population (%)	Average localization error (m)
20	3.0
25	1.8
30	1.0

FCMTSR-SVM was compared with SVM in this network with beacon population 20%, 25%, and 30%. The simulation results of average localization error and training time are shown in Figures 13 and 14, respectively. As shown in these two figures, FCMTSR-SVM has higher accuracy and less training time than SVM in the C-shape network area.

Figure 13.

Average localization error comparison of FCMTSR-SVM versus SVM in C-shape network.

Figure 14.

Average training time comparison of FCMTSR-SVM versus SVM in C-shape network.

In the second group of simulations, 1000 sensor nodes are deployed randomly in the 100 m × 100 m square-shaped network area with two holes. The communication range is 10 m. The radius of the left hole is 10 m, and the radius of the right hole is 15 m. The node distribution is shown in Figure 15.

Figure 15.

Node distribution in the network with two holes.

FCMTSR-SVM was compared with SVM in this network with beacon population 20%, 25%, and 30%. Figures 16 and 17 show the results of average localization error and training time, respectively. Similarly, the results suggest that in the network with two holes, FCMTSR-SVM has higher accuracy and less training time than SVM.

Figure 16.

Average localization error comparison of FCMTSR-SVM versus SVM in the network with two holes.

Figure 17.

Average training time comparison of FCMTSR-SVM versus SVM in the network with two holes.

From the above results of the simulations, we can see that the localization accuracy of FCMTSR-SVM may be a little lower in the networks with holes. But it appears that the existence of coverage holes does not have big effects on FCMTSR-SVM. Moreover, FCMTSR-SVM in the networks with holes has better performance than SVM. For example, when beacon population is 30% in the network with two holes, the average localization error of SVM is 1.5 m and the average training time of SVM is 86.55 s, the average localization error of FCMTSR-SVM is 1.2 m and the average training time of FCMTSR-SVM is 49.22 s, respectively. Therefore, FCMTSR-SVM has good performance not only for the border problem but also for the coverage hole problem. The reason can be explained that localization based on SVM is relative to hop-count, not relative to geographic distances, so the network holes do not have significant effect on localization accuracy. And it proves that FCMTSR-SVM can reduce scale of training sample and keep support vectors effectively in the network with holes.

Discussion

Because the power and memory of sensor node is limited, an effective localization algorithm needs to consider these factors of storage, calculation, and communication capacities. In the localization algorithm based on FCMTSR-SVM, each node needs 2 × (M − 1) × (4k + 4) + k memory units, where k is the number of beacons, M is the number of parts that network is divided into. Each k hop-count value can be represented by 1 byte. Each SVM needs the ${\mathrm{b}}^{*}$ value and ${\mathrm{\alpha }}_{\mathrm{i}}^{*}{\mathrm{y}}_{\mathrm{i}}$ value for each beacon. Each ${\mathrm{b}}^{*}$ can be represented by 4 bytes, and each ${\mathrm{\alpha }}_{\mathrm{i}}^{*}{\mathrm{y}}_{\mathrm{i}}$ value can be represented by 4 bytes. For example, if the network is divided into M = 128 parts and the beacons size k is 50, each node needs a memory of 51,866 bytes at most. So, the proposed algorithm satisfies the demand of little memory.

In the point of computation cost, each node needs to compute decision function 2log₂M times. Hence, for k = 50, M = 128, it results in not more than 14 × 50 = 600 multiplications. At the base station, when the SVM is trained without FCMTSR (sample size is n), the iterative processes need to use Hessian matrix many times, the kernel function needs O(n²) order calculation. But FCMTSR only needs to calculate O(iter × c × n) order Euclidean distance for the FCM clustering process, where c is the clustering number, iter is the maximum iteration times, c << n, and iter << 100. After reduction, it needs ${\mathrm{O}(\mathrm{n}}_1^2)$ order kernel function calculation, where n₁ is the potential support vector number. Normally, support vectors are only a small part of the boundary data of the training sample set, so we can consider n₁ < n/2. The consumption of time of the above calculation is O(iter × c × n) +  ${\mathrm{O}(\mathrm{n}}_1^2)$ , which is much less than O(n²). So, FCMTSR can reduce calculation burden of training process at the base station.

In terms of communication cost, to calculate the hop-count of each node, beacon nodes should broadcast less than k byte message except the base station (or sink node). It means each node transmit less than k unit of memory to its neighbor nodes in the initial phase. To train the SVM, each beacon node needs to transmit k byte hop-count to the base station. After building the SVM model, the base station broadcasts 2(M−1) groups of SVM parameters

However, our proposed localization algorithm has its own limitation. Like other localization algorithm based on SVM, the quality of training process directly affects the localization accuracy. Training data are made by beacon nodes. So, the number of beacon nodes has effect on accuracy. The accuracy is decreased with beacon nodes being reduced. FCMTSR-SVM localization algorithm is aimed at the large-scale WSN. For the small-scale WSN, the FCMTSR is not very effective.

Conclusion

In this article, we propose a distributed localization algorithm for large-scale WSNs based on FCMTSR-SVM. The proposed localization algorithm transforms the location estimation problem into multi-class problem, and binary SVM classification is used to solve the multi-class. So, it is suitable for WSNs that do not require pairwise distance measurements and special assisting devices. The SVM classification accuracy is the key to the localization accuracy. The training process is the important factor that influences the performance of SVM. The large-scale training samples will lead to high burden of the training calculation, over learning, and low classification accuracy. So, this article proposes a new reduction method based on FCM (FCMTSR). Using fuzzy clustering method, the potential support vectors are obtained and the non-boundary outlier data immixed are removed. Thus, the training time can be reduced and the localization accuracy can be improved. Then, we conducted the simulations to examine the performance of localization. The simulation results show that localization algorithm based on FCMTSR-SVM has the lower training time cost and more accuracy than localization algorithm based on SVM. The border problem and coverage hole problem also cannot affect its performance, which many other localization algorithms have not overcome. The communication and processing overheads are kept small in this algorithm, so it is suitable for practical application in large-scale WSNs.