路徑計算節點

在計算機網路中, 路徑計算節點 (英語：Path Computation Element，PCE) 是能夠在來源和目的之間，發現並選擇可用路徑的組件、套用或網路節點。

基本介紹

• 中文名：路徑計算節點
• 外文名：Path Computation Element

詳情

路由的選擇會受到一些因素的影響，如服務質量 (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的出現。

部署 PCE 的一個動力在於 PCE 把路徑計算和需要路徑記錄的客戶端 (PCC)分離。 PCE和PCC之間使用路徑計算節點通信協定(PCEP)進行通信。PCEP運行與傳輸控制協定 (TCP)之上。

該項目的步伐已經開發出一個引那些有興趣在PCE的。 從 PACE 的網站可以免費下載。

路徑節點編碼的相關研究

國內關於主要基於視覺的機器人導航中的路徑節點編碼問題的文獻並不多見。對基於軌線引導的機器人視覺導航中的停靠位標識進行了設計和識別，停靠位標識為3 × 3 的方格。

利用上述方法，機器人根據識別出的停靠位標識進行停靠並完成特定任務，解決的是簡單軌線導航中機器人的停靠問題，並沒有涉及複雜導航線交叉路口處路徑節點的識別和導航問題。王寧等設計了一種二進制編碼方案。

該方案設計容易，算法簡單，不失為一種簡單有效的路徑節點編碼方案，但是，由於方塊形二進制圖案不具有對稱性，容易受到攝像頭角度問題帶來的圖像畸變影響，魯棒性差，同時為了保證機器人從各個方向上識別結果的一致性，必須在路徑節點各個方向上都要設定一個同樣的節點編碼圖案，這無疑增加了工程量，也存在節點編碼的重複識別問題。為克服該問題，我們提出一種具有各向同性的二進制圓環編碼方案，無需重複設定編碼圖案，實施起來更加簡單方便、利於擴展、準確可靠。

路徑節點圓環編碼的設計

機器人行走路線上有大量的路徑節點，對各個路徑節點編碼設計的好壞直接關係到機器人能否準確識別路徑節點和自身定位，如果不能準確定位，導航也就無從談起，因此設計出一套簡單有效、易於識別的路徑節點編碼方案，成為機器人視覺導航的首要任務。為了使編碼識別更加容易並適應大規模路徑節點的需要，我們採用二進制編碼的方式。分別用黑白兩色來表示二進制位的“0”和“1”，通過黑白兩色的組合就能表示大量不同的二進制編碼，從而區分各個路徑節點，同時這種編碼方式也可以方便地進行擴展。考慮到路徑節點處機器人從各個方向上都能獲得相同的識別結果，決定採用二進制圓環編碼的形式，以保證機器人從不同方向看到的效果是一樣的。經過反覆測試，最終形成圓環樣式的二進制路徑節點編碼方案，見圖1。

圖1

圖1 中，圓環編碼圖案由黑白相間的多個圓環構成，其中，每一個寬的圓環都代表一個二進制位“0”或“1”，如箭頭1 至9 所指區域，這裡白色圓環表示“1”，黑色圓環表示“0”，反之亦然。相鄰的兩個編碼圓環如果編碼相同，它們之間應該間隔開，相鄰黑色編碼圓環用白的窄圓環分開，相鄰白色編碼圓環用黑的窄圓環分開，窄圓環只起間隔作用，並不包含在編碼中。為了更好地定位編碼區域，在圖案中心位置設定了非編碼標誌的中心圓，同時，為了使編碼區域和背景區分開，編碼圖案的最外圈應根據實際情況和背景形成反差。確定路徑節點編碼方案後，實際使用時，首先將機器人導航路徑上的交叉路口作為節點進行編號，並根據每個路徑節點編號所對應的二進制碼設計出相應的圓環編碼圖案，然後將其鋪設在各自對應的交叉路口節點處供機器人識別。鋪設好的包含導航線的路徑節點圓環編碼實拍圖片如圖2 所示。

圖2

Dijkstra算法

Dijkstra算法是一個優秀的最短路徑求解算法，同時也產生一棵最短路徑樹SPT（ shortest path tree ）；該算法在網路計算與最佳化中得到了廣泛的套用。

Dijkstra最短路徑算法是圖靈獎獲得者Dijkstra提出的一個優秀的求解最短路徑的算法。該算法廣泛套用於求解兩點間的最短路徑，比如Internet網路通信路由協定等；同時，在路徑規劃、運輸最佳化等運籌學眾多領域也具有廣泛的套用。由於該算法在計算最短路徑的同時也求解一棵最短路徑樹，因此，它也是計算最短路徑樹的一個重要算法。典型套用如組播路由協定中組播樹的計算；在網路管理中，各代理（agent）相對於控制中心（manger）的最佳化分布；圖論中特定節點集的覆蓋問題；無線感測器網路中，會聚節點（sink node）對感測器節點數據的收集、融合；在路由器EIGRP協定中還用生成樹來進行拓撲更新數據包的傳送，很多情況下都是構建以特點參數為度量的最短路徑樹。

根據最短路徑樹算法，通過計算能夠求解樹根（或者信號源s）到每個目的節點的最短路徑。但對一個具的目的節點而言，均有可能存在一條或者多條最短路徑；根據不同的最短路徑，其生成樹各邊代價之和（即生成樹代價性能）是不同的。因此，最短路徑樹還存在代價最佳化的問題。對最短路徑樹進行代價最佳化，特別是找出最小代價最短路徑樹在多個研究領域具有重要的理論意義和實際套用價值。

PCE 的擴展

PCE 有不同的擴展來實現不同的功能，比如：

• 域間 PCE 發現擴展