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

1 典型的PLCAMR體系

典型的PLCAMR體系由三級系統構成：主站、集中器和電能表終端。主站負責管理全局的集中器與電能表信息，可通過光纖、GPRS、公話網或其他方式與集中器通信；集中器一般每個配電臺區安裝一個，管理所在臺區的全部電能表，其日常工作是通過電力線通信采集各電能表數據；電能表負責計量用電戶的各類用電量。

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

解決上述問題的本質在于系統能夠從零知識開始工作。所謂零知識是指初始時主站只知道有哪些配電臺區和集中器，但是并不清楚哪些電能表屬于哪個臺區的集中器；集中器僅知道自己的編號（ID），但不知道有哪些，有多少電能表隸屬自己；電能表僅知道自己的編號（還有自己的計量項目），但不知管轄自己的集中器是誰。但目前國家電網關于自動抄表的通信協議都是主從結構的，電能表作為通信節點只有被動應答的能力，不能主動發起通信任務［1-4］。為了適應主從體系結構，本文設計了專門的電能表捕獲算法。該算法的優點在于不需要額外的空間資源，線性時間，倘若臺區內有n個電能表，算法可在O（n）次報文跳轉時間內完成搜索任務。

2 表號捕獲算法

假設電能表編號的區間為［a，b］（實際應用中a=0，b=1012，或者說是6 B的BCD碼）。表號捕獲算法的核心思想比較簡單，有2點：

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

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

以下分4個子節描述基于上述思想的表號捕獲算法。為了簡明本文略去實現細節。在以后的敘述中，集中器和電能表統稱為節點。

2.1 判定給定區間的鄰居分布情況

首先定義一種查詢報文Q={IDsource，a，b}。其中IDsource為報文源節點（發出者）的編號，IDmin≤a≤b≤IDmax.報文Q向編號在區間［a，b］內的節點發出查詢請求，凡是編號在此區間的節點（即編號IDme滿足a≤IDme≤b的節點）收到該報文后立即回應一個報文R={IDme，r}，報出自己的編號IDme和自己的屬性r.

定義了以上2種報文，節點IDsource判定給定區間［a，b］的鄰居情況的方法是依靠區別沖突信號與背景噪音的能力。這種能力是指當有多個節點同時發送報文時，接收節點雖然由于報文沖突不能正確地收到任何一個報文，但不會和無報文（線路上只有背景噪音）混為一談，接收者能夠根據沖突信號與背景噪音的特征差異判斷出有多個報文同時到達并造成了沖突。正如當多人同時講話時，可能聽不清楚任何一個人說的內容，但能夠斷定有多人在講話。如果PLC的物理層能夠將沖突信號與背景噪音區分出來，則一個節點IDsource就可以發送報文Q={IDsource，a，b}，然后利用載波偵聽判定其周圍節點的編號。在給定編號區間［a，b］內的3種分布情況為：

（1）正確完整地偵聽到一個報文R={IDme，r}：說明存在編號為IDme的節點，且是唯一的一個編號在a和b之間的節點。

（2）未能正確地偵聽到任何一個報文，并且線路只有背景噪音：說明沒有節點其編號在a和b之間；

（3）未能正確地偵聽到任何一個報文，但是存在沖突信號：說明存在多個節點，其編號在a和b之間。

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

S型報文比Q型報文多了一個已知節點的編號IDknown，該報文的功能是令編號為IDknown的節點或編號處于a、b之間的節點收到該S報文后立即回應R型報文，報出自己的編號和屬性。區分上述3種情況的算法如下：

算法1 WhoIn（a，b）：

算法說明：該算法的輸入是兩個非負整數 a、b，使得［a，b］形成節點ID區間； 設運行該算法的節點的ID為IDsource，節點IDsource已知其一個鄰居節點IDknown，算法要求IDknown不屬于區間［a，b］;該算法判定節點IDsource有一個、還是沒有、還是有多個鄰居其ID屬于區間［a，b］;對應這三種情況，算法分別報告唯一鄰居的ID、或者ZERO、或者MANY.

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次報文跳轉的時間內作出正確判斷。

2.2 搜索編號最小的鄰居節點

使用普通的二分搜索技術，節點IDsource在表號區間［a，b］上重復地調用算法WhoIn，可以快速地搜索出編號最小的鄰居節點（若存在）。算法可遞歸描述如下：

算法2 MinID（a，b）：

算法說明：該算法的輸入及要求同算法WhoIn（a，b）；如果區間［a，b］有鄰居節點，算法返回其中最小的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）次調用算法WhoIn，其總的時間復雜度不大于4log（b-a）次報文跳。

2.3 搜索全部鄰居節點編號

有了MinID算法，節點IDsource通過在表號區間［a，b］重復地搜索最小的未知表號，直至獲得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）跳時間搜索到一個節點。若節點IDsource在區間［a，b］上有n個鄰居節點，節點IDsource在4nlog（b-a）跳時間內可完成捕獲這n只電能表的任務。

2.4 集中器捕獲全部電能表節點

假設一個臺區內存在n個電能表節點，由集中器節點直接運行算法IDsIn（0，248），可在 4nlog（248-0）≤192n跳時間內搜索到全部一跳（直抄）電能表節點。然后由集中器通知一跳表，二跳表，……運行同一算法，并將發現的節點編號上報集中器，于是集中器可以繼續搜索到二跳表，三跳表，……全部過程進行完最多用192n2跳時間。

為了簡單易讀，上述的2.1~2.4節中只是在思路層敘述算法設計，忽略了很多重要的實現細節。

時間界192n2在2.4節中估計得很粗略。將一些精細的實現細節納入考慮后，該時間界可下降。例如在任何節點執行該算法時，如果其他節點記錄偵聽到的節點，則時間可降至192n跳。

在青島東軟公司的一個實驗臺區運行本文所述算法，捕獲全部的620只電能表需要1.5 h.算法實現細節上可以進一步優化，使捕獲效率更高。