GeometryBased Sensor Selection for Large Wireless Sensor Networks
 Author: Kim Yoon Hak
 Organization: Kim Yoon Hak
 Publish: Journal of information and communication convergence engineering Volume 12, Issue1, p8~13, 31 March 2014

ABSTRACT
We consider the sensor selection problem in large sensor networks where the goal is to find the best set of sensors that maximizes application objectives. Since sensor selection typically involves a large number of sensors, a low complexity should be maintained for practical applications. We propose a geometrybased sensor selection algorithm that utilizes only the information of sensor locations. In particular, by observing that sensors clustered together tend to have redundant information, we theorize that the redundancy is inversely proportional to the distance between sensors and seek to minimize this redundancy by searching for a set of sensors with the maximum average distance. To further reduce the computational complexity, we perform an iterative sequential search without losing optimality. We apply the proposed algorithm to an acoustic sensor network for source localization, and demonstrate using simulations that the proposed algorithm yields significant improvements in the localization performance with respect to the randomly generated sets of sensors.

KEYWORD
Iterative sequential search , Localization , Sensor networks , Sensor selection

I. INTRODUCTION
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 batterypowered 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 [13]. For example, the entropybased 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 ratedistortion (RD) 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 geometrybased 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 noisecorrupted measurement, such as signal energy or temperature using actual measurements (e.g., timeseries measurements or spatial measurements) and there are only oneway 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.
II. PROBLEM FORMULATION
Within the sensor field
S of interest, suppose that there areM sensors located at the known spatial locations, denoted byx _{i},i = 1, , M, wherex _{i }∈S ⊂R ^{2}. It is assumed thatK ≪M sensors are selected prior to the sensing operation and the selected sensors will measure signals related to the unknown parameterx and send them to a fusion node that estimates the parameter by usingK measurements. The measurement at sensori over a given time intervalk , denoted by z_{i} can be expressed as follows:where
f (x ,x _{i},P _{i}) indicates the sensor model employed at sensori andw_{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 ofP _{i} for an acoustic amplitude sensor case is given in Section V). It is assumed that each sensor measures its sensor readingz_{i} (x ,k ) at time intervalk 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 sensori . 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 atx ∈S . In the following paragraphs, we explain the motivation for a geometrybased sensor selection algorithm and propose an iterative sequential search algorithm.III. GEOMETRYBASED SENSOR SELECTION 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 fromM 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 selectingK fromM 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 ofK 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 setV . The procedure for finding the next set can be elaborated as follows: First, we construct theK regions such that thek th region includes the candidate sensors for in the next set. Formally, we obtain from the setwhere
S_{k} consists of the sensors closer to than other sensors, ,j ≠k; j = 1, …,K . Clearly, each sensor inS_{k} can be selected as the next candidate for because most of the assignments of the sensors inS_{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 nondecreasing 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.IV. PROPOSED ALGORITHM
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: Geometrybased 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 kth 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 Vn1= 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.V. APPLICATION TO ACOUSTIC AMPLITUDE SENSOR CASE
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 omnidirectionally 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 [810]. When an acoustic sensor is employed at each sensor, the signal energy measured at sensor
i over a given time intervalk , and denoted byz_{i} , can be expressed as follows:where the parameter vector
P _{i} in Eq. (1) consists of the gain factor of thei th sensorγ_{ i} , an energy decay factorα , which is approximately equal to 2 in free space, and the source signal energya . The measurement noise termw_{i} (k ) can be approximated using a normal distributionN (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.> A. Location Estimation Technique Based on Quantized Data
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, sincez_{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 energybased source localization by using quantized data. Note that the localization algorithm to be explained in this section is designed for the high signaltonoise 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 ringshaped area,
A_{i} ,i = 1,…,K , corresponds to a quantized measurement at thei 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 ringshaped 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 intersectionA . Clearly, is the minimum mean squared error (MMSE) estimator under the assumption of no measurement noise.VI. SIMULATION RESULTS
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 ofK sensors is selected by using the proposed algorithm and denoted byV* . It is assumed that the source locations are uniformly distributed and the measurements are generated from the model parameters in Eq. (5) by settinga = 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 selectingK sensors fromM 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.> A. Performance Analysis I: Comparison with Random Sensor Selections
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 ofK = 12 sensors and is compared with the sensor selection executed by randomly choosingK fromM 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_{10 }a ^{2}/σ^{2} 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 σ^{2} = 0.05^{2} (=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.> B. Performance Analysis II: Effect of Quantization
One hundred different sensor configurations are generated for
M = 50, and for each configuration, we execute our algorithm forK = 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 distancedivided 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.> C. Performance Evaluation: Comparison with Optimal Selection
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 ofK = 8 andM = 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* , andV_{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.VII. CONCLUSION
In this paper, we have proposed a geometrybased 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.

[Fig. 1.] Localization of the source on the basis of the quantized sensor readings.

[Fig. 2.] Comparison of the proposed algorithm with random selection. The average localization error is plotted vs. SNR (dB) with K = 12 and M = 50. SNR: signaltonoise ratio.

[Fig. 3.] Comparison of the proposed algorithm with random selection: The average localization error is plotted vs. the rate Ri = 2, 3, 4 bits with K = 8, M = 50, and signaltonoise ratio (SNR) = ∞.

[Table 1.] Comparison of the selection techniques, VR, V* with optimal solutions, and Vopt for K = 8, M = 20, and SNR = 40 dB