基于鄰節(jié)點覆蓋的電力線通信組網(wǎng)路由算法

尹 萍，徐東明

(西安郵電大學 通信與信息工程學院，陜西 西安 710121)

0 引 言

低壓電力線載波通信(low voltage power line communication，LVPLC)技術(shù)作為電力行業(yè)特有的通信技術(shù)，在智能配電領(lǐng)域有著廣闊的應用前景，比如高速的窄帶PLC上網(wǎng)、電力系統(tǒng)的智能抄表以及智能家居等[1]。作為數(shù)據(jù)傳輸?shù)囊环N方式，電力線載波通信利用遍布城鄉(xiāng)的供電線路進行數(shù)據(jù)傳輸，主要的優(yōu)勢是無需額外布線。然而，電力線設(shè)計的初衷是用來傳輸電能而非數(shù)據(jù)通信，當以電力線作為通信介質(zhì)時，傳輸信道存在的強干擾噪聲和較大的信號衰減都不利于信號傳輸，這些特有的信道狀況使得通信的可靠性降低。為提升電力線通信的可靠性，當前的研究主要從兩方面入手，即增強物理層的通信能力和建立網(wǎng)絡(luò)中繼[2]。有關(guān)物理層的研究主要從信道特性、信號調(diào)制與解調(diào)等方面入手，而網(wǎng)絡(luò)中繼則主要體現(xiàn)在網(wǎng)絡(luò)拓撲中繼的研究[3]。如文獻[4]提出了基于非交疊分簇算法的電力線通信組網(wǎng)和重構(gòu)算法，該算法能適應信道質(zhì)量的實時變化進行自動組網(wǎng)，邏輯通信鏈路破壞時有一定的自愈能力；文獻[5]提出的基于受限洪泛和分級的LPLC組網(wǎng)算法，可有效提升通信穩(wěn)定性和通信效率。本文將融合非交疊分簇算法層次分明和洪泛算法的可靠性高的特點，提出一種基于鄰節(jié)點覆蓋的分簇洪泛路由組網(wǎng)算法，該算法首先采用覆蓋優(yōu)先策略為相鄰節(jié)點分配不同的轉(zhuǎn)發(fā)優(yōu)先權(quán)，篩選出可能成為簇頭的節(jié)點，然后為避免盲目洪泛出現(xiàn)的消息內(nèi)爆和冗余現(xiàn)象，采用簇節(jié)點的轉(zhuǎn)發(fā)抑制策略和動態(tài)延時轉(zhuǎn)發(fā)機制，在有效降低信道的沖突碰撞的同時確立正式簇頭，達到組網(wǎng)的目的，研究表明該算法可提升電力線通信系統(tǒng)的可靠性。

1 電力線通信組網(wǎng)算法基礎(chǔ)

1.1 低壓配電網(wǎng)通信網(wǎng)絡(luò)模型

低壓配電網(wǎng)拓撲結(jié)構(gòu)因應用場所的不同而復雜多變，常見多用的拓撲主要有樹形拓撲、星型拓撲、環(huán)形拓撲。在樓宇中低壓配電網(wǎng)的結(jié)構(gòu)主要是基于樹形的混合拓撲結(jié)構(gòu)，其電力通信系統(tǒng)可分為兩部分：監(jiān)控室內(nèi)的主機和電網(wǎng)內(nèi)的若干終端。低壓配電網(wǎng)分為三相供電且對于電力線載波通信而言不能跨相通信，三相之間在邏輯拓撲上是并列且相互獨立的，取其中一相拓撲進行研究就具有代表性[6]。為方便論述，本文以一相為基礎(chǔ)，將此相電網(wǎng)上的主機稱為網(wǎng)關(guān)，載波通信模塊稱為節(jié)點。圖1為低壓電力線通信網(wǎng)絡(luò)邏輯拓撲，總網(wǎng)關(guān)下設(shè)網(wǎng)關(guān)A、B、C分別代表配電網(wǎng)中的一相，單相網(wǎng)關(guān)下由若干終端組成。由于低壓電力線的載波通信特點，終端側(cè)負載節(jié)點的臨時加入或退出，使得電力線上信號的數(shù)據(jù)傳輸更加不穩(wěn)定，造成節(jié)點之間往往在物理鏈路上連通而在數(shù)據(jù)鏈路上處于斷開狀態(tài)。如圖2所示，節(jié)點0與1號鏈路的斷裂，造成以3為中繼的節(jié)點4、7、9退出通信。為了保障網(wǎng)絡(luò)的完整通信，從網(wǎng)關(guān)節(jié)點到部分終端節(jié)點的數(shù)據(jù)傳遞需要借助部分節(jié)點充當中介(中繼節(jié)點)才可有效擴展鏈路的通信距離，所有節(jié)點才有可能連入電力線通信網(wǎng)絡(luò)。所以，中繼技術(shù)在實現(xiàn)大規(guī)模的電力線通信中是必不可少[7]。

圖1 低壓電力線通信網(wǎng)絡(luò)拓撲

圖2 節(jié)點退出通信

1.2 非交疊分簇算法

分簇算法是從邏輯上將載波網(wǎng)絡(luò)劃分為“簇”狀結(jié)構(gòu)，由“簇頭”和“簇員”構(gòu)成完整一簇[8]。通過規(guī)定簇成員是否屬于同一簇，分為交疊分簇和非交疊分簇?；陔娏€載波網(wǎng)絡(luò)的樹狀結(jié)構(gòu)，采用非交疊分簇算法分簇過程為：如圖3所示，由網(wǎng)關(guān)節(jié)點0向網(wǎng)絡(luò)洪泛消息，收到消息的一跳通信范圍內(nèi)的節(jié)點1、2、3在回復網(wǎng)關(guān)節(jié)點后成為一級節(jié)點，一級節(jié)點依次按照節(jié)點編號順序替代網(wǎng)關(guān)角色依次向網(wǎng)絡(luò)洪泛消息探測網(wǎng)絡(luò)的二級節(jié)點，依次類推，直到網(wǎng)絡(luò)中所有節(jié)點被發(fā)現(xiàn)[9]。

圖3 非交疊分簇算法分簇

2 基于鄰節(jié)點覆蓋的組網(wǎng)算法原理

2.1 網(wǎng)絡(luò)節(jié)點角色定義

電力線載波網(wǎng)絡(luò)簇的建立是由中心節(jié)點向外發(fā)送消息開始的，網(wǎng)絡(luò)中接收到消息的簇節(jié)點給予相應的反應，其角色(發(fā)送狀態(tài)/接收狀態(tài))的動態(tài)變化使得在不同時刻簇節(jié)點扮演的角色不同[10]。為了方便描述算法形成過程，將有關(guān)節(jié)點定義如下：

中心節(jié)點(網(wǎng)關(guān))：電力線載波網(wǎng)絡(luò)與外網(wǎng)的中轉(zhuǎn)節(jié)點，起到網(wǎng)關(guān)的作用，通過網(wǎng)關(guān)可以管理電力線載波網(wǎng)絡(luò)。

鄰節(jié)點：在當前發(fā)送節(jié)點的有效通信范圍內(nèi)的一跳鄰節(jié)點，構(gòu)成當前節(jié)點的準簇成員。

準簇頭節(jié)點：可能成為簇頭的節(jié)點，一般某簇頭一跳通信范圍內(nèi)某分枝上具有最大覆蓋域的節(jié)點可能成為準簇頭節(jié)點。

正式簇頭節(jié)點：分簇過程中被選擇為簇頭負責轉(zhuǎn)發(fā)數(shù)據(jù)信息的節(jié)點。

2.2 相鄰覆蓋優(yōu)先策略

簇節(jié)點覆蓋域是指在當前發(fā)送節(jié)點(網(wǎng)關(guān)節(jié)點/轉(zhuǎn)發(fā)節(jié)點)洪泛入簇消息時，收到入簇消息的鄰居節(jié)點組成的集合，這些節(jié)點成為某級準簇頭節(jié)點。相鄰覆蓋優(yōu)先是指發(fā)送節(jié)點指定收到消息的節(jié)點的優(yōu)先轉(zhuǎn)發(fā)權(quán)，而優(yōu)先轉(zhuǎn)發(fā)權(quán)由當前節(jié)點的覆蓋域大小決定。覆蓋新區(qū)域越大，轉(zhuǎn)發(fā)優(yōu)先權(quán)就越高[11]。因此，相鄰覆蓋優(yōu)先的關(guān)鍵在于相鄰覆蓋域的確立和轉(zhuǎn)發(fā)優(yōu)先權(quán)的計算。

2.2.1 簇節(jié)點相鄰覆蓋域

通過發(fā)送節(jié)點的物理ID來確定本節(jié)點的鄰居節(jié)點的覆蓋狀態(tài)，因此每個簇節(jié)點都會存有本地路由表和鄰居信息表，鄰居信息表內(nèi)存儲了鄰居節(jié)點的位置信息，發(fā)送節(jié)點的物理ID在洪泛入簇消息數(shù)據(jù)包中獲知。假設(shè)所有節(jié)點有效通信距離為R，任意節(jié)點i位置坐標為(xi,yi)，物理ID記為i。借助圖4，簇節(jié)點的相鄰覆蓋域確立過程如下：

網(wǎng)關(guān)節(jié)點M洪泛入簇消息，收到消息的節(jié)點構(gòu)成以M為簇頭的一級鄰節(jié)點集合U={T、K、X、Y、L}。 依據(jù)洪泛算法擴散的方向性，距離簇頭M最遠的節(jié)點K覆蓋新域最大，具有優(yōu)先轉(zhuǎn)發(fā)數(shù)據(jù)包的權(quán)利。節(jié)點K依據(jù)來自M洪泛數(shù)據(jù)包中的ID，先與自身的ID對比，如果一致，則在規(guī)定時間內(nèi)回復簇頭確立自身角色，如果不一致，則替代簇頭M的角色轉(zhuǎn)發(fā)該數(shù)據(jù)包。直到在有效時間內(nèi)找到目的終端為止。當前轉(zhuǎn)發(fā)節(jié)點可依據(jù)鄰居表查詢得到節(jié)點M的位置坐標(xm,ym)。從圖4可知，M節(jié)點作為K節(jié)點的鄰居，節(jié)點K的鄰節(jié)點中部分節(jié)點與M鄰節(jié)點重疊，重疊的節(jié)點即為M的鄰節(jié)點與K的鄰節(jié)點的交集。即位于K鄰節(jié)點中的任意節(jié)點j若滿足下列條件

則稱K的鄰節(jié)點j處于相鄰覆蓋狀態(tài)。

圖4 相鄰覆蓋優(yōu)先數(shù)據(jù)轉(zhuǎn)發(fā)

2.2.2 簇節(jié)點轉(zhuǎn)發(fā)優(yōu)權(quán)與中繼節(jié)點

當篩選出位于相鄰覆蓋域內(nèi)的簇節(jié)點之后，發(fā)送節(jié)點的鄰節(jié)點就被分為兩類，即處于覆蓋域之內(nèi)與覆蓋域之外的。位于相鄰覆蓋狀態(tài)的節(jié)點構(gòu)成的集合記為U1={T、K、X}，U1集合中的簇節(jié)點將優(yōu)先確立自身是否能成為一級簇頭節(jié)點。非相鄰覆蓋狀態(tài)的節(jié)點構(gòu)成集合U2={A、E、W}，U2集合中的節(jié)點構(gòu)成以當前轉(zhuǎn)發(fā)節(jié)點K為準簇頭的一級準簇成員。如圖4所示，由于洪泛算法擴散的方向性，處于U2中的簇節(jié)點要比位于U1中的簇節(jié)點的覆蓋新域的能力要強,且在U2中，A節(jié)點比節(jié)點E的覆蓋新域要大。所以，距離K節(jié)點最遠的A節(jié)點具有優(yōu)先轉(zhuǎn)發(fā)權(quán)。所以，節(jié)點轉(zhuǎn)發(fā)優(yōu)先權(quán)的確立需要依據(jù)簇節(jié)點所在的集合及距離當前發(fā)送節(jié)點的距離來決定。當簇節(jié)點位于集合U1/U2時，轉(zhuǎn)發(fā)優(yōu)先權(quán)Qi計算如下

2.3 簇節(jié)點的動態(tài)延時機制

相鄰覆蓋優(yōu)先策略使得洪泛消息快速覆蓋網(wǎng)絡(luò)的同時，對準簇頭節(jié)點給予了有效篩選，避免了冗余數(shù)據(jù)包的傳遞。在成簇算法過程中，未經(jīng)限制的洪泛數(shù)據(jù)包往往會發(fā)生信息碰撞，增加消息的重傳機率。為了盡可能避免消息的碰撞引入基于節(jié)點優(yōu)先轉(zhuǎn)發(fā)權(quán)的動態(tài)延時機制，即結(jié)合節(jié)點的轉(zhuǎn)發(fā)優(yōu)先權(quán)給節(jié)點分配不同的轉(zhuǎn)發(fā)時延。動態(tài)延時的分配首先需要判斷當前節(jié)點是否具有轉(zhuǎn)發(fā)權(quán)。同時規(guī)定成為中繼的節(jié)點不在具有轉(zhuǎn)發(fā)權(quán)。對于具有轉(zhuǎn)發(fā)權(quán)的節(jié)點，假設(shè)節(jié)點i收到來自節(jié)點n的洪泛入簇消息，則按照下式進行數(shù)據(jù)包延時轉(zhuǎn)發(fā)：若首次收到數(shù)據(jù)包，轉(zhuǎn)發(fā)時延為

(1)

否則

Tdelay(i) =max{Tc-delay(i),Tm-delay×Qi}

(2)

其中，Tm-delay是轉(zhuǎn)發(fā)數(shù)據(jù)包時的最大延時，Tc-delay是當前轉(zhuǎn)發(fā)節(jié)點收到數(shù)據(jù)包時的剩余延時時間。當節(jié)點第一次收到需要轉(zhuǎn)發(fā)的數(shù)據(jù)包時，需要等待的延時時間如式(1)所示，第一次收到數(shù)據(jù)包的節(jié)點是集中在相鄰覆蓋域之外的節(jié)點中，相鄰覆蓋域之內(nèi)的節(jié)點會出現(xiàn)多次數(shù)據(jù)包的接收轉(zhuǎn)發(fā)，此時則需要按照式(2)，在本次最大延時和當前剩余延時中選取最大值，以保證有足夠的時間進行準簇頭的篩選。

2.4 算法步驟描述

相鄰覆蓋域、優(yōu)先轉(zhuǎn)發(fā)權(quán)和動態(tài)延時機制是本文算法的核心，成簇算法的具體步驟如下：

步驟1 網(wǎng)關(guān)節(jié)點洪泛入簇消息，確定其鄰節(jié)點，計算鄰節(jié)點的相鄰覆蓋域，選取優(yōu)先權(quán)最小的鄰節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，轉(zhuǎn)發(fā)節(jié)點洪泛入簇消息。

步驟2 當前轉(zhuǎn)發(fā)節(jié)點依據(jù)相鄰覆蓋優(yōu)先原則和簇節(jié)點動態(tài)延時標準，依次轉(zhuǎn)發(fā)洪泛包，確定自身的準簇成員，同時篩除不能成為簇頭的節(jié)點。

步驟3 成為準簇成員的節(jié)點回復網(wǎng)關(guān)確立當前轉(zhuǎn)發(fā)節(jié)點為正式簇頭。若在一定的時間內(nèi)未收到準簇成員的回復，則發(fā)送節(jié)點降級為網(wǎng)關(guān)的簇成員。

步驟4 當前轉(zhuǎn)發(fā)簇節(jié)點自身角色確立及準簇成員確立完畢，一級簇頭剩余節(jié)點替代網(wǎng)關(guān)節(jié)點的角色進行洪泛入簇廣播，處理方式同上。

步驟5 依次類推，直到所有節(jié)點都收到過數(shù)據(jù)包，確立了角色，則分簇組網(wǎng)完成。

步驟6 組網(wǎng)完成后，在網(wǎng)絡(luò)運行過程中如果發(fā)現(xiàn)鏈路出現(xiàn)斷裂的少數(shù)節(jié)點，通過洪泛分簇算法為其重新尋找路由。

成簇算法實現(xiàn)的流程如圖5所示。

圖5 成簇算法流程

3 算法仿真及結(jié)果分析

為了驗證算法的有效性，利用Matlab對文中算法進行了仿真。在100m*100m的區(qū)域，40個節(jié)點隨機分布，無孤立節(jié)點。假設(shè)節(jié)點0為網(wǎng)關(guān)節(jié)點，位于區(qū)域正中間。剩余39個節(jié)點代表載波節(jié)點，編號為1，……39。為了模擬電力線載波通信邏輯結(jié)構(gòu)的時變性和隨機性，假設(shè)載波節(jié)點間有效通信距離在20m～25m內(nèi)隨機變化。分別對非交疊分簇算法和改進分簇算法進行仿真，結(jié)果分別如圖6～圖8 所示。

圖6 非交疊分簇算法仿真

圖7 改進分簇算法仿真

圖8 傳輸延時隨傳輸半徑的變化

圖6顯示，采用非交疊分簇算法和改進分簇算法進行組網(wǎng)時，組網(wǎng)結(jié)構(gòu)有明顯差異。圖6組網(wǎng)結(jié)構(gòu)層次分明，節(jié)點之間路徑唯一，簇頭數(shù)目達到20個。圖7節(jié)點之間路徑有所增加，如圖中0→8的路徑除原有的路徑0→7→32→8之外，增加了一條新路徑0→7→23→8。簇頭總數(shù)為14。這是由于在簇節(jié)點角色確定過程中，不滿足條件的節(jié)點成為相鄰節(jié)點之間的中繼。降低了簇頭的數(shù)量，增加了簇間的路徑，從而改善了簇間路徑的唯一性，避免了簇間路徑失效時網(wǎng)絡(luò)的頻繁重構(gòu)。

圖8是采用非交疊分簇算法和改進分簇算法進行組網(wǎng)時，節(jié)點端到端傳輸延時隨傳輸半徑變化的仿真結(jié)果。如圖8所示，當傳輸半徑從20 m均勻增加到50 m時，兩種算法的傳輸延時均呈下降狀態(tài)。相比之下，本文算法的傳輸延時優(yōu)于非交疊分簇算法，這是由于傳統(tǒng)算法在成簇過程中并未對洪泛的范圍及數(shù)據(jù)包的轉(zhuǎn)發(fā)有所限定，而本文算法在成簇過程中對節(jié)點采取了優(yōu)先覆蓋和動態(tài)延時機制，有效避免了消息洪泛的盲目性，降低冗余數(shù)據(jù)包的產(chǎn)生從而避免了信道沖突。使得端到端傳輸延時得以有效降低。

4 結(jié)束語

本文提出了一種基于鄰居節(jié)點覆蓋的分簇路由組網(wǎng)算法，該算法通過利用相鄰覆蓋優(yōu)先策略為相鄰節(jié)點分配不同的轉(zhuǎn)發(fā)優(yōu)先權(quán)，先篩選出可能成為簇頭的節(jié)點，為提高數(shù)據(jù)傳輸效率及避免消息的冗余，結(jié)合節(jié)點的轉(zhuǎn)發(fā)優(yōu)先權(quán)引入了基于簇節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)抑制策略和動態(tài)延時轉(zhuǎn)發(fā)機制，在有效降低信道的沖突碰撞的同時確立正式簇頭，達到組網(wǎng)的目的。仿真結(jié)果表明，該算法可以有效降低節(jié)點端對端傳輸延時，減少簇頭，建立多條通信路徑，進而提升系統(tǒng)的可靠性。此算法為低壓電力線載波通信組網(wǎng)提供了一種可參考的方法。

[1]XIE Zhiyuan,WU Xiaoyan,HU Zhengwei,et al.10 kV powerline communication automatic relay algorithm research and application[J].Electric Power in China,2012,45(11):82-85(in Chinese).[謝志遠,吳曉燕,胡正偉,等.10 kV電力線通信自動中繼算法研究與應用[J].中國電力,2012,45(11):82-85.]

[2]LIU Xiaosheng,LI Yanxiang,WANG Juan,et al.Low vol-tage powerline clustering web mixed multipath routing algorithm and the communication protocol design[J].Journal of Elect-rical Engineering Technology,2015,30(s1):337-345(in Chinese).[劉曉勝,李延祥,王娟,等.低壓電力線分簇蛛網(wǎng)混合多徑盲路由算法及通信協(xié)議設(shè)計[J].電工技術(shù)學報,2015,30(s1):337-345.]

[3]Huang C,Ning Y.Study on cluster-based dynamic routing algorithm in power line communication network[C]//IEEE International Conference on Automation and Logistics.IEEE,2012:461-465.

[4]WANG Zhenchao,WANG Yijin,WANG Jing.A kind of sui-table for Ad hoc network of overlapping clustering routing algorithm[J].Computer Engineering and Application,2012,48(7):88-91(in Chinese).[王振朝,王伊瑾,王靜.一種適用于Ad hoc網(wǎng)絡(luò)的交疊分簇路由算法[J].計算機工程與應用,2012,48(7):88-91.]

[5]Liu X S,Li Y X,Wang J,et al.Multipath blind routing algorithm for low-voltage power line communication based on improved clustering[C]//Fourth International Conference on Instrumentation and Measurement,Computer,Communication and Control.IEEE,2014:578-583.

[6]BAO Weidong.Based on the limited and flooding the network algorithm[J].Power Line Carrier-Current Communication Power of Information and Communication Technology,2014,12(3):41-44(in Chinese).[鮑衛(wèi)東.基于受限和洪泛的電力線載波通信組網(wǎng)算法[J].電力信息與通信技術(shù),2014,12(3):41-44.]

[7]Liu X S,Li Y X,Wang J,et al.Multipath blind routing algorithm for low-voltage power line communication based on improved clustering[C]//Fourth International Conference on Instrumentation and Measurement,Computer,Communication and Control.IEEE,2014:578-583.

[8]Xie Z Y,Wu X Y,Liu J N,et al.Study on automatic routing algorithm for medium voltage powerline communication[C]//International Conference on Systems and Informatics.IEEE,2012:1577-1580.

[9]LIN Jingdong,QIN Yulong,LIAO Xiaoyong.Electric power carrier communication research dynamic network algorithm[J].Journal of Control Engineering,2013,20(5):841-843(in Chinese).[林景棟,秦玉龍,廖孝勇.電力載波通信動態(tài)組網(wǎng)算法的研究[J].控制工程,2013,20(5):841-843.]

[10]HONG Li.Low voltage power carrier network media access control and clustering routing protocol research[D].Qingdao:China University of Petroleum (East China),2010:71-84(in Chinese).[洪利.低壓電力載波網(wǎng)絡(luò)介質(zhì)訪問控制與分簇路由協(xié)議研究[D].青島:中國石油大學(華東),2010:71-84.]

[11]LI Fangmin,LIU Xinhua,KUANG Hailan.An energy efficient wireless sensor network low latency flooding algorithm study[J].Journal of Communications,2007,28(8):46-53(in Chinese).[李方敏,劉新華,曠海蘭.無線傳感器網(wǎng)絡(luò)中一種高能效低延時的泛洪算法研究[J].通信學報,2007,28(8):46-53.]

[12]ZHAO Tao,LI Jianqi,WANG Zhihui,et al.A clustering routing algorithm based on flooding probability and statistics in the application of low voltage power carrier network research[C]//Power Communication Management and Smart Grid Communication Technology BBS,2013(in Chinese).[趙濤,李建岐,王智慧,等.一種基于洪泛概率統(tǒng)計的分簇路由算法在低壓電力載波組網(wǎng)中的應用研究[C]//電力通信管理暨智能電網(wǎng)通信技術(shù)論壇,2013.]