Employing (1- ) Dominating Set Partitions as Backbones in Wireless Sensor Networks

The Twelfth Workshop on Algorithm Engineering and Experiments

Dhia Mahjoub

Others  :  http://www.siam.org/proceedings/alenex/2010/alx10_010_mahjoubd.pdf
PID  :  37687

来源: CEUR

【 摘 要 】

For a random geometric graph G(n; r) of minimum degree , we introduce an efficient algorithm for selecting ( + 1) backbones with disjoint node sets that are each independent (1") dominating sets of G. The backbone node sets are determined by a graph coloring algorithm employing only the topology (not the geometry) of G(n; r), and the back- bone links are selected with link lengths in a narrow window between r and 2r and further to form a planar graph back- bone. For large vertex sets (n = 1600; 3200) the resulting backbones are shown to each cover typically over 99% of the vertices of G (i.e. " < 0:01), with about 30% being fully dominating, which is consistent with the 14 constant approximation factor algorithm proposed recently in [23] for the domatic partition problem in Unit Disk Graphs. We establish experimentally by measures of node degrees, link lengths, and interior triangular face counts that each individual backbone has most of the coverage behavior and routing convenience of the triangular "perfect packing" lattice. We further show for each sample G(n; r) that the relatively few vertices not covered by all ( + 1) backbones are covered by most of the backbones. Hence backbone rotation in a wireless sensor network would reach all sensors (vertices) sufficiently frequently. Our novel backbone generation algorithm confirms experimentally the existence of these (+ 1) backbones in a random geometric graph, and provides an efficient topologically based centralized algorithm for deter- mining the backbones. We also point out that our novel backbone construction method is flexible such that any efficient coloring algorithm can be plugged into it. In this pa- per, we experiment with several coloring algorithms: Small- est Last, Largest First, Lexicographic, Radial Sweep and Random and we compare their respective performance. Our emphasis is, however, on SL since it offers robust proper- ties and interesting expected behavior. We also experiment with several random node distributions: uniform, skewed and normal in both unit square and disk of which we also discuss the results.