一种改进的无线传感器网络MCDS构造算法  

An Improved MCDS Constructing Algorithm on Wireless Sensor Network

作　　者：王娜[1] 霍英[1] 

机构地区：[1]韶关学院信息科学与工程学院,广东韶关512005

出　　处：《计算机技术与发展》2015年第3期122-125,共4页Computer Technology and Development

基　　金：广东省科技创新项目(2013KJCX0168)

摘　　要：在单位圆盘图中的连通支配集被作为无线传感器网络的虚拟主干网提出并研究。无线网络具有网络拓扑结构可变,且节点之间可以随意通信的特点,所以其路由的算法要求能够对拓扑结构的变化快速做出反映,而图论中连通支配集分层路由算法可以很好地满足无线网络的通信要求。文中基于连通支配集,在已有的求解最小连通支配集的分布式算法(MCDS)的基础上,提出了一种改进的基于节点邻居关系构造最小连通支配集(MCDS)的算法,并通过仿真实验与NMCDS算法进行了性能比较。实验结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源。该算法优于NMCDS算法,能够快速得到更小规模的MCDS,并且对由于节点发生故障造成网络拓扑的变化,文中还提出一种局部修复算法以得到新的MCDS。The connected dominating set in quasi-unit disk graph has been proposed as virtual backbone or spine for wireless sensor network. Wireless network have characteristics of network topology structure is variable and the communication is free betw een notes. So the routing algorithm requires that can make a quick response to the change of the network topology. The algorithm of connected dominating set in graph theory may meet demand very well to the communication of wireless. Based on the connected dominating set and the existing algorithm of M inimum Connected Dominating Set（ M CDS）,propose an improved constructing algorithm based on nodes neighboring relation for connected domination set. Simulation result compared with NM CDS on performance confirms that the connected dominating set the algorithm got has smaller size,decreasing the number of forwarding node in the process of network broadcasting and saving the network resource greatly. M oreover,this algorithm is better than NM CDS,can quickly obtain the M CDS with smaller size,and in view of the change of network topology caused by the failure for nodes,also propose a local maintenance algorithm to get a new MCDS.

关 键 词：无线传感器网络 连通支配集 最小连通支配集 分布式算法 路由 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]