| 引用本文: | 戴海鹏,陈贵海,徐力杰,刘云淮,吴小兵,何田.一种高效有向无线充电器的布置算法.软件学报,2015,26(7):1711-1729 |
| |
|
| |
|
|
| 本文已被：浏览 4580次 下载 7244次 |
码上扫一扫！ |
|
|
| 一种高效有向无线充电器的布置算法 |
|
戴海鹏1, 陈贵海1,2, 徐力杰1, 刘云淮3, 吴小兵1, 何田4,5
|
|
1.计算机软件新技术国家重点实验室(南京大学), 江苏 南京 210023;2.上海市可扩展计算与系统重点实验室(上海交通大学), 上海 200240;3.公安部第三研究所, 上海 200031;4.上海交通大学 电子信息与电气工程学院, 上海 200240;5.Computer Science and Engineering, University of Minnesota, Minneapolis, USA
|
|
| 摘要: |
| 传统的传感器节点通常采用电池供电,有限的电池能量限制了传感器网络整体的寿命.无线能量传输技术可将能量以无线方式从充电器发送至传感器,从而可以彻底解决这一问题.无线可充电传感网中的一个重要问题是无线充电器的布置问题,即,如何有效地布置充电器,使得传感器网络的整体充电效用最大化.已有的工作主要考虑的是全向充电器的布置问题,且充电器可布置的位置受限,如只能布置在三角形顶点或网格中的格点处,因此具有相当的局限性.首次考虑了有向充电器的一般布置问题,即,充电器充电区域为扇形,并且充电器可布置在区域内任何位置处,其朝向可任意调节.另外,首次基于实测数据建立了有向充电器的充电模型,并提出一系列创新方法将问题进行转化,设计了一种近似比为(1-1/e)/(1+e)的高效算法——CDG(charger deployment-greedy)算法来解决这一问题.仿真实验结果说明了CDG算法的有效性.与其他提出的两种随机算法相比,CDG算法的性能分别提升了将近300%和100%. |
| 关键词: 有向无线充电器 有向充电 布置 子模性 近似算法 |
| DOI：10.13328/j.cnki.jos.004618 |
| 分类号: |
| 基金项目:国家重点基础研究发展计划(973)(2012CB316201, 2014CB340303); 国家自然科学基金(61133006, 61321491, 61373130, 61170247, 613230428); 江苏省研究生培养创新工程(CXZZ12_0056) |
|
| Effective Algorithm for Placement of Directional Wireless Chargers |
|
DAI Hai-Peng1, CHEN Gui-Hai1,2, XU Li-Jie1, LIU Yun-Huai3, WU Xiao-Bing1, HE Tian4,5
|
|
1.State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023, China;2.Shanghai Key Laboratory of Scalable Computing and Systems (Shanghai Jiaotong University), Shanghai 200240, China;3.Third Research Institute of Ministry of Public Security, Shanghai 200031, China;4.School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University, Shanghai 200240, China;5.Computer Science and Engineering, University of Minnesota, Minneapolis, USA
|
| Abstract: |
| 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+e) 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. |
| Key words: directional wireless charger directional charging placement submodularity approximation algorithm |
|
|
|
|
