基于有序樹的電力線網(wǎng)絡(luò)路由算法

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

(蘇州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院　江蘇 蘇州 215006)

?

基于有序樹的電力線網(wǎng)絡(luò)路由算法

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

(蘇州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院江蘇 蘇州 215006)

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

關(guān)鍵詞電力線網(wǎng)絡(luò)有序樹PLC-TR樹路由算法最短路徑算法

0引言

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

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

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

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

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

1電力線網(wǎng)絡(luò)模型

電力線網(wǎng)絡(luò)中將存在三種節(jié)點：網(wǎng)關(guān)節(jié)點、路由節(jié)點和普通節(jié)點。其中，網(wǎng)關(guān)節(jié)點為整個網(wǎng)絡(luò)的中心，是與外網(wǎng)通信的樞紐節(jié)點；路由節(jié)點除了具有普通節(jié)點的功能外主要負(fù)責(zé)路由選擇和選擇轉(zhuǎn)發(fā)節(jié)點和維護(hù)下級節(jié)點；普通節(jié)點和路由節(jié)點為基本的通信節(jié)點。

1.1電力線網(wǎng)絡(luò)模型及相關(guān)定義

如圖1所示，我們將電力線網(wǎng)絡(luò)表示成圖G={N,E}。

圖1　電力線網(wǎng)絡(luò)模型

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

1.2相關(guān)定義

1.2.1有序樹

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

1.2.2分支權(quán)重

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

1.2.3能量值

是指信號的接收節(jié)點所接收到數(shù)據(jù)信號的能量大小。節(jié)點使用相同的能量發(fā)送數(shù)據(jù)信號，信號在電力線上傳輸過程中逐漸衰減，因此節(jié)點間的距離越遠(yuǎn)接收到信號的能量值越小，反之越大?？梢允褂媚芰恐祦肀硎军c對點的最大有效距離。能量值E可以表示為：

(1)

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

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

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

(2)

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

為了降低路由維護(hù)開銷，提高點對點通信效率，在如圖1所示的網(wǎng)絡(luò)模型中，我們將以網(wǎng)關(guān)節(jié)點為頭結(jié)點構(gòu)造一棵有序樹，這棵樹必須滿足兩個條件：(1)具有最短的平均路徑長度，利于降低通信時延，提高包遞率。(2)有序，便于路由選擇。在下文中，拓?fù)涮剿鬟^程將使得這棵樹滿足第一個條件，地址分配策略使其滿足第二個條件。

2有序樹構(gòu)建策略

2.1拓?fù)涮剿骱吐酚晒?jié)點選取策略

在路由節(jié)點選取策略中用能量值表征兩節(jié)點間的距離來代替?zhèn)鹘y(tǒng)算法中使用跳數(shù)來表示的距離，使得本算法更能適應(yīng)時變的電力線網(wǎng)絡(luò)。本文使用樹的廣度優(yōu)先搜索算法探索未知拓?fù)涞碾娏€網(wǎng)絡(luò)，算法優(yōu)先將能量值小的節(jié)點分配為候選路由節(jié)點。如果此節(jié)點可以探索到未加入網(wǎng)絡(luò)的節(jié)點，則其成為路由節(jié)點，否則成為普通節(jié)點，以便探測更遠(yuǎn)的距離。在拓?fù)涮剿鬟^程中，節(jié)點間使用載波監(jiān)聽多點接入碰撞避免(CSMA/CA)算法[16]來提高節(jié)點數(shù)據(jù)鏈路層的通信質(zhì)量。拓?fù)涮剿髑盃顟B(tài)如圖2所示。

圖2　拓?fù)涮剿髑盃顟B(tài)

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

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

圖3　拓?fù)涮剿骱鬆顟B(tài)

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

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

在算法執(zhí)行完成之后，圖3中的節(jié)點ni搜索到了節(jié)點nj、nn、nk，節(jié)點nk搜索到節(jié)點nm、np,則ni和nk成為路由節(jié)點并分別獲得節(jié)點集Ni={ni，nn，nk}和Nk={nm，np}。其他節(jié)點因沒有搜索到任何未加入網(wǎng)絡(luò)的節(jié)點成為了普通節(jié)點。探索完成后的網(wǎng)絡(luò)如圖3所示將電力線網(wǎng)絡(luò)在邏輯上構(gòu)造成樹型拓?fù)洹?/p>

證明：以網(wǎng)關(guān)節(jié)點為頭結(jié)點的這棵拓?fù)錁渚哂凶疃痰钠骄窂介L度。如果可以證明，對于網(wǎng)絡(luò)中的任一節(jié)點ni(0

假設(shè)以最遠(yuǎn)距離選出的轉(zhuǎn)發(fā)序列為P1，轉(zhuǎn)發(fā)節(jié)點數(shù)為x1，并且假設(shè)存在一個轉(zhuǎn)發(fā)序列P2，其每一次并不一定選擇相距最遠(yuǎn)的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，經(jīng)過的轉(zhuǎn)發(fā)節(jié)點數(shù)為x2，x2m，則在dmax范圍內(nèi)節(jié)點nin包含更遠(yuǎn)的可選下一跳節(jié)點。因此每一跳P1序列都比P2序列更接近目的節(jié)點T，所以P2序列的轉(zhuǎn)發(fā)節(jié)點個數(shù)不可能小于P1，x2

2.2地址域分配策略

算法主要是路由節(jié)點根據(jù)其子節(jié)點表中路由節(jié)點的個數(shù)和對應(yīng)的權(quán)重，將其獲得的地址域劃分為多個連續(xù)的的地址段并將這些地址段分配給相應(yīng)的子節(jié)點。且這些地址段在個數(shù)上等于子路由節(jié)點的個數(shù)，大小上和對應(yīng)的子路由節(jié)點權(quán)重成正比使得以網(wǎng)關(guān)節(jié)點為頭結(jié)點的整個電力線網(wǎng)絡(luò)是一棵有序樹。

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

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

(3)

(4)

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

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

3有序樹路由策略

3.1節(jié)點網(wǎng)絡(luò)地址和MAC地址對應(yīng)關(guān)系維護(hù)

節(jié)點間為了能夠通信，源節(jié)點需要知道目的節(jié)點的網(wǎng)絡(luò)地址，在網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時，同一個節(jié)點的網(wǎng)絡(luò)地址可能發(fā)生變化。而節(jié)點的MAC地址是節(jié)點的硬件地址，不會隨網(wǎng)絡(luò)拓?fù)涞淖兓兓?，在具體應(yīng)用中，MAC 地址通常和應(yīng)用相關(guān)。從網(wǎng)絡(luò)地址的分配策略可知：網(wǎng)關(guān)節(jié)點一定是網(wǎng)絡(luò)地址為零的節(jié)點且固定不變。因此任何節(jié)點都知道網(wǎng)關(guān)節(jié)點的網(wǎng)絡(luò)地址可以和網(wǎng)關(guān)節(jié)點通信。和IP網(wǎng)絡(luò)類似，本文使用網(wǎng)關(guān)節(jié)點提供地址解析服務(wù)，即任何節(jié)點都可通過目的節(jié)點MAC地址向網(wǎng)關(guān)節(jié)點請求目的節(jié)點的網(wǎng)絡(luò)地址。為了使網(wǎng)關(guān)節(jié)點包含整個網(wǎng)絡(luò)的最新地址對應(yīng)關(guān)系，網(wǎng)絡(luò)中的節(jié)點行為規(guī)定如下：

1) 網(wǎng)關(guān)節(jié)點要維護(hù)一張網(wǎng)絡(luò)中所有節(jié)點MAC地址和網(wǎng)絡(luò)地址對應(yīng)關(guān)系的解析表。

2) 節(jié)點新加入網(wǎng)絡(luò)，發(fā)送自身的網(wǎng)絡(luò)地址和MAC地址對應(yīng)關(guān)系到網(wǎng)關(guān)節(jié)點。

3) 網(wǎng)關(guān)節(jié)點收到地址解析請求，如果解析表沒有對應(yīng)的網(wǎng)絡(luò)地址則通過廣播方式請求目的節(jié)點網(wǎng)絡(luò)地址。為了減少網(wǎng)絡(luò)中的通信數(shù)據(jù)量，和無線網(wǎng)絡(luò)中的源驅(qū)動路由(AODV)相似，網(wǎng)關(guān)節(jié)點在收到地址解析請求且無對應(yīng)地址表項時，才廣播獲取對應(yīng)的網(wǎng)絡(luò)地址，更新地址表項。

3.2有序樹路由策略

經(jīng)過上文闡述的基于分支權(quán)重的地址分配方法之后，整個電力線網(wǎng)絡(luò)構(gòu)成一棵有序樹。任何子路由節(jié)點地址域是其父路由節(jié)點地址域的細(xì)化，任何父節(jié)點的地址域都是其子節(jié)點的泛化。因此，路由選擇過程就是細(xì)化過程和泛化過程的組合。

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

圖4　樹型網(wǎng)絡(luò)通訊模型

路由策略描述：路由節(jié)點收到的數(shù)據(jù)幀有可能是父節(jié)點發(fā)送的下行幀或子節(jié)點發(fā)送的上行幀。對于下行幀，如果目的節(jié)點網(wǎng)絡(luò)地址在路由節(jié)點地址域內(nèi)，則進(jìn)行轉(zhuǎn)發(fā)，否則不轉(zhuǎn)發(fā)；對于上行幀，如果目的節(jié)點網(wǎng)絡(luò)地址在路由節(jié)點的地址域內(nèi)，則將數(shù)據(jù)幀類型轉(zhuǎn)為下行幀，然后轉(zhuǎn)發(fā)，否則不轉(zhuǎn)發(fā)。如果目的節(jié)點網(wǎng)絡(luò)地址與路由節(jié)點地址相同，則根據(jù)目的節(jié)點的MAC地址一跳內(nèi)到達(dá)目的節(jié)點 。路由算法的偽代碼表示如下所示：

樹路由算法(PLC-TR)

功能:路由節(jié)點通過比較目的網(wǎng)絡(luò)地址與自身地址域,進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。參數(shù):D_ADDR目的節(jié)點的網(wǎng)絡(luò)地址D_MAC目的節(jié)點的物理地址ns_MAC路由節(jié)點物理地址Amins路由節(jié)點地址段最小值A(chǔ)maxs路由節(jié)點地址段最小值START 收到數(shù)據(jù)幀F(xiàn) IF(D_ADDR=Amins)數(shù)據(jù)幀F(xiàn)一跳之內(nèi)可達(dá)目的節(jié)點IF(D_MAC=ns_MAC)路由節(jié)點為目的節(jié)點ELSE:通過D_MAC直接發(fā)送數(shù)據(jù)幀F(xiàn)到目的節(jié)點ENDIF ELSEIF(D_ADDR>AminsANDD_ADDR

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

在路由過程中，算法執(zhí)行兩次比較用以確定目的網(wǎng)絡(luò)地址是否在轉(zhuǎn)發(fā)節(jié)點的地址域內(nèi)，再根據(jù)數(shù)據(jù)幀的上下行屬性即可選擇是否轉(zhuǎn)發(fā)。因此，算法時間復(fù)雜度為O(1)，算法的空間復(fù)雜度為O(n)，n的值與其子節(jié)點的個數(shù)正相關(guān)。

4仿真和仿真結(jié)果分析

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

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

圖5　平均路由跳數(shù)和節(jié)點數(shù)量關(guān)系　圖6　平均端到端時延和節(jié)點數(shù)量關(guān)系

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

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

圖7　數(shù)據(jù)包交付率和節(jié)點數(shù)量關(guān)系　　　圖8　網(wǎng)絡(luò)吞吐量與節(jié)點數(shù)量關(guān)系

5結(jié)語

本文提出的電力線組網(wǎng)算法PLC-TR充分利用了電力線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行網(wǎng)絡(luò)組建和路由選擇在一定程度上解決了電力線網(wǎng)絡(luò)路由效率不高的問題，在很大程度上降低了網(wǎng)絡(luò)開銷。通過仿真實驗表明，PLC-TR在線路質(zhì)量變化的過程中依然能夠在端到端時延，數(shù)據(jù)包交付率等方面表現(xiàn)出較好的性能。

參考文獻(xiàn)

[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。國家自然科學(xué)基金(61272449,61201212)。何華冰，碩士生，主研領(lǐng)域：無線傳感器網(wǎng)絡(luò)，嵌入式系統(tǒng)，電力線通信技術(shù)。姚婷婷，碩士生。李云飛。教授。賈俊鋮，副教授。

中圖分類號TP393

文獻(xiàn)標(biāo)識碼A

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