Computational Method Using Quantum Annealing for TDMA Scheduling Problem in Wireless Sensor Networks
Computational Method Using Quantum Annealing for TDMA Scheduling Problem in Wireless Sensor Networks
复制标题
无线传感器网络中 TDMA 调度问题的量子退火计算方法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
F. Ishizaki
中科院分区：
文献类型：
--
作者：
F. Ishizaki
在本文中，我们考虑一个无线传感器网络的网络拓扑结构是一个树和媒体访问控制是TDMA。本文主要研究文献[1]中研究的TDMA调度问题。由于排序问题被认为是NP难问题，因此很难得到排序问题的最优解。为了克服这个困难，我们开发了一种计算方法，使用量子退火，以找到接近最佳的解决方案，在TDMA调度问题。我们提供了一些数值结果比较的计算方法，使用量子退火与其他方法的解决方案的质量，计算时间和规模的问题。
In this paper, we consider a wireless sensor network where the network topology is a tree and medium access control is TDMA. We focus on TDMA scheduling problem studied in [1]. Since scheduling problems are considered as a member in the class of NP-hard, it is difficult to obtain the optimal solution in the scheduling problem. To overcome the difficulty, we develop a computational method using quantum annealing in order to find near-optimal solutions in the TDMA scheduling problem. We provide some numerical results to compare the computational method using quantum annealing with other methods in terms of quality of solution, computation time and size of problem.