计算机应用研究

作者：杜磊,付喜梅,杨文瀚,

单位：1.华南师范大学计算机学院,广州510631；2.韶关学院数学与统计学院,广东韶关512005；

关键词：无线传感网络,贪心算法,干扰最小化,批量处理,连通图,缩边策略,

基金：国家自然科学基金资助项目(61370003)；韶关学院科研项目(S201501019)；；

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

来源：2020年第5期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2020年第5期