一种基于节点相似度和活跃度的数据转发算法

汪晶明， 王青山， 沈 进， 刘 静， 时宽凯

（合肥工业大学 数学学院，安徽 合肥 230009）

0 引 言

延迟容忍网络（delay tolerant network，DTN）又称容迟网络，是指一类特殊的无线网络，主要应用于海洋监测、卫星通信［1］、汽车网络［2］、移动社交网络［3］、军事网络［4］及偏远地区通信等领域。在该网络中端到端的路径通常很难建立，所以网络中的消息传播具有很大的延时。但在容迟网络中，由于节点运动的不确定性和节点的密度不同造成网络一般不存在端到端的路径，因此传统的无线网络算法已经不适用于容迟网络。

移动社交网络（mobile social networks，MSNets）是容迟网络中的一种，也是近年来研究的一个热点问题。在移动社交网络中，即使没有网络基础设施或端到端的连接，也能通过用户移动的相互作用，从而达到网络服务的目的，该网络不需要一些网络基础设施，因此可用于广域传感器网络中［5－6］等关键领域。移动社交网络可视为一种具有社会意识的容迟网络，随着智能手机、车载移动终端等多种移动设备的普及以及传感网络技术的广泛应用，移动社交网络已经开始得到更多人的关注。

移动社交网络中，节点移动与其他节点相遇而形成通信机会，消息随着节点的移动而传播，在节点之间转发从而实现传输。由于数据传播具有间歇性和不确定性，因此设计一种高效的转发算法是实现数据传输的关键。近年来，国内外相关研究人员已经对社交网络的转发算法进行了大量的研究，并取得了一定的成果。从实际的跟踪文件中发现，在移动社交网络中，用户通常会有几个经常有规律移动的区域，根据该规律本文建立了社区网络模型。

目前较为经典的转发算法有基于复制、基于效用以及基于社会属性的转发算法。基于复制的转发算法是在传输信息时产生多份拷贝信息，通过增加网络中消息拷贝数目来提高数据传输率，如Epidemic算法［7］和自我限制的传染性转发算法［8］。基于效用的转发算法利用网络中节点的状态信息来决定节点相遇时是否转发消息，建立一个预测函数来估计节点的效用，节点的效用越高，遇到目的节点的概率越高，如概率路由（probabilistie routing）算法［9］和基于搜索聚焦（seek and focus）的转发算法［10］。基于社会属性的转发算法根据节点的社会属性（影响力、价值及能力等）来选择转发节点，如Label算法［11］和基于信任为基础的路由转发算法［12］。

然而在以往基于社会属性的转发算法［13］中只考虑了单个节点的社会属性，对通过多个节点共同作用得到的社会属性考虑很少，本文主要通过2个节点共同形成的社会属性以及节点的相似度和活跃度的数据概念，提出一种基于节点相似度和活跃度的数据转发算法（data forwarding algorithm based on the similarity and activity of nodes，DASA）。通过仿真实验，与Epidemic算法和Label算法以及Greedy Total算法［14］进行比较，得出本文提出的算法可提高数据的传递率，同时能够大大降低网络资源的消耗。

1 网络模型建立

社区定义为一些成员通过直接联系或一些中间个体间接联系而形成的一个群体。通常一个社区中的成员有一些共同的社会属性，如共同的爱好、相似的社会功能。比如在同一个俱乐部的成员有相同的爱好，相互交流的机会比较多，从而会形成一个社区；在公司中，同一个办公室的员工彼此交流比较频繁，就会形成一个群体。从以往的跟踪数据中发现，在移动社交网络中，人们的移动具有一定的规律性，从而通常会形成若干个社区。

定义1 对一个群体用户根据他们的兴趣爱好和地理定位，他们相互联系的区域定义为一个社区。社区网络可表示为：

其中，ci（1≤i≤J）为第i个社区；C为社区网络。

由于地理位置和人们的兴趣爱好等原因，一个社区网络会形成了不同的社区，其划分如图1所示。

图1 社区网络划分

本文将时间t分割成若干个很小的等长时间段t＝｛t1，t2，…｝。为了表示出社区网络在时间段ti的状态，本文使用该时间段内各社区上所有节点的集合来表示在时间段ti社区网络的状态，具体如下：

其中，cti，k（1≤k≤J）为在ti时间段社区ck中节点的集合；Cti为网络节点在ti时间段的一个划分，具体实例，如图2所示。

图2 ti时间段社区网络状态

在图2中，ti时间段社区c1、c2、c3、c4中节点集合分别为：

则在ti时间段社区网络的状态为：

2 DASA算法

DASA算法以节点的相似度和活跃度为基础，运用节点运动所遇到的节点个数和邻居分别对节点的活跃度和相似度进行建模计算。通过对转发条件和拷贝数目的控制，达到提高消息传递率，降低网络资源消耗的目的。

节点的相似度是指节点移动范围和所遇节点的相似程度。在选择节点转发时，考虑到有些节点和携带数据包的节点相似，就不需要把包转发给那些节点，从而提高了传递率，降低了拷贝数目。本文通过在一定时间内节点所遇相同邻居个数来计算相似度。

定义2 在一段时间内节点i和j在相同社区内碰到的共同节点个数与它们所遇节点总数的比值，称为节点i和j的相似度，即

其中，K为遇到总的节点数目；k为在相同社区中所遇共同节点个数。

节点的活跃度是指节点活动能力的大小，活动能力是指在一定的时间内所遇节点的数目。由于每个人的活动范围和活动能力各不相同，活动能力越大则说明其移动的范围越广，接触的节点越多，则传输到目的节点的概率就比较大，这种活动能力称为活跃度。活跃度越大则说明能接触的节点越多，因此能够成功转发到目的节点的机会越大。

定义3 节点i的活跃度A（i）表示它的邻居的个数。

当两节点i、j相遇时，节点i是否把包传递给节点j，取决于节点j的活跃度A（j）是否大于节点i的活跃度A（i），只有满足该条件时才可能传包。根据定义可知，节点i、j相遇时他们的邻居个数是计算活跃度的指标，记Si为节点i的邻居集合，Sj为节点j的邻居集合，节点i遇到节点j是否传包的表达式如下：

其中，G（i，j）表示是否传包情况，如果节点i可能传包给节点j，则为1；否则为0。

本文设定一个相似度的阈值α，若节点i和节点j的相似度小于该阈值，可以选择它作为待选节点，否则不转发。考虑它们的活跃度，若节点j的活跃度大于节点i的活跃度，就直接转发，相反不转发。DASA算法的具体描述如下：

当节点i遇到节点j，如果j是目的节点则直接转发；如果不是，则根据节点间的相似度和活跃度来判断是否转发，有效选择转发节点，可以提高传输的成功率，降低了网络资源的消耗。

3 模拟实验结果和分析

本文用C＋＋语言开发了一个模拟器来研究DASA算法、Epidemic算法、Label算法和Greedy Total算法在移动社交网络中的性能。其中Greedy Total算法的主要思想是当节点j遇到节点i时，如果节点j遇到的节点数目比节点i遇到的多，则把信息传递给j，反之则不传。

本文选择了Infocom 06的节点［15］移动轨迹作为节点移动模式，共设置了98个节点，其中有20个AP（不动节点），每个AP分别放置在20个不同的社区内。随机产生了200对源节点和目的节点通信，为了简单起见，假设每对源节点向目的节点发送1个数据包。DASA算法初始时在源节点处产生的数据包数量L设置为200。本文主要比较以下3个方面的性能：

（1）消息的传递率。即目的节点成功收到消息与源节点产生消息数目的比值。

（2）平均延迟。即成功传送的消息中，消息到达目的节点的时间与消息从源节点产生的时间差的平均值。

（3）拷贝数目。即整个网络中复制转发的消息数目。

通过改变DASA算法中源节点初始数据包数量L来评价4种算法性能，实验结果如图3所示。

在图3a中，随着数据包数量L的增加，4种算法的传递率均减小，这是由于随着包数目的增多，算法的性能更加稳定。同时可以看出，DASA算法略差于Epidemic算法和Greedy Total算法，但是优于Label算法。

由图3b可以看出，随着数据包数量L的增加，4种算法的平均延迟都有所增加，DASA算法的平均延迟虽然比Epidemic算法、Label算法和Greedy Total算法略差，但其传递率和拷贝数目均优于Label算法。

由图3c可看出，DASA算法的拷贝数目比Epidemic算法、Label算法和Greedy Total算法的拷贝数目少很多，相对于Epidemic算法最多能少73.21%，对于Label算法最多能少54.08%，对于Greedy Total算法最多能少47.21%，其主要原因是由于DASA算法具有在较高的传递率下，通过选择性地选择下一节点，可减少拷贝数目。

通过将算法中数据包的生存时间（time to live，TTL）从12～44h来评价4种算法性能，实验结果如图4所示。

在图4a中，随着TTL时间的增加，4种算法的传递率均有所增加，这是由于随着包存活时间的增长，使得转发成功的概率变大，传递率有所增加，可以看出4种算法的变化趋势基本相同。DASA算法的传递率略低于Epidemic算法和Greedy Total算法，但优于Label算法，最多能高3.89%。

由图4b可以看出，随着TTL时间的增加，4种算法的平均延迟都有所增加，并且增加的趋势和幅度都基本相同。

由图4c可以看出，随着TTL时间的推移，拷贝数目变化很小，因此TTL对拷贝数目的影响不大。DASA算法的拷贝数目明显比Epidemic算法和Label算法的拷贝数目少很多，最多比Epidemic算法少73.14%，比 Label算法少54.61%，比Greedy Total算法少46.21%。

图3 源节点初始数据包的个数对算法的影响

图4 TTL对算法的影响

改变DASA算法中相似度的阈值来测试算法的性能，实验结果如图5所示。

由图5a可看出，随着相似度值的增大，DASA算法传递率逐渐增高，通过算法设计可知，相似度的阈值越高，就有更多的节点可以满足相似度这一限制条件，则参与传播数据的节点增多导致传递率明显升高。由图5b可以看出，随着相似度的增加，算法的平均延迟有所增加。由图5c可看出，增大相似度的值意味着有更多的节点选择，使拷贝副本随之增加。

图5 相似度阈值对DASA算法的影响

4 结束语

本文研究了在移动社交网络中节点间信息的转发机制，根据用户移动的一般规律性，建立网络社区模型，并给出了节点的相似度和活跃度的概念，提出了一种基于节点相似度和活跃度的数据转发算法（DASA）。实验结果表明，DASA算法与Epidemic算法、Label算法和Greedy Total算法相比，明显地减少了网络拷贝数目，降低了网络开销，同时在传递率方面优于Label算法。

［1］ Caini C，Firrincieli R.Application of contact graph routing to LEO satellite DTN communications［C］／／2012IEEE International Conference on Communications（ICC）.Ottawa，ON：IEEE Press，2012：3301－3305.

［2］ Zhang L，Peng L，Zhang Y，et al.Urban bus transport network optimization from complex network［C］／／2012Proceedings of International Conference on Modelling，Identification ＆ Control（ICMIC）.Wuhan，Hubei，China：IEEE Press，2012：1159－1164.

［3］ Zhao P，Zhao J，Wang W.Division of mobile social network based on user behavior［C］／／2013International Conference on Wavelet Analysis and Pattern Recognition （ICWAPR）.Tianjin：IEEE Press，2013：148－152.

［4］ Tauil M，kant L，McAuley A，et al.Capacity estimation and waveform assignment in military networks［C］／／MILCOM 2012，Military Communications Conference.Orlando，FL：IEEE Press，2012：1－6.

［5］ Said H，Guimaraes M，Al Mutawa N，et al.Forensics and war－driving on unsecured wireless network［C］／／2011International Conference for Internet Technology and Secured Transactions（ICITST）.Abu Dhabi：IEEE Press，2011：19－24.

［6］ Shen Jian，Moh S，Chung I，et al.Buffer scheme optimization of epidemic routing in delay tolerant networks［J］.Journal of Communications and Networks，2014，16：656－666.

［7］ Vahdat A，Becker D.Epidemic routing for partially connected ad hoc networks［EB／OL］.（2014－02－05）.http：／／citeseerx.ist.psu.edu／viewdoc／download？doi＝10.1.1.160.5495＆rep＝rep1＆type＝pdf.

［8］ Ramanathan R，Hansen R，Basu P，et al.Prioritized epidemic routing for opportunistic networks［C］／／Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking，2007：1－5.

［9］ Yin L，Lu H，Cao Y.Probabilistic delay routing for delay tolerant networks［C］／／10th International Conference on Advanced Communication Technology.Gangwon－Do：IEEE Press，2008：191－195.

［10］ Spyropoulos T，Psounis K，Raghavendra C.Efficient routing in intermittently connected mobile networks：the single－copy case［J］.IEEE／ACM Transactions on Networking，2008，16：63－76.

［11］ Pan H，Crowcroft J.How small labels create big improvements［C］／／Fifth Annual IEEE international Conference.White Plains：IEEE Press，2007：65－70.

［12］ Liu Y，Li L，Li Z，et al.Trust－based optimized routing scheme in mobile social networks［C］／／2013International Conference on Communications，Circuits and Systems（ICCCAS）.Chengdu：IEEE Press，2013：87－90.

［13］ Tang J，Kim S.Theme－based mobile social network system［C］／／Dependable，Autonomic and Secure Computing（DASC），2011Ninth International Conference on.IEEE，2011：1089－1095.

［14］ Erramill V，Chaintreau A，Crovella M，et al.Diversity of forwarding paths in pocket switched networks［C］／／IMC’07，Proceedings of the 2007ACM SIGCOMM Internet Measurement Conference，2007.doi＝10.1.1.72.6472.

［15］ Scott J，Gass R，Crowcroft J，et al.CRAWDAD data set cambridge／haggle［EB／OL］.（2009－05－29）.http：／／crawdad.cs.dartmouth.edu／haggle.