An Area Optimization Based Cooperative Localization Algorithm with Node Selection

Ke Han,Chongyu Zhang,Huashuai Xing,Yunfei Xu

1 School of Electronic Engineering,Beijing University of Posts and Telecommunications,Beijing 100876,China

2 State Key Laboratory of Information Photonics and Optical Communications(Beijing University of Posts and Telecommunications),Beijing 100876,China

Abstract: In recent years, position information has become a key feature to drive location and context aware services in mobile communication.Researchers from all over the world have proposed many solutions for indoor positioning over the past several years.However, due to weak signals, multipath or non-lineof-sight signal propagation, accurately and efficiently localizing targets in harsh indoor environments remains a challenging problem.To improve the performance in harsh environment with insufficient anchors,cooperative localization has emerged.In this paper,a novel cooperative localization algorithm, named area optimization and node selection based sum-product algorithm over a wireless network(AN-SPAWN),is described and analyzed.To alleviate the high computational complexity and build optimized cooperative cluster, a node selection method is designed for the cooperative localization algorithm.Numerical experiment results indicate that our proposed algorithm has a higher accuracy and is less impacted by NLOS errors than other conventional cooperative localization algorithms in the harsh indoor environments.

Keywords: cooperative localization; node selection;PDR;indoor localization

I.INTRODUCTION

With the development of science and technology, position information is becoming more and more important in people’s daily life.The Global Positioning System (GPS), developed in 1973 by the U.S.Department of Defense, provides enough positioning accuracy in suitable environments like outdoors with clear view to the sky, meaning that there are line-of-sight signal propagation conditions between mobile terminals and the satellites.However,due to the indoor environments are much more complicated and the signal has more interference than outdoors, GPS cannot meet the need of high accurate indoor positioning.Therefore, developing accurate and reliable indoor positioning system has become a top priority.In recent years,researchers from all over the world have proposed many non-cooperative indoor location systems, such as Wi-Fi [1–3], Radio Frequency Identification (RFID) [4–6], Ultra-Wide Band (UWB) [7–10], Bluetooth [11–14], Ultrasound [15–17], etc.In[18], it considers a passive localization scenario relying on a single transmitter, several receivers, and multiple moving targets to be located.Existing approaches assume that the transmitter and receivers are synchronous or quasi-synchronous, which is not always realistic in practical scenarios.Hence, an asynchronous wireless network is considered,where different clock offsets are assumed at different receivers.In previous work[19],we proposed a Probabilistic Location Selection Algorithm (PPSA) with NLOS recognition for non-cooperative indoor positioning systems.Although it is indicated that PPSA has a higher accuracy and is less impacted by NLOS errors than other conventional non-cooperative methods, in harsh indoor environment with insufficient anchors, it is hard for GNSS to position accurately and continuously.Cooperative localization alleviates this problem by additionally using distance estimation between mobile terminals.In[20],it presents an implicit cooperative positioning(ICP)algorithm that exploits the Vehicle-to-Vehicle (V2V) connectivity in an innovative manner,avoiding the use of explicit V2V measurements such as ranging.In the ICP approach,vehicles jointly localize non-cooperative physical features(such as people,traffic lights, or inactive cars) in the surrounding areas, and use them as common noisy reference points to refine their location estimates.

With the development of 5G, technologies such as high bandwidth and dense antennas have effectively ameliorated the problems caused by the multipath effect.In [21], we determine the effects of multipath propagation on the localization performance using large-scale antenna arrays.Besides,a direct localization algorithm based on the coherent decoupled maximum likelihood criteria is developed for multipath environments.Besides,Device to Device(D2D)envisaged for a 5G communications system provides interesting prospects which are beneficial for cooperative positioning, which can increase the probability of the Line of Sight(LOS)signal received by the target and has been widely used for solving non-line-ofsight(NLOS)problems and improving positioning accuracy.

In the future 5G cellular network, with the wide application of D2D communication technology, each mobile device can perform additional distance measurement with its neighboring devices,and the neighboring mobile terminal can be used as an additional reference node for coordinated positioning during the positioning process.Through the exchange of positioning information with neighboring terminals, the positioning performance of the mobile terminal is greatly improved, and the problem of high signal transmission power and high node deployment density required by the conventional positioning method is well circumvented.The advantages of D2D communication can be mainly manifested in two aspects.First,it can be used to improve the original positioning technology and improve its positioning accuracy and reliability.In addition,when the number of signal reference nodes available for positioning in the environment is insufficient,D2D technology is still used.The positioning service can continue.It is conceivable that in the future 5G cellular network,with the application of the new co-location algorithm, future indoor positioning will obtain higher positioning accuracy and reliability without additional hardware overhead.

Recently,various solutions for cooperative localization are presented in the literature, proposing cooperative localization algorithms generally categorized as non-Bayesian algorithms and Bayesian algorithms.The basic theory of non-Bayesian localization algorithm is introduced in[22],and it mainly includes cooperative Least Squares (LS) and Maximum Likelihood (ML) localization.The basis of cooperative LS localization is introduced in [23–25], and weighted LS and regularized LS are introduced in [26] and[27].Based on cooperative LS, a cooperative ML algorithm was adopted in [28].Non-Bayesian cooperative localization ignores the estimation uncertainties and treats the state of mobile terminals as a nonrandom but unknown parameter, which would degrade the localization performance in cooperative localization [22].Thus, Bayesian estimators are the better choice in cooperative localization.In [29], the cooperative localization algorithm based on the extended Kalman filter (EKF) and the unscented Kalman filter (UKF) is proposed, but the mobile terminals’ position uncertainties are treated as range measurement errors, which causes the performance loss.In [30],an extended Kalman-based interacting multiple model(EK-IMM) smoother is proposed for mobile location estimation with the data fusion of the time of arrival(TOA) and the received signal strength (RSS) measurements in a rough wireless environment.In[31],a particle filter(PF)based cooperative localization algorithm,which can be used in nonlinear systems,is proposed for hybrid GNSS-terrestrial environment.Based on the sum-product algorithm(SPA)and factor graph(FG),a distributed cooperative positioning algorithm,named SPAWN, is introduced in [32].However, due to its high computational complexity,it is hard to implement in practice.A variational message passing(VMP) algorithm in [33] complements belief propagation methods for probabilistic inference on factor graphs, which allows simpler representation of messages and thus lower communication overhead between nodes.In [34], a message passing algorithm,named hybrid sum-product algorithm over a wireless network (H-SPAWN), is described and analyzed, and in order to reduce computational and communication overhead,a new parametric message representation is also introduced.The main novelty of H-SPAWN is the inclusion of GNSS information.

For the conventional cooperative positioning algorithm, although localization accuracy is much better than non-cooperative localization algorithm,each mobile terminal is localized with all neighboring terminals which are within its communication range without selection,therefore,it suffers from immense computational complexity and increasing network in large indoor environment.Therefore,how to balance the positioning accuracy and computational complex has become an important research topic.In[35],to improve the efficiency of cooperative localization, researchers propose a distributed scheduling algorithm with low complexity and overhead for dynamic cooperative localization networks,designed by determining the evolution of each terminal’s positioning error through cooperation and movement using Fisher information analysis, which improves the efficiency of localization by means of node selection and collision control.In [36], an effective censoring criterion based on the Cramer-Rao low bound(CRLB)is proposed for blocking selected broadcasts and discarding selected incoming information, which leads to an algorithm with reduced complexity and traffic,without significantly affecting accuracy and latency.In[37],the source transmit powers are considered as nuisance parameters and estimated along with the source locations.The corresponding Cramer-Rao lower bound (CRLB) of the problem is derived.To find the maximum likelihood(ML) estimator, it is necessary to solve a nonlinear and nonconvex optimization problem, which is computationally complex.To avoid the difficulty in solving the ML estimator, we derive a novel semidefinite programming(SDP)relaxation technique by converting the ML minimization problem into a convex problem which can be solved efficiently.The algorithm requires only an estimate of the path loss exponent(PLE).In[38],a cluster node selection strategy is proposed based on the CRLB for the cooperative localization algorithm in wireless network.Researchers first define clusters for every mobile terminal by setting the received signal strength(RSS)threshold to screen out some less useful nodes, which greatly saves the energy at a cost of only a slight degradation in accuracy.Then,to improve the localization accuracy,the cluster node selection strategy catches the nodes that make the biggest contribution to localization results while discarding the least ones based on the derived analogous-CRLB values.In [39], researchers design a node selection algorithm by setting a criterion to select the beacon nodes with highest utilities for the localization,and use a link condition indicator (LCI) to quantify the link quality of selected connections corresponding to the LOS/NLOS conditions.All these node selection strategies aim to alleviate the high computational and communicational consumption problem in cooperative localization while scheduling the positioning accuracy as the second phase.[40] explores various network operation strategies, which play an essential role in NLN as they determine the network lifetime and localization accuracy.Some important concepts such as cooperative operation, robustness guarantee,and distributed design in the development of the network operation strategies are also introduced.

This paper focuses on extreme indoor positioning environments, when the number of positioning signals received by the mobile terminal is insufficient,due to sparse positioning nodes and NLOS errors,resulting in the inability of the non-cooperative positioning algorithm to provide a high-precision positioning solution.In these extreme cases, we propose a region-optimization and node-preferred sum-product algorithm (AN-SPAWN) to solve the problem of colocation.The co-location scheme can be positioned using a 5G signal and a ranging signal such as a Bluetooth signal.In order to alleviate the high computational complexity and build optimized cooperative cluster,a node selection method is designed based on the basis of[38]and the NLOS identification method in our previous work [19] for the cooperative localization algorithm.Given the complexity, in the algorithm modeling in this paper,RSSI is used by default as the basis for locating the Bluetooth signal,and TOA is used as a basis for locating the 5G signal.Consider the synchronization required to use TOA, [41] develops a framework for the performance analysis of cooperative network synchronization.Compared with traditional layer-by-layer methods, cooperative network synchronization techniques lead to significant improvement in performance,efficiency,and robustness.In [42], it proposed new methods for network localization and synchronization (NLS) using full-duplex radios through only two frames of transmission.We develop distributed algorithms to estimate the arrival times of different components in the received signals.These arrival times are then used to determine the local network geometry and clock offsets.In order to reduce the complexity of the proposed cooperativelocation algorithm to meet the requirements of practical applications, a node optimization scheme based on Cramer–Rao lower bound and NLOS recognition is proposed to filter out the positioning signal that does not contribute much to positioning to construct an optimal co-located cluster without reducing the positioning accuracy of the cooperative-location algorithm.Through experiments and simulations, the AN-SPAWN cooperative-localization algorithm proposed in this chapter has better positioning performance than the traditional cooperative-localization algorithm in terms of positioning accuracy and NLOS error.The node optimization algorithm is used to filter the cooperative-located nodes that have little contribution to the positioning, and the optimal cooperativelocation cluster is constructed, which greatly reduces the number of cluster elements and the complexity of the co-location algorithm.The main contributions of this paper are given as follows:

• We propose a region-optimization and nodepreferred sum-product algorithm (AN-SPAWN)using a 5G signal and a ranging signal such as a Bluetooth signal to solve the problem of colocation.

• A node selection method is designed for the cooperative localization algorithm which can help reduce the complexity of the proposed cooperativelocation algorithm.

• Numerical experiment results indicate that our proposed algorithm has a higher accuracy and is less impacted by NLOS errors than other conventional cooperative localization algorithms such as SPAWN and H-SPAWN in the harsh indoor environments.

The rest of this paper is organized as follows.Section II introduces the system model of the proposed cooperative localization algorithm.Section III introduces the details of the proposed AN-SPAWN and the proposed cluster node selection algorithm.Section IV analyzes the results of the experimental implementation and simulation of the proposed AN-SPAWN.Finally, the conclusions of the study are presented in Section V.

II.SYSTEM MODEL OF COOPERATIVE LOCALIZATION

In this paper, as shown in Figure 1, the cooperative localization system involves Bluetooth low energy(BLE)beacons BT,base station supplements(BS)and mobile terminals(MT).In our system model,each mobile terminal makes measurement with its neighboring nodes and exchanges information with them through peer-to-peer communications.This direct information exchange on one hand enables the determination of distances in form of pseudo ranges between cooperative nodes.On the other hand, relevant information for cooperative positioning algorithms can be shared directly among the nodes.

Figure 1. The schematic drawing of system model.

2.1 Mathematical Formulation of System Model

In the considered cooperative positioning system,three types of measurements are performed:

1.Estimated distances from BLE beacons.In this case, mobile terminal m makes measurements with BLE beacons by received signal strength indicator(RSSI).

2.Estimated distances from base station supplements.In this case, mobile terminal m makes measurements with base station supplements by time of arrival(TOA).

3.Estimated distances from base station supplements.In this case, mobile terminal m makes measurements between cooperative terminals by TOA.

As shown in equation(5), the cooperative localization problem can be converted to the problem to determine the posterior distribution ofusing all the available measurements in the cluster after node selection at each time slot k:

In this paper, we make the following two assumptions:

Firstly,the movement of mobile terminal nodes can be modeled as a Markov process, and the mobile terminals are independent of each other and their motion states do not affect each other:

Secondly, Measurement likelihood depends only on the current state and can be split into three factors,since MT-BT,MT-BS and MT-MT measurements are independent:

2.2 Factor Graph of System Model

Based on equation(7),the joint Posterior distribution ofcan be expressed as:

For convenience,we convert equation(8)to the following form:

As this paper uses a Bayesian-based model of the localization algorithm, the global function is transformed into a factor graph in this paper.The socalled factor diagram, is a function of the factor decomposition of the representation of the diagram,generally containing two kinds of nodes, variable nodes and function nodes.We know that by factorization, a global function can be decomposed into the product of multiple local functions, and these local functions and the corresponding the variables can then be represented on the factor plots.Finally, the sum product algorithm is used to find the edge distribution of each corresponding variable.Figure 2 shows the factor graph of the cooperative positioning system,wherefrepresents mobility model of mobile terminal,ρrepresents the range likelihood between the mobile terminal and BLE beacons in clusterC,x1represents the first mobile terminal,drepresents the range likelihood between the mobile terminal and the base station supplements in clusterCandrrepresents the peer to peer range likelihood.The part in the dashed red boxed denotes the physical mobile terminal.The range messages in the red boxes are treated as the internal messages which are computed by a mobile terminal and factors connected to pairs of nodes imply packet exchanges.

Figure 2. The factor graph of system model.

III.AREA OPTIMIZATION BASED COOPERATIVE LOCALIZATION ALGORITHM WITH NODE SELECTION

The proposed cooperative localization algorithm is described in this section and it can be referred to in the system diagram shown in Figure 3.As shown in the figure,the cooperative localization algorithm consists of three main steps.Firstly, using the node selection strategy,we build an optimized cooperative cluster to decrease the computational complexity.Secondly,based on AN-SPAWN,the mobile terminals in the cluster after node selection update their positions.Thirdly,after the positions update of nodes in cluster,nodes of cluster update based on the catch rules and discard rules of node.The details of these three parts are described in the following.

Figure 3. The procedure of the proposed cooperative localization algorithm.

3.1 AN-SPAWN

In this section, the detailed process of AN-SPAWN is introduced.As shown in Figure 2, the message passing of AN-SPAWN can be divided into the following parts: mobility messages,messages from BLE factors, messages from factors of base station supplement, message from factors of cooperative nodes,message to factors of cooperative nodes and belief value.

The SPAWN algorithm has two parts: a prediction operation based on the MT movement and a correction operation based on mutual measurement between nodes.For the prediction operation,the mobile terminal calculates the output belief message according to the input belief message, the mobile terminal model and the local likelihood equation; for the correcting operation, the mobile terminal according to the relative metric between all mobile terminals and the input belief message To calculate the output belief message,which means that the corrective operation is to exchange information between the mobile terminals for the purpose of co-location.

1.Mobility messages: according to internal mobility modelfm, each node propagates the beliefs offrom timek −1 tok.Mobility messages can be interpreted as a prediction step in the cooperative localization process.

2.Messages from BLE factors:due to the connects between cooperative nodes and BLE beacons,messages can be simply described in the following function:

3.Messages from factors of base station supplements:same as equation (11), messages can be described in the following:

4.Message from factors of cooperative node: according to SPAWN algorithm, the messages can be expressed in equation(13)

wherehn,mrepresents the ranging likelihood,equation received by node m from node n.

5.Message to factors of cooperative nodes: according to the messages passing of SPAWN,the messages to factors of cooperative nodes are given by:

After introducing the message passing of ANSPAWN, the cooperative localization estimation will be introduced in the next part.The step of cooperative localization estimation is mainly based on the basis of PPSA proposed in our previous work,and we convert the cooperative localization to the problem of area optimization.In this paper,according to the message received by node,a cost function of position estimation is built,and the optimized position is solved by using adaptive moment estimation(Adam)[43].

First, we need to determine the area of optimization.In this paper, we use PDR to predict the position of mobile terminal in next time slot.Assuming that the velocityvand heading angleαmeasured by PDR obey the Gaussian distribution, as shown in Figure 4, the area of optimization is a part of the ringandα −3σα ≥˙α ≥α+3σα), whereσvandσαrepresent the standard deviation of velocityvand heading angleα, respectively.As equation (16) shown,represents the distance between the mobile terminal and the predicted position.As shown in equation(17),represents the angle between the connection of the current position,the predict position,and the north direction.are the coordinates of predicted position which are computed by PDR.

Figure 4. The schematic drawing of the optimization area.

After determining the optimization area, we build a cost function of cooperative localization estimation based on the mobility model and range likelihoods.Due tovandαobey the Gaussian distribution,the part of mobility model of the cost function is expressed in the following:

Therefore, the cost function is built in the following form:

Next,by using Adam,the optimal solution of the cost function is solved in the optimization area.The detail of the optimization step is introduced in Algorithm 1.

The position estimation algorithm used in this paper does not use the method of generating particles to optimize the selection.Instead, the position estimation problem is converted to the optimal solution problem by constructing the loss equation in the pre-selected region, and then through machine learning.Then use a more popular adaptive moment estimation algorithm(Adam)finds the optimal solution.

Algorithm 1. Adam.Initial parameter:Initial step size ϵ= 0.1; Exponential decay rate ρ1 = 0.9 and ρ2 = 0.999, constant δ= 10−8; Initial coordinates θ =■x0m,y0m■, where■x0m,y0m■is initialized as the coordinates of the mobile terminal updated by PDR in the current time;Initialize the first moment variable s=0,the second moment variable r=0;Initialized count variable τ =0.Output: the optimal solution of θ.START 1: While(stop condition not reached)do.2: Calculate the gradient g =∇θh(θ);3: Update count variable τ =τ +1;4: Update biased first moment estimate s = ρ1s+(1 −ρ1)g;5: Update biased second moment estimate r =ρ2r+(1 −ρ2)g;6: Modify the bias of the first moment ˆs= s 1−ρτ1;7: Modify the bias of the second moment ˆr = r 1−ρτ2;8: Calculate updated values ∆θ =−ϵ ˆs√ˆr+δ;9: Update parameter θ: θ =θ+∆θ;10: End While.END

Adam’s algorithm is suitable for the case where the objective function is unstable by calculating the firstorder moment estimation of the gradient of the loss function and the second-order moment estimation for different parameters adaptively changing the step size,and has the advantages of simple implementation,fast convergence and low required space complexity,so it is used in this paper.We perform convergence analysis of its Adam algorithm,settingf(θ)as a stochastic objective function and differentiable with respect to the parameterθ.Using the regret evaluation algorithm,then we have:

Thus the computational complexity of Adam’s algorithm isThe detailed procedure of AN-SPAWN is introduced in Algorithm 2.

3.2 CRLB and NLOS Identification Based Node Selection

Algorithm 2. AN-SPAWN.Input:Initial belief Output: updated belief START 1: While(stop condition not reached)do.2: for timestep=1 to K do 3: ∀m ∈M, according to equation 10, compute the mobility messages ηfm→x(k)m■x(k)m■;4: ∀m ∈ M, set the mobility messages as the initial messages to factors of cooperative nodes,ηxkm→hn,m =ηfm→x(k)m ;5: Collect the mobility message and range messages from BLE beacons, base station supplements and cooperative nodes, ρbt→m ∀bt ∈BT,m ∈M,dbs→m ∀bs ∈BS,m ∈M,rm→n∀m,n ∈M;6: According to equation 16 and 17, set the ptimization area;7: for iteration i=1 to I do 8: for nodes m ∈M in parallel do 9: Receive the messages form factors of cooperative,ηxkm→hn,m■x(k)m■;10: According to equation(11 - 13), compute the messages from BLE beacons ηρbt,m→x(k)m■x(k)m■,message from base station supplements ηdbs,m→x(k)m■x(k)m■and message from factors of cooperative nodes ηhn,m→x(k)m■x(k)m■;11: According to equations(18 - 23), build the cost function h(˙xm, ˙ym);12: Solve the optimal location of mobile terminal by Algorithm 1;13: According to equation 14, compute the messages to factors of cooperative nodes,ηxkm→hn,m;14: According to equation 15, update belief ˆρ(xkm)and propagate the belief;15: end for 16: end for 17: end for END

To cope with the high computational complexity of the cooperative localization algorithm in large indoor environment, a CRLB and NLOS Identification based Node Selection strategy is proposed in this section.According to the proposed node selection strategy,the nodes are selected by the contribution indicators of localization, and the optimal cooperative cluster is built for AN-SPAWN.When selecting the nodes in the cooperative cluster for mobile terminal, three aspects should be considered: the link quality indicator of neighboring nodes, the position uncertainty of neighboring nodes and the contribution indicator for cooperative localization.

First,the link quality indicator of neighboring nodes will be introduced in the following.In our previous work, we proposed a ranging signal and PDR based NLOS identification algorithm to identify the link condition between the BLE beacons and mobile terminals,and the NLOS identification indicator can dynamically estimate the link quality.Therefore, in this paper, we use the NLOS identification indicator as the link quality indicator of neighboring nodes.

Second,the concentration of the neighboring nodes’belief affects the cooperative localization accuracy of mobile terminal, significantly.The more concentration the belief of cooperative nodes has,the more beneficial it is for cooperative positioning.In the proposed cooperative localization system, since the locations of the BLE beacons and base station supplements are fixed and the locations of the mobile terminals have much more uncertainty, priority should be given to the nodes with defined locations under the same conditions.Equation(26)shows the uncertainty of the cooperative nodes.

The degree to which each cooperating node contributes to the current mobile terminal location will next be estimated by calculating the Carmelo lower bound of the location for each cooperating node.In[44]and[45],these two articles explore and establish a clearer framework and definition of the cooperative FIM and CRLB.Thus, we use the CRLB of each cooperative node for contribution screening.In a twodimensional positioning scenario,the Fisher information matrix F can be divided into the following forms:

whereFxxstands for fisher information.

Thus,the CRLB for mobile terminal j can be derived as

In the following, according to proposed cooperative localization system,we will use RSSI and TOA as the range signal to derive the positioning contribution indicator of the cooperative nodes, respectively.When using RSSI as the range signal, the path loss model can be expressed as

Thus, the RSSI-based range likelihood can be derived as

According to equation(30)and(31),the FIM elements can be expressed as

From equations (28) and (32) - (34), the CRLB for mobile terminaljbased on RSSI can be calculated as

wheredj⊥i,nis the shortest distance from nodejto the line segment connecting nodeiand noden.

When using TOA as the range signal, the range model can be expressed as

Thus,the TOA-based range likelihood can be derived as

According to equation (37), the FIM elements can be expressed as

From equation(28)and(38)-(40),the CRLB for mobile terminaljbased on TOA can be calculated as

Based on equations(35)and(41),in order to estimate the link quality,the positioning contribution indicator between nodejand nodeiis expressed in the following formula.

After introducing these three aspects of the link quality indicator of neighbouring nodes, the position uncertainty of neighbouring nodes and the contribution indicator for cooperative localization, the node selection indicator between nodeiand nodejis built in the following equation.

whereδj,irepresents the link quality indicator of neighbouring nodes, which is determined by the NLOS identification in our previous work [19];ciis the position uncertainty of neighbouring nodes;σj,i2represents the contribution indicator for cooperative localization.

3.3 The Update of Nodes in Optimal Cluster

After the nodes’positions updated in the optimal cluster, the update rules of the optimal cluster are shown in algorithm 3.

IV.RESULTS

In this section,the proposed AN-SPAWN is evaluated using numerical simulations.Firstly, to evaluate the performance of the AN-SPAWN,we deployed 14 BLE beacons (model: CC2640, price: ¥20) on the ceiling of the ninth floor of the Beijing University of Posts and Telecommunications (BUPT) Research Building and we use Huawei Mate 9 to collect data.Due to equipment limitations,direct ranging between mobile phones is not possible.Thus, in this experiment, the ranging information between mobile phones is generated by simulation.However, the experiment results will be not affected by this situation.

Algorithm 3. The Update of nodes in Optimal Cluster.Input: the old cluster Output: the updated cluster START 1: Update the positions of nodes in the cluster by AN-SPAWN;2: Sort the node selection indicators in the cluster from small to large,Qj,1 ≤Qj,2 ≤···≤Qj,m;3: if Qj,k ≥Qj,1&&RSSIk ≥RSSIth then 4: Catch the node k into the cluster;5: else if Qj,i is the minimum indicator in the cluster&& RSSIi ≤RSSIth&& the number of nodes in cluster ≥3 then 6: Discard node i from the cluster;7: else 8: Don’t update the nodes in the cluster;9: end if END

Table 1 shows the coordinates of the deployed BLE beacons.In order to simulate the cooperative localization environment,as shown in Figure 5,we set 5 routes of mobile terminals and the velocity of the mobile terminals is set to 1m/s.The terminals circulate between the start and end points of the route.The coordinates of the start and end points of the 5 routes and the mean error of PPSA,SPAWN,H-SPAWN and AN-SPAWN in every route are shown in the Table 2.A comparison of the AN-SPAWN with PPSA, SPAWN and H-SPAWN is shown in Figure 6.As Figure 6 shown,the proposed AN-SPAWN has better localization accuracy than H-SPAWN,SPAWN and PPSA.And the cooperative localization algorithms such as AN-SPAWN,H-SPAWN and SPAWN,have better performance than noncooperative localization algorithms,such as PPSA.However,because of the limitation of the experimental environment, only 5 mobile terminals can participate in the cooperative positioning process and we are unable to further evaluate the performance of the cooperative localization algorithms in this situation.Thus,in order to explore the performance of the proposed ANSPAWN in large indoor environment, we consider a 100 m × 100 m indoor environment, where 9 anchor nodes are systematically placed at the fixed locations,and 30 mobile terminals are deployed with random motion track.

Table 1. The coordinates of the deployed BLE beacons.

Table 2. The coordinates of the start and end points of the 5 routes and the mean errors of PPSA, SPAWN, H-SPAWN and AN-SPAWN of every route.

Figure 5. The schematic drawing of the experimental cooperative localization environment.

Figure 6. The cumulative distribution function (CDF) of AN-SPAWN, H-SPAWN, SPAWN and PPSA in the experimental cooperative localization environment.

To better simulate the cooperative positioning in a real environment,the range error can be expressed as

In order to control the probability of the range path in NLOS(NLOS rate),in the position update process of this simulation,we randomly select a certain number of paths in NLOS and add the NLOS impact factor into the range error.The heading angle of every mobile terminal obeys a random distribution of 0 to 2πand adds a Gaussian error with a mean of 0 and a standard deviation ofσα.The speed of mobile terminal is uniformly set to 2.5m/s and adds a Gaussian error which the mean value is 0 and the standard deviation isσv.Table 3 shows the values of the parameters which are used in the simulation.The cooperative localization results,in the environment which simulate a large indoor scene,are shown in Figure 7-10,where the red lines represent the localization error;the black asterisks represent the real positions of mobile terminals;the black diamonds represent the locations positioning by PPSA;the pink triangles represent the locations positioning by SPAWN; the green circles represent the locations positioning by H-SPAWN;the blue squares represent the locations positioning by the proposed AN-SPAWN.

Table 3. The parameter values for evaluating the performance of our proposed AN-SPAWN.

Figure 7. The cooperative localization results of PPSA in the environment which simulate a large indoor scene.

Figure 8. The cooperative localization results of SPAWN in the environment which simulate a large indoor scene.

Figure 9. The cooperative localization results of H-SPAWN in the environment which simulate a large indoor scene.

Figure 10. The cooperative localization results of ANSPAWN in the environment which simulate a large indoor scene.

Next, the proposed AN-SPAWN is analyzed and compared the cooperative localization performance with SPAWN and H-SPAWN.Figures 11 - 14 indicate the results of the simulation by increasing the NLOS probability from 0 to 1 to show the impact of the NLOS rate on the cooperative localization accuracy.The NLOS rate is defined as follows:pathLOSandpathNLOSdenote the signal propagation conditions between the mobile terminal and the localization node as LOS and NLOS,respectively.Therefore, the NLOS rate can be controlled by artificially changing the path propagation state.We can conclude that the positioning errors of the three cooperative localization algorithms have a similar characteristic: it tends to decrease with the increase in the NLOS rate.However,it is obvious that the proposed AN-SPAWN has the best localization accuracy in the environment with the same NLOS rate.Meanwhile, it can be observed that the NLOS error has a significant impact on the cooperative localization performance of both SPAWN and H-SPAWN.However,the proposed ANSPAWN is less affected by the NLOS error.Based on the analysis of these results, the performance of the three cooperative positioning algorithms from best to worst are the proposed AN-SPAWN, H-SPAWN,and SPAWN.Therefore,we can conclude that the proposed AN-SPAWN can mitigate the impact of NLOS error effectively.This is because when the NLOS rate is less than 1, node selection scheme is started to filter the nodes which have less contribution to cooperative position by the node selection indicator in equation (41).Thus, our proposed AN-SPAWN can migrate the impact of NLOS error.In Figure 15, when the NLOS rate is set to 0.25, the localization performance in cooperative localization with AN-SPAWN,H-SPAWN and SPAWN is further evaluated by the convergence speed,which is indicated by the required iterations.Figure 15 illustrates the localization errors versus the convergence speed for the three cooperative localization algorithms.It is observed that the proposed AN-SPAWN converges are faster than HSPAWN and SPAWN with the required iterations of 5 versus 8 and 10 as shown in Figure 15.In the environment which simulates a large indoor scene,using the proposed node selection scheme, the cooperative localization estimation process of our proposed AN-SPAWN doesn’t need to communicate all the 30 mobile terminals and 9 anchors,and selects the nodes that are more useful for the localization to build an optimal cooperative cluster.Figure 16 shows the average number of every node in its cooperative cluster and the average number of nodes in the cluster is 7.1047.

Figure 11. The CDF of AN-SPAWN in the NLOS rate of 0,0.25,0.5,0.75,and 1.

Figure 12. The CDF of H-SPAWN in the NLOS rate of 0,0.25,0.5,0.75,and 1.

Figure 13. The CDF of SPAWN in the NLOS rate of 0,0.25,0.5,0.75,and 1.

Figure 14. The NLOS rate versus the mean RMSE.

Figure 15. The number of iterations versus the mean RMSE.

Figure 16. The average number of every node in its cooperative cluster.

V.CONCLUSIONS AND FUTURE WORK

In this paper, to improve the performance in harsh environment with insufficient anchors, we proposed an area optimization and node selection based sumproduct algorithm over a wireless network (ANSPAWN) for cooperative localization.To alleviate the high computational complexity and build an optimized cooperative cluster, a node selection method is designed for the cooperative localization algorithm.This study assessed the developed cooperative localization algorithm in experimental indoor environment of BUPT research building and a simulation environment to simulate the large indoor scene.The PPSA,SPAWN and H-SPAWN were subjected to the same testbeds to serve as a benchmark for comparison with the proposed AN-SPAWN.In the simulation environment, to demonstrate the reliability and robustness of AN-SPAWN, the validation tests included different NLOS rates of signal propagation by varying the quality of the signal propagation condition.Through comparison with SPAWN and H-SPAWN,we verified that the proposed AN-SPAWN outperforms the other cooperative localization algorithms in terms of the localization accuracy and that it can better overcome the negative impact of NLOS errors.By using node selection scheme, The AN-SPAWN obtains the ability to select the nodes that are more useful for the localization to build an optimal cooperative cluster and instead of communicating with all 30 mobile terminals and 9 anchors, the average number of nodes in cooperative cluster is 7.1047.

ACKNOWLEDGEMENT

This work was financially supported by the NationalKey Research&Development Program of China under Grant No.2020YFC1511702 and Open Fund of IPOC(BUPT)No.IPOC2021ZT20.