基于节点相似性的容延/容断网络路由算法

doi:10.11772/j.issn.1001-9081.2014.09.2476

计算机应用 ›› 2014, Vol. 34 ›› Issue (9): 2476-2481.DOI: 10.11772/j.issn.1001-9081.2014.09.2476

基于节点相似性的容延/容断网络路由算法

戴晨曲,李建波,由磊,徐吉兴

青岛大学信息工程学院，山东青岛 266071

收稿日期:2014-02-10 修回日期:2014-03-18 出版日期:2014-09-01 发布日期:2014-09-30
通讯作者: 李建波
作者简介:
戴晨曲(1987-),女,山东潍坊人,硕士研究生,主要研究方向:容延网络路由算法;
李建波(1980-),男,山东潍坊人,副教授,博士,主要研究方向:传感网络、容延网络路由;
由磊(1989-),男,山东海阳人,硕士研究生,主要研究方向:车载自组织网络路由;
徐吉兴(1989-),男,山东栖霞人,硕士研究生,主要研究方向:Ad Hoc网络路由算法。
基金资助:
青岛市科技计划基础研究项目;山东省自然科学基金资助项目;山东省教育厅项目

Routing algorithm based on node similarity in delay/disruption tolerant networks

DAI Chenqu,LI Jianbo,YOU Lei,XU Jixing

College of Information Engineering, Qingdao University, Qingdao Shandong 266071, China

Received:2014-02-10 Revised:2014-03-18 Online:2014-09-01 Published:2014-09-30
Contact: LI Jianbo
Supported by:
Foundation Research Project of Qingdao Science and Technology Plan

摘要/Abstract

摘要：

针对容延/容断网络(DTN)网络的时延高、割裂频繁，以及节点缓存和能量受限等网络特性，为提高容延网络的传输率，同时降低网络开销和网络时延，提出了一种基于节点相似性的容延网络路由算法(RABNS)。该算法利用历史相遇信息预测节点未来相遇概率，并且把历史相遇的节点录入为集合，利用集合的交集运算来评估一对相遇节点的相似性，并以此为判定条件控制网络中的副本数量。在模拟器The ONE上采用RandomWaypoint运动模型进行仿真，其中RABNS在消息投递率方面优于PROPHET，网络负载约为PROPHET的50%，较大程度上提高了网络资源利用率；平均时延稍高于Epidemic但低于PROPHET，节点缓存空间大小对算法的平均跳数影响不大，且RABNS的平均跳数约为PROPHET的一半。仿真结果表明，RABNS能有效地限制消息洪泛，获取更高的消息投递率、更低的网络开销和数据时延，因此尤其适用于节点存储空间有限的DTN环境和具有群居特性的社交容延网络中。

Abstract:

Delay/Disruption Tolerant Network (DTN) has characteristics of long delay, intermittent disruption, and limitation of buffer space and energy. To improve the delivery rate of messages, while reducing network overhead and the average latency, a new Routing Algorithm Based on Node Similarity (RABNS) in DTN was proposed. The algorithm used historical information to predict node encounter probability in future. The nodes which encountered historically were recorded as a collection, then the set intersection operation was applied to evaluate the similarity of a pair of nodes. And the similarity was used to control the number of copies in the network. Simulations were conducted on The ONE platform using RandomWaypoint motion model. In the simulation, RABNS performed better than PROPHET (Probabilistic ROuting Protocol using History of Encounters and Transitivity) in the message delivery rate. And the network overhead of RABNS was about half of PROPHET, which greatly improved the utilization of network resources. The average latency of RABNS was a little higher than Epidemic but lower than PPROPHET, the node cache size did not have a significant impact on average-hops, and its average-hops was about half of PROPHET. The simulation results show that RABNS can effectively limit the message flooding with higher message delivery rate, lower network overhead and average latency, therefore it is suitable for the DTN scenes with limited nodes' storage and also applicable in social DTN with gregarious characteristics.

中图分类号:

TP393

戴晨曲李建波由磊徐吉兴. 基于节点相似性的容延/容断网络路由算法[J]. 计算机应用, 2014, 34(9): 2476-2481.

DAI Chenqu LI Jianbo YOU Lei XU Jixing. Routing algorithm based on node similarity in delay/disruption tolerant networks[J]. Journal of Computer Applications, 2014, 34(9): 2476-2481.

参考文献

［1］FALL K. A delay-tolerant network architecture for challenged Internets ［C］// Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. New York: ACM, 2003: 27-34.

［2］ZHANG L, ZHOU X, WANG J, et al.Routing protocols for delay and disruption tolerant networks ［J］. Journal of Software, 2010, 21(10): 2554-2572. (张龙,周贤伟,王建萍,等. 容迟与容断网络中的路由协议［J］. 软件学报, 2010, 21(10):2554-2572.)

［3］AKKAYA K, YOUNIS M. A survey on routing protocols for wireless sensor networks ［J］. Ad Hoc Networks, 2005, 3(3):325-349.

［4］WU H, FUJIMOTO R, GUENSLER R, et al.MDDV: a mobility-centric data dissemination algorithm for vehicular networks ［C］// VANET '04: Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks. New York: ACM, 2004: 47-56.

［5］PEREIRA P R, CASACA A, RODRIGUES J J P C, et al.From delay-tolerant networks to vehicular delay-tolerant networks ［J］. IEEE Communications Surveys & Tutorials, 2012, 14(4):1166-1182.

［6］SOARES V, RODRIGUES J, FARAHMAND F. GeoSpray: a geographic routing protocol for vehicular delay-tolerant networks ［J］. Information Fusion, 2011, 15:102-113.

［7］GUO Z, WANG B, CUI J. Generic prediction assisted single-copy routing in underwater delay tolerant sensor networks ［J］. Ad Hoc Networks, 2013, 11(3):1136-1149.

［8］DEMMER M, FALL K. DTLSR: Delay tolerant routing for developing regions ［C］// Proceedings of the 2007 Workshop on Networked Systems for Developing Regions. New York: ACM, 2007: No.5.

［9］JAIN S, FALL K, PATRA R. Routing in a delay tolerant networks ［C］// Proceedings of the 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2004:145-158.

［10］AHMED S, KANHERE S. A Bayesian routing framework for delay tolerant networks ［C］// WCNC 2010: Proceedings of the 2010 IEEE Wireless Communications and Networking Conference. Piscataway: IEEE, 2010:1-6

［11］GUO Z, WANG B, CUI J. Prediction assisted single-copy routing in underwater delay tolerant networks ［C］// GLOBECOM 2010: Proceedings of the Global Telecommunications Conference. Piscataway: IEEE, 2010: 1-6

［12］SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks ［C］// WDTN '05: Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. New York: ACM, 2005: 252-259.

［13］LINDGREN A, DORIA A, SCHELEN O. Probabilistic routing in intermittently connected networks ［J］. ACM SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3):19-20.

［14］JAIN S, DEMMER M, PATRA R, et al.Using redundancy to cope with failures in a delay tolerant networks ［C］// Proceedings of the 2005 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2005:109-120.

［15］WANG Y, JAIN S, MARTONOSI M, et al.Erasure-coding based routing for opportunistic networks ［C］// Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. New York: ACM, 2005:229-236.

［16］WIDMER J, BOUDEC J. Network coding for efficient communication in extreme networks ［C］// Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. New York: ACM, 2005:284-291.

［17］LIU C, WU J. On Multicopy opportunistic forwarding protocols in nondeterministic delay tolerant networks ［J］. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(6):1121-1128

［18］ZHU Y, XU B, SHI X, et al.A survey of social-based routing in delay tolerant networks: positive and negative social effects ［J］. IEEE Communications Surveys & Tutorials, 2013, 15(1):387 - 401

［19］VAHDAT A, BECKER D. Epidemic routing for partially connected Ad Hoc networks, CS-2000-06 ［R］. Durham: Duke University, Department of Computer Science, 2000.

［20］KERANEN A, OTT J, KARKKAINEN T. The ONE simulator for DTN protocol evaluation ［C］// Proceedings of the 2nd International Conference on Simulation Tools and Techniques. New York: ACM, 2009: No.55.

[1]	毕文婷林海涛张立群. 基于多阶段演化信号博弈模型的移动目标防御决策算法[J]. 计算机应用, 0, (): 0-0.
[2]	朱玉娜, 张玉涛, 闫少阁, 范钰丹, 陈韩托. 基于半监督子空间聚类的协议识别方法[J]. 计算机应用, 2021, 41(10): 2900-2904.
[3]	杨书新许景峰. 基于反向影响采样的积极影响力最大化[J]. 计算机应用, 0, (): 0-0.
[4]	郭棉, 张锦友. 移动边缘计算环境中面向机器学习的计算迁移策略[J]. 计算机应用, 2021, 41(9): 2639-2645.
[5]	倪萍, 陈伟. 基于模糊测试的反射型跨站脚本漏洞检测[J]. 计算机应用, 2021, 41(9): 2594-2601.
[6]	曾续玲李陶深巩健杜利俊. 无线供能移动边缘计算系统的安全卸载优化[J]. 计算机应用, 0, (): 0-0.
[7]	谢家贵李志平金键. 基于星火区块链的跨链机制[J]. 计算机应用, 0, (): 0-0.
[8]	张立群林海涛郇文明毕文婷. 基于OpenFlow的软件定义网络流规则冲突检测系统的设计与仿真[J]. 计算机应用, 0, (): 0-0.
[9]	赖涵光李清江勇. 基于场景变化的传输控制协议拥塞控制切换方案[J]. 计算机应用, 0, (): 0-0.
[10]	陈葳葳, 曹利, 顾翔. 基于区块链的车联网电子取证模型[J]. 计算机应用, 2021, 41(7): 1989-1995.
[11]	肖跃雷, 邓小凡. 基于证书的有线局域网安全关联方案改进与分析[J]. 计算机应用, 2021, 41(7): 1970-1976.
[12]	邓伟健陈曦. 基于时变资源的容器化虚拟网络映射算法[J]. 计算机应用, 0, (): 0-0.
[13]	董文涛, 李卓, 陈昕. 基于联邦学习的在线短视频内容分发策略[J]. 计算机应用, 2021, 41(6): 1551-1556.
[14]	施安妮, 李陶深, 王哲, 何璐. 基于缓存辅助的全双工无线携能通信系统的中继选择策略[J]. 计算机应用, 2021, 41(6): 1539-1545.
[15]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.

基于节点相似性的容延/容断网络路由算法

Routing algorithm based on node similarity in delay/disruption tolerant networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics