(1)基站和传感器节点的位置是固定的。所有节点以密度 ρ均匀分布在该区域中,并通过交换信息来识别自身和基站的地理位置。

(2)每个节点拥有一个唯一标识符(ID)。所有节点的初始能量相同且传输能量可控。在最高能量级状态下,节点可以直接与基站通信。

(3)链路是对称的。如果传输能量已知,节点可以根据接收到的信号强度来估算到另一个节点的距离。

(4)所有节点以相同的固定速率进行感知且不间断地向用户发送数据。每个数据包的长度相等。

采用经典能耗模型^{[ 5]}进行计算。将一个 l比特的消息传输距离 d消耗的能量为:

式中: E_elect表示发送或接收1 bit的数据消耗的能量; ε_fs和 ε_amp分别表示由发送者和接收者间的不同距离决定的放大1 bit数据所消耗的能量。如果该距离小于一个阈值 d₀,使用自由空间模型(fs);否则,使用多径模型(mp)。

接收该消息所消耗的能量为:

聚合该消息所消耗的能量为:

式中: E_agg表示聚合1 bit的数据消耗的能量。

用 E_MAX表示节点剩余能量的阈值。如果一个节点的剩余能量小于该值,它将放弃竞选簇头节点。根据等式(1)(2)(3),可以得到 E_MAX的值:

式中: φ表示每一轮获取数据的次数; θ表示聚合数据的压缩比例; d表示当前处理节点和它下一跳节点间的距离; λ表示一个节点的邻居数。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 分层的网络拓扑结构Fig.1 Level structure of network topology

基本的成簇算法在划分簇时不考虑能量的消耗,大致可以分为均匀分簇和不均匀分簇两大类。EESA从能量消耗的角度出发,对分簇方式进行了改进。如图1所示,假定一个实验网络拥有 Y个不同规模的簇层,且每个簇的成员节点都向簇头传送1 bit的数据。为方便计算,我们将位于两个不同层次的簇之间的传输距离看作是它们的半径之和(第1层除外)。也就是说, Y层到 Y-1层的传输距离为( r_y+r_y-1), Y-1层到 Y-2层的传输距离为( r_y-1 +r_y-2)等(图2)。由于最外层(第 Y层)的簇头节点没有中继任务而只负责处理本簇内节点传输的数据,它的总能耗可以表示为:

第1项表示簇头节点接收本簇内成员节点发送数据的能耗;第2项表示进行数据聚合的能耗;第3项表示将处理后的数据从第 Y层传输到第 Y-1层的能耗。由于第 Y-1层的簇头节点不仅要考虑本簇内节点传输的数据,还要对中继的 Y层数据进行处理,它们消耗的总能量可以表示为:

同理,第 Y-2层的簇头节点要同时对本簇内和中继的第 Y-1层的数据进行处理,所消耗的总能量可以表示为:

通过这种方式,每一层的簇头节点消耗的总能量可以通过下式计算得到:

其中 r₁, r₂,…, r_y分别表示第1层,第2层,…,第 y层的簇半径; r表示第1层到基站的传输距离(见公式(12)); E_i(1≤ i≤ y)表示第 i层的簇头节点消耗的能量。

由于假定每一层的簇头消耗的能量基本相等,可以用下式来计算每一层的簇半径:

根据式(8)(9),计算得到所有的簇半径,簇划分完成。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 簇半径的计算Fig.2 Calculation of cluster radius

为了减轻簇头的负载,不同于以往的单个簇头选举策略,EESA同时选举两个不同的节点——处理节点和转发节点作为簇头节点(见图3)。通过任务分离,

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 簇头节点选举Fig.3 Election of cluster heads

将单个簇头的任务分配给两个节点完成,以减小簇头和簇内成员节点之间的能耗差。选举结束后,结合2.1节计算得到的簇半径,完成簇的形成过程。簇头节点传输模式如图4所示。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 簇头节点传输模式Fig.4 Transmission mode of cluster heads

2.2.1 处理及转发节点选举

在每一轮的开始,每个节点都会在其通信半径范围内广播基本消息 E_Msg( IDs, E_rs, L( x_s, y_s))。 E_rs和 L( x_s, y_s)分别表示节点 s的剩余能量和位置。所有处在广播源半径范围内的节点都被看作是邻居节点,并在接收到广播消息后更新自己的邻居信息表。每个剩余能量大于 E_MAX的节点都有机会参与选举并成为候选节点,假定候选节点所占比例为 p。以第 j层为例(1≤ j≤ Y),簇头的选举过程如下:

每个候选节点 s都会根据更新后的信息表计算其通信半径范围内所有邻居节点的平均剩余能量 E_res:

s和其邻居节点间的平均通信距离可以表示为:

用 d_sm来表示节点 s和 m之间的距离,则:

同时考虑到剩余能量和距离,每个候选节点分别应用等式(13)(14)来计算处理节点和转发节点的竞争指标值:

其中 μ和 τ的值是由簇内的节点分布及剩余能量情况决定的。 d( s, BS)表示节点 s和基站之间的距离。然后,候选节点在其通信半径范围内广播竞争消息 Com_Pro( ID_s, E_rs, CLP_s, CLF_s)。

广播完成后,所有的候选节点都转换为接收状态并等待时间 T。 T的长度设定至少要保证节点可以接收到来自所有邻居节点的竞争消息。之后,每个候选节点将自身和接收到的竞争指标值进行对比。 CLP值最大的节点将成功当选为处理节点,而 CLF值最大的节点将成功当选为转发节点。如果出现两个相等的 CLP或 CLF的最高指标值,拥有较大剩余能量的节点当选。如果一个候选节点同时具备 CLP和 CLF的最高指标值,它将同时扮演处理节点和转发节点这两种角色。

2.2.2 簇的形成

根据对比结果,竞选处理节点成功的节点将在其通信半径内广播竞选成功消息 Suc_Pro( ID_s, E_rs, L( x_s, y_s)),其余节点则等待接收该消息。一旦某个候选节点接收到一个或多个竞选成功消息,它将放弃继续竞争并发送加入消息 Join_Pro( ID_s, E_rs, L( x_s, y_s))到接收信号强度最大的广播节点。由于转发节点只负责转发处理后的数据,因此不需要向其所有邻居节点广播竞选成功消息。它只将竞选成功消息添加到加入簇的数据包信息中,并将其发送给同簇的处理节点(如果转发节点和处理节点为同一节点,该步骤省略)。因此,与已有算法相比,本文提出的新算法不会增加更多的消息负载。此后,处理节点会为所有簇成员分配TDMA时隙。

2.2.3 数据聚合树的构建

在数据聚合树的构建过程中,EESA选择距离当前转发节点最近的两个低层处理节点作为候选中继节点,并将候选节点的剩余能量和转发当前数据需要消耗的能量进行对比,根据对比结果确定中继节点。以第 p层和第 q层(1≤ p<q≤ y)为例,假定 q层的某个簇 u的转发节点要在 p层选择一个处理节点作为中继节点。假定 p层的簇 v和簇 w是离簇 u最近的两个簇。根据等式(1), CLF_u可以计算出它将数据包分别发送到 CLP_v和 CLP_w所消耗的能量差值:

式中: k_u表示簇 u发送的数据量。

同时,计算出节点 CLP_v和 CLP_w的剩余能量差值:

将 ΔE和 ΔE_T进行对比,若 ΔE的值大于 ΔE_T,将选择 CP_v作为中继节点;否则,选择 CP_w作为中继节点。也就是说,距离当前转发节点较远的候选节点只有在它的剩余能量远远大于距离当前转发节点较近的候选节点时,它才可能被选择。每个簇的转发节点都会按照同样的方式找出自己的中继节点,该网络的骨干网形成(见图4)。这种策略不仅考虑了簇头节点的剩余能量,同时考虑了网络总能耗的平衡,因此极大地提高了能量的利用率。

由于EESA的簇头选举过程是消息驱动的,所以首先讨论算法的消息复杂度。

定理1 EESA成簇算法的消息复杂度为 O( N),其中 N为传感器节点总数。

证明 在簇头选举阶段的开始,所有节点共广播 N个基本消息 E_Msg( ID_s, E_rs, L( x_s, y_s))。由于所有剩余能量大于 E_MAX的节点都有机会参与选举并成为候选节点,假定候选节点的比例为 p,则 Np个候选节点产生。所有候选节点共发送 Np个竞争消息 Com_Pro( ID_s, E_rs, CLP_s, CLF_s)。假定选举得到 k个处理节点,则共要发送 k个竞选成功消息 Suc_Pro( ID_s, E_rs, L( x_s, y_s))。相应地,其他普通节点共要发送 N-k个加入簇消息 Join_Pro( ID_s, E_rs, L( x_s, y_s))。由于转发节点只需要将竞选成功消息添加到加入簇数据包中,所以不会产生额外的消息负载。因此,在每轮的成簇阶段需要广播的消息总数为 N+Np+k+N-k=( p+2) N,即 O( N)。

表1给出了EESA与其他同类算法消息复杂度的对比结果。由表1可知,虽然EESA选举两个不同的节点作为簇头,它的消息复杂度并没有增加。所以很明显,EESA的性能要优于其他已有算法。

表1

Table 1

表1(Table 1)

表1 消息复杂度对比 Table 1 Comparison of message complexity 算法 EESA ACT EECA MR-LEACH LEACH 消息复杂度 ( O) N (O)N (O)N (O)N (O)N

表1 消息复杂度对比 Table 1 Comparison of message complexity

定理2 如果两个节点互为邻居,二者在参与簇头选举时不会产生冲突。

证明 假定 S_u和 S_v是两个邻居节点,二者同时参与簇头竞争选举。根据EESA,如果 S_u和 S_v拥有相等的 CLP或 CLF的最高指标值,拥有较大剩余能量的节点当选。在二者的 CLP或 CLF的最高指标值相等且剩余能量相等的情况下,若 S_u首先成为簇头节点,则会发送竞选成功消息通知 S_v, S_v接到消息后会退出竞争成为普通节点。反之亦然。因此,EESA的簇头选举策略不会引起邻居节点间的冲突,选举得到的簇头分布状况良好。

仿真结果由网络仿真器Omnet++实验得出。假定MAC层是理想的且通信链路无误。实验在稳态下进行,仿真参数如表2所示。

表2

Table 2

表2(Table 2)

表2 仿真参数 Table 2 Simulation parameters 参数 值 节点数 98 网络规模/m2 70×140 基站位置/m (40,150) 节点初始能量/J 2 候选节点比例 p 0.3 Eelect(10-9J/bit) 50 εfs(10-12J/bit·m-2) 10 d0/m 100 Eagg(10-9J/bit/信号) 5 数据包长度/bit 500

表2 仿真参数 Table 2 Simulation parameters

4.2.1 网络寿命

应用几种不同算法时的网络寿命曲线如图5所示。从图中可以看出,采用EESA的网络寿命最长。MR-LEACH只根据节点的剩余能量来选择簇头,EECA在选择簇头时同时参照节点的剩余能量和通信距离等因素,但是由于二者没有对多跳通信模式下簇头能量消耗的不均衡性做出改善,部分簇头节点的过早死亡导致了网络寿命的缩短。ACT根据每个簇头的能耗量对簇的规模进行调整,但是同样存在能量洞问题。同时,随着时间的进行,选举得到的簇头节点会逐渐偏离理想位置,使得簇头与簇内成员节点之间的能耗差值迅速增大。而EESA通过计算簇间能耗来确定簇,同时采用任务分离方法减少关键节点的能耗,从而延长了网络的寿命。由此可见,EESA算法能够均衡节点间的能量消耗,对于提高传感器网络的生存时间具有重要意义。

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 网络寿命Fig.5 Network lifetime

4.2.2 平均剩余能量

图6给出了4种算法中节点的平均剩余能量。显然,EESA算法对节点能耗的控制比较好。MR-LEACH,EECA和ACT都采用了多跳通信模式,节点剩余能量的差别在于它们的簇头选举方式和数据聚合树的构建方式不同。在每一轮簇头选举中,

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 平均剩余能量Fig.6 Average residual energy

MR-LEACH直接指定剩余能量最大的节点为簇头,并由基站来确定每个簇头的下一跳节点。EECA在选举簇头时同时考虑了剩余能量和通讯距离两个因素,并通过构建一个由这两个因素关联而成的权值函数来为每个簇头选择最优的中继节点。ACT根据每个簇头的能耗量来计算簇半径,然后选举最接近理想位置的节点作为簇头。同时,按照中继负载等量分配的原则来构建数据聚合树。由此可见,MR-LEACH因缺乏对影响因素的全面考虑而导致了过多的能耗;EECA没有对热点问题做出任何改善,能量洞仍然存在;而ACT则会由于运行后期所选簇头节点远远偏离理想位置而导致能耗的增加。EESA从三个方面改善了热点问题:①根据簇头的总能耗相等来计算簇半径,达到了簇间的能耗平衡;②同时选举两个节点来共同完成单一簇头的工作,通过任务分离减缓了簇内关键节点的能耗;③通过计算差值 ΔE-ΔE_T来构建数据聚合树,实现了整个网络总能耗的平衡。因此,EESA具备最高的能量效用,剩余能量最多。

4.2.3 簇头节点的能耗标准差

如图7所示,由于簇头的选举方式和承担的负载量不同,簇头节点的能耗标准差也呈现出不规则的振荡。在簇头选举过程中,MR-LEACH只考虑节点的剩余能量,EECA算法设计同时参照了节点的剩余能量和通讯距离这两个因素。在多跳通信模式下,每个簇头因负载量不同而消耗不同的能量。所以,MR-LEACH和EECA算法曲线波动较大,簇头节点能量消耗不均衡。ACT根据簇头的能量消耗来计算簇半径,在一定程度上减轻了热点问题。同时,后期维护采用的跨层数据传输模式也使得位于不同层次的簇头拥有相近的能耗量。因此,ACT的算法曲线相对平稳。从图中可以看出,EESA算法的曲线最稳定。这是因为EESA采用簇头节点负载平衡的思想来减轻热点问题,同时,簇头任务的分离降低了簇内关键节点的能耗,避免了能量差异较大的节点出现。

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 簇头能量消耗标准差Fig.7 The standard deviation of energy consumption of cluster leaders

4.2.4 平均剩余能量的变化

图8给出了网络中节点平均剩余能量的变化曲线。本文采用节点平均剩余能量的变化来衡量几种算法能耗的均衡程度。平均剩余能量的变化越小,表明能耗越均衡。由图8可以看出,与其余3种算法相比,EESA的平均剩余能量的变化较小,即获得了更均衡的能耗。这是因为,在采用EECA,ACT,和MR-LEACH这三种算法时,“能量洞”问题明显,距离基站较近的簇头节点常因负载过重而先于其他节点死亡,从而导致了其平均剩余能量变化曲线的振荡。而EESA同时从簇间和簇内能耗平衡角度进行了考虑,有效地缓解了“能量洞”效应,所以平均剩余能量的变化最小。

图8

Fig.8

	Figure Option ViewDownloadNew Window
	图8 平均剩余能量的变化Fig.8 Variance of average residual energy