# An Efficient Location Verification Scheme for Static Wireless Sensor Networks
## 5 Security and Performance Analysis
### Performance Analysis  
The performance of the proposed and related schemes was analyzed in terms of communication and computation costs when verifying a single sensor. This analysis is done based on each system model of those schemes. Communication cost was defined as the number of packets that must be exchanged during the location verification process. Packets exchanged to prepare the protocol, such as the initial distance measurement or neighbor determination, were not counted as part of the communication costs. This is because all of the relevant schemes in comparison require the update of neighbor information, and the update of the information can be done by exploiting the data packets delivering sensed data, such as temperature. In the same way, computation cost was defined as the computational complexity that a sensor needed to perform for the location verification process. Cryptographic operations were considered to have the same computation costs as basic operations, such as addition and subtraction, to give the maximum advantage to the other schemes. Note that our scheme does not perform cryptographic operations for the verification. The scheme proposed in this paper was compared to the phantom [14] and lightweight [15] on-spot verification schemes. Table 2 defines the terms used in the analysis, and Table 3 summarizes the communication and computation cost for each scheme. Under the phantom method, each sensor measures its distance from each of its neighbors and then broadcast them. As packets used for protocol preparation were excluded from the communication cost in this analysis, the costs associated with this measurement are omitted. Thus, the final communication cost is the number of packets that are used to announce the measurements, which is the same as the number of the claimant's neighbors. As such, the communication cost grows linearly according to the network's sensor density. The computation cost is measured by \(O(iter*N_{ne})\). It requires the encryption and decryption of the distance measurement information of all of its neighbors, which is a total of \(N_{ne}+1\) cryptographic operations. \(N_{ne}\) trilateration processes must be performed to filter out the malicious sensors during \(iter\) iterations. Here, \(iter\) is the number of trials that the algorithm must be run to successfully complete the verification process. Thus, the total computation cost can be represented as \(iter*N_{ne}+(N_{ne}-1)\), which can be expressed as \(O(iter*N_{ne})\) in complexity notation. In order to produce a location verification success rate of 99%, \(iter\) = 7 when 30% of the sensors are phantom nodes. The more compromised sensors there are, the more times the verification process must be run to maintain a particular success rate, so \(iter\) and the proportion of compromised sensors are positively correlated. In the lightweight scheme [15], communication cost is \(N-1\) because all of the sensors need to send their observation results to the central verifier. Here, neighbor observation packets are not counted. If only a single sensor malfunctions, it requires \((N_{ne}+1)\) communication costs since each \begin{table}
\begin{tabular}{c c} \hline \hline
**Terms** & **Definition** \\ \hline \(N\) & Number of total sensors \\ \(N_{ne}\) & Average number of neighbors of a sensor, \(N_{ne}<N\) \\ \(m\) & Number of mutually-shared neighbors of two sensors, \(m<N_{ne}\) \\ \(iter\) & Iteration count for the speculative filtering (in the phantom scheme) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Terms and definitions. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Scheme** & **Communication Cost (\(C_{comm}\))** & **Computation Cost (\(C_{comp}\))** \\ \hline Phantom [14] & \(N_{ne}\) & \(O(iter*N_{ne})\) \\ Lightweight [15] & \(N_{ne}+1\) & \(O(N)\) \\ Our scheme (MSRLV) & 2 & \(O(m)\simeq O(N_{ne})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Communication and computation cost for the verification of a single sensor. sensor in the target area must send and receive its observation.