›› 2013,Vol. 28 ›› Issue (3): 574-582.doi: 10.1007/s11390-013-1357-x

• Special Section on Selected Paper from NPC 2011 • 上一篇    

陌生人对机会路由性能的影响

Pei-Yan Yuan (袁培燕), Member, ACM, Hua-Dong Ma* (马华东), Member, CCF, ACM, IEEE and Peng-Rui Duan (段鹏瑞)   

  1. Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • 收稿日期:2012-05-03 修回日期:2013-01-18 出版日期:2013-05-05 发布日期:2013-05-05
  • 作者简介:Pei-Yan Yuan received the B.S. and M.S. degrees in computer science from Henan Normal University, in 2001 and Wuhan University of Technology, China, in 2007, respectively. He is currently a Ph.D. student in the School of Computer Science, Beijing University of Posts and Telecommunications. His research interests include networking and protocol engineering, mobile ad hoc networks, sensor networks, delaytolerant networks, social networks, quality of service, performance evaluation, etc. He is a member of ACM.
  • 基金资助:

    This work is supported by the National Basic Research 973 Program of China under Grant No. 2011CB302701, the National Science Fund for Distinguished Young Scholars of China under Grant No. 60925010, the National Natural Science Foundation of China under Grant Nos. 61133015, 61003280, and 61272517, the Funds for Creative Research Groups of China under Grant No. 61121001, the Program for Changjiang Scholars and Innovative Research Team in University of China under Grant No. IRT1049, and the Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20120005130002.

Impact of Strangers on Opportunistic Routing Performance

Pei-Yan Yuan (袁培燕), Member, ACM, Hua-Dong Ma* (马华东), Member, CCF, ACM, IEEE, and Peng-Rui Duan (段鹏瑞)   

  1. Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Received:2012-05-03 Revised:2013-01-18 Online:2013-05-05 Published:2013-05-05
  • Contact: 10.1007/s11390-013-1357-x
  • Supported by:

    This work is supported by the National Basic Research 973 Program of China under Grant No. 2011CB302701, the National Science Fund for Distinguished Young Scholars of China under Grant No. 60925010, the National Natural Science Foundation of China under Grant Nos. 61133015, 61003280, and 61272517, the Funds for Creative Research Groups of China under Grant No. 61121001, the Program for Changjiang Scholars and Innovative Research Team in University of China under Grant No. IRT1049, and the Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20120005130002.

由于节点之间的间歇式连通及无法获取网络全局知识,使得机会网络中的路由算法面临更大的挑战。在数据包的转发过程中,大部分工作采取一种贪婪的转发策略,也就是说,只把数据包转发给到目前为止效用最高的节点。普遍缺乏对洪泛路由最优路径特征的深入研究。由于洪泛算法刻画了数据包传播延时的下限和路由负载的上限,分析洪泛过程中最优路径特征对于设计高效的机会路由至关重要。基于这点考虑,本文通过观察最优路径上节点社会关系的变化来识别这些特征。通过对三种数据集的分析,本文发现陌生人在转发过程中具有两面性,一方面加快了数据包的扩散,另一方面也加重了路由负载;同时,随着转发过程的进行,陌生人所起的作用逐渐减低。基于这些现象,本文提出了一种轻量级分布式的机会转发算法:STRON。分布式的特征使得STRON非常适合于机会场景,轻量级的特点使得它很容易整合于其它经典的算法。模拟结果显示,STRON在路由负载和传播延时方面均优于经典的算法,同时保持了与洪泛算法近似的投递率。

Abstract: Routing is one of the challenging tasks in Delay Tolerant Networks (DTNs), due to the lack of global knowledge and sporadic contacts between nodes. Most existing studies take a greedy scheme in data forwarding process, i.e., only nodes with higher utility values than current carriers can be selected as relays. They lack an in-depth investigation on the main features of the optimal paths in Epidemic. These features are vital to any forwarding scheme that tends to make a trade-off between packet delivery delay and cost. This is mainly because Epidemic provides an upper bound on cost and a lower bound on delivery delay. Therefore, a deep understanding of these features is useful to make informed forwarding decisions. In this paper, we try to explore these features by observing the roles of different social relationships in the optimal paths through a set of real datasets. These datasets provide evidence that strangers have two sides in data forwarding process, and that the importance of strangers shows a decreasing trend along the forwarding paths. Using this heuristic knowledge, we propose STRON, a distributed and lightweight forwarding scheme. The distributed feature makes it very suitable for opportunistic scenarios and the low communication and computation features make it easy to be integrated with state-of-the-art work. The trace-driven simulations obviously confirm its effectiveness, especially in terms of packet delivery delay and cost.

[1] Fall K, Farrell S. DTN: An architectural retrospective. IEEE Journal on Selected Areas in Communications, 2008, 26(5): 828-836.

[2] Conti M, Kumar M. Opportunities in opportunistic computing. Computer, 2010, 43(1): 42-50.

[3] Vahdat A, Becker D. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, 2000.

[4] Burgess J, Gallagher B, Jensen D, Levine B N. MaxProp: Routing for vehicle-based disruption-tolerant networks. In Proc. the 25th INFOCOM, April 2006, pp.1-11.

[5] Lindgren A, Doria A, Schelen O. Probabilistic routing in intermittently connected networks. ACM SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3): 19-20.

[6] Leguay J, Friedman T, Conan V. Evaluating mobility pattern space routing for DTNs. In Proc. the 25th INFOCOM, April 2006, pp.1-10.

[7] Yuan P, Ma H. Hug: Human gathering point based routing for opportunistic networks. In Proc. WCNC, March 2012, pp.3024-3029.

[8] Nguyen N, Dinh T, Tokala S. Thai M. Overlapping communities in dynamic networks: Their detection and mobile applications. In Proc. the 17th MOBICOM, Sept. 2011, pp.85-96.

[9] Hui P, Crowcroft J, Yoneki E. BUBBLE rap: Social-based forwarding in delay tolerant networks. In Proc. the 9th MobiHoc, May 2008, pp.241-250.

[10] Mtibaa A, May M, Diot C, Ammar M. PeopleRank: Social opportunistic forwarding. In Proc. the 29th INFOCOM, March 2010, pp.111-115.

[11] Daly E, Haahr M. Social network analysis for routing in disconnected delay-tolerant MANETs. In Proc. the 8th MobiHoc, Sept. 2007, pp.32-40.

[12] Palla G, Derényi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818.

[13] Shah R, Roy S, Jain S et al. Data MULEs: Modeling and analysis of a three-tier architecture for sparse sensor networks. Ad Hoc Networks, 2003, 1(2/3): 215-233.

[14] Li Q, Rus D. Sending messages to mobile users in disconnected ad-hoc wireless networks. In Proc. the 6th MobiCom, Aug. 2000, pp.44-55.

[15] Zhao W, Ammar M, Zegura E. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In Proc. the 5th MobiHoc, Sept. 2004, pp.187-198.

[16] Zhao W, Ammar M, Zegura E. Controlling the mobility of multiple data transport ferries in a delay-tolerant network.In Proc. the 24th INFOCOM, March 2005, pp.1407-1418.

[17] He T, Lee K, Swami A. Flying in the dark: Controlling autonomous data ferries with partial observations. In Proc. the 11th MobiHoc, Sept. 2010, pp.141-150.

[18] Spyropoulos T, Psounis K, Raghavendra C. Efficient routing in intermittently connected mobile networks: The multiplecopy case. Transactions on Networking, 2008, 16(1): 77-90.

[19] Qin R, Li Z, Wang Y et al. An integrated network of roadside sensors and vehicles for driving safety: Concept, design and experiments. In Proc. the 8th PerCom, March 29-April 2, 2010, pp.79-87.

[20] Ivancic W, Wood L, Hdiday P et al. Experience with delaytolerant networking from orbit. In Proc. the 4th ASMS, Aug. 2008, pp.173-178.

[21] Merugu S, Ammar M, Zegura E. Routing in space and time in networks with predictable mobility. Technical Report GITCC-04-7, Georgia Institute of Technology, 2004.

[22] Jain S, Fall K, Patra S. Routing in a delay tolerant network. In Proc. the ACM SIGCOMM, Aug. 30-Sept. 3, 2004, pp.145158.

[23] Liu C, Wu J. Routing in a cyclic mobispace. In Proc. the 9th MobiHoc, May 2008, pp.351-360.

[24] Musolesi M, Hailes S, Mascolo C. Adaptive routing for intermittently connected mobile ad hoc networks. In Proc. the 6th WoWMoM, June 2005, pp.183-189.

[25] Yuan Q, Cardei I, Wu J. Predict and relay: An efficient routing in disruption-tolerant networks. In Proc. the 10th MobiHoc, May 2009, pp.95-104.

[26] Gaito S, Pagani E, Rossi G. Strangers help friends to communicate in opportunistic networks. Computer Networks, 2011, 55(2): 374-385.

[27] Yoneki E, Hui P, Crowcroft J. Visualizing community detection in opportunistic networks. In Proc. the 2nd CHANTS, Sept. 2007, pp.93-96.

[28] Hui P. People are the network: Experimental design and evaluation of social-based forwarding algorithms. Technical Report UCAM-CL-TR-713, University of Cambridge, March 2008.

[29] Rhee I, Shin M, Hong S et al. On the levy-walk nature of human mobility. In Proc. the 27th INFOCOM, April 2008, pp.924-932.

[30] Lee K, Hong S, Kim S et al. SLAW: A mobility model for human walks. In Proc. the 28th INFOCOM, April 2009, pp.855-863.

[31] Zyba G, Voelker G, Ioannidis S et al. Dissemination in opportunistic mobile ad-hoc networks: The power of the crowd. In Proc. the 30th INFOCOM, April 2011, pp.1179-1187.

[32] Pietiläinen A, Diot C. Dissemination in opportunistic social networks: The role of temporal communities. In Proc. the 13th MobiHoc, June 2012, pp.165-174.

[33] Sarwar B, Karypis G, Konstan J et al. Application of dimensionality reduction in recommender system——A case study. In Proc. WEBKDD, Aug. 2000, pp.1-12.

[34] Zhang Y, Yu T. Mining trust relationships from online social networks. Journal of Computer Science and Technology, 2012, 27(3): 492-505.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Harald E. Otto;. UNDO, An Aid for Explorative Learning?[J]. , 1992, 7(3): 226 -236 .
[2] 马颂德; 魏国庆; 黄金风;. Segment Based Camera Calibration[J]. , 1993, 8(1): 11 -16 .
[3] 胡占义; 杨长江; 杨毅; 马颂德;. An Inherent Probabilistic Aspect of the Hough Transform[J]. , 1999, 14(1): 44 -48 .
[4] 李晓山;. Decidability of Mean Value Calculus[J]. , 1999, 14(2): 173 -180 .
[5] 刘云龙; 陈俊亮;. Garbage Collection in Uncoordinated Checkpointing Algorithms[J]. , 1999, 14(3): 242 -249 .
[6] 黄雄; 李未;. On k-Positive Satisfiability Problem[J]. , 1999, 14(4): 309 -313 .
[7] 齐越胜; 王保中; 康立山;. Genetic Programming with Simple Loops[J]. , 1999, 14(4): 429 -433 .
[8] 刘斌; 卢增祥; 甘泉; 冯翱; 王普;. Infomarker—A New Internet Information Service System[J]. , 2000, 15(3): 300 -304 .
[9] . 一个基于高级数据模型的说明性XML更新语言[J]. , 2005, 20(3): 373 -377 .
[10] . 隐式曲面的反射和折射绘制[J]. , 2006, 21(2): 166 -172 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: