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

doi:10.3969/j.issn.0372-2112.2013.09.023

PDF(1129 KB)

ACTA ELECTRONICA SINICA ›› 2013, Vol. 41 ›› Issue (9) : 1815-1820. DOI: 10.3969/j.issn.0372-2112.2013.09.023

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⁴

Author information +

History +

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

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

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. https://doi.org/10.3969/j.issn.0372-2112.2013.09.023

References

[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.

Funding

Fund for State Key Laboratory of Software Development Environment (No.SKLSDE-2012ZX-17); National Natural Science Foundation of China (No.61170296, No.61190120); Program for New Century Excellent Talents in University (No.NECT-09-0028)