算法说明：该算法的输入是两个非负整数 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，多功能电能表通信规约.
上一页 [1] [2]
