# LaRaWAPS: A Wide-Area Positioning System Based on LoRa Mesh
## 4 System Design
### LoRa Ranging and Localization
#### 4.3.3 Location Algorithm  
With multiple distance information from moving target to stationary anchors with known coordinates, the authors are able to solve coordinates target. The classic three-point positioning method is usually adopted. Assume that the coordinates of the three selected anchor points are \((x_{a},y_{a})\), \((x_{b},y_{b})\), \((x_{c},y_{c})\), the ranging results between the LoRa tag and the three anchors are \((\tilde{d}_{a},\tilde{d}_{b},\tilde{d}_{c})\), and \((\hat{x},\hat{y})\) represents the estimated LoRa tag position coordinates. The optimal \((\hat{x},\hat{y})\) is obtained using the iterative method, which minimizes the ranging error \(f(x,y)=\sum_{i=a,b,c}\left(\tilde{d}_{i}-\sqrt{(x_{i}-\hat{x})^{2}+(y_{i}- \hat{y})^{2}}\right)^{2}\). The expression of the \(k+1\) iteration is written as:  
\[\begin{cases}\hat{x}_{k+1}=\hat{x}_{k}-f(\hat{x}_{k},\hat{y}_{k})\cdot\left( \left.\frac{\partial f(x,y)}{\partial x}\right|_{x=\hat{x}_{k},y=\hat{y}_{k}} \right)^{-1},\\ \hat{y}_{k+1}=\hat{y}_{k}-f(\hat{x}_{k},\hat{y}_{k})\cdot\left(\left.\frac{ \partial f(x,y)}{\partial y}\right|_{x=\hat{x}_{k},y=\hat{y}_{k}}\right)^{-1}.\end{cases} \tag{8}\]  
Since the true position of the target is unknown, it is impossible to know the positioning error after positioning, so we cannot directly optimize the positioning performance. However, since the RSSI measurements of all anchors to the targets and the estimated loca tion of the target are known, the performance of positioning can be heuristically estimated by comparing the difference between measured and calculated RSSI using the estimated location of the target. Therefore, the posteriori RSSI error (PRE) between the anchor and the target is defined to evaluate the anchor positioning capability as:  
\[PRE_{i}=\sum\limits(r_{i}^{\prime}-\hat{r}_{i}), \tag{9}\]  
where \(r_{i}^{\prime}=r_{0}-10\alpha\log_{10}\hat{d}_{i}\) denotes the wireless signal strength calculated according to the estimated position. \(r_{0}\) is the radio signal intensity at an interval of 1 m. Based on the above heuristic, the location algorithm is shown in Algorithm 2.  
Firstly, \(M\) different sets are selected from the ranging data of \(N\) anchor points to the target obtained, and the location of anchor points \((\hat{x}^{M},\hat{y}^{M})\) is estimated according to the method in Equation (8). Secondly, calculate the mean PRE of each anchor point corresponding to each \((\hat{x}^{m},\hat{y}^{m})\) according to Equation (9), \(m\in M\). Finally, \((\hat{x}^{m},\hat{y}^{m})\) corresponding to the set m with the minimum mean PRE is selected as the positioning result.  
```
Input: Number of anchors participating in positioning \(N\), Position coordinates of each anchor point\((x_{i},y_{i})\). Output: The estimated position coordinates of the target node \((\hat{x}^{m},\hat{y}^{m})\)
1 Iterate over a three-element subset of a set of \(N\) anchor points, whose set is \(\mathbf{N^{3}}\);
2 Initialize the set \(M\) as the first element in the set \(\mathbf{N^{3}}\);
3 while\(M\in\mathbf{N^{3}}\)do
4 According to the Algorithm 1, the distance between each anchor point and the target node in the set M is obtained;
5 Calculate \((\hat{x}^{M},\hat{y}^{M})\) according to the Formula (8);
6 Calculate \(PRE_{M}\) according to the Formula (9);
7 Update the set M to the next element in the set \(\mathbf{N^{3}}\);
8
9 end while
10 Find the set \(m\) corresponding to \(min(PRE_{M})\);
11 return\((\hat{x}^{m},\hat{y}^{m})\);
```  
**Algorithm 2**Multi-point location algorithm based on minimizing posteriori error