冯诺依曼人工蜂群算法求解RFID网络优化问题

摘 要：本文提出了一种具有冯诺依曼社会结构的新型人工蜂群算法（VNABC）。本文采用四个测试函数验证VNABC算法性能，并将其应用于求解射频识别系统中的读写器网络覆盖和防冲突问题。试验结果表明，与基本人工蜂群算法和粒子群优化算法比较，VNABC算法求解复杂优化问题收敛速度较快、求解精度更高，从而为应用智能方法求解RFID系统优化问题提供了有效的可行方案。

关键词：人工蜂群算法；冯诺依曼结构；群体智能；RFID网络优化

中图分类号：TP18 文献标识码：A

1 引言（Introduction）

射频识别技术（Radio Frequency Identification， RFID）是对物理世界的信息进行感知和采集的物联网支撑技术，被列为本世纪十大重要技术之一[1]。在大规模RFID应用中，在工作区域内部署多个RFID读写器，构成密集读写器网络。网络中每个RFID读写器分别对其识读区域内的电子标签进行读写，并将采集到的标签数据发送到中央控制系统进行处理。由于密集读写器网络要对物理环境中海量标签进行全方位覆盖（防止漏读），某些读写器不可避免地会发生识读区域的相互重叠情况[2]。

人工蜂群算法（Artificial Bee Colony，ABC）是近几年来最流行的一种基于蜜蜂觅食行为的智能优化算法，由土耳其Erciyes大学的Karabog教授于2005年第一次提出[3]。ABC算法自提出以来，就以概念简单、控制参数少、算法容易实现、优化效果良好等优点吸引了大批学者进行研究，并逐渐进入到了各个应用领域[4]。但是，基本ABC算法是典型的高度连接网络结构，其快速收敛的代价则是容易陷入局部最优值，这主要是因为高度连接的网络中的个体对搜索空间的覆盖程度不如较少连接的网络结构。

本文将冯诺依曼结构[5]引入ABC中，提出一种具有冯诺依曼信息交流拓扑结构的新型人工蜂群算法（Von Neumann Artificial Bee Colony Algorithm，VNABC）。仿真实验首先采用四个测试函数验证VNABC算法性能，然后应用VNABC对具有10个读写器的RFID网络实例系统优化问题进行求解。RFID系统优化包括两个目标，即最大化标签覆盖率和最小化网络中的读写器冲突。仿真结果表明，与基本ABC算法与粒子群优化（Particle Swarm Optimization，PSO）算法相比，本文提出的VNABC算法能够更加有效地求解RFID系统优化问题。

2 冯诺依曼人工蜂群算法（Von Neumann artificial

bee colony algorithm）

驱动群体智能算法工作的本质是社会交流。种群里的个体根据自己通过社会交流得到的知识相互学习以向更好的位置移动。为此，本文将冯诺依曼信息交流拓扑结构引入最近提出的人工蜂群优化算法中，旨在解决其在求解复杂优化问题时的早熟收敛问题。

2.1 VNABC算法模型

在ABC算法中主要包括三种元素：食物源、雇佣蜂（employed bees）和非雇佣蜂（unemployed bees）；其中的非雇佣蜂又包括了：观察蜂（onlooker bees）和侦查蜂（scouts）。基本ABC算法中在新解产生时，是以原解为基础随机向任一其他解的任一维度进行学习，这是随机式的信息学习策略。在VNABC算法中，群体已经有特殊拓扑结构，因此在这里采用的精英学习策略，即每个个体向冯诺依曼社会结构构建的本身邻域内最优个体进行学习，而不再是随机挑选其他个体。VNABC算法的具体步骤如下：

在VNABC算法的初始阶段：产生随机分布的SN个解，即食物源位置。每个解是一个D维的向量，D是待优化参数的个数。然后对解进行评估，得到其适应度值fit。

在雇佣蜂阶段：每个雇佣蜂根据公式（1）在当前食物源位置的周围找到一个新的位置，即产生一个新的解。

（1）

这里，（1，2，...，SN）和（1，2，...，D） 是随机选择的索引，并且，是在[-1，1]之间产生的一个随机数。然后比较新产生解的值和原解的值，根据贪婪算法选择好的一个作为其对应的食物源位置。

在观察蜂阶段：每个观察蜂根据临域内雇佣蜂分享的食物源适应度值的信息，以一定概率选择一个食物源。表1给出了VNABC算法中冯诺依曼社会结构的构建策略。

表1 冯诺依曼形拓扑结构构造方法

Tab.1 Von Neumann shaped topology construction method

选择概率以公式（2）进行计算：

（2）

在侦查蜂阶段：如果一个食物源的适应值经过limit次循环之后没有得到改善，则该食物源位置将被移除。与该食物源对应的雇佣蜂变成侦查蜂。侦查蜂根据公式（3）随机产生一个新的食物源位置：

（3）

这里和是参数的上、下边界。

以上步骤将被重复MCN次或者直到某个终止条件达到满足。

2.2 函数测试

为了测试VNABC算法的性能，选择了常用的一组标准测试函数，分别是Sphere、Rosenbrock、Rastrigrin和Griewank。并将算法与基本ABC、PSO进行了比较。测试函数表达式如下所示：

Sphere函数是单峰函数，很容易求解。该函数在解（0，0，…，0）处取得全局最优值0。函数的初始范围为[-5.12，5.12]。Sphere函数表达式：

（4）

Rosenbrock函数是多峰函数，在解（1，1，…，1）处取得全局最优值0。函数的初始范围为[-15，15]。该函数在全局最优点附近有一个狭窄的波谷，因此优化方法很难收敛到全局最优点。Rosenbrock函数表达式：endprint

（5）

Rastrigin函数是一个复杂的多峰函数，很难求解。该函数在解（0，0，…，0）处取得全局最优值0。函数的初始范围为[-15，15]。该函数存在大量局部最优点，因此优化算法极容易选入其中而未能求得全局最优值。Rastrigin函数表达式：

（6）

Griewank在解（0，0，…，0）处取得全局最优值0。函数的初始范围为[-600， 600]。该函数有一个乘积项，使得变量之间相互依赖，因此该函数很难求解到全局最优点。Griewank函数也是多峰函数，表达式：

（7）

在本实验中，所有测试函数均设为30维。种群大小均为100。PSO惯性权重从0.9随着迭代次数的增加线性下降到0.7，学习因子c1和c2均为2.0。实验结果包括算法独立运行30次后函数的平均值，数据如表2所示。

表2 测试函数实验结果

Tab.2 The experimental results of test function

由实验结果可以看出，VNABC算法在复杂多峰函数Rosenbrock、Rastrigin和Griewank函数上要明显优于其他算法，而PSO算法在单峰函数Sphere上表现出了较高的性能。ABC算法在四个算法中表现相对较差。

3 RFID网络优化问题（RFID network optimization）

本文考虑RFID网络标签覆盖率和读写器防冲突建立RFID系统优化的目标函数，表示为：

（1）标签覆盖率

（8）

其中，NT表示RFID网络工作区域中的标签数量，表示第i个标签接收到的读写器信号强度，Pd表示保证标签和读写器能够建立有效连接的最小场强阈值。该目标函数能够将读写器定位在标签密集的区域，并通过调整读写器发射功率来最大化工作区域中的RFID标签覆盖率。

（2）读写器防冲突

（9）

在该模型中用实数编码的形式直接解决防冲突的问题。其中M表示工作区域中的读写器数量，函数dist（）表示两两读写器间的距离计算，Ri和Rj分别表示读写器i和j的实际位置，ri和rj则表示这两个读写器的识读范围。该目标函数通过调整读写器的实际位置，即使两两读写器间的实际距离大于等于其识读距离之和，尽量使读写器的识读区域不发生重叠，从而达到防冲突的目的。

总目标函数为标签覆盖率和读写器防冲突的加权函数。

（10）

4 基于VNABC的RIFD网络优化（RIFD network

optimization based on VNABC）

在仿真试验中，读写器工作区域为30m×30m的正方形，其中随机分布着100个RFID标签。由十个读写器组成的RFID网络对该工作区域中的标签进行数据采集。

实验一，只考虑工作环境中RFID标签覆盖率的优化结果。从仿真结果图中可以观察到，VNABC算法通过调整读写器空间位置和发射功率来获得合适的标签覆盖率，有效地将读写器定位在标签密集的区域，发现的最终解也要好于ABC和PSO算法。

实验二，只考虑降低网络中RFID读写器信号干扰的优化结果。同样，VNABC以较快的收敛速度发现较好的最终解。从仿真结果中可以观察到，VNABC算法通过调整读写器空间位置和发射功率来尽量使读写器间的信号覆盖区域不发生重叠。

实验三，综合考虑两种因素的RFID网络优化。结果显示VNABC算法取得的结果仍然好于其他两种方法。

5 结论（Conclusion）

本文的研究包括两个个方面：第一，提出了一种基于冯诺依曼社会结构的新型人工蜂群优化算法—VNABC。该算法具有更强的稳定性和整体优化性，在标准测试函数上的性能验证表明，所提出算法在收敛速度、跳出局部最优等性能方面均优于基本ABC算法和PSO算法，具有良好的工程应用前景。第二，将VNABC应用于求解RFID网络标签覆盖和防冲突优化问题，并给出了具体实例的仿真分析，从而进一步验证本文提出的模型和算法的有效性。

参考文献（References）

[1] 刘化君.物联网关键技术研究[J].计算机时代，2010（07）：4-6.

[2] 张光山，张烁，张有光.基于随机时隙的RFID读写器防冲突方

法[J].北京航空航天大学学报，2013（6）：782-786.

[3] Karaboga D，Basturk B.On the performance of artificial beecolony

（ABC） algorithm[J].Applied Soft Computing，2008：687-689.

[4] 程晓雅.人工蜂群算法理论及其在通信中的应用研究[D].山

东大学，2012.

[5] A.P.Engelbrecht.Fundamentals of Computational Swarm

Intelligence.Wiley Publishing，Inc.2009.

作者简介：

苏红丽（1979-），女，硕士，讲师.研究领域：计算机网络.endprint

（5）

Rastrigin函数是一个复杂的多峰函数，很难求解。该函数在解（0，0，…，0）处取得全局最优值0。函数的初始范围为[-15，15]。该函数存在大量局部最优点，因此优化算法极容易选入其中而未能求得全局最优值。Rastrigin函数表达式：

（6）

Griewank在解（0，0，…，0）处取得全局最优值0。函数的初始范围为[-600， 600]。该函数有一个乘积项，使得变量之间相互依赖，因此该函数很难求解到全局最优点。Griewank函数也是多峰函数，表达式：

（7）

在本实验中，所有测试函数均设为30维。种群大小均为100。PSO惯性权重从0.9随着迭代次数的增加线性下降到0.7，学习因子c1和c2均为2.0。实验结果包括算法独立运行30次后函数的平均值，数据如表2所示。

表2 测试函数实验结果

Tab.2 The experimental results of test function

由实验结果可以看出，VNABC算法在复杂多峰函数Rosenbrock、Rastrigin和Griewank函数上要明显优于其他算法，而PSO算法在单峰函数Sphere上表现出了较高的性能。ABC算法在四个算法中表现相对较差。

3 RFID网络优化问题（RFID network optimization）

本文考虑RFID网络标签覆盖率和读写器防冲突建立RFID系统优化的目标函数，表示为：

（1）标签覆盖率

（8）

其中，NT表示RFID网络工作区域中的标签数量，表示第i个标签接收到的读写器信号强度，Pd表示保证标签和读写器能够建立有效连接的最小场强阈值。该目标函数能够将读写器定位在标签密集的区域，并通过调整读写器发射功率来最大化工作区域中的RFID标签覆盖率。

（2）读写器防冲突

（9）

在该模型中用实数编码的形式直接解决防冲突的问题。其中M表示工作区域中的读写器数量，函数dist（）表示两两读写器间的距离计算，Ri和Rj分别表示读写器i和j的实际位置，ri和rj则表示这两个读写器的识读范围。该目标函数通过调整读写器的实际位置，即使两两读写器间的实际距离大于等于其识读距离之和，尽量使读写器的识读区域不发生重叠，从而达到防冲突的目的。

总目标函数为标签覆盖率和读写器防冲突的加权函数。

（10）

4 基于VNABC的RIFD网络优化（RIFD network

optimization based on VNABC）

在仿真试验中，读写器工作区域为30m×30m的正方形，其中随机分布着100个RFID标签。由十个读写器组成的RFID网络对该工作区域中的标签进行数据采集。

实验一，只考虑工作环境中RFID标签覆盖率的优化结果。从仿真结果图中可以观察到，VNABC算法通过调整读写器空间位置和发射功率来获得合适的标签覆盖率，有效地将读写器定位在标签密集的区域，发现的最终解也要好于ABC和PSO算法。

实验二，只考虑降低网络中RFID读写器信号干扰的优化结果。同样，VNABC以较快的收敛速度发现较好的最终解。从仿真结果中可以观察到，VNABC算法通过调整读写器空间位置和发射功率来尽量使读写器间的信号覆盖区域不发生重叠。

实验三，综合考虑两种因素的RFID网络优化。结果显示VNABC算法取得的结果仍然好于其他两种方法。

5 结论（Conclusion）

本文的研究包括两个个方面：第一，提出了一种基于冯诺依曼社会结构的新型人工蜂群优化算法—VNABC。该算法具有更强的稳定性和整体优化性，在标准测试函数上的性能验证表明，所提出算法在收敛速度、跳出局部最优等性能方面均优于基本ABC算法和PSO算法，具有良好的工程应用前景。第二，将VNABC应用于求解RFID网络标签覆盖和防冲突优化问题，并给出了具体实例的仿真分析，从而进一步验证本文提出的模型和算法的有效性。

参考文献（References）

[1] 刘化君.物联网关键技术研究[J].计算机时代，2010（07）：4-6.

[2] 张光山，张烁，张有光.基于随机时隙的RFID读写器防冲突方

法[J].北京航空航天大学学报，2013（6）：782-786.

[3] Karaboga D，Basturk B.On the performance of artificial beecolony

（ABC） algorithm[J].Applied Soft Computing，2008：687-689.

[4] 程晓雅.人工蜂群算法理论及其在通信中的应用研究[D].山

东大学，2012.

[5] A.P.Engelbrecht.Fundamentals of Computational Swarm

Intelligence.Wiley Publishing，Inc.2009.

作者简介：

苏红丽（1979-），女，硕士，讲师.研究领域：计算机网络.endprint

（5）

Rastrigin函数是一个复杂的多峰函数，很难求解。该函数在解（0，0，…，0）处取得全局最优值0。函数的初始范围为[-15，15]。该函数存在大量局部最优点，因此优化算法极容易选入其中而未能求得全局最优值。Rastrigin函数表达式：

（6）

Griewank在解（0，0，…，0）处取得全局最优值0。函数的初始范围为[-600， 600]。该函数有一个乘积项，使得变量之间相互依赖，因此该函数很难求解到全局最优点。Griewank函数也是多峰函数，表达式：

（7）

在本实验中，所有测试函数均设为30维。种群大小均为100。PSO惯性权重从0.9随着迭代次数的增加线性下降到0.7，学习因子c1和c2均为2.0。实验结果包括算法独立运行30次后函数的平均值，数据如表2所示。

表2 测试函数实验结果

Tab.2 The experimental results of test function

由实验结果可以看出，VNABC算法在复杂多峰函数Rosenbrock、Rastrigin和Griewank函数上要明显优于其他算法，而PSO算法在单峰函数Sphere上表现出了较高的性能。ABC算法在四个算法中表现相对较差。

3 RFID网络优化问题（RFID network optimization）

本文考虑RFID网络标签覆盖率和读写器防冲突建立RFID系统优化的目标函数，表示为：

（1）标签覆盖率

（8）

其中，NT表示RFID网络工作区域中的标签数量，表示第i个标签接收到的读写器信号强度，Pd表示保证标签和读写器能够建立有效连接的最小场强阈值。该目标函数能够将读写器定位在标签密集的区域，并通过调整读写器发射功率来最大化工作区域中的RFID标签覆盖率。

（2）读写器防冲突

（9）

在该模型中用实数编码的形式直接解决防冲突的问题。其中M表示工作区域中的读写器数量，函数dist（）表示两两读写器间的距离计算，Ri和Rj分别表示读写器i和j的实际位置，ri和rj则表示这两个读写器的识读范围。该目标函数通过调整读写器的实际位置，即使两两读写器间的实际距离大于等于其识读距离之和，尽量使读写器的识读区域不发生重叠，从而达到防冲突的目的。

总目标函数为标签覆盖率和读写器防冲突的加权函数。

（10）

4 基于VNABC的RIFD网络优化（RIFD network

optimization based on VNABC）

在仿真试验中，读写器工作区域为30m×30m的正方形，其中随机分布着100个RFID标签。由十个读写器组成的RFID网络对该工作区域中的标签进行数据采集。

实验一，只考虑工作环境中RFID标签覆盖率的优化结果。从仿真结果图中可以观察到，VNABC算法通过调整读写器空间位置和发射功率来获得合适的标签覆盖率，有效地将读写器定位在标签密集的区域，发现的最终解也要好于ABC和PSO算法。

实验二，只考虑降低网络中RFID读写器信号干扰的优化结果。同样，VNABC以较快的收敛速度发现较好的最终解。从仿真结果中可以观察到，VNABC算法通过调整读写器空间位置和发射功率来尽量使读写器间的信号覆盖区域不发生重叠。

实验三，综合考虑两种因素的RFID网络优化。结果显示VNABC算法取得的结果仍然好于其他两种方法。

5 结论（Conclusion）

本文的研究包括两个个方面：第一，提出了一种基于冯诺依曼社会结构的新型人工蜂群优化算法—VNABC。该算法具有更强的稳定性和整体优化性，在标准测试函数上的性能验证表明，所提出算法在收敛速度、跳出局部最优等性能方面均优于基本ABC算法和PSO算法，具有良好的工程应用前景。第二，将VNABC应用于求解RFID网络标签覆盖和防冲突优化问题，并给出了具体实例的仿真分析，从而进一步验证本文提出的模型和算法的有效性。

参考文献（References）

[1] 刘化君.物联网关键技术研究[J].计算机时代，2010（07）：4-6.

[2] 张光山，张烁，张有光.基于随机时隙的RFID读写器防冲突方

法[J].北京航空航天大学学报，2013（6）：782-786.

[3] Karaboga D，Basturk B.On the performance of artificial beecolony

（ABC） algorithm[J].Applied Soft Computing，2008：687-689.

[4] 程晓雅.人工蜂群算法理论及其在通信中的应用研究[D].山

东大学，2012.

[5] A.P.Engelbrecht.Fundamentals of Computational Swarm

Intelligence.Wiley Publishing，Inc.2009.

作者简介：

苏红丽（1979-），女，硕士，讲师.研究领域：计算机网络.endprint