基于进化计算的RFID网络规划研究

作     者：刘嘉豪 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：刘静;任媛媛

授予年度：2020年

学科分类：1305[艺术学-设计学（可授艺术学、工学学位）] 13[艺术学] 081104[工学-模式识别与智能系统] 08[工学] 0804[工学-仪器科学与技术] 081101[工学-控制理论与控制工程] 0811[工学-控制科学与工程] 

主      题：无线射频网络 多目标进化算法 差分进化 并行计算 PSO算法 

摘      要：近些年,RFID网络因其具有工作环境要求低、成本低、投放方便等优点,得到了学术界广泛关注,并且已经在商业、工业、军事等方面大量应用,而RFID网络规划问题则是研究的重中之重。RFID网络因其标签、阅读器的运动状态不同,分为静态网络和动态网络,由于阅读器的扫描读取范围有限,因此设计合理的阅读器部署策略成为了研究热点。RFID网络规划的目的就是通过算法找到合适的部署策略,使RFID网络在覆盖率、总成本、干扰、负载平衡等方面均取得优秀的性能。很多有效的RFID网络规划算法被提出,然而大多数研究都是对已有的优化算法套用,忽略了与RFID网络自身特点的结合。此外,大多数已有的方法使用了进化算法,但并未试图解决在大规模RFID网络规划问题上进化算法耗时严重的缺点。本论文一方面设计了一个基于多目标优化的静态RFID网络规划算法,并将其并行化设计以解决大规模问题下耗时严重的缺点;另一方面结合动态RFID网络的特点设计了一个基于粒子群算法的动态RFID网络规划算法,主要工作总结如下:基于分解的多目标自适应差分进化RFID网络规划:进化算法因其对目标函数无要求、鲁棒性强、自适应强、具有自学习等特点,已被广泛应用在优化问题上,而基于分解的多目标进化算法则具有较低计算复杂度、较好的多样性、精准度高等特点。本文将基于分解的多目标进化算法应用于静态RFID网络规划,并结合静态RFID网络自身特点进行改进,提出了一种基于分解的多目标自适应差分进化RFID网络规划算法(Decomposition-based Multi-objective Self-adaptive Differential Evolution Algorithm for RFID Network Planning,MOSDE/D)。设计了独特的编码方式、改进的种群初始化策略、自适应差分进化及拥挤距离排序策略。在不同类型、不同规模的静态RFID网络实例上进行了大量实验,结果表明MOSDE/D算法能够设计出性能优秀的部署策略。与已有两个算法的对比显示了其更好的规划性能。基于粗粒度模型的并行MOSDE/D算法:RFID网络规划算法属于优化问题,绝大多数方法均采用了进化算法,却很少有研究解决基于进化算法的方法在大规模RFID网络规划问题上耗时严重的问题,而在实际应用中大规模的RFID网络又是随处可见的,因此解决RFID网络规划算法在大规模网络规划上的耗时问题是十分重要且有现实意义的。我们将基于粗粒度模型的并行设计与MOSDE/D算法结合,提出了基于粗粒度模型的并行MOSDE/D算法(Parallel Decomposition-based Multi-objective Self-adaptive Differential Evolution Algorithm for RFID Network Planning,PMOSDE/D),并应用于大规模静态RFID网络规划问题上。设计了子种群划分算法、独特的拓扑结构、“移民迁移策略。在不同类型的大规模静态RFID网络实例的测试中,PMOSDE/D表现出了优越的规划性能,与MOSDE/D算法的对比显示出其并行设计所带来的明显的加速性能。基于多种群PSO的动态RFID网络规划:动态RFID网络相对于静态RFID网络属于较新的研究方向,大多数研究都将研究集中在设计阅读器或标签读取协议来解决标签移动带来的“碰撞问题,却鲜有从问题源头出发,针对动态RFID网络特点设计动态规划算法的研究。因此,我们将基于多种群的动态进化优化方法和动态RFID网络特点相结合,提出了基于多种群PSO的动态RFID网络规划算法(Multi Population-based Particle Swarm Optimization for dynamic RFID Network Planning,PSOMP)。设计了动态自适应目标函数、感知与响应策略、动态PSO速度算子和排斥操作。在动态RFID网络实例上与已有方法进行了对比实验,结果表明PSO-MP具有很好的动态规划能力。