机会社交网络中基于时变兴趣社区的查询消息路由算法

doi:10.11959/j.issn.1000-436x.2019177

通信学报 ›› 2019, Vol. 40 ›› Issue (9): 86-94.doi: 10.11959/j.issn.1000-436x.2019177

机会社交网络中基于时变兴趣社区的查询消息路由算法

毕俊蕾¹,李致远^2,³

¹ 江苏大学信息化中心，江苏镇江212013
² 江苏大学计算机科学与通信工程学院，江苏镇江 212013
³ 江苏大学新一代信息技术产业研究院，江苏镇江 212013

修回日期:2019-06-28 出版日期:2019-09-25 发布日期:2019-09-28
作者简介:毕俊蕾（1981- ），女，河南南阳人，博士，江苏大学讲师，主要研究方向为移动社交网络、机会网络路由算法。|李致远（1981- ），男，河南开封人，博士，江苏大学副教授、硕士生导师，主要研究方向为移动社交网络、物联网和软件定义网络及其安全机制。
基金资助:
江苏省自然科学基金资助项目(BK20170558);中国博士后科学基金资助项目(2015M570469)

Time-variant interest community based query message routing algorithm in opportunity social network

Junlei BI¹,Zhiyuan LI^2,³

¹ Information Center,Jiangsu University,Zhenjiang 212013,China
² School of Computer Science and Telecommunication Engineering,Jiangsu University,Zhenjiang 212013,China
³ New-Generation Information Technology Industry Institute,Jiangsu University,Zhenjiang 212013,China

Revised:2019-06-28 Online:2019-09-25 Published:2019-09-28
Supported by:
The Natural Science Foundation of Jiangsu Province(BK20170558);China Postdoctoral Science Foundation of China(2015M570469)

摘要/Abstract

摘要：

针对机会社交网络环境下资源查询成功率低的问题，提出一种基于时变兴趣社区的查询消息路由算法。首先，分析了2个重要的移动社交网络数据集，发现了用户节点行为在时间和空间上的关联性和规律性；然后，基于用户行为在时空上的关联和规律性，构建了时变兴趣社区；最后，在时变兴趣社区的基础上，设计新的查询消息路由算法。理论分析结果表明，所提算法时间复杂度是O(nlog n)；仿真实验结果表明，所提算法在查询成功率、平均查询时延、查询跳数及系统开销方面均优于与同类型算法。

关键词: 机会社交网络, 查询路由, 移动社交数据分析, 时变兴趣社区

Abstract:

To solve the problem that the successful rate of resource query is low in opportunity social network,a query message routing algorithm based on time-variant interest community was proposed.Two well-known mobile social datasets were firstly analyzed,and then the temporal and spatial correlations of users were found.The time-variant interest communities based on temporal and spatial correlations of users were constructed.Next,a dynamic query routing on the constructed time-variant interest communities was proposed.Theoretical analysis shows that the proposed routing can run in O (nlog n) time.The comparisons between the proposed routing and state-of-the-art message delivery algorithms show that the proposed routing can keep high query success rate,reduce the average query latency and the hop count of a query and maintain low system overhead.

Key words: opportunistic social network, query routing, mobile social data analysis, time-variant interest community

中图分类号:

TP393

毕俊蕾,李致远. 机会社交网络中基于时变兴趣社区的查询消息路由算法[J]. 通信学报, 2019, 40(9): 86-94.

Junlei BI,Zhiyuan LI. Time-variant interest community based query message routing algorithm in opportunity social network[J]. Journal on Communications, 2019, 40(9): 86-94.

图/表 14

图1

图2

图3

图4

图5

图6

图7

图8

表1

图9

图10

图11

图12

图13

参考文献 17

[1]	PIETIL?NEN A K , DIOT C . Dissemination in opportunistic social networks:the role of temporal communities[C]// The 13th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 2012: 165-174.
[2]	李超, 殷丽华, 耿魁 ,等. 面向移动社交网络内容分享的位置隐私保护方法[J]. 通信学报, 2016,37(11): 31-41.
	LI C , YIN L H , GENG K ,et al. Location privacy preservation Approach towards to content sharing on mobile online social network:survey and perspectives[J]. Journal on Communications, 2016,37(11): 31-41.
[3]	VAHDAT A , BECKER D . Epidemic routing for partially connected ad Hoc networks:technical report：CS-200006[R]. North Carolina:Duke University, 2000.
[4]	SPYROPOULOS T , PSOUNIS K , RAGHAVENDRA C S . Spray and wait:an efficient routing scheme for intermittently connected mobile networks[C]// The 21th ACM SIGCOMM Workshop on Delay-Tolerant Networking. ACM, 2005: 252-259.
[5]	LINDGREN A , DORIA A , DAVIES E ,et al. Probabilistic routing protocol for intermittently connected networks:RFC 6693[Z]. IETF Datatracker, 2012.
[6]	DALY E M , HAAHR M . Social network analysis for routing in disconnected delay-tolerant manets[C]// The 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM, 2007: 32-40.
[7]	LIU Q , HU C , LI Y , ZHAO W ,et al. An interest community routing scheme for opportunistic networks[C]// The 54th IEEE Globecom Workshops. IEEE, 2013: 4366-4371.
[8]	ZHENG Z J , WANG T Y , SONG L Y ,et al. Social-aware multi-file dissemination in device-to-device overlay networks[C]// The 33rd IEEE International Conference on INFOCOM. IEEE, 2014: 219-220.
[9]	LI Y , LI Q , JIN D P ,et al. Contact duration aware evaluation for content dissemination delay in mobile social network[J]. Wireless Communications ＆ Mobile Computing, 2015,15(3): 527-537.
[10]	MANSILLA A T , ESTEVA J L . Question waves:a multicast query routing algorithm for social search[J]. Information Sciences, 2013,253(1): 1-25.
[11]	YOU L , LI J B , WEI C J . MPAR:a movement pattern-aware optimal routing for social delay tolerant networks[J]. Ad Hoc Networks, 2015,24(3): 228-249.
[12]	PAGANI E , VALERIO L , ROSSI G P . Weak social ties improve content delivery in behavior-aware opportunistic networks[J]. Ad Hoc Networks, 2015,25(7): 314-329.
[13]	LI Y , WU D , XUA J ,et al. Spatial-aware interest group queries in location-based social networks[J]. Data ＆ Knowledge Engineering, 2014,92(1): 20-38.
[14]	FIRDOSE S , LOPES L , MOREIRA W ,et al. The copelabs/usense dataset:Crawdad[J].(2017-01-27)[2018-12-16].
[15]	CIOBANU R I , DOBRE C . The upb/hyccups dataset:Crawdad[J].(2016-10-17)[2018-12-16].
[16]	徐健锐, 詹永照 . 基于 Spark 的改进 K-means 快速聚类算法[J]. .江苏大学学报 (自然科学版) , 2018,39(3): 316-323.
	U J R , ZHAN Y Z . Improved K-means fast clustering algorithm based on Spark[J]. Journal of Jiangsu University (Natural Science Ditions), 2018,39(3): 316-323.
[17]	PEDREGOSA F , VAROQUAUX G , GRAMFORT A ,et al. Scikit-learn:machine learning in Python[J]. Journal of machine learning research, 2011,32(1): 2825-2830.

参数	描述	默认值
world size	仿真实验场景面积	100 m × _{200 m}
EndTime/天	仿真时间	7
NrofHosts	用户节点个数	200
NrofHostGroups	分组数	4
Interface.type	通信接口类型	SimpleBroadcast
transmit speed/(Mbit·s^-1)	传输带宽	2
transmit range/m	传输距离	10～20
MovementModel	组内节点移动模型	ShortestPathMap
		BasedMovement
mobility speed/(m·s^-1)	节点的移动速度	0.5～1.5
Message.Size/KB	消息的大小	500～1024
Message.Interval/s	消息产生的间隔	1～2
Message.TTL/min	消息的生存周期	300
L	消息副本数	6

机会社交网络中基于时变兴趣社区的查询消息路由算法

Time-variant interest community based query message routing algorithm in opportunity social network

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 17

相关文章 15

Metrics

推荐阅读 0

[1]	李竟博, 马礼, 李阳, 傅颖勋, 马东超. 感传算协同工业互联网优化设计[J]. 通信学报, 2023, 44(6): 12-22.
[2]	赵仕祺, 黄小红, 钟志港. 基于信誉的域间路由选择机制的研究与实现[J]. 通信学报, 2023, 44(6): 47-56.
[3]	陈真, 陈文辉, 刘啸威, 尤殿龙, 刘林林, 申利民. 功能互补关系增强的云API推荐方法[J]. 通信学报, 2023, 44(6): 125-137.
[4]	魏德宾, 潘成胜, 杨力, 颜佐任. 基于网络流量水平等级预测的自适应随机早期检测算法[J]. 通信学报, 2023, 44(6): 154-166.
[5]	李元诚, 秦永泰. 基于深度强化学习的软件定义安全中台QoS实时优化算法[J]. 通信学报, 2023, 44(5): 181-192.
[6]	夏莹杰, 朱思雨, 刘雪娇. 区块链架构下具有条件隐私的车辆编队跨信任域高效群组认证研究[J]. 通信学报, 2023, 44(4): 111-123.
[7]	谢人超, 文雯, 唐琴琴, 刘云龙, 谢高畅, 黄韬. 轨道交通移动边缘计算网络安全综述[J]. 通信学报, 2023, 44(4): 201-215.
[8]	罗智勇, 张玉, 王青, 宋伟伟. 基于贝叶斯攻击图的SDN入侵意图识别算法的研究[J]. 通信学报, 2023, 44(4): 216-225.
[9]	王一丰, 郭渊博, 陈庆礼, 方晨, 林韧昊, 周永良, 马佳利. 基于对比增量学习的细粒度恶意流量分类方法[J]. 通信学报, 2023, 44(3): 1-11.
[10]	张进, 葛强, 徐伟海, 江逸茗, 马海龙, 于洪涛. 拟态路由器BGP代理的设计实现与形式化验证[J]. 通信学报, 2023, 44(3): 33-44.
[11]	经普杰, 王良民, 董学文, 张玉书, 王骞, Muhammad Sohail. 分层跨链结构：一种面向区块链系统监管的可行架构[J]. 通信学报, 2023, 44(3): 93-104.
[12]	舒坚, 史佳伟, 刘琳岚, Manar Al-Kali. 基于时空卷积的机会网络拓扑预测[J]. 通信学报, 2023, 44(3): 145-156.
[13]	王东滨, 吴东哲, 智慧, 郭昆, 张勖, 时金桥, 张宇, 陆月明. 软件定义网络抗拒绝服务攻击的流表溢出防护[J]. 通信学报, 2023, 44(2): 1-11.
[14]	康海燕, 龙墨澜. 基于吸收马尔可夫链攻击图的网络攻击分析方法研究[J]. 通信学报, 2023, 44(2): 122-135.
[15]	张云涛, 方滨兴, 杜春来, 王忠儒, 崔志坚, 宋首友. 基于异构观测链的容器逃逸检测方法[J]. 通信学报, 2023, 44(1): 49-63.