机会网络中计算节点间数据分组余弦相似度的高效转发策略

刘名阳,陈志刚,吴 嘉

1(中南大学 软件学院,长沙 410075)2(“移动医疗”教育部-中国移动联合实验室,长沙 410083)

1 引 言

机会网络(Opportunistic networks,OPN)是一种在间歇性连通的网络环境下,通过节点之间的相互移动带来的接触机会,完成网络中的信息转发[1].机会网络源于早期的间歇式连通网络(intermittently connected networks,ICN)[2]和延迟容忍网络(delay-tolerant networks,DTN)[3].机会网络的通信不同于传统的无线网络,最大的不同点就是机会网络中的节点并不是统一部署的,其不需要发送端和接收端之间拥有完全连通的传输路径[4].在机会网络中,由于网络链接时断时续、网络链接持续时间短、网络拓扑结构动态变化[5,6],源节点和目的节点之间往往不存在可靠的通信链路[7].由于应用特点、环境、成本等多种因素的限制,机会网络恰好可以满足某些特定应用的需求.现如今,机会网络的典型应用主要有:野外数据收集[8]、偏远地区网络通信[9]、车载网络[10]以及各种环境下的自组织通讯网络[11]等.

由于机会网络中不存在固定的传输路线,所以采用“存储—携带—转发”的路由机制进行信息传送[12].该方式不需要节点维护到网络中其他节点的路由表,而是将信息缓存到具有存储能力的移动节点上,借助节点的移动带来的相遇机会,寻找合适的下一跳节点进行信息传输.图1为机会网络信息传输过程示意图.假设发送端S和接收端D要进行信息传输,由于在t1时刻发送端S和接收端D并不在同一个连通域内,在它们之间不存一条完整的通信链路,因此节点S将数据发送给中继节点A.由于节点A同样没有到达节点D的合适路径,节点A携带该信息等待合适的转发机会.随着节点移动带来的相遇机会,在t2时刻,节点A和节点C移动到同一连通域内,节点A将数据转发给节点C.节点C在t3时刻与接收端D相遇,将携带的数据转发给接收端D,完成信息传输.

(1) 盾构隧道常见病害之间是相互联系的，往往表现为多种病害同时存在，且随着地铁运营时间的增加病害亦会随之加剧。其中，隧道不均匀沉降是导致产生其他常见病害的重要原因之一，也是判断隧道是否稳定的重要依据之一。

教育教学的过程十分漫长，需要不断地发现与改良，其最终目标是给学习者带来极大的便利与可能性。信息技术便是能够体现该可能性的关键因素，因此，信息技术与教育教学的完美融合是当代教育领域中极为重要的研究项目。通过利用信息技术可以将传统的教育教学方式做出改变，提高“教师”与“学生”的信息素养，将“教”与“学”的方式做出变革，完成信息技术与教育教学完美融合是所有从事教育工作人士不断追求的目标。

图1 机会网络信息传输过程示意图Fig.1 Schematic diagram of opportunistic network transmission

因为机会网络中节点的移动性导致网络拓扑结构呈现出动态变化的趋势,使得传统的路由算法很难应用于机会网络中.因此,如何在拓扑结构中选择合适的邻居节点进行信息传输成为了机会网络的研究热点之一.目前,对于机会网络路由算法的研究主要分为两类,一种类型先验式路由,另一种类型是后应式路由.但由于机会网络中节点自身的移动以及无线连接的间歇性,依然存在传输成功率较低以及下一跳节点选择不合理的问题.

在实际的应用场景中,机会网络中的节点通常是处于一定社会关系的人[13],其进行信息的交互行为与移动模式都具有社会性[14].在以人作为网络终端载体的机会网络中,人的行为特征和社会属性是区别于其他移动网络模式的本质特征[15],在路由算法设计中具有举足轻重的作用.例如,人类移动行为的小世界特性和集聚性可以帮助路由协议利用节点的影响力和社区特征辅助消息转发;人类移动巧为的规律性和社会性可以帮助路由协议预测节点未来的相遇过程,以帮助数据选择最佳的下一跳转发节点.

通过分析一些传统机会网络路由算法存在的问题,结合机会网络“小世界”的特点,本文从节点之间的社会属性角度去考虑如何选择合适的邻居节点作为下一跳,提出了基于节点间数据分组余弦相似度的路由算法.实践证明,余弦相似度算法可以很好的计算出两个文本之间的相似度情况.通过计算节点间数据分组的余弦相似度来衡量节点间社会关系的强弱,以此进行路由选择.

2 相关工作

在机会网络,采用“存储—携带—转发”的传输策略进行数据转发,由于节点的移动导致的网络拓扑结构动态变化,使得传统的路由算法难以适用于机会网络中.因此,如何合理的选择下一跳节点,高效地进行信息传递已成为机会网络的一个重要研究方向[16].现如今,对于对于机会网络路由算法的研究主要有以下一些方法.

Epidemic算法[17]基于泛洪策略,主要的思想就是相遇的节点交换彼此缺少的报文信息.该路由算法可以很好地提高网络传输成功率,有效地降低传输延迟,但是会在网络中产生大量的数据副本,容易导致网络的路由开销过高,造成网络负载.Ren Z[18]等人在传统的Epidemic算法的基础上提出了一种具有自适应能力的Epidemic路由算法,通过观察周围节点的缓存状态,实时调整节点向网络中注入消息副本的数量,进而改善Epidemic算法性能,有效地降低了路由开销.

SIM27≈0.22,SIM28≈0.18,SIM29≈0.13

由于机会网络中节点的移动特性,网络的拓扑机构呈现出动态变化的趋势,整个网络并不是全连通网络,因此在机会网络中随机选取某一子网络拓扑结构进行研究.假设选取的子网络拓扑结构如图2所示,共有12个节点,节点集合为V={V1,V2,…,V12},所有节点均为中继节点,都具有移动的特性以及携带与转发信息的能力.在当前时段,假设节点V1为源节点需要发送信息,并且信息在节点之间传递的速度远远大于节点的移动速度,信息在子网络中进行传输时,网络拓扑结构不会发生本质上的改变.

文献[21]提出了基于历史信息的路由算法(HBPR),将网络的地理区域划分为不同的区域单元并编号,每个节点利用GPS软件记录自身的位置信息,并统计访问最频繁的区域,源节点将一份消息传输给地理位置上与目的节点更近的中继节点,不断缩短携带消息的节点与目的节点的距离,达到与目的节点相遇并传输消息的效果.

文献[22]从机会网络和社交网络相结合的角度考虑,提出了基于节点社会属性的路由算法SNOP.该算法利用节点的社会属性,分析网络中存在的社团结构,并计算社团之间的相似程度与节点在社团中的活跃度,进而有目的性地选择中继节点.该算法并将计算节点之间的社会性与信息转发两项任务拆分开,分别以离线与在线的方式进行,以此实现数据分组的高效转发.

文献[23]提出了SRBet路由算法,在利用时空演化图模型来准确捕捉机会网络的动态拓扑结构的基础上,根据节点历史接触记录,提出基于中介中心性度量的社会关系,以确保消息通过具有更强社会关系的节点进行转发.

针对机会网络路由算法存在的一些问题,本文从网络中节点间存在的关系进行分析,提出了基于节点间数据分组余弦相似度的高效转发算法CSDP.在该算法下,首先计算节点间数据分组的余弦相似度,以此来定义节点之间的关系,根据节点之间的相似程度选择下一跳进行数据转发.

3 基于节点间余弦相似度的高效转发策略

3.1 构建机会网络拓扑结构

文献[20]通过对节点存在的社会属性进行分析,提出了一种基于节点归属位置感知的转发策略.该策略首先是根据节点的社会属性,对网络中的节点进行社区划分.然后在节点的移动过程中,检测副本消息的接收端是否与相遇的节点在相同的社区.根据与相遇节点的检测结果,进而执行社区内转发策略或是社区间转发策略.在相遇的同时,根据相遇节点与目的节点之间的相邻程度,为副本信息选择合理的转发节点.

在机会网络中,每个节点的邻居节点都可以进行信息传递,每个邻居节点都有可能成为下一跳节点.相对于动态变化的网络拓扑结构,在以人为载体的机会网络中,节点之间的社会关系则是相对比较稳定的,并不会随着拓扑结构的变化而变化,而节点所呈现的社会性则具体表现在其自身携带的数据上.因此需要在众多的邻居节点之间选择一些相对比较可靠、社会关系比较稳定且有效性较大的节点进行信息传递.本文是利用余弦相似度来计算节点间所携带数据分组的相似度,节点间数据分组的相似度等同于节点间的相似度,从而来定义节点之间社会关系的强弱.

“孟母三迁”的故事意在阐述环境对人成长的重要意义。以美国行为主义者华生为代表的西方学者也提出环境决定论，认为儿童是被动的个体，其成长由所处的环境决定。儿童成长为什么样的人，教育者负有很大的责任。

图2 子网络拓扑结构图Fig.2 Topology structure of sub-network

3.2 节点定义及相似度计算

定义1.节点数据分组合集Di={di1,di2,…,dij},表示任一节点i所携带的j个数据分组信息,并将节点i所携带的数据分组信息表达为向量Ci=(wi1,wi2,…,wij),其中wij为第j个数据分组信息在节点i中的权重,即该数据分组在节点i中出现的频率,初始值为1.

实验中，由于直接测量主轴热变形不太方便，所以用一根铁棒来代替主轴，把铁棒用磁性表座固定在主轴上，间接获得主轴径向与轴向变形。然后通过电涡流位移传感器测得这两个方向上的热误差数据。

定义2.任意两个节点a与b的数据分组合集的合并运算,记为D′=Da∪Db,并在合并之后的数据分组合集基础上,重新计算各自的数据分组向量表达式.

设节点a共有n个数据分组信息,其合集为:

Da={da1,da2,…,dai,…,dan},1≤i≤n

(1)

则节点a的数据分组信息可表达为向量Ca:

Ca=(wa1,wa2,…,wai,…,wan),1≤i≤n

(2)

设节点共m有个数据分组信息,其合集为:

Db={db1,db2,…,dbj,…,dbm},1≤j≤m

(3)

则节点b的数据分组信息可表达为向量Cb:

Cb=(wb1,wb2,…,wbj,…,wbm),1≤j≤m

(4)

节点a和节点b的数据分组合并运算,记为:

(5)

(6)

2)依次访问节点V2、V3、V4、V5、V6,计算它们与当前节点的相似度.节点V1和节点V2的相似度计算过程如下:

(7)

(8)

1)初始化一棵有向树Tree,每个节点i都维持一个数据分组集合Di,以及数据分组向量Ci,将当前要传送信息的节点s作为树Tree的根节点.

(9)

定义3.节点相似度SIMab,表示节点a和节点b之间的相似程度.

已知向量Q和向量D之间余弦相似度为:

人们也将由裁判官创造的“三重告示”的时间锁定在公元前2世纪，其因包含了三项诉权而得名：“在特有产的限度内”(actio de peculio)、“在权力拥有者获益的限度内”(actio de in rem verso)以及“根据从权力拥有者处接收的命令”(actio quod iussu)。它们被用来给那些与处于他人权力下之人完成了交易的债权人使用，就像告示使用的话语指出的那样，“基于与处在他人权力下的人缔结了一笔交易的情况”，由乌尔比安记录在D. 15,1,1 pr.-2(乌尔比安：《告示评注》第29卷)当中：

我告诉寝室的阿莲我爱上了一个35岁的男人时，她不动声色地看着我半分钟，然后从嘴里挤出三个字儿，有病啊。

(10)

(11)

定义4.邻居节点访问控制数K,用来控制节点访问其邻居节点的个数.当一个节点的邻居节点的数量比较多时,要把所有的邻居节点完全遍历一遍时会花费比较长的时间,这会造成更长时间的传输延迟,不利于信息在网络中传递.因此,当节点的邻居数大于访问控制数K时,则根据该节点与其各邻居节点的传输距离进行排序,优先访问前K个传输距离相对比较近的邻居节点,这样可以有效地减少CSDP算法的计算时间,避免了随着网络中节点数量的增加而节点之间对比的次数显著增加的情况.

定义5.节点相似度下阈值α,作为下一跳候选节点筛选标准.当一个节点与其邻居节点的相似度大于下阈值时,则将该邻居节点作为下一跳候选节点.如果求得一个节点与其所有的邻居节点的相似度都小于下阈值α,则选择其中相似度最大的节点进行信息传输.

丙组40例患者应用培美曲塞联合顺铂治疗，即给予患者静脉滴注135 mg/m2培美曲塞+25mg/m2顺铂。

定义6.节点相似度上阈值β.在以人为载体的机会网络中,如果一个节点与其一个邻居节点的相似度大于上阈值β时,则表明该两个节点的社会属性十分相似,可能它们的移动轨迹,能接触到的节点都没有太大的区别,所以就没有必要把这个邻居节点作为下一跳的候选节点.如果一个节点与其所有邻居节点的相似度都大于上阈值β,则选择其中相似度最小的节点进行信息传输.

农民是从事农业生产的主体人员，因此农民的自身素质对于设施农业的发展有直接影响。农民对于机械的使用认识程度不高，是影响设施农业发展的重要原因之一。所以，可以向农民开展“如何致富”、“如何增加粮食产量”为主题的指导课程，通过课程向农民讲解设施农业机械化的重要性，提高农民对机械的使用意识和市场竞争意识，向农民明确使用机械设施会减少人力劳动的投入、提高生产效率、科学的种植能够提高农作物的产量、能够提高农民的经济效益。农民对于设施农业有正确的认识，才能积极使用设施农业机械设备，进而推动我国设施农业的发展水平。

如果求得一个节点与一部分邻居节点的相似度小于相似度下阈值α,而与剩下一部分邻居节点的相似度大于相似度上阈值β,则在所有相似度小于下阈值α的邻居节点中,选择相似度最大的邻居节点,以及在所有相似度大于上阈值β的邻居节点中,选择相似度最小的邻居节点进行信息传输.

3.3 节点信息遍历过

如图2所示的子网络拓扑结构中每个节点维护一个缓冲区,缓冲区中存放本节点和其他节点需要本节点转发的数据分组,每个数据分组有一个全局唯一的标识.假设该子网络拓扑结构中每个节点的数据分组如表1所示.

4:Set:T.setRootNode(i);Ui;/*A set of neighbor nodes of node i*/

基于图2的节点遍历过程如下所示:

1)首先,初始化一颗有向树Tree,把当前要发送信息的节点V1作为根节点,按照与节点V1的传输距离依次将前K个邻居节点插入树中作为节点V1的子节点,如图3所示.

①合并节点V1与V2数据分组合集:

D12=D1∪D2={b,c,d,j,p,k}

表1 节点数据分组
Table 1 Data packet of nodes

节点数据分组合集数据分组向量V1{b,c,j,k}(1,1,2,1)V2{d,j,p}(1,1,1)V3{a,c,d}(1,1,2)V4{a,e,k,o}(2,2,1,1)V5{a,e,j,k}(1,1,1,2)V6{a,b,j,k}(1,1,2,2)V7{b,p,n,t}(2,1,1,1)V8{d,g,h,n}(1,2,2,1)V9{c,k,m,n,p}(2,3,2,1,1)V10{b,a,e,k}(1,1,1,2)V11{a,e,j,k}(1,1,1,1)V12{a,c,j,p}(1,2,1,3)

②重新计算节点V1与V2的数据分组向量:

嗜水气单胞菌、鲁氏不动杆菌、温和气单胞菌等均可导致腐皮病的发生，外伤、营养不良和水质恶化是该病发生的重要诱因。特别是在蛙池内无饲料或投喂量不足时，会出现大蛙残食小蛙现象，造成小蛙挣扎逃脱后头背部位皮肤受损，诱发腐皮病。该病流行于夏、秋两季，8-10月份是发病的高峰期。该病具有发病快、病期长、致死率高等特点，幼蛙死亡率高达90%，且常与红腿病并发。

图3 树Tree结构图Fig.3 Structure of the Tree

③计算节点V1与V2的相似度:

(12)

根据上述节点V1与V2的计算过程,计算节点V1与V3、V4、V5、V6的相似度.结果如下:

SIM13≈0.15,SIM14≈0.12,SIM15≈0.57,SIM16≈0.84.

假设其中SIM13和SIM14都小于下阈值α;SIM16大于上阈值β;SIM12和SIM15的值位于下阈值和上阈值之间.

所以,将节点V3、V4和V6从树Tree中删除,留下节点V2与V5作为节点V1的下一跳,并把节点V2与V5的邻居节点按照传输距离优先将前K个节点插入树中,作为相应节点的子节点.此时,树Tree的结构图如图4所示.

一般说来，学者在进入村落进行调查的时候，多会寻找合适的合作者。他们不仅能够提供丰富的乡村生活资料，还能为学者搭建更多的田野关系提供便利。正如劳格文所言：

3)依次访问节点V2的邻居节点V7、V8与V9,以及节点V5的邻居节点V10、V11、与V12,计算相应节点之间的相似度.结果如下:

文献[19]提出了喷洒等待(Spray and Wait)算法,该算法分为两个阶段:Spray阶段,发送端将自身携带的报文信息按照一定的数量转发出去,若没有发送到接收端则进入Wait阶段;Wait阶段,携带该报文信息的节点通过直接传递的策略把信息传输到接收端.Spray and Wait算法的主要优点就是路由开销显著地小于Epidemic算法,有更好的扩展性,能够很好地适应各种规模的机会网络.

SIM5,10≈0.86,SIM5,11≈0.96,SIM5,12≈0.20.

假设SIM27、SIM28和SIM29都小于下阈值α,此时将其中与节点V2相似度最大的节点V7保留,删除剩余的节点V8与V9.

假设SIM5,10与SIM5,11均大于上阈值β,而SIM5,12小于下阈值α,则在小于下阈值的节点中保留相似度最大的节点V12,在大于上阈值的节点中保留相似度最小的节点V10,删除剩余节点V11.

图4 树Tree结构图Fig.4 Structure of the Tree

此时,子网络拓扑结构已经遍历完毕,得到最终的有向树Tree,如图5所示,即为该子网络的传输路径图.

图5 传输路径图Fig.5 Transmission paths

3.4 算法设计

根据上一小节的节点在子网络拓扑结构中的遍历过程推导出基于节点间数据分组余弦相似度的路由算法,具体的算法执行过程如下:

2)创建当前节点s的邻居节点集合Us,若是在树Tree中存在当前节点s的父节点p,则创建父节点的邻居节点集合Up,并作如下运算:Us=Us-(Us∩Up).

3)判断集合Us中节点的个数是否大于K,若集合Us中的节点个数大于访问控制数K,则对集合Us中的节点按照与当前节点的传输距离由近至远排序,将前K个节点一次插入树Tree中,作为当前节点s的子节点.

5)判断当前节点与各邻居节点之间的相似度大小,选择SIMsk值大小在下阈值α和上阈值β之间的节点作为下一跳,并将其余节点从树中删除.

如果与所有的邻居节点的相似度都小于下阈值,即max(SIMsk)<α,则从中选择相似度最大的邻居节点,即max(SIMsk),作为下一跳,并将其余节点从树中删除;

如果min(SIMsk)>β,则选择相似度最小的邻居节点,即min(SIMsk),作为下一跳,并将其余节点从树中删除;

如果与一部分邻居节点的相似度小于下阈值α,与剩余邻居节点的相似度大于上阈值β,则在所有相似度小于下阈值α的邻居节点中,选择相似度最大的邻居节点,以及在所有相似度大于上阈值β的邻居节点中,选择相似度最小的邻居节点作为下一跳,并将其余节点从树中删除.

6)依次把当前节点s在树Tree中的所有子节点作为当前节点,重复2)、3)、4)、5)、6),直至访问完子网络拓扑结构.

7)根据上述过程,最终可以得到一个树Tree,可以得到一条或多条传输路径,将当前要发送信息的节点通过复制转发策略在这些路径上进行转发.

根据上述算法的推导过程,可以设计相似度算法,如下所示：

算法1.Opportunistic Network Routing Algorithm Based on Cosine similarity of data packets between nodes

1:Input:A graph G(V,E),a source S,Dz:Data packet aggregation of node z,Cz:Data packet weight vector of node z collection of z(z∈V);

2:Output:A or more paths.

3:Init:InitTree(T),CurrentNode(i,s);/*set the node s as the current node i*/

当上述曲面为球面时，设球面为Sβ，如图4所示，其中oimmobile-ximmobileyimmobilezimmobile为实验室坐标系.此时，(10)式中的Gauss曲率K为球面半径平方的倒数.若沿Sβ上的一条闭曲线平移矢量一周后，与平移前相比的角度差别为：

5:if(Node p=T.getParentNode(i));Up;Ui=Ui-(Ui∩Up);

我一个很好的同事经常和我抱怨类似的事情，他是一个对熟悉的人很随和的人，但是却很容易与其他专业的人员发生矛盾。在一次他在电话中的激烈争吵后，我问其原因，他说，是由于对方人员提供的设计资料不够规范，虽然资料已经进行多次修改，但是还是没有符合要求，于是对方人员误以为是我方进行故意刁难，所以发生了激烈的争吵。

/*if the node i has parent node p in the tree T,set the node sets of p,and delete the same part from the Uias Up*/

采用SPSS 20.0统计学软件对数据进行处理，计量资料以“±s”表示；计数资料以百分数（%）表示，以P＜0.05为差异有统计学意义。

6:SortbyDistance(Us);Us.Delete(K);/*Sorting neighbor nodes in Uiaccording to the transmission distance,and delete the neighbor nodes after K*/

7:while(! Empty(Ui))

8:for(Neighbor j:Ui)

11:end for;

12:SelectSim(SIMij);T.setChildNode(i,j)/*select the similarity between r and R*/

13:If(all(SIMij)<αor all(SIMij)>β)selectNode(max(SIMij)or min(SIMij));

T.setChildNode(i,j);

14:If(onePart(SIMij)<αand theRest(SIMij)>β)selectNode(max(onePart)and min(theRest));T.setChildNode(i,j);

15:for(ChildNode k:T.getChildNode(i))

16:CurrentNode(i,k),continue;

17:end for;

18:Node p=T.getParentNode(i);Up;

Ui= Ui- Up;Sort(Ui);Ui.Delete(K);

19:end while;

20:getPath(T);/*Gets the transmission paths based on the tree T*/

上述算法的执行主体是一个双层嵌套循环,用来计算当前节点和邻居节点之间的相似程度,并对其作一定规则的筛选,选择出合适的下一跳节点.整个算法的时间复杂度为O(n2),算法的复杂度相对较高,整个计算过程会占用大量的时间,容易造成高的传输延迟,但是由于定义了邻居节点访问控制数K,将要访问的邻居节点控制在一定的范围内,有效地降低了计算过程需要消耗的时间.

4 实验结果与分析

针对上述过程提出的CSDP路由算法,本文将采用机会网络仿真平台ONE,并于传统的路由算法Spray and Wait(S&W)算法和Epidemic算法进行方针实验对比.文中将选用传输成功率、传输延迟和路由开销这三个指标对上述的三个算法进行比较分析.仿真场景设置如表2所示.

表2 仿真场景设置
Table 2 Simulation parameter setting

参数值模拟时间15h模拟区域范围4500m*3000m节点移动速度2～10(m/s)节点传输速率300kb/s最大传输范围10m传输方式广播通信方式蓝牙节点缓存大小15MB数据分组大小25kb～100kb数据分组生成频度25～35s

表3为算法参数设置,通过多次的仿真实验表明,当下阈值α=0.26,上阈值β=0.83时,CSDP算法的综合性能相对较好,且邻居节点访问控制数K位6或7时,不会显著地增加节点之间的比较次数,可以有效地降低算法的执行时间.

表3 算法参数设置
Table 3 Algorithm parameter setting

参数值α0.26β0.83K6、7

下面是CSDP算法、S&W算法和Epidemic算法在不同情况下的分析比较.图6为三种路由算法在不同的节点缓存的情况下传输成功率.

图6 传输成功率(节点缓存)Fig.6 Deliver ratio(node cache)

根据图6可知,节点缓存大小对CSDP算法传输成功率的影响最为显著.在节点缓存非常小的情况下,三种算法的传输成功率都很低,随着节点缓存的不断增大,三种算法的传输成功率都呈现出了不同程度的增长趋势.S&W算法和Epidemic算法的传输成功率呈现出了缓慢的增长趋势,当节点缓存在50M时,S&W算法和Epidemic算法的传输成功率分别维持在60%和50%左右.而CSDP算法的传输成功率的增长趋势比较快速,当节点缓存在25M时,CSDP算法的传输成功率就已经达到了S&W算法和Epidemic算法的最高水平,最终,CSDP算法的传输成功率可以达到85%左右.

图7为节点数量对三种算法传输成功率的影响.整体趋势和节点缓存比较相似,不同的是,在节点缓存不断变大的情况下,Epidemic算法的传输成功率一直高于S&W算法,而在节点数量不断增多时,S&W算法的传输成功率一直高于Epidemic算法.这说明Epidemic算法比较依赖节点的缓存大小,而S&W算法比较依赖网络中的节点数量.当网络中的节点数量达到600时,Epidemic算法和S&W算法和的传输成功率分别为45%和55%,而CSDP算法的传输成功率高达80%左右.

图7 传输成功率Fig.7 Deliver ratio

图8为三种算法的传输延迟在节点数不同情况下的表现.CSDP算法的传输延迟受节点变化的影响最小,S&W算法和Epidemic算法的传输延迟呈现出相同的增长趋势.在节点数为600的情况下,Epidemic算法和S&W算法的传输延迟分别高达6500和5500左右.而CSDP算法传输延迟的增长速度比较缓慢,在节点数大于400以后,CSDP算法的传输延迟一直维持在3000上下,要比S&W算法低2500,还不到Epidemic算法的二分之一.

图8 传输延迟Fig.8 Delivery delay

图9为节点数对三种算法路由开销的影响.随着节点数不断增加,三种算法的路由开销呈现出不同的增长趋势.其中,Epidemic算法的路由开销增长速率最快,约为Epidemic算法的两倍,约为CSDP算法的三倍.当网络中的节点数高达600时,S&W算法在2500左右,Epidemic算法的路由开销在4500左右,而CSDP算法的路由开销最低,在1500左右.因为Epidemic算法是基于泛洪策略,会在网络中产生大量的副本消息,造成网络的路由开销过大,而CSDP算法则是基于节点之间的关系进行信息转发,不会在网络中产生过多的副本消息.

图9 路由开销Fig.9 Routing overhead

上述的仿真结果表明,相对于传统的路由算法,S&W算法和Epidemic算法,CSDP算法更加适应机会网络数据转发,可以有效地提高传输成功率,并降低网络的传输延迟以及路由开销.

5 结束语

对于机会网络数据转发过程中存在的问题,本文从节点间关系进行分析,提出了基于节点间数据分组余弦相似度的转发策略,通过计算节点间数据分组的余弦相似度来定义节点间社会关系的强弱,并通过一系列阈值的定义,用来筛选邻居节点,最终可以在子网中得到多条有效的传输路径.通过仿真实验表明,CSDP算法要比传统的路由算法S&W 和Epidemic效果好很多,CSDP算法在提高机会网络传输成功率的同时,可以有效地减少传输延迟,降低路由开销.实际上,节点的社会属性是十分复杂的,消息在节点间的传播过程会受到各种因素的影响,如节点的移动模型,以及节点所在的社群等等,对上述因素进行综合分析是下一步工作的重点.