无线传感网高斯分簇路由算法的研究及实现*

陈宁宁，俞 立，洪 榛，张贵军

(浙江工业大学计算机学院，杭州 310023)

无线传感器网络(Wireless Sensor Networks，WSNs)［1－4］是一种集传感器技术、计算机技术和无线通信技术的新型无线网络。它由部署在监测区域的大量的传感器节点组成，通过自组织的方式协同工作，以获取恶劣环境下的外部物理信息。由于传感器节点的能量有限并且部署之后难以再次补充，降低传感器节点的能量消耗成为延长网络生存周期的重要方法。而节点的能量消耗与网络的路由算法又息息相关，因此对无线传感器网络路由算法的研究具有非常重要的现实意义。

优化路由协议是均衡节点能量消耗的主要途径。针对无线传感器网络路由的特点，国内外的专家与学者提出了一些适合无线传感器网络的路由协议。这些路由协议的设计模式大致可以分为以下几类［5］:泛洪式路由协议、层次式路由协议、以数据为中心的路由协议、基于位置信息的路由协议和基于QoS的路由协议。在层次式路由协议中，簇头的选取应同时满足三个条件:簇头节点有足够的剩余能量来保证数据传递;簇头与簇内节点间距离在正常通信距离之内;簇头节点间距离不会太近。由于分簇路由具有拓扑结构简单、易于维护适合大规模网络等特点，一直是无线传感器网络路由研究的热点。

LEACH协议［6］作为最早提出分簇路由算法的协议，有效地降低了网络能耗，延长了网络生命。但LEACH协议在选取簇头时没有考虑目标节点的剩余能量的因素，也不能避免簇头节点因相距较近产生的重簇现象。HEED［7］、TEEN［8］和 PEGASIS［9］等分簇路由协议在LEACH协议的基础上进行了改进。HEED通过迭代的方式选取簇头，增大了簇头与基站通信的能量消耗;TEEN中的属性值若一直达不到软硬门限用户将接收不到网络的任何数据;PEGASIS协议在大规模网络中易增大网络数据传输时延，成簇开销非常大，不适合实际应用。由卢强等提出的CMCRP算法［10］将节点之间的距离作为簇头选取的参考因素，但目标节点当选簇头的概率随着与已知簇头距离的增大而增大，使得距离适合的能量较大的目标节点失去了竞争力。

针对以上情况，本文提出一种高斯分布分簇路由算法(GCRA)。在簇头选取过程中充分考虑目标簇头节点的剩余能量以及簇头之间的最优距离，保证簇头节点的均匀分布。节点根据通信代价最小的原则选取距离自己最近的簇头节点作为其最终簇头，均衡簇头节点的负载，延长网络的生存周期。

1 网络模型

在本文中，无线传感器网络节点具有如下性质:传感器节点随机地均匀分布在目标区域范围内，网络运行过程中均处于静止状态;传感器节点结构相同，所有传感器节点具有相同的功能和属性;传感器节点能够计算出自己当前的剩余能量，并具备数据融合功能;基站与每个传感器节点都可以直接通信，且基站位置固定，能量不受限。

参考LEACH协议的能量模型，节点的能量消耗由发射电路的能量消耗和功率放大器能量消耗两部分组成，即如果某一节点要发送kbits的数据包到距离为d的另一节点，则该节点所要消耗的能量模型为:

其中，Eelec表示发射和接收单位bit数据发射电路消耗的能量。当d＜do时，使用放大单位bit数据消耗能量为Efs的信号功率放大器，当d≥do时使用放大单位bit数据消耗能量为Emp的信号功率放大器。节点接收kbits数据的接收电路所消耗的能量模型为:

成员节点将监测数据发送到簇头，簇头节点对数据进行融合后发送到基站。数据融合单位bit数据消耗的能量为

其中Edf表示融合单位bit数据所消耗的能量。

2 簇头选择机制

2.1 网络最优化覆盖

在分簇路由协议中，簇头节点均匀分布具有以下优点:保证每个簇的大小尽量均等;平衡普通节点与簇头节点的能量消耗;降低网络的簇内通信代价。在成簇过程中，若簇头节点距离基站较远并且成员节点距离其所属簇头也较远，则节点与簇头均需消耗较大的能量以维持通信，大大增加整个网络的能量消耗。簇头节点均匀分布使得各个节点均可以较小的通信代价与簇头保持通信，均衡网络的能量消耗。因此，在成簇过程中将簇头的均匀分布作为簇头选取的重要衡量标准。

在网络覆盖过程中，簇头节点以“蜂窝”状的正六边形形式分布最优［11］，在这种网络模型下，网络的重复覆盖率最低并且无覆盖漏洞，以较少的簇头节点达到较高的网络覆盖率。如图1所示。

图1 网络最优覆盖

设网络中每个簇的半径为R，则簇头之间的最优距离应为R，即与已知簇头之间的距离为R的目标节点优先当选簇头。因此，优先选取距离已知簇头R圆上的节点当选簇头是这一模型得以实现的重要保证。

2.2 LEACH和CMCRP簇头选取机制

在LEACH协议簇头选取过程中，目标节点随机生成一个取值范围为0～1的小数，同时节点根据自身的阈值函数生成阈值Pi(t)，若随机数小于阈值，则该节点当选为簇头。Pi(t)的计算公式为:

其中，p表示簇头节点所占比例，r表示当前循环的轮数，n表示的是第n个节点，G表示最近1/p轮中仍未当选簇头的节点集合。LEACH协议有效降低了网络能耗，延长了网络生存周期，但仍存在一些缺陷:簇头节点的分布不能保证均匀;各个节点与基站的距离均不相等。从而在数据传输阶段能量消耗不能满足均等消耗。

CMCRP协议通过引入拟物力的思想把已产生的簇头节点看做是通信半径为R的“簇头圆盘”，设参与簇头选择并未被“簇头圆盘”覆盖的目标节点对其邻近的“簇头圆盘”具有吸引力，而已经被“簇头圆盘”覆盖的目标节点受“屏蔽效应”的影响对“簇头圆盘”不具有吸引力。参照万有引力引入“屏蔽效应”。改进后的簇头阈值为:

通过对簇头选择阈值的改进，CMCRP延长了网络生存周期。但节点距离已知簇头越远，当选簇头的概率越高，从而使得距离已知簇头较远的低能量节点当选簇头的概率高于距离已知簇头节点较近的高能量节点当选簇头的概率，使得高能量节点丧失了竞争力。

由以上分析可知，LEACH算法没有考虑节点的剩余能量因素，对其改进的CMCRP也没有保证簇头节点均匀分布。对于以上算法的缺陷和不足，本文提出一种高斯分簇路由算法。

3 高斯分簇路由算法(GCRA)

3.1 簇头距离因素

在高斯分簇路由算法的模型中，将簇头节点的均匀分布作为簇头选取的重要因素。

如图2所示，已知节点A已经被选为簇头节点，节点B、C、D、E、F和G均有可能成为下一个簇头节点。若簇头的基本通信范围为R，根据网络最优化覆盖原理，下一个簇头的最优位置应该在与簇头A的距离为R的圆上，即节点B所在的圆上。但在实际应用中，节点B可能由于剩余能量太低而不满足当选簇头的要求，或者在半径为R的圆上恰好没有节点，则与簇头节点A的距离在区间(R－ΔdR+Δd)上的节点C和D就成为次优目标簇头节点，从而在簇头节点A的周围形成了一条宽度为2Δd的圆环。在簇头选取过程中，处于圆环中的所有节点组成的概率带形成下一个簇头节点的最优目标区域。不在概率带上的节点E和F为最差目标簇头。为避免重簇现象的出现，节点G不应当选簇头。

图2 簇头选取示意图

要满足节点B当选簇头的概率最大、节点C、D次之、节点E、F最小、节点G为0的条件，刚好满足高斯分布概率密度函数的性质。由此本文引入高斯分布概率密度函数作为簇头选取的阈值函数。当选簇头的概率阈值函数为:

即以目标簇头节点与已知簇头节点的距离d为参数，簇头之间的最优距离R为均值，其函数曲线如图3所示。

图 3 概率阈值函数(σ1＜σ2＜σ3)

该概率阈值函数依然保留了高斯分布概率密度函数的性质。在d=R处概率最大。σ值一定的情况下，距离在最优目标簇头节点所在圆的两侧范围内满足f(R)≥f(R±Δd)。目标簇头节点与已知簇头之间的距离与最优距离的差值越小，即‖d－R‖越小，目标节点当选簇头的概率越大，即与已知簇头节点的距离越接近最优距离的目标节点当选簇头的概率越大，满足网络最优化覆盖的条件。

根据高斯分布的性质［12］，随机变量落在横轴区间(μ－2.58σ，μ+2.58σ)内的面积占总面积的比例约为99%。

由图3可知，节点当选簇头的概率随着与最优距离的差值的增大而逐渐降低，趋近于0。由于事件发生的概率低于1%为小概率事件，为了降低算法的时间复杂度，在簇头选取过程中引入最小概率阈值Pmin=0.01，概率低于Pmin的节点在本轮中不再竞争簇头，设定Prob(d=R+Δd)=Pmin，这样使得概率大于Pmin的节点落于候选概率带范围之内，这样就将簇头的选取范围划定在了宽度为2Δd的圆环内。

假设节点在检测范围内大致均匀分布，网络最终形成N个簇，网络面积为S，在选取簇头的过程中，对于任一簇头，其所在簇的半径为R，簇的面积为πR2。由高斯分布的性质可知，概率带之外的其他节点当选簇头的概率远远小于Pmin趋近于0，若把这些节点也选定为候选节点将大大提高算法的时间复杂度，因此将剩下的S－πR2区域划分N－1个簇，在每个候选区域内选取簇头，则每个簇头的平均候选面积为(S－πR2)/(N－1)，而由图2可知候选区域的面积，因此有:

由图3可知，σ的值越大，概率大于Pmin的节点形成的概率带的宽度也就越大，候选节点越多;反之亦然。由式(10)可知σ的值与网络的簇的数量息息相关，由于节点的通信半径一定，因此应根据网络的大小来选取合适的簇的数量使得每个簇头的承受得到均衡。

3.2 能量因素

LEACH算法在簇头选取的过程中没有考虑目标节点的剩余能量，使得低能量节点具有与高能量节点相同的概率当选簇头，加速节点的死亡。

本算法在成簇过程中将节点的剩余能量和目标节点的平均能量作为簇头选取的参考因素，优先选取剩余能量高于平均能量的目标节点当选簇头，使得高能量节点更具竞争力。对簇头选取阈值prob引入能量阈值模型:

其中，Eresidual表示当前节点的剩余能量，Nsum表示在概率带范围内未被覆盖的存活节点的个数，Esum表示该Nsum个节点的总剩余能量。改进后的阈值公式为:

改进后的阈值公式使得剩余能量较高且位置较优的节点优先当选簇头，既保证簇头节点的均匀分布，又保证簇头节点的剩余能量，均衡网络的整体能量消耗。

3.3 算法流程

在GCRA算法中，首先根据网络的规模和节点的数量选定适当的节点基本通信范围R和控制概率带宽度的σ的值。

簇头选取过程完成后，当选为簇头的节点设定时间片并接收入簇请求，同时，未当选簇头的节点根据本地的簇头信息表选取距离最近的簇头发送入簇请求。簇头时间片到后，簇头节点对接收到的入簇请求进行信息处理，分配簇内节点TDMA时间表，以R为通信半径在簇内广播成簇信息。各个成员节点根据接收到的成簇信息判断入簇结果，然后根据接收到的TDMA时间表向簇头节点发送监测数据。簇头节点将接收到的数据包进行数据融合后发送到基站。算法实现流程图如图4所示。

图4 算法流程图

普通节点选择距离最近的簇头节点为最终簇头并请求入簇，簇头节点向簇内成员节点一次性广播簇信息，避免了簇头节点与成员节点之间一对一的通信，有效降低簇头的能量消耗，均衡各个节点的能量消耗。

4 仿真实现

本文采用MATLAB仿真平台对LEACH、CMCRP以及GCRA进行仿真比较，以评价GCRA算法的性能。仿真参数［6］如下表1所示。

表1 仿真数据参数

本文主要选取剩余节点个数、网络平均剩余能量和基站接收信息量来比较三种算法的性能。在不考虑其他外界因素干扰的情况下，节点的能量等于零时视为死亡。网络生存周期为第一个节点的死亡时间。三种算法各进行仿真实验50次取平均值。

图5 簇头节点分布图

图5为在GCRA算法仿真过程中某次组网时簇头节点的基本分布示意图，从图中可以看出，网络共生成9个簇，与设置的目标数量10个基本相符，且簇头节点分布均匀，簇头之间的距离满足GCRA路由协议的定义，满足网络全局覆盖的要求。

图6是三种路由算法在每一轮循环中剩余节点个数的对比情况。具体各个时刻节点死亡时间如表2所示。

图6 网络剩余节点个数

表2 节点死亡时刻表

显然，该图反映了GCRA算法在降低能耗延长网络生命周期上的优越性。第一个节点死亡时，CMCRP算法运行了126轮，LEACH算法运行了103轮，而GCRA算法已经运行了166轮。GCRA算法的网络生存周期比 LEACH算法提高了61%，比CMCRP算法提高了31.7%，并且从曲线的斜率可知，相对于LEACH和CMCRP协议，GCRA算法每个节点的网络负载均衡得到明显地提高。

图7给出了三种算法的网络平均剩余能量的比较情况。可以看出，MPDFR算法节点的平均剩余能量比LEACH和CMCRP算法均有显著的提高。CMCRP算法虽然在簇头选取的过程中加入了拟物力的思想，距离已知簇头越远的节点当选簇头的概率越大，没有考虑到节点剩余能量的因素使得能量较低的节点当选簇头，节点的能量消耗得不到有效均衡，加快了节点的死亡。图8则反映了三种算法基站接收到的数据量的比较情况，GCRA算法接收到的数据量远远大于LEACH协议和CMCRP协议，是CMCRP协议接收数据量的近两倍。

图7 节点平均剩余能量

图8 基站接收数据包

5 结束语

本文提出了一种高斯分布分簇路由协议(GCRA)。在簇头选取过程中将高斯分布概率密度函数模型应用其中，结合目标节点的剩余能量，优先选取与已知簇头距离最优且剩余能量较高的节点当选簇头。仿真实验证明，GCRA算法比LEACH和CMCRP路由算法更具优越性，有效地解决了LEACH的能量缺陷和CMCRP簇头选取的不足，均衡节点的能量消耗，延长网络生命周期。

［1］Yick J，Mukherjee B，Ghosal D.Wireless Sensor Network Survey［J］.Computer Networks，2008，52(12):2292－2330.

［2］Al-Karaki J N，Kamal A E.Routing Techniques in Wireless Sensor Networks:A Survey［J］.Wireless Communications，2004，11(6):6－28.

［3］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2006.

［4］Akyildiz IF，SuW，Sankarasubramaniam Y.WirelessSensor Networks:A Survey［J］.Computer Networks，2002，38(4):393－422.

［5］赵强利，蒋艳凰，徐明.无线传感器网络路由协议的分析与比较［J］.计算机科学，2009，36(2):35－41.

［6］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［7］Youni O，Fahmy S.HEED:A Hybrid，Energy-Efficient，Distributed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Transactions on Mobile Computing，2004，3(4):366－379.

［8］Manjeshwar A，Agrawal D P.TEEN:A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks［C］//Proceedings of 15th IEEE International Parallel and Distributed Processing Symposium，San Francisco，2001，2009－2015.

［9］Lindsey S，Raghavendra C S.PEGASIS:Power Efficient Gathering in Sensor Information Systems［C］//Proceedings of the IEEE Aerospace Conference.Los Angeles，2002，1125－1130.

［10］卢强，何熊熊，冯远静，等.基于竞争机制的无线传感器网络分簇路由协议［J］.传感技术学报，2010，23(2):245－250.

［11］赵仕俊，张朝晖.无线传感器网络正六边形节点覆盖模型研究［J］.计算机工程，2010，36(20):113－115.

［12］李忠范，高文森.应用数理统计［M］.北京:高等教育出版社，2009.

［13］王微，冯静远，俞立.一种高效的无线传感器网络路由协议设计［J］.传感技术学报，2008，21(12):2061－2066.