论文部分内容阅读
近年来,研究人员对Adhoc网络组播已有了较深入的研究,但仍然存在一些关键技术至今尚不成熟,在对组播树结构的研究中,普遍认为Steiner树是最小代价组播树。但是,这一结论在无线组播通信中并不成立,由于无线媒介的广播本质,组播通信的能量主要由节点转发消耗,总体取决于组播树中的报文转发次数,也即承担转发任务的节点个数。因此,最小化Adhoc网络资源消耗的目标就是要建立一棵转发节点数最少的组播树,此问题归结为图论中寻找最小连通支配集(MCDS)问题。另外,在组播协议方面,作为路由协议基础的泛洪广播技术由于存在网络风暴及节能等问题,使得泛洪广播仍然无法胜任实际应用的需要。针对以上问题主要研究了一下几个方面的问题:1)移动Adhoc网络中基于连通支配集的广播算法;2)移动Adhoc网络中基于连通支配集的组播算法及有时延约束的组播算法;3)移动Adhoc网络中基于连通支配集的组播协议。本文的主要工作和创新点如下:
由于无线信号的发送具有广播特性,无线网络中的能量和带宽资源主要由无线广播发送消耗。本文基于构建具有最少非叶子节点的组播树来实现最小化组播通信转发次数的目的,提出了在Adhoc网络环境下用MCDS近似算法构建组播树算法;给出了静态网络中基于MIS策略的最小化MIS连接节点的CDS构造算法和移动网络中基于广播策略的组播支配树的动态构建及维护算法;用数学方法证明了该算法的正确性及性能下限的存在。
根据无线信号传播方式的特殊性,重新定义了无线组播路由中的代价和时延函数,基于图论中最小连通支配集(MCDS)理论,提出的基于图论中点着色思想的时延定界组播转发结构的构建方法,通过求解MCDS来实现构建最小代价组播路由结构的目的,提出了组播路由时延定界的概念,并在该约束下构建MCDS。理论推导证明了该算法的正确性,与同类算法相比,较低的近似比证明了该算法的有效性,同时具有O(n)的时间复杂度和O(n)的消息复杂度,进一步证明了其高效性,具有适应于灵活多变的Adhoc网络的优势。