基于生成樹的低壓電力線載波的STTDA算法*

索 劍，羅中良

(惠州學(xué)院計(jì)算機(jī)科學(xué)系，廣東 惠州 516007)

近年來，基于擴(kuò)頻通信技術(shù)、OFDM 調(diào)制技術(shù)[1-3]，通過電力線載波PLC(Power Line Carrier)在低壓電網(wǎng)環(huán)境中實(shí)現(xiàn)自動(dòng)抄表已逐漸得到大量應(yīng)用，PLC技術(shù)也被認(rèn)為是“最后300 m”互聯(lián)網(wǎng)接入的理想解決方案之一[4]。

網(wǎng)絡(luò)拓?fù)錁?biāo)明了每一個(gè)智能電表在網(wǎng)絡(luò)中的位置，同時(shí)映射終極用戶；動(dòng)態(tài)獲取低壓電網(wǎng)的網(wǎng)絡(luò)拓?fù)湓陔姳?、電路故障診斷方面具有現(xiàn)實(shí)意義。

網(wǎng)絡(luò)拓?fù)涞墨@取對(duì)于信道傳輸質(zhì)量有較高的依賴，此前的討論大多基于中壓PLC環(huán)境下。近幾年隨著低壓PLC的應(yīng)用拓展，文獻(xiàn)對(duì)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)的探討也逐漸增多，蟻群算法等啟發(fā)式算法被引入此領(lǐng)域應(yīng)用[5-8]。

本文基于生成樹提出了一種低壓PLC網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，給出了判定各類關(guān)系節(jié)點(diǎn)的規(guī)則，通過生成樹的規(guī)則實(shí)現(xiàn)了網(wǎng)絡(luò)拓?fù)涞陌l(fā)現(xiàn)。

1 低壓電力線載波通信模型

1.1 通信網(wǎng)路架構(gòu)及特性

根據(jù)低壓配電網(wǎng)二次布線和低壓電力線通信結(jié)構(gòu)可以把低壓配電網(wǎng)絡(luò)抽象為星形和樹形混合拓?fù)淠Ｐ蚚9-10]。不失一般性，可將其抽象為如圖1所示，由主站、集中器和終端三層結(jié)構(gòu)組成的基本架構(gòu)。目前，通過載波電路已可有效地對(duì)抗頻率選擇性衰落[11]，因此可以通過統(tǒng)計(jì)的方法來計(jì)算分析低壓電網(wǎng)通信信號(hào)的衰減特性[12]，以均值獲取用以表示節(jié)點(diǎn)間距離的可比較的相對(duì)衰減量。集中器和終端通過載波電路沿通信線路發(fā)送廣播信息，收到廣播后的節(jié)點(diǎn)會(huì)返回地址以及本節(jié)點(diǎn)距離廣播節(jié)點(diǎn)的衰減數(shù)據(jù)。

圖1 PLC基本架構(gòu)

在實(shí)際部署中，很多情況是若干電表放置在一個(gè)表箱里的，同一表箱的電表之間衰減遠(yuǎn)小于表箱內(nèi)的電表與該表箱外的電表之間的衰減，不失一般性，可認(rèn)為表箱內(nèi)電表之間的衰減為0；表箱雖不能收發(fā)數(shù)據(jù)，但可依據(jù)表箱中的電表來確定。

1.2 問題描述

一個(gè)低壓PLC子網(wǎng)就是一個(gè)多結(jié)點(diǎn)的多叉樹，節(jié)點(diǎn)之間均可進(jìn)行廣播。圖2為抽象后的模型樹，其中A0為根節(jié)點(diǎn)亦即集中器，An(n<>0)為智能電表亦即樹的節(jié)點(diǎn)，兩節(jié)點(diǎn)之間的衰減量可用于描述節(jié)點(diǎn)間的距離，D0為包含若干終端的表箱。

圖2 模型樹

2 網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)原理與算法設(shè)計(jì)

由圖2可知，拓?fù)錁鋵?shí)際是一個(gè)連通圖G=(A，M)[13]，A為節(jié)點(diǎn)集合，M為邊集合，節(jié)點(diǎn)之間通過M值來確定相互位置，以此構(gòu)成整個(gè)網(wǎng)絡(luò)。

2.1 相關(guān)定義與定理

為了便于描述拓?fù)浒l(fā)現(xiàn)的過程，作如下定義：

定義1 節(jié)點(diǎn)間的距離：設(shè)As、Ad∈G(A)，則Msd為As節(jié)點(diǎn)到Ad節(jié)點(diǎn)的距離。

定義2 最大允許距離：設(shè)Mmax為G中兩節(jié)點(diǎn)可以通信的最大值，即能夠穩(wěn)定傳輸數(shù)據(jù)所需的最大距離值。因此若Msd<=Mmax，則As、Ad兩節(jié)點(diǎn)可以通信；反之則不能通信。

在G中的任何節(jié)點(diǎn)As(s=0，1，2，……，n)均可發(fā)出廣播信息，通過邊連接的所有滿足Msd≤Mmax的其它節(jié)點(diǎn)均可接受該信息，這樣就形成了一個(gè)節(jié)點(diǎn)集合Ca，Ca中的節(jié)點(diǎn)接收到廣播信息后，向As返回地址以及對(duì)應(yīng)的距離值。

2.2 節(jié)點(diǎn)間判定規(guī)則

分析線路中各節(jié)點(diǎn)的距離，節(jié)點(diǎn)之間的關(guān)系存在如下判定規(guī)則：

規(guī)則1：父子節(jié)點(diǎn)判定規(guī)則。如圖3(a)所示，若Ax發(fā)送廣播信息，Ao、Ap、Aq為滿足條件并返回?cái)?shù)據(jù)的節(jié)點(diǎn)，距離最短的節(jié)點(diǎn)則為Ax的兒子；反之，則不能確定是Ax的兒子。若有幾個(gè)節(jié)點(diǎn)距離信息源節(jié)點(diǎn)相等且均為最小，可判定這幾個(gè)節(jié)點(diǎn)均是Ax的兒子。

規(guī)則2：兄弟節(jié)點(diǎn)判定規(guī)則。如圖3(b)所示，若Ax發(fā)送廣播信息，Ao、Ap、Aq為滿足條件并返回?cái)?shù)據(jù)的節(jié)點(diǎn)，其中Mxo

規(guī)則3：表箱內(nèi)電表判定規(guī)則。如圖3(c)所示，設(shè)Ax發(fā)送廣播信息，Ao、Ap、Aq為滿足條件并返回?cái)?shù)據(jù)的節(jié)點(diǎn)，Ao、Ap根據(jù)規(guī)則1可確定為Ax的兒子即Mxo=Mxp；若再次對(duì)Ao做廣播，存在Mop=0，則可判定Ao、Ap在同一表箱。

圖3 拓?fù)浒l(fā)現(xiàn)判定規(guī)則

2.3 STTDA算法設(shè)計(jì)

算法的基本思想是從根節(jié)點(diǎn)開始確定一對(duì)父子關(guān)系，通過分析其他節(jié)點(diǎn)與這對(duì)父子節(jié)點(diǎn)的距離，得到一個(gè)節(jié)點(diǎn)，它要么是父親的兒子，要么是兒子的后代；對(duì)于新確定的父子關(guān)系進(jìn)行遞歸搜索，直到不再搜索出新的節(jié)點(diǎn)為止，每一個(gè)父子關(guān)系最終都得到確定。作如下數(shù)據(jù)結(jié)構(gòu)定義：

T：為目標(biāo)樹集合，其結(jié)構(gòu)為(parent，child，attenuation，box)其中parent為父親節(jié)點(diǎn)，child為兒子節(jié)點(diǎn)，attenuation為兩個(gè)節(jié)點(diǎn)間距離，box為表箱標(biāo)志；

S：為構(gòu)造集合，其結(jié)構(gòu)為(parent，child，attenuation)，屬性含義同上；

A：為候選節(jié)點(diǎn)，即準(zhǔn)備廣播的節(jié)點(diǎn)，是每一次遞歸被最新確定出來的兒子；

Data：為候選節(jié)點(diǎn)A廣播后，滿足條件的數(shù)據(jù)返回集合，其結(jié)構(gòu)為(parent，child，attenuation)，含義同S集合；

L：為一組父子節(jié)點(diǎn)關(guān)系，其結(jié)構(gòu)為(Ax，Ay，Mxy)，其中Ax為父親節(jié)點(diǎn)，Ay為兒子節(jié)點(diǎn)，兩節(jié)點(diǎn)間距離為Mxy。

從根節(jié)點(diǎn)A0開始發(fā)出廣播命令Broadcasting(A0)，則獲得一個(gè)節(jié)點(diǎn)集合C0，C0中任意一個(gè)距離最短的節(jié)點(diǎn)Ak被認(rèn)為是A0的兒子，即為候選節(jié)點(diǎn)，并將該節(jié)點(diǎn)以及與A0的距離記錄在目標(biāo)樹集合T中，所有C0中其他節(jié)點(diǎn)以及與A0的距離值被記錄在構(gòu)造集合S中；從Ak再次發(fā)出廣播命令Broadcasting(Ak)，則可獲得節(jié)點(diǎn)集合C1，將C1集合的所有節(jié)點(diǎn)以及和Ak的距離值也添加進(jìn)S中；從S集合中，可以分析出哪些節(jié)點(diǎn)距離Ak和A0更近一些，刪除距離遠(yuǎn)的父子關(guān)系，在S中找到距離最近的節(jié)點(diǎn)關(guān)系，節(jié)點(diǎn)關(guān)系取決于某一節(jié)點(diǎn)Ak+1(即新的候選節(jié)點(diǎn))與目標(biāo)樹中A0和Ak之間的距離值，亦即Ak+1是A0或Ak的兒子，將此節(jié)點(diǎn)以及和目標(biāo)樹中節(jié)點(diǎn)的距離記錄在目標(biāo)樹中；這樣每次都可求出一個(gè)父子關(guān)系，并以子節(jié)點(diǎn)再次廣播，依次遞歸，可求出所有節(jié)點(diǎn)的父子關(guān)系。

2.4 STTDA算法實(shí)現(xiàn)

根據(jù)上述拓?fù)浒l(fā)現(xiàn)思想，定義如下方法：

PutIntoS(Data)：將返回的數(shù)據(jù)集合送入在構(gòu)造集合S中；

PutIntoT(L，Dxy)：從S集合中將父子關(guān)系L復(fù)制到T集合中。若Mxy=0，則Ax、Ay在同一表箱，記錄同一表箱的標(biāo)志Dxy；否則為空；

Delete(L，Q)：從Q集合中刪除L父子關(guān)系；

Broadcasting(A)：A節(jié)點(diǎn)發(fā)送廣播信息的命令；

GetData(A)：A節(jié)點(diǎn)發(fā)送廣播信息的命令后，得到相應(yīng)的各節(jié)點(diǎn)返回?cái)?shù)據(jù)Data集合；

GetMinRelationship(Q)：Q為父子關(guān)系集合，此命令返回在Q集合中最短距離的一組父子關(guān)系，若有多個(gè)相等最小距離，則隨機(jī)取一組；

GetChild(L)：在一組父子關(guān)系中取出兒子節(jié)點(diǎn)；

GetParent(L)：在一組父子關(guān)系中取出父親節(jié)點(diǎn)；

GetAttenuation(L)：在一組父子關(guān)系中取出距離值；

拓?fù)浒l(fā)現(xiàn)算法實(shí)現(xiàn)如下：

PutIntoT(Φ，A0，0)/*將根節(jié)點(diǎn)A0送入在目標(biāo)樹中*/

A=A0/*將候選節(jié)點(diǎn)設(shè)為A0*/

Do

Broadcasting(A)/*A節(jié)點(diǎn)發(fā)出廣播信息*/

Data=GetData(A)/*得到數(shù)據(jù)返回集合*/

PutIntoS(Data)/*將返回的數(shù)據(jù)集合送入在構(gòu)造集合S中*/

For everyLinS/*在S集合中若存在同一表箱的電表，則讀入T集合中*/

If GetAttenuation(L)=0 then

PutIntoT(L，D)

Delete(L，S)

For everyLinS/*在S集合中若存在某一記錄L，該子節(jié)點(diǎn)已經(jīng)在T集合中出現(xiàn)，則刪除L*/

If GetChild(L)inTDelete(L，S)

For everyLinS/*在S集合中若存在某一記錄L1，其父親節(jié)點(diǎn)和L不同，但兒子節(jié)點(diǎn)相同，而距離值小于L，則刪除L*/

If Exist GetParent (L1)<> GetParent (L) and GetChild(L1)= GetChild(L) and GetAttenuation(L1)< GetAttenuation(L) then Delete(L，S)

L=GetMinRelationship(S) /*在構(gòu)造表S中求出最短距離關(guān)系*/

PutIntoT(L)/*將最短距離關(guān)系送入在目標(biāo)樹中*/

Delete(L，S)

A=GetChild(L)/*取得下一個(gè)候選節(jié)點(diǎn)*/

UntilS=Φ

PrintT/*輸出目標(biāo)樹*/

3 實(shí)驗(yàn)與結(jié)果分析

根據(jù)上述思想，設(shè)計(jì)模擬系統(tǒng)進(jìn)行N個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)的實(shí)驗(yàn)。設(shè)有節(jié)點(diǎn)邏輯如圖4所示。

圖4 邏輯節(jié)點(diǎn)圖

圖4中，An為節(jié)點(diǎn)標(biāo)志，連接線上的數(shù)據(jù)表示衰減，若設(shè)衰減40為可搜索的最大衰減度，則A0可廣播搜索的范圍如圖5(a)所示；進(jìn)行4次搜索后，A1、A6、A12和A2節(jié)點(diǎn)被搜索出來，如圖5(b)所示；圖5(c)所示為相應(yīng)的搜索過程，高亮的部分A2表示剛找出的節(jié)點(diǎn)，它是由A1搜索到的。

以此類推，發(fā)現(xiàn)所有節(jié)點(diǎn)。在此作如下假設(shè)：載波頻率40 k，9 600波特率發(fā)送，則發(fā)送一個(gè)字節(jié)約需1 ms，若一個(gè)消息包24字節(jié)，應(yīng)答消息包8個(gè)字節(jié)，一個(gè)應(yīng)答過程則需32 ms；在真實(shí)情況下，載波傳輸很受到很多干擾因素的影響，應(yīng)答電表需要一段時(shí)間才能發(fā)出應(yīng)答信號(hào)，同時(shí)為了保證傳輸質(zhì)量往往需要3-4次發(fā)送才能完成準(zhǔn)確傳輸，因此可設(shè)一次可靠的完整傳輸需要200 ms。

圖5 搜索過程及結(jié)果

由于在搜索前無法確定到底有多少節(jié)點(diǎn)，也無法確定哪些節(jié)點(diǎn)是葉子節(jié)點(diǎn)，理論上只有遍歷樹中的每一個(gè)節(jié)點(diǎn)，才能確定整體結(jié)構(gòu)；從根自頂向下的搜索時(shí)，對(duì)于每一個(gè)候選節(jié)點(diǎn)，不對(duì)已知所有父輩進(jìn)行廣播并接收數(shù)據(jù)，可有效提高效率。表1為依次搜索出的節(jié)點(diǎn)及相應(yīng)廣播得到的節(jié)點(diǎn)個(gè)數(shù)。

表1 節(jié)點(diǎn)及搜索個(gè)數(shù)

可求得在理想狀況下，該網(wǎng)絡(luò)所有廣播次數(shù)為13，反饋的節(jié)點(diǎn)次數(shù)46，從而可以得到這個(gè)網(wǎng)絡(luò)拓?fù)淅碚摪l(fā)現(xiàn)的時(shí)間為46*200 ms,多次實(shí)驗(yàn)后總衰減量、節(jié)點(diǎn)個(gè)數(shù)和反饋次數(shù)之間的關(guān)系如圖6(a)(b)所示。

圖6 實(shí)驗(yàn)結(jié)果

由圖6(a)和(b)可以看出，節(jié)點(diǎn)個(gè)數(shù)D和總衰減量Msum雖然不易確定和反饋次數(shù)Sum之間的函數(shù)關(guān)系，但隨著節(jié)點(diǎn)個(gè)數(shù)D和總衰減量Msum的增加反饋次數(shù)Sum呈近似線性增加狀態(tài)。

實(shí)際部署中，電表多位于表箱中，對(duì)于同一個(gè)表箱內(nèi)的若干電表來說，僅一次廣播就可以確定相互的關(guān)系，表箱內(nèi)的其它電表只記錄無需再發(fā)出廣播信息，這樣就可大大減少反饋次數(shù)。

4 結(jié) 語

由于智能電表電網(wǎng)需要多次廣播才能得到節(jié)點(diǎn)間的關(guān)系，本文沒有采取多叉樹深度或廣度優(yōu)先遍歷的算法，而是根據(jù)電網(wǎng)的延展以生成樹來進(jìn)行節(jié)點(diǎn)的逐步發(fā)現(xiàn)。智能電表低壓電網(wǎng)拓?fù)浒l(fā)現(xiàn)的意義不僅能夠?qū)崟r(shí)的了解網(wǎng)絡(luò)結(jié)構(gòu)，而且能夠通過已知的網(wǎng)絡(luò)有效地確定故障電表和故障線路，同時(shí)在已知拓?fù)浣Y(jié)構(gòu)的情況下，更高效的數(shù)據(jù)傳輸也成為可能。在未來智能家電、智能樓宇不斷的發(fā)展中，載波電路可植入不同的受控設(shè)備中，其網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)思想類同。

參考文獻(xiàn)：

[1] 張平澤，趙振勇. 基于低壓電力線載波通信方法的比較[J]. 電子設(shè)計(jì)工程，2010，2(2):26-28.

[2] 張廣馳, 江艷敏, 秦家銀. OFDM系統(tǒng)中基于有限反饋的余量自適應(yīng)比特加載[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，48(5)：39-42.

[3] 李峰,蘇愛國,吳茂初，等.自適應(yīng)頻域判決-反饋迫零均衡的 OFDM系統(tǒng)[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，47(4)：38-41.

[4] SILVA J M，WHITNEY B. Evaluation of the potential for powerline carrier to interfere with use of the nationwide differential GPS network[J]. IEEE Trans Power Delivery，2002，4(17):348-352.

[5] 羅中良,易明珠,劉小勇.最優(yōu)化問題的蟻群混合差分進(jìn)化算法研究[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，47(3)：33-36.

[6] 楊佳,許強(qiáng),張金榮，等. 一種新的量子蟻群優(yōu)化算法[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，48(3)：34-37.

[7] 趙杰衛(wèi)，盧文冰，李賢亮.電力線載波自動(dòng)抄表動(dòng)態(tài)路由技術(shù)研究[J].電力系統(tǒng)通信，2007，11:1-4.

[8] 高柏臣，高俊英，潘政剛，等. 基于動(dòng)態(tài)自適應(yīng)路由技術(shù)的低壓PLC 集抄系統(tǒng)[J].電力系統(tǒng)通信，2009.10:23-27.

[9] GEORGE Jee, CON Edison. Demonstration of the technical viability of PLC systems on medium-and low-voltage lines in the United States [J].IEEE Communications,2003(5):108-112.

[10] HALID Hrasnica, ABDELFATTEH Haidine,RALF Lehnert.寬帶電力線通信網(wǎng)絡(luò)設(shè)計(jì)[M]. 宋健,趙丙鎮(zhèn),李曉,譯.北京：人民郵電出版社, 2008.

[11] 樊建學(xué)，盛新富.低壓電力線載波通信技術(shù)的研究[J].電測與儀表，2005(2)：36-38.

[12] 謝飛，熊立翔, 楊士中.低壓電力網(wǎng)載波通信信號(hào)衰減特性的研究[J].電子技術(shù)應(yīng)用,1998(1):36-37.

[13] 陳松，王珊，周明天.一種新的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法[J] .電子與信息學(xué)報(bào)，2010，1(1)：172-176.