基于改进粒子群算法的RFID网络系统的优化
刘快，沈艳霞，纪志成
(江南大学 物联网工程学院，江苏 无锡，214122)
摘要：针对如何有效地放置阅读器，使得阅读器可以同时读取多个标签信息的问题，提出一种基于遗传算法(GA)和粒子群算法(PSO)的改进的粒子群算法GA-PSO。通过仿真，将改进的粒子群算法GA-PSO与遗传算法、粒子群算法进行比较，体现出GA-PSO的优越性。
关键词：RFID网络；遗传算法；粒子群算法；改进的粒子群算法；优化
中图分类号：TN92 文献标志码：A 文章编号：1672-7207(2011)S1-0900-05
RFID network optimization based on
improved particle swarm optimization algorithm
LIU Kuai, SHEN Yan-xia, JI Zhi-chen
(School IOT Engineering, Jiangnan University, Wuxi 214122, China)
Abstract: An improved particle swarm optimization (GA-PSO) algorithm based on genetic algorithm(GA) and particle swarm optimization (PSO) algorithm was proposed to solve the problem how to place readers so that the readers can effectively get the information of multiple tags. The performances of the GA-PSO algorithm were compared with GA and PSO. The results indicate that the GA-PSO algorithm is more effective.
Key words: RFID network; genetic algorithm (GA); particle swarm optimization (PSO); improved particle swarm optimization algorithm; optimization
Radio Frequency Identification(RFID)射频识别是一种非接触式的自动识别技术，它通过射频信号自动识别目标对象并获取相关数据。RFID技术无需人工干预，可以工作于各种恶劣环境，且避免接触，操作方便[1-3]。RFID主要是由电子标签、阅读器、天线和上位机系统组成。电子标签和阅读器之间通过无线射频技术进行非接触双向数据传输，必要时将信息传到上位机系统。
RFID网络系统具有异构、随机部署、自组织、网络节点资源有限、网络拓扑经常发生变化、可扩展性、成本低、标签的计算能力和能量有限、环境复杂等特点。RFID网络规划不仅要要求网络比较节能，而且对网络的覆盖质量和连通性也有一定的要求[4-6]。本文作者提出了用遗传算法同粒子群算法相结合的改进的粒子群算法来优化网络资源的分布，使得阅读器有较高的读取率。
1 算法介绍
1.1 遗传算法的基本思想
遗传算法(GA)的基本思想是模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量(染色体)，染色体群一代代不断进化，包括复制、交叉和变异等操作，通过不断计算各染色体的适应值，选择最好的染色体，获得最优 解[7]。具体实现步骤如下[8]。
步骤1：产生初始种群。设定的参数有种群规模、最大迭代次数N、变量个数、交叉概率pc、变异概率pm。
步骤2：将染色体群中每个染色体串代入适应度函数，计算适应值。
步骤3：判断是否满足终止条件，若满足，则适应值最大的染色体对应的候选解就是需要的解；否则，转入步骤4。
步骤4：重复下列步骤，直至产生了n个后代为止。
(a) 在当前的染色体群中随机选取2个染色体作为父本，选取染色体的概率函数应该是适应值的增函数。在选取父本的过程中，一个染色体可以被多次选中。
(b) 对于选中的父本，按照交叉概率pc决定是否交叉产生2个新的后代，发生交叉的位置是随机的，每个位置的概率是相同的。如果不发生交叉，则2个后代是对2个选中的父本进行严格复制的结果。
(c) 对于产生的2个后代，分别在每个位置上按照变异概率pm发生变异，将2个后代放入新的染色体群中。
如果n是奇数，可以随机地放弃一个新的后代。
步骤5：生成n个新的染色体后，用新的染色体群代替原来的染色体群。
步骤6：转向步骤2。
1.2 粒子群算法的基本思想
粒子群(PSO)算法源于对鸟类捕食行为的研究，一群鸟在随机搜索食物，如果这个区域里只有一块食物，那么找到食物的最简单有效的策略就是搜寻目标离食物最近的鸟的周围区域。PSO算法就是从这种模型中得到启示而产生的，并用于解决优化问题[9-11]。PSO中，一个群体可以看做由m个粒子组成，在D维搜索空间中以一定的速度飞行。每个粒子在搜索时，考虑到了自己搜索到的历史最好点和群体内其他粒子的历史最好点，在此基础上进行位置(状态，即解)的变化。第i个粒子的位置表示为Xi=(xi1, xi2, …, xiD)，第i个粒子的速度表示为Vi=(vi1, vi2, …, viD)，第i个粒子经历的历史最好点表示为Pi=(pi1, pi2, …, piD)，群体内所有粒子经过的最好的点表示为Pg=(pg1, pg2, …, pgD)。粒子的速度和位置按照下式进行变化[12]：
(1)
(2)
其中：w称为惯性权重，其值决定了对粒子当前速度继承的程度，合适的惯性权重可以使粒子具有均衡的探索能力和开发能力；c1和c2为学习因子或加速系数，一般为常数。学习因子具有自我总结和向群体中优秀个体学习的能力，从而向自己的历史最优点以及群体内的历史最优点靠近；rand( )为[0,1]的随机数。
为了使粒子在搜索过程中加大全局搜索能力，并避免粒子陷入局部最优解，按照文献[13]中的方法设计惯性权重因子为：
其中：N为最大迭代次数；i为当前迭代次数。
1.3 改进的粒子群算法
常规的PSO算法中，粒子的历史最优解的确定相当于一种隐含的选择机制，这种选择机制可能通过较长时间才能发生作用，而传统的的GA中的选择策略可以将搜索定向于较好的区域，合理地分配有限的资源。常规的PSO的初始解是随机的，如果初始解不好，需要很多次迭代才能到达最优解，而采用GA中的选择机制，选出一个较好的解，再利用PSO的优化方法使得要求解的解更优，有效地寻找到最优解。为了使粒子在飞行的时候尽可能在可行域内，对粒子的最大飞行速度限制为vmax。具体实现步骤如下。
步骤1：初始化粒子的位置，并设定参数。
步骤2：判断是否满足按GA选择的终止条件，若不满足，进入步骤3。
步骤3：计算每个个体的适应值。
步骤4：在规定的较小的迭代次数中选择适应值最大的粒子作为粒子群算法的初始解。
步骤5：初始化粒子的速度，并取步骤4中的解作为粒子的初始位置及个体历史最佳位置。
步骤6：计算每个粒子的适应值。
步骤7：对每个粒子，将其适应值与所经历的最好位置的适应值进行比较，若更好，则用当前位置更新个体历史最好位置。
步骤8：对每个粒子，将其历史最优适应值与群体领域内所经历的最好位置的适应值进行比较。若更好，则将其作为当前的全局最好位置。
步骤9：根据式(1)和(2)对粒子的位置和速度进行更新。
步骤10：若未达到PSO的终止条件，则转入步骤6。
2 实例仿真
2.1 GA-PSO算法的仿真结果
使用MATLAB 7.1对RFID网络进行仿真。在30 m×30 m的区域内，随机分布50个RFID电子标签，使用9个阅读器对RFID网络中的标签进行数据采集。设电子标签和阅读器之间的通信及能量感应方式为电磁反向散射耦合，工作频率为433 MHz，设阅读器的感知范围为圆形[14]，取感知半径R=5 m[15]。参数如下表1所示。
表1 参数设定
Table 1 Parameters setting
运行15次取平均值的仿真结果[16-17]。图1所示为GA-PSO算法对RFID网络的优化仿真。
2.2 与其他算法的比较
为了进一步验证GA-PSO算法的有效性，将本算法分别与GA和PSO算法进行比较。图2所示为GA对RFID网络的优化仿真结果，图3所示为PSO对RFID网络的优化仿真结果。
当阅读器的个数分别取不同值时，3种算法分别运行15次，得到的平均最优的覆盖率及迭代次数如表2所示。
从仿真结果可以看出：在相同的条件下，GA-PSO的覆盖率最大或者迭代次数最少，即GA-PSO的优化效果最好。由于粒子群算法的迭代次数与粒子的初始位置密切相关，先通过遗传算法找到较好的位置，再用粒子群算法做进一步的优化，所以，迭代次数明显减少。
图1 GA-PSO算法对RFID网络的优化
Fig.1 RFID network optimization for GA-PSO algorithm
图2 GA对RFID网络的优化
Fig.2 RFID network optimization for GA
图3 PSO对RFID网络的优化
Fig.3 Network optimization for PSO algorithm
表2 不同算法的覆盖率及迭代次数
Table 2 Coverage and iterations of different algorithms
3 结论
(1) 基于遗传算法和粒子群算法的思想，提出一种将遗传算法同粒子群算法结合起来的优化算法，首先用GA找到较好的解，再将其作为PSO算法的初始解，从而减少了PSO的迭代次数，使最优解快速收敛。
(2) 通过仿真结果，并与其他算法相比较，说明该算法的有效性和优越性。特别是对优化控制的时间要求比较严格的系统，GA-PSO算法更有实用意义。
参考文献：
[1] Decker C, Kubach U, Beigl M. Revealing theretail black box by interaction sensing[C]//Rhode Island: Proceedings of the ICDCS 2003. Providence, 2003: 328-333.
[2] Kim D S, Shin T H, Park J S. A security framework in RFID multi-domain system[C]//IEEE International Conference on Availability. Reliability and Security: ARES, 2007: 1227-1234.
[3] 游战清, 李苏剑. 无线射频识别技术(RFID)理论与应用[M]. 北京: 电子工业出版社, 2004: 50-62.
YOU Zhan-qing, LI Su-jian. Wireless RFID theory and application[M]. Beijing: Electronics Industry Press, 2004: 50- 62.
[4] Want R. An introduction to RFID technology[J]. IEEE Pervasive Computing, 2006, 5(1): 25-33.
[5] Han M K, Paik I W, Lee B H, et al. A framework for seamless information retrieval between an EPC network and a mobile RFID network[C]//IEEE International Conference on Computer and Information Technology. Korea, 2006: 98.
[6] GUAN Qiang, LIU Yu, YANG Yi-ping, et a1. Genetic approach for network planning in the RFID systems[C]//IEEE International Conference on Intelligent Systems Design and Applications. Ji’nan, 2006: 567-572.
[7] Holland J H. Adaptation in natural and artificial system[M]. Ann Arbor: University of Michigan Press, 1975: 93-104.
[8] 李敏强, 寇纪凇, 林丹, 等. 遗传算法的基本理论与应用[M]. 北京: 科学出版社, 2002: 75-79.
LI Min-qiang, KOU Ji-song, LIN Dan, et al. Basical theory and application of GA[M]. Beijing: Science Press, 2002: 75-79.
[9] 魏秀业, 潘宏侠. 粒子群优化及智能故障诊断[M]. 北京: 国防行业出版社, 2010: 32-34.
WEI Xiu-ye, PAN Hong-xia. Optimization of PSO and intelligent fault diagnosis[M]. Beijing: National Defence Industry Press, 2010: 32-34.
[10] Coello C A, Pulido G T, Lechuga M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Transaction on Evolutionary Computation, 2004, 8(3): 256-279.
[11] Pradhan P M, Baghel V, Panda G, et al. Energy efficient layout for a wireless sensor network using multi-objective particle swarm optimization[C]//IEEE Advance Computing Conference. Milan, 2004: 65-70.
[12] 张可村, 李换琴. 工程优化方法及其应用[M]. 西安: 西安交通大学出版社, 2007: 238-250.
ZHANG Ke-cun, LI Huan-qin. Engineering optimization and application[M]. Xi’an: Xi’an Jiaotong University Press, 2007: 238-250.
[13] 汪定伟, 王俊伟, 王洪峰, 等. 智能优化方法[M]. 北京: 高等教育出版社, 2007: 217-226.
WANG Ding-wei, WANG Jun-wei, WANG Hong-feng, et al. Intelligent optimization methods[M]. Beijing: Higher Education Press, 2007: 217-226.
[14] Rahman F. Towards secure and scalable tag search approaches for current and next generation RFID systems[D]. Milwaukee, Wisconsin: Marquette University, 2010: 76-79.
[15] 王永华. 超高频RFID多读写器部署与协调技术研究[D]. 广州: 中山大学信息科学与技术学院, 2009.
WANG Yong-hua. Research on UHF RFID multi-readers deployment and coordination technology[D]. Guangzhou: Sun Yat-sen College. Information of Science and Technology. 2009.
[16] 陈瀚宁, 朱云龙, 胡琨元. 基于多种群共生进化的RFID网络优化[J]. 解放军理工大学学报: 自然科学版, 2008, 9(5): 413-416.
CHEN Han-ning, ZHU Yun-fei, HU Kun-yuan. RFID network optimization based on multi-species coevolution[J]. Journal of PLA University of Science and Technology, 2008, 9(5): 413- 416.
[17] 向西西, 黄宏光, 李予东. 基于粒子群算法的混合无线传感网覆盖优化[J]. 计算机应用研究, 2010, 27(6): 2273-2275.
XIANG Xi-xi, HUANG Hong-guang, LI Yu-dong. Hybird sensor networks coverage-enhancing approach based on partical swarm optimization[J]. Application Research of Computers, 2010, 27(6): 2273-2275.
(编辑 李向群)
收稿日期：2011-04-15；修回日期：2011-06-15
基金项目：中央高校基本科研业务费专项资金资助项目(TUSRP31106)
通信作者：刘快(1988-)，女，陕西咸阳人，硕士，从事无线传感网优化控制研究；电话：15995238690；E-mail：liukuai07@126.com
