基于社会特征周期演化的机会移动网络路由转发策略

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

Abstract

Abstract:

To avoid monster community problem which suffered by distributed k-clique community detection, τ-window community detection was proposed. In addition, τ-window centrality estimation was put forward. By investigating the periodic evolution of τ-window community and τ-window centrality, two new metrics, TTL(time to live) community and TTL centrality, were proposed to improve the prediction of the node's encounter during the message's lifetime. Moreover, a social-aware routing algorithm, PerEvo, was then designed based on them. Extensive trace-driven simulation results show that PerEvo achieves higher message delivery ratio than the existing social-based forwarding schemes, while keep-ing similar routing overhead.

Key words: opportunistic mobile networks, community, centrality, periodic evolution, message forwarding

Yong-feng HUANG,Yong-qiang DONG,San-feng ZHANG,Guo-xin WU. Message forwarding based on periodically evolving social characteristics in opportunistic mobile networks[J]. Journal on Communications, 2015, 36(3): 21-32.

Figures/Tables 17

References 24

[1]	HUI P , CHAINTREAU A , SCOTT J , et al. Pocket switched networks and human mobility in conference environments[A]. Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking[C]. ACM: Philadelphia, Pennsylvania, USA, 2005.
[2]	MCNAMARA L , MASCOLO C , CAPRA L . Media sharing based on colocation prediction in urban transport[A]. Proceedings of the 14th ACM International Conference on Mobile Computing and Networking[C]. ACM: San Francisco, California, USA, 2008.58-69.
[3]	PELUSI L , PASSARELLA A , CONTI M . Opportunistic networking:data forwarding in disconnected mobile ad hoc networks[J]. IEEE Communications Magazine, 2006,44(11):134-141.
[4]	FALL K . delay-tolerant network architecture for challenged internets[A]. Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications[C]. ACM: Karlsruhe, Germany, 2003.
[5]	LINDGREN A , DORIA A , SCHELEN O . Probabilistic routing in intermittently connected networks[J]. SIGMOBILE Mob Comput Commun Rev, 2003,7(3):19-20.
[6]	BURGESS J , GALLAGHER B , JENSEN D , et al. MaxProp:routing for vehicle-based disruption-tolerant networks[A]. Proceedings of INFOCOM[C]. Barcelona, Spain, 2006.
[7]	HUI P , CROWCROFT J , YONEKI E , BUBBLE Rap: social-based forwarding in delay-tolerant networks[J]. IEEE Transactions on Mobile Computing, 2011,10(11):1576-1589.
[8]	DALY E M , HAAHR M , et al. Social network analysis for routing in disconnected delay-tolerant MANET[A]. Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing[C]. ACM: Montreal, Quebec, Canada, 2007.
[9]	NEWMAN M E , GIRVAN M . Finding and evaluating community structure in networks[J]. Physical Review E, 2004,69(2):026113.
[10]	FREEMAN L C . Centrality in social networks conceptual clarification[J]. Social Networks, 1979,1(3):215-239.
[11]	HUI P , CROWCROFT J . How small labels create big improvements[A]. Proceedings of IEEE PerCom Workshops[C]. New York, USA, 2007.
[12]	SONG C M , QU Z , BLUMM N , et al. Limits of predictability in human mobility[J]. Science, 2010,327(5968):1018-1021.
[13]	EAGLE N , PENTLAND A . Reality mining: sensing complex social systems[J]. Personal Ubiquitous Comput, 2006,10(4):255-268.
[14]	MOREIRA W , MENDES P , SARGENTO S . Opportunistic routing based on daily routines[A]. Proceedings of IEEE WoWMoM[C]. San Francisco, California, USA, 2012.
[15]	FREEMAN L C . A set of measures of centrality based on betweenness[A]. Sociometry[C]. 1977.35-41.
[16]	MARSDEN P V . Egocentric and sociocentric measures of network centrality[J]. Social Networks, 2002,24(4):407-422.
[17]	HUI P , YONEKI E , CHAN S Y , et al. Distributed community detection in delay tolerant networks[A]. Proceedings of 2nd ACM/IEEE International Workshop on Mobility in the Evolving Internet Architecture[C]. Kyoto, Japan, 2007.
[18]	PALLA G , DERENYI I , FARKAS I , et al. Uncovering the overlapping community structure of complex networks in nature and society[A]. Proceeding of The 2nd ACM/IEEE Internetal Workshop on Mobility in the Evowing Internet Architectue[C]. Kyoto, Japan, 2007.
[19]	ORLINSKI M , FILER N . Quality distributed community formation for data delivery in pocket switched networks[A]. Proceedings of the Fourth Annual Workshop on Simplifying Complex Networks for Practitioners[C]. Lyon, France, 2012.
[20]	ORLINSKI M , FILER N . Distributed expectation-based spatio-temporal cluster detection for pocket switched networks[A]. Proceedings of Wireless Days IFIP IEEE[C]. 2012.
[21]	GAO W , LI Q , ZHAO B , et al. Social-aware multicast in disruption-tolerant networks[J]. IEEE/ACM Transactions on Networking, 2012,20(5):1553-1566.
[22]	GAO W , CAO G T L P , et al. On exploiting transient social contact patterns for data forwarding in delay-tolerant networks[J]. IEEE Transactions on Mobile Computing, 2013,12(1):151-165.
[23]	KIM H , ANDERSON R . Temporal node centrality in complex networks[J]. Physical Review E, 2012,85(2):026107.
[24]	KERANEN A , OTT J , KARKKAINEN T . The ONE simulator for DTN protocol evaluation[A]. Proceedings of the 2nd International Conference on Simulation Tools and Techniques[C]. Rome, Italy, 2009.

Metrics

Recommended 0

No Suggested Reading articles found!

函数	含义
Tcom	针对消息m的TTL社区
C_T	节点T时刻的τ-window社区
getTtl(m)	消息m的生存时间
λ	TTL社区准入参数
K	消息m生存期跨越的时间窗数
L	预设周期数
CC_thresh	消息生存期TTL社区判定阈值
τ	时间窗长度
ArrayC	图9的τ-window社区数组
inCount(v_j,ArrayC)	v_j在ArrayC中出现的次数

函数	含义
buffer(v₀)	v₀缓存区中的消息集合
dst(m)	消息m的目的节点
Tcom(v₀, m)	v₀针对m的TTL社区
LTcen(v₀,m)	v₀针对m的社区TTL中心性
GTcen(v₀,m)	v₀针对m的全局TTL中心性

参数	取值
(PerEvo)时间窗上社区保存的周期数L	5
(PerEvo)时间窗长度τ	3h
(PerEvo Bubble-E)社区老化指数α	0.1
(PerEvo Bubble Bubble-E)社区阈值F_thresh	300 s
(PerEvo)TTL社区准入参数λ	0.5
(DEBTT DEBTT)时间窗长度	1h
(DEBTE DEBTT)基线计算时间窗数w	6
(PerEvo Bubble Bubble-E)k团k值	5

Message forwarding based on periodically evolving social characteristics in opportunistic mobile networks

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 17

References 24

Related Articles 15

Metrics

Recommended 0

[1]	Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk [J]. Journal on Communications, 2023, 44(6): 198-210.
[2]	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.
[3]	WANG Li’na,GUO Xiaodong,WANG Run. Automated crowdturfing attack in Chinese user reviews [J]. Journal on Communications, 2019, 40(6): 1-13.
[4]	Hao LONG, Shukui ZHANG, Yang ZHANG, Li ZHANG. Task distribution algorithm based on community in mobile crowd sensing [J]. Journal on Communications, 2019, 40(10): 42-54.
[5]	Yancui SHI,Yuan WANG,Qing ZHAO,Xiankun ZHANG. Research status of community detection based on local expansion [J]. Journal on Communications, 2019, 40(1): 149-162.
[6]	Qiang LIU,Yan JIA,Binxing FANG,Bin ZHOU,Yue HU,Jiuming HUANG. Research on the scalability of parallel community detection algorithms [J]. Journal on Communications, 2018, 39(4): 13-20.
[7]	Yue-ping CAI,Jun LIU,Xin-wei FAN. Node centrality metric based caching mechanism in content-centric network [J]. Journal on Communications, 2017, 38(6): 10-18.
[8]	Ying PENG,Nao WANG,Gao-cai WANG. Optimal energy efficiency routing strategy based on community in mobile social network [J]. Journal on Communications, 2017, 38(5): 128-144.
[9]	Jing CHEN,Yun WAN. Research on label propagation algorithm based on modularity maximization in the social network [J]. Journal on Communications, 2017, 38(2): 25-33.
[10]	Kun DENG,Wen-ping LI,Fa-hong YU,Jian-pei ZHANG. Overlapping community detection in complex networks based on multi kernel label propagation [J]. Journal on Communications, 2017, 38(2): 53-66.
[11]	Zhuang-liang GAO,Yan-fei LYU,Hong ZHANG. Key nodes discovery in network graph based on Graphlab [J]. Journal on Communications, 2016, 37(3): 182-189.
[12]	Zhen-chao CHANG,Hong-chang CHEN,Rui-yang HUANG,Hong-tao YU,Yang LIU. Semi-supervised dynamic community detection based on non-negative matrix factorization [J]. Journal on Communications, 2016, 37(2): 132-143.
[13]	Jun CAI,Shun-zheng YU,Wai-xi LIU. Caching strategy based on node’s importance to community in information-centric networks [J]. Journal on Communications, 2015, 36(6): 173-182.
[14]	AOJiu-xin C,HENGao-jun C,ANGJing Y,HUZi-qing Z,IUBo L. Social-based routing in pocket switched networks [J]. Journal on Communications, 2015, 36(5): 13-22.
[15]	Kun GUO,Wen-zhong GUO,Qi-rong QIU,Qi-shan ZHANG. Community detection algorithm based on local affinity propagation and user profile [J]. Journal on Communications, 2015, 36(2): 68-79.