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

关键词：有向传感器网络 连通k覆盖集 概率感知模型 覆盖效益 

单位：国防科技大学计算机学院 湖南长沙410073