摘要:无线信号之间的干扰阻碍了信号的并发传输,降低了无线网络的吞吐量.链路调度是提高无线网络吞吐量、减少信号传输延迟的一种有效方法.因为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是最长链路的长度.据我们所知,本文提出的算法是第一个用于动态无线网络的在线分布式链路调度算法.