传统的无线自组织网络(mobile Ad hoc networks，MANETs)中，节点发送数据之前，需要按照所给定的路由协议建立端到端路径，通常，此种网络都假设端到端路径始终存在，但是对于泛在化的个人移动通信系统来说，多种原因将使得端到端路径具有间断连接特性，无法持续地完成信息传输。区别于传统的无线自组织网络，机会网络^[1]中，源节点利用随机运动带来的相遇机会将消息传输给中继节点，进而，再将消息转发给目标节点或其他中继节点，以“存储携带转发”的方式来取代传统自组织网络中的端到端路由。可见，机会网络能够以更加灵活的方式实现数据传输。

针对机会网络的特性，国内外研究人员提出了相应的路由机制。文献[2]提出了一种基于历史相遇频率的路由机制。该机制中采用滑动时间窗统计节点间的平均相遇次数，根据历史相遇信息推断出未来一段时间内的相遇频繁程度，进而自适应地调整消息副本数；该机制并不为了单方面改善消息传输率，而是着眼于网络节点的转发总次数，降低消息延迟和网络负荷量。但没有从理论上界定时间窗长度，反映未来相遇频率的依据不够充分。文献[3]利用节点间的相遇时间间隔在延迟受限的情况下预测节点相遇的个数，源节点和中继节点总是将消息转发给中心性较高的节点，且中继节点独立决策要散发的消息副本数量，从而提高网络的自适应性，但是该机制中的消息副本数的初始化值属于人为设定，没有充分的理论依据。文献[4]提出了基于历史时间间隔的机会网络路由机制，该机制中用历史相遇信息更新节点间相遇时间间隔，当前时间间隔和过去的n个时间间隔存在线性关系，并用于社会网络。该算法利用了社会关系特点，根据节点之间的历史相遇间隔信息来估计节点之间的亲密程度，选择与目的节点关系更亲近的节点作为下一跳节点，从而保证了消息朝着靠近目的节点方向发送，获得更高的消息投递率。但是该机制在社会网络环境中节点相遇的间隔时间不具有随机性，不足以反映社区内部随机相遇特性。文献[5]提出了一个基于概率参数的自适应路由算法。该算法中引入了一个新的估计参数，即连接概率，根据历史连接概率估算当前节点之间连接概率，从而将消息转发给连接概率最大的节点，同时加入了一个自适应消息优先级的缓存管理策略，主要为了提高消息的成功投递率，但是消息平均延迟没有得到较好的改善。

基于节点历史相遇规律，文献[6]提出了一种适用于机会网络的PROPHET路由机制，节点运动过程中保存与其他节点的相遇信息，从而预测到达目的节点的概率。与文献[2]的机制相似，节点之间的可达概率随着两者相遇次数逐渐增加。为了尽可能获得节点与目标节点的相遇概率，PROPHET利用概率传递性来更新与其他节点之间的可达概率，但是，对于间断连接的机会网络来说，PROPHET路由策略存在显著缺点，其所使用的概率传递性没有遵循节点相遇的顺序，因此，在中继节点选择方面，基于历史相遇信息和概率传递性预测未来相遇状态的方法都具有一定的片面性。

众多的机会路由协议采用随机运动模型描述节点运动状态，但是实际上通信设备的使用者并不是总在做随机的运动。泛在化的个人移动通信中，人的活动具有极强的规律性。经过对Infocom会议召开地点迈阿密(2005) 和巴塞罗那(2006)、剑桥大学等多个地点实际测量，结果表明泛在化个人移动通信网络中的节点行为呈现出社会网络学中的“小世界，大世界”现象^[7-10]。显然，以上提到的经典路由机制并不能在社区运动环境下发挥很好的性能，难以应用于未来泛在化的个人通信网络中。根据社会网络学中的“小世界，大世界”现象，文献[11-14]针对运动辅助下的机会网络路由策略进行了研究，但是所提出的机制均需要特殊移动中继节点的支持，适用性受到较大程度的限制。

根据节点访问各个社区的概率估计机会网络中节点间的相遇间隔时间，进而，提出了相遇时间感知的路由机制，选择与目标节点相遇间隔时间较小的节点作为中继节点，以便更准确地选择转发机会。仿真结果表明所提出的相遇间隔时间估计方法比较准确，传输率、延迟以及网络负荷等各方面网络性能得到了有效改善。

1 社区运动模型

根据社会网络中的“小世界，大世界”理论，机会网络的拓扑可以从逻辑上划分为若干个区域，每个区域称为社区，社区内部节点采用短距离无线通信协议进行数据传输，如蓝牙、IEEE802.11等，且网络中的节点具有唯一的归属社区，因此，根据节点运动过程中所处的社区情况，可以将节点划分为两种状态，分别为本地状态和漫游状态。本地状态对应节点的归属社区，当节点处于本地社区的时候，通常在下一个运动周期内以较大的概率处于本地状态，以较小的概率漫游到其他社区；若当前节点处于漫游状态，则以较小的概率继续漫游在其他社区，而以较大的概率回到本地社区。

为了便于对机会网络中的节点移动状态进行分析，所使用的相关参数如表 1中所示

初始情况下，节点随机选择运动参数，方向参数范围为[0, 2π)，速度参数为均匀分布在[V_min, V_max]范围，且各个运动周期所选择的参数具有独立性。对于节点A和B来说，二者在同时运动的情况下的相遇间隔时间期望如式(1) 所示^[15]

$ E{{M}_{\text{comm}}}=\frac{E{{T}_{\text{comm}}}}{p_{m}^{c}{{{\bar{\hat{v}}}}_{rd}}+2(1-p_{m}^{c})}。$

(1)

2 相遇时间估计

对于包含多个社区的网络来说，任意节点i访问各个社区的概率满足归一化条件，即

$ \sum\limits_{k = 1}^n {p_i^k = 1, } $

(2)

机会网络中各个节点的随机运动过程相互独立，根据机会网络消息传输原理可知，若节点i与其他节点交换各个社区的访问概率后，则可获知节点i在每个运动周期内与节点j在同一个社区k相遇的概率，如式(3) 所示

$ p_{ij}^k = p_i^k \times p_j^k。$

(3)

进而，在给定运动周期内，节点i和j在整个区域内的相遇概率为

$ {p_{ij}} = 1 - \prod\limits_{k = 1}^n {(1 - {p}_{ij}^k)} 。$

(4)

根据移动模型相关原理，网络中的节点在各个运动周期内的运动参数选择是相互独立的，则节点i在第e个运动周期与节点j相遇的概率可用式(5) 表示

$ {p_{ij}}({e}) = {(1 - {p_{ij}})^{e - 1}} \times {p_{ij}}。$

(5)

按照上述方法，可以计算出节点i在所有运动周期内与节点j相遇的概率。可见，当2个节点在第e个运动周期相遇时，所经历的间隔时间为e-1个运动周期所经历的时长，即T×(e-1)，结合各个节点运动的独立性，可以获知节点之间相遇间隔时间的期望，如式(6) 所示。

$ \begin{array}{l} {T_{ij}} = \sum\limits_{e = 1}^{ + \infty } {({{T}_{ij}}({e}) \times {p_{ij}}({e})) = } \sum\limits_{e = 1}^{ + \infty } {(({e} - 1)} T \times \\ {(1 - {p_{ij}})^{e - 1}} \times {p_{ij}}) = \mathop {\lim }\limits_{e \to \infty } (0 \times {p_{ij}} + 1T \times (1 - {p_{ij}}) \times \\ \;\;\;\;\;\;\;\;\;\;\;{p_{ij}} + 2T\; \times {(1 - {p_{ij}})^2} \times {p_{ij}} + \cdot \cdot \cdot \\ \;\; + ({e} - 1)T \times {(1 - {p_{ij}})^{e - 1}} \times {p_{ij}}) = \frac{{1 - {p_{ij}}}}{{{p_{ij}}}}。\end{array} $

(6)

显然，此参数估计值的准确程度将极大地影响路由策略的有效性，文中数值结果分析部分对所估计结果与实际值进行了比较。

3 相遇时间感知的路由策略

根据所估计的相遇间隔时间，节点可以获知到达网络中其他节点所需要耗费的时间，进而，合理地选择中继节点以提高网络资源利用率。

提出了一种相遇时间感知的机会网络路由策略CMDAR(community meeting delay aware routing)，该策略主要包含2个过程，分别为预热过程和稳态过程。预热过程中，网络中的各个节点无法获知到达目的节点的时间参数，因此，源节点根据初始化概率信息值选择中继节点。为了使所提出的方法具有较好的扩展性，初始状态下，节点所保存的邻居节点社区访问概率相等，且满足归一化条件，显然，由此得到的节点相遇间隔时间的准确性较低，中继节点的选择缺乏充分的依据，带有一定程度的盲目性。

该阶段中，节点通过随机运动带来的相遇机会进行通信。当节点相遇之后，交换彼此的消息概要向量Summary Vector以及节点访问各个社区的概率向量P_i^kVector。节点获取完整的网络状态信息P_iHashMap需要经过一定的时间，因此，当经过预热时间之后，节点所获取的概率信息P_iHashMap处于稳态，进而，根据式(6) 可以对到达目的节点的间隔时间进行估计，以合理地选择中继节点，最终将消息成功地发送至目的节点。

对于节点u和v来说，网络初始化时首先预置节点的概率向量P_u^kVector={p_u^A, p_u^B, p_u^C, p_u^D}，该向量表示节点u访问社区A、B、C、D的概率分别为p_u^A、p_u^B、p_u^C、p_u^D。与节点v相遇之前，节点u所保存的概率信息表P_uHashMap中，节点v访问各个社区的概率向量预置为p_v^A=p_v^B=p_v^C=p_v^D=0.25。当节点u和v相遇后，交换彼此的消息概要向量和概率信息，并更新各自的概率信息表。节点u更新P_uHashMap中对应的概率向量{0.25, 0.25, 0.25, 0.25}为{p_v^A, p_v^B, p_v^C, p_v^D}，式(7)和(8)给出P_uHashMap更新前后的变化。

$ \left[ \begin{array}{l} \;\;\;p_u^A,\;\;p_u^B,\;\;\;p_u^C,\;\;\;p_u^D\;\\ 0.25,0.25,0.25,0.25\\ \;\;\; \vdots ,\;\;\;\;\; \vdots ,\;\;\;\;\; \vdots ,\;\;\;\;\; \vdots \\ 0.25,0.25,0.25,0.25 \end{array} \right], $

(7)

$ \left[ {\begin{array}{*{20}{l}} {\;\;\;p_u^A,\;\;p_u^B,\;\;\;p_u^C,\;\;\;p_u^D\;}\\ {\;\;p_v^A,\;\;p_v^B,\;\;\;p_v^C,\;\;\;p_v^D}\\ {\;\;\; \vdots ,\;\;\;\;\; \vdots ,\;\;\;\;\; \vdots ,\;\;\;\;\; \vdots }\\ {0.25,0.25,0.25,0.25} \end{array}} \right]。$

(8)

对于节点u中以k为目的节点的消息来说，节点u根据式(6) 计算节点k与u、v的相遇间隔时间T_uk和T_vk。若T_uk>T_vk，则选择v作为中继节点，并将消息转发给节点v。

如上所述，在预热过程中，根据本文所提出的相遇间隔时间估计方法所得到的估计数值并不准确，中继节点的选择带有一定程度的随机性，使得给定消息的副本数量增加。机会网络中的节点缓存资源有限，且所提出的方法需要一定的时间获取状态信息，因此，相遇时间感知的路由策略需要对节点的缓存状态进行调整。根据节点中所保存消息的时间信息，当缓存空间占满之后，节点将删除缓存时间较长的消息副本，以高效地利用有限的缓存资源。

伪代码如下所示

Message transmission Algorithm (DTNHost v, meeting u)

{

Upon ConnectionIsUp (v, u);

//一旦u进入v的通信范围

Send_Summery_vector_To (u); //发送消息概要向量

Send_P_u^k Vector_To (u); //发送自身的概率向量

    Update P_uHashMap; //更新概率信息表

      For(m : messagesNotInSV){

//对于消息概要向量中u没有的所有消息

            if (T_vk＜T_uk)

//如果v到消息的目的节点的相遇间隔较小

                return; //消息不发送给u

            else

//否则消息发送给u

                messageSendTo (u); }

//进入下一个消息检测循环

}

以图 1所描述的网络结构为例，其中包含4个社区，分别为A、B、C和D，数值表示节点在各个社区之间的间隔时间，a(A)表示节点a的归属社区为A。当社区A中的节点a遇到了社区B中的节点b，采用所提出的相遇间隔时间估计方法，可获知并比较两个节点到达各个社区的间隔时间，若节点a中消息m的目的节点归属社区为C，且根据当前网络状态可知，节点a要经过12.2 s才能到达C社区，而节点b在5.2 s后就能到达C社区，则节点a将消息m转发给节点b，以快速、准确地将消息传输至目的节点。

对于广泛采用的PROPHET策略来说，目标节点归属于社区C，与节点b和d不属于同一个社区，则认为节点b和d到达C社区的概率较小，根据其概率更新方法，节点a选择b和d作为中继节点的概率极小，反而有较大的概率把消息转交给C社区内的节点，显然，消息传输过程中所耗费的时间将显著上升，导致消息占用缓存资源时间较长，进而影响网络性能，可见所提出的中继节点选择方法更加合理。

4 数值结果分析

利用机会网络环境(opportunistic network environment，ONE)^[16]仿真平台创建社区模型，对所提出的相遇间隔时间估计方法的准确性进行验证，进而衡量所提出路由机制的有效性。节点采用社区运动模型，当节点处于本地状态的时候，节点社区内部做随机运动，并以较小的概率在下一个运动周期离开本地社区；一旦节点进入其他社区，则会以较大的概率重返本地社区，以较小的概率继续漫游在别的社区。仿真场景由4个社区构成，每个社区包含30个节点。

具体的参数设定如下表 2所示。

如前所述，节点之间的相遇时间估计值的准确性将直接影响路由协议的有效性，本部分对式(6) 的准确性进行验证。

社区A中的节点与社区A、B、C、D中对应的节点a、b、c、d的相遇间隔时间如图 2所示。

从图 2可以看出，处于本地状态的节点和本社区节点a平均1.24 s以后有一次相遇机会，而与社区其他节点分别有平均3.95 s，4.64 s和4.37 s的相遇延迟时间。仿真过程中所得到的结果与公式(6) 推导的结果偏差较小，可见，所提出的节点相遇时间估计方法比较准确。

对于节点缓存容量不同的情况下，本部分对所提出策略的投递率、消息传输延迟和负载率3个方面的性能进行了比较和分析。

图 3比较了所提出的路由策略与PROPHET策略的消息传输概率，可见，消息的传输率随着节点缓存增加逐渐提高，进而趋向于稳定。随着缓存空间的逐渐增加，消息在缓存内停留时间延长，可以在被删除之前得到更多的转发机会，仿真结果表明所提出的机制在传输率方面平均提高了11.09%。

图 4描述了2种路由方法下的延迟性能。从总体上来说，消息的延迟随着缓存的增加而降低。根据所提出的路由策略基本原理可知，消息能沿着延迟更少的方向进行传输，进而，在更短的时间内到达目的节点。仿真结果表明，与PROPHET相比较，所提出的路由策略平均延迟降低了35.41%。

网络负荷是衡量路由策略有效性的关键指标，用于表示传输给定数量的消息所需要耗费的网络资源，其定义为中继消息数量与传输成功的消息数量的比值。

从图 5的结果可以看出，所提出路由策略的网络负荷量低于PROPHET，由于所提出的路由策略中，消息转发次数较少，因此，消息副本数量得到了有效的控制，使得网络负荷降低。

5 结论

机会网络中的节点通过随机移动获得相遇机会，进而传递消息，合理地选择中继节点将有效提高网络性能。本文根据节点访问各个社区的概率估计节点间相遇时间，进而，选择与目的节点相遇间隔时间较小的节点作为中继节点，消息经过此类节点携带并转发后到达目的节点。理论和仿真分析表明，所提出的相遇时间预测方法能够准确地估计节点间的相遇时间，采用此参数选择中继节点更具有针对性，相比基于历史信息的路由方法，所提出的路由策略能够有效提高网络性能。