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]	Zhang Xiaodong, Zhang Chaokun, Zhao Jijun. State-of-the-Art Survey on Edge Intelligence[J]. Journal of Computer Research and Development, 2023, 60(12): 2749-2769. DOI: 10.7544/issn1000-1239.202220192
[2]	Wang Rui, Qi Jianpeng, Chen Liang, Yang Long. Survey of Collaborative Inference for Edge Intelligence[J]. Journal of Computer Research and Development, 2023, 60(2): 398-414. DOI: 10.7544/issn1000-1239.202110867
[3]	Zhang Wenzhu, Yu Jinghua. Task Offloading Strategy in Mobile Edge Computing Based on Cloud-Edge-End Cooperation[J]. Journal of Computer Research and Development, 2023, 60(2): 371-385. DOI: 10.7544/issn1000-1239.202110803
[4]	Su Mingfeng, Wang Guojun, Li Renfa. Resource Deployment with Prediction and Task Scheduling Optimization in Edge Cloud Collaborative Computing[J]. Journal of Computer Research and Development, 2021, 58(11): 2558-2570. DOI: 10.7544/issn1000-1239.2021.20200621
[5]	Huang Qianyi, Li Zhiyang, Xie Wentao, Zhang Qian. Edge Computing in Smart Homes[J]. Journal of Computer Research and Development, 2020, 57(9): 1800-1809. DOI: 10.7544/issn1000-1239.2020.20200253
[6]	Yue Guangxue, Dai Yasheng, Yang Xiaohui, Liu Jianhua, You Zhenxu, Zhu Youkang. Model of Trusted Cooperative Service for Edge Computing[J]. Journal of Computer Research and Development, 2020, 57(5): 1080-1102. DOI: 10.7544/issn1000-1239.2020.20190077
[7]	Ning Zhenyu, Zhang Fengwei, Shi Weisong. A Study of Using TEE on Edge Computing[J]. Journal of Computer Research and Development, 2019, 56(7): 1441-1453. DOI: 10.7544/issn1000-1239.2019.20180522
[8]	Shi Weisong, Zhang Xingzhou, Wang Yifan, Zhang Qingyang. Edge Computing: State-of-the-Art and Future Directions[J]. Journal of Computer Research and Development, 2019, 56(1): 69-89. DOI: 10.7544/issn1000-1239.2019.20180760
[9]	Deng Xiaoheng, Guan Peiyuan, Wan Zhiwen, Liu Enlu, Luo Jie, Zhao Zhihui, Liu Yajun, Zhang Honggang. Integrated Trust Based Resource Cooperation in Edge Computing[J]. Journal of Computer Research and Development, 2018, 55(3): 449-477. DOI: 10.7544/issn1000-1239.2018.20170800
[10]	Zhao Ziming, Liu Fang, Cai Zhiping, Xiao Nong. Edge Computing: Platforms, Applications and Challenges[J]. Journal of Computer Research and Development, 2018, 55(2): 327-337. DOI: 10.7544/issn1000-1239.2018.20170228