连通支配集

摘要： 矿井事故常导致部分通信链路损坏、通信网络连通性恶化,利用残存节点和有限的新设节点,通过构造局部虚拟骨干网方式重构矿山救援网络可降低网络能量开销,增强连通覆盖控制能力。提出了一种基于多维度虚拟骨干网构造的煤矿井下无线自组网灾后重构算法。考虑无线传感器网络介数中心度、节点紧密度、节点剩余能量筛选机制3个维度,构建了虚拟骨干网节点综合评价指标,选取综合评价指标大的节点作为统治节点,以增强虚拟骨干网的鲁棒性,延长网络寿命。介绍了虚拟骨干网构造过程:在初始阶段,通过多轮选举产生统治节点并更新支配集;在支配集连接阶段,选举出中继节点,各统治节点、中继节点建立连接,形成连通支配集。采用一阶无线电能耗模型分析了虚拟骨干网能耗。采用Matlab R2017A平台对基于该算法重构的网络进行仿真实验,结果表明网络剩余能量、统治节点数量、节点覆盖率等指标均优于采用基于休眠机制和能量均衡的连通支配集算法、能量均衡的最小连通支配集算法构建的网络。

摘要： 无线自组织网络中的信息共享是指,每个节点都将自己所拥有的信息传播到其他节点的行为.然而,在时延敏感型的网络中,需要努力减小共享过程的时延.针对定向自组织网络信息共享中的冗余控制和空分复用问题,提出了一种基于连通支配集优化的调度方案.该方案首先设计了适合定向传输的连通支配集构造方法,其次根据节点负载和链路耗费对连通支配集进行优化,最后通过贪心调度策略完成一次信息共享过程的调度.仿真分析表明,所提方案在任意拓扑下都能够增大定向传输的空分复用率,消除冗余传输,减少信息共享的时延.

摘要： 无线传感器网络在数据传递过程中容易造成广播风暴,导致能量消耗过多,且不能适应网络的动态拓扑结构变化。文章提出了一种基于连通支配集的无线传感器网络能量有效算法,支配节点考虑能量剩余、邻居数量等参数,构建支配集组成较高能量的网络骨干,简化了构建过程,可避免频繁构建主干网带来能量大量消耗。实验结果证明该算法具有较好的算法性能,能降低广播风暴,延长网络生命周期。

摘要： 无线传感器网络在数据传递过程中容易造成广播风暴,导致能量消耗过多,且不能适应网络的动态拓扑结构变化.文章提出了一种基于连通支配集的无线传感器网络能量有效算法,支配节点考虑能量剩余、邻居数量等参数,构建支配集组成较高能量的网络骨干,简化了构建过程,可避免频繁构建主干网带来能量大量消耗.实验结果证明该算法具有较好的算法性能,能降低广播风暴,延长网络生命周期.

摘要： 为了解决无线传感网络因节点电池容量有限而导致其网络寿命和计算能力受限的问题,本文提出了一种基于启发式遗传算法的无线传感网络均衡节能虚拟骨干网构建(Balanced Energy Efficient Virtual Backbone Construction,BEE-VBC)算法.该算法通过综合考虑多种因素设计的适应度函数来选择最佳节点集,通过基于启发式遗传算法确定最优的连通支配集(Connected Dominating Set,CDS)来确保支配节点的连通性,将最优CDS用作向基站进行数据传输和转发的虚拟骨干网.实验表明与其他算法相比,本文BEE-VBC算法在网络寿命、平均能耗和数据包传输率等方面均优于现有方法.

摘要： 针对在无线网络中构造连通支配集问题,提出了一种基于圆盘图模型构造连通支配集的分布式算法PS-CDS,算法分为2部分,首先由PS-CDS-1算法构造极大独立集,然后通过PS-CDS-2算法向极大独立集中添加连通节点得到连通支配集.所提出的算法包括功率分配方案,选择能完成邻域广播的最小发送功率.算法的时间复杂度为O(n),消息复杂度为O(nm),近似比为R2Τ/R2min(2opt+1)-2.将PS-CDS算法与其他连通支配集算法进行实验比较,结果表明PS-CDS算法所生成的连通支配集规模最小.

摘要： In wireless sensor networks,clustering routing scheme is the main method for low energy routing design, and cluster-heads rotating algorithm is an effective way to balance the nodes energy consumption in clustering rou-ting. However,few studies have been done on how to calculate cluster-heads rotating intervals. A cluster-heads rota-ting interval optimization algorithm is proposed based on the concept of cluster-tree working period,and the adaptive cluster-heads rotating mechanism is implemented. Meanwhile,in order to reduce the number of the cluster-heads, this paper proposes a clustering algorithm based on CDS( connected dominating set) . In the simulation experiment, compared with four cluster-heads rotating strategies which have different fixed-length rotating intervals,the results show that the adaptive cluster-heads rotating algorithm has the longest network lifetime;compared with classical al-gorithms such as TopDisc and Guho,the results show that the CDS constructed by the proposed algorithm has the minimum size and diameter.%分簇路由方案是无线传感器网络中低能耗路由设计的主要方法,簇头轮换机制是平衡分簇路由中节点能耗的有效手段.然而,如何优化簇头轮换间隔却鲜见文献研究.基于簇树工作周期的概念,提出了一个簇头轮换间隔的优化算法,实现了自适应簇头轮换机制.同时,为了减少簇头数量,该文提出了一个基于连通支配集CDS(Connected Dominating Set)的分簇算法.仿真中,与4种不同长度的定长间隔簇头轮换策略进行了对比试验,结果表明自适应簇头轮换策略具有最长的网络寿命和最大的网络能量利用率;与TopDisc和Guho等经典算法进行了对比,该文提出的算法构造的CDS具有最小规模和直径.

摘要： 首先给出无线Ad Hoc网络的异构圆盘图模型HDG,并分析HDG模型的不同形态;然后设计出一种新的节点双向链表结构,在此基础上,提出一种基于链表结构的异构连通支配集算法C-LDS.该算法通过双向链表结构管理支配集,并通过节点引用的方式来提高支配集节点增加、删除及修改的时间效率,从而得到优化的连通支配集.将C-LDS算法与其他支配集算法进行对比测试,结果表明:在均匀分布以及随机分布的网络场景中,C-LDS所生成的支配集尺寸是最小的;在随机移动的网络场景中,C-LDS的分组投递率是最高的,展现出了较好的异构连通性并且提高了支配集节点的生成效率.

摘要： 本文提出了一种基于连通支配集的覆盖控制算法(CBCCA).CBCCA算法中,在构建连通支配集的基础上,通过调整连通支配集中节点的状态,以及连通支配集之外的节点状态,进行工作节点选取,然后根据邻居节点信息进行工作节点优化.仿真实验表明,算法可以满足网络的覆盖质量要求,同时实现连通性覆盖.

摘要： 传感器网络中的目标跟踪需要较好地解决目标状态信息共享问题。针对DCTC、基于簇算法的不足,给出了基于连通支配集(CDS)构造汇聚树的方法。根据节点是否具备定位功能,目标状态信息在汇聚树内可以采用广播或单播的方式共享.由于汇聚树结构稳定,当目标切换覆盖区域时也能很好地实现连续跟踪.基于汇聚树的目标状态信息经逐级融合后到达基站,能极大地减少冗余报文传送,节省节点能量。

摘要： 为了避免由洪泛搜索方法引起的大量网络流量问题,基于连通支配集的广播算法BCDS通过减少转发节点来减少查询消息数.文章对BCDS算法进行改进,选择转发节点时考虑节点间的距离,简化选择转发节点的操作,且不用维持局部两跳拓扑信息.实验结果表明当搜索结果相同时,改进的BCDS算法的消息数量平均仅为洪泛搜索方法的35％.

摘要： 移动Ad hoc网与无线传感器网络均可通过构建虚拟骨干网来减少参与路由计算的节点数量.虚拟骨干网可以由近似的最小连通支配集(MCDS)组成.本文主要研究了Ad hoc与无线传感器网络中的连通支配集问题,介绍了几类典型的连通支配集构造算法,以及算法的度量标准,比较了各算法的优缺点,并介绍了在特定情况下如何选择合适的算法.

摘要： 本发明公开了一种基于内外层嵌套的第二代非支配遗传算法的纵向连通空气悬架的几何参数优化方法，其步骤包括：1.建立纵向连通空气悬架关键几何参数多目标优化模型；2.利用内外层嵌套第二代非支配遗传算法求解多目标模型，得到优化后的帕累托解集前沿；3.利用逼近理想解排序法对帕累托前沿中的个体进行排序，筛选出最优关键几何参数。本发明在考虑行驶条件(路面不平度、车速、载荷)不确定的条件下，能有效改善多联轴纵向连通空气悬架半挂车的综合行驶性能。

摘要： 本发明涉及一种面向分布式网络的多层连通支配集构建方法，包括以下步骤：构建一个随机的分布式网络；将所有低层支配节点标记为高一层的被支配节点，并更新所述低层支配节点的高层的度数和邻居；对于每一层的任意节点，若该节点及其邻居在当前层没有支配节点，则根据所述节点的度数和妥协概率选择一个节点作为支配节点；对于每一层的被支配节点，若所述被支配节点两跳内的支配节点不能构成连通集，则将所述被支配节点标记为连通节点；重复上述步骤直至每一层的支配节点小于预设值时，得到多层连通支配集。本发明构建的多层连通支配集能够用于信任模型中的可信路由。

摘要： 本发明涉及无线传感网技术领域，更具体地，涉及一种无线传感器网集中式连通支配集构造方法。该方法基于贪心思想去层层推举下一批支配节点。方法中引入了有效度的概念，通过实时更新每一个节点的有效度信息，每一个现有的支配节点始终选举邻居节点中有效度最大的节点成为下一个支配节点，支配节点完成推举任务后开始判断自身是否为冗余支配节点，如果是则退化为灰色被支配节点。如此循环，在有限的循环次数内达到全网中所有支配节点的所有邻居节点的有效度为零时即生成最终的连通支配集。相比现有的其他技术，该方法实施简单，收敛时间短，产生的连通支配集大小较小。

摘要： 本发明公开了一种自定义的无线传感器网络中基于独占区域的连通支配集构造方法。本发明根据无线传感器网络虚拟骨干网的特点和分布式连通支配集构造算法，引入独占覆盖和延时等待规则的概念，通过两者的共同作用，每个节点维护自身的独占区域内至多一个节点，从而减小连通支配集的规模，使得支配节点分布更为均匀。本发明能够很好的减低连通支配集的规模，同时保证支配节点的分布均匀稀疏，同时节约能量，延长整个网络的生命周期，很好地适应了节点分布密集的无线传感器网络。

摘要： 本发明涉及一种基于重叠连通支配集的间接信任计算与分发方法，包括以下步骤：构建至少3层的重叠连通支配集；当第一节点请求获取第二节点的信誉值时，第一节点分别在每层连通支配集中发布请求信息；当某个节点发现恶意行为时，将所述恶意行为的相关信息发布到整个网络中；所述恶意行为相关的节点的邻居节点存储所述恶意行为的相关信息，并更新所述恶意行为相关的节点的信誉值。本发明能够可靠传输信任信息。

摘要： 本发明涉及一种面向分布式网络的多层连通支配集构建方法，包括以下步骤：构建一个随机的分布式网络；将所有低层支配节点标记为高一层的被支配节点，并更新所述低层支配节点的高层的度数和邻居；对于每一层的任意节点，若该节点及其邻居在当前层没有支配节点，则根据所述节点的度数和妥协概率选择一个节点作为支配节点；对于每一层的被支配节点，若所述被支配节点两跳内的支配节点不能构成连通集，则将所述被支配节点标记为连通节点；重复上述步骤直至每一层的支配节点小于预设值时，得到多层连通支配集。本发明构建的多层连通支配集能够用于信任模型中的可信路由。

摘要： 本发明涉及无线传感网技术领域，更具体地，涉及一种无线传感器网集中式连通支配集构造方法。该方法基于贪心思想去层层推举下一批支配节点。方法中引入了有效度的概念，通过实时更新每一个节点的有效度信息，每一个现有的支配节点始终选举邻居节点中有效度最大的节点成为下一个支配节点，支配节点完成推举任务后开始判断自身是否为冗余支配节点，如果是则退化为灰色被支配节点。如此循环，在有限的循环次数内达到全网中所有支配节点的所有邻居节点的有效度为零时即生成最终的连通支配集。相比现有的其他技术，该方法实施简单，收敛时间短，产生的连通支配集大小较小。

摘要： 本发明公开了一种基于最小连通支配集的卫星网络多播路由方法及系统，其方法包括：获取三层卫星网络的具体参数，并在STK软件中模拟卫星的运行情况来获取卫星节点在一整个周期内的通断情况表；基于通断情况表，通过时隙划分的策略构造时空图模型，获知卫星网络的时间链路和空间链路信息；根据获知的卫星网络的时间链路和空间链路信息，应用预设的基于最小连通支配集的MCDS路由算法进行多播路由业务。本发明降低了资源的浪费及避免了广播风暴，不仅降低了单时隙情况下随着节点数的增多所带来的路由代价，在时隙数增多的情况下，也有效降低了路由代价，并在路由代价和端到端跳数这两个性能指标之间取得一平衡，另外，算法实现起来复杂度低。

摘要： 本发明公开了一种自定义的无线传感器网络中基于独占区域的连通支配集构造方法。本发明根据无线传感器网络虚拟骨干网的特点和分布式连通支配集构造算法，引入独占覆盖和延时等待规则的概念，通过两者的共同作用，每个节点维护自身的独占区域内至多一个节点，从而减小连通支配集的规模，使得支配节点分布更为均匀。本发明能够很好的减低连通支配集的规模，同时保证支配节点的分布均匀稀疏，同时节约能量，延长整个网络的生命周期，很好地适应了节点分布密集的无线传感器网络。

摘要： 本发明涉及无线传感器网络中数据收集的方法，具体是一种仅对连通支配集中节点增加占空比进行数据收集的方法。该发明方法首先选择一部分节点构建包含sink的连通支配集，网络中所有的数据都经过连通支配集上的节点路由到sink。连通支配集上的节点(支配节点)采用占空比的模式，并且支配节点的占空比依据节点能量充裕情况而动态调整，由于远sink区域的大部分节点都有能量剩余，从而可以增大其占空比，加快数据收集的速度。而被支配节点不承担数据路由功能，仅在自己有数据需要发送时才进入活跃状态并将数据发送给支配集的节点，而在其它时间睡眠以节省能量。为平衡网络的能耗，本发明的方法对支配节点集进行定期轮换，以保持较高的网络性能。