## 6 Security Analysis and Results
### Summary of Our Results and Comparison to Prior Schemes  
We present a comparison of existing schemes vs **Disccard** in Table 1. This table illustrates the memory, communication and computation costs for each protocol. The communication costs are for the entire network per time period, and the memory costs are per node. Computation costs shown are per node, per time period. \(g\) stands for the number of witnesses/verifiers selected by each neighbor of a node; \(p\) is the probability a neighbor will transmit location claim to witnesses; \(n\) is the number of nodes in the sensor network; \(d\) represents the average degree of each node; and \(s\) is number of sensors in a group/cell. Since it is infeasible, due to space considerations, to describe the costs for each of these existing protocols in complete detail here, we refer the reader to the references listed in the table for a more thorough comprehension and insight into these costs. ND in Table 1 stands for \"no discussion\", as in the paper that presented the scheme does not discuss the cost in question. In summary, we highlight the most notable features of **Discard** as a list below:  
* Scheme III by [PERSON] _et al._[18] and similar duplicate detecting schemes do not seem to place an emphasis on detecting duplicates within a small geographic region (say, within a home zone). The reasoning is that the adversary can exert his or her influence only within this small region, which is reasonable. However, in our scheme, we detect these duplicates, as well. * We present an explicit relationship between storage costs and detection accuracy. * It is also noteworthy that, in **Discard**, the detection rate is independent of the deployment accuracy. However, as expected, the communication cost of course depends on the deployment accuracy. * As noted earlier, since every location claim is digitally signed, the adversary cannot make uncompromised nodes appear to be replicas by faking their location claims. Thus, **Discard** works without any false positives. * The schemes we outlined in prior work, Section 2, use broadcast mechanisms to propagate duplicate node information in the home zone. However, these broadcast communication costs are typically not accounted for and are deemed negligible. In our scheme, we account for all costs explicitly. * Lastly, unlike Scheme III by [PERSON] _et al._[18], our storage costs are independent of the group size. * In this paragraph, we sketch a quick comparison of our work with the scheme called CSI [45], depicted in the table above. In the protocol CSI, presented by [PERSON] _et al._[45], the detection of duplicate nodes in the sensor network is accomplished by the scheme CSI that employs a novel signal processing technique called compressed sensing. CSI has a communication cost of O(\(n\log n\)), which the authors show to be the lowest possible communication cost in an unstructured sensor network. However, in our work, we are dealing with a group-deployed static sensor network. To this end, we are able to enjoy a lower communication cost of O(\(n\)). Naturally, these two schemes are not directly comparable because of the differences in their underlying network topologies. Furthermore, while the authors demonstrate that CSI has low \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Schemes** & **Communication** & **Storage** & **Computation** \\ \hline Broadcast [10] & O(\(n^{2}\)) & O(\(d\)) & ND \\ RM [10] & O(\(n^{2}\)) & O(\(\sqrt{n}\)) & ND \\ LSM [10] & O(\(n\sqrt{n}\)) & O(\(\sqrt{n}\)) & ND \\ SET [17] & O(\(n\sqrt{n}\)) & O(\(n\)) & O(1) \\ RED [14, 15] & O(\(gpd\)) & O(\(gpd\)) & O(\(gpd\)) \\ SDC [16] & O(\(p\)\(s\)\(\sqrt{n}\)) & O(1) & ND \\ P-MPC [16] & O(\(p\)\(s\)\(\sqrt{n}\)) & O(1) & ND \\ Scheme III [18] & O(\(n\)) & O(\(s\)) & O(1) \\ CSI [45] & O(\(n\log n\)) & ND & ND \\
**Discard** & O(\(n\)) & O(1) & O(1) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of existing schemes _vs_. **Discard**. ND, no discussion; SDC, single deterministic cell; P-MPC, parallel multiple probabilistic cells.