从节点度数生成无向简单连通图

许多现实问题可以抽象成无向简单连通图的生成问题。为了从节点的度数序列得到所有可能的无向简单连通图,针对度数序列设计了适合用计算机实现的去点回溯算法,证明了算法的正确性,通过每一步去点回溯后的变化矩阵,得到生成无向简单连通图所需的邻接矩阵,并最终用计算机实现了该算法,解决了节点度数已知时无向简单连通图的生成问题。     

三维最优持久编队拓扑生成策略

针对智能体间的通信拓扑优化问题, 结合图论知识研究了三维空间中最优持久图的生成算法. 首先,利用刚度矩阵生成最优刚性图;然后,根据顶点连通度数的不同分别采取有向化操作方法, 通过逐层缩小最优刚性图范围的方式把刚性图持久化,生成了最优持久图;最后, 对三维空间中随机分布的智能体进行仿真实验,其结果验证了该算法的可行性和有效性, 此算法能降低编队拓扑的通信复杂度,减少通信能量消耗.     

基于扩展力学模型的网络拓扑图布局算法*

针对现有网络拓扑图布局算法多以节点分布均匀为目标,没有考虑边的布局,可能会导致生成的拓扑图中边布局不清晰,提出一种基于扩展力学模型的网络拓扑图布局算法。该算法通过引入点边斥力保证边布局清晰,通过节点坐标的分层分配可以方便地满足某些网络的拓扑图层次布局需求。仿真结果表明,扩展力学模型生成的拓扑图节点分布均匀,节点和边之间距离合理,布局效果得到提高。     

三维无线自组网络的成簇及自适应路由算法

针对三维无线自组织网络拓扑结构复杂导致的不易寻路的问题,提出成簇算法和基于部分超立方体网络结构(PCCN)的自适应路由算法.成簇算法考虑到节点疏密不均的情况,利用节点的空间密度分布将节点分割成候选簇,采用融合机制将候选簇构建成更均匀的簇结构.使用实际拓扑到虚拟拓扑的转化策略,在簇结构的基础上构建PCCN.PCCN作为虚拟拓扑结构,简化了实际网络拓扑,具有可扩展性、延伸性能好等优点.利用PCCN,对节点进行编号之后进行自适应路由.自适应路由算法包括簇内和簇间路由两种情况.算法分析及算例表明,PCCN简化了三维网络的拓扑结构,能够有效路由,为三维自组织网络的管理提出了新的方法和手段.     

服务质量路由算法仿真平台的设计与实现

下一代网络服务质量要求解决多约束服务质量路由问题.在分析服务质量路由特点及相关工作的基础上,设计服务质量路由算法的仿真平台.仿真平台基于随机网络模型,结合Waxman方法设计随机连接的产生方法,并通过深度优先搜索遍历算法来检查图的连通性.通过对网络拓扑状态仿真结果表明,该平台能嵌入各种多约束路由算法并进行仿真实现.     

基于全网能量均衡的WirelessHART图路由算法

如何均衡使用网络节点能量并生成高可靠路由是WirelessHART网络研究的一个难题,为此提出了一种GRAEB（graph routing algorithm based on energy balancing）图路由算法。首先,网络被初始化为连通的图结构,能够提高丰富的冗余路径。网络管理器根据全网节点剩余能量、通信周期、链路分布等因子生成节点鲁棒系数矩阵,节点通过比较邻居的鲁棒系数来选择最优路径。另外,规定了邻居节点数的上限阈值,每次路由更新只保留鲁棒系数最优的邻居。仿真结果表明GRAEB不仅提高了网络可靠性,而且延长了网络寿命。     

安全审计域的规划模型

介绍了一种基于图论的安全审计域规划模型。该模型首先将真实的网络拓扑抽象为图论中的无向图连通图，并求得其关联矩阵。然后计算图中的割点，以割点为边界将整个无向图连通图划分为若干个块，构造出无向图连通图的块图。对于网络拓扑而言模型得到的割点分布即为网络中关键节点的分布，而块图就是安全审计域的规划分布。通过测试表明，该模型对于安全系统中审计节点及防御节点的合理部署起着非常重要的指导作用。     

一种适合多域WDM光网络的拓扑聚合算法

根据多域波分复用光网络的特点提出一种以波长为压缩参数的拓扑聚合算法。该算法根据原拓扑资源图构造边界节点的全连通拓扑,在其基础上进一步压缩为非对称星型图。用随机产生的网络拓扑仿真表明,算法能在很小的精度损失情况下有效地压缩信息。相对于全连通拓扑,其压缩后的复杂度可降低到O（N）。     

基于三角构成规则的加权有向网络拓扑生成算法

针对加权无向图的网络拓扑模型难以表征真实网络环境下节点间有向性的问题,提出了基于三角构成规则的加权有向网络拓扑生成算法,依据概率优先选择节点的邻居节点进行有向性加边,通过网络边权的动态演化实现节点间的不对称性增长。并利用该算法进行了仿真实验。实验表明,基于三角构成的加权有向网络拓扑算法生成的网络拓扑结构符合真实环境下的网络拓扑结构所体现出来的拓扑特性,同时具有较好的聚类系数可控性。     

容断网络中基于ACK机制的喷射等待路由

容断网络(DTN)试图通过间歇连通的节点传送信息,其路由的困难在于连通是机会性的,节点间缺乏网络拓扑连接的信息。喷射等待路由是这种网络的一种高效路由策略,它先向网络中喷射一定数目的消息副本,然后等待其中之一遇见目的节点。与传染路由算法相比,喷射等待路由消耗的网络资源明显减少,但在高网络负载下仍遭受严重的资源竞争。为此,在喷射等待路由分析的基础上,针对缓存消耗大、带宽效率不高的问题,提出利用ACK机制移除冗余的消息副本和使用令牌转发技术提高带宽利用率的改进机制。通过仿真平台ONE对改进算法进行了仿真分析,结果表明改进后的算法虽平均延迟略有增加,但能够提升投递率,降低网络资源消耗量。该算法不依赖任何预先连接知识,适用于间歇连通移动网络环境。