CMST问题的新算法

本文提出了解决按约束条件求最小代价生成树(简称CMST)问题的两个新算法,即给定结点数N,每个结点的负载,链路的代价及链路的容量后,在符合某些约束条件下,求代价最小的树结构.两个新算法的计算复杂性均为O(N^2).计算结果表明,新算法所得结果的代价低于几个现有算法,而计算复杂性比现有算法小得多.

基于混合遗传算法的树状注水管网拓扑优化

以投资最小为目标函数,以井间隶属关系的惟一性、连接注水井数量等限制为约束条件,建立了树状注水管网拓扑优化数学模型。根据模型特点,将优化问题分为分配层和几何层,分别采用遗传算法和非线性优化方法进行求解。并对遗传算法的操作过程进行了改进,调整了适应函数,采用随机多父辈适应函数值加权交叉和多种变异操作,结合了模拟退火算法,并给出了初温的确定方法,改进了选择复制操作,从而形成了混合遗传算法。该算法能够有效地提高收敛速度,避免早熟收敛。利用算例说明了该方法的有效性。

双环网络G(N;1,s)等价生成树

提出研究双环网络G(N;1,s)的抽象模型——等价生成树,并对其性质进行了研究,给出了双环网络G(N;1,s)等价生成树的构造方法.提出基于等价生成树G(N;1,s)的直径d(N;1,s)的求解算法,并给出了其显式公式,利用C语言编程对等价生成树的结构模型进行了仿真.结果表明:算法不仅可在有限时间内求出G(N;1,s)的所有直径,而且可方便地得到源结点到所有其他结点的最短路径.算法的复杂度为O(N).

基于满Steiner树问题的水下无线传感器网络拓扑愈合算法研究

建立了水下无线传感器网络模型,对拓扑愈合问题进行了形式化描述,该问题最终映射到数学上的满Steiner树问题。针对满Steiner树问题设计了一种近似的拓扑愈合算法,通过把自移动节点迁移至合适位置,不仅使拓扑得以愈合,还能够改善时延和能耗指标。仿真实验结果表明,该算法能愈合通信拓扑至较优状态,降低了传输时延和能耗,并能有效地延长水下传感器网络生命期。

树状结构网络在列车状态监测中的应用

为确保大数据量下列车状态数据传输有序、传输错误可修复,建立了列车状态监测设备树状组网模型,分析了树状拓扑列车在途监测系统应用的可行性,继而给出了支持自由挂载的车载设备组网算法,实现了基于以太网的数据传输和路由数据结构与算法在NS-2工具上的建模.仿真结果表明,树状网络延时主要受制于发送端与接收端所在网络的深度,相对于EXP流量模型和使用TCP协议,在树状网络中使用CBR流量模型与UDP协议能够获得更好的性能.

基于EM算法的树状注水管网优化设计

针对油田系统中的树状注水管网的拓扑优化问题,以最小管网造价为目标函数,以站、间、井的隶属关系惟一性及服务能力等为约束条件,建立优化数学模型。尝试利用一种新型优化算法——类电磁机制算法对模型进行求解,该方法以站、间的空间位置作为带电粒子,在若干带电粒子形成的电场中,粒子受力移动以更新管网的拓扑结构及站、间规模,实现对管网造价的优化。运用实例进行优化验证,优化后的管网造价与原管网的布局造价相比降低了15.28%,充分表明了EM算法在油田树状注水管网拓扑优化方面的有效性。

受限最小生成树算法在城镇管网布局优化中的应用研究

随着天然气输配管网规模的大型化,管网系统进一步优化对提高运行的经济效益和利用率显得非常重要.采用受限最小生成树算法对城镇燃气管网布局进行优化,并将该算法与最小生成树算法(prim)进行了比较.仿真表明,该算法实用性强,对城镇天然气系统工程投资的评估预算有重要的参考价值.

一种针对树形拓扑网络的混合MAC协议

在树形拓扑水声传感网络中,时分多址(TDMA)机制存在信道利用率低的问题。为此,提出一种轻量级的流量自适应随机访问与TDMA的混合MAC协议。该协议在网络流量较低时采用S-ALOHA竞争机制提高信道利用率,运用最优化算法计算分配给簇内子节点的最大发送概率,通过流量自适应的灵活时隙分配机制以适应不同的网络流量。实验结果表明,该协议不仅能够提高树形拓扑网络中节点的通信效率,能减少子节点的等待时间。

树拓扑片上网络的低能耗映射

针对树拓扑片上网络(NoC)中通信时延受约束的低能耗映射问题,提出了一种递归的二路划分算法RPM(recursive bipartitioning for mapping)。RPM基于分而治之策略,首先将NoC映射转化为多层次的IP核通信任务图划分问题,并采用带参数的Kernighan-Lin算法实现最小割值划分。实验结果表明,与已有算法相比,RPM可以在较短的时间内获得能耗更低的映射解。通过设置不同的参数,RPM既可以用于生成高质量的优化解,也可用于快速的NoC设计空间探索中。

LR-WPAN Mesh网络双重能效优化设计

针对IEEE 802.15.5低速无线个域网(LR-WPAN)标准缺乏能效均衡设计的问题,提出LR-WPAN Mesh网络双重能效优化方法。在自适应树建立和拓扑引导分布式链路状态路由环节中引入合理的能效评估要素,优化拓扑结构和路由选择。实验结果表明,双重能效优化方法可使网络寿命延长97%,并使网络的能耗更加均衡。

区块链网络拓扑优化和转发策略设计

为解决区块链网络的数据传输效率低问题,提出了区块链传输效率优化方法来优化网络拓扑和转发策略。首先,设计了可信值函数计算区块链节点的可信值,综合考虑可信值和传输时间构建树形拓扑。然后,基于树形拓扑设计转发路径选择策略,以最小整体并发传输时间为目标,建立节点关于其邻居节点转发次序的转发表。为了减小节点变化对树形拓扑的影响,提出了拓扑动态优化策略局部调整树形拓扑。转发路径选择策略使整个数据传输过程具有最小传输时间,动态优化策略避免重构全网拓扑,有效缩短数据传输时间。仿真结果表明,与权重优先算法相比,所提方法的传输时间减小了约20%,显著提高了数据传输效率。

传感器网络基于最优修复率的拓扑控制研究

针对无线传感器网络的使用寿命问题,提出一种基于最优修复率的拓扑构建算法(TC-OR)用于构造类正则树结构的虚拟骨干网.算法首先选取剩余能量较多、连通度较好的节点作为正则树的树节点;针对树上链路的联通情况,再选取补充树节点构成补充链路;最后利用退火算法,以骨干网修复率为评价函数,最终确定各个树节点在类正则树上的位置分配和补充节点,从而建立具有最优修复率的虚拟骨干网.对于使用TC-OR算法的无线传感器网络进行了仿真分析,结果表明提出的算法构建的虚拟骨干网具有较高的修复率,从而延长了无线传感器网络的寿命,且更适用于中小型网络.

VLSI电源/地网设计方法

对芯片有效供电的电源/地网设计在VLSI设计中非常重要。电源/地网布线设计方法可分成建立电源/地网拓扑结构、在已有拓扑结构及约束条件的基础上进行线宽优化等两步。本文简要介绍了电源/地网拓扑生成、线宽优化算法的研究进展,并指出了这些算法存在的一些问题。

路灯树型网络拓扑结构的边魔幻全标号算法

给出了路灯树型网络拓扑结构T(P_(m),S_(1,n),S_(2,n),…,S_(m,n))的定义,提出了该类网络拓扑结构的边魔幻全标号算法,证明了STREETLAMP_EMTL算法的正确性、时间复杂度及时间最优性,从而进一步得到了路灯树型网络拓扑结构T(P_(m),S_(1,n),S_(2,n),…,S_(m,n))的边魔幻性.

城市天然气管网的拓扑优化

提出了一种城市天然气管网的拓扑优化算法,介绍了目标函数、管网布置优化及算法实现。