Non-existence of Isolated Nodes in Secure Wireless Sensor Network

Abstract

In this paper, we focus on the non-existence of isolated nodes in secure wireless sensor networks under full visibility condition. Here, we consider a sensor network with n sensor nodes distributed uniformly over a compact space $C \subset {\mathbb {R}}^2$. We establish a threshold for the proportion of key ring and key pool size; above this threshold isolated nodes disappear from the network almost surely. We derive that for key pool of size $cn\log \,n$ and key ring of size $c\log \,n$ (of an arbitrary node) and $c>2$ there will be no isolated nodes in the network almost surely.

Appendix

Proof of Lemma 1

Let a is some positive integer such that $aK < P$. Then

$$\begin{aligned} \frac{{{{P}-{aK}}\atopwithdelims (){K}}}{{{P}\atopwithdelims (){K}}}=\, & {} \frac{(P-aK)!(P-K)!}{(P-(a+1)K)!P!}\\=\, & {} \frac{(P-aK)(P-aK-1)\cdots (P-(a+1)K+1)}{P(P-1)(P-2)\cdots (P-K+1)}\\=\, & {} \left( 1-\frac{aK}{P}\right) \left( 1-\frac{aK}{P-1}\right) \cdots \left( 1-\frac{aK}{P-K+1}\right) .\\ \end{aligned}$$

Then it is easy to show that,

$$\begin{aligned} \left( 1-\frac{aK}{P-K}\right) ^{K}\le \frac{{{{P}-{aK}}\atopwithdelims (){K}}}{{{P}\atopwithdelims (){K}}} \le \left( 1-\frac{aK}{P}\right) ^{K}\le \exp \left( -\frac{aK^2}{P}\right) . \end{aligned}$$

(12)

Taking $a = 1,$ we have

$$\begin{aligned} \left( 1-\frac{K}{P-K}\right) ^{K}\le q \le \left( 1-\frac{K}{P}\right) ^{K}\le \exp \left( -\frac{K^2}{P}\right) . \end{aligned}$$

(13)

From Eq. (12) we can derive the lower bound of $\frac{{{{P}-{aK}}\atopwithdelims (){K}}}{{{P}\atopwithdelims (){K}}},$

$$\begin{aligned} \frac{{{{P}-{aK}}\atopwithdelims (){K}}}{{{P}\atopwithdelims (){K}}}\ge & {} \left( 1-\frac{aK}{P-K}\right) ^{K}\nonumber \\=\, & {} 1-\frac{aK^2}{P-K}+{\frac{K(K-1)}{2}} {\left( \frac{aK}{P-K} \right) ^2}-\cdots \nonumber \\\ge & {} 1-\frac{aK^2}{P-K}. \end{aligned}$$

(14)

This implies

$$\begin{aligned} q \ge 1-\frac{K^2}{P-K}. \end{aligned}$$

(15)

Hence

$$\begin{aligned} 1-q \le \frac{K^2}{P-K}. \end{aligned}$$

(16)

Now for the upper bound of $\frac{{{{P}-{aK}}\atopwithdelims (){K}}}{{{P}\atopwithdelims (){K}}},$ we have

$$\begin{aligned} \frac{{{{P}-{aK}}\atopwithdelims (){K}}}{{{P}\atopwithdelims (){K}}}\le & {} \left( 1-\frac{aK}{P}\right) ^{K}\nonumber \\=\, & {} 1-\frac{aK^2}{P}+\frac{K(K-1)}{2} \left( \frac{aK}{P}\right) ^2\nonumber \\\le & {} 1-\frac{aK^2}{P}\nonumber \\ \Rightarrow 1-\frac{{{{P}-{aK}}\atopwithdelims (){K}}}{{{P}\atopwithdelims (){K}}}\ge & {} \frac{aK^2}{P}\,. \end{aligned}$$

(17)

From (15) and (17), we have

$$\begin{aligned} \frac{aK^2}{P} \le 1-\frac{{{{P}-{aK}}\atopwithdelims (){K}}}{{{P}\atopwithdelims (){K}}}\le \frac{aK^2}{P-K}. \end{aligned}$$

Hence

$$\begin{aligned} \frac{K^2}{P} \le p\le \frac{K^2}{P-K}. \end{aligned}$$

This completes the proof. $\square$