## 2 Localization Algorithm based on Spring Model (LASM)
### The basic LASM (LASM(B))  
The simple process for localization based on the spring model is explained above. We describe the LASM(B) in detail in this part. This localization algorithm can be executed in both distributed and centralized schemes. In a distributed scheme, each sensor node calculates its position through communicating with its neighbors. It's a good method when the sensor network is very large. However, each node needs to communicate with its neighbors, which uses a lot of energy. In a centralized scheme, the sensor nodes send information to the head node. The head node executes the localization algorithm for these nodes and calculates their positions. This method doesn't need rapid communication, but the head node needs a relatively much larger memory and more powerful computing capability.  
The distributed scheme for LASM(B) is described as follows:  
For each anchor particle, it just sends its actual absolute position to its neighbors if needed. It does nothing else.  
For each blind particle \(i\) in the network:  
Step 1: Initialization  
Assign its virtual position at \((x_{i},y_{i})\) randomly and its velocity as zero.  
Step 2: Communication  
Figure 2: Explanation of the proposed localization algorithm based on spring model.  
Communicate with its neighbor particles, obtaining the distances between its neighbor particles and itself (the distances can be calculated by RSSI, TDoA, AoA etc.) and the virtual positions of its neighbors.  
Step 3: Calculation  
Calculate the total force exerted by its neighbors, the acceleration \(a\), and then the next virtual position and velocity using (2)(3)(5). It can be noticed that the next step of position is related with \(\Delta T\). The larger the \(\Delta T\) is, the more rapidly the position changes. Therefore, in the beginning, we set the \(\Delta T\)  larger to let the particle run to the right position more rapidly. After that, we set the \(\Delta T\)  smaller to let the particle adjust its position lightly. Here, we set \(\Delta T\)  be:  
\[\Delta T=c(1-l/\mathit{lstep}) \tag{6}\]  
where \(c\) is a constant, \(l\) is the number of calculation steps it has run (or the number the particle communicates with its neighbors), and \(\mathit{lstep}\) is the upper limited number of steps we set for each particle.  
Step 4: Iteration  
Repeat step 2,3 until the total force exerted by neighbors is smaller than a threshold \(\mathit{Tforce}\) or \(l\) is larger than \(\mathit{lstep}\).  
The centralized scheme for LASM(B) is described as follows:  
Here, without loss of generality, we assume that the centralized algorithm is executed in the sink node.  
Step 1: each sensor node sends the distances between itself and its neighbors to the sink node. The anchor nodes also send their absolute positions to the sink node.  
Step 2: the sink node calculates the positions and velocities for all nodes, using the formula similar with the step3 in the distributed scheme described before.  
Step 3: repeat step 2 until the total forces of all particles exerted by neighbors are smaller than a threshold \(\mathit{Tforce}\) or \(l\) is larger than \(\mathit{lstep}\).  
In the distributed scheme of LASM(B), each node just communicates with its immediate neighbor nodes and the calculation steps is less than a threshold. Therefore, the computational complexity for each node is \(O(1)\) and the communication cost is also \(O(1)\). The total communication cost will be \(O(n)\), where \(n\) is the number of blind nodes. Each sensor node executes the localization algorithm in parallel model, and has a computational complexity of \(O(1)\), therefore the time complexity is \(O(1)\). The computational complexity, time complexity and communication complexity are very appropriate for the large scale sensor networks. In the centralized scheme, the total computational complexity is \(O(n)\), which is also much smaller than that of other localization algorithms such as MDS-MAP (\(O(n^{3})\) ).