摘要： 为在无线可充电传感器网络中部署尽量少的充电器实现充电代价最小化,根据传感器节点的位置关系和拓扑特征设计2种无线充电器位置优化算法:近似算法与聚类分区算法。采用分割技术将网络划分成若干个网格的形式,分别求解每个网格内最少充电器数目,并通过移位策略减少充电器数目,提出近似比为(1+ε)的近似算法。同时,采用贪心思想进行聚类分区,结合最小包围圆算法提出聚类分区算法。复杂度分析与仿真结果表明,2种算法都能准确求解出充电器的位置,其中聚类分区算法部署的充电器数目更少,并且时间复杂度更低。

关键词: 无线可充电传感器网络, 充电器部署, 非均匀分布, 近似算法, 分区算法

Abstract: In order to minimize the charging cost in wireless sensor networks,two wireless charger location optimization algorithms are designed according to the location and topological features of sensor nodes:approximate algorithm and cluster partitioning algorithm.The segmentation technology is used to divide the network into several grids.The minimum number of chargers in each grid is solved separately.The number of chargers is reduced by the shift strategy,and an approximation ratio approximation (1+ε)algorithm is obtained.At the same time,the greedy thought is adopted to cluster the clusters,and the clustering partitioning algorithm is proposed based on the least enclosing circle algorithm.Complexity analysis and simulation results show that both algorithms can effectively solve the position of the charger and are superior to other algorithms.The clustering partitioning algorithm has fewer number of chargers and lower time complexity.

Key words: Wireless Rechargeable Sensor Network(WRSN), charger deployment, non-uniform distribution, approximation algorithm, partitioning algorithm

中图分类号: 

• TP393