移动社交网络中基于影响力的数据转发算法

刘艳萍， 王青山， 王 琦， 付沙沙， 任丽丽

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

移动社交网络中基于影响力的数据转发算法

刘艳萍， 王青山， 王 琦， 付沙沙， 任丽丽

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

在移动社交网络中，人们通过携带无线设备在近距离范围内彼此传递信息，从而达到信息的传播。由于移动社交网络中一般不存在端到端的连接，使得数据转发算法成为一个重要问题。文章从社区和节点的社会属性角度，利用社区和节点的影响力，提出了一种基于影响力的数据转发算法（data forwarding algorithm based on impact，DFAI）。在该算法中，携带数据包的节点只有在遇到影响力达到一定要求的节点时，才拷贝数据包给相遇节点。仿真试验结果显示，与经典的Epidemic和Label算法相比，DFAI可以明显降低网络开销，同时接近Epidemic算法达到的最大传递率。

移动社交网络；影响力；转发；延迟

网络中由于节点密度稀疏、电量有限等原因导致数据在传输过程中不能确保端到端之间存在一条路径，这类网络被称为时延容忍网络，也叫容迟网络（delay and disruption－tolerant interoperable networking，DTN）［1－2］。DTN 的提出是为了解决网络中端到端连接和节点资源都有限的问题，满足随意异步消息的可靠传递。DTN的研究和发展将为军事战争、航天通信、灾难恢复、应急抢险等领域的消息交互提供有力的科学理论和技术支持，并会有力地推进未来网络通信智能化、泛在化、融合化的发展。

移动社交网络是DTN网络［3］应用中的一种，即携带移动无线终端设备的网络节点通过设备近距离传递数据并共享网络中的服务。近年来，智能手机和无线网络技术（WIFI、3G、蓝牙等）的发展使得移动社交网络成为无线网络研究领域的一个热点问题。由于在一般情况下此网络中不存在端到端的连接，所以传统的路由协议无法直接应用于移动社交网络，因此数据转发策略是一个关键且极具挑战性的问题。在移动社交网络中往往采取“存储－携带－转发”的方法来传输报文。Epidemic算法［4］是信息在相遇节点之间存储并被转发给所有相邻节点，达到最大化传递率和最小化延迟的目的；但是，该算法容易引起信息洪泛和较多资源开销，受缓存及带宽影响很大，因此一些路由算法期望以较低的开销达到Epidemic算法的传递率和延迟性能。Spray and Wait算法［5］和 Spray and Focus算法［6］都将路由算法分为2个阶段，第1阶段称为喷洒（spray），即在网络中产生固定数目的拷贝进行传播；第2阶段分别为等待（wait）和焦点（focus），在等待阶段携带数据包的节点除碰到目的节点外，不再传播数据包，在焦点阶段携带数据包的节点除碰到目的节点或效用值比本节点高的节点外，不再传播数据包。Delegation forwarding算法［7］假定每个节点都有一个相关的质量参数，节点在遇到质量参数比之前遇到的任何节点质量参数都高的节点时才转发数据包；该算法虽然思想简单，但有效地减少了资源开销。

近年来的研究热点是利用人类的社会联系模式设计路由算法，Label算法［8］针对同一社区的节点联系紧密的特性，仅将数据包拷贝给目的节点所在的社区节点，从而大大提高了数据包传输的效率。Bubble rap算法［9］从社区以及节点的中心性2个方面来设计转发算法；在该算法中，每个节点具有全局秩和局部秩，当携带数据包的节点A和一个节点B相遇时，在以下2种情况下节点A产生一个拷贝给节点B：①节点A、B和目的节点同时属于同一社区且节点A的局部秩比节点B大；② 节点A和目的节点不属于同一社区，如果节点B和目的节点属于同一社区或者节点B全局秩比节点A大。Del Que算法［10］从源节点的邻居中选择若干节点去目的社区查询信息并且返回信息，同时满足信息查询概率大于等于一定概率。

本文同时考虑节点和社区的社会属性，设计基于它们影响力的数据转发算法（data forwarding algorithm based on impact，DFAI）。在一些有较多节点出现的社区，源节点有更大的机会偶遇目的节点，如学校食堂、迎新晚会现场、学术交流会场等，定义这些社区的影响力为大；同时，经常出现在这些社区的节点，与其他节点相比有更大的概率遇到目的节点，相应定义这些节点的影响力为较大。因此，从社会网的观点来看，人们共享一些兴趣爱好而成为一个团体，通过DFAI算法尽量选择影响力大的节点来转发数据包，达到提高传递率和减少网络开销的目的。

1 网络模型

由闻名的小世界模型可知，人们通常因为兴趣爱好、职业及一些社会属性属于多个社区。若移动社交网络包含N1个“热点”地理区域社区，每个社区有一个固定的AP（access point）配置无线访问设备，N2个携带无线访问设备的人可以在网络中随意走动。将该网络模型化为一个图G＝（V，E），其中V为N1个AP和N2个人组成的N（N＝N1＋N2）顶点集合；E为顶点之间形成的边集合。定义ti，j（1≤i≤N，1≤j≤N1）为节点i位于社区j中的累积时间。

定义1 当且仅当ti，j≥λ（1≤i≤N，1≤j≤N1）时，节点i属于社区j，其中λ是阈值。

在上述定义的基础上，社区j的影响力Icj定义为该社区中节点的个数，则节点的影响力In i为其所在社区的影响力之和，即

其中，xi，j表示节点i是否属于社区j，如果节点i属于社区j，则xi，j＝1，否则xi，j＝0。由（1）式可知，若社区l、m、n的影响力分别为9、8、6，节点i属于社区l、m，节点k属于社区m、n，则节点i、j的影响力分别为17和14，节点i比k有更好的数据转发性能。

2 基于影响力的数据转发算法

作为AP，将统计每个进入本社区的节点的累积时间，然后根据定义1判断该节点是否属于本社区，从而计算出社区的影响力。同样当节点进入社区时，也会根据定义1判断自己是否属于该社区，如果属于该社区，则通过和AP联系获得该社区的影响力，再计算出自己的影响力。

在基于影响力的数据转发算法（DFAI）中，希望影响力越大的节点越多地参与数据转发。假设携带数据包p的节点i遇到节点j时，DFAI算法步骤如下：

（1）当节点j也携带数据包p时，转到步骤（3）。

（2）当节点j不携带数据包p时，若节点j和目的节点属于同一社区且Inj≥βIni，则拷贝数据包给节点j；若节点j和目的节点不属于同一社区且Inj≥Ini，也拷贝数据包给节点j。

（3）结束。

在步骤（2）中，β∈［0，1］为一个阈值；条件表达式Inj≥βIni表示目的社区的节点只要其影响力达到携带数据包节点影响力的β倍，就可以获得拷贝。

若节点i同时属于社区l和m，节点k同时属于社区m 和n，且Inl＝9，Inm＝8，Inn＝6，β＝0.8，则Ini＝17，Ink＝14。根据DFAI算法，如果节点k不属于目的节点社区，则根据Ink＜Ini可知节点i不会拷贝数据包给节点k；否则根据Ink≥Ini拷贝数据包给节点k。DFAI考虑了具有相同兴趣的节点有较大概率再次相遇，通过选择影响力较大的节点来进行数据转发，使转发策略达到最优。

3 性能评价

本文使用Infocom06的真实跟踪数据进行模拟实验，该数据是2006年西班牙巴塞罗那的Infocom会议上由78个学生通过携带Imote设备采集得到的，会场布置20个固定Imote设备作为AP，分布在不同区域形成社区。本文将DFAI算法与Epidemic和Label算法进行比较。

在Epidemic算法中，信息被相遇节点存储并被转发给所有相邻节点；在Label算法中，携带数据包的节点只是将数据包拷贝给目的社区节点，从而减少网络开销。用以下量度来衡量不同转发策略的性能：① 传递率，网络中被成功传递到目的节点的数据包占所有发送数据包的比率；② 延迟，数据包从源节点到达目的节点所经历的时间；③ 开销，采用一个数据包被成功传递时在网络中产生的拷贝数目。数据包存在时间（time－to－live）为24 h，源节点和目的节点从移动节点中随机选取，每个实验结果都是300次运行结果的平均值。

研究将λ从10 min变化到40 min对3种算法性能的影响，仿真结果如图1所示。

从图1a中可以看出，DFAI算法传递率接近Epidemic算法，高于Label算法；Epidemic取得最大传递率，是因为采用了洪泛策略；随着λ增大，DFAI算法和Epidemic算法的传递率几乎不变，而Label算法的传递率有所变小。从图1b中可以看出，DFAI算法的开销最小，最多比Epidemic和Label算法分别降低35.0%和27.4%。从图1c中可以看出，DFAI算法的延迟比Epi－demic和Label算法稍有提高，最多提高3.1%和2.5%。

图1 3种算法的网络性能随阈值λ的变化

将节点的发包时刻从上午8：00变化到下午14：00，仿真结果如图2所示。

由图2a可以看出，3种算法的传递率随着时间的变大而降低，在相同条件下DFAI算法的传递率都比Label算法高。由图2b可以看出，DFAI算法开销比Epidemic算法和Label算法都低，最多降低35.0%和26.3%，这是因为DFAI算法只有在遇到目的节点社区中的节点或者其他影响力达到一定要求的节点时，才会转发数据包给它们，从而减少了网络中拷贝数目。由图2c可以看出，DFAI算法的延迟比其他2种算法稍许提高。

图2 3种算法的网络性能随发包时刻的变化

本文提出的DFAI算法考虑了具有相同兴趣的节点有较大概率再次相遇，或经较少转发次数到达目的节点，通过选择影响力大的节点来使转发性能达到最优；与Epidemic和Label算法相比，DFAI算法依赖于社区和节点的影响力进行数据转发，能够提供更好的转发效果。

4 结束语

随着无线移动设备数量的高速增长以及功能的不断丰富，移动社交网络越来越广泛地被关注。

本文提出了基于影响力的数据转发算法DFAI，利用节点的影响力对数据进行转发，使信息在尽量小的网络开销下成功地交付给目的节点。仿真结果表明，相比于经典的Epidemic和Label算法，DFAI算法明显降低了网络开销，并且在传递率方面接近于Epidemic算法。

［1］Balasubramanian A，Levine B N，Venkataramani A.DTN routing as a resource allocation problem［C］／／Proceedings of SIGCOMM 2007，Kyoto，2007：373－384.

［2］柏亚平，王青山，孙雪莲.DTN网络中一种基于区域的缓存区管理策略［J］.合肥工业大学学报：自然科学版，2013，36（9）：1063－1067.

［3］Ioannidis S，Chaintreau A，Massoulie L.Optimal and scalable distribution of content updates over a mobile social network［C］／／Proceedings of INFOCOM 2009，IEEE，Rio de Janeiro，2009：1422－1430.

［4］Vahdat A，Becker D.Epidemic routing for partially－connected ad hoc networks［R］.San Diego：University of California，San Diego，2000.

［5］Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait：an efficient routing scheme for intermittently connected mobile networks［C］／／Proceedings of the 2005 ACM SIGCOMM Workshop.New York：ACM Press，2005：252－259.

［6］Spyropoulos T，Psounis K，Raghavendra C S.Spray and focus：efficient mobility－assisted routing for heterogeneous and correlated mobility［C］／／Proceedings of Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops.White Plains：IEEE Press，2007：79－85.

［7］Erramilli V，Crovella M，Chaintreau A，et al.Delegation forwarding［C］／／Proceedings of MobiHoc’08.New York：ACM Press，2008：251－260.

［8］Pan Hui，Crowcroft J.How Small labels create big improvements［C］／／Proceedings of Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops. White Plains：IEEE Press，2007：65－70.

［9］Pan Hui，Crowcroft J，Yoneki E.Bubble rap：social－based forwarding in delay－tolerant networks［J］.IEEE Transactions on Mobile Computing，2011，10（11）：1576－1589.

［10］Fan Jialu，Chen Jiming，Du Yuan，et al.Del Que：a socially－aware delegation query scheme in delay－tolerant networks［J］.IEEE Transactions on Vehicular Technology，2011，60（5）：2181－2193.

Data forwarding algorithm based on impact in mobile social networks

LIU Yan－ping， WANG Qing－shan， WANG Qi， FU Sha－sha， REN Li－li
（School of Mathematics，Hefei University of Technology，Hefei 230009，China）

Mobile social users can communicate by physical interact with each other via mobile device in mobile social networks.In view of the intermittent and uncertain network connectivity in the mobile social network，the data forwarding algorithm becomes important.From the social perspective of community and node，a data forwarding algorithm based on impact（DFAI）is proposed in this paper.In DFAI，the node with the packet only copies to the encounter node whose impact meets certain requirement.The simulation results show that the proposed algorithm can reduce network overhead obviously compared with Epidemic algorithm and Label algorithm，and its maximum delivery ratio is close to that obtained by Epidemic algorithm.

mobile social network；impact；forwarding；delay

TP301.6

A

1003－5060（2015）02－0195－04

10.3969／j.issn.1003－5060.2015.02.012

2014－01－15；

2014－04－15

安徽省自然科学基金资助项目（1208085MF89；1308085MF87）；教育部留学回国人员科研基金资助项目

（2013JYLH0280）和高等学校博士学科点专项科研基金资助项目（2013111120018）

刘艳萍（1985－），女，安徽阜阳人，合肥工业大学硕士生；

王青山（1987－），男，安徽合肥人，博士，合肥工业大学副教授，硕士生导师.

（责任编辑 胡亚敏）