基于SINR的动态无线网络分布式链路调度.pdf

基于 SINR 的动态无线网络分布式链路调度*黄宝贵1,禹继国2,3,马春梅11(曲阜师范大学计算机学院,山东日照276826)2(齐鲁工业大学大数据研究院,山东济南250353)3(山东省计算机网络重点实验室,山东济南250014)通信作者:禹继国,E-mail:1/O(logn+logR)5(121/2)/6摘要:无线信号之间的干扰阻碍了信号的并发传输,降低了无线网络的吞吐量.链路调度是提高无线网络吞吐量、减少信号传输延迟的一种有效方法.因为 SINR(signaltointerferenceplusnoiseratio)模型准确地描述了无线信号传播的固有特性,能够真实反映无线信号之间的干扰,提出一种在动态无线网络中基于 SINR 模型的常数近似因子的在线分布式链路调度算法(OLD_LS).在线的意思是指,在算法执行的过程中任意节点可以随时加入网络,也可以随时离开网络.节点任意加入网络或者从网络中离开体现了无线网络的动态变化的特性.OLD_LS 算法把网络区域划分为多个正六边形,局部化 SINR 模型的全局干扰.设计动态网络下的领导者选举算法(LE),只要网络节点的动态变化速率小于,LE 就可以在时间复杂度内以高概率选举出领导者.其中,常数满足,表示路径损耗指数,n 是网络节点的规模,R 是最长链路的长度.根据文献调研,所提算法是第 1 个用于动态无线网络的在线分布式链路调度算法.关键词:无线动态网络;信号与干扰加噪声比 SINR;链路调度;分布式算法;领导者选举中图法分类号:TP393中文引用格式:黄宝贵,禹继国,马春梅.基于SINR的动态无线网络分布式链路调度.软件学报,2023,34(9):42254238.http:/ Link Scheduling in Dynamic Wireless Networks under SINR ModelHUANGBao-Gui1,YUJi-Guo2,3,MAChun-Mei11(SchoolofComputerScience,QufuNormalUniversity,Rizhao276826,China)2(BigDataInstitute,QiluUniversityofTechnology,Jinan250353,China)3(ShandongProvincialKeyLaboratoryofComputerNetworks,Jinan250014,China)Abstract:Interference among wireless signals hinders the concurrent transmission of signals and reduces the throughput of wirelessnetworks.Linkschedulingisaneffectivewaytoimprovethroughputanddecreasetransmissiondelayofwirelessnetworksasthesignal-to-interference-plus-noise ratio(SINR)model can accurately describe the inherent characteristics of wireless signal propagation and trulyreflecttheinterferenceamongwirelesssignals.Therefore,thisstudyproposesanonlinedistributedlinkscheduling(OLD_LS)algorithminthedynamicwirelessnetworkswiththeconstantapproximationfactoroftheSINRmodel.Specifically,onlinemeansthatnodescanjoinandleavewirelessnetworksatanytime,andthisarbitrarybehaviorofnodesreflectsthedynamiccharacteristicsofwirelessnetworks.TheOLD_LSalgorithmpartitionsthenetworkregionintohexagonstolocalizetheglobalinterferenceoftheSINRmodel.Inaddition,aleaderelection(LE)subroutineindynamicnetworksisdesignedinthisstudy.Itisshownthataslongasthedynamicrateofnodesislessthan*基金项目:国家自然科学基金(61672321,61832012,61771289,61373027);山东省重点基础研究计划(ZR201906140028)收稿时间:2020-11-05;修改时间:2021-06-01;采用时间:2021-12-13;jos 在线出版时间:2022-03-24CNKI 网络首发时间:2023-02-24软件学报ISSN1000-9825,CODENRUXUEWE-mail:Journal of Software,2023,34(9):42254238doi:10.13328/ki.jos.006634http:/中国科学院软件研究所版权所有.Tel:[phone]O(logn+logR)5(121/2)/61/,LE can elect a leader with a high probability in the time complexity of,where is a constant satisfying,with being the path loss exponent,n the number of senders,and R the longest link length.To the best of ourknowledge,thealgorithmproposedinthisstudyisthefirstOLD_LSalgorithmfordynamicwirelessnetworks.Key words:dynamic wireless networks;signal to interference plus noise ratio(SINR);link scheduling;distributed algorithm;leaderelection第 5 代(5G)通信系统为无线工业控制和自动化、无人驾驶等应用提供网络支持,这些应用都需要无线网络满足超可靠低延迟通信(ultra-reliablelow-latencycommunications,URLLC)的特点.对 URLLC 的严格要求催生出许多研究问题,包括 5G 系统的链路调度问题1,2.链路调度问题及其变种在提高网络性能方面起着至关重要的作用,例如提高网络吞吐量,延长网络的生命周期,提高信道的利用率等,是当前的研究热点之一312.链路调度主要包括两类子问题:最大链路调度(maximumlinkscheduling,MLS)3,4和最短链路调度(shortestlinkscheduling,SLS)5,6.其中,MLS 是指从一组链路集合中选择最大的子集,使这个子集中的所有链路可以同时通信.MLS 问题也称为单时隙调度问题7,8或极大(加权)独立链路集问题911.SLS 是指把一组链路集划分为最小数量的子集,每个子集中的链路可以同时通信,即用最短的时间调度所有链路.无线信号之间的相互干扰阻碍了共享信道中信号的同时传输,使链路调度问题变得异常困难.只有准确地建立无线信号的传播模型以及干扰模型才能使链路调度协议应用于实际网络环境.近年来,链路调度协议采用了许多干扰模型1319.其中,基于图的干扰模型具有二元性:两条通信链路之间要么存在干扰,要么不存在干扰.图干扰模型只考虑某个范围内的较强信号干扰,忽略范围之外的微弱信号的干扰.尽管基于图的干扰模型使链路调度算法更容易设计,但是它过于简单和理想化,无法正确描述无线通信的基本特征.事实上,许多微弱信号的累加干扰也是不容忽视的.近年来,物理干扰模型,也称为信号干扰加噪声比(signaltointerferenceplusnoiseratio,SINR)模型,在链路调度算法设计中得到广泛的应用.与基于图的干扰模型不同,SINR 模型考虑了全局干扰,任何微弱信号的干扰也不会忽略.正是这种干扰全局化的特点,使 SINR 模型下的链路调度算法设计成为一个极具挑战性的NP 难问题20,21.多包接收(multiplepacketreception,MPR)是消除干扰并显著提高无线网络吞吐量的一种有效方法22,23,相继干扰消除(successiveinterferencecancellation,SIC)是 MPR 缓解干扰的一项主要技术.SIC 利用干扰信号的结构特征解码多个信号,允许接收节点同时接收两个或更多信号,使用迭代方法解码接收到的信号.在每次迭代过程中解码功率水平最高的信号,将其余信号视为干扰.如果接收节点的 SINR 值不小于给定的阈值,则正确解码该信号并将其从复合信号中删除.然后再解码剩余信号中功率水平最高的信号.这个过程一直持续到需要的信号被成功解码,或某个信号解码失败为止.动态性是无线网络(如 AdHoc 网络)的重要内在本质特性,通信节点间歇性地加入网络执行任务、由于能量耗尽及故障而离开网络、从一个位置移动到另一个位置等,都导致无线网络拓扑发生变化.相应地,通信链路的集合也是动态变化的.然而,先前的工作都忽略了网络的动态性,因此这些算法无法适用于随时间变化的动态无线网络环境.在设计链路调度算法时,外部环境的变化不应该被忽略.此外,对于无线网络来说,通信请求可能随时到达.因此,设计在线链路调度算法处理这种动态通信请求成为亟待解决的问题.一种 SLS 构造方法是重复执行MLS 算法,在网络负载较大的情况下,SLS 算法的每个时隙调度的结果相当于 MLS.而且,由于网络中通信链路可能随时发生变化,链路集也相应地发生变化,所以在动态网络中研究 MLS 比 SLS 有更重要的意义.本文主要研究动态网络的 MLS 问题,主要贡献如下.uh1h2uh1h2(1)研究了动态无线网络中基于 SINR 干扰模型的吞吐量最大化问题,提出了常数近似因子的分布式最大链路调度算法.本文考虑了节点的扰动和移动性.扰动是指节点间歇性地加入网络或者离开网络;移动性是指节点从一个位置移动到另一个位置.针对上述两种情况,本文提出了一种新颖的方法,把这 3 种动态过程转化为一种情况.受蜂窝无线网络的启发,我们把网络区域划分为正六边形,使任意节点都位于某个确定的六边形中.当节点(例如)移动时,它从某个六边形(如)移动到另外一个六边形(如)中,可以认为离开加入.而本文提出的算法对节点的离开并不敏感,即节点的离开不影响算法的正确性.所以,本文仅考虑一种动态情形,即节点加入网络.4226软件学报2023 年第 34 卷第 9 期O(logn+logR)(2)设计了一个分布式领导者选举的概率算法,在轮内以高概率选举出领导者,而且该算法可以完全运行在动态无线网络中.其中,n 是网络中节点的规模,R 是最长链路的长度.分布式算法仅需要获取网络的局部信息,而集中式算法需要网络的全局信息.所以,对于大型无线网络来说,分布式链路调度算法比集中式算法更具竞争优势.我们在算法中引入了相继干扰消除技术,加速算法的执行过程.据我们所知,本文提出的算法是第一个用于动态无线网络的在线分布式链路调度算法.本文第 1 节中介绍相关工作.第 2 节中给出网络拓扑结构定义及假设.第 3 节介绍了一种新颖的领导者选举算法,并证明了算法的正确性.用领导者选举算法作为子程序,本文在第 4 节构造了最大链路调度算法.最后,第 5节总结全文并讨论了下一步的工作方向.1 相关工作O(log)O(log4n)O(log)O(log)O(n)O(lognloglog)2006 年 Moscibroda 等人开创性地提出了在 SINR 模型下进行链路调度问题的研究24,把网络区域划分为正方形,发送节点采用线性功率分配,提出了一种近似因子为的 SLS 算法.其中,是最长链路长度与最短链路长度之比.另外,文献 24 还提出了一种时间复杂度为的调度算法,调度任意无线网络中的一个强连通集.其中,n 是节点的数目.Goussevskaia 等人证明,在几何 SINR 干扰模型下 SLS 和 MLS 都是 NP 难问题20,继而为 SLS 和 MLS 提出了近似因子为的近似算法,把网络区域划分为正方形并进行 4 染色,发送节点采用一致功率分配,根据链路长度进行分类调度.虽然 SLS 算法可以通过多次调度 MLS 算法实现,但当调度一组静态链路集时其性能未必达到渐近最优.而且,文献 20 仅使用了简化的 SINR 模型,没有考虑环境噪声的影响,只考虑了其他链路的干扰.Blough 等人考虑了环境噪声的影响,并且按照信噪比的大小对链路进行分类,提出近似因子为的近似算法25.其中,是链路分类的数目.通信链路的长度影响该算法的性能,最坏情况下算法的近似比达到,n 是链路的数目.Halldrsson 结合功率控制,提出了基于 SINR 模型的近似因子为的 SLS 算法26,节点的发送功率仅与链路的长度相关,这种功率分配方法称为无感知(oblivious)功率分配.Zhou等人通过将分割-平移策略与选择-比较方案相结合,提出了一种基于 SINR 模型的局部化 MLS 算法27.与文献 20,25不同的是,文献 27 把网络区域划分为矩形,在每个矩形中构造一个极大独立集而不是只选择一条链路.由于超图模型可以限制自身周围链路的干扰,因此远距离链路的干扰可以忽略不计.基于这个特征以及文献 25 的算法思想,Wang 等人提出了一种改进的 SLS 算法14.文献 14 的近似因子与矩形中的极大链路集成正比,而极大链路集又决定了矩形的边长,这两个因素互相影响,互相矛盾.Huang 等人提出了基于无感知功率分配的 SLS 近似算法6,根据链路的长度对链路进行分类调度,并且把网络区域划分为正方形,将链路划分为彼此相距较远的不相交的局部链路集,为局部链路集设计 MLS 算法.上述算法均采用矩形划分方案控制 SINR 全局干扰.受蜂窝网络的启发,Yu 等人采用六边形区域划分策略,提出了一种新颖的 SLS 算法5.结合不同的功率分配方案,文献 5 提出的算法不仅大大降低了调度时间,而且节省了发送节点的能量消耗.文献 5 与本文算法有很大的相似性,但是文献 5 采用集中式链路调度,而且只处理一组静态的通信链路.以上算法只适应于静态网络,调度一组静态链路集.在实际网络中,通信请求具有时变性,上述算法无法直接适应于具有时变特征的动态网络.O(log2n)O(logn)O(log2n)O(log2n/loglogn)O(logn+log)近年来,SIC 技术得到了广泛的应用,极大地提高了网络的容量2831.SIC 技术基于以下事实:不应将干扰信号视为随机噪声,而是结构良好的信号.Lv 等人证明了基于 SIC 的链路调度问题是 NP 难的32.Goussevskaia 等人在 SINR 模型下针对 SLS 问题提出了一种采用 SIC 技术的多项式时间算法33,利用噪声的结构特征提高了网络容量.Lv 等人证明了使用 SIC 技术并不能降低算法的近似因子34.使用 SIC 技术与不使用 SIC 技术相比,虽然算法的近似因子具有相同的阶,但是网络容量提高了 20%到 100%.由于可用的频谱资源是有限的,一些通信设备必须竞争使用这些受限的网络资源,争用解问题也是当前的研究热点,尤其在分布式计算方面,争用解问题是一个非常重要的研究课题.通常,在争用解的概率性算法中,需要通过轮以高概率得到一个解,当使用载波监听技术时,算法的时间复杂度可以提高到轮35.近来,Jurdzinski 等人在 SINR 模型下把时间从轮提升到轮36,而 Fineman 等人在 SINR 模型中用轮以高概率得到争用解37.Yu 等人把争用解问题应用于动态网络中,设计了局部广播算法38.由于节点的扰动,即节点加入或离开网络,网络拓扑结黄宝贵等:基于 SINR 的动态无线网络分布式链路调度4227构随时发生变化,增加了算法设计的难度.另外,节点的移动,环境的变化以及敌手阻塞网络等情况在一些文献中也得到广泛关注3942.2 网络模型及假设 2.1 网络拓扑结构n=|V|u Vv Vl=(u,v)uvlen(l)=d(u,v)PTPTd2 1 N 1其中,是发送节点发送数据的功率.本文使用一致功率分配,即假设所有节点的发送功率是相同的,常数.表示环境噪声,是信号能够被成功解码的最小 SINR 阈值.通常,常数.2.3 SIC 模型vk=Pv(u1),Pv(u2),.,Pv(uk)kPv(u1)Pv(u2).Pv(uk)Pv(ui)uivvvvv设接收节点接收到个不同的信号,用表示这个不同信号的功率,并且功率大小满足,表示由发送节点发送的信号的功率.迭代解码各个信号.首先,解码功率水平最强的信号,把其他信号看作噪声.如果最强信号的 SINR 值满足公式(1),则最强信号解码成功.如果最强信号不是节点所需要的信号,则 把该信号剔除.此时,次强的信号成为最强信号.然后,解码次强信号.重复上述过程,直到成功解码需要的信号,或者某次迭代过程解码失败43.vkx1,2,.,k形式上,节点能够解码个冲突信号当且仅当,以下不等式成立:Pv(ux)uyU,Pv(uy),Pv(uy)Pv(ux)Pv(uy)+uzU,Pv(uz)Pv(uz)+N(2)uyU,Pv(uy),Pv(uy)Pv(ux)Pv(uy)Pv(ux)xuzU,Pv(uz)Pv(ux)Pv(uy)uzU,uz,ux,Pv(uz)Pv(uy)Pv(uz)+Pv(ux)+N Pv(ux)uzU,Pv(uz)t1t1u1u2u3t2u4u4t1 t2u4本文考虑两种动态网络模型.一是节点扰动,即节点加入或者离开网络;二是节点移动,即节点从一个位置移动到另外一个位置.把网络区域划分为多个正六边形,任意一个六边形都是一个小网络区域.节点扰动如图 1 所示.假设,在时刻该六边形中只有 3 个节点(,和),如图 1(a).在时刻,加入六边形,如图 1(b).此时,称加入网络.反之,假设,即网络状态由图 1(b)变成图 1(a),则表示节点离开网络.u1u1u2u3u4u2u3(a)在 t1 时刻六边形(b)在 t2 时刻六边形中有3个节点中有4个节点图1节点扰动t1uut2t2 t1uu1u2u3u4uu1uuuu2u3uuu4u节点移动性如图 2 所示.每个六边形都有一个编号 n,n1,2,3.假设时刻节点在某个编号为 1 的六边形中,可以自由移动.在时刻(),可以移动到或、的位置.如果移动到当前六边形的其他位置,如的位置,则仍然在当前网络中;如果移动到编号不是 1 的六边形中,如移动到或的位置,则称离开网络;如果移动到编号为 1 的其他六边形中,如的位置,则称离开当前网络区域而加入另一个网络区域.在下文中证明节点离开网络不影响算法的执行.这样,在本文剩余的内容中,只需要处理一种网络的动态行为,即节点加入网络.1113332212u4u2u3u1u图2节点u移动其他位置 2.5 网络拓扑结构假设网络区域有个中心位置,所有节点都共享这个中心位置.每个节点都知道它自己的位置,这可以通过内置GPS 或定位算法实现(如文献 44,45).所有节点都满足时钟同步,把时间划分为轮,每个轮包含常数个时隙.节点在一个时隙内可以发送或接收一个消息.节点采用半双工通信,即在某个时刻节点只能发送或接收消息而不能同时进行.如果节点需要发送消息,则节点加入到网络中.假设发送节点只在每轮的开始加入网络,在这轮中网络拓扑结构不再发生变化.假设每轮最多有 n 个发送节点.节点发送消息的最小距离是 1,最大距离是 R.节点可以同时接收 k 个消息并且能够通过 SIC 技术解码这 k 个消息.2.6 问题定义及研究路线网络中存在一组动态的、等待调度的链路,其发送节点共享无线信道.他们竞争信道的使用权,胜出者可以向黄宝贵等:基于 SINR 的动态无线网络分布式链路调度4229nSS其接收节点发送数据,其链路获得调用权.竞争过程持续许多轮.每轮开始时可能有部分发送节点退出信道竞争,也可能有一些新发送节点加入信道竞争,但是每轮参与信道竞争的发送节点不超过个.本文的目标是,经过有限轮的竞争后,计算一个最大链路子集,使中的每一条链路都满足 SINR 干扰约束条件.研究路线概述如下.SSS首先,通过把网络区域划分为正六边形的方法控制 SINR 模型的全局干扰.受移动蜂窝网络的启发,把网络区域划分为正六边形,并且用 1、2、3 为每个六边形编号,使任意相邻的两个六边形具有不同的编号.把中的每一条链路“安排”在不同的六边形中,而且这些六边形具有相同的编号.这种方法可以保证中的任意一条链路受到的干扰有上界,从而保证中的每一条链路都满足 SINR 干扰约束条件.然后,为发送节点设计分布式领导者选举算法.通过领导者选举算法,使每个编号相同的六边形中最多只有一个发送节点发送数据.每个六边形是一个独立的网络区域,其中的发送节点分布式竞争信道的使用权.设计领导者选举算法以及证明算法的正确性和有效性是本文的关键,也是主要内容.所以,本文首先介绍领导者选举算法,称为 LE,并证明 LE 算法的正确性和有效性.3 领导者选举本文的基本思路是把网络区域划分为正六边形,并用数字 1、2、3 编号,编号相同的六边形中的发送节点在发送数据之前通过领导者选举算法竞争信道,使每个六边形中最后只保留一个节点发送数据.下面详细介绍领导者选举算法,这是本文的关键内容.3.1 网络区域划分R处理 SINR 干扰模型的全局干扰是设计链路调度算法的关键.解除全局干扰的一种有效方法是把网络区域划分为多个小区域,使来自每个小区域中的干扰有上界.基于此,本文把网络区域划分为边长为的正六边形,的值将在下文中给出.每个六边形用数字 1、2 或 3 进行编号,使任意两个相邻的正六边形具有不同的编号.将网络区域的中心作为坐标原点,是某个编号为 1 的正六边形的中心.如图 3 所示.与该六边形相邻的左上角和右上角的正六边形的编号分别为 2 和 3.如果发送节点 u 恰好位于两个六边形相交的边缘线上,则规定 u 位于编号较小的六边形中.这样,每个发送节点都位于某个特定的六边形中.根据第 2.5 节对网络模型的假设,因为每个节点都知道它自己的位置,并且知道网络区域的中心位置,所以每个节点都知道它所处的六边形的编号.1231232311232312312312323123123xy231111图3网络区域划分为正六边形并用1,2,3编号;坐标原点位于编号为1的某个六边形的中心 3.2 领导者选举算法概述编号相同的六边形中的发送节点同时执行领导者选举算法,如编号为 1 的六边形中的发送节点执行领导者选举算法,然后编号为 2、3 的六边形中的发送节点依次轮流执行领导者选举算法.不失一般性,以下叙述中假设编号为 1 的六边形中的发送节点执行领导者选举算法.PC=2NRR=2R每个节点有 3 种不同的状态:活跃状态(Active),静默状态(Silence)和领导者(Leader).如果节点 u 需要发送消息,则 u 处于活跃状态并参与领导者选举算法.u 以概率 p 发送探测消息,发送功率为.其中,.如果 u 收到同一个六边形中其他发送节点发送的探测消息,则 u 退出领导者选举算法,u 转入静默状态.经过 T 轮之后,如果 u 依然是活跃的,则 u 成为领导者.领导者选举算法的伪代码如算法 1 所示.4230软件学报2023 年第 34 卷第 9 期u算法 1.Leaderelection(LE)(executedbythesender).uInit:state()=Active;Tforroundsdouifstate()=Activethenuptransmitsaprobemessagewithprobability;ureceivesanddecodesmessageswiththeSIC;uifreceivesoneormoreprobemessagesfromthesamehexagonthenustate()=Silence;endifendifendforuifstate()=Activethenustate()=Leader;endifh接下来证明 LE 经过 T 轮后以高概率选择一个领导者.LE 算法虽然简单,但理论分析过程却非常复杂.LE 的目标是在每个六边形中以高概率选择一个领导者.不失一般性,我们考虑一个编号为 1 的非空六边形,下面的引理和定理的分析都与这个六边形相关.为了证明 LE 算法能够以高概率选择一个领导者,需要证明两件事情:一是经过任意一轮后有部分活跃节点转变为静默节点;二是即使网络拓扑结构发生变化,经过 T 轮后算法仍然可以结束.证明思路如下.ni ni(1)证明在任意一轮的竞争过程中,如果在本轮开始时活跃节点个数满足(参数的意义参考引理 1),总有常数比例的节点退出竞争信道的过程(引理 1).引理 1 的证明过程中需要假设通信节点具备多包接收的能力,可以使用相继干扰消除技术解码存在干扰的信号.1/(2)网络的动态性导致在每轮竞争过程中总有一些发送节点加入网络(本文把 3 种不同的动态过程归为一种),定义网络节点的动态变化率(定义 4),当时,经过一段时间后,活跃节点持续减少的概率至少是 1/2(引理 2和引理 3).1/(3)最后,应用切诺夫界定理,当时,LE 算法经过有限轮后以高概率选择一个领导者(定理 1).3.3 理论分析uuulogRg0,g1,.,glogRgid2i d 2i+1Vigini=|Vi|i i iVi=i1j=0Vjni=|Vi|活跃节点竞争无线信道,同时也收到其他活跃节点发送的探测信号,需要解码这些信号,判断在当前六边形中是否存在其他活跃节点竞争信道.即,需要计算每一个信号的 SINR 值.首先,把活跃节点划分为类,.其中,类的活跃节点与其最近的相邻节点的距离满足:.用表示类的活跃节点,.根据需要,下标 可以用、和替换.例如,.gii=0,1,.,logRtni nitVi1e|Vi|5(121/2)/6引理 137.非空六边形中任意类,如果在 轮开始时,那么在 轮结束时,集合中至少有常数部分的活跃节点以概率成为静默节点.其中,是常数.u Viu2iAit(u)u2t2i2t+12it=0,1,.,logRGiu|Ait(u)|802t(/2+1)n 0引理 1 的证明过程非常复杂,本文借用文献 37 的证明思路,修改重要的参数以适应算法 LE.证明思路如下.设,则与其最近的活跃节点的距离不小于.定义是以为圆心,分别以和为半径的圆构成的圆盘中的活跃节点集合,.定义“良好”节点集合(参考文献 37 的定义 1),良好节点满足,并证明如果,则中至少一半的节点是良好节点.其中,.然后从良好节点中构造“稀疏”节点集合,中的任意两个节点之间距离不小于.其中,.并且,有常数部分的良好节点是稀疏节点,即.然后证明重要结论:存在概率和常数,如黄宝贵等:基于 SINR 的动态无线网络分布式链路调度4231pSi1e|Si|p=c1/(4cmax)c1=1/(2+2)cmax=80/(121/2)n Pu(u1)uu1u2uu2u2uuu2uu1uuu2u2uu2uuu2u1u1uu假设和同时以功率发送探测消息,则能够收到这两个探测消息,它们在处的功率分别是和.显然,.因此,不能直接解码发送的探测消息,但能够解码发送的探测消息.然而,和在两个不同的六边形中,不与竞争信道.即应该忽略的探测消息.如果不使用 SIC 技术,无法解码发送的探测消息,则无法转变为静默节点.所以,本文使用 SIC 技术,首先解码发送的探测消息,由于与在两个不同的六边形中,不与竞争信道.所以,忽略的探测消息,进而再解码发送的探测消息.由于与在同一个六边形中,转为静默节点.ukPu(u1),.,Pu(uk)Pu(u1)Pu(u2).Pu(uk)PCRuPu(u1)u1uuuu设同时接收个消息,其功率满足.这样,可以解码功率最强的信号,把其他信号看作噪声.如果与位于同一六边形中,那么变为非活跃节点,保持静默,不需要再解码其他信号.否则,把功率最强的信号从复合信号中删除,然后解码次强信号.这个过程持续进行,直到变为非活跃节点,或者某个信号违反 SINR 约束而不能解码为止.接下来分析,LE 需要经过多少轮才能以高概率选择一个领导者.n假设在一个轮中网络的拓扑结构不变,即网络拓扑结构在一个轮的开始时发生变化,但是在这个轮中保持不变.假设活跃节点不超过个.Vhi(t)Vhi(t)i=0,1,.,logRtt Tnhi(t)=|Vhi(t)|nhi(t)=|Vhi(t)|定义 1.动态变化率.令和,分别表示在第 轮,开始和结束时六边形中的活跃节点的集合,.节点的动态变化率定义为:=maxtT,hH,i0,logR?nhi(t+1)nhi(t)?/nhi(t),其中,H 表示六边形的集合.r1gi0 r1 1 r2=(r1+/(1)(1+)10 sti.i=0st0=0g0i 0gigi1t stiqt(i1)=r2qt(i)qt(i)当时,.即类的节点数目在第 1 轮就开始减少.当时,类比类的节点延迟轮开始减少.所以,当时,.gitqt+1(i)nqt(i)=i1j=0qt(j)qt(i)/(1)引理 2.如果类在第 轮满足,那么.4232软件学报2023 年第 34 卷第 9 期qt(i1)qt(i)证明:因为,所以:qt(i)=i1j=0qt(j)=qt(i1)+qt(i2)+.+qt(1)+qt(0)=qt(i)(+2+.+i)qt(i)/(1).tgiqt(i)ni qt(i)t下面证明,存在一个特殊的轮,从这轮开始类的节点最多有个,即.但是这个特殊的轮 很难求得,因为网络存在如下几个动态行为.(1)当节点需要发送新消息时节点随时加入网络;(2)节点随时可能离开网络;(3)节点因为收到其他节点的探测消息而变为静默节点.giqt+1(i)这些节点的动态行为导致的大小随时可能发生变化.定义一个比更严格的界:qt+1(i)=qt(i)r2qt(i)/(1)=qt+1(i)qt(i)/(1).(3)j inj qt(j)ni qt+1(i)t+1ni qt+1(i)公式(3)表明,如果,并且,那么在第轮有.把多个轮定义为一个阶段,轮的个数称为阶段的长度.git t 0ni qt(i)gini qt+1(i)引理 3.考虑某个阶段,开始时所有的类在第()轮满足,那么在这个阶段结束时类以常数概率满足.nj qt(j)j ini qt(i)ni qt(i)/(1)qt+1(i)证明:首先,考虑一个轮的执行过程.因为,所以.由引理 2,.根据的定义有:qt(i)=qt+1(i)r2/(1)nir2/(1).ni qt+1(i)1(1+)r11 1/最后一个不等式成立,因为假设,否则引理 3 自然成立.选择一个很小的常数,使得,并且.则:ni1nir2/(1)ni.r11enir1ni(r2/(1)ni=qt+1(i)引理 1 表明,只有不超过的活跃节点没有成为静默节点,这个事件概率是.所以,.max2/(1r2),2=(1)把一个阶段的长度定义为,其中:=qt+1(i)qt+1(i)=r2r2/(1),ni qt+1(i)e2ni/(1r2)1r22ni1r22 qt+1(i)=1r22qt+1(i)那么的概率为.gini qt+1(i)根据一致限定理(unionbound),存在类使得的概率至多是:logR1i=01r22qt+1(i)1r22logR1i=01qt+1(i)=1r221nrt+12logR1i=0(r2)i1r221nrt+1211r212.giqt+1(i)1/2所以,在这个阶段结束时类活跃节点的数目少于的概率至少是.1/O(logn+logR)定理 1.如果节点的动态变化率,LE 算法经过轮后以高概率选择一个领导者.tni qt(i)t+1ni qt+1(i)O(logn+logR)1eni证明:在每个阶段,如果在第 轮时,那么从轮以后至少以常数概率满足.根据切诺夫界(Chernoffbound),LE 算法经过轮后以概率选择一个领导者.3.4 仿真10001000=3=10 N=70 dB c=3=6cc12+4(33)(12+1)1/=0.15在的正方形区域中随机部署 200 条通信链路,最短链路长度设置为 1,最长链路长度设置为 30,.节点的动态变化率,每轮增加的链路数目是前一轮剩余链路的 15%.节点以概率 p 发送探测消息,而 p 的值非常小,所以仿真结果的随机性非常大.本文运行程序 300 次,然后取运行结果的平均值.因为概率 p 非常小,当竞争信道的发送节点比较少时,所有黄宝贵等:基于 SINR 的动态无线网络分布式链路调度42331eni发送节点可能都不发送探测消息,导致节点竞争信道的轮数比较大.另外,定理 1 表明,LE 以概率选择一个领导者.所以,当发送节点比较少时,无法达到以“高概率”选择一个领导者的要求.另一方面,当发送节点比较多时,发送探测消息的节点的数目增加,接收节点利用 SIC 技术可以同时解码多个干扰信号,收到探测消息的发送节点更快地成为静默节点,加速算法的执行过程,在更短的时间内选择出领导者.观察图 5 发现,当发送节点的数目在 1020 个时,LE 选择一个领导者所需要的时间基本符合一条对数曲线的形状,当发送节点超过一定的数量时反而能够在更短的时间内选出领导者.3 0002 5002 0001 5001 000500010 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25仿真结果轮数11692+1432(logn+logR)17769+2133(logn+logR)发送节点数图5领导者选举算法的仿真结果 4 链路调度算法设计 4.1 算法概述Rl=(u,v)huhuuaa本节提出一种在线分布式链路调度算法,简称 OLD_LS(onlinedistributedlinkscheduling),以 TDMA 方式执行.首先,把网络区域划分为边长为的正六边形,并用 1、2、3 编号,使任意相邻的两个正六边形的编号不同.链路在六边形中,当且仅当发送节点在中.如果恰好位于两个六边形相交的边缘线上,则规定在编号较小的六边形中.规定链路的编号与六边形的编号相同.编号相同的六边形中的发送节点同时执行 OLD_LS算法.如果发送节点等待发送消息,则该节点的初始状态是活跃的(Active);否则,该节点状态是非活跃的(inActive).编号为的活跃节点执行 LE 算法.执行 LE 后,编号为的六边形中的领导者可以发送消息,即该链路被调度.LE 算法执行时间是 T 轮,领导者用一轮的时间发送消息.经过 T+1 轮后静默节点重新设置为活跃状态,重新竞争信道.算法 OLD_LS 伪代码如算法 2 所示.u算法 2.Onlinedistributedlinkscheduling(OLD_LS)(performedbythesender).a=1Init:;whiletruedouifhasamessagetotransmitthenustate()=Active;elseustate()=inActive;endifuaifstate()=inActiveoruslabelisnotthenuT+1waitsrounds;el