无线传感器网络中干扰最小化问题的后悔贪心算法

无线传感器网络是当前信息领域的一个研究热点,由于无线传感器携带的能量有限,限制了无线传感器的使用寿命,通过减少由于邻近节点同时传输信号产生的干扰可以降低节点的能耗。拓扑控制技术可在保持网络连通的情况下,调整节点传输半径,以降低干扰。以接收者为中心的干扰模型中,求解无线传感器网络中基于拓扑控制技术的干扰最小化问题是NP难问题。现有的贪心算法求解思路是依据某个贪心准则依次确定每个节点的传输半径,求解速度快,但精度有待提高。探讨了增强目前最好贪心算法精度的策略,允许部分后悔操作,即每个贪心迭代步中当前网络的最大干扰增加时,通过两个后悔策略重新调整某些节点的传输半径,力图降低当前网络的最大干扰。模拟实验结果表明,针对随机产生的算例,所提出的后悔贪心算法在略有增加的时间内有效提高了现有贪心算法的精度。

A regret greedy algorithm for the interference minimization problem in wireless sensor networks

The wireless sensor network is one of the active research areas in current information field. However, wireless sensors carry limited energy, which limits its service life. One way of reducing the energy consumption of a node is to reduce the interference caused by the simultaneous transmission of the signals from its neighboring nodes. The topology control technology can adjust every node transmission radius to reduce interference while maintaining network connectivity. Under the receiver centric interference model, solving the interference minimization problem based on the topology control technique in wireless sensor networks is NP-hard. The existing greedy algorithms, which are based on some greedy criterions to determine the transmission radius of each node successively, are fast but their accuracy needs to be improved. We explore some strategies to enhance the accuracy of the best greedy algorithm available in the literature, which allows partial regret, that is, whenever the maximum interference of the current network increases in one greedy iteration step, through two regret strategies we attempt to re-adjust the transmission radii of some nodes in order to reduce the maximum interference in the current network. Experimental results show that the accuracy of the existing greedy algorithm is improved within a slightly increasing time for our randomly generated instances.