无线传感器网络中最大集合覆盖的最优解

Optimal solution for maximum set covers in wireless sensor network

无线传感器网络因其广泛的应用而成为众多学者竞相研究的领域。特别是WSN中传感节点的最大集覆盖(MSC)问题被提出至今一直被许多研究人员研究,MSC问题旨在降低能耗并延长WSN的使用寿命。原MSC问题的主要模型形式是非线性整数规划问题,非线性整数规划已被证明是一个NP-Complete问题。由于很难找到原MSC模型的最优解,所以大多数文献都集中在启发式方法上。虽然这个策略在一定意义上提供了一些有用的解决方案,但就MSC问题而言,往往不是最佳解决方案。原MSC问题用等价的线性规划问题来描述。新MSC模型极大简化了原MSC问题,并且可以高效地计算出新MSC问题的最优解。通过一个简单的例子,描述了基于图论建模过程的细节。针对大规模、随机部署的无线传感网络,新MSC模型完全具有普适性。由于现实中部署的无线传感网络具有节点数量多、节点部署随机性强的特征,即使是新MSC模型涉及的变量与约束的数量依然十分庞大,若采用传统的单纯型方法求解新MSC模型的线性规划问题,效率将十分低下,所以使用了效率更高的内点法求解。仿真表明,通过内点算法求解新MSC问题是非常高效的。