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

Edge shrinking greedy algorithm for minimizing interference in wireless sensor network

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

The problem of minimizing the maximum interference in wireless sensor networks can be described as follows:the given n points with their positions on the plane and thresholds of transmission ranges,for each point,the maximum number of other points whose transmission ranges cover this point is minimized.To effectively solve this problem,this paper proposed a new greedy algorithm called edge shrinking algorithm.The algorithm constructed a desirable network communication topology by shrinking edges,which was different from existing algorithms and was accelerated by incorporating the idea of batch processing in operating system to shorten its running time.The experimental result shows that this algorithm can produce better solutions than existing algorithms.