ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2016, Vol. 53 ›› Issue (1): 15-25.doi: 10.7544/issn1000-1239.2016.20150657

Special Issue: 2016优青专题

Previous Articles     Next Articles

Survey of Approximation Algorithm on Virtual Backbone of Wireless Sensor Network

Zhang Zhao   

  1. (Zhejiang Normal University, Jinhua, Zhejiang 321004)
  • Online:2016-01-01

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.

Key words: wireless sensor network (WSN), virtual backbone, connected dominating set (CDS), approximation algorithm, performance ratio

CLC Number: