基于二部图匹配的车载网络分布式存储机制
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61502320,61373161,61173009);国家科技支撑计划(2014BAF07B03);北京市教委项目(KM201410028015);深圳市基础研究计划(JCYJ20140509150917445);软件开发环境国家重点实验室开放课题(SKLSDE-2015ZX-25);中央高校基础科研业务费;北京市优秀人才培养资助青年骨干个人项目(2014000020124G133);首都师范大学青年燕京学者培育对象


Distributed Storage Scheme Using Bipartite Graph Matching for Vehicular Networks
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61502320, 61373161, 61173009); National Key Technology Support Program (2014BAF07B03); Science & Technology Project of Beijing Municipal Commission of Education (KM201410028015); Science Foundation of Shenzhen City (JCYJ20140509150917445); State Key Laboratory of Software Development Environment (SKLSDE-2015ZX-25); Fundamental Research Funds for the Central Universities; Youth Backbone Project of Beijing Outstanding Talent Training Project (2014000020124G133); Cultivation Object of Young Yanjing Scholar of Capital Normal University

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    现有的车载网络中对数据存储机制的研究大多以移动车载节点作为数据载体,然而车载节点的快速移动、存储空间有限、存在安全风险等特性,限制了车载网络数据存储性能的进一步优化.针对部署有路边基础设施的车载网络场景,以路边单元作为存储节点,提出了基于二部图匹配的车载网络分布式存储机制(distributed storage scheme,简称DSS).在车载网络中,以最大化数据响应率为目标,路边单元的数据存储问题是NP完全问题.首先,依据请求分割规则将原问题转化为二部图最大匹配问题,其中,二部图左顶点代表车载节点的请求,右顶点代表路边单元的存储单元;进而,利用Hungarian算法在多项式时间内求得最优解.由于问题转化可能造成不同路边单元存储相同数据的冗余问题,设计了冗余副本清理算法,依据不同副本的响应因子排序,检查并清理冗余副本.实验结果表明:DSS能够提高数据响应率,降低响应时延,并保持较小的网络资源开销.

    Abstract:

    The vast majority of existing studies on data distribution in vehicular networks utilize the mobile vehicular nodes as content carriers, however the high mobility, the limited resources and the security risks of vehicular nodes prohibit the performance improvements. This paper proposes a distributed storage scheme named DSS using bipartite graph matching for vehicular networks where roadside units are regarded as storage devices. Considering the content replication at roadside units is NP-complete, DSS tackles the problem by transforming it into a maximal matching problem of bipartite graph in which the left vertices stand for the requests from vehicular nodes and the right vertices represent the storage cells of roadside units. Hence the original problem is solved by Hungarian algorithm in polynomial time. In addition, a redundant content deletion algorithm overcomes the possible duplications generated from the problem transformation by checking the redundancy in the order of the response factors of different replicas. Experiments show that the DSS scheme achieves a high access ratio and keeps a short access delay with a small cost of network resources.

    参考文献
    相似文献
    引证文献
引用本文

唐晓岚,洪东惠,陈文龙,蒲菊华.基于二部图匹配的车载网络分布式存储机制.软件学报,2016,27(9):2377-2388

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2015-11-16
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2016-09-02
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号