## 2 Algorithm
### Phase 1: Coarse Location Estimation  
In this phase, each sensor first makes an initial guess of its location that is irrelevant to its actual location and can be obtained by random assignment, then ranges to each of its visible beacons, and uses the estimated distance from signal strength to iteratively refine this initial guess. Precisely, each \(Sensor_{i},i\in\mathbb{S}\) first makes the initial guess of \(\overrightarrow{V_{i}}\), then measures the signal strength from each of its visible \(Beacon_{j},j\in\mathbb{B}\). Based on the measured signal strength, \(s_{i,j}\), the distance between \(Sensor_{i}\) and \(Beacon_{j}\) is estimated using the path loss model [18], called \(d_{i,j}\). \(Sensor_{i}\) also collects the location of \(Beacon_{j}\) which is \(\overrightarrow{V_{j}}\). After collecting the distances and locations of all its visible beacons, \(Sensor_{i}\) executes the algorithm to estimate its location based on the spring-relaxation technique described previously. Algorithm 1 describes the procedure for \(Sensor_{i}\) to obtain its coarse location estimation.  
```
//For \(Sensor_{i}\)  INPUT: received signal strengths \(s_{i,j}\), estimated distances \(d_{i,j}\), beacon locations \(\overrightarrow{V_{j}}\), and initial guess of \(\overrightarrow{V_{i}}\)  OUTPUT: phase 1 estimate of \(\overrightarrow{V_{i}}\) \(\overrightarrow{F_{i}}=\tau_{1}\) while\(\|\overrightarrow{F_{i}}\|\geq\tau_{1}\)do \(\overrightarrow{F_{i}}=0\) for all\(Beacon_{j}\)do if\(Beacon_{j}\) is visible to \(Sensor_{i}\)then \(\overrightarrow{F_{i,j}}=(d_{i,j}-\|\ \overrightarrow{V_{i}}-\overrightarrow{V_{j}}\|) \times u(\overrightarrow{V_{i}}-\overrightarrow{V_{j}})\) \(\overrightarrow{F_{i}}=\overrightarrow{F_{i}}+\overrightarrow{F_{i,j}}\) endif endfor \(\overrightarrow{V_{i}}=\overrightarrow{V_{i}}+\delta_{1}\cdot\overrightarrow {F_{i}}\) endwhile
```  
**Algorithm 1** Coarse Location Estimation  
In the algorithm, there are several design parameters that are used to adjust the algorithm behavior and control the algorithm execution. Threshold is a constant that used to define the visibility or connectivity. If the received signal strength \(s_{i,j}\) from \(Beacon_{j}\) to \(Sensor_{i}\) is no smaller than the threshold, then \(Beacon_{j}\) is visible to \(Sensor_{i}\). The specific value of the threshold follows the specification for receiver sensitivity defined in [19]. Tolerance \(\tau_{1}\) is involved in the termination expression of the \(while\) loop. The iterative update of location estimate in the \(while\) loop continues executing until the magnitude of the net force \(\|\overrightarrow{F_{i}}\|\) falls below \(\tau_{1}\). Step size \(\delta_{1}\) controls the proportion that \(Sensor_{i}\) updates its location according to the net force in each iteration, that is the convergence speed of the algorithm. Both \(\tau_{1}\) and \(\delta_{1}\) have profound impacts on the algorithm behavior and performance, which is analyzed in later sections.  
It should be pointed out that it is not a necessity for every sensor to have visible beacons for practical purpose. Instead, we assume that every sensor has at least three non-collinear neighboring sensors, and this assumption can be easily met in practical applications with large network size and high node density. In multi-hop applications where many sensors reside outside the transmission range of available beacons, those outside sensors will keep their initial guesses as the output of phase 1, and let the refinement process in phase 2 to handle the location estimation with the help of neighboring sensors. The advantage the knowledge of beacon locations constantly brings will be transferred eventually to all sensors in a hop-by-hop manner. As a matter of fact, our localization solution aims to provide accurate location estimation with minimal system requirement and deployment effort, e.g., decentralized structure and low coverage of beacons.