通信学报 ›› 2015, Vol. 36 ›› Issue (6): 94-104.doi: 10.11959/j.issn.1000-436x.2015152

• 学术论文 • 上一篇    下一篇

基于量子遗传算法的无线视频传感网络优化覆盖算法

樊富有1,2,杨国武1,乐千桤1,吕凤毛1,赵超1   

  1. 1 电子科技大学 计算机科学与工程学院,四川 成都 611731
    2 宜宾学院 计算机与信息工程学院,四川 宜宾 644000
  • 出版日期:2015-06-25 发布日期:2017-05-11
  • 基金资助:
    国家自然科学面上基金资助项目;四川省科技厅基础研究计划基金资助项目;四川省教育厅重点基金资助项目

Optimized coverage algorithm of wireless video sensor network based on quantum genetic algorithm

Fu-you FAN1,2,Guo-wu YANG1,Qian-qi LE1,Feng-mao LV1,Chao ZHAO1   

  1. 1 School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China
    2 School of Computer and Information Engineering,Yibin University,Yibin 644000,China
  • Online:2015-06-25 Published:2017-05-11

摘要:

针对智慧城市无线视频传感网络建设需要,提出一种基于量子遗传算法的网络优化覆盖算法。算法面向复杂的监视区场景,监视区中存在形状各异的障碍物,各区域的重要程度不同。以二维离散网格模型描述监视区场景,用编码描述矩阵表示监视区域,用七元组描述有向无线视频传感器。通过严格的数学推导得出了问题的数学规划模型。优化覆盖算法由IntialDeployment算法和OptimizedDeployment算法2部分组成,以获得最大有效覆盖率的网络部署方案为求解目标。采用量子遗传算法搜索解空间,通过合理编码染色体,优化量子旋转门参数,使算法的运算速度快,收敛性好。引入理想覆盖率和理想加权覆盖率2个极限值,采用相对比较法评判算法优劣。仿真实验和数据分析表明,算法获得的方案能很好地逼近理想极限值。在传感器节点数给定的情况下,算法能获得最大的覆盖率。

关键词: 无线视频传感网络, 有向感知模型, 量子遗传算法, 优化覆盖算法, 理想覆盖率

Abstract:

According to the construction needs of the smart city wireless video sensor network,an optimized network coverage algorithm based on quantum genetic algorithm is proposed.The algorithm fits in with complicated monitoring scene which has some different obstacles and different degree of importance.The monitoring region is depicted by two-dimensional discrete grid model,and the discrete grid model is represented by a code description matrix.The directional wireless video sensor is described by a seven-tuples.The mathematical programming model of the coverage problem is obtained by strict mathematical derivation.The optimized coverage algorithm is comprised by IntialDeployment and OptimizedDeployment algorithms,which takes the maximum coverage rate network deployment scheme as the solving goal.The quantum genetic algorithm with reasonable chromosome coding and optimized quantum rotation gate parameter is used to search the solution space,which has a good convergence rate and a fast computation speed.Two limit values of ideal coverage rate and ideal weighted coverage rate are introduced to evaluate the algorithm by the way of relative comparison.The result of simulation experiments and data analyses show that the solutions worked out by the algorithm can well approximate the ideal limit value.When the number of sensor nodes is given,the algorithm can obtain the maximum effective coverage rate.

Key words: wireless video sensor network, directional sensing model, quantum genetic algorithm, optimized coverage algorithm, ideal coverage rate