一种高效有向无线充电器的布置算法

Effective Algorithm for Placement of Directional Wireless Chargers

传统的传感器节点通常采用电池供电,有限的电池能量限制了传感器网络整体的寿命.无线能量传输技术可将能量以无线方式从充电器发送至传感器,从而可以彻底解决这一问题.无线可充电传感网中的一个重要问题是无线充电器的布置问题,即,如何有效地布置充电器,使得传感器网络的整体充电效用最大化.已有的工作主要考虑的是全向充电器的布置问题,且充电器可布置的位置受限,如只能布置在三角形顶点或网格中的格点处,因此具有相当的局限性.首次考虑了有向充电器的一般布置问题,即,充电器充电区域为扇形,并且充电器可布置在区域内任何位置处,其朝向可任意调节.另外,首次基于实测数据建立了有向充电器的充电模型,并提出一系列创新方法将问题进行转化,设计了一种近似比为(1-1/e)/(1+ε)的高效算法——CDG(charger deployment-greedy)算法来解决这一问题.仿真实验结果说明了CDG算法的有效性.与其他提出的两种随机算法相比,CDG算法的性能分别提升了将近300%和100%.

Traditional sensor nodes are powered by batteries. The limited battery capacity, however, constrains the lifetime of the wireless sensor networks. Wireless power transfer technology allows energy transfers from a charger to sensor nodes via wireless, and thus solves the problem completely. One fundamental issue in wireless rechargeable sensor networks is the wireless charger placement problem, i.e., how to effectively place the chargers to maximize the overall charging utility of the network. Existing works mainly focus on the deployment issues of omnidirectional chargers, which are confined to positions such as the end point of triangles or lattice point in a grid. These works inevitably have their limitations. This study is to consider the general placement problem in which the charging area of chargers is a sector and the charger can be deployed at any position in the field with arbitrary orientation. First, a charging model for directional chargers is constructed based on trace data. Then, a series of novel techniques is proposed to transform the problem to develop an effective algorithm, CDG （charger deployment-greedy）, with approximation ratio （1-1/e）/（1＋ε） to solve this problem. The simulation results demonstrate the effectiveness of the CDG algorithm. Compared with other two random algorithms, the CDG algorithm has performance gains of nearly 300% and 100%, respectively.