基于圖論生成樹的低壓電力線通信路由方法＊

李 祥，劉宏立，劉述鋼，2，谷志茹，陳 艷

（1.湖南大學電氣與信息工程學院，湖南長沙410082；2.珠海中慧微電子有限公司，廣東珠海519085）

1 引言

低壓配電網具有電力線分布廣泛、不用布線、投資成本低；而且電力線不易破壞，后期維護量小的特點。因此，低壓電力線通信前景被十分看好。高可靠性、高速率已經成為電力線載波通信網絡的重要目標。然而，由于低壓配電網上輸入阻抗變化復雜、噪聲干擾使得信號衰減嚴重［1～4］；用戶供電范圍和供電對象的經常變化，以及負載加入退出的不確定性，使得低壓配電網具有很大的時變性。這些因素都會嚴重影響低壓電力載波通信的可靠性。

為了提高電力線通信的可靠性，目前國內外主要從物理層和網絡層兩方面來著手［5～7］。物理層方面主要通過信道估計、信道編碼以及調制解調方法等方面來考慮；網絡層方面主要通過選擇合適的中繼組網算法。

目前國內外已經有很多學者對于低壓電力線載波的中繼組網算法進行了研究［8～10］，比如類蟻群算法、分簇算法等。它們都能夠實現中繼組網，具有一定的適用性，同時也有一定的局限性。類蟻群算法，即是一種隨機搜索算法，也是一種比較耗時的算法，同時容易陷入局部最優。分簇算法在網絡的可靠性和抗毀性上具有一定的優勢，但是對于網絡節點要求具有一定的路由能力，在工程應用中會增加產品成本。

本文針對網絡節點僅具有中繼轉發功能的低壓電力線通信網絡的路由方法進行研究，首先對低壓配電網的物理拓撲結構和邏輯拓撲結構進行分析；然后結合低壓集中抄表工程應用中對于網絡節點能力的要求，通過對圖論生成樹的遍歷搜索算法進行研究，提出了基于遍歷搜索算法的中繼組網策略和網絡維護策略；最后進行了實驗研究并做出了分析。

2 低壓配電網通信網絡模型

2.1 低壓配電網物理結構

低壓配電網電力線通信網絡物理拓撲結構和應用場所緊密相關，物理拓撲復雜多變，但總體上可以歸納為星型拓撲和樹型拓撲［11］。本文以配電網單相的樹型拓撲結構作為重點研究對象，如圖1所示，圖中弧上的數字表示該網絡的各點之間的距離。

Figure 1 A typical structure of single－phase tree topology of distributions圖1 一種典型的配電網單相樹型拓撲結構

2.2 低壓配電網邏輯結構

由于受到低壓電力線信道高衰減和強干擾的影響，使得原本物理連通的節點間的通信并不可靠，它們的可靠通信距離會受到影響。假設圖1中集中器和單相表的最大有效通信距離是10，可以得出圖2所示的邏輯拓撲結構。由圖2可見，單相表1是連在四條分裂總線上的。因此，對于終端較多、分布不均勻的低壓配電網來說，其拓撲結構是一個非常復雜的圖［12］。

Figure 2 Single－phase logic topology structure of distributions圖2 配電網單相邏輯拓撲結構

3 基于圖論生成樹的遍歷搜索路由組網與重構算法

3.1 數學模型的建立

將圖2所示的配電網邏輯拓撲結構抽象為連通圖G（V，E），記為G（V（G），E（G））。如圖3所示，其中，V（G）稱為圖G的頂點集，元素v∈V，稱為圖G的頂點。E（G）稱為圖G的邊集，元素eij∈E為V中元素的有序對，稱為圖G從vi到vj的一條邊。在低壓電力線通信網絡中，由于通信信道的變化，節點間的有效通信距離也是動態變化的，所以，集合E可以看作是動態的。

Figure 3 Routing model of power line communication network圖3 電力線通信網絡的路由模型

生成樹是當且僅當一個圖的生成子圖是連通圖且不含回路的。圖4給出了圖3中連通圖的生成樹。

因為在任何兩個頂點之間都有生成樹里的通路，所以有生成樹的簡單圖必然是連通的，而且每個連通圖都有生成樹。那么，在連通圖的數學模型構建之后，我們的目標就轉化為如何在連通圖中尋找它的一個生成樹。由此，電力線通信網絡中的節點通信問題就可以抽象為圖論中怎樣形成圖的生成樹的問題。

Figure 4 Spanning tree of routing model of power line communication network圖4 電力線通信網絡路由模型的生成樹

3.2 廣度優先搜索路由組網算法

一般情況下，一相電網內有一個中心節點，n個（n≥1）普通節點，電力線物理鏈路是連通的，且滿足如下條件：

（1）中心節點的地址為0，普通節點的地址為1，2，3，…，n。

（2）中心節點具有路由功能，其他普通節點僅具有載波信號中繼轉發的功能。

（3）中心節點按照其存儲的普通節點的物理地址進行通信組網。

（4）普通節點的通信中繼級別不超過7級。

在圖論生成樹的遍歷搜索算法中包含深度優先搜索和廣度優先搜索。深度優先搜索算法是從某一頂點開始盡可能深入到未搜索過的頂點中去，總是從一個頂點搜索到另一個新的頂點，直到不能進行才返回。廣度優先搜索算法是按照由近及遠的順序去搜索每個頂點，在不產生簡單回路的情況下搜索完所有的節點。由于深度優先搜索算法和廣度優先搜索算法的復雜度為O（e），e為連通圖的邊數［13］。忽略電信號在銅介質中的傳輸時間，電力線通信網絡中心節點到目的節點之間通信的時間消耗與目的節點深度成正比，且在某些實際工程中普通節點僅具有中繼轉發而不具備路由功能，為了快速地實現通信組網，本文選擇廣度優先搜索算法以得到最優解。

廣度優先搜索路由組網算法主要包括以下步驟：

步驟1 由中心節點按照其存儲的普通節點地址來順序發送組網命令，接收到組網命令的普通節點通過地址識別，如果是本節點的地址就回復一個響應幀數據，如果不是本節點的地址就忽略本條命令。對于所有的普通節點都發送命令訪問一遍之后，中心節點將回復響應幀的m個普通節點添加到生成樹的第一層。

步驟2 如果普通節點都已經添加到生成樹中，那么組網成功；否則，中心節點以生成樹第一層節點作為一級中繼節點來訪問還未加入生成樹的（n－m）個節點。中心節點發送組網命令幀中將包含中繼節點地址和目的節點地址。組網訪問順序為：以第一層的第k個節點（k＝1，2，…，m）作為中繼節點依次訪問沒有加入生成樹的所有節點。接收到組網命令幀的普通節點判斷目的地址是不是本節點的目的地址，如果是則發送響應幀，如果不是則忽略。中心節點將回復響應幀的j個普通節點添加到生成樹的第二層，并記錄它們的中繼節點。

步驟3 如果此時普通節點都已經添加到生成樹中，那么組網成功；否則，中心節點以生成樹第二層節點作為二級中繼節點來訪問還未加入生成樹的（n－m－j）個節點。具體中繼組網訪問順序和方法與步驟2相同。

步驟4 中心節點通過增加中繼級別來搜索剩余的普通節點，直到將所有n個普通節點都添加到生成樹為止；若中繼級別大于7級，還存在剩余節點，則組網結束，剩余節點為孤立節點。

廣度搜索遍歷算法組網流程圖如圖5所示。其偽代碼如下：

3.3 路由重構算法

Figure 5 Flow chart of network organizing of breadth traversal search algorithm圖5 廣度遍歷搜索算法組網流程圖

由于低壓電力線載波的時變性和未知性，在成功組網之后，如果發現節點k（中繼級別為x）暫時不能通信，則中心節點開始發起路由重構過程。路由重構算法是基于廣度優先搜索算法的改進，考慮到按照廣度優先搜索算法組網建立的通信網絡中，網絡節點的深度最小，在路由重構時，首先考慮原中繼級別中的其他節點作為中繼，其次再考慮比原中繼級別高一級的節點作為中繼，然后再依次遞減原中繼級別。具體實現步驟如下：

步驟1 中心節點按照原路徑m次（10≤m≤15）嘗試通信節點k。由于低壓載波網絡具有時變性，頻繁更換路由路徑反而不利于通信的穩定和可靠。若多次嘗試原路徑通信成功，則路由重構成功。

步驟2 在原路徑多次嘗試失敗的情況下，開始嘗試歷史路徑k次（3≤k≤5）。歷史路徑為曾經通信成功的路徑。若嘗試歷史路徑通信成功，則路由重構成功。

步驟3 開始嘗試新的路徑。保持原中繼級別，即通過x層節點來作為中繼嘗試探測節點k。若x層節點作為中繼節點能夠探測成功，則路由重構成功。

步驟4 其次，滿足中繼級別x＜7時，嘗試新的路徑，否則跳過此步驟。將原中繼級別加1，即通過（x＋1）層的節點來作為中繼嘗試探測節點k。若（x＋1）層節點作為中繼節點能夠探測成功，則路由重構成功。

步驟5 再次，若滿足中繼級別x≥1，嘗試新的路徑，否則跳過此步驟，進入步驟7。將原中繼級別減1，即通過（x－1）層的節點來作為中繼嘗試探測節點k。若（x－1）層節點作為中繼節點能夠探測成功，則路由重構成功。

步驟6 嘗試新的路徑策略。若上述方法都不能與節點k通信成功，則中繼級別一直減少至直接通信。若能探測成功，則路由重構成功。

步驟7 重新搜索新的路徑。按照直接通信、1級中繼、…、7級中繼的順序嘗試探測節點k。若能探測成功，則路由重構成功。

步驟8 若上述步驟都不能將路由重構成功，則判斷節點k已經脫離低壓電力線載波通信網絡。

網絡路由維護算法流程圖如圖6所示。其偽代碼如下所示：

4 實驗研究

4.1 虛擬電力線網絡的實驗研究

以中慧公司開發的電力線網絡虛擬平臺《配電臺區仿真測試系統》來驗證算法的可行性。該虛擬平臺是針對低壓電力線集中抄表系統專門設計與開發的，能夠虛擬載波網絡的拓撲環境，并經華北電科院測試通過。在整個實驗環境中，采用威勝集團研發的DJGZ33－WFET1600集中器，并搭載中慧公司生產的路由模塊，本文的路由算法已經在路由模塊中實現。通過UART串口將路由模塊與PC機相連，在PC機中虛擬載波網絡結構。實驗環境如圖7所示。

Figure 7 Experimental environment of virtual network圖7 虛擬網絡實驗環境

為驗證算法的有效性，建立一個與實際系統近似的簡化網絡結構，該結構是一個具有6級的網絡結構，其中第一級包含5個節點，第二級包含7個節點，第三級包含2個節點，第四級包含1個節點，第五級包含1個節點，第六級包含1個節點。虛擬電力線網絡物理拓撲結構如圖8所示，虛擬電力線網絡邏輯拓撲結構如圖9所示。

Figure 8 Physical topology structure of virtual power line network圖8 虛擬電力線網絡物理拓撲結構

實驗1 通過集中器下發抄表命令，啟動路由模塊開始抄表組網，運行于路由模塊中的路由算法通過UART串口抄讀PC機中的虛擬表，最終所有虛擬表組網成功，如圖10所示，組網時間為11分59秒，組網成功率為100%。其組網生成樹如圖11所示。

Figure 6 Flow chart of routing reconfiguration algorithm圖6 路由重構算法流程圖

Figure 9 Logic topology structure of virtual power line network圖9 虛擬電力線網絡邏輯拓撲結構

Figure 10 Chart of network organizing success of experiment 1圖10 實驗1組網成功圖

Figure 11 Spanning tree of network organizing圖11 組網生成樹

實驗2 在實驗1的基礎上，刪除節點37，此時網絡生成樹如圖12所示。由于節點51需要節點37作為中繼節點進行通信，網絡出現通信故障，需要進行網絡重構。此時當路由模塊多次按原路徑與節點51進行通信失敗，則開始變換路徑進行試探，按照前面講述的路由重構策略進行試探。在同級中繼中嘗試以節點36、38、39、40作為中繼，通信均失??；然后再在高一級中繼中嘗試以節點41作為中繼，通信成功；節點51添加到生成樹中。重構后生成樹如圖13所示。重構時間為18分32秒，重構成功率為100%。

Figure 12 Spanning tree after deleting node37圖12 刪除節點37后生成樹

Figure 13 Spanning tree after reconfiguration圖13 重構后生成樹

虛擬電力線網絡的實驗結果表明：利用遍歷搜索算法能夠實現低壓電力線載波通信組網，同時能根據網絡節點的變化實現動態路由，以保證網絡通信的可靠性。

4.2 實驗研究

測試環境為威勝集團廠房，共掛載104塊載波電能表，該載波電能表僅具有中繼轉發功能。使用DJGZ33－WFET1600集中器進行抄表，路由模塊采用ARM Cotex－M4為MCU，并外擴8M Flash用于存儲路由表。

實驗1 組網測試。在路由未知的情況下進行第一次抄表，即網絡組網，其每個時段的抄表數如圖14所示，該算法在10個小時內將104塊表全部抄回，即組網成功。其邏輯拓撲結構如圖15所示，其中方框中括號外和括號內的數字分別表示電表的物理地址和網絡地址。由實驗可見該算法具有較強的路由組網能力。

Figure 14 Statistic chart of meter reading圖14 抄表統計圖

Figure 15 Logic topology structure after network organizing圖15 組網后邏輯拓撲結構

實驗2 日抄讀測試。在成功組網之后，每日的抄讀情況如圖16和圖17所示。由圖可以看出，在0：00～0：59的時間段內能抄到大多數的表，說明組網后的路由很穩定；剩下的表也能在5小時內抄回，抄表成功率為100%。實驗說明該算法具有很強的路由維護能力，能夠進行網絡重構。

Figure 16 Chart of daily meter reading圖16 日抄表情況圖

Figure 17 Chart of daily meter reading（continued）圖17 日抄表情況圖（續）

5 結束語

本文針對工程實踐中載波網絡節點僅具有中繼轉發功能的路由方法進行研究，提出了一種基于圖論生成樹的路由方法。該方法采用遍歷搜索算法中的廣度優先搜索算法，能夠簡單、可靠地實現低壓電力線載波的通信組網。以改進的廣度優先遍歷搜索算法作為路由重構策略，能夠有效增強網絡的抗毀性，快速實現網絡的重構。由于該方法在組網過程中需要一層一層輪詢每一個未組網的節點，故存在組網比較耗時的缺點，對于組網實時性要求不是很高的集中抄表系統，以耗時來換取可靠性的辦法還是適用的。

本文提出的方法相比于類蟻群算法來說，類蟻群算法需要考慮節點信息素的揮發等，組網搜索和工程實現相對比較復雜，而本方法實現過程比較簡單，具有更強的可靠性和穩定性；相比于分簇算法，對網絡節點的要求比較低，僅需要支持中繼轉發功能即可，而分簇算法需要網絡節點具有一定的路由組網能力，網絡節點成本相對較高。

針對本方法路由組網耗時缺點，可以考慮結合其他算法的思想進行改進；本文沒有在路徑優化方面做工作，可以考慮對于路由表采用基于傳輸矩陣或其他方法進行路徑優化。這些問題的改善還需要進一步地研究。

［1］ Zhen Xiang－yu，Yang Qing－qing，Zhou Xiao－fang，et al.A－nalysis and modeling of the indoor low voltage power－line channel noise［J］.Journal of Circuits and Systems，2011，16（4）：58－62.（in Chinese）

［2］ Yang Xiao－xian，Zheng Tao，Zhang Bao－hui.Measurement and research of the characteristics of noise distribution in three－phase four－wire low－voltage power network channels［J］.IEEE Transactions on Power Delivery，2007，22（1）：122－128.

［3］ Cortes J A，Diez L，Canete F J，et al.Analysis of the indoor broadband power－line noise scenario［J］.IEEE Transactions on Electromagnetic Compatibility，2010，52（4）：849－858.

［4］ Ling Cheng，Ferreira H C.Time－diversity permutation coding scheme for narrow－band power－line channels［C］∥Proc of 2012 16th IEEE International Symposium on Power Line Communications and Its Applications（ISPLC），2012：120－125.

［5］ Liu Xiao－sheng，Zhou Yan，Qi Jia－jin.Method study of automatic routing for power line communication［J］.Proceedings of the Chinese Society for Electrical Engineering，2006，26（21）：76－81.（in Chinese）

［6］ Qi Jia－jin，Liu Xiao－sheng，Xu Dian－guo，et al.Simulation study on cluster－based routing algorithm and reconstruction method of power line communication over lower－voltage distribution［J］.Proceedings of the Chinese Society for Electrical Engineering，2008，28（4）：65－71.（in Chinese）

［7］ Qi Jia－jin，Liu Xiao－sheng，Wu Di，et al.Study on power line communication routing method for low－voltage distribution［J］.Chinese Journal of Electron Devices，2008，31（3）：1033－1038.（in Chinese）

［8］ Ran Qing－hua，Wu Yu－cheng，Qi Mei－juan.Research on automatic routing method of low－voltage power line carrier network［J］.Power System Protection and Control，2011，39（10）：53－58.（in Chinese）

［9］ Huo Feng－cai，Ren Wei－jian，Han Bo.An improved ant colony algorithm and its application in power route optimization［J］.Science Technology and Engineering，2009，9（21）：6371－6373.（in Chinese）

［10］ Hong Li.Research on medium access control and cluster routing protocols in low voltage power line carrier network［D］.Qingdao：China University of Petroleum，2010.（in Chinese）［11］ Qi Jia－jin.Research on dynamic routing methods for power line communication over lower voltage distributions［D］.Harbin：Harbin Institute of Technology，2009.（in Chinese）［12］ Dong Ya－bo，Gao Feng.Analysis of structure of carrier communication network for low voltage power［J］.Power System Technology，2003，27（2）：58－62.（in Chinese）

［13］ Rosen K H.Discrete mathematics and its applications［M］.Beijing：China Machine Press，2011.（in Chinese）

附中文參考文獻：

［1］ 甄翔宇，楊慶慶，周曉方，等.室內低壓電力線信道噪聲分析與建模［J］.電路與系統學報，2011，16（4）：58－62.

［5］ 劉曉勝，周巖，戚佳金.電力線載波通信的自動路由方法研究［J］.中國電機工程學報，2006，26（21）：76－81.

［6］ 戚佳金，劉曉勝，徐殿國，等.低壓電力線通信分簇路由算法及網絡重構［J］.中國電機工程學報，2008，28（4）：65－71.

［7］ 戚佳金，劉曉勝，吳迪，等.低壓電力線載波通信網絡組網方法研究［J］.電子器件，2008，31（3）：1033－1038.

［8］ 冉慶華，吳玉成，祁美娟.低壓電力線載波通信網絡自動組網方法研究［J］.電力系統保護與控制，2011，39（10）：53－58.

［9］ 霍鳳財，任偉建，韓博.改進蟻群算法及在電力線路優化問題中的應用［J］.科學技術與工程，2009，9（21）：6371－6373.

［10］ 洪利.低壓電力載波網絡介質訪問控制與分簇路由協議研究［D］.青島：中國石油大學（華東），2010.

［11］ 戚佳金.低壓配電網電力線載波通信動態組網方法研究［D］.哈爾濱：哈爾濱工業大學，2009.

［12］ 董亞波，高鋒.低壓電力線載波通信網絡結構分析［J］.電網技術，2003，27（2）：58－62.

［13］ Rosen K H.離散數學及其應用［M］.北京：機械工業出版社，2011.