Optimal Dropbox Deployment Algorithm for Data Dissemination in Vehicular Networks
Optimal Dropbox Deployment Algorithm for Data Dissemination in Vehicular Networks
复制标题
DOI：
10.1109/tmc.2017.2733534
复制
发表时间：
2018-03
影响因子：
7.9
通讯作者：
Jianping He;Yuanzhi Ni;Lin X. Cai;Jianping Pan;Cailian Chen
中科院分区：
文献类型：
--
作者：
Jianping He;Yuanzhi Ni;Lin X. Cai;Jianping Pan;Cailian Chen
对于车载网络，Dropbox对于辅助数据传播非常有用，因为它们可以极大地增加车辆之间的接触概率，减少数据传输延迟。然而，由于Dropbox的部署成本高昂，以密集的方式部署Dropbox是不切实际的。在本文中，我们研究了如何在交付延迟和Dropbox部署成本之间进行权衡，从而实现Dropbox的最优部署。由于精确估计时延的难度和优化问题的复杂性，这是一个非常具有挑战性的问题。为了解决这个问题，我们首先提供了一个准确估计交付延迟的理论框架。然后，基于扩维和动态规划的思想，设计了一种新的最优Dropbox部署算法(ODDA)来获得最优的部署策略。证明了ODDA算法具有较快的收敛速度，收敛所需的迭代次数少于$kappa$($kappa)。我们还证明了Odda的计算复杂性为$O(nkappa m；logm)$，即对于给定的用于部署的Dropbox的数目$m$，Odda具有多项式的计算复杂性。仿真结果表明，与基准方法相比，所提出的策略具有更好的性能。
For vehicular networks, dropboxes are very useful for assisting the data dissemination, as they can greatly increase the contact probabilities between vehicles and reduce the data delivery delay. However, due to the costly deployment of dropboxes, it is impractical to deploy dropboxes in a dense manner. In this paper, we investigate how to deploy the dropboxes optimally by considering the tradeoff between the delivery delay and the cost of dropbox deployment. This is a very challenging issue due to the difficulty of accurate delay estimation and the complexity of solving the optimization problem. To address this issue, we first provide a theoretical framework to estimate the delivery delay accurately. Then, based on the idea of dimension enlargement and dynamic programming, we design a novel optimal dropbox deployment algorithm (ODDA) to obtain the optimal deployment strategy. We prove that ODDA has a fast convergence speed, which is less than $\kappa$ ( $\kappa ) iterations for convergence. We also prove that the computational complexity of ODDA is $O(n \kappa m \;\log m)$ , i.e., ODDA has a polynomial computational complexity for a given $m$ , the number of dropboxes for deployment. Performance evaluation by simulation demonstrates the superior performance of the proposed strategies compared with the benchmark methods.