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

抽象的

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

1.介绍

图论中的单源最短路径问题是网络路径选择、车辆导航、出行路线等在现实生活中有着广泛应用的非常典型的问题。解决这类问题的经典算法是Dijkstra算法[1] Dijkstra于1959年提出，很多研究人员都关注这一研究区域[2- - - - - -4］.但是，Dijkstra算法无法解决从起点出发，经过指定的中间节点，最终到达目的地的路径问题，更实际的问题有:

“邮递员问题”：邮递员从邮局开始，向居民发送信件，并返回回家，我们需要在给定时间内找到邮政的最短路径。

“有限的时间问题”：在有限的时间内，提出了为使用深度传感器履行同意的工作人员而设计的活动，并仔细提醒他们的非符合活动[5]，提出了一种智能手机协作任务模型，称为基于协作的智能感知任务模型(collaborative - based Intelligent Perception task model, CMST) [6］.

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

“压缩问题”：提出了一种用于大数据环境的新压缩方法，可以有效地减少单个节点的数据压缩并确保数据的质量[9］.由于web服务数据量大，一种基于核最小均方(KLMS)算法的数据驱动方案[10］.为了压缩输入进一步提高学习效果，新的QKLMS基于熵导学习[11］.

“网络路由问题”：找到一种有效的路由算法来解决无线传感器网络路径优化问题，考虑到一些实际因素的影响，例如节点的能量消耗和路由的恢复时间[12- - - - - -14］.

"拉盖尔神经网络" [15]:提出一种新的自动学习方案，在保持或提高数据跟踪精度的同时提高跟踪效率。该方案的核心策略是基于Laguerre神经网络(LaNN)的近似动态规划(ADP)设计。

“传感器节点的能量”[16]：提出了一种使用灰色模型（GM）和最佳修剪的极端学习机（OP-ELM）的新型预测的数据融合方案。称为GM-OP-ELM的所提出的数据融合方案使用双重预测机制来保持宿节点和传感器节点同步的预测数据序列。

这些问题可以概括为一个图论问题;即在加权有向图中，路线从起点出发，经过指定的中间节点，到达目的地。需要在指定的时间内找到有效路径，计算这些路径的权值，并选择权值最低的路径作为最终结果。

为了解决这类问题，我们可以遍历整个图并找到一条最短路径，虽然理论上这种遍历算法最终会找出最优解;然而，时间复杂度仍然很高。鉴于此，本文提出了一种考虑时间限制的节点压缩路由算法。该研究注重节点压缩，并将在寻径中获得的有用信息用于搜索条件、调整子节点顺序等方法。同时，改进了传统算法时间复杂度高的缺点，为此类问题提供了有效的解决方案。

2.问题描述

２.１.问题的数学模型

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

在…的条件下 ,解决 ，为了定义起点和目标确保每个顶点只有一个内边和外边除了起始点和目标路径的边;我们做以下约束: 在哪里0或1,1的整数表示边吗在结果路径上，0表示边缘出于结果路径，和用于计算得到的路径的权值。 在哪里 意味着结果路径不能包含起始节点和结束节点是相同节点的边缘，这意味着只能发生一次的中间节点中的中间节点中的点，只能发生一次并且必须发生一次。

公式定义了一条边，它以结果路径中应该出现的开始节点开始，并且边中的开始节点不能是结束节点。

公式限制了起始节点只能是边缘中的起始节点，也不能是任何其他类型的节点，例如结束节点或中间节点。

该公式限制结果路径必须具有以结束节点结束的边 ，这意味着边不能从终点开始 ．

公式限制了结果路径不能包含以结束节点开始的边 ；也就是说，结束节点只能用作生成的路径上的最终节点。

这个公式定义了结果路径上的边数，可以是节点数减去1;也就是说，生成的路径不能带有不相关的边和循环。

为了便于后续描述，给出了以下两个定义。

定义1（关键节点）。的节点包括除起点以外的其他必须通过的节点和目的地 ．

定义2(空闲节点)。包括除密钥节点以外的所有其他节点。

2.2。简单的例子

在加权图中如图1，可以找到四个节点，即0,1,2和3;所以 ，有7条边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.基于节点压缩的搜索算法

改进的回溯算法虽然可以在一定程度上提高搜索效率，但随着图的规模和求解域的扩大，改进的回溯算法的负复杂性也会增加。为了降低算法复杂度，本文提出了一种基于节点压缩的搜索算法:NCSA。

随着图形规模的增加，路径也会相应的扩展。同样的问题是从起点找到一条路径，到达中间节点，最后到达目的地。为了降低算法复杂度，我们可以对图进行预处理。该方法是压缩节点总数，去除无用节点和低值路径片段，然后保存唯一需要的路径，从而简化整个图;目标是压缩解决方案域，最终提高搜索效率。

4．1.节点压缩算法

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

解决这个问题的方法是节点压缩算法(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问题，本文提出了一种更有效的压缩策略，压缩图中的所有自由节点，降低图的复杂度，提高搜索效率。

问题在通过中间节点集的同时从起始节点找到从起始节点到目的节点的非频带路径，使得路径上的边缘的权重尽可能小。当节点的可达性是复杂的时，将有许多可能的路径达到一个和另一个的节点。由于问题要求中间节点集，集合中节点之间有多条可达路径，但集合中只会选择一条路径作为最终解的一个片段，因此，我们应该找出所有可达路径，同时保存权值最小的路径。当搜索算法到达相应的节点时，将从存储的信息中检索出有效路径，同时将路径上的原始节点从图中删除，减少无用节点和重复计数。这种压缩方法只保留起始点、目的地、中间节点集及其相互关联的路径信息，在很大程度上简化了整个图，压缩效率很高。

就像图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。问题描述

给定一个加权图 ，是顶点集，是定向边缘集，每个定向边缘包含重量。对于给定的顶点 ， ，和一个子集的 ，查找无关的定向路径从到在给定的时间内通过所有顶点（不需要传递的顺序），使所有定向边的总重量进行路径尽可能小。

5.1.2。数据描述

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

任何有向边的起点都不是终点。

连接顶点的定向边的数量到顶点可能不止一个，其重量可能是或可能不一样。

定向图的顶点的总数不超过600，以及每个顶点OUT度的数量（随着起点的这些点的指向边的数量）不超过8。

元素的数量不超过50。

非定向路径从到 ，在哪里有向连通路径是否由一系列有向边组成到 ，不允许重复路径。

路径的重量是路径的定向边缘上的所有权重的总和。

5.1.3。数据格式

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

其中LinkID为有向边的索引，SourceID为有向边的起始顶点索引，DestinationID为有向边的目的顶点索引，Cost为有向边的权值。顶点的索引和有向边的索引从0开始编号(不一定是连续的，但这种情况确保索引不会重复)。

路径信息包括 ，

其中roseId是路径的起点，disectoryid是路径的目的地，includingset表示必须通过的顶点集 ，不同的顶点索引被分段为“ ．”

5.1.4。实验环境

使用Windows 7 64位操作系统，使用Intel Core I5处理器，JRE1.6,32位Java虚拟机，最多4g内存。

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显示实验的实验结果3.它提出了CCA的优越性证明，随着图形复杂性逐渐改善，CCA的优越性明显。

实验4。节点总计40;必须通过的节点为10;边缘是229。

数字6显示实验的实验结果4它提出了反向特触发方法如果图表的复杂性更高，则效率低;相比之下，CCA效率合理地表现得很好。

实验结果表明，IBA的效率高于通过重量或搜索时间判断的回溯方法的效率。NCA仅显示IBA略有优势，因为图中的远程节点非常有限。特别是，从所有尺寸判断，CCA都证明了在寻找对其他算法的卓越效率的结果中的显着质量，表明CCA在解决这些问题方面的有效性。

5.2.2。CCA和ICCA比较

从前四个实验中观察到，随着节点的总和增加，前四个实验从前四个实验中的相应效率显着降低，随着节点的总和增加。因此，没有研究值可以将更多节点添加到图形中。本节继续在CCA和ICCA之间进行比较。

实验环境与实验保持一致1- - - - - -4；实验将逐渐增加节点和边缘，而中间节点集的大小也将增加。比较将基于以下五个实验。

实验5。总节点为60，必须通过节点为10，边缘为285。

实验6。总节点是100，必须通过节点为15，边缘为516。

实验7。总节点是200，必须通过节点为20，边缘为997。

实验8。总节点是400，必须通过节点为28，边缘为2178。

实验9。总共有600个节点，必须通过的节点有50个，边有3418条。

数字7实验结果表明，ICCA比CCA得到了更好的解。因此，本节提出了改进策略4.3被证明是有效的。

六，结论

邮递员问题，旅行者问题，总线设计，网络路由问题等问题可以被抽象为本研究中讨论的路径查找图模型。IBA和NCA适用于中型问题。建议使用NCA来解决包含许多远程节点的图表，而CCA和ICCA在处理具有很大算法复杂性的大规模问题方面更有效。此外，ICCA能够在重新调整子节点时促进搜索效率。

随着问题的大小变得更大，CCA和ICCA可能无法在给定时间内完全使用最佳解决方案来搜索整个解决方案空间。在这种情况下，压缩思想将集成到启发式算法之类的启发式算法和蚁群算法中，以期望更有效的搜索算法，以便解决大规模更大的路由问题。

的利益冲突

提交人声明有关本文的出版物没有利益冲突。

参考文献

1. E. W. dijkstra，“关于与图形的两个问题有关两个问题的说明，”Numerische Mathematik，第1卷，269-271页，1959年。查看在：出版商网站|谷歌学术|Mathscinet.
2. D.-Y.张，w.-l.吴和C.-f.欧阳，“RDF图上的Top-K最短路径查询，”Tien Tzu Hsueh Pao / Acta Electronica Sinica号，第43卷。8, pp. 1531-1537, 2015。查看在：出版商网站|谷歌学术
3. 曹海云，袁勇，刘志强，“基于节点剩余能量和最大角度的无线传感器网络路由算法”，传感器和微系统技术, 2015年。查看在：谷歌学术
4. L.-Y。冯,L.-W。罗伟。李,Z.-Y。“基于几何代数的节点约束最短路径求解算法”，Tien Tzu Hsueh Pao / Acta Electronica Sinica，第42卷，第2期5, pp. 846-851, 2014。查看在：出版商网站|谷歌学术
5. W. Zhao, R. Lun, C. Gordon et al，“以人为中心的活动跟踪系统:迈向更健康的工作场所”，IEEE人机系统汇刊，第47卷，第47期。3, pp. 343-355, 2017。查看在：出版商网站|谷歌学术
6. T. Li，Y. Liu，L. Gao和A. Liu，雾计算中的智能传感任务的合作模式，IEEE访问，卷。5，pp。21296-21311,2017。查看在：出版商网站|谷歌学术
7. 中州。气,Y.-G。蔡慧玲，蔡玉玲。唐,W.-X。吕，“旅行推销员问题的混沌混合离散蝙蝠算法”，Acta Electronica Sinica.，卷。44，不。10，pp。2543-2547,2016。查看在：谷歌学术
8. 王永哲，陈永哲，j.s。“基于学习和记忆的新型果蝇算法求解旅行推销员问题”，计算机系统学报，卷。37，不。12，pp。2722-2726,2016。查看在：谷歌学术
9. 杨春春，张旭东，钟春春等，“基于时空压缩的云大数据高效处理方法”，计算机与系统科学杂志，第80卷，第2期。8, pp. 1563-1583, 2014。查看在：出版商网站|谷歌学术
10. X. Luo，J. Liu，D. D. D. Zhang和X. Chang，基于内核机器学习算法的工业互联网的大规模网页QoS预测方案，“计算机网络，卷。101，pp。81-89,2016。查看在：出版商网站|谷歌学术
11. “基于熵引导学习的智能数据分析的量化核最小均方方案”，中国通信，卷。14，不。7，pp。127-136,2017。查看在：出版商网站|谷歌学术
12. A.Fernández-Fernández，C.Cervelló-牧师和L. Ochoa-Aday，“在软件定义的网络中改进了能量感知路由算法”第41届IEEE会议关于本地计算机网络，LCN 2016年第41次IEEE会议，第196-199页，阿联酋，2016年11月。查看在：出版商网站|谷歌学术
13. N. Li，J.-f.Martínez和V.H.Díaz，“使用模糊逻辑的无线传感器网络的平衡跨层设计路由算法”传感器，卷。15，不。8，pp。19541-19559,2015。查看在：出版商网站|谷歌学术
14. L. Lei，W.F.LI，H. J. Wang，“基于遗传算法的无线传感器网络路径优化”电子科技大学学报，卷。38，不。2，pp。227-230，2009。查看在：谷歌学术
15. 王伟，“一种基于laguerre神经网络的ADP学习方法及其在物联网跟踪控制中的应用”，个人和普适计算，卷。20，没有。3，pp。361-372,2016。查看在：出版商网站|谷歌学术
16. 关键词:无线传感器网络，数据融合，灰色模型，极限学习机控制、自动化和系统国际期刊，第13卷，第2期5, 2015。查看在：出版商网站|谷歌学术

版权

版权所有©2017 Lifeng Yang等。这是分布下的开放式访问文章知识共享署名许可协议如果正确引用了原始工作，则允许在任何媒体中的不受限制使用，分发和再现。