Trajectory Comparison in a Vehicular Network II: Eliminating the Redundancy
Trajectory Comparison in a Vehicular Network II: Eliminating the Redundancy
复制标题
DOI：
10.1007/978-3-030-23597-0_21
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
L. Qingge;Peng Zou;Lihui Dai;Qing Yang;B. Zhu
中科院分区：
文献类型：
--
作者：
L. Qingge;Peng Zou;Lihui Dai;Qing Yang;B. Zhu
研究了车载网络中两个节点（车辆）之间的真实性建立问题。我们更专注于没有进行交互的情况下，我们使用的两个节点（车辆）访问的兴趣点（POI），以建立初始的真实性。事实证明，这是计算基因组学中一个被广泛研究的问题的一般版本，称为CMSR（互补最大条带恢复），其中字母（类似于POI）不能被复制，而在我们的问题中，POI肯定可以被复制。我们表明，一个版本（当嘈杂的兴趣点被删除时，所有剩余的兴趣点必须参与一些邻接），是NP难的，而另一个版本（与邻接参与约束被丢弃），是硬集覆盖。然后，我们设计了一个实用的解决方案的基础上局部搜索的第一个问题。通过对多种模拟数据的仿真，表明了该算法的有效性.
This paper investigates the truthfulness establishment problem between two nodes (vehicles) in a vehicular network. We focus more on the case when no interaction has been conducted and we use the Point of Interests (POIs) visited by the two nodes (vehicles) to establish the initial truthfulness. It turns out that this is a general version of a well-studied problem in computational genomics called CMSR (Complementary Maximal Strip Recovery) in which the letters (similar to POIs) cannot be duplicated, while in our problem POIs could certainly be duplicated. We show that one version (when noisy POIs are deleted all the remaining POIs must be involved in some adjacency), is NP-hard; while the other version (with the adjacency involvement constraint is dropped), is as hard as Set Cover. We then design a practical solution based on local search for the first problem. Simulations with various synthetic data show that the algorithm is very effective.