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

Abstract:

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 remarkably 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.

Key words: wireless mesh networks, maximal clique, cross-layer optimization, column generation algorithm