The Effects of Motion on Distributed Detection in Mobile Ad Hoc Sensor Networks

Abstract

We consider a set of mobile wireless sensors that collect observations about a brief, localized event. As they continue to move about, one of them processes its observations, decides that an event of interest occurred, and wants to determine if other sensors confirm its results. This sensor assumes the role of a Cluster Head (CH) and requests that all other sensors that collected observations at that time/location reply to it with their decisions. The motion of the sensors since the observation time determines how many wireless hops their decision must cross to reach the CH. We analyze the effect of this motion in the 1D case by modeling each sensor's motion as a Correlated Random Walk (CRW). We also account for measurement errors and communication or processing errors in each wireless hop. Quantities, such as the error probability of the final decision at the CH and the minimum energy required to collect the local decisions from all relevant sensors, can then be directly calculated as functions of time and the parameters of the CRW, the measurement noise and the channel noise. These results allow rapid characterization of the time-dependence of distributed detection algorithms that are executed in mobile sensor networks.

1. Introduction

The systems-level work reported in this paper is motivated by a security scenario that has arisen in the context of the eStadium project [1–3], which develops smartphone applications/games, wireless communication networks, and wireless sensor networks for football games and other large-scale events. One security scenario of great interest occurs in the hour immediately before or immediately after a large event. At these times, large numbers of fans, stadium personnel, and concession staff are typically walking toward or away from the stadium. This is a time when they are very vulnerable to deliberate or accidental exposure to hazardous chemical or biological agents.

Suppose that the smartphones that the fans are carrying, or possibly the tickets that they have bought, have sensors embedded in them that can detect these agents. Capabilities like this are the goal of the US Department of Homeland Security's “Cell-All” program [4]. These sensors would necessarily be small and inexpensive and might thus have high false-alarm rates or low rates of correct detection. It is thus important that as many of their individual decisions as possible be fused with each other to ensure a correct final decision. They must therefore be able to communicate with each other or with a designated Cluster Head (CH) to accomplish this goal. These mobile, battery-powered, wireless sensors can thus be modeled as a mobile ad hoc network that is supporting an application that performs distributed detection.

Our first goal is to develop algorithms to efficiently calculate the performance of distributed detection algorithms in this dynamic and complex scenario. These numerical algorithms should account for as many factors as possible, including the motions that are typical of people in crowds, measurement errors in the sensors, errors made during wireless communication, and fusion algorithms with low enough complexity that they can be executed on very low-power processors or on processors that are shared by many different applications.

This paper is organized as follows. Section 2 describes the scenario that has motivated the work in this paper and that is analyzed as an example in Section 8. Prior work in this area is summarized in Section 3. In Section 4, the transient behavior of semi-infinite correlated random walks is reviewed. The solution to the finite case, which is a good model for the motion of people in the scenario of interest to us, is provided in Section 5. Its statistical properties that have the greatest impact on detection applications are analyzed in Section 6. In Section 7, the performance of detection tasks in mobile wireless sensor networks is determined. Numerical and simulation results are provided in Section 8 for the scenario described in Section 2. They demonstrate (i) the use of the mobility model in calculating the minimum energy required to collect data from each sensor participating in the data fusion process, and (ii) the decision error probability at the cluster head once the decisions from all participating sensors have been gathered. These two quantities are functions of both time and the parameters of the mobility model and we demonstrate how the results in this paper provide the ability to rapidly and accurately calculate or simulate them. Some conclusions and a discussion of future work are provided in Section 9.

2. Scenario: Distributed Detection in a Mobile Ad Hoc Network

To evaluate the tools developed in this paper, we assume a situation like that shown in Figure 1. The wireless nodes shown in the figure are carried by people or vehicles that are moving. They have been moving for some time, generally toward the stadium entrance, which is at position $x=N$ at the right end of each subfigure. Their motion to the right is thus strongly dominant over motion to the left, which is shown by arrows to the right that are larger than arrows pointing to the left. Each node may occasionally switch its direction of motion and briefly move against the general flow, just as people do in a real crowd.

Figure 1

A security scenario that arises when large crowds are moving toward a stadium or other venue to participate in an event.

At time $t_0$ we assume without loss of generality that the sensors are in a configuration like that shown in Figure 1(a). We assume that the sensors that are colored blue have each collected observations/samples that have been affected by a chemical or biological agent. It takes time for the sensors to process these observations/samples and the processors managing the sensors may have to finish other tasks before processing them. During this processing delay, the people carrying the sensors continue to move toward the stadium.

At time $t_1>t_0$ one of the sensors shown in Figure 1(b) has finished processing its observations. The results satisfy some criterion—a preliminary positive detection—that requires that sensor to seek other sensor's results so they can be fused with its own to make a highly reliable decision. This sensor declares itself to be a cluster head (CH) and floods the network of sensors—shown in Figure 1(b) as one sensor transmitting at time $t_1$ —with a request for other nodes to send it their results if they were at approximately the same location and time that the CH acquired its samples. This first request for data will suppress or supersede any other requests by any other sensors for data generated for this location and time. Thus, all other sensors with data about this event will forward it to the CH. For our analysis, we will consider two situations: (i) the CH remains stationary, and (ii) the CH continues to move with the crowd.

At time $t_2>t_1$ , the CH's request for reports has reached all other sensors, including those with nothing to report, as shown in Figure 1(c). Sensors with data to report, shown in blue, begin transmitting their results to the CH. In some cases, the CH may be multiple wireless hops away, so intermediate nodes will relay these transmissions. We assume that no local fusion takes place as the nodes' data is relayed to the CH.

It is during this data collection phase that the behavior becomes quite interesting. From the moment it starts, we want to determine the best decision that the CH can make given the multi-hop network that exists at time $t_2$ . If $t_2$ is close to $t_1$ , the sensors would not have spread out very much, so each one may be within one wireless hop of the CH. If $t_2$ is significantly greater than $t_1$ , then the nodes may be either very spread out or, if they have all gotten close to the stadium entrance, have begun to bunch up again. In any of these cases, there will be communication errors, but more errors will occur when the nodes are spread out because additional transmissions are needed to relay the data. The algorithms we use for distributed detection account for these situations and can even determine how much energy each node should dedicate to sending its data—where the energy is measured in terms of the number of bits the node sends.

We develop analytical models of this scenario and numerical methods to calculate the best possible performance that can be expected at any time t. We are thus interested in the behavior of the network as it changes over time, where these changes are due to the motion of the crowd. The transient behavior of stochastic models of this motion is critical to understanding this scenario and eventually determining the optimal time at which to make a decision.

We must first model how sensors organize into a cluster, which must be done very rapidly in mobile, event-driven scenarios. We thus assume the existence of a very fast, low-complexity algorithm for clustering that is triggered by an event—in this case the request by one node for other nodes' data. The algorithm we choose is the one defined and analyzed in [5, 6]. We will only consider the single-cluster case that is created in the scenario in this paper; the more general case of hierarchical clustering is relevant if we need to collect results from all sensors participating in an event. In this more general case, many thousands of sensors may be involved, one for each person attending the event.

In the single-cluster scenario, the communication architecture is some variation of the 2-hop cluster shown in Figure 2. The sensor in the center of the cluster, called the CH, is the one that requested the decisions from other sensors. The sensors shown in the first ring are one wireless hop from the CH; the ones in the second ring are two hops away, and so forth. Three sensors in a sector of ring 2 are shown forwarding their decisions to one sensor in ring 1. Each sensor's observation is affected by measurement noise and all communications throughout the network will be affected by channel noise, fading, and transceiver errors. Because the cluster is multi-hop, decisions forwarded from the outer rings will suffer repeated exposure to the sources of communication error and more energy must be expended to get them to the CH.

Figure 2

A 2-hop, 2D cluster. The mobility of the sensors produces this temporary, multi-hop cluster. Each sensor's decision may be incorrect because of measurement noise; transmitted packets may suffer bit errors because of noisy communication channels. If the number of hops in the cluster increases with time, the energy required for communication will increase and detection performance will decrease.

The mobility model governing each sensor and the time since the event of interest will clearly affect the number of hops, and thus both the probability of detection at the CH and the energy consumed to gather the local decisions. It will also affect the network's performance in terms of coverage, maximum throughput, and throughput-delay trade-offs.

3. Prior Work on Mobility Models and Distributed Detection

Many mobility models have been proposed for analyzing the behavior of mobile ad hoc networks like the one described previously. In [7, 8], those models are categorized into four classes: random models, models with temporal dependency, models with spatial dependency, and models with geographic restrictions. For instance, random walks and random waypoint models are random models; Gauss-Markov mobility models and Smooth Random models are models with temporal dependency; group mobility models [7] are models with spatial dependency; Pathway mobility models and Obstacle mobility models are models with geographic restrictions. These models are useful as analytical or simulation tools but none of them can account for all of the constraints or features of real systems.

We thus use Correlated Random Walks (CRWs) as the model for the motion of the sensors in our security scenario. They can account for time dependency, geographical restrictions, and nonzero drift. They are more general than random walks but are still amenable to analysis, sometimes in closed-form. The limiting distribution for a discrete-time 1D doubly-infinite CRW on the integers was derived in [9]. The probabilities of being at any lattice point at the nth step for a discrete-time 1D CRW in different cases were found in [10–13]. The absorbing probability and expected duration of a discrete-time CRW was found in [14]. The transient behavior of the continuous-time CRW on a semi-infinite, 1D state space, is solved, in closed-form in some cases, in [15]. The behavior of multiple sensors whose motion is modeled by discrete-time processes related to CRWs has been studied in [16]. In this paper, we use continuous-time, 1D CRWs on finite state spaces to calculate the behavior of mobile sensors in the security scenario described previously.

Ultimately, our goal is to determine—by numerical analysis instead of simulation—the effect of the mobility of the nodes on the detection problem that exists at the application layer of the mobile, ad hoc network. The performance of these applications will vary with time because of the nodes' motions. Understanding the significance of these transient effects, and being able to precisely determine such quantities as a lower bound on the probability of detection, is critical to developing a strategy for reaching a decision meeting certain criteria in the minimum amount of time.

In [17], an optimal distributed detection strategy in a single-hop network was studied. In [18], a decentralized detection problem under bandwidth-constrained communication was investigated. The noise at different sensors was assumed to be independent, but the statistics of the noise were assumed to be unknown to the CH, so it treats all received detection results equally. It is shown in [19] how the performance of detection algorithms is improved by knowledge of the channel. The limits of detection performance in a one-hop sensor cluster with nonideal channels were determined in [20].

In [21], the performance of distributed detection in a random sensor field is analyzed. The works of [22, 23] discuss the distributed detection problem for Gaussian signals under communication constraints. In [24], the authors consider the detection and localization problem of material releases with sparse sensor configurations. In [25], the sensors adopt robust binary quantizers for distributed detection. Censoring and sequential tests have also been adopted in distributed detection to achieve the same detection accuracy with less energy [26, 27], and they have been combined to further save energy [28, 29].

4. Basic Results on Transient Analysis of a Correlated Random Walk on $\{\mathrm{0,1},\dots ,\infty \}$

In this section, we briefly review results on the transient probability distributions of continuous-time, 1D CRWs on $\{\mathrm{0,1},2,\dots ,\infty \}$ [15]. In this case, the sensor moves according to the following rules.

It takes a step in the same direction as its previous step with probability $p_1$ or $p_2$ depending on whether its previous step was in the positive or negative direction, respectively. It takes a step in the opposite direction of its previous step with probability $q_1=1-p_1$ or $q_2=1-p_2$ depending on whether its previous step was in the positive or negative direction, respectively. On reaching a (reflecting) boundary, it takes a step in the opposite direction with probability one.

The time at which the sensor takes its next step is governed by a Poisson process of intensity λ.

A CRW on $\{\mathrm{0,1},\dots ,\infty \}$ with a reflecting boundary at 0 can be modeled as a quasi-birth-death (QBD) process [30] with the state transition diagram shown in Figure 3. The state $n-$ at any level n is entered when the sensor moves to location n from location $n+1$ . The state $n+$ at any level n is entered when the sensor moves to location n from location $n-1$ .

Figure 3

A Correlated Random Walk (CRW) on $\{\mathrm{0,1},\dots ,\infty \}$ .

Let

$\pi \left(t\right)=\left[\begin{array}{cccccc}{\pi }_{0-}\left(t\right)& {\pi }_{1+}\left(t\right)& {\pi }_{1-}\left(t\right)& {\pi }_{2+}\left(t\right)& {\pi }_{2-}\left(t\right)& \cdots \end{array}\right]$

(1)

be the row vector of probabilities that the chain is in any of the possible states at time t, and define $\Pi (s)$ to be the Laplace transform of the vector $\pi (t)$ . Letting Q denote the generator for this QBD process, then [31]

$\Pi \left(s\right)\left(Q-sI\right)=-\pi \left(0\right),\hspace{1em}\pi \left(0\right)=\pi \left(t\right){\mid }_{t=0}.$

(2)

For this QBD process,

$Q=\left[\begin{array}{ccccccccc}-\lambda & \lambda & 0& 0& 0& 0& 0& 0& \cdots \\ q_1\lambda & -\lambda & 0& p_1\lambda & 0& 0& 0& 0& \cdots \\ p_2\lambda & 0& -\lambda & q_2\lambda & 0& 0& 0& 0& \cdots \\ 0& 0& q_1\lambda & -\lambda & 0& p_1\lambda & 0& 0& \cdots \\ 0& 0& p_2\lambda & 0& -\lambda & q_2\lambda & 0& 0& \cdots \\ 0& 0& 0& 0& q_1\lambda & -\lambda & 0& p_1\lambda & \cdots \\ 0& 0& 0& 0& p_2\lambda & 0& -\lambda & q_2\lambda & \cdots \\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& \ddots & & \end{array}\right].$

(3)

For simplicity only, assume that the initial position of the sensor is 0; that is, $\pi (0)=[\mathrm{1,0},0,\dots ]$ . Define ${\Pi }_n(s)$ to be the transform of ${\pi }_n(t)=[{\pi }_{n+}(t),{\pi }_{n-}(t)]$ , the row-vector of transient probabilities for states on level n of the process. Then,

$\begin{array}{c}-\left(\lambda +s\right){\Pi }_0\left(s\right)+{\Pi }_1\left(s\right)\left[\begin{array}{c}{q}_1\lambda \\ p_2\lambda \end{array}\right]=-1,\\ \lambda {\Pi }_0\left(s\right)+{\Pi }_1\left(s\right)\left[\begin{array}{c}-\left(\lambda +s\right)\\ 0\end{array}\right]=0,\\ {\Pi }_n\left(s\right)B\left(s\right)+{\Pi }_{n+1}\left(s\right)C\left(s\right)=0,\hspace{1em}n\ge 1,\end{array}$

(4)

where

$\begin{array}{cc}\hfill B\left(s\right)& =\left[\begin{array}{cc}0& \mathrm{\hspace{0.17em}\hspace{0.17em}}{p}_1\lambda \\ -(\lambda +s)& \mathrm{\hspace{0.17em}\hspace{0.17em}}{q}_2\lambda \end{array}\right],\hfill \\ \hfill C\left(s\right)& =\left[\begin{array}{cc}{q}_1\lambda & \mathrm{\hspace{0.17em}\hspace{0.17em}}-(\lambda +s)\\ p_2\lambda & 0\end{array}\right].\hfill \end{array}$

(5)

Thus we get

${\Pi }_{n+1}\left(s\right)={\Pi }_n\left(s\right)W\left(s\right),$

(6)

where

$W\left(s\right)=-B\left(s\right){\left[C\left(s\right)\right]}^{-1}=\left[\begin{array}{cc}\frac{p_1\lambda }{\lambda +s}& -\frac{p_1{q}_1\lambda }{p_2(\lambda +s)}\\ \frac{q_2\lambda }{\lambda +s}& \mathrm{\hspace{0.17em}\hspace{0.17em}}\frac{\lambda +s}{p_2\lambda }-\frac{q_1{q}_2\lambda }{p_2(\lambda +s)}\end{array}\right].$

(7)

The boundary variables must also satisfy the following:

${\Pi }_1\left(s\right){\upsilon }_1\left(s\right)=0,$

(8)

where ${\upsilon }_1(s)$ denotes the right eigenvector corresponding to the eigenvalue of $W(s)$ whose magnitude is greater than or equal to 1 for all possible values of s. For this CRW, $W(s)$ is diagonalizable and its eigenvalues are given by

${\gamma }_k\left(s\right)=\frac{f\left(s\right)-{\left(-1\right)}^k\sqrt{{\left(f\left(s\right)\right)}^2-4p_1{p}_2{\lambda }^2{\left(\lambda +s\right)}^2}}{2p_2\lambda \left(\lambda +s\right)},$

(9)

where $f(s)=(p_1+p_2){\lambda }^2+2s\lambda +s^2$ , for $k=\mathrm{1,2}$ . The right eigenvectors ${\upsilon }_k(s)$ , $k=\mathrm{1,2}$ , corresponding to the eigenvalues ${\gamma }_1(s)$ and ${\gamma }_2(s)$ are

$\begin{array}{cc}\hfill & {\upsilon }_k\left(s\right)\hfill \\ \hfill & =\left[\begin{array}{c}\frac{f\left(s\right)-2p_1{p}_2{\lambda }^2+{\left(-1\right)}^k\sqrt{{\left(f\left(s\right)\right)}^2-4p_1{p}_2{\lambda }^2{\left(\lambda +s\right)}^2}}{2p_2\left(p_2-1\right){\lambda }^2}\\ 1\end{array}\right].\hfill \end{array}$

(10)

We find numerically that, for all possible values of $p_1,p_2,\lambda$ , and s, the magnitude of ${\gamma }_1(s)$ is greater than or equal to 1. Hence,

$\begin{array}{cc}\hfill {\Pi }_{1+}\left(s\right)& =\frac{2\lambda \left(1-p_2\right)}{A{\lambda }^2+B\left(p_2\right){\left(s+\lambda \right)}^2+g\left(s\right)},\hfill \\ \hfill {\Pi }_{1-}\left(s\right)& =\frac{f\left(s\right)-C{\lambda }^2-\sqrt{{\left(f\left(s\right)\right)}^2-2C{\lambda }^2{\left(\lambda +s\right)}^2}}{p_2\lambda \left(A{\lambda }^2+B\left(p_2\right){\left(s+\lambda \right)}^2+g\left(s\right)\right)},\hfill \end{array}$

(11)

where $g(s)=\sqrt{(s+\lambda {)}^4-[B(p_1)B(p_2)+1]{\lambda }^2(\lambda +s{)}^2+A^2{\lambda }^4}$ and $A=p_1+p_2-1$ , $B(x)=1-2x$ , $C=2p_1{p}_2$ .

Thus by recursion,

${\Pi }_n\left(s\right)={\Pi }_1\left(s\right){\tilde{W}}^{n-1}\left(s\right),$

(12)

where $\tilde{W}(s)$ is $W(s)$ after the mode whose eigenvalue is outside of the unit circle has been removed [31]. This ensures the stability of the recursion even when numerical errors occur in enforcing the orthogonality condition in (8).

5. New Results on Transient Analysis of Correlated Random Walks on $\{\mathrm{0,1},\dots ,N\}$

A CRW on $\{\mathrm{0,1},\dots ,N\}$ with reflecting boundaries at 0 and N can be modeled as a QBD process with the state transition diagram shown in Figure 4 and the following generator:

$Q=\left[\begin{array}{ccccccccc}-\lambda & \lambda & 0& 0& 0& 0& \cdots & 0& 0\\ q_1\lambda & -\lambda & 0& p_1\lambda & 0& 0& \cdots & 0& 0\\ p_2\lambda & 0& -\lambda & q_2\lambda & 0& 0& \cdots & 0& 0\\ 0& 0& q_1\lambda & -\lambda & 0& p_1\lambda & \cdots & 0& 0\\ 0& 0& p_2\lambda & 0& -\lambda & q_2\lambda & \cdots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& 0& \cdots & q_1\lambda & -\lambda & 0& p_1\lambda \\ 0& 0& 0& 0& \cdots & p_2\lambda & 0& -\lambda & q_2\lambda \\ 0& 0& 0& 0& \cdots & 0& 0& \lambda & -\lambda \end{array}\right].$

(13)

We assume without loss of generality that the initial position of the sensor is 0; that is, $\pi (0)=[\mathrm{1,0},\dots ,0]$ . Then we get

$\begin{array}{c}-\left(\lambda +s\right){\Pi }_0\left(s\right)+{\Pi }_1\left(s\right)\left[\begin{array}{c}{q}_1\lambda \\ p_2\lambda \end{array}\right]=-1,\\ \lambda {\Pi }_0\left(s\right)+{\Pi }_1\left(s\right)\left[\begin{array}{c}-\left(\lambda +s\right)\\ 0\end{array}\right]=0,\\ {\Pi }_n\left(s\right)B\left(s\right)+{\Pi }_{n+1}\left(s\right)C\left(s\right)=0,\hspace{1em}1\le n\le N-2.\\ \lambda {\Pi }_N\left(s\right)+{\Pi }_{N-1}\left(s\right)\left[\begin{array}{c}0\\ -\left(\lambda +s\right)\end{array}\right]=0,\\ -\left(\lambda +s\right){\Pi }_N\left(s\right)+{\Pi }_{N-1}\left(s\right)\left[\begin{array}{c}{p}_1\lambda \\ q_2\lambda \end{array}\right]=0.\end{array}$

(14)

Figure 4

A Correlated Random Walk on $\{\mathrm{0,1},\dots ,N\}$ .

Thus, solving for $\Pi (s)$ in $\Pi (s)(Q-sI)=-\pi (0)$ is reduced to solving

$\left[{\Pi }_0\left(s\right),{\Pi }_1\left(s\right),{\Pi }_{N-1}\left(s\right),{\Pi }_N\left(s\right)\right]\tilde{Q}\left(s\right)=\left[\begin{array}{c}-1\\ 0\\ 0\\ 0\end{array}\right],$

(15)

where, if we define I to be a $2\times 2$ identity matrix, and $\bar{0}=[\mathrm{0,0}]$ ,

$\tilde{Q}\left(s\right)=\left[\begin{array}{ccc}\left[\begin{array}{cc}-\left(\lambda +s\right)& \lambda \end{array}\right]& \bar{0}& \\ \left[\begin{array}{cc}{q}_1\lambda & -\left(\lambda +s\right)\\ p_2\lambda & 0\end{array}\right]& I& \\ & W^{N-2}\left(s\right)& \left[\begin{array}{cc}0& p_1\lambda \\ -\left(\lambda +s\right)& q_2\lambda \end{array}\right]\\ & \bar{0}& \left[\begin{array}{cc}\lambda & -\left(\lambda +s\right)\end{array}\right]\end{array}\right]$

(16)

and the $2\times 2$ matrix $W^{N-2}(s)$ can be computed, via the Cayley-Hamilton theorem, as a linear combination of $W(s)$ and I. It is then straightforward to calculate the transient distributions of the process via stable algorithms for transform inversion [32–34].

As a check on the aforementioned results for the transient behavior of the CRW, we can use the previous results to find its limiting distribution. Since $\pi (\infty )={\lim \hspace{0.17em}}_{s\to 0}\hspace{0.17em}s\Pi (s)$ , it is easy to show that the limiting probability of the CWR on $\{\mathrm{0,1},\dots ,N\}$ being at any location n is [13]

$\begin{array}{cc}\hfill {\bar{\pi }}_0& =\frac{1}{2}\frac{\left(p_1/p_2\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}-1}{{\left(p_1/p_2\right)}^N-1},\hfill \\ \hfill {\bar{\pi }}_n& ={\bar{\pi }}_0\left(1+\frac{p_1}{p_2}\right){\left(\frac{p_1}{p_2}\right)}^{N-1},\hspace{1em}n=\mathrm{1,2},\dots ,\left(N-1\right),\hfill \\ \hfill {\bar{\pi }}_N& ={\bar{\pi }}_0{\left(\frac{p_1}{p_2}\right)}^{N-1}.\hfill \end{array}$

(17)

For the special case of $p_1=p_2=p$ , ${\bar{\pi }}_0={\bar{\pi }}_N=1/(2N)$ , and ${\bar{\pi }}_n=1/N$ , for $n=\mathrm{1,2},\dots ,(N-1)$ . Note, though, that the transient behavior is of interest to us in the rest of this paper.

Note that this approach to analyzing the transient behavior of a simple CRW can be extended to model more complex motion. The number of states in each level of the QBD—two states in the case of the CRW in Figure 4—can be increased. With four to five states per level, the walker can pause, can walk at different speeds at different times, and so forth. The only difference in the algorithms for calculating the transient distribution is that the eigenvalues and eigenvectors of $W(s)$ may not be available in closed form. These techniques can also be extended to some classes of 2D CRWs [15].

6. Statistical Properties of Distances of Nodes from the CH

Suppose that the CH is motionless and there are a total of K sensors in the cluster. As described in the introduction, they start at the the same location as the CH ( $n=0$ ) and then move independently based on identical but independent CRW models. Define $x_i(t)$ as the location of the ith sensor at time t. Further define $d_{\max \hspace{0.17em}}(t)$ and $d_{\min \hspace{0.17em}}(t)$ as the maximum distance and the minimum distance between any sensor in the cluster and the CH, respectively. Then,

$\begin{array}{cc}\hfill P\left(d_{\max }\left(t\right)=n\right)& =P\left(d_{\max }\left(t\right)\le n\right)-P\left(d_{\max }\left(t\right)\le n-1\right)\hfill \\ \hfill & =P{\left(x_1\left(t\right)\le n\right)}^K-P{\left(x_1\left(t\right)\le n-1\right)}^K\hfill \\ \hfill & ={\left({\displaystyle \sum }_{l=0}^n{\pi }_l\left(t\right)\right)}^K-{\left({\displaystyle \sum }_{l=0}^{n-1}{\pi }_l\left(t\right)\right)}^K,\hfill \\ \hfill P\left(d_{\min }\left(t\right)=n\right)& =P\left(d_{\min }\left(t\right)\ge n\right)-P\left(d_{\min }\left(t\right)\ge n+1\right)\hfill \\ \hfill & =P{\left(x_1\left(t\right)\ge n\right)}^K-P{\left(x_1\left(t\right)\ge n+1\right)}^K\hfill \\ \hfill & ={\left({\displaystyle \sum }_{l=n}^N{\pi }_l\left(t\right)\right)}^K-{\left({\displaystyle \sum }_{l=n+1}^N{\pi }_l\left(t\right)\right)}^K.\hfill \end{array}$

(18)

Now assume that the CH is also mobile, that its position is governed by the same CRW as any sensor, and, as before, their motions are all independent. Then $d_{\max \hspace{0.17em}}(t)$ and $d_{\min \hspace{0.17em}}(t)$ become the maximum distance and the minimum distance between a specified sensor and any other sensor in the cluster. The probabilities remain the same whether the sensor is designated as the CH before or after motion of the sensors begins. Denote the position of the CH by $x_0(t)$ . We have

$\begin{array}{cc}\hfill & P\left(d_{\max }\left(t\right)=n\right)\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^{N}P\left(x_0\left(t\right)=m\right)P\left(d_{\max }\left(t\right)=n\mid x_0=m\right)\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^{N}P\left(x_0\left(t\right)=m\right)[P\left(d_{\max }\left(t\right)\le n\mid x_0=m\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-P\left(d_{\max }\left(t\right)\le n-1\mid x_0=m\right)]\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^{N}P\left(x_0\left(t\right)=m\right)\hfill \\ \hfill & \hspace{1em}\times [P\left(m-n\le x_i\left(t\right)\le m+n,\mathrm{\hspace{0.17em}\hspace{0.17em}}1\le i\le K\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}-P\left(m-n+1\le x_i\left(t\right)\le m+n-1,\mathrm{\hspace{0.17em}\hspace{0.17em}}1\le i\le K\right)]\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^N{\pi }_m\left(t\right)\left[{\left({\displaystyle \sum }_{l=m-n}^{m+n}{\pi }_l\left(t\right)\right)}^K-{\left({\displaystyle \sum }_{l=m-n+1}^{m+n-1}{\pi }_l\left(t\right)\right)}^K\right],\hfill \\ \hfill & P\left(d_{\min }\left(t\right)=n\right)\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^{N}P\left(x_0\left(t\right)=m\right)[P\left(d_{\min }\left(t\right)\ge n\mid x_0=m\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-P\left(d_{\min }\left(t\right)\ge n+1\mid x_0=m\right)]\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^N{\pi }_m\left(t\right){\left({\displaystyle \sum }_{l=0}^{m-n}{\pi }_l\left(t\right)+{\displaystyle \sum }_{l=m+n}^N{\pi }_l\left(t\right)\right)}^K\hfill \\ \hfill & \hspace{1em}-{\displaystyle \sum }_{m=0}^N{\pi }_m\left(t\right){\left({\displaystyle \sum }_{l=0}^{m-n-1}{\pi }_l\left(t\right)+{\displaystyle \sum }_{l=m+n+1}^N{\pi }_l\left(t\right)\right)}^K.\hfill \end{array}$

(19)

The probability distribution of the distance between any two sensors $d(t)$ is, for $n=0$ , $P(d(t)=0)={\sum }_{m=0}^N{\pi }_m(t{)}^2$ , and, for $n\ne 0$ ,

$P\left(d\left(t\right)=n\right)={\displaystyle \sum }_{m=0}^N{\pi }_m\left(t\right)\left({\pi }_{m+n}\left(t\right)+{\pi }_{m-n}\left(t\right)\right).$

(20)

Define $D_{\max \hspace{0.17em}}(t)$ and $D_{\min \hspace{0.17em}}(t)$ as the maximum distance and the minimum distance between any two sensors in the cluster. Then,

$\begin{array}{cc}\hfill P\left(D_{\max }\left(t\right)=0\right)& ={\displaystyle \sum }_{m=0}^{N}P\left(x_i\left(t\right)=m,\mathrm{\hspace{0.17em}\hspace{0.17em}}1\le i\le K\right)={\displaystyle \sum }_{m=0}^N{\pi }_m{\left(t\right)}^K,\hfill \end{array}$

(21)

and for $n\ne 0$ ,

$\begin{array}{cc}\hfill & P\left(D_{\max }\left(t\right)=n\right)\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^{N-n}P\left(\min \left\{x_i\left(t\right)\right\}=m,\max \left\{x_i\left(t\right)\right\}=m+n,\mathrm{\hspace{0.17em}\hspace{0.17em}}1\le i\le K\right)\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^{N-n}\hspace{0.17em}{\displaystyle \sum }_{l=1}^{K-1}\hspace{0.17em}{\displaystyle \sum }_{r=1}^{K-l}\left(\begin{array}{c}K\\ l\end{array}\right)\left(\begin{array}{c}K-l\\ r\end{array}\right){\pi }_m{\left(t\right)}^l{\pi }_{m+n}{\left(t\right)}^r\hfill \\ \hfill & {\hspace{1em}\times \left({\displaystyle \sum }_{s=m+1}^{m+n-1}{\pi }_s\left(t\right)\right)}^{K-l-r},\hfill \end{array}$

(22)

where l sensors are at the location m and r sensors are at the location $m+n$ , while all the others are in between. The calculation of the probability distribution of $D_{\min \hspace{0.17em}}(t)$ is much more complicated and, when $K>N$ , it is always zero.

Thus, for both the motionless- and mobile-CH cases, computing $D_{\max \hspace{0.17em}}(t)$ , $D_{\min \hspace{0.17em}}(t)$ , $d_{\max \hspace{0.17em}}(t)$ , and $d_{\min \hspace{0.17em}}(t)$ has been reduced to computing the transient distributions of CRWs. The computational techniques in Sections 2 and 3 thus enable fast and stable computation of statistics of interest in the structure of a cluster of mobile nodes as it evolves over time.

7. Detection in Wireless Sensor Networks

Here we assume a multi-hop sensor network in which each wireless hop is modeled as a Binary Symmetric Channel (BSC). The BSC cross-over probability captures the effect of channel errors on each individual decision bit and is easier to estimate than the full characteristics of the channel. The assumptions of symmetry and the same cross-over probability for each mote-to-mote channel are easily relaxed—they are used only to simplify the analysis so that important trends can be discerned. This paper also assumes that the error probabilities of the individual-received detection results are learned over time by the CH. Hence, the CH is assumed to know the optimal weights for the weighted median in the MAP detector [35] it uses to fuse the received detection results.

In [35], a MAP approach to the distributed detection problem in a multi-hop cluster in a sensor network was developed. It considered a cluster with K rings and $N_k$ motes in the kth ring. Each mote makes a decision between two hypotheses, $s_0=0$ and $s_1=1$ , where “1” denotes that an event has occurred and “0” that it has not. The detection results by different motes are assumed to be i.i.d. Bernoulli random variables, each with a detection error probability $p_m<1/2$ . The noise processes in different wireless channels are assumed to be independent and white. Each hop in the network is modeled as a BSC with cross-over probability $p_c<1/2$ . The decisions made by motes in the outer rings are relayed by the motes in inner rings to the CH. Let the error probability of the detection results received by the CH from the kth ring be $p_{e,k}$ . Then, for example, $p_{e,1}=p_c(1-p_m)+p_m(1-p_c)$ . Denote the detection result received by the CH from the ith mote in the kth ring by $r_{k,i}$ and arrange the detection results in the same ring in a vector ${\bar{r}}_k=(r_{k,1},r_{k,2},\dots ,r_{k,N_k}),k=\mathrm{1,2},\dots ,K$ . Let E denote the event that a decision error happens at the CH.

In a one-hop cluster, suppose that the correct decision should be s. Assume the prior probability $p(s=s_0)=p<1/2$ and find a real number χ such that $\ln \hspace{0.17em}((1-p)/p)=\chi \ln \hspace{0.17em}((1-p_{e,1})/p_{e,1})$ . Define $W=\lfloor N_1/2+\chi /2\rfloor$ . The MAP-based decision bit at the CH is $\widehat{r}=({\bar{r}}_1{)}_W=W$ 'th order statistic of $(r_1,r_2,\dots ,r_{N_1})$ . The decision error probability at the CH is

$\begin{array}{cc}\hfill P\left(E\right)& =\left(1-p\right)\left({\displaystyle \sum }_{i=W}^{N_1}\left(\begin{array}{c}{N}_1\\ i\end{array}\right){\left(p_{e,1}\right)}^i{\left(1-p_{e,1}\right)}^{N_1-i}\right)\hfill \\ \hfill & \hspace{1em}+p\left({\displaystyle \sum }_{i=N_1-W}^{N_1}\left(\begin{array}{c}{N}_1\\ i\end{array}\right){\left(p_{e,1}\right)}^i{\left(1-p_{e,1}\right)}^{N_1-i}\right).\hfill \end{array}$

(23)

It is shown in [35] that, as an estimate of the true decision bit, this weighted order statistic is biased but asymptotically unbiased. When the prior probability is $p=1/2$ , it simplifies into a majority logic operator.

Now we summarize key results in [35] for the multi-hop case. For a mote that is k hops away from the CH, the detection result received by the CH after being relayed over these hops has error probability:

$p_{e,k}=\frac{1}{2}-\frac{1}{2}\left(1-2p_m\right){\left(1-2p_c\right)}^k,\hspace{1em}k\ge 1.$

(24)

We use the notation $W◊x$ , which means that x should be duplicated W times. For simplicity, suppose that the prior probabilities are $p(s=s_0)=p(s=s_1)=1/2$ .

Theorem 1.

Define ${\chi }_k=\ln \hspace{0.17em}((1-p_{e,k})/p_{e,k})$ , and assume that these ${\chi }_k$ 's can be scaled so that ${\chi }_1:{\chi }_2:\cdots :{\chi }_K=W_1:W_2:\cdots :W_K$ , where the $W_k$ 's are positive integers with $gcd(W_1,W_2,\dots ,W_K)=1$ . The MAP-based decision bit is then given by $\widehat{r}=\text{Median}(W_1◊{\bar{r}}_1,W_2◊{\bar{r}}_2,\dots ,W_K◊{\bar{r}}_K)$ . The decision error probability at the CH is given by

$P\left(E\right)={\displaystyle \sum }_{\sum W_k\left(2c_k-N_k\right)>0}^{}\hspace{0.17em}{\displaystyle \prod }_{k=1}^K\left(\begin{array}{c}{N}_k\\ c_k\end{array}\right){\left(p_{e,k}\right)}^{c_k}{\left(1-p_{e,k}\right)}^{N_k-c_k},$

(25)

where $c_k$ is the number of occurrences of $1-s$ in the vector ${\bar{r}}_k,k=\mathrm{1,2},\dots ,K$ .

Because the weighted median is the MAP detector, we assume—even for sector-level fusion algorithms—that the CH calculates this weighted median after receiving inputs from all motes in the cluster. To understand what happens in these more complex cases, the asymptotic behavior of the weighted median must be determined for the single- and multi-hop cases; otherwise, it is too difficult to determine the probability of a clusterwide decision error at the CH.

The asymptotic behavior of the median filter in one-hop clusters has thus been studied using large deviation techniques in [36]:

$\begin{array}{c}\underset{N_1\to \infty }{\lim }-\frac{1}{N_1}P\left(E\right)=C\left(p_{e,1}\right),\\ C\left(p_{e,1}\right)=-\ln \left(2\right)-\frac{1}{2}\ln \left(p_{e,1}\left(1-p_{e,1}\right)\right).\end{array}$

(26)

We now find the error exponent for the decision error probability for the multi-hop case.

Theorem 2.

In multi-hop sensor networks in which $p_{e,k}$ is the error probability of the individual detection results received by the CH from nodes in ring k, the error probability of the MAP detector is upper bounded by [37]

$\ln \left(P\left(E\right)\right)\le {\displaystyle \sum }_{k=1}^K{N}_k\left[\ln \left(2\right)+\frac{1}{2}\ln \left(p_{e,k}\left(1-p_{e,k}\right)\right)\right].$

(27)

Proof.

In the context of the weighted median filter, the decision error probability at the CH is

$\begin{array}{cc}\hfill P\left(E\right)& =P\left({\displaystyle \sum }_{k=1}^K{W}_k{\displaystyle \sum }_{i=1}^{N_k}{r}_{k,i}\ge {\displaystyle \sum }_{k=1}^K\frac{W_k{N}_k}{2}\right)\hfill \\ \hfill & =P\left({\displaystyle \sum }_{k=1}^K{\displaystyle \sum }_{i=1}^{N_k}{W}_k\left(r_{k,i}-\frac{1}{2}\right)\ge 0\right).\hfill \end{array}$

(28)

Since $P(Z\ge 0)\le E[e^{Zt}]$ , let $r_{k,i}^{\prime }=r_{k,i}-1/2$ , and $E[r_{k,i}^{\prime }]=p_{e,k}-1/2<0$ . We have

$P\left(E\right)\le E\left[e^{t{\sum }_{k=1}^K{\sum }_{i=1}^{N_k}{W}_k{r}_{k,i}^{\prime }}\right]={\displaystyle \prod }_{k=1}^K\hspace{0.17em}{\displaystyle \prod }_{i=1}^{N_k}E\left[e^{t{W}_k{r}_{k,i}^{\prime }}\right].$

(29)

For each term in the product, $E[e^{t{W}_k{r}_{k,i}^{\prime }}]=p_{e,k}{e}^{(1/2)t{W}_k}+(1-p_{e,k})e^{(-1/2)t{W}_k}$ . Setting $\partial E[e^{t{W}_k{r}_{k,i}^{\prime }}]/\partial t=0$ , we find

$\begin{array}{cc}\hfill \frac{1}{2}{W}_k{p}_{e,k}{e}^{\left(1/2\right)t{W}_k}& =\frac{1}{2}{W}_k\left(1-p_{e,k}\right)e^{\left(-1/2\right)t{W}_k},\hfill \\ \hfill t& =1.\hfill \end{array}$

(30)

This error exponent is accurate and the bound is tight when the motes are densely deployed; that is, the number of sensors is large. Minimizing $P(E)$ when the number of motes is finite is a very difficult combinatorial problem, so we can minimize this upper bound instead. Also note that the effect of each ring of motes on the decision error probability at the CH is apparent in this bound. It may thus be used to simplify many optimization problems in distributed detection in multi-hop scenarios.

Figure 5 compares the large deviation bound on the error probability with the error probability from simulations for a 3-ring cluster. It shows the desired result that the large deviation error exponent is accurate—the bound is parallel with the simulation result over the entire range of spatial densities. Of course, the bound is high by a multiplicative factor, which is often the case with large deviation techniques.

Figure 5

Comparison for a 3-ring cluster of the error probability obtained via simulation and its large deviations bound. The error exponent is clearly correct and the difference approaches zero asymptotically. Comparing the performance of complex strategies via their error exponents will thus correctly show which strategy is best when motes have large numbers of 1-hop neighbors. Direct calculations and simulations are used to confirm those results for small to moderate numbers of neighbors.

If the CH is static, then we have

$\begin{array}{cc}\hfill P\left(E\right)& \le E\left[{\displaystyle \prod }_{i=1}^{K}2\sqrt{p_{e,i}\left(1-p_{e,i}\right)}\right]\hfill \\ \hfill & ={\displaystyle \prod }_{i=1}^{K}E\left[2\sqrt{p_{e,i}\left(1-p_{e,i}\right)}\right]\hfill \\ \hfill & ={\left[E\left[2\sqrt{p_{e,1}\left(1-p_{e,1}\right)}\right]\right]}^K,\hfill \end{array}$

(31)

where

$p_{e,1}=\frac{1}{2}-\frac{1}{2}\left(1-2p_m\right){\left(1-2p_c\right)}^{\lceil x_1\left(t\right)/r\rceil }.$

(32)

The expected energy consumption for collecting the data is then

$C=K\lceil \frac{E\left[x_1\left(t\right)\right]}{r}\rceil .$

(33)

If the CH is also mobile and its position is governed by a CRW, then we have

$\begin{array}{cc}\hfill P\left(E\right)& \le {\displaystyle \sum }_{m=0}^{N}P\left(x_0\left(t\right)=m\right)P\left(E\mid x_0\left(t\right)=m\right)\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^{N}P\left(x_0\left(t\right)=m\right){\displaystyle \prod }_{i=1}^{K}E\left[2\sqrt{p_{e,i}\left(1-p_{e,i}\right)}\mid x_0\left(t\right)=m\right]\hfill \\ \hfill & ={\displaystyle \sum }_{m=0}^{N}P\left(x_0\left(t\right)=m\right){\left[E\left[2\sqrt{p_{e,1}\left(1-p_{e,1}\right)}\mid x_0\left(t\right)=m\right]\right]}^K,\hfill \end{array}$

(34)

where

$p_{e,1}=\frac{1}{2}-\frac{1}{2}\left(1-2p_m\right){\left(1-2p_c\right)}^{\lceil d\left(t\right)/r\rceil }.$

(35)

The expected energy consumption for collection of the data is

$C=K\lceil \frac{E\left[d\left(t\right)\right]}{r}\rceil .$

(36)

8. Numerical Results

Figure 6 shows the transient probability distribution of two CRWs on $[\mathrm{0,10}]$ with different parameters. One CRW is asymmetric, which means that the walker tends, in the case shown, to prefer motion to the right. The other CRW is symmetric, which means that the walker has no preference for one direction or the other—but its motion is still correlated, unlike in a standard random walk.

Figure 6

Transient probability distribution calculated for two CRWs on $[\mathrm{0,10}]$ . The curve for a given n shows the probability that the walker is at position n at time t.

Figure 7 shows the transient probability distribution of the distance from a static clusterhead to the furthest of five mobile sensors for each point in time. The static clusterhead is assumed to be at location 0. This distance d is important for calculating the number of wireless hops between each sensor and the CH that is trying to gather data. If the transmission radius of each sensor is r, then the number of hops to the CH is the ceiling of $d/r$ .

Figure 7

Calculations of the transient probability distribution of the distance d from a static CH to the furthest of five sensors that are moving according to independent CRWs on $[\mathrm{0,10}]$ .

Figure 8 shows the transient probability distribution of the maximum distance between any of the five sensors and the CH when the mobile CH moves according to the same mobility model as the sensors. This is probably the most realistic case for mobile networks. It leads to an interesting phenomenon when the motion is on a finite grid and the CRWs are all asymmetric in the same direction. The sensors start at 0 when they gathered their observations. With time, they spread out but they all tend to move to the right. As they get close to the other barrier, they then tend to bunch up again. This effect is similar to a crowd moving in a given direction and then gathering around that destination. The distance here, when divided by the transmission radius of the sensors, tells the maximum size, in wireless hops, of the cluster.

Figure 8

Calculations of the transient probability distribution of the distance d from a mobile CH to the furthest of five sensors for d from 0 to 10. The CH and the sensors are all moving independently and according to CRWs on $[\mathrm{0,10}]$ .

Figure 9 shows the expected energy consumed—as a function of the time at which data collection starts—for a static or mobile CH to collect one packet of data from five mobile sensors. The six sensors all collected measurements at the same time/place but then continued to move. By the time a request to send in all data has been received, they are at locations in the state space with probabilities determined by their CRWs. The data collected and decisions made by the sensors that have wandered the furthest require the most energy to collect—that data must travel over the largest number of hops to reach the CH.

Figure 9

Calculation of the expected energy consumed by the network when the collection of data from the five mobile sensors begins at time t. The cases considered are when the transmission radius of each sensor is $\mathrm{\hspace{0.17em}\hspace{0.17em}}r=1$ or $r=3$ and all sensors move according to symmetric or asymmetric CRWs.

Note that some curves in Figure 9 have a stepped appearance. This is due to the existence of the rings in the network that result from the fixed transmission radius for each node. When a node in ring i moves further from the cluster head, it may cross from ring i to ring $i+1$ . Its packets must then be relayed over one additional hop to reach the CH. This extra relay results in a significant jump in the energy that must be expended by the network.

Also note that the mobility of the CH has a significant impact on the energy consumed to collect data. If it is mobile and all sensors are moving according to a CRW that is asymmetric, then the energy required for collection first increases and then decreases. In this case, it is better to collect data either very quickly after the event, or, if that is not possible because of the time to process measurements, to wait until the CH and the other sensors bunch up again at their destination.

Figure 10 shows the large deviation bound of the error probability as a function of time for a static or mobile CH to collect one packet of data from five mobile sensors. It shows good agreement with the results in Figure 9, which shows the expected energy consumption as a function of time for a static or mobile CH to collect one packet of data from five mobile sensors.

Figure 10

Calculation of the large deviation bound of the error probability when the collection of data from the five mobile sensors begins at time t. The cases considered are when the transmission radius of each sensor is $r=1$ or $r=3\mathrm{\hspace{0.17em}\hspace{0.17em}}$ with $p_m=0.10$ and $p_c=0.05$ and all sensors move according to symmetric or asymmetric CRWs.

Figure 11 shows the expected error probability as a function of time for a static or mobile CH to collect one packet of data from five mobile sensors. The same comments made previously about the effects of the mobility of the CH, and the effects of symmetric and asymmetric CRWs, apply here. The values of the probabilities of the nodes locations used to calculate these expected error probabilities were obtained in this case by simulations of the CRW.

Figure 11

Expected error probability when the collection of data from the five mobile sensors begins at time t. The cases considered are when the transmission radius of each sensor is $r=1$ or $r=3$ with $p_m=0.10$ and $p_c=0.05$ and all sensors move according to symmetric or asymmetric CRWs. The curves in this figure were generated from 5 million runs of a simulation of the detection process for each setting of the mobility parameters. The values of the probabilities of the nodes locations for the detection process were obtained by simulations of the CRW.

9. Conclusions

In this paper, the solution to the finite state space CRW was provided and its statistical behavior was studied both analytically and numerically. As an illustration of the application-specific performance measures it can help address, we studied the impact of motion on the error probability of the final decision at the CH and the energy required to collect the decisions from all relevant sensors. Thus the temporary cluster head can decide the most appropriate time to call for data reports to help it make decisions within the allowed time frame and energy budget. In future research, we will study the impact of motion on the energy required to gather data and the error probability of the final decision in complex mobile wireless sensor networks.