• 面向低占空比传感网的最小代价充电调度优化

    Minimum cost charging scheduling optimization for low duty cycle sensor networks

    • 低占空比传感网中的充电调度优化是一个重要且具有挑战性的问题。为此,提出了一个新颖的付费充电服务模型,并基于该模型研究了面向低占空比传感网的充电代价最小化问题,即如何在一个有限的充电调度时间约束下找到一个满足低占空比传感网中所有传感器设备充电需求的充电调度决策,以实现充电服务费用和网络服务质量的权衡优化。首先形式化定义了低占空比工作模型下的网络服务质量干扰度和充电代价,对目标问题进行了建模并证明了其NP困难性,然后通过构造一个非负且单调非递减的子模函数,将目标问题转化为一个等价的最小代价子模覆盖问题,进一步设计了一个高效的多项式时间贪心算法,同时分析了该方法的近似比性能。最后,通过广泛的仿真实验从传感器设备数量变化、充电站数量变化、电池容量变化、充电调度时间变化、充电服务费用单价变化、充电功率变化、各种模型参数变化等多个维度将所提出的算法和其他3种对比算法进行比较,实验结果表明其充电代价分别至少平均降低了14.6%、12.4%和17.1%,验证了所提算法的性能优越性。

       

      Abstract: Charging scheduling optimization for low-duty-cycle sensor networks is an important and challenging issue. To this end, a novel paid charging service model is proposed, and based on this model, the problem of minimizing charging cost for low-duty-cycle sensor networks is studied. That is, how to find a charging schedule decision that satisfies the charging needs of all sensor devices in low duty cycle sensor networks within a limited charging scheduling period constraint, in order to achieve a trade-off optimization between charging service fee and the quality of network service. Firstly, the interference degree of network service quality and the charging cost under the low-duty-cycle working mode are formalized, the target problem is modeled and its NP-hardness is proved. Then, the target problem is transformed into an equivalent minimum cost submodular coverage problem by constructing a non-negative and monotonically non-decreasing submodular function. Furthermore, an efficient polynomial-time greedy algorithm is designed, and the approximation ratio performance of the proposed algorithm is analyzed. Finally, through extensive simulation experiments, the proposed algorithm is compared with three other baselines from multiple dimensions such as changes in the number of sensor devices, the number of charging stations, battery capacity, charging scheduling period, per-time-slot charging service fee, charging power, and various model parameters. The experimental results show that the proposed algorithm reduces charging cost by at least an average of 14.6%, 12.4% and 17.1% respectively, verifying the superior performance of the proposed algorithm.

       

    /

    返回文章
    返回