基于速度差分变异粒子群的RFID网络优化

吴 琼，纪志成，吴定会

（江南大学 物联网工程学院，江苏 无锡214122）

0 引 言

RFID 网络规划问题可描述为在工作区域内部署m 个读写器读取n 个电子标签信息。合理的RFID 网络规划不仅可以提高网络的覆盖质量，还可以提高网络的成本效率，保证 网络的连通 质量［1－3］。

目前，针对RFID 网络规划即优化部署问题已有一定的研究，文献 ［4］利用混沌原理优化粒子群算法，以提高网络覆盖率为目标，对RFID 与WSNs集成网络智能节点的部署进行优化。文献 ［5］将遗传算法与粒子群算法相结合，利用两种算法并行优化的方式实现RFID 网络中读写器的合理部署。文献 ［6］利用改进粒子群算法，根据工作区域内电子标签的实际数量与位置分布，动态调整读写器个数，减少区域内读写器的冗余。文献 ［7］以加强网络覆盖率和降低网络成本为目标，采用一种禁忌搜索算法对带有容量约束的读写器部署模型进行优化。文献 ［8］将遗传算法变异机制引入到粒子群算法中，提出了一种带变异机制的粒子群优化算法，以提高读写器对电子标签的覆盖率，降低信号间的干扰为目标，对RFID 网络进行优化部署。上述文献的研究都取得了可观的结果，但都未考虑到RFID网络实际的经济效益。

粒子群算法具有收敛速度快，搜索精度高，操作简单，易实现等优点，但在进化后期算法易陷入局部最优解，不能保证找到全局最优解。因此本文将差分变异思想引入到粒子群算法中，提出了一种利用差分算法进一步优化粒子群算法的速度差分变异粒子群算法，并将其应用到优化RFID网络规划中，在保证网络负载平衡的前提下，提高网络中读写器对电子标签的覆盖率和网络经济效益。

1 网络优化模型

在实际应用中，RFID 网络规划不仅要保证目标区域内读写器对电子标签的覆盖率达到要求，同时要降低读写器与读写器之间干扰，降低网络成本，提高网络的经济效益。因此RFID 网络模型应同时满足以下3个方面的问题：

（1）读写器对标签的覆盖：在RFID 网络规划中，读写器对标签的覆盖问题是首要问题，要尽可能的保证读写器的高覆盖率，减少网络设备成本，RFID 网络覆盖率性能指标表示如下

式中：n——目标区域内电子标签的个数，Ci——电子标签i的覆盖情况，当标签i被一个或多个读写器覆盖时，Ci＝1，否则Ci＝0。

（2）网络经济效益：为了提高网络的经济效益，读写器应尽可能部署在电子标签密集区域，该性能指标可用下式表示

式中：m——目标区域内读写器的个数，di——第i个读写器距离标签密集区域的距离，f2越大，网络经济效益越高。

（3）网 络 负 载 平 衡［9］：RFID 网 络 负 载 平 衡 问 题 是RFID 网络规划的必备问题，网络中读写器的负载分布情况关乎网络的使用寿命和稳定性，是RFID 网络规划的一个重要组成部分，该性能指标可如下表示

式中：ki——读取i电子标签的读写器的个数，通过均衡每个读写器读取的电子标签数量来达到RFID 读写器网络负载均衡的目的，f3越大，网络负载分配的越均衡。

为了同时满足上述3个优化目标，采用加权和的方式，将上述多目标问题转换成单目标问题进行求解，因此RFID网络规划问题的优化目标函数可表示为

其中，w1＋w2＋w3＝1，w1，w2和w3分别表示覆盖率、网络经济效益和负载平衡的权重，其大小表示实际工程应用中RFID 网络规划部署的具体要求。

2 算法描述

2.1 算法基本思想

（1）粒子群 （PSO）算法M 个粒子构成的种群在D 维的工作区域内飞行搜索，每个粒子是待求解问题的一个解决方案，解的优劣由求解问题的目标函数决定。所有粒子在工作区域内以一定的速度飞行并不断追寻群体中的最优粒子，直至达到终止条件或找到满意解为止，粒子i在t次迭代后的状态如下所示：

位置：xi＝ （xi1，xi2，…，xiD），xid∈ ［a，b］其中a、b分别表示工作区域上、下界；

速度：vi＝ （vi1，vi2，…，viD），vid∈ ［vmin，vmax］其中vmin、vmax分别粒子运动的最小、最大速度；当前个体最优位置：pi＝ （pi1，pi2，…，piD）；当前种群最优位置：pg＝ （pg1，pg2，…，pgD）；其中1≤d≤D，1≤i≤M。

第t＋1次迭代后，粒子i速度和位置的更新机制如下所示［4］

式中：t——当前迭代次数，T——算法总的迭代次数，wmax、wmin——惯性权重的最大和最小值。

粒子群算法具有记忆搜索过程中的个体最优解和种群最优解的能力，并通过个体和种群最优解以及本身状态指导粒子下一步的寻优过程，算法搜索速度快，搜索精度高。但在进化后期，粒子都趋于最优解，种群多样性降低，算法易陷入局部最优解。

（2）差分进化算法：差分进化（DE）算法是一种基于群体差异的全局并行搜索算法［11，12］。其基本思想是，与粒子群算法相似，随机产生一个初始群体，对该群体中的个体按照一定规则进行变异、交叉和选择操作，不断地迭代计算，根据群体内各个体的适应值，优胜劣汰，引导搜索过程向群体内最优解逼近。DE算法在种群进化前期寻优能力强，搜索速度快，稳健；算法可记忆个体最优解，通过粒子的交叉和变异操作有效保持种群的多样性，从而保证全局最优。

（3）速度差分变异粒子群 （VDM－PSO）算法 为了改进粒子群算法寻优后期进化停滞现象，本文将差分变异思想引入到粒子群算法中，取长补短，提出了一种带压缩因子和惯性权重的速度差分变异粒子群优化算法，在保证算法前期收敛速度和后期搜索精准性的前提下，增强算法邻域搜索能力和进化后期种群多样性，提高算法进化后期的寻优速度和寻优能力，保证全局最优解的获取。粒子速度差分变异公式定义如下

其中：k表示粒子的任一维度，以保证粒子至少有一个维度的速度发生了变异；r表示 ［0，1］间的随机数；CR 为粒子变异概率即交叉因子。F 表示变异因子，为 ［0，2］之间的一个常数。v1d，v2d为vi中随机选取的两个粒子d维的速度。粒子的变异时机由粒子的进化停滞步数t0确定，当t0大于停滞阈值T0时，粒子开始变异。

2.2 算法设计

以式 （4）为网络规划的优化目标，设计算法的具体步骤如下所示：

（1）初始化种群以及算法运行参数。

（2）根据式 （4）计算种群内各粒子的适应度。

（3）找出群体内每个粒子的个体历史最优解和种群全局最优解。

（4）对种群中的各个粒子，按式 （5）和式 （6）更新速度和位置。

（5）当粒子进化停滞步数大于设定值时，转入步骤（6），否则转入步骤 （9）。

（6）产生一个随机数，若随机数小于变异概率，则对种群内的各粒子进行变异交叉操作；否则转入步骤 （7）。

（7）随机选取群体内粒子的任一维度进行变异交叉操作。

（8）若变异后的粒子适应值优于变异前，则用变异后的粒子取代变异前，否则转入步骤 （6）继续变异，直至成功。

（9）若达到算法的终止条件，则优化过程结束，输出算法获取的最优解，否则转入步骤 （2）继续寻优过程。

算法流程如图1所示。

图1 算法流程

3 实例仿真

3.1 仿真环境及参数设定

本文采用MATLAB7.1仿真软件对RFID 网络中读写器的部署规划进行仿真。读写器的工作区域为30m×30m的正方形，利用9个读写器对该工作区域内随机分布的50个电子标签进行数据采集。粒子种群大小M 为150，搜索空间维数D 为27，算法的最大迭代次数T 为500。当种群进化停滞步数大于设定的停滞阈值时，粒子根据变异条件进行变异和交叉操作。由于在实际应用中RFID 网络中读写器的覆盖区域并非一个理想的圆形，而是一个近似的椭圆形，因此本文采用椭圆模型进行实例仿真，此处取椭圆长轴5m，短轴4m［8］，椭圆的位置、旋转角度由粒子维度分量确定。算法其它仿真参数见表1。

表1 仿真参数

为了验证VDM－PSO 算法在RFID 网络规划部署问题求解上的应用效果，将其优化结果与PSO 算法在相同读写器初始分布下进行了比较，为保证比较结果的公平性，两种算法采用相同的仿真参数。图2为工作区域内读写器的初始分布，其中星形点表示电子标签的位置，空心圆点表示读写器的位置，椭圆区域表示读写器的通信边界。

图2 初始读写器分布

3.2 仿真结果与分析

利用VDM－PSO 和PSO 两种优化算法优化后工作区域内读写器的分布和适应度函数变化曲线分别如图3 和图4所示。

图3 读写器分布对比

图4 适应值对比

由图3可以看出，VDM－PSO 算法较PSO 算法可以获得更好的标签覆盖率，且在标签密集区域，采用VDM－PSO算法优化后，各读写器读写区域重叠减少，网络的负载更为均衡，网络的经济效益更高。对比两种算法的适应度函数曲线，可以看到，两种算法都具有很快的收敛速度，但VDM－PSO 算法能够避免早熟问题，及时跳出局部极点，防止算法陷入局优，如图4所示，PSO 算法在迭代初步即陷入局优，寻优结果不佳，相比PSO 算法，VDM－PSO 算法适应值曲线的跳变为粒子过早收敛时，采用差分原理对粒子进行变异交叉操作，有效保持了粒子群体的多样性，从而摆脱局部极点的束缚，增强了粒子的邻域搜索能力，保证全局最优解的获取。

为了进一步验证VDM－PSO 算法在RFID 网络规划方面的性能，在不同初始读写器分布情况下，将两种算法分别运行10次［13］，优化后的平均最优适应值，达到最优适应值的迭代次数和读写器平均移动距离对比见表2。

表2 10次独立优化性能对比

由表2可知，VDM－PSO 算法的平均最大适应值和读写器的平均移动距离显著优于PSO 算法，提高了网络优化效果，同时降低了因读写器移动带来的能量消耗，降低了网络成本，提高了网络总体经济效益，说明了该算法在求解网络规划问题上的有效性。由于VDM－PSO 算法在进化停滞时加入了速度差分变异、交叉操作，使得算法陷入局部最优时能够及时跳出，增强了算法的全局与邻域搜索能力，保证全局最优，也因此算法达到最大适应值的迭代次数相比PSO 算法要高，但仍具有较快的收敛速度。

4 结束语

本文针对RFID 网络读写器的优化部署问题，建立多目标网络优化部署模型，提出一种基于速度差分变异粒子群的RFID 网络优化算法。利用差分算法对粒子群算法速度更新机制进行改进，提高进化后期种群的多样性，增强算法的邻域搜索能力，有效防止算法陷入局部最优解，保证全局最优解。仿真实验结果表明，该算法在提高RFID网络覆盖率，加强网络负载平衡和增加网络经济效益方面，显著优于标准粒子群算法，能够有效实现RFID 网络资源的合理分布。但该算法在求解较大规模的RFID 网络规划问题方面的有效性还有待进一步的研究与验证。

［1］Kranzfelder Michael，Schneider Armin，Fiolka Adam，et al.Real－time instrument detection in minimally invasive surgery using radiofrequency identification technology ［J］.Journal of Surgical Research，2013，185 （2）：704－710.

［2］Hinkka Ville，Tatila Jaakko.RFID tracking implementation model for the technical trade and construction supply chains［J］.Automation in Construction，2013，35 （1）：405－414.

［3］Xu Zhitao，Ming X G，Zhou Jingling，et al.Management optimisation based on dynamic SKU for RFID－enabled warehouse management in the steel supply chain ［J］.International Journal of Production Research，2013，51 （10）：2981－2996.

［4］JI Zhicheng，ZHANG Yunya.Optimization of the integrated networks based on chaos particle swarm algorithm ［J］.Control Engineering of China，2012，19 （5）：737－739 （in Chinese）.［纪志成，张云亚.基于混沌粒子群算法的集成网络优化 ［J］.控制工程，2012，19 （5）：737－739.］

［5］Chiu Chuiyu，Ke Chenghsin，Chen K Y.Optimal RFID net－works scheduling using genetic algorithm and swarm intelligence［C］／／Proc of the IEEE International Conference on System，Man，and Cybernetics，2009：1201－1208.

［6］Gong Yuejiao，Shen Meie，Zhang Jun，et al.Optimizing RFID network planning by using aparticle swarm optimization algorithm with redundant reader elimination ［J］.IEEE Transactions on Industrial Informatics，2012，8 （4）：900－912.

［7］WANG Yonghua，YANG Jian，ZHAN Yiju，et al.RFID networks planning based on tabu search algorithms［J］.Application Research of Computers，2011，28 （6）：2116－2119 （in Chinese）.［王永华，杨健，詹宜巨，等.一种基于禁忌搜索的RFID读写器部署算法 ［J］.计算机应用研究，2011，28（6）：2116－2119.］

［8］FENG Han.RFID systems optimization deployment research and application ［D］.Shanghai：Donghua University，2013：18－37 （in Chinese）.［冯晗.RFID 系统优化部署研究与应用［D］.上海：东华大学，2013：18－37.］

［9］Chen Hanning，Zhu Yunlong.RFID networks planning using a multi－swarm optimizer ［C］／／Proc of Chinese Control and Descision Conference.Piscataway.NJ：IEEE Press，2009：3548－3552.

［10］Li Yanliang，Shao Wei，You Long，et al.An improved PSO algorithm and its application to UWB antenna design ［J］.IEEE Antennas and Wireless Propagation Letters，2013，12：1236－1239.

［11］Mandal KK，Chakraborty N.Differential evolution techniquebased short－term economic generation scheduling of hydrothermal systems ［J］.Electric Power Systems Research，2008，78 （11）：1972－1979.

［12］YANG Yan，CHEN Ruqing，YU Jinshou.Study on differential evolution－particle swarm optimization based hybrid optimization algorithm and its application［J］.Computer Engineering and Applications，2010，46 （25）：238－241（in Chinese）. ［杨妍，陈如清，俞金寿.差分进化粒子群混合优化算法的研究与应用［J］.计算机工程与应用，2010，46 （25）：238－241.］

［13］LIU Weiting，FAN Zhouyuan.Based on chaotic particle swarm optimization of wireless sensor network coverage ［J］.Computer Applications，2011，31 （2）：338－341 （in Chinese）.［刘维亭，范洲远.基于混沌粒子群算法的无线传感网络覆盖优化 ［J］.计算机应用，2011，31 （2）：338－341.］