Charging Utility Optimization For Wireless Rechargeable Sensor Networks

Sensor nodes in traditional wireless sensor networks are powered by batter-ies,which leads to the finite lifetime of sensor nodes,as well as the wireless sensor networks.The nodes in wireless rechargeable sensor networks based on wireless power transfer technology are able to transfer the RF energy emitting from chargers to DC energy to power themselves,effectively alleviating the limited lifetime prob-lem of the networks and thus attracting intensive research and industry interests.After the rapid development in the recent years,wireless rechargeable sensor net-works have found many applications including environmental monitoring,medical care and smart grids.Charging utility optimization problem focuses on how to design charging plans for chargers and schedule sensor nodes appropriately to reduce the cost of chargers,optimize the performance of sensor nodes,enhance the overall performance of the network,etc.It is one of the most fundamental and important problems in wireless rechargeable sensor networks.The existing works usually overlooks the danger of electromagnetic radiation(EMR)during the charging process,adopts unreasonable charging models and ideal assumptions for the charging scenarios,and pays little attention to some specific cases.For this reason,their obtained results can hardly be applied to real applications,or achieve the expected performances.Based on this observation and latest existing results,this thesis considers the EMR safety,adopting the more realistic charging models and studying the charging utility optimization problem in various practical cases.The main contributions of this paper are summarized as follows:1.For the charging utility maximization problem for non-adjustable power charg-ers under charging safety,a centralized near optimal algorithm is presented.A series of novel techniques are designed to transfer the problem to two tra-ditional problems,namely a multidimensional 0/1 knapsack problem and a Fermat-Weber problem.The techniques include constraint conversion and re-duction,bounded EMR function approximation,area discretization and ex-pansion,and a tailored Fermat-Weber algorithm.A centralized near optimal algorithm is proposed,which provably outperforms the optimal solution to the problem with the EMR threshold relaxing from Rt to(1-?)Rt.2.For the charging utility maximization problem for adjustable power chargers under charging safety,a distributed near optimal algorithm is proposed.An area discretization approach is presented to transform the problem into a linear programming problem.Then,a distributed redundant linear constraints reduc-tion algorithm is proposed to reduce the number of constraints,reducing the computational cost of the linear programming problem.Finally,a distributed algorithm with approximation ratio(1-?)is proposed.3.For the directional charger placement problem for maximizing the charging utility,an approximation algorithm is presented.By introducing two novel approaches,i.e.,area discretization and coverage dominating set extraction,an effective placement algorithm PARA is proposed.Through theoretical analysis,PARA can achieve(1-1/e)/(1+?)-approximation ratio.4.For the quality of energy provisioning problem for mobile nodes,upper and lower bounds for 1D and 2D cases with single or multiple chargers are derived.A new metric-Quality of Energy Provisioning is introduced.By borrowing the idea of flows in physics,a novel approach-flow pattern analysis-is adopted to facilitate theoretical analysis.Based on this approach,the tight upper and lower bounds are obtained for the 1D case with single charger,as well as the tight lower bounds and loose upper bounds for the 1D and 2D cases with multiple chargers.5.For the problem of maximizing quality of monitoring for stochastic events,an effective approximation algorithm is proposed.To simplifying the analysis,the travel time and energy consumption of the mobile node is omitted at the be-ginning.The original problem is thus transformed to maximizing a monotone submodular function subject to two matroids,and an approximation algorithm is presented to address the transformed problem.Based on the obtained re-sults,an approximation algorithm is devised by taking into consideration the travel time and energy consumption.6.For the problem of minimizing the number of mobile chargers,an effective ap-proximation algorithm is proposed.The original problem is formulated into an optimization problem with one linear constraint and one non-linear constraint.Then,a novel method is proposed to approximate these two constraints as one constant constraint.Finally,an approximation algorithm is obtained by adopting the classical theoretical results of DVRP.In the end,the thesis is concluded and some future research works are discussed.