无线可充电传感器网络高效在线充电算法

EFFICIENT ONLINE CHARGING ALGORITHM IN WIRELESS RECHARGEABLE SENSOR NETWORKS

在无线可充电传感器网络中,传感器节点的电池寿命是决定整个传感器网络生命周期的重要因素之一,而移动充电车可有效地为传感器节点提供电量补给。在动态请求(On-Demand)的无线可充电传感器网络中,研究充电车移动耗能和充电周期内总电量两个约束条件下的充电传感器数量最大化问题。针对该问题建立非线性整型数学模型,并提出一个基于贪心策略的在线算法。该算法在每个充电周期内,充电车依次选择距离最近的传感器节点进行充电。基于聚类思想,提出另一个在线算法。该在线聚类算法利用解决旅行商问题的最小生成树算法,使得充电车在每一个类中的充电路径构成一条回路的同时,减少移动耗能。实验结果表明,在线贪心算法、在线聚类算法得出的充电传感器数量分别占充电请求总数的67%与76%。

In wireless rechargeable sensor networks (WRSNs), battery capacity of sensor node is one of the dominate factors which affects the lifetime of WRSNs. Mobile charging vehicle can effectively supply electricity for sensor nodes. This paper tried to maximize the number of charged sensors in the on-demand WRSNs, with constraints of the moving energy consumption of the mobile charger and total amount of energy supply in the charging cycle. We established a non-linear integer mathematical model and proposed an online algorithm based on greedy strategy. Charging vehicles selected the nearest sensor nodes to charge in the charging period. Based on clustering thought, another online algorithm was proposed in this study. The online clustering algorithm used an MST algorithm which was initially used to solve the traveling salesman problem, so as to make the charging path of the charging vehicle in each class form a circuit and reduce the mobile energy consumption. The experimental results show that the number of charging sensors obtained by online greedy algorithm and online clustering algorithm account for 67% and 76% of the total number of charging requests respectively.