## 5 Performance and Security Analysis
### Security Analysis
Therefore, the probability of randomly selecting a sensor whose hop distance to \(s_{j}\) is within \(\lambda\) is \(\frac{\sum_{\sigma=1}|N_{\sigma}|}{n}\), and the expected number of randomly chosen sensors whose hop distance to \(s_{j}\) is within \(\sigma\) is \(\frac{\sum_{\sigma=1}^{\lambda}|N_{\sigma}|}{n}\cdot t\) when \(t\) sensors are randomly chosen. These \(\frac{\sum_{\sigma=1}^{\lambda}|N_{\sigma}|}{n}\cdot t\) sensors exactly constitute the set of sensors in \(\bar{S}_{j}^{\bar{r}}\). Recall that one of the characteristics of Bloom filter is that the query result is always correct if the content to be queried is indeed stored in the Bloom filter. Thus, we have \(\bar{t}_{j}^{\bar{r}}=\frac{\sum_{\sigma=1}^{\lambda}|N_{\sigma}|}{n}\cdot t\). On the other hand, all the sensors on the route to the sensors in \(\bar{S}_{j}^{\bar{r}}\) also contribute to the authentication procedure. As the number of these sensors is difficult to be precisely calculated, we will approximate it by assuming that the routes to the selected sensors in \(\bar{S}_{j}^{\bar{r}}\) are non-overlapping. For each sensor \(s_{i}\) that is exactly \(\sigma\)-hop away from \(s_{j}\), \(\sigma-1\) sensors lie on the route between \(s_{j}\) and \(s_{i}\). Thus, \(\sum_{\sigma=1}^{\lambda}\frac{|N_{\sigma}|}{n}t(\sigma-1)\) sensors are involved when \(\frac{\sum_{\sigma=1}^{\lambda}|N_{\sigma}|}{n}t\) sensors are in \(\bar{S}_{j}^{\bar{r}}\). It implies that, \(|\bar{S}_{j}^{\bar{r}}\cup\mathcal{E}_{\bar{S}_{j}^{\bar{r}}}|\) can be upper bounded by:  
\[\frac{|N_{1}|}{n}t(1+0)+\cdots+\frac{|N_{\lambda}|}{n}t(1+\lambda-1)\] \[= \sum_{\sigma=1}^{\lambda}\frac{|N_{\sigma}|}{n}t\sigma \tag{3}\]  
Because of our assumption that the routes from \(s_{j}\) to the sensors in \(\bar{S}_{j}^{\bar{r}}\) are non-overlapped, this value overestimates \(|\bar{S}_{j}^{\bar{r}}\cup\mathcal{E}_{\bar{S}_{j}^{\bar{r}}}|\) and, thus, can only work as the upper bound of \(|\bar{S}_{j}^{\bar{r}}\cup\mathcal{E}_{\bar{S}_{j}^{\bar{r}}}|\). In practice,the approximation of \(|\bar{S}_{j}^{\bar{r}}\cup\mathcal{E}_{\bar{S}_{j}^{\bar{r}}}|\) in Equation (3) is quite accurate when the ratio \(\frac{\bar{t}_{j}^{r}}{\eta}\), where \(\eta\) denotes the average number of one-hop neighbors for a sensor, is sufficiently small. Nonetheless, since we know that the fewer the sensors involved in the authentication procedure, the lower the resilience against sensor compromises, even Equation (3) provides a good approximation of \(|\bar{S}_{j}^{\bar{r}}\cup\mathcal{E}_{\bar{S}_{j}^{\bar{r}}}|\) in most cases and can be used to estimate the upper bound of communication overhead in Section 5.2, we still need a lower bound of \(|\bar{S}_{j}^{\bar{r}}\cup\mathcal{E}_{\bar{S}_{j}^{\bar{r}}}|\) to derive the lower bound of the resilience of AAD against sensor compromises. In essence, even if the setting of \(\bar{t}_{j}^{r}\geq 1\) is used, the lower bound of \(|\bar{S}_{j}^{\bar{r}}\cup\mathcal{E}_{\bar{S}_{j}^{\bar{r}}}|\) can be obtained according to the setting of \(\bar{t}_{j}^{r}=1\). By the similar calculation as in Equation (3), we can know that \(|\bar{S}_{j}^{\bar{r}}\cup\mathcal{E}_{\bar{S}_{j}^{\bar{r}}}|\geq L(\lambda,n)\), where  
\[L(\lambda,n)=\sum_{\sigma=1}^{\lambda}\frac{|N_{\sigma}|}{n}\sigma \tag{4}\]  
Define \(P_{ADV}\) as the probability that the event described in Equation (2) happens. Thus, for the adversary that always randomly compromises the sensors over the whole network, the upper bound of probability \(P_{ADV}\) can be obtained as:  
\[\left\{ \begin{array}{ll}\frac{\binom{n-L(\lambda,n)}{n}}{\binom{n}{\bar{r}}} &\text{if }k\bar{r}\leq n\\ 1&\text{if }k\bar{r}>n\end{array} \right. \tag{5}\]  
With \(k\bar{r}>n\), it means that all the sensors are compromised and the whole network is in the complete control of the adversary.