移动社会网络接口及系统设计

汪 云, 陈家旭

(1. 西安邮电大学 教务处, 陕西 西安 710121; 2.北京航天控制仪器研究所, 北京100094)

移动社会网络接口及系统设计

汪 云1, 陈家旭2

(1. 西安邮电大学 教务处, 陕西 西安 710121; 2.北京航天控制仪器研究所, 北京100094)

针对移动社会网络中存在的运动模型与路由协议不能协同工作的问题,设计了一个较为完整的移动社会网络系统和基于社区与效用值的路由协议,结果表明,通过所设计的接口,原本不能与所选运动模型协同工作的路由协议可以正常地工作在系统中,并且所设计的路由协议性能优于现有的路由协议。

移动社会网络；社区；效用值

人类运动模型与社会感知的路由协议是移动社会网络研究领域的两个热点问题。人类运动模型如CMM[1],TLW[2],SIMPS[3],SLAW[4],SWIM[5-6],HCMM[7],HHW[8],SMOOTH[9]致力于用数学模型还原人类真实运动情况,而社会感知的路由协议如[10],SocialCast[11],SANE[12]目标则是在人类运动的环境下提供良好的消息传输。虽然二者在设计中都考虑了人类之间的社会关系,在实际模拟中常常出现运动模型与路由协议不能协同工作的情况。例如SocialCast是一个基于效用(utility)的协议,效用值与节点兴趣相关联。协议将节点兴趣直接固化在路由算法中,导致没有设置节点兴趣的运动模型无法在模拟中直接使用。也有一些工作如SANE[1]以破坏运动模型的独立性为代价,使得其可以与所提出的路由协议协同工作,这种做法不能体现出由原始运动模型所描述的网络环境。而国内研究人员完成的一些工作,并没有特别关注所采用的运动模型,而是直接使用了不能反映人类运动规律的随机路点运动模型[13]或直接采用人类实际运动轨迹[14]完成实验,回避了运动模型和路由协议的耦合问题。

针对这一现象,本文选择了一个合理的运动模型作为系统的运动环境,建立起运动模型与基于社区的路由协议的接口,在此基础上设计了基于效用值的路由协议,在运动模型与路由协议之间起到耦合作用。

1 运动模型的选择

系统对运动模型的需求是能够准确反映人类运动特征。表1中总结了现有运动模型需要的输入及它们重现的人类运动特征。

表1 运动模型输入及重现情况总结

从表1可以看到,SWIM重现了与实际人类运动相匹配的几个指标：①接触间隔时间；②接触时长；③接触数量；④社区(community)结构。其中,接触间隔时间是研究人类运动的最重要的参数之一。定义为同一对节点的两次相邻相遇之间的时间间隔。对于缺少固定链路,只能依赖通过节点运动造成的节点相遇机会进行数据传输的移动社会网络,接触间隔时间对其中的路由协议性能有显著的影响。接触时长和接触数量作为配合接触间隔时间的参量,通常被一起使用,来研究随运动而生成的节点社区的情况。例如,BubbleRap[15]中根据接触时长与接触数量的关系,将节点之间的关系分为4种：社区、熟悉的陌生人、陌生人、朋友。并以这4种关系为基础设计路由协议。然而在上述例举出的典型人类运动模型[1-9]中,只有SWIM同时重现了与实际人类运动相符的接触时长与接触数量的分布。配合接触间隔时间,SWIM在人类运动中与“接触”有关的方面得到了较完整的重现。

除了能够准确反映相遇量之外,在反映人类社会关系特别是社区结构方面,作为一个不需要任何输入,纯设计的(synthetic)运动模型,SWIM也有较突出的性能。SWIM可以通过修改参数(而不是外部输入),模拟出与指定的实际人类运动数据相一致的社区结构特征[5-6]。

2 接口的设计

运动模型的输出是节点的运动轨迹。而移动社会网络中社会感知的路由协议往往对网络环境做了一些假设(如节点兴趣,节点社区等),并且路由策略主要是基于这些假设而设计的。虽然移动社会网络运动模型也会对网络环境做假设(如SWIM中节点家的分布情况),然而当路由协议和运动模型对网络环境所做的假设不同时,就导致了二者不能协同工作。本文的接口,就是在运动模型基础上提取出路由协议所需要的假设,从而使二者能够协同工作的一系列机制。

文献[15]验证了k-clique社区检测算法[16]的准确性。k-clique算法适用于系统以全局的观点得知整个网络的社区结构情况,一般由k与Tth两个参数共同确定一个社区,其中Tth表示网络图中边的权重的阈值,k表示所探测的多边形社区的边数。由于无法得到整个网络的信息,实际移动社会网络中的节点并不能直接使用k-clique算法来进行社区检测。通过将k-clique算法分布式化,各节点能够在本地进行社区检测,从而基于社区的路由协议可以应用在模拟系统中并与运动模型达到良好的耦合。

按照时间顺序对系统设计的接口进行描述,可得到如图1所示的系统时间轴。

图1 系统时间轴

自S1起,所有节点按照SWIM模型运动。此时节点对网络情况一无所知,且社区结构也没有成型。不加载任何路由协议,让网络自主运行一段足够长的时间,直到S2,以等待SWIM生成相对稳定的社区结构。在从S1到S2这段时间内,除了每个节点记录下所有与自己相遇过的节点的id,接触次数和接触时长之外,不进行控制信息交换。

而从S2时刻起,直到P1,节点在遇到其他节点时,将此前C1时间内收集到的信息作为控制信息进行交换。在P1时间,各节点在本地运行分布式k-clique算法,于是在P1之后,节点具备了本地所知的社区结构,可以加载基于社区的路由协议。P1到P2为网络中源节点的集中发包时间,TTL为包的生存周期,S3为模拟结束的时间。通过这种方式观测到网络的性能参数。

在缺少接口设计的网络系统模拟中,假设S1到S3是系统的模拟时间,P1到P2是网络中源节点的开始发包时间和结束发包的时间,那么在P1时刻,只有运动模型直接提供了路由协议所需的社会量,或者对网络环境做了与路由协议相同的假设的情况下,二者才能够协同工作。通过对C1时间和C2时间机制的设计,以及在此机制之下P1时间的分布式社区检测算法,使得二者可以协同工作。所设计的接口偏重于社区结构,事实上,各社会量之间联系密切,在一定基础上可以互相转换。比如社区结构可以较方便地与节点兴趣相关联,从而生成偏重于节点兴趣的接口,以便在模拟中采用基于节点兴趣的路由协议。

案例分析：本案例是销售送赠品业务，且赠送的100个富光500mL太空杯是企业有偿购入的其他商品。洪福商贸在核算该笔业务时，对于销售的汇源1L100%苹果汁属于正常的销售业务，根据销售普通业务核算流程处理即可；对于随同发出的100个富光500mL太空杯因在采购时成本已计入“销售费用”，因此在核算时，不需要核算发出成本，但要将已计入“应交税费——应交增值税（进项税额）”的税金转出。因此，本案例的关键点是：①无偿赠送的富光500mL太空杯只需要录入出库单即可；②因富光500mL太空杯系免费赠送，购入时列入“应交税费——应交增值税（进项税额）”应要做进项转出处理。具体操作流程如下：

3 路由协议的设计

在基于效用的路由协议中,效用值衡量了一个节点被选为下一跳的权重。当两个节点相遇时,对于需要发送的消息,两节点将比较各自的对于该消息的效用值,选择效用值更高的一方携带消息。这里的效用值由节点的运动状态和节点所处社区状况共同决定。本协议设计节点n的效用值的具体表达式为

utility(n)=Pdis/LeastDistance(n,L) +

Pstop×pause_time(n)+Pcom×NiC(n)，

其中为节点id,utility(n)代表节点n的效用值,Pdis代表了节点n处于运动状态时的效用值总效用值中所占的权重,L及LeastDistance(n,L)的含义随协议的单播/多播模式而不同,当协议处于单播模式时,L为目的节点,LeastDistance(n,L)表示在之前运动阶段内节点n与L相遇的平均时间间隔；当协议处于多播模式时,L表示目的节点组,LeastDistance(n,L)表示在之前运动阶段内节点n与L内所有节点相遇的平均时间间隔。由于LeastDistance(n,L)越大,表明n和L之间社会关系越弱,而节点n的效用值应随其与目的节点之间社会关系的加强而增大(即更适合作为中继节点),因此Pdis与LeastDistance(n,L)之间以“/”连接。

Pstop表示了节点n处于停止状态时在总效用值中所占的比重。pause_time(n)代表节点n的停止时间长度。即当两个静止节点处于相遇状态时,协议倾向于把消息传给静止时间较长的节点。这是因为协议中消息是逐渐向目的地接近的,在无法确定下一步的方向时选择保守的继续等待策略,以期望选择到最合适的中继。

Pcom代表社区状况在总效用值中的权重。NiC(n)定义为,当节点n处于目的节点所在社区时,其值为1,否则为0。Pdis,Pstop和Pcom是比例常数,其中Pcom所占权重要远大于其他两项,因此在这3个权重中,协议最倾向的是将消息传递给目的节点所属社区的节点。一旦消息进入了目的节点所在社区,由于Pcom×NiC(n)所占比重大,保证了消息尽可能地在社区内部传递,以便快速到达社区的各个节点。

上述给出的是单副本的路由协议,即网络中允许存在的同一个消息及其副本的总数R=1。在移动社会网络环境中,更多的副本数能够以增加少量开销为代价使消息更快地到达目的节点。本协议可以非常方便地扩展为多副本协议。在保持参数R的定义的基础上,指定参数ε为对消息进行复制的阈值,当相遇的两节点的效用值之差大于ε时,对消息进行传递；小于ε时,对消息进行复制,使得两节点都携带此消息,以便更快地到达目的节点。

4 模拟及性能分析

在评估移动社会网络协议的性能时,最常用的量是分组投递率、延迟和开销。分别代表了发送消息的成功率,消息从源节点到目的节点需要的平均时间,和平均发送一个消息所需要消耗的控制信息的数量。模拟参数如表2所示。

表2 模拟参数

作为对比的SocialCast协议的参数则采用了与文献[11]同样的设置。P1、P2、S1、S2、S3为图2所示的5个时间点的取值。

运动模型的参数则按照SWIM的特点,为了构建中社区个数为1的网络环境,在100个节点中平均随机选择了20个,把这20个节点的家设置在彼此附近。整个网络区域分成30×30的单元格,单元格对节点的权重中,与节点家的距离相关部分的权重(即[6]中参数α的值)设为0.25,停止时间(秒)服从[10,1440]间斜率为1.45的截断幂律分布,运动时间固定为10 s。k-clique的参数设置为k=4,Tth=33 000 s。

图2～图6分别给出了系统采用本文所设计的路由协议与SocialCast协议的分组投递率、延迟和开销的模拟结果对比情况。

协议分组投递率与生存时间的关系,如图2所示。

图2 分组投递率与生存时间的关系

图2中,设计的协议的副本数取1,SocialCast的副本数取5的情况下,设计的协议已经达到比SocialCast更高的分组投递率。

协议延迟与生存时间的关系,如图3所示。

图3 延迟与生存时间的关系

协议开销与生存时间的关系,如图4所示。

图4 开销与生存时间的关系

从图3～图4中,可以看出两个协议有着相近的延迟和开销。因此总体来看,设计的协议整体性能更好。

值得注意的是,原本不能直接协同工作的SWIM和SocialCast(因为后者需要社区结构而前者并未直接提供)经过接口的耦合而应用在同一个网络系统中,体现出了接口设计的必要性。

图5～图7则描绘出了系统路由性能随副本数变化的情况。

图5 分组投递率与副本数的关系

在图5中,随着副本数的增加,SocialCast的分组投递率增长幅度比本文所设计的协议更大。

图6 延迟与副本数的关系

图6中,显示出了相似的情况,说明SocialCast更易从增加副本数中获得性能上的提升。

图7 开销与副本数的关系

从图7可以看出,随着副本数的增长,设计的协议将产生比SocialCast更多的开销的现象,也同样支持该结论。

从协议性能上看,与SocialCast相比,本协议具有更高的分组投递率与更低的延迟,虽然开销也更高,但整体性能仍优于SocialCast。此外,无论是对于SocialCast还是本文所设计的协议,增加副本数都会提高分组投递率并降低延迟,而代价则是增加系统的开销。总体上看,与SocialCast相比,本文所设计的协议对副本数的依赖性相对较小,这说明本协议的路由策略能够更为准确地将消息向其目的节点推进,另一方面,对于本文提出的协议,难以通过只靠增加消息的副本数来提升性能。

5 结语

引入移动社会网络中接口的概念,设计了一个较为完整的移动社会网络系统。选择了一个合理的运动模型作为系统的运动环境,建立起运动模型与基于社区的路由协议的接口,并在此基础上设计了基于效用值的路由协议,通过模拟与一个基于社区的协议SocialCast对比,证明所设计的网络系统路由性能可以达到超越现有工作的性能。结果表明通过接口的设计,原本不能与所选运动模型协同工作的路由协议可以正常地工作在系统中,并且所设计的路由协议性能优于现有的路由协议。

[1] Musolesi M, Mascolo C. Designing mobility models based on social network theory[C]//ACM SIGMOBILE Mobile Computing and Communication Review, 2007, 11(3): 59-70.

[2] Rhee I, Shin M, Lee K, Hong S, Kim S.J, and S. Chong. On the Levy-walk Nature of Human Mobility[J]. IEEE/ACM Transactions on Networking, 2011, 19(3): 630-643.

[3] Borrel V, Legendre F, MD de Amorim, Fdida S. SIMPS: Using Sociology for Personal Mobility[J]. IEEE/ACM Transactions on Networking, 2009, 17(3): 831-842.

[4] Lee K, Hong S, Kim S.J, Rhee I and Chong S. SLAW: A Mobility Model for Human Walks[C]//Proc. INFOCOM’09, 2009: 855-863.

[5] Mei A, Stefa J. Swim: a simple model to generate small mobile worlds[C]//Proc. INFOCOM’09, 2009: 2106-2113.

[6] Kosta S, Mei A, Stefa J. Small World in Motion (SWIM)：Modeling Communities in Ad-Hoc Mobile Networking[C]. Proc. SECON’10, 2010:1-9.

[7] Boldrini C, Passarella A. HCMM: Modelling spatial and temporal properties of human mobility driven by users’ social relationships[J]. Computer Communications, 2010, 33(9):1056-1074.

[8] Yang S, Yang Z, Zhang C and Spyrou E. Using social network theory for modeling human mobility[J]. IEEE network, 2010, 24(5): 6-13.

[9] Munjal A, Camp T and Navidi WC. SMOOTH: a simple way to model human walks[C]//ACM SIGMOBILE Mobile Computing and Communications Review, 2010, 14(4): 34-36.

[10]Zhang L, Zhou XW, Wang JP, et al. Routing Protocols for Delay and Disruption Tolerant Networks[J]. Journal of Software, 2010, 21(10):2554-2572.

[11]Costa P, Mascolo C, Musolesi M, and Picco G.P.. Socially-aware Routing for Publish-Subscribe in Delay-tolerant Mobile Ad Hoc Networks[J]. JSAC’08, 2008, 26(5):748-760.

[12] Mei A, Morabito G, Santi P, et al. Social-Aware Stateless Forwarding in Pocket Switched Networks[J]. Proc. INFOCOM’11, 2011(3):251-255.

[13]Zhu JQ, Liu M, Gong HG, et al.Event Delivery in Publish/Subscribe System for Delay Tolerant Sensor Networks[J]. Journal of Software, 2010, 21(8):1954-1967.

[14]Li S, Li QM, Zhang H, et al. Closely Social Circuit Based Routing in Social Delay Tolerant Networks[J]. Journal of Computer Research and Development, 2012(6):1196-1203.

[15]Hui P, Crowcroft J. Bubble Rap: Forwarding in small world dtns in ever decreasing circles[R]. Technical Report UCAM-CL-TR-684, University of Cambridge, May 2007.

[16] Palla G, Dernyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.

[责任编辑：汪湘]

Interface and system design for mobile social networks

WANG Yun1, CHEN Jiaxu2

(1. Xi’an University of Posts and Telecommunications dean’s office, Xi’an 710121, China;2. Beijing Institute of Aerospace Control Devices, Beijing 100094, China)

A comprehensive mobile social network system containing a community and utility based on routing protocol is proposed to tackle the problem in which some mobility models cannot work well with some routing protocols existing in mobile social networks. Simulation results show that with the help of the designed interface, the routing protocol which cannot couple with the chosen mobility model works well in the system, and that the designed routing protocol outperforms the existing one.

mobile social networks，community，utility

2015-06-06

汪云(1979-),女,工程师,从事计算机网络技术研究。E-mail:amywau@xupt.edu.cn 陈家旭(1983-),男,工程师,从事移动自组织网研究。E-mail:cjx_squall@163.com

10.13682/j.issn.2095-6533.2015.05.018

TP301

A

2095-6533(2015)05-0091-05