论文部分内容阅读
无线传感器网络的基本问题之一是，网络节点如何利用有限的能量对人们所关注的物理世界进行满意的监测，这可抽象为最小连通k覆盖集问题。传统的最小连通k覆盖集问题是基于确定型全向感知模型的，该模型过于理想化，不能适用于复杂的应用环境，也不能应用于有向传感器网络中。针对上述局限，本文提出了有向传感器网络中基于概率感知模型的最小连通k覆盖集问题（MCKS），并指出这是NP难问题；设计了基于0-1整数规划和最小生成树的集中式近似算法（IPA）和基于覆盖效益探测的分布式近似算法（CBDA），分别证明两种算法最终得到的是M