考虑节点多社区属性的机会网络高吞吐量路由算法

2018-09-07李秀峰王坤龙曹红伟

小型微型计算机系统 2018年8期

任智，李秀峰，王坤龙，曹红伟

(重庆邮电大学移动通信技术省部级重点实验室，重庆 400065) E-mail：kcrisli@163.com

1 引言

机会网络是一种在消息源节点和目的节点之间不需要存在任何完整、持续、稳定的通信链路，只利用节点的运动所创造的通信机会完成数据传递的无线自组织网络[1].随着科技的不断发展，大量功能强大、价格低廉的智能移动设备(智能手机，便携式电脑等)已被广泛使用，并逐步成为未来网络和服务的主体.而由人所携带的智能设备之间的信息传输都具有一定的社区属性，鉴于这类基于社区的机会网络的广泛应用，研究基于社区的机会网络路由算法已经成为机会网络研究领域的热点之一.

社区划分标准有很多种，最常见的划分方法分为集中式和分布式社区划分算法.集中式的社区划分方法，是服务器或者网络中的某个控制节点收集网络中其它节点的信息并进行整理，再按照一定的标准统一进行社区划分，其中具有代表性的算法是HSEO算法[2]，该算法由系统维护着一个模块度Q值，首先服务器或者控制节点将网络随机分为节点等同的两个社区，然后寻找其中对社区吸引力最小的节点移动到另一社区，由服务器或者控制节点计算此时网络的模块度Q值，重新调整节点所在社区，直到模块度Q值不在增长，即得到了最优的两个社区结构，然后依次对最优的两个社区结构迭代，不断增加需要划分的社区数目，直到网络中个社区达到稳定.

由于在移动自组织网络中，服务器不可能收集到所有节点的信息，研究者们提出了一种节点根据其本身收集到的信息划分其所在社区的分布式社区划分算法，其中具有代表性的算法是 CSCBR[3]，该算法通过计算一组节点两两间在单位时间内的相遇次数来评价一组节点相互间的通信能力，并作为节点分簇的依据，从而达到把移动规律相近的节点聚合成簇(作者把这种簇称为“最近社交圈”)的效果.节点成簇操作是分布式进行的，一个簇的形成需要经过相遇权值计算、簇头选举和簇成员竞争3个阶段，成簇之后，在簇内和簇间会进行消息的传送.该算法不需要某一个节点控制划分过程和维护整个网络的社区结构，每个节点只需要维护自己的社区，后期维护社区结构的开销比较小.其带来的好处就是减少了社区划分阶段和社区维护阶段时大量的控制消息.

2 相关工作

基于社区的机会网络的路由算法是在机会网络的经典路由算法下发展起来的，主要有以下一些路由算法.

Epidemic[4]算法是研究者们最早提出的机会网络路由算法.携带消息的节点采用泛洪的方式将消息转发给每个相遇节点，直至消息到达目的节点.该方式使网络中的消息副本数过多，增大了整个网络的开销.ProPHET[5]算法中每个节点都维护一张与其它节点的相遇概率表，通过交换概要向量和预测概率矢量.携带消息的节点将消息转发给与目的节点相遇概率更高的节点，这就大大的减少了网络中该消息的副本数.但是ProPHET算法没有说明在消息被转发目的节点后该消息在网络中的副本如何消除，同时各节点无法保证计算预测概率矢量的准确性.

Label[6]算法根据用户的兴趣将机会网络中的节点划分社区，如每一个节点有不同的兴趣就分配不同的Label，拥有相同的Label的节点属于同一社区.Bubble Rap[7]算法是综合考虑了节点的中心度和社区结构来提高消息的传输效率.每个节点有至少一个Label，相同Label的节点属于同一个社区.消息总是向着中心度高的节点转发，但消息汇聚在中心度高的节点的缓存中，有可能会造成消的拥堵或者节点能量过快的消耗而死亡.STBID[8]算法节点间社会连接强度的计算机制，不同社会连接强度的节点分配有不同的用于发送数据的令牌个数.SROR[9]算法和TDFSON[10]算法提供了节点社会关系的计算方法，用于在数据转发时选择最优的转发节点.

Int-Tree算法[11]假设相同兴趣的节点会频繁的相遇，携带消息的节点遇到与目的节点同社区的节点时，如果携带消息的节点也与目的节点同社区，则比较双方节点到达目的节点的社会连接度.若对方节点的连接度更高，则转发消息.如果携带消息的节点和相遇节点都与目的节点不同社区，则比较它们到目的节点的社区、目的节点的父社区以及直到根节点之间的所有父社区的密度，如果对方节点到其中任何一个社区的密度值比对应本节点到该社区的值大，则节点把数据转发给对方节点.

BEEINFO[12]是一种基于兴趣社区人工智能路由算法集合，每个节点与对应的人或者车辆具有相同的社会特性和移动规律.网络中的节点根据自身的兴趣划分为不同的社区，BEEINFO主要是充分利用个人的学习能力和相互合作来感知环境的动态变化，该算法可以根据环境的不同可以分为三种不同的算法：BEEINFO-D、BEEINFO-S和BEEINFO-D&S.BEEINFO-D算法的思路是消息在社区间传递时主要利用社区密度作为转发参数，在社区内部时，由携带消息的节点直接将消息投递给目的节点；BEEINFO-S算法的思路是消息在社区间传递时，源节点只把消息转发给目的社区内的节点.当消息转发到目的节点后，根据节点与目的节点的社会连接度大小转发消息；BEEINFO-D&S算法利用社会密度信息帮助节点在社区间转发消息，利用社会连接度信息帮助节点在社区内部转发消息.

在深入研究基于社区的机会网络路由算法后，发现现有基于兴趣划分社区的算法存在没有考虑节点多社区属性、统计节点相遇次数不够准确和相遇节点间控制信息冗余的问题.为解决以上问题，本文提出一种考虑节点多社区属性的机会网络高效路由算法—HRCMA，并从理论分析和仿真验证了所提算法的有效性.

3 系统模型与问题描述

3.1 系统模型

本文以行人所携带的智能设备(如手机)为网络节点，具有相同兴趣的人(例如同学或同事)通常会聚在一起讨论并分享他们的兴趣，他们经常联系并组成一个社区.这些利益相关的社区与地区保持一致，在利益上彼此不同.此外，不同兴趣每天都会生成大量不同的数据，通常用不同的标签标记以表示其类别.因此网络节点使用不同数据类别来代表人们的兴趣对社区进行划分，一个社区与一个类别有关.对于一个特定的社区，如果一个人对该类别感兴趣，则对应节点属于该社区；如果他有多个兴趣，他同时属于并影响到几个社区.毫无疑问，多重兴趣比单一兴趣更复杂，本文系统模型为多兴趣网络模型.

定义1.移动模型：机会网络中的节点具有一定的社会性，其运动并不是完全随机的，经常相遇的节点之间有一个较高的接触概率，在未来相遇的可能性也较大.

定义2.社区密度：社区密度可以用节点在时间窗口T内所遇到的某一个社区i内节点的次数n表示，在BEEINFO算法中，社区密度计算公式如1，而公式2是对该社区未来密度的预测.

(1)

Densityi(t+Δt)=α×Densityi(t-Δt)+(1-α)×Densityi(t)

(2)

式中，α是社区密度的预测因子，表明过去密度信息和现在密度信息的影响权重.

如果当前节点长时间没有与某社区内的节点相遇，则该社区的密度也会逐渐降低，计算公式如(3)所示：

Densitynew(t)=Densityold×γk

(3)

式中，γ是衰退指数，k是距离上次更新的时间间隔.

定义3.社会连接度：用来表示相同社区(兴趣)的节点之间社会关系的强弱.节点的社会连接度信息只能在社区内部发挥作用.在BEEINFO算法中，社会连接度计算公式如公式(4)，而公式(5)是对未来社会连接度的预测.

SoTiei，j(t)=(λi，j×di，j(t))/T

(4)

SoTiei，j(t+Δt)=β×SoTiei，j(t-Δt)+(1-β)×SoTiei，j(t)

(5)

式中，λi，j是接触频率(在时间窗口T内，节点i与j的相遇次数)，di，j是在时间窗口T内节点i与j的接触时间，β是预测因子.

随着节点之间长时间未相遇，节点之间的连接度也会不断减小.

SoTienew=SoTieold×γk

(6)

定义4.节点亲密度：在节点多兴趣模型中，用来表示节点间的亲密程度.当两节点无共同的兴趣时，节点亲密度计算公式如公式(7)所示，当两节点存在共同的兴趣时，节点节点亲密度计算公式如公式(8)所示.

(7)

(8)

3.2 问题描述

通过研究发现，现有的以BEEINFO算法为代表的基于兴趣划分的社区网络存在以下3个问题：

3.2.1 节点多社区属性问题

在BEEINFO算法中，作者假设节点只有单一兴趣，即只属于某一社区，然后利用相遇节点双方与目的节点的社区关系进行转发选择，没有考虑现实中节点同时属于多个社区的情况，从而缩小了转发节点的选择范围，数据包的转发机会受到抑制，对数据传送成功率和吞吐量有不利影响.

3.2.2 节点相遇历史中存在无效相遇情况

BEEINFO算法在数据转发时主要依赖两个参数：社区密度和社会连接度.这两个参数在节点相遇后的更新过程如图1所示，在两个相遇节点相互交换兴趣信息和消息摘要列表后，如果两个节点处于不同社区，则更新它们所记录的对方社区的密度信息(UpdateDensity).否则，更新它们所记录的本社区密度信息(UpdateDensity)和对方节点的社会连接度信息(UpdateSocTie).

图1 节点相遇后更新的过程Fig.1 Update process after node’s encounter

BEEINFO算法在统计节点之间相遇历史次数时没有考虑无效相遇的情况，而无效相遇会对数据转发所依据的社会连接度和社区密度两个参数造成虚高的不利影响，虚高的社会连接度和社区密度值使得邻居节点向其转发更多的消息，但是该节点到达目的节点或社区的消息转发能力可能低于实际情况，从而造成数据传递成功率的降低和传输时延的增大.

3.2.3 控制消息存在冗余

在BEEINFO所研究的节点单社区模型中，两个节点成为邻居后，需要交换各自的兴趣I(用以标识各自的社区)和消息摘要列表Lm(本节点携带的所有消息摘要)，然后根据消息目的节点的兴趣，发送给对方自己记录的目的社区的密度信息或目的节点的社会连接度信息，最后选择目的社区密度大或者与目的节点社会连接度大的节点携带该消息.但是在其中一个节点收到对方的兴趣后，可以在要发送的消息摘要列表中删掉肯定不会转发给对方的消息的摘要信息.也可以在一个节点收到对方兴趣消息和请求消息后，减少要发送的请求消息中对方节点肯定会转发给自己的消息的请求内容.通过缩减这些控制消息可以减少网络资源的消耗，提高消息转发效率.

4 HRCMA算法

针对上边所述的3个问题，本章提出一种新的HRCMA算法.HRCMA算法增加了节点多社区属性的消息转发策略，通过筛选掉节点间的无效相遇和精简控制消息的内容来提高消息转发效率.

4.1 HRCMA算法新机制

4.1.1 节点多社区属性的消息转发策略

节点A，B相遇后，相互交换兴趣信息In(表示当前节点所属的社区集合)和消息摘要列表Lm(所携带的消息的摘要信息)，通过In+Lm 信息判断是否向对方提出消息转发请求，判断策略如下：

假设A节点的消息列表Lm中的消息M，其目的节点为D，所属社区集SD={S1，S2，S3…}；

1)如果节点A所属社区集SA与SD互异，即SA∩SD=Ø，而节点B所属社区集SB与SD有相同子集，即SB∩SD≠Ø，则节点A将消息M转发给节点B；反之，若SA∩SD≠Ø而SB∩SD=Ø，则不转发该消息.

2)如果节点A，B的社区集SA，SB都与SD互异，即SA∩SD=Ø且SB∩SD=Ø，各节点计算与目的节点的亲密度，根据公式(7)计算得到IntimacyA，D和IntimacyB，D，通过相互发送REQIntimacy得知彼此与目的节点的亲密度，比较亲密度的大小，若IntimacyB，D>IntimacyA，D，则A转发该消息，否则不转发.

3)如果节点A，B都与节点D存在相同的兴趣，即SA∩SD≠Ø且SB∩SD≠Ø，则同样比较A，B节点与目的D的亲密度，根据公式(8)计算IntimacyA，D和IntimacyB，D，相互发送REQIntimacy得知彼此与目的节点的亲密度，若IntimacyB，D>IntimacyA，D，则A转发该消息，否则不转发.

4.1.2 节点无效相遇的判断机制

节点A和B相互收到hello消息确定邻居关系，之后判断A、B相遇是否有效的机制如下：

1)判断A、B节点是否收到对方发送的数据.如果收到对方发送的数据，则此次相遇有效.否则，跳到(2).

2)判断在上次收到对方消息后的一个hello周期内是否第二次收到对方的hello消息.如果收到，则此次相遇有效.否则，跳到(3).

3)判断是否收到对方的请求消息REQDensity or SocTie(请求消息的内容是节点记录的对方发送来的Lm中自己感兴趣的消息的目的节点的社会连接度或者目的社区的社区密度)或REQIntimacy.如果收到了，则此次相遇有效.否则，跳到(4).

4)判断是否收到In+Lm，如果没有收到，则此次相遇为无效相遇，否则，跳到(5).

5)判断A、B的运动方向.根据节点第一次收到对方发来的hello包和In+Lm包，采用接收信号强度指数(RSSI)测距机制[13]计算A与B节点之间的距离，从而判断两个节点是相互靠近还是相互远离.如果两个节点相互靠近，则此次相遇有效；如果相互远离，则此次相遇无效.

4.1.3 精简控制消息

在节点单社区模型中，相遇节点交互过程如图2所示.图中REQDensity or SocTie在节点i与j不同社区时是REQDensity，在节点i和j同社区时是REQSocTie.但是在i先收到对方的Ij+Lmj后，之后再发送的Ii+Lmi和REQ(i)Density or SocTie长度是可以缩减的，同时REQ(j)Density or SocTie也可以缩减.

图2 相遇节点之间的交互过程Fig.2 Interaction process between nodes

1)Ii+Lmi

在节点i收到Ij+Lmj后获知节点j所属的社区，如果节点i和j不在同一个社区，由于同社区内的节点之间相遇的概率比社区间的节点相遇概率大，所以Lmi中不必携带节点i缓存中与i同社区的消息的摘要信息，只需要发送L(m-m＇)i(m＇表示节点i缓存中所有目的节点与i同社区的消息集合).同理，该策略可以应用于节点多社区模型，在节点i收到Inj+Lmj后，若缓存中存在目的节点社区集与节点j所属社区集互异而与本节点所属社区集有相同子集的消息时，可以在发送Lmi时从列表中去掉这部分消息.

2)REQDensity orSocTie

两个节点成为邻居后，节点i收到对方j发送的Ij+Lmj消息，获知自己、节点j和消息M(M是mj中的任意一个消息)的目的节点d之间的社区关系；如果节点i又收到REQ(j)Density or SocTie，则节点i可以确定节点j也收到了自己发送的Ij+Lmj，并据此判断是否减少REQ(i)Density or SocTie中所包含的信息.同理，节点j收到节点i的Ii+Lmi消息后，可以采用同样的策略减少REQ(j)Density or SocTie消息的内容.以节点i收到节点j的Ij+Lmj消息和REQ(j)Density or SocTie消息的情况为例，判断是否减少REQ(i)Density or SocTie中消息M的请求信息的过程如下：

a)如果节点i与节点j都与节点d同社区，则REQ(i)Density or SocTie包含消息M的请求信息.

b)如果节点i与节点d同社区，节点j与节点d不同社区，则REQ(i)Density or SocTie中就删除消息M的请求信息，只发送REQ＇(i)Density or SocTie，因为即使节点i不向节点j请求消息M，节点j也会把消息M转发给节点i.

c)如果节点i与节点j都不与节点d同社区，则REQ(i)Density or SocTie包含消息M的请求信息.

同理，在节点多社区模型中，可以采用该策略，若节点j携带的消息M的目的节点社区集与节点j所属社区集互异而与节点i所属社区集有相同子集时，节点i可以在发送REQ(i)Intimacy时删除对消息M的请求信息.

4.2 HRCMA算法步骤

采用HRCMA算法的节点A判断节点A，B相遇情况及消息交互的操作步骤如下：

1)节点A收到B发送的hello消息后，确定节点B为邻居节点；

2)判断是否收到InB+LmB(节点B发送).如果收到，则向节点B发送改进后的InA+L(m-m＇)A；否则发送InA+LmA，并等待接收InB+LmB.

3)判断收到REQ(B)Density or SocTie或REQ(B)Intimacy？如果收到，则向节点B发送改进后的REQ′(A)Density or SocTie或REQ′(A)Intimacy；否则发送REQ(A)Density or SocTie或REQ(A)Intimacy，并等待接收REQ(B)Density or SocTie或REQ(B)Intimacy.

4)根据节点B发送的REQ(B)Density or SocTie或REQ(B)Intimacy，通过判断选出要发送给节点B的数据并发送.等待接收节点B的数据.

5)通过控制消息的交互，结合节点无效相遇判断机制判断本次相遇是否为有效相遇，并根据判断结果更新到节点B所在社区的社区密度和与节点B的社会连接度.

5 HRCMA算法仿真验证

本节利用ONE仿真平台对HRCMA算法的相关性能进行仿真验证，并与BEEINFO、Epidemic和ProPHET算法对比相关性能的优劣.

5.1 仿真统计量的定义

1)吞吐量：吞吐量是指在单位时间内成功送达的消息的比特数.计算公式为：

π=P/T

(9)

式中，π表示吞吐量；P表示成功送达的消息的比特数；T表示运行时间.

2)归一化控制开销：归一化控制开销表示网络中所有控制消息总比特数所占比例，公式如下：

η=Nc/(Ng+Nd)

(10)

式中，Nc为所有控制消息的总比特数，Ng为到达目的节点的控制消息的总比特数，Nd为到达目的节点的数据消息的总比特数.

3)消息传输成功率：消息传输成功率是指成功投递到目的节点的消息数量与网络中源节点产生的消息(不含副本)的数量的比值，公式如下：

(11)

式中，D表示成功投递到目的节点的消息的总数，C表示源节点产生的所有消息的总数.

4)平均端到端时延：平均端到端时延表示从消息产生的时刻到该消息被成功投递到目的节点的时刻的时间均值，公式如下：

(12)

式中，Ti表示第i个被成功投递到目的节点的消息从产生到被投递到目的节点的时间间隔，D表示所有被成功投递到目的节点的消息数量的总数.

5.2 网络场景及参数设置

HRCMA算法的仿真地图场景为ONE仿真软件默认的芬兰赫尔辛基市地图，仿真场景的相关参数设置如下表1所示：

5.3 仿真结果及分析

5.3.1 网络吞吐量

图3显示的是网络吞吐量对比图.由图可知，各算法消息网络吞吐量随节点缓存增长而增长，相比于BEEINFO算法，HRCMA算法在网络吞吐量上提高了至少3.26%(节点缓存为50M时，(380-368)/368=3.26%)，这是因为HRCMA算法增加了多个社区的情形，将节点亲密度作为多社区情形下转发消息的度量，与目的节点具有部分相同兴趣的节点会参与消息的转发，因此网络中被转发的消息数量得到有效提升，网络吞吐量更高，同时HRCMA算法的节点间的相遇次数更可靠，选择的转发节点能转发该消息的概率更大，进而网络吞吐量得到提高.

表1 仿真场景参数Table 1 Simulation scene parameters

5.3.2 消息投递成功率

图4显示的是投递成功率对比图.由图可知，各算法消息投递成功率与节点缓存呈正相关，因为节点的缓存增大，节点携带消息的副本数增加，缓存容量丢包概率降低.相比于BEEINFO算法，HRCMA算法在投递概率上提高了至少2.81%(节点缓存为50M时，(73-71)/70=2.81%)，这是因为HRCMA算法考虑了节点可能属于多个社区的情形，增加了节点亲密度作为转发消息的度量，在HRCMA算法中与目的节点具有部分相同兴趣的节点也会协助转发消息，因此节点转发的概率更高，同时HRCMA算法统计的节点间的相遇次数更可靠，改进后计算得到的社区密度和节点社会连接度及节点亲密度更能体现节点转发数据的能力，选择的转发节点成功投递该消息的概率更大.

图3 网络吞吐量对比Fig.3 Comparison of throughput图4 投递成功率对比Fig.4 Comparison of succeed delivery rate

5.3.3 归一化控制开销

图5所示的是归一化控制开销对比图.由仿真结果可以看出，归一化控制开销随着节点缓存的增加逐渐减小，因为网络中控制消息总比特数未变，但节点缓存增加会提高投递成功率，使得到达目的节点的比特数增加.HRCMA算法比BEEINFO算法的归一化开销至少减低6.1%(缓存为10M时，(0.65-0.61)/0.65=6.1%)，其原因是，在每次节点相遇时，HRCMA算法通过两个节点之间交互的控制消息的信息和顺序，缩减它们之间之后需要交换的In+Lm和REQ控制消息的内容.同时，统计节点相遇次数时，去除不能传输数据的相遇情况，消息的投递概率更高.

图5 归一化控制开销对比Fig.5 Comparison of normalized control overhead图6 消息投递平均时延对比Fig.6 Comparison of transmission delay

5.3.4 平均端到端的时延

图6显示的是消息投递平均时延对比图.HRCMA和BEEINFO算法相比，节点缓存在10MB到20MB之间时，平均端到端时延略有降低；而节点缓存在20MB到50MB之间时，HRCMA算法的平均端到端的时延和BEEINFO算法相比至少降低0.5%(节点缓存为20M时，(5650-5620)/5650=0.5%)，主要是因为HRCMA算法考虑了节点可能属于多个社区的情形，在该情形下，与目的节点具有部分相同兴趣的节点个数高于BEEINFO算法中与目的节点同社区的节点个数，因此节点转发的概率更高，同时HRCMA算法统计的是节点相遇且能够传输数据的相遇历史，据此选择出的转发节点可以更快的把数据转发给下一个可以转发的节点甚至目的节点.