基于节点的路由优化算法压缩在大数据环境

文摘

最短路径问题是一个经典的问题。困难仍然涉及大数据环境下更是如此。当前对最短路径问题的研究主要集中在寻求从出发点到目的地的最短路径,与顶点已经给出;但最短路径的研究在一个有限的时间和有限的节点通过很少,然而,这样的问题不可能在现实生活中更常见。在本文中,我们提出几个这个问题的时间优化算法。关于传统的回溯和不同的节点压缩方法,我们首先提出一个条件的改进回溯算法在大数据环境下,三种类型的基于节点的优化算法压缩涉及大数据,以实现的路径选择起点通过一个给定的一组节点达到在有限的时间内结束。因此,问题涉及不同的数据量和网络结构的复杂性和采用适当的算法可以解决。

1。介绍

图论的单源最短路径问题是非常典型的问题,享受广泛应用在现实生活中,如网络路由路径选择、车辆导航、和旅游路线。经典的算法来解决此类问题是迪杰斯特拉算法1Dijkstra算法提出的)1959年,很多研究人员关注这个研究领域2- - - - - -4]。然而,Dijkstra算法无法解决问题,需要路线从起点,通过指定的中间节点,最后到达destination-far更实际的问题例子如下:

“邮递员问题”:邮递员从邮局,向居民发送信件,和回家,我们需要找到邮递员在给定时间内的最短路径。

“有限的时间问题”:活动设计在有限的时间内,工作人员跟踪同意使用深度传感器提出了,他们小心翼翼地提醒违规活动的5),和一个协作智能手机任务模型,提出了叫做开始智能感知任务模型(CMST) [6]。

“旅行问题”:计算一个旅游路线的旅行者在指定的时间内,谁需要从指定的位置,通过指定的景点,并访问给定的地方。总距离最短的或总费用应该是最低的7,8]。

“压缩问题”:提出了一种新的压缩方法对于大型数据环境,可以有效地减少单个节点的数据压缩和确保数据的质量9]。由于大量的web服务的数据,数据驱动的方案是基于内核至少意味着广场(荷航)算法(10]。为了压缩输入,进一步改善学习效果,基于一个新的QKLMS entropy-guided学习(11]。

“网络路由问题”:找到一个高效的路由算法来解决无线传感器网络的路径优化问题,考虑到一些实际因素的影响,如节点的能量消耗和恢复时间的路由12- - - - - -14]。

“拉盖尔神经网络”[15]:它打算提出一种新颖的自动学习计划来提高跟踪效率的同时保持或提高跟踪精度的数据。方案的核心战略是拉盖尔的设计基于神经网络- (LaNN)近似动态规划(ADP)。

传感器节点的能量”(16:小说prediction-based数据融合方案使用灰色模型(GM)和最优裁剪极端学习机(OP-ELM)提出。提出的数据融合方案称为GM-OP-ELM使用双预测机制保持预测数据系列水槽节点和传感器节点同步。

这些问题可以概括为一个图论问题;在加权有向图,路线从一个起点,通过指定的中间节点,到达目的地。应在指定的时间内寻找有效路径,这些路径的重量计算,并选择一条最低的重量作为最终结果。

解决这类问题,我们可以遍历整个图并找到最短路径,尽管理论上这遍历的算法最终将解决最优解;然而,时间复杂度仍然很高。针对这一点,本文提出一种节点压缩路由算法,考虑时间限制。这项研究关注节点压缩和有用的信息获得的路径找到适用于搜索条件,调整子节点的顺序和其他方法。此外,传统算法时间复杂度高,为这类问题提供一个有效的解决方案。

2。问题描述

2.1。问题的数学模型

给定一个加权图 在哪里 是顶点集, 是边集。 顶点的重量吗来 ,在哪里 和 ;而和可能是不平等的, 。我们需要找到的序列 在给定的时间内,是起点,是目的地, 和 , 不属于 ,所有的元素必须出现在序列 ,使所有边的权重的和路径形成的序列最小和循环是不允许在任何路径。问题的数学模型定义如下。

条件下的 ,解决 为了定义的起点和目标并确保只有一个在边缘和条边每个顶点的边缘除了起点和目的地的路径;我们做出以下约束: 在哪里是0或1的整数,1代表优势结果路径,0代表边缘结果路径,用于计算的重量产生的路径。 在哪里 意味着结果路径不能包含起始节点和结束节点的边是相同的节点,这意味着在中间节点上设置结果路径只能发生一次,必须发生一次。

公式定义了一条边,从起始节点应该出现在路径的结果,和起始节点优势不能结束节点。

这个公式的起始节点的限制只能起始节点优势,它不能被任何其他类型的节点,如结束节点或中间节点。

公式限制,结果路径结束,结束节点必须有一个优势 ,这意味着边缘不能从终点开始 。

公式限制,由此产生的路径不能包含边缘开始和结束节点 ;也就是说,结束节点只能作为最后的节点生成的路径。

这个公式定义的边缘产生的路径可以- 1的节点数量;与无关,由此产生的路径不能出现边缘和循环。

为方便后续的描述,下列两个定义。

定义1(关键节点)。的节点包括其他附着在节点除了起点和目的地 。

定义2(自由节点)。除了所有其他节点的关键节点。

2.2。简单的例子

在加权图如图1可以发现,四个节点,即0,1,2,3;因此 ,有七个边缘0,1,2,3,4,5,6,所以 边的重量 。找到一个路径通过顶点2和3,从0到1 。两条路径可以找到解决这一问题:0→2→3→1和0→3→2→1。自边缘第一路线的重量是4,和其他的重量是5,最优解应该是0→2→3→1。

3所示。改进回溯算法:IBA

如果使用回溯法来解决这个问题,从理论上说,我们可以有最优解,当然其他的解决方案。然而,回溯方法不能有效地使用信息构建在搜索过程或最优解,为项目下一步的优化条件奠定基础搜索。在本节中,提出一种改进的回溯法(OPT-Backtrack算法)基于传统回溯的方法。新IBA从先前的搜索中检索已知信息和有效的结果并将它们添加到下一个搜索规则之前从其他节点搜索。通过这种方式,可以提高搜索方法和算法,因为现有的信息和可能的结果是考虑更高的搜索效率。

改进回溯算法的加法规则如下所示。

规则1。如果下一个节点是目的,然而当前路径没有附着在那些经历了每一个节点的节点集,这条路将追溯并开始寻找下一个节点。这条规则可以避免许多无效的解决方案从而提高算法的生成效率。

规则2。如果当前路径的重量和到下一个节点的边的权值大于或等于最低重量可用的解决方案,将跟踪的路径返回,继续寻找下一个节点。如果当前路径被发现的当前重量和边缘到下一个节点的重量不超过现有的重量,然后不需要寻找下一个节点,因为最初的问题是找到的最小重量的道路。

规则3。对于那些nondestination节点没有子节点,我们应该避免进入搜索。如果不是目的地和一个节点没有子节点,路径不得继续;因此,没有必要这样的搜索在节点或,而他们可以简单地从图中删除。

的关键改进回溯算法的伪代码所示算法1。

4所示。节点搜索算法为基础的压缩

虽然可以提高搜索效率改进回溯算法在一定程度上,负面的复杂性提高回溯方法也将增加作为图的规模和解决方案领域扩张。降低算法复杂度,提出了一种新的算法,基于节点压缩搜索算法:机子。

随着图的规模增加,相应的路径将扩大。同样的问题是找到一条从起始点,达到一个中间节点中间和最终的目的地。降低算法复杂性,我们可能图进行预处理。方法是压缩的总数节点,删除无用的节点和低价值路径片段,然后保存的唯一路径是必要的简化整个图;我们的目标是压缩解决方案域并最终提高搜索效率。

4.1。节点压缩算法(NCA)

该算法适用于以下情况:如果一个节点是相对偏远,只有到达另一个节点,也就是说,一个节点后只有一个孩子节点,在这种情况下,唯一的子节点路由搜索会下来,将重复这个哪里有这种节点在搜索过程中。我们要做的是避免这种情况的简单和重复计算。

解决这个问题是节点压缩算法(NCA)。NCA记录的路径通过上述节点算法时第一次申请,并将删除节点但保留路径信息;因此,当下一次搜索仍在这个节点,只存储路径信息将被用来避免重复计算。因此,节点的总数是压缩和减少,使其更容易寻找更好的解决方案。

流程如图2。

在图2节点1是紧随其后的是唯一的子节点2,体重从节点1到2是2,路径标记为1;压缩过程意味着传输节点1信息节点2节点2成为节点的直接子节点0。如果压缩,重量从节点0到2是3,从0到2节点和路径” 。“这意味着删除节点1,而路径信息从节点1到2只保留节点2。下一个节点搜索算法达到0时,信息保留在节点2可以直接使用没有回到节点1。因此减少和路径的节点数量将不会再次搜索。

4.2。完成压缩算法:CCA

由于节点压缩算法(NCA)主要用于解决自由节点只有一个子节点,如果这些节点是许多图,算法效率会显著提高。然而,如果此类节点的规模有限,基本压缩算法将少或没有影响,这限制了压缩搜索算法的有效性。

鉴于NCA的问题,提出了一种更高效的压缩策略,压缩所有自由节点图中减少图像的复杂性,提高了搜索效率。

问题是找到一个noncircle从开始节点到目标节点的路径,通过中间节点集的权重的边缘路径尽可能小。当节点的可达性很复杂,将会有更多的可能的路径到达节点的一个,另一个。因为这个问题需要中间节点集被传递,在一组,有多个可及节点之间的路径,然而,只会选择一条路径设置为一个片段内的最终解决方案,因此,我们应该找出所有可获得的路径而保存路径最小的重量。搜索算法达到相应的节点,有效途径将从存储中检索信息而原始节点路径可以从图中删除,减少无用的节点和重复计算。与此压缩方法,只有起点,目的地,中间节点集,和他们的相互联系的路径信息仍将是,简化整个图在很大程度上与优秀的压缩效率。

就像图1,它可以被视为一个简化的图,只有起点,目的地,中间节点集。通过这种方式,我们可以通过选择可以实现良好的压缩效率路径最小的路径。

4.3。改善完成压缩算法:ICCA

为了进一步提高压缩效率,本节继续调整和完善节点压缩的三个步骤。

4.3.1。调整子节点按重量

在搜索过程中,算法可以基于可行的解决方案(见规则的重量2IBA)。第一子节点的顺序是根据重量大小排序从小型到大型。算法搜索路径时,子节点携带小重量与优先级,这样搜索路径较小的体重很容易获得。由于这种搜索策略,可以跳过其他路径与更大的重量。这无疑降低了不必要的搜索过程,提高效率。

4.3.2。调整子节点顺序的序列通过节点(从小型到大型)

从概率的角度来看,当一个新节点插入到图,节点的路径传递越多,越有可能重复路径将生成。因此,重量相同的情况下,用更少的子节点的节点将优先从下面路径会让更少的重复尝试,使其更容易找到解决路径。

4.3.3。删除子节点与更大的重量

这个策略只适用于高复杂性的图表。压缩后,剩余的节点将连接一个和另一个形成路径;图的复杂性可能仍然很高。会有一条路径的情况可能是一个有效的解决方案,但节点通过携带过多的重量,所以道路不会被认为是最终的解决方案。在这种情况下,节点删除重会降低图像的复杂性和提高搜索效率。此外,它将节省时间和找出一种更好的解决方案权重较低的路径。

通过分析,IBA的空间复杂性 ,虽然NCA的空间复杂性、CCA和ICCA ,在哪里图中节点的总数。ICCA可以快速选择最短路径根据节点和节点的权重较小的权重和删除节点权重较大的压缩大型网络效率。

5。实验分析

5.1。数据描述和分析

不失一般性,实验数据的情况下2016华为软件精英竞争;这些引用的例子是基于网络拓扑图形华为的网络路由器,交换机等网络元素时,华为建立了自己的网络设施。

5.1.1。问题描述

给定一个加权图 ,是顶点集,定向边缘设置,每个导演边缘包含了重量。对于一个给定的顶点 , ,和一个子集的 ,找到一个nonringing定向路径从来在给定的时间内,经过所有的顶点(不需要传递的顺序),使所有定向边缘路径的总重量尽可能小。

5.1.2中。数据描述

图中所有的重量都是整数 。

任何定向边的起点不是目的地。

定向边缘连接顶点的数量到顶点可能不止一个,他们的体重可能会或可能不会是相同的。

有向图的顶点的总数不会超过600,和每个顶点的数量有关学位(定向边的数量和这些点为起点)不超过8。

元素的数量不超过50岁。

nonringing定向路径从来 ,在哪里是一个有向连接路径组成的一系列定向边的来 ,不允许重复的路径。

重量的路径权重的总和的定向边缘路径。

5.1.3。数据格式

图中,每一行包含以下信息: ,

LinkID定向边缘指数,SourceID是指数的起始顶点定向边缘,DestinationID指数的目标定向边的顶点,成本是定向边缘的重量。定向边的顶点的索引,编号从0(不一定连续,但确保索引不重复)。

路径信息包括 ,

SourceID路径的起点,DestinationID目的地的路径,和IncludingSet代表附着在顶点集吗 ,和不同的顶点索引分段” 。”

5.1.4。实验环境

64位操作系统Windows 7,英特尔酷睿i5处理器,jre1.6, 32位的java虚拟机,4 G内存,使用。

5.2。实验方法和结果分析

5.2.1。IBA, NCA, CCA的比较

验证回溯法和IBA, NCA, CCA算法,四组实验将进行解决方案的时间限制为10秒。从实验中1- - - - - -4,图中节点和边的总数将会逐渐增加,而中间节点的数量将保持不变。实验结果将由最终的重量相比路径结果和时间。

实验1。总节点10;附着在节点3;边是39。

图3从实验展示了实验结果1提出了这样一个事实,IBA的效率高于回溯法。NCA效率差别不是很明显和CCA因为压缩过程也需要时间和效率变得更明显的如果图的复杂度很低。

实验2。总节点20;附着在节点5;边是55。

图4从实验展示了实验结果2它介绍了IBA, NCA, CCA比回溯法有更高的效率。CCA的效率最高,而IBA和NCA有相似的效率,因为几个远程节点。

实验3。总节点30;附着在节点10;边是135卡路里。

图5从实验展示了实验结果3CCA的优越性,它介绍了事实证明明显图复杂性逐渐提高。

实验4。总节点40;附着在节点10;边是229卡路里。

图6从实验展示了实验结果4这礼物回溯法的事实表明低效率如果图甚至更高的复杂性;相比之下,CCA效率执行得相当好。

实验结果表明,IBA效率高于回溯法评判权重或搜索时间。NCA只显示略有优势IBA因为远程节点图中是非常有限的。特别是,从所有维度来看,CCA证明重要的搜索结果质量效率优越其他算法,表明CCA在解决此类问题的有效性。

5.2.2。CCA和ICCA比较

从之前的四个实验观察,回溯法的各自的效率,IBA, NCA大大降低节点增加的总和。因此,没有研究价值添加更多的节点图。本节继续CCA和ICCA之间进行比较。

实验环境仍将是相同的实验1- - - - - -4;实验将逐渐增加总节点和边,中间节点集的大小也将增加。将基于以下五个实验比较。

实验5。总节点是60,附着在节点和边是285卡路里。

实验6。总节点100,附着在节点是15,边缘是516。

实验7。总节点200,附着在节点20日和边是997卡路里。

实验8。总节点400,附着在节点是28岁,而边缘是2178。

实验9。总节点600,附着在节点是50,和边是3418卡路里。

图7显示的实验结果表明,与CCA相比,ICCA获得更好的解决方案。因此,改进的策略4.3是被证明是有效的。

6。结论

像邮递员问题,旅行问题,总线设计、网络路由问题,和其他类似的情况下可以抽象为路径找到图模型作为本研究中讨论。IBA和NCA适用于中等规模的问题。NCA建议解决图表包含许多远程节点,而CCA和ICCA更高效地处理大规模问题的算法的复杂性。此外,ICCA能够提高搜索效率时,子节点调整。

当问题的规模变得更大,CCA, ICCA可能无法搜索整个解空间完全在给定时间内的最优解。在这种情况下,压缩的想法将被纳入启发式算法如遗传算法、蚁群算法期待一个更高效的搜索算法,以解决路由问题规模。

的利益冲突

作者宣称没有利益冲突有关的出版。

引用

1. e·w·迪杰斯特拉”,注意在连接图,两个问题”Numerische Mathematik1卷,第271 - 269页,1959年。视图:出版商的网站|谷歌学术搜索|MathSciNet
2. D.-Y。张,w l。吴,张炳扬。欧阳,“Top-k RDF图最短路径查询,”Tien慈济Hsueh Pao /《电子学报》,43卷,不。8,1531 - 1537年,2015页。视图:出版商的网站|谷歌学术搜索
3. 曹h . y, y元,z .问:刘,“网络路由算法基于节点的剩余能量和最大角,“传感器与微系统技术,2015年。视图:谷歌学术搜索
4. L.-Y。冯,L.-W。元,w·罗,R.-C。李,Z.-Y。Yu”几何algebra-based算法求解节点约束最短路径,”Tien慈济Hsueh Pao /《电子学报》,42卷,不。5,846 - 851年,2014页。视图:出版商的网站|谷歌学术搜索
5. w·赵r . Lun c·戈登et al .,“以人为中心的活动跟踪系统:向一个更健康的工作场所,”IEEE人机系统卷,47号3、343 - 355年,2017页。视图:出版商的网站|谷歌学术搜索
6. l . y . t . Li Liu高,A .刘”cooperative-based模型在雾smart-sensing任务计算,”IEEE访问5卷,第21311 - 21296页,2017年。视图:出版商的网站|谷歌学术搜索
7. 中州。气,Y.-G。Cai, h . Cai,杨绍明。关铭唐,W.-X。Lv,“混沌混合离散蝙蝠AIgorithm TraveIing SaIesman ProbIem,”《电子学报》,44卷,不。10日,2543 - 2547年,2016页。视图:谷歌学术搜索
8. y y z . Wang Chen和js。张,“小说基于学习和记忆的果蝇算法解决旅行Salmesman问题,“《中国计算机系统,37卷,不。12日,第2726 - 2722页,2016年。视图:谷歌学术搜索
9. c .杨x张c中et al .,“时空压缩的方法高效的大数据处理基于云,“计算机与系统科学杂志》上,卷80,不。8,1563 - 1583年,2014页。视图:出版商的网站|谷歌学术搜索
10. d·d·张x罗,j . Liu, x,“大规模网络QoS预测方案基于内核的工业物联网机器学习算法,”计算机网络卷,101年,第89 - 81页,2016年。视图:出版商的网站|谷歌学术搜索
11. j·邓罗x, x禁令,w . Wang j . Liu和j·王,”一个量子化的内核与entropy-guided最小均方计划学习智能数据分析,“中国通信,14卷,不。7,127 - 136年,2017页。视图:出版商的网站|谷歌学术搜索
12. a . Fernandez-Fernandez c Cervello-Pastor, l . Ochoa-Aday“提高节能意识在软件定义网络的路由算法,”第41届IEEE会议程序本地计算机网络,LCN 2016阿联酋,页196 - 199年,2016年11月。视图:出版商的网站|谷歌学术搜索
13. n . Li肯尼迪。马丁内斯,v . h·迪亚兹,“平衡跨层设计在无线传感器网络路由算法使用模糊逻辑,“传感器,15卷,不。8,19541 - 19559年,2015页。视图:出版商的网站|谷歌学术搜索
14. l . Lei w·f·李,h . j .王”路径优化基于遗传算法的无线传感器网络,”电子科技大学学报,38卷,不。2、227 - 230年,2009页。视图:谷歌学术搜索
15. 罗x, y Lv, m .周w . Wang和w·赵,”拉盖尔神经网络ADP学习计划与物联网的应用程序来跟踪控制,”个人和无处不在的计算,20卷,不。3、361 - 372年,2016页。视图:出版商的网站|谷歌学术搜索
16. 罗x, x张”,一种新颖的数据融合方案使用灰色模型和极端学习机在无线传感器网络中,“国际期刊的控制、自动化和系统,13卷,不。5,2015。视图:出版商的网站|谷歌学术搜索

版权

版权©2017总裁杨等。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。