无线网络中可靠的链路调度算法设计与分析

计算机与现代化 ›› 2020, Vol. 0 ›› Issue (12): 9-12.

无线网络中可靠的链路调度算法设计与分析

(曲阜师范大学信息科学与工程学院，山东日照276800)

出版日期:2021-01-07 发布日期:2021-01-07
作者简介:张鑫(1998—)，男，甘肃临洮人，本科生，研究方向：无线网络通信，软件开发，E-mail: 3456106355@qq.com；张旭(1998—)，女，本科生，研究方向：无线通信,E-mail: 1440984747@qq.com；张入文（2000—），女，本科生，研究方向：软件开发,E-mail: 1356572472@qq.com；于琪琦(2000—),女，本科生，研究方向：无线网络中可靠的链路调度，E-mail: 2806080467@qq.com；王玉霞(2000—)，女，本科生，研究方向：数据结构与算法，E-mail: 938586696@qq.com；韦迎新(2000—)，女，本科生，研究方向：无线网络通信，E-mail: 2827812643@qq.com；黄宝贵(1977—)，男，讲师，硕士，研究方向：无线网络算法设计与分析，分布式计算，物联网，E-mail: hjbaogui@163.com。
基金资助:
国家自然科学基金面上项目（F020104）; 高等学校科技计划项目（J15LN05）; 曲阜师范大学大学生创新创业训练计划项目（2019A050）

Design and Analysis of Reliable Link Scheduling Algorithm in Wireless Network

(School of Information Science and Engineering, Qufu Normal University, Rizhao 276800, China)

Online:2021-01-07 Published:2021-01-07

摘要/Abstract

摘要： 无线信号在传输过程中存在许多不确定性的干扰，导致信号到达接收端时其质量严重下降，接收端不能正确解码接收到的信号，使无线通信出现差错。目前，基于SINR（Signal to Interference plus Noise Ratio）干扰模型的低延迟链路调度算法是提高无线网络可靠性和通信容量的有效方法。基于此本文提出一种近似比为O(log Δ)的最短链路调度算法（Δ是最长链路长度与最短链路长度的比值），所有链路采用一致功率分配，根据链路长度把链路集划分为不同的子集，运用TDMA运行机制，为每个子集中相互干扰的链路分配不同的传输时隙，使每个时隙中的链路同时通信。通过理论证明了本文算法的正确性和有效性。

关键词: SINR, 链路调度, 可靠通信

Abstract: There is much uncertain interference in the wireless signal transmission process, which causes the quality of the signal to seriously degrade when it reaches the receiver. The receiver cannot correctly decode the received signal and communication error occurs. At present, low-latency link scheduling algorithms based on the SINR (Signal to Interference plus Noise Ratio) interference model are effective methods to improve the reliability and communication capacity of the wireless network. In this paper, a shortest link scheduling algorithm with an approximate ratio of O(log Δ) is proposed (Δ is the ratio of the longest link length to the shortest link length). All links adopt the uniform power assignment. First, the link set is divided into subsets according to the link length. Then, using TDMA operation mechanism, the interfering links in each subset is assigned different transmission time slots so that the links in each time slot can communicate simultaneously. The theory proves the correctness and effectiveness of the algorithm in this paper.

Key words: SINR, link scheduling, reliable communication

张鑫, 张旭, 张入文, 于琪琦, 王玉霞, 韦迎新, 黄宝贵. 无线网络中可靠的链路调度算法设计与分析[J]. 计算机与现代化, 2020, 0(12): 9-12.

ZHANG Xin, ZHANG Xu, ZHANG Ru-wen, YU Qi-qi, WANG Yu-xia, WEI Ying-xin, HUANG Bao-gui. Design and Analysis of Reliable Link Scheduling Algorithm in Wireless Network[J]. Computer and Modernization, 2020, 0(12): 9-12.

参考文献［23］

［1］	LE T T T, MOH S. A spectrum-aware priority-based link scheduling algorithm for cognitive radio body area networks［J］. Sensors, 2019,19(7):1640:1-21.
［2］	NA W, LEE Y, DAO N N, et al. Directional link scheduling for real-time data processing in smart manufacturing system［J］. IEEE Internet of Things Journal, 2018,5(5):3661-3671.
［3］	YU D X, ZOU Y F, ZHANG Y, et al. Distributed dominating set and connected dominating set construction under the dynamic SINR model［C］// 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2019:835-844.
［4］	HALLDRSSON M M, HOLZER S, MARKATOU E A, et al. Leader election in SINR model with arbitrary power control［J］. Theoretical Computer Science, 2020,811:21-28.
［5］	HU M S, CHANG Y Y, ZENG T Y, et al. SINR loss and user selection in massive MU-MISO systems with ZFBF［J］. ETRI Journal, 2019,41(5):637-647.
［6］	BOLHASANI M, MEHRSHAHI E, GHORASHI S A, et al. Constant envelope waveform design to increase range resolution and SINR in correlated MIMO radar［J］. Signal Processing, 2019,163:59-65.
［7］	GHIASIAN A, OMOOMI B, SAIDI H. Complexity reduction of throughput optimal link scheduling algorithm through topology control in wireless networks［J］. International Journal of Ad Hoc and Ubiquitous Computing, 2018,27(1):69-79.
［8］	WANG Y, XIA Y. I-CSMA: A link-scheduling algorithm for wireless networks based on Ising model［J］. IEEE Transactions on Control of Network Systems, 2018,5(3):1038-1050.
［9］	POCOVI G, PEDERSEN K I, MOGENSEN P. Joint link adaptation and scheduling for 5G ultra-reliable low-latency communications［J］. IEEE Access, 2018,6:28912-28922.〖HJ1.55mm〗
［10］	GE M Y, BLOUGH D M. Mobility-aware multi-user MIMO link scheduling for dense wireless networks［C］// 2018 IEEE International Conference on Communications (ICC). IEEE, 2018:DOI:10.1109/ICC.2018.8422380.
［11］	LEONG A S, QUEVEDO D E, DOLZ D, et al. Transmission scheduling for remote state estimation over packet dropping links in the presence of an eavesdropper［J］. IEEE Transactions on Automatic Control, 2019,64(9):3732-3739.
［12］	WU J H, LIN D D, LI G S, et al. Distributed link scheduling algorithm based on successive interference cancellation in MIMO wireless networks［J］. Wireless Communications and Mobile Computing, 2019:DOI:10.1155/2019/9083282.
［13］	王颖,熊文成,李文璟. 基于最大独立链路集的随机虚拟网络映射算法［J］. 北京邮电大学学报, 2014,37(s1):8-11.
［14］	WANG C, YU J G, YU D X, et al. An improved approximation algorithm for the shortest link scheduling problem in wireless networks under SINR and hypergraph models［C］// International Conference on Wireless Algorithms, Systems, and Applications (WASA). 2014:150-160.
［15］	HUANG B G, YU J G, YU D X, et al. SINR based maximum link scheduling with uniform power in wireless sensor networks［J］. KSII Transactions on Internet & Information Systems, 2014,8(11):4050-4067.
［16］	HUANG B G, YU J G, CHENG X Z, et al. SINR based shortest link scheduling with oblivious power control in wireless networks［J］. Journal of Network and Computer Applications, 2017,77:64-72.
［17］	SAAD M, ABDALLAH S. On millimeter wave 5G backhaul link scheduling［J］. IEEE Access, 2019,7:76448-76457.
［18］	BORBASH S A, EPHREMIDES A. Wireless link scheduling with power control and SINR constraints［J］. IEEE Transactions on Information Theory, 2006,52(11):5106-5111.
［19］	WANG Y S, CHIN K W, SOH S. Link scheduling in wireless networks with RF energy harvesting nodes［J］. IEEE Transactions on Green Communications & Networking, 2019,3(2):302-316.
［20］	YU J G, HUANG B G, CHENG X Z, et al. Shortest link scheduling algorithms in wireless networks under the SINR model［J］. IEEE Transactions on Vehicular Technology, 2017,66(3):2643-2657.
［21］	马春梅,黄宝贵,张秀娟. 基于SINR干扰模型的低延迟链路调度［J］. 电子技术, 2016,45(8):90-92.
［22］	BLOUGH D M, RESTA G, SANTI P. Approximation algorithms for wireless link scheduling with SINR-based interference［J］. IEEE/ACM Transactions on Networking, 2010,18(6):1701-1712.
［23］	RICARDO G I, DE REZENDE J F, BARBOSA V C. Scheduling wireless links in the physical interference model by fractional edge coloring［J］. IEEE Wireless Communications Letters, 2020,9(4):528-532.