论文部分内容阅读
无线传感器网络(WSN)早已成为进化计算体系研究的热点,对如国防安全、环境监测、智能家居、农业及医疗等诸多领域起到很大的推动作用。基于无线传感器网络(WSN)能够很好的联络物理与数字世界,它帮助人们更有效的观测目标、采集信息,进而执行制定的策略。这标示无线传感器网络在如森林火灾或战场环境等许多目标监控的情形中有着很大的发展应用潜力。但鉴于对这一类系统的复杂度及最重要的目标覆盖问题尚未很好的解决,并且很少有深层次的理论研究,这都阻碍了无线传感器网络在实际应用中的推进。本论文针对这方面研究的不足建立普遍适用的优化模型,并且进一步进行理论分析,提出实际有效的节能算法,推进无线传感器网络在实际中的应用。本文的具体的研究内容:(1)针对同构无线传感器网络静止目标覆盖问题,提出借由松弛及基于列生成算法两个理论。前者建立了以线性优化为基础的网络生命周期的上界方程,此理论为有效算法的性能比较建立了基准。基于分治迭代思想的列生成算法克服了前人所提贪心及启发式算法无性能保障的不足。重要的是,所提理论具有普适性,即对不同的覆盖问题只需调整优化框架中的某些细节,就可以产生有效的算法。(2)针对异构无线传感器网络中有路由需求的静止目标覆盖问题,重点解决在保持对不同种类、不同需求的目标覆盖情况下,如何通过对路由的调度最优化网络的生命周期。在对问题进行数学建模后,提出改进的列生成算法,它把基于列生成的算法与可取得较好初始可行基加快收敛速度的随机选择算法结合起来,并且改进算法终止条件进一步加速收敛,进而求得最优解。实验探究和分析了网络参数(如初始可行基、通讯半径、传感半径等)对网络生命周期的影响,验证了算法的有效性,该算法可对建立实际的系统提供指导。(3)提出目标非整型覆盖问题,并建立新的覆盖模型。新的非整型覆盖模型:目标其实并不需要在任一时刻都被覆盖,若这样,网络的瓶颈目标将大大限制生命周期,相对地,非整型覆盖,如80%的时间内被覆盖,就可以满足覆盖要求。基于新的覆盖模型设计了最优节点分配算法。通过实验验证了该算法相比于列生成算法在计算时间及性能参数等方面都有明显优势。