构造自组网的容错骨干集

为简化网络结构和提高网络性能所使用的骨干网技术若未考虑容错易造成自组网无法面对节点和无线信道失效.本文研究了如何利用容错骨干来提高网络可靠性,设计了一种分布式容错骨干集构造算法LKFB,满足网络内任意两点之间仅通过容错骨干集保持最大限度K连通容错能力.仿真结果表明,LKFB能够通过改变K值来调整网络的容错能力,通过增加较少的骨干节点换得较高的容错性能.最后通过修改权值函数能够保证按照全网能耗均衡的方式选择容错骨干.

一种求解命题公式骨干集的警示传播算法

警示传播WP算法是一类重要的信息传播算法,在命题公式的可满足性判定中非常有效。通过对WP算法的数学原理分析发现,当算法收敛时以高概率固定部分变元的赋值,可以对公式进行化简。基于这样的特征修改WP算法的迭代方程和变元赋值条件,设计了一种求解命题公式骨干集的信息传播算法。当变元数目超过400时,与经典骨干集求解算法对比,效率提高了40%,与目前常用算法对比也有10%的提高。结果表明,所提算法求解命题公式骨干集时非常有效。

基于骨干结点集的移动IP组播路由算法研究

为了优化移动IP组播生成树代价,减少移动结点切换加入时延和信息传输时延,引入了移动IP"骨干结点集"思想,设计了移动IP组播路由算法BNSBMR(bone node set-based multicast routing algorithm)."骨干结点集"是移动IP环境下满足一定条件的IP子网接入路由器AR(access router)的集合.该算法通过"骨干结点集"降低移动IP组播生成树的代价;减少移动结点切换的加入时延;并通过路径优化降低信息传输时延.从理论上证明了算法的正确性,并分析了其计算复杂度.仿真实验表明:BNSBMR算法从树代价、加入时延、传输时延3个方面提高了移动IP环境下组播业务满足QoS约束的能力.

WP可解公式上警示传播算法收敛的有效条件

通过对警示传播(warning propagation,WP)算法的数学原理分析,高概率确定的部分变元与公式的骨干集和后门集有密切关系。针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n,3,m)模型和植入指派模型下证明WP算法的收敛性,给出算法收敛的充要条件。最后,通过在植入指派的公式产生模型上进行数值实验验证,结果表明:如果一个可满足性公式WP-可解公式,当且仅当WP算法高概率收敛。

一个有效的分布式移动IP组播路由算法

为了优化移动IP环境下组播树的代价,减少移动结点的切换时延,设计了分布式移动IP组播路由算法BNSBMR(Bone NodeSet-Based Multicast Routing Algorithm)。该算法使用"骨干结点集"的思想,能大大降低组播树代价,并优化切换时延;同时使用分布式的策略来进行设计,使得算法具有良好的可扩展性,有利于在大规模移动Internet上的实现。仿真实验表明:根据该算法生成的组播树代价、时延等性能明显优于其他同类移动IP组播路由算法。