高新賀，劉 萌，徐 廣，王 銳

(中國海洋大學 計算機科學系，山東 青島266100)

電力線通信 PLC(Power Line Communication)，又稱電力線載波通信，是指利用電力線，通過載波方式將模擬或數(shù)字信號進行傳輸?shù)募夹g(shù)，是電力系統(tǒng)特有的通信方式。通常所說的電力線載波通信多指窄帶電力線通信技術(shù)，即指帶寬限定在 3 kHz～500 kHz、通信速率小于1 Mb/s的電力線載波通信技術(shù)[1]。

目前電力線載波通信研究多集中在信道特性分析、估測、編/解碼、功率控制和頻譜管理等領(lǐng)域。雖然有部分文獻[1-4]對電力線載波自動抄表系統(tǒng)路由技術(shù)進行了探討，但開展有關(guān)電力線通信路由算法的研究還不夠深入廣泛。

本文著重介紹自動抄表系統(tǒng)中用于實現(xiàn)監(jiān)控電表和例行抄讀業(yè)務(wù)的路由算法——點名請求算法和數(shù)據(jù)收集算法。

1 電力線通信自動抄表系統(tǒng)

基于電力線通信技術(shù)的自動抄表系統(tǒng)是一個3級系統(tǒng)，由主站、集中器以及電能表組成，物理拓撲結(jié)構(gòu)如圖1所示。

主站是一個管理系統(tǒng)，每個電力公司設(shè)置一個主站系統(tǒng)統(tǒng)轄管理所有的集中器和電能表。每個配電臺區(qū)（一臺配電變壓器供電的區(qū)域）中安裝一只集中器，用于管理所在臺區(qū)的用戶電能表。集中器與主站之間通過公共網(wǎng)絡(luò)（GPRS、PSTN、GSM等）通信。電力線通信限于配電臺區(qū)內(nèi)。集中器和電能表都具備電力線通信能力，它們之間通過220 V電力線交換數(shù)據(jù)，從而互連成一個通信網(wǎng)絡(luò)。

在自動抄表領(lǐng)域，兩個基本的功能需求是點名請求和數(shù)據(jù)收集。點名請求一般由人工從主站發(fā)起，指定監(jiān)控某只電能表，例如讀取電能表數(shù)據(jù)、狀態(tài)，或者發(fā)送通/斷電指令。數(shù)據(jù)收集是定期抄讀全部電能表某一時刻的數(shù)據(jù)，用于每月的計費收費或者每日的線損計算考核。本文針對這兩個最常用功能，介紹相關(guān)的路由算法。

由于電力線最初的設(shè)計是以傳輸電能為目的，與專門進行數(shù)據(jù)傳輸?shù)碾p絞線、同軸電纜以及光纖等介質(zhì)相比，具有自己的特點。當前電力線通信技術(shù)的發(fā)展狀態(tài)和特點概述如下：

(1)低速率。為了應對電力線上固有的強噪聲，電力線通信速率一般不太高，窄帶電力線通信的有效速率通常都低于 1 kb/s。

(2)短距離。電力線對于載波信號衰減較高，直接通信距離通常是數(shù)百米甚至數(shù)十米。環(huán)境惡劣時，兩節(jié)點之間的報文傳遞甚至需要10多個中間節(jié)點的中繼轉(zhuǎn)發(fā)。

(3)半雙工。受成本所限，各節(jié)點的通信芯片上的接收和發(fā)送不能同時工作。當一個節(jié)點在發(fā)送報文時，它就不能偵聽、接收報文，反之亦然。實際上，在任何時間，通信節(jié)點處于且僅處于以下4種狀態(tài)之一：

①發(fā)送態(tài)：正在發(fā)送某個報文；

②偵聽態(tài)：試圖捕獲其他節(jié)點發(fā)出的報文；

③接收態(tài)：正在接收某個報文；

④處理態(tài)：忙于節(jié)點內(nèi)部的處理，例如報文的解析或組織、電能計量等。

(4)同頻點。各節(jié)點工作在同一個通信頻點，節(jié)點發(fā)送報文的本質(zhì)方式是廣播，發(fā)送的報文可以同時被多個節(jié)點接收。這意味著如果多個不同的報文同時到達同一個節(jié)點，這些報文會在該節(jié)點處發(fā)生沖突，該節(jié)點識別不出任何一個報文，甚至不能夠判斷出網(wǎng)絡(luò)上有多少個節(jié)點在發(fā)送報文，因為通信節(jié)點不能夠區(qū)別背景噪音與報文沖突的差異。

(5)時變性。由于隨機干擾、用電器關(guān)停啟動、環(huán)境溫度變化、阻抗變化等原因，電力線通信具有不確定性，網(wǎng)絡(luò)的通信拓撲結(jié)構(gòu)不是恒定的。

(6)非對稱。因為噪音分布的不均勻性、元器件的離散性，兩節(jié)點之間通信往往具有不對稱性。可能節(jié)點u能夠正確地接收到節(jié)點v發(fā)送的報文，但是節(jié)點v接收不到節(jié)點u發(fā)送的報文。

當前基于電力線通信技術(shù)的自動抄表系統(tǒng)的重要特點是零知識初態(tài)。系統(tǒng)初始時，各電能表節(jié)點僅知道自己的通信編號(ID)，不知道除了自己之外還存在多少個通信節(jié)點，更不知道能夠與哪些節(jié)點直接通信。集中器除了知道自己的編號，還知道臺區(qū)內(nèi)它所統(tǒng)轄的所有電能表節(jié)點及其編號，但對于拓撲結(jié)構(gòu)等路由信息完全不知。

2 網(wǎng)絡(luò)模型及問題描述

2.1 網(wǎng)絡(luò)模型

本文將給出2個面向點名請求問題的路由算法和3個面向數(shù)據(jù)收集問題的路由算法。假設(shè)電力線通信是對稱的，這樣一個配電臺區(qū)內(nèi)組成的電力線通信網(wǎng)絡(luò)可以抽象為簡單無向圖 G=(V，E)。 其中，V={v0，v1，v2，…，vn}為全部通信節(jié)點的集合，包括集中器節(jié)點v0和n個電能表節(jié)點 v1，v2，…，vn；E=V2為 G 的邊集合，如果邊(u，v)∈E，則表示節(jié)點u與v可以互相直接通信。否則，u與v之間的通信報文必須通過其他一個或多個節(jié)點中繼轉(zhuǎn)發(fā)。

兩個節(jié)點 u、v之間的距離（跳數(shù)）是圖 G中 u、v之間最短路徑 u=u0u1…uk=v的長度 k，記為 d(u，v)。如果兩節(jié)點之間的距離為k，其中一個節(jié)點發(fā)出的報文至少需要經(jīng)過k次跳轉(zhuǎn)才能到達另一個節(jié)點。

如果d(v0，u)=k，即節(jié)點 u距離集中器節(jié)點 v0為 k跳，則稱節(jié)點u為k跳節(jié)點。在此定義下，集中器節(jié)點v0是0跳節(jié)點，能夠與集中器直接通信的節(jié)點稱為1跳節(jié)點。

2.2 問題描述

在上述模型下，自動抄表系統(tǒng)的2個基本功能需求的路由問題可以敘述為：

(1)點名請求：集中器節(jié)點v0有一個發(fā)往電能表節(jié)點u的請求報文Q，節(jié)點u收到Q后將回應報文R發(fā)送給節(jié)點v0，要求給出傳送此類報文的算法和協(xié)議。

(2)數(shù)據(jù)收集：集中器節(jié)點 v0發(fā)出請求，要求所有電能表節(jié)點向v0發(fā)送各自的回應報文，給出執(zhí)行此功能的算法和協(xié)議。

本文主要從時間效率和能量損耗兩方面考察算法的性能。由于電力線通信的速率低，報文旅程的時間主要耗費在報文跳轉(zhuǎn)的過程中，途經(jīng)各節(jié)點的本地處理時間可以忽略不計，以所需報文的跳數(shù)衡量其時間復雜性。當節(jié)點靜默時幾乎不耗電，能量主要耗費在發(fā)送報文的過程中，所以以各節(jié)點報文發(fā)送次數(shù)之和衡量能量耗費。

由于電力線通信的時變性和不確定性，評估算法的平均或最壞時間、能量耗費需要引入合理的概率模型和復雜的概率分析。為了簡便，本文只估測算法能夠達到的最好情況。

3 點名請求算法

集中器節(jié)點v0向一個k跳的電能表節(jié)點發(fā)出請求報文，請求報文至少需要k次跳轉(zhuǎn)才能到達u。同樣，u的回應報文也至少需要k次跳轉(zhuǎn)才能到達v0。于是給出點名請求問題的時間和能量下界。

定理1如果v0點名請求u，則任何正確完成該請求的算法所需的時間和能量皆不小于2d(v0，u)。

以下分別給出2個算法：第一個是單路徑路由SPR（Single-Path Routing）算法，第二個是全路徑路由APR（All-Path Routing）算法。

3.1 單路徑算法SPR

在單路徑算法SPR下，如果集中器節(jié)點v0點名請求電能表節(jié)點 u，v0首先決定一條到達 u的路徑v0=w0w1…wk=u，然后附加請求指令q形成單路徑點名請求報文Q={w0w1…wk，q}。v0在發(fā)出Q之后的2k跳時間內(nèi)等待由 u發(fā)送回來的回應報文R（如果超時，可斷定執(zhí)行失?。?/p>

單路徑點名請求報文Q由集中器節(jié)點v0發(fā)出后，將按照v0規(guī)定的路徑依次經(jīng)過中繼節(jié)點w1…wk-1，直到目的節(jié)點u。電能表節(jié)點u的回應報文R將沿Q的來路返回。

Q在旅途中已經(jīng)跳過的路徑被刪除，若路途中被轉(zhuǎn)發(fā)的 Q={w0w1…wk，q}，則其中的 w0w1…wk只是含當前跳(w0，w1)的剩余路徑。

電能表節(jié)點執(zhí)行如下算法：

(1)電能表節(jié)點收到單路徑點名請求報文Q={w0w1…wk，q}：

①如果 myID=w1、k＞1（本節(jié)點是中繼節(jié)點）：記錄節(jié)點 w0和 w2，刪除路徑中的節(jié)點 w0，發(fā)出報文 Q={w1w2…wk，q}，設(shè)置2k跳的計時器，進入計時等待狀態(tài)；

②如果 myID=w1、k=1(本節(jié)點是目的節(jié)點)：記錄節(jié)點 w0，交應用程序處理 Q，將響應結(jié)果 r組成回應報文R={myID，myID，w0，r}，其中頭部的 3個節(jié)點標識分別表示R的源節(jié)點、當前發(fā)送節(jié)點、當前接收節(jié)點；

③否則忽略。

(2)電能表節(jié)點在計時等待狀態(tài)的算法如下：

①如果超時事件發(fā)生：退出等待狀態(tài)；

②如果收到回應報文R={ID0，ID1，ID2，r}， 并 且myID=ID2、w2=ID1：修改 R={ID0，myID，w0，r}，發(fā)送該報文。

SPR算法的主要優(yōu)點在于簡單直接。如果集中器能夠確定出有效的最短路徑，可以在時間和能量上與理論下界匹配，但實際上這一點卻往往不能保證。

算法SPR存在的問題是：強烈依賴路由知識，算法要求集中器節(jié)點掌握全局的路由信息，需要靠專門的智能學習算法探索路徑或者在日常工作過程中總結(jié)積累；其結(jié)果是系統(tǒng)初始時性能低下，需要較長一段時間的運行才能趨于穩(wěn)定；不能應對時變性，路由知識獲取和使用不在同一時間，在時變性高的環(huán)境下，過時的路由知識反而浪費時間；成功率低，當集中器節(jié)點決定沿一條長度為k的路徑訪問請求一個電能表節(jié)點時，需要報文來回連續(xù)成功跳轉(zhuǎn)2k次。由于通信的不確定性，實際上一次跳轉(zhuǎn)成功的概率p＜1。于是點名請求的成功概率為p2k，成功率隨著路徑的變長急劇下降。

3.2 全路徑點名請求算法APR

全路徑點名請求算法APR使請求/回應報文在旅行過程中衍生成多路[5]，同時沿著所有可能的路徑向目的節(jié)點推進。該算法又稱為泛洪算法，該算法具有簡單易實現(xiàn)、時間最優(yōu)、成功率高、零知識運行、克服時變性和隨機干擾能力強的優(yōu)點。

如果電力線上多個節(jié)點同時發(fā)送不同的報文，會導致在這些節(jié)點通信范圍重疊的區(qū)域發(fā)生沖突。但是，如果這些節(jié)點同時發(fā)送同一個報文，電力線上傳播的信號會因疊加而加強，其他節(jié)點能正確接收這個報文。APR算法正是基于這一論斷。試驗表明，這一論斷至少在FSK擴頻通信的方式下是成立的。

在APR算法下實現(xiàn)的點名請求及其回應報文的格式形如{x，y，k，l，p}。 其中的 p 是請求指令或應答結(jié)果。x是報文的源節(jié)點ID，如果是請求報文，它應該是集中器節(jié)點v0，如果是回應報文，它應該是一個電能表節(jié)點。y是報文的目的節(jié)點ID，如果是請求報文，它應該是一個電能表節(jié)點，如果是回應報文，它應該是集中器節(jié)點v0。k是報文的可以旅行的距離（跳數(shù)）。l是報文的已經(jīng)旅行的距離（跳數(shù)）。

當集中器節(jié)點v0點名請求電能表節(jié)點u時，v0首先估測u距離它的跳數(shù)k，將有關(guān)信息和點名請求指令q一起組成全路徑點名請求報文 Q={v0，u，k，1，q}發(fā)出，然后在2k跳時間內(nèi)等待以u為源節(jié)點的回應報文R(如果超時，可斷定執(zhí)行失敗)。

各電能表節(jié)點上的APR算法如下：

(1)事件“收到全路徑點名請求報文 Q={x，y，k，l，q}”：

①如果 myID≠y、k＞l：將 Q 中 l+1，發(fā)出報文 Q={x，y，k，l+1，q}，在 k-l-1 跳時間內(nèi)屏蔽事件“收到全路徑點名請求報文Q”；

②如果 myID=y：記錄 x，k，l，將 q交給應用程序處理，取應用程序返回結(jié)果r形成回應給節(jié)點x的報文R={myID，x，l，1，r}, 等待 k-l跳時間后發(fā)出報文 R。

(2)事件“收到全路徑點名回應報文 R={x，y，k，l，r}”：

如果 myID≠y、k＞l：將 Q 中 l+1，發(fā)出報 文 R={x，y，k，l+1，r},在 k-l-1跳時間內(nèi)屏蔽事件 “收到全路徑點名回應報文R”。

由于多個節(jié)點可能同時收到全路徑點名請求報文Q={x，y，k，l，q}， 算法實現(xiàn)的關(guān)鍵點在于保證那些滿足條件 myID≠y和 k＞l的節(jié)點必須在同一時刻轉(zhuǎn)發(fā)報文Q={x，y，k，l+1，q}， 以確保這些節(jié)點發(fā)送到電力線上的的信號是相互疊加而不是相互抵消。同樣，對于事件“收到全路徑點名回應報文 R={x，y，k，l，r}”的實現(xiàn)，必須使那些滿足條件myID≠y和 k＞l的節(jié)點在同一時刻發(fā)送報文 R={x，y，k，l+1，r}。

算法APR的唯一缺點是高能耗。最壞情況下，網(wǎng)絡(luò)中的每個電能表節(jié)點都要參與兩次報文發(fā)送（請求和回應各一次），能量消耗達到2n+1。

算法APR的時間復雜性為k+d(v0，u)，如果集中器能夠使 k=d(v0，u)，時間復雜性可降至 2d(v0，u)，達到最優(yōu)，同時能量消耗也得到改善。這一點容易做到，只需要集中器節(jié)點增加總結(jié)積累和管理各節(jié)點跳數(shù)的算法即可。

4 數(shù)據(jù)收集算法

集中器v0發(fā)出數(shù)據(jù)收集請求，網(wǎng)絡(luò)中的n個電能表節(jié)點向集中器發(fā)送回應報文。對一個k跳的電能表節(jié)點，回應報文至少需要k次跳轉(zhuǎn)才能到達集中器。下面給出數(shù)據(jù)收集問題的時間和能量下界。

定理2如果v0收集網(wǎng)絡(luò)中的n個電能表節(jié)點的數(shù)據(jù)，則任何正確完成該數(shù)據(jù)收集算法所需的時間和能量皆不小于

在本節(jié)中首先利用已有的點名請求算法實現(xiàn)數(shù)據(jù)收集算法，而后提出一個新的數(shù)據(jù)收集算法：并行路由算法 PRA（Parallel Routing Algorithm）。PRA算法中的報文都是并行傳輸?shù)模⑶沂褂门R時路由信息，可以減少發(fā)送報文的數(shù)量，縮短抄表時間。

4.1 利用點名請求算法實現(xiàn)數(shù)據(jù)收集算法

重復n次點名請求算法就可以收集網(wǎng)絡(luò)中所有電能表的數(shù)據(jù)，實現(xiàn)數(shù)據(jù)收集算法。

4.2 并行式路由算法PRA

PRA算法的報文在傳輸過程中采用存儲轉(zhuǎn)發(fā)機制。每一個收到報文的節(jié)點，首先向發(fā)送方回復一個確認，然后將報文保存到當?shù)氐囊粋€待發(fā)隊列中。報文當前所在節(jié)點根據(jù)報文的目的地和線路狀況來決定將報文發(fā)送給哪一個節(jié)點。沒有節(jié)點為該類報文確定出全部的路徑，下一步跳往哪個節(jié)點是由當前轉(zhuǎn)發(fā)節(jié)點臨時決定的。節(jié)點轉(zhuǎn)發(fā)報文后，等待接收方回復一個確認。只有得到確認后，發(fā)送方才能將報文從自己的待發(fā)隊列中刪除，從而解除它對該報文所負的責任。否則，若在規(guī)定的時間內(nèi)沒有收到接收方的確認，則需尋機再次轉(zhuǎn)發(fā)。

PRA 算法報文的格式形如{x，u，v，y，q，r}，其中的 q是請求指令，而r是節(jié)點的應答結(jié)果，x是報文的源節(jié)點ID，u是報文的當前發(fā)送節(jié)點 ID，v是報文的當前接收節(jié)點ID，y是報文的目的節(jié)點 ID，在 PRA算法中y一直是集中器節(jié)點v0。

當集中器v0要收集網(wǎng)絡(luò)中所有電能表節(jié)點的某項數(shù)據(jù)時，v0會發(fā)送報文{v0，v0，v0，v0，q}。

各電能表節(jié)點上的PRA算法如下：

(1)電能表節(jié)點收到報文 P={x，u，v，v0，q，r}：

①如果 myID≠v：記錄 preID=u，將 q交給應用程序處理，取返回結(jié)果r形成發(fā)送到節(jié)點u的報文P={myID，myID，u，v0，q，r}。 節(jié)點將該報文存放到待發(fā)隊列尾，并等待發(fā)送報文P。電能表節(jié)點屏蔽該事件直到算法結(jié)束；

②如果 myID=v：向節(jié)點 u發(fā)送確認，修改 P={x，myID，preID，v0，q，r}，將該報文存放到待發(fā)隊列尾，并等待發(fā)送報文P。

(2)電能表節(jié)點發(fā)送待發(fā)隊列頭的報文，然后進入計時等待狀態(tài)。在計時等待狀態(tài)的算法如下：

①超時發(fā)生：重新發(fā)送待發(fā)隊列頭報文；

②收到確認：從待發(fā)隊列頭刪除報文，發(fā)送下一個報文。

當忽略發(fā)送確認報文給算法帶來的影響，并假設(shè)在報文的傳輸過程中，沒有重傳現(xiàn)象發(fā)生，并且報文按最優(yōu)路徑到達集中器，PRA算法的時間復雜性為1+能量消耗為時間和能量損耗都達到理論下界。但在實際應用中很難達到這種理想狀態(tài)。

PRA算法的主要優(yōu)點是：使用臨時路由，可以更好地應對電力線網(wǎng)絡(luò)的時變性，本地的臨時路由信息隨著報文的傳遞快速更新，可以更準確地反應網(wǎng)絡(luò)的拓撲結(jié)構(gòu)；報文可并行傳輸，并且傳輸?shù)亩际巧闲谢貞獔笪?，減少了發(fā)送報文的數(shù)量，節(jié)約了抄表時間；多任務(wù)機制，在網(wǎng)絡(luò)中可以發(fā)送不同的報文，因此在同一時間可以執(zhí)行不同的任務(wù)。

本文提出了2種自動抄表系統(tǒng)路由算法，其中點名請求算法能夠很好地解決電力線載波抄表系統(tǒng)中對某塊表的點名抄讀任務(wù)，PRA算法能顯著減少整個網(wǎng)絡(luò)發(fā)送的報文數(shù)量，縮短抄表時間。 由于電力線信道環(huán)境的特殊性，使得應用單一的路由算法在抄表過程中表現(xiàn)不理想。對于不同的線路狀況和通信要求應采用不同的路由算法來提高抄表成功率，這就給電力線通信路由算法帶來了新的問題。目前，電力線通信路由算法的研究中還存在著許多亟待解決的問題，有待于進一步深入研究。

[1]劉曉勝，周巖，戚佳金.電力線載波通信的自動路由方法研究[J].中國電機工程學報，2006，26(21)：76-81.

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

[3]丹梅.自動抄表系統(tǒng)幀中繼技術(shù)及其實現(xiàn)[J].儀表技術(shù)，2002，(1)：15-17．

[4]趙建軍，侯彥東，張苗輝.基于網(wǎng)絡(luò)技術(shù)的電力載波抄表系統(tǒng)[J].計算技術(shù)與自動化，2006，25(2)：52-54．

[5]CHROBAK M，GPIENIECT L，RYTTER W.Fast broadcasting and gossiping in radio networks.Proceedings of the 41st Annual Symposium on Foundations of Computer Science，2000 IEEE：575-581.