| 摘要: |
| 无线信号之间的干扰阻碍了信号的并发传输, 降低了无线网络的吞吐量. 链路调度是提高无线网络吞吐量、减少信号传输延迟的一种有效方法. 因为SINR (signal to interference plus noise ratio)模型准确地描述了无线信号传播的固有特性, 能够真实反映无线信号之间的干扰, 提出一种在动态无线网络中基于SINR模型的常数近似因子的在线分布式链路调度算法(OLD_LS). 在线的意思是指, 在算法执行的过程中任意节点可以随时加入网络, 也可以随时离开网络. 节点任意加入网络或者从网络中离开体现了无线网络的动态变化的特性. OLD_LS算法把网络区域划分为多个正六边形, 局部化SINR模型的全局干扰. 设计动态网络下的领导者选举算法(LE), 只要网络节点的动态变化速率小于${1 \mathord{\left/ {\vphantom {1 \varepsilon }} \right. } \varepsilon }$, LE就可以在${\rm{O}}(\log n + \log R)$时间复杂度内以高概率选举出领导者. 其中, 常数$\varepsilon $满足$\varepsilon \leqslant {{5(1 - {2^{1 - {\alpha/ 2}}})} /6}$, $\alpha $表示路径损耗指数, n是网络节点的规模, R是最长链路的长度. 根据文献调研, 所提算法是第1个用于动态无线网络的在线分布式链路调度算法. |
| 关键词: 无线动态网络 信号与干扰加噪声比SINR 链路调度 分布式算法 领导者选举 |
| DOI：10.13328/j.cnki.jos.006634 |
| 分类号: |
| 基金项目:国家自然科学基金(61672321, 61832012, 61771289, 61373027); 山东省重点基础研究计划(ZR201906140028) |
|
| Distributed Link Scheduling in Dynamic Wireless Networks under SINR Model |
|
HUANG Bao-Gui1, YU Ji-Guo2,3, MA Chun-Mei1
|
|
1.School of Computer Science, Qufu Normal University, Rizhao 276826, China;2.Big Data Institute, Qilu University of Technology, Jinan 250353, China;3.Shandong Provincial Key Laboratory of Computer Networks, Jinan 250014, China
|
| Abstract: |
| Interference among wireless signals hinders the concurrent transmission of signals and reduces the throughput of wireless networks. Link scheduling is an effective way to improve throughput and decrease transmission delay of wireless networks as the signal-to-interference-plus-noise ratio (SINR) model can accurately describe the inherent characteristics of wireless signal propagation and truly reflect the interference among wireless signals. Therefore, this study proposes an online distributed link scheduling (OLD_LS) algorithm in the dynamic wireless networks with the constant approximation factor of the SINR model. Specifically, online means that nodes can join and leave wireless networks at any time, and this arbitrary behavior of nodes reflects the dynamic characteristics of wireless networks. The OLD_LS algorithm partitions the network region into hexagons to localize the global interference of the SINR model. In addition, a leader election (LE) subroutine in dynamic networks is designed in this study. It is shown that as long as the dynamic rate of nodes is less than 1/ε, LE can elect a leader with a high probability in the time complexity of ${\rm{O}}(\log n + \log R)$, where ε is a constant satisfying $\varepsilon \leqslant {{5(1 - {2^{1 - {\alpha/ 2}}})} /6}$, with $\alpha $ being the path loss exponent, n the number of senders, and R the longest link length. To the best of our knowledge, the algorithm proposed in this study is the first OLD_LS algorithm for dynamic wireless networks. |
| Key words: dynamic wireless networks signal to interference plus noise ratio (SINR) link scheduling distributed algorithm leader election |
