电力线通信自动抄表系统中的电能表捕获算法

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，多功能电能表通信规约.