## 6 Security Analysis and Results
### Communication Cost  
As we have seen, sensor node \(n\) initiates one outgoing active connection to a peer node \(p\) to perform its cache exchange (per cycle). We also need to determine the number of incoming connections for node  
Figure 3: The proportion of nodes that have not learned about the duplicate, as a function of consecutive cycles of the **Disccard** algorithm. The expected size of the home zone is 45 nodes. The plot points are averages of 100 runs. \(n\) in order to compute the total communication cost. Let \(b\) represent the average degree of a node, _i.e._, the number of neighbors in the immediate communication range of the node. Let \(N(n)\) refer to the set of neighbors of node \(n\), and from the above assumption, \(\mathsf{E}\left(|N(n)|\right)=b\). Each neighboring node of \(n\) may choose to conduct a cache exchange with \(n\) with probability \(1/b\). As there are \(b\) such neighbors, the expected number of incoming contacts for node \(n\) is therefore one per cycle. This suggests that it might follow a Poisson distribution with mean one, and we verified this empirically, as displayed in Figure 4. We calculated the empirical probabilities in the following manner: we fixed a specific node from the 1000 deployed nodes in the sensor field. Having fixed this node, we tallied the number of incoming connections in each cycle for 1000 cycles and computed the probability to notice that they are very similar to that of the Poisson(1)distribution. Therefore, in each time cycle, there are two cache exchanges: one outgoing and one (expected) incoming exchange. Recall that the neighborhood cache is of size \(c\) and the duplicate cache is of size \(d\) (refer to Figure 2 for the structure and content of these caches). The communication cost per node is therefore proportional to \(2(c+d)\) every \(\delta\) time units. More precisely, the cost per node, per \(\delta\) time unit, is given by \(T_{\$}(c+d)+R_{\$}(c+d)\), where \(T_{\$}\) and \(R_{\$}\) are the transmission and reception costs, respectively. In an effort to put these costs in perspective, let us now use the energy model proposed by [PERSON] _et al._[40] to compute the energy expended by **Discard** towards communication. In their model, the total available node battery is 324,000 mJ; 45.0 mJ for signing a packet (or signature check), 15.104 mJ for transmitting a packet, 7.168 mJ for receiving a packet (assuming a packet length of 32 bytes), 0.059 mJ for bit sending and 0.028 mJ for bit receiving. Assuming (using standard bit representation schemes in Mica2 motes) the ID field takes 16 bits and the \((x,y)\) coordinates take 32 bits, \(c\) entries in the neighborhood cache constitute \(48c\) bits and \(d\) entries of the duplicate cache constitute \(80d\) bits. Concretely, for \(c=5\) and \(d=5\), we see that the neighborhood and the duplicate cache call for \(240\) and \(400\) bits exchanged each period. We can therefore estimate the cost using the model above to yield: \(T_{\$}(c+d)+R_{\$}(c+d)=T_{\$}(640\text{ bits})+R_{\$}(640\text{ bits})=37.76\text{ mJ}+17.92\text{ mJ}=55.68\text{ mJ}\) per node, per cycle. By adjusting the parameters \(c,d\) and \(\delta\), we can tradeoff between the time advantage that the adversary obtains and the lifetime of the sensor network in terms of the energy expended by the **Discard** algorithm for communication. Figure 4: Number of incoming cache exchange requests per cycle, per sensor. In our analysis above, we have not accounted for the one-time energy expenses incurred by the process involving the nodes deployed outside their home zone transmitting their signed locations and requesting verification evidence from nodes in the home zone. Suppose there are \(t\) nodes that find themselves deployed outside their home zone, and they contact \(v\) verifiers. We can estimate this cost as follows: Each of these \(t\) nodes transmit \(v\) signed location claims to the \(v\) verifiers. The \(v\) verifiers send their signed response back to these nodes.