论文部分内容阅读
在图论中,如何有效构造图的连通支配集(CDS: Connected DominatingSet)是一个极富挑战且极具应用价值的NP-hard问题。在无线传感器网络中,它是构造虚拟骨干网的理论基础。虚拟骨干网在路由、分簇和节能等诸多方面都有着重要的意义,因此,研究基于CDS的分布式构造算法将具有重大的理论和现实意义。另外,由于无线节点的能量受限,最大化传感器网络的性能和延长网络有效生存时间是两个相互矛盾的优化目标。基于网络效用函数的建模和跨层分解计算在网络多目标优化上展现出巨大的优势,在能量有效的速率和功率控制算法以及MAC层协议设计等方面提供了优化求解的思路。本文在能量有效的网络拓扑构建和速率优化控制方面做了系统和深入的研究工作。针对NP-hard的CDS构造问题提出了一种基于加权最优Steiner树且近似系数有界的近似算法,并将CDS的构建思想应用于能量有效的分簇中,并提出了分布式的分簇构建算法;在速率优化控制方面,针对不同的网络建模提出了最优速率分配算法和自适应的速率控制算法。本文主要有以下工作:1.在拓扑控制的理论研究方面,本文改进经典的染色支配集构造算法,将贪心算法引入到了算法的本地化过程中,有效的改进了加权最优支配集的构造,并通过理论证明分析了算法的常数渐进上限。针对CDS的构建问题,本文提出了一种基于加权Steiner树的最小连通支配集优化构造算法。通过对节点的赋权,可以将最优Steiner权值树与连通支配集规模的最优性相对应。为了保证算法的有效性和构造理论的完整性,本文还对连通算法的近似上限进行了严格的数学证明,给出了该算法构造出的支配集的规模与理论最优解之间的关系。另外,从与同类算法的比较中可以看出,本文提出的算法具有较好的连通效果;2.为了构建能量有效的层次型网络拓扑,本文给出了一种基于连通支配集的分布式成簇算法,通过有序连接本地贪心生成树,算法可以得到一个全局连通的优化拓扑。与同类工作相比,这种有序构造算法更利于分布式实现,另外,本文还在数学上就构造算法的连通性给出了严格的证明。最后,针对不同的网络指标,将算法与同类工作进行了大量的仿真对比实验,实验结果表明,算法在能量有效性和分簇均衡等诸多方面均有着显著的改进效果;3.在速率控制方面,本文通过将全局能量的最优性和速率效用函数最优性的加权综合作为多目标优化的目标函数,并通过对偶分解的优化计算方法,给出了分层设计的迭代算法,并就算法的分布式近似实现问题进行了深入的讨论。与同类工作相比,算法着重于多汇聚节点源速率优化问题的建模和控制,且在实现中不需路由反馈因子的参与,本文中理论分析和仿真实验结果都确保了算法解的最优性。4.在链路质量受限的无线网络中,针对速率和功率控制的问题,本文结合瑞利信道的特点和链路实际吞吐量的概念进行了多汇聚节点源速率优化的建模。由于优化问题的非凸特性,算法的求解采用了渐进凸近似的方法,并在数学上证明了近似解序列的收敛性。最后,本文还就信道估计和算法的实现等问题进行了分析,给出了多汇聚节点源速率优化问题的分布式算法。由于这里的速率控制方案基于实时的信道参数估计,算法还具有较好的自适应性的特点。