A coloring based backbone construction algorithm in wireless ad hoc network

Zhiwei Lin; Li Xu; Dajin Wang; Jianliang Gao

doi:10.1007/11745693_50

A coloring based backbone construction algorithm in wireless ad hoc network

Zhiwei Lin, Li Xu, Dajin Wang, Jianliang Gao

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

A wireless ad hoc network consists of many mobile hosts communicating with each other without any infrastructure. Virtual backbone plays a key role in a wireless ad hoc network for routing optimization, energy conservation and resource allocation. To construct virtual backbones efficiently, a new distributed method based on coloring algorithm is proposed in this paper. Because the proposed algorithm uses only 1-hop neighbors information, it is proven that this coloring based method can cluster into groups with O(Δ) time complexity and O(nΔ²) message complexity, which are better than referenced work in this paper.

Original language	English
Title of host publication	Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings
Pages	509-516
Number of pages	8
DOIs	https://doi.org/10.1007/11745693_50
State	Published - 17 Jul 2006
Event	1st International Conference on Grid and Pervasive Computing,GPC 2006 - Taichung, Taiwan, Province of China Duration: 3 May 2006 → 5 May 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3947 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	1st International Conference on Grid and Pervasive Computing,GPC 2006
Country	Taiwan, Province of China
City	Taichung
Period	3/05/06 → 5/05/06

Access to Document

10.1007/11745693_50

Link to publication in Scopus

Fingerprint Dive into the research topics of 'A coloring based backbone construction algorithm in wireless ad hoc network'. Together they form a unique fingerprint.

Cite this

Lin, Z., Xu, L., Wang, D., & Gao, J. (2006). A coloring based backbone construction algorithm in wireless ad hoc network. In Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings (pp. 509-516). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3947 LNCS). https://doi.org/10.1007/11745693_50

Lin, Zhiwei ; Xu, Li ; Wang, Dajin ; Gao, Jianliang. / A coloring based backbone construction algorithm in wireless ad hoc network. Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings. 2006. pp. 509-516 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7ed523ccc5884b9e94143cdf7b779567,

title = "A coloring based backbone construction algorithm in wireless ad hoc network",

abstract = "A wireless ad hoc network consists of many mobile hosts communicating with each other without any infrastructure. Virtual backbone plays a key role in a wireless ad hoc network for routing optimization, energy conservation and resource allocation. To construct virtual backbones efficiently, a new distributed method based on coloring algorithm is proposed in this paper. Because the proposed algorithm uses only 1-hop neighbors information, it is proven that this coloring based method can cluster into groups with O(Δ) time complexity and O(nΔ2) message complexity, which are better than referenced work in this paper.",

author = "Zhiwei Lin and Li Xu and Dajin Wang and Jianliang Gao",

year = "2006",

month = jul,

day = "17",

doi = "10.1007/11745693_50",

language = "English",

isbn = "3540338098",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "509--516",

booktitle = "Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings",

note = "null ; Conference date: 03-05-2006 Through 05-05-2006",

}

Lin, Z, Xu, L, Wang, D & Gao, J 2006, A coloring based backbone construction algorithm in wireless ad hoc network. in Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3947 LNCS, pp. 509-516, 1st International Conference on Grid and Pervasive Computing,GPC 2006, Taichung, Taiwan, Province of China, 3/05/06. https://doi.org/10.1007/11745693_50

A coloring based backbone construction algorithm in wireless ad hoc network. / Lin, Zhiwei; Xu, Li; Wang, Dajin; Gao, Jianliang.

Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings. 2006. p. 509-516 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3947 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A coloring based backbone construction algorithm in wireless ad hoc network

AU - Lin, Zhiwei

AU - Xu, Li

AU - Wang, Dajin

AU - Gao, Jianliang

PY - 2006/7/17

Y1 - 2006/7/17

N2 - A wireless ad hoc network consists of many mobile hosts communicating with each other without any infrastructure. Virtual backbone plays a key role in a wireless ad hoc network for routing optimization, energy conservation and resource allocation. To construct virtual backbones efficiently, a new distributed method based on coloring algorithm is proposed in this paper. Because the proposed algorithm uses only 1-hop neighbors information, it is proven that this coloring based method can cluster into groups with O(Δ) time complexity and O(nΔ2) message complexity, which are better than referenced work in this paper.

AB - A wireless ad hoc network consists of many mobile hosts communicating with each other without any infrastructure. Virtual backbone plays a key role in a wireless ad hoc network for routing optimization, energy conservation and resource allocation. To construct virtual backbones efficiently, a new distributed method based on coloring algorithm is proposed in this paper. Because the proposed algorithm uses only 1-hop neighbors information, it is proven that this coloring based method can cluster into groups with O(Δ) time complexity and O(nΔ2) message complexity, which are better than referenced work in this paper.

UR - http://www.scopus.com/inward/record.url?scp=33745855078&partnerID=8YFLogxK

U2 - 10.1007/11745693_50

DO - 10.1007/11745693_50

M3 - Conference contribution

AN - SCOPUS:33745855078

SN - 3540338098

SN - 9783540338093

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 509

EP - 516

BT - Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings

Y2 - 3 May 2006 through 5 May 2006

ER -

Lin Z, Xu L, Wang D, Gao J. A coloring based backbone construction algorithm in wireless ad hoc network. In Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings. 2006. p. 509-516. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11745693_50