Semisupervised Location Awareness in Wireless Sensor Networks Using Laplacian Support Vector Regression

Abstract

Supervised machine learning has been widely used in context-aware wireless sensor networks (WSNs) to discover context descriptions from sensor data. However, collecting a lot of labeled training data in order to guarantee good performance requires much cost and time. For this reason, the semisupervised learning has been recently developed due to its superior performance despite using only a small amount of the labeled data. In this paper, we extend the standard support vector regression (SVR) to the semisupervised SVR by employing manifold regularization, which we call Laplacian SVR (LapSVR). The LapSVR is compared with the standard SVR and the semisupervised least square algorithm that is another recently developed semisupervised regression algorithm. The algorithms are evaluated for location awareness of multiple mobile robots in a WSN. The experimental results show that the proposed algorithm yields more accurate location estimates than the other algorithms.

1. Introduction

Location awareness is one of the most important issues for context-aware wireless sensor networks (WSNs) because many applications need to know where the data has been obtained. For example, in applications such as target tracking [1–5], network routing [6, 7], human-centric service [8–10], and monitoring system [11, 12], the measurement data is useless without location information of sensing device.

Machine learning methods have been adopted to learn location context from law sensor data. The standard SVR learning [13, 14], manifold learning [15], and neural network learning [16, 17] can be employed to obtain precise estimate of the location. However, all these methods require a large amount of the labeled training data for high accuracy. Also, a significant effort such as cost, time, and human skill is needed in order to generate a large set of the labeled data. To make location-aware algorithm viable with a negligible effort, this paper adopts a semisupervised learning which uses a small number of the labeled data.

Based on the semisupervised learning framework suggested in [18], various algorithms such as [19–21] have been developed by defining different loss functions and regularization functions. In this work, we develop Laplacian support vector regression (LapSVR) which extends the standard SVR to the semisupervised learning framework. This approach uses the standard SVR to define the loss function and kernel-based regularization. However, for utilization of unlabeled data, the manifold regularization based on the concept of the graph Laplacian [22] is performed.

We evaluate the LapSVR to estimate locations of multiple mobile robots in the WSN. The deployed anchor nodes broadcast RF signal whose signal strength (RSSI) is measured by the mobile robots. The mobile robots independently localize themselves by using the trained regression model and current RSSI measurements. The LapSVR is compared with the standard SVR and the semisupervised Laplacian least square algorithm [23]. The location awareness performance is compared according to the number of labeled data, unlabeled data, and anchor nodes. From the experimental results, we confirm that the LapSVR estimates the location most accurately and is least sensitive to the variation of the number of the anchor nodes.

This paper is organized as follows. In Section 2, we provide details on Laplacian support vector regression algorithm. Section 3 describes the estimation process of mobile robots using the proposed algorithm. Section 4 reports empirical results with the description of the experimental setting. Finally, concluding remarks are given in Section 5.

2. Laplacian Support Vector Regression

This section describes a semisupervised regression approach named Laplacian support vector regression (LapSVR). We use the standard SVR algorithm to define the loss function and kernel-based regularization. Also, the graph Laplacian is employed for manifold regularization. We describe these ingredients of the formulation in the following.

2.1. Semisupervised Learning Framework

We define a set of l labeled samples $\{x_i,y_i{\}}_{i=\mathrm{1}}^l$ and a set of u unlabeled samples $\{x_i{\}}_{i=l+\mathrm{1}}^{l+u}$ , where $x_i\in X\subseteq {ℝ}^n$ and $y_i\in ℝ$ . Semisupervised learning aims to establish a mapping $f:X\to ℝ$ , by the following regularized minimization functional:

$$\begin{array}{cc}& f^{*}=\arg \underset{f\in {\mathscr{H}}_k}{\min }\frac{\mathrm{1}}{l}{\displaystyle \sum }_{i=\mathrm{1}}^l‍V\left(x_i,y_i,f\right)+{\gamma }_A{\parallel f\parallel }_A^{\mathrm{2}}+{\gamma }_I{\parallel f\parallel }_I^{\mathrm{2}},\end{array}$$

(1)

where V is a loss function, ${\parallel f\parallel }_A^2$ is the norm of the function in the reproducing kernel Hilbert space (RKHS), and ${\parallel f\parallel }_I^2$ is the norm of the function in the low-dimensional manifold. ${\gamma }_A$ and ${\gamma }_I$ are the regularization weight parameters.

2.2. Decision Function

By the representer theorem [25], the solution of (1) can be defined as an expansion of kernel function over the labeled and the unlabeled data, given by

$$\begin{array}{cc}& f\left(x\right)={\displaystyle \sum }_{i=\mathrm{1}}^{l+u}‍{\alpha }_{i}K\left(x_i,x\right)+b\end{array}$$

(2)

with the kernel function $K(x_i,x_j)=〈\varphi (x_i),\varphi (x_j)〉$ , where $\varphi \hspace{0.17em}(·)$ is a nonlinear mapping to the RKHS.

Also, the regularization term ${\parallel f\parallel }_A^{\mathrm{2}}$ which is associated with the RKHS is defined as

$$\begin{array}{cc}& {\parallel f\parallel }_A^2={\left(\Phi \mathbf{\alpha }\right)}^T\left(\Phi \mathbf{\alpha }\right)={\mathbf{\alpha }}^{T}K\mathbf{\alpha },\end{array}$$

(3)

where $\Phi =[\varphi \hspace{0.17em}(x_{\mathrm{1}}),\dots ,\varphi \hspace{0.17em}(x_{l+u}){]}^{}$ , $\mathbf{\alpha }=[{\alpha }_{\mathrm{1}},\dots ,{\alpha }_{l+u}{]}^T$ , and K is the $(l+u)\times (l+u)$ kernel matrix whose element is $K(x_i,x_j)$ .

2.3. Manifold Regularization

According to the manifold regularization (or manifold assumption), the data points are samples from a low-dimensional manifold which is embedded in a high-dimensional space. This is represented by the graph Laplacian and the kernel function:

$$\begin{array}{l}{\parallel f\parallel }_I^2=\frac{\mathrm{1}}{{\left(l+u\right)}^{\mathrm{2}}}{\displaystyle \sum }_{i=\mathrm{1}}^{l+u}\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍W_{ij}{\left(f\left(x_i\right)-f\left(x_j\right)\right)}^{\mathrm{2}}\hfill \\ =\frac{\mathrm{1}}{{\left(l+u\right)}^{\mathrm{2}}}{\mathbf{f}}^{T}L\mathbf{f},\hfill \end{array}$$

(4)

where L is the graph Laplacian given by $L=D-W$ , $\mathbf{f}=[f(x_{\mathrm{1}}),\dots ,f(x_{l+u}){]}^T$ , W is the adjacency matrix of the data graph, and D is the diagonal matrix given by $D_{ii}={\sum }_{j=\mathrm{1}}^{l+u}‍W_{ij}$ . In this paper, the edge weights $W_{ij}$ are defined as Gaussian function of Euclidean distance, given by

$$\begin{array}{cc}& W_{ij}=\exp \left(\frac{-{\parallel x_i-x_j\parallel }^{\mathrm{2}}}{{\sigma }_w^{\mathrm{2}}}\right),\end{array}$$

(5)

where ${\sigma }_w^{\mathrm{2}}$ is the kernel width parameter.

Minimizing ${\parallel f\parallel }_I^2$ is equivalent to penalizing the rapid changes of the regression function evaluated between two samples.

2.4. Loss Function for Regression

We employ the ε-insensitive loss function:

$$\begin{array}{cc}& V(x_i,y_i,f)=\{\begin{array}{cc}0\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}|f\left(x_i\right)-y_i|<\epsilon \hfill \\ \left|f\left(x_i\right)-y_i\right|-\epsilon \hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(6)

Also, slack variables ${\xi }_i$ , ${\xi }_i^{*}$ are used with the ε-insensitive loss function in order to cope with infeasible constraints of the optimization problem that uses only the ε constraint, described in [24]. Figure 1 depicts an example of one-dimensional linear regression function with ε-tube. The samples outside the ε-tube are called support vectors. Slack variables ξ, ${\xi }^{*}$ , which establish trade-off between model complexity and the support vectors, are determined by solving the optimization problem in the following section.

Figure 1

A behavior of the ε-intensive loss function with slack variable ξ [24].

2.5. Complete Formulation

In this subsection, the complete formulation of the LapSVR is given based on the ingredients described in Sections 2.1–2.4. Substituting (2)–(6) into (1) with the slack variables ${\xi }_i$ , ${\xi }_i^{*}$ , the primal problem is defined as

$$\begin{array}{l}\underset{\alpha \in {ℝ}^{l+u},\xi \in {ℝ}^l,{\xi }^{*}\in {ℝ}^l}{\min }\hspace{1em}\frac{\mathrm{1}}{l}{\displaystyle \sum }_{i=\mathrm{1}}^l‍\left({\xi }_i+{\xi }_i^{*}\right)+{\gamma }_A{\mathbf{\alpha }}^{T}K\mathbf{\alpha }\hfill \\ \phantom{\underset{\alpha \in {ℝ}^{l+u},\xi \in {ℝ}^l,{\xi }^{*}\in {ℝ}^l}{\min }}\hspace{1em}\hspace{1em}+\frac{\mathrm{1}}{{\left(l+u\right)}^{\mathrm{2}}}{\gamma }_I{\mathbf{\alpha }}^{T}KLK\mathbf{\alpha }\hfill \\ \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to:}\hspace{1em}\hspace{1em}{y}_i-{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)-b\le \epsilon +{\xi }_i,\hfill \\ \phantom{\underset{\alpha \in {ℝ}^{l+u},\xi \in {ℝ}^l,{\xi }^{*}\in {ℝ}^l}{\min }}\hspace{1em}{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)+b-y_i\le \epsilon +{\xi }_i^{*},\hfill \\ \phantom{\underset{\alpha \in {ℝ}^{l+u},\xi \in {ℝ}^l,{\xi }^{*}\in {ℝ}^l}{\min }}\hspace{1em}{\xi }_i,{\xi }_i^{*}\ge \mathrm{0},\hspace{1em}i=\mathrm{1},\dots ,l.\hfill \end{array}$$

(7)

After the introduction of four sets of l multipliers β, ${\beta }^{*}$ , η, and ${\eta }^{*}$ , the Lagrangian H can be obtained in the following:

$$\begin{array}{l}H\left(\alpha ,b,\xi ,{\xi }^{*},\beta ,{\beta }^{*},\eta ,{\eta }^{*}\right)\hfill \\ \hspace{1em}\hspace{1em}=\frac{\mathrm{1}}{\mathrm{2}}{\alpha }^T\left(\mathrm{2}{\gamma }_{A}K+\frac{\mathrm{2}}{{\left(l+u\right)}^{\mathrm{2}}}{\gamma }_{I}KLK\right)\alpha +\frac{\mathrm{1}}{l}{\displaystyle \sum }_{i=\mathrm{1}}^l‍\left({\xi }_i+{\xi }_i^{*}\right)\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}-{\displaystyle \sum }_{i=\mathrm{1}}^l‍{\beta }_i\left(\epsilon +{\xi }_i-y_i+{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)+b\right)\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}-{\displaystyle \sum }_{i=\mathrm{1}}^l‍{\beta }_i^{*}\left(\epsilon +{\xi }_i^{*}+y_i-{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)-b\right)\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}-\frac{\mathrm{1}}{l}{\displaystyle \sum }_{i=\mathrm{1}}^l‍\left({\eta }_i{\xi }_i+{\eta }_i^{*}{\xi }_i^{*}\right).\hfill \end{array}$$

(8)

In order to convert the primal problem to the dual representation, we take derivatives

$$\begin{array}{cc}& \frac{\partial H}{\partial b}={\displaystyle \sum }_{i=\mathrm{1}}^l‍\left({\beta }_i-{\beta }_i^{*}\right)=\mathrm{0},\\ \frac{\partial H}{\partial {\xi }_i^{\left(*\right)}}=\frac{\mathrm{1}}{l}-{\beta }_i^{\left(*\right)}-\frac{\mathrm{1}}{l}{\eta }_i^{\left(*\right)}=\mathrm{0}.\end{array}$$

(9)

Using the above equations, we can rewrite the Lagrangian as a function of α, β, and ${\beta }^{*}$ only, given by

$$\begin{array}{lll}H(\alpha ,\beta ,{\beta }^{*})\hfill & =\hfill & \frac{1}{2}{\alpha }^T\left(2{\gamma }_{A}K+\frac{2}{{(l+u)}^2}{\gamma }_{I}KLK\right)\alpha \hfill \\ \hfill & \hfill & -\sum _{i=1}^l\left(({\beta }_i-{\beta }_i^{*})\sum _{j=1}^{l+u}{\alpha }_{j}k(x_i,x_j)\right)\hfill \\ \hfill & \hfill & -\epsilon \sum _{i=1}^l({\beta }_i+{\beta }_i^{*})+\sum _{i=1}^l{y}_i({\beta }_i-{\beta }_i^{*})\hfill \\ \hfill & =\hfill & \frac{1}{2}{\alpha }^T\left(2{\gamma }_{A}K+\frac{2}{{(l+u)}^2}{\gamma }_{I}KLK\right)\alpha -{\alpha }^{T}K{J}_L^T𝔹\hfill \\ \hfill & \hfill & -\epsilon \sum _{i=1}^l({\beta }_i+{\beta }_i^{*})+\sum _{i=1}^l{y}_i({\beta }_i-{\beta }_i^{*}),\hfill \end{array}$$

(10)

where $𝔹=[{\beta }_{\mathrm{1}}-{\beta }_{\mathrm{1}}^{*},\dots ,{\beta }_l-{\beta }_l^{*}{]}^T$ and $J_L=\left[\begin{array}{cc}{I}_{l\times l}& {\mathbf{0}}_{l\times u}\end{array}\right]$ where $I_{l\times l}$ is the $l\times l$ identity matrix and ${\mathbf{0}}_{l\times u}$ is the $l\times u$ zero matrix.

Taking derivatives with respect to α, we obtain

$$\begin{array}{cc}& \frac{\partial H}{\partial \alpha }=\left(\mathrm{2}{\gamma }_{A}K+\frac{\mathrm{2}}{{\left(l+u\right)}^{\mathrm{2}}}{\gamma }_{I}KLK\right)\alpha -K{J}_L^T𝔹=\mathrm{0}.\end{array}$$

(11)

From (11), a direct relationship between α and 𝔹 is obtained:

$$\begin{array}{cc}& \alpha ={\left(\mathrm{2}{\gamma }_{A}I+\mathrm{2}\frac{\mathrm{1}}{{\left(l+u\right)}^{\mathrm{2}}}{\gamma }_{I}LK\right)}^{-\mathrm{1}}{J}_L^T𝔹,\end{array}$$

(12)

where I is the $(l+u)\times (l+u)$ identity matrix. Substituting (12) back into Lagrangian (10), we arrive at the convex optimization problem:

$$\begin{array}{l}\underset{\beta \in {ℝ}^l,{\beta }^{*}\in {ℝ}^l}{\max }\hspace{1em}\hspace{1em}-\frac{\mathrm{1}}{\mathrm{2}}{𝔹}^T{J}_{L}K{\left(\mathrm{2}{\gamma }_{A}I+\frac{\mathrm{2}}{(l+u{)}^{\mathrm{2}}}{\gamma }_{I}LK\right)}^{-\mathrm{1}}\hfill \\ \phantom{\underset{\beta \in {ℝ}^l,{\beta }^{*}\in {ℝ}^l}{\max }\hspace{0.33em}}\hspace{1em}\hspace{1em}{J}_L^T𝔹-\epsilon {\displaystyle \sum }_{i=\mathrm{1}}^l‍({\beta }_i+{\beta }_i^{*})+{\displaystyle \sum }_{i=\mathrm{1}}^l‍y_i({\beta }_i-{\beta }_i^{*})\hfill \\ \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to:}\hspace{1em}{\displaystyle \sum }_{i=\mathrm{1}}^l‍({\beta }_i-{\beta }_i^{*})=\mathrm{0}\hfill \\ \phantom{\text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}:}\hspace{1em}\mathrm{0}\le {\beta }_i,\hspace{1em}{\beta }_i^{*}\le \frac{\mathrm{1}}{l},\hspace{1em}i=\mathrm{1},\dots ,l.\hfill \end{array}$$

(13)

The optimal solution ${𝔹}^{*}$ of the above quadratic problem is linked to the optimal ${\alpha }^{*}$ in (12). Then, the optimal regression function $f^{*}(x)$ can be obtained by substituting ${\alpha }^{*}=[{\alpha }_{\mathrm{1}}^{*},\dots ,{\alpha }_{l+u}^{*}{]}^T$ into (2).

2.6. Computation of b

Now, the remaining work to establish regression function (2) is computation of the bias term b. As described in [24], b is calculated by using Karush-Kuhn-Tucker (KKT) conditions which state that the product between dual variables and constraints has to be zero at the point of the solution. From (8), we obtain

$$\begin{array}{cc}& {\beta }_i\left(\epsilon +{\xi }_i-y_i+{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)+b\right)=\mathrm{0},\\ {\beta }_i^{*}\left(\epsilon +{\xi }_i^{*}+y_i-{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)-b\right)=\mathrm{0},\\ \left(\frac{\mathrm{1}}{l}-{\beta }_i\right){\xi }_i=\mathrm{0},\\ \left(\frac{\mathrm{1}}{l}-{\beta }_i^{*}\right){\xi }_i^{*}=\mathrm{0},\end{array}$$

(14)

for any labeled data; that is, $i=\{\mathrm{1},\dots ,l\}$ .

Equations (14) lead to three conclusions. First, only the samples $(x_i,y_i)$ with corresponding ${\beta }_i^{(*)}=\mathrm{1}/l$ lie outside the ε-tube. Second, ${\beta }_i^{*}{\beta }_i=\mathrm{0}$ ; that is, a set of dual variables ${\beta }_i$ , ${\beta }_i^{*}$ is never simultaneously nonzero. Finally, for ${\beta }_i\in (\mathrm{0,1}/l)$ , we have

$$\begin{array}{cc}& {\xi }_i=\mathrm{0},\hspace{1em}\left(\epsilon +{\xi }_i-y_i+{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)+b\right)=\mathrm{0},\end{array}$$

(15)

and for ${\beta }_i^{*}\in (\mathrm{0,1}/l)$ we have

$$\begin{array}{cc}& {\xi }_i^{*}=\mathrm{0},\hspace{1em}\left(\epsilon +{\xi }_i^{*}+y_i-{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)-b\right)=\mathrm{0}.\end{array}$$

(16)

Hence, we can compute b using any data point satisfying ${\beta }_i\in (\mathrm{0},\mathrm{1}/l)$ or ${\beta }_i^{*}\in (\mathrm{0},\mathrm{1}/l)$ , given by

$$\begin{array}{cc}& b=\{\begin{array}{cc}{y}_i-{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)-\epsilon \mathrm{\hspace{0.17em}\hspace{0.17em}}\hfill & \text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\beta }_i\in \left(\mathrm{0},\frac{\mathrm{1}}{l}\right)\hfill \\ y_i-{\displaystyle \sum }_{j=\mathrm{1}}^{l+u}‍{\alpha }_{j}k\left(x_i,x_j\right)+\epsilon \mathrm{\hspace{0.17em}\hspace{0.17em}}\hfill & \text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\beta }_i^{*}\in \left(\mathrm{0},\frac{\mathrm{1}}{l}\right).\hfill \end{array}\end{array}$$

(17)

In reality, the value of b can be slightly different depending on which data point is used in (17). Averaging over all b obtained from support vectors may improve robustness.

3. RSSI-Based Location Awareness

In RSSI-based location awareness, mobile nodes of unknown locations collect the RSSI measurements emitted by n anchor nodes. We assume that the anchor nodes are stationary with known location in $\chi \in R^{\mathrm{2}}$ where χ is the area of interest. Each mobile node (i.e., mobile robot in our setting) estimates its own 2D location using the RSSI measurements.

Here, we introduce notations of the labeled and the unlabeled training data sets. Because each robot estimates its own location independent of the others, we will describe the algorithm of one mobile node. In the training phase, we put the mobile node at the specific location $s_i=[s_{xi},s_{yi}{]}^T$ and obtain the RSSI values $Z_i=[z_{i\mathrm{1}},\dots ,z_{ip},\dots ,z_{in}{]}^T\in R^n$ , where $s_{xi}$ and $s_{yi}$ are the x- and y-coordinate of the mobile node, and $z_{ip}$ is the RSSI value from the pth anchor node for $i=\mathrm{1},\dots ,l$ . The total l labeled training data sets to learn the $s_x$ and $s_y$ are defined as ${ℒ}_{s_x}=\{Z_i,s_{xi}{\}}_{i=\mathrm{1}}^l$ and ${ℒ}_{s_y}=\{Z_i,s_{yi}{\}}_{i=\mathrm{1}}^l$ , respectively. On the other hand, u unlabeled data consists of only the RSSI measurements, given by $𝒰=\{Z_j{\}}_{j=\mathrm{1}}^{l+u}$ .

In the test phase, with the trained semisupervised SVR model, the mobile node determines its own location $\widehat{s}(t)=[\widehat{s_x}(t),\widehat{s_y}(t){]}^T$ using the RSSI set $Z(t)\in R^n$ measured at time t.

We summarize the detail of the semisupervised SVR for RSSI-based location awareness Algorithms 1 and 2.

Algorithm 1 (training phase).

Consider the following.

Step 1.

Collect the training data set ${ℒ}_x$ , ${ℒ}_y$ , and 𝒰.

Step 2.

Obtain the kernel matrix K in (2).

Step 3.

Build weight matrix W and the graph Laplacian $L=D-W$ in (4).

Step 4.

Choose the regularization weights ${\gamma }_I$ and ${\gamma }_A$ in (1).

Step 5.

Solve the QP problem twice in order to obtain ${\alpha }_{s_x}^{*}$ and ${\alpha }_{s_y}^{*}$ in (13).

Step 6.

Compute $b_{s_x}$ and $b_{s_y}$ in (17).

Algorithm 2 (test phase).

Consider the following.

Step 1.

At time t, the mobile node collects the RSSI measurements $Z(t)$ from the n anchor nodes.

Step 2.

Obtain the regression estimation with $\widehat{s_x}(t)={\sum }_{i=\mathrm{1}}^{l+u}‍{\alpha }_{s_x}^{*}K(Z_i,Z(t))+b_{s_x}$ and $\widehat{s_y}(t)={\sum }_{i=\mathrm{1}}^{l+u}‍{\alpha }_{s_y}^{*}K(Z_i,Z(t))+b_{s_y}$ . Then decide the location estimate $\widehat{s}(t)=[\widehat{s_x}(t),\widehat{s_y}(t){]}^T$ .

4. Experimental Results

In the experimental setup, the total of thirteen anchor nodes using IEEE 802.15.4 and TinyOS is deployed. The nodes use commercial CC2420 radio chip which operates in the 2.4 GHz ISM band with a data rate of 256 kbps and provides a received signal strength indicator (RSSI) for each received packet. Two mobile robots, which are equipped with one receiver node, respectively, estimate their own position using the RSSI measurements obtained from the anchor nodes distributed in the 3 m × 4 m workspace, shown in Figure 2. For accuracy analysis, the true locations of the mobile robots are measured by the Vicon Motion System [26] composed of eight cameras that track reflective markers attached to the mobile robots.

Figure 2

Experimental setting with two mobile robots and thirteen anchor nodes in the 3 m × 4 m area.

For obtaining labeled training data, we collect the RSSI data sets of the mobile robot placed at the different locations, repeatedly. On the other hand, the unlabeled data sets are obtained as we let the mobile robots move automatically and collect the RSSI measurements. Figure 3 is an illustration of the obtained data set. Note that the real locations of the unlabeled data are not included in the unlabeled data set, although Figure 3 shows the locations of the unlabeled data.

Figure 3

Distribution of the thirty labeled and eighty unlabeled data and thirteen anchor nodes.

4.1. Characteristics of RSSI

Radio signal is easily influenced by environmental noise. Also, its measured value affects the performance of the location awareness. Here, we examine the characteristic of RSSI measurement.

We record RSSI measurements of one moving receiver, emitted by the fixed thirteen anchor nodes. The distance between the anchor nodes and receiver varies from 0.2 m to 3 m. Figure 4 shows the boxplot of the obtained measurements. The central red bar is the median and the edges of the box are the 25% and 75%. The upper and lower bars outside the box represent extreme data points. The results show highly nonlinear and noisy RSSI measurements, which supports the need for learning to obtain accurate estimates. Still, we can observe that similar RSSI values denote similar distance values, which suggests that RSSI values are meaningful data representing the actual phenomenon in a kernel space (i.e., RSSI measurements obtained from our experimental setup satisfy manifold assumption described in Section 2.3). Hence, the RSSI is suitable to be used for the LapSVR. We note that the LapSVR can be used with other sensors as long as they satisfy the manifold assumption.

Figure 4

Relationship between RSSI measurements and distance between fixed thirteen anchor nodes (transmitter) and one mobile node (receiver).

4.2. Model and Parameter Setting

We use as the kernel function in (2) the radial basis function (RBF) given by $K(x_i,x_j)=\exp (-{\parallel x_i-x_j\parallel }^{\mathrm{2}}/{\sigma }^{\mathrm{2}})$ , where σ is the kernel width parameter. In (4), the graph Laplacian consisted of $(l+u)$ samples using k-nearest neighbors, and the edge weights $W_{ij}$ are defined as Gaussian function of Euclidean distance. In all experiments, we set $\sigma =\mathrm{0.5}$ and $k=\mathrm{10}$ .

On the other hand, the regularization parameters ${\gamma }_A$ , ${\gamma }_I$ are obtained using cross-validation. We compute leave-one-out in the range $[\mathrm{1}{\mathrm{0}}^{-\mathrm{5}},\mathrm{1}{\mathrm{0}}^{-\mathrm{2}}]$ . Figure 5 shows the cross-validation result using 80 labeled data and 100 unlabeled data. We set optimal ${\gamma }_A$ , ${\gamma }_I$ minimizing the training error.

Figure 5

Training error over the validation set for the LapSVR as a function of regularization parameters ${\gamma }_A$ and ${\gamma }_I$ .

4.3. Performance

The proposed algorithm is compared with two other algorithms. First, the standard SVR is conventionally employed for the location awareness problem as in [14, 27]. Second, Laplacian least square (LapLS) is a recently developed semisupervised regression algorithm and its application to the location estimation can be found in [23]. LapLS solves optimization using graph Laplacian and loss function in the least square that does not have any constraint for the optimization. Therefore, an optimal solution can be obtained without a numerical process.

Figure 6 illustrates the true and estimated trajectories of the LapSVR, standard SVR, and LapLS algorithms using the obtained data set in Figure 3, where the LapSVR gives the best tracking performance. In the following, we show three kinds of performance criteria to compare the algorithms.

Figure 6

True and estimated trajectories of the mobile robots via Laplacian SVR (LapSVR), standard SVR (SVR), and Laplacian least square (LapLS).

First, Figure 7 shows the average location estimation errors according to the number of the labeled data, which are calculated after two mobile robots move along their own trajectories. We confirm that the proposed algorithm gives the best performance over the other two algorithms.

Figure 7

Performance of the three different algorithms according to the number of the labeled data.

Second, location estimation error of the LapSVR according to the number of the unlabeled data is described in Figure 8. From this result, we confirm that the unlabeled data gives a positive effect when the labeled data is insufficient (less than 50 labeled data in Figure 8). The excessive unlabeled data (more than 50 unlabeled data in Figure 8) does not improve the performance.

Figure 8

Performance of the LapSVR according to the number of the unlabeled data.

Third, we examine the sensitivity of the location estimation error with respect to the number of the anchor nodes. We prepare the set 2 consisting of all the deployed nodes. The set 1 is formed with the nodes whose numbers are from 1 to 9 depicted in Figure 2. The set 0 consists of the nodes whose numbers are 1, 3, 5, 7, and 9. In this experiment, we use 40 labeled data and 200 unlabeled data. As the result in Figure 9, the LapSVR algorithm causes the smallest growth of error as the number of the anchor nodes decreases in comparison with the other algorithms.

Figure 9

Sensitivity of the location estimation error to the number of the anchor nodes.

5. Conclusion

This paper proposes a semisupervised regression algorithm named Laplacian SVR by combining the core concepts of the standard SVR and a manifold regularization framework. The proposed algorithm learns the relation mapping function between the observation space and the physical space using a small number of the labeled data and a large number of the unlabeled data which can often be easily acquired more than the labeled data. The suggested algorithm is evaluated for location estimation of mobile robots in the wireless sensor network. In our multirobot system, the input of the learner is defined as the RSSI observation set and the output is the physical location. The experimental results show that the proposed algorithm gives the most precise performance and is least sensitive to variation of the number of anchor nodes in comparison with the standard SVR and the Laplacian least square algorithm.