油田水電站通信系統中網路最短路徑的計算

瓊州學院網絡與教育技術中心

油田水電站通信系統中網路最短路徑的計算

王乙人

瓊州學院網絡與教育技術中心

油田水電站通信系統網路最短路徑算法包括最小生成樹算法、狄克斯特拉算法和網路最大流最短路徑傳輸算法。最小生成樹算法主要用于水電站接收設備傳輸路徑的選擇，可查詢由接收設備至終端設備的最短傳輸線路。該算法可將每個站點的距離矢量的豎列劃去，在橫向排中尋找最小傳輸距離；最后，將每行的數據進行排列相加，得出接收設備與終端設備的最短傳輸距離。狄克斯特拉最短路徑運算方法主要用于油田水電站通信站點互通距離計算。網絡最大流傳輸路徑算法可用于通信數據信息傳輸線路的選擇，尋找傳輸至數據處理系統的最短線路，保證其他各條通信線路的正常使用。

網路；最小生成樹算法；最大流控制；水電站；通信系統

1 通信系統網路最短路徑算法

1.1 最小生成樹算法

在油井網路水電站通信系統中，最小生成樹的運算流程為：首先，找到水電站通信網路中的節點，將各個節點之間的傳輸距離進行標注。接著，將所標的數值從小到大進行有序排列，選出序列中最小的加權值。最后，將加權值依次排列，查看所構成的傳輸通信線路是否構成回路。假如在排列過程中構成回路，則舍去該邊的傳輸路徑，在此基礎上尋找另一條傳輸路徑。若水電站通信傳輸系統中共包含n個傳輸節點，則構成的傳輸線路共有n-1條，將傳輸路徑的有效值相加，便構成了最小生成樹。

1.2 狄克斯特拉最短路徑算法

油井水電站通信傳輸系統中，另一種尋找最短路徑的算法稱為狄克斯特拉算法。這種算法在運算模式上比最小生成樹的邏輯性更強，主要用于水電站數據信息傳輸系統中。該方法首先對傳輸節點的有效距離進行標注，將端點標為0，終點標為∞，最后找端點至終點的最短距離。如圖1所示，s點至2節點的有效距離為10，2點至5節點的有效距離為1，5點至t節點的有效距離為20，s點至3節點的有效距離為15，s點至4節點的有效距離為8，4點至6節點的有效距離為7，3點至5節點的有效距離為9，5點至6節點的有效距離為2，6點至7節點的有效距離為30，3點至6節點的有效距離為2，3點至4節點的有效距離為4。s至節點3的傳輸路徑有s—2—5—3，s—3，s—4—3，s—4—6—3；s—2—5—3傳輸路徑的距離為19，s—3的傳輸距離為15，s—4—3的傳輸路徑距離為12，s—4—6—3的傳輸路徑距離為17。s至節點5的傳輸路徑有s—2—5，s—3—5，s—4—3—5，s—2—3—5；s—2—5的傳輸距離為11，s—3—5的傳輸距離為24，s—4—3—5的傳輸距離為21，s—2—3—5的傳輸距離為27。s至節點5的傳輸最短路徑為s—2—5。然后再找出節點5至終點t的傳輸路徑，其中包括5—t，5—6—t；5—t的傳輸路徑過程中，傳輸的有效距離為20；5—6—t的傳輸路徑過程中，傳輸的有效距離為32。因此s—t最短傳輸路徑為31。

圖1 狄克斯特拉最短路徑算法

1.3 網路最大流最短路徑傳輸算法

水電站通信系統中網路最大流的最短路徑傳輸算法利用的是尋找增廣鏈的方式，保證傳輸路徑中正向的傳輸鏈路為非飽和邊，反向邊為非零流邊。油田水電站通信系統中有多個網路站點，每個站點彼此之間的傳輸路線不同。假設油田水電站通信系統站點有n個，傳輸的路線便存有n2-1條。若油田系統中存有的站點有6個，每個站點傳輸的路線都配有坐標值，其中s站點傳輸路線的坐標值為

（8，4），（7，4）；1站點傳輸路線的坐標值為（9，7），（5，1）；2站點傳輸路線的坐標值為（2，0），（9，，5）；3站點傳輸路線的坐標值為（6，1），（10，4）。由站點s出發至節點t的傳輸路徑有：s—1—3—t，s—1—2—4—t，s—1—2—4—3—t，s—1—3—4—t，4條傳輸線路。將4條傳輸路徑長度的最大值相加便得出最大流的傳輸距離。

2 最短傳輸路徑算法的應用

由于油田通信系統傳輸線路較多，當傳輸較多的數據信息時會造成通信線路的堵塞，進而隔斷了信息傳輸線路，使數據信息失真。最小生成樹算法主要用于水電站接收設備傳輸路徑的選擇。由于通信系統中終端設備與傳輸設備間隔距離較長，數據在傳輸過程中容易出現延時效應，造成數據信息大量地堆積在通信線路中。而最小生成樹算法可查詢由接收設備至終端設備的最短傳輸線路，將每個油田通信站點的接收設備連成一個矢量的矩陣，每個站點與站點之間的傳輸都能在矩陣規劃中明確地體現出來。該算法可將每個站點的距離矢量的豎列劃去，在橫向排中尋找最小傳輸距離。最后，將每行的數據進行排列相加，得出接收設備與終端設備的最短傳輸距離。

狄克斯特拉最短路徑運算方法主要用于油田水電站通信站點互通距離計算。假設油田水電站通信系統是獨立劃分的，在同一條通信線路上進行數據信息傳輸，那么很可能會造成通信系統中內部的數據網絡無法進行有效共享，出現數據信息泛洪現象。由于沒有進行線路的劃分，各個終端處理器傳輸的數據信息將會大量地堆積在傳輸信道內，服務臺無法獲取準確的有效信息，大量的數據信息傳輸至各條線路，使得每個終端系統都能接收傳輸的數據信息，造成傳輸信道資源的浪費。

網絡最大流傳輸路徑算法可用于通信數據信息傳輸線路的選擇，尋找傳輸至數據處理系統的最短線路，保證其他各條通信線路的正常使用。

3 結語

傳統油田水電站通信系統在傳輸數據信息時存有嚴重問題，主要是因為數據信息在傳輸線路上難以找到最短的傳輸路徑，造成數據信息大量的堆積在傳輸信道內，使終端系統無法獲取有效的數據信息。通過對油田網絡最大流控制技術在水電站通信系統中的應用分析，表明該技術能確保傳輸數據信息的安全，提高通信系統的穩定性。

（欄目主持 楊 軍）

10.3969/j.issn.1006-6896.2014.9.019