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

来源：软件学报杂志2015年第7期北京时间：

作者：戴海鹏,陈贵海,徐力杰,刘云淮,吴小兵,何田

单位：戴海鹏，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21002311,陈贵海，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 210023;上海市可扩展计算与系统重点实验室(上海交通大学), 上海 20024002,徐力杰，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21002303,刘云淮，公安部第三研究所, 上海 20003104,吴小兵，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21002305,何田，上海交通大学 电子信息与电气工程学院, 上海 200240;Computer Science and Engineering, University of Minnesota, Minneapolis, USA06

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

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

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