算法說(shuō)明：該算法的輸入是兩個(gè)非負整數 a、b，使得[a，b]形成節點(diǎn)ID區間; 設運行該算法的節點(diǎn)的ID為IDsource，節點(diǎn)IDsource已知其一個(gè)鄰居節點(diǎn)IDknown，算法要求IDknown不屬于區間[a，b]；該算法判定節點(diǎn)IDsource有一個(gè)、還是沒(méi)有、還是有多個(gè)鄰居其ID屬于區間[a，b]；對應這三種情況，算法分別報告唯一鄰居的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次報文跳轉的時(shí)間內作出正確判斷。 2.2 搜索編號最小的鄰居節點(diǎn) 使用普通的二分搜索技術(shù)，節點(diǎn)IDsource在表號區間[a，b]上重復地調用算法WhoIn，可以快速地搜索出編號最小的鄰居節點(diǎn)(若存在)。算法可遞歸描述如下： 算法2 MinID(a，b)： 算法說(shuō)明：該算法的輸入及要求同算法WhoIn(a，b)；如果區間[a，b]有鄰居節點(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)次調用算法WhoIn，其總的時(shí)間復雜度不大于4log(b－a)次報文跳。 2.3 搜索全部鄰居節點(diǎn)編號 有了MinID算法，節點(diǎn)IDsource通過(guò)在表號區間[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)跳時(shí)間搜索到一個(gè)節點(diǎn)。若節點(diǎn)IDsource在區間[a，b]上有n個(gè)鄰居節點(diǎn)，節點(diǎn)IDsource在4nlog(b－a)跳時(shí)間內可完成捕獲這n只電能表的任務(wù)。 2.4 集中器捕獲全部電能表節點(diǎn) 假設一個(gè)臺區內存在n個(gè)電能表節點(diǎn)，由集中器節點(diǎn)直接運行算法IDsIn(0，248)，可在 4nlog(248－0)≤192n跳時(shí)間內搜索到全部一跳(直抄)電能表節點(diǎn)。然后由集中器通知一跳表，二跳表，……。運行同一算法，并將發(fā)現的節點(diǎn)編號上報集中器，于是集中器可以繼續搜索到二跳表，三跳表，……。全部過(guò)程進(jìn)行完最多用192n2跳時(shí)間。 為了簡(jiǎn)單易讀，上述的2.1～2.4節中只是在思路層敘述算法設計，忽略了很多重要的實(shí)現細節。 時(shí)間界192n2在2.4節中估計得很粗略。將一些精細的實(shí)現細節納入考慮后，該時(shí)間界可下降。例如在任何節點(diǎn)執行該算法時(shí)，如果其他節點(diǎn)記錄偵聽(tīng)到的節點(diǎn)，則時(shí)間可降至192n跳。 在青島東軟公司的一個(gè)實(shí)驗臺區運行本文所述算法，捕獲全部的620只電能表需要1.5 h。算法實(shí)現細節上可以進(jìn)一步優(yōu)化，使捕獲效率更高。 參考文獻 [1] Q/GDW 376.1-2009電力用戶(hù)用電信息采集系統通信協(xié)議，第一部分：主站與采集終端通信協(xié)議. [2] Q/GDW 376.2-2009電力用戶(hù)用電信息采集系統通信協(xié)議，第二部分：集中器本地通信模塊接口協(xié)議. [3] DL/T645-2007，多功能電能表通信協(xié)議. [4] DL/T645-1997，多功能電能表通信規約.
加入技術(shù)交流群
評論