D0I:10.13374/i.issnl001t03.2009.0L.025 第31卷第1期 北京科技大学学报 Vol.31 No.1 2009年1月 Journal of University of Science and Technology Beijing Jan.2009 基于邻域势函数的无线传感器网络模糊分簇算法 杨斌阳建宏徐金梧 杨德斌 北京科技大学机械工程学院，北京100083 摘要为解决冶金工业中网络拓扑稳定情况下的分簇问题，提出了一种基于节点邻域势函数的无线传感器网络模糊分簇 算法·该算法将邻居节点的势函数信息作为模糊C均值隶属度矩阵的权值，用于网络分簇，提高了网络的负载均衡指数，确保 分簇更加均衡.仿真实验表明，与LEACH相比，该算法使网络生命周期提高了93.6%，大幅延长了网络生命周期. 关键词无线传感器网络：分簇；邻域势函数：模糊C均值：负载均衡 分类号TP393 Weighted fuzzy clustering strategy for wireless sensor networks based on the neighbor potential function YANG Bin,YA NG Jian-hong,XU Jin-wu,YANG De-bin Mechanical Engineering School.University of Science and Technology Beijing.Beijing 100083.China ABSTRACT A weighted fuzzy clustering algorithm based on the neighbor potential function for wireless sensor networks is proposed to solve clustering problems in the case of network topology stability in the metallurgical industry.The potential function of neighbor nodes is used to optimize the network clustering.which enhances the load balance factor and ensures cluster heads being well scat- tered.Simulation experiments illustrate that compared with LEACH,the proposed algorithm is able to significantly prolong the net- works lifetime by 93.6%. KEY WORDS wireless sensor networks:clustering:potential function:fuzzy C-mean:load balance 作为一种新的信息获取和处理技术，无线传感 法是指由基站基于整个网络信息挑选簇头，如 器网络(wireless sensor network,WSN),已在军事、 LEACH-C LEACH-centralized )[5]LEACH-F 环境科学、医疗健康、空间探索及其他商业领域得到 (LEACH-fixed)[5]HYENAS (hybrid energy-aware 广泛应用，无线传感器网络中的层次型拓扑结构由 sensor network)[6]FCMC (fuzzy cluster mean 于具有通信量少、可扩展性强、能量利用效率高及适 clustering)☑等. 合大规模部署等特点，成为当前拓扑控制研究的重 现有的很多分簇算法都存在分簇数目和簇间重 点. 叠过多、分簇效率低的问题，而且大多是先选举出簇 近几年，国内外研究工作者对无线传感器网络 头，然后通过簇头组织簇，由于每个工作周期中簇 的分簇算法进行了大量研究，根据簇头产生方式的 内节点都会发生变化，簇头和簇内成员必须通讯来 不同，可以把分簇算法分为分布式和集中式两种. 了解簇内情况，消耗的能量较大·但在很多实际应 分布式算法包括两类：一类是由节点根据某个阈值 用中（例如工业设备状态监测，节点的位置相对稳 自主决定是否当选簇头，如LEACH(low-energy 定，网络中几乎没有大范围移动的节点)，节点的位 adaptive clustering hierarchy)];另一类是通过节点 置通常由需要监测的设备位置来决定，本文针对这 之间的信息交互动态产生簇头，如HEED(hybrid 类应用，利用节点的位置信息，将邻居节点的势函数 energy efficient distributed clustering)l.集中式算 信息作用到模糊C均值算法中，构造新的隶属度矩 收稿日期：2008-02-04 基金项目：国家高技术研究发展计划资助项目(N。.2007AA04z169):国家自然科学基金资助项目(N。-50674010) 作者简介：杨斌(1979一)，男，博士研究生，E-mail:jpuyang007@gmail.com:徐金梧(1949一)，男，教授，博士生导师
基于邻域势函数的无线传感器网络模糊分簇算法 杨 斌 阳建宏 徐金梧 杨德斌 北京科技大学机械工程学院北京100083 摘 要 为解决冶金工业中网络拓扑稳定情况下的分簇问题提出了一种基于节点邻域势函数的无线传感器网络模糊分簇 算法．该算法将邻居节点的势函数信息作为模糊 C 均值隶属度矩阵的权值用于网络分簇提高了网络的负载均衡指数确保 分簇更加均衡．仿真实验表明与 LEACH 相比该算法使网络生命周期提高了93∙6％大幅延长了网络生命周期． 关键词 无线传感器网络；分簇；邻域势函数；模糊 C 均值；负载均衡 分类号 TP393 Weighted fuzzy clustering strategy for wireless sensor networks based on the neighbor potential function Y A NG BinY A NG Jian-hongXU Jin-w uY A NG De-bin Mechanical Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China ABSTRACT A weighted fuzzy clustering algorithm based on the neighbor potential function for wireless sensor networks is proposed to solve clustering problems in the case of network topology stability in the metallurgical industry．T he potential function of neighbor nodes is used to optimize the network clusteringwhich enhances the load balance factor and ensures cluster heads being well scattered．Simulation experiments illustrate that compared with LEACHthe proposed algorithm is able to significantly prolong the networks lifetime by 93∙6％． KEY WORDS wireless sensor networks；clustering；potential function；fuzzy C-mean；load balance 收稿日期：2008-02-04 基金项目：国家高技术研究发展计划资助项目（No．2007AA04Z169）；国家自然科学基金资助项目（No．50674010） 作者简介：杨 斌（1979—）男博士研究生E-mail：jpuyang007＠gmail．com；徐金梧（1949—）男教授博士生导师 作为一种新的信息获取和处理技术无线传感 器网络（wireless sensor networkWSN）已在军事、 环境科学、医疗健康、空间探索及其他商业领域得到 广泛应用．无线传感器网络中的层次型拓扑结构由 于具有通信量少、可扩展性强、能量利用效率高及适 合大规模部署等特点成为当前拓扑控制研究的重 点［1—2］． 近几年国内外研究工作者对无线传感器网络 的分簇算法进行了大量研究．根据簇头产生方式的 不同可以把分簇算法分为分布式和集中式两种． 分布式算法包括两类：一类是由节点根据某个阈值 自主决定是否当选簇头如 LEACH （low-energy adaptive clustering hierarchy） ［3］；另一类是通过节点 之间的信息交互动态产生簇头如 HEED （hybrid energy-efficient distributed clustering） ［4］．集中式算 法是指由基站基于整个网络信息挑选簇头如 LEACH-C （ LEACH-centralized ） ［5］ 和 LEACH-F （LEACH-fixed） ［5］、HYENAS （hybrid energy-aware sensor network ） ［6］ 和 FCMC （fuzzy cluster mean clustering） ［7］等． 现有的很多分簇算法都存在分簇数目和簇间重 叠过多、分簇效率低的问题而且大多是先选举出簇 头然后通过簇头组织簇．由于每个工作周期中簇 内节点都会发生变化簇头和簇内成员必须通讯来 了解簇内情况消耗的能量较大．但在很多实际应 用中（例如工业设备状态监测节点的位置相对稳 定网络中几乎没有大范围移动的节点）节点的位 置通常由需要监测的设备位置来决定．本文针对这 类应用利用节点的位置信息将邻居节点的势函数 信息作用到模糊 C 均值算法中构造新的隶属度矩 第31卷 第1期 2009年 1月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．31No．1 Jan．2009 DOI:10．13374／j．issn1001－053x．2009．01．025
第1期 杨斌等：基于邻域势函数的无线传感器网络模糊分簇算法 ,119 阵，提高网络的负载平衡指数，优化网络分簇，然后 中，节点的布置往往受限于监测位置，很容易获取节 在簇内根据节点的剩余能量或者ID号轮流选举簇 点的坐标.因此可以利用模糊C均值算法(fzzy 头，从而提高了整个网络的生命周期 C-mean,FCM)对网络进行分簇.1973年，Bezdek[9)] 1约束条件及相关模型 提出了FCM算法，其思想是使得被划分到同一簇 的对象之间相似度最大，而不同簇之间的相似度最 本文所描述的算法遵循以下约束条件]：()工 小 业无线传感器网络节点位置相对固定，网络拓扑在 设x={x1,x2,…,xN}∈RP,令表示第k 组网后相对稳定，移动性小；(2)网络节点组织成簇 个样本属于第i类的隶属度，以表示每个给定数据 结构的形式，簇头执行数据的融合功能，并负责将集 点属于各个组的程度，隶属矩阵U中每个元素 中后的数据传输到汇聚节点，簇内节点之间不发生 的取值范围为[0,1]，并且一个数据集的隶属度的和 通信：（③）每个传感器节点在每一轮数据采集过程中 总等于1，在实验过程中，RP为二维空间p=2,x= 所产生的数据量是相同的：(4)节点的射频芯片具有 {x1,x2}表示节点的坐标，u表征节点i划分到簇k 发射功率调节功能；(5)不失一般性，为了简化仿真 的程度，其中FCM的价值函数（或目标函数）： 工作量，假设所有节点的通信范围都不超过1跳 网络拓扑结构模型如图1所示.能耗模型采用 ua)=空4=2 u脉d(3) 无线通信能耗模型].实验采用自由空间(d功率 其中，c为网络分簇个数，：表示每个簇的聚类中 损失)和多径衰落(d功率损失)两种通道模型，使 心，du=‖v:一x‖为第i个聚类中心与第k个数 用何种模型取决于发送节点和接收节点之间的距 据点间的欧几里德距离，m是一个加权指数，通常 离，如果发送节点和接收节点之间的距离小于阈值 可选取m为2.聚类准则为求J(U,C)的极小值. do,则使用自由空间模型：否则使用多径衰落模型， 2.2基于邻域势函数的加权模糊C均值分簇算法 本算法首先获取节点的坐标值，使用传统的模 糊C均值算法进行分簇，然后考查网络的负载均衡 指数。如果网络中指数低于阈值，则使用如下方法 ●传感器节点 进行调整：节点首先调整发射功率使得通讯距离为 ●熊头节点 r,找到自己的邻居节点，将邻居节点的势函数信息 作为隶属度矩阵的权重，迭代求取新的隶属度矩阵， 对网络分簇进行优化， 网络的负载平衡指数(load balancing factor, 图1网络拓扑结构 LBF)定义为簇覆盖节点的平均程度，其计算公 Fig-1 Topological Structure of network 式为： no 当传送数据量为k,传输距离为d时，消耗的能 LBF (4) u)2 量为： Etx(k,d)=Etx_elck Etx_amp(k,d) 其中，u= N二亚是簇内节点的平均数，V是网络中 ne Ex-elek十kesd2 ddo 节点总数，c是网络中簇头的数量，xi是簇内成员 (I) Ex-eek十kEmp dd≥do 节点数，LBF值越大说明网络的负载均衡性越好. 为了接收该数据，消耗的能量为： 网络中节点的模糊隶属度为”，周围邻居节点 Erx(k)=Erx_elec k (2) 对其作用关系为P,其中卫指的是xk属于第i类 的权重系数，则改进后的模糊隶属度表达式为： 其中，Ex-ele=En-eke=Eelee u=u"pk,1≤k≤n,1≤≤c,然后求出新的隶 2基于节点邻域势函数的加权模糊C均值 属度，则改进后FCM算法的目标函数为： 分簇算法 minJm(U,V)= 2空(t)同 2.1模糊C均值算法 将改进的FCM算法用拉格朗日乘法求解，并 工业无线传感器网络应用于设备状态监测过程 对其中参数求导可得到模糊隶属度和聚类中心的迭
阵提高网络的负载平衡指数优化网络分簇然后 在簇内根据节点的剩余能量或者 ID 号轮流选举簇 头从而提高了整个网络的生命周期． 1 约束条件及相关模型 本文所描述的算法遵循以下约束条件［3］：（1）工 业无线传感器网络节点位置相对固定网络拓扑在 组网后相对稳定移动性小；（2）网络节点组织成簇 结构的形式簇头执行数据的融合功能并负责将集 中后的数据传输到汇聚节点簇内节点之间不发生 通信；（3）每个传感器节点在每一轮数据采集过程中 所产生的数据量是相同的；（4）节点的射频芯片具有 发射功率调节功能；（5）不失一般性为了简化仿真 工作量假设所有节点的通信范围都不超过1跳． 网络拓扑结构模型如图1所示．能耗模型采用 无线通信能耗模型［8］．实验采用自由空间（ d 2 功率 损失）和多径衰落（ d 4 功率损失）两种通道模型使 用何种模型取决于发送节点和接收节点之间的距 离．如果发送节点和接收节点之间的距离小于阈值 d0则使用自由空间模型；否则使用多径衰落模型． 图1 网络拓扑结构 Fig．1 Topological Structure of network 当传送数据量为 k传输距离为 d 时消耗的能 量为： Etx（ kd）＝ Etx— elec k＋ Etx— amp（ kd）＝ Etx— elec k＋kεfs d 2 d＜ d0 Etx— elec k＋kεmp d 4 d≥ d0 （1） 为了接收该数据消耗的能量为： Erx（ k）＝ Erx— elec k （2） 其中Etx— elec＝ Erx— elec＝ Eelec． 2 基于节点邻域势函数的加权模糊 C 均值 分簇算法 2∙1 模糊 C 均值算法 工业无线传感器网络应用于设备状态监测过程 中节点的布置往往受限于监测位置很容易获取节 点的坐标．因此可以利用模糊 C 均值算法（fuzzy C-meanFCM）对网络进行分簇．1973年Bezdek ［9］ 提出了 FCM 算法其思想是使得被划分到同一簇 的对象之间相似度最大而不同簇之间的相似度最 小． 设 x＝｛x1x2…x N｝∈R p令 uik表示第 k 个样本属于第 i 类的隶属度以表示每个给定数据 点属于各个组的程度．隶属矩阵 U 中每个元素 uik 的取值范围为［01］并且一个数据集的隶属度的和 总等于1．在实验过程中R p 为二维空间 p＝2x＝ ｛x1x2｝表示节点的坐标uik表征节点 i 划分到簇 k 的程度．其中 FCM 的价值函数（或目标函数）： J（ Uc1…cc）＝ ∑ c i＝1 Ji＝ ∑ c i＝1 ∑ n k＝1 u m ikd 2 ik （3） 其中c 为网络分簇个数vi 表示每个簇的聚类中 心dik＝‖vi— xk‖为第 i 个聚类中心与第 k 个数 据点间的欧几里德距离m 是一个加权指数通常 可选取 m 为2．聚类准则为求 J（ UC）的极小值． 2∙2 基于邻域势函数的加权模糊 C 均值分簇算法 本算法首先获取节点的坐标值使用传统的模 糊 C 均值算法进行分簇然后考查网络的负载均衡 指数．如果网络中指数低于阈值则使用如下方法 进行调整：节点首先调整发射功率使得通讯距离为 r找到自己的邻居节点将邻居节点的势函数信息 作为隶属度矩阵的权重迭代求取新的隶属度矩阵 对网络分簇进行优化． 网络的负载平衡指数（load balancing factor LBF） ［10］定义为簇覆盖节点的平均程度其计算公 式为： LBF＝ nc ∑i （ xi － u） 2 （4） 其中u＝ N— nc nc 是簇内节点的平均数N 是网络中 节点总数nc 是网络中簇头的数量xi 是簇内成员 节点数．LBF 值越大说明网络的负载均衡性越好． 网络中节点的模糊隶属度为 uik周围邻居节点 对其作用关系为 pik其中 pik指的是 xk 属于第 i 类 的权重系数则改进后的模糊隶属度表达式为： u ∗ ik＝ uik·pik1≤k≤ n1≤ i≤c．然后求出新的隶 属度则改进后 FCM 算法的目标函数为： min J ∗ m （ UV）＝ ∑ n k＝1∑ c i＝1 （ u ∗ ik） m d 2（ xkvi） （5） 将改进的 FCM 算法用拉格朗日乘法求解并 对其中参数求导可得到模糊隶属度和聚类中心的迭 第1期 杨 斌等： 基于邻域势函数的无线传感器网络模糊分簇算法 ·119·
,120 北京科技大学学报 第31卷 代函数为： 算法流程如图2. u(8)= 22a1≤区c,1≤k≤n, 卫谈 获取节点的位置信息 FCM对节点进行初始分簇，同时 获取隶属度矩阵和聚类中心 (uio)4 计算负载均衡指数LBF v(6+1)=三 ,1≤≤c (6) (u在)m LBF<圆值或者达到选代次数 k=1 其中，b是迭代次数，c是分类个数，n是节点个数 Y 根据式(6)计算新的隶属度矩阵和聚类中心 该算法的关键是如何确定权重系数卫k,其系数 将最终决定网络中分簇优化的效果，当P=1时上 根据隶属度最大原则，输出分簇结构 述算法就是标准的FCM算法，本文提出了一种基 根据剩余能量和D号选举簇头 于邻居节点势函数信息的策略来确定Pk,其步骤如 下.节点调整通讯距离为r,求出网络的连通度矩 图2算法流程图 阵，获取邻居节点信息；然后根据原始的势函数模 Fig-2 Flowchart of the algorithm 型山，同时考虑节点与邻居节点之间的势函数关 系，构造权重系数的函数表达式为： 3 仿真实验及讨论 ∑1/1+‖x-x3) 为了验证本文提出算法的性能，通过仿真实验 E N P 将本文提出的算法与LEACH及FCMC[门算法进行 1/(1+‖xn-‖3) 比较.实验模型由200个节点组成，它们随机均匀 E∈N N为x邻居节点的集合，N指的是xk邻居 分布在(x=0,y=0)至(x=200,y=200)的正方 形区域内，能耗模型采用First Order Radio模型，其 节点中属于第i类的集合，为了简化计算，也可把 他设定的参数包括：覆盖区域面积200m×200m,节 式(7)简化为节点与聚类中心的距离：来代替： ∑1/1+‖x,-:3) 点的初始能量E为0.5J,基站位置(0,0)，每次发 送数据包大小2000bit.节点发送和接收1bit数据 IE ∑1/1+I.-,I3 (8) 所消耗的能量Ex=4.23×10-7J和E.=1.39× IE 10-72,数据融合能耗EDA为5 nJ.bit1·sig 算法详细步骤如下： nal-1. (a)获取节点的坐标值，使用原始的FCM算法 在仿真实验中，本文的分簇算法PWFCMC及 对网络中节点进行初始分簇，并根据公式(3)，求得 FCMC算法将网络划分为10个簇，LEACH算法中 隶属度矩阵和聚类中心； 的簇头在所有节点中所占的比例为0.05，节点调整 (b)根据初始的隶属度和聚类中心结果，计算 后的通讯距离为20m, 网络的负载均衡指数，如果负载均衡指数低于规定 本文使用如下两个指标来评估算法的性能 的阈值则从步骤(c)开始进行调整，否则转到(e): 负载平衡指数：由于每轮中簇覆盖节点的平均 (c)节点调整发射功率，使通讯距离为r,获取 程度也会影响网络的生存时间，簇中包含节点数目 节点的邻域节点信息，根据邻居节点的隶属度计算 的不平衡会导致不同簇之间数据的容量不同，因此 出N后，根据式(7)或(8)求出P; 簇的负载平衡程度是分层算法中衡量簇性能的重要 (d)根据式(6)计算出新的隶属度矩阵和聚类 标准之一· 中心，转到(b): 网络生命周期：在不考虑其他外界可能破坏因 (ε)根据隶属度矩阵，利用最大隶属度原则，输 素的前提下，当节点的能量小于相应的阈值时，认为 出网络最终的分簇结果； 节点死亡，网络中出现第一个死亡节点的时间作为 ()分簇完成后，在各个簇内挑选簇内剩余能 网络的生命周期 量最多的节点作为这一轮数据发送的簇头，如果多 图3~图5分别表示了LEACH算法、FCMC算 个节点的剩余能量相同，则选择节点ID号最小的 法及PWFCMC的分簇情况， 作为簇头· 从图3~图5可以看出，PWFCMC相对
代函数为： u ∗（b） ik ＝ pik ∑ c j＝1 d （b） ik d （b） jk 2／m－1 1≤ i≤c1≤k≤ n v （b＋1） i ＝ ∑ n k＝1 （ u ∗（b） ik ） m xk ∑ n k＝1 （ u ∗（b） ik ） m 1≤ i≤c （6） 其中b 是迭代次数c 是分类个数n 是节点个数． 该算法的关键是如何确定权重系数 pik其系数 将最终决定网络中分簇优化的效果当 pik＝1时上 述算法就是标准的 FCM 算法．本文提出了一种基 于邻居节点势函数信息的策略来确定 pik其步骤如 下．节点调整通讯距离为 r求出网络的连通度矩 阵获取邻居节点信息；然后根据原始的势函数模 型［11］同时考虑节点与邻居节点之间的势函数关 系构造权重系数的函数表达式为： pik＝ ∑x∈ N i k 1／（1＋‖xn － xk‖2） x∑n∈ Nk 1／（1＋‖xn － xk‖2） （7） Nk 为 xk 邻居节点的集合N i k 指的是 xk 邻居 节点中属于第 i 类的集合．为了简化计算也可把 式（7）简化为节点与聚类中心的距离 vi 来代替： pik＝ ∑x∈ N i k 1／（1＋‖xn － vi‖2） x∑n∈ Nk 1／（1＋‖xn － vi‖2） （8） 算法详细步骤如下： （a） 获取节点的坐标值使用原始的 FCM 算法 对网络中节点进行初始分簇并根据公式（3）求得 隶属度矩阵和聚类中心； （b） 根据初始的隶属度和聚类中心结果计算 网络的负载均衡指数如果负载均衡指数低于规定 的阈值则从步骤（c）开始进行调整否则转到（e）． （c） 节点调整发射功率使通讯距离为 r获取 节点的邻域节点信息根据邻居节点的隶属度计算 出 N i k 后根据式（7）或（8）求出 pik； （d） 根据式（6）计算出新的隶属度矩阵和聚类 中心转到（b）； （e） 根据隶属度矩阵利用最大隶属度原则输 出网络最终的分簇结果； （f） 分簇完成后在各个簇内挑选簇内剩余能 量最多的节点作为这一轮数据发送的簇头如果多 个节点的剩余能量相同则选择节点 ID 号最小的 作为簇头． 算法流程如图2． 图2 算法流程图 Fig．2 Flowchart of the algorithm 3 仿真实验及讨论 为了验证本文提出算法的性能通过仿真实验 将本文提出的算法与 LEACH 及 FCMC ［7］算法进行 比较．实验模型由200个节点组成它们随机均匀 分布在（ x＝0y＝0）至（ x＝200y＝200）的正方 形区域内能耗模型采用First Order Radio 模型．其 他设定的参数包括：覆盖区域面积200m×200m节 点的初始能量 E 为0∙5J基站位置（00）每次发 送数据包大小2000bit．节点发送和接收1bit 数据 所消耗的能量 Etx＝4∙23×10—7 J 和 Erx＝1∙39× 10—7 J ［12］数据融合能耗 EDA 为5nJ·bit —1·signal —1． 在仿真实验中本文的分簇算法 PWFCMC 及 FCMC 算法将网络划分为10个簇LEACH 算法中 的簇头在所有节点中所占的比例为0∙05节点调整 后的通讯距离为20m． 本文使用如下两个指标来评估算法的性能． 负载平衡指数：由于每轮中簇覆盖节点的平均 程度也会影响网络的生存时间簇中包含节点数目 的不平衡会导致不同簇之间数据的容量不同因此 簇的负载平衡程度是分层算法中衡量簇性能的重要 标准之一． 网络生命周期：在不考虑其他外界可能破坏因 素的前提下当节点的能量小于相应的阈值时认为 节点死亡网络中出现第一个死亡节点的时间作为 网络的生命周期． 图3～图5分别表示了 LEACH 算法、FCMC 算 法及 PWFCMC 的分簇情况． 从 图 3～ 图 5 可 以 看 出PWFCMC 相 对 ·120· 北 京 科 技 大 学 学 报 第31卷
第1期 杨斌等：基于邻域势函数的无线传感器网络模糊分簇算法 121 200 不一样，这里采用10次平均的方法来求LEACH的 160 负载均衡指数，根据式(4)计算求得LBFLEACH= 120 0.015. 80 从实验结果可以看出，本文提出的算法相对 FCMC算法和LEACH算法，在负载均衡指数方面 100 20 有了较大幅度的提高 x/m 最后将本文的算法与LEACH算法及FCMC算 法在网络生命周期方面进行比较，实验结果如图6 图3 LEACH算法分簇情况 Fig-3 Clustering of LEACH algorithm 所示 从图6可以看出，在网络的生命周期方面，本文 200 提出的PWFCMC算法比LEACH算法提高了 160 93.6%,比FCMC算法提高了5.6%，有效地延长了 120 网络生命周期，其原因是：LEACH分簇的随机性将 会导致某些节点过快地耗尽电池能量；FCMC算法 没有对网络的负载均衡进行优化，导致某些簇不均 100 200 匀；本文提出的算法从分簇的合理性、网络的负载均 x/m 衡以及簇内节点的剩余能量三个方面进行优化，减 图4FCMC算法分簇情况 少了网络中节点的能量消耗， Fig.4 Clustering of FCMC algorithm 3001 PWFCMC 250 FCMC -LEACH 200 200 160 150 节点所属的 120 筷通过优化 100 后发生变化 50 40 150 300 450 网络生命周期数 40 80 120160 200 x/m 图6网络生命周期对比图 图5本文提出的PWFCMC算法的分簇情况 Fig-6 Comparison of the lifetime of network Fig-5 Clustering of PWFCMC algorithm 在实时性方面，由于本文的算法采用集中式的 分簇方法，中心服务器负责使用本算法对节点进行 LEACH及FCMC,在分簇上更加均衡，其原因是： 分簇运算，一次分簇后，簇内节点不再变化·网络的 在LEACH算法中簇头产生是随机的，每一轮中产 时延主要是每轮簇内交互信息了解节点的ID和剩 生的簇头数目不总是等于预先设定的值，而且簇头 余能量，从而选举出簇头，由于簇内节点数目通常 产生的随机性会导致簇内簇头的分布不均：FCMC 较少，所以本文算法具有较好的实时性 算法由于每个簇具有簇内距离均方差最小的特点， 使得分簇均匀性有了一定提高；本文提出的 4结论 PWFCMC算法利用了节点的邻域势函数信息，均 本文针对网络的节点位置相对固定，并且节点 衡了网络负载，使得每个簇的节点个数更趋于平均， 位置已知的情况下，提出了基于邻域势函数的加权 分簇更加合理， 模糊C均值分簇算法，算法具有以下优点：①算法 下面分别计算三种算法的负载均衡指数，以上 采用集中的方式分簇，分簇后网络中各簇所包含的 面的分簇情况为例，根据式(4)，求得FCMC算法的 节点不再变化，先形成簇，簇头的选择只在局部的簇 负载均衡指数为LBFFCMC=0.0342,本文提出算法 内进行，避免了大范围的消息交互带来的能量消耗； 的负载均衡指数为LBFPWFCMc=0.0485. ②算法将邻居节点的势函数信息作为FCM的隶属 本文的算法在分簇后，网络中的分簇情况不再 度加权指数，以负载均衡指数为标准优化网络中簇 变动，相比较而言，LEACH算法每次的分簇情况都 头节点的负载，平衡了网络中各簇的节点个数，确保
图3 LEACH 算法分簇情况 Fig．3 Clustering of LEACH algorithm 图4 FCMC 算法分簇情况 Fig．4 Clustering of FCMC algorithm 图5 本文提出的 PWFCMC 算法的分簇情况 Fig．5 Clustering of PWFCMC algorithm LEACH 及 FCMC在分簇上更加均衡．其原因是： 在 LEACH 算法中簇头产生是随机的每一轮中产 生的簇头数目不总是等于预先设定的值而且簇头 产生的随机性会导致簇内簇头的分布不均；FCMC 算法由于每个簇具有簇内距离均方差最小的特点 使得 分 簇 均 匀 性 有 了 一 定 提 高；本 文 提 出 的 PWFCMC 算法利用了节点的邻域势函数信息均 衡了网络负载使得每个簇的节点个数更趋于平均 分簇更加合理． 下面分别计算三种算法的负载均衡指数．以上 面的分簇情况为例根据式（4）求得 FCMC 算法的 负载均衡指数为 LBFFCMC＝0∙0342本文提出算法 的负载均衡指数为 LBFPWFCMC＝0∙0485． 本文的算法在分簇后网络中的分簇情况不再 变动．相比较而言LEACH 算法每次的分簇情况都 不一样这里采用10次平均的方法来求 LEACH 的 负载均衡指数根据式（4）计算求得 LBFLEACH ＝ 0∙015． 从实验结果可以看出本文提出的算法相对 FCMC 算法和 LEACH 算法在负载均衡指数方面 有了较大幅度的提高． 最后将本文的算法与 LEACH 算法及FCMC 算 法在网络生命周期方面进行比较实验结果如图6 所示． 从图6可以看出在网络的生命周期方面本文 提出 的 PWFCMC 算 法 比 LEACH 算 法 提 高 了 93∙6％比 FCMC 算法提高了5∙6％有效地延长了 网络生命周期．其原因是：LEACH 分簇的随机性将 会导致某些节点过快地耗尽电池能量；FCMC 算法 没有对网络的负载均衡进行优化导致某些簇不均 匀；本文提出的算法从分簇的合理性、网络的负载均 衡以及簇内节点的剩余能量三个方面进行优化减 少了网络中节点的能量消耗． 图6 网络生命周期对比图 Fig．6 Comparison of the lifetime of network 在实时性方面由于本文的算法采用集中式的 分簇方法中心服务器负责使用本算法对节点进行 分簇运算一次分簇后簇内节点不再变化．网络的 时延主要是每轮簇内交互信息了解节点的 ID 和剩 余能量从而选举出簇头．由于簇内节点数目通常 较少所以本文算法具有较好的实时性． 4 结论 本文针对网络的节点位置相对固定并且节点 位置已知的情况下提出了基于邻域势函数的加权 模糊 C 均值分簇算法．算法具有以下优点：①算法 采用集中的方式分簇分簇后网络中各簇所包含的 节点不再变化先形成簇簇头的选择只在局部的簇 内进行避免了大范围的消息交互带来的能量消耗； ②算法将邻居节点的势函数信息作为 FCM 的隶属 度加权指数以负载均衡指数为标准优化网络中簇 头节点的负载平衡了网络中各簇的节点个数确保 第1期 杨 斌等： 基于邻域势函数的无线传感器网络模糊分簇算法 ·121·
.122 北京科技大学学报 第31卷 簇头的均匀分布，提高算法的分簇性能，使得分簇更 [5]Heinzelman W.Application-Specific Protocol Architectures for 加合理；③在簇内的簇头选举过程中以节点的剩余 Wireless Networks Dissertation].Boston:Massachusetts Insti- 能量作为簇头选取的标准，提高了网络的生命周期 tute of Technology.2000 [6]Tillapart P.Thumthawatworn T,Pakdeepinit P,et al.Method 仿真实验表明，本文提出的算法在负载均衡性上比 for cluster heads selection in wireless sensor networks//Proceed- LEACH有了大幅度提高，网络的生命周期比 ings of the 2004 IEEE Aeraspace Conference.Chiang Mai:IEEE LEACH提高了93.6%，大幅提高了网络的生命周 Press,2004:3615 期 [7]Wei Z H.Hou X D.Zhou H.Research on clustering strategy for wireless sensor networks based on fuzy theory//Proceedings The 3rd International Conference on Mobile Ad-hoc and Sensor Net- 参考文献 works.Beijing,2007:596 [1]Akyildiz I F.Su W,Cayirci E.A survey on sensor networks. [8]Heinzelman W,Chandrakasan A,Balakrislman H.Energy effi- IEEE Commun Mag:2002:43(5):51 cient communication protocol for wireless microsensor networks [2]Ren F Y.Huang H N.Lin C.Wireless sensor networks.J Soft- The Proceedings of the Hawaii International Conference on Sys ware,2003:14(2):1148 tem Sciences.Maui,2000 (任丰原，黄海宁，林闯.无线传感器网络.软件学报，2003,14 [9]Bezdek J.Pattern Recognition with Fuzzy Objective Function (2):1148) Algorithms.New York:Plenum Press,1981 [3]Heingelman W.Chandrakasan A,Balakrishnan H.Energy-effi- [10]Chatterjee M,Das J.Turgut D.WCA:a weighted clustering cient communication protocol for wireless microsensor networks algorithm for mobile ad-hoe network.Clustering Comput, Proceedings of the 33rd Annual Hawaii International Confer- 2002,5(2):193 ence on System Sciences.Maui:IEEE Computer Society,2000: [11]TouJT.Pattern Recognition Principles.Massachusetts:Addi 3005 son-Wesley Company:1974 [4]Younis O,Fahmy S.Distributed clustering in ad-hoc sensor net- [12]He J.Liu L J,Wang Q.Behavior of energy consumption in wire- works:a hybrid.energy efficient approach Proceedings of the less sensor network devices.Comput Eng Sci,2007.34(9):41 23rd Annual Joint Conference of the IEEE Computer and Com- (何杰，刘兰军，王沁·无线传感器网络器件能耗行为研究 munications Societies (INFOCOM).2004:7 计算机科学，2007,34(9)：41)
簇头的均匀分布提高算法的分簇性能使得分簇更 加合理；③在簇内的簇头选举过程中以节点的剩余 能量作为簇头选取的标准提高了网络的生命周期． 仿真实验表明本文提出的算法在负载均衡性上比 LEACH 有 了 大 幅 度 提 高网 络 的 生 命 周 期 比 LEACH 提高了93∙6％大幅提高了网络的生命周 期． 参 考 文 献 ［1］ Akyildiz I FSu WCayirci E．A survey on sensor networks． IEEE Commun Mag2002：43（5）：51 ［2］ Ren F YHuang H NLin C．Wireless sensor networks．J Software2003：14（2）：1148 （任丰原黄海宁林闯．无线传感器网络．软件学报200314 （2）：1148） ［3］ Heinzelman WChandrakasan ABalakrishnan H．Energy-efficient communication protocol for wireless microsensor networks∥ Proceedings of the 33rd A nnual Hawaii International Conference on System Sciences．Maui：IEEE Computer Society2000： 3005 ［4］ Younis OFahmy S．Distributed clustering in ad-hoc sensor networks：a hybridenergy efficient approach∥ Proceedings of the 23rd A nnual Joint Conference of the IEEE Computer and Communications Societies （ INFOCOM）2004：7 ［5］ Heinzelman W． Application-Specific Protocol A rchitectures for Wireless Networks ［Dissertation ］．Boston：Massachusetts Institute of Technology2000 ［6］ Tillapart PThumthawatworn TPakdeepinit Pet al．Method for cluster heads selection in wireless sensor networks∥ Proceedings of the2004IEEE Aerospace Conference．Chiang Mai：IEEE Press2004：3615 ［7］ Wei Z HHou X DZhou H．Research on clustering strategy for wireless sensor networks based on fuzzy theory∥ Proceedings The 3rd International Conference on Mobile A d-hoc and Sensor Networks．Beijing2007：596 ［8］ Heinzelman WChandrakasan ABalakrislman H．Energy-efficient communication protocol for wireless microsensor networks∥ The Proceedings of the Hawaii International Conference on System Sciences．Maui2000 ［9］ Bezdek J．Pattern Recognition with Fuzz y Objective Function Algorithms．New York：Plenum Press1981 ［10］ Chatterjee MDas JTurgut D．WCA：a weighted clustering algorithm for mobile ad-hoc network． J Clustering Comput 20025（2）：193 ［11］ Tou J T．Pattern Recognition Principles．Massachusetts：Addison-Wesley Company1974 ［12］ He JLiu L JWang Q．Behavior of energy consumption in wireless sensor network devices．Comput Eng Sci200734（9）：41 （何杰刘兰军王沁．无线传感器网络器件能耗行为研究． 计算机科学200734（9）：41） ·122· 北 京 科 技 大 学 学 报 第31卷