電力線通信自動抄表系統(tǒng)中的電能表捕獲算法
加入技術(shù)交流群
算法說明：該算法的輸入是兩個非負(fù)整數(shù) a、b，使得[a，b]形成節(jié)點(diǎn)ID區(qū)間; 設(shè)運(yùn)行該算法的節(jié)點(diǎn)的ID為IDsource，節(jié)點(diǎn)IDsource已知其一個鄰居節(jié)點(diǎn)IDknown，算法要求IDknown不屬于區(qū)間[a，b]；該算法判定節(jié)點(diǎn)IDsource有一個、還是沒有、還是有多個鄰居其ID屬于區(qū)間[a，b]；對應(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 搜索編號最小的鄰居節(jié)點(diǎn)
使用普通的二分搜索技術(shù)，節(jié)點(diǎn)IDsource在表號區(qū)間[a，b]上重復(fù)地調(diào)用算法WhoIn，可以快速地搜索出編號最小的鄰居節(jié)點(diǎn)(若存在)。算法可遞歸描述如下：
算法2 MinID(a，b)：
算法說明：該算法的輸入及要求同算法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)編號
有了MinID算法，節(jié)點(diǎn)IDsource通過在表號區(qū)間[a，b]重復(fù)地搜索最小的未知表號，直至獲得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í)間搜索到一個節(jié)點(diǎn)。若節(jié)點(diǎn)IDsource在區(qū)間[a，b]上有n個鄰居節(jié)點(diǎn)，節(jié)點(diǎn)IDsource在4nlog(b－a)跳時(shí)間內(nèi)可完成捕獲這n只電能表的任務(wù)。
2.4 集中器捕獲全部電能表節(jié)點(diǎn)
假設(shè)一個臺區(qū)內(nèi)存在n個電能表節(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)編號上報(bào)集中器，于是集中器可以繼續(xù)搜索到二跳表，三跳表，……。全部過程進(jìn)行完最多用192n2跳時(shí)間。
為了簡單易讀，上述的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跳。
在青島東軟公司的一個實(shí)驗(yàn)臺區(qū)運(yùn)行本文所述算法，捕獲全部的620只電能表需要1.5 h。算法實(shí)現(xiàn)細(xì)節(jié)上可以進(jìn)一步優(yōu)化，使捕獲效率更高。
參考文獻(xiàn)
[1] Q/GDW 376.1-2009電力用戶用電信息采集系統(tǒng)通信協(xié)議，第一部分：主站與采集終端通信協(xié)議.
[2] Q/GDW 376.2-2009電力用戶用電信息采集系統(tǒng)通信協(xié)議，第二部分：集中器本地通信模塊接口協(xié)議.
[3] DL/T645-2007，多功能電能表通信協(xié)議.
[4] DL/T645-1997，多功能電能表通信規(guī)約. 電能表相關(guān)文章:電能表原理
評論