電力線通信自動抄表系統中的電能表捕獲算法
加入技術交流群
算法說明：該算法的輸入是兩個非負整數 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。算法實現細節上可以進一步優化，使捕獲效率更高。
參考文獻
[1] Q/GDW 376.1-2009電力用戶用電信息采集系統通信協議，第一部分：主站與采集終端通信協議.
[2] Q/GDW 376.2-2009電力用戶用電信息采集系統通信協議，第二部分：集中器本地通信模塊接口協議.
[3] DL/T645-2007，多功能電能表通信協議.
[4] DL/T645-1997，多功能電能表通信規約. 電能表相關文章:電能表原理
評論