古奋飞，王涛春

(1.安徽新华学院； 2.安徽师范大学)

基于K-means聚类的安全高效的数据聚集算法*

古奋飞1，王涛春2

(1.安徽新华学院； 2.安徽师范大学)

无线传感器网络(Wireless Sensor Networks，简称WSNs)是一种多跳、自组织式的网络，传感器节点在能量、通信能力以及计算能力等方面均受限，并且在数据传输过程中也存在安全隐患，基于此提出了一种基于K-means聚类的安全高效的数据聚集算法KSEDA(K-means Safe and Efficient Data Aggregation).该算法采用K-means聚类算法对传感器节点进行分簇，通过分析节点的剩余能量进行选择簇头节点；并在向汇聚节点Sink传递过程中通过安全多方计算协议进行数据安全聚集.通过与CPDA算法进行实验对比，算法具有低能耗、高安全性等特点.

无线传感器网络；聚类；数据聚集；安全高效

0 引言

随着物联网技术的不断发展和应用的不断推广，其中无线传感器网络(Wireless Sensor Networks，简称WSNs)是整个物联网的核心部分，而终端设备可以称为边缘部分.WSNs是一种多跳、自组织的网络，目前研究的典型是以两层传感器网络[1]作为研究基础，即包括传感器节点、聚集节点.传感器节点是一些能耗、通信、计算能力等均受限的节点，而聚集节点则是在能耗、通信、计算能力均优于普通传感器节点.在通信过程中，传感器节点主要承担者数据采集的作用，然后将采集到的数据聚集到Sink汇聚节点进行存储.在此过程中个，每个节点都将各自的数据层层上传，因此数据冗余严重、每个节点能耗损失较多以及要保证数据隐私.因此为了减少冗余、提高整个网络生命周期，提出一种基于聚类的安全高效的数据聚集算法KSEDA.

1 相关研究

随着物联网的不断发展，WSNs目前在智能交通、医疗健康、智慧城市、环境监测等[2]领域有广泛应用，但由于传感器节点受能耗、计算能力以及通信能力的制约，因此降低能耗、减少通信量是研究热点问题.文章主要采取K-means聚类算法对传感器节点数据进行分簇以减少数据冗余，并利用多方安全计算协议提高数据的隐私保护.

1.1 数据聚集

数据聚集是利用自身的有限资源以及计算通信能力，对传感器节点收集到的数据进行处理，减少冗余数据，减少节点数据传输量，同时在不影响数据准确性的情况下传递给汇聚节点.文献[4]是采用了LEACH协议对传感器节点进行分簇，但是该算法在簇头的选取时，能量消耗较大.文献[5]提出的CPDA算法，是基于分簇的一种隐私保护算法，但计算量较大，并且隐私保护比较单一.

1.2 CPDA算法

CPDA算法分为三个阶段：簇的建立，簇内数据聚集，簇间数据聚集.在监测区域内，节点会根据所处的地理位置互相结合随机形成很多个簇，簇内所有的成员节点将采集的数据进行相关的多项式运算得到簇内的聚集结果.CPDA算法在簇内数据聚集过程中，每个节点将数据分成若干组，其中的部分分组传给邻居节点；邻居节点在收到传递过来的数据将其进行聚集再传递给簇头节点实现簇内数据聚集；每一个簇头节点再传递给基站进行簇间数据聚集.CPDA算法的信息传递过程如图1所示，A是簇头节点，B、C是普通节点，该过程表示A和B、C之间进行数据信息交换.

图1 数据信息交换图

(1)

节点A的干扰数据经过加密的传递过程后，节点A和B、节点A和C均存在一个共享密钥.

同理，节点B和C也采用同样的方法，形成相应节点之间的密钥对.

最后，对A节点进行数据融合可以得到：

(2)

通过对CPDA算法的分析，改算法虽做到数据聚集，但在簇的建立，簇内数据聚集，簇间数据聚集的过程增加计算量，增大了传输开销等，因此对传感器网络具有很多不利.

2 KSEDA算法

针对CPDA算法的不足，该文提出了基于K-means分簇的隐私保护算法KSEDA.该算法在分簇建立、簇头的选取在能耗上均有所降低，并且利用了安全多方计算协议加强了数据的隐私保护，大大提高了安全性，并节约了能耗.

2.1 准备知识

(1)K-means聚类算法

K-means算法一种非监督聚类划分算法.该算法的基本思想是: 将有N个节点组成的空间模型，确定k个分类，每个分类具有一个初始化的中心节点，通过距离计算将离该中心最近的节点划分到该类中.然后通过迭代的方法，不断更新各聚类中心的值，直至相邻的2次的聚类中心没有变化为止.假设要把数据分为k个类别，算法的实现基本步骤如下:

①选择k个类别的初始聚类中心.

②在每一次的迭代中，求任意一个节点到各初始聚类中心的距离，将该节点归类到与之相距最短的中心所在的类.

③重新计算每个类的中心值，观察有无变化.

④重复执行②,③两个步骤，观察每个聚类的中心值是否变化，若保持不变，则停止更新，否则继续更新.

在K-means聚类算法中，聚类中心k个数的选择对聚类结果影响很大，聚类结果会随着k的改变而改变，不合适的k会影响聚类质量，或使算法陷入局部最优.如果k偏小，会造成硬性划分，影响聚类质量; 如果k偏大，则需要上传的数据量增大，增加了簇头节点的能源消耗.所以选择一个合适的k至关重要.

(2)安全多方计算协议

(3)

利用公式(1)和n个数据可得到公式(2)，从而求出n个数据和，具体如下：

(4)

其中，循环乘法群G1⊂p2，其序为p(p-1)，p为一个素数.

2.2 KSEDA算法思想

通过前面的分析，KSEDA算法可以分以下三个步骤实现，描述如下：

(1)的建立

为获取一个合理的区域簇，该文采用的是K-means聚类算法来确定这个区域簇.首先在监测区域内选取核心节点，作为k类分簇的初始中心节点也即为初始簇首节点.然后通过广播的方式将簇头节点信息发送到各个节点上，直到所有的节点都接收到这些消息，然后通过K-means来划分区域簇，根据上述描述的K-means算法步骤，最后对分簇后的类别进行迭代，直至中心值不变，即形成最终分簇.

(2)簇首的选择

在WSNs分簇中，簇首节点一般选择能量损耗较少的节点.按照这种需求，文章通过如下公式来计算能耗.

(7)

Ecosti表示节点i作为簇首所消耗的能量；Etotal指簇内所有节点充当簇首时所消耗的能量总和；Di表示节点i到该簇中心的距离；Dtotal表示簇中所有节点到该簇中心的距离之和；a，b∈[0，1]，a，b分别表示能量消耗与距离所占的权重；SELECT(i)是表示能量和距离的目标函数，SELECT(i)越小，簇首节点能量消耗就越低.

首先簇内每个节点都置空，簇内所有节点相互传递信息，形成邻居表.然后计算每个节点作为簇首节点完成一次数据传输所需要的能量Ecost.则Ecost的表示为：

Ecost=2×(Eelec×k×εamp×k×d2)+N×Eelec×k

(8)

聚类分簇与CPDA协议中分簇的区别：在CPDA协议中，网络中自行选择簇的个数，网络中传感器节点的能量负荷平均分担[8]；而在聚类分簇中，区域内的节点是先规定划簇的个数再划分区域簇，然后在簇内选择能量消耗的比较少的节点来作为簇头.

(3)安全多方计算协议实现隐私保护

Step1：让n个参与者构成一个树形结构，如图2所示，即参与者均有其父节点，父节点为Si，左孩子节点为Sil，右孩子节点为Sir.其中A为根节点即汇聚Sink节点.

Step2：每个参与者Si通过伪随机生成函数生成一个随机数ri，其中左孩子节点计算gril，右孩子节点计算gril，并将gril，gril传输给父节点，同理，根节点下的每一个分支均按照此方法进行数据的传递.

Step3：每个父节点收到子节点Si传递过来的数据并对数据进行加密，即Ci=(1+xi*p)*Rimodp2，其中Ri=(gril/grir)ri，并最终将Ci传输给根节点A.

Step4：根节点A接收了所有Ci后，计算得到n个参与方的数据之和，如下：

(5)

所以：

(6)

图2 数据传输示意图

2.3 算法性能分析

(1)安全性

(2)通信能耗

3 实验及分析

实验的硬件环境为Core i3 CPU，4G内存,软件环境为Win7 OS，VS.NET 2013和Matlab,数据参量采用英特尔伯克利实验室的传感器网络数据中 20 个节点的温度数据.实验是求执行50轮的平均值，分别对KSEDA 和CPDA算法进行对比，其能耗与安全性结论如下.

(1)能耗的影响

图3显示KSEDA 和CPDA算法在通信能耗方面的对比，由图3可知，KSEDA算法的通信能耗比CPDA算法通信能耗低得多.主要原因是KSEDA算法在首先选簇的个数时，已经过实验选取，其k值为4是最佳聚类个数.

图3 能量对比图

(2)安全性影响

图4是反映了KSEDA 和CPDA算法在安全性方面的对比，CPDA算法是通过将上传的数据进行切片，一旦被捕获，很容易得到真实数据；而KSEDA中含有大量的伪装数据，这样就算数据被捕获，也很难在短时间内进行破解，这样能利用时间差来挽回损失.

图4 安全性对比图

4 结束语

该文提出的KSEDA算法利用K-means算法对节点进行分簇，并且利用多方安全计算协议实现数据隐私保护问题.通过实验仿真，在节点的能耗和安全性方面KSEDA算法均优于CPDA算法.但整个算法是是基于K值最佳的情况下，同时构建了树形结构的传感器网络，并利用多方安全计算协议实现数据隐私保护.通过实验表明算法KSEDA具有一定的安全高效性.

[1] Mohamed A F, Fahim K, Mathieu B, et al. The Internet of Things: The Next Technological Revolution[J]. IEEE Computer, 2013, 46(2):24-25.

[2] Mark H. The Internet of Things and Commerce. ACM Crossroads, 2011, 17(3):19-22.

[3] He W, Liu X, Nguyen H V, et al. PDA: Privacy-Preserving Data Aggregation for Information Collection[J]. ACM Transactions on Sensor Networks, 2011, 8(1):6.

[4] Zhu L, Yang Z, Li M, et al. . An efficient data aggregation protocol concentrated on data integrity in wireless sensor networks[J]. International Journal of Distributed Sensor Networks , 2013(7): 718 - 720.

[5] Girao J, Westhoff D, Schneider M. CDA: Concealed data aggregation for reverse multicast traffic in wireless sensor networks. Proceedings of the International Conference on Communications[J]. Seoul, Korea, 2005: 3044-3049.

[6] 范永健, 陈红, 张晓莹. 无线传感器网络数据隐私保护技术[J]. 计算机学报. 2012. 35(6):1131-1144.

[7] Wan R Z, Zhang X Y. A Privacy-Preserving Intra-Cluster Data Aggregation Method in Wireless Sensor Networks[J]. Applied Mechanics & Materials, 2015, 719-720:773-778.

[8] He W, Liu X, Nguyen H, et al. A Cluster-Based Protocol to Enforce Integrity and Preserve Privacy in Data Aggregation[J]. 2009:14-19.

[9] He W, Liu X, Nguyen H, et al. SPDA: A Secure and Privacy-preserving Data Aggregation in Wireless Sensor Networks[C]// INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE. IEEE, 2007.2045 - 2053.

[10] He W, Liu X, Nguyen H V, et al. PDA: Privacy-Preserving Data Aggregation for Information Collection[J]. Acm Transactions on Sensor Networks, 2011, 8(1):108-108.

(责任编辑：季春阳)

A Secure and Efficient Data Aggregation Algorithm Based on K-means Clustering

Gu Fenfei1, Wang Taochun2

(1.Anhui Xinhua University; 2.Anhui Normal University)

Wireless sensor network (Wireless Sensor Network, referred to as WSN) is a multi hop, self-organizing type network, which sensor node energy, communication ability and computational capability are limited, and security risks still exist in the process of data transmission. Based on these, a fusion algorithm of KSEDA K-means clustering is put forward which is algorithm safe and efficient based on the data presented (K-means Safe and Efficient Data Aggregation). The K-means clustering algorithm is used for clustering of sensor nodes, the cluster head node is selected by analyzing the node residual energy; and through the integration of secure multi-party protocols data security are improved in transmission to the sink node in the process. Compared with the CPDA algorithm, the algorithm has the characteristics of low energy consumption, high security and so on.

Wireless Sensor Network; Clustering; Data Aggregation; Safe and efficient

2016-12-22

*国家自然科学基金(61402014);省级重点研究项目(kj2016A303);校级自然科学研究项目(2015zr008);校级质量工程项目(2015sysxs01)

TP393

A

1000-5617(2016)05-0020-05