刘 鹰，赵小晴，张开伟

（哈尔滨工程大学自动化学院，黑龙江哈尔滨150001）

0 引 言

射频识别（radio frequency identification，RFID）是一种无需在识别系统与目标之间建立接触，仅通过无线射频信号就能识别目标并读写相关数据的非接触式自动识别系统［1］。随着RFID的大范围应用，它也出现了一些未解决的问题。多个阅读器感知范围有重叠时，对处于重叠区中的标签有干扰，会影响阅读器与其各自感知范围内的标签之间的通讯，甚至使得整个定位系统崩溃，所以就需要对RFID无线网络中的阅读器进行规划。RFID阅读器网络的合理规划可以大大减少网络消耗、节约节点能量、提高信号的覆盖率，减少阅读器之间的数据冲突，同时还能改善网络的安全性和可靠性。当阅读器网络规划首次被提出时，Daniel及Engels他们将阅读器碰撞看成一种类似于简单图着色的问题，随后S.K.Padhi等提出了一种阅读器防碰撞算法Colorwave，J.Ho和S.M.Birari分别提出Q－learning算法和Pulse算法来解决阅读器碰撞问题［2－4］。当前对阅读器网络规划都整体对阅读器建模，需要同时考虑很多方面，环境、标签分布、阅读器分布、干扰等问题，这使得建模复杂且效果不理想［5－7］。例如田景贺、范玉顺等针对密集阅读器环境中的RFID阅读器碰撞提出了一种阅读器集中控制方法，主要根据图着色理论，将密集阅读器网络的阅读器防碰撞等效为阅读器网络的时隙分配问题。高彦芬，宋革联对RFID系统在考虑阅读器数量、时隙分配及总处理时间，建立系统规划的目标函数［8，9］。

针对上述的情况，本文结合粒子群优化算法和图着色理论提出了将阅读器布局与阅读器分配时隙分解为两步进行仿真，利用粒子群算法对阅读器进行布局，再利用图着色最小着色对阅读器进行时隙分配，如此进行规划，使得整个阅读器网络规划简单可行，提高阅读器的读取率，从而完成阅读器的防碰撞处理。

1 阅读器模型

阅读器网络覆盖问题的研究依赖于每个阅读器的覆盖模型和放置位置，要对阅读器进行布局，首先需要选定阅读器模型。

最常用的阅读器模型是布尔模型，即0－1模型。若标签能被阅读器覆盖到，则阅读器的作用状态为1，否则为0。当阅读器感知特性为全向时，布尔模型就简化成圆盘布尔模型。如图1所示，以阅读器为中心的圆盘，在感知半径R下，只要标签处于圆盘内即认为标签被阅读器覆盖，圆盘之外的标签则在阅读器覆盖区域之外。模型表示阅读器能够覆盖到圆盘内标签发生的概率恒为1，覆盖到圆盘外的概率恒为0，即假设阅读器坐标为r（xr，yr），任意标签坐标为t（xt，yt），阅读器能够覆盖标签的概率为

图1 阅读器布尔模型

2 粒子群算法

2.1 粒子群算法原理

粒子群优化算法（particle swarm optimization，PSO）是一种多维优化的群体智能算法，通过抽象、模拟自然界鸟群觅食过程时的迁徙和群聚行为而提出。这种全局随机搜索算法简单且易于实现，求解质量高，所以自从提出后迅速被应用于各个领域。PSO中，搜索空间中的每一个粒子就是优化问题的潜在解。

初始化时PSO随机定义一群粒子，然后模拟鸟类群居的方式飞行。粒子群算法有两个极值，一个称为个体极值（pbest），是个体自身找到的当前最优解；另一个称为全局极值（gbest），是整个种群找到的当前最优解。进行每次迭代时，粒子通过跟踪这两个极值来不断更新自己。同时每个粒子都有一个适应度值（fitness value）以及决定其飞翔的方向和距离的速度，每次迭代之后，粒子根据其适应度值改变自身的飞行速度，使得粒子能够飞向pbest和gbest，从而追随当前的最优粒子在解空间中进行搜索［10，11］。

2.2 粒子群算法数学描述

粒子群算法的数学描述:每个粒子i包含一个m维的位置向量xi＝（xi1，xi2，……，xim）和速度向量vi＝（vi1，vi2，……，vim）。粒子i搜索解空间时，保存其搜索到的最优经历位置pi＝（pi1，pi2，……，pim）。在每次迭代开始时，粒子根据自身惯性和经验及群体最优经历位置pg＝（pg1，pg2，……，pgm）来调整自己的速度向量以调整自身位置。Ω称为惯性权重，其值用于反映下一刻对当前速度的继承程度，合理地设置惯性权重可以使粒子具有均衡的探索能力和开发能力；c1、c2是正的常数，称之为加速因子；r1、r2为［0，1］上均匀分布的随机数，d为维数。其中，粒子的位置和速度更新按下式

3 图论以及图着色

3.1 图着色起源

图着色问题起源于四色猜想，所谓四色猜想就是证明:给一个平面或者球面上的地图着色，至多只要4种颜色就可以完成，并且能够保证任意相邻两个国家是不同的颜色，使得各国家之间可以很明显的辨认。由地图着色问题引申的图着色理论在结合计算机的情况下已得以证明，如今已广泛应用于各种领域:排课表问题，考试安排问题，化学药品贮藏问题，无线电频谱分配等。

3.2 图着色相关概念

要应用图着色理论对各种问题进行解决，就需要知道图着色的相关概念，定义如下:

（1）正常顶点着色:给图的顶点进行着色，满足任意相邻的顶点颜色不同的条件；

（2）k－顶点着色:用k种颜色对图中所有顶点正常顶点着色；

（3）图的最小着色数:对图进行正常顶点着色所需颜色的最小数［12］。

3.3 图的矩阵表示

一个给定图G＝（V，E）既可以由它的顶点与顶点之间的邻接关系唯一确定，也可以由它的顶点与边之间的关联关系唯一确定。所以下面就对邻接矩阵、关联矩阵定义。

邻接矩阵的定义:设（无向）图G＝（V，E），其中顶点集V＝｛v1，v2，……，vn｝，边集E＝｛e1，e2，……，en｝。用aij表示顶点vi与顶点vj之间的边数，可能取值为0，1，2，称所得矩阵A＝A（G）＝（aij）n×n为图G的邻接矩阵。

关联矩阵的定义:设（无向）图G＝（V，E），其中顶点集V＝｛v1，v2，……，vn｝，边集E＝｛e1，e2，……，en｝。用mij表示顶点vi与边ej关联的次数，可以取值0，1，2，称所得矩阵M（G）＝（mij）n×l为图G的关联矩阵。

图G＝（V，E）在计算机中存储的数据结构必须完全等价于图本身的顶点与顶点或顶点与边之间的结构关系，而图的表示矩阵就承担了这种重要媒介角色。通过对图的表示矩阵进行讨论就可以得到图的若干性质。作为图的一个关键矩阵，邻接矩阵有其自身的一些特定性质。

根据邻接矩阵的定义，易得到若干性质如下:

（1）A（G）是对称矩阵；

（2）若G为无环图，则A（G）中第i行（列）的元素之和等于顶点vi的度；

（3）两图G和H同构的充分必要条件是存在置换矩阵P使得A（G）＝PTA（G）P。

RFID阅读器系统中各阅读器的工作范围可能会有重叠，这与地图中各个部分可能相邻相似；当有重叠区的阅读器同时工作时，如果不采取措施，就会产生阅读器碰撞，甚至使整个RFID系统无法正常工作。而RFID系统能够正常工作需要相互有重叠区的阅读器工作于不同的时隙来避免碰撞，这与图着色所希望的各相邻国家着不同的颜色以便可以明显辨认的想法相似。综上，阅读器时隙分配与图着色具有同样的前提和期望有相同的结果，所以本文运用图着色理论进行时隙分配进行阅读器碰撞处理。

在对阅读器布局图进行时隙分配时将每个阅读器视为一个顶点，阅读器之间是否碰撞视为是否相邻。即若阅读器若R1、R2同时工作，则其重叠区域发生碰撞，可视为阅读器1，2相邻，此时其邻接矩阵W中w12＝w21＝1。

4 算法设计

4.1 RFID阅读器布局

其中:n为被阅读器覆盖的标签个数，N为设置的标签的个数设计的具体步骤:

（1）初始化种群。设定如下参数:加速因子，迭代次数maxgen，种群规模sizepop，粒子位置（即阅读器位置），标签位置tag，速度；

（2）粒子进行适应度值计算；

（3）寻找个体极值和群体极值；

（4）速度和位置更新，计算粒子适应度值；

（5）个体极值和群体极值更新，若满足终止条件，结束，否则转到（4）。

4.2 阅读器着色

具体设计步骤:

（1）根据所得阅读器位置求得邻接矩阵；

（2）求出阅读器布局图简化图各顶点度数；

（3）从顶点度数最小的未着色顶点开始着色，找到与其不相邻的顶点并选择其中一个顶点进行着色；

（4）找到与前两个顶点都不相邻的顶点集合，并对其中一个顶点着色，重复当前步骤，直到找不到为止；

（5）所有顶点均已着色，则结束，否则转到步骤（3）。

5 实验仿真

5.1 RFID阅读器布局仿真结果

使用MATLAB对RFID阅读器网络进行布局仿真。指定区域大小为18m×18m，在其中随机地布置50个电子标签，使用9个可以移动的阅读器对RFID网络中的标签进行数据采集。工作频率在433MHz的RFID系统，通信距离长，信号绕射能力强，故本文的阅读器工作频率选用433MHz，假定阅读器的感知范围为一个半径为3m的圆（实际应用中感知范围可能为不规则形状）。

表1 参数初始化

利用粒子群算法对阅读器进行布局时粒子的维数即等于阅读器的个数，仿真结果如图2、图3所示，其中图2为粒子群算法求得的标签被阅读器覆盖的覆盖率，图3为阅读器对标签进行覆盖的示意图。

图2 PSO优化阅读器对标签的覆盖率

5.2 图着色对阅读器分配时隙

图论中邻接矩阵W＝（wij）n×n中各元素的标示方法如下

其中阅读器编号i和j满足1≤i，j≤n的条件，则可以得到图3所示阅读器分布图的邻接矩阵W

图3 PSO优化阅读器及标签位置

根据图着色算法得到

将矩阵W作为程序的输入矩阵，即为给定的图的邻接矩阵，通过仿真可以得到各阅读器着色状态，color为最终给阅读器着色所需的最少颜色，C为阅读器的着色方案。

由PSO所得的阅读器布局图和图着色所得的着色方案，可以给出RFID网络优化的整个阅读器防碰撞方案，如图4所示。

图4 RFID阅读器网络规划

6 结束语

通过直接对阅读器网络进行整体建模，实现布局、防碰撞处理，仍然会存在阅读盲区，从而无法达到避碰效果，影响整个系统工作。简化阅读器防碰撞的过程，对其进行两步处理，首先利用粒子群算法对阅读器的位置进行布局，再利用图着色算法对每个阅读器着色，使其与其周围的颜色都不同，可以达到时隙分配的效果，仿真结果表明，通过上述的网络规划可以减少阅读器的碰撞。采用分步时隙分配可以降低处理复杂度，并且能够使得网络规划简单可行。

［1］HAN Xia1in，ZHAO Weidong，JI Jun，et al.Indoor location algorithm based on RFID technology and its improvement［J］.Computer Engineering，2008，34（22）:266－270（in Chinese）.［韩下林，赵卫东，季军，等.基于RFID技术的室内定位算法及其改进［J］.计算机工程，2008，34（22）:266－270.］

［2］Ben Niu，Edward C Wong，Yujuan Chai，et al.RFID network planning based on MCPSO alogorithm［C］//Second International Symposium on Information Science and Engineering，2009:8－12.

［3］Hanning Chen，Yunlong Zhu，Kunyuan Hu.RFID networks planning using a multi－swarm optimizer［C］//Chinese Control and Decision Conference，2009:3548－3552.

［4］XU Xuehui，LI Lingyuan，WANG Zhengqiang，et al.An adaptive graph coloring algorithm for RFID reader collision problem［J］.Modern Electronics Technique，2006（9）:27－30（in Chinese）.［徐雪慧，李玲远，王正强，等.用自适应图着色算法解决RFID阅读器冲突问题［J］.现代电子技术，2006（9）:27－30.］

［5］CHEN Hanning，ZHU Yunlong，HU Kunyuan.RFID network optimization based on multi－species coevolution［J］.Journal of PLA University of Science and Techonology（Natural Science Edition），2008，9（5）:413－416（in Chinese）.［陈瀚宁，朱云龙，胡琨元.基于多种群共生进化的RFID网络优化［J］.解放军理工大学学报（自然科学版），2008，9（5）:413－416.］

［6］LIU Kuai，SHEN Yanxia，JI Zhicheng.RFID network optimization based on improved particle swarm optimization algorithm［J］.Journal of Central South University（Natural Science Edition），2011，42（suppl1）:900－904（in Chinese）.［刘快，沈艳霞，纪志成.基于改进粒子群算法的RFID网络系统的优化［J］.中南大学学报（自然科学版），2011，42（增1）:900－904.］

［7］LIU Kuai，JI Zhicheng.RFID network deployment based on hybrid particle swarm optimization［J］.Application Research of Computers，2012，29（4）:1326－1328（in Chinese）.［刘快，纪志成.基于混合粒子群的RFID网络的优化部署［J］.计算机应用研究，2012，29（4）:1326－1328.］

［8］TIAN Jinghe，FAN Yushun，ZHU Yunlong，et al.Chaos neural network modeling and solution for RFID reader anticollision problem［J］.Chinese High Technology Letters，2008，18（8）:217－218（in Chinese）.［田景贺，范玉顺，朱云龙，等.RFID读写器防冲突问题的混沌神经网络建模与求解［J］.高技术通讯，2008，18（8）:217－218.］

［9］GAO Yanfen，SONG Gelian.Researcn on RFID network pianning based on GCPSO aigorithm［J］.Industrial Control Computer，2011，24（2）:4－8（in Chinese）.［高彦芬，宋革联.基于GCPSO算法的RFID读写器网络规划的研究［J］.工业控制计算机，2011，24（2）:4－8.］

［10］QIN Quande，LI Li，CHENG Shi，et al.Interactive learning particle swarm optimization algorithm［J］.CAAI Transactions on Intelligent Systems，2012，7（6）:1－7（in Chi－nese）.［秦全德，李丽，程适，等.交互学习的粒子群优化算法［J］.智能系统学报，2012，7（6）:1－7.］

［11］GAO Zhengwei，PANG Hali，WANG Dingwei，et al.RFID network scheduling based on symbiotic particle swarm optimization［J］.Information and Control，2012，41（5）:564－577（in Chinese）.［高政威，庞哈利，汪定伟，等.基于共生粒子群优化的RFID网络调度［J］.信息与控制，2012，41（5）:564－577.］

［12］WEN Shiguang.Coloring research and application［D］.Shenyang:Northeastern University，2009（in Chinese）.［闻时光.图着色的研究与应用［D］.沈阳:东北大学，2009.］