无线自组织网高吞吐量时隙调度算法研究

作     者：刘志聪 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：刘勤

授予年度：2022年

学科分类：080904[工学-电磁场与微波技术] 0810[工学-信息与通信工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 080402[工学-测试计量技术及仪器] 0804[工学-仪器科学与技术] 081001[工学-通信与信息系统] 

主      题：无线自组织网 时分多址 时隙调度 高吞吐量 图染色 

摘      要：无线自组织网是一项已经发展五十多年的通信网络技术,它以无线通信技术为基础,与传统通信相比有着无中心、组网快捷、抗毁能力强等诸多特点,拓展了传统网络无法普及的应用场景,为实现随时随地自由通信提供了一份保障。它凭借特殊的组网方式在军事通信、无线传感器网络(Wireless Sensor Network,WSN)等多个领域都得到了不错的发展。随着“5G通信的发展,“万物互联等理念的相继出现,诸多技术的实现及场景需要无线自组网的支撑,因此对无线自组织网的研究仍是一项极具意义的工作。本文通过将无线自组织网与传统网络进行对比,明确了无线自组织网的介质访问控制层(Medium Access Control,MAC)协议设计是重要研究对象之一,在基于时分多址(Time Division Multiple Access,TDMA)的通信网络中,其中比较重要的内容为时隙调度算法的研究。本文基于该内容主要进行了如下工作:(1)分析时隙调度算法在基于链路或节点调度时,会对广播类型和单播类型的业务及网络吞吐量产生不同程度的影响。为了获得更高的网络吞吐量,本文提出时隙调度算法采用基于链路的时隙调度,通过提高时隙复用度的方式来提高网络吞吐量。针对采用TDMA方式的无线自组织网进行资源分配时需要避免链路干扰的问题,通过图论数学工具,将原本的有向网络模型图转为无向的冲突图,直观地刻画了链路之间的干扰关系,简化了时隙调度中避免冲突的问题,并将该问题转为数学图染色问题。(2)针对传统方法中使用图染色算法进行时隙调度时产生的时隙资源浪费问题进行研究与改进,通过重新构造数学模型并加以解决,从而进一步提高时隙资源复用度。具体研究分析中发现在图染色算法保证链路只进行一次调度且达到最优的情况下,想要进一步提高时隙资源的复用度,可以放宽每条链路只能进行一次染色的限制,以及松弛链路调度的绝对公平。在此构建了新的约束条件,通过把冲突图补全为完全图,将图染色问题转化为最优组合的搜索问题。针对该问题,设计了一种从最大组合成员数向下搜索的集中式算法,让该算法在获得最优组合后能够及时终止,保证每个组合中成员数是尽可能大,即每个时隙尽可能调度多条链路。通过在随机图上进行仿真对比,验证了该算法在时隙资源复用度上具有明显的提升效果。(3)针对较大网络规模的分布式时隙调度问题,本文通过改进Schneider和Wattenhofer提出的分布式最大独立集(Max Independent Set,MIS)算法,进一步提高时隙资源复用度。由于分布式场景中每个节点只能获得局部网络冲突图,也只能决策与自身相关的链路进行收发的时隙,因此需要节点间进行多轮协商才能收敛确定最终时隙调度结果。在集中式图染色算法中,节点的度是一个很重要的影响因素,因此在分布式SW-MIS算法的基础上,引入链路干扰数作为链路权值,并针对权值相等时简化了处理流程。通过为链路增加可重复状态以及在每一轮MIS计算后增加重复链路的选取环节,实现了链路的多次调度。为了保证了全网每一轮MIS计算流程的一致性,给每个节点增加算法轮次的属性,保证每次进行权值比较时处于同一轮次。最后通过仿真,验证了算法在时隙资源复用度上具有提升效果。