作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 移动互联与通信技术 • 上一篇    下一篇

基于节点相似性的容迟网络概率路由算法

宋有美1,李建波1,和天玥2,徐吉兴1   

  1. (1.青岛大学 信息工程学院,山东 青岛 266071; 2.南京邮电大学 海外教育学院,南京 210023)
  • 收稿日期:2015-09-06 出版日期:2016-09-15 发布日期:2016-09-15
  • 作者简介:宋有美(1991-),女,硕士研究生,主研方向为容延网络、路由算法;李建波(通讯作者),教授、博士、CCF会员;和天玥,本科生;徐吉兴,硕士研究生。
  • 基金资助:
    国家自然科学基金资助项目(61502261,61572457,61379132);山东省自然科学基金资助项目(ZR2013FQ022);山东省教育厅高校科技计划基金资助项目(J14LN85)。

Probabilistic Routing Algorithm in Delay Tolerant Network Based on Node Similarity

SONG Youmei 1,LI Jianbo 1,HE Tianyue 2,XU Jixing 1   

  1. (1.College of Information Engineering,Qingdao University,Qingdao,Shandong 266071,China; 2.College of Overseas Education,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)
  • Received:2015-09-06 Online:2016-09-15 Published:2016-09-15

摘要: 在容迟网络(DTN)中节点密度稀疏和节点移动导致网络拓扑结构频繁割裂,消息在传递时无法始终存在一条端到端的连通路径,因此DTN路由算法通常采用存储-携带-转发机制将消息从源节点投递至目的节点。针对上述情况,结合节点间相似性与消息生存时间内节点到达目的节点的概率值,提出一种基于节点相似性的概率路由算法(SBPR),包含消息复制与消息转发2种策略。当持有消息的节点与其他节点相遇时,将消息复制给消息节点相似性较小的节点以提高消息投递率。对于与其相似性较大的邻居节点,如果该邻居节点到达目的节点的概率更大,将消息转发至邻居节点以节省网络资源消耗。实验结果表明,在节点缓存不足的情况下,SBPR在消息投递率、网络负载率及消息丢包数等方面的表现均优于Epidemic,Prophet和First Contact路由算法。

关键词: 容迟网络, 路由算法, 消息复制, 节点相似性, 概率转发

Abstract: In Delay Tolerant Network(DTN),due to the frequent network partitions caused by sparse node density and node mobility,there is not always a connected end-to-end path in the process of message delivery.Thus,the routing algorithms in DTN generally adopt a store,carry and forward mechanism so as to deliver a message from a source to a destination.For the above problems,a Similarity-based Probabilistic Routing(SBPR) algorithm is proposed,which combines the concept of node similarity with the delivery probability to the destination during the messages’ Time to Live(TTL).Both message replication and message forwarding strategies are adopted in SBPR.Concretely,on one hand,when a node holding messages encounters other nodes,it replicates the message to the neighboring node which has a smaller inter-node similarity,so as to increase the message delivery ratio.On the other hand,if a neighboring node has a larger node similarity and delivery probability to the destination node,it forwards the message to this neighboring node for the purpose of saving the network resource consumption.Expermental result shows that the proposed SBPR outperforms Epidemic,Prophet and First Contact(FC) routing algorithms in terms of delivery ratio,network overhead ratio and message dropping ratio in the case of insufficient node buffer.

Key words: Delay Tolerant Network(DTN), routing algorithm, message copy, node similarity, probabilistic forwarding

中图分类号: