This is the accepted version of the journal article: Albaidhani, Abbas; Morell Pérez, Antoni; López Vicario, José. «Anchor selection for UWB indoor positioning». Transactions on Emerging Telecommunications Technologies, Vol. 30, Issue 6 (June 2019), art. e3598. DOI 10.1002/ett.3598 This version is available at https://ddd.uab.cat/record/273830 under the terms of the license Anchor selection for UWB positioning Abbas Albaidhani, Antoni Morell, Jose Lopez Vicario Telecommunications and Systems Engineering Department Universitat Autònoma de Barcelona, Bellaterra 08193 - Barcelona, Spain abbassabbar.ghali@e-campus.uab.cat, {antoni.morell,jose.vicario}@uab.cat Abstract—On the positioning accuracy, the geometric distri- In this approach, we provide an IP system suitable for bution of anchor nodes in wireless sensor networks (WSN) different situations including emergency situations. Indoor has notable impacts. To select the optimum node combination, environments could be distributed as structured or known, conventional methods that depend on geometric dilution of precision (GDOP) demand to spend time on calculating every semi-structured and unstructured or unknown depending on possible combination of nodes. In military urban and emergency the control that the IPs possesses over them [3], [4]. response operations, the time is a crucial issue, and a precise Localization in radio frequency (RF) communication network positioning system with a clear indoor covering is a highly could be divided into range-free and range-based techniques prerequisite tool to enhance the safety. It should be seamless, [5]. The most common range-free method is a radio signal low, frugal, power efficacious, low cost and supply less meter- level accuracy. In this paper, the main goal is to reduce the strength indication (RSSI). Theoretical or experimental model anchors installation time and to obtain a precise localization of the signal propagation in this method is translated into system. To obtain this goal, a novel algorithm to build an accurate position or distance estimations [6], [7]. The range based indoor positioning (IP) system is created using a mean square methods are according to distances measurements between error (MSE) of an estimated position of a mobile station located transceivers utilizing the time of arrival (TOA), time difference by different groups of installed anchor nodes online using least square (LS) method then selecting the group having less MSE of arrival (TDOA) or tow way ranging time of flight (TWR- value (anchor selection ”AS” method) to relocate the mobile TOF) [8]. station using a weighted least square (WLS) method. The results Of the aforementioned forms of RF technology, ultra wide were highly acceptable for indoor localization because the module band (UWB) signal is considered one of the most precise attained an MSE localization accuracy in a hard non-line of sight approaches because it can provide location estimates with (NLOS) environment below 0.5 m2 also the time of installing the anchor nodes will be reduced. This paper includes the description centimeter-level accuracy [9]. It is widely used for ranging of the algorithm and the results of the conducted experiments. estimation and creating an indoor positioning system. In the indoor environment, the propagation channels could be divided Keywords- WSN, Indoor Positioning Systems, UWB into a line of sight (LOS) and non line of sight (NLOS). technology. Also, the NLOS could be divided into soft NLOS and hard NLOS depending on the attenuation of the radio signal. In the UWB signals, it is possible to transmit and detect very short I. I NTRODUCTION pulses permitting for high accuracy of positioning because In Indoor Positioning Systems (IPs), obtaining a sufficient of the accurate calculation of signal delays. In an indoor precisely indoor positioning method, robust with the changes environment, the propagation path length is not always a in the environmental conditions, adequate for expanded areas, good indicator of the ranging between a sender and receiver. and simple as possible is a difficult task. Several methods such Thus, these systems are predominately bounded to the LOS as fingerprinting technique and geometric approaches (such as conditions [10]. It precisely measures the distance in the LOS trilateration and triangulation) utilizing distinct technologies channel but suffers in the NLOS channel, and the error in have been presented. Based on these methods, different IPs are distance measurements is significantly high [11] [12] which on the market to present indoor location-based services (ILBS) impacts the positioning accuracy. [1]. However, none of these commercial IPs is adequate to In this paper, we address the UWB indoor positioning in overcome the problem of emergency responders location [2], different environments and scenarios such as an emergency as all solutions require in advance measurements, calibration, scenario using the AS algorithm. The contributions are i) configuration, and deployment. obtaining of the MSE of the IPs when linearized LS is In emergency scenarios, we don’t have enough flexibility and adopted as the trilateration solution; ii) development of an time to install all anchor nodes in a proper situation that anchor selection (AS) strategy to mitigate the positioning error may help to obtain an appropriate accuracy for locating a induced by the least accurate distance measurements and iii) mobile station, but command centers require observing their for using the MSE to evaluate the positioning accuracy of operational forces, and rescuers demand to detect potential the two anchor group, addition of a virtual node to employ victims to perform a proper care. The most common users the linearized LS in the case where ambiguity is resolved by for these situations are the firefighters, police, military, and additional information. civilians. Our approach helps to avoid installing all anchors in a proper way and just distribute them randomly to reduce the instal- estimation. With a limited overhead in term of computational lation time, and the cost of using a high number of sensors cost, these methods present suitable positioning results and and could be used to precisely locate a mobile station with an obtain a greater robustness to an inaccuracy in channel error ranges from 10 cm to 50 cm in any environments. It is modeling. The average errors of the positioning systems implemented experimentally using the UWB technology. created by the proposed algorithms are 3.69 m and 2.56 m The positioning system survey related to this work is presented [19]. in Section II. In Section III, the system model is presented. MSE computation in linearized LS is presented in section IV. In 2017, the authors of [33] presented a modified least Section V presents AS algorithm. Experimental and evaluation squares iterated (MLSI) to minimize errors and optimize the activities are presented in section VI. Section VII presents relationship of anchor nodes and a mobile station. The MLSI results and discussion related to the experimental activities. implements the iteration method to reduce the error of the Finally, section VIII offers a conclusion. conventional LS method. That means the MLSI can effectively improve position error rate. When using four anchor nodes II. S URVEY OF INDOOR POSITIONING SYSTEMS system, the average error is 0.8 m. Moreover, increase anchor In this section, we present some related works to the nodes from four to five; the error value is convergence to anchor selection for UWB indoor positioning. 0.48 m. The idea of this approach is to modify the vector For the recent decades, the problem of range-based localization of distance measurements used in the main equation of the system has been studied, especially in radar and sonar field conventional linearized LS method by involving the average where range measurements are normally acquired from the distance error. Also, the positioning accuracy might be in- time of flight (TOF) or the time of difference of arrival creased while implementing more number of the installed (TDOA) measurements. Different IPs using UWB technique anchor nods. are created to locate a mobile station in indoor environments under normal or emergency situation such as in [13, 14, 16, III. S YSTEM MODEL 17, 28], and we state some of them below. In this work, some problems of UWB technology in indoor In [15], Mathias Pelka presented an iterative approach for environments aforementioned in the introduction section likely anchors configuration of a positioning system. He used an solved. We create an IP system using MSE to online evaluate anchor node randomly as the origin of the coordinate system. the accuracy of the positioning system of a mobile station For the second anchor position, they presumed that the first created using different anchor groups (n̂ groups) installed in two anchors are along one axis and the distance between both the environment then selecting the anchor group having better anchors is measured. An initial guess of the remaining anchor positioning accuracy to relocate the mobile station. positions is generated according to a uniform distribution. The proposed system consists of a number of wireless sensors The algorithm iterates for all anchor nodes in the positioning created using UWB technology. It consists of n anchor nodes system. Then, the MSE is computed between the measured installed randomly and one mobile station moving around. and Euclidean distance of the anchor nodes. The MSE is Figure 1 depicts the proposed model when n anchor nodes compared with a threshold which depends on the standard in the network and only n̂ < n optimum anchor node are deviation of the distance estimation. If the MSE passes the selected to compute the mobile position (see section V for MSE threshold, the algorithm dismisses the solution and starts details). To fit with different situations and one of them is the process again. The positioning problem with a Taylor the emergency situation, we took into consideration some expansion combined with a Monte Carlo approach is solved constraints may exist in such scenarios, such as the anchor to avoid ambiguity flip. They obtained a mean positioning nodes were randomly distributed to reduce the installation error of 0.62 m. time. Also, the installation area should be narrow and not The authors of [18], presented a GDOP assisted nodes very suitable to distribute the anchor nodes in a proper way, selection (GANS) algorithm for calculating the GDOP value and the mobile station has been restricted to move through a of the current geometric distribution. As the evaluation harsh environment. Then, we use the linearized LS to locate criteria, sensor nodes contribution to the total GDOP value is the mobile station and evaluate the positioning accuracy by adopted. When The contribution value of the node is higher implementing the proposed MSE, and a proposed algorithm than the threshold, it will be selected. The anchor nodes named AS is used to select the anchor group providing the subset, which shares in the localization, will be real-time best positioning accuracy and relocate the mobile with the determined. By simulation, This approach shows that the selected group using the WLS method. The linearized LS GANS algorithm can minimize the energy consumption of and WLS are implemented to avoid the initial guess point the system while the accuracy of the positioning system has and the iteration that should be used in the non-linear LS no clear loss, and the computational complexity is decreased. method, so the computation time of the mobile location is In 2011, Paula Tarrio presented two weighted least squares reduced. Also, the proposed MSE will be computed with less methods based on the standard hyperbolic, and circular complexity in the linearized LS. Estimating a positioning node positioning algorithms that consider the accuracy of the in two-dimensions acquires range information from at least different measurements to obtain a better positioning three anchors. In this model and for simplicity, we provide A. L S linearization To linearize the LS solution, one of the equations in the group of the equations in Eq.1 is selected as a reference equation and subtract it from all other equations in the system. For simplicity, we state A1 as a reference node having x1 = y1 = 0, so r12 = x2 + y 2 (4) Then the linearization problem will be r12 − ri2 = x2 + y 2 − ((xi − x)2 + (yi − y)2 ) (5) Where, i = 1..........n By modifying Eq.5, we obtain Eq.6 as written below x2i + yi2 + r12 − ri2 = 2xxi + 2yyi (6) Fig. 1. The system model that has n number of anchor nodes and one mobile station(should be in any direction in the plane). and distance measurements have different errors. The yellow line denotes the n̂ = 2, 3, ... < n selected Then converting Eq.6 to matrix notation, we can obtain anchor nodes.   2x2 2y2  2x3 2y3  an analysis of two dimensional localization. Let h = [x; y] A= .   ..  presents the mobile station position in Cartesian coordinates  .. .  x and y. Also, Ai = [xi ; yi ] denotes Anchor nodes positions. 2xn 2yn i = 1, ....n̂ denotes the index of the anchor node and n̂ denotes the number of the entire optimum anchor nodes. Then, we can  b  x22 + y22 + r12 − r22  2 compute the Euclidean (real) distance (r) between h and A in  x23 + y32 + r12 − r32   b  a generic way.   3  b= =  ..  . .  . .  ri2 = ||xi − x||2 = (xi − x)2 + (yi − y)2 (1) x2n + yn2 + r12 − rn2 bn A localization algorithm should be applied once the distances where, r1 denotes the real distance between the reference node (r) to different anchor nodes are measured to calculate the and mobile station and ri denotes the distance between mobile position of the mobile node. The simplest and most common station and all nodes except the reference. Finally, the mobile positioning algorithm that has been used for RSS-based lo- station coordinates h will be computed as shown in Eq.7 calization is the hyperbolic positioning algorithm [20, 21]. As   we explained above, r denotes the real distance and let denote x h= = (AT A)−1 AT b (7) the measured distance extracted from the sensor as r̂ then the y error is computed as As mentioned in Eq.7, at least three distance measurements n X will be needed to obtain a solution using the LS method. = (ri − rˆi ) (2) However, it is not always installing more anchor nodes in the i=1 network means that we obtain a good IP system. In some cases, we could have a better positioning system with only The estimated position can be calculated iteratively by imple- two anchor nodes as shown in figure 2. So, the solution menting a straight gradient method for an example. presented in this work is to involve virtual anchor nodes in " # " # " ∂ # the LS method instead of the worst measured distance. With x̂ x̂ ∂x ĥ = = −α ∂ (3) two anchor nodes, only two equations are available to guess ŷ ŷ ∂y the x and y coordinates. However, two equations provide k+1 k x=x̂k ,y=ŷk two possible solutions and, if we know how to resolve the where α is a scalar selected to minimize . Also, x̂ and ŷ ambiguity by some extra information such as to locate the the estimated coordinates of the MS. In this method, an initial mobile position using three anchor nodes then replacing the value of the position estimation is needed. To convert this node that provides worst distance estimation by the virtual non linear into a linear problem, the hyperbolic positioning distance so the LS could be used for unifying the MSE method algorithm is used by implementing least square method [19] for group two or more anchor nodes. as we presented in the next subsection. The next subsection explains the virtual distance. Fig. 3. Virtual node and its distance to the mobile station. aforementioned in the anchor selection section. The MSE could be written in a generic way as shown in Eq.9 ( ) Fig. 2. Two and three anchor nodes having different distance error to the 2 n o n o mobile station when the localization system with two anchor nodes provides M SE = E ĥ − h = E ĥT ĥ − 2E ĥT h + hT h better accuracy. (9) where h and ĥ denote the real and estimated position of the B. Virtual distance MS respectively. Also, Eq.7 in section III can be split into two parts as shown below: As stated before, The two anchor nodes system could be in The first part of Eq.7 ((AT A)−1 ) is only deterministic data (the some states provide better positioning accuracy. Such a system coordinates of the anchor nodes) and therefore, implementing also will be involved in the MSE and the AS algorithms using matrix operation to it, we obtain a new matrix of 2 by 2 as the virtual node. Thus, we can unify the proposed MSE to shown below when we denoted it as V . extend the selection of anchor node by also selecting two   anchor nodes system. Figure. 3 depicts the creation of the v11 v12 V = virtual distance dv and all variables mentioned in Eq.8. The v21 v22 Virtual node could be fixed in any place in the space. Then, it is computed using the triangle rules as shown below. where, (y22 + y32 + ...yn2 ) q dv = d21 + d2ava1 − 2d1 dava1 cos(θ) (8) v11 = 0.25 (y22 + y32 + ...yn2 )(x22 + x23 + ...x2n ) − (x2 y2 + x3 y3 + ...xn yn )2 Where, θ could be β − A1 or β + A1 according to the mobile station position located previously. , (x2 y2 + x3 y3 + ...xn yn ) d2 + d2ava1 − d2ava2 v12 = −0.25 β = cos− 1( a2a1 ) (y22 + y32 + ...yn2 )(x22 + x23 + ...x2n ) − (x2 y2 + x3 y3 + ...xn yn )2 2da2a1 dava1 , and d2a2a1 + d22 − d21 A1 = cos− 1( ) (x22 + x23 + ...x2n ) 2da2a1 dava1 v22 = 0.25 (y22 + y32 + ...yn2 )(x22 + x23 + ...x2n ) − (x2 y2 + x3 y3 + ...xn yn )2 The next section presents the MSE derivation. IV. MSE COMPUTATION IN LINEARIZED LS and v21 = v12 Also implementing matrix operation to the second part of Eq.7 In this section, the MSE is achieved by the linearized LS (AT b) will be solution explained in section III when the true value of the X n  mobile position is unknown.  2xi bi In this work, the solution of LS method is considered for the AT b =  X  i=2 n   (10) best linear unbiased estimator (BLUE) when n anchor nodes   2yi bi distributed in an environment to locate a mobile station as i=2 where, bi = x2i + yi2 + r12 − ri2 using the RSL. In this work, we consider a real environment Then, the Eq.7 in section III is rearranged to be with 6 UWB sensors covering an area of 9 m2 : one sensor  X n Xn  as a tag and the remaining five sensors installed as anchor nodes. According to our experience, positioning accuracy is v11 2xi bi + v12 2yi bi i=2 i=2 not significantly improved when a large number of anchor h= X (11)   n n nodes is available and usually 4 to 6 anchor nodes provides X    v21 2xi bi + v22 2yi bi a good compromise. Then, the 5 nodes are clustered into i=2 i=2 different groups according to the combination algorithm. So To start solving Eq.9, we solve each part of it individually the total number of groups = n̂2 + n̂3 + .... + n̂n̂   then combine them. First and for simplicity, let us denote the where n and n̂ are the total number of the anchor nodes first, second n ,oand third part of it as: installed in the entire network and the total number of selected p1 = E ĥT ĥ anchors (in this work n̂ = 5) installed to build the positioning n o system. p2 = E ĥT h The RSL is extracted from the UWB device (DW 1000 - EVK 1000) used in this work. It indicates the level of the received p3 = hT h signal power provided by an anchor node [30]. It is chosen in So, Eq 9. could be rewritten as this work as criteria to select the optimum anchor nodes (n̂) selected for the combination process. The total number of the M SE = p1 − 2p2 + p3 (12) anchor nodes used in this work (5 anchor nodes) is not large, For simplicity, we move all mathematical steps of the proposed and it is not so important, and therefore it does not depend on MSE to appendix 1. how large the network (n anchor nodes). Then, The performance in terms of MSE achieved is Also, every group should have a reference node. We locate  n X n  the mobile station using the conventional LS method then 2 o evaluate the positioning accuracy of each group of anchor nods  E 2xi b̄i  using the derived MSE and select the group having less MSE  2 2 T  i=2  v11 + v21   n X n 2 o   and removing all other anchor groups from the positioning 2 2   E 2y b̄ M SE =  v12 + v22  i i   system to relocate the mobile station using WLS algorithm. 2v11 v12 + 2v21 v22   nX n i=2 n  The algorithm 1 depicts the steps of the proposed algorithm. X o  E 2xi b̄i 2yi b̄i  The next section provides the experimental results of the LS, i=2 i=2 WLS, and MLSI (before anchor selection), and AS localization (13) algorithms. Proof: see the Appendix. VI. EXPERIMENTAL AND EVALUATION To implement the proposed MSE method, we should clarify ACTIVITIES that the only input variable of the MSE function is the real In this section, we provide experimental results obtained distance (r). But, in a real experiment when we don’t have with a commercial UWB device (DW 1000-EVK 1000). The it, we implement proper NLOS identification and mitigation DW 1000 is a fully integrated low-power, multichannel single- method created by [11]. In addition to the aforementioned chip CMOS radio transceiver that meets the IEEE 802.15.4- method of NLOS identification, we created a database as 2011 ultra-wideband (UWB) standard [30]. shown in table I to estimate the average distance error in hard Before starting with the experimental activities, we start with and soft NLOS and LOS propagation channels to enhance the the evaluation process of the derived MSE and an overview of measured distance as shown in Eq.14 below the WLS and MLSI methods as explained in the next items. ŕ = r̂ − ε(e) ' r (14) A. Evaluation of the derived MSE and an overview of WLS where, ŕ, r̂, ε(e), and r denote the approximated real distance, and MLSI measured distance, the average distance error, and the real distance respectively. So, the approximated real distance (ŕ) is The items below explains the process of the evaluation used in the MSE method instead of the real distance (r) and method used for evaluating the derived MSE and provides an also used in all positioning methods used in this work. overview of the WLS and MSLI methods used to be compared with the proposed IP system (AS). V. A NCHOR SELECTION (AS) • Evaluation of the derived MSE The proposed IP system which is an online selection of a After computing the MSE, it is compared with MSE group of two anchor nodes or more up to n̂ anchor nodes Matlab function using a rational error as shown in Eq.15 using MSE evaluation method is explained below. to ensure the accuracy of the mathematical derivation. For a generic scenario of IP system dealing with UWB signal, Figures 4 and 5 show the value of the derived MSE com- we may install n nodes in the WSN and we could select n̂ < n pared to MSE Matlab function of a mobile positioning Algorithm 1 Anchor Selection (AS) DW 1000 (EVK 1000) device provides 8 distance 1: procedure A NCHOR GROUP . Create different anchor measurements per second and therefore, we calculate node groups and update the variance every one second and calculate 2: n̂ ← n . The total anchor nodes the matrix of it (W) which is the covariance matrix of 3: for i = 2 to n̂ do vector b̂ as aforementioned below, then using the inverse Anchor group= n̂i  4: Pn̂ n̂ of it in the final equation of the WLS as shown in Eq.16. 5: m= i i . the total anchor groups 6: end for W = 7: end procedure  var(r´1 2 ) + var(r´2 2 ) var(r´1 2 )... var(r´1 2 )  1: procedure LS . Locate the mobile station  var(r´1 2 ) var(r´1 2 ) + var(r´3 2 )... var(r´1 2 )    .. ĥ = (AT A)−1 AT b̂    .  2 2 2 2 2: end procedure var(r´1 ) var(r´1 )... var(r´1 ) + var(r´n ) 1: procedure MSE . Compute MSE for each group where var(rˆ1 2 ) denotes the variance of a squared 2: for i = 1 to m do estimated distance between the reference node and mobile station, and var(rˆi 2 ) denotes variance of a ( ) 2 M SE = E ˆ − h(i) h(i) squared estimated distance between all other nodes and the mobile station. 3: end for 4: end procedure x22 + y22 + r´1 2 − r´2 2   1: procedure AS . Select the group having minimum MSE  x23 + y32 + r´1 2 − r´3 2  2: for i = 1 to m do b̂ =    ( ) ..   .  M SE = min M SE(i) x2n + yn2 + r´1 2 − r´n 2 . 3: end for   4: end procedure x̂ ĥ = = (AT W −1 A)−1 AT W −1 b̂ (16) ŷ 1: procedure WLS . Compute the variance of the estimated distance Presuming that the distance measurements bˆi to different . Relocate the Mobile station nodes are independent and xi and yi are constant. ĥ = (AT W −1 A)−1 AT W −1 b̂ • Modified least square iteration (MLSI) method. 2: end procedure The MLSI method has the same mathematical expression of the conventional LS (Eq.7) with modifying the distance vector (b̂) by involving the average distance error to it for 14 different mobile positions and the rational error between them respectively. M SEdir − M SE E= 100% (15) M SE where, E, M SEdir , and M SE denote the rational error, proposed MSE, and MSE of matlab function respectively. • Weighted least square (WLS). To validate the anchor selection system model, it is compared to the conventional LS and also, to the WLS and MLSI algorithms created by [19] and [33] respectively. A short overview of the WLS and MLSI algorithms is presented below. The liner equation in Eq.7 could be solved implementing a weighted least-square estimator as shown in Eq.16 below. The weights implemented in the WLS algorithm is adjusted taking into account the inverse of the variance of the corresponding distance measurements [19]. The Fig. 4. Values of the proposed MSE and matlab functions. as shown below. where Ai denotes the anchor node in the network. The esti- First, let ε(e1 ) and ε(ei ) denote the average distance mated distances between anchor nodes and the mobile station error between the MS and the reference node and the are extracted from the EVK 1000 device. To build the proposed average distance error between the MS and the rest of IP system by implementing the AS method, we implemented the entire anchor nodes respectively where i = 2, ....n = a proper NLOS identification method [11] and created table I Then: to estimate the average distance bias. Then, Eq.14 is used to obtain the approximated real distance for the proposed MSE to b̂i = x2i + yi2 + r´1 2 − r´i 2 + ε(e1 ) − ε(ei ) evaluate the positioning accuracy of different groups of anchor nodes (including the virtual nodes group), and select the group Or having the less MSE, then relocated the mobile station with x22 + y22 + r´1 2 − r´2 2 + ε(e1 ) − ε(e2 )   the selected group using the WLS method. In this work, the  x23 + y32 + r´1 2 − r´3 2 + ε(e1 ) − ε(e3 )  distance measurement is extracted from the EVK 1000. It is a b̂ =    ..  transceiver sensor uses two-way time of flight to compute the  .  2 2 2 2 distance between two transceivers, and it is a Bias estimator xn + yn + r´1 − r´n + ε(e1 ) − ε(en ) in a LOS environment according to [25, 26, 27] so we should . overcome this issue to cope with the proposed linear MSE B. Experimental activities method. So, we applied an algorithm presented by [29] to modify the EVK 1000 having the BLUE specifications in a In this part of the work, different scenarios are created LOS environment. This algorithm is to place two EVKs 1000 to examine the proposed method used for a moving target with 8 m apart in between inside a LOS environment and take in different directions and distances to the installed anchor at least 400 times of distance measurements then compute nodes. We randomly installed the anchor nodes as shown in the average error between the true and estimated values then figure 7 inside a narrow squared area of 9 m side within the apply Eq.17 below to obtain a new estimated distance by total moving area of 16 m width and 25 m length. Figure reprogramming EVK 1000, and Table I shows that modified 8 presents scenario 1 for a trajectory of the mobile station EVK 1000 is a BLUE estimator. created using the AS, MLSI, and WLS algorithms. Figure 9 presents scenario 2 for a different trajectory created by the AS, eav = dreal − dest WLS, and LS. The AS algorithm with a suitable anchor group for every point in the trajectory. The MLSI with the four and dnew = dest + eav (17) five anchor nodes group. The WLS and LS algorithms with the group of five anchor nodes for the entire trajectory. The where, the dreal , dnew , dest , eav , are the real distance, new coordinates of the anchor nodes in the two different scenarios estimated distance, average of old estimated distance, and the as follows: average of the computed error experimentally for 8 m distance. Scenario 1 :A1 = (0; 0), A2 = (1;7.8), A3 = (2;7.8), A4 = (2.6; The transceivers were randomly distributed in the environment 1.4), and A5 = (3;1.6) as shown in figure 8. presented in fig.6 as shown in fig.7. Scenario 2 :A1 = (0; 0), A2 = (2;4.8), A3 = (4;4.8), A4 = (7.6; In [11], we estimated the error of a measured distance of 4.4), and A5 = (3;1.6). as shown in figure 9. a walking human in an indoor environment having different channel types (LOS, soft NLO, and hard NLOS) using UWB technology (DW1000, EVK 1000). The estimated error of the distance from 2 m to 26 m ranges between 0.3 m to 1.8 m depends on the traveled distance and number of walls that may affect the measured distance. In this work, we restricted the mobile station to move through Fig. 5. Rational error between the derived and matlab MSE functions. Fig. 6. The real environment. one and two concert walls 30 cm width each (soft and hard VII. R ESULTS AND DISCUSSION NLOS channels) and through LOS channel using channel 2 mode 2 of DW 1000 (EVK 1000) [23, 11]. Also, in [11], the In the experimental activity, Different Mobile station tra- ch 2 mode 2 of EVK 1000 was experimentally validated for jectories have been created to measure the estimated distance obtaining ranging measurements. having different distance errors then the average and variance To place a wireless sensor in a network, an area should be of it used for the AS and WLS algorithms are computed. taken into consideration called a Fresnel zone (FZ) around As mentioned before, we assume a proper NLOS identification the visual line of sight that radio waves spread out into after method is used to extract the average distance bias as shown in they leave the antenna [24]. The FZ must be clear to avoid Table I used to enhance the approximated distance computed the weak in the signal strength level. in Eq.14 to compute the proposed MSE to evaluate the LS Then, we measured the distances and computed the related method. For special cases in the NLOS propagation channels, average error to eliminate the bias in the distance and compute It is observed; when placing a transceiver opposite to a wall the approximated real distance used in the MSE evaluation with distance less than 1.3 m, the distance error increased method. abnormally to approximately 1 m. This abnormal increment The ranging measurements are used in different environments in distance error is due to the high attenuation of the UWB (LOS, soft NLOS, and hard NLOS) for distance ranges from signal when placing or moving the sensors close to a wall. 2 m to 20 m. Table I presents the information used for the This problem should be taken into consideration when using AS algorithm extracted from the modified EVK 1000. an NLOS identification and mitigation method. In this work, the results plot trajectories of the mobile node but, at every point in the trajectory, the position is computed TABLE I without taking into account node dynamics. Only, the last D ISTANCE MEASUREMENT WHERE , r,r̂, AND V ar DENOTE THE REAL , known position is used to obtain the estimated distances to ESTIMATED , AND VARIANCE OF DISTANCE RESPECTIVELY FOR LOS, SOFT NLOS, AND HARD NLOS CHANNELS AND Av DENOTES THE AVERAGE OF the anchors in order to feed the anchor selection algorithm. THE DISTANCE B IAS The AS is compared to the LS, WLS, MLSI, and GDOP methods as shown in figure 9 which presents the empirical LOS HNLOS SNLOS cumulative distribution function (ECDF) of the trajectory Bias Var Bias Var Bias Var presented in scenario 1 (figure 8), and figure 11 presents the r(m) r̂(m) r̂(m) r̂(m) (m) (m2 ) (m) (m2 ) (m) (m2 ) same information provided in figure 9 but for the scenario 2 2 2.09 0.09 0.00 − − − − − − (figure 10). As we mentioned in the titles of figures 7, The AS 4 4.09 0.09 0.00 − − − 4.20 0.16 0.06 is implemented for different groups of anchor nodes according 6 6.02 0.02 0.01 − − − 6.3 0.26 0.10 8 8.05 0.05 0.08 9.33 1.33 0.01 8.28 0.27 0.07 to the proposed MSE method and therefore, the points may be 10 10.06 0.06 0.00 10.74 0.74 0.08 10.12 0.12 0.11 located by 2,3,...n̂ anchor nods. But, the WLS and LS methods 12 12.000 0.00 0.01 12.59 0.59 0.07 12.10 0.10 0.04 are implanted with n̂ anchor nodes.Also, the MLSI and GDOP 14 14.00 −0.06 0.00 15.00 1.00 0.09 14.505 0.51 0.07 methods are implemented with n̂ anchor nodes (in this work 16 16.05 0.05 0.00 16.95 0.95 0.05 16.36 0.36 0.06 n̂ = 5 nodes). 18 18.02 0.02 0.00 18.47 0.47 0.12 18.24 0.244 0.10 20 20.07 0.07 0.00 20.70 0.70 0.14 20.50 0.50 0.12 As we mentioned above in the abstract of this paper about Av GDOP, we address some drawbacks that impact the indoor − 0.052 − − 0.822 − − 0.279 − Bias positioning accuracy. First, we should address that IPs usually have irregular propagation models and barriers that complicate deployment, making it defy to specify a metric to readily compare anchor configuration. GDOP is a unit-less quantity which is a function of the geometry between the target and the beacons, often utilized to estimate the expected accuracy of GPS due to the location of satellites [34]. GDOP has three main drawbacks when utilized as a metric for assessing indoor accuracy. First, Some circumstances cause the standard GDOP metric to expand towards infinity which makes it difficult to normalize over multiple competing configurations [31]. Second, For a terrestrial system, if the location and number of base stations in the desired coverage area are not neatly planned, the GDOP effect can become the dominant factor in limiting the performance of a system [32]. Third, theoretically, the more the nodes involved in the calculation, the lower the GDOP value of the combination will be, which represents a Fig. 7. Simulation of the moving target in real environment (one of different scenarios) that will be located using different distance measurement affect by higher positioning accuracy. Also, In the traditional GDOP- different walls. based nodes selection algorithm, n nodes will be selected from m anchor nodes, and therefore in order to select a subset which has the smallest GDOP, matrix multiplication and inversion should be executed for a combination of m to n times [18]. Finally, some accuracy results are provided to have a reference about performance obtained with GDOP. For instance, the best positioning accuracy obtained in [18] is around 1 m when 10 anchor nodes are involved in the system. Another example of GDOP is presented in [20], where it is assumed that there is no mobile target but all anchor nodes will act as mobile units. In that work, 36 nodes are considered and a positioning accuracy around half meter is obtained. For the sake of comparison, we also include results corresponding to the GDOP strategy proposed in [20] in Fig. 9. In particular, this figure presents the ECDF of MSE of MLSI, WLS, AS, and GDOP and shows how the technique derived in this work outperforms the other methods. The result of figures 9 and 11 experimentally show that the proposed method significantly improves the localization accuracy, reducing the estimation error between 60% and 95% Fig. 9. Empirical distributed function (ECDF) of AS, MLSI, WLS, and GDOP on average, compared with the existing approaches. The results methods in scenario 1. presented in this section clearly show how the AS method is confident in different indoor scenarios including emergency. done with experiment phase presents an evidence using the VIII. C ONCLUSION AS can reach an accurate IP system with less than 0.5 m2 of MSE of a positioning and less installation time and number The cost in term of installation time and the number of of wireless sensors in a harsh environment while the WLS, wireless sensors in an indoor environment and precisely locate MLSI, GDOP, and LS algorithms reach more than 3.5 m2 , a moving target are the goals of this work. To obtain this 1.2 m2 , 1.4 m2 , and 9 m2 of MSE respectively. The proposed goal, we present a novel algorithm of three steps:i- create method provides a highly an accepted localization accuracy online an MSE using the linearized LS to dynamically evaluate for different scenarios including emergency. the positioning accuracy of the IP system created by different groups of anchor nodes. ii- Select the group having the best A PPENDIX A accuracy (AS) and relocate the mobile station using the WLS. MSE DERIVATION iii- Involve the virtual node to enable the LS working with In this Appendix, we present the entire derivation of MSE. only two anchor nodes when needed for the MSE. The work Fig. 8. Scenario 1: simulation of the moving target in real environment (one Fig. 10. Scenario 2: simulation of the moving target in real environment (one of different scenarios) affected by different walls and will be located using of different scenarios) affected by different walls and will be located using AS, MLSI, and WLS localization algorithm. AS, WLS, and LS localization algorithm. 2 dˆ1 = r1 + e1 → dˆ1 = r12 + 2e1 r1 + e21 2 and, dˆi = ri + ei → dˆi = ri2 + 2ei ri + e2i Then substituting 2 2 dˆ1 and dˆi in b̂, to obtain  2 x2 + y22 + r12 + 2e1 r1 + e21 − r22 + 2e2 r2 − e22   x23 + y32 + r12 + 2e1 r1 + e21 − r32 + 2e3 r3 − e23  b̂ =    ..   .  2 2 2 2 2 2 xn + yn + r1 + 2e1 r1 + e1 − rn + 2en rn + en Now, let denote b̄i = e21 − e2i + 2r1 e1 + 2ri ei . Then, the expectation value of b̂ is written as   ( b2 + b̄2 )   b3 + b̄3  E b̂ = E    ..   .  bn + b̄n In Eq.1, the difference between p1 and p3 is only the notation Fig. 11. Empirical distributed function (ECDF) of AS, WLS, and LS methods of the expectation value which is expressed in p1. Thus, in scenario 2. solving p1 will be in the same way of solving p3 with taking into account the expectation notation. Also, we denote the first part of p1 as p11 and the second part p12 . For the similarity AS we mentioned in MSE computation section above, the in p11 and p12 , we solve only p11 . MSE could be written as shown in Eq. 12 and below ( n hX i2 ) 2 M SE = p1 − 2p2 + p3 (1) p11 = v11 E 2xi (bi + b̄i ) i=2 So, we solve every part of Eq.1 separately then collect them to ( n n ) X X obtain the final mathematical expression of the derived MSE. +2v11 v12 E 2xi (bi + b̄i ) 2yi (bi + b̄i ) First, we start with p3, i=2 ( i=2 ) " #2 n hX i2 n n 2 X X +v12 E 2yi (bi + b̄i ) p3 = v11 2xi bi + v12 2yi bi i=2 i=2 i=2 " n n #2 Now,(we analyze ) X X n i2 + v21 2xi bi + v22 2yi bi hX 2 v11 E 2xi (bi + b̄i ) i=2 i=2 i=2 Furthermore, only the first part of p3 is solved because the to obtain second part is similar and the difference is only with v values ( n hX i2 ) n hX i2 which is constant. The first and second part of it are denoted 2 v11 E 2xi (bi + b̄i ) 2 = v11 2xi bi by p31 and p32 respectively and starting to solve p31 i=2 i=2 n n n n n hX i2 X X 2 X nX o 2 p31 = v11 2xi bi + 2v11 v12 2xi bi 2yi bi +2v11 xi bi E 2xi b̄i i=2 i=2 i=2 i=2 ( n i=2 ) n hX i2 hX i2 2 2 +v12 2yi bi +v11 E 2xi b̄i i=2 i=2 Second, the other parts (p1 and p2) in Eq.1 are computed. Also, by the same way, we obtain So, b should be changed to b̂. ( n ) hX i2 n hX i2 2 2 2 2 x22 + y22 + dˆ1 − dˆ2  v12 E 2yi (bi + b̄i ) = v12 2yi bi 2 2 i=2 i=2  x3 + y32 + dˆ1 − dˆ3   2 n n b̂ =   ..  2 X nX o  .   +2v12 2yi bi E 2yi b̄i 2 2 i=2 x + y + dˆ1 − dˆn 2 n 2 n ( n i=2 ) hX i2 2 2 2 +V12 E 2yi b̄i where, bˆi = x2i + yi2 + dˆ1 − dˆi , i=2 the last part needed to analyze is 2) C. Fuchs, N. Aschenbruck, P. Martini, and M. Wieneke, ( n n ) ”Indoor tracking for mission critical scenarios: A sur- vey,” Pervasive Mob. Comput., vol. 7, no. 1, pp. 1-15, X X 2v11 v12 E 2xi (bi + b̄i ) 2yi (bi + b̄i ) = i=2 i=2 Feb. 2011. n X n X n nX n X o 3) J. Callmer, ”Autonomous localization in unknown envi- 2v11 v12 2xi bi 2yi bi + 2v11 v12 E 2xi bi 2yi b̄i ronments”,Linkoping University Electronic Press, 2013. i=2 i=2 i=2 i=2 4) M. Algabri, H. Mathkour, H. Ramdane, and M. Al- n n nX X o sulaiman, ”Comparative study of soft computing tech- +2v11 v12 E 2yi bi 2xi b̄i niques for mobile robot navigation in an unknown i=2 i=2 n n environment”, Comput. Human Behav., vol. 50, pp. 42- 56, Sep. 2015. nX X o +2v11 v12 E 2xi b̄i 2yi b̄i i=2 i=2 5) He T, Huang C, Blum BM, Stankovic A, Abdelzaher T,”Range free localization schemes for large scale sensor Then using the same way, we can find p32 and p12 and networks”,Proceedings of the 9th annual international compute conference on Mobile computing and networking, pp p32 + p31 = p3 81-95, 2003. 6) Lourenco P, Batista P, Oliveira P, Silvestre C, Chen p12 + p11 = p1 P,”A received signal strength indication-based localiza- Finally, compute the last part of Eq.1, p2 and split it into two tion system”, 21st Mediterranean Conference on Control parts which will be denoted p21 and p22 respectively, also, we Automation,(MED), pp 1242-1247, 2013. can compute one of them. We are computing p21 . 7) Wu L, Meng MQ-H, Lin Z, He W, Peng C, Liang H, n n n ”practical evaluation of radio signal strength for mobile hX i2 nX o robot localization” International Conference on Robotics X 2 2 p21 = v11 2xi bi + v11 E 2xi bi 2xi b̄i i=2 i=2 i=2 and Biomimetics (ROBIO), pp 516-522, 2009. n X n X 8) Farid Z, Nordin R, Ismail M, ”Recent advances in +2v11 v12 2xi bi 2yi bi wireless indoor localization techniques and system”, J i=2 i=2 Comput Netw Commun, 2013. n n nX X o 9) Matteo Ridolfi, Stef Vandermeeren, Jense +v11 v12 E 2yi bi 2xi b̄i Defraye,”Experimental Evaluation of UWB Indoor i=2 i=2 Positioning for Sport Postures”, Sensors, 2018. n n 10) Ali Yassin, Youssef Nasser, Mariette Awad,”Recent Ad- nX X o +v11 v12 E 2xi b̄i 2yi b̄i i=2 i=2 vances in Indoor Localization: A Survey on Theoretical n hX i2 n nX n X o Approaches and Applications”, University of New South 2 2 Wales, IEEE, 2016. +v12 2yi bi + v12 E 2yi bi 2yi b̄i i=2 i=2 i=2 11) Abbas Albaidhani, Antoni Morell, Jose Lopez Vicario,” Ranging in UWB using commercial radio modules: After solving the p22 , we will have experimental validation and NLOS mitigation”, IEEE, p22 + p21 = p2 IPIN conference, pp 1-7, 2016. 12) Decawave LTD. APS 006 APPLICATION NOTE, Finally, putting the result of p1, p2 and p3 in Eq.1, the compact ”CHANNEL EFFECTS ON COMMUNICATIONS equation of it is obtained as shown in the Eq.2 below. RANGE AND TIME STAMP ACCURACY IN  n X n  DW1000 BASED SYSTEMS”, Version 1.02, pp 12-16, 2 o 2014.  E 2xi b̄i 13) Guosai Yang1, Linhui Zhao1, Yaping Dai2, and Yijun   2 2 T  i=2  v11 + v21   n X n 2 o   Xu2, ”A KFL-TOA UWB Indoor Positioning Method 2 2 M SE =  v12 + v22  E 2yi b̄i for Complex Environment” IEEE, pp 3010-3104, 2017.     2v11 v12 + 2v21 v22   nX n i=2 n   14) Fabian Hoflinger, Rui Zhang, Patrick Fehrenbach, Joan X o  E 2xi b̄i 2yi b̄i  Bordoy, Leonhard Reindl, Christian Schindelhauer, ”Lo- i=2 i=2 calization System based on Handheld Inertial Sensors (2) and UWB”, IEEE, 2017. 15) Mathias Pelka, Grigori Goronzy, and Horst Hellbruck, R EFERENCE ”Iterative approach for anchor configuration of position- 1) Andre G. Ferreira, Duarte Fernandes, Andre P. Catarino, ing systems”, ScienceDirect, 2016. and Joao L. Monteiro, ”Localization and Positioning 16) Chenchen Zhang, Xiaoyu Bao, Qilu Wei, Qun Ma, Yuan Systems for Emergency Responders: a Survey”, 2017, Yang and Qing Wang, ”A Kalman Filter for UWB DOI 10.1109/ COMST, 2703620, IEEE, 2017. Positioning in LOS/NLOS Scenarios”, IEEE UPINLBS, pp 73-78, 2016. Based Indoor Localization”, IEEE, pp 1-8, IPIN 2016. 17) Manon Kok, Jeroen D. Hol, and Thomas B. Schon, 32) Ian Sharp, Kegen Yu, Y. Jay Guo, ”GDOP Analysis for ”Indoor Positioning Using Ultrawideband and Inertial Positioning System Design”, IEEE TRANSACTIONS Measurements” IEEE TRANSACTIONS ON VEHICU- ON VEHICULAR TECHNOLOGY, VOL. 58, NO. 7, LAR TECHNOLOGY, pp 1293-1303, 2015. SEPTEMBER 2009. 18) Yunzhou Zhang, Dongfei Wei, Wenyan Fu, and Bing 33) Kuang-Hao Lin, Chi-Chang Lu, Hou-Ming Chen, Hsu- Yang, ”Target Positioning with GDOP Assisted Nodes Feng Li, and Cheung-Fu Chuang.”A Modified Least Selection Algorithm in Wireless Sensor Networks”, In- Squares Iteration for Indoor Positioning System”, IEEE ternational Journal of Distributed Sensor Networks, pp International Conference on Consumer Electronics, Tai- 1-10, 2014. wan. 19) Paula Tarrio, Ana M. Bernardos and Jose R. Casar, 34) Pratap Misra and Per Enge.”Global Positioning Sys- ”Weighted Least Squares Techniques for Improved Re- tem: Signals, Measurements and Performance Second ceived Signal Strength Based Localization”, Sensors, pp Edition.”, Lincoln, MA: Ganga- Jamuna Press, 2006. 8570-8592, 2011. (ICCE-TW), 2017. 20) Ian Sharp, Kegen Yu, and Mark Hedley, ”On the GDOP and Accuracy for Indoor Positioning”, IEEE TRANS- ACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS VOL. 48, NO. 3, pp 2032-2051, 2012. 21) Liu B, Lin K, Wu J, ”Analysis of hyperbolic and circular positioning algorithms using stationary signal strength difference measurements in wireless commu- nications”, IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, pp 499-509, 2006. 22) Sun G, Chen J, Guo W, Liu K, ”Signal processing techniques in network-aided positioning: A survey of state of the art positioning designs”, IEEE, 12-23, 2005. 23) Decawave LTD. EVK1000 USER MANUAL, ”HOW TO USE, CONFIGURE AND INTERFACE TO THE DW1000 EVALUATION KIT”, http//www.decawave.com, pp 1-26, 2014. 24) Decawave LTD. APS 0006 Application Note: ”Chan- nel Effect on Communication Range and time stamp accuracy in DW 1000 Based Systems”, http//www.decawave.com, pp 1-21 ,2014. 25) Valent in Barral, Pedro Su arez Casal, Carlos J. Es- cudero, Jose A. Garc ia Naya, ”Assessment of UWB Ranging Bias in Multipath Environments” IEEE, pp 1- 4, IPIN 2016. 26) Decawave, Sources of error in DW1000 based two-way ranging (TWR) schemes. Decawave, 2014. 27) D. B. Jourdan, J. J. Deyst, M. Z. Win, and N. Roy, ”Monte carlo localization in dense multipath environ- ments using UWB ranging”,IEEE International Confer- ence on Ultra-Wideband, pp 314-319, Sept 2005. 28) Imane Horiya Brahmi1, Giovanni Abbruzzo1, and Michael Walsh1 ”A Fuzzy Logic Approach for Im- proving the Tracking Accuracy in Indoor Localisation Applications”, IEEE Wireless Days journal, pp 137-144, 2018. 29) Decawave LTD. ”Upgrading EVB 1000 to lat- est software:software: Offset Compensation”, http/ www.decawave.com, 2015. 30) Decawave Ltd. DW1000 user manual, http//www.decawave.com, 2015. 31) Niranjini Rajagopal, Sindhura Chayapathy, Bruno Si- nopoli, Anthony Rowe, ”Beacon Placement for Range-