基于K-Means算法改进的NTP及其在用电信息采集系统中的应用

张明艳，查晓锐

(1.国网马鞍山供电公司，安徽马鞍山243000；2.南京国电南自电网自动化有限公司，江苏南京211100)

用电信息采集系统是指在电力系统连续运行过程中，通过不间断地采集现场终端各类设备信息并将信息上送主站，达到监控和管理现场终端用电的目的。用电信息采集系统是一个多层的主从模型，每一层设备均是下一层设备的时钟基准源，集中器在系统中承担着链接主站和电能表的作用，其自身的时钟精度尤为重要[1]。采集主站通过通用分组无线服务(general packet radio service，GPRS)通信链路，采用NTP对集中器进行对时，主要的时钟偏差来自于GPRS通信延时。文献[2]利用最大似然估计的方法计算多组测量的网络延时δ和时钟偏差θ，将得到的多组时钟偏差均值作为时钟偏差的最优估计值。文献[3]采用双NTP专用服务器，形成冗余系统，并采用P/S模式的同步算法计算时钟偏差θ，利用锁相环进行本地时钟对时，但该方法使用冗余服务器配置，增加了设备成本。为解决用电信息采集系统中主站对集中器的对时精度问题，笔者在不增加任何成本的前提下，基于K-Means算法，设计一种改进的NTP方案，并将其应用于用电信息采集系统中的主站和集中器对时，以期提高时钟偏差的计算精度，满足用电信息采集系统对对时方案精度的要求。

1 NTP

1.1 NTP的原理

NTP 指采用国际标准时间(coordinated universal time，UTC)使同一网络中的设备时钟同步，其可提供高精准度的时间校准。理论上NTP 可达到1～50 ms 的对时精度，且可通过加密的方式来阻挡网络攻击[4]。典型的NTP对时模型如图1。

图中：t1为client发送同步请求报文时的本地时间；t2为server 收到同步请求时的本地时间；t3为server 回送时间同步信息时的本地时间；t4为client接收到同步信息时的本地时间；δ1为请求报文在路径上的传输时间；δ2为回复报文在路径上的传输时间。令θ 为client和server的时钟偏差值，则由图1可得：

图1 NTP对时过程Fig.1 Timing process of NTP

其中δ 为总的传输延时时间。理想情况下，往返报文的路径一致，即δ1=δ2，可得

根据式(2)可得到client 与server 的时钟偏差值，利用得到的时钟偏差值补偿client 时钟时间，即可使client和server的时钟同步。

1.2 NTP在用电信息采集系统中的应用

用电信息采集系统中，集中器的GPRS模块接收主站的GPRS信号，通过NTP完成同步对时。集中器完成对时后通过RS485、电力载波通信等方式与智能电能表建立通信，并从电能表中提取电压、电流、用电量等数据；之后，集中器一般按照采集时间对数据进行存储梳理，等待主站上召数据或者主动上送给主站[5]。由此可知，集中器时钟准确是实现主站到智能电能表各层设备时钟同步的前提，也是用电信息采集系统正常工作的关键所在。

在用电信息采集系统中，一般采用单一时钟源分层对时的方案，主站和集中器的时钟同步采用NTP，通过集中器多次向主站发送对时报文计算出通信延时和时钟偏差，从而实现时钟同步[6]。NTP一般有3种工作模式：

1)广播模式 服务器以固定周期广播自己的时标，客户端用一定的过滤算法修正接收到的时标；

2)主从模式 客户端向一个或多个服务器发送对时请求，双方交换信息的时间戳，估算时间偏差和网络延时，采用过滤算法从中计算出最优的时间偏差；

3)对称模式 服务器之间交换信息的时间戳，使整个网络时间保持一致。

用电信息采集系统中的终端一般采用主从模式通过主站的对时服务器对集中器进行对时[7]。针对主从模式的NTP方案，在计算时钟偏差的过程中，将主站和集中器往返的通信延时视为对称，简化时钟偏差的计算难度，但实际情况下主站和集中器的往返通信延时是有差异的且存在测量误差。

2 基于改进K-Means算法的NTP集中器时钟同步方案

基于K-Means 算法，设计一种NTP 集中器时钟同步的改进方案。首先，根据n 次NTP 对时时标t1、t2、t3、t4求出n组时钟偏差θ,通过对时误差阈值滤波方法对时钟偏差值进行筛选，过滤畸变的数据，保留较优的样本数据；其次，利用改进的K-Means算法对滤波后的数据进行迭代计算；最后，根据计算出的时钟偏差值对集中器时间进行补偿从而完成主站和集中器的时钟同步。

2.1 对时误差阈值滤波

理论上，NTP 对时在多数情况下延时误差可精确到±1 ms 以内，但在实际使用中，延时误差值远大于1 ms，造成这一现象的主要原因是测量误差[8]。文献[9]根据NTP对时原理，基于多组对时报文，对延时计算公式进行变换，得出实际时钟偏差的限定范围，剔除畸变数据，优化样本数据。典型的NTP对时过程如图1，由图1可知：

其中θt为实际时钟偏差。式(3)可等效变换为：

δ1和δ2分别为请求信息和回复信息在路径上的传输时间，实际值不小于0。由此，结合式(1)～(2)可得：

由式(5)可知

将实际时钟偏差θt和理想情况下时钟偏差θ 的差值定义为时钟偏差的对时误差。由式(6)可知，在实际NTP对时过程中，时钟偏差值的对时误差是有边界的，根据NTP对时过程中的4个时标t1、t2、t3、t4可确定对应对时过程实际时钟偏差的有效范围。

在实际NTP对时过程中，1次对时选定的时间服务器有代表性，其有效性在较长时间内都有效，无需在每次对时重新对新的数据进行处理[10]。由此，利用1次NTP对时得出限定范围，在多次NTP对时过程中进行对时样本点的优化选择，将时钟偏差不在限定范围内的对时样本点剔除，可将延时严重不对称或测量误差较大的畸变数据滤除。

2.2 K-Means算法的改进

K-Means算法在原始数据集中随机选K个数据作为初始聚类中心，计算剩余数据到初始聚类中心的欧式距离，将剩余的数据归类至其距离最小聚类中心所在的类当中，根据各类中的数据对象计算他们的平均值，以此作为新的聚类中心，继续聚类，直至相邻的两次聚类中心不再变化，则准则函数收敛，输出最终的聚类中心[11]。

K-Means算法中，收敛效果依赖于合适的聚类个数和初始聚类中心，且可能收敛到局部最优解[12]。鉴于此，采用逐一划分的方式优化初始聚类中心对K-Means算法进行改进，避免聚类过程陷入局部最优解。令原始数据集N={ x1,x2,x3,…,xn-2,xn-1,xn} ，N 中每个对象均含有p 个属性，第i 个数据对象xi={xi1,xi2,xi3,…,xip} ，从N中随机选择K个对象作为初始聚类中心，聚类步骤如下：

1)建立原始数据集N；

2)建立K个空类簇，从N中随机选择多个对象，将选择的对象随机分配到建立的K个空类簇；

3)选择数据对象最多的一个类簇，记为M；

4)计算M中两两数据对象之间的欧式距离，找出距离最大的两个数据对象Mi和Mj，并填充到创建的空类簇中；

5)以Mi和Mj为聚类中心，分别计算M中剩余数据对象到Mi和Mj的欧式距离，将他们分别划分至离其距离最小的类中；

6)检查是否将数据集N划分为K个类簇，若是则结束，以得到的K个聚类中心进行常规的K-Means算法聚类，否则跳至步骤3)。

改进的K-Means算法流程如图2。

2.3 改进的NTP集中器时钟同步机制

改进的NTP集中器时钟同步方案为：基于NTP原理，根据用电信息采集系统集中器时钟的同步设置，启动对时流程；集中器向主站请求时间，主站回应请求并向集中器答复时间，重复此同步过程若干次；依据若干次请求的各个时标计算每次对应的总延时时间和时钟偏差；根据对时误差阈值滤波方法，对若干组计算出的总延时时间和时钟偏差进行筛选，剔除因测量或延时严重不对称导致误差较大的样本点；对保留的样本点利用改进K-Means算法进行时钟偏差聚类，直到准则函数收敛，输出最终的时钟偏差；将计算出的时钟偏差值补偿到集中器的时钟，完成对集中器的对时。改进的NTP集中器时钟同步流程如图3。

图2 改进的K-Means算法流程Fig.2 Flow of improved K-means algorithm

图3 改进的NTP集中器对时流程Fig.3 Timing process of collector based on improved NTP

3 实验验证

表1 改进的NTP方案时钟偏差实际值Tab.1 Actual clock deviation values by using the improved NTP

由表1知，采用对时误差阈值滤波和改进的K-Means算法对用电信息采集系统中的集中器和主站进行同步，同步后的时钟偏差平均误差为-88.1 ms，满足国家电网公司企业标准中集中器对时误差在±5 s的精度要求。

4 结 论

为提高用电信息采集系统中主站对集中器的对时精度，基于K-Means算法，提出一种改进的NTP方案，即采用对时误差阈值滤波算法，对若干次NTP对时过程中由于各种因素导致的畸变数据进行过滤；采用改进的K-Means算法对保留的对时数据进行聚类迭代，输出准则函数收敛对应的时钟偏差值；将输出的时钟偏差值补偿到集中器时间上，即可完成主站对集中器的对时同步。根据某供电公司提供的主站和集中器对时数据，采用改进的NTP方案对集中器进行对时同步，对时后的集中器时钟精度满足实际现场要求，可为用电信息采集系统的稳定可靠运行提供了重要保障。