无线Mesh回程网的跨层优化快速算法

摘要：

针对时分多址(TDMA)模式下无线Mesh回程网的路由及调度的跨层优化问题,提出了两种跨层优化的快速算法.首先在以最短系统调度时间为目标的跨层优化模型的基础上,提出了一种基于极大团搜索的快速最优算法,该算法通过Bron-Kerbosch极大团搜索算法列举出网络中所有极大并发传输模式,简化了跨层优化模型,从而可以用线性规划方法最小化系统调度时间,极大提高了运算的速度.仿真结果表明,与经典的列生成最优算法相比,该算法的运算时间缩短了99％以上.根据无线Mesh回程网的流量特点,文中还提出了一种基于链路权重分类的快速启发式算法,该算法能以较大的概率筛选出含有较大权重链路的极大并发传输模式.仿真结果表明,对于35节点的网络,该算法得到的次优结果相对于最优的平均偏离率在0.5％以下,平均运算时间仅为极大团最优算法的2.5％左右.

关键词：无线Mesh网、极大团、跨层优化、列生成算法

所属期刊栏目：40

分类号：TP393(计算技术、计算机技术)

资助基金：国家"863"计划项目2008AA04A103;国家自然科学基金资助项目61001113

在线出版日期：2012-10-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：29-35,42