Multi-targets device-free localization based on sparse coding in smart city

Abstract

With the continuous expansion of the market of device-free localization in smart cities, the requirements of device-free localization technology are becoming higher and higher. The large amount of high-dimensional data generated by the existing device-free localization technology will improve the positioning accuracy as well as increase the positioning time and complexity. The positions required from single target to multi-targets become a further increasing difficulty for device-free localization. In order to satisfy the practical localizing application in smart city, an efficient multi-target device-free localization method is proposed based on a sparse coding model. To accelerate the positioning as well as improve the localization accuracy, a sparse coding-based iterative shrinkage threshold algorithm (SC-IA) is proposed and a subspace sparse coding-based iterative shrinkage threshold algorithm (SSC-IA) is presented for different practical application requirements. Experiments with practical dataset are performed for single-target and multi-targets localization, respectively. Compared with three typical machine learning algorithms: deep learning based on auto encoder, K-nearest neighbor, and orthogonal matching pursuit, experimental results show that the proposed sparse coding-based iterative shrinkage threshold algorithm and subspace sparse coding-based iterative shrinkage threshold algorithm can achieve high localization accuracy and low time cost simultaneously, so as to be more practical and applicable for the development of smart city.

Introduction

Smart cities intelligently respond to the needs of life, environmental protection, public safety, urban services, and industrial and commercial activities by using information and communication technologies to perceive, analyze, and integrate key information from core urban operating systems. ¹ Its essence is to apply advanced information technology to realize the intelligent management and operation of the city and create a better life for the urban people. A smart city, trying to deal with the problems intelligently, may involve many application areas, as shown in Figure 1. Among all technologies and services in smart city, localization information is one of the most important elements. Thus, wireless localization technology, especially indoor localization technology, has become the practical basis for extensive applications. For example, in the healthcare of a home or hospital for detecting the location and activities of the elderly people or patients;^2,3 in smart spaces such as airports, shopping centers, and tourist attractions for location-based services;^4,5 in case of fire for location detection of firefighters and survivors to realize emergency rescue; ⁶ for indoor environmental monitoring and building energy saving control; ⁷ as well as for detecting and tracking the location of terrorists in safety protection. ⁸

Figure 1.

Frame diagram of smart city.

Various wireless localization technologies such as GPS, ⁹ infrared, ¹⁰ ultrasonic, ¹¹ and radio frequency (RF) identification ¹² have been developed to support the needs of the aforementioned scenarios. The application of these technologies, however, requires the target to be equipped with wireless devices, such as smart phones, ultrasonic receiver nodes, and tags.^13,14 Therefore, these device localization technologies may be limited in some scenarios, like in a fire or earthquake, in an emergency, and in detecting or tracking illegal people in the building, because the targets may not wear or carry trackable devices all the time.

Device-free localization (DFL) technology, using RF sensor network to detect, track, and locate targets without any additional devices, has attracted wide attention.^15–17 The principle of DFL is to detect targets and estimate the location of targets by the small RF signal changes caused by targets. Most current DFL methods, however, can only detect a single target rather than multi-targets, which will limit the practical application in smart city. Moreover, high localization accuracy depends on the deployment of large number of nodes and the repeated measurements of received signal strength (RSS), which will affect the efficiency and timeliness severely so as not to support the applications like real-time navigation or rescue in emergency. Therefore, reducing the total localization duration without sacrificing accuracy becomes critical. However, Wilson’s RF-based model ¹⁸ shows that as the number of nodes in the network increases, the total number of links will increase quadratically. Therefore, the processing of high-dimensional data in the DFL system will be the fundamental focus for practical application.

In order to deal with high-dimensional data and achieve high localization accuracy in the process of multi-target locating, an efficient multi-target device-free localization (EMDL) method is proposed. First, an iterative shrinkage threshold algorithm (ISTA) for target localization is combined with a sparse coding method based on convex optimization. Then, a subspace-based sparse coding (SSC) scheme is further proposed to reduce the dimension in the direction of row dimension and column dimension so as to handle the high-dimensional data problem. Finally, experiments based on practical dataset are carried out on the sparsely distributed targets, and the results are compared with those by three typical machine learning algorithms, deep learning based on auto encoder (DL-AE), K-nearest neighbor (KNN), and orthogonal matching pursuit (OMP), to evaluate the performance of the proposed algorithm.

The rest of this article is organized as follows: section “DFL model and algorithm” describes the typical DFL algorithms and models. Section “EMDL” introduces the established architecture, the localization stage, and the proposed algorithms of EMDL method in detail. The performance evaluation results are shown in section “Simulation results and evaluations,” and section “Conclusion” summarizes the whole work.

DFL model and algorithm

As shown in Table 1, the existing DFL methods mainly include fingerprint recognition, geometric methods, and compressive sensing (CS), where fingerprint-based localization is also integrated into other localization methods^19–22 to convert the localization problems into fingerprint matching problems. Collecting the fingerprint training database is always the first step, and then some machine learning classifier is adopted to match from the new fingerprint to determine the location of the target. Zhang et al. ²³ proposed a typical geometric method, in which the tracking field was divided into different regions, and the adjacent regions took different communication channels to improve the matching efficiency. For each zone, three nodes were deployed on the ceiling to form a regular triangle to monitor the zone. In each triangle region, a Support Vector Regression (SVR) model could be adopted to locate the object. Wang et al. ²⁴ converted the DFL problem into a sparse signal reconstruction problem and reconstructed the location information from the undersampling measurements using a recursive compressed sensing algorithm. The common problem of the aforementioned existing methods is that a large number of nodes are required to meet the requirements of high localization accuracy.

Table 1.

The list of DFL models.

DFL model	Core algorithm	Feature
Mager et al., 19 Seifeldin et al., 20 Molina et al., 21 and Roth et al. 22	Fingerprint matching	Numerous nodes
Zhang et al. 23	Support Vector Regression	Numerous nodes
Wang et al. 24	Recursive compressed sensing	Numerous nodes
Wang et al. 25	DBGM and KC	Low efficiency
Youssef et al. 26	CS and BGMP	Low efficiency
Liu et al. 27	LP and OMP	Low efficiency
Wang et al. 28	Sparse representation	Single target

DFL: device-free localization; DBGM: dynamic Bayesian Gaussian mixture; KC: K-means clustering; CS: compressive sensing; BGMP: Bayesian greedy matching pursuit; LP: linear programming; OMP: orthogonal matching pursuit.

Many models and algorithms are presented based on the characteristics of the target locations and the relationship between the RSS measurements and the target states. Wang et al. ²⁵ used a dynamic Bayesian Gaussian mixture algorithm (DBGM) and a K-means clustering (KC) to improve the objects tracking in radio tomographic imaging (RTI) systems. Youssef et al. ²⁶ proposed a dynamic statistical model based on CS theory and used Bayesian greedy matching pursuit (BGMP) algorithm to locate the target. Liu et al. ²⁷ used sparse representation model for indoor localization and applied the traditional sparse coding algorithms LP and OMP to solve the l₁-norm constraint minimization problem. These algorithms are inefficient in processing high-dimensional data. In addition, ²⁸ a sparse representation model for DFL was proposed, but only focused on single-target localization rather than multi-target localization. In addition, ²⁹ a novel affine scaling steepest descent (ASSD) algorithm was also proposed to find a satisfying sparse solution of l_p-norm minimization. The optimal step size is calculated by the steepest descent direction, which not only overcomes the problem that the traditional l_p-norm minimization sparse recovery algorithm usually obtains the suboptimal sparse solution when the initial point does not belong to the convergence domain of the global optimal sparse solution, and convergence is also accelerated at low signal-to-noise ratio (SNR). The sparse matrix construction and iterative ideas in this algorithm are very instructive for accelerating locating.

Based on the aforementioned algorithms, for the purpose of practical application in smart city, an efficient multi-target DFL model is proposed based on sparse representation. Algorithmically, unlike the traditional sparse coding algorithms like OMP, the advanced Iterative-shrinkage-threshold Algorithm (IA) is introduced for sparse coding to improve the efficiency of processing high-dimensional data in DFL.

EMDL

This section focuses on the architecture of the proposed EMDL, as well as the core algorithms presented based on the sparse model.

Architecture of EMDL

The architecture of EMDL proposed in this article can be described from both the theoretical models and practical applications.

Theoretical model

Sparse coding algorithm is an unsupervised learning method to represent the sample data efficiently by exploring a set of super-complete basis vectors. In view of the large amount of data and high dimensions in indoor localization, sparse coding algorithm will be introduced in the proposed EMDL to achieve high precision and efficiency of localization. Figure 2 shows the theoretical framework of EMDL. According to the theoretical model of EMDL, the feature data will be extracted from each sub-dataset of the original data and stored in a column, so as to achieve dimensionality reduction in the column. Then, similar method is adopted to further reduce the row dimension. The reduction from two dimensions can improve the effect of data shrinking and avoid the main original information lost.

Figure 2.

Theoretical framework of EMDL.

Practice model

The monitoring area of the proposed EMDL system can be discretized into a grid as shown in Figure 3, where only the target location is non-zero, so as to weaken the energy of signal broadcasting. That is, only the target locations will affect the RSS measurements of each anchor point (AP) in the detection area of the EMDL system. The wireless sensor node is referred to as the AP. ³⁰ All APs are transmitters–receivers, which are deployed around the monitoring area and can communicate with each other. These APs act as the transmitters in sequence according to the schedule, that is, only one AP transmits the detecting signal and the other APs receive the signal at some time. As shown in Figure 3, the appearance of a target may absorb and scatter the transmitted signals, which will cause the RSS measurements changing so as to achieve the target detection.

Figure 3.

Practice model of EMDL.

Overall process of EMDL

Assume that there $L$ APs deployed in the monitoring area. As shown in Figure 2, $L$  = 24 and the APs are sequentially used as transmitters from No.1 to No.24. ${\varphi }_{i,j}$ indicates the RSS measurements received by the ith AP from the jth AP with the target lying at a known location. For example, ${\varphi }_{16,1}$ in Figure 3 indicates the 16th AP receiving RSS from the first AP. The vector ${\varphi }_i$ is composed of RSS measurements received at the ith-AP from all the $L$ APs and can be noted as equation (1)

$${\varphi }_i={[{\varphi }_{i,1},{\varphi }_{i,2},...,{\varphi }_{i,L}]}^T\in R^L$$

(1)

where [.] ^T represents the transposition. There will be $L$ elements in the RSS matrix.

Considering that there will be only one AP operating as the transmitter at one time, ${\varphi }_{i,i}$ is set to be a constant value for each AP, since it is equivalent to the transmitting signal strength theoretically. Therefore, an RSS matrix $\varphi$ containing all links can be obtained as equation (2)

$$\varphi ={[{\varphi }_1,{\varphi }_2,...,{\varphi }_L]}^T=\left[\begin{array}{cccc}{\varphi }_{1,1}\hfill & {\varphi }_{1,2}\hfill & ...\hfill & {\varphi }_{1,L}\hfill \\ \multicolumn{1}{c}{{\varphi }_{2,1}}& {\varphi }_{2,2}\hfill & ...\hfill & {\varphi }_{2,L}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\varphi }_{L,1}}& {\varphi }_{L,2}\hfill & ...\hfill & {\varphi }_{L,L}\hfill \end{array}\right]\in R^{L\times L}$$

(2)

where there will be $L\times L$ elements in the RSS matrix $\varphi$ . After the models being established, the proposed EMDL method can be performed by two phases: (1) the dictionary constructing phase and (2) the unknown target detecting and localizing phase.

Dictionary constructing phase

The monitoring area is discretized into $K$ grids, as shown in Figure 4. A reference point (RP) is defined in each grid to make these RPs be divided into $K$ classes according to their locations.

Figure 4.

The dictionary constructing phase.

During the offline testing process, assume a target lying at or passing some RP, each AP will transmit the detecting signal in turn according to the schedule, and the other APs will obtain the RSS measurements to form the RSS matrix. To cover all the possible positions, the aforementioned measuring steps will be repeated for all $K$ RPs. Take the simulate target lying in any qth RP as an example, and $\tau$ time tests are repeated to get $\tau$ RSS matrices $\{{\varphi }_{q1},{\varphi }_{q2},...{\varphi }_{\mathrm{qb}},...{\varphi }_{q\tau }\}$ , where ${\varphi }_{\mathrm{qb}}$ $(1\le b\le \tau )$ is the bth RSS matrix at the qth RP. Then, each RSS matrix can be vectorized as equation (3)

$$W_{\mathrm{qb}}=\mathrm{vec}\left({\varphi }_{\mathrm{qb}}\right),(1\le b\le \tau )$$

(3)

where $W_{\mathrm{qb}}\in R^m$ is the bth sample vector at the qth RP. Then the $\tau \mathrm{th}$ sample vector of the qth RP is taken as the column of the matrix $W_q$ with the structure as equation (4)

$$\begin{array}{c}{W}_q=[w_{q1},w_{q2},...,w_{\mathrm{qb}},...,w_{q\tau }]\in R^{m\times \tau }\hfill \\ (1\le q\le K)\hfill \end{array}$$

(4)

where $m=L\times L$ , W_q is the sample matrix of the qth RP, and $w_{\mathrm{qb}}$ is the bth column of $W_q$ .

Performing τ tests at $K$ RPs will be generated $K$ sample matrices, each of which is similar to $W_q$ . Then, $n(n=K\times \tau )$ sample vectors are ranged together to form a new matrix as equation (5)

$$\begin{array}{l}W=\left[W_1,W_2,\dots W_q,\dots W_K\right]\\ =\left[w_{11},w_{12},\dots w_{K\tau }\right]\in R^{m\times n}\end{array}$$

(5)

where the $W$ composed of all samples is called the dictionary.

Detecting and localizing phase

After the training in the offline stage, the target will be detected and localized, which can be called online stage. The practical detecting signal will be obtained and the detecting vector $y$ $(y\in R^m)$ is as equation (6)

$$y=\mathrm{vec}(\varphi )$$

(6)

Linear combination of the detecting signals

Assume that the target is lying at the pth RP, that is, the target belongs to the pth class. If there are enough experiments performed at the pth RP in the dictionary constructing phase to obtain enough samples for the pth RP, the new sample of the simulate target obtained at the pth RP can be approximated by the pth sample matrix $W_p$ as equation (7)

$$\begin{array}{cc}\multicolumn{1}{c}{y}& =W_p{\alpha }_p\hfill \\ \multicolumn{1}{c}{}& =\sum _{l=1}^{\tau }{w}_{\mathrm{pl}}{\alpha }_{\mathrm{pl}}\hfill \\ \multicolumn{1}{c}{}& ={\alpha }_{p1}{w}_{p1}+{\alpha }_{p2}{w}_{p2}+...+{\alpha }_{\mathrm{pn}}{w}_{p\tau },(1\le p\le K)\hfill \end{array}$$

(7)

where ${\alpha }_{\mathrm{pn}}\in R$ is the linear combination coefficient of each term, and ${\alpha }_p=[{\alpha }_{p1},{\alpha }_{p2},\dots {\alpha }_{p\tau }]\in R^{\tau }$ is the formed vector.

Sparse representation of the detecting signals

The samples in Figure 5 are taken as example with the dataset consisting of 81 points from 9 classes. The red triangle in Figure 5 represents the detecting signal, the blue circle represents the non-zero coefficient of the red triangle after classification by sparse representation, and the rest represents the training sample of the dictionary. It can be seen that if the detecting signal belongs to the fifth class, the selected samples for indicating the non-zero coefficients of the detecting signal sorted by the sparse representation are also mainly from the fifth class.

Figure 5.

Description of the detecting signal sparse-representation classification.

Based on equation (7), the linear representation of the detecting vector $y$ can be sparsely represented by $n$ sample vectors of the dictionary as equation (8)

$$y=W_p{\alpha }_p=W\alpha$$

(8)

where $\alpha =[0,...,{\alpha }_{p1},{\alpha }_{p2},...,{\alpha }_{p\tau },...,0{]}^T\in R^n$ corresponds to the sparse coefficient vector, and the non-zero elements in the vector are related to the locations of the targets. From this point of view, equation (8) becomes a sparse representation problem.

EMDL algorithms

Sparse model

Sparse coding is a process of calculating the coefficient vector based on the detecting signals set $y$ and the known dictionary $W$ as shown in Figure 6. The sparse solutions of equation (8) by sparse coding are the locations of the targets.

Figure 6.

Description of the sparse coding process for the target localization.

For $W\in R^{m\times n}$ , if $m>n$ , equation (8) is an overdetermined system with a unique solution. In most cases for DFL, however, there is $m<n$ . Because it is expected to achieve the higher accuracy in the dictionary construction phase, the more experiments on each RP should be performed. Such relationship may result in the total number of columns $n=K\times \tau$ being greater than $m$ .

If $m<n$ , equation (8) is an underdetermined system with more than one solution. The sparsest selection method may help to solve such problem. Generally, direct sparse metric is implemented by the l₀-norm (the l₀-norm refers to the number of non-zero elements in the vector), and the sparsest solution of equation (8) can be obtained by solving the optimization problem of the following l₀-norm equation (9)

$${\alpha }^{*}=\underset{\alpha }{\arg min}\Vert \alpha {\Vert }_0\mathrm{s}.\mathrm{t}.y=W\alpha$$

(9)

where l₀-norm $\Vert \alpha {\Vert }_0$ is used to count the number of non-zero elements in $\alpha$ . To find the sparsest solution of equation (9) in the underdetermined linear equation, however, has been proved to be an non-deterministic polynomial (NP) problem. Moreover, l₀-norm is non-differentiable and non-convex. Therefore, according to Smith ³¹ and Zhang et al., ³² the sparsest solution can be obtained through l₁-norm convex optimization. We replace the l₀-norm in equation (9) with the following l₁-norm minimization problem equation (10)

$${\alpha }^{*}=\underset{\alpha }{\arg min}\Vert \alpha {\Vert }_1\mathrm{s}.\mathrm{t}.y=W\alpha$$

(10)

Considering the noise in practical data, the dense noise model is introduced and equation (8) is modified to equation (11)

$$y=W\alpha +v$$

(11)

where $v\in R^m$ is a noise term with the boundary of $\Vert v{\Vert }_2^2<\epsilon$ , and $v$  = 0 is a noiseless condition. Then, equation (10) can be modified to equation (12)

$${\alpha }^{*}=\underset{\alpha }{\arg min}\Vert \alpha {\Vert }_1\mathrm{s}.\mathrm{t}.\Vert y-W\alpha {\Vert }_2^2<\epsilon$$

(12)

For sparse coding, a more general modification of equation (12) is to use the $l_1$ regularization method, as in equation (13)

$${\alpha }^{*}=\{\underset{\alpha }{\arg min}\frac{1}{2}\Vert y-W\alpha {\Vert }_2^2+\mu {\Vert \alpha \Vert }_1\}$$

(13)

where the first term with l₂-norm square is the reconstructing error term, and the second term with l₁-norm is the sparse penalty term related to the possible location range of the target. $\mu$ is a small empirical constant called the scaling constant, to weigh the first error term and the second sparse term.

Finally, equation (13) is optimized in EMDL using the ISTA ³³ with the sparse coding steps as in equation (14)

$$\begin{array}{c}\multicolumn{1}{c}{{\alpha }_{k+1}=h_{\theta }(\frac{1}{C}{W}^{T}y+(I-\frac{1}{C}{W}^{T}W){\alpha }_k}\end{array})\theta =\frac{\mu }{C},{\alpha }_0=0$$

(14)

where $C$ is a constant greater than the maximum eigenvalue of $W^{T}W$ , $\mu$ is the scaling constant of equation (13), $I$ is an identity matrix, and $\theta$ is the threshold being calculated according to $C$ and $\mu$ . In addition, $h_{\theta }$ is a contraction operator, defined as equation (15)

$$h_{\theta }{\left(x\right)}_i={(|x_i|-\theta )}_{+}+\mathrm{sign}\left(x_i\right),i=1,...,n$$

(15)

where $(·{)}_{+}$ represents returning the positive part.

Sparse coding-based iterative shrinkage threshold algorithm

Sparse coding-based iterative shrinkage threshold algorithm (SC-IA) is proposed based on the aforementioned established model to accelerate the positioning. According to equations (14) and (15), ${\alpha }^{*}$ in equation (13) can be expressed as equation (16)

$$\begin{array}{c}\multicolumn{1}{c}{{\alpha }^{*}=\{{\alpha }_1^{*},...,{\alpha }_n\}=\{\alpha {11}^{*},...,{\alpha }_{\mathrm{pj}}^{*},...,{\alpha }_{K\tau }^{*}\},}\\ \multicolumn{1}{c}{p=1,...,K;j=1,...\tau }\end{array}$$

(16)

Based on equation (16), let ${\alpha }_p^{★}=\sum _{j=1}^{\tau }{\alpha }_{\mathrm{pj}}^{*}$ , so ${\alpha }^{*}$ is changed to ${\alpha }^{★}$ as equation (17)

$${\alpha }^{★}=\{{\alpha }_1^{★},...,{\alpha }_p^{★},...,{\alpha }_K^{★}\},{\alpha }^{★}\in R^{K\times 1}$$

(17)

If the solution only includes one non-zero component, the corresponding location of RP can be directly treated as the target location. If the solutions contain multiple non-zero components, it can be divided into the following two cases:

• For a single target, the location of the target can be estimated at the $\phi \mathrm{th}$ RP by equation (16), where $\phi$ is given by equation (18)

$$\phi =\underset{p}{\arg max}\{{\alpha }_1^{★},...,{\alpha }_p^{★},...,{\alpha }_K^{★}\}$$

(18)

• For $N$ sparse targets, the relative locations are estimated at the ${\phi }_1\mathrm{th},\dots ,{\phi }_N\mathrm{th}$ RP, where ${\phi }_1,\dots ,{\phi }_N$ are subscripts of elements in vector ${\alpha }^{★}$ in increasing order. Then, equation (17) can be expressed as equation (19)

$$\{\begin{array}{c}{\phi }_1=\underset{p}{\arg max}\{{\alpha }_1^{★},...,{\alpha }_p^{★},...,{\alpha }_K^{★}\}\hfill \\ \multicolumn{1}{c}{⋮}\\ \multicolumn{1}{c}{{\phi }_N=\underset{p}{\arg max}\{{\alpha }_1^{★},...,{\alpha }_p^{★},...,{\alpha }_K^{★}\}}\end{array}$$

(19)

where $\{{\alpha }_{\phi 1}^{*},...,{\alpha }_{\phi N-1}^{*}\}$ is not contained in $\{{\alpha }_1^{*},...,{\alpha }_p^{*},...,{\alpha }_K^{*}\}$ . SC-IA is shown in Table 2.

Table 2.

Pseudocode for SC-IA.

Input: $y\in R^m$ , $W\in R^{m\times n}\mu$ , $C$  > max (eigenvalue) $W^{T}W,\theta =\frac{\mu }{C},{\alpha }_0=0,I=1$ 1: Fori = 0: max (iteration) 2: ${\alpha }_{i+1}\leftarrow h_{\theta }(\frac{1}{C}{W}^{T}y+(I-\frac{1}{C}{W}^{T}W){\alpha }_i)$ 3: Until $\Vert {\alpha }_{i+1}-{\alpha }_i{\Vert }_2^2\le \gamma$ $\mathrm{\%}\gamma$ is a threshold 4: End If 5: ${\alpha }^{*}\leftarrow {\alpha }_{i+1}$ 6: ${\alpha }^{*}$ is transformed to ${\alpha }^{☆}$ by equation (17) 7: If Num(target) == 1 Then 8: Determine $\phi$ as the ID of targets location by equation (18) 9: Return $\phi$ 10: End If 11: If Num(target) == N $(N>1)$ Then 12: Determine ${\phi }_1,...,{\phi }_N$ by equations (17) and (19) 13: Return $\{{\phi }_1,...,{\phi }_N\}$ 14: End If Output: $\phi$ or ${\phi }_1,...,{\phi }_N$

SC-IA: sparse coding efficient multi-target device-free local.

SSC-IA

Considering that the large amount of data in the space may affect the localizing efficiency, a SSC scheme is proposed to utilize subspace techniques. After the dimensionality reduction is operated in the row and column directions of the EMDL dataset, SC-IA can be performed in the low-dimensional subspace to improve the efficiency without sacrificing the localization accuracy.

Inspired by subspace techniques used in dimensionality reduction ³⁴ and denoising, ³⁵ a new dictionary will be constructed in the principal component subspace. Specifically, the entire process of the SSC scheme is divided into two steps.

Dimensionality reduction in column direction

It can be known from equation (5) that the original dictionary $W=[W_1,W_2,...W_q,...W_K]$ can obtain a corresponding matrix $W_{\mathrm{norm}}=[W_1^{\prime },...,W_q^{\prime },...,W_K^{\prime }]$ by zero-mean normalization, that is, subtracting the sample mean and dividing by the standard deviation. For any qth RP (i.e. any qth class), the correlation matrix of can be calculated as equation (20)

$$M_q=\frac{1}{\tau }\sum _i^{\tau }{w}_{\mathrm{qi}}^{\prime }{w}_{\mathrm{qi}}^{\prime H}$$

(20)

where $[·{]}^H$ is a conjugate transpose and there is $M_q\in R^{m\times m}$ . By singular value decomposition (SVD), there will be equation (21)

$$M_q=U_q{\Sigma }_q{V}_q$$

(21)

where $U$ is a normalized eigenvector matrix of size $m\times m$ to represent the characteristics of the original dataset. $\Sigma =\mathrm{diag}\{{\sigma }_1,...,{\sigma }_2,...,{\sigma }_m\}$ is a diagonal singular value matrix, and all singular values are sorted in descending order. ${\mu }_{q1}$ is related to the largest singular value ${\sigma }_1$ and represents the major characteristic of $W_q$ . Therefore, after SVD is performed on all the total $K$ sample matrices, the semi-transform matrix $U$ can be obtained as equation (22), which is constituted by the eigenvectors related to the maximum eigenvalues of all RPs

$$U=\{u_{11},u_{21},...,u_{q1},...,u_{K1}\},(1\le q\le K)$$

(22)

Dimensionality reduction in row direction

Before dimensionality reduction in the row dimension, zero-mean normalization is performed on $U$ just like the first step of dimensionality reduction in the column dimension direction, and the corresponding matrix $U_{\mathrm{norm}}$ can be obtained. The covariance matrix $\mathrm{\Omega }$ of $U_{\mathrm{norm}}$ is calculated as equation (23)

$$\mathrm{\Omega }=\frac{1}{K}{U}_{\mathrm{norm}}{U}_{\mathrm{norm}}^H$$

(23)

Then, the eigenvalues and eigenvectors of $\mathrm{\Omega }$ will be obtained by eigenvalue decomposition (EVD) by equation (24)

$$\mathrm{\Omega }=S\wedge S^T$$

(24)

where $S=\{s_1,s_2,...,s_k,...,s_m\}$ is an m × m normalized eigenvector matrix, and the eigenvectors $s_1,...,s_k,...s_m$ therein represent the characteristics of the original dataset. $\lambda =\mathrm{diag}\{{\lambda }_1,{\lambda }_2,...,{\lambda }_m\}$ is a diagonal eigenvalue matrix and ${\lambda }_1\ge {\lambda }_2\ge ,...,\ge {\lambda }_m$ are sorted in descending order. $\{s_1,...,s_k,...,s_m\}$ and $\{{\lambda }_1,...,{\lambda }_k,...,{\lambda }_m\}$ are the eigenvectors and eigenvalues of $\mathrm{\Omega }$ with $s_k$ related to ${\lambda }_k$ . Finally, the principal component subspace is found by transforming the matrix $S_k$

$$S_k=\{s_1,s_2,...,s_k\},(1\le k\le m)$$

(25)

where $S_k$ is the sub-matrix of $S$ depending on the selection of $k$ . Since eigenvalues represent the energy distribution of the original data, the cumulative energy content (CEC) of the first eigenvector is the sum of the energy of all eigenvalues from 1 to $k$ . Then, $k$ can be determined by equation (26)

$$\mathrm{RoC}=\frac{\mathrm{CE}{C}_p}{\mathrm{CE}{C}_a}=\frac{\sum _{z=1}^k{\lambda }_z}{\sum _{z=1}^m{\lambda }_z},(1\le k\le m)$$

(26)

where RoC is the abbreviation for ratio of cumulative distribution. $\mathrm{CE}{C}_p$ is the CEC of principal component. $\mathrm{CE}{C}_a$ is the CEC of all components.

Therefore, it is necessary to achieve a high RoC with the smallest possible $k$ value. To be more specific, RoC should be above a certain threshold $\gamma$ in practical application. Putting $\mathrm{RoC}=\gamma$ into equation (26) can explore the minimum $k$ . Then, the transformation matrix $S_k\in R^{m\times k}$ can be found based on equations (25) and (26), where $S_k$ consists of eigenvectors associated with the principal components that span subspaces of signal principal component.

Therefore, a new approximate sample dictionary $W_{\mathrm{appr}}$ can be obtained by $S_k$ and will be transformed into the dictionary of the main component subspace as in equation (27)

$$W_{\mathrm{appr}}=S_k^{T}U$$

(27)

where $S_k^T\in R^{k\times m}$ is the transpose of $S_k$ and $W_{\mathrm{appr}}\in R^{k\times K}$ is the new dictionary after the dimension reduction on the original dictionary $W$ .

In the detecting phase, when the target is in the monitoring area, a new approximate detecting vector $y_{\mathrm{appr}}$ can be obtained from equation (28)

$$y_{\mathrm{appr}}=S_k^{T}y$$

(28)

where $y_{\mathrm{appr}}\in R^{k\times 1}$ is the new detecting result after reducing the dimension of the original detection signal $y$ .

Therefore, similar to the process of SC-IA, targets can be located by addressing the following issues (equation (29))

$${\beta }^{*}=\{\underset{\beta }{\arg min}\frac{1}{2}\Vert y_{\mathrm{appr}}-W_{\mathrm{appr}}\beta {\Vert }_2^2+\rho {\Vert \beta \Vert }_1\}$$

(29)

where $\beta$ is the coefficient vector and ${\beta }^{*}$ is the sparse solution. Combining equations (14) and (15), ${\beta }^{*}$ will be obtained from equation (30)

$${\beta }^{*}=\{{\beta }_1^{*},...,{\beta }_p^{*},...,{\beta }_K^{*}\},p=1,...,K;{\beta }^{*}\in R^{K\times 1}$$

(30)

If ${\beta }^{*}$ includes only one non-zero component, the corresponding RP location can be considered as the location of the target. For the condition of multiple non-zero components, there will be the following two cases:

• For a single target, the location of the target will be estimated at the $\phi \mathrm{th}$ RP based on equation (30) with $\phi$ given by equation (31)

$$\phi =\underset{p}{\arg max}\{{\beta }_1^{*},...,{\beta }_p^{*},...,{\beta }_K^{*}\}$$

(31)

• For $N$ targets of sparse distribution, the locations are estimated from ${\phi }_1\mathrm{th}$ to the ${\phi }_N\mathrm{th}$ RP, where ${\phi }_1,\dots ,{\phi }_N$ are subscripts of elements with decreasing order in the vector as equation (32)

$$\{\begin{array}{c}{\phi }_1=\underset{p}{\arg max}\{{\beta }_1^{*},...,{\beta }_p^{*},...,{\beta }_K^{*}\}\hfill \\ \multicolumn{1}{c}{⋮}\\ \multicolumn{1}{c}{{\phi }_N=\underset{p}{\arg max}\{{\beta }_1^{*},...,{\beta }_p^{*},...,{\beta }_K^{*}\}}\end{array}$$

(32)

where $\{{\beta }_{\phi 1}^{*},...,{\beta }_{\phi N-1}^{*}\}$ is not contained in $\{{\beta }_1^{*},...,{\beta }_p^{*},...,{\beta }_K^{*}\}$ . Based on the construction of $W_{\mathrm{appr}}$ and $y_{\mathrm{appr}}$ the proposed subspace sparse coding-based iterative shrinkage threshold algorithm (SSC-IA) is given in Table 3.

Table 3.

Pseudocode for SSC-IA.

Input: $y\in R^m$ , $W\in R^{m\times n}\rho$ , $C$ , ${\beta }_0$  = 0, $I$  = 1 1: Perform SVD procedure and conduct transformation in the direction of column dimension, according to equations (20)–(22) 2: Choose $C$ : $C$  > max eigen $(U_{\mathrm{norm}}^T{U}_{\mathrm{norm}})$ , $\theta \leftarrow \frac{\rho }{C}$ 3: Perform EVD procedure and conduct dimensionality reduction in the direction of row dimension, according to equations (23)–(28) 4: For $i$  = 0: max(iteration) 5: ${\beta }_{i+1}\leftarrow h_{\theta }(\frac{1}{C}{W}_{\mathrm{appr}}^r{y}_{\mathrm{appr}}+(I-\frac{1}{C}{W}_{\mathrm{appr}}^r{W}_{\mathrm{appr}}){\beta }_i)$ 6: Until $\Vert {\beta }_{i+1}-{\beta }_i{\Vert }_2^2\le \gamma$ $\mathrm{\%}\gamma$ is a threshold 7: End for 8: ${\beta }^{*}\leftarrow {\beta }_{i+1}$ 9: If Num(target) == 1 Then 10: Determine $\phi$ by equation (31) 11: Return $\phi$ 12: End If 13: If Num(target) == N(N>1) Then 14: Determine ${\phi }_1,...,{\phi }_N$ by equation (32) 15: Return $\{{\phi }_1,...,{\phi }_N\}$ 16: End If Output: $\phi$ or ${\phi }_1,...,{\phi }_N$

SSC-IA: subspace sparse coding-based iterative shrinkage threshold algorithm; SVD: singular value decomposition; EVD: eigenvalue decomposition.

Simulation results and evaluations

The performance of the proposed EMDL will be evaluated using the experimental dataset from the SPAN laboratory of the University of Utah.

Figure 7 shows the experimental scenario on the first floor of the physical laboratory building. A total of 24 APs are deployed on a 12 m × 12 m square simulating area with 2 m between APs. Each AP works in 2.4 GHz and communicates using the IEEE 802.15.4. There are 36 RPs in the monitoring area. Thirty tests are performed repeatedly with the same configuration for each RP. The RSS sample matrix at each RP is divided into two parts, where 25 tests are used to construct the dictionary and the average of the rest 5 tests is used as a detecting signal for locating a single target. For the condition with multiple targets, the dictionary is the same as the dictionary for locating a single target, but the detecting signal is from another 30 new RSS samples for each additional target.

Figure 7.

Description of the experimental scenario.

Settings and indicators

SC-IA and SSC-IA are compared with three popular algorithms widely used in DFL such as DL-AE, KNN, and OMP. Considering OMP is an effective DFL algorithm based on sparse coding ²³ essentially, SSC-OMP representing OMP based on the SSC mechanism proposed in this article is also adopted for performance comparison to estimate the subspace sparse coding algorithm. Some performance indicators used are described as follows:

• $B_{\mathrm{total}}$ is the total number of testing samples and $B_{\mathrm{correct}}$ is the number of samples that can be correctly located. The localization accuracy is calculated as equation (33)

$$\mathrm{Accuracy}=\frac{B_{\mathrm{correct}}}{B_{\mathrm{total}}}$$

(33)

• Assuming that the actual locations of $N$ targets are $(x_1,y_1),...,(x_N,y_N)$ , the corresponding estimated locations are $(x{\prime }_1,y{\prime }_1),...,(x{\prime }_N,y{\prime }_N)$ . The mean localization error (MLE) is the average distance between the actual locations and the estimated locations of $N$ targets, expressed as equation (34)

$$\mathrm{MLE}=\frac{\sum _{l=1}^N\sqrt{{(x_1-{x_1}^{\prime })}^2+{(y_1-y\prime )}^2}}{N}$$

(34)

For a single target location (N = 1), MLE becomes localization error (LE) $e_i(1\le i\le 36)$ , representing the Euclidean distance between the estimated location of the assumed target at the ith RP and the actual location. The average localization error (ALE) $\mathrm{ALE}=\sum _{i=1}^{36}{e}_i/36$ will be obtained by the target passing through all RPs.

• When data are converted to the subspace, both the row and column dimensions are reduced. For ease of presentation, the row dimension is abbreviated as Rds, and the column dimension is abbreviated as Cds in the following description.

• In practical applications, the EMDL system is inevitably subject to the noise. Gaussian distribution is adopted to simulate the additive noise in the experiments. For any ith RP $(1\le i\le 36)$ as an example, noise is added to the detecting signal matrix $S_i$ and the dictionary $D$ by $S_i^{★}=S_i+N$ and $D^{★}=D+N$ , respectively, where $N$ is a Gaussian noise matrix that obeys Gaussian distribution. SNR is a common measure of signal quality in noisy environments. In the experiments, the SNR of the detecting signal is set between −10 and 40 dB, and the SNR of the dictionary is set between 0 and 40 dB.

Single target localization

The experiments for single target localization are performed during the dictionary constructing phase with the comparison in noisy environment and noise-free environment.

Localization performance of SC-IA

Figure 8 shows the comparison of localizing performance by SC-IA, DL-AE, KNN, and OMP. It can be seen from Figure 8(a) that when the SNR is greater than 10 dB, the accuracy of four algorithms is basically above 90%. However, when the SNR is between 5 and 10 dB, the accuracy of the SC-IA algorithm is significantly higher than that of the other three algorithms. When the SNR is less than 5 dB, it can be seen that the accuracy of all algorithms drops sharply, indicating that this range does not satisfy the localization conditions. Figure 8(b) depicts the case of LE for SC-IA with SNR in the range of −10 to 40 dB. It can be seen that in the case where the SNR of the detection signal is 10 dB or noiseless, the LE of all detected locations is close to zero. This means that SC-IA is robust to noise when the SNR of the detecting signal is greater than 10 dB.

Figure 8.

Localization performance of SC-IA with noisy and noiseless detecting signals: (a) comparison of localizing accuracy with different SNRs and (b) comparison of LE for SC-IA at each RP.

Localization performance of SSC-IA

Figure 9 shows the comparison of the localization performance of SSC-IA and other three algorithms in processing low-dimensional data. It can be seen from Figure 9(a) that when the row dimension of the data is reduced to 10, the localizing accuracy of the SSC-IA can reach 97.5%, which is much higher than that of the other three algorithms. When the row dimension of the data is higher than 12, the accuracy of the algorithm is 100%, but the convergence speed of SSC-IA is better than the other three algorithms. When the row dimension of the data is less than 10, the accuracy of the four algorithms is less than 93%, indicating that the lower limit of the dimension of accurate localization is reached at this time. Figure 9(b) shows the comparison of the ALE of SC-IA with the processing data of 576-Rds-900-Cds and SSC-IA with processing data sizes of 10-Rds-35-Cds, 20-Rds-35-Cds, and 30-Rds-35-Cds, when the SNR of the detecting signal is between −10 to 40 dB. It can be seen that when the SNR is greater than 10 dB, the ALE of the SC-IA and the SSC-IA with a processing data dimension of 30-Rds-35-Cds is close to 0; at the same time, when SNR is greater than 15 dB, SSC-IA with the processing data dimension of 20-Rds-35-Cds also performs well. This shows that if the data dimension is reduced to 30-Rds-35-Cds, the localizing accuracy and the robustness are not affected. SSC-IA can be used to process reduced dimensionality data and is robust to noisy environments when the SNR is above 10 dB. This means that even if the dimension of EMDL data is reduced from 576-Rds-900-Cds to 20-Rds-35-Cds in noiseless condition, or the data dimension drops to 30-Rds-35-Cds when the SNR is higher than 10 dB, SSC-IA can maintain high accuracy and efficient processing performance, which will greatly reduce the computational burden.

Figure 9.

Localization performance of SSC-IA and the compared methods with different row dimensional data: (a) comparison of localizing accuracy with other algorithms and (b) comparison of ALE with SNR from −10 to 40 dB.

In addition, the reason why low-dimensional data are used in EMDL is that almost all important features of each class are extracted into the eigenvector after EVD. Therefore, reducing the column dimension will not lose the main feature. As shown in Figure 10(a), the eigenvalues associated with the original data are sorted in descending order. The first principal component ${\mu }_1$ represents the feature of the maximum variance in the EMDL data. The second principal component ${\mu }_2$ represents the characteristic of the next largest variance in the EMDL data. As shown in Figure 10(b), after the SVD, according to the calculation results, about 97.3% of the main features move to the first 12 rows, and another 2.7% of the unimportant features move to the next rows. Moreover, noise is included in the later unimportant features and is rejected by the dataset.

Figure 10.

Eigenvalue (a) and cumulative distribution ratios (RoC) (b) associated with the 1st to the 40th.

Therefore, it is understandable that the accuracy can reach 100% when the eigenvalue is higher than 12 in Figure 9(a). That is because the first 12 features of the reduced data can represent 97.3% of the characteristics of the original dataset, which is enough to ensure the accuracy of EMDL.

Localization performance of dictionary construction with noise

SSC-IA with data dimension of 30-Rds-35-Cds shows the same good localization performance as SC-IA with data dimension of 576-Rds-900-Cds when SNR is greater than 10 dB according to Figure 9(b). Therefore, in this section, the original data as well as the data with dimension reduced to 30-Rds-35-Cds are adopted to simulate the localization performance in dictionary construction with noise.

As shown in Figure 11, the noise is added to the dictionary ranging from 0 to 40 dB with an interval of 5 dB. Meanwhile, experiments were performed using the detecting signal datasets with SNR = 10 dB and SNR = 20 dB and a noiseless dataset, processing the original dataset of 576-Rds-900-Cds and the dimensionality reduced dataset of 30-Rds-35-Cds. Figure 11(a) shows that ALE will approach 0 when a noiseless detecting signal or a detecting signal with SNR = 20 dB is input. SC-IA can achieve high accuracy and is robust when the SNR of the dictionary is 15 dB. After the SNR of the dictionary is higher than 25 dB, SC-IA can achieve very low error even if the detecting signal with SNR = 10 dB is input.

Figure 11.

Localization performance of SC-IA and SSC-IA with the noisy dictionary when the detection signal is noisy with SNR = 10 and 20 dB and noiseless: (a) average localization error of SC-IA and (b) average localization error of SSC-IA.

After the SNR of the dictionary reaches 10 dB, ALE will approach 0 when the noiseless detecting signal or the detecting signal with SNR = 20 dB is input as in Figure 11(b), which indicates that the proposed SSC-IA can maintain high accuracy and robustness. However, when the SNR of the detecting signal is 10 dB, SSC-IA may fail to maintain the localizing accuracy. In addition, it can be found that when the SNR of the dictionary is 10 dB, the localizing accuracy of SSC-IA is greater than that of SC-IA, mainly because EVD is actually a denoising process of feature extraction.

From Figure 12, the localization performance of SSC-IA and SC-IA is greater than the that of other three algorithms, and SSC-IA is superior to SC-IA with the noisy dictionary.

Figure 12.

Performance comparison between proposed algorithm and other algorithms for processing noiseless detection signals.

Therefore, it can be considered that SC-IA and SSC-IA can maintain good performance in terms of accuracy and robustness even if the dataset is affected by a certain degree of noise during the dictionary constructing stage and the target detecting stage.

Multi-targets localization

The localizing performance of the proposed SC-IA and SSC-IA for multi-targets, which is the most practical requirement in smart city, will be evaluated in this section. The case of two targets is taken as an example. Table 4 provides six possible locations of the simulated two targets.

Table 4.

Six locations of the two simulated targets (unit: meter).

Cases: coordinate	Target 1 ( $x_1$ , $y_1$ )	Target 2 ( $x_2$ , $y_2$ )
Location 1	(2,8)	(6,4)
Location 2	(2,8)	(6,8)
Location 3	(2,8)	(8,8)
Location 4	(2,8)	(10,8)
Location 5	(2,8)	(8,4)
Location 6	(2,8)	(4,8)

Figure 13 is a comparison of the localizing results of the two targets. Figure 13(a) shows that the MLE for the last five cases is almost zero for SC-IA based on the dictionary of 576-Rds-900-Cds so as to prove that the two target locations can be accurately estimated. However, for the first case, target 1 can be accurately located, while there is a small LE of 0.63 m at its adjacent location of (4,6) for target 2. When a 15-Rds-35-Cds low-dimensional dictionary is adopted by SSC-IA, there will be a small error in the fourth case and a large error in the first case. When using a dictionary of20-Rds-35-Cds, the LE of the first case can be reduced significantly. In addition, when using the dictionary of 25-Rds-35-Cds, there is no error except for the first case, and the same localization accuracy is achieved by SC-IA. Figure 13(b) further proves that SSC-IA is superior to the other three algorithms when the data dimension is reduced to 15-Rds-35-Cds, 20-Rds-35-Cds, and 25-Rds-35-Cds. Therefore, SSC-IA with 25-Rds-35-Cds data can achieve the same high accuracy with SC-IA for two target localization.

Figure 13.

Comparison of localization performance between SC-IA and SSC-IA locating two targets: (a) mean localization error of SC-IA and SSC-IA and (b) comparison of the mean localization error between SSC-IA and other three algorithms for processing 15, 20, and 25 rows of data, respectively, where KNN cannot locate multiple targets.

In addition, the execution time costs of OMP, SSC-OMP, SC-IA, and SSC-IA in processing different dimensional data are listed and compared in Table 5 to show the time cost of sparse coding to process high-dimensional data, and the acceleration effect when the input data is reduced from 576-Rds-900-Cds to low dimension.

Table 5.

Time costs for processing different dimensional data.

Coding method	Dictionary dimension	Coding time (s)
OMP	576-Rds-900-Cds	0.35
SC-IA	576- Rds-900-Cds	2.0 × 10−3
SSC-OMP	30- Rds-35-Cds	3.6 × 10−4
SSC-IA	30- Rds-35-Cds	1.9 × 10−4

OMP: orthogonal matching pursuit, SC-IA: sparse coding based iterative shrinkage threshold algorithm; SSC: subspace-based sparse coding; SSC-IA: subspace sparse coding-based iterative shrinkage threshold algorithm.

It can be seen from Table 5, when the original data are 576-Rds-900-Cds, the time costs of OMP and SC-IA are 0.35 s and 2.0 × 10⁻³ s, respectively, which indicates that the proposed SC-IA is more efficient than OMP in processing high-dimensional data of EMDL. For the low-dimensional data of 30-Rds-35-Cds, the relative time costs are further reduced to 3.6 × 10⁻⁴ and 1.9 × 10⁻⁴ s by SSC, which means that the subspace sparse coding algorithm can accelerate the convergence significantly to improve the localizing efficiency remarkably.

Conclusion

Indoor location sensing is one of the important elements in smart city. In this article, an EMDL system is proposed to provide effective and accurate DFL for multi-targets, so as to expand new practical application as well as accelerate the development of relative intellectual technologies. Considering the accuracy requirement on DFL for multi-targets, a sparse coding model and a sparse coding method based on iterative shrinkage threshold algorithm (SC-IA) are proposed in this article. The high localizing accuracy, however, causes the sample data to increase seriously and inevitably. Aiming at the curse of dimensionality in multi-targets localization, a subspace sparse coding mechanism is presented to optimize SC-IA as SSC-IA, for obtaining low-dimension data and high efficiency by maintaining the localizing accuracy. Simulating results show that, compared with three typical algorithms of FDL, the proposed EMDL based on SC-IA can achieve much higher localizing accuracy and that based on SSC-IA can reduce the data dimension more greatly, so as to perform better than the other typical algorithms, both a single target localization and multiple targets localization. Moreover, experiments in noisy environment prove that the proposed EMDL system possesses better robustness. Finally, the analyses on operating efficiency further suggest that EMDL has obvious advantages in localization time cost. The superiorities in accuracy and efficiency make the proposed EMDL have more practical application value in the development of smart cities. Future research direction will focus on the moving target and the indoor navigation based on SSC.