瓊州學(xué)院網(wǎng)絡(luò)與教育技術(shù)中心

油田水電站通信系統(tǒng)中網(wǎng)路最短路徑的計算

王乙人

瓊州學(xué)院網(wǎng)絡(luò)與教育技術(shù)中心

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

網(wǎng)路；最小生成樹算法；最大流控制；水電站；通信系統(tǒng)

1 通信系統(tǒng)網(wǎng)路最短路徑算法

1.1 最小生成樹算法

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

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

油井水電站通信傳輸系統(tǒng)中，另一種尋找最短路徑的算法稱為狄克斯特拉算法。這種算法在運算模式上比最小生成樹的邏輯性更強，主要用于水電站數(shù)據(jù)信息傳輸系統(tǒng)中。該方法首先對傳輸節(jié)點的有效距離進行標注，將端點標為0，終點標為∞，最后找端點至終點的最短距離。如圖1所示，s點至2節(jié)點的有效距離為10，2點至5節(jié)點的有效距離為1，5點至t節(jié)點的有效距離為20，s點至3節(jié)點的有效距離為15，s點至4節(jié)點的有效距離為8，4點至6節(jié)點的有效距離為7，3點至5節(jié)點的有效距離為9，5點至6節(jié)點的有效距離為2，6點至7節(jié)點的有效距離為30，3點至6節(jié)點的有效距離為2，3點至4節(jié)點的有效距離為4。s至節(jié)點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至節(jié)點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至節(jié)點5的傳輸最短路徑為s—2—5。然后再找出節(jié)點5至終點t的傳輸路徑，其中包括5—t，5—6—t；5—t的傳輸路徑過程中，傳輸?shù)挠行Ь嚯x為20；5—6—t的傳輸路徑過程中，傳輸?shù)挠行Ь嚯x為32。因此s—t最短傳輸路徑為31。

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

1.3 網(wǎng)路最大流最短路徑傳輸算法

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

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

2 最短傳輸路徑算法的應(yīng)用

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

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

網(wǎng)絡(luò)最大流傳輸路徑算法可用于通信數(shù)據(jù)信息傳輸線路的選擇，尋找傳輸至數(shù)據(jù)處理系統(tǒng)的最短線路，保證其他各條通信線路的正常使用。

3 結(jié)語

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

（欄目主持 楊 軍）

10.3969/j.issn.1006-6896.2014.9.019