In sensor networks, a large number of inexpensive, lowpower communication sensor devices with one or more sensing capabilities are deployed in a sensor field, providing physical sensing phenomena, processing them, and communicating this information to other sensors. These sensors are battery-powered and the network lifetime is a crucial concern for sensor networks. Collecting measurements from many sensors and transmitting them for various tasks (e.g., localization, tracking targets, and temperature monitoring) will reduce the lifetime of a network. Thus, the sensing tasks should be able to minimize the number of sensors involved in order to prolong the network lifetime. This will motivate the selective use of the most informative sensors, resulting in a reduction of the number of sensors in operation.

In the scenario of localization using wireless sensor networks, the localization accuracy can be significantly improved by selecting the most informative sensors [1-3]. For example, the entropy-based heuristic approach proposed in [1] greedily selects the next sensor in order to reduce the overall uncertainty. The authors of [2] focus on finding the best set of sensors that maximizes the localization accuracy, under the assumption of a known uncertainty region for the source location; further, they present analytical bounds on the performance of their sensor selection algorithm. In [3], the author addresses the sensor selection problem when the quantization of measurements is taken into account and shows that this sensor selection problem can be treated as a rate allocation problem where the goal is to allocate the rate to each sensor so as to minimize the localization error. To solve this problem, the generalized Breiman, Friedman, Olshen, and Stone (BFOS) algorithm (see [4]) is applied with the rate-distortion (R-D) calculation for each candidate rate allocation.

However, most of the existing algorithms suffer from a high computational complexity, since the sensor networks consist of a large number of sensors and the process of selecting sensors must be executed online whenever every event of interest occurs. Thus, fast and powerful sensor selection algorithms are required to facilitate the practical applications of large sensor networks. In this paper, we propose a simple geometry-based sensor selection algorithm by utilizing only the information of sensor locations. Motivated by the observation that sensors clustered together tend to generate redundant information [3], we seek to find a set of sensors that are located at the maximum distance from each other. More specifically, we search the best set of sensors that maximizes the average distance between the sensors within the set. Furthermore, in order to accelerate the selection process, we propose an iterative sequential search algorithm without losing optimality, instead of directly conducting an exhaustive search of sensors over the sensor field. We show that the proposed algorithm reduces the average distance in each iteration, ensuring the convergence of the algorithm. Our experiments demonstrate that the proposed sensor selection achieves a significant performance improvement as compared to random sensor selections and exhibits a performance close to that of the exhaustive search among sensors over the sensor field.

Throughout this paper, it is assumed that each sensor can obtain a noise-corrupted measurement, such as signal energy or temperature using actual measurements (e.g., time-series measurements or spatial measurements) and there are only one-way noiseless communication channels from the sensors to the fusion node; i.e., there is no feedback channel, and the sensors do not communicate with each other (no relay between sensors).

The rest of this paper is organized as follows: The problem formulation is given in Section II. The geometrybased sensor selection algorithm is explained in Section III. The iterative sequential algorithm is summarized in Section IV and the proposed algorithm is applied to the acoustic amplitude sensor system for source localization, which is introduced in Section V. Simulation results are presented in Section VI and the conclusion is stated in Section VII.

Within the sensor field S of interest, suppose that there are M sensors located at the known spatial locations, denoted by x_i, i = 1, …, M, where x_i ∈ S ⊂ R². It is assumed that K ≪ M sensors are selected prior to the sensing operation and the selected sensors will measure signals related to the unknown parameter x and send them to a fusion node that estimates the parameter by using K measurements. The measurement at sensor i over a given time interval k, denoted by z_i can be expressed as follows:

where f(x, x_i, P_i) indicates the sensor model employed at sensor i and w_i denotes a combined noise term that includes both measurement noise and modeling error and can be approximated using a normal distribution, N(0, ). P_i is the parameter vector for the sensor model (an example of P_i for an acoustic amplitude sensor case is given in Section V). It is assumed that each sensor measures its sensor reading z_i (x,k) at time interval k and sends it to a fusion node, where all sensor measurements are used to obtain an estimate . For the case of quantized measurements, we use an R_i-bit quantizer with a dynamic range at sensor i. We assume that the quantization range can be selected for each sensor on the basis of the desirable properties of their respective sensing ranges (see [5] for the details). Each sensor generates a quantization index Q_i ∈ I_i = {1, …, 2^Ri} to which the measurement z_i belongs to.

We believe that this formulation is general and captures many scenarios of practical interest. Each scenario will obviously lead to a different sensor model f(x, x_i, P_i). For example, for the source localization in acoustic sensor networks, each sensor captures acoustic energy from a source located at x ∈ S. In the following paragraphs, we explain the motivation for a geometry-based sensor selection algorithm and propose an iterative sequential search algorithm.

It is observed that sensors clustered together tend to send redundant information to a fusion node [3] and thus, a good strategy would be to select sensors that are at the maximum distance from each other. To be specific, we seek to search the best set of K sensors from M sensors in a sensor field that maximizes the average distance over the set:

where the distance ║x_i-x_j║should be in the range [d_min, d_max] and is one of the possible sets that can be constructed by selecting K from M sensors. Note that sensors located very far from each other should be excluded from our selection process because sensors typically assume their sensing ranges for reliable measurements. The parameters (d_min, d_max) that determine the range of the acceptable distance between sensors will depend upon the applications. Clearly, the best set will consist of the sensors that are at the maximum distance from each other on average under the constraint of the distance range.

In search for the best set, we take an iterative sequential approach rather than an exhaustive search to make the algorithm practically applicable to large sensor networks (M large). Suppose that we are initially given the set of K sensors Then, we find the next set that reduces the metric in Eq. (2) in each iteration. This search is repeated until there is no change in the set V. The procedure for finding the next set can be elaborated as follows: First, we construct the K regions such that the k-th region includes the candidate sensors for in the next set. Formally, we obtain from the set

where S_k consists of the sensors closer to than other sensors, , j ≠ k; j = 1, …, K. Clearly, each sensor in S_k can be selected as the next candidate for because most of the assignments of the sensors in S_k to the other elements , j ≠ k; j = 1, …, K, will likely cause the average distance over the next set to decrease. Notice that this step will reduce the search range for the next element The next step is to choose one from the sensors in each region that maximizes the metric:

Note that this search should be conducted under the constraint of the distance range. It is obvious that the construction of K regions, S_k , k = 1, …, K and the subsequent selection of the next sensor over each region, the two main tasks in the proposed algorithm will guarantee that the metric remains non-decreasing over the iterations, implying the convergence of the algorithm. Note that each sensor in the next set is searched for over a small region and in a sequential manner, enabling fast operation.

The proposed algorithm is iteratively executed over all sensors i = 1, …, M until no change in the set is achieved; it can be summarized as follows:

Algorithm 1: Geometry-based iterative design algorithm.

Step 1 : Initially, set iteration index n = 1 and choose randomly K out of M sensors to construct a set, Step 2 : Construct K regions, Sk , k = 1, …, K by using Eq. (3).Step 3 : Find the k-th sensor from its corresponding region Sk that maximizes the average distance by using Eq. (4).Step 4 : Set = and repeat Step 3 for the other K − 1 sensors.Step 5 : Set n = n + 1 and construct the new set Step 6 : If Vn-1= Vn , then stop; otherwise, go to Step 2.

Note that the proposed iterative algorithm suffers from the presence of numerous poor local optima depending on the initialization of set V. Hence, it is recommended that the sensors sufficiently distant to each other be selected for the initial set.

As an example of an application of the proposed algorithm, we consider the acoustic amplitude sensor system for source localization where an energy decay model of sensor signal readings proposed in [6] is used for localization. This model is based on the fact that the acoustic energy emitted omni-directionally from a sound source will attenuate at a rate that is inversely proportional to the square of the distance in free space [7] and was verified by the field experiment in [6] and used in [8-10]. When an acoustic sensor is employed at each sensor, the signal energy measured at sensor i over a given time interval k, and denoted by z_i, can be expressed as follows:

where the parameter vector P_i in Eq. (1) consists of the gain factor of the i-th sensor γ _i , an energy decay factor α, which is approximately equal to 2 in free space, and the source signal energy a. The measurement noise term w_i (k) can be approximated using a normal distribution N(0, ) . In (5), it is assumed that the signal energy α, is uniformly distributed over the range [α_min , α_max].

The K sensors are first searched by applying the algorithm proposed in Section IV, and the selected sensors will capture the signal energies generated from a source by using Eq. (5) and send them to a fusion node that will produce the estimate of the source location from the measurements z_i, i = 1, …, K. For the case of quantized measurements, it is assumed that each sensor quantizes its measurement with a predesigned quantizer of R_i-bits before sending them to a fusion node.

Clearly, for z_i(x, k) to be useful for localization, it must be a function of the relative positions of the source and the sensor. Thus, there exists some function that can provide an estimate of the source location on the basis of the original, unquantized measurements; these estimators have been the focus of most of the literature to date on both sensor networks and other source localization scenarios. Instead, we consider the corresponding estimators g(.) that operate on quantized data to estimate the source location .

While specific g(.) choices depend on the sensor model f(x, x_i, P_i), we can sketch some of the general properties of this estimator. First, since z_i(x, k) is used for localization, it must provide distance information about the relative position of the sensor and the source. Thus, after quantization, each transmitted symbol will represent a range of positions (e.g., a range of distances from the sensor). Second, once information is obtained from all sensors, it will be optimal to exploit the range information corresponding to each quantized measurement without obtaining its reconstructed value that has been used in a standard estimator (i.e., by replacing a range of distances by a single distance). That is, an optimal estimator g(.) should be a function of the range information rather than the reconstructed values.

More specifically, here, we consider the estimator g(.) that performs energy-based source localization by using quantized data. Note that the localization algorithm to be explained in this section is designed for the high signal-tonoise ratio (SNR) regime (σ_i = 0) but will also provide a foundation for the localization based on noisy quantized data [9]. Since each quantized sensor reading corresponds to a region where a source is located, all quantized sensor readings lead to a partition of a sensor field obtained by intersecting the regions corresponding to each sensor reading. The localization based on the quantized sensor readings is illustrated in Fig. 1, where the ring-shaped area, A_i, i = 1,…, K, corresponds to a quantized measurement at the i-th sensor. By computing the intersection of all the ring areas (one per sensor), it is possible to define an area where the source is expected to be located. Note that at least three quantized readings are required to achieve a connected intersection. Formally,

where A_i denotes the ring-shaped region obtained from the quantization index Q_i that z_i falls into (Fig. 1). If the source is uniformly distributed in the sensor field, the estimate will be the sample mean in intersection A. Clearly, is the minimum mean squared error (MMSE) estimator under the assumption of no measurement noise.

In the experiments, we consider an acoustic sensor network where M (=50) sensors are randomly deployed in a sensor field measuring 20 m × 20 m. Prior to performing the localization process, the best set of K sensors is selected by using the proposed algorithm and denoted by V*. It is assumed that the source locations are uniformly distributed and the measurements are generated from the model parameters in Eq. (5) by setting a = 50, α = 2, and γ _i = 1.

The sensor selection of the proposed algorithm is compared with many sensor selections V^R that can be constructed by randomly selecting K sensors from M sensors. We also investigate the performance of the proposed algorithm when the sensor measurements are quantized before being transmitted to the fusion node. Finally, our search algorithm is evaluated by comparing its solution with the optimal solution obtained by an exhaustive search that requires a huge computational complexity. For the evaluation, the localization error is computed using the maximum likelihood (ML) estimation except where stated otherwise.

In this experiment, 100 different sensor configurations are generated for M = 50, and for each configuration, the proposed algorithm is executed to find the best set of K = 12 sensors and is compared with the sensor selection executed by randomly choosing K from M sensors. For testing the sensor selections, 1,000 source locations are generated with the SNR ranging from 30 to 70 dB obtained by varying σ_i = σ. Note that the SNR computed by 10 log₁₀ a²/σ² is measured at a distance of 1 m from the source, and for a practical vehicle target, it is often considerably higher than 40 dB. A typical value of the variance of the measurement noise is σ² = 0.05² (=60 dB) [6, 8]. In Fig. 2, the localization error averaged over 100 configurations is plotted for comparison. As expected, our sensor selection performs considerably well with respect to random selections because the sensors that are remotely distant to each other are likely to be selected and they send considerably less redundant information to a fusion node that can estimate the source location with a relatively high accuracy. In addition, our sensor selection produces a better localization result for noisy cases.

One hundred different sensor configurations are generated for M = 50, and for each configuration, we execute our algorithm for K = 8 in order to obtain the best set and examine the effect of quantization on the performance of the proposed algorithm with respect to that of random selections. In the experiment, it is assumed that each sensor employs the equally distance-divided quantizer (EDQ), which is designed with the rate R_i = 2, 3, 4 bits. The EDQ is introduced in [11] and shown to achieve good localization performance in an acoustic amplitude sensor system. Fig. 3 demonstrates that the proposed selection shows improved performance over the random selections when the quantization process is involved. Obviously, a good sensor selection will have a dominant impact on the performance as sensor measurements are coarsely quantized because the importance of the information associated with sensor locations becomes more significant. While computing the localization error based on quantized measurements, the localization algorithm in Eq. (6) is applied for fast computation.

The proposed algorithm is evaluated by comparing its selection with the optimal selection V_opt, which is generated by an exhaustive search. In this experiment, because the computational complexity required for the search is extremely high, we consider the case of K = 8 and M = 20 in a sensor field measuring 20 m × 20 m in order to curtail the search size. It is noted that the proposed sensor selection is suboptimal and is affected by the initial sets.

Thus, for each configuration, the localization errors are computed for V^R, V*, and V_opt, respectively, and are averaged over 100 different sensor configurations for the evaluation. In Table 1, the localization results for three different selection techniques (i.e., random selection, the proposed algorithm, and the exhaustive search) are tabulated for the sake of comparison. It can be seen that the proposed technique achieves a performance close to the optimal one while maintaining a considerably low complexity, implying that the geometric metric in Eq. (2) is effective for the acoustic source localization system.

In this paper, we have proposed a geometry-based sensor selection algorithm optimized for large sensor networks. To achieve low complexity, we suggest the use of the average distance between sensors within a set as a metric to be maximized and propose an iterative sequential search algorithm to find the best set of sensors that maximizes the average distance. This algorithm was applied to an acoustic sensor network for source localization and was shown to perform quite well in comparison to random sensor selections. In the future, we will continue to improve the proposed algorithm in terms of performance and complexity.