路径计算节点

在计算机网络中, 路径计算节点 (英语：Path Computation Element，PCE) 是能够在来源和目的之间，发现并选择可用路径的组件、应用或网络节点。

详情路由的选择会受到一些因素的影响，如服务质量 (QoS)、策略或价格。 在MPLS 和 GMPLS 网络中，考虑这些限制因素的条件下计算路径是流量工程的重要内容。这是用来确定流量应遵循的路径，并为每个标签交换路径(LSP)提供路由。

路径计算的以前是在一个网管系统或者每个标签交换路径的首尾。 但是，在大型及多域网络中进行路径计算可能非常复杂的，以至于超出了典型的网络节点的所拥有的计算能力和网络信息。

PCE 是一种能够为单个或者一些服务计算路径的设备。 PCE可能是网络节点、网管节点，或者的有能力了解网络全局拓扑的平台。 PCE的应用可以为MPLS和GMPLS网络的流量工程计算标签。IETF's PCE工作组正在为 PCE 的各部分结构进行标准化。

PCE 表示愿景的网络分开路线计算从该信的端对端连接和实际的分组交换的。 有一个基本教程上的PCE作为提交ISOCORE的MPLS2008会议 和教程，在先进的PCE作为提交ISOCORE SDN/协2014年会议。

PCE 的架构已发生了很大的变化，以此涵盖更复杂的网络场景。比如分层 PCE (H-PCE) 和有状态主动模式的PCE的出现1。

部署 PCE 的一个动力在于 PCE 把路径计算和需要路径记录的客户端 (PCC)分离。 PCE和PCC之间使用路径计算节点通信协议(PCEP)进行通信。PCEP运行与传输控制协议 (TCP)之上。

该项目的步伐已经开发出一个引那些有兴趣在PCE的。 从 PACE 的网站可以免费下载。

路径节点编码的相关研究国内关于主要基于视觉的机器人导航中的路径节点编码问题的文献并不多见。对基于轨线引导的机器人视觉导航中的停靠位标识进行了设计和识别，停靠位标识为3 × 3 的方格2。

利用上述方法，机器人根据识别出的停靠位标识进行停靠并完成特定任务，解决的是简单轨线导航中机器人的停靠问题，并没有涉及复杂导航线交叉路口处路径节点的识别和导航问题。王宁等设计了一种二进制编码方案。

该方案设计容易，算法简单，不失为一种简单有效的路径节点编码方案，但是，由于方块形二进制图案不具有对称性，容易受到摄像头角度问题带来的图像畸变影响，鲁棒性差，同时为了保证机器人从各个方向上识别结果的一致性，必须在路径节点各个方向上都要设置一个同样的节点编码图案，这无疑增加了工程量，也存在节点编码的重复识别问题。为克服该问题，我们提出一种具有各向同性的二进制圆环编码方案，无需重复设置编码图案，实施起来更加简单方便、利于扩展、准确可靠。

路径节点圆环编码的设计机器人行走路线上有大量的路径节点，对各个路径节点编码设计的好坏直接关系到机器人能否准确识别路径节点和自身定位，如果不能准确定位，导航也就无从谈起，因此设计出一套简单有效、易于识别的路径节点编码方案，成为机器人视觉导航的首要任务。为了使编码识别更加容易并适应大规模路径节点的需要，我们采用二进制编码的方式。分别用黑白两色来表示二进制位的“0”和“1”，通过黑白两色的组合就能表示大量不同的二进制编码，从而区分各个路径节点，同时这种编码方式也可以方便地进行扩展。考虑到路径节点处机器人从各个方向上都能获得相同的识别结果，决定采用二进制圆环编码的形式，以保证机器人从不同方向看到的效果是一样的。经过反复测试，最终形成圆环样式的二进制路径节点编码方案，见图1。

图1 中，圆环编码图案由黑白相间的多个圆环构成，其中，每一个宽的圆环都代表一个二进制位“0”或“1”，如箭头1 至9 所指区域，这里白色圆环表示“1”，黑色圆环表示“0”，反之亦然。相邻的两个编码圆环如果编码相同，它们之间应该间隔开，相邻黑色编码圆环用白的窄圆环分开，相邻白色编码圆环用黑的窄圆环分开，窄圆环只起间隔作用，并不包含在编码中。为了更好地定位编码区域，在图案中心位置设置了非编码标志的中心圆，同时，为了使编码区域和背景区分开，编码图案的最外圈应根据实际情况和背景形成反差。确定路径节点编码方案后，实际使用时，首先将机器人导航路径上的交叉路口作为节点进行编号，并根据每个路径节点编号所对应的二进制码设计出相应的圆环编码图案，然后将其铺设在各自对应的交叉路口节点处供机器人识别。铺设好的包含导航线的路径节点圆环编码实拍图片如图2 所示。

Dijkstra算法Dijkstra算法是一个优秀的最短路径求解算法，同时也产生一棵最短路径树SPT（ shortest path tree ）；该算法在网络计算与优化中得到了广泛的应用。

Dijkstra最短路径算法是图灵奖获得者Dijkstra提出的一个优秀的求解最短路径的算法。该算法广泛应用于求解两点间的最短路径，比如Internet网络通信路由协议等；同时，在路径规划、运输优化等运筹学众多领域也具有广泛的应用。由于该算法在计算最短路径的同时也求解一棵最短路径树，因此，它也是计算最短路径树的一个重要算法。典型应用如组播路由协议中组播树的计算；在网络管理中，各代理（agent）相对于控制中心（manger）的优化分布；图论中特定节点集的覆盖问题；无线传感器网络中，会聚节点（sink node）对传感器节点数据的收集、融合；在路由器EIGRP协议中还用生成树来进行拓扑更新数据包的传送，很多情况下都是构建以特点参数为度量的最短路径树3。

根据最短路径树算法，通过计算能够求解树根（或者信号源s）到每个目的节点的最短路径。但对一个具的目的节点而言，均有可能存在一条或者多条最短路径；根据不同的最短路径，其生成树各边代价之和（即生成树代价性能）是不同的。因此，最短路径树还存在代价优化的问题。对最短路径树进行代价优化，特别是找出最小代价最短路径树在多个研究领域具有重要的理论意义和实际应用价值。

PCE 的扩展PCE 有不同的扩展来实现不同的功能，比如：

域间 PCE 发现扩展

本词条内容贡献者为:

曹慧慧 - 副教授 - 中国矿业大学