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]	Tang Guowei, Wang Shanshe, Zhang Yan, Zhao Debin. Fractal-Searching-Tree-Based Embedded Wavelet Image Coding[J]. Journal of Computer Research and Development, 2013, 50(7): 1484-1490.
[2]	Zhou Lian, Wang Guojin. Piecewise Linear Approximation of Rational Triangular Surfaces[J]. Journal of Computer Research and Development, 2012, 49(5): 1116-1122.
[3]	Han Xuming, Zuo Wanli, Wang Limin, Shi Xiaohu. Atmospheric Quality Assessment Model Based on Immune Algorithm Optimization and Its Applications[J]. Journal of Computer Research and Development, 2011, 48(7): 1307-1313.
[4]	Huang Weixian and Wang Guojin. The L\-2 Distances for Rational Surfaces Based on Matrix Representation of Degree Elevation[J]. Journal of Computer Research and Development, 2010, 47(8): 1338-1345.
[5]	Yan Guanghui and Li Zhanhuai. A Two Phases Unsupervised Sequential Forward Fractal Dimensionality Reduction Algorithm[J]. Journal of Computer Research and Development, 2008, 45(11): 1955-1964.
[6]	Chen Jun and Wang Guojin. Optimal Parameterizations of the Degree 2 Rational Bézier Curves[J]. Journal of Computer Research and Development, 2008, 45(9): 1601-1604.
[7]	He Chuanjiang, Liu Weisheng, Shen Xiaona. Fast Fractal Image Coding Based on Quincunx Sums of Normalized Blocks[J]. Journal of Computer Research and Development, 2007, 44(12): 2066-2071.
[8]	Li Yajuan and Wang Guozhao. Uniform Interval Implicitization of Rational Surfaces[J]. Journal of Computer Research and Development, 2006, 43(5): 914-919.
[9]	Wang Fangshi, Xu De, and Wu Weixin. A Cluster Algorithm of Automatic Key Frame Extraction Based on Adaptive Threshold[J]. Journal of Computer Research and Development, 2005, 42(10): 1752-1757.
[10]	Zhang Can, Tu Guofang, Liu Xiaozhou. Remote Sensing Image Processing Using Wavelet Fractal Interpolation[J]. Journal of Computer Research and Development, 2005, 42(2): 247-251.

Cited By

Cited by

Periodical cited type(3)

1.	丁坤，刘增泉，张经炜，杨泽南，李喆雨. 基于图像奇异值分解的局部遮挡光伏阵列输出特性建模研究. 综合智慧能源. 2023(02): 53-60 .
2.	李新. 功率谱估计在舰船噪声特征提取中的应用仿真. 舰船科学技术. 2022(04): 43-46 .
3.	杨宝军. 基于有限元特征值的船舶螺旋桨噪声数据分类算法. 舰船科学技术. 2021(14): 7-9 .