论文部分内容阅读
近年来无线传感器网络在许多领域有着巨大的应用前景因而受到广泛关注。将一组传感器节点布局在指定区域,节点通过其装备的无线电装置和能量互相通信,由此构成一个无线传感器网络。由于节点能量非常有限,节省其能量来延长无线传感器网络的生命周期是十分必要的。而降低干扰提高无线通信效率可达此目的。 无线传感器网络中如何有效降低干扰是一个研究热点。这个问题常用拓扑控制技术来解决,该技术在保证网络连通性的情况下通过调节传感器节点的传输半径来降低干扰。普遍采用的问题模型是以接收者为中心的干扰模型。在该模型下,布局在平面上的无线传感器网络的干扰最小化问题已经被证明是NP难问题。因而在实际应用中,设计有效的多项式算法显得尤为重要。鉴于该问题本身结构相当复杂,现有的几个多项式时间算法的效果不佳,本论文旨在探究该问题的更有效的多项式求解算法。首先,我们提出了一个简单局部搜索算法,该算法从一个初始解开始,通过两个策略调整某些节点的传输半径来改进解的质量,直到达到一个局部最优解为止。其次,实验中我们发现简单局部搜索算法的迭代过程中存在选取待调整节点的次序敏感性问题,我们提出一种学习策略来改进该算法。该学习策略采用给干扰度大的节点加权的方法,通过若干次在同一初始解上执行简单局部搜索算法进而学习到一种效果较好的降低节点干扰的次序。通过大量模拟实验表明,我们所提出的简单局部搜索算法和基于学习策略的局部搜索算法在随机算例上所得解的质量方面通常要好于现有的算法。