不相交并和一阶语言的有穷模型性

在模型论语义下,一个公式是否具有有穷模型往往和可计算性相关。但是我们也可以仅仅从基数的角度来观察,譬如在一阶语言里,是什么样的因素强迫一个公式有或者没有有穷模型。对比于一个有穷模型的所有理论1都具有有穷模型性这一事实,发现存在另外一类无穷模型,通过不相交并的方式构造出来,因而它们的所有一阶理论都有有穷模型性。

一种电力通信网最大不相交双路由配置方法

针对现有电力通信网路由算法不能为业务分配双路由的问题,提出一种最可靠环路策略下的最大不相交双路由算法(the maximally disjoint routing algorithm under the most reliable loop strategy,MRMLS)。研究了公共通信网中三种类型的双路由算法,考虑了双路由算法可能面临的网络结构,阐述了采用最大不相交双路由算法的必要性。分析了最大不相交双路由的可靠性,并采用最可靠环路策略完成最大不相交双路由的分配工作。改进了原有最大不相交双路由算法,使所提算法充分考虑节点与链路的可靠性。仿真实验将MRMLS与其他两种方法进行对比,验证了MRMLS的可行性与有效性。

基于拓扑的不相交路径抗毁性评估方法

为了能够定量地计算出通信网络的抗毁性,以网状全连通网络作为参考基准,定义了基于拓扑的不相交路径抗毁性评估指标,以及节点和链路重要性评估指标,并配套研究了不相交路径的计算方法。计算被考核网络与全连通网络节点间不相交路径数的比重,得到抗毁性指标。通过计算各节点及链路失效后抗毁性变化的大小,得到网络元素重要性评估指标。阐述了计算方法的正确性,并给出时间及空间复杂度。通过算例分析并且与基于最短路径的评估方法进行对比,论证了不相交路径抗毁性评估指标和计算方法更加合理,更能体现出实际通信网络性能。

一种适用于无线多媒体传感器网络的节点不相交多路径路由协议

设计了一种适用于无线多媒体传感器网络的高效节点不相交多路径路由协议。以源路由的方式建立多路径,中间节点通过有选择的转发RREQs,降低路由建立开销。将链路质量量化为数据接收率,利用数据接收率、节点能量及路径跳数等,定义了路径效率模型,将路径效率模型引入到路由建立过程中。仿真结果表明,与SMR及TinyONDMR协议相比,新协议建立路由的开销更低,所建路径上节点能量分布更理想,进行数据传输时的能量效率更高,同时不会显著增加路径的传输时延。

无线传感器网络一种不相交路径路由算法

无线传感器网络经常被用来采集物理数据,监测环境变化.由于低功耗无线通信不确定性、链路质量不稳定性以及节点失效等问题,传感器网络很容易导致路由数据包丢失.为了提高网络路由的可靠性,人们提出多路径路由算法.多路径路由中源节点到目的节点的多条路径可能含有公共节点,或者公共边,如果公共节点或者公共链路失效,则这个数据包也丢失,因此又有人提出不相交多路径路由算法.不相交多路径路由算法又分为链路不相交多路径路由算法和节点不相交多路径路由算法.提出了一种不相交路径路由算法,可以将感知节点采集到的数据通过不相交路径传送到汇聚节点,提高路由的可靠性.而且,这个算法还可以很方便地应用到多Sink节点的网络当中.该路由算法用到的路由表大小为|K|,其中|K|表示路径数.算法的运行时间复杂度是O(|L|),其中|L|表示网络中的边数.

基于相关因子的节点不相交的Ad Hoc多路径路由算法

多路径路由算法可以均衡负载、提高可靠性,但是A d Hoc网络的无线多播特性(WM A)使得多路径数据传输存在严重的冲突隐患,即便是节点不相交的多路径,以并发的方式来进行数据传输的效率并没有理论上的高.为此本文提出基于相关因子的节点不相交的多路径路由算法(NDCF),该算法引入相关因子来衡量多条节点不相交路径以并发的方式进行数据传输时发生冲突的可能性的大小,从而选择冲突可能性最小的节点不相交路径.仿真结果表明,NDCF算法可明显提高数据包的投递率,降低端到端的传输时延.

网树求解有向无环图中具有长度约束的最大不相交路径

对有向无环图中具有长度约束的最大不相交路径问题进行研究,该问题是求解图中两点间路径长度为k的最大不相交路径。为了对该问题进行求解,提出了贪婪搜索算法(GP,greedy path),该算法先将一个有向无环图转化为一棵深度为k+1的网树,然后计算每个网树节点的树根叶子路径数,并以此计算图中每个顶点的总路径数,之后从网树的第k+1层节点出发,在当前节点的双亲节点中选择未被使用且总路径数最小的双亲,以此形成一条优化的不相交路径,最后迭代这一过程,直到不再有新的不相交路径为止。GP算法的时间和空间复杂度分别为O(wkn(p+q))和O(kn(p+q)+n2)。为了测试GP算法的近似性,又建立了一种能够生成人工数据的算法,该算法能够准确地控制有向无环图中最大不相交路径的数量。通过该算法生成了大量测试用数据,实验结果表明GP算法较其他对比性算法具有良好的近似性且实际求解时间较短,验证了该方法的有效性和可行性。

Ad-Hoc网络中一种可靠的节点不相交多路径路由算法

提出了一种可靠的节点不相交多路径路由算法(RNDMRA).结合预测模型和能量模型,利用网格中节点的地理信息,有效减少路由发现泛洪的频率.同时为了选择与最短路径相似的稳定多路由,RNDMRA应用相似性因子选择相似的稳定节点不相交多路径路由.模拟结果显示,与AODV和NDMR相比,RNDMRA有更高的投递率,更小的路由延迟和路由负载.

基于区域不相交的无线传感网任播路由算法

在无线传感器网络(wireless sensor networks,WSN)中采用任播技术可以均衡数据流及能耗。传统算法常采用节点不相交路由策略,但隐终端问题仍会造成任播路径间的传递碰撞。针对该问题,提出基于区域不相交策略的WSN任播路由算法。该算法采用扇形通道技术和基于不同时隙的区域不相交发送策略以减少任播路径传递碰撞问题。仿真实验数据表明,相比较节点不相交路由策略和最短路径优先区域不相交路由策略,本文算法在分组投递成功率和节点平均能耗上具有较好的性能优势,从而提高网络生存期。

无线Mesh网链路不相交多路径路由策略

无线Mesh网以其高覆盖面、低功耗等优势,将在下一代无线通信技术中扮演重要角色,路由技术一直是其研究热点.为了提高无线Mesh网的生存性、可靠性和无线信道的利用率,针对无线Mesh网的特点提出了一种基于链路不相交技术的多路径路由算法,以求通过尽可能少的信息交换,获得尽可能多的网络状态信息,保证网络的负载平衡.仿真实验证明,采用多路径路由机制中的链路不相交技术,不但提高了数据传输的可靠性,而且在大规模网络环境中表现出较好的性能,如传输时延低、分组投递率高和协议开销小等优点.

一种稳定的不相交多路径蚂蚁路由算法

提出一种稳定的不相交多路径蚂蚁路由算法(SDMAR).基于稳定性模型和能量模型,该算法主要依靠节点能量和生命周期的联合参数进行概率转发,并提供了多条到目的节点的冗余路径.这些路径基于路径信息分成不同等级,当最优路径断开时,它们即被使用.模拟结果表明,与动态源路由算法和Ad hoc按需多路径距离矢量路由算法相比,SDMAR的数据包投递率约高出8%,路由负载约降低25%,能量消耗节约15%.

中心计算的无线传感器网络2-不相交路径路由算法

在多路径路由(multipath routing,MPR)算法中,不相交多路径路由(disjoint multipath routing,DMPR)算法具有更高的可靠性和容错性.DMPR算法面临的主要挑战有2点:不相交路径的选优问题和数据包在不相交路径上的传输问题.针对某些工业应用(例如矿井环境监测)中网络拓扑比较稳定,sink节点运算和存储能力较强等特点,提出了一种中心计算的2-不相交路径路由算法——CCDMPR算法.算法利用全网信息计算出从源节点到sink节点的近似最优2-节点(链路)不相交路径,然后生成仅包含<主父交节点,辅父节点>对和路径比特序列的微路由表并下传到每个节点;针对中心计算方式对链路状态变化的反应迟缓问题,采用了一种中心调度的自适应机制提高路径维护的灵活性.实验结果证明,CCDMPR算法能够显著减小平均路径长度,节省网络整体能量,并能提高数据传输的可靠性.

最小能量节点不相交多路径的自组网路由算法

为减轻节点不相交多路径路由负载和解决路径间的耦合问题,提出了一种基于定向天线的最小能量节点不相交多路径自组网路由算法(RMENDMRDA).初始时该算法应用优化波宽选择算法确定定向天线的最小扇形覆盖区域,从而节省能量消耗,在选择累计能量最小的节点不相交多路径时采用链路可靠性选择算法,以满足链路的可靠性要求.分析及模拟结果表明,该算法路由负载更小、路由发现频率更低.与源传输能量选择路由算法和节点不相交多路径路由算法相比,RMENDMRDA的数据包投递率提高了18%,路由负载降低了24%,节省能量约8%.

不相交的m—路中心

本文提出图的顶点和边不相交的 k-支配数的概念.并就树的情形对顶点和边不相交的 k-支配数分别给出 O(n^2)算法.从而解决了树的顶点和边不相交的 m-路中心问题.本文还解决了[2]中的一个未解决问题.

MCM布线中求取最大加权不相交匹配的有效算法

ＭＣＭ在集成电路封装中的广泛应用，迫切需要高效准确的布线．四通孔布线算法用于实际ＭＣＭ布线时，需要解决最大加权不相交匹配问题．基于现在解决此问题较复杂，在描述四通孔布线和把此问题转化为求取最大链问题的基础上，提出了一种有效算法来解决最大加权不相交匹配问题，其主要思想是利用求最长路径的方法来解决最大链问题；证明了此算法并给出实际的布线结果．实践证明。

一种基于生存时间的Ad hoc网络不相交多路径路由算法

针对无线移动Ad hoc网络的节点具有移动性和能量限制等问题,提出了一种根据网络动态拓扑结构和节点能量来进行多路由选择的混合式路由算法PEMP-OLSR。该算法以改进的链路状态路由算法为基础,通过在网络拓扑构造过程中引入链路和节点生存时间等参数来提高所选路径的稳定性,同时通过设定影响链路和节点权重的迭代因子来提高多条路径的不相交性,以提高此并行多路径算法的传输效率。通过大量仿真实验结果表明,该算法能有效地提高所选择的多条路径的稳定性和不相交性。

一种端到端网络的不相交多路径QoS路由算法

不相交多路径路由算法旨在一个端到端的网络中为应用流选择多个路径,且这些路径在瓶颈链路上是彼此不相交的。本文提出的不相交多路径QoS路由(DMQR)算法在Dijkstra最短路径和最短最宽路径(SWP)算法的基础上,能够动态地计算时延最短、带宽最宽、在瓶颈链路上互不相交的路径,且保证每个路径都是满足一定服务质量的。在视频会议、远程医疗和远程教育等重要的视频通信场合,要求应用层和网络层必须协同工作以保证一些必要的QoS,例如端到端的带宽、时延和包丢失率等。本文针对端到端的网络,重点讨论不相交多路径QoS路由算法在应用层的设计和实现。性能分析和模拟结果显示,所提出的不相交多路径QoS路由算法总是收敛的,且当网络流量增加时,该算法具有较低的包丢失率和较高的吞吐量。

Hilbert K-模上广义框架的不相交性

引入了紧算子代数模(简称Hilbert K-模)上广义框架,广义框架变换,广义框架算子,(强)不相交等概念,给出并证明了Hilbert K-模上广义框架(强)不相交的充要条件。

Ad hoc网络节点不相交多路径距离矢量路由协议

AMR算法是Ad hoc网络计算节点不相交最大路径集合的累积多路径路由机制。针对节点不相交多路径源路由协议MNDP及SMNDP存在的问题,整合按需距离矢量路由AODV和AMR算法,提出了节点不相交多路径距离矢量路由协议MDVR。MDVR协议建立的路径信息分布在网络节点中,可缩短路由分组长度以及减轻路由发现源节点建立路由的负担;可防止攻击者通过篡改路由消息中的路径信息攻陷协议。

一种优化的节点不相交多径路由策略

移动Ad Hoc网络是一种新型的不依赖于固定设施实现通信的无线移动网络,其节点兼具主机和路由器的功能,适用于Ad Hoc网络的路由策略是目前广泛研究的核心问题之一。通过深入研究移动Ad Hoc网络中多径路由协议,以AOMDV算法为基础,提出了一种优化的节点不相交多径路由策略ONDMRP,可以有效提高路由表中多条路径的性能。