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

Effective Algorithm for Placement of Directional Wireless Chargers

作　　者：戴海鹏[1] 陈贵海[1,2] 徐力杰[1] 刘云淮[3] 吴小兵[1] 何田[4,5] 

机构地区：[1]计算机软件新技术国家重点实验室(南京大学),江苏南京210023 [2]上海市可扩展计算与系统重点实验室(上海交通大学),上海200240 [3]公安部第三研究所,上海200031 [4]上海交通大学电子信息与电气工程学院,上海200240 [5]Computer Science and Engineering,University of Minnesota

出　　处：《软件学报》2015年第7期1711-1729,共19页Journal of Software

基　　金：国家重点基础研究发展计划(973)(2012CB316201;2014CB340303);国家自然科学基金(61133006;61321491;61373130;61170247;613230428);江苏省研究生培养创新工程(CXZZ12_0056)

摘　　要：传统的传感器节点通常采用电池供电,有限的电池能量限制了传感器网络整体的寿命.无线能量传输技术可将能量以无线方式从充电器发送至传感器,从而可以彻底解决这一问题.无线可充电传感网中的一个重要问题是无线充电器的布置问题,即,如何有效地布置充电器,使得传感器网络的整体充电效用最大化.已有的工作主要考虑的是全向充电器的布置问题,且充电器可布置的位置受限,如只能布置在三角形顶点或网格中的格点处,因此具有相当的局限性.首次考虑了有向充电器的一般布置问题,即,充电器充电区域为扇形,并且充电器可布置在区域内任何位置处,其朝向可任意调节.另外,首次基于实测数据建立了有向充电器的充电模型,并提出一系列创新方法将问题进行转化,设计了一种近似比为(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.

关 键 词：有向无线充电器 有向充电 布置 子模性 近似算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]