Space-time Coordinated Distributed Sensing Algorithms for Resource Efficient Narrowband Target Localization and Tracking

Abstract

Distributed sensing has been used for enhancing signal to noise ratios for space-time localization and tracking of remote objects using phased array antennas, sonar, and radio signals. The use of these technologies in identifying mobile targets in a field, emitting acoustic signals, using a network of low-cost narrow band acoustic micro-sensing devices randomly dispersed over the region of interest, presents unique challenges. The effects of wind, turbulence, and temperature gradients and other environmental effects can decrease the signal to noise ratio by introducing random errors that cannot be removed through calibration. This paper presents methods for dynamic distributed signal processing to detect, identify, and track targets in noisy environments with limited resources. Specifically, it evaluates the noise tolerance of adaptive beamforming and compares it to other distributed sensing approaches. Many source localization and direction-of-arrival (DOA) estimation methods based on beamforming using acoustic sensor array have been proposed. We use the approximate maximum likelihood parameter estimation method to perform DOA estimation of the source in the frequency domain. Generally, sensing radii are large and data from the nodes are transmitted over the network to a centralized location where beamforming is done. These methods therefore depict low tolerance to environmental noise. Knowledge based localized distributed processing methods have also been developed for distributed in-situ localization and target tracking in these environments. These methods, due to their reliance only on local sensing, are not significantly affected by spatial perturbations and are robust in tracking targets in low SNR environments. Specifically, Dynamic Space-time Clustering (DSTC)-based localization and tracking algorithm has demonstrated orders of magnitude improvement in noise tolerance with nominal impact on performance. We also propose hybrid algorithms for energy efficient robust performance in very noisy environments. This paper compares the performance of hybrid algorithms with sparse beamforming nodes supported by randomly dispersed DSTC nodes to that of beamforming and DSTC algorithms. Hybrid algorithms achieve relative high accuracy in noisy environments with low energy consumption. Sensor data from a field test in the Marine base at 29 Palms, CA, were analyzed for validating the results in this paper. The results were compared to “ground truth” data obtained from GPS receivers on the vehicles.

Keywords

Distributed sensor network beamforming clustering power usage target tracking

1. Challenges in Distributed Sensing in Noisy Environments

The surface layer of the atmosphere is driven by the heat flux from the sun and, at night time, its re-radiation into space, the latent heat contained in water vapor, the forces of gravity, and the forces of the prevailing geotropic wind. Swanson [1] has studied the effects of atmospheric dynamics to conclude that wind noise is the most significant performance limitation on acoustic sensors as turbulence in the atmosphere tends to scatter and refract sound rays. Real-time distributed micro-sensor networks are also very limited in resources. There is often a very limited amount of battery power and limited communications bandwidth. However, better performance comes at the expense of increased power consumption, which may render the sensor network impractical should this consumption exceed battery capacity too quickly. Thus sensor network design is often evaluated in terms of tradeoffs between performance and resource consumption with the goal of maximizing the effectiveness of the sensor network.

When sensor networks are embedded in real environments, ambient noise levels can adversely affect the performance of these networks. This has driven the development of techniques to improve the signal to noise ratio. Attenuation of the signal with distance leads to a decrease in signal to noise ratio. The purpose of this work is to examine the performance of distributed sensing algorithms for acoustic-based target localization and tracking in the presence of noise. The algorithms employed include beamforming, an example of a centralized processing system, dynamic space-time clustering (DSTC) an example of a distributed processing system, and hybrid algorithms that combine the salient features of the two to enhance performance and resource utilization.

1.1 Experimental Objectives

We compare the performance of three power-aware tracking algorithms as they respond to varying signal-to-noise ratios (SNR). Autonomous sensor networks in the field must be operated to maximize their life. As a result, they must be power-stingy. Simultaneously, environments produce significant noise in sensor readings. The sensor network must be robust to sensor noise. Finally, in the presence of both power-stingy algorithms and environmental noise the sensor network will be expected to produce accurate target tracks for the end-users. Our experiments compare a target tracking algorithm that uses AML beam-forming [2], the DSTC algorithm [3], and a hybrid algorithm that uses both beamforming and DSTC.

Tracking using the AML beamforming algorithm is accomplished with nodes that contain multiple acoustic sensors set at regular intervals in a circular pattern. Acoustic signals from a target that arrives at these sensors are compared by the node according to the phase shifts produced by the geometry of the sensors' positions to determine the direction of arrival of the acoustic signal to the node. The resulting rays from two or more Beamforming nodes can then be combined to find the intersection point and therefore the position of each target. Over time, these points are combined into target tracks.

Tracking using the DSTC algorithm is accomplished using a dense distributed sensor network composed of simple acoustic sensors with processors. Acoustic signals from a target arrive at a sensor that exchanges closest point of approach information with a dynamic cluster of sensors determined by a space-time window. The node with the peak signal intensity is selected as the leader and uses a linear regression technique to compute the estimated target velocity. The target is localized using the weighted centroid of the cluster. The computed information is compared to a list of known target tracks that have been passed through the network to determine whether a track can be matched. Either a track is initiated (if no match exists) or continued and information is propagated along the direction of target motion so that the process can be repeated by other nodes in the network.

The advantage of AML beamforming over DSTC is that it requires far fewer nodes to cover an area. Its main disadvantages are its high power cost compared to DSTC and its inability to distinguish between more than 4 targets simultaneously [4].

We hypothesized that the hybrid algorithm would be able to combine the accuracy, robustness to noise and the power-greediness of the two individual methods to produce better results than either the AML beamforming or DSTC tracking algorithms alone.

1.2 Paper Organization

In Section 2 we review fundamental concepts from blind beamforming, AML beamforming, DSTC and our previous experimental results with these algorithms. In Section 3 we describe our experimental setup, methods and data analysis. In Section 4 we present our experimental results and discuss them in the context of our experimental setup. Finally in Section 5 we present future directions of research and final conclusions.

2. Preliminaries

In this section we review the mathematical formulation of the beamforming and DSTC algorithms.

2.1 Beamforming

Beamforming [4] is a method of estimating the direction of arrival of a wavefront emitted by a target based on the space-time acoustic data acquired by each sensor node p (p = 1, … P). The data received by each sensor is discretized to yield a time series vector [x_p(n)] of size N, i.e., n = 0, 1, …, N − 1. In general, there may be more than one target source emitting the acoustic signals. Assuming that there are m = 1, 2, …, M acoustic sources present and that signal from the m^th source arrives from the direction θ^(m) (with respect to a common but arbitrary reference direction). Since each sensor has different spatial coordinates with respect any acoustic emitter, the received signal samples at each sensor node can be expressed as,

x_{p} (n) = \sum_{i = 1}^{M} s^{(m)} (n - τ_{p}^{(m)}) + w_{p} (n)

where, s^(m) is the acoustic signal emitted by the m^th source and w_p(n) is the additive white Gaussian noise component.

τ_{p}^{(m)}

is the differential propagation delay experienced by the m^th signal at the p^th sensor node with respect to the first node and

τ_{1}^{(m)}

for m = 1, …, M. Set of differential delays

{τ_{p}^{(m)}}

are associated with the direction-of-arrival (DOA) θ^(m) of the wavefront from source m. It is assumed that all M acoustic signals are uncorrelated with each other as well as with the additive noise. The N-point discrete Fourier transforms (DFT) of the N received signal samples x_p(n) can now be written as,

X_{p} (k w_{0}) = \sum_{i = 1}^{M} S^{(m)} (k w_{0}) e^{j w_{0} τ_{p}^{(m)}} + W_{p} (k w_{0}), k = 0, 1, \dots, N - 1

where, w₀ is the fundamental frequency of the received data. At a particular kw₀ ¹ the received signal vector at P sensor nodes can be written as,

[\begin{matrix} X_{1} (k) \\ X_{2} (k) \\ ⋮ \\ X_{P} (k) \end{matrix}] = [\begin{matrix} d_{1}^{(1)} (k) & d_{1}^{(2)} (k) & \dots d_{1}^{(M)} (k) \\ d_{2}^{(1)} (k) & d_{2}^{(2)} (k) & \dots d_{2}^{(M)} (k) \\ ⋮ & ⋮ & ⋮ \\ d_{P}^{(1)} (k) & d_{P}^{(2)} (k) & \dots d_{P}^{(M)} (k) \end{matrix}] [\begin{matrix} S^{(1)} (k) \\ S^{(2)} (k) \\ ⋮ \\ S^{(M)} (k) \end{matrix}]

Above equation may be expressed more concisely in the matrix form as,

X (k) = A (k) S (k) + W (k), k = 0, 1, \dots N - 1

where,

X (k) = [X_{1} (k), X_{2} (k), \dots, X_{P} (k)]^{T}

is the k^th frequency component of the received signal vector across the P sensor nodes, and

A (k) = [d_{1}^{(1)} (k), d_{1}^{(2)} (k), \dots, d_{P}^{(M)} (k)]

such that,

d^{(m)} = [d_{1}^{(m)}, d_{2}^{(m)}, \dots, d_{p}^{(m)}]

d^(m) is also known as the steering vector and its elements give the amount of phase shift experienced by the m^th wavefront across the sensor nodes. These phase shifts at frequency kw₀ are given by,

d_{p}^{(m)} = e^{- j 2 π k w_{0} τ_{p}^{(m)} / N} = e^{- j θ^{(m)}}

In beamforming, one node is chosen to be the processing node, P. This node may be chosen arbitrarily, though power considerations may dictate that the node with the largest amount of battery power remaining be chosen instead for processing the data. The discrete frequency domain data vector, X_i(k), k = 1, …, N/2 is communicated to the processing node P by each node i, 0 ≤ i ≤ N, i ≠ P, in the sensor network. The processing node establishes the relative fractional time delays between the data acquired by each node i ≠ P and the data acquired by node P using correlation and interpolation methods. The processing node has to execute the beamforming algorithm to estimate the DOAs of the M independent source. In this paper, we utilize the approximate maximum likelihood (AML) algorithm for estimating θ₁, …, θ_M from the received data X(k), k = 1, 2, N/2. The AML algorithms maximizes likelihood function which is given by the joint conditional probability density function p(X(1), …, X(N/2) |θ₁, …, θ_M). Since all X have Gaussian distribution, it is more convenient to work with the log-likelihood function instead. The log-likelihood function L(Θ) after dropping irrelevant terms is given by,

L (Θ) = - {∥ X (k) - d (k) S (k) ∥}^{2}

and the AML estimate of the source angle and source signal is given by

max_{Θ} L (Θ) = min_{θ_{S}, S} \sum_{k = 1}^{N} {∥ X (k) - d (k) S (k) ∥}^{2},

For fixed _S, the estimated source signal can be given by the least-squares solution S(k) = d∗(k)X(k), where d∗(k) = (d(k)^Hd(k)⁻¹d(k)^H). By substituting this estimated source signal back in the log-likelihood function, we obtain the AML estimate of _S given by

max_{θ_{S}} L (θ_{S}) = max_{θ_{S}} \sum_{k = 1}^{N} {∥ d (k) d^{*} (k) X (k) ∥}^{2} .

The AML beamforming algorithm is described fully in [2] and [6]. There are computationally efficient methods for using AML beamforming. These are described in [6]. For a complete exposition on beamforming, see [2].

2.2 Dynamic Space-time Clustering

Dynamic Space-time Clustering (DSTC) is a distributed processing algorithm based on the closest point of approach (CPA) of the target to each of the sensors in the network [3], [7], [8]. DSTC is based on the concepts of a space-time neighborhood, a dynamic window, and an event. A space-time neighborhood centered on the space-time point ( $({\bar{x}}_{0}, t_{0})$ ) is the set of space-time points,

N ({\bar{x}}_{0}, t_{0}) = {(\bar{x}, t) | | \bar{x} - {\bar{x}}_{0} | \leq Δ x and | t - t_{0} | \leq Δ t} .

The quantities Δx and ∧t define the size of the neighborhood. The space-time window contains all the data that was measured within a distance Δx and Δt around ${\bar{x}}_{0}$ and within the time interval t₀ ± Δt. We can define a dynamic window around a moving point, $\bar{g} (t)$ , as

w (t) = {(x, t) | | {\bar{x}}_{0} - \bar{g} (t_{0}) | \leq Δ x and | t - t_{0} | \leq Δ t} .

Ideally, if $\bar{g} (t)$ was the trajectory of the target, we would analyze time-series data from sensors in the window, N_c = w(t_e) to determine information about the target at time t_e.

The target trajectory $\bar{g} (t)$ is unknown. It is, in fact, what we want to determine. We therefore look at CPA events that occur within a single space-time neighborhood. A CPA event e_ij is defined for platform i occurring at the CPA time, t_j. The space-time coordinates of the event are $({\bar{x}}_{i} (t_{j}), t_{j})$ where ${\bar{x}}_{i} (t_{j})$ is the trajectory of platform i.

Nodes located within a given space-time window form a cluster. The space-time size of the window is held constant. The maximum possible spatial size of the window is constrained by the transmission range of the sensors. Each node contains a buffer for its own CPA events, and a buffer for CPA events transmitted by its neighbors. We make the assumption that sensor energy increases as distance from the source decreases. This is a reasonable assumption for acoustic and seismic sensors. The CPA event is therefore assumed to occur when there is a peak in sensor energy. The amplitude of the event, a_ij, is defined as the amplitude of the corresponding peak. In order to filter out noise, reflection, or other spurious features, we count only peaks above a threshold and do not allow two events on a single platform within the same space-time window. If data from multiple sensors are available, they must be integrated to determine a single peak time for the event.

For an event e_ij, we analyze data from platforms in the neighborhood $N ({\bar{x}}_{i} (t_{i}), t_{i})$ . We define the set of platforms that contain events in this space-time neighborhood as the cluster of platforms associated with event e_ij. These definitions apply to both stationary and moving platforms and seamlessly integrate both types. They can be used to determine target velocity as long as the platform trajectories are known and the platform speed is small compared to the propagation speed of the energy field measured by the sensors. Platform locations can be determined by GPS and, for stationary platforms, additional accuracy can be achieved by integrating GPS signals over time. Other localization methods can be used if GPS units are not available [9].

We have developed an algorithm that limits data processing to the platforms closest to the trajectory of the target rather than processing each CPA event. It evenly spreads the processing out over the space-time range of the target trajectory. All of the platforms within the neighborhood of an event are assumed to be capable of communicating with each other.

Let N be the number of nodes in the sensor network. In this case, the acoustic time-series is abstracted by finding the point of maximum intensity in the signal acquired by a particular node i. If this intensity is above a threshold, a CPA packet for that particular node is constructed. This packet is then sent to all sensors j « N (if N is sufficiently large), in the “local neighborhood” of sensor i. This neighborhood defines a space-times window around each sensor node that includes all sensors whose distance is below a threshold and whose readings occur at about the same time. Following the transmission of the packet, each sensor that detected a CPA waits a certain amount of time (the Δt). After that portion of time expires, each node checks their queue of CPA packets acquired from the local neighborhood. If the intensity of that node is the largest compared to the others in the queue, that node is elected to do the processing. In this way, processing is distributed across the sensor network in the sense that the node closest to the target should be the one processing the data. The estimated position of the target is found by taking a weighted centroid (with the signal intensity as the weight) of the positions of all sensors that detected a CPA. The velocity of the target is computed using a weighted regression technique that gives both the magnitude of the target's velocity and its direction. Using this information, the node that performed the processing can propagate the track information acquired by the nodes in the targets estimated direction. It should be noted that fewer than five CPA points could severely bias the results. Another problem occurs if a node receives two tracks whose information is contradictory with respect to the direction of propagation. A method called lateral inhibition is used in this case to eliminate the contradictory tracks.

2.2.1 Target Velocity and Position Estimation

Models of human perception of motion may be based on the spatio-temporal distribution of energy detected through vision [10], [11]. Similarly, the network detects motion through the spatio-temporal distribution of sensor energy.

We extend techniques found in [12] and adapt them to find vehicle velocity estimates from acoustic sensor signals. The definitions shown below are for one temporal and two spatial dimensions, $\bar{x} = (x, y)$ , however their extension to three spatial dimensions is straightforward.

The platform location data from the CPA event cluster can be organized into the following sets of observations:

{(x_{0}, t_{0}), \dots, (x_{n}, t_{n})},

and,

{(y_{0}, t_{0}), \dots, (y_{n}, t_{n})},

where (x₀, y₀) is the location of event k_ij, which contains the largest amplitude CPA peak in the cluster. We redefine the times in the observations so that t₀ = 0 where t₀ is the time of CPA event k_ij.

We weight the observations based on the CPA peak amplitudes on the assumption that CPA times are more accurate when the target passes closer to the sensor to give:

{(x_{0}, t_{0}, w_{0}), \dots, (x_{n}, t_{n}, w_{n})}

and,

{(y_{0}, t_{0}, w_{0}), \dots, (y_{n}, t_{n}, w_{n})},

where w_i is the weight of the i^th event in the cluster. This greatly improved the quality of the predicted velocities. We defined the spatial extent of the neighborhoods so nodes do not span more than a few square meters and vehicle velocities are approximately linear. Under these assumptions, we can apply least square linear regression to obtain the following equations [13]:

\begin{aligned} x (t) & = v_{x} t + c_{1} \\ y (t) & = v_{y} t + c_{2}, \end{aligned}

where,

\begin{aligned} v_{x} & = \frac{\sum_{i} t_{i} \sum_{i} x_{i} - \sum_{i} w_{i} \sum_{i} x_{i} t_{i}}{(\sum_{i} t_{i})^{2} - \sum_{i} w_{i} \sum_{i} t_{i}^{2}} \\ v_{y} & = \frac{\sum_{i} t_{i} \sum_{i} y_{i} - \sum_{i} w_{i} \sum_{i} y_{i} t_{i}}{(\sum_{i} t_{i})^{2} - \sum_{i} w_{i} \sum_{i} t_{i}^{2}} \end{aligned}

and the position

\bar{x} (t_{0}) = (c_{1}, c_{2})

. The space-time coordinates of the target for this event are

(\bar{x} (t_{0}), t_{0})

This simple technique can be augmented to ensure that changes in the target trajectory do not degrade the quality of the estimated track. The correlation coefficients for the velocities in each spatial dimension, (r_x, r_y), can be used to identify large changes in vehicle direction and thus limit the CPA event cluster to include only those nodes that will best estimate local velocity. Assume that the observations are sorted as follows:

o_{i} < o_{j} \Rightarrow | t_{i} - t_{0} | < | t_{j} - t_{0} |,

where o_t is an observation containing a time, location and weight and t₀ is the time of the event k_ij. The velocity elements are computed once with the entire event set. After this, the final elements of the list are removed and the velocity is recomputed. This process is repeated while at least five CPAs are present in the set and subsequently the event subset with the highest velocity correlation is used to determine velocity. Fewer than five CPA points could bias the computed velocity and thus render our approximation useless. We summarize the DSTC process in Figure 1.

Figure 1

Flowchart of the processing performed at any given node to allow distributed target tracking.

Dynamic Space-Time Clustering has been implemented in [14], [15], [8], [16]. Data routing is done via the diffusion routing approach described in [17], which supports communications based on data attributes instead of node network addresses. Communications can be directed to geographic locations or regions.

2.3 Previous Experimental Results

As part of the DARPA SensIT program, we fielded an operational systems at the Marine Corps Air Ground Combat Center, 29 Palms, CA, in coordination with multiple universities and industrial partners. Details of the experiments are discussed in [16]. Acoustic data were taken from a variety of ground vehicles including high mobility, multipurpose wheeled vehicles (HMMWVs), dragonwagons, five-ton trucks, light armored vehicles, and tanks.

Sound samples obtained in these experiments are used in the experiments described in Section 3. The software used in the field for computing targets with the DSTC algorithm is also used with a simulation in these experiments.

3. Experimental Design

In this section, we describe our experimental setup. All experiments were run in simulation on an Intel 686 processor using Redhat Linux. DSTC algorithm was run using the software that was used in field testing at 29 Palms. AML beamforming source code was provided (in Matlab) by the University of California Los Angeles.

Figure 2

Armored Personnel Carrier

3.1 Beamforming Implementation: Scenario I

The first tracking system evaluated uses beamforming only. Three beamforming nodes are placed on the periphery of a circular region such that their sensor ranges overlap sufficiently to fully cover a region of 80m by 80m. The beamforming nodes detect a target entering the region and track it by exchanging their Direction of Arrival (DOA) results and triangulating to find the targets current position.

An acoustic data file obtained at 29 Palms was provided by UCLA along with software to transform the signal to obtain the correct DOA for use in simulation. The portion of the signal used was sufficiently small to require attenuation to adjust for the relative distance of the target to the signal. We attenuated the amplitude of the signal by a factor proportional to the distance of the simulated signal source to the microphone. Gaussian white noise was added to the signal. This allowed us to simulate the energy loss associated with the spread of the sound signal.

3.2 DSTC Implementation: Scenario II

The second scenario used DSTC nodes only for tracking. It consists of 100 DSTC nodes arrayed in a rectangular grid. We assumed the grid to occupy 80m × 80m. The scenario assumes some of the DSTC nodes inactive and some active. Inactive nodes are conserving energy and wake up periodically to check for messages. Active nodes periodically become inactive (sleep) to conserve energy. If a target enters the field, active nodes may detect the target and attempt to track it. These alerted nodes continue to stay active for an extended period of time, continuously attempting to gather more sensor data; form ad hoc clusters to localize the target position and velocity, and form tracks; and alert those nodes that are inactive but may soon become active. Nodes which are inactive are not able to participate until their predefined wake time arrives, at which point they may begin receiving data from their own sensors and information from other active nodes in their regions. After a set period of no target activity being detected, the nodes return to their active/inactive cycle. We expect this scenario to have less complete coverage than beamforming alone due to lost connections and sensor data during the inactive periods—but to be more accurate and less subject to noise interference.

Figure 3

Three beamforming Node Tracking with Signal to Noise Ratio of 10 dB. Large hexagonal shapes are the Beamforming nodes. Dark blue dots are the estimated positions of the targets. Red dots are the actual target path. Dark line emanating from one of the Beamforming nodes is a DOA estimate

3.3 Hybrid Implementation: Scenario III

We formulated a hybrid tracking algorithm to emphasize the strengths and mitigate the limitations of the constituent DSTC and beamforming algorithms. It consists of 100 DSTC nodes arrayed in a rectangular 80m × 80m grid with one beamforming sentry node in the center acting as an always awake sentry. The scenario begins with all DSTC nodes inactive (asleep) and the single Beamforming node activate. If a target enters the Beamforming nodes detection range it determines the direction to the target and sends out a wakeup call to the DSTC nodes along that beam. The awakened DSTC nodes in turn, perform target tracking as previously described and then return to sleep. As the target continues to move through the field, the beamforming node continues to wake the next set of DSTC nodes in turn until the target passes beyond detection range, with the awakened DSTC nodes at each point in time adding their inputs to the progressing target track. It is assumed that this hybrid may allow us to track targets more accurately and efficiently as only those DSTC nodes actually needed to track a particular target would be activated.

3.4 Data Analysis

All nodes, beamforming or DSTC, will be assumed to contain the same CPU running at the same clock speed and to be communicating using the same radio.

Figure 4

Scenario III: A single beamforming node acts as a sentry to awaken sleeping DSTC nodes.

To estimate the energy consumed while tracking targets, we estimated the amount of energy used by each node type (beamforming or DSTC). Energy consumed by the code was estimated by multipling the total time of execution by the Power draw of the CPU. Power draw was estimated by the current load on a known CPU running at a set voltage while the beamforming and DSTC programs were running and multiplying the voltage and current [5] thus obtained according to the familiar equation:

P = V I .

The value of P thus obtained and used in this experiment is 2.478 Joules/second.

Broadcast energy consumed is estimated by multiplying the Energy consumed per byte broadcast by the total number of bytes broadcast. The Energy per byte is assumed to be 0.36e-4 Joules/byte [18].

Tracking accuracy is determined by calculating the variance of the distance errors d_i at n times t between the estimated track locations and actual corresponding locations of the target.

V = \frac{1}{n - 1} \sum_{i} d_{i}

Track coverage is determined by calculating the portion of the actual target path time that was covered by a track.

4. Results and Discussion

Tracking quality using beamforming only began to degrade as the background noise level increased. This result is not unexpected, since [6] notes that AML beamforming works well in high to medium SNR situations. While the track variance for the Scenarios II and III never rose above 5 m²; for Scenario I it was over 5000 m² when SNR was 40dB. Results are summarized in Tables 1 and Tables 2.

Table 1
Comparison of Track Variance and Track Coverage for three Tracking Systems: DSTC Node sleep time is held constant at 60%. SNR is varied

SNR (dB) R² Value Point Variance (m²) Track Coverage (%/100)

Scenario I

0 0.34509 7057.25 1

5 0.31575 6438.31 1

10 0.27082 5717.78 1

15 0.2066 5429.9 1

20 0.13416 2600.95 1

25 0.36695 1701.57 1

30 0.6104 825.62 1

35 0.88256 157.9 1

40 0.951 61.22 1

Scenario II

0 0.99717 2.59 0.759

5 0.99642 3.34 0.787

10 0.99673 2.83 0.709

15 0.99597 2.93 0.511

20 0.99638 3.34 0.513

25 0.99646 3.02 0.474

30 0.99679 3.06 0.535

35 0.99664 3.06 0.357

40 0.99621 3.33 0.442

Scenario III

0 0.99783 2.01 0.777

5 0.99651 3.41 0.762

10 0.99736 2.43 0.786

15 0.99738 2.35 0.776

20 0.99726 2.45 0.769

25 0.99721 2.56 0.76

30 0.9968 2.93 0.738

35 0.99712 2.8 0.711

40 0.99687 3.19 0.686

Table 2

Comparison of Track Variance and Track Coverage for three Tracking Systems: SNR = 40dB. DSTC Node sleep time is varied

Sleep Proportion	R² Value	Point Variance (m²)	Track Coverage (%/100)
		Scenario I
0	0.951	61.22	1
		Scenario II
0	0.99798	1.86	0.804
0.2	0.99766	2.13	0.813
0.3	0.99741	2.44	0.774
0.4	0.99707	2.8	0.727
0.5	0.99675	3.02	0.663
0.6	0.99621	3.33	0.442
0.7	0.95424	3.74	0.308
		Scenario III
0	0.99798	1.86	0.804
0.2	0.99796	1.87	0.804
0.3	0.99775	2.06	0.804
0.4	0.99752	2.25	0.79
0.5	0.99713	2.68	0.751
0.6	0.99687	3.19	0.686
0.7	0.99676	3.24	0.666

Because Scenarios II and III were nearly equal in track variation, we will have to turn to Track Coverage to distinguish between their performances.

As seen in the Figure 5, the addition of a single beamforming nods to a field of DSTC nodes can significantly improve the percentage of the track that they are able to cover. Improvements are caused by the sentry nod, which can give advanced warning to the DSTC nodes at the edge of the field at the beginning of the target path, thus allowing them to remain awake to track the target.

Figure 5

Pure beamforming vs. Hybrid beamforming

4.1 Energy Usage Comparison

We analyzed the energy use of the sensor system at several different SNR values and for different sleep percentages (in the hybrid and pure DSTC implementation only). These results are summarized in Table 3. It is clear that for fixed SNR, the quality of tracking in Scenario II and in the Scenario III suffered as the sleep percentage of the nodes increased.

Table 3
For sleep percent fixed at 60%, we compare per node energy usage for the three different scenarios

SNR (dB) CPU Run Time (s) CPU Energy Per Node (J) Broadcast Energy Per Node (J) Total Energy Per Node (J)

Scenario I

0 162.08 401.63 0.29 401.91

5 162.07 401.62 0.29 401.91

10 161.84 401.05 0.29 401.34

15 161.91 401.2 0.29 401.49

20 161.77 400.88 0.29 401.16

25 161.59 400.41 0.29 400.69

30 161.39 399.94 0.29 400.22

35 161.34 399.79 0.29 400.08

40 161.8 400.94 0.29 401.22

Scenario II

0 19.83 49.13 0.03 49.16

5 20.23 50.13 0.03 50.16

10 19.44 48.18 0.03 48.21

15 17.1 42.38 0.02 42.4

20 16.91 41.9 0.02 41.92

25 16.38 40.6 0.02 40.62

30 16.88 41.83 0.02 41.85

35 15.5 38.41 0.01 38.42

40 16.54 40.98 0.02 41

Scenario III: Beamforming Node

0 161.56 400.36 0.29 400.64

5 161.68 400.64 0.29 400.93

10 161.51 400.23 0.29 400.52

15 161.29 399.69 0.29 399.97

20 161.34 399.81 0.29 400.1

25 161.06 399.11 0.29 399.39

30 161.07 399.13 0.29 399.41

35 160.99 398.92 0.29 399.21

40 161.1 399.2 0.29 399.49

Scenario III: DSTC Node

0 34.17 84.66 0.04 84.7

5 34.92 86.54 0.04 86.57

10 32.85 81.4 0.03 81.44

15 32.08 79.5 0.03 79.53

20 32.53 80.61 0.04 80.65

25 27.14 67.26 0.04 67.3

30 24.16 59.87 0.04 59.91

35 23.57 58.41 0.04 58.46

40 23.12 57.29 0.04 57.34

Table 4

For SNR fixed at 40dB, we compare per node energy usage for the three different scenarios while varying DSTC node sleep proportion

Sleep Proportion	CPU Run Time (s)	CPU Energy Per Node (J)	Broadcast Energy Per Node (J)	Total Energy Per Node (J)
		Scenario I
0	161.8	400.94	0.286704	401.22
		Scenario II
0	32.72	81.08	0.02	81.1
0.2	28.16	69.79	0.02	69.81
0.3	26.4	65.42	0.02	65.44
0.4	24.55	60.84	0.02	60.87
0.5	21.75	53.89	0.02	53.92
0.6	16.54	40.98	0.02	41
0.7	12.23	30.3	0.02	30.31
		Scenario III: Beamforming Node
0	161.1	399.2	0.29	399.49
0.2	161.1	399.2	0.29	399.49
0.3	161.1	399.2	0.29	399.49
0.4	161.1	399.2	0.29	399.49
0.5	161.1	399.2	0.29	399.49
0.6	161.1	399.2	0.29	399.49
0.7	161.1	399.2	0.29	399.49
		Scenario III: DSTC Node
0	32.72	81.08	0.04	81.12
0.2	29.48	73.05	0.04	73.09
0.3	28.18	69.83	0.04	69.87
0.4	26.81	66.44	0.04	66.48
0.5	25.21	62.48	0.04	62.53
0.6	23.12	57.29	0.04	57.34
0.7	21.62	53.58	0.05	53.62

The lifespan of an operational network depends on the energy use per node. To compute the per node energy cost in Scenarios I and II, we divide the total energy used by the number of nodes. For example, consider the total energy used in tracking with a 40dB SNR and DSTC nodes sleeping 60% of the time. Then the per node energy cost for Scenario I is 401.22J, the per node energy cost for Scenario II is 41.0J. For Scenario III we report the per node energy for both the beamforming node and a representative DSTC node. Differences in energy use can be attributed to the simplicity of the DSTC algorithm and the decreased communications overhead of local cluster communications for track formation. These results are summarized visually in Figure 7. Note also that the amount of total energy used by the network in tracking the target was always less in the beamforming scenario. This can be explained by the fact that Scenario I uses only three sensor nodes, while Scenarios II and III use 100 and 101 nodes respectively.

Figure 6

Charts summarizing the results of Tables 1 and 2.

Figure 7

Energy usage for target tracking.

5. Conclusion and Future Directions

In our simulations, the DSTC based localization is more noise tolerant than the beamforming localization. This is due, in large part, to the fact that the target is much closer to the sensor when the localization is performed. Hence the DSTC nodes are not as affected by signal attenuation. DSTC nodes use less power on a per node basis, but require significantly higher sensor density and thus require a higher total energy. The hybrid algorithm we proposed used less per node energy than Scenario I but more than Scenario II. The hybrid algorithm also used less total energy than the pure DSTC algorithm. This algorithm showed more robustness to noise than pure beamforming, however this result is potentially misleading. Because the beamformer was more likely to get an incorrect (and random) direction of arrival in the presence of noise, more DSTC sensor nodes were likely to get woken up, thus ensuring than the target was accurately tracked. This result while useful is unfortunately spurious and must be treated with caution when used for designing fieldable algorithms.

In our simulations, the noise level at each sensor is roughly constant but the signal level at the sensor node varies with the distance between the signal source and the sensor node. Beamforming improves signal-to-noise ratios by increasing the directional sensitivity of the sensor node. Only noise sources in the same direction as the signal source contribute to the noise level. DSTC nodes are sensitive to noise sources in all directions. However, the DSTC array is dense enough that the signal source comes close enough to enough DSTC nodes that the signal is stronger then the noise. For beamforming to achieve similar performance to DSTC, it would be necessary to use a dense array of beamforming nodes, thus negating the power savings associated withing using only three beamforming nodes.

Furture experiments are required to evaluate appropriate hybridization to derive maximal benefit from both beamforming and DSTC algorithms. These experiments may include evaluating:

DSTC sentry nodes (ad hoc) with sleeping beamforming node(s),

Traffic determined tracking (BF/hybrid until more than 4 targets then DSTC),

Hybrid localization (DSTC nodes also consider received beamforming DOA's in target localization), and

Power aware reconfiguration.

An analytic model of the DSTC algorithm's handling of the signal-to-noise ratio is needed to predict the theoretical limits of the DSTC algorithm to validate our conclusions. Our results for this paper indicate the benefit that the use of hybrid algorithms is useful for creating power stingy algorithms for robust target tracking. Further research must be done to identify the best hybridization of beamforming and DSTC algorithms for collaborative signal processing.

Footnotes

1

Henceforth, ω₀ will be dropped from the equations.

References

Swanson

D. C.

, “Environmental effects,” in Frontiers in Distributed Sensor Networks, vol. 11, pp. 201–212, 2004. The CRC Press, Boca Raton, FL, USA.

Chen

J. C.

and Yao

, “Beamforming,” in Frontiers in Distributed Sensor Networks, vol. 56, pp. 1069–1106, 2004. The CRC Press, Boca Raton, FL, USA.

Phoha

Jacobson

Friedlander

, and Brooks

, “Sensor network based localization and target tracking through hybridization in the operational domains of beamforming and dynamic space-time clustering,” in Proceedings of Globecom 2003, pp. 2952–2956, 2003.

Yao

Hudson

Reed

C. W.

Chen

, and Lorenzelli

, “Blind beamforming on a randomly distributed sensor array system,” IEEE Journal On Selected Areas In Communications, vol. 16, no. 8, pp. 1555–1567, October 1998.

Brooks

E. R. S.

III Brooks

R. R.

, and Keller

, “A comparison of tracking algorithms using beamforming and cpa methods with an emphasis on resource consumption vs. performance,” IEEE Trans. Aerospace and Electronics, Manuscript submitted for publication, 2004.

Yip

Chen

J. C.

Hudson

R. E.

, and Yao

, “Numerical implementation of the aml algorithm for wideband doa estimation,” in Proceedings of the 48th SPIE Conference, pp. 2952–2956, 2003.

Friedlander

Griffin

Jacobson

Phoha

, and Brooks

R. R.

, “Dynamic agent classification using an ad hoc mobile acoustic sensor network,” EURASIP J. Applied Signal Processing, vol. 4, pp. 371–377, March 2003.

Friedlander

and Phoha

, “Semantic information fusion of coordinated signal processing in mobile sensor networks,” J. High Performance Computing, Special Issue on Sensing vol. 16, no. 3, pp. 235–242, 2002.

Bulusu

J. H. N.

and Estrin

, “Gps-less lowcost outdoor localization for very small devices,” IEEE Personal Communication Magazine, vol. 7, no. 5, pp. 28–34, 2000.

10.

Adelson

and Bergan

, “Spatiotemporal energy modes for the perception of motion,” Journal of the Optical Society of America (A), vol. 2, no. 2, pp. 284–299, 1985.

11.

Adelson

E. H.

, “Mechanisms for motion perception,” Optics and Photonics, vol. 46, no. 1, pp. 2952–2956, 1991.

12.

Hellebrant

Mathar

, and Scheibenbogen

, “Estimating position and velocity of mobiles in a cellular radio network,” IEEE Trans. Vehicular Technology, vol. 46, no. 1 pp. 65–71, 1997.

13.

Press

W. H.

Teukolsky

Vetterling

, and Flannery

, Numerical Recipes in C. Cambridge, England: Cambridge University Press, 1992.

14.

Brooks

R. R.

and Griffin

, “Traffic model evaluation of ad hoc target tracking algorithms,” J. High Performance Computing, Special Issue on Sensing, vol. 16, no. 3, pp. 221–234. 2002.

15.

Brooks

R. R.

and Griffin

, and Friedlander

, “Self-organized distributed sensor network target tracking,” J. High Performance Computing, Special Issue on Sensing, vol. 16, no. 3, pp. 207–220, 2002.

16.

Brooks

R. R.

Ramanathan

, and Sayeed

, “Distributed target tracking and classification in sensor networks,” Proceeding of the IEEE, vol. 91, no. 8, pp. 1163–1171. 2003.

17.

Heideman

Silva

Intanagonwiwat

Estrin

, and Ganesan

, “Building efficient wireless sensor networks with low-level naming,” in Proc. Sym. on Operating Sys. Princ., pp. 146–159, October 2001.

18.

Technologies

. “Sc-pa series transceiver module design guide.” Available: http://www.linxtechnologies.com/ldocs/pdfs/scpamanual.pdf

SNR (dB)	R² Value	Point Variance (m²)	Track Coverage (%/100)
		Scenario I
0	0.34509	7057.25	1
5	0.31575	6438.31	1
10	0.27082	5717.78	1
15	0.2066	5429.9	1
20	0.13416	2600.95	1
25	0.36695	1701.57	1
30	0.6104	825.62	1
35	0.88256	157.9	1
40	0.951	61.22	1
		Scenario II
0	0.99717	2.59	0.759
5	0.99642	3.34	0.787
10	0.99673	2.83	0.709
15	0.99597	2.93	0.511
20	0.99638	3.34	0.513
25	0.99646	3.02	0.474
30	0.99679	3.06	0.535
35	0.99664	3.06	0.357
40	0.99621	3.33	0.442
		Scenario III
0	0.99783	2.01	0.777
5	0.99651	3.41	0.762
10	0.99736	2.43	0.786
15	0.99738	2.35	0.776
20	0.99726	2.45	0.769
25	0.99721	2.56	0.76
30	0.9968	2.93	0.738
35	0.99712	2.8	0.711
40	0.99687	3.19	0.686

SNR (dB)	CPU Run Time (s)	CPU Energy Per Node (J)	Broadcast Energy Per Node (J)	Total Energy Per Node (J)
		Scenario I
0	162.08	401.63	0.29	401.91
5	162.07	401.62	0.29	401.91
10	161.84	401.05	0.29	401.34
15	161.91	401.2	0.29	401.49
20	161.77	400.88	0.29	401.16
25	161.59	400.41	0.29	400.69
30	161.39	399.94	0.29	400.22
35	161.34	399.79	0.29	400.08
40	161.8	400.94	0.29	401.22
		Scenario II
0	19.83	49.13	0.03	49.16
5	20.23	50.13	0.03	50.16
10	19.44	48.18	0.03	48.21
15	17.1	42.38	0.02	42.4
20	16.91	41.9	0.02	41.92
25	16.38	40.6	0.02	40.62
30	16.88	41.83	0.02	41.85
35	15.5	38.41	0.01	38.42
40	16.54	40.98	0.02	41
		Scenario III: Beamforming Node
0	161.56	400.36	0.29	400.64
5	161.68	400.64	0.29	400.93
10	161.51	400.23	0.29	400.52
15	161.29	399.69	0.29	399.97
20	161.34	399.81	0.29	400.1
25	161.06	399.11	0.29	399.39
30	161.07	399.13	0.29	399.41
35	160.99	398.92	0.29	399.21
40	161.1	399.2	0.29	399.49
		Scenario III: DSTC Node
0	34.17	84.66	0.04	84.7
5	34.92	86.54	0.04	86.57
10	32.85	81.4	0.03	81.44
15	32.08	79.5	0.03	79.53
20	32.53	80.61	0.04	80.65
25	27.14	67.26	0.04	67.3
30	24.16	59.87	0.04	59.91
35	23.57	58.41	0.04	58.46
40	23.12	57.29	0.04	57.34