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

来源：计算机技术与发展杂志2015年第03期北京时间：

作者：王娜;霍英

摘要：在单位圆盘图中的连通支配集被作为无线传感器网络的虚拟主干网提出并研究。无线网络具有网络拓扑结构可变,且节点之间可以随意通信的特点,所以其路由的算法要求能够对拓扑结构的变化快速做出反映,而图论中连通支配集分层路由算法可以很好地满足无线网络的通信要求。文中基于连通支配集,在已有的求解最小连通支配集的分布式算法( MCDS)的基础上,提出了一种改进的基于节点邻居关系构造最小连通支配集( MCDS)的算法,并通过仿真实验与NMCDS算法进行了性能比较。实验结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源。该算法优于NMCDS算法,能够快速得到更小规模的MCDS,并且对由于节点发生故障造成网络拓扑的变化,文中还提出一种局部修复算法以得到新的MCDS。

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