摘要
无线传感器网络被广泛应用于军事监视、灾害预测、危险环境勘探等领域。然而,无线传感器的寿命有限,需要频繁更换电池才能维持正常工作,这带来了昂贵的维护成本和极大的不便。近年来,随着无线电力传输技术的发展,无线可充电传感器网络应运而生,为研究提供了新的思路。尽管如此,大多数相关工作仅考虑充电电量对调度的制约,未能体现现实情况下传感器质量不同与紧急任务中时间的重要性。将时间和电量同时作为约束,研究无线可充电传感器网络中异构感知的充电调度问题。首先,以最大化传感器的监控效用为目标,形式化了无线可充电传感器网络中针对异构感知的有限时间下的充电调度问题,并证明了该问题的NP困难性;然后,通过对充电时间离散化,将问题转化为子模最大化问题,并提出了针对转化后问题的近似算法;最后,通过大量的仿真实验验证了该算法的有效性。结果表明所提出的算法可以显著提高监控效用,且有理论支撑该效果与最优值之间的近似比,例如与传统NJNP算法相比,其将监控效用最多提高了279.79%。
Wireless Sensor Networks(WSNs)are widely deployed in various applications,including military surveillance,disaster prediction,and hazardous environment exploration.However,the limited lifespan of wireless sensors necessitates frequent battery replacements,leading to high maintenance costs and significant inconvenience.In recent years,with the advent of wireless power transmission technology,wireless rechargeable sensor networks(WRSNs)have been developed to address these issues,providing new avenues for research.Nonetheless,existing studies typically prioritize charging capacities,underestimating the urgency and heterogeneity of sensors in emergency scheduling.Formally,this paper treats the scheduling task as a constrained optimization problem with the aim to maximizing the monitoring utility for heterogeneous sensors,which has been proven to be NP-hard.Therefore,it converts the problem to sub-modular maximization through the discretization of charging time.This naturally leads to develop approximate algorithms based on a greedy strategy,with theoretical backing for the approximation ratio to the optimal value.Extensive experiments demonstrate that the proposed algorithms can significantly enhance monitoring utility,with the highest improvement reaching 279.79%compared to the classical NJNP algorithm.
作者
李德强
任新一
徐佳
LI Deqiang;REN Xinyi;XU Jia(Advanced Network and Economic Lab,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)
出处
《计算机科学》
北大核心
2025年第6期355-364,共10页
Computer Science
基金
国家自然科学基金(62372249,62272237,62302236,62171217,62272244,62372250)
江苏省自然科学基金(BK20230350)
南京邮电大学引进人才科研启动基金(NY222014)。
关键词
无线可充电传感器网络
移动充电
充电时间离散化
子模函数
近似算法
Wireless rechargeable sensor network
Mobile charging
Discretization of charging time
Submodular function
Approximation algorithm
