能耗均衡的多跳多路径认知分层路由算法*

王俊喜,陈桂芬

(长春理工大学电子信息工程学院，吉林 长春 130022)

1 引言

认知无线传感器网络是近几年的研究热点，它的前身，无线传感器网络[1 - 3]是由大量微型传感器节点构成的，传感器节点通常由电池供电，密集地部署在所需区域监测环境参数或感测特定数据。传感器节点将它们感测到的数据以多跳或单跳的方式传输给一个或多个数据接收器。

无线传感器网络通常是基于多种不同应用环境的网络，由于传感器节点配备的是低成本的电池，节点的存储器有限，处理能力低。而在大多数应用中，更换电池或者为电池充电是不切实际的，所以很多节点会耗尽其自身能量导致部分网络失去连接。因此，在设计高效率、长寿命的无线传感器网络时，拥有适配的高效节能路由算法是至关重要的[4 - 6]。

近年来，相关算法被陆续提出，文献[7]提出了集中式节能距离CEED(Centralized Energy Efficient Distance)路由算法，旨在改善簇首CH(Cluster Head)的选择和簇的形成。在CEED中，簇首CH的选择基于剩余能量和每个节点到接收器的距离。在网络分簇结构形成中，每个节点都基于剩余能量和距离参数选择其CH，然后和CH构造一条链，用于将数据包以多跳方式传输到接收器。

文献[8]提出了一种新的簇首选择方案，所有节点根据其自身剩余能量竞选成为簇首，形成簇结构之后，剩余能量更高、距离汇聚节点(Sink)更近的簇首将成为其他簇首的数据收集节点，数据收集节点再将数据转发至汇聚节点。

文献[9]提出了一种能量感知的多跳多路径路由EAMMH(Energy Aware Multi-hop Multi-path Hierarchical)算法，该算法通过引入能量感知和簇内多跳功能来降低网络总能耗。

文献[10]提出了一种结合节点能耗因子改进协议SEP(Stable Election Protocol)的EC-SEP(Energy Consumption-SEP)算法，该算法根据节点剩余能量不断更新簇首选举概率，以此来均衡网络的能量消耗，延长生命周期。

随着无线传感器网络的广泛应用，其与ZigBee、WiFi和蓝牙等共享频段的方式导致频谱资源的日益紧缺[11]。以上算法将不再契合未来发展需要，近几年来，人们将能够缓解频谱资源紧缺问题的认知无线电与无线传感器网络进行结合，提出了认知无线传感器网络CRSN(Cognitive Radio Sensor Network)这个热点话题，适用于认知无线传感器网络的路由算法成为目前研究方向[11]。

文献[12]提出了一种适用于CRSN的低能耗自适应非均匀分簇LEAUCH(Low Energy Adaptive Uneven Clustering Hierarchy)算法，其核心是应用认知无线传感器节点进行数据传输，并利用非均匀的簇首竞争半径均衡簇首能量消耗。

文献[13]提出了一种改进的能量有效阈值敏感传感器网络路由协议A-TEEN(Advanced Threshold Sensitive Energy Efficient Sensor Network Protocol)算法，将路由协议TEEN(Threshold Sensitive Energy Efficient Sensor Network Protocol)应用于CRSN，并根据节点空闲信道数改进了簇首选举概率公式。

上述算法能够应用于CRSN，并能结合认知能力缓解频谱资源紧缺的现状，但是其网络能量消耗不够均衡，认知传感器节点对接收器灵敏度需求较高，网络中节点均为认知传感器节点的铺设难度较大。无线传感器网络节点数目大、分布稠密、维护难度高，节点存储空间小、能量受限，节点开始工作后，除具备可移动装置的节点外普遍处于静止状态。基于网络特点研究设计路由算法并不断推陈出新具有重要意义。

能量受限问题是无线传感器网络实际应用的主要瓶颈，能够提高网络能量的使用效率并延长网络寿命是路由算法的基本设计目标[14]，针对该目标并结合缓解频谱资源日益紧缺的问题，本文提出了一种应用于异构CRSN的能耗均衡多跳多路径路由EMMCH(Energy-balanced Multi-hop Multi-path Cognitive Hierarchical)算法。

EMMCH算法为上述问题提供了解决方案，首先EMMCH算法适用于当下研究热点CRSN，能够缓解频谱资源日益紧缺的现状；其次，算法采用了异构网络设置，普通节点与认知传感器节点协作通信，降低了铺设难度与铺设成本；最后，算法着重考虑并提高了网络能耗均衡性，延长了网络生命周期。

对比仿真结果发现，与EAMMH算法[9]、LEAUCH算法[12]、EC-SEP[10]算法、结合认知能力改进SEP算法的CSEP(Cognitive-SEP)算法等相比，EMMCH算法具有更长的生命周期、更高的稳定性、更多的数据传输量和更均衡的网络能耗。

2 网络模型的建立

2.1 能量消耗模型

文献[15]提供了一种经典的无线传输能量消耗模型，根据传输距离d，该传输消耗模型分为2种，其一为自由空间模型，其二为多径传输模型。能量计算公式如式(1)所示：

(1)

其中，k为节点发送字节数，d为数据传输距离，εfs为自由空间模型放大倍数，εmp为多径传输模型放大倍数。Eelec为发送或者接收单位比特数据的能耗。其中：

(2)

节点接收数据消耗为：

ERx(k)=ERx-elec(k)=kEelec

(3)

其中,k为接收的数据比特数。

2.2 网络模型

以随机的方式在规定区域内部署若干个节点，节点包括普通传感器节点和认知传感器节点，认知传感器节点能够感知节点空闲信道情况并动态连接。普通传感器节点能够独立感知信息[16]。暂不考虑传输误差，设定节点能量耗尽为节点死亡。为了避免其他因素的影响，对网络中节点性质进行以下设定：

(1)节点编号唯一且不发生改变，节点在监测区域内随机部署，部署后不再移动；

(2)汇聚节点能量无限、位置不变；

(3)节点可以根据接收信号强度感知距离、定位其自身位置；

(4)认知传感器节点均具有与汇聚节点直接通信的能力(即认知传感器节点均可成为簇首，能耗随距离的增大而增加)；

(5)节点可以根据通信距离调节通信功率。

3 EMMCH算法

本文提出的EMMCH算法是一种异构认知无线传感器网络能量感知多跳多路径认知分簇路由算法，认知传感器节点通过感知到的频谱空闲信息，机会地接入空闲信道，将无线传感器网络的监测数据传输至汇聚节点。算法通过多跳传输降低传输消耗。节点通过判别剩余能量、节点距离、节点密度及其频谱能量等级判别是否成为候选簇首。担任候选簇首的节点结合竞争半径和频谱能量等级判断其频谱能量等级在竞争半径范围内为最高后，宣布担任簇首。其竞争半径内的其余候选簇首退出竞选。距离汇聚节点越远的簇首拥有越大的竞争半径，汇聚节点附近处可形成比较远处更多的簇，避免依据节点位置选择簇首带来的 “热区”问题。

首先，在一定大小的检测区域内随机铺设共N个节点，由汇聚节点在监测区域内广播信号，各个节点根据接收到的信号强度，得到与汇聚节点的大致距离di,1≤i≤N，随后将距离di和自身的剩余能量返回给汇聚节点。由于在实际应用环境中，节点位置一般不变，这里不讨论移动节点，则可得节点距离因子α：

(4)

其中，dmax为节点到汇聚节点的距离最大值，dmin为节点到汇聚节点的距离最小值。

为确保簇首的利用率设置节点密度因子ρ，使邻居节点较密集的节点较易成为簇首，若邻居节点密度很小，则该节点不适合成为簇首，以避免相对边缘的节点成为簇首，造成能量浪费。首先，将与某节点距离小于R的节点定义为该节点的邻居节点。距离R的定义式如式(5)所示：

(5)

其中，S为检测区域的面积，Popt为最佳簇首比率(模拟取值0.1)[12]。那么，节点密度因子定义式如式(6)所示：

(6)

其中，Nlj为邻居节点数。

本文结合节点竞争半径Rc，采用非均匀分簇的思想，降低靠近汇聚节点的簇的规模，以避免“热区”问题。竞争半径Rc计算公式如式(7)所示：

(7)

其中，d(i,Sink)为节点i到Sink的距离，c为取值控制参数。确定了成为簇首的竞争条件，即相邻簇首互不在对方的竞争半径内。

所有认知传感器节点按随机次序进行判决，判决思想继承了EAMMH算法轮的概念。簇首数根据文献[17]提供的动态选举思想进行确定。簇首选举概率公式结合了节点剩余能量、节点密度因子ρ和节点距离因子α，选举较优候选簇首。簇首选举概率计算公式如式(8)所示：

(1-β)[τρ+(1-τ)α]

(8)

其中，β为能耗因素占比权重系数，τ为节点密度因素占比系数，β与τ可以根据实际需求更改，本文算法均取值0.5。根据式(8)，剩余能量多、邻居节点密度大、距离汇聚节点近的节点有更高的候选簇首当选概率。E(i)为节点剩余能量，Ei(0)为该节点的初始能量，Etotal为节点能量和，Ea为当前轮次节点理论剩余能量平均值，Etotal和Ea的计算方法分别如式(9)和式(10)所示：

(9)

Ea=Etotal(1-r/rmax)/N

(10)

其中，r为网络当前测试轮次，rmax为最大测试轮次。在选举候选簇首时，节点生成一个0～1的随机数，若该随机数小于该节点阈值，则该节点担任候选簇首。EMMCH算法中的节点阈值计算公式如式(11)所示：

(11)

k=P(t)×N

(12)

其中，G(t)为当前普通传感器节点集合，即，担任过簇首的节点不重复成为簇首。

将全部通过判决的节点定义为候选簇首。随后，认知传感器节点独立监测无线传输环境并通过频谱感知方法中的能量检测算法找到频谱空穴信息。设可用信道数为C，Vi(t)为t时刻节点i的信道可用性向量：

i≤c≤C

(13)

对特定信道中的主用户活动的预测会为该信道提供更准确的判决信息，因此节点i在t时刻的预期信道可用性定义如式(14)所示：

(14)

(15)

其中，Ni是节点i的邻居节点集合，ei是其剩余能量，γij(t)是在时刻t节点i的邻居节点j的相对频谱可用性，其计算公式如式(16)所示：

(16)

其中，min是最小值运算符，*表示内积。据此，频谱能量等级最高的候选簇首担任簇首。

每个非簇首节点根据其到各个簇首(CHs)的距离入簇。在确定CH并形成簇之后，启动路径建立过程。每个CH在公共控制信道上广播CH路由请求(CH-RREQ)消息。当成员节点si从其CH接收到CH-RREQ消息时，若该消息是重复的，则丢弃该消息;否则，若满足以下条件，则广播该消息：

(1)成员节点si到接收器的距离比发送节点ss到接收器的距离短，即d(si，Sink)

(2)剩余能量高于平均水平，即E(si)>Eth,保护低能量的节点不参与路由过程。

(3)发送节点ss和接收节点si之间至少有一个公共空闲频率信道。

如果满足上述所有条件，则si将CH-RREQ转发给其邻居节点;否则，丢弃该消息。 以这种方式，其他簇结构的成员在公共控制信道上接收CH-RREQ，并且如果满足以上条件则将其转发到其CH。重复此过程，直到接收器收到消息。接收器收到消息后，将路由应答(RREP)消息返回原CH，此消息包含组成路径的节点的ID号以及这些节点之间的距离。

随后，CH在所有接收到的可用路径中选择最佳路径。选择依据为路径的通信成本D：

D=Cost×Unbalance

(17)

其中，Cost表示传输成本，由于能量消耗取决于发射器和接收器之间的距离，因此传输成本可以定义为：

(18)

其中,Wj是节点sj-1和sj之间距离的平方，L是由集合{s0，s1，…，sL}表示的路径中的节点总数，sL表示接收器。Unbalance表示路径的不均衡程度，代表路径上的节点之间能量消耗的变化，其定义如式(19)所示：

(19)

CH选择D最小的路径为传输数据包的路径，使整体能量消耗更小、更均衡。

定义φ为节点死亡收敛速率，在保证网络生命周期的前提下，在某一段时间内，节点的死亡速率越高，网络的稳定性越好。节点死亡收敛速率如式(20)所示：

(20)

其中，ω和θ表示在网络运行时间tω和tθ内死亡的节点比率。在θ不变的情况下，越长的tθ代表越长的网络生命周期。若ω和θ不变，tω和tθ之间的差值越小，网络能量消耗越均衡。

各节点间的剩余能量差别的大小可直接反映网络能耗的均衡程度。定义节点剩余能量标准差σ如式(21)所示。σ越小，说明各节点之间剩余能量差别越小，即网络能耗越均衡。

(21)

4 仿真结果分析

本节将EMMCH算法与EAMMH算法、LEAUCH算法、结合能量改进SEP算法的EC-SEP算法和适用于CRSN的改进算法CSEP进行仿真实验并对比讨论。仿真对比了网络的生命周期、节点平均剩余能量、节点死亡收敛速率、传输数据量及网络监测范围大小的影响等方面。

设置仿真模拟节点数为100，节点随机部署在监测区域内。其他仿真参数设置如表1所示。

Table 1 Simulation parameter settings

首先，设置各算法节点总数、总能量相同，讨论监测区域范围大小对EMMCH算法及其他算法的网络生命周期影响程度，仿真结果如图1所示。

Figure 1 Comparison of the influence of the monitoring area

从图1中可见，EMMCH算法在监测区域边长为80 ～140 m时，始终有较长的网络生命周期且受检测区域面积变化影响不大。检测区域边长的增加意味着数据传输距离的增加，代表着更高的传输消耗。在监测区域为60 m×60 m时，EMMCH算法网络生命周期要短于LEAUCH算法；在监测区域为200 m×200 m时，EMMCH算法网络生命周期与CSEP算法的接近；在监测区域边长为80～140 m时，EMMCH算法的网络生命周期约为CSEP算法的1.22倍，约为EC-SEP算法的1.54倍，约为LEAUCH算法的2.86倍。

设置相对均衡的网络监测区域为100 m×100 m，网络生命周期仿真对比如图2所示。

Figure 2 Comparison of network life cycle

如图2所示，在不考虑延迟和可靠性的情况下，保持各算法参数一致，EMMCH算法具有更长的网络生命周期，节点能量耗尽轮次最为接近，说明网络消耗均衡性更高。可见，EMMCH算法具有更高的网络实用性和稳定性。

Figure 3 Comparison of average remaining energy of nodes

节点平均剩余能量仿真结果如图3所示。从图3可见，各算法中节点初始总能量一致，EMMCH算法的节点平均剩余能量最高，说明能耗最低。为讨论算法的稳定性，本文仿真对比了节点死亡收敛速率及节点剩余能量标准差，结果分别如图4～图6所示。

Figure 4 50% node death convergence rate

Figure 5 80% node death convergence rate

Figure 6 Comparison of node residual energy standard deviation

节点死亡收敛速率代表了各节点能量消耗的均衡性。如图4和图5所示，EMMCH算法具有最高的节点死亡收敛速率，说明有节点能量耗尽时开始，EMMCH算法节点死亡速率最大，即各节点能耗更均衡。图6为网络中普通传感器节点的剩余能量标准差对比图。节点剩余能量标准差表示各节点剩余能量的差异，差异越小，消耗越均衡，网络越稳定。由图6可知，EMMCH算法的节点剩余能量标准差最小，说明EMMCH算法具有最高的网络稳定性。

网络中数据传输量对比如图7所示。从图7可知，EMMCH算法具有更长的网络生命周期、更强的网络实用性和更高的数据传输量。

Figure 7 Comparison of data transmission volume

5 结束语

本文基于EAMMH算法提出了一种适用于认知无线传感器网络的分层路由算法——EMMCH算法。该算法根据节点剩余能量、节点的位置因子和邻居节点密度因子改进了簇首选举概率，降低了能量低、位置差、邻居节点少的节点成为簇首的可能性。根据节点的信道可用性向量、预期信道可用性向量和节点剩余能量设计的频谱能量等级选举最优簇首，使簇首选举更为合理。结合节点竞争半径的概念，平衡了“热区域”簇首能量消耗。簇首数依据动态变化的思想，减少了资源浪费。数据传输阶段，簇首节点选取节点剩余能量在平均值之上、距离汇聚节点更近且存在空闲信道的节点进行多跳传输路径规划，再结合由路径消耗和不均衡程度定义的通信成本选取最优路径进行数据传输，使网络中能量消耗更为均衡。

仿真结果表明，EMMCH算法可延长网络生命周期，提高系统稳定性，增加数据传输量，均衡网络能耗。