摘要:
1．本文的创新点
本文的创新点在于下列的两个方面：
1) 针对无线传感器网络中的目标覆盖问题，提出了基于松弛思想的两个生命周期的上界。上界的意义在于，它们可以被用来对启发式算法的性能做进一步的刻画。
2) 设计了一种最优的基于列生成的算法，保证了解的最优性或者近最优性。它可以被很容易的扩展去适应其他相似的目标覆盖问题，如Maximum Set Cover问题。
2．实现方法
前人研究传感器网络中的目标覆盖的文献，或者是专注于提出启发式算法，这些算法的性能不能被很好的论证, 或者是对问题本身进行了松弛(relax)以降低问题的复杂度根据调研的结果，对传感器网路中的目标覆盖问题并没有理论上的结果。为了填补这一空白，本文提出一个普适的优化体系，这个优化体系可以用来求解一系列相似的目标覆盖问题。这个体系包含了以下两个模块:
第一个模块提供了两个生命周期的上界，它们可以用来验证前人文献中提出的启发式算法的性能表现。第一个上界是基于对MINLP 模型的松弛与再建模(relaxation and reformulation)，第二个上界是基于对覆盖需求的松弛。具体来说，原本的覆盖需求是，对任何一个目标节点来说，在任何一个时刻都至少被 个活跃的传感器节点所覆盖，松弛以后的覆盖需求为，对任何一个目标节点来说，平均每个时刻都被至少 个活跃的传感器节点所覆盖。同时，还发现了这两个上界之间的联系，由此给予了它们以物理上的意义。考虑到上述的松弛技术具有普适性，同样可以被用来应用于其他相似的目标覆盖问题，例如MSC问题。因此，这两个上界的意义不仅仅局限于TQC问题，它们也同样可以被应用到其他相似的目标覆盖问题，并用来对这些问题上的启发式算法的性能做验证。
第二个模块包含了一个基于列生成(Column Generation, CG)理论的算法，目标是得到最优解。算法的输入为网络拓扑以及覆盖需求，输出为一个最优的时间表，这个时间表具体规定了从哪一时刻到哪一时刻，哪个传感器节点覆盖哪些目标节点。这个算法将MINLP 模型分解成一个主问题与子问题，并通过对它们的迭代求解以取得最优解。这里一个“列”就代表了一个“覆盖模式”, 基本的想法是迭代地将对当前解最优的那个覆盖模式从解空间中搜索出来，并判断加入了这个覆盖模式后，得到的解是是否是最优，如果是，就停止，否则就继续重复这个过程，由于解空间的大小是有限的，因此这个算法一定会停止。由于CG算法需要一个初始的可行基，提出了一种基于随机选取的算法去的到一个初始可行基，以加速迭代的收敛。此外，考虑到子问题是一个整形规划(Integer Programming, IP)问题，在传感器网络中这样的整形规划问题的求解耗时非常严重，为了解决这一点，并不直接的求解子问题，而是先将它松弛到一个线性规划问题(Linear Programming, LP)，并且提出了近似算法将得到的线性解映射到一个整形解。由于线性规划问题可以在多项式时间来求解，因此在经过这样的过程后，成功的降低了CG算法每一轮的时间复杂度，并且同时证明了这样的一个处理算法也可以保证解的性能。
3．结论及未来待解决的问题
本文主要试图解决传感器网络中对物理目标的最优覆盖问题。首先对这个优化问题简历了一个非线性的优化方程。考虑到直接求解非线性方程的困难度，直接求解是不可取的。本文的贡献在于提出了两个理论上的结论。第一个贡献为网络的上界。基于低不同的松弛技术，得到了两种不同的上界。这两个上界之间存在着重要的联系，并且这中联系确认了二者的物理含义。在这一类型的覆盖问题中，提出的上界的意义在于，它们也可以同样被应用于相似的问题如最大集覆盖(Maximum Set Cover)问题。并且由于它们对小规模问题的求解效率很高，因此可以被用于与启发式算法进行比较，以验证这些启发式算法的效率。
第二个结果为基于列生成的算法，这个算法将原来的非线性的问题分解上两个子问题，并且通过迭代的求解它们去逼近最优解。试验的结果告诉，基于CG的方法可以有效的求解提出的覆盖问题，得到最优或者接近最优的结果。
由于问题本身的困难度，能够取得最优解的CG算法计算复杂度较高，因而在小的问题规模下，可以被实际应用。当问题的规模较大时，计算的耗时较高。因此，第一个需要解决的问题即为如何有效的降低CG算法的复杂度。第二个为建立一些多项式时间可解的启发式或者谈心算法，尤其是可以保证性能的相应的多项式时间复杂度算法。
4．实用价值或应用前景
本文解决的问题可以被归结于无线传感器网络的基础研究问题。因此在具体的应用前景比较广阔。考虑到无线传感器网络的主要应用在与对物理世界的监控问题，而在涉及到物理目标可以被归结为“点目标”的时候，本文提供的方法就可以被很好的应用。