# Wireless Network Indoor Positioning Method Using Nonmetric Multidimensional Scaling and RSSI in the Internet of Things Environment

Authors: Shuxia Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Aiming at the problem that the indoor target location algorithm based on received signal strength (RSSI) in the IoT environment is susceptible to interference and large fluctuations, an indoor localization algorithm combining RSSI and nonmetric multidimensional scaling (NMDS) is proposed (RSSI- NMDS). First, Gaussian filtering is performed on the received plurality of sets of RSSI signals to eliminate abnormal fluctuations of the RSSI. Then, based on the RSSI data, the dissimilarity matrix is constructed, and the relative coordinates of the nodes in the low-dimensional space are obtained by NMDS solution. Finally, according to the actual coordinates of the reference node, the coordinate transformation is performed by the planar four-parameter model, and the position of the node in the actual coordinate system is obtained. The simulation results show that the proposed method has strong anti-RSSI perturbation and high positioning accuracy.


---

## Body

## 1. Introduction

With the development of Internet of things and mobile Internet technology, smart home is gradually entering people’s daily life. As an important information-processing technology in the field of smart home, indoor positioning technology is the key to improve the comfort, safety, and intelligence of home environment and build an efficient smart home system [1–3].At present, the positioning algorithm can be divided into two categories: based on ranging positioning algorithm and no ranging positioning algorithm [4, 5]. The ranging algorithm is commonly used based on received signal strength indicator (RSSI), based on time of arrival (TOA), time difference of arrival (TDA), and AOA based on the signal arrival angle (angle of arrival) positioning method [6–8]. No distance and angle information is needed without the ranging positioning algorithm, and the algorithm implements node positioning based on information such as network connectivity [9].Due to the popularity and improvement of indoor wireless local area network (WLAN), ranging-based positioning usually uses an RSSI-based approach. Compared with the other wireless positioning technologies, the RSSI-based positioning technology performs position estimation according to the law that the received signal strength changes with the signal propagation distance, so no additional equipment for precise time synchronization and angle measurement is needed [10]. At the same time, the RSSI-based positioning technology has the characteristics of wireless low power consumption and strong adaptability to complex nonvisual indoor environments. It is also possible to make full use of the networking functions of existing wireless network facilities and expand the application range of the positioning system. Therefore, the RSSI-based positioning technology is currently a research hotspot for indoor positioning [11, 12]. In reference [13], based on the existing research, an improved location fingerprint location method based on RSSI was proposed from the aspects of offline fingerprint database construction, subregion division, and online position estimation. Reference [14] proposed a dynamic interval particle filter algorithm based on pedestrian dead reckoning (PDR) information and RSSI localization information. With PDR azimuth information, the algorithm can adaptively control the interval derivative particle number to enhance the filtering real time ability; meanwhile, the building map information, RSSI positioning information, and certainty factor are integrated into the particle weight calculation to improve the positioning accuracy. Aiming at the problem of the information jump in WIFI indoor location based on the RSSI, which influences the positioning accuracy, the authors in [15] proposed an improved adaptive weighted K-nearest neighbor (AWKNN) localization method based on the Kalman filter. Experiments show that these methods have achieved good results.However, RSSI-based positioning methods are susceptible to insufficient indoor wireless signals, time differences in indoor signals, and multipath effects [16]. In order to solve the problem that RSSI ranging technology introduces large errors in complex and variable indoor environments, multidimensional scaling (MDS) is introduced [17]. The MDS technology in statistics has strong fault tolerance to the data sample, so the technology can be introduced into the indoor RSSI positioning, which will improve the antijamming ability of the positioning and obtain better positioning effect. In order to improve the positioning performance, this paper applies Gaussian filtering to RSSI signal and adopts nonmetric multidimensional scaling (NMDS) to enhance the resistance to RSSI perturbation and improve the positioning accuracy.


## 2. The Principle of RSSI Ranging

### 2.1. RSSI Ranging

In indoor environments, the strength of wireless signals is unpredictable due to multipath propagation and shadowing effects, and log-distance models are often used to represent signal propagation losses [18]. Let the distance between the receiving node and the transmitting node be d, then the loss caused by the signal during propagation can be expressed as(1)PLd=PLd0+10nlogdd0+Xσ,where d is the distance between the transmitting node and the receiving node; n is the path loss index, indicating how fast the path loss increases with distance, and is related to the surrounding environment; Xσ is the mean in decibels, and the standard deviation is σ the Gaussian distribution random variable; d0 is the reference distance, usually 1 m; and PLd0 represents the path loss when the reference distance is d0.The signal strength received at the receiving end is(2)RSSI=Pt−PLd,where P represents the transmit power of the signal and PLd is the path loss after the distance d.According to the above theoretical model, for a single wireless access node (AP), the size of the RSSI value read by the receiving end is closely related to the distance from the AP. However, as shown in Figure1, for a single AP, the difference in signal strength between pairs of different locations does not effectively characterize the distance between them. For example, the distance between A and C in Figure 1 is much larger than the distance between A and B. However, according to the foregoing signal propagation theory, the difference in signal strength received at two points A and C is smaller than the difference in signal strength received at two points A and B. This problem still exists when the number of APs is small.Figure 1
RSSI ranging diagram.When the number of APs in the system increases, the consistency between the RSSI difference obtained between pairs of nodes at different locations and the actual physical distance is improved.In other words, the farther the two locations are apart, the greater the RSSI difference obtained at these two locations, and vice versa. Next, we analyze the relationship between the signal strength distance between different pairs of locations and the actual physical distance in the case of multiple APs. Assume that each point in the area can receive signals from N APs, and the RSSI obtained at the A position can be expressed as(3)RSSIA=RSSIA1,RSSIA2,…,RSSIAN,where RSSIAi=Pti−PLid0−10nlogdAi/d0−Xσi, 1≤i≤N, dAi is the distance from the A position to the i AP, and Pti and PLid0 are the transmit power of the i AP and the near-ground reference point power, respectively.Since the transmit power of each AP and the power of the near-ground reference point are unchanged, equation (3) can be expressed as(4)RSSIA=AP1−10nlogdA1+Xσ1,AP2−10nlogdA2+Xσ2,⋯APN−10nlogdAN+XσN,where APi=Pti−PLid0. Similarly, we can write the RSSI read at the B and C positions.From equation (4), the Euclidean distance between the RSSIs read by A and B is(5)RSSIAB=∑i=1N10nlogdBidAi+δi2,where dAi and dBi are the distances from A and B to the i AP, respectively.


### 2.2. RSSI Filter Processing

The RSSI value between nodes has a certain relationship with the distance. The overall trend is that the farther the distance between the two nodes is, the smaller the RSSI value is, and the closer the distance is, the larger the RSSI value is. However, since the RSSI value extracted during transmission is not stable, its volatility is large, and the RSSI value of the node near the distance is often smaller than the RSSI value of the node farther [19, 20]. Since the RSSI value is easily affected by air or occlusion in the environment, the RSSI value received by the same unknown node will fluctuate to varying degrees when the distance is constant. Therefore, in practical applications, the RSSI value is received multiple times for the same node for a period of time, and the RSSI values are processed to avoid the accuracy of the data in the case of individual abnormalities. Substituting the processed RSSI value into equation (5) yields a more accurate internode distance.Commonly used filtering models include maximum likelihood filtering, mean filtering, least squares estimation filtering, and Gaussian filtering. It has been studied that most of the variables in the natural environment are subject to positive or similar distributions, so Gaussian functions are often used in the processing of some data variables. To this end, Gaussian filtering is used to process the extracted sets of data.In this paper, Gaussian models are used to filter multiple RSSI values. Selecting the data information that occurs in the high probability region among a large amount of sampled data, eliminating the small probability event, thus avoiding the influence of the small probability zone data on the accuracy of the whole experiment, is essential for improving the accuracy of the entire laboratory data. In this paper, the RSSI value of the selected high probability data area is geometrically averaged, which reduces the influence of data volatility on experimental performance, makes the experimental data more representative and stable, and the positioning experiment results are more convincing. Usually, the probability density function of a Gaussian function can be expressed as(6)fx=12πσe−x−u2/2σ2,where(7)u=1n∑i=1nxi,σ2=1n−1∑i=1nxi−u2.In practical system applications, according to engineering experience, the numerical range of event occurrence probability greater than 0.6 is defined as the high probability event data generation area. Therefore, the Gaussian distribution function occurs in the interval0.6≤Fx≤1, which leads to(8)0.15σ+u≤x≤3.09σ+u.Therefore, it can be obtained from the Gaussian filter distribution function in the range of the above equation. The size of the sampled RSSI data value shall be0.15σ+u,3.09σ+u; here, the relationship between the RSSI value and u, σ is(9)u=1n∑i=1nRSSIi,σ=1n−1∑i=1nRSSIi−1n∑i=1nRSSIi2.The values ofu and σ are substituted into the range of the RSSI value to obtain an accurate range of RSSI values. All the RSSI data sampled are filtered by the value range. Filter data are not in this range and save all sampled data within this range. Finally, the RSSI values occurring in the high probability occurrence area are geometrically averaged to obtain the RSSI values between the nodes in the communication process.


## 2.1. RSSI Ranging

In indoor environments, the strength of wireless signals is unpredictable due to multipath propagation and shadowing effects, and log-distance models are often used to represent signal propagation losses [18]. Let the distance between the receiving node and the transmitting node be d, then the loss caused by the signal during propagation can be expressed as(1)PLd=PLd0+10nlogdd0+Xσ,where d is the distance between the transmitting node and the receiving node; n is the path loss index, indicating how fast the path loss increases with distance, and is related to the surrounding environment; Xσ is the mean in decibels, and the standard deviation is σ the Gaussian distribution random variable; d0 is the reference distance, usually 1 m; and PLd0 represents the path loss when the reference distance is d0.The signal strength received at the receiving end is(2)RSSI=Pt−PLd,where P represents the transmit power of the signal and PLd is the path loss after the distance d.According to the above theoretical model, for a single wireless access node (AP), the size of the RSSI value read by the receiving end is closely related to the distance from the AP. However, as shown in Figure1, for a single AP, the difference in signal strength between pairs of different locations does not effectively characterize the distance between them. For example, the distance between A and C in Figure 1 is much larger than the distance between A and B. However, according to the foregoing signal propagation theory, the difference in signal strength received at two points A and C is smaller than the difference in signal strength received at two points A and B. This problem still exists when the number of APs is small.Figure 1
RSSI ranging diagram.When the number of APs in the system increases, the consistency between the RSSI difference obtained between pairs of nodes at different locations and the actual physical distance is improved.In other words, the farther the two locations are apart, the greater the RSSI difference obtained at these two locations, and vice versa. Next, we analyze the relationship between the signal strength distance between different pairs of locations and the actual physical distance in the case of multiple APs. Assume that each point in the area can receive signals from N APs, and the RSSI obtained at the A position can be expressed as(3)RSSIA=RSSIA1,RSSIA2,…,RSSIAN,where RSSIAi=Pti−PLid0−10nlogdAi/d0−Xσi, 1≤i≤N, dAi is the distance from the A position to the i AP, and Pti and PLid0 are the transmit power of the i AP and the near-ground reference point power, respectively.Since the transmit power of each AP and the power of the near-ground reference point are unchanged, equation (3) can be expressed as(4)RSSIA=AP1−10nlogdA1+Xσ1,AP2−10nlogdA2+Xσ2,⋯APN−10nlogdAN+XσN,where APi=Pti−PLid0. Similarly, we can write the RSSI read at the B and C positions.From equation (4), the Euclidean distance between the RSSIs read by A and B is(5)RSSIAB=∑i=1N10nlogdBidAi+δi2,where dAi and dBi are the distances from A and B to the i AP, respectively.


## 2.2. RSSI Filter Processing

The RSSI value between nodes has a certain relationship with the distance. The overall trend is that the farther the distance between the two nodes is, the smaller the RSSI value is, and the closer the distance is, the larger the RSSI value is. However, since the RSSI value extracted during transmission is not stable, its volatility is large, and the RSSI value of the node near the distance is often smaller than the RSSI value of the node farther [19, 20]. Since the RSSI value is easily affected by air or occlusion in the environment, the RSSI value received by the same unknown node will fluctuate to varying degrees when the distance is constant. Therefore, in practical applications, the RSSI value is received multiple times for the same node for a period of time, and the RSSI values are processed to avoid the accuracy of the data in the case of individual abnormalities. Substituting the processed RSSI value into equation (5) yields a more accurate internode distance.Commonly used filtering models include maximum likelihood filtering, mean filtering, least squares estimation filtering, and Gaussian filtering. It has been studied that most of the variables in the natural environment are subject to positive or similar distributions, so Gaussian functions are often used in the processing of some data variables. To this end, Gaussian filtering is used to process the extracted sets of data.In this paper, Gaussian models are used to filter multiple RSSI values. Selecting the data information that occurs in the high probability region among a large amount of sampled data, eliminating the small probability event, thus avoiding the influence of the small probability zone data on the accuracy of the whole experiment, is essential for improving the accuracy of the entire laboratory data. In this paper, the RSSI value of the selected high probability data area is geometrically averaged, which reduces the influence of data volatility on experimental performance, makes the experimental data more representative and stable, and the positioning experiment results are more convincing. Usually, the probability density function of a Gaussian function can be expressed as(6)fx=12πσe−x−u2/2σ2,where(7)u=1n∑i=1nxi,σ2=1n−1∑i=1nxi−u2.In practical system applications, according to engineering experience, the numerical range of event occurrence probability greater than 0.6 is defined as the high probability event data generation area. Therefore, the Gaussian distribution function occurs in the interval0.6≤Fx≤1, which leads to(8)0.15σ+u≤x≤3.09σ+u.Therefore, it can be obtained from the Gaussian filter distribution function in the range of the above equation. The size of the sampled RSSI data value shall be0.15σ+u,3.09σ+u; here, the relationship between the RSSI value and u, σ is(9)u=1n∑i=1nRSSIi,σ=1n−1∑i=1nRSSIi−1n∑i=1nRSSIi2.The values ofu and σ are substituted into the range of the RSSI value to obtain an accurate range of RSSI values. All the RSSI data sampled are filtered by the value range. Filter data are not in this range and save all sampled data within this range. Finally, the RSSI values occurring in the high probability occurrence area are geometrically averaged to obtain the RSSI values between the nodes in the communication process.


## 3. Multidimensional Scaling Technology

Robustness is one of the important indicators to evaluate the quality of a positioning algorithm. In the indoor environment, the RSSI is disturbed by many unfavorable factors such as multipath, diffraction, and obstacles, which may cause the signal strength value to deviate. Therefore, the accuracy of the positioning algorithm is difficult to guarantee.The fluctuation of RSSI will cause a large error in the distance of the conversion, which leads to the fact that most RSSI-based positioning algorithms cannot obtain the positioning accuracy comparable to the simulation in the actual environment. However, it is worth mentioning that RSSI can indeed reflect the relationship between nodes. The closer the receiving point is to the transmitting point, the stronger the measured signal strength; the farther the receiving point is from the transmitting point, the weaker the measured signal strength. This monotonic relationship between the wireless signal strength RSSI and the distance satisfies the requirements for the dissimilarity data between objects in the multidimensional scaling. Considering this feature, it can be directly located by RSSI. The RSSI is used to construct the dissimilarity matrix in the multidimensional scaling method to calculate the relative coordinates of each node in low-dimensional space.MDS is a data analysis technique commonly used for exploratory data analysis or information visualization, which was originally used for data analysis in psychometrics. At present, multidimensional scaling analysis has been used as a general data analysis technique, not only in the scope of psychology, but also widely used in various fields. Multidimensional scaling techniques use the dissimilarity between entities to construct a relative coordinate map of points on a multidimensional space, and make the construction points correspond to the individual entities in the multidimensional space. The distance between two points in a multidimensional space is closely related to the similarity of the entities it corresponds to. The more similar entities, the closer they are in the multidimensional space.


### 3.1. Classic Multidimensional Scaling

Classical multidimensional scaling (Classic MDS) is the simplest multidimensional scaling method, the data are quantitative, and the similarity between objects can be characterized by Euclidean distance. The goal of the multidimensional scaling method is to determine the relative position coordinates of the analysis object in the multidimensional space. The Euclidean distance between the objects through some transformations (such as linear transformation) will be related to the similarity provided. Without considering the error, if the similarity data are measured in Euclidean space, the classical multidimensional scaling algorithm will accurately reproduce the positional distribution of the analysis object.Assume thatpij represents the similarity measured between the analysis objects i and j (i,j=1,…,N), and the Euclidean distances of the points Xi=xi1,xi2,…,xim and Xj=xj1,xj2,…,xjm in the multidimensional space are expressed as(10)dij=∑k=1mxik−xjk2.The goal of the classic multidimensional scaling technique is to minimize the stress strength coefficient, where the threat strength factor is(11)stress=∑i≠jpij−dij2.The classical multidimensional scaling solution process is divided into the following three steps:(1)
Square the individual elements of the dissimilarity matrixpij, denoted as P2.(2)
Double-centeringP2, that is, both sides of P2 are multiplied by the central matrix J at the same time, as defined below:(12)J=E−1n,whereE is an n order identity matrix, and after double-centering, matrix B is obtained:(13)B=−12J⋅P2⋅J.(3)
Perform singular value decomposition on B, and obtain the largestr eigenvalues λ1∼λr and the corresponding eigenvectors e1∼er to form the matrix A of the diagonal matrix V and n×r, respectively, to obtain the relative coordinates of the analysis object in the multidimensional space:(14)X=V⋅A1/2.The firstr maximum eigenvalues and eigenvectors (r<m) are reserved, resulting in a solution in the low-dimensional space. This means that the k sums in equation (10) are run from 1 to r, not 1 to m. In the least squares sense, this is the optimal low rank approximation. For example, for a two-dimensional network, the first two largest eigenvalues and their eigenvectors are taken to construct an optimal two-dimensional approximation. For a three-dimensional network, the first three largest eigenvalues and their eigenvectors are taken to construct an optimal three-dimensional approximation.


### 3.2. Nonmetric Multidimensional Scaling

The nonmetric multidimensional scaling is a kind of multidimensional scaling technique, and the requirement for constructing the object dissimilarity matrix is not as strict as the classical multidimensional scaling, as long as the monotonic relationship of the distance is satisfied.The nonmetric multidimensional scale reconstructs the coordinates and distances of things in a multidimensional space according to the dissimilarity between given things. This is a process of iterative judgment. Assuming that the dissimilarity matrix between things ispij, the specific process can be described as follows:(1)
Arbitrarily generate the initialization coordinatesX0 of each thing and calculate the distance dij0 between them, and initialize the coordinate X0 only to satisfy the different coordinates of each thing.(2)
Generate an intermediate valued^ij0, which is generated by constructing a monotonic regression relationship between pij and dij0. d^ij0 and pij need to satisfy the weak monotonic relationship, that is, for any i,j,k,l, if pij≥pkl, that is d^ij0≥d^kl0. The following approximation can be used to obtain d^ij0. Starting from the minimum value of pij, the adjacent d^ij0 is compared with each pij to determine whether the monotonic relationship is satisfied. When there is a continuous d^ij0 that violates the monotonic relationship with pij, the average of these values is taken for the next iteration.(3)
Calculate the new coordinatesX1 according to X0 and d^ij0, and calculate the distance between them dij1, and determine whether the stress coefficient stress1 meets the requirements. If stress1 does not meet the requirements, repeat the second and third steps until stress1 meets the requirements. Here, the stress strength coefficient stress1 is defined as(15)stress1=∑i≠jd^ij−dij2∑i≠jdij2.


### 3.3. Construct Dissimilarity Matrix Based on RSSI

The RSSI-NMDS algorithm proposed in this paper directly uses the RSSI value for positioning. Based on RSSI, the dissimilarity matrix P in the multidimensional scaling method is constructed, and the relative coordinates of each node in low-dimensional space are calculated.The multidimensional scaling method dissimilarity matrix P is a symmetric matrix. However, due to the nonuniformity of antenna transmission, in the actual environment, there is oftenRSSIij≠RSSIji. Therefore, in order to obtain a symmetric matrix, the average value RSSIij+RSSIji/2 of the two may be taken, or one of them may be selected to construct the dissimilarity matrix. In practical applications, the difference between the two is small. To reduce communication overhead, usually choose one of these values. For example, the reference node is set to a number, and the N reference node is sent to all reference nodes whose number is less than N, and the mobile node sends a message to the reference node, and uses the one-way communication to obtain the RSSI value to construct a symmetric dissimilarity matrix P:(16)pij=pji=RSSIijα,i≠j,0,i=j,where a denotes the dissimilarity correction index for correcting the rank order of the RSSI values. Taking 4 nodes as an example, directly construct the dissimilarity matrix P using RSSI:(17)P=0RSSI21αRSSI31αRSSI41αRSSI21α0RSSI32αRSSI42αRSSI31αRSSI32α0RSSI43αRSSI41αRSSI42αRSSI43α0.The dissimilarity matrix is constructed based on the RSSI value, and the relative coordinates of the nodes in the low-dimensional space are obtained by the multidimensional scaling method. In order to obtain the actual position of the mobile node, the coordinate transformation can be performed by using the planar four-parameter model according to the actual coordinates of the reference node, thereby obtaining the position of the mobile node in the actual coordinate system. The four-parameter coordinate transformation model is(18)x2y2=x1y1⋅1+mcosβ1+msinβ−1+msinβ1+mcosβ+ΔxΔy,where x1y1 is the relative coordinate of the nodes in the two-dimensional space, x2y2 is the actual coordinate after the transformation, m, β, Δx, Δy are the four to be determined parameters.In order to reduce the error in the coordinate conversion process and ensure the accuracy of the actual coordinates of the moving node, the parameter should be selected to minimize the sum of the deviations of the coordinates of thek reference nodes after conversion and their true coordinates (xiryir,i=1,…,k). The deviation performance function measures the appropriateness of the parameters of the coordinate transformation model:(19)difference=∑i=1k1+mcosβxli−1+msinβyli+Δx−xir2+1+msinβxli+1+mcosβyli+Δy−yir1/2.The smaller the deviation difference, the smaller the positioning error caused by the coordinate transformation. With the goal of minimizing equation (19), appropriate optimization algorithms must be used to select the appropriate parameters.


## 3.1. Classic Multidimensional Scaling

Classical multidimensional scaling (Classic MDS) is the simplest multidimensional scaling method, the data are quantitative, and the similarity between objects can be characterized by Euclidean distance. The goal of the multidimensional scaling method is to determine the relative position coordinates of the analysis object in the multidimensional space. The Euclidean distance between the objects through some transformations (such as linear transformation) will be related to the similarity provided. Without considering the error, if the similarity data are measured in Euclidean space, the classical multidimensional scaling algorithm will accurately reproduce the positional distribution of the analysis object.Assume thatpij represents the similarity measured between the analysis objects i and j (i,j=1,…,N), and the Euclidean distances of the points Xi=xi1,xi2,…,xim and Xj=xj1,xj2,…,xjm in the multidimensional space are expressed as(10)dij=∑k=1mxik−xjk2.The goal of the classic multidimensional scaling technique is to minimize the stress strength coefficient, where the threat strength factor is(11)stress=∑i≠jpij−dij2.The classical multidimensional scaling solution process is divided into the following three steps:(1)
Square the individual elements of the dissimilarity matrixpij, denoted as P2.(2)
Double-centeringP2, that is, both sides of P2 are multiplied by the central matrix J at the same time, as defined below:(12)J=E−1n,whereE is an n order identity matrix, and after double-centering, matrix B is obtained:(13)B=−12J⋅P2⋅J.(3)
Perform singular value decomposition on B, and obtain the largestr eigenvalues λ1∼λr and the corresponding eigenvectors e1∼er to form the matrix A of the diagonal matrix V and n×r, respectively, to obtain the relative coordinates of the analysis object in the multidimensional space:(14)X=V⋅A1/2.The firstr maximum eigenvalues and eigenvectors (r<m) are reserved, resulting in a solution in the low-dimensional space. This means that the k sums in equation (10) are run from 1 to r, not 1 to m. In the least squares sense, this is the optimal low rank approximation. For example, for a two-dimensional network, the first two largest eigenvalues and their eigenvectors are taken to construct an optimal two-dimensional approximation. For a three-dimensional network, the first three largest eigenvalues and their eigenvectors are taken to construct an optimal three-dimensional approximation.


## 3.2. Nonmetric Multidimensional Scaling

The nonmetric multidimensional scaling is a kind of multidimensional scaling technique, and the requirement for constructing the object dissimilarity matrix is not as strict as the classical multidimensional scaling, as long as the monotonic relationship of the distance is satisfied.The nonmetric multidimensional scale reconstructs the coordinates and distances of things in a multidimensional space according to the dissimilarity between given things. This is a process of iterative judgment. Assuming that the dissimilarity matrix between things ispij, the specific process can be described as follows:(1)
Arbitrarily generate the initialization coordinatesX0 of each thing and calculate the distance dij0 between them, and initialize the coordinate X0 only to satisfy the different coordinates of each thing.(2)
Generate an intermediate valued^ij0, which is generated by constructing a monotonic regression relationship between pij and dij0. d^ij0 and pij need to satisfy the weak monotonic relationship, that is, for any i,j,k,l, if pij≥pkl, that is d^ij0≥d^kl0. The following approximation can be used to obtain d^ij0. Starting from the minimum value of pij, the adjacent d^ij0 is compared with each pij to determine whether the monotonic relationship is satisfied. When there is a continuous d^ij0 that violates the monotonic relationship with pij, the average of these values is taken for the next iteration.(3)
Calculate the new coordinatesX1 according to X0 and d^ij0, and calculate the distance between them dij1, and determine whether the stress coefficient stress1 meets the requirements. If stress1 does not meet the requirements, repeat the second and third steps until stress1 meets the requirements. Here, the stress strength coefficient stress1 is defined as(15)stress1=∑i≠jd^ij−dij2∑i≠jdij2.


## 3.3. Construct Dissimilarity Matrix Based on RSSI

The RSSI-NMDS algorithm proposed in this paper directly uses the RSSI value for positioning. Based on RSSI, the dissimilarity matrix P in the multidimensional scaling method is constructed, and the relative coordinates of each node in low-dimensional space are calculated.The multidimensional scaling method dissimilarity matrix P is a symmetric matrix. However, due to the nonuniformity of antenna transmission, in the actual environment, there is oftenRSSIij≠RSSIji. Therefore, in order to obtain a symmetric matrix, the average value RSSIij+RSSIji/2 of the two may be taken, or one of them may be selected to construct the dissimilarity matrix. In practical applications, the difference between the two is small. To reduce communication overhead, usually choose one of these values. For example, the reference node is set to a number, and the N reference node is sent to all reference nodes whose number is less than N, and the mobile node sends a message to the reference node, and uses the one-way communication to obtain the RSSI value to construct a symmetric dissimilarity matrix P:(16)pij=pji=RSSIijα,i≠j,0,i=j,where a denotes the dissimilarity correction index for correcting the rank order of the RSSI values. Taking 4 nodes as an example, directly construct the dissimilarity matrix P using RSSI:(17)P=0RSSI21αRSSI31αRSSI41αRSSI21α0RSSI32αRSSI42αRSSI31αRSSI32α0RSSI43αRSSI41αRSSI42αRSSI43α0.The dissimilarity matrix is constructed based on the RSSI value, and the relative coordinates of the nodes in the low-dimensional space are obtained by the multidimensional scaling method. In order to obtain the actual position of the mobile node, the coordinate transformation can be performed by using the planar four-parameter model according to the actual coordinates of the reference node, thereby obtaining the position of the mobile node in the actual coordinate system. The four-parameter coordinate transformation model is(18)x2y2=x1y1⋅1+mcosβ1+msinβ−1+msinβ1+mcosβ+ΔxΔy,where x1y1 is the relative coordinate of the nodes in the two-dimensional space, x2y2 is the actual coordinate after the transformation, m, β, Δx, Δy are the four to be determined parameters.In order to reduce the error in the coordinate conversion process and ensure the accuracy of the actual coordinates of the moving node, the parameter should be selected to minimize the sum of the deviations of the coordinates of thek reference nodes after conversion and their true coordinates (xiryir,i=1,…,k). The deviation performance function measures the appropriateness of the parameters of the coordinate transformation model:(19)difference=∑i=1k1+mcosβxli−1+msinβyli+Δx−xir2+1+msinβxli+1+mcosβyli+Δy−yir1/2.The smaller the deviation difference, the smaller the positioning error caused by the coordinate transformation. With the goal of minimizing equation (19), appropriate optimization algorithms must be used to select the appropriate parameters.


## 4. Simulation and Analysis

### 4.1. Simulation Settings

Set up 45 unknown nodes and perform simulation experiments in the Microsoft Visual Studio 2010 programming environment. The distance between nodes is obtained according to the node coordinates, and then substituted into the wireless signal propagation model to obtain the RSSI value of each node in the communication process. When constructing the dissimilarity matrix based on the RSSI values between nodes, the value ofa affects the final precision of the algorithm. Usually a takes values from 0.2 to 0.4, making the average positioning error small, so a is taken as 0.3 in this simulation experiment. The random variable when simulating the RSSI value between nodes is selected as a Gaussian random variable with a variance of 4 mean values of zero.


### 4.2. Analysis of Positioning Results

Figure2 shows the coordinates of each node and the actual coordinates of the nodes estimated by the RSSI-NMDS algorithm. Among them, the red circle represents the true coordinate position of each unknown node, the blue triangle represents the coordinates estimated by RSSI-NMDS, and the coordinate line represents the distance error between the estimated position of the algorithm and the real position. Table 1 shows the actual coordinates of 15 nodes and the estimated coordinates calculated by the algorithm and the distance error.Figure 2
Estimated position and actual position.Table 1
Position data of some nodes.
NodesActual coordinatesEstimated coordinatesError (m)N1(0.9, 9.0)(1.7, 8.9)0.81N2(1.1, 7.4)(1.7, 6.8)0.85N3(1.4, 4.2)(0.9, 3.6)0.78N4(1.1, 8.0)(4.9, 8.1)0.91N6(5.5, 6.6)(4.9, 5.9)0.92N7(3.0, 4.8)(3.7, 4.5)0.76N8(4.5, 3.1)(5.2, 2.9)0.94N9(3.8, 1.9)(4.2, 1.3)0.72N10(5.7, 8.5)(6.7, 9.1)1.17N11(7.2, 6.5)(6.8, 5.6)0.98N12(9.1, 6.8)(8.6, 6.0)0.94N13(7.2, 2.5)(8.1, 3.4)1.27N14(9.5, 2.5)(8.8, 3.1)0.92N15(7.2, 1.5)(6.2, 0.7)1.28It can be seen from Figure2 that the error lines of each node are different in length. This is because the fluctuation of the RSSI value is different, which results in different error sizes when performing position estimation. If the RSSI value fluctuates greatly, the estimated node coordinate error increases. It can be seen from Table 1 that the error of the indoor positioning of the unknown node by the RSSI-NMDS algorithm is relatively stable, and is basically maintained at about 1 m, and the minimum error can reach 0.7 m or less.


### 4.3. Comparison of Positioning Performance

The RSSI-NMDS algorithm proposed in this paper is compared with the traditional RSSI-based positioning algorithm. Figure3 shows the positioning results of 15 points. The circular and triangular identifiers are the same as in Figure 2. The black square indicates the node coordinates obtained by the RSSI ranging method, the solid line indicates the estimation error of the RSSI-NMDS algorithm, and the broken line indicates the estimation error of the RSSI ranging algorithm.Figure 3
Estimated position of the RSSI and RSSI-NMDS algorithms.It can be seen from Figure3 that the average error of the positioning result based on RSSI is significantly larger than that of the RSSI-NMDS algorithm. This is because the minimum error based on the RSSI ranging algorithm can only reach 2 m under relatively good conditions, and the error will increase significantly in a more complicated environment. In addition, after the actual distance between each communication node obtained in the RSSI ranging algorithm, an appropriate algorithm needs to be selected, and the position coordinates are estimated according to the distance. However, the positioning result is also different because the number of beacon nodes is different, and the position estimation algorithm is selected differently, thereby generating different positioning precisions. However, the positioning result of RSSI-NMDS algorithm is stable, and the positioning accuracy of the algorithm is not affected by the number of beacon nodes. The algorithm does not need to convert the RSSI value into distance and then coordinate estimation. It can directly obtain the node with the RSSI value. The relative position coordinates also avoid the effect of converting the RSSI value into a distance on the positioning accuracy.Then, the RSSI-NMDS algorithm proposed in this paper is compared with the algorithm in reference [13], the algorithm in reference [14], and the algorithm in reference [15]. Figure 4 shows the location error distribution of several algorithms. According to Figure 4, the positioning error of RSSI-NMDS algorithm proposed in this paper is smaller than that of other three algorithms. According to the actual coordinates of the reference node, the proposed RSSI-NMDS algorithm uses the plane four-parameter model to transform the coordinates and get the position of the node in the actual coordinate system. The simulation results show that the method has strong anti-RSSI interference ability and high positioning accuracy.Figure 4
Location error distribution of four algorithms.


## 4.1. Simulation Settings

Set up 45 unknown nodes and perform simulation experiments in the Microsoft Visual Studio 2010 programming environment. The distance between nodes is obtained according to the node coordinates, and then substituted into the wireless signal propagation model to obtain the RSSI value of each node in the communication process. When constructing the dissimilarity matrix based on the RSSI values between nodes, the value ofa affects the final precision of the algorithm. Usually a takes values from 0.2 to 0.4, making the average positioning error small, so a is taken as 0.3 in this simulation experiment. The random variable when simulating the RSSI value between nodes is selected as a Gaussian random variable with a variance of 4 mean values of zero.


## 4.2. Analysis of Positioning Results

Figure2 shows the coordinates of each node and the actual coordinates of the nodes estimated by the RSSI-NMDS algorithm. Among them, the red circle represents the true coordinate position of each unknown node, the blue triangle represents the coordinates estimated by RSSI-NMDS, and the coordinate line represents the distance error between the estimated position of the algorithm and the real position. Table 1 shows the actual coordinates of 15 nodes and the estimated coordinates calculated by the algorithm and the distance error.Figure 2
Estimated position and actual position.Table 1
Position data of some nodes.
NodesActual coordinatesEstimated coordinatesError (m)N1(0.9, 9.0)(1.7, 8.9)0.81N2(1.1, 7.4)(1.7, 6.8)0.85N3(1.4, 4.2)(0.9, 3.6)0.78N4(1.1, 8.0)(4.9, 8.1)0.91N6(5.5, 6.6)(4.9, 5.9)0.92N7(3.0, 4.8)(3.7, 4.5)0.76N8(4.5, 3.1)(5.2, 2.9)0.94N9(3.8, 1.9)(4.2, 1.3)0.72N10(5.7, 8.5)(6.7, 9.1)1.17N11(7.2, 6.5)(6.8, 5.6)0.98N12(9.1, 6.8)(8.6, 6.0)0.94N13(7.2, 2.5)(8.1, 3.4)1.27N14(9.5, 2.5)(8.8, 3.1)0.92N15(7.2, 1.5)(6.2, 0.7)1.28It can be seen from Figure2 that the error lines of each node are different in length. This is because the fluctuation of the RSSI value is different, which results in different error sizes when performing position estimation. If the RSSI value fluctuates greatly, the estimated node coordinate error increases. It can be seen from Table 1 that the error of the indoor positioning of the unknown node by the RSSI-NMDS algorithm is relatively stable, and is basically maintained at about 1 m, and the minimum error can reach 0.7 m or less.


## 4.3. Comparison of Positioning Performance

The RSSI-NMDS algorithm proposed in this paper is compared with the traditional RSSI-based positioning algorithm. Figure3 shows the positioning results of 15 points. The circular and triangular identifiers are the same as in Figure 2. The black square indicates the node coordinates obtained by the RSSI ranging method, the solid line indicates the estimation error of the RSSI-NMDS algorithm, and the broken line indicates the estimation error of the RSSI ranging algorithm.Figure 3
Estimated position of the RSSI and RSSI-NMDS algorithms.It can be seen from Figure3 that the average error of the positioning result based on RSSI is significantly larger than that of the RSSI-NMDS algorithm. This is because the minimum error based on the RSSI ranging algorithm can only reach 2 m under relatively good conditions, and the error will increase significantly in a more complicated environment. In addition, after the actual distance between each communication node obtained in the RSSI ranging algorithm, an appropriate algorithm needs to be selected, and the position coordinates are estimated according to the distance. However, the positioning result is also different because the number of beacon nodes is different, and the position estimation algorithm is selected differently, thereby generating different positioning precisions. However, the positioning result of RSSI-NMDS algorithm is stable, and the positioning accuracy of the algorithm is not affected by the number of beacon nodes. The algorithm does not need to convert the RSSI value into distance and then coordinate estimation. It can directly obtain the node with the RSSI value. The relative position coordinates also avoid the effect of converting the RSSI value into a distance on the positioning accuracy.Then, the RSSI-NMDS algorithm proposed in this paper is compared with the algorithm in reference [13], the algorithm in reference [14], and the algorithm in reference [15]. Figure 4 shows the location error distribution of several algorithms. According to Figure 4, the positioning error of RSSI-NMDS algorithm proposed in this paper is smaller than that of other three algorithms. According to the actual coordinates of the reference node, the proposed RSSI-NMDS algorithm uses the plane four-parameter model to transform the coordinates and get the position of the node in the actual coordinate system. The simulation results show that the method has strong anti-RSSI interference ability and high positioning accuracy.Figure 4
Location error distribution of four algorithms.


## 5. Conclusions

In order to solve the problem that the RSSI-based positioning algorithm is easily affected by the complex environment of the interior and the actual positioning accuracy is low, this paper proposes the RSSI-NMDS algorithm. The nonmetric multidimensional scaling method is applied, and the RSSI value is directly used for positioning, thereby avoiding the calculation amount and error of the ranging. The simulation shows that the proposed algorithm can resist the disturbance of RSSI value and has high positioning accuracy. In the future research, we can study from the following perspectives: in addition to the classical multidimensional scaling method, there are many other derived algorithms in the multidimensional scaling method. In the process of indoor positioning, we can compare it with other multidimensional scaling methods as much as possible, and select the best method for indoor positioning. In the process of wireless sensor network node localization, the use of more regular node area, so in the irregular node area positioning is worth further discussion. Although complex algorithms can improve the positioning accuracy of sensor network nodes, the energy consumption in wireless sensor networks is also a problem, so the balance between energy consumption and positioning accuracy in the network is worth further discussion and research.



---

*Source: 8830891-2020-11-12.xml*