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

张　昭

(浙江师范大学　浙江金华　321004)

(hxhzz@sina.com)



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

张昭

(浙江师范大学浙江金华321004)

(hxhzz@sina.com)

Survey of Approximation Algorithm on Virtual Backbone of Wireless Sensor Network

Zhang Zhao

(ZhejiangNormalUniversity,Jinhua,Zhejiang321004)

AbstractUsing 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 wordswireless sensor network (WSN); virtual backbone; connected dominating set (CDS); approximation algorithm; performance ratio

摘要在无线传感器网络中应用虚拟骨干，可以有效地节约能量、减少干扰、延长网络寿命，在几何路由算法和网络拓扑控制等方面具有广泛的应用.虚拟骨干可以模型化为图中的连通控制集.主要从近似算法角度介绍连通控制集及其各种变形在国内外的研究现状及最新进展，侧重于研究方法和理论结果，为相关研究人员提供参考.

关键词无线传感器网络；虚拟骨干；连通控制集；近似算法；近似比

无线传感器网络(wireless sensor network, WSN)是一种分布式的传感网络，它由大量可以感知外部世界的传感器组成，并通过无线通信方式形成一个多跳的自组织网络.无线传感器网络在军事和民用等领域具有广泛的应用，如战场监控、环境监测、交通监管、智能家居、医疗卫生等[1].由于无线传感器网络没有固定的基础设施，传感器主要以自组织和多跳的方式协作地完成信息的传输和共享，故如何有效地进行拓扑控制和路由选择以获得一个高效、可靠、节能的自组织网络是一个具有挑战性的课题.如果信息传输过程使用简单的洪泛(flooding)方式(即每个传感器将它所感知的信息立即播报出去)，则极易造成能量的耗费并产生大量的信号干扰，引起广播风暴(broadcast storm)[2].文献[3]研究表明：在无线传感器网络中引入虚拟骨干(virtual backbone)，可以有效地减少信息传输过程中的拥堵、极大……