0 引言

近年来，随着一些实际应用的需要，如野生动物生活规律监测^[1]、牧区牲畜监测、移动目标跟踪^[2]、城市车联网等，由这些移动物体携带传感器在移动的过程中常常会出现“大世界小世界”^[3]的聚集现象，从而形成多个偶有联系的区域(社区)。传感器节点拥有的能量有限且能量消耗完便无法参与数据收集、传输等过程。如何延长网络生命周期一直是无线移动传感器网络(Mobile Wireless Sensor Network, MWSN)研究的难题。

层次路由通过分簇在一定程度上缓解了节点能耗不均衡的问题。文献[4]结合改进的粒子群聚类算法与群集间路由算法，提出了一种自适应高能效分簇路由协议(Adaptive Energy-Efficient Clustering Routing Protocol, AECRP)。在初始化阶段，根据节点能量、簇内分布和簇的分布情况提出了基于粒子群算法的分簇方法；在稳定阶段传输数据。为了避免靠近基站的簇能量消耗过快，AECRP为基站附近的簇首设置了能量阈值E，若此类簇首剩余能量低于E时不再转发任何消息。文献[5]结合混合压缩感知(Compressed Sensing, CS)理论提出了基于混合CS的无线传感器网络(Wireless Sensor Network, WSN)六边形格状优化分簇路由算法：首先建立基于混合CS的六边形格状WSN分簇模型；然后对全网数据传输次数进行量化分析，并求解混合CS的WSN六边形格状最优分簇半径；最后实现基于混合CS的WSN六边形格状优化分簇路由算法。层次路由虽在一定程度上缓解了节点能耗不均衡的问题，但并未考虑节点的移动性。

分簇路由大都假设节点的位置固定，并未考虑节点的移动性。为了实现移动节点间的数据传输，文献[6]提出了传染病路由(Epidemic Routing)，其采用洪泛的转发机制。在节点缓存和能量充足的场景下，Epidemic路由可达到较好的网络性能，但在能量受限的移动传感器网络中，泛洪转发策略会使节点能量消耗太快。之后出现了n-Epidemic^[7]、能量感知的Epidemic路由(Energy-Aware Epidemic Routing, EAER)^[8]、Spray and Focus^[9]、使用历史相遇数据和传递性的概率路由协议(Probabilistic ROuting Protocol using History of Encounters and Transitivity, PROPHET)^[10]等，但文献[8-10]仅仅在Epidemic路由的基础上调整消息副本数，并没有很好地解决节点能耗不均衡的问题。

BUBBLE RAP^[11]使用节点的活跃度建立全局和社区内部的排序表，消息携带者总是选择排名靠前的节点来转发消息。由于BUBBLE RAP采用单拷贝，消息的延时较长，若某节点只在社区内非常活跃，而在整个系统排名时必然排在前面，但它只适合社区内部的数据转发，并不适合社区间的数据转发。IFR(Integrating Forwarding and Replication)^[12]利用节点的中心度将网络中的节点划分为若干社区。社区间采用多拷贝的数据转发方法；社区内采用Epidemic算法。若节点个数增大，消息副本数将迅速增多，节点的能量也会消耗殆尽。文献[13]提出了基于友谊关系的移动社会网络路由(Friendship Based Routing, FBR)，利用节点所具有的多个社会特征提出了社会压力(Social Pressure Metric, SPM)和相对社会压力(Relative Social Pressure Metric, RSPM)两个度量指标。根据SPM和RSPM构造友谊社区，采用消息的单副本传输策略。若网络很庞大，FBR算法的交付率不是最优的。为了提高路由的效率，文献[14]提出了基于社交链路感知路由(Social Link Awareness Based Routing, SLABR)，在社区间采用单拷贝传输机制，总是传输给社会关系强且与目的节点属于同一社区的节点；社区内使用多副本二进制扩散的机制。虽然使用二进制转发机制有效地控制了副本的数量，但是没有考虑社区内节点关系的差异性和节点当前的剩余能量。以上算法大都选择排名靠前的节点作为中继节点，必然加快这部分节点的能量消耗。吴大鹏等^[15]利用消息扩散程度和节点当前剩余能量，并结合节点相遇概率预测方法，提出了能量有效的副本分布状态感知路由机制(Energy Efficient Copy Distributing status aware Routing mechanism, EECDR)，分布式地选择中继节点。随之杨鹏等^[16]提出了节点剩余能量均衡路由(Node Residual Energy Balanced routing, NREB)，根据节点的活跃程度以及当前剩余能量选择转发节点。

为了解决移动传感器网络社区间路由节点能量消耗过快的问题，本文提出了一种社区间能量均衡路由算法(Energy-balanced Routing Algorithm for Inter-community, ERAI)。ERAI将消息传输分为两个阶段：第一阶段，社区间传输，从相遇节点中首先选择下一时刻前往社区与消息的目的社区相同的节点，然后综合考虑节点的剩余能量以及与目的社区相遇情况选择转发节点，不仅均衡了节点的能量消耗，而且缩短了延迟；第二阶段，社区内传输，综合考虑节点的剩余能量及社区内节点间的相遇情况选择转发节点，在均衡节点能耗的同时延长了网络生命周期。

1 社区与能耗模型

本章主要介绍了两部分：社区模型和能量消耗模型。

1.1 社区模型

传感器节点由移动实体携带在移动的过程中常常会出现“大世界小世界”的聚集现象，从而形成多个不同的、偶尔有联系的区域，本文称这样的区域为社区。社区模型作如下假设：

1) 本文中的社区是节点在移动过程中形成的。

2) 网络中的节点都是移动的，且每个节点x有唯一的ID，并且只属于一个社区，表示为C_x。

3) 所有节点的初始能量和缓存大小都是相同的。设置一个能量阈值E_thr，当节点剩余能量小于E_thr时，节点不再参与消息传输。

4) 所有节点之间都是相互信任的，相遇时彼此交换去向信息。

5) 所有节点都能感知自己的剩余能量。

6) 消息携带节点只与其通信范围内的节点交换消息。

7) 社区间不需要摆渡节点，社区之间是通过往返于社区间的节点来交换消息的。

1.2 能耗模型

传感器节点一般由感知单元、处理单元(包括处理器与存储器)和无线通信单元组成，其中无线通信单元^[17]是主要的耗能单元。本文使用文献[18]提出的一阶无线通信能量模型如图 1，忽略节点在感知、计算、存储等过程中的能量消耗，主要考虑发送能耗、接收能耗与探测能耗。

由此可知，传输距离为d，发送k bit的消息，所消耗的能量如式(1) 所示：

$ \begin{array}{l} {E_{{\rm{Tx}}}}(k, d) = {E_{{\rm{Tx}}-{\rm{elec}}}}(k) + {E_{{\rm{Tx-amp}}}}(k, d) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ \begin{array}{l} k{E_{{\rm{elec}}}} + k{\varepsilon _{{\rm{f}}s}}{d^2}, \;\;\;\;\;d < {d_0}\\ k{E_{{\rm{elec}}}} + k{\varepsilon _{{\rm{mp}}}}{d^4}, \;\;\;\;d \ge {d_0} \end{array} \right. \end{array} $

(1)

其中：d₀为距离阈值，E_elec表示发送或接收每比特数据时的能量消耗，ε_fsd²和ε_mpd⁴是发送每比特数据放大器的能量消耗。

由于移动传感网利用节点移动带来的相遇(在彼此通信范围内)机会传输数据，距离较短，因此本文仅考虑d < d₀的情况。

节点接收k bit的消息所消耗的能量如式(2) 所示：

$ {E_{{\rm{Rx}}}}\left( k \right) = {E_{{\rm{Rx-elec}}}}\left( k \right) = k{E_{{\rm{elec}}}}\left( k \right) $

(2)

中继节点转发k bit的消息，首先要接收k bit的消息，然后将收到的消息发送出去，因此，转发k bit的消息所消耗的能量如式(3) 所示：

$ \begin{array}{l} {E_{{\rm{RTx}}}}\left( k \right) = {E_{{\rm{Tx}}}}\left( {k, d} \right) + {E_{{\rm{Rx}}}}\left( k \right) = k{E_{{\rm{elec}}}} + k{\varepsilon _{{\rm{fs}}}}{d^2} + k{E_{{\rm{elec}}}} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2k{E_{{\rm{elec}}}} + k{\varepsilon _{{\rm{fs}}}}{d^2} \end{array} $

(3)

节点探测能耗是指节点在移动的过程中探测周围以发现其与哪些节点相遇所消耗的能量^[15]。节点在移动的过程中周期性地广播探测分组(DEtection GRouping, DEGR)(如图 2(a)所示)，收到DEGR分组的节点回复确认分组(COnfirm GRouping, COGR)(如图 2(b)所示)。令节点发送DEGR和接收COGR所消耗能量相同，设为ed，节点的探测周期为T_c，c_i为第i次探测接收COGR的个数。在t时刻，移动节点广播DEGR的次数是一定的，接收COGR的个数越多，E_de值越大，则E_de的计算公式如式(4) 所示。

图 2分组格式中各字段的含义如下：NOP表示协议版本信息；N_id为发送节点ID；C_Nid为发送节点所属社区；E_res为发送节点剩余能量；C_goi为发送节点即将前往社区；N_b广播ID；D_{Nid, Cid}表示目的节点为N_id，所属社区为C_id。

$ {E_{de}} = \sum\limits_{i = 1}^{t/{T_c}} {({c_i} + 1)} * ed $

(4)

综上，时刻t节点x消耗的总能量E_c^x(t)和剩余能量E_res^x(t)如式(5)~(6) 所示：

$E_c^x(t) = \sum\limits_{t = 0}^t {{E_{{\rm{Tx}}}}} (k, d) + \sum\limits_{t = 0}^t {{E_{{\rm{Rx}}}}} (k) + {E_{de}}$

(5)

$E_{{\rm{res}}}^x(t) = {E_{{\rm{init}}}} - E_c^x(t)$

(6)

其中E_init为节点的初始能量。

2 ERAI路由算法描述

移动传感网中节点间的相遇总是短暂的，利用节点间短暂的接触特性转发消息。本章主要从以下4部分描述ERAI路由算法：路由度量指标、社区间消息传输、社区内消息传输和ERAI流程。

2.1 路由度量指标

根据节点的相遇信息和当前拥有的能量提出了转发能力(Forwarding Capacity, FC)，即作为中继节点转发消息的能力。另外相遇概率(Encounter Probability, EP)表示节点与社区或社区内的节点间联系强度。

2.1.1 相遇概率EP

1) 节点与社区的相遇概率。

在周期T内，t时刻节点x与社区C_y内的节点相遇，EP_t(x, C_y)的计算过程如式(7) 所示：

$E{P_t}(x,Cy) = E{P_{t - 1}}(x,Cy) + (1 - E{P_{t - 1}}(x,{C_y}))/\Delta t$

(7)

其中：Δt表示在周期T内，节点x与社区C_y内的节点相遇的时间间隔，即Δt=t_c-t_c-1，t_c是当前相遇时刻，t_c-1为最近一次相遇时刻。

若在周期T内节点x与社区C_y内任何节点都没有相遇，EP_t(x, C_y)的值也会随着Δt的增大而减少，如式(8) 所示：

$ E{P_t}(x,{C_y}) = E{P_{t - 1}}(x,{C_y})*{\lambda ^k} $

(8)

其中，λ∈[0, 1]，k=⌊Δt/T⌋，Δt=t-t_c-1，t为当前时刻，t_c-1为最近一次相遇时刻。

2) 社区内节点间的相遇概率。

同一社区内的节点x与y相遇，更新概率度量值EP_t(x, y)，如式(9) 所示：

$E{P_t}(x,y) = E{P_{t - 1}}(x,y) + (1 - E{P_{t - 1}}(x,y))/\Delta t $

(9)

其中，Δt表示在周期T内，节点x与节点y前后两次相遇时间间隔，即Δt=t_c-t_c-1，t_c是当前相遇时刻。

若在周期T内节点x与y没有相遇，EP_t(x, y)将随着Δt的增大而减小，具体计算公式如式(10) 所示：

$ E{P_t}(x,y) = E{P_{t - 1}}(x,y)*{\lambda ^k} $

(10)

其中，λ∈[0, 1]，k=⌊Δt/T⌋，Δt=t-t_c-1，t为当前时刻，t_c-1为节点x与节点y最近一次相遇时刻。

2.1.2 转发能力FC

由于节点x时刻t剩余能量E_res^x(t)与概率度量指标的量纲不同，利用线性归一化公式将E_res^x(t)变换成无量纲的值如式(11) 所示：

$ E_u^x(t) = \left( {E_{{\rm{res}}}^x(t) - {E_{{\rm{thr}}}}} \right)/\left( {{E_{{\rm{init}}}} - {E_{{\rm{thr}}}}} \right) $

(11)

其中：E_res^x(t)节点x时刻t剩余能量；E_thr为节点能量阈值，当E_res^x(t)≤E_thr时，节点x不再参与消息转发；E_init为节点的初始能量。

根据节点相遇信息和节点当前拥有的能量计算FC。节点x与社区C_y的转发能力FC(x, C_y)的计算公式如式(12) 所示；在相同社区内，节点x与节点y的FC(x, y)计算公式如式(13) 所示：

$ FC(x,{C_y}) = \beta E{P_t}(x,{C_y}) + (1 - \beta )E_u^x(t) $

(12)

$ FC(x,y) = \beta E{P_t}(x,y) + (1 - \beta )E_u^x(t) $

(13)

其中，β为权重因子，β∈(0, 1)。

2.2 社区间消息传输

消息携带者与目的节点隶属于不同的社区，消息成功投递到目的节点所在社区是社区间消息传输的关键。当消息携带者与目的节点的社区不同时，将执行社区间消息传输，具体步骤如下。

步骤1  节点x携带消息m移动，目的节点为d。在t时刻与节点x_i(i=1, 2, …, n)相遇。

步骤2  节点x_i中是否有前往C_d社区的，若有，跳转到步骤3；否则，跳转到步骤1。

步骤3  相遇节点中对前往C_d社区的节点计算FC(x_i, C_d)，若max(FC(x_i, C_d))>FC(x, C_d)，节点x将消息m转发给x_i；否则，跳转到步骤1。

ERAI：社区间消息传输。

当节点x携带消息m(目的节点d)与节点x_i(前往社区C_goi)相遇时

Begin

1)   for each x_i do

2)     if C_goi=C_d then

3)       if max(FC(x_i, C_d))>FC(x, C_d)

           then

4)         x.SendMessageTo(x_i)

5)       end if

6)     end if

7)   end for

End

ERAI路由算法中社区间消息传输过程的时间开销主要是FC的计算开销。根据FC计算过程，节点需分别计算节点与目标社区的相遇概率以及节点当前拥有的能量。对于节点与目标社区相遇概率的更新，需计算前后两次相遇的时间间隔，时间复杂度为O(1)；同理，在更新节点当前剩余能量中，节点需计算网络从运行到当前时间发送与接收消息的总数，时间复杂度为O(1)。由于节点FC是由节点与目标社区的相遇概率与当前剩余能量线性相加而得，算法中语句执行次数为常数，因此ERAI执行一次社区间消息传输的时间复杂度为O(1)，转发n个消息的时间复杂度为O(n)。由此看出，ERAI具有较高的执行效率。社区间消息传输算法能够正确执行社区间的消息传输。

2.3 社区内消息传输

若消息进入目的社区，节点将实施社区内消息传输。

假设在社区内，节点x携带消息m，目标节点为d，且C_x=C_d。在t时刻，节点x与x_i(i=1, 2, …, n)相遇，消息传输过程如下所示：

1) 若x_i=d，即相遇节点中存在目标节点d，则节点x将消息m转发给节点x_i，并广播消息m的ACK。

2) 若x_i≠d且max(FC(x_i, d))>FC(x, d)，则节点x将消息m直接转发给节点x_i，并将m从缓存中删除；否则，节点x节点消息m继续移动，直到下一个相遇机会。

ERAI：社区内消息传输。

当节点x携带消息m(目的节点d)与节点x_i相遇

Begin

1)   for each x_i do

2)     if x_i= =d then

3)       x.SendMessageTo(x_i)

4)       x.deleteMessage

5)     else

6)       if max(FC(x_i, d))>FC(x, d) then

7)         x.SendMessageTo(x_i)

8)         x.deleteMessage

9)       end if

10)     end if

11)   end for

End

ERAI路由算法中社区内消息传输过程的时间开销主要是FC的开销。根据节点FC计算过程，节点需分别计算节点与目的节点的相遇概率以及自身当前剩余能量。对于节点与目的节点相遇概率的更新，需计算前后两次相遇的时间间隔，时间复杂度为O(1)；同理，在更新节点当前剩余能量中，节点需计算网络从运行到当前时间发送与接收消息的总数，时间复杂度为O(1)。由于节点FC是由节点与目的节点的相遇概率与当前剩余能量线性相加而得，算法中语句执行次数为常数，因此ERAI执行一次社区内消息传输的时间复杂度为O(1)，转发n个消息的时间复杂度为O(n)。由此看出，ERAI具有较高的执行效率。社区内消息传输算法能够正确执行社区内的消息传输。

2.4 ERAI流程

ERAI路由算法分为社区间和社区内消息传输。节点s携带消息m移动，首先比较C_s与C_m是否属于同一社区，若属于同一社区将执行社区间消息传输过程，否则执行社区内消息传输过程。ERAI流程如图 3所示。

3 仿真结果与性能分析

本文主要从网络中首个节点消亡时间、节点剩余能量均方差(Residual Energy Mean Square Error)、节点消亡数以及数据包交付率(Packet Delivery Ratio, PDR)四个指标评估ERAI路由算法的性能。节点剩余能量均方差与PDR的计算公式如式(14)~(16) 所示。

节点剩余能量平均值(average residual energy)：

$ E_{\rm{avg}}(t) = \frac{{\sum\limits_{i = 1}^N {节点i在t时刻的剩余能量} }}{{网络中节点的总个数N}} $

(14)

节点剩余能量均方差：

$ \sigma \left( t \right) = \sqrt {\frac{{\sum\limits_{i = 1}^N {{{\left( {节点i在t时刻的剩余能量 - {E_{{\rm{avg}}}}\left( t \right)} \right)}^2}} }}{N}} $

(15)

数据包交付率(PDR)：

$ PDR{\rm{ = }}\frac{{成功投递的消息个数}}{{消息总数}} * 100{\rm{\% }} $

(16)

3.1 仿真环境设置

本文采用ONE(Opportunistic Network Environment)^[19]对ERAI的性能进行仿真，并和机会网络中Epidemic和PROPHET路由进行了对比。假定场景中有300个移动节点，在4 500 m×3 400 m区域内移动。假设300个节点被分为8个组(社区)分别用C₁~C₈表示，每个社区的节点数为[30,90]。每个节点的通信半径为50 m，消息的存活时间(Time To Live, TTL)为3 600 s。由于实验需要节点间相遇的历史信息，仿真开始时先进行了900 s的预处理过程。具体仿真场景设置如表 1所示。

3.2 实验结果与分析

1) 首个节点消亡时间比较。

图 4所示，在相同初始能量下，ERAI路由算法中首个节点消亡时间最迟。由于Epidemic采用洪泛转发策略，大量相同的数据副本重复扩散将导致节点能量消耗速度提高，而PROPHET路由机制总是将消息传输给概率值高的节点进行数据转发，一直使用概率值高的节点必然使这部分节点能量消耗速度高于其他节点，提高了这部分节点消亡速度。而ERAI路由算法考虑了节点剩余能量，避免使用剩余能量较低的节点转发数据，延迟了节点消亡时间，从而延长网络的生命周期。ERAI路由算法下网络中首个节点消亡时间相比Epidemic与PROPHET路由算法分别延迟了12.6%~15.6%和4.5%~8.3%。

2) 节点剩余能量均方差比较。

图 5显示，在仿真时间相同时ERAI的节点剩余能量均方差值最小，说明节点剩余能量集中。由于ERAI充分考虑了节点的剩余能量，避免能量低的节点过早失效，与Epidemic和PROPHET相比ERAI中各节点的能量消耗较均衡。

3) 节点消亡数比较。

从图 6可以看出，随着仿真时间的流逝，网络中节点消亡数都是逐渐增加的，但在相同仿真时间下ERAI的节点消亡数是最少的。由于ERAI在选择中继节点时均衡了节点的能量消耗，延迟了节点消亡的时间，在一定程度上延长了网络的生存周期。

4) 交付率比较。

从图 7可以看出，在仿真开始时，节点拥有充足的能量和缓存，Epidemic展现了最好的性能，但是随着时间的流逝，ERAI具有较高的PDR。这是由于Epidemic采用洪泛机制，大量副本的转发加快了节点的能量消耗和缓存空间占据，而ERAI不仅均衡了节点的能量消耗，避免节点因能量不足或失效而丢弃消息，并考虑了节点前往社区和节点间的相遇频繁程度，增大了PDR。

4 结语

本文针对移动传感器网络中社区间路由节点能量消耗过快的问题，提出了一种移动传感网社区间能量均衡路由算法(ERAI)。首先考虑了节点的去向信息，然后结合节点当前剩余能量和相遇情况，选择转发节点。大量实验验证，ERAI在一定程度上均衡了各节点的能耗，延长了网络的生命周期。未来的主要工作是采用机器学习方法预测移动节点下一时刻前往的社区，优化节点在消息传输过程中的能量消耗，延长网络生命周期。