有向传感器网络中基于概率感知模型的最小连通k覆盖集算法

• 作者: 伍勇安 李敏 殷建平 祝恩 蔡志平
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 有向传感器网络 连通k覆盖集 概率感知模型 覆盖效益
• 年，卷（期）: 2008,（12）
• 所属期刊栏目: 计算机网络与安全
• 页码范围: 19-22,48
• 页数: 5页
• 分类号: TP393
• 字数: 4879字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2008.12.005

摘要

无线传感器网络的基本问题之一是,网络节点如何利用有限的能量对人们所关注的物理世界进行满意的监测,这可抽象为最小连通k覆盖集问题.传统的最小连通k覆盖集问题是基于确定型全向感知模型的,该模型过于理想化,不能适用于复杂的应用环境,也不能应用于有向传感器网络中.针对上述局限,本文提出了有向传感器网络中基于概率感知模型的最小连通志覆盖集问题(MCKS),并指出这是NP难问题;设计了基于0-1整数规划和最小生成树的集中式近似算法(IPA)和基于覆盖效益探测的分布式近似算法(CBDA),分别证明两种算法最终得到的是MCKS问题的可行解,并分析了算法的时间复杂度、性能比和通信复杂度.通过仿真实验并与ILP算法和DGA算法进行比较的结果表明:在基于概率感知模型的条件下,IPA和CBDA能够有效实现有向传感器网络中的连通k覆盖,并且激活节点数目较少,网络寿命延长.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	殷建平	国防科技大学计算机学院	84	762	14.0	21.0
2	蔡志平	国防科技大学计算机学院	48	471	12.0	18.0
3	祝恩	国防科技大学计算机学院	35	252	10.0	12.0
4	李敏	国防科技大学计算机学院	10	105	6.0	10.0
5	伍勇安	国防科技大学计算机学院	4	47	3.0	4.0