计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 13-19.DOI: 10.11772/j.issn.1001-9081.2017071824

• 2017年全国开放式分布与并行计算学术年会(DPCS 2017)论文 • 上一篇    下一篇

移动机会网络中一种轻量级的分布式社会距离路由算法

袁培燕, 宋明阳   

  1. 河南师范大学 计算机与信息工程学院, 河南 新乡 453007
  • 收稿日期:2017-07-24 修回日期:2017-08-04 出版日期:2018-01-10 发布日期:2018-01-22
  • 通讯作者: 袁培燕
  • 作者简介:袁培燕(1978-),男,河南邓州人,副教授,博士,CCF高级会员,主要研究方向:移动通信与群智计算;宋明阳(1991-),男,河南安阳人,硕士研究生,主要研究方向:移动机会网络。
  • 基金资助:
    国家自然科学基金资助项目(U1404602);河南省科技攻关项目(172102210341);河南省高等学校青年骨干教师资助计划项目(2015GGJS086);河南师范大学博士科研启动课题项目(qd14136);河南师范大学青年骨干教师基金资助项目(15018)。

Lightweight distributed social distance routing algorithm in mobile opportunistic network

YUAN Peiyan, SONG Mingyang   

  1. School of Computer and Information Engineering, Henan Normal University, Xinxiang Henan 453007, China
  • Received:2017-07-24 Revised:2017-08-04 Online:2018-01-10 Published:2018-01-22
  • Supported by:
    This work is partially supported by by the National Natural Science Foundation of China (U1404602), the Science and Technology Foundation of Henan Province (172102210341), the Young Scholar Program of Henan Province (2015GGJS086), the Doctoral Research Startup Project of Henan Normal University (qd14136), the Young Scholar Program of Henan Normal University (15018).

摘要: 目前大部分机会路由算法采取洪泛的方式进行辅助信息的交换造成网络资源浪费严重。针对此问题,提出了一种分布式社会距离路由算法。首先,通过分析节点间接触的稳定性与规律性来确定朋友关系。其次,通过朋友关系来构建节点间的社会距离;进一步地,每个节点维护一张用于记录当前已知的到其他节点的最短社会距离表,通过朋友节点之间相互交换并比较表中信息来不断更新最短社会距离。由于社会距离的构建与更新只需要朋友之间交换信息而并不需要全部节点来参与,极大地减少了辅助信息的交换次数。最后,数据包被发送到与其目的节点社会距离较近的中继节点,保证了数据包高效率地投递。实验结果表明:与接触和传输记录的概率路由(PRoPHET)算法相比投递率提升约3%,包传输延时降低约27%,辅助信息交换次数减少约63%;与基于中心度与相似度的路由(SimBet)算法相比包投递率提升约11%,包传输延时方面基本持平,辅助信息交换次数减少约63%。社会距离路由算法在可扩展性方面的良好表现,为移动机会网络大规模部署提供了理论支撑。

关键词: 移动机会网络, 路由协议, 朋友关系, 辅助信息, 社会距离

Abstract: In most routing algorithms of the previous work, the flooding method is used to obtain auxiliary information, which wastes network resources. Motivated by this, a distributed social distance routing algorithm was proposed. Firstly, the stability and regularity of contact between nodes were analyzed to determine the friend relationship. Then, the social-distance between nodes was constructed by the friend relationship. In addition, a table for recording the shortest social distance to other nodes was maintained by each node, and the minimum social distance was continually updated by exchanging and comparing the information in the table. The construction of social distance only needs to exchange information among friends instead of all nodes, which can greatly reduce the time of auxiliary-information exchange. Finally, when the packet was sent to the relay node with a smaller social distance to its destination node, the delivery ratio could be significantly improved. The experimental results demonstrate that, compared with the Probabilistic Routing Protocol using History of Encounters and Transitivity (PRoPHET) algorithm, the delivery ratio of the proposed algorithm is increased by about 3%, the data packet transmission delay is reduced by about 27%, and the auxiliary-information exchange times is reduced by about 63%. Compared with the routing based on Betweenness centrality and Similarity (SimBet) algorithm, the delivery ratio of the proposed algorithm is increased by about 11%, the data packet transmission delay basically equals, the auxiliary-information exchange times is reduced by about 63%. The social distance algorithm provides a theoretic support for large-scale mobile opportunistic networks, because of its better performance in scalability.

Key words: mobile opportunistic network, routing protocol, friend relationship, auxiliary-information, social distance

中图分类号: