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

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

?

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

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

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

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

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

0引言

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

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

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

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

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

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

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

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

1.2相關(guān)定義

1.2.1有序樹(shù)

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

1.2.2分支權(quán)重

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

1.2.3能量值

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

(1)

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

證明：以網(wǎng)關(guān)節(jié)點(diǎn)為頭結(jié)點(diǎn)的這棵拓?fù)錁?shù)具有最短的平均路徑長(zhǎng)度。如果可以證明，對(duì)于網(wǎng)絡(luò)中的任一節(jié)點(diǎn)ni(0

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

2.2地址域分配策略

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

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

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

(3)

(4)

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

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

3有序樹(shù)路由策略

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

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

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

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

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

3.2有序樹(shù)路由策略

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

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

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

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

樹(shù)路由算法(PLC-TR)

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

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

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

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

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

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

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

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

從圖6中可以看出平均端到端通信時(shí)延(包括發(fā)送時(shí)延、傳播時(shí)延、處理時(shí)延)隨著節(jié)點(diǎn)密度的增加而逐漸增高，在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ò)開(kāi)銷，進(jìn)一步使得數(shù)據(jù)包在網(wǎng)絡(luò)中碰撞重傳次數(shù)加大。隨著節(jié)點(diǎn)數(shù)的增加，這種開(kāi)銷快速上升，使得端到端的通信時(shí)延越來(lái)越大。由于PLC-TR成功地減少了這種維護(hù)開(kāi)銷，因此在端到端通信時(shí)延方面大幅降低。也由于同樣的原因，在數(shù)據(jù)包交付率和吞吐量方面PLC-TR也有了較大提高，如圖7、圖8所示。

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

5結(jié)語(yǔ)

本文提出的電力線組網(wǎng)算法PLC-TR充分利用了電力線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行網(wǎng)絡(luò)組建和路由選擇在一定程度上解決了電力線網(wǎng)絡(luò)路由效率不高的問(wèn)題，在很大程度上降低了網(wǎng)絡(luò)開(kāi)銷。通過(guò)仿真實(shí)驗(yàn)表明，PLC-TR在線路質(zhì)量變化的過(guò)程中依然能夠在端到端時(shí)延，數(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。國(guó)家自然科學(xué)基金(61272449,61201212)。何華冰，碩士生，主研領(lǐng)域：無(wú)線傳感器網(wǎng)絡(luò)，嵌入式系統(tǒng)，電力線通信技術(shù)。姚婷婷，碩士生。李云飛。教授。賈俊鋮，副教授。

中圖分類號(hào)TP393

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

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