董国勇，彭 力，吴 凡，闻继伟

(江南大学 物联网工程学院，江苏 无锡214122)

0 引 言

无线传感器网络(wireless sensor networks，WSNs)节点由于能量受限等特点严重影响了其网络性能，因此，WSNs协议的首要设计目标就是要高效地使用传感器节点的能量，延长网络存活时间。

研究人员们陆续提出了分簇路由协议［1～3］。Heinzelman W 等人［1］提出的LEACH 分簇路由协议随机选举簇首，收集簇内节点的数据并融合后发送给观察者来减少能耗。Younis O 等人［4］提出一种混合式的分簇协议HEED，算法根据节点剩余能量来概率性地选取一些候选簇首，然后以簇内部通信代价的高低来竞争产生最终簇首。LEACH-CS［5］以跨区距离的约束来自定义合适的多跳路由方案，通过均匀分簇、多跳路由一定程度上平衡了簇首的能量消耗，但是距离Sink 节点近的簇首会因转发大量数据而能耗较大，容易导致“热区”问题。

针对这一问题，李成法等人提出了EEUC［6］非均匀分簇路由算法。依据节点距基站的远近构建大小不等的簇，离基站越近簇半径越小，簇内成员越少，为簇首间数据转发预留能量。然而，算法是随机地挑选候选簇首，并没有考虑到节点分布的不均匀性。

文献［7］提出的WSNs 中基于能量代价的能量优化路由算法在选择平面路由时利用了节点间能量代价函数和前向区域来选择下一跳节点。文献［8］提出的能量均衡的WSNs 非均匀分簇路由协议分簇时采用了定时机制，一定程度上减少了信息交互量。然而，在选择中继节点时没有考虑到节点间的负载均衡。

针对以上算法存在的一些问题，本文提出了一种基于权值和代价函数的WSNs 非均匀分簇路由(uneven clustering routing based on weight and cost function，WCF-UC)算法，算法考虑节点剩余能量与节点密度计算簇首竞争权值。用一个代价函数，综合考虑簇首剩余能量、簇内成员节点数和位置信息等，决定每个簇首下一跳节点的最优路径。

1 系统模型

1.1 网络模型

假设N 个传感器节点随机分布在一个M×M 的正方形区域内，且该网络具有以下性质:1)节点可感知自身剩余能量;2)相邻节点采集的数据有相似性，可进行数据融合处理;3)链路是对称的，节点可根据RSSI 计算出发送者到自身的近似距离;4)节点可根据需要调整自身发射功率。

1.2 能量消耗模型

本文与文献［9，10］使用了类似的无线通信模型，发送需要消耗的能量为

接收需要消耗的能量为

其中，Eelec为发送电路和接收电路消耗的能量，εfs，εmp分别为自由空间传播模型和多路径衰减传播模型的能耗，为融合单位比特数据消耗的能量。

2 WCF-UC 算法基本思想

2.1 簇首选择与簇的建立

算法通过候选簇首竞争方式决定最终簇首，根据节点与基站距离及剩余能量来决定节点竞争半径。靠近基站的簇首要承担更多的数据转发任务，为了节省该簇首的能耗，需要保证节点有较高的能量同时缩小竞争半径，即根据公式(3)

其中，dmax，dmin分别为节点到Sink 节点的最大和最小距离，d(si，DS)为节点到Sink 节点的距离，R0c 为竞争半径最大值，c 为0 ～1 可控制取值的参数，Eini，Ei，Emin分别为节点初始能量、剩余能量、设置的最低工作能量。

竞争簇首时，须同时考虑节点剩余能量、充当簇首后能耗及整个区域平均剩余能量。节点剩余能量越大，竞争机会越大;节点越密集，该区域成簇的可能性越大。节点计算收到的各个候选簇首的竞争权值，选择较大的作为簇首并加入。竞争权值如式(4)

式中 Wn为簇首竞争权值，Ecurrent，Eini分别为该节点剩余能量和初始能量，α 为小于1 的常数，经过实验，取0.85 时簇首效果最佳;Kc为最佳簇首个数，M 为节点覆盖区域面积，dtoBS为网络中心到基站的距离。这里，引入节点密度的概念［11，12］，即节点在某一范围内的存活邻居节点数占所有存活节点总数的比重，Qn为节点密度。在每个周期开始，节点对外广播，收集半径为RC范围内的存活节点信息，同时将自身存活情况报告给邻居节点。这样可以得到Neighbor(n)alive.RC通过公式(2)获得。Networkalive可以通过基站在获得所有节点自身情况时，广播给网络内所有节点。

2.2 簇内数据通信

簇内节点交换数据时，簇首将簇内成员节点连成一条数据传输链，成员节点从传输链的两端向簇首传送数据，因此，簇首只需和邻近的成员节点各收发一次数据。假设在第a 轮采集过程中，第i 个簇有n 个节点，每个节点每次采集k bit 数据，那么，簇首在这次数据采集过程中接收簇内节点数据和数据融合能量的消耗为

而簇内节点以点对点的方式向簇首传输数据时，簇首的能量消耗为

由上式可知，n≫3，所以，采用上述算法后，簇首消耗能量将大大减小，可以有效平衡簇首与成员节点的能耗。

2.3 簇间多跳路由

本算法多跳路由设计目标是为了找到一条最优化路径，以减小簇间数据传输时的能耗和避免“热点”问题。首先，簇首Hi在竞争范围内广播一条消息，包括簇内节点数、簇首ID、剩余能量和基站距离。若邻居簇首到基站的距离较小，那么，簇首Hi计算和邻居簇首Hj的距离，并且建立一张包含邻居簇首信息表。

Hi在邻居簇首集中选择下一跳节点NHi，该节点在所有的邻居簇首中具有最小的代价函数。代价函数如下定义

式中 Eavr(Hi)表示簇首Hi邻居簇首的剩余能量均值，Ecurrent(Hj)为簇首Hj的剩余能量，Nc(Hj)为簇首Hj的成员节点数，Nc_avr(Hi)为簇首Hi邻居簇首平均节点数，dHi-Hj为Hi到Hj的距离，dHj-BS为Hj到基站的距离，α，β，γ 为加权系数，满足α+β+γ=1。代价函数第一项是为了选择剩余能量较大的簇首作为下一跳节点，因为下一跳节点需要转发数据消耗更多能量，所以，能量因素是首要考虑的;第二项是为了选择成员节点数量较少的作为下一跳，这样簇内通信能耗较少，有更多能量用于转发数据;第三项主要是为了下一跳节点位置的考虑，多跳路由应该尽量选择最短路径，使得传输能耗最小。如果Hi的下一跳为本身，那么，直接发送数据到基站;否则，将数据发往下一跳节点，所有节点都找到下一跳节点后，簇间多跳路由建立完成。

3 仿真实验与结果分析

本文在Matlab 平台下仿真实验，将500 个节点随机分布在一个200 m×200 m 区域中，Sink 节点的坐标为(100，250)m。实验参数如表1 所示。

表1 实验参数Tab 1 Experimental parameters

算法开始，N×p 个节点成为候选簇广播N×p 条竞选消息。每个候选簇首广播一条竞选簇首成功消息，或广播一条退出竞选消息通知邻簇首，总N×p 条消息。设共k 个簇首，广播k 条竞选获胜消息，之后N-k 个普通节点发送N-k 条申请加入消息。总计2N×p+N 条消息。与EEUC算法一样，本文WCF-UC 也是消息驱动的算法，消息复杂度仍为O(N)。

比较4 种算法的网络生命周期。如图1，LEACH 的第一个节点在305 轮死亡，HEED，EEUC，WCF-UC 算法分别为220 轮、480 轮和610 轮，WCF-UC 算法明显延迟了首个节点失效时间。WCF-UC 算法最后一个节点的死亡轮数是1610 轮，EEUC，HEED，LEACH 算 法 分 别 为1190，1000，790 轮，相对于实验总轮数(1800 轮)，分别延迟了23.3%，33.9%，45.6%。由此可见，WCF-UC 有效提高了能量的均衡性，延长了网络生命周期。

图1 网络生命周期对比Fig 1 Comparison of network lifetime

簇首能耗占网络能耗主要部分，因此，须对比4 种协议的簇首能耗之和。实验中随机选取10 轮，统计各轮中所有簇首能耗和。如图2，WCF-UC 和EEUC 算法的簇首能耗最低。因为两种协议中，簇首采用多跳方式将数据发送至汇聚点，显著降低了能耗。

图2 簇首消耗能量之和对比Fig 2 Comparison of sum of cluster heads energy consumption

图3 对比了4 种算法网络剩余总能量随周期的变化情况，LEACH 最先消耗为0。WCF-UC 比LEACH，HEED，EEUC 的能量消耗减少了30.3%，25.2%，10.6%。WCF-UC更有效地节约了能量，因为同时考虑了节点剩余能量、与基站距离及节点分布进行簇首选择与簇的建立，采用代价函数的多跳路由优化了各簇首间的能量路径。

4 结束语

本文基于权值和代价函数提出的非均匀分簇路由算法，有效减少了簇首选举和路由数据转发能耗。仿真分析表明:WCF-UC 算法网络存活时间有明显提高，能有效均衡网络节点能耗。但是本文没有考虑簇半径的优化等问题，有待进一步完善研究。

［1］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocols for wireless microsensor networks［C］∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000:3005-3014.

［2］ Heinzelman W，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［3］ Soro S，Heinzelman W.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium，2005:236-243.

［4］ Younis O，Fahmy S.HEED:A hybrid，enegry-efficient，distribued clustering approach for Ad Hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3(4):660-669.

［5］ 顾跃跃，白光伟，陶金晶.LEACH-CS:一种自定义的WSNs 跨区多跳路由机制［J］.计算机科学，2011，38(1):78-82.

［6］ 李成法，陈贵海，叶 懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30(1):27-36.

［7］ 许彦芹，陈庆奎.基于SMP 集群的MPI+CUDA 模型的研究与实现［J］.计算机工程与设计，2010，31(15):3408-3412.

［8］ University of Illinois at Urbana-Champaign.Accelerator cluster webpage［EB/OL］.［2013—03—12］.http:∥iacat.illinois.edu/resources/cluster/.

［9］ Ye Mao，Li Chengfa，Chen Guihai，et al.EECS:An energy efficient clustering scheme in wireless sensor networks［C］∥IEEE International Performance Computing and Communications Conference(IPCCC)，2005:535-540.

［10］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:1-10.

［11］乔俊峰，刘三阳，曹祥宇.无线传感器网络中基于节点密度的簇算法［J］.计算机科学，2009，36(12):46-49.

［12］卢先领，王莹莹，王洪斌，等.无线传感器网络能量均衡的非均匀分簇算法［J］.计算机科学，2013，40(5):78-81.