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

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

Algorithms for the Minimal Connected k-Coverage Set Problem under Probabilistic Sensing Models in Directional Sensor Networks

The fundamental issue in sensor networks provides a certain degree of coverage and maintains connectivity under the energy constraint,on which the minimal connected k-coverage set problem is proposed.The traditional problem studies the deterministic omni-directional sensing model which is too ideal to adapt atrocious environments or directional sensor networks.To overcome the shortcomings,the connected k-coverage problem is investigated under the probabilistic sensing models in directional sensor networks in this paper.Because it is NP-hard,two approximate algorithms,IPA and CBDA,are proposed.IPA is a centralized solution based on 0-1 integer programming and minimum spanning tree.And CBDA is a distributed algorithm based on coverage benefit.It is proved that the solution gotten by IPA and CBDA are feasible.The time complexities,the communication complexities and the performance ratio are theoretically analyzed.Simulation results show that IPA and CBDA significantly maintain coverage in the probabilistic sensing model and prolong the network lifetime in some sense compared with the ILP and DGA3].