无线传感网络干扰最小化问题的一种缩边贪心算法

无线传感器网络的最大干扰最小化问题可以被描述为已知平面上<i>n</i>个点的位置及发射半径的阈值，要求设置发射半径使得任意点被其他点发射范围覆盖的最大数量达到最小。为了有效求解该问题，提出了一种新的贪心算法——缩边算法。不同于已有算法的构图方式，该算法是通过采取缩边的方式构造网络通信拓扑图，并结合了操作系统中批量处理的思想对贪心算法进行了加速，缩短了算法的运行时间。通过实验验证，该算法相比于已有算法在随机产生的算例上能产生更优的解。