Virtual backbone formation algorithm based on GBG for wireless sensor networks
An approximation algorithm of virtual backbone formation （VBF） based on a more generalized and realistic wireless network communication model of bounded growth graph （GBG） was proposed. This approach constructs an maximal independent set （MIS） by network decomposition scheme and a clustergraph by co...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2008-01-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/74651813/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | An approximation algorithm of virtual backbone formation （VBF） based on a more generalized and realistic wireless network communication model of bounded growth graph （GBG） was proposed. This approach constructs an maximal independent set （MIS） by network decomposition scheme and a clustergraph by coloring, computes local mini- mum dominating sets in 2-separated collection of subnets to form a global optimal solution which is used to directly con- struct an approximation minimum connected dominating sets by adjusting transmission range of clusterheads and finally use marking process and self-pruning to reduce the virtual backbone, without additional gateways. The computed con- nected dominating set guarantees a constant stretch factor and constant degree while the nodes only require direct neighborhood information. The efficiency and correctness of the VBF is confirmed through theoretical analysis as well as comparison study in details. |
|---|---|
| ISSN: | 1000-436X |