Optimal Road Side Unit (RSU) deployment is of crucial importance to VANETs. The RSU Deployment (RDP) Problem models in the literature usually lack of ability to describe curve-shaped roads and roads non-uniform statistics. We had proposed a more realistic RDP problem model taking these features into consideration. However, our understanding of the RDP problem with the new model is still seriously limited. In this paper, we try to deepen our understanding of the one-dimensional RDP problem with the new model by analyzing its basic properties and designing optimal and efficient approximate algorithms for it. We first analyze the properties of optimal solutions of the one-dimensional RDP problem. Next, suspecting that the one-dimensional RDP problem with $n$ RSUs of different coverage radii is intractable, we propose two greedy-based algorithms (named as Greedy2P3 and Greedy2P3E) and show that Greedy2P3E's approximation ratio is at least $1{-}(\frac{n{-}1}{n})^2$. Then, for the case of $n$ RSUs of identical radii, we found that the RDP problem can be transformed to a geometric version of the well-known Maximum Coverage (MC) problem, which is NP-hard. And then, by exploiting the properties of optimal solutions of our RDP problem, we propose an optimal algorithm named OptGreDyn by combining greedy idea and dynamic programming, and prove its optimality. At last, we proved that, if applied to our RDP problem with $n$ RSUs of identical radii, the approximation ratios of Greedy2P3 and Greedy2P3E are at least 2/3, and it is tight for Greedy2P3 when $n{=}3i$, here $i$ can take any positive integer value. Simulation results verify the optimality of OptGreDyn, meanwhile show that Greedy2P3 and Greedy2P3E usually return near-optimal solutions with profit more than 98% of optimal solutions, and they are preferable than existing approximate algorithms.

Because of the excessive cost of Road Side Units (RSUs), optimal RSU deployment is of crucial importance to VANETs. Since existing models of the RSU Deployment (RD) problem lack ability to describe curve-shaped roads with non-uniform statistics, a more realistic model with this ability for the RD problem was proposed recently. However, our understanding of the RD problem with the new model is still far from satisfactory. Even to the simpler one-dimensional RD (D1RD) problem, properties are not analyzed, optimal algorithms are not proposed yet. In this paper, we focus on the D1RD problem with the new model. We firstly analyze the properties of the optimal solutions of the D1RD problem. We then propose an efficient technique named Dynamic Limiting (DynLim) technique, which reduces solution search space size considerably by adjusting search space limits dynamically. Finally, an optimal algorithm named OptDynLim is proposed based on DynLim, and its optimality is proved. Numerical simulations validate the correctness of our analyses and show that DynLim can usually reduce solution search space size by more than 99%.

For the capability of concentrating radiation energy along a direction, using Directional Mobile Chargers (DMCs) for charging the nodes in a Wireless Rechargeable Sensor Network (WRSN) via wireless power transfer has become a research hotspot. However, existing research neglect cooperative Energy ReDistribution (ERD) among nodes, handering energy charging efficiency. This motivated us to focus on the scenario of charging a WRSN using a DMC and address the underlying ERD-Assisted Directional Charging Schedule (ERADCS) problem. This problem involves determining a charging schedule with minimal energy loss and minimum time span. We first proved the NP-hardness of ERADCS and then proposed a Directional Charging Schedule algorithm Based on Greedy Strategy (DCSBGS) to solve it. In DCSBGS, to tackle the infinite charging directions, we created cMFRDS algorithm to determine a minimum-size representative direction set functionally equivalent to the original infinite directions, and proved its optimality. Subsequently, we assumed Virtual Mobile Chargers (VMCs) fixed to the representative directions, transformed ERADCS into a charging schedule problem using the VMCs, solving it using a two-step framework. We also established key properties of DCSBGS and its sub-algorithms. Furthermore, we extended DCSBGS for ERADCS involving a DMC with multiple charging beams. Our simulation results validate the superiority of DCSBGS over other typical algorithms.

The use of mobile chargers (MCs) to charge the nodes in wireless rechargeable sensor networks via wireless power transfer (WPT) has attracted much research effort. Existing works mostly concentrate on path planning whereas neglecting the opportunities to improve charging coverage and efficiency by exploiting the energy redistribution (ERD) process among nodes and an MC’s capability of charging multiple nodes simultaneously via WPT. To exploit such opportunities, we study the underlying ERD-assisted MC charge scheduling (ERAMCCS) problem, i.e., to find a charging schedule satisfying the nodes’ energy demands with minimum energy loss and minimum time span. After proving that the problem is NP-hard, we propose a charge scheduling algorithm based on the greedy idea (CSBGI), which provides a solution by decoupling the problem into two subproblems: 1) ERAMCCS-Energy and 2) ERAMCCS-Time, to minimize the energy loss and the time span, respectively. By partitioning the energy loss into transmission energy loss and moving energy loss, we solve the ERAMCCS-Energy problem by minimizing the two parts, respectively, by formulating and solving some linear programming problems and traveling salesman problem problems based on the charging position set. The charging position set is iteratively refined by identifying and removing redundant charging positions. For the ERAMCCS-Time problem, concurrent energy transmission opportunities are exploited to try to minimize the time span of the schedule. We demonstrate some key properties of CSBGI, such as its approximation ratio in terms of energy loss and its time complexity. Testbed experiments and numerical simulations confirm the superiority of CSBGI over typical algorithms.

By enabling energy redistribution among nodes in Wireless Sensor Networks (WSNs), the Wireless Power Transfer (WPT) technology provides a new approach to prolong life time of WSNs or a fundamental block for building perceptual WSNs. In this paper, we attempt to deal with the underlying WPT based Energy ReDistribution (WPTERD) problem, which is targeted for finding an energy transmission schedule that satisfies the nodes' energy expectations, meanwhile achieves minimum energy loss and shortest time span. In this paper, we propose a two-step approach for WPTERD by splitting it into two sub-problems named WPTERD-Egy and WPTERD-Time, which focus on the optimization in energy loss and in time span respectively. Basing on some proved properties, we transform WPTERD-Egy to a Linear Programming problem and thus can obtain an optimal time-length list of the nodes' energy transmissions leading to minimum energy loss. Finding that WPTERD-Time is NP-hard, we propose an approximate algorithm to solve the WPTERD problem by exploiting the concurrent energy transmission opportunities. The algorithm is named as Greedy Energy ReDistribution Scheduling (GERDS) algorithm, which is proved to finish in limited loops. Simulations validate the algorithm's ability in minimizing energy loss, and meanwhile return near-optimal schedules with time span in range 100~125% of the optimal value. Simulation results also show that GERDS outperforms a typical flow-based algorithm in terms of the tested performance metrics.