论文部分内容阅读
无线传感器网络是由部署在物理空间内的大量廉价微型的传感器节点通过无线通信技术自组织构成的网络系统，可实现特殊环境下的数据的采集、处理和传输功能。无线传感器网络是当前信息领域的研究热点之一，其应用前景广阔，可广泛用于国防军事、环境监测、医疗监护、工业控制、智能家居等方面。由于无线传感器节点体积微小，通常携带的能量十分有限，这使得能耗成为制约无线传感器网络使用寿命的关键要素之一。降低节点能耗的常用方法之一是减少因邻近节点同时传输信号所产生的干扰。因此，如何减少干扰成为无线传感器网络中的一个基本问题。拓扑控制技术能有效地减少无线传感器网络中的干扰，它旨在通过调整各传感器节点的发射半径来获得一个干扰较小的连通拓扑。在普遍采用的接收者中心干扰模型下，无线传感器网络中干扰最小化问题已经被证明是NP难度问题，当前有一类简单常用的算法是称作最近邻法的贪心算法。本文目的是在此基础上为无线传感器网络中干扰最小化问题设计出更有效的算法。 本文主要工作是改进已有最近邻算法在某些最差情况的性能而提出新的贪心算法。最近邻法的贪心策略是每次通过调整某两个节点的发射半径使得当前网络中距离最近的两个连通部分能连通起来，直至整个网络连通。所提出的新的贪心算法叫作最佳邻算法，其贪心策略是每次调整使得当前网络干扰最大增幅最小的某两个节点的发射半径来将当前网络中两个连通部分连通起来，直至整个网络连通。通过吸收图最小生成树问题的Prim算法和Kruskal算法的思想可对新算法采用不同的实现方式，我们得到两种具体的最佳邻算法，分别叫做基于Prim算法的最佳邻算法和基于Kruskal算法的最佳邻算法。基于Prim算法的最佳邻算法的主要思想是每次调整连通部分内某点u和其外某点v的发射半径，将v并入到连通部分且使得对当前网络中节点的干扰最大增幅最小，直至整个网络连通。基于Kruskal算法的最佳邻算法的主要思想是每次调整来自两个不同连通分量中的某两个点的发射半径，将这两个连通分量连通起来且使得对当前网络中节点的干扰最大增幅最小，直至网络连通。在这两个最佳邻算法中，当满足贪心策略的节点对有多个选择时，则优先选择距离最近的节点对，此时最佳邻算法兼顾了最近邻算法的特点。 为了评价算法所获得解的质量，我们首先在最近邻算法表现较差的一些典型的算例上比较了最佳算法与最近邻算法，结果表明两个最佳邻算法明显要优于最近邻算法。对一般情况，我们通过产生大量随机算例对两个最佳邻算法和最近邻算法进行了比较，实验结果表明，在这些算例上两个最佳邻算法都要优于最近邻算法;而两个最佳邻算法的效果差别不大，但在那些图中点呈现“分块”特征的算例上基于Prim算法的最佳邻算法要略优于基于Kruskal算法的最佳邻算法。