基于任务调度的无线网贪婪信道分配算法

Greedy Channel Assignment Algorithm for Wireless Networks Based on Task Scheduling

针对无线网络链路干扰问题,综合借鉴多处理器任务调度算法提出了一种贪婪信道分配算法,为所访问的无线网链路甄选出干扰最小的信道,并且证明了本算法的近似比率为2-1/k,其中为k为可用的正交信道数,算法复杂度为O(|E|2)。为了验证本文算法的可行性和有效性,将本文所提出的贪婪算法与随机信道分配算法和按序信道分配算法进行了实验对比。仿真结果表明:本文所提出的贪婪算法的整体性能优于其他两种算法,并且贪婪算法得到的最大干扰和平均干扰归一化值随着可用正交信道数的变化趋势较其他两种算法稳定。从而验证了本文算法能有效的降低链路干扰,一定程度上可以提升网络吞吐量。

Aiming at the problem of link interference in wireless networks, this paper proposes a greedy channel allocation algorithm based on multi processor task scheduling algorithm, which is the minimum channel for the access link selection. At the same time, the approximate ratio of the proposed algorithm is 2-1/k, and the k is the available orthogonal channel number, and the complexity of the algorithm is 0 （ ｜E｜2） .In order to verify the feasibility and effectiveness of the proposed algorithm, the proposed algorithm is compared with the random channel assignment algorithm and the random channel assignment algorithm. The simulation results show that the overall performance of the proposed algorithm is better than the other two algorithms, and the maximum interference and average interference normalized values obtained by the greedy algorithm are more stable than the other two algorithms.So the algorithm can effectively reduce the link interference, and can improve the network throughput in a certain degree.