留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于聚类算法的机会网络路由算法

何志立 潘达儒 宋晖

何志立, 潘达儒, 宋晖. 一种基于聚类算法的机会网络路由算法[J]. 华南师范大学学报(自然科学版), 2019, 51(4): 120-128. doi: 10.6054/j.jscnun.2019076
引用本文: 何志立, 潘达儒, 宋晖. 一种基于聚类算法的机会网络路由算法[J]. 华南师范大学学报(自然科学版), 2019, 51(4): 120-128. doi: 10.6054/j.jscnun.2019076
HE Zhili, PAN Daru, SONG Hui. An Opportunistic Network Routing Algorithm Based on Clustering Algorithm[J]. Journal of South China normal University (Natural Science Edition), 2019, 51(4): 120-128. doi: 10.6054/j.jscnun.2019076
Citation: HE Zhili, PAN Daru, SONG Hui. An Opportunistic Network Routing Algorithm Based on Clustering Algorithm[J]. Journal of South China normal University (Natural Science Edition), 2019, 51(4): 120-128. doi: 10.6054/j.jscnun.2019076

一种基于聚类算法的机会网络路由算法

doi: 10.6054/j.jscnun.2019076
基金项目: 

国家自然科学基金项目 61471175

国家自然科学基金项目 61771206

详细信息
    通讯作者:

    宋晖,讲师,Email:songhui@m.scnu.edu.cn

  • 中图分类号: TP393

An Opportunistic Network Routing Algorithm Based on Clustering Algorithm

  • 摘要: 在传统的历史路径算法的基础上,提出一种基于聚类算法的历史路径机会网络路由算法(RACA算法).该算法使用无监督学习中的k-means++算法对节点进行编码,并使用编码的方式更新历史路径算法,具有缓存空间占用低、节点搜索速度快和在拓扑结构多变的环境的适应性强等特点.实验结果表明:RACA算法在多个方面有着较好的表现,特别是在传输成功率和开销比率方面有较好的表现; 出色的网络性能表现使得RACA算法能够在资源有限的场景和网络环境变化较大的场景使用,例如车载网络环境.
  • 图  1  节点的分布区域示意图

    注:红黄绿三区分别代表节点不同的区域分类.

    Figure  1.  The node distribution in a simulation environment

    图  2  进行节点分类后的结果

    注:每种颜色表示同一类的节点.

    Figure  2.  The results from k-means++ classification

    图  3  不同分类个数下的DBI值

    Figure  3.  The DBI values for different classification numbers

    图  4  不同分类个数的分类效果

    注:每种颜色表示同一类的节点.

    Figure  4.  The results from different classification numbers

    图  5  成功转发记录的更新示意图

    注:Ni为更新前编号为i的节点,Ci为更新后编号为i的节点.

    Figure  5.  The update process of successful transmission records

    图  6  系统结构示意图

    Figure  6.  The structure of the system models

    图  7  缓存大小对成功传输率的影响

    Figure  7.  The impact of cache size on delivery ratio

    图  8  缓存大小对传输延时的影响

    Figure  8.  The impact of cache size on delivery latency

    图  9  缓存大小对开销比率的影响

    Figure  9.  The impact of cache size on overhead ratio

    图  10  缓存大小对缓存时间的影响

    Figure  10.  The impact of cache size on buffer time

    图  11  缓存大小对平均跳数的影响

    Figure  11.  The impact of cache size on average hop count

    图  12  缓存大小对网络率的影响

    Figure  12.  The impact of cache size on network ratio

  • [1] 胡四泉, 红兵, 俊峰.机会型网络研究综述[J].计算机科学, 2009, 36(10):32-37. doi: 10.3969/j.issn.1002-137X.2009.10.008

    HU S Q, HONG B, JUN F. Survey on opportunistic networks[J]. Computer Science, 2009, 36(10):32-37. doi: 10.3969/j.issn.1002-137X.2009.10.008
    [2] 熊永平, 孙利民, 牛建伟, 等.机会网络[J].软件学报, 2009, 20(1):124-137. http://d.old.wanfangdata.com.cn/Periodical/rjxb200901010

    XIONG Y P, SUN L M, NIU J W, et al. Opportunistic networks[J]. Journal of Software, 2009, 20(1):124-137. http://d.old.wanfangdata.com.cn/Periodical/rjxb200901010
    [3] MUSOLESI M, HAILES S, MASCOLO C. Adaptive routing for intermittently connected mobile ad hoc networks[C]//Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks. Washington: IEEE, 2005: 183-189.
    [4] NAUMOV V, GROSS T R. Connectivity-aware routing (CAR) in vehicular ad-hoc networks[C]//Proceedings of the 2007-26th IEEE International Conference on Compu- ter Communications. Washington: IEEE, 2007: 1919-1927.
    [5] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. New York: ACM, 2005: 252-259.
    [6] VAHDAT A, BECKER D. Epidemic routing for partially connected ad hoc networks: Technical Report CS-200006[R]. Durham: Duke University, 2000.
    [7] LINDGREN A, DORIA A, SCHELÉN O. Probabilistic routing in intermittently connected networks[C]//ACM SIGMOBILE Mobile Computing and Communications Review. New York: ACM, 2003, 7(3): 19-20.
    [8] BURGESS J, GALLAGHER B, JENSEN D D, et al. MaxProp: routing for vehicle-based disruption-tolerant networks[C]//Proceedings of the 25th IEEE International Conference on Computer Communications. Barcelona: IEEE, 2006: 1-11.
    [9] LI L, QIN Y, ZHONG X. A novel routing scheme for resource-constraint opportunistic networks:a cooperative multiplayer bargaining game approach[J]. IEEE Transactions on Vehicular Technology, 2016, 65(8):6547-6561. doi: 10.1109/TVT.2015.2476703
    [10] MAI L, PAN D, SONG H, et al. A T2T-based offloading method:virtual bank with movement prediction[J]. IEEE Access, 2018, 6:16408-16422. doi: 10.1109/ACCESS.2018.2801022
    [11] YOON J, KIM S K, LEE J Y, et al. An enhanced friendship-based routing scheme exploiting regularity in an opportunistic network[C]//Proceedings of the 2016 IEEE International Conference on Internet of Things(iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data(SmartData). Chengdu: IEEE, 2016: 51-57.
    [12] LIU Q, HU C, LI Y, et al. An interest community routing scheme for opportunistic networks[C]//Proceedings of the 2013 IEEE Global Communications Conference. Atlanta: IEEE, 2013: 4366-4371.
    [13] ZHAO L, LI Y, MENG C, et al. A SVM based routing scheme in VANETs[C]//Proceedings of the 2016 16th International Symposium on Communications and Information Technologies. Qingdao: IEEE, 2016: 380-383.
    [14] SHARMA D K, DHURANDHER S K, WOUNGANG I, et al. A machine learning-based protocol for efficient routing in opportunistic networks[J]. IEEE Systems Journal, 2018, 12(3):2207-2213. doi: 10.1109/JSYST.2016.2630923
    [15] DAVIES D L, BOULDIN D W. A cluster separation mea-sure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979(2):224-227.
    [16] AGARWAL P K, MUSTAFA N H. k-means projective clustering[C]//Proceedings of the Twenty-third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2004: 155-165.
    [17] ALOISE D, DESHPANDE A, HANSEN P, et al. NP-hardness of euclidean sum-of-squares clustering[J]. Machine Learning, 2009, 75(2):245-248. doi: 10.1007/s10994-009-5103-0
    [18] ARTHUR D, VASSILVITSKⅡ S. k-means++: the advantages of careful seeding[C]//Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM, 2007: 1027-1035.
    [19] KERÄNEN A, OTT J, KÄRKKÄINEN T. The ONE simulator for DTN protocol evaluation[C]//Proceedings of the 2nd International Conference on Simulation Tools and Techniques. Brussels, Belgium: ICST, 2009: 55.
    [20] KERANEN A. Opportunistic network environment simulator[R]. Finland: Helsinki University of Technology, Department of Communications and Networking, 2008.
  • 加载中
图(12)
计量
  • 文章访问数:  1838
  • HTML全文浏览量:  590
  • PDF下载量:  31
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-03-05
  • 刊出日期:  2019-08-25

目录

    /

    返回文章
    返回