We use cookies to improve your experience with our site.

无线传感器网络的能量有效的最小移动充电设备覆盖研究

Energy-Efficient Minimum Mobile Charger Coverage for Wireless Sensor Networks

  • 摘要: 因为需要持续不断地给电池供电型传感器充电,所以维持无线传感器网络(WSN)的运转是个具有挑战性的问题。可以覆盖到网络中固定传感器,并能有效地无线地传输能量的可移动充电设备器(MC),有望解决这一挑战。保证所有的传感器正常工作,并且在满足传感器充电频率和充电设备的调度的前提下所需要的MC最少,是一个优化问题。在高维空间里,该优化问题为NP问题。而如果考虑一维空间是一条线还是一个环时,传感器具有同构充电频率这一特殊场景则有一个可解算法。本文旨在寻找在可解空间和不可解空间间的微妙的界限。具体而言,我们学习了在线性空间中,频率为1秒和2秒 (生命周期为1和0:5时间单位)的异构传感器,猜想其NP困难,提出了一个新的暴力破解算法,并给出了能提供1:5近似解决方案的线性贪婪算法。然后,我们介绍了使用最少MC的能源优化问题,并给出最优解决方案。我们通过充分的仿真验证了本文提出MC数量最小化算法的有效性。

     

    Abstract: Sustaining an operational wireless sensor network (WSN) is challenging due to the persistent need of the battery-powered sensors to be charged from time to time. The procedure of exploiting mobile chargers (MCs) that traverse to the fixed sensors of the network and wirelessly transfer energy in an efficient matter has been considered widely as a promising way to tackle this challenge. An optimization problem, called the mobile charger coverage problem, arises naturally to keep all of the sensors alive with an objective of determining both the minimum number of MCs required meeting the sensor recharge frequency and the schedule of these MCs. It is shown that this optimization problem becomes NP-hard in high-dimensional spaces. Moreover, the special case of the homogeneous recharge frequency of the sensors has already been proven to have a tractable algorithm if we consider whether the 1-dimensional space is a line or a ring. In this work, we seek to find a delicate border between the tractable and the intractable problem space. Specifically, we study the special case of heterogeneous sensors that take frequencies of 1's and 2's (lifetime of 1 and 0.5 time units) on a line, conjecture the special case's NP-hardness, propose a novel brute-force optimal algorithm, and present a linear-time greedy algorithm that gives a 1.5-approximation solution for the problem. Afterwards, we introduce the energy optimization problem of the MCs with the minimized number and solve it optimally. Comprehensive simulation is conducted to verify the efficiency of using our proposed algorithms that minimize the number of MCs.

     

/

返回文章
返回