首页 | 本学科首页   官方微博 | 高级检索  
     

基于分布式图算法的无线网络MAC调度算法
引用本文:曾健平,张晓轲,徐朝农,徐勇军.基于分布式图算法的无线网络MAC调度算法[J].计算机工程,2012,38(19):15-20.
作者姓名:曾健平  张晓轲  徐朝农  徐勇军
作者单位:1. 湖南大学物理与微电子科学学院,长沙,410003
2. 中国石油大学(北京)计算机科学与技术系,北京,102249
3. 中国科学院计算技术研究所,北京,100008
基金项目:国家自然科学基金资助项目(61003307,61040061); 国家“973”计划基金资助项目(2011CB302803); 国家科技重大专项基金资助项目(2010ZX03006-002,2010ZX03006-007); 湖南省自然科学基金资助重点项目(11JJ2034)
摘    要:针对无线自组织网络带宽利用率低的问题,在主干扰模型的基础上,提出一种基于分布式极大独立集(MIS)的无线自组织网络STDMA节点调度算法.该算法以分布式MIS算法为基础,在算法进入平衡状态时,优先让度大的节点加入MIS,再通过将其结果转化成△+1染色,从而完成时槽分配.该算法是完全分布式的,且时间复杂度为O(1bn).仿真结果表明,与分布式MIS算法相比,该算法收敛速度平均提高23.6%.

关 键 词:无线自组织网络  调度  极大独立集  分布式  主干扰模型  带宽
收稿时间:2011-11-22

MAC Scheduling Algorithm for Wireless Networks Based on Distributed Graph Algorithm
ZENG Jian-ping , ZHANG Xiao-ke , XU Chao-nong , XU Yong-jun.MAC Scheduling Algorithm for Wireless Networks Based on Distributed Graph Algorithm[J].Computer Engineering,2012,38(19):15-20.
Authors:ZENG Jian-ping  ZHANG Xiao-ke  XU Chao-nong  XU Yong-jun
Affiliation:1.School of Physics and Microelectronics Science,Hunan University,Changsha 410003,China;2.Department of Computer Science and Technology,China University of Petroleum,Beijing 102249,China;3.Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100008,China)
Abstract: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.
Keywords:wireless ad hoc networks  scheduling  Maximal Independent Set(MIS)  distributed  main interference model  band width
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机工程》浏览原始摘要信息
点击此处可从《计算机工程》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号