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!
|
| _version_ | 1841537568956481536 |
|---|---|
| author | SUN Yan-jing QIAN Jian-sheng |
| author_facet | SUN Yan-jing QIAN Jian-sheng |
| author_sort | SUN Yan-jing |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-bdfc9262345d48269cfc2aae7b00070f |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2008-01-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-bdfc9262345d48269cfc2aae7b00070f2025-01-14T08:31:23ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2008-01-01299810474651813Virtual backbone formation algorithm based on GBG for wireless sensor networksSUN Yan-jingQIAN Jian-shengAn 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.http://www.joconline.com.cn/zh/article/74651813/wireless sensor networksvirtual backbonebounded growth graphconnected dominating set |
| spellingShingle | SUN Yan-jing QIAN Jian-sheng Virtual backbone formation algorithm based on GBG for wireless sensor networks Tongxin xuebao wireless sensor networks virtual backbone bounded growth graph connected dominating set |
| title | Virtual backbone formation algorithm based on GBG for wireless sensor networks |
| title_full | Virtual backbone formation algorithm based on GBG for wireless sensor networks |
| title_fullStr | Virtual backbone formation algorithm based on GBG for wireless sensor networks |
| title_full_unstemmed | Virtual backbone formation algorithm based on GBG for wireless sensor networks |
| title_short | Virtual backbone formation algorithm based on GBG for wireless sensor networks |
| title_sort | virtual backbone formation algorithm based on gbg for wireless sensor networks |
| topic | wireless sensor networks virtual backbone bounded growth graph connected dominating set |
| url | http://www.joconline.com.cn/zh/article/74651813/ |
| work_keys_str_mv | AT sunyanjing virtualbackboneformationalgorithmbasedongbgforwirelesssensornetworks AT qianjiansheng virtualbackboneformationalgorithmbasedongbgforwirelesssensornetworks |