基于拥挤度快速排序的物联网RFID系统优化设计

王 芳，程 杰，乔 木

(郑州升达经贸管理学院 信息工程系，河南 郑州 451191)

基于拥挤度快速排序的物联网RFID系统优化设计

王 芳，程 杰，乔 木

(郑州升达经贸管理学院 信息工程系，河南 郑州 451191)

大规模物联网射频识别（RFID）网络规划问题已被证明是一个NP难问题，为提高物联网RFID系统设计的合理性，提出一种基于个体拥挤度快速排序的物联网RFID系统设计方法。首先，将RFID网络规划问题分解为最佳标签覆盖、读写器干扰、经济性指标和负载均衡指标四项指标构成的多目标优化问题，并引入多目标人工蜂群算法（MABC）进行优化；其次，为提高MABC算法的优化性能，利用非支配排序方法设计了一种快速的排序方法，并利用拥挤度分析提高种群的多样性；最后，通过实验对比验证了所提系统设计方法的有效性。

个体拥挤度；快速排序；射频识别；物联网；人工蜂群算法；多目标优化

本文著录格式：王芳，程杰，乔木. 基于拥挤度快速排序的物联网RFID系统优化设计[J]. 软件，2017，38（1）：37-43

0 引言

射频识别（RFID）[1~2]技术作为一种新的库存跟踪技术已经取得了显著的发展，在许多实际的工业场景，特别是在物联网技术中有很大的应用潜力[3]。在许多现实世界的RFID应用，如生产、物流和供应链管理，越来越多的读写器部署在特定的区域中提供标签的完全覆盖。可以利用无线射频识别技术建立的“物联网”，连接到互联网的物理关口，并可远程访问传感器数据实现物理世界的控制。

然而，由于在实际应用中单一的读写器识别范围有限，许多读写器和标签需要进行优化部署，以在场景区域中建立射频识别系统。需要考虑的问题有[4~5]：（1）读写器的部署数量；（2）读写器的部署位置；（3）读写器的有效参数设置。此外，考虑到成本效益的射频识别系统，网络应满足最小数量的读写器和最大标签覆盖。因此，RFID网络规划问题（RNP）是一个NP难问题[6]。

在一般情况下，定义RNP旨在通过调整混合离散和连续系统的控制变量，如读写器数量，坐标和天线参数，优化目标包括部署成本，标签覆盖、负载平衡、经济效率和读写器之间干扰。在过去的二十年中，利用进化计算（EC）和群智能优化算法（SI）求解RNP问题得到了越来越多关注，例如遗传算法（GA）[7]、进化策略（ES）[8]、粒子群算法（PSO）[9]和人工免疫算法（AI）[10]等。最近，人工蜂群算法（ABC）[11]作为群体智能算法中的一个相对较新的成员，得到了学者的关注。由于其算法简单、鲁棒性好，ABC及其变种已用来求解RNP问题。但是这种采取单一混合目标形式的优化策略，会出现指标间的吞并问题，导致部分指标无法得到优化。

对此，本文考虑采用多目标人工蜂群算法进行RFID网络规划问题求解，获得部署成本、标签覆盖、负载平衡、经济效率和读写器之间干扰多项指标的同步优化。

1 射频识别网络规划优化模型

1.1 RFID系统构成

一个的射频识别系统由四种类型的重要部分组成，见图1所示[12]：（1）RFID标签，放在每个物体上，由芯片和嵌入式天线组成并包含独特电子产品代码（EPC）；（2）RFID读写器，每个含有一个以上的天线，并负责通过射频波发射和接收数据；（3）RFID中间件，用于管理读写器，并过滤和格式化RFID原始标签数据；（4）RFID数据库，用于记录RFID标签数据中包含的信息，如阅读时间，地点和标签的EPC。在这一部分中，提出基于RFID中间件的RNP问题的数学优化模型。

图1 RFID系统Fig.1 RFID system

该模型包含几个不同的方面：RFID热点部署区域为二维正方形区域，这里的标签是基于2代超高频标准规范的。这意味着，他们只能从读写器中通过无线电频率提供能量。该RNP模型旨在通过优化目标，包括成本、覆盖率、干扰、负载均衡等子指标，通过调节RFID网络读写器的参数，包括数量，位置和辐射功率，从而提高RFID网络的QoS和总效率。

1.2 RNP问题描述

本文对物联网进行RFID网络部署设计过程，采用如下评价指标[13]：

（1）最佳标签覆盖（C）：第一个目标函数是覆盖范围指标，其为射频识别系统中最重要的指标。在本文中，如果标签接收无线电信号高于阈值那么读写器和标签之间可以建立通信。然后函数转化为在读写器j的讯问区域所需的功率水平δ和标签i实际接收功率之间的差异之和：

式中，TS和RS分别为部署在工作区域中的标签集合读写器集，RSi表示在其阅读区域中具有标记i的读写器集。这个目标功能是确保标签i从RSi中的读写器j接收到的功率，逐渐逼近或是略高于阈值δ，可确保标签被激活，同时能够保持能源使用的有效性和效率。

（2）读写器干扰（I），发生在密集读写器环境中的阅读碰撞，一般是有几个读写器试图在同一时间查询同一区域的读写器。这可能会导致误读，而无法进行信息接受。目标函数定义形式为：

其中，TSk是在读写器k的查询区域中的标签集。对于每个标签i，该目标考虑所有的读写器，除了干扰源。也就是说，通过改变读写器的位置和功率，该算法可调整读写器的位置以降低干扰。

（3）经济性指标（E），可从不同的角度进行定义，例如考虑到信道传播中存在的随机噪声，多径效应和衰减，读写器应部署在标签热点的中心。从这个角度来看，这个目标可以通过权衡每个标签集的中心距离与最佳服务读写器的距离进行实现。可采用k-均值聚类算法来找到标签集群，可定义为：

其中，dist()是第k个读写器Ik和第个k标签中心kθ的距离，在该目标中，算法试图降低读写器与高密度标签元素之间的距离。

（4）负载均衡指标（L），具有均匀分布的读写器网络要比不平衡配置的网络具有更优的负载均衡成本。因此，在大型的RFID系统中，标签集需要在所有读写器读者之间实现一定的平衡。据此，目标函数可定义为：

式中，Ck是读写器k分配的标签数量，为读写器k在单位时间内可读取的最大标签数量。需要注意的是根据网络中使用的读写器类型，需要设定不同的值。该目标是通过改变读写器位置和辐射功率，以降低负载均衡方差。

2 多目标人工蜂群算法

2.1 人工蜂群算法

人工蜂群（ABC）算法是一种基于蜜蜂智能觅食行为的进化算法，分为三个组成要素：被雇佣蜜蜂、侦察员以及未雇佣蜜蜂。雇佣蜜蜂搜索具体的花蜜（食品）源，并将其传递给跟随蜂。每个食物源仅对应于一个雇佣蜜蜂，雇佣蜜蜂的数量等于花蜜源数量。如果雇佣蜜蜂发现蜜源枯竭，它将通过侦察员进行新蜜源更换。根据图2可更好地了解蜜蜂群体觅食行为的基本行为特征。

图2 蜜蜂采集花蜜的行为Fig.2 behavior of bees collecting nectar

在图2中，假设有两个食物源被发现：A和B。在开始的时候，一个潜在的蜜蜂作为未雇佣密封开始觅食，该蜜蜂不知道蜂巢周围的食物源情况，这样的蜜蜂有两种可能选择：

（1）它可以是一个侦察员，因为内部动机或可能的外部线索开始搜索蜂巢周围的食物源（图2中的‘S’）。

（2）它可通过观看摇摆舞，并开始寻找食物源（图2中的‘R’）。在寻找到食物源后，蜜蜂利用其能力记住该位置，然后立即开始食物采集。此时蜜蜂会成为一个“雇佣者”。觅食蜜蜂需要在食物源上进行花蜜采集，并返回到蜂巢中在食物仓库中进行花蜜卸载。在卸载食物后，蜜蜂有以下选项：（2-1）它可能在放弃了食物来源后，成为自由的未雇佣者（UF）。（2-2）它会跳舞然后招聘其他蜜蜂返回同一食物源（EF1）。（2-3）它可能会继续搜寻食物源，而不招募蜜蜂（EF2）。则蜜蜂算法可构建为：

步骤1：（初始化阶段）产生一个随机分布的初始食物源位置解决方案：

步骤2：（蜜蜂雇佣阶段）每个受雇蜜蜂在其当前食物源xi发现一个新的食物来源vi，使用下列表达式计算新的食物源：

步骤3：（蜜蜂侦查阶段）每个侦查员以一定概率选择雇佣蜜蜂共享的与花蜜量相关的食物源。概率计算形式如下：

如果不能在确定周期内实现食物源质量提升，则将其从种群中移除，并重新确定为侦查蜂。侦察蜂查找新的随机的食物源位置如下：

式中，k为蜜蜂在种群中的索引。上述步骤在预定数量周期内被重复执行，直到一个终止准则满足。

2.2 非支配快速排序

对蜂群算法的初始种群使用如下非支配快速排序过程进行处理：

步骤1：对人工蜂群算法的蜜蜂种群P的蜜蜂个体p进行以下操作步骤：

1-2：对于蜜蜂种群P内的个体q，若满足p≻q，那么可得否则q≻p，并且令

1-3：若np=0，那么设定蜜蜂个体p等级为并且令蜜蜂个体p附加到蜜蜂种群的Pareto前沿内，可表示为

步骤2：对人工蜂群算法的蜜蜂种群执行下列步骤，直到满足条件iF=φ：

2-1：令Q=φ，作用是对Pareto前沿iF进行临时存放；

2-2：对于Pareto前沿iF内蜜蜂个体p，操作如下：对Sp内蜜蜂个体q，操作如下：令若满足那么表示q仅被蜜蜂个体p支配，则设置蜜蜂个体q等级为并且可得

2-3：令i=i+1；

2-4：令Pareto前沿iF=Q，则同理可获得2~n前沿集

2.3 拥挤度指标设计

在人工蜂群种群进化过程中，适应度高且同其余蜜蜂间距相对较小的个体进行保留，假定共有r组子目标形式为f1、f2…fr，蜜蜂i的在种群中的拥挤度数值为是蜜蜂i对于子目标m的对应函数取值，那么可得拥挤度指标为：

如果蜜蜂种群规模是N，那么在最坏运行状况下，进行r组子目标的拥挤度计算复杂度为排序计算复杂度为那么可得总复杂度是

2.4 多目标人工蜂群算法步骤

步骤1：设定人工蜂群算法种群规模是N，进化终止代数为gen，蜜蜂个体取值上限为XVmax，下限为XVmin，初始化蜜蜂种群pop，进行适应值计算、排序和个体的拥挤度计算，并设定i=1；

步骤2：基于竞标赛个体保留方式在种群pop内获得N/2数量的蜜蜂个体构建父代蜜蜂个体parent_pop，并进行3.1节蜜蜂觅食有关操作，获得临时性种群pop1，规模为N/2；

步骤3：将临时性种群pop1与原始种群pop生成混合种群intermediate_pop，进行蜜蜂的排序及相应的拥挤度值获取，并在此基础上选择N个蜜蜂构成种群pop；

步骤4：令i=i+1，若满足i≤gen，那么重新调用步骤2；若满足i＞gen，那么算法继续；

步骤5：输出pareto最优解集pop，作为多目标人工蜂群算法的输出结果。

3 实验分析

3.1 多目标优化算法性能测试

测试函数形式如下：

图3a~图3b分别为MOP1和MOP2函数所求解的Pareto最优解对比情况，多目标进化算法性能评价指标主要有两个：解的均匀性和前沿性。根据图3所示可看出，本文算法在这两项评价指标上均要优于选取的对比算法，在均匀性上与SPEA和NSGAⅡ两种算法非常接近。图4所示为对比算法Pareto解集分布对比，可看出本文算法在上述两项指标上也要优于其他四种对比方法。实验结果验证了本文多目标人工蜂群算法有效性。

图3 Pareto最优解对比Fig.3 comparison of Pareto optimal solutions

图4 最优解分布Fig.4 optimal solution distribution

3.2 物联网RFID系统实验

这里使用的读写器是移动的，标签是被动的。相关的射频识别读写器参数设置见表1所示。查询范围可根据读写器的辐射功率进行计算，参见文献[6]所示。RNP实例选取CD100，对所提算法的有效性进行验证。CD100实例的工作区域大小为30m× 30m，具有100个集群分布式测试标签。对比算法选取：（1）单目标人工蜂群算法，各指标权重均设置为0.25；（2）普通多目标人工蜂群算法（MABC）。实验对比结果见图5~6所示。

图5 各指标优化对比Fig.5 optimization and comparison of each indicator

根据图5a~图5d可知，最佳标签覆盖、读写器干扰、经济性指标和负载均衡指标四项指标的数量级并不相同，如果采用单一目标的人工蜂群算法，如果权重系数设置不合适，会造成多数指标优化失败的问题，如图5a~图5d所示，在上述四组指标中，仅有数量级较大的最佳标签覆盖指标得到优化，而其他指标的优化过程被弱化或覆盖，无法实现所有指标的同步优化。而采用多目标算法的优化结果，虽然在最佳标签覆盖指标上的优化结果不如单目标优化结果，但是在读写器干扰、经济性指标和负载均衡指标三项指标上的优化结果要优于单目标优化结果。同时可看出，本文所提方法在上述四项指标上的优化结果均要优于选取的普通MABC算法，体现了方法有效性。

采用上述三种算法的网络RFID读写器部署对比情况见图6所示。

图6 RFID读写器部署对比情况Fig.6 compares of RFID reader-writer deployment

根据图6a~图6c可知，在RFID读写器部署效果对比情况看，本文算法所设置的读写器位置均适当的位于标签周围，并且每个标签集簇仅含有一个读写器，实现了读写器的相对优化部署。普通MABC算法除个别RFID读写器部署出现问题外，整体上普通MABC算法要优于单一目标的人工蜂群算法。

4 结束语

本论文提出一种基于个体拥挤度快速排序MABC的物联网RFID系统设计方法，将RFID网络规划问题（RNP）分解为最佳标签覆盖、读写器干扰、经济性指标和负载均衡指标四项指标构成的多目标优化问题，并利用多目标人工蜂群算法进行优化，同时利用非支配排序方法设计了一种多目标人工蜂群算法的快速排序方法，并利用拥挤度分析提高种群的多样性。实验结果验证了所提方法的有效性。因为实验条件所限，本文算法验证仅通过模拟数据集实现，如何在实际应用中验证算法的有效性，是今后研究的重点。

[1] Chung-Hao Huang, Lun-Hui Lee, Chian C Ho, et al. Real-Time RFID Indoor Positioning System Based on Kalman-Filter Drift Removal and Heron-Bilateration Location Estimation[J]. IEEE Transactions on Instrumentation and Measurement, 2015, 728-739.

[2] 张士庚, 刘光亮, 刘漩, 等. 大规模RFID系统中一种能量有效的丢失标签快速检测算法[J]. 计算机学报, 2014, 37(2): 434-444. Shi-Geng Zhang,Guang-Liang Liu, Xuan Liu, et al. An Energy-Efficient and Fast Missing Tag Detection Algorithm in Large Scale RFID Systems[J]. Chinese Journal of Computers, 2014, 37(2): 434-444.

[3] 李国家, 汪定伟. 分销网络多级存储的RFID使能的Pull控制系统[J]. 系统管理学报, 2016, 25(3): 571-576. Guo-Jia Li, Ding-Wei Wang. Pull control system of RFID enable for multi-level storage in distribution network[J]. Journal of Systems & Management, 2016, 25(3): 571-576.

[4] Siddika Parlak, Ivan Marsic, Aleksandra Sarcevic, et al. Passive RFID for Object and Use Detection during Trauma Resuscitation[J]. IEEE Transactions on Mobile Computing, 2016, 15(4): 924-937.

[5] Po Yang. PRLS-INVES: A General Experimental Investigation Strategy for High Accuracy and Precision in Passive RFID Location Systems[J]. IEEE Internet of Things Journal, 2014, 2(2): 159-167.

[6] Herbjørn Nysveen, Per Egil Pedersen. Consumer adoption of RFID-enabled services. Applying an extended UTAUT model[J]. Information Systems Frontiers, 2016, 18(2): 293-314.

[7] Tin-Yu Wu, Guan-Hsiung Liaw, Sing-Wei Huang, et al. A GA-based mobile RFID localization scheme for internet of things[J]. Personal and Ubiquitous Computing, 2012, 16(3): 245-258.

[8] Han Feng, Jie Qi. Radio frequency identification networks planning using a new hybrid evolutionary algorithm[C]//2013 15th International Conference on Advanced Communication Technology (ICACT), IEEE, PyeongChang, 2013, pp.179-188.

[9] Wen-Tsai Sung, Yen-Chun Chiang. Improved Particle Swarm Optimization Algorithm for Android Medical Care IOT using Modified Parameters[J]. Journal of Medical Systems, 2012, 36(6): 3755-3763.

[10] R J Kuo, J W Chang. Intelligent RFID positioning system through immune-based feed-forward neural network[J]. Journal of Intelligent Manufacturing, 2015, 26(4): 755-767.

[11] 周新宇, 吴志健, 王明文. 基于正交实验设计的人工蜂群算法[J]. 软件学报, 2015, 26(9): 2167-2190. Xin-Yu Zhou, Zhi-Jian Wu, Ming-Wen Wang. Artificial Bee Colony Algorithm Based on Orthogonal Experimental Design[J]. Journal of Software, 2015, 26(9): 2167-2190.

[12] 王雪, 钱志鸿, 刘晓慧, 等. 改进的树型结构RFID防碰撞算法[J]. 通信学报, 2015, 36(7): 2015161. Xue Wang, Zhi-Hong Qian, Xiao-Hui Liu, et al. Improved tree structure anti-collision algorithm of RFID[J]. Journal on Communication, 2015, 36(7): 2015161.

[13] Vishwa V Kumar, F W Liou, S N Balakrishnan, et al. Economical impact of RFID implementation in remanufacturing: a Chaos-based Interactive Artificial Bee Colony approach[J]. Journal of Intelligent Manufacturing, 2015, 26(4): 815-830.

[14] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength pareto evolutionary algorithm[R]. Zurich: Computer Engineering and Networks Laboratory(TIK), Swiss Federal Institute of Technology (ETH) Zurich, 2001.

[15] Deb K, Pratap A, Agarwal S. A fast and elitist multiobjective genetic algorithm: NSGA2[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-197.

Crowding Degree Fast Sorting Based RFID System Optimal Design For Internet of Things

WANG Fang, CHENG Jie, QIAO Mu

(Department of Information Engineering, Zhengzhou Shengda College of Economics & Trade Management, Zhengzhou, 451191, China)

The mass network radio frequency identification (RFID) network planning problem has been shown to a NP hard problem, in order to improve the design of the RFID system rationality, we put forward an Individual crowding degree fast sorting MABC based RFID system design for Internet of things. Firstly, we decompose the RFID networks planning as the four indexes of multi-objective optimization problems, such an optimal tag coverage, reader interference, economic index and load balance index, and it used the multi-objective artificial bee colony algorithm (ABC) to optimize it. Secondly, in order to improve the optimization performance of ABC algorithm, a fast sorting method is designed by using non dominated sorting method, and the diversity of population is improved by using the analysis of crowding degree; Finally, the effectiveness of the proposed system design method is verified by experiments.

Individual congestion degree; Fast sorting; Radio frequency identification; Internet of things; Artificial bee colony algorithm; Multi objective optimization

TP18

A

10.3969/j.issn.1003-6970.2017.01.009

2015年度河南省重点科技攻关项目基金(152102210176)

王芳(1973-)，女，河南郑州人，硕士，副教授，主要研究方向：网络优化、物联网、真实感绘制。