A point-distribution index and its application to sensor-grouping in wireless sensor networks

Abstract

We propose ℓ, a novel index for evaluation of point-distribution. ℓ is the minimum distance between each pair of points normalized by the average distance between each pair of points. We find that a set of points that achieve a maximum value of ℓ result in a honeycomb structure. We propose that ℓ can serve as a good index to evaluate the distribution of the points, which can be employed in coverage-related problems in wireless sensor networks (WSNs). To validate this idea, we formulate a general sensorgrouping problem for WSNs and provide a general sensing model. We show that locally maximizing ℓ at sensor nodes is a good approach to solve this problem with an algorithm called Maximizing-ℓ Node-Deduction (MIND). Simulation results verify that MIND outperforms a greedy algorithm that exploits sensor-redundancy we design. This demonstrates a good application of employing ℓ in coverage-related problems for WSNs. Copyright 2006 ACM.