ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (1): 15-25.doi: 10.7544/issn1000-1239.2016.20150657

所属专题: 2016优青专题

• 网络技术 • 上一篇    下一篇

无线传感器网络虚拟骨干近似算法综述

张昭   

  1. (浙江师范大学 浙江金华 321004) (hxhzz@sina.com)
  • 出版日期: 2016-01-01
  • 基金资助: 
    国家自然科学基金项目(61222201,11531011);教育部高等学校博士学科点专项科研基金项目(20126501110001);新疆杰出青年科技人才培养项目(2013711011)

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

中图分类号: