共查询到20条相似文献，搜索用时 15 毫秒
1.
本文考虑到节点度的代价问题 ,提出了广义最小生成树的概念 ,并分析了最小生成树在实际应用中的局限性 .针对一般遗传算法求解该问题的不足 ,提出了自调整的变异算子和混合选择策略 .通过仿真 ,证明了广义最小生成树模型的适用性 .最后将改进前后两种算法的仿真结果进行比较 ,证明了改进后遗传算法的有效性 . 相似文献
2.
量子遗传算法求解度约束最小生成树 总被引：1，自引：0，他引：1
度约束最小生成树问题属于NP完全问题,但在现实中具有非常重要的应用价值.针对度约束最小生成树问题,采用量子遗传算法来求解该问题.并对基本的量子遗传算法进行改进.针对度约束最小生成树问题的特征,设计了一种新的量子编码方式,保证算法获得可行解;并与深度优先搜索的思想结合,保证得到树的连通性;通过数值试验验证新算法的可行性,并与其他算法进行比较.取得了良好的效果. 相似文献
3.
索红军 《渭南师范学院学报》2012,(10):78-80
文章联系实际问题,结合旅行商问题和中国邮递员问题,提出赋权连通图中最小环路遍历路径以及求解该路径的方案.该方案参考最小生成树的普里姆算法,依据狄杰斯特拉算法,通过往返最短路径逐次比较,在赋权连通图中实现寻找最小环路遍历路径. 相似文献
4.
由于Odd-Eyen路由算法对数据包能够发生转向的位置进行了限制,使得NoP选择策略在选择数据包输出信道的时候必然会优先选择某些固定的方向.这就使得网络节点负载不均衡.所以,该选择策略在具有hotspot类型节点的通信模式中性能较低.文中提出了改进的NoP选择策略(ANoP).该选择策略能够克服NoP选择策略的缺点,使网络流量均匀分布.在ANoP选择策略下,流量在水平方向的传播较远,这就使得它比较适用于非对称的mesh网络.仿真结果表明,在具有hotspot类型节点的通信模式中,ANoP选择策略的平均性能比NoP选择策略提高达24%. 相似文献
5.
6.
针对无线传感器网络虚拟骨干时延和功耗的约束问题,提出（α,β）-约束的连通支配集算法．根据（α,β）-约束定义了时延约束的连通支配树问题（CDTT）,并给出构建同时符合时延约束和有限总功率消耗的连通支配树（CDT）算法．算法分为2个阶段执行：首先在单位圆图上构建网络的极大独立集,然后在无向图上基于不同权值的最小生成树和最短路径树,构造满足（α,β）-约束要求的支撑树．理论分析和仿真结果表明提出的算法能够正确地解决CDTT问颢,并能够构建平衡功率消耗和传输时延要求的无线传感器网络虚拟骨干． 相似文献
7.
由于无线信道的广播特性,无线网络中任一节点发送的无线信号都可能被其通信范围内的其它节点接收。因此,当同一地理区域范围内的节点同时传输信号时,会形成相互干扰,从而导致信号无法正确接收。有效协调多个簇共享无线信道资源,避免冲突发生是ZigBee簇树网络面临的关键问题之一,直接影响无线资源的使用效率、网络吞吐和时延等重要性能。针对这一问题,提出基于时分的自适应SD（TD-ASD）调度算法。理论分析和仿真结果证明,TD-ASD算法可以运用在ZigBee网络中,并且在不同输入业务条件下,与传统ZigBee算法相比,该算法提高了系统吞吐量,降低了网络工作负载和端到端的平均延迟。 相似文献
8.
为了提高数据分发效率,在发布/订阅模式下提出了一个面向负载均衡的数据分发方法 LBDD.在LBDD方法中,订阅方既接收数据,又承担数据转发工作.采用M D5算法,在发布方和订阅方间建立一棵分发树,其中发布方是根节点.给出了桶建立、目标选择以及路径修正方法,并进一步证明了数据单向分发性质.LBDD方法可保证分发树中任意一个节点的平均出度为2.针对数据分发延迟、数据分发速率和负载分布进行了实验.实验数据表明,LBDD方法能够有效地均衡发布方和订阅方的负载,分发效率高于点到点分发方式. 相似文献
9.
《实验室研究与探索》2017,(1):117-122
针对现有无线传感器网络数据汇集算法延时较大这一不足,对最小延时数据汇集树和传输调度问题进行了研究。提出一种基于度约束的汇集树构建算法(DCAT)。该算法按照BFS方式遍历图,当遍历到每个节点时,通过确定哪些节点与汇点更近来确定潜在母节点集合。然后,选择图中度数最小的潜在母节点作为当前被遍历节点的母节点。此外,为了在给定的汇集树上进行高效数据汇集,文中还提出两种新的基于贪婪的TDMA传输调度算法:WIRES-G和DCAT-Greedy。利用随机生成的不同规模的传感器网络,参照当前最新算法,对本方法的性能进行了全面评估。结果表明,与当前最优算法相比,本调度算法与汇集树构建算法结合起来,可显著降低数据汇集的延时。 相似文献
10.
在量子通信过程中,通信质量主要受到量子噪声、通信节点数、纠缠粒子数等因素影响,为得到更适合实际应用的通信路由,对相位阻尼信道进行研究。在以最小等效阻尼系数为度量的最佳中继路由算法基础上进行改进,给出一种综合性路由度量的最佳路由选择方案。该方案充分考虑了对通信路由影响较大的几个因子,并采用路径先验方案以避免路径失效后网络进行通信请求。理论分析与仿真对比结果表明,该路由协议使路径节点中的最小纠缠粒子对数得到明显提高,从而提高了网络稳定性。 相似文献
11.
12.
13.
以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了"无性生殖"的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高.使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树. 相似文献
14.
无线传感器网络的DV-HOp定位算法是通过计算未知节点和锚节点的最小跳数,估算平均每跳的距离,并使用跳段距离代替实际距离来计算未知节点坐标。当节点规模变大、连通度过高时,该算法定位精度大大降低。根据DV-Hop算法的定位过程,考虑到节点位置的相对稳定,在DV-Hop的定位中应用ATR-CKN睡眠调度算法,让部分锚节点和已经定位的盲节点进入睡眠,从而降低节点规模和冗余定位信息,保证了节点低能耗下的精确定位。仿真结果表明,采用ATR-CKN睡眠调度算法的网络节点能量消耗大大降低,DV-Hop算法的定位精度也有提高。 相似文献
15.
在Ad Hoc网络中,链路间共享信道的机制导致干扰的产生,造成分组丢失、频繁重传,影响网络可用性和持续时间。以优化整个网络的干扰度为原则,提出一种连通子图生成算法—DBSA,将原始的全连通图简化为一张新的能够保持连通性的子图,在保证网络连通的情况下延长网络生命周期。仿真结果表明:DBSA算法能实现预期目标,并拥有比CPC算法更低的转发代价。 相似文献
16.
求解最小生成树是《数据结构》课程教学中的一个学生重点学习的图论问题,但是目前的教材中普遍讲解Prim算法和Kruskal算法,这两个算法的基本思想均是基于避圈法。而从相反的角度求解最小生成树:破圈法构造最小生成树算法,虽然该算法的时间复杂度较高(O(n3)),但从教学的角度来看,有利于训练学生深刻理解和掌握最小生成树算法。 相似文献
17.
ZigBee网络的传统算法(簇树路由算法和AODVjr路由算法)在发现路由过程中节点能耗较大。为此,结合节点能量、簇树路由算法和AODVjr路由算法,提出一种改进的ZigBee网络路由算法。该路由算法选择路由时尽量避免能量较低的节点,选择最佳路径,维持网络稳定性。仿真结果表明,改进后的算法能有效降低整个网络总体能耗,合理分配网络负载,大大降低了死亡节点数量,从而延长整个网络的使用寿命。 相似文献
18.
19.
网络用户大幅度增加为网络发展带来机遇的同时也带来了挑战,当前使用的数据负载均衡方法节点数据分发能力较差导致网络节点吞吐量较低。因此,设计了基于深度强化学习算法的高能效数据负载均衡方法。选择隐式并行程序设计方法,设计网络数据并行程序。根据存储节点个数,设计数据分配与迁移方法。根据存储节点数据量与特征,选择深度强化学习算法,实现高能效数据负载均衡。构建仿真分析环节,经多次测试证实,深度强化学习负载均衡方法具有调节网络节点平均吞吐量的能力,且此方法的使用效果优于当前所使用的其他方法。 相似文献
20.
研究了给定一个连通图,如何确定其Wiener数最小的生成树问题。Dobrynin等构造了超立方体的两类Wiener数“很小”的生成树,并进一步猜想这两类树都是Wiener数最小的生成树。利用归纳推理及递归关系,对更一般的且具有良好拓扑性质和较高网络模型应用价值的乘积图,如G1×G2、Kmn等,构造了相应的生成树并计算了它们的Wiener数的值,以期获得这些乘积图Wiener数最小的生成树。这些结果推广了Dobrynin关于超立方体的结果。 相似文献