基于极大独立集的最小连通支配集的分布式算法

来源 :电子学报 | 被引量 : 0次 | 上传用户:caful
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.
其他文献
袁枚对乾嘉考据诗风的批判态度与他对乾嘉考据学风的态度紧密相联。他没有主张诗歌要绝对排斥考据,认为只要适量和切入得好,考据可以入诗,考据诗也是诗歌大家庭中的一员。但他反
探讨人文社科各学科的合作现状以及合作研究与论文质量的相关性,对期刊发展与评估、课题立项与研究、学科建设与管理有重要的理论价值和实际意义。通过研究发现,在经济学、管理
文章研究了8种常见金属离子K^+,Na^+、Mg^2+、Mn^2+、Ca^2+、Zn^2+、Cu^2+,Fe^2+对4PCA饲料复合酶中蛋白酶活性的影响,离子浓度设定为1×10^-4mol·L^-1、1×10^-3mol&#18
环境犯罪是一种新型犯罪,其在产生原因、危害性、犯罪构成等方面都有别于传统犯罪,对这种犯罪进行处罚的最现实、最有效的措施应当是罚金刑。我国环境犯罪罚金刑制度在运行中存
Q2算法是新一代国际视频编码标准MPEG-4的标准码率控制算法,但在低码率和低延迟的实时视频通信中,Q2算法往往会导致编码图像质量产生剧烈的波动,大大降低了信宿端重建视频的视觉
基于六面体的高阶叠层基函数,提出了一种新颖的构造预条件矩阵的方法.该方法基于叠层基函数特有的嵌套性质,利用特殊的编号策略,将由有限元方法导致的系数矩阵分成块矩阵的形
在20世纪中国文学的发展历程中,"传统"与"现代化"相互抵牾、碰撞,成为文学史中一个重要的母题。"五四"新文学从一开始就不可避免地带上了"反传统"的历史印记,但"重估"是现代作家对待传
在农业部9月底举办的农产品加工技术对接活动上,承办此次活动的农业部规划设计研究院把资源节约型农业技术的示范、推广作为一个重要内容。该院农副产品加工所所长、高级工程
该文从最大似然估计出发,得出了一种IFM信号参数估计方法,并采用一阶扰动模型分析其统计性能.该方法涵盖经典的多项相位变换法,将最大似然估计的多维搜索转化为一维搜索,但性能较
基于粒子滤波在非线性非高斯情况下具有较好的预测结果,本文提出了一种自适应背景图像分割新算法,该算法利用粒子滤波对下一帧的前景区域进行预测,进而计算出下一帧各像素点属于背景的概率以指导下一帧图像分割;在前景像素值与背景像素值相近的情况下利用先验知识进行图像分割是一种较好的方法,本文以粒子滤波预测结果与先验概率模型计算结果的均值作为当前像素点属于背景的概率来进行图像分割,实验结果表明,该方法在背景变化