Survey of Approximation Algorithm on Virtual Backbone of Wireless Sensor Network

Zhang Zhao

doi:10.7544/issn1000-1239.2016.20150657

Journal of Computer Research and Development > 2016 > 53(1): 15-25. > DOI: 10.7544/issn1000-1239.2016.20150657 CSTR: 32373.14.issn1000-1239.2016.20150657

Zhang Zhao. Survey of Approximation Algorithm on Virtual Backbone of Wireless Sensor Network[J]. Journal of Computer Research and Development, 2016, 53(1): 15-25. DOI: 10.7544/issn1000-1239.2016.20150657

Citation:

PDF (1187 KB)

Survey of Approximation Algorithm on Virtual Backbone of Wireless Sensor Network

Zhang Zhao

(Zhejiang Normal University, Jinhua, Zhejiang 321004)

More Information

Published Date: December 31, 2015

Graphical Abstract

Abstract

Abstract

Using virtual backbone in wireless sensor network can effectively save energy, reduce interference, and prolong lifetime, which has a wide application in the field of geometric routing and topology control. Virtual backbone can be modeled as a connected dominating set (CDS) in a graph. This paper introduces the state of art of approximation algorithms on CDS and its variations. The focus is put on theoretical results and methods. The purpose is to provide a reference for researchers who are interested in this field.
- wireless sensor network (WSN),
- virtual backbone,
- connected dominating set (CDS),
- approximation algorithm,
- performance ratio

FullText(HTML)

References (0)

[1]	Zeng Weixin, Zhao Xiang, Tang Jiuyang, Tan Zhen, Wang Wei. Iterative Entity Alignment via Re-Ranking[J]. Journal of Computer Research and Development, 2020, 57(7): 1460-1471. DOI: 10.7544/issn1000-1239.2020.20190643
[2]	Dai Chenchao, Wang Hongyuan, Ni Tongguang, Chen Shoubing. Person Re-Identification Based on Deep Convolutional Generative Adversarial Network and Expanded Neighbor Reranking[J]. Journal of Computer Research and Development, 2019, 56(8): 1632-1641. DOI: 10.7544/issn1000-1239.2019.20190195
[3]	Du Ruizhong, Li Mingyue, Tian Junfeng. Multi-keyword Ranked Ciphertext Retrieval Scheme Based on Clustering Index[J]. Journal of Computer Research and Development, 2019, 56(3): 555-565. DOI: 10.7544/issn1000-1239.2019.20170830
[4]	Guo Jiafeng, Fan Yixing. Exploration on Neural Information Retrieval Framework[J]. Journal of Computer Research and Development, 2018, 55(9): 1987-1999. DOI: 10.7544/issn1000-1239.2018.20180133
[5]	Zhong Qi, Wang Jing, Guan Xuetao, Huang Tao, Wang Keyi. Data Object Scale Aware Rank-Level Memory Allocation[J]. Journal of Computer Research and Development, 2014, 51(3): 672-680.
[6]	Liu Xiping, Wan Changxuan, and Liu Dexi. Effective XML Vague Content and Structure Retrieval and Scoring[J]. Journal of Computer Research and Development, 2010, 47(6): 1070-1078.
[7]	Xu Cunlu, Chen Yanqiu, Lu Hanqing. Statistical Landscape Features for Texture Retrieval[J]. Journal of Computer Research and Development, 2006, 43(4): 702-707.
[8]	Xing Qiang, Yuan Baozong, and Tang Xiaofang. A Fast Image Retrieval Method Based on Weighted Chromaticity Histogram[J]. Journal of Computer Research and Development, 2005, 42(11): 1903-1910.
[9]	Ru Liyun, Ma Shaoping, and Lu Jing. Feature Fusion Based on the Average Precision in Image Retrieval[J]. Journal of Computer Research and Development, 2005, 42(9): 1640-1646.
[10]	Zhang Min, Lin Chuan, and Ma Shaoping. Dynamic Parameter Learning Approach for Information Retrieval with Genetic Algorithm[J]. Journal of Computer Research and Development, 2005, 42(3).