Complexity and Algorithms for Superposed Data Uploading Problem in Networks With Smart Devices
Complexity and Algorithms for Superposed Data Uploading Problem in Networks With Smart Devices
复制标题
智能设备网络中叠加数据上传问题的复杂性和算法
DOI：
10.1109/jiot.2019.2949352
复制
发表时间：
2020-07-01
影响因子：
10.6
通讯作者：
Singh, Saurabh
中科院分区：
文献类型：
--
作者：
Li, Wenjun;Xu, Huayi;Singh, Saurabh
作为边缘计算在工业生产环境中的成功应用，延长智能设备（sd）电池寿命已成为一个重要问题。在一些特殊的实际应用中，从数据存储单元上传到车载基站或服务器的数据可以在固定大小的数据存储单元之间进行合并，称为叠加数据。在本文中，我们考虑了分散设备对设备通信系统中的重叠数据上传问题。问题的任务是最小化上传数据的总能耗。我们从图论的角度将其简化为一个组合优化问题。对于具有无限容量的vbs或服务器，我们提出了一个运行时间为多项式的最优算法。当vbs或服务器的容量有限时，即使在非常特殊的情况下，问题也是np困难的。针对这一NP-hard问题，给出了两种启发式算法并给出了相应的数值模拟结果。
As a successful application of edge computing in the industrial production environment, prolonging the smart devices' (SDs') battery lifetime has become an important issue. In some special practical applications, the uploaded data from SDs to vehicle base stations (VBSs) or servers can be merged between SDs with a fixed size, which is called superposed data. In this article, we consider the superposed data uploading problem in a decentralized device-to-device communication system. The task of the problem is to minimize the total energy consumption of uploading data. We reduce it into a combinatorial optimization problem from the graph theory perspective. For VBSs or servers with infinite capacities, we propose an optimal algorithm with polynomial running time. When VBSs or servers have limited capacities, the problem is NP-hard even in very special cases. For this NP-hard problem, we give two heuristic algorithms and the corresponding numerical simulation results.