Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (3): 793-798.DOI: 10.11772/j.issn.1001-9081.2019071201

• Network and communications • Previous Articles     Next Articles

Wireless sensor deployment optimization based on improved IHACA-CpSPIEL algorithm

DUAN Yujun1, WANG Yaoli1, CHANG Qing1, LIU Xing2   

  1. 1. College of Information and Computer, Taiyuan University of Technology, Taiyuan Shanxi 030024, China;
    2. Network Center, 32152 Troops, Shijiazhuang Hebei 050000, China
  • Received:2019-07-10 Revised:2019-10-11 Online:2020-03-10 Published:2019-10-25
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China(61828601), the Natural Science Foundation of Shanxi Province(201801D121141).

改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化

段宇君1, 王耀力1, 常青1, 刘鑫2   

  1. 1. 太原理工大学 信息与计算机学院, 太原 030024;
    2. 32152部队 网络中心, 石家庄 050000
  • 通讯作者: 常青
  • 作者简介:段宇君(1993-),女,山西太原人,硕士研究生,主要研究方向:无线传感器布局;王耀力(1965-),男,山西太原人,副教授,博士,主要研究方向:智能感知与架构、人机视觉处理与分析;常青(1975-),男,河南洛阳人,副教授,博士,主要研究方向:人机视觉处理与分析、嵌入式电路设计;刘鑫(1988-),男,山东淄博人,硕士,主要研究方向:无线通信。
  • 基金资助:
    国家自然科学基金资助项目(61828601);山西省自然科学基金资助项目(201801D121141)。

Abstract: Aiming at the problems of low coverage and high communication cost for wireless sensor deployment, an Improved Heuristic Ant Colony Algorithm (IHACA) merging Chaos optimization of padded Sensor Placements at Informative and cost-Effective Locations algorithm (IHACA-CpSPIEL) method for sensor deployment was proposed. Firstly, the correlation between observation points and unobserved points was established by mutual information, and the communication cost was described in the form of graph theory to establish the mathematical model with submodularity. Secondly, chaos operator was introduced to improve the global searching ability of pSPIEL (padded Sensor Placements at Informative and cost-Effective Locations) algorithm for local parameters, and then the optimal number of clusters was found. Then, the factors of the colony distance heuristic function and the pheromone updating mechanism were changed to jump out of the local solution of communication cost. Finally, Chaos optimization of pSPIEL algorithm (CpSPIEL) was integrated with the IHACA to determine the shortest path, so as to achieve the purpose of low-cost deployment. The experimental results show that the proposed algorithm can jump out of the local optimal solution well, and the communication cost is reduced by 6.5% to 24.0% compared with the pSPIEL algorithm, and has a faster search speed.

Key words: wireless sensor, sensor deployment, communication cost, padded Sensor Placements at Informative and cost-Effective Locations (pSPIEL), chaotic operator, Ant Colony Algorithm

摘要: 针对无线传感器布局存在覆盖率低、通信成本高等问题,提出一种基于改进蚁群算法(IHACA)的融合混沌优化pSPIEL算法(IHACA-CpSPIEL)的传感器布局方法。首先,采用互信息量建立观测点与未观测点间相关性,并以图论形式对通信成本进行描述,建立具有子模性的数学模型;其次,引入混沌算子以提高pSPIEL算法局部性参数的整体搜索能力,进而找到最优分簇个数;然后,更改蚁群距离启发函数因子及信息素更新机制以跳出通信成本局部解;最后,将基于混沌优化的pSPIEL (CpSPIEL)与IHACA融合以确定出最短路径,从而实现低成本部署的目的。实验结果表明,该算法能够较好地跳出局部最优解,且通信成本比pSPIEL算法减少了6.5%~24.0%,具有更快的搜索速度。

关键词: 无线传感器, 传感器布局, 通信成本, pSPIEL, 混沌算子, 蚁群算法

CLC Number: