基于定向扩散的最小连通支配集构造算法  

Minimum connected dominating set algorithm based on directed diffusion

作　　者：李克清[1] 常晋义[1] 王加年[1] 

机构地区：[1]常熟理工学院计算机科学与工程学院,江苏苏州215500

出　　处：《通信学报》2008年第11期91-97,共7页Journal on Communications

基　　金：江苏省教育厅高校自然科学基础研究自筹经费项目(08KJD520012) ~~

摘　　要：针对区域覆盖算法未考虑节点的通信梯度问题,利用定向扩散路由在构造以sink节点为根的有向路由树时形成的递增梯度序列,提出了一种基于定向扩散的最小连通支配集构造算法。在路由信息扩散的同时逐级挑选出互不相邻的传感器节点构造出一个最大支撑集,然后在相邻层次的支撑集节点间寻找中间节点将独立集节点连通起来,最终得到一个近似的最小连通支配集。理论及仿真实验结果表明,该算法构造的连通支配集最小且计算耗时少,能多重有效覆盖热点区域,从而延长无线传感器网络的寿命。A new minimum connected dominating set algorithm based on directed diffusion MCDSDD was proposed, which attempted to improve the existed area coverage algorithms through introducing node＇s gradient in wireless sensor networks. During built a directed tree rooted from sink node using directed diffusion routing algorithm, an ascending node＇s gradient series could be constructed. Non-adjacent sensor nodes were picked out and made up a maximum dominator set during routing information diffusion gradient by gradient, and then some intermediate nodes are sought from those nodes, which were adjacent to both nodes unconnected in maximum dominator set and their gradients just between them yet, to ＂glue＂ the non-adjacent two nodes in maximum dominator set, and last, an approximate minimum connected dominator set was constructed. Simulation results show that MCDSDD can save time and multiple covers hot spot in the surveillance area, and prolong the life time of the WSN.

关 键 词：无线传感器网络 区域覆盖 最小连通支配集 定向扩散 轮换调度 

分 类 号：TN953[电子电信—信号与信息处理]