摘要
为在无线可充电传感器网络中部署尽量少的充电器实现充电代价最小化,根据传感器节点的位置关系和拓扑特征设计2种无线充电器位置优化算法:近似算法与聚类分区算法。采用分割技术将网络划分成若干个网格的形式,分别求解每个网格内最少充电器数目,并通过移位策略减少充电器数目,提出近似比为(1+ε)的近似算法。同时,采用贪心思想进行聚类分区,结合最小包围圆算法提出聚类分区算法。复杂度分析与仿真结果表明,2种算法都能准确求解出充电器的位置,其中聚类分区算法部署的充电器数目更少,并且时间复杂度更低。
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.
作者
王志方
郑霖
李晓记
WANG Zhifang;ZHENG Lin;LI Xiaoji(School of Information and Communication, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China;Guangxi Experiment Center of Information Science, Guilin, Guangxi 541004, China)
出处
《计算机工程》
CAS
CSCD
北大核心
2018年第5期83-87,93,共6页
Computer Engineering
基金
国家自然科学基金(61362006
61571143
61371107)
广西自然科学基金(2014GXNSFBA118288)
广西信息科学实验中心基金"基于信息融合的室内智能定位关键技术研究"(PT1604)
关键词
无线可充电传感器网络
充电器部署
非均匀分布
近似算法
分区算法
Wireless Rechargeable Sensor Network （WRSN）
charger deployment
non-uniform distribution
approximation algorithm
partitioning algorithm
