電力線通信PLC（Power Line Communication），又稱電力線載波通信，是指利用電力線，通過(guò)載波方式將模擬或數(shù)字信號(hào)進(jìn)行傳輸?shù)募夹g(shù)，是電力系統(tǒng)特有的通信方式。通常所說(shuō)的電力線載波通信多指窄帶電力線通信技術(shù)，即指帶寬限定在3kHz~500kHz、通信速率小于1Mb/s的電力線載波通信技術(shù)。目前電力線載波通信研究多集中在信道特性分析、估測(cè)、編/解碼、功率控制和頻譜管理等領(lǐng)域。雖然有部分對(duì)電力線載波自動(dòng)抄表系統(tǒng)路由技術(shù)進(jìn)行了探討，但開展有關(guān)電力線通信路由算法的研究還不夠深入廣泛。

1 典型的PLCAMR體系

典型的PLCAMR體系由三級(jí)系統(tǒng)構(gòu)成：主站、集中器和電能表終端。主站負(fù)責(zé)管理全局的集中器與電能表信息，可通過(guò)光纖、GPRS、公話網(wǎng)或其他方式與集中器通信；集中器一般每個(gè)配電臺(tái)區(qū)安裝一個(gè)，管理所在臺(tái)區(qū)的全部電能表，其日常工作是通過(guò)電力線通信采集各電能表數(shù)據(jù)；電能表負(fù)責(zé)計(jì)量用電戶的各類用電量。

當(dāng)前的集中器雖然不同程度地具備了自學(xué)習(xí)路由知識(shí)和自組網(wǎng)絡(luò)的能力，但還不能基于純零知識(shí)開始工作。只有在了解了要管轄的電能表編號(hào)及其計(jì)量項(xiàng)目后才能工作，這就要求電力營(yíng)銷部門理清配電臺(tái)區(qū)的用電戶檔案，尤其是電能表編號(hào)，通過(guò)主站將這些資料下發(fā)到臺(tái)區(qū)集中器，才能啟動(dòng)自動(dòng)抄表。同樣，在抄表系統(tǒng)運(yùn)行過(guò)程中，當(dāng)臺(tái)區(qū)內(nèi)發(fā)生更換電能表、新增用電戶或者臺(tái)區(qū)之間發(fā)生線路切換等業(yè)務(wù)時(shí)，必須及時(shí)正確地維護(hù)集中器中的用戶資料。由于電力公司通常是按照面向人工抄表的習(xí)慣劃分組織用戶資料（例如按街道順序組織），理清配電臺(tái)區(qū)與用電戶的關(guān)系往往需要耗費(fèi)很大的人力。所以經(jīng)常因?yàn)榕_(tái)區(qū)集中器裝入了錯(cuò)誤的表號(hào)而導(dǎo)致費(fèi)時(shí)費(fèi)力的現(xiàn)場(chǎng)排查工作，尤其對(duì)于用電歷史長(zhǎng)的老城區(qū)，理清電能表與臺(tái)區(qū)的關(guān)系極其困難，成為普及自動(dòng)抄表技術(shù)的關(guān)鍵瓶頸。

解決上述問題的本質(zhì)在于系統(tǒng)能夠從零知識(shí)開始工作。所謂零知識(shí)是指初始時(shí)主站只知道有哪些配電臺(tái)區(qū)和集中器，但是并不清楚哪些電能表屬于哪個(gè)臺(tái)區(qū)的集中器；集中器僅知道自己的編號(hào)（ID），但不知道有哪些，有多少電能表隸屬自己；電能表僅知道自己的編號(hào)（還有自己的計(jì)量項(xiàng)目），但不知管轄自己的集中器是誰(shuí)。但目前國(guó)家電網(wǎng)關(guān)于自動(dòng)抄表的通信協(xié)議都是主從結(jié)構(gòu)的，電能表作為通信節(jié)點(diǎn)只有被動(dòng)應(yīng)答的能力，不能主動(dòng)發(fā)起通信任務(wù)［1-4］。為了適應(yīng)主從體系結(jié)構(gòu)，本文設(shè)計(jì)了專門的電能表捕獲算法。該算法的優(yōu)點(diǎn)在于不需要額外的空間資源，線性時(shí)間，倘若臺(tái)區(qū)內(nèi)有n個(gè)電能表，算法可在O（n）次報(bào)文跳轉(zhuǎn)時(shí)間內(nèi)完成搜索任務(wù)。

2 表號(hào)捕獲算法

假設(shè)電能表編號(hào)的區(qū)間為［a，b］（實(shí)際應(yīng)用中a=0，b=1012，或者說(shuō)是6 B的BCD碼）。表號(hào)捕獲算法的核心思想比較簡(jiǎn)單，有2點(diǎn)：

（1）對(duì)于給定的表號(hào)區(qū)間I=［a，b］，利用報(bào)文沖突判斷出3種情況：在區(qū)間I中恰有1只電能表；在區(qū)間I中無(wú)電能表；在區(qū)間I中存在多只電能表。

（2）利用二分搜索技術(shù)快速縮減查找空間。

以下分4個(gè)子節(jié)描述基于上述思想的表號(hào)捕獲算法。為了簡(jiǎn)明本文略去實(shí)現(xiàn)細(xì)節(jié)。在以后的敘述中，集中器和電能表統(tǒng)稱為節(jié)點(diǎn)。

2.1 判定給定區(qū)間的鄰居分布情況

首先定義一種查詢報(bào)文Q={IDsource，a，b}。其中IDsource為報(bào)文源節(jié)點(diǎn)（發(fā)出者）的編號(hào)，IDmin≤a≤b≤IDmax.報(bào)文Q向編號(hào)在區(qū)間［a，b］內(nèi)的節(jié)點(diǎn)發(fā)出查詢請(qǐng)求，凡是編號(hào)在此區(qū)間的節(jié)點(diǎn)（即編號(hào)IDme滿足a≤IDme≤b的節(jié)點(diǎn)）收到該報(bào)文后立即回應(yīng)一個(gè)報(bào)文R={IDme，r}，報(bào)出自己的編號(hào)IDme和自己的屬性r.

定義了以上2種報(bào)文，節(jié)點(diǎn)IDsource判定給定區(qū)間［a，b］的鄰居情況的方法是依靠區(qū)別沖突信號(hào)與背景噪音的能力。這種能力是指當(dāng)有多個(gè)節(jié)點(diǎn)同時(shí)發(fā)送報(bào)文時(shí)，接收節(jié)點(diǎn)雖然由于報(bào)文沖突不能正確地收到任何一個(gè)報(bào)文，但不會(huì)和無(wú)報(bào)文（線路上只有背景噪音）混為一談，接收者能夠根據(jù)沖突信號(hào)與背景噪音的特征差異判斷出有多個(gè)報(bào)文同時(shí)到達(dá)并造成了沖突。正如當(dāng)多人同時(shí)講話時(shí)，可能聽不清楚任何一個(gè)人說(shuō)的內(nèi)容，但能夠斷定有多人在講話。如果PLC的物理層能夠?qū)_突信號(hào)與背景噪音區(qū)分出來(lái)，則一個(gè)節(jié)點(diǎn)IDsource就可以發(fā)送報(bào)文Q={IDsource，a，b}，然后利用載波偵聽判定其周圍節(jié)點(diǎn)的編號(hào)。在給定編號(hào)區(qū)間［a，b］內(nèi)的3種分布情況為：

（1）正確完整地偵聽到一個(gè)報(bào)文R={IDme，r}：說(shuō)明存在編號(hào)為IDme的節(jié)點(diǎn)，且是唯一的一個(gè)編號(hào)在a和b之間的節(jié)點(diǎn)。

（2）未能正確地偵聽到任何一個(gè)報(bào)文，并且線路只有背景噪音：說(shuō)明沒有節(jié)點(diǎn)其編號(hào)在a和b之間；

（3）未能正確地偵聽到任何一個(gè)報(bào)文，但是存在沖突信號(hào)：說(shuō)明存在多個(gè)節(jié)點(diǎn)，其編號(hào)在a和b之間。

然而，目前的PLC技術(shù)還不能提供區(qū)分沖突信號(hào)與背景噪音的能力，從而分辨不清情況（2）、（3）。目前的低成本技術(shù)僅能做到接收到報(bào)文或者接收不到報(bào)文。在未收到報(bào)文時(shí)，區(qū)分不出是情況（2）還是情況（3）。對(duì)于低成本的載波芯片，實(shí)現(xiàn)這一功能目前還是一項(xiàng)極具挑戰(zhàn)性的任務(wù)。在此，本文給出一個(gè)方法可繞過(guò)這一難題。該方法利用報(bào)文沖突實(shí)現(xiàn)這一功能，在收不到報(bào)文時(shí)，利用報(bào)文沖突進(jìn)一步區(qū)分出是的確沒有報(bào)文，還是由于多個(gè)節(jié)點(diǎn)同時(shí)發(fā)送報(bào)文造成了沖突。采用該方法需要付出額外的代價(jià)是：多一次報(bào)文應(yīng)答過(guò)程；源節(jié)點(diǎn)需要事先知道一個(gè)確實(shí)存在的節(jié)點(diǎn)IDknown;需要定義一種新型的報(bào)文S={IDsource，IDknown，a，b}。

S型報(bào)文比Q型報(bào)文多了一個(gè)已知節(jié)點(diǎn)的編號(hào)IDknown，該報(bào)文的功能是令編號(hào)為IDknown的節(jié)點(diǎn)或編號(hào)處于a、b之間的節(jié)點(diǎn)收到該S報(bào)文后立即回應(yīng)R型報(bào)文，報(bào)出自己的編號(hào)和屬性。區(qū)分上述3種情況的算法如下：

算法1 WhoIn（a，b）：

算法說(shuō)明：該算法的輸入是兩個(gè)非負(fù)整數(shù) a、b，使得［a，b］形成節(jié)點(diǎn)ID區(qū)間； 設(shè)運(yùn)行該算法的節(jié)點(diǎn)的ID為IDsource，節(jié)點(diǎn)IDsource已知其一個(gè)鄰居節(jié)點(diǎn)IDknown，算法要求IDknown不屬于區(qū)間［a，b］;該算法判定節(jié)點(diǎn)IDsource有一個(gè)、還是沒有、還是有多個(gè)鄰居其ID屬于區(qū)間［a，b］;對(duì)應(yīng)這三種情況，算法分別報(bào)告唯一鄰居的ID、或者ZERO、或者M(jìn)ANY.

send out a packet Q={IDsource，a，b}

wait for a packet R

if a packet R={IDme，r} arrived

then return IDme //*IDme is the unique neighbor

in［a，b］*/

else if a=b

then return ZERO

else send out a packet S={IDsource，IDknown，a，b}

wait for a packet R

if a packet R={IDme，r} arrived

then return ZERO //*Dme must be IDknown

and whose packet has not been

collided*//

else if no packet received

then return MANY //*IDme must have been interfered with some neighbors

in［a，b］*//

end if

end if

顯然，該算法最壞情況下也能在4次報(bào)文跳轉(zhuǎn)的時(shí)間內(nèi)作出正確判斷。

2.2 搜索編號(hào)最小的鄰居節(jié)點(diǎn)

使用普通的二分搜索技術(shù)，節(jié)點(diǎn)IDsource在表號(hào)區(qū)間［a，b］上重復(fù)地調(diào)用算法WhoIn，可以快速地搜索出編號(hào)最小的鄰居節(jié)點(diǎn)（若存在）。算法可遞歸描述如下：

算法2 MinID（a，b）：

算法說(shuō)明：該算法的輸入及要求同算法WhoIn（a，b）；如果區(qū)間［a，b］有鄰居節(jié)點(diǎn)，算法返回其中最小的ID，否則返回ZERO.

let result=WhoIn（a，b）

if result is a valid ID or result=ZERO

then return result

let result=MinID（a，［（a+b）/2］）

if result is a valid ID

then return result

else return MinID（［（a+b）/2］，b）

該算法log（b-a）次調(diào)用算法WhoIn，其總的時(shí)間復(fù)雜度不大于4log（b-a）次報(bào)文跳。

2.3 搜索全部鄰居節(jié)點(diǎn)編號(hào)

有了MinID算法，節(jié)點(diǎn)IDsource通過(guò)在表號(hào)區(qū)間［a，b］重復(fù)地搜索最小的未知表號(hào)，直至獲得ZERO值。算法如下：

算法3 IDsIn（a，b）：

result=MinID（a，b）

while result≠ZERO do

report result

result=MinID（result+1，b）

end while

該算法最多每4log（b-a）跳時(shí)間搜索到一個(gè)節(jié)點(diǎn)。若節(jié)點(diǎn)IDsource在區(qū)間［a，b］上有n個(gè)鄰居節(jié)點(diǎn)，節(jié)點(diǎn)IDsource在4nlog（b-a）跳時(shí)間內(nèi)可完成捕獲這n只電能表的任務(wù)。

2.4 集中器捕獲全部電能表節(jié)點(diǎn)

假設(shè)一個(gè)臺(tái)區(qū)內(nèi)存在n個(gè)電能表節(jié)點(diǎn)，由集中器節(jié)點(diǎn)直接運(yùn)行算法IDsIn（0，248），可在 4nlog（248-0）≤192n跳時(shí)間內(nèi)搜索到全部一跳（直抄）電能表節(jié)點(diǎn)。然后由集中器通知一跳表，二跳表，……運(yùn)行同一算法，并將發(fā)現(xiàn)的節(jié)點(diǎn)編號(hào)上報(bào)集中器，于是集中器可以繼續(xù)搜索到二跳表，三跳表，……全部過(guò)程進(jìn)行完最多用192n2跳時(shí)間。

為了簡(jiǎn)單易讀，上述的2.1~2.4節(jié)中只是在思路層敘述算法設(shè)計(jì)，忽略了很多重要的實(shí)現(xiàn)細(xì)節(jié)。

時(shí)間界192n2在2.4節(jié)中估計(jì)得很粗略。將一些精細(xì)的實(shí)現(xiàn)細(xì)節(jié)納入考慮后，該時(shí)間界可下降。例如在任何節(jié)點(diǎn)執(zhí)行該算法時(shí)，如果其他節(jié)點(diǎn)記錄偵聽到的節(jié)點(diǎn)，則時(shí)間可降至192n跳。

在青島東軟公司的一個(gè)實(shí)驗(yàn)臺(tái)區(qū)運(yùn)行本文所述算法，捕獲全部的620只電能表需要1.5 h.算法實(shí)現(xiàn)細(xì)節(jié)上可以進(jìn)一步優(yōu)化，使捕獲效率更高。