论文部分内容阅读
无线传感器网络是当前国际上备受关注的,由多学科高度交叉的新兴前沿热点研究领域,具有十分广阔的应用前景。随着无线传感器网络的布置和无线传感器网络应用的发展,急需相应的控制和管理算法,这是无线传感器网络的发展所提出的挑战。本文由6章组成,重点研究了无线传感器网络中的路由算法设计、路由算法收敛性分析、能量消耗分析、网络寿命的优化模型与求解等问题。第一章是绪论,概述了无线传感器网络的概念、特点、性能评价、核心技术、无线传感器网络所研究的问题和研究进展情况,并且还介绍了蚁群优化的相关知识。
第二章研究了无线传感器网络中单源单汇和多源单汇路由算法。根据无线传感器网络数据传送的多跳特点,用动态规划的原理来设计传感器网络从单源到单汇的路由算法。基于动态规划,通过节点跳数生成算法为传感器网络中的每个节点赋一个表示到Sink点跳数的节点跳数值,具体设计了无线传感器网络的最小跳数(MinH)、最小跳数最大剩余能量(MinHMaxRE)和最小跳数最小费用(MinHMinC)三种路由算法,并且对它们进行了复杂性分析,这三种算法分别能够在多项式时间内找到符合设计要求的从单源到单汇的数据传输路径。此外还探讨了最小跳数最小费用路由与最小费用路由之间的关系,给出了判断最小跳数最小费用路径是最小费用路径的一个充要条件。对于无线传感器网络中多源单汇的路由问题,可以通过最小Steiner树模型来描述,本章建立了以数据为中心的无线传感器网络路由问题的Steiner树模型。通常,最小Steiner树问题是NP难问题,为了满足实际需求,必须寻找有效的启发式求解算法,蚁群的择路行为与传感器网络的路由具有十分相似的特点,针对现有求解Steiner树模型蚁群优化算法收敛性慢、早期很难找到可行解、易陷入局部最有解等不足,给出了求解最小Steiner树模型的改进蚁群优化算法。该改进算法通过增加探索蚂蚁和清道蚂蚁来设置和清除到Sink点的路标,大大提高了早期找到可行解的可能性;通过信息素的局部更新实现了信息素对择路概率的全局调解,加快了算法的收敛速度。模拟结果表明,无论从求解速度还是从所得解的质量讲,所给改进算法能够满足无线传感器网络的实际需要。
第三章研究了以数据为中心的求解无线传感器网络多源单汇路由问题蚁群优化算法在不同条件下的收敛性。首先以无线传感器网络中的核心问题之一,路由问题为例,建立了相应的最小Steiner树模型,给出了求解最小Steiner树的蚁群优化算法的框架。把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解。其次给出了求解无线传感器网络路由的信息素受限的蚁群优化算法,对算法的收敛性进行了证明,并对找到最优解后信息素值的变化进行了分析。即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值。最后注意到在蚁群优化算法中,信息素的更新规则直接影响着算法性能,固定挥发率条件下,虽然也能得到求解无线传感器网络路由问题的最小Steiner树模型的蚁群优化算法的收敛性结果,但算法的探优能力差,易于陷入局部最优。于是在设计求解最小Steiner树蚁群优化算法时,采用了动态更新信息素挥发率的方法,并给出了时变挥发率条件下算法的收敛性证明。具体的,在时变挥发率条件下,当迭代次数充分大时,该算法能以概率1找到最优解。另外,在动态更新信息素下界的条件下,也能得到类似的收敛性结果。
能量问题是决定无线传感器网络寿命的核心问题之一,第四章对无线传感器网络能量消耗的不均匀性进行了研究。理论分析表明,无线传感器网络中传感器节点平均消耗的能量是不均匀的,它随离Sink节点(或异构网络中的上一层节点)跳数的增加而快速单调递减。传感器网络中能量的利用率是很低的,而能量的浪费系数很高;它们分别随离Sink节点(或异构网络中的上一层节点)跳数的增加而单调降低和增加。本章首次提出传感器网络的剩余能量、传感器网络的能量利用率和能量浪费系数等概念作为传感器网络能量分析的基础,具体分析了格子网络和随机均匀网络中能量的消耗情况,格子网络中第h跳节点的平均能量负担为(H-h+1)(H+h)/2hEr,能量利用率和能量浪费系数与网络最大跳数H的关系是2(2H+1)/3H(H+1)和(H-1)(3H+2)/4H+2,当网络跳数大于2时,剩余的总能量就会远远超过网络实际消耗的能量。而对于随机均匀分布的传感器网络,能量的浪费则更为严重。为了节省能量,提出了变发射半径的节能方案;作为应用,构造了一种拟格子网络,并给出了能量消耗均匀的路由算法,从而达到了降低剩余能量、延长网络寿命的目的。分析表明:在拟格子网络中,由于各跳节点平均能量消耗相对比较均匀,拟格子网络的能量利用率比格子网络有了大幅度的提高。当网络最大跳数为5时,能量利用率提高了2.45倍,而当网络最大跳数为10时,能量利用率提高了4.16倍。
在第五章中,对于有两类无线传感器网络组成的异构监测网络,通过异构传感器网络中成功完成的数据收集次数来定义传感器网络的寿命,给出了反映被监测区域平均连通覆盖程度的条件,通过网络中所有传感器的“突然死亡”效应来减少网络的剩余能量,给出了考虑连通覆盖约束条件的求解网络寿命的最优化模型;根据KKT条件,最优解处的不等式约束可以转化为等式约束,得到了最优模型的最优解,该最优解对于实时调整传感器网络的感知/发射半径,提高传感器网络最大寿命,具有很强的指导意义。数值结果表明,网络最大寿命值随传感器的感知/发射半径的增加而减小;同时传感器发射半径的调整,可以提高网络寿命。