针对无线传感器节点能量有限的问题，为了延长无线传感网络的生存周期，研究人员提出了许多能量高效的算法^[1]。其中PEGASIS(power-efficient gathering in sensor information system)链式协议^[2]是建立在LEACH(low energy adaptive clustering hierarchy)分簇算法^[3]基础上的改进协议，通过贪婪算法生成一条由所有节点组成的单链，然后由链中的节点轮流担任LEADER节点，并在融合全网数据后将数据发往基站。这种做法可以在最大程度上减少节点的耗能，EEPB(energy-efficient PEGASIS- base protocol)^[4]则是基于PEGASIS协议的改进算法；GAF(geographical adaptive fidelity)^[5]协议是以节点的地理位置为依据的算法，通过把检测区域划分成虚拟的单元格，每个单元格中的节点可以认为是等价的，因此在一个时间段内，一个单元格只需要一个节点实施数据采集，同一单元格内的其他节点可以进入睡眠以节省能量。上述算法的不足主要体现在：PEGASIS中已经加入链的邻居不能被再次访问，因此相邻节点间长链不可避免，且节点轮流当选LEADER策略会导致远离基站的节点过早死亡；而GAF则要求节点配备GPS等额外设备来获取节点地理位置信息，增加了无线传感器节点的制造成本。此外，还有在GAF和PEGASIS的基础上改进的GSSC^[6]协议，该协议同GAF一样把检测区域分成虚拟单元格，格间节点按距离组成多条链，也需要节点拥有全局位置信息。而CRBCC^[7]则是在PEGASIS的基础上并行建成多跳链，链首之间又建链，挑选其中一个链首向基站发送消息，该协议有效地减少了数据传输时延，但节能性略差于PEGASIS。类似的还有CCM^[8]，要求节点均匀地分布在监测区域。在分析各种算法后，本文提出了一种基于轮作和链式的无线传感网络节能路由新算法RPB(rotation and PEGASIS-based protocol)。

1 无线传感网络随机分布模型及覆盖控制

在对协议进行描述之前，先介绍无线传感网络随机分布及覆盖控制模型。参考文献[9]已经证明，在一个k覆盖的网络模型中，如果传感器节点在监测区域${S_{\rm{D}}}$内呈密度分布为$\lambda $的均匀分布，区域内节点个数X的概率服从泊松分布，其概率密度函数为：

$ P\{ X = k\} = {{\rm{e}}^{-\lambda {S_{\rm{D}}}}}\frac{{{{(\lambda {S_{\rm{D}}})}^k}}}{{k!}} $

(1)

由此函数可以得出：如果节点呈泊松分布，当$k = |\lambda |$时取得最大值。

证明：

$ \frac{{P\{ X = k\} }}{{P\{ X = k-1\} }} = \frac{{{{\rm{e}}^{-\lambda {S_{\rm{D}}}}}\frac{{{{(\lambda {S_{\rm{D}}})}^k}}}{{k!}}}}{{{{\rm{e}}^{-\lambda {S_{\rm{D}}}}}\frac{{{{(\lambda {S_{\rm{D}}})}^{k - 1}}}}{{(k - 1)!}}}} = \frac{{\lambda {S_{\rm{D}}}}}{k} $

(2)

如果在单位面积下，假设${S_{\rm{D}}} = 1$，式(2)的值变为$\lambda {\rm{ /}}k$；当$k = |\lambda |$时，取得最大值。

设面积覆盖率${f_{\rm{ \mathsf{ α} }}}$为监控区域被覆盖的百分比，$\lambda (S)$表示区域S内传感器节点数目，已证明它是一个服从以$\lambda (S)$为参数的泊松分布的随机变量，有：

$ P\{ N(S) = K\} = \frac{{{{\rm{e}}^{ - \lambda \left\| S \right\|}}{{(\lambda \left\| S \right\|)}^k}}}{{k!}} $

(3)

式中，$\left\| S \right\|$表示区域S的面积。

对于区域S内的任意一点P，不位于任何传感器节点监测范围的概率为${(1 - {\rm{\pi }}{r^2}\left\| S \right\|)^n}$，其中n为当前网络中节点个数，r为传感器节点的感知半径，有：

$ \begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;P点不被覆盖 = \\ \sum\limits_{k = 0}^{ + \infty } {P\{ N(S) = K\} {{(1 - {\rm{\pi }}{r^2}/s)}^k}} = {{\rm{e}}^{ - \lambda {\rm{\pi }}{r^2}}} \end{array} $

(4)

则区域S内满足任意一点被覆盖的区域，面积覆盖率为：

$ {f_{\rm{ \mathsf{ α} }}} = 1 - P = 1 - {{\rm{e}}^{ - \lambda {\rm{ \mathsf{ π} }}{r^2}}}$

(5)

式中，n为区域面积S内的节点个数。

2 协议描述

RPB协议由3个阶段组成：链路建立阶段、LEADER节点选取阶段和数据传输阶段。

2.1 链路建立阶段

在链路建立阶段，基站广播hello消息，节点应答后基站即获取全网信息，如节点ID、存活状况、节点到基站的距离等，此时当一个节点收到其他节点发送给基站的信息时，可以通过键值对的方式记录所有其他节点的ID及这些节点与自己的距离。然后，基站广播最远节点(END)的ID并从离基站最远的节点开始建立链路，END节点在记录中寻找距离自己最近的未加入链的节点，通过发送数据量很少的请求消息让目标节点加入链中，其中，请求消息含有当前已经加入链路的节点个数，其他节点监听到该消息时更新自己的链路信息，如果监听到的请求消息信息与自身记录信息不符，可通过询问邻居节点的方式获得当前链路。

假设已经有$i - 1(i > 1)$个节点在链中，节点i是最靠近节点还没加入链的节点，节点i在收到节点发送的请求消息时，在已经加入链的节点中寻找离自己最近的节点，假设为节点j，节点i和节点j之间距离为${d_{ij}}$。

比较${d_{{\rm{threshold}}}}$和${d_{ij}}$(${d_{{\rm{threshold}}}}$与节点传感器的感知半径r有关，通过仿真实验，可选取${d_{{\rm{threshold}}}} = 2r/5$，该值也可以由用户选取，值越大，一轮里进入休眠的节点越多，但网络覆盖率越低)：

1) 如果${d_{ij}} > {d_{{\rm{threshold}}}}$，则节点i将通过与节点j直接相连的方式加入链中，同时对发出请求消息的节点作出已经加入链路的应答，然后节点i继续在未加入链的节点中寻找离自己最近的节点。

2) 如果${d_{ij}} \le {d_{{\rm{threshold}}}}$，那么节点i向节点j发送消息告诉节点j自己将在下一轮接替节点j工作，同时对发出请求消息的节点i作出拒绝加入链路的应答；然后节点i设定定时器并进入睡眠并确保在下一轮建立链路之前醒来(在没有大量节点加入或者退出的情况下，每一轮建立链路和数据发送的时间比较稳定，因此可以在第一轮完毕后由基站记录并公布节点休眠的时间长度)，而节点继续在未加入链的节点中寻找除了节点i外距离最近的节点。

3) 如果在节点j附近${d_{ij}} \le {d_{{\rm{threshold}}}}$的节点(本轮进入睡眠的节点)有2个或以上，那么这些在本轮进入睡眠的节点在下一轮都会醒来接替工作(这些节点在下一轮将自己标记为该轮不休眠，无论附近有没有距离小于${d_{{\rm{threshold}}}}$的节点都不会进入休眠)，然后在第三轮节点j醒来，这些节点再次进入睡眠，如此类推。

当节点能量即将耗尽时，为了确保节点留有一定的剩余能量并能在下一个数据发送周期开始前通知邻居，设节点最小剩余能量为${E_{\rm{r}}} = 2{E_{{\rm{BS}}}}$，其中${E_{{\rm{BS}}}}$为节点作为LEADER发送一次数据到基站所消耗的能量，当节点能量小于等于${E_{\rm{r}}}$，节点不再进入睡眠，并通知被接替工作的节点(假设为节点k)，如果节点周围没有剩余能量大于${E_{\rm{r}}}$的节点在下一轮接替其工作，则节点k也不再进入睡眠，每一轮都参加链路建立和数据传输。

RPB协议的链路建立过程如图 1所示。${N_0}$首先向N₁发送加入链路的请求，${N_1}$收到消息后在消息的数据中查找链中有没有除${N_0}$外离自己更近的节点，确认${N_0}$是链中离自己最近的节点后，在自身记录中查找自身到${N_0}$的距离${d_{01}}$，查得${d_{01}} > {d_{{\rm{threshold}}}}$，于是${N_1}$通过直接与${N_0}$相连的方式加入链路，然后${N_1}$向${N_2}$发送加入链路的请求；${N_2}$收到消息后在自身记录中查找自身到N₁的距离${d_{12}}$，查得${d_{12}} \le {d_{{\rm{threshold}}}}$，然后检测自己的剩余能量，测得剩余能量大于${E_{\rm{r}}}$，于是不加入链路并通知${N_1}$将在下一轮接替其工作，设置定时器并进入休眠。${N_1}$收到通知后在自己的表中寻找次近的未加入链的节点${N_3}$并发出入链请求，${N_3}$的处理步骤和${N_1}$相同。在${N_3}$加入链路以后，找到${N_4}$并发送入链请求。N₄收到消息后在其携带的链路信息中找到离自己最近的节点${N_0}$，在自身记录中查找自身到${N_0}$的距离${d_{04}}$，于是${N_4}$通过直接与${N_0}$相连的方式加入链路，在收到${N_0}$的确认消息后，${N_4}$再向${N_1}$发送确认消息及更新后的链路信息。

由该算法构成的链如图 2所示(图中未加入链的带“*”的节点为本轮进入睡眠的节点，带“+”的节点为下一轮将进入睡眠的节点)。

2.2 LEADER节点选取阶段

选取LEADER节点时，参考常用的无线传输能量耗费模型(radio energy dissipation model, REDM)。基于该模型，传输一个k比特的消息，节点消耗的能量为：

$ \begin{array}{c} {E_{{\rm{TX}}}}(k, d) = {E_{{\rm{TX}}-{\rm{elec}}}}(k) + {E_{{\rm{TX}}-{\rm{amp}}}}(k, d) = \\ \left\{ \begin{array}{l} k{E_{{\rm{elec}}}} + k{\varepsilon _{{\rm{fs}}}}{d^2}\;\;\;\;\;d \le {d_0}\\ k{E_{{\rm{elec}}}} + k{\varepsilon _{{\rm{mp}}}}{d^4}\;\;\;\;\;d > {d_0} \end{array} \right. \end{array} $

(6)

式中，${E_{{\rm{TX}}}}(k)$为节点发送k个比特数据损耗的能量；${E_{{\rm{elec}}}}$为电子能量，其值取决于处理单位信号需要经过的数字编码、调制、滤波等因素；${\varepsilon _{{\rm{fs}}}}{d^2}$和${\varepsilon _{{\rm{mp}}}}{d^4}$为由距离决定的模型，当$d \le {d_0}$时，采用自由空间模型，当$d > {d_0}$时，采用多径衰减模型，具体取值将在仿真中说明。

接收该消息需要消耗的能量为：

$ {E_{{\rm{RX}}}}(k) = {E_{{\rm{RX}} - {\rm{elec}}}}(k) = {E_{{\rm{elec}}}}k$

(7)

式中，${E_{{\rm{RX}}}}(k)$为节点接收k个比特数据损耗的能量。参照该模型，基站在每一轮计算每个节点的Q值为：

$ {Q_i} = {w_1}{E_i} + \frac{{{w_2}}}{{{d_{{\rm{BS}}}}(i)}}$

(8)

式中，${w_1}$和${w_2}$为权重值，可以自由选取，满足${w_1} + {w_2} = 1$，由于离基站越远，耗费的能量是距离的平方或者四次方，因此一般有${w_2} > {w_1}$；${E_i}$为节点i的剩余能量；${d_{{\rm{BS}}}}(i)$为节点i到基站的距离。基站在计算出最大Q值的节点后，向全网络广播该节点成为LEADER的消息。按照PEGASIS算法顺序选举LEADER会导致离基站远的节点过早死亡，如取${w_1}$和${w_2}$的值分别为0.2和0.8，则只有当节点j的能量是节点i能量的2.3倍时，节点j才有可能成为LEADER节点，因此离基站越近的节点成为LEADER的可能性远大于远离基站的节点，这使得全网能量消耗趋于均匀。仿真实验表明，当选取${w_1} = 0.1,{w_2} = 0.9$时，协议性能较好。

2.3 数据传输阶段

在数据传输阶段，每个传感器节点调整自身发射功率以便只有最近邻居才能听到，然后进入数据传输阶段。数据传输阶段使用Token(令牌)机制，Token很小，因此在传输过程中耗能较小，其传输过程如图 3所示。END节点C₀首先获得Token，沿着数据链将数据传给C₁，C₁将C₀发来的数据和自身采集的数据进行融合后传给C₂，然后C₂将Token传给端节点C₄；C₂以同样的方式收集到C₄和C₃的数据以后与自身采集的数据融合，沿着LEADER节点方向将数据传到C₅^[10]。

LEADER节点以同样方式收集到所有数据并进行融合后发送到基站，至此一轮数据收集结束。在该轮进入休眠的节点此时醒来，被接替工作的节点设定定时器并进入睡眠，协议从链路建立阶段的“基站广播hello消息，节点应答后基站即获取全网信息”这一步骤之后重新开始下一轮数据传输。

3 仿真实验

结合上述覆盖模型，通过MATLAB以不同的密度将无线传感器节点部署在不同的场景中，并改变${d_{{\rm{threshold}}}}$的值，观察其面积覆盖率。其中传感器节点的感知半径r由传感器本身性能决定。本文假设r=0.8，对每个场景下的不同节点总数分别进行500次节点随机撒播模拟，并取在一轮里面工作节点的平均个数(结果统一向下取整)，得到的数据如表 1和表 2所示。

当所有节点在一轮里全部投入工作，即其最大面积覆盖率对应25、50和100个节点分别为86.6%、98.2%和99.97%。

当所有节点在一轮里全部投入工作，即其最大面积覆盖率对应50、100、150和200个节点分别为63.39%、86.6%、95.09%和98.2%。

可见，随着${d_{{\rm{threshold}}}}$的增大，在某一轮里可以进入睡眠的节点增多，其面积覆盖率就会减少。在保证一定面积覆盖率的情况下，通过分析表 1和表 2的数据，选择${d_{{\rm{threshold}}}} = 2r/5$比较合理，当然也可以根据用户需求设定具体的值。

3.1 仿真场景及参数

本文在100 m×100 m的场景中随机放置了100个节点，其中基站的位置为(50, 300)，其他具体仿真参数如表 3所示。

3.2 不同协议性能对比分析

通过MATLAB分别对LEACH、PEGASIS、EEPB(a为定义距离门限时用户自定义的系数，本文取值1.2)和RPB进行仿真对比，得到的结果如图 4所示，其中轮数越大表示网络的生存时间越长。

从存活节点图可以看出链式协议比簇类协议在减少能量消耗、延长网络生命周期方面的优势较为突出，而通过轮作的策略使得RPB比EEPB的生存时间延长了15.04%，比PEGASIS的生存时间延长了28.72%，比LEACH的生存时间延长了115%，其中RPB优于EEPB的部分主要为休眠节点所贡献。

表 4为死亡节点占所有节点不同百分比下的协议轮数对比，可见RPB首个死亡节点出现比EEPB早，这是由于选取链首的策略不一样造成的。死亡节点占10%时出现的轮数比EEPB延后了11.3%，而死亡节点占50%以及死亡节点占100%时，RPB相对EEPB延后了14.6%和15%。

图 5为网络的剩余能量图，从网络能量消耗曲线可以看出，LEACH的斜率较大，曲线较陡，PEGASIS次之，EEPB和RPB的曲线斜率较小也较为平缓。由此可见，在一定时间内，链式协议的剩余能量明显多于分簇式协议的剩余能量。以EEPB和RPB参照节点能量来选择LEADER节点，因此消耗曲线看似一条直线，而LEACH和PEGASIS则以概率或者轮流的方式来选择簇头或者链首，因此消耗曲线在剩余能量较低的地方斜率会发生变化，这是因为远离基站的节点此时都已经死亡，只剩下离基站近的存活节点在工作。

3.3 改变节点数量n时不同协议性能对比分析

通过MATLAB分别对LEACH、PEGASIS、EEPB和RPB在不同节点数量n时的性能进行仿真和对比分析，其结果如图 6所示。

分析图 6的数据可得，当n改变时，基于分簇的LEACH协议由于节点并没有分摊将数据发送到基站所消耗的能量，因此在存活时间上没有改善，而链式协议由于节点分摊了将数据发送到基站所消耗的能量，因此存活时间得以延长。通过协议间比较可以发现，当n=100时，RPB比EEPB的存活周期延长了15.04%，比PEGASIS延长了28.72%；当n=150时，RPB比EEPB的存活周期延长了23.63%，比PEGASIS延长了39.35%；当n=200时，RPB比EEPB的存活周期延长了39.1%，比PEGASIS延长了54.89%。可见，随着监测区域中节点密度的提高，可以进入休眠的节点也随着增加，休眠轮作调度的优越性也渐渐显示出来。

4 结论

结合无线传感网络节点被密集撒播的特点，对某些感知范围被其他节点完全或绝大部分覆盖的节点实行休眠轮作调度策略，以及改变节点加入链的条件和LEADER节点的选取策略，可以进一步实现减少节点能耗，从而为保证一定覆盖率的前提下实现最大限度减少节点耗能提供了一种解决方案。对实时性不高，节点撒播较为密集且需要持续长久地监测目标的场合，其优势比较明显。