图1 节点能耗模型
Fig.1 Model for energy consumption of nodes
无线传感器网络WSNs[1]通过部署在监测区域中的传感器节点，对监测对象协作感知、采集并处理其信息，然后发送到基站BS.WSNs技术以物物相联的观念改变了人类社会与大自然的交流方式，它对信息世界与客观物理世界进行了逻辑融合，被广泛应用于社会各个领域，包括环境监测、工业控制、智能家居、军工航天和城市交通等，形成了以其作为支撑的泛在物联网络.无线传感器网络路由包括平面路由和分层结构.平面路由中传感器节点身份对等，网络流量相对均匀，但适用的网络规模相对较小.分层路由采用簇对传感器节点进行管理，由成簇、簇维护、簇内路由三个阶段组成.成簇负责动态环境下的传感器节点聚集成簇问题，簇维护负责节点移动与节点进出网络中的结构维护，簇内路由负责局部范围的数据通信.
早期的WSNs多采用均匀分簇的分层路由，即以某种标准将网络划分为规模均等的簇.LEACH[2]是无线传感器网络最早的分簇路由，该协议随机选取簇头，非簇头节点将数据传送到簇头，簇头进行数据融合后发送到基站.LEACH减少了与基站直接通信的节点数和数据量，且采用了簇头轮换机制，有较好的节能效果.TEEN[3]对LEACH做了改进，通过设置广播硬门限值和软门限值降低了不必要的数据传输次数，使数据传输更加高效.PEGASIS[4]在LEACH的基础上加入了链式结构，即各节点均从邻居接收数据，并向另一邻居发送数据，最终发送给基站.PEGASIS的通信只限于邻居节点，每轮只随机选取一个簇头与基站通信，大大减少了通信量.
可见，均匀分簇无论簇间路由的形式是单跳还是多跳，均会导致各个簇的能耗不均衡，个别簇头和簇成员会快速死亡，而非均匀分簇可有效改善该问题.在EECS协议[5]中，节点兼顾考虑簇头到BS的距离以及自身到簇头的距离，以便建立规模不均匀的簇结构.由于采用了与LEACH一样的簇间单跳模式，EECS使得距离BS更远的簇规模更小，但这仅缓解了簇头的能耗不均，整个网络的能耗均衡问题仍未得到解决.NUCRP[6-7]以非均匀分簇方式平衡簇头能耗，考虑了簇内通信和簇间通信能耗，前者能耗与簇内成员数量有关，后者能耗则是转发数据量的函数.EEUC[8]为了使得靠近BS的簇规模更小，设置了非均匀的簇头竞争半径，使簇头能够节约部分能耗.此外，选择中继节点时，不仅考虑了候选中继与BS的位置关系，还考虑节点能量，从而进一步均衡能耗.AC-EBUC[9]在EEUC的基础上对簇头的随机周期性簇首选择方式做了改进，即首轮所有节点参与竞选，而后续轮簇内再进行调整.文献[10-11]将单跳改进为多跳方式，由簇头承担邻居簇头的数据转发任务，解决了簇头的能耗问题，并改进了簇头的选择策略.EBFA[12]采用非均匀分簇和簇间多跳转发策略，在多跳转发阶段，引入社会福利函数评估数据转发路径上节点间的能量均衡程度，选择能量均衡程度较好的作为转发节点.
本文提出一种新的高能效分簇路由，新路由能够通过非均匀规模的分簇与簇间多跳路由方式有效延长网络存活时间.引入簇头竞争算法有效地选择簇头，选择标准同时考虑了候选簇头的剩余能量和邻居的剩余能量，目的是使距离BS更近的候选簇头在竞争正式簇头时范围更小，这样导致距离基站较近的簇具有更小的规模，簇成员也更少，簇内通信时产生的能耗也更少，直接有利于作为中继节点的簇头可以承担后面的转发任务，最终带来更加均衡的能耗水平.
对本文考虑的无线传感器网络属性做如下假设：1)观测区域为矩形区域，所有节点不具备移动性；2)节点是同质的，具有唯一的标识，且具备数据融合功能；3)节点可以根据距离对发射功率进行调整；4)收发双方的通信链路具有对称性.
网络节点能耗采用文献[13]中提出的无线通信能耗模型，如图1所示.模型由功率放大器和射频电路组成，前者能耗根据收发节点间距离的不同分为自由空间模型和多路径衰减模型.自由空间模型的路径损耗指数为2(d2功耗)，多路径衰减模型的路径损耗指数为4(d4功耗).使用哪种模型取决于通信距离，若通信距离小于门限值，则使用自由空间模型.
图1 节点能耗模型
Fig.1 Model for energy consumption of nodes
根据文献[13]中的能耗模型，若发送方发送l bit数据至距离d处，则其能耗为
ETx(l，d)=ETx-elec(l)+ETx-amp(l，d)
(1)
(2)
而接收l bit的消息时，接收方能耗为
ERx(l)=ERx-elec(l)=lEelec
(3)
为了简化实验过程，假设通信能耗采用Friss自由空间模型，簇j内的成员节点数量为m，那么簇内成员节点h发送l bit数据至簇头j时的能耗为
(4)
式中，dhj为成员节点h与簇头j之间的距离.
簇头j消耗的总能量应包括：接收簇内所有成员节点发送数据的能耗、发送融合后数据的能耗以及接收和转发其他K个簇头数据的能耗，假设所有簇内成员节点是近似的，则有
Ei= (K+1)m(ETx(l，d)+ERx(l))=
(K+1)ml(2Eelec+εfriss-ampd2)
(5)
结合式(4)、(5)可以看出，簇头能耗由簇内节点数m、需要转发的数据量l、簇内节点与簇头间的距离dhj以及至下一跳中继节点的距离d决定，因此，优化这些参数将直接可以降低簇头能耗，这也是本文选择优化簇头选择策略以及优化数据传输路径中中继节点选择的依据所在.
设矩形观测区域中的网络以基站BS为中心划分为N个扇形区域，扇形区域的上边界表示为UL，下边界表示为LL，最远层次表示的非规则区域间距(上边界与矩形下边)设置为R0，该层次为不规则区域.计算层次UL边和LL边与BS间的距离，然后将该距离通过Hello广播至全网，广播消息格式为：网络层数，UL边与BS间距，LL边与BS间距.同时，在部署阶段，节点根据Hello广播信号强度计算与BS的间距，同时节点通过该距离计算出自己所属的层数i，其计算公式为
(6)
式中：Uj为UL边的节点j与BS的间距；Uj′为LL边的节点j′与BS的间距.节点计算层次的过程如算法1所示，节点层次划分如图2所示.
算法1 计算节点层次
1) BS广播Hello消息至观测区域
2) For每个传感节点
3) 节点Si接收Hello消息
4) End For
5) 计算节点Si与BS间的距离di_to_BS
6) Fori=1 ton-1
7) 如果LLi<di_to_BS<ULi
8)Si.level=i
9) 否则
10)Si.level=n
11) End
12) End For
算法说明：步骤1)表明基站BS向全网广播Hello消息，步骤2)～4)表明观测区域的传感节点接收步骤1)的Hello广播，之后所有接收消息的传感节点根据接收信号强度计算自身与BS之间的距离(步骤5))，步骤6)～12)则对所有节点进行层次划分.
图2 节点层次划分
Fig.2 Level division of nodes
节点接收Hello广播后，需要将自身剩余能量及与BS距离发送至BS，基站根据该消息计算层次平均能量.在每轮的建簇阶段，BS向全网广播AvE_lay_msg消息(包含层次平均能量)，节点接收并进行阈值比较，因此，考虑节点剩余能量，本文改进阈值公式，将其定义为
(7)
算法2 簇头选择与成簇过程
1) BS广播消息AvE_lay_msg(AvE1，AvE2，…，AvEn)
2) 每个节点接收消息AvE_lay_msg
3) 设置随机数u←Rand(0，1)
4) 计算Tthresh=PEr/Eave
5) 如果u<Tthresh
6) 设置节点状态为candidate cluster_head
7) End
8) 如果节点状态为candidate cluster_head
9) 节点广播消息Compete_head_msg(ID，Er，R)
10) 否则
11) 退出
12) End
13) 当candidate headSi接收来自Sj的Compete_head_msg时
14) 如果di_to_j<MAX(Ri，Rj)
15) 添加Sj至集合Si.neighbor_head中
16) End
17) 当节点状态为candidate cluster_head时
18) 如果Sj∈Si.neighbor_head且Esi>Esj
19) 节点Si广播消息Norm_head_msg(ID)并退出
20) 否则如果Esi=Esj
21) 如果di≤dj
22) 节点Si广播消息Norm_head_msg(ID)并退出
23) End
24) End
25) 当节点Sj接收来自Sj的消息Norm_head_msg时
26) 如果Sj∈Si.neighbor_head
27) 节点Sj广播消息Exit_head_msg(ID)并退出
28) End
29) 当节点状态为normal cluster_head
30) 节点广播消息CH_ADV_msg(ID)
31) 如果节点状态为common
32) 节点接收CH_ADV_msg并广播Join_ADV_msg(ID)
33) End
其中：P∈[0，1]为任一节点当选簇头的概率；Tthresh为单个节点成为候选簇头的概率；Er为节点剩余能量；Eave为层次平均能量；R为簇头竞选半径；Si.neighbor_head为候选簇头的邻居候选簇头集.表1为主要的消息定义.邻居簇头集合定义Si.neighbor_head={Sj|Sj为候选簇头，di_to_j<MAX(Ri，Rj)}.
表1 消息说明
Tab.1 Message description
消息消息定义消息发送者消息接收者AvE_lay_msg平均能量基站所有传感节点Compete_head_msg正式簇头竞选消息候选簇头所有候选簇头Norm_head_msg正式簇头正式簇头所有传感节点Exit_head_msg退出簇头竞争候选簇头所有候选簇头CH_ADV_msg簇头消息正式簇头所有传感节点Join_ADV_msg申请簇成员非簇头节点簇头节点
算法说明：步骤1)中BS广播消息AvE_lay_msg(包含层次平均能量)至全网，步骤2)表明各网络节点接收了该消息；步骤3)～7)表示候选簇头选择策略，步骤4)中的阈值Tthresh考虑了节点层次平均能量和自身剩余能量；步骤8)～12)表明，对于候选簇头，需要广播正式簇头竞选消息Compete_head_msg，其他节点则进入休眠；步骤13)～16)表示，若两个候选簇头处于两者中竞选半径较大的范围内，需要根据广播消息构建邻居候选簇头集Si.neighbor_head，并在构建完之后，通过步骤17)～24)选出最终簇头，即邻居候选簇头中剩余能量最大的当选簇头，并广播正式簇头消息Norm_head_msg；步骤25)～28)表明正式簇头广播当选消息，而其邻居候选簇头集中的簇头广播消息Exit_head_msg退出竞争，消息中包含节点标识符；步骤29)～33)表明簇头向全网广播簇头消息CH_ADV_msg，而其他节点广播加入消息Join_ADV_msg进行入簇.
在本文设计的簇头选择与成簇算法中，对各层次的候选簇头竞争半径重新进行了定义，以形成非均匀簇.算法目标是使得靠近BS的簇内成员更少，因此，靠近BS的候选簇头竞争半径应较小.设簇头竞争半径为
(k=1，2，…，n)
(8)
式中：k为节点所处的层次；n为网络划分的层数；c为[0，1]之间的常数.
单跳通信方式会使得距离BS较远的簇头较快死亡，影响网络的连通性.UCER协议采用多跳的簇间路由方式将各簇头数据转发至BS.本文假设不同簇间传送的数据无法在单个节点上进一步进行数据融合，即所选择的中继簇头节点只负责数据转发，模型如图3所示.
图3 多跳非均匀分簇
Fig.3 Multi-hop unequal clustering
UCER令中继路由节点的选取范围为上层区域的簇头中，即k层簇头选择k-i的簇头作为中继.簇头Si选择簇头Sj作为中继的条件为：1)Sj所在层次比Si所在层次离BS更近，即dj_to_BS<di_to_BS；2)Si到Sj的距离小于Si到基站的距离，即di_to_j<di_to_BS；3)Sj比较Si位于更低的层次中，即Sj.level<Si.level.当同时满足条件1)～3)的中继节点个数大于1时，将所有符合条件的簇头定义为候选中继节点.
Si需要从候选中继节点集中选择数据路由中继，在这个过程中，若只考虑节点剩余能量因素可能导致网络整体能效下降.假设Si选择Sj作为中继，若采用Friss自由空间模型，设Sj接收数据后直接发送至BS，则能耗为
E2-hop=ETx(l，d(Si，Sj))+ERx(l)+
ETx(l，d(Sj，BS))=
l(Eelec+εfriss-ampd2(Si，Sj))+lEelec+
l(Eelec+εfriss-ampd2(Sj，BS))=
3lEelec+l2εfriss-amp(d2(Si，Sj)+
d2(Sj，BS))
(9)
由式(9)可知，总能耗E2-hop将取决于d2(Si，Sj)+d2(Sj，BS)，即节点Si与节点Sj之间的距离以及节点Sj与基站之间的距离.那么，如果Sj位于Si与基站之间，则此时能耗是最小的.为了兼顾考虑传感器节点的剩余能量以及通信链路能量开销，中继节点选择策略为：Si从所有候选中继节点能耗最小的两个节点中进行选择，剩余能量更高的节点作为正式中继节点，因此，本文定义中继簇头节点的转发参数为
(10)
式中：Einitial为节点的初始能量；α和β为权重因子.当选择的中继节点Tc(j)值较小时，表明该中继节点不仅可以节省能耗，还可以均衡该节点作为中继节点在通信链路上的负载.在此过程中，需要建立一个邻居簇头信息表，如表2所示.
表2 邻居簇头信息
Tab.2 Information of neighbor cluster heads
标识含义ID邻居簇头的标识Er邻居簇头的剩余能量Nnum_CH簇内成员节点数量d_to_BS邻居簇头至基站的距离d_to_CH邻居簇头到自身的距离
中继节点选择过程如算法3所示.
算法3 中继节点选择过程
1) For网络中的每个簇头
2) 如果dj_to_BS<di_to_BS，di_to_j<di_to_BS且Sj，k<Si，k
3) 添加Sj至集合Si.relay
4) End
5) End For
6) 如果Si.relay为空集
7)Si.nexthop=BS
8) 否则
9)Si.nexthop=MAX(Em，En)
10)Em(2-hop)，En(2-hop)<El(2-hop)，m，n，l∈Si.relay
11) End
算法说明：在选择中继节点过程中，簇头维护一个集合Si.relay，用来存储候选中继节点中符合以上三个条件的可能中继节点；步骤6)～7)表明，如果Si.relay中没有符合条件的中继节点，Si则选择直接将数据发送至基站BS；否则，通过步 骤8)～11)，Si选择剩余能量更高的作为通向基站的中继节点.
本文利用NS2对协议进行了实验分析.实验中节点的部署位置由NS2的genscen工具随机生成，选取均匀分簇路由协议LEACH、非均匀分簇路由协议EEUC和AC-UBEC作为比较协议.实验参数如表3所示.
表3 实验参数设置
Tab.3 Setting of experimental parameters
参数取值网络规模/m200×200基站坐标(100,350)传感节点数量200节点初始能量/J0.5数据包大小/bit3000控制包大小/bit200层次3R0100α0.6β0.4Eelec/(nJ·bit-1)50εfriss-ampd2/(pJ·bit-1·m-2)10εtwo-ray-ampd4/(pJ·bit-1·m-4)0.0013EDA/(pJ·bit-1·signal-1)50
选取以下五个性能标准进行观察与比较：成簇量、簇头分布、簇头能耗、建簇能耗、节点存活量.其中，簇头分布以簇头间距表示，建簇能耗主要来源于成簇时的消息传播.
图4为新协议的成簇个数分布.LEACH的成簇量分布范围最大，而EEUC和UCER相比较更为集中，主要原因是三种协议在簇头选择上的差异.LEACH的簇头选择由随机数控制，每一轮的成簇量是无法控制的.相比较而言，EEUC和UCER通过竞争方式产生簇头，每一轮产生的成簇量则更为稳定.同时，UCER在层次内以计时广播形式和设置成簇半径方式取代竞争协商，簇头数量更为稳定.
图4 新协议的成簇个数分布
Fig.4 Number distribution of clusters of new protocols
图5为几种协议所产生的簇头间距变化.可以看出，LEACH中簇头间距平均约为20 m，EEUC约为40 m，本文协议UCER约为65 m.该指标直接受成簇数量的影响，在固定区域内，成簇量过多，则直接导致簇头间距过小，LEACH可能导致在局部区域内簇头过于密集，而其他区域簇头过于稀少，直接导致簇内数据通信产生更大的开销.而UCER通过在层次内部设置竞争半径使得各簇头不在相互竞争半径内，簇头分布更加均匀.
图5 簇头间的最小距离
Fig.5 Minimal distance between cluster heads
图6为协议的簇头能耗变化.簇头能耗的变化取决于协议在簇间是单跳还是多跳方式.由于LEACH与基站的数据通信是单跳方式，簇头能耗最大，因为长距离通信占据能耗主要部分.EEUC和UCER采用簇间多跳方式路由，但EEUC每一轮的簇头选择是在全网范围内进行广播竞争，消耗了更多的能耗.UCER则在层次内进行广播簇头选择，节省了部分数据通信能耗.同时，由于文中假设簇头上的数据融合能耗是固定的，所以这部分能耗不会因单跳或多跳通信方式产生很大变化.
图6 簇头能耗
Fig.6 Energy consumption of cluster heads
图7为几种协议的成簇能耗，表现为网络的总剩余能量.由于EEUC和UCER在成簇阶段加入了簇头竞争机制，候选节点需要在局部范围内进行簇头竞选，此时需要广播竞选消息，但由于该消息报文容量极小，所以相较LEACH而言，会带来一部分能耗.LEACH成簇是随机的，没有节点间的簇头竞争，因此网络剩余能量更多.总体来说，尽管成簇能耗变大，但所占比例较小，通过簇头竞争的非均匀分簇路由效率仍是更好的.
图7 建簇能耗
Fig.7 Energy consumption of cluster forming
图8为网络的生存时间，以传感器节点是否存活情况表示.可以看出，LEACH最早出现节点死亡情况，UCER则到40轮才出现第一个节点死亡.主要原因是新协议在选择簇头时考虑了节点的剩余能量和各层次的平均剩余能量，且根据距离基站的远近划分将节点组织成不均匀大小的簇规模，并采用多跳的簇间路由方式，为节点节省了能耗.EEUC出现节点死亡和最后一个节点死亡均早于UCER，这是由于UCER中提出的计时广播方式能有效减少簇头竞争阶段产生的通信能耗，而EEUC的全局协商簇头选择机制相对而言会消耗更多能耗，且UCER层次内的簇头选择机制为节点进一步节省了能耗，其网络生存时间更长.
图8 存活节点数量
Fig.8 Number of survival nodes
本文提出了一种基于层次的多跳非均匀分簇路由协议UCER.改进协议的主要工作是对簇头选举、簇间路由和成簇规模进行了改进，旨在让具有更多能量的节点担任簇头，并基于层次的划分形成非均匀簇结构，以支持后续数据的簇间多跳路由.结果表明，UCER协议在簇头分布的合理性与节省能耗方面均有更好表现.
[1]Akyildiz L F，Su W L，Sankarasubramaniam Y.A survey on sensor networks [J].IEEE Communication Magazine，2002，40(8)：102-114.
[2]Heinzelman W R，Chandrakasan A，Balakrishnan H.An application-specific protocol for wireless microsensor networks [J].IEEE Transactions on Wireless Communication，2002，1(4)：660-670.
[3]Manjeshwar A，Agrawal D P.TEEN：a routing protocol for enhanced efficiency in wireless sensor networks [C]//Proceedings of the 5th Parallel and Distributed Processing Symposium.San Francisco，USA，2001：1-7.
[4]Lindsey S，Raghavendra C S.PEGASIS：power efficient gathering in sensor information systems [C]//Proceedings of IEEE Aerosapce Conference.Coimbatore，India，2002：1125-1130.
[5]Li C F，Ye M，Chen G H，et al.An energy-efficient unequal clustering mechanism for wireless sensor networks [C]//IEEE International Conference on Mobile Adhoc Sensor Systems.Yangzhou，China，2005：535-540.
[6]廖福保，张文梅，李向阳，等.无线传感器网络中一种新的非均匀分簇路由协议 [J].小型微型计算机系统，2015，36(6)：1265-1270.
(LIAO Fu-bao，ZHANG Wen-mei，LI Xiang-yang，et al.New unequal clustering routing protocol for wireless sensor networks [J].Journal of Chinese Computer Systems，2015，36(6)：1265-1270.)
[7]张文梅，廖福保.改进的无线传感器网络非均匀分簇路由算法 [J].传感技术学报，2015，28(5)：739-743.
(ZHANG Wen-mei，LIAO Fu-bao.Improved uneven clustering routing algorithm for wireless snesor networks [J].Journal of Sensor Technology，2015，28(5)：739-743.)
[8]李成法，陈贵海，叶懋，等.一种基于非均匀分簇的无线传感器网络路由协议 [J].计算机学报，2007，30(1)：27-36.
(LI Cheng-fa，CHEN Gui-hai，YE Mao，et al.An uneven cluster-based routing protocol for wireless sensor networks [J].Journal of Computer，2007，30(1)：27-36.)
[9]缪聪聪，陈庆奎，曹剑炜，等.基于蚁群的无线传感器网络能量均衡非均匀分簇路由算法 [J].计算机应用，2013，33(12)：3410-3414.
(MIAO Cong-cong，CHEN Qing-kui，CAO Jian-wei，et al.Energy balanced uneven clustering algorithm based on ant colony for wireless sensor network [J].Journal of Computer Application，2013，33(12)：3410-3414.)
[10]Sun Y Q，Peng J，Liu T，et al.Uneven clustering routing protocol based on dynamic partition for wireless sensor network [J].Journal on Communication，2014，35(1)：198-206.
[11]Liao Y，Qi H.Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks [J].IEEE Sensors Journal，2013，13(5)：1498-1506.
[12]孙彦景，林昌林，江海峰.一种能量高效的分布式非均匀分簇路由算法 [J].传感技术学报，2015，28(8)：1194-1200.
(SUN Yan-jing，LIN Chang-lin，JIANG Hai-feng.An energy efficient distributed uneven clustering routing algorithm for WSNs [J].Journal of Sensor Technology，2015，28(8)：1194-1200.)
[13]Ashtar A M，Nahai M，Aghvami A H.Power aware cooperative routing in wireless mesh networks [J].IEEE Communications Letters，2012，16(5)：670-673.