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

Fast Algorithms for Cross-layer Optimization in Wireless Mesh Backhaul Networks

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

Proposed in this paper are two fast algorithms for the cross-layer optimization of routing and scheduling in the TDMA（Time Division Multiple Access） mode in wireless mesh backhaul networks.The first algorithm,which is based on the maximal clique search and introduces a cross-layer optimization model with the minimum system activation time as the optimization target,enumerates all maximal concurrent transmission scenarios in the network by using the Bron-Kerbosch maximal clique searching algorithm,and it simplifies the optimization framework.Thus,the system scheduling time can be minimized via the linear programming and the computation can be remar-kably speeded up.Simulated results indicate that,as compared with the classical column generation algorithm,the first algorithm reduces the average runtime by more than 99%.Furthermore,the second algorithm,which is proposed according to the flow characteristics of wireless backhaul networks,is a fast heuristic algorithm based on the classification of link weights.It can find out the concurrent transmission scenarios that include high weight links with high probability.Simulated results show that the second algorithm helps to obtain suboptimal results with a bias ratio being less than 0.5% from the optimality for the networks with 35 nodes,and the average runtime is only about 2.5% of that of the first algorithm.