一种基于二部图的车载网络分布式存储方法

摘要

本发明公开了一种基于二部图的车载网络分布式存储方法，该方法首先对分布式存储问题进行建模，利用二部图匹配，实现了每个车载节点发送的车载请求标识信息在不相同的条件下、最优的车载网络分布式存储方法，保证了车载网络能够响应最多车载请求标识信息；然后对路边单元存储的重复网络信息进行清理，避免了多个路边单元响应同一车载请求标识信息带来的资源浪费，同时不影响已经满足的车载请求标识信息；最后收集尚未满足的车载请求标识信息，对于清理路边单元获得的空余存储空间，进行二次分配，直到每个路边单元没有空余存储空间，或者该路边单元收到的全部车载请求标识信息都已响应，或者剩下的车载请求标识信息已无法满足。本发明方法提升了存储资源利用率和数据响应率，保证了车载网络的数据服务质量。

主权项

一种基于二部图的车载网络分布式存储方法，任意一所述车载网络中包括有多个路边单元、多个车载节点和一个信息中心IC；车载节点与路边单元的通信为V2I，车载节点之间的通信为V2V，信息中心IC与路边单元的通信为Internet网络；路边单元采用集合形式表达为RD＝{R¹,R²,…,R^r}；R¹表示第一个路边单元，R²表示第二个路边单元，R^r表示最后一个路边单元；车载节点采用集合形式表达为VD＝{V¹,V²,…,Vⁿ}；V¹表示第一个车载节点，V²表示第二个车载节点，Vⁿ表示最后一个车载节点；网络信息采用集合形式表达为第一个网络信息记为Rf¹(content₁,1)，content₁表示数字标识号为1的车载网络信息内容，1表示第一个车载网络信息内容对应的数字标识号；第二个网络信息记为Rf²(content₂,2)，content₂表示数字标识号为2的车载网络信息内容，2表示第二个车载网络信息内容对应的数字标识号；第三个网络信息记为Rf³(content₃,3)，content₃表示数字标识号为3的车载网络信息内容，3表示第三个车载网络信息内容对应的数字标识号；第四个网络信息记为Rf⁴(content₄,4)，content₄表示数字标识号为4的车载网络信息内容，4表示第四个车载网络信息内容对应的数字标识号；第五个网络信息记为Rf⁵(content₅,5)，content₅表示数字标识号为5的车载网络信息内容，5表示第五个车载网络信息内容对应的数字标识号；第Z‑1个网络信息记为Rf^Z‑1(content_Z‑1,Z‑1)，content_Z‑1表示数字标识号为Z‑1的车载网络信息内容，Z‑1表示第Z‑1个车载网络信息内容对应的数字标识号；最后一个网络信息记为Rf^Z(content_Z,Z)，content_Z表示数字标识号为Z的车载网络信息内容，Z表示最后一个车载网络信息内容对应的数字标识号；其特征在于信息中心IC对网络信息的分布式存储包括有下列步骤：步骤一：构造二部图步骤11：设置一个空的二部图记为G＝(X,Y,E)，X表示左边顶点，Y表示右边顶点，E表示边；执行步骤12；步骤12：将当前存储周期τ中信息中心IC采集到的中的元素加入到空的二部图G＝(X,Y,E)的X中，得到具有左顶点的二部图G^X，执行步骤13；所述车载请求标识信息是指F^τ中被第一个车载节点V¹请求到的车载网络信息内容content对应的数字标识号ID；所述车载请求标识信息是指F^τ中被第二个车载节点V²请求到的车载网络信息内容content对应的数字标识号ID；所述车载请求标识信息是指F^τ中被最后一个车载节点Vⁿ请求到的车载网络信息内容content对应的数字标识号ID；所述具有左顶点的二部图G^X的左顶点中包含的元素为X＝{a₁,a₂,a₃,a₄,a₅,a₆,a₇,…,a_i‑1,a_i}，其中：a₁表示第一个左顶点，a₁记录的内容是中包含的数字标识号1；a₂表示第二个左顶点，a₂记录的内容是中包含的数字标识号2；a₃表示第三个左顶点，a₃记录的内容是中包含的数字标识号1；a₄表示第四个左顶点，a₄记录的内容是中包含的数字标识号3；a₅表示第五个左顶点，a₅记录的内容是中包含的数字标识号4；a₆表示第六个左顶点，a₆记录的内容是中包含的数字标识号5；a₇表示第七个左顶点，a₇记录的内容是中包含的数字标识号Z‑1；a_i‑1表示第i‑1个左顶点，a_i‑1记录的内容是中包含的数字标识号1；a_i表示最后一个左顶点，a_i记录的内容是中包含的数字标识号Z；步骤13：针对车载网络中任意一个路边单元R^r，构造一个大小为存储容量的存储位置集合，记为其中，表示R^r的第一个存储位置，表示R^r的第二个存储位置，表示R^r的最后一个存储位置，执行步骤14；步骤14：遍历所有RD＝{R¹,R²,…,R^r}中的路边单元，获得全网存储位置集合并将中的元素加入到具有左顶点的二部图G^X的Y中，得到具有左右顶点集的二部图G^X+Y，执行步骤15；所述具有左右顶点集的二部图G^X+Y的Y＝{b₁,b₂,b₃,b₄,b₅,b₆,b₇,b₈,…,b_j‑1,b_j}，其中：b₁表示第一个右顶点，b₁记录的内容是R¹的第一个存储位置b₂表示第二个右顶点，b₂记录的内容是R²的第一个存储位置b₃表示第三个右顶点，b₃记录的内容是R³的第一个存储位置b₄表示第四个右顶点，b₄记录的内容是R⁴的第一个存储位置b₅表示第五个右顶点，b₅记录的内容是R⁵的第一个存储位置b₆表示第六个右顶点，b₆记录的内容是R⁵的第二个存储位置b₇表示第七个右顶点，b₇记录的内容是R⁵的第三个存储位置b₈表示第八个右顶点，b₈记录的内容是R^r‑1的第一个存储位置b_j‑1表示第j‑1个右顶点，b_j‑1记录的内容是R^r的第一个存储位置b_j表示最后一个右顶点，b_j记录的内容是R^r的第二个存储位置步骤15：以顶点匹配条件且且来判断所述具有左右顶点集的二部图G^X+Y中的X与Y是否连边，从而构建得到具有顶点和边的二部图执行步骤21；为车载节点Vⁿ在下一个存储周期τ+1将要遇到的路边单元集合；a₁与b₂满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₁,b₂>；a₂与b₃满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₂,b₃>；a₂与b₄满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₂,b₄>；a₃与b₅满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₃,b₅>；a₃与b₆满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₃,b₆>；a₃与b₇满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₃,b₇>；a₄与b₅满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₄,b₅>；a₄与b₆满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₄,b₆>；a₄与b₇满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₄,b₇>；a₅与b₈满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₅,b₈>；a₅与b_j‑1满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₅,b_j‑1>；a₅与b_j满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₅,b_j>；a₆与b₅满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₆,b₅>；a₆与b₆满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₆,b₆>；a₆与b₇满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₆,b₇>；a₇与b₅满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₇,b₅>；a₇与b₆满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₇,b₆>；a₇与b₇满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₇,b₇>；a₇与b_j‑1满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₇,b_j‑1>；a₇与b_j满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a₇,b_j>；a_i‑1与b₅满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i‑1,b₅>；a_i‑1与b₆满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i‑1,b₆>；a_i‑1与b₇满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i‑1,b₇>；a_i‑1与b_j‑₁满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i‑1,b_j‑1>；a_i‑1与b_j满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i‑1,b_j>；a_i与b₅满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i,b₅>；a_i与b₆满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i,b₆>；a_i与b₇满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i,b₇>；a_i与b_j‑1满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i,b_j‑1>；a_i与b_j满足顶点匹配条件且且则在G^X+Y的边集E中添加边<a_i,b_j>；统计边集E中的边包括有<a₁,b₂>、<a₂,b₃>、<a₂,b₄>、<a₃,b₅>、<a₃,b₆>、<a₃,b₇>、<a₄,b₅>、<a₄,b₆>、<a₄,b₇>、<a₅,b₈>、<a₅,b_j‑1>、<a₅,b_j>、<a₆,b₅>、<a₆,b₆>、<a₆,b₇>、<a₇,b₅>、<a₇,b₆>、<a₇,b₇>、<a₇,b_j‑1>、<a₇,b_j>、<a_i‑1,b₅>、<a_i‑1,b₆>、<a_i‑1,b₇>、<a_i‑1,b_j‑1>、<a_i‑1,b_j>、<a_i,b₅>、<a_i,b₆>、<a_i,b₇>、<a_i,b_j‑1>和<a_i,b_j>；步骤二：求出二部图最大匹配子图步骤21：若具有顶点和边的二部图的边集E不为空，则执行步骤22；若具有顶点和边的二部图的边集E为空，则结束分布式存储，且输出车载分配结果DI；步骤22：应用匈牙利算法从具有顶点和边的二部图中得到最大匹配子图GB＝<(X,Y),EB>，其中EB是具有顶点和边的二部图的边集E的子集，简称为边子集；EB＝{<γ,β>|γ∈X,β∈Y}，其中γ表示最大匹配子图GB＝<(X,Y),EB>边集EB中的任意一个边的左顶点，β表示最大匹配子图GB＝<(X,Y),EB>边集EB中的任意一个边的右顶点；执行步骤31；边子集EB中的边包括有<a₁,b₂>、<a₂,b₃>、<a₃,b₅>、<a₄,b₆>、<a₅,b₈>、<a₆,b₇>、<a₇,b_j‑1>和<a_i‑1,b_j>；则γ包括有边<a₁,b₂>中的a₁、边<a₂,b₃>中的a₂、边<a₃,b₅>中的a₃、边<a₄,b₆>中的a₄、边<a₅,b₈>中的a₅、边<a₆,b₇>中的a₆、边<a₇,b_j‑1>中的a₇和边<a_i‑1,b_j>中的a_i‑1；则β包括有边<a₁,b₂>中的b₂、边<a₂,b₃>中的b₃、边<a₃,b₅>中的b₅、边<a₄,b₆>中的b₆、边<a₅,b₈>中的b₈、边<a₆,b₇>中的b₇、边<a₇,b_j‑1>中的b_j‑1和边<a_i‑1,b_j>中的b_j；步骤三：分配、清理网络信息步骤31：完成网络信息分配后，获得车载分配结果为执行步骤32；将边<a₁,b₂>中的第一个左顶点a₁所对应的Rf¹分配到第二个右顶点b₂对应的R²中；将边<a₂,b₃>中的第二个左顶点a₂所对应的Rf²分配到第三个右顶点b₃对应的R³中；将边<a₃,b₅>中的第三个左顶点a₃所对应的Rf¹分配到第五个右顶点b₅对应的R⁵中；将边<a₄,b₆>中的第四个左顶点a₄所对应的Rf³分配到第六个右顶点b₆对应的R⁵中；将边<a₅,b₈>中的第五个左顶点a₅所对应的Rf⁴分配到第八个右顶点b₈对应的R^r‑1中；将边<a₆,b₇>中的第六个左顶点a₆所对应的Rf⁵分配到第七个右顶点b₇对应的R⁵中；将边<a₇,b_j‑1>中的第七个左顶点a₇所对应的Rf^Z‑1分配到第j‑1个右顶点b_j‑1对应的R^r中；将边<a_i‑1,b_j>中的第i‑1个左顶点a_i‑1所对应的Rf¹分配到第j个右顶点b_j对应的R^r中；分配了第一个网络信息Rf¹的路边单元有第二个路边单元R²、第五个路边单元R⁵、第r个路边单元R^r，简称为第一车载分配结果分配了第二个网络信息Rf²的路边单元有第三个路边单元R³，简称为第二车载分配结果分配了第三个网络信息Rf³的路边单元有第五个路边单元R⁵，简称为第三车载分配结果分配了第四个网络信息Rf⁴的路边单元有第r‑1个路边单元R^r‑1，简称为第四车载分配结果分配了第五个网络信息Rf⁵的路边单元有第五个路边单元R⁵，简称为第五车载分配结果分配了第Z‑1个网络信息Rf^Z‑1的路边单元有第r个路边单元R^r，简称为第Z‑1车载分配结果分配了第Z个网络信息Rf^Z的路边单元不存在，简称为第Z车载分配结果采用集合形式表达车载分配结果为步骤32：逐个判断和中的路边单元个数是否大于1；若路边单元个数大于1，即则执行步骤33；若路边单元个数小于等于1，即和则放弃对路边单元分配到的网络信息的清理；具体地，则信息中心IC放弃对R³分配到的Rf²的清理；则信息中心IC放弃对R⁵分配到的Rf³的清理；则信息中心IC放弃对R^r‑1分配到的Rf⁴的清理；则信息中心IC放弃对R⁵分配到的Rf⁵的清理；则信息中心IC放弃对R^r分配到的Rf^Z‑1的清理；说明没有路边单元分配到Rf^Z，故不进行清理；步骤33：对于在当前存储周期τ内请求了第一个网络信息Rf¹，并在下一个存储周期τ+1内将要遇到第二个路边单元R²的车载节点有第一个车载节点V¹，简称为R²－Rf¹－车载节点即在当前存储周期τ内请求了第一个网络信息Rf¹，并在下一个存储周期τ+1内将要遇到第五个路边单元R⁵的车载节点有第三个车载节点V³、第n个车载节点Vⁿ，简称为R⁵－Rf¹－车载节点即在当前存储周期τ内请求了第一个网络信息Rf¹，并在下一个存储周期τ+1内将要遇到第r个路边单元R^r的车载节点有第n个车载节点Vⁿ，简称为R^r－Rf¹－车载节点即依据和中元素个数降序排列，得到路边单元的处理次序依次为第五个路边单元R⁵、第二个路边单元R²、第r个路边单元R^r；对排序后位于首位的第五个路边单元R⁵执行步骤34，位于首位之后的第二个路边单元R²和第r个路边单元R^r分别依次执行步骤35；步骤34：保留第五个路边单元R⁵分配到的第一个网络信息Rf¹，并记录第一车载中间分配结果然后执行步骤35；步骤35：对于第二个路边单元R²，针对中的第一个车载节点V¹，判断是否为空集，若为空集，则保留第二个路边单元R²分配到的第一个网络信息Rf¹，并对第一车载中间分配结果重新赋值否则，清理第二个路边单元R²分配到的第一个网络信息Rf¹；由于所以保留第二个路边单元R²分配到的第一个网络信息Rf¹，并对第一车载中间分配结果重新赋值对于第r个路边单元R^r，针对中的第n个车载节点Vⁿ，判断是否为空集，若为空集，则保留第r个路边单元R^r分配到的第一个网络信息Rf¹，并对第一车载中间分配结果重新赋值否则，清理第r个路边单元R^r分配到的第一个网络信息Rf¹；由于所以清理第r个路边单元R^r分配到的第一个网络信息Rf¹；完成清理路边单元分配到的网络信息后，执行步骤36；步骤36：将第一车载中间分配结果赋值给第一车载分配结果即对路边单元个数大于1的全部执行完步骤33到36后的所有，执行步骤41；步骤四：二次分配、更新二部图顶点集步骤41：去除车载请求标识信息中与连边的左顶点相关的数字标识号，即：中包含的数字标识号1；中包含的数字标识号2；中包含的数字标识号1；中包含的数字标识号3；中包含的数字标识号4；中包含的数字标识号5；中包含的数字标识号Z‑1；中包含的数字标识号1；得到二次分配的车载请求标识信息其中步骤42：将二次分配的车载请求标识信息中的元素Z加入空的二部图的左顶点的标识为a_i，其中，a_i记录的内容是中数字标识号Z；执行步骤43；步骤43：已经分配有网络信息的存储位置有去除全网存储位置集合中已经分配有网络信息的存储位置，得到二次分配的全网存储位置集合其中执行步骤44；步骤44：将二次分配的全网存储位置集合中的元素加入二部图的右顶点的标识号有b₁,b₄,b_j，其中，b₁记录的内容是R¹的第一个存储位置b₄记录的内容是R⁴的第一个存储位置b_j记录的内容是R^r的第二个存储位置执行步骤15。