Constructing efficient rotating backbones in wireless sensor networks using graph coloring
详细信息查看全文 | 推荐本文 |
摘要
For a dense deployment of sensors modeled as a random geometric graph of minimum degree , we introduce efficient algorithms both centralized and distributed for selecting ( + 1) backbones with disjoint node sets that are each independent and fully (or nearly) dominating. The backbone sets are initialized by graph coloring employing either topology or geometry. To support efficient routing, each set is extended to constitute a connected, constant density, planar backbone by using localized 2-hop relay and Gabriel Graph rules. The novel concept of a bipartite backbone is introduced with derivation of a planarity, bounded degree, and domination properties. Two algorithms for selecting ( + 1)/2 disjoint bipartite backbones are introduced and analyzed. One employs coloring and independent set pairing with dominating and relay sets of the pair each determined separately to serve the other. A second algorithm sequentially selects bipartite backbones focusing on the domination property of a primary part and the relay property of the second part to optimize the topological properties of each bipartite backbone. Extensive experimental results are presented to demonstrate the properties of the resulting backbone partitions.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700