基于二部图匹配的车载网络分布式存储机制

Distributed Storage Scheme Using Bipartite Graph Matching for Vehicular Networks

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

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 bytransforming 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.