PQBCF:一种基于中间中心度的机会网络P2P查询算法

doi:10.3969/j.issn.0372-2112.2013.09.023

电子学报 ›› 2013, Vol. 41 ›› Issue (9): 1815-1820.DOI: 10.3969/j.issn.0372-2112.2013.09.023

PQBCF:一种基于中间中心度的机会网络P2P查询算法

牛建伟¹, 戴彬¹, 孙利民², 林佳骝³, 熊永平⁴

1. 北京航空航天大学软件开发环境国家重点实验室, 北京 100191;
2. 中国科学院软件研究所, 北京 100190;
3. 卡内基梅隆大学计算机学院, 宾夕法尼亚州匹兹堡 15213;
4. 北京邮电大学网络与交换技术国家重点实验室, 北京 100876

收稿日期:2012-07-23 修回日期:2013-04-02 出版日期:2013-09-25
- 作者简介:
- 牛建伟 男,1969年7月出生于河南.博士,现为北京航空航天大学计算机学院教授,CCF高级会员,主要研究方向为嵌入式与移动计算. E-mail:niujianwei@buaa.edu.cn;戴彬 男,1987年3月出生于天津.2013年毕业于北京航空航天大学计算机学院.现为北京航空航天大学教师,主要研究方向为机会网络和社会网络计算. E-mail:daibin_buaa@hotmail.com;孙利民 男,1966年出生于河南,博士,中国科学院软件所研究员,博士生导师,CCF高级会员,主要研究领域为无线传感器网络,无线接入网和多媒体技术;林佳骝 女,1985年出生于江苏,美国卡内基梅隆大学计算机学院博士研究生,主要研究领域为移动和普适计算;熊永平 男,1982年出生于江西,博士,CCF会员,主要研究领域为移动感知网络,机会组网和无线传感网.
- 基金资助:
- 软件开发环境国家重点实验室基金 (No.SKLSDE-2012ZX-17); 国家自然科学基金 (No.61170296,No.61190120); 新世纪优秀人才支持计划 (No.NECT-09-0028)

PQBCF:A P2P Query Algorithm Based on Betweenness Centrality Forwarding in Opportunistic Networks

NIU Jian-wei¹, DAI Bin¹, SUN Li-min², LIN Jia-liu³, XIONG Yong-ping⁴

1. State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China;
2. Institute of Software, Chinese Academy of Sciences, Beijing 100190, China;
3. School of Computer Science, Carnegie Mellon University, Pittsburgh, PA15213, USA;
4. State Key Lab of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2012-07-23 Revised:2013-04-02 Online:2013-09-25 Published:2013-09-25

摘要/Abstract

摘要： 社会机会网络由人携带的带有短距离通信接口的移动设备利用人的移动形成,其数据采用"存储-携带-转发"的模式进行传输,本文针对这类网络,提出了一种基于中间中心度的P2P查询算法(P2P Query based on Betweenness Centrality Forwarding,PQBCF).节点的中间中心度描述了节点在信息传输转发过程中的参与度和重要度,PQBCF算法通过选择具有较大中间中心度的节点来实现信息的高效转发.仿真实验表明,与目前该研究领域的SF(Spray and Focus)等主流算法相比,PQBCF算法能够有效提高查询成功率,并降低查询延时.

关键词: 机会网络, P2P查询, 中间中心度, 社会网络, 移动设备

Abstract: With the proliferation of high-end mobile devices that feature wireless interfaces,many practical applications are enabled in opportunistic networks which comprise mobile devices.Contrary to the traditional networks,opportunistic networks utilize the mobility of nodes to relay messages based on the store-carry-forward paradigm.We propose an efficient P2P query algorithm based on betweenness centrality forwarding (PQBCF) for opportunistic networking,which adopts the metric of betweenness centrality from social network analysis to estimate the active degree of nodes in the networks.PQBCF leverages nodes with greater betweenness centrality as relays to increase query success rate and reduce query latency.Simulation results demonstrate that PQBCF outperforms most state-of-the-art algorithms and achieves approximate efficiency as epidemic with much less resource consumption.

Key words: opportunistic networks, P2P query, betweenness centrality, social networks, mobile devices

中图分类号:

TP393

牛建伟, 戴彬, 孙利民, 林佳骝, 熊永平. PQBCF:一种基于中间中心度的机会网络P2P查询算法[J]. 电子学报, 2013, 41(9): 1815-1820.

NIU Jian-wei, DAI Bin, SUN Li-min, LIN Jia-liu, XIONG Yong-ping. PQBCF:A P2P Query Algorithm Based on Betweenness Centrality Forwarding in Opportunistic Networks[J]. Acta Electronica Sinica, 2013, 41(9): 1815-1820.

参考文献

[1] 熊永平,孙利民,牛建伟,等.机会网络[J].软件学报,2009,20(1):124-137. Xiong Yong-ping,Sun Li-min,Niu Jian-wei,et al.Opportunistic networks[J].Journal of Software,2009,20(1):124-137.(in Chinese)
[2] K Fall.A delay-tolerant network architecture for challenged Internets [A].Proceedings of 2003 Conference on Application,Technologies,Architectures,and Protocols for Computer Communications [C].New York:ACM,2003.27-34.
[3] P Juang,H Oki,Y Wang,et al.Energy-efficient computing for wildlife tracking:Design tradeoffs and early experiences with ZebraNet [A].Proceedings of the 10th ASPLOS [C].New York:ACM,2002.96-107.
[4] B Hull,V Bychkovsky,Y Zhang,et al.CarTel:A distributed mobile sensor computing system [A].Proceedings of the 4th Int’l Conf on Embedded Networked Sensor Systems [C].New York:ACM,2006.125-138.
[5] H Pan,A Chaintreau,J Scott,et al.Pocket switched networks and human mobility in conference environments [A].Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking [C].New York:ACM,2005.244-251.
[6] A Vahdat,D Becker.Epidemic Routing for Partially-Connected Ad Hoc Networks,CS-2000-06 [R].Durham:Department of Computer Science,Duke University,2000.
[7] T Spyropoulos,K Psounis,C S Raghavendra.Spray and wait:An efficient routing scheme for intermittently connected mobile networks [A].Proceedings of ACM SIGCOMM workshop on Delay Tolerant Networking(WDTN) [C].New York:ACM,2005.252-259.
[8] T Spyropoulos,K Psounis,C S Raghavendra.Spray and focus:Efficient mobility-assisted routing for heterogeneous and correlated mobility [A].Proceedings of the IEEE PerCom Workshop on Intermittently Connected Mobile Ad Hoc Networks [C].New Jersey:IEEE,2007.79-85.
[9] 霍广城,王晓东.移动传感网中一种基于RSSI的机会主义路由设计[J].电子学报,2009,37(3):608-613. Huo Guang-cheng,Wang Xiao-dong.An opportunistic routing for mobile wireless sensor networks based on RSSI[J].Acta Electronica Sinica,2009,37(3):608-613.(in Chinese)
[10] A Lindgren,A Doria,O Schelén.Probabilistic routing in intermittently connected networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):19-20.
[11] B Xu,A Ouksel,O Wolfson.Opportunistic resource exchange in inter-vehicle ad-hoc networks [A].Proceedings of Mobile Data Management IEEE International Conference [C].New Jersey:IEEE,2004.4-12.
[12] 卢翼,肖嵩,吴成柯.基于机会式网络编码的低时延广播传输算法[J].电子学报,2011,39(5):1214-1219. Lu Yi,Xiao Song,Wu Cheng-ke.Opportunistic network coding based delay sensitive broadcast transmission algorithm[J].Acta Electronica Sinica,2011,39(5):1214-1219.(in Chinese)
[13] R Baldoni,R Beraldi,M Migliavacca,et al.Content-based routing in highly dynamic mobile ad hoc networks[J].International Journal of Pervasive Computing and Communications,2005,1(4):277-288.
[14] 彭喜元,潘大为,彭宇.无线传感器网络多时间尺度链路估计算法研究[J].电子学报,2011,39(3A):80-85. Peng Xi-yuan,Pan Da-wei,Peng Yu.On multiple time scales link estimation in wireless sensor network[J].Acta Electronica Sinica,2011,39(3A):80-85.(in Chinese)
[15] H Pan,J Leguay,J Crowcroft,et al.Osmosis in pocket switched networks [A].Proceedings of the First International Conference on Communications and Networking in China (CHINACOM 2006) [C].New Jersey:IEEE,2006.1-6.
[16] 徐佳,孙力娟,王汝传,等.机会网络中基于种子喷雾的自适应路由协议[J].电子学报,2010,38(10):2315-2321. Xu Jia,Sun Li-juan,Wang Ru-chuan,et al.Adaptive seed spray routing for opportunistic networks[J].Acta Electronica Sinica,2010,38(10):2315-2321.(in Chinese)
[17] L C Freeman.Centrality in social networks:Conceptual clarification[J].Social Networks,1978,1(3):215-239.
[18] L A Adamic,A Eytan.Friends and neighbors on the web[J].Social Networks,2003,25(3):211-230.
[19] A Ker nen.Opportunistic Network Environment Simulator.Helsinki:Department of Communications and Networking,Helsinki University of Technology,May 2008.

PQBCF:一种基于中间中心度的机会网络P2P查询算法

PQBCF:A P2P Query Algorithm Based on Betweenness Centrality Forwarding in Opportunistic Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	崔苑茹, 李鹏, 刘宏, 王小明, 吴晓军. 基于校园机会网络的协作小组缓存调度策略[J]. 电子学报, 2021, 49(12): 2399-2406.
[2]	高玉君, 梁刚, 蒋方婷, 许春, 杨进, 陈俊任, 王浩. 社会网络谣言检测综述[J]. 电子学报, 2020, 48(7): 1421-1435.
[3]	杨洁, 朱咸军, 周献中, 柳毅. 基于混杂社会网络的个性化Web服务推荐方法[J]. 电子学报, 2020, 48(2): 341-349.
[4]	马慧芳, 刘文, 李志欣, 蔺想红. 融合耦合距离区分度和强类别特征的短文本相似度计算方法[J]. 电子学报, 2019, 47(6): 1331-1336.
[5]	马学彬, 郑田玉, 李明珠. 机会网络中自私行为影响的分析与调节[J]. 电子学报, 2019, 47(4): 837-847.
[6]	汪林玉, 谷科, 余飞, 尹波, 廖年冬. 基于个人意愿的社会网络团体结构与信息检测方案[J]. 电子学报, 2019, 47(4): 886-895.
[7]	朱恩强, 吴艳蕾, 许宇光, 牛云云. 基于树核度的社交网络影响最大化问题[J]. 电子学报, 2019, 47(1): 161-168.
[8]	李鹏, 王小明, 张立臣, 卢俊岭, 朱腾蛟, 张丹. 机会网络视频数据的分块渐进传输新方法[J]. 电子学报, 2018, 46(9): 2165-2172.
[9]	舒坚, 张学佩, 刘琳岚, 杨志勇. 基于深度卷积神经网络的多节点间链路预测方法[J]. 电子学报, 2018, 46(12): 2970-2977.
[10]	马学彬, 王应彪, 高瑞超, 张晓娟. 具有传输成功率保证的概率路由算法的TTL预测模型[J]. 电子学报, 2018, 46(11): 2679-2687.
[11]	俞春花, 刘学军, 李斌, 章玮. 基于上下文相似度和社会网络的移动服务推荐方法[J]. 电子学报, 2017, 45(6): 1530-1536.
[12]	龚卫华, 兰雪锋, 裴小兵, 杨良怀. 基于k-度匿名的社会网络隐私保护方法[J]. 电子学报, 2016, 44(6): 1437-1444.
[13]	刘春蕊, 张书奎, 贾俊铖, 林政宽. 机会网络中基于摆渡节点与簇节点相互协作的路由机制[J]. 电子学报, 2016, 44(11): 2607-2617.
[14]	王萌萌, 左万利, 王英. 基于加权非负矩阵分解的链接预测算法[J]. 电子学报, 2016, 44(10): 2391-2397.
[15]	马学彬, 白婧, 郑田玉. 机会网络中基于有权社团结构图的路由协议研究[J]. 电子学报, 2016, 44(10): 2449-2458.