无线信号之间的干扰阻碍了信号的并发传输,降低了无线网络的吞吐量.链路调度是提高无线网络吞吐量、减少信号传输延迟的一种有效方法.因为SINR(Signal to Interference plus Noise Ratio)模型准确地描述了无线信号传播的固有特性,能够真实反映无线信号之间的干扰,本文提出了一种在动态无线网络中基于SINR模型的常数近似因子的在线分布式链路调度算法(简称OLD_LS).在线的意思是指,在算法执行的过程中任意节点可以随时加入网络,也可以随时离开网络.节点任意加入网络或者从网络中离开体现了无线网络的动态变化的特性.OLD_LS算法把网络区域划分为多个正六边形,局部化SINR模型的全局干扰.本文设计了动态网络下的领导者选举算法(简称LE),只要网络节点的动态变化速率小于1/ε,LE就可以在O(logn+logR)时间复杂度内以高概率选举出领导者.其中, 常数ε满足ε≤5(1-21-α/2)/6,α表示路径损耗指数,n是网络节点的规模,R是最长链路的长度.据我们所知,本文提出的算法是第一个用于动态无线网络的在线分布式链路调度算法.
Interferences among wireless signals hinder concurrent transmissions such that the throughput of wireless networks decreases. It is well known that link scheduling is an effective way to improve throughput and decrease transmission delay of wireless networks. SINR (Signal to Interference plus Noise Ratio) model accurately describes the inherent characteristics of wireless signal propagation. Therefore, in this paper, an online distributed link scheduling (OLD_LS) algorithm with a constant approximation factor under the SINR model is proposed. Here, online means that nodes can join in and leave from wireless networks. Nodes joining in or leaving from networks arbitrarily reflects the dynamic characteristics of wireless networks. OLD_LS partitions the network region into hexagons and localizes the SINR model, which is a global interference model. A leader election (LE) subroutine in dynamic networks is proposed in this paper. It is shown that if the dynamic rate of nodes is less than 1/ε, LE elects a leader with a high probability and the time complexity is O(logn+logR). Where,ε is a constant and satisfies ε≤5(1-21-α/2)/6, with α being the path loss exponent, n is the number of senders and R is the longest link length. To the best of our knowledge, the algorithm proposed in this paper is the first online distributed link scheduling algorithm for dynamic wireless networks.