基于无线传感器网络的K均值算法研究

石红丽， 王 洁 ， 唐 艳， 张小军

（1.成都理工大学 信息科学与技术学院，四川 成都 610059；2.长庆油田超低渗透油藏第一项目部 甘肃 庆阳 745400）

无线传感网是计算机技术应用的一个崭新研究领域，它综合了传感器技术、嵌入式计算技术、分布式信息处理技术、现代网络及无线通信等技术。通过各类微型传感器对目标信息进行实时监测，由嵌入式计算资源对信息进行处理，能够协作地实时监测、感知和采集各种环境信息。在军事国防、工农业控制、城市管理、生物医疗、环境监测、抢险救灾、防恐反恐和危险远程控制等许多领域都有重要的科研和实用价值。目前，对无线传感器网络的研究主要集中在网络层和链路层，而路由算法已成为无线传感器网络的核心技术之一。根据网络中各个节点的地位和功能是否相同，路由算法可以分成平面路由算法和分簇路由算法。K均值算法是一种比较成熟的基于聚类的算法，选择K均值算法作为探讨的对象具有较好的意义和研究前景。

1 传感器网络结构

传感器网络[1]结构如图1所示，通常包括传感器节点（sensor node）、汇聚节点（sink node）和管理节点。大量传感器节点随机部署在监测区域 （sensor field）并通过自组织方式构成网络。传感器节点监测的数据经过多跳后路由到汇聚节点[2]，最后通过互联网或卫星到达管理节点。用户通过管理节点对传感器网络进行配置和管理，发布监测任务以及收集监测数据。传感器节点能量有限，处理能力、存储能力和通信能力相对较弱。它们主要是进行本地信息收集和数据处理外，并且对转发来的数据进行处理。

由于无线传感器网络自身的特点，要求其路由协议必须能够满足相应的应用要求、可以实现较低的网络消耗、整体有效地利用资源以及拥有较高的网络吞吐量，这就要求无线传感器网络的路由不能像传统的网络一样，因此，它具有传统网络所不具备的一些特点：1）具有应用相关性；2）均衡性低耗能；3）以数据为中心。

由此可见能耗问题是无线传感器网络的关键问题之一。层次路由协议已经被证明能够有效地节约能量，它将网络中的所有节点划分为簇头节点和一般节点两类。 一般节点负责数据的采集，并将采集到得数据发送给簇头节点。簇头节点接收簇内一般节点发来的数据，融合后再转发给汇聚节点，这种算法称为分簇算法。具有代表性的分簇算法有LEACH[3]、PEGAGIS、HEED等。在不改变硬件的前提下，通过深入分析这些代表性的算法存在的不足，提出了一种基于聚类的K均值算法。

2 K均值算法原理

2.1 K均值算法的前提

K均值算法[4-5]基于如下前提：

1）无线传感器网络中的每个节点的位置已定；

2）每个节点包括簇头节点是静止的；

3）每个节点的通信半径可调，并可以与簇头节点直接通信；4）整个网络的簇头个数是固定的。

2.2 算法的具体思想

K均值[6]是一种迭代的聚类算法，迭代过程中不断地移动簇集中的成员，直到得到理想的簇集为主，在这里理想的簇集标准为具有低能耗、高稳定性[7-8]。

K均值伪代码：

2.3 K的确定方式

K的确定方式如下：

I为网络的节点个数，εfs为自由空间衰减信道模式（d2功耗）放大指数，εmp为多路径衰减信道模式（d4功耗）放大指数，dtoBs为簇头节点到汇聚节点的距离，J为正方形区域边长。

利用无线电通信模型[9-10]用ETx/ERx分别表示节点发送/接收信息消耗的能量，则节点经过距离d发送k比特数据消耗的能量为：

节点接收k比特数据消耗的能能量为：

无线电通信模型如图2所示。

3 仿真实验

100个节点m分布在100×100的矩阵区域中，各样本节点位于（0，100）处，整个网络被分为5个区域，即为5个分簇。 初始能量 Einit=1 J ， Eelec=25 nJ/bit，εmp=5 pJ/bit/m2，数据融合所消耗的能量EDA=25 pJ/bit/singnal，每次内部节点要发送的数据大小为1 000 bit.

样本点的坐标：

100个节点分布情况如图3所示。100个节点分布情况聚类后的情况如图4所示。

分成五类后的簇头节点坐标：

C=[45 53；46 5；49 82；73 70；18 89]

将以上数据通过NS-2仿真平台仿真，发现K均值算法第一个节点的死亡时间 （FND）和全部节点死亡的时间（LND）都比LEACH[3]算法的时间长。统计50次实验后的结果为:K均值算法的FND平均是LEACH的115倍，LND平均是LEACH的117倍。这说明本文的算法将能量的损耗均匀分布到了所有节点中，避免了单个节点过早死亡，提高了网络的生命周期。

4 结束语

本文提出了一种基于无线传感器网络的K均值算法，它生成的簇头节点散播到了网络的各个区域中，从而减少了每个区域内通信的能耗和可能会出现的节点稀疏没有簇头节点而导致一般节点直接与汇聚节点通信导致过早死亡的情况，从而避免了网络对该区域提早失去监控。本算法对各节点位置确定的无线传感器网络有低能耗、高稳定性。由于现阶段还处于模拟仿真阶段，还不能将已有算法写入平台中达到自适应的阶段。

[1]杨冕，秦前清.基于无线传感器网络的路由协议[J].计算机工程与应用， 2004（32）:130-131.YANG Mian，QINQian-qing.Routingprotocolbasedonwireless sensor network[J].Computer Engineering and Applications，2004（32）:130-131.

[2]Dunham M H.数据挖掘教程[M].北京:清华大学出版社，2005:95-131.

[3]唐漪.无线传感器网络LEACH算法的研究与改进[D].兰州:兰州理工大学，2008.

[4]陈良维.数据挖掘中聚类算法研究[J].微计算机信息，2006，2（1）:209-211.CHEN Liang-wei.Clustering algorithm study in data mining[J].Journal of Micro Computer Information，2006，2（1）:209-211.

[5]杨小兵.聚类分析中若干关键技术的研究[D].杭州:浙江大学计算机学院，2005.

[6]Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy efficient communication protocol for wireless microsensor networks [C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences， 2000（2）：10.

[7]Lindsey S，Raghavendra C S.PEGASIS:power efficient gathering in sensor information systems[C]//Proceedings of IEEE Aerospace Conference，2002（3）:1125-1130.

[8]徐义峰，陈春明，徐云青.一种改进的k均值聚类算法[J].计算机应用与软件，2008，25（3）:275-277.XU Yi-feng， CHEN Chun-ming， XU Yun-qing.An improved clustering algorithm for K-means[J].Computer Applications and Software， 2008， 25（3）:275-277.

[9]顾洪博，张继怀.基于孤立点和初始质心选择的K-均值算法改进[J].长江大学学报：自然科学版，2009，6（1）:60-62.GU Hong-bo，ZHANG Ji-huai.Animproved K-means algorithm based on outliers and original clustering center[J].Journal of Yangtze University：Natural Science， 2009，6（1）:60-62.

[10]徐艺萍.动态聚类法研究[D].重庆:西南大学，2006.