移动无线可充电传感器网络中的充电路径优化

Charging path optimization in mobile wireless rechargeable sensor networks

无线能量传输技术能够有效缓解无线传感器网络中传感器节点的能量供给瓶颈问题,延长网络寿命甚至实现网络的永久可持续性运转。已有工作大多针对静态无线传感器网络(传感器节点位置固定)研究静态充电器的部署问题或是移动充电器的充电路径优化问题,而忽略了传感器节点移动的场景。因此,针对动态无线传感器网络(传感器节点可以移动),设计并优化了移动充电器在网络中的充电路径,使得在有限的时间内最大化移动充电器的充电效用,即充电器在有限的时间内遇到尽可能多的传感器节点并为它们充电。注意,移动充电器在移动的过程中可以选择停下来,为其当前位置充电范围内所遇到的多个节点同时进行无线充电。首先证明该问题是一个APX-hard问题。其次,基于离散化构造的有向无环图,提出一种基于回溯思想的分层剪枝算法,该算法以贪婪算法的解作为基准,逐层剪枝,从而得到固定时隙划分下的最优充电路径。仿真结果表明,所提算法能够有效地提升充电效用。

The wireless power transfer technique is promising in solving the energy bottleneck of sensor nodes in wireless sensor networks,which can thus prolong the network lifetime or even maintain sustainable network operations.Most existing works focused on optimizing the static chargers’deployment or mobile chargers’charging path for static sensor nodes with fixed sensor node positions,ignoring the scenario with mobile sensor nodes.Thus,design and optimize the charging path of a mobile charger was studied for dynamic wireless sensor networks with mobile sensor nodes,to maximize the charging utility within a finite time horizon,that is,the charger can encounter as more sensor nodes as possible in a limited time and charge them.Notice that the mobile charger may stop to simultaneously charge multiple nodes within its charging range during its charging tour.The proposed charging path optimization problem was proven to be an APX-hard problem.Then,based on the constructed directed acyclic graph using discretization method,a layer-wise pruning algorithm based on the backtracking method was proposed.The proposed algorithm took the solution generated by the greedy algorithm as the benchmark and searched the optimal charging path under a fixed time division by layer-wise pruning.Simulation results show that the proposed algorithm can effectively improve the charging utility.