Joint Monitoring and Routing in Wireless Sensor Networks Using Robust Identifying Codes

Abstract

Wireless Sensor Networks (WSNs) provide an important means of monitoring the physical world, but their limitations present challenges to fundamental network services such as routing. In this work we utilize an abstraction of WSNs based on the theory of identifying codes. This abstraction has been useful in recent literature for a number of important monitoring problems, such as localization and contamination detection. In our case, we use it to provide a joint infrastructure for efficient and robust monitoring and routing in WSNs. Specifically, we make use of efficient and distributed algorithm for generating robust identifying codes, an NP-hard problem, with a logarithmic performance guarantee based on a reduction to the set k-multicover problem. We also show how this same identifying-code infrastructure provides a natural labeling that can be used for near-optimal routing with very small routing tables. We provide experimental results for various topologies that illustrate the superior performance of our approximation algorithms over previous identifying code heuristics.

Appendix

We provide here the proof of Theorem 5. Recall that G(n,p) = (V,E ) is a random graph of n vertices where the existence of an edge between any pair of distinct vertices is determined independently and in random with probability p.

Proof of Theorem 5

The proof is based on developing the probability that a subset of size c is not a robust identifying code and showing that this probability goes to zero asymptotically in n. But first we show that the expression for c can always be made feasible under the settings of the theorem, namely that c ≤ n.

Observe that log1/q = log(1 + (1/q − 1)) ≥ (1/q − 1) − $\frac{1}{2}(1/q-1)^2= (1/q -1)[1-\frac{1}{2}(1/q-1)]\geq \frac{1}{2}(1/q-1)$, where the last inequality follows from the fact that 0.5 ≤ q ≤ 1. If r ≤ O(logloglogn) then the bound on c can be upper bounded by

$$\begin{array}{lll} &&{\kern-7pt} \frac{2\log n+2r\log \log n}{\log 1/q}\\ &&{\kern5pt} \leq \frac{4q\left(\log n+r\log \log n\right)}{1-q}\\ &&{\kern5pt} \leq \frac{4q\left(\log n+O(\log\log\log n)\log \log n\right)}{1-q}\\ &&{\kern5pt} \leq \frac{O(\log n)}{1-q} \end{array}$$

Since $1-q\geq \Omega\left(\frac{\log n}{n}\right)$, it follows that there exist constants K > K ₀ > 0 such that for large enough n, $1-q\geq \frac{K_0\log n}{n}$, and for large enough K our assertion that c ≤ n can be made true.

We next show that any subset of size c is almost surely an r-robust identifying code. Fix ${\ensuremath{\mathbb{C}} }$ to be a code of size c and let q = p ² + (1 − p)² be the probability that a codeword in ${\ensuremath{\mathbb{C}} }$ does not distinguish between a pair of vertices in V, namely the probability that the codeword doesn’t appear in the pair’s difference set. In the rest of the proof we develop an upper bound on the probability that ${\ensuremath{\mathbb{C}} }$ is not an r-robust identifying code and show that for a certain size c it goes to zero asymptotically in n.

By Lemma 1 if ${\ensuremath{\mathbb{C}} }$ is not r-robust then there must be a pair of distinct vertices u,v ∈ V, for which the difference set under ${\ensuremath{\mathbb{C}} }$ has at most 2r elements. The probability of such an event, Pe(u,v), depends whether either u or v, or both are in ${\ensuremath{\mathbb{C}} }$:

• 1) Both u,v are in ${\ensuremath{\mathbb{C}} }$. There are two possibilities here that need to be addressed separately; either there is an edge between u and v, and hence there can be at most 2r distinguishing codewords from the remaining c − 2 codewords, namely $Pe(u,v|u,v\in{\ensuremath{\mathbb{C}} },(u,v)\in E)=p\sum_{i=0}^{2r} {c-2 \choose i}(1-q)^i q^{c-2-i}$, or there is no edge between u and v, implying that both u and v are already in the distinguishing set; therefore there can be at most 2r − 2 additional distinguishing codewords from the remaining c − 2 codewords, namely $Pe(u,v|u,v\in{\ensuremath{\mathbb{C}} },(u,v)\not\in E)=(1-p)\sum_{i=0}^{2r-2} {c-2 \choose i}(1-q)^i q^{c-2-i}$. In total we have:

  $$\begin{array}{lll}Pe(u,v|u,v\in{\ensuremath{\mathbb{C}} })&=&\sum\limits_{i=0}^{2r-2} {c-2 \choose i}(1-q)^i q^{c-2-i}\\ &&+\,p\sum\limits_{i=2r+1}^{2r} {c-2 \choose i}(1-q)^i q^{c-2-i}. \end{array}$$

• 2) Exactly one of u,v is in ${\ensuremath{\mathbb{C}} }$. Similarly to the previous case there are two possibilities here depending whether an edge between the two vertices exists. In total the probability Pe is given by

  $$\begin{array}{lll}Pe(u,v||{\{{u,v}\}}\cap{\ensuremath{\mathbb{C}} }|=1)&=&\sum\limits_{i=0}^{2r-1} {c-1 \choose i}(1-q)^i q^{c-1-i}\\ &&+\,p {c-1 \choose 2r}(1-q)^{2r}q^{c-1-2r}. \end{array}$$

• 3) Neither u nor v are in ${\ensuremath{\mathbb{C}} }$. Here there are at most 2r distinguishing codewords in ${\ensuremath{\mathbb{C}} }$.

  $$Pe(u,v|u,v\notin {\ensuremath{\mathbb{C}} })=\sum\limits_{i=0}^{2r} {c \choose i}(1-q)^i q^{c-i}.$$

We use the union bound to set an upper bound on the probability that ${\ensuremath{\mathbb{C}} }$ is not an r-robust identifying code:

$$\begin{array}{lll}P(\mbox{${\ensuremath{\mathbb{C}} }$ is not $r$-robust})&\leq& {c \choose 2}Pe(u,v|u,v\in{\ensuremath{\mathbb{C}} })\\&&+\,(n-c)c Pe(u,v||{\{{u,v}\}}\cap{\ensuremath{\mathbb{C}} }|=1)\\&&+\,{n-c \choose 2}Pe(u,v|u,v\notin {\ensuremath{\mathbb{C}} })\\ &\leq& 3n^2q^{c-2}\sum\limits_{i=0}^{2r} {c \choose i}\left(\frac{1-q}{q}\right)^i\\ &\leq& 3n^2q^{c-2}\frac{\left(\frac{c(1-q)}{q}\right)^{2r}-1}{\frac{c(1-q)}{q}-1}\\ &\leq& 3n^2q^{c-2}\frac{\left(\frac{c(1-q)}{q}\right)^{2r}}{\frac{c(1-q)}{q}-1}. \end{array}$$

Next consider a code ${\ensuremath{\mathbb{C}} }$ of size $c=\frac{2\log n+(2r-1+\epsilon)\log \log n}{\log 1/q}$ for arbitrary small ϵ > 0, and r = O(logloglogn).

Under this selection of parameters we show that the following equations holds:

$$q^c=n^{-2}(\log n)^{-2r+1-\epsilon}$$

(3)

$$c^{2r}\leq O\left(\left(\frac{2}{\log (1/q)}\right)^{2r}(\log n)^{2r}\right)$$

(4)

$$\frac{1-q}{\log{1/q}}=\Theta(1)$$

(5)

$$c(1-q)\geq\Omega(\log n).$$

(6)

Equation 3 is straightforward.

To see why Eq. 4 is true observe that

$$\begin{array}{lll}c^{2r}&=&\left(\frac{2}{\log (1/q)}\right)^{2r} (\log n)^{2r}\left(1+O\left(\frac{\log\log n}{\log n}\right)\right)^{2r}\\ &\leq &\left(\frac{2}{\log (1/q)}\right)^{2r}(\log n)^{2r}e^{O(1)}. \end{array}$$

Equation 5 follows form the fact that 0.5 ≤ q ≤ 1 and hence $\frac{0.5}{\log 2}\leq\frac{1-q}{\log{1/q}}=\frac{1-q}{\sum_{i=1} \frac{(1-q)^i}{i}}=\frac{1}{1+\sum_{i=1}\frac{(1-q)^i}{i+1}} \leq 1$.

Finally Eq. 6 follows from a directs substitution of c in Eq. 5.

We can use these equations to complete the proof by further bounding the probability that ${\ensuremath{\mathbb{C}} }$ is not an r-robust identifying code:

$$\begin{array}{lll}P(\mbox{${\ensuremath{\mathbb{C}} }$ is not $r$-robust})&\leq& O\left((\log n)^{1-\epsilon}\frac{\left(\frac{2(1-q)}{q\log (1/q)}\right)^{2r}}{cq(1-q)-q^2}\right)\\ &\leq& (\log n)^{1-\epsilon}\frac{(O(1))^{2r}}{\Omega(\log n)}\\ &\leq& O\left(\frac{\log \log n}{(\log n)^{\epsilon}}\right)=o(1). \end{array}$$

□