基于有序樹的電力線網絡路由算法

何華冰　 姚婷婷　李云飛　賈俊鋮

(蘇州大學計算機科學與技術學院　江蘇 蘇州 215006)

?

基于有序樹的電力線網絡路由算法

何華冰 姚婷婷李云飛賈俊鋮

(蘇州大學計算機科學與技術學院江蘇 蘇州 215006)

摘要電力線通信(PLC)依靠現有的分布廣泛的電力線路設施進行數據傳輸不需要額外布線開銷，越來越受到人們的關注。但是，目前電力線網絡路由效率不高，通信延遲較大。為解決以上問題，根據電力線網絡的樹型拓撲結構的特點，提出一種樹路由算法(PLC-TR)。算法將電力線網絡組織成一棵有序樹，并通過地址比較進行路由選擇，最大限度降低了因路由維護產生的網絡開銷。通過仿真表明，和傳統上性能優異的最短路徑算法(SPR)相比，在同等干擾情況下，PLC-TR具有較低的數據包平均傳輸時延和較高的數據包交付率。

關鍵詞電力線網絡有序樹PLC-TR樹路由算法最短路徑算法

0引言

近年來，有關電力線載波通信技術的應用研究格外引人關注[1]，比如高速的寬帶PLC上網、智能家居[2]、大型自動化系統[3]以及電力系統的遠程抄表等。作為數據傳輸的一種方式，電力載波通信利用供電線路進行傳輸數據，不需要額外布線是其主要的應用優勢。但是，配電網絡電氣負載環境復雜，強衰減，高噪聲不利于信號的傳輸。比如，電力信道上負載的動態加入或離開網絡導致輸入阻抗不匹配引起較強的信號衰減。有色背景噪聲、工頻信號噪聲和開關電源引起的脈沖噪聲都嚴重影響了信號的傳輸質量。因此依靠物理層和數據鏈路層有限的點對點通信是難以實現的，其需要網絡層的支持，如中繼轉發和路由選擇等，來提高電力線通信的可靠性。

目前，應用于電力線路由方面的算法很少且其中大部分算法來源于無線網絡[4-8]。國內外很多學者在無線移動自組網方面的研究較多，路由算法一般基于位置或基于拓撲。在信號的傳播方式上，無線方式是以發送節點為中心向四周傳播，而電力線上，信號只能沿著通信線纜進行傳播，即使通信源宿節點在物理上很近也不一定能直接進行通信。因此，基于位置的路由算法不能很好地適用于有線網絡。在應用于電力線網絡的算法中，基于拓撲的最短路徑算法SPR(Shortest Path Routing)[9]由Dijkstra算法將網絡構造成一顆最小生成樹。源宿節點間具有最短路由，在傳統的路由算法中往往是表現最佳的一個，但是SPR需要定期與鄰居節點交換路由信息。由Dijkstra算法計算最短路徑，這無疑增加了網路開銷，而且在節點數目較大時，這種開銷將不容忽視。

Zigbee樹路由算法[10-12]是一種分層的路由算法，其通過規定網絡的最大層數和每個路由節點允許連接的最大節點數來限定網絡。在本網絡中，路由節點通過自身地址和網絡層數及目的地址進行計算來選擇下一跳路由，不需要定期與鄰居節點交換路由信息。在很大程度上避免了多轉發節點產生的數據碰撞，在理論上具有較高的數據包交付率和較低的通信時延。為減少網絡中的信息交換提供了新的思路。

電力線網絡在物理上是樹型或星型結構，電力線上的設備絕大多數情況下都是靜態的，因此，將電力線網絡在邏輯上組織成樹型結構[13-15]，在路由選擇上具有一定優越性。Zigbee樹路由算法應用于電力線網絡中，將面臨以下問題：其一，網絡的最大深度與線路的最大長度和單跳有效通信距離有關，線路越長或單跳有效距離越短,需要的路由深度越大，反之越小。電力線信道具有較強的干擾，而且具有時變性，固定的路由深度難以適應時變的信道。其二，電力線網絡中節點不一定均勻分布，有可能大量的節點集中在某個分支，導致節點稀疏區地址富裕，而在密集區地址不夠分配。

本文主要在Zigbee樹路由算法的基礎上做出改進如下：其一，算法取消了路由層數，每個路由節點都將獲得一個地址域，其最大值為本路由節點的地址，其最小值為以此節點為根節點的子樹中最小的地址。其二，算法需要探索整個網絡，根據節點分布密度分配地址域。稱這種樹為有序樹，改進后的算法為基于有序樹的電力線網絡路由算法(PLC-TR)。

1電力線網絡模型

電力線網絡中將存在三種節點：網關節點、路由節點和普通節點。其中，網關節點為整個網絡的中心，是與外網通信的樞紐節點；路由節點除了具有普通節點的功能外主要負責路由選擇和選擇轉發節點和維護下級節點；普通節點和路由節點為基本的通信節點。

1.1電力線網絡模型及相關定義

如圖1所示，我們將電力線網絡表示成圖G={N,E}。

圖1　電力線網絡模型

其中N={n1,n2,…,nj,…,nM},ni表示第i單個節點，M表示網絡中節點的個數，E表示節點間的邊集，在初始狀態下為空。我們定義一個和節點連通的節點集，表示為：Ni= {nj|Eij>Emin;j= 0,1,2,…,M}。其中nj表示第j個節點，Eij表示ni和nj兩個節點之間傳送信號的能量值，Emin表示保障正常通信的最小能量值。

1.2相關定義

1.2.1有序樹

如果一棵樹滿足，任意兩個以節點ni和nj為頭結點的獨立子樹(其中一棵樹不是另一棵樹的一部分)，i ≠ j，ni子樹中有一個節點的值大于nj子樹其中一個節點的值，那么ni子樹中的任一節點的值都將大于nj子樹中的所有節點的值。那么，這棵樹是一棵有序樹。

1.2.2分支權重

如果節點ni為路由節點，則節點ni的分支權重Wi是以節點ni為頭結點的分支樹上所有路由節點的個數總和。在圖 2中，節點ni為頭結點的分支樹上有ni， nk為路由節點，Wi=2，同樣的Wk=1。

1.2.3能量值

是指信號的接收節點所接收到數據信號的能量大小。節點使用相同的能量發送數據信號，信號在電力線上傳輸過程中逐漸衰減，因此節點間的距離越遠接收到信號的能量值越小，反之越大。可以使用能量值來表示點對點的最大有效距離。能量值E可以表示為：

(1)

其中δ表示一個常數，其意義為能量計算模塊的等效阻值，t1和t2表示接收數據幀的起始和結束時間，f(t) 表示幀中數據幅值隨時間的變化曲線。

能量值的計算也可以依靠功率譜密度經驗式(2)進行計算。功率譜密度經驗公式如下：

μ(f,D)=(0.0034D+1.0893)f+0.1295D+17.3481

(2)

其中，f表示低壓電力線頻率,單位KHz，D表示距離，單位為m。

為了降低路由維護開銷，提高點對點通信效率，在如圖1所示的網絡模型中，我們將以網關節點為頭結點構造一棵有序樹，這棵樹必須滿足兩個條件：(1)具有最短的平均路徑長度，利于降低通信時延，提高包遞率。(2)有序，便于路由選擇。在下文中，拓撲探索過程將使得這棵樹滿足第一個條件，地址分配策略使其滿足第二個條件。

2有序樹構建策略

2.1拓撲探索和路由節點選取策略

在路由節點選取策略中用能量值表征兩節點間的距離來代替傳統算法中使用跳數來表示的距離，使得本算法更能適應時變的電力線網絡。本文使用樹的廣度優先搜索算法探索未知拓撲的電力線網絡，算法優先將能量值小的節點分配為候選路由節點。如果此節點可以探索到未加入網絡的節點，則其成為路由節點，否則成為普通節點，以便探測更遠的距離。在拓撲探索過程中，節點間使用載波監聽多點接入碰撞避免(CSMA/CA)算法[16]來提高節點數據鏈路層的通信質量。拓撲探索前狀態如圖2所示。

圖2　拓撲探索前狀態

能量值確定和候選路由節點選取過程如下：

第一步節點ni廣播發送拓撲探索幀進行探索網絡，假如某節點收到探索幀并且沒有加入網絡，則節點nk計算探索幀的能量值Eik(見式(1))。并和正常通信所要求的最小能量值Emin進行比較，Eik>Emin則以nk節點自身的MAC地址和能量值Eik回復節點ni。如果節點ni收到其他節點的回復，則通知其父節點將其分配為路由節點。如圖3所示，假如有節點nkj、nn、nk回復了節點ni，則ni將節點nj、nn、nk按能量值EijEin、Eik從小到大排列并加入ni的子節點集Ni。

圖3　拓撲探索后狀態

第二步節點ni使用樹的廣度優先搜索策略，優先選擇節點集Ni中能量值最小，即距離節點ni最遠的節點nk為候選路由節點。nk重復第一步中節點ni的過程。如果沒有收到任何未加入網絡的節點的回復，則被分配為普通節點。

第三步在子節點集Ni中選擇能量值次小的節點重復第二步的過程直到節點集Ni中所有的節點都被選為候選路由節點并且執行了搜索過程。

在算法執行完成之后，圖3中的節點ni搜索到了節點nj、nn、nk，節點nk搜索到節點nm、np,則ni和nk成為路由節點并分別獲得節點集Ni={ni，nn，nk}和Nk={nm，np}。其他節點因沒有搜索到任何未加入網絡的節點成為了普通節點。探索完成后的網絡如圖3所示將電力線網絡在邏輯上構造成樹型拓撲。

證明：以網關節點為頭結點的這棵拓撲樹具有最短的平均路徑長度。如果可以證明，對于網絡中的任一節點ni(0

假設以最遠距離選出的轉發序列為P1，轉發節點數為x1，并且假設存在一個轉發序列P2，其每一次并不一定選擇相距最遠的節點作為轉發節點，經過的轉發節點數為x2，x2m，則在dmax范圍內節點nin包含更遠的可選下一跳節點。因此每一跳P1序列都比P2序列更接近目的節點T，所以P2序列的轉發節點個數不可能小于P1，x2

2.2地址域分配策略

算法主要是路由節點根據其子節點表中路由節點的個數和對應的權重，將其獲得的地址域劃分為多個連續的的地址段并將這些地址段分配給相應的子節點。且這些地址段在個數上等于子路由節點的個數，大小上和對應的子路由節點權重成正比使得以網關節點為頭結點的整個電力線網絡是一棵有序樹。

假設：某路由節點ns獲得的地址域為[A1,AN],ns的子節點集Ns中的路由節點的個數為K，路由節點集為R={ns+1，ns+2，…，ns+k}，對應的分支權重集為W={Ws+1，Ws+2，…，Ws+k}。節點ns地址預留百分比為p，其中0

1) 節點ns獲得地址域中值最小的地址作為自身網絡地址。即節點ns獲得的地址為A1，所有ns節點集中的非路由節點共享ns的網絡地址。

(3)

(4)

考慮到電力線信道的特性，雖然有線網絡中的節點是靜態的，但是隨著信道的波動，節點故障或人為因素的影響，任何節點在某一時刻都有可能加入或離開網絡。為了保證節點能夠快速入網和網絡連通性，首先使普通節點共享父節點網絡地址，任何節都作為普通節點加入網絡。由于普通節點只是通信終端不進行路由過程，其加入或離開都不影響網絡連通性。所以共享地址方式更簡單，更快速。

在地址分配過程中每個路由節點都保留了一定比例的預留空間，為新的路由節點加入保留地址。

3有序樹路由策略

3.1節點網絡地址和MAC地址對應關系維護

節點間為了能夠通信，源節點需要知道目的節點的網絡地址，在網絡拓撲發生變化時，同一個節點的網絡地址可能發生變化。而節點的MAC地址是節點的硬件地址，不會隨網絡拓撲的變化而變化，在具體應用中，MAC 地址通常和應用相關。從網絡地址的分配策略可知：網關節點一定是網絡地址為零的節點且固定不變。因此任何節點都知道網關節點的網絡地址可以和網關節點通信。和IP網絡類似，本文使用網關節點提供地址解析服務，即任何節點都可通過目的節點MAC地址向網關節點請求目的節點的網絡地址。為了使網關節點包含整個網絡的最新地址對應關系，網絡中的節點行為規定如下：

1) 網關節點要維護一張網絡中所有節點MAC地址和網絡地址對應關系的解析表。

2) 節點新加入網絡，發送自身的網絡地址和MAC地址對應關系到網關節點。

3) 網關節點收到地址解析請求，如果解析表沒有對應的網絡地址則通過廣播方式請求目的節點網絡地址。為了減少網絡中的通信數據量，和無線網絡中的源驅動路由(AODV)相似，網關節點在收到地址解析請求且無對應地址表項時，才廣播獲取對應的網絡地址，更新地址表項。

3.2有序樹路由策略

經過上文闡述的基于分支權重的地址分配方法之后，整個電力線網絡構成一棵有序樹。任何子路由節點地址域是其父路由節點地址域的細化，任何父節點的地址域都是其子節點的泛化。因此，路由選擇過程就是細化過程和泛化過程的組合。

樹型網絡的數據幀按傳輸方向可以分為由父節點到子節點的下行幀(細化過程)和由子節點到父節點的上行幀(泛化過程)。任意兩個節點進行通信存在圖4所示三種通信模型即上行通信(b)，下行通信(a)，先上行再下行的通信(c)。

圖4　樹型網絡通訊模型

路由策略描述：路由節點收到的數據幀有可能是父節點發送的下行幀或子節點發送的上行幀。對于下行幀，如果目的節點網絡地址在路由節點地址域內，則進行轉發，否則不轉發；對于上行幀，如果目的節點網絡地址在路由節點的地址域內，則將數據幀類型轉為下行幀，然后轉發，否則不轉發。如果目的節點網絡地址與路由節點地址相同，則根據目的節點的MAC地址一跳內到達目的節點 。路由算法的偽代碼表示如下所示：

樹路由算法(PLC-TR)

功能:路由節點通過比較目的網絡地址與自身地址域,進行數據轉發。參數:D_ADDR目的節點的網絡地址D_MAC目的節點的物理地址ns_MAC路由節點物理地址Amins路由節點地址段最小值Amaxs路由節點地址段最小值START 收到數據幀F IF(D_ADDR=Amins)數據幀F一跳之內可達目的節點IF(D_MAC=ns_MAC)路由節點為目的節點ELSE:通過D_MAC直接發送數據幀F到目的節點ENDIF ELSEIF(D_ADDR>AminsANDD_ADDR

如圖4(c)所示源節點S發送數據到目的節點D，由前文地址分配策略可知，父節點的地址域包含所有子節點的地址域，兄弟節點之間地址域不相交。所以，節點的地址域不包含D地址域，在n1的路由表中找不到任何轉發節點可到達節點D，數據幀繼續上行。在節點n2處，由于節點n2是節點D的父節點，其地址域包含節點D的地址域，所以在n2的路由算法中可以找到到達節點D的轉發節點。上行幀在節點n2處轉為下行幀。

在路由過程中，算法執行兩次比較用以確定目的網絡地址是否在轉發節點的地址域內，再根據數據幀的上下行屬性即可選擇是否轉發。因此，算法時間復雜度為O(1)，算法的空間復雜度為O(n)，n的值與其子節點的個數正相關。

4仿真和仿真結果分析

為了驗證PLC-TR算法的性能，本文在NS2環境下對其進行仿真。由于實際情況下電力線網絡存在時變的干擾，源節點發送的節點可能因干擾問題不能正確到達轉發節點或目的節點。為了模擬此種情況，我們建立雙狀態馬爾科夫模型。定義電力線網絡模型中的任意節點ns都有無法接收數據包Serror的狀態和正常收發數據包的Srun狀態，線路影響因子為p(0

為測試PLC-TR和SPR在不同節點數量和線路影響因子下，網絡的平均路由跳數、數據包分組的平均傳輸時延和交付率。仿真模型如圖1所示，模擬電力線總長度為6 km，初始節點個數為19個沿電力線均勻分布，其中節點0為網關節點，節點間的有效傳播距離為200 m，數據發送速率為20 kb/s，每個數據包大小為64 byte，類型為CBR數據包。實驗首先將1至18號節點隨機分配為9對源、目的節點。在節點個數增加到40、80、120、160、200、240時分別以PLC-TR和SPR構建網絡，并使9對源，目的節點進行300秒數據傳輸。仿真數據統計結果如圖5、圖6所示。仿真結果顯示，相比于SPR，PLC-TR平均路由跳數較少了4.3%，在p=0.02和p=0.2下，平均端到端時延分別降低了29.7%和41.4%。PLC-TR在數據包交付率和吞吐量上也有了明顯提高。

圖5　平均路由跳數和節點數量關系　圖6　平均端到端時延和節點數量關系

從圖5中可以看出平均路由跳數(源節點與目的節點間經過的路由節點的個數)PLC-TR算法明在節點增加的過程中平均路由跳數相對穩定，在節點個數達到120以前明顯高于SPR算法。SPR算法中的所有節點都有可能在其他源宿節點的最短路徑上，由于信道干擾，每個節點的失聯都有可能導致失去多條最短路徑，使得平均路由跳數逐漸上升。PLC-TR路由節點的選取是根據能量值進行的，增加節點的數量只能增加普通節點的數量而對路由的深度影響較小，在節點數增加的過程中平均路由跳數相對穩定。

從圖6中可以看出平均端到端通信時延(包括發送時延、傳播時延、處理時延)隨著節點密度的增加而逐漸增高，在p=0.02和p=0.2兩種干擾程度下PLC-TR也明顯低于SPR。由于干擾的原因，SPR算法平均路由跳數高于PLC-TR，需要更多的轉發次數，加大了數據包發生碰撞的概率。除此之外，SPR還有因維護最短路徑的網絡開銷，進一步使得數據包在網絡中碰撞重傳次數加大。隨著節點數的增加，這種開銷快速上升，使得端到端的通信時延越來越大。由于PLC-TR成功地減少了這種維護開銷，因此在端到端通信時延方面大幅降低。也由于同樣的原因，在數據包交付率和吞吐量方面PLC-TR也有了較大提高，如圖7、圖8所示。

圖7　數據包交付率和節點數量關系　　　圖8　網絡吞吐量與節點數量關系

5結語

本文提出的電力線組網算法PLC-TR充分利用了電力線網絡拓撲結構進行網絡組建和路由選擇在一定程度上解決了電力線網絡路由效率不高的問題，在很大程度上降低了網絡開銷。通過仿真實驗表明，PLC-TR在線路質量變化的過程中依然能夠在端到端時延，數據包交付率等方面表現出較好的性能。

參考文獻

[1] Slootweg H.Smart Grids - the future or fantasy?[C]// Smart Metering-making It Happen,Iet.IET,2009:1 - 19.

[2] Lin Y,Latchman H A,Lee M,et al.A power line communication network infrastructure for the smart home [J].Wrl Ommnaon, 2002,9:104 -111.

[3] Bumiller G,Lampe L,Hrasnica H.Power line communication networks for large-scale control and automation systems [J].Ommnaon Magazn,2010,48(4):106 - 113.

[4] Li H,Kensheng W,Li H,et al.Cluster Based Dynamic Routing on Powerline Carrier Network[C]//Wireless Communications,Networking and Mobile Computing,2009.WiCom’09.5th International Conference on.IEEE,2009:1 - 4.

[5] Biagi M,Greco S,Lampe L.Neighborhood-knowledge based geo-routing in PLC[C]//Power Line Communications and Its Applications,IEEE International Symposium on.IEEE,2012:7-12.

[6] Yoon S,Jang S,Kim Y,et al.Opportunistic Routing for Smart Grid With Power Line Communication Access Networks[J].Mar Grd Ranaon on,2014,5(1):303 - 311.

[7] Biagi M,Lampe L.Location Assisted Routing Techniques for Power Line Communication in Smart Grids[C]// Smart Grid Communications,First IEEE International Conference on.IEEE,2010:274-278.

[8] Sanchez J A,Ruiz P M,Marin-Perez R.Beacon-less geographic routing made practical:challenges,design guidelines,and protocols [J].Ommnaon Magazn,2009,47(8):85 - 91.

[9] Galli S,Scaglione A,Wang Z.For the Grid and Through the Grid:The Role of Power Line Communications in the Smart Grid[J].Rodng of H,2011,99:998 - 1027.

[10] Kim T,Kim S H,Yang J,et al.Neighbor Table Based Shortcut Tree Routing in ZigBee Wireless Networks[J].Aralll and Drbd Ym Ranaon on,2014,25(3):706 - 716.

[11] Kim T,Kim D,Park N,et al.Shortcut Tree Routing in ZigBee Networks[C]//Wireless Pervasive Computing,Iswpc 07,International Symposium on.IEEE,2007.

[12] Ren Z,Tian L,Cao J,et al.An efficient hybrid routing algorithm for ZigBee networks[C]// Instrumentation and Measurement,Sensor Network and Automation,International Symposium on.IEEE,2012:415 - 418.

[13] Delestre C,Ndo G,Labeau F.A binary tree network topology for statistical and physical PLC channel modeling[C]//Power Line Communications and Its Applications (ISPLC),2013 17th IEEE International Symposium on.IEEE,2013:327 - 332.

[14] Tripathi S,Dwivedi J K,Shukla M.Power Line Communication with Tree Based Interleaver in Iterative IDMA Systems[C]// Computational Intelligence and Communication Networks,International Conference on.IEEE,2013:286 - 290.

[15] Mirabella O,Raucea A.Tree based routing in power line communication networks[C]//Iecon-annual Conference on IEEE Industrial Electronics Society.IEEE,2010:1398 - 1403.

[16] Pinero-Escuer P J,Malgosa-Sanahuja J,Manzanares-Lopez P,et al.Homeplug-AV CSMA/CA Evaluation in a Real In-Building Scenario [J].Communications Letters,IEEE,2011,(6):683-685.

ORDERED TREE-BASED ROUTING ALGORITHM FOR POWER LINE COMMUNICATION NETWORK

He HuabingYao Tingting Li Yunfei Jia Juncheng

(SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou215006,Jiangsu,China)

AbstractPower line communication (PLC) is getting more and more attentions because it transmits data only relying on existing widespread power line facilities without additional wiring cost.However,current power line network still has the problems of low routing efficiency and high communication delay.To overcome these problems,we propose a tree routing algorithm,short for PLC-TR,according to the characteristics of tree topology of power line network.Specifically,PLC-TR first organises the power line networks into an ordered tree,and then selects the routes by comparing their addresses,this minimises the network overhead caused by routing maintenance.It is shown through simulation that compared with the shortest path routing (SPR) which is traditionally one of the optimal algorithms,under the same disturbance the PLC-TR has lower average packet transmission delay and higher packet delivery rate.

KeywordsPower line networkOrdered treePLC-TRTree routing algorithmSPR

收稿日期：2014-12-01。國家自然科學基金(61272449,61201212)。何華冰，碩士生，主研領域：無線傳感器網絡，嵌入式系統，電力線通信技術。姚婷婷，碩士生。李云飛。教授。賈俊鋮，副教授。

中圖分類號TP393

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.029