基于分布式图算法的无线网络MAC调度算法  

MAC Scheduling Algorithm for Wireless Networks Based on Distributed Graph Algorithm

作　　者：曾健平[1] 张晓轲[1] 徐朝农[2] 徐勇军[3] 

机构地区：[1]湖南大学物理与微电子科学学院,长沙410003 [2]中国石油大学(北京)计算机科学与技术系,北京102249 [3]中国科学院计算技术研究所,北京100008

出　　处：《计算机工程》2012年第19期15-20,共6页Computer Engineering

基　　金：国家自然科学基金资助项目(61003307;61040061);国家"973"计划基金资助项目(2011CB302803);国家科技重大专项基金资助项目(2010ZX03006-002;2010ZX03006-007);湖南省自然科学基金资助重点项目(11JJ2034)

摘　　要：针对无线自组织网络带宽利用率低的问题,在主干扰模型的基础上,提出一种基于分布式极大独立集(MIS)的无线自组织网络STDMA节点调度算法。该算法以分布式MIS算法为基础,在算法进入平衡状态时,优先让度大的节点加入MIS,再通过将其结果转化成1染色,从而完成时槽分配。该算法是完全分布式的,且时间复杂度为O(lbn)。仿真结果表明,与分布式MIS算法相比,该算法收敛速度平均提高23.6%。Aiming at the problem of low throughput utility rate in wireless ad hoc networks,a STDMA node scheduling algorithm which is based on a novel distributed Maximal Independent Set（MIS） algorithm is proposed,on the assumption of the primary interference model.Based on the distributed MIS algorithm proposed,the node whose degree is the maximal among its neighbors has a preference for joining MIS when the balanced state emerges.The output of MIS is converted into a node coloring,thus the MAC scheduling policy is correspondingly determined.The algorithm is fully distributed and its time complexity is proved to be.Simulation result shows that the convergence time has an average increase of 23.6% compared with that of MIS algorithm.

关 键 词：无线自组织网络 调度 极大独立集 分布式 主干扰模型 带宽 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]