BIRI：支持信息中心范型的BBO启发式MSN路由算法

涂盼鹏 王兴伟 李 婕 黄 敏

1(东北大学计算机科学与工程学院 沈阳 110169)2(复杂网络系统安全保障技术教育部工程研究中心(东北大学) 沈阳 110169)3(东北大学信息科学与工程学院 沈阳 110819)

社会学将人类在实际生活中形成的网络关系结构称为社交网络[1].因人类具备社会属性，社交网络得以保持相对稳定的结构.然而在移动社交网络(mobile social network， MSN)中，用户的移动导致端到端路由呈现间歇性，使MSN具备延迟容忍网络(delay tolerant network， DTN)[2-3]的诸多特征，如投递率低、延迟高、能量和存储受限等.“尽力而为”的数据传输模式难以满足当今互联网的需求，如何设计高效的MSN路由机制成为研究的重点和难点.

互联网用户规模剧增的同时，用户对网络中内容的需求量也急剧上涨.但现有的基于IP地址的端到端主机通信模式难以有效地支持以内容为中心的数据检索和服务访问[4].如何设计高效的内容检索策略也是当前互联网亟待解决的一大难题.对用户而言，信息本身比其存储位置更重要[5]，因此引入信息中心网络(information-centric networking, ICN)的思想，将内容名称作为唯一网络标识进行缓存和路由，是提升MSN路由效率的良好思路.

针对上述问题，本文充分利用MSN中的社交关系和社区结构，引入ICN以内容为中心的思想，基于网络图论对生物地理优化(biogeography-based optimization, BBO)算法进行改进，以此为基础设计了一种支持信息中心范型的BBO启发式MSN路由算法(BBO-inspired MSN routing algorithm with information-centric paradigm support, BIRI).

本文的主要贡献有4个方面：

1) 综合考虑节点的接触规律以及兴趣和内容的相似性，提出了新的度量用以衡量节点社会关系强度，并改进了中心度的计算方式;

2) 基于节点之间的内容相似度以及网络动态特性改进了BBO算法，优化MSN中的社区划分过程;

3) 引入ICN内容为中心的设计思想，为MSN节点设计了内容缓存和缓存替换策略;

4) 通过内容聚集、桥节点选取等机制辅助数据包和兴趣包的路由，提高了内容查找速率和路由效率.

1 相关工作

目前，对MSN中社区检测、内容分发以及节点安全和隐私等方面的研究都取得了诸多成果[6-7]，并且基于内容的MSN数据传输机制已成为新的研究热点，但将ICN架构引入具备DTN特征的MSN中以提升通信效率的相关研究尚处于起步阶段.相关研究工作如下：

文献[8]基于ICN提出了一种缓存感知型MSN路由方案，充分考虑节点间的社会关系、分布规律以及存储内容以建立路由和缓存机制，提升了信息传递率并降低了网络开销.文献[9]利用启发式的贪婪算法针对DTN中的节点缓存选择进行优化，实现DTN中内容分发效益最大化，降低了时延并提高了内容接收率.文献[10]针对DTN提出一种基于代理的内容检索机制(agent-based content retrieval， ACR)，无需修改现有的ICN消息处理流程，具有灵活性和可操作性.文献[11]将蚁群算法引入ICN，提出了一种启发式的路由机制，该机制的特点在于通过检索最接近的内容副本实现对节点移动性的支持.文献[12]将移动自组织网络的自治特性和内容中心网络的底层框架相结合，提出了一种拓扑感知的内容中心网络协议，该协议采用基于多点中继的分组转发和主动内容发现以及基于邻居信息的洪泛控制算法，有效降低了传输时延和网络开销.文献[13]基于社区结构提出了一种以内容为中心的发布订阅服务策略(mobile community-based pubsub scheme, MOPS)，但MOPS中网关节点不仅要总结本地社区的兴趣还要维护其他社区的内容索引，成为了性能瓶颈.

本文提出的BIRI机制不仅通过高效的社区划分提升了MSN的路由效率，而且引入ICN以内容为中心的数据请求模式，并辅以节点的缓存机制，降低路由开销与路由时延，同时缓解了MSN因节点动态性和链路不稳定性导致的路由难题.

2 系统模型

本文的研究对象为分布式MSN，其网络模型主要由节点以及节点之间的边构成.其中，每个节点都具有计算、存储和转发的功能，并维护5种表结构：内容存储表(CS)、转发信息表(FIB)、社会关系表(ST)以及低中心度节点摘要(LCD)、邻居集内容摘要(NCD).MSN在任意时刻的拓扑可抽象为无向赋权连通图G=(V,E,W).其中，集合V代表移动节点，即持有移动设备的用户，移动过程中在各自的通信范围内与其他节点相遇并建立连接；边集合E则表示MSN中存在于节点间的社会关系；W是网络中边的权重，即节点间的社会关系强度.

本文的主要研究内容是在MSN的网络系统中引入ICN范型以完成社交节点之间的数据传输服务，专注于基于朋友关系的数据转发服务.因此本文的数据转发服务基于2条假设：

1) 使用本系统进行数据转发服务的节点彼此愿意进行数据转发服务，以交换服务的互惠方式作为转发机制的激励因素；

2) 参与本系统的用户关系为朋友关系且进行实名验证，不考虑恶意节点及由此产生的安全访问问题.

3 社交度量

3.1 社会关系强度

定义1.节点间的社会关系强度[14].它为逻辑关系强度和物理关系强度的加权和，即：

SS(i,j)=α×SSL(i,j)+(1-α)×SSP(i,j)，α∈[0,1].

(1)

逻辑关系强度SSL(i,j)正相关于2个节点中内容的累计新鲜度的Jaccard相关度,如式(2)(3)：

(2)

(3)

其中，Tcur为当前时刻，R(δ,t)表示在时刻t数据中是否包含词缀δ.

物理关系强度SSP(i,j)则为描述节点的移动性对节点间的社会关系强度的影响而设计.因节点在移动过程中只有相互接触才具备直接的社会关系，因此在设计中无需限定节点的具体运动方式，通过考虑节点接触的物理规律，包括频率、平均接触间隔等指标，可以得出如式(4)所示的定义式，其实际含义是i向j发送消息的平均转发延迟的倒数，该值越大则平均转发延迟越小，用户关系越紧密.

(4)

其中，fij(t)表示在时刻t时距下一次相遇的时间间隔，如果i和j正在保持联系，那么fij(t)=0，否则fij(t)=tnext-t.

3.2 中心度

节点的中心度[15]衡量节点在MSN中的消息扩散能力.因此中心度较高的节点具备较高的转发效率.本文在紧密中心度[16]的基础上进行修改，得出了如式(5)所示的中心度定义：

Cc(i)=β×CS(i)+(1-β)×CJ(i)，β∈[0,1],

(5)

其中，CS(i)为节点i与其所有相遇节点间的社会关系强度的均值，衡量i对消息的转发能力，如式(6)；CJ(i)是简氏公平系数[17]，用来评价社会关系分布对中心度的影响,如式(7)；β是两者的权重系数.

(6)

(7)

其中，Nm表示与i相遇的节点总数.

4 基于BBO的社区发现算法

BBO算法将问题的候选解模拟为栖息地[18]，并模拟生物种群在栖息地之间的迁移，使得优秀的影响因素得以共享，进而优化栖息地；同时模拟生物变异以增强算法的自适应能力.因此本文引入BBO算法并针对MSN的社区发现问题加以改进，用以优化社区划分的结果.表1给出了BBO数学模型与社区发现算法的对应关系.

Table 1 Mapping Relationship Between BBO Mathematical Model and Community Detection Algorithm表1 BBO数学模型与社区发现算法的对应关系

4.1 优化目标

动态的MSN被表示为随时间变化的图序列，所以社区发现应基于当前时刻MSN的 “快照”进行，故任意时刻每个节点仅隶属于1个社区.动态网络社区发现可以看作多目标优化问题，应同时优化2个目标函数：

(8)

Maximize:NMI=

(9)

其中，Q是模块度，定义为社区内的边占比和跨社区的边占比之差的期望.Q越接近1代表社区内聚越高，划分结果越趋于合理.式(9)表示标准化互信息.其中，设H和I是2次划分结果，Cij代表H中的社区i与I中的社区j中相同节点的数目，Ci是模糊矩阵Cconf中表示社区i的行向量的元素之和，Nnd是节点总数.对相邻时刻的2种划分结果而言，NMI越大则两者越接近，因此划分结果越符合实际.

4.2 适应度函数

适应度表示栖息地质量的优劣，作为社区搜索的依据，其定义为

(10)

其中，xi表示栖息地个体，X表示种群，N是种群规模.记(f1,f2)为目标函数向量，其中Q=f1，NMI=f2，现有2个解xi和xj，当且仅当fk(xi)≤fk(xj)(∀k=1,2)且fk(xi)

4.3 确定初始社区

初始时刻，节点没有所隶属的社区编号，无法计算Q和NMI.所以依据内容相似度进行聚类，在每轮迭代中合并内容相似度最大的节点对形成社区并将其视为新节点，然后重复该过程直至社区数目达到预设值.内容相似度如式(11)：

(11)

其中，num为全网中的关键词总数，内容向量u=(u1,u2,…,unum)和v=(v1,v2,…,vnum)的分量表示对应关键词的内容权重.

4.4 迁移操作

4.5 变异操作

变异策略会改变栖息地个体的质量.当某个分量进行变异操作时，寻找该分量代表的节点的最多邻居节点所属的社区，再从中随机挑选1个节点作为突变值进行替换.这种基于社区结构设计的变异策略考虑到了随机替换的差异性可能对系统造成不同的影响，保证节点变异后所属社区与最多的邻居节点所属社区一致，使得社区结构不会发生过大的变化.

4.6 排重操作

对比所有个体的适应度向量，若存在xi=xj，则初始化新向量xk，并用xk替换xj.该步骤是为了降低解向量的重复率，增加算法的广度搜索范围.

4.7 基于BBO的社区发现算法描述

算法1.基于BBO的社区发现算法.

输入：T个时刻下的动态网络DN={G1,G2,…,GT}；

输出：每个时刻的社区结构C={C1,C2,…,CT}.

① 初始化总时刻T、种群规模N、栖息地维度n、最大迭代次数Gmax；

③ fort=1 toTdo

⑤ whileG

⑥ 根据式(10)计算各栖息地的HSI；

⑦ 对X中所有个体根据HSI值升序排序；

⑧ if非支配个体数>N

⑨ 选取前N个个体作为新种群X′；

⑩ else

5 基于ICN的缓存机制

5.1 缓存决策

基于ICN思想，节点可以缓存数据以响应后续的内容请求.在本文设计的缓存决策中，设i和j分别是数据包途经节点和请求节点，则i为j进行数据缓存的优先级为

(12)

χ∈[0,1]，

其中，hop表示节点i与j间隔的跳数；k是节点j帮助i缓存的累计次数，代表j对i的贡献值.显然，j曾经帮助i的次数越多，两者间的距离越近，则以j为目的地的数据包被缓存的优先级越高.

5.2 缓存替换

当节点的缓存空间耗尽，需要缓存替换策略置换新数据.依据访问局部性原理，节点中的缓存内容被其他节点请求的频率会随时间发生变化，一定时间内，内容被请求得越频繁，代表其流行度越高，因此应当以内容流行度作为替换依据.

(13)

θ∈[0,1]，

(14)

6 社区感知型路由

6.1 社区内路由机制

为了加快内容检索过程，节点首先应进行内容聚集，使得中心度高的节点掌握一定范围内中心度低的节点所能检索的信息.具体方案是每个节点维护LCD和NCD这2种内容摘要，NCD记录了邻居节点集中占比较高的内容摘要，且初始时刻各节点将LCD初始化为NCD.内容聚集过程就是各节点向相遇的中心度更高的节点发布各自的LCD，因此LCD概括了节点在比其中心度低的节点范围内所能检索的信息内容，信息内容将逐步聚集到中心度高的节点上.LCD仅存储内容名字以起到“索引”的作用.

另外，为提高兴趣包的转发效率，本文采用k-均值聚类算法将社区内的节点以中心度为指标进行层次划分，使得各层中的中心度方差值最小，达到层内紧凑、层间独立的效果.当进行数据请求时，兴趣包仅向更高层次的节点转发，有效减少低效率的转发次数.

当网络工作时，兴趣包的转发策略为：内容请求者携带兴趣包，若遇到比自己且比上次转发的节点的中心度层次更高的节点时才转发兴趣包.当某节点接收到兴趣包时，若本地缓存中存在对应条目，则返回数据包以响应请求者；否则，查找LCD，若其中有匹配信息，就根据ST将兴趣包转发到内容源，否则继续按照上述规则转发兴趣包.

为了避免因存储-转发模式的延迟产生的路由回路的影响，每个兴趣包都设有生存时间(time-to-live， TTL).且针对存在回路的情况，设计了备用兴趣包转发策略，即中继节点将兴趣包发送给比自己中心度层次高的节点即可.

当节点将数据包返回给请求者时，对应的数据包转发策略为：数据包携带者以与目的节点的社会关系强度为判据，对比自身与每个接触的节点，仅当后者判据值更大才将其作为下一跳节点进行转发.

6.2 社区间路由机制

若社区内不存在所请求的内容信息，则需要设计合适的“桥节点”选择策略.在本文中，桥节点负责跨社区的兴趣包的转发，向其他社区内的节点进行内容请求.桥节点包含2种兴趣内容表：1)内部兴趣表(internal interest table， IIT)，记录本社区的兴趣内容列表；2)外部兴趣表(external interest table，EIT)，记录它能到达的外部社区的兴趣内容列表.簇头节点(即最高中心度层次内的节点序列)定期向桥节点发送本社区的兴趣列表，以便桥节点及时更新IIT.当不同社区的桥节点相遇，则相互发送IIT以更新各自的EIT.

本文用社区隶属度作为选取桥节点的标准.节点i在其所属社区C的社区隶属度CDi按照式(15)计算：

CDi=min{SS(i,j),i∈VC∧j∈VC}，

(15)

其中VC是社区C的节点集合.CDi越小代表i与隶属社区间联系越弱，与其他社区内节点相遇的概率越高，因此越适合作为桥节点进行跨社区的路由.

综上，社区间的路由策略可概括为：簇头节点收到兴趣包后，若内容存储表CS和LCD均无法与兴趣包匹配时，首先计算各节点的CDi并选择该值最小的节点序列作为桥节点集，簇头节点向所有桥节点发送兴趣包，仅当桥节点的EIT中存在对应的匹配项时才进行转发，否则直接将其丢弃.

6.3 社区感知型路由算法描述

算法2.社区感知型路由算法.

输出：消息的转发路径.

① 更新节点i，更新其生存时间nTTL；

② if 节点i的缓冲区中无待转发的兴趣包

④ end if

⑤ form∈Interests_MSGdo*遍历节点i的缓冲区中所有兴趣包*

⑥ if节点i不是本社区簇头节点

⑦ ifm的nTTL>0

⑩ 执行社区内兴趣包备用转发策略；

7 实验与结果

本文基于机会网络环境[19](opportunistic network environment, ONE)这一平台对BIRI机制进行仿真实现，模拟了在分布式MSN中的消息转发过程.相关参数如表2所示.使用Infocom 2006数据集模拟MSN节点，包含节点的真实运动特征.将BIRI路由机制分别与Epidemic Routing[20]，Bubble Rap Routing[21]，SCAN[22]这3种路由算法进行对比.其中，Epidemic类似于病毒传染，采取基于洪泛思想的多副本路由；Bubble Rap则是基于社区结构的单副本路由机制；SCAN路由则是一种可扩展的内容感知路由机制，可以通过扫描附近的节点内的副本提高投递率.3种对比指标分别为投递率、平均时延和网络开销比率.

Table 2 The Configuration of Simulation表2 仿真配置

7.1 投递率

投递率代表到达目的节点的消息比例.如图1所示，无论是所请求的内容在社区内的情况还是既包括社区内又包括社区外的混合情况，BIRI在该指标上都仅次于Epidemic机制，这是因为Epidemic采取洪泛思想，大大提高了投递率.与另外2种路由机制相比，BIRI机制在进行路由时不仅考虑社交关系、社区结构，还能迅速匹配请求内容信息，使得内容检索不仅速度快而且准确率高，提升了投递率.

Fig. 1 Delivery rate comparison on BIRI, Epidemic, Bubble Rap and SCAN图1 4种算法的投递率比较

7.2 平均时延

Fig. 2 Average latency comparison on BIRI, Epidemic, Bubble Rap and SCAN图2 4种算法的平均时延比较

平均时延体现了路由过程的平均时长.如图2所示，BIRI在该指标上优于SCAN和Bubble Rap.由于SCAN过度依赖附近节点的内容副本且对网络的间歇特性缺乏考虑,而Bubble Rap忽视了社区内的可用内容缓存的作用，分别导致了SCAN和Bubble Rap平均路由时间的增加.而Epidemic因其洪泛特性，平均时延比BIRI更低.另外，相对于图2(a)，图2(b)中BIRI的路由延迟明显增大，这是因为不同社区间进行转发时需要借助桥节点，增加了路由时延.

7.3 网络开销比率

Fig. 3 Network overhead ratio comparison on BIRI, Epidemic, Bubble Rap and SCAN图3 4种算法的开销比率比较

网络开销比率反映了消息在路由过程中对缓存、带宽以及能量等网络资源的消耗，定义为消息转发的总次数与成功送达的消息之差除以消息转发总次数.如图3所示，BIRI机制的网络开销比率仅高于Bubble Rap算法.因为BIRI在社区内路由中划分聚类层次减少了无效的转发次数，且选取合适的桥节点负责跨社区的路由，这些策略不仅能保证准确地找到内容提供者，而且在一定程度上控制了网络开销.Bubble Rap网络开销较小则是因为相比于BIRI的多副本消息传输，Bubble Rap采用单副本消息传输，减小了消息副本数量，相应地降低了网络开销代价.

8 结 论

本文以MSN网络为研究对象，充分挖掘MSN中复杂的社交关系和社区结构，引入ICN以内容为中心的思想，运用网络图论、BBO算法、k-均值聚类算法等，全面深入地研究了基于ICN的MSN社区感知型路由机制，旨在满足MSN用户多样的内容需求并提高MSN动态网络结构中的路由效率.通过对比实验和分析可知，本文提出的BIRI机制在投递率、平均延迟和路由开销比率这3项指标上相比于对比算法表现出了较好的综合性能，是ICN与MSN相结合的初步探索与尝试.但BIRI机制仍存在改进空间，研究BBO算法中不同变异策略对性能的影响并加以改进，以及在现实背景下对其实用性和安全性进行验证和优化是今后研究工作的重点.