基于负载平衡与粒子群算法的射频识别网络布局方法

摘要

本发明公开了一种基于负载平衡与粒子群算法的射频识别网络布局方法，主要解决现有技术用遗传算法布局网络易出现早熟、收敛速度慢、稳定性差的问题。其技术方案是：1.对粒子群个体进行初始化编码；2.计算粒子群中每个个体的适应度值；3.比较每个个体的适应度值，计算出全局最优个体；4.根据全局最优个体的信息，利用粒子群优化方法更新粒子群中每个个体的位置信息；5.判断是否满足终止条件，若是，则进行试探性删除计算，输出最优个体，否则返回步骤2。本发明具有初始种群规模小，收敛速度快，稳定性高的优点，可以有效的解决射频识别网络布局问题。

说明书

技术领域

本发明属于网络技术领域，具体涉及一种射频识别网络布局优化方法，可用于网络 规划。

背景技术

近些年来，射频识别RFID技术作为物联网技术的一个代表，越来越多的受到研究者 的关注。在RFID系统中也涉及许多方面的技术问题，如随着RFID技术的发展和广泛应 用，RFID网络的布局优化问题就成为一项急剧挑战性的工作。对于RFID网络布局优化 问题，这里涉及到许多约束条件和目标，并已被证明是NP-hard问题。RFID网络布局优 化问题的目的就是满足在一定的约束条件，如标签覆盖率，阅读器的数量，干扰，负载 平衡，找到阅读器的最佳位置。

目前文献中提出了大量的解决方法，大致可分为三类：最优化算法、启发式算法、 元启发式算法。其中，元启发式算法主要包括遗传算法、模拟退火算法、禁忌搜索算法、 粒子群优化算法等。RFID网络布局问题属于组合优化问题，元启发式算法是目前被普遍 认为在性能、可扩展性和易于实现性等方面权衡后的最佳方法。其中，遗传算法是最常 用的一种元启发式算法。更广义的地说，遗传算法属于一种进化算法，由于进化算法与 传统优化方法相比，具有简单、通用、鲁棒性强和便于并行化处理等优点，已被广泛应 用于数值优化、组合优化、分类器设计等领域。但实践也表明，仅仅使用以遗传算法为 代表的进化算法来模仿生物处理事物的智能还是远远不够的，还必须更加深层地挖掘与 利用生物的智能资源。在遗传算法中，用于产生子代的个体是根据适应度从整个种群中 选择出来的，因此必须预先确定整个种群的适应度分布。但在自然界中并不存在全局选 择，也无法计算全局的适应度分布。事实上，自然选择本身是一种局部现象，它只与个 体所在的局部环境有关。也就是说，某一阶段，自然进化是一个局部过程，它通过渐渐 扩散，才使得信息为全局共享。因此，用遗传算法求解RFID网络布局问题不能很好的模 仿生物处理事物的智能，另外遗传算法还有易早熟收敛、收敛速度慢、稳定性差等缺点， 从而无法得到好的网络布局方案。

发明内容

本发明的目的在于提出一种基于负载平衡与粒子群算法的射频识别网络布局方法， 以克服上述遗传算法的不足，实现对RFID网络的更好布局。

为实现上述目的，本发明的技术方案是这样实现的：

(1)根据射频识别网络设置模型参数：电磁波的波长λ＝0.328m，阅读器与标签通信 的门槛功率R_q＝-14dBm，阅读器的天线增益G₁＝6.7dBi；标签的天线增益G₂＝3.7dBi；

(2)设置粒子群优化算法参数：设粒子群优化的最大粒子个数M＝20，优化最大代 数N＝1000，优化的代数gen，其取值在0～N-1；设置保存每一代中适应度最大个体信息 的结构体数组为B[m][M]，设置保存全局适应度最大个体信息的结构体数组为G[M]；

(3)输入射频识别网络中的标签位置坐标和个数，对该射频识别网络中的阅读器位 置坐标和发射功率进行编码初始化：

3a)在50m×50m二维平面内，随机的产生M个阅读器的个体；

3b)初始化M个阅读器的个体的位置坐标及发射功率：随机的产生阅读器的个体的 位置坐标，且位置坐标是0～50m内的一个随机实数，同时随机的产生阅读器的个体的发 射功率，且发射功率是在20～33dBm内的一个随机实数；

3c)设进化的代数gen＝0；

(4)判断是否满足进化的代数gen<N，若是，执行步骤(5)，否则，跳转到步骤(9)；

(5)计算每个个体的适应度值，该适应度值包括：标签的覆盖率COV，负载平衡约 束的信息熵F，阅读器的干扰ITF，阅读器数量N_r；

(6)按照目标函数的重要程度依次排序；

(7)对重要程度最强的个体按照适应度值从大到小进行排序，将适应度值最大的个 体信息存放在结构体数组B[m][M]中；

(8)更新第gen代个体的位置坐标；

(9)计算出全局的最优个体，将其信息存于结构体数组G[M]中，并进行试探性的删 除计算；

(10)判断是否满足终止条件：如果是，则输出结构体数组G[M]中阅读器的最优位 置，否则，将gen自加1，返回步骤(4)。

本发明与现有的技术相比具有以下优点：

1.本发明由于将RFID网络布局系统与进化算法相结合，设计了一种基于负载平衡约 束的射频识别网络布局优化方法，与传统遗传算法中种群的模型相比，粒子群的网络模 型更接近于真正的自然进化机制，能够得到更好的布局方案。

2.本发明由于采用了依次比较目标函数的策略和试探删除算子，使粒子群算法种群 规模小，收敛速度快，稳定性高。

3.本发明由于采用了粒子群进化方法，该方法不仅使用于求解RFID网络布局问题， 同时也可以将该方法扩展到求解其它带有优先关系限制的组合优化问题。

附图说明

图1是本发明的实现流程图；

图2是本发明的射频识别网络模型图。

具体实施方式

如图2所示，射频识别RFID网络模型，主要有标签和阅读器组成，标签与读写器之 间通过电磁波实现通信，阅读器发射能量信号，通过阅读器的天线将信号发射出去，标 签通过自身天线完成接收功能。

参照图1，本发明的具体实施步骤如下：

步骤1.设置参数网络参数。

根据射频识别网络模型设置如下参数：

电磁波的波长λ＝0.328m，阅读器与标签通信的门槛功率R_q＝-14dBm，阅读器的天 线增益G₁＝6.7dBi；标签的天线增益G₂＝3.7dBi。

步骤2.设置粒子群进化算法参数。

在函数优化领域通常使用粒子群算法进行目标优化，由于粒子群算法中涉及的参数 很多，本实例根据需要设置如下参数：

设粒子群的最大粒子个数M＝20，优化最大代数N＝1000，优化的代数gen为0～N-1；

设置保存每一代中适应度最大个体信息的结构体数组为B[m][M]，设置保存全局适 应度最大个体信息的结构体数组为G[M]。

步骤3.输入射频识别网络中的标签位置坐标和个数，对该射频识别网络中的阅读 器位置坐标和发射功率进行编码初始化。

3a)在50m×50m二维平面内，随机的产生M个阅读器的个体；

3b)初始化M个阅读器的个体的位置坐标及发射功率：随机的产生阅读器的个体的 位置坐标，且位置坐标是0～50m内的一个随机实数，同时随机的产生阅读器的个体的发 射功率，且发射功率是在20～33dBm内的一个随机实数；

3c)设进化的代数gen＝0。

步骤4.判断是否满足进化的代数gen<N，若是，执行步骤5，否则，跳转到步骤9。

步骤5.计算每个个体的适应度值。

每个个体的适应度值包括标签覆盖率COV、负载平衡的信息熵F、阅读器的干扰 ITF、阅读器数量N_r，这些参数的计算如下：

5a)将射频识别网络的标签覆盖率COV定义为：

COV＝∑_t∈TSC_v(t)/N_t×100％

其中，C_v(t)表示每个标签的覆盖率，N_t是分布在工作区域中的标签的个数，是 标签t收到的来自阅读器r₁的功率，R_q是读写器与标签之间通信的最小功率，是标 签t收到的来自阅读器r₂的功率，RS是阅读器的集合，r₁和r₂是阅读器集合中的两个不 同的元素，TS代表标签的集合；

5b)计算反映负载平衡约束的信息熵F：

$F=-{\Sigma }_{i=1}^{\left|\mathrm{TS}\right|}(n_i/|\mathrm{TS}\left|\right)\mathrm{In}(n_i/|\mathrm{TS}\left|\right)/\mathrm{In}\left(\right|\mathrm{RS}\left|\right),$

其中n_i是第i个阅读器负载的标签个数，RS是阅读器的集合，TS代表标签的集合；

5c)计算阅读器的干扰ITF：

ITF＝∑_t∈TSγ(t)，

其中γ(t)表示每个标签的干扰，γ(t)＝∑P_r,t-max{P_r,t},r∈RS∩P_r,t≥R_q，R_q是读写 器与标签之间通信的最小功率，P_r,t是标签t收到的来自阅读器r的功率，RS是阅读器 的集合，r是阅读器集合中的一个元素，t是标签集合中的一个元素；

5d)将射频识别网络布局问题中阅读器数量N_r表示为：N_r＝N_max-N_red，其中 N_max表示分布在工作区域中阅读器的总数，N_red表示发现多余的阅读器的个数。

步骤6.按照目标函数的重要程度依次排序。

6a)将步骤5中计算出的当前个体的适应度值与之前适应度值最大的个体进行比较 判断：

如果当前个体适应度值中的标签覆盖率比个体之前的最大标签覆盖率小，则结束当 前目标函数的重要程度排序；

如果当前个体适应度值中的标签覆盖率比个体之前的最大标签覆盖率大，则更新当 前的适应度值最大的个体；

如果两个值一样，则将当前的负载平衡信息熵比与个体之前最大的负载平衡信息熵 进行比较；若当前的负载平衡信息熵比个体之前最大的负载平衡信息熵小，则结束当前 目标函数的重要程度排序；若当前的负载平衡信息熵比个体之前最大的负载平衡信息熵 大，则更新当前的适应度值最大的个体；若当前的负载平衡信息熵比个体之前最大的负 载平衡信息熵相等，则将当前的阅读器的干扰比与个体之前最小的阅读器的干扰值进行 比较；

如果当前的阅读器的干扰比个体之前的阅读器最小的干扰值大，则结束当前目标函 数的重要程度排序；

如果当前的阅读器的个数比个体之前的阅读器最小的干扰值小，则更新当前的适应 度值最大的个体；

如果当前的阅读器的干扰与个体之前的阅读器最小的干扰值相等，则将当前的阅读 器的个数比与个体之前阅读器最少的个数值进行比较；对于当前的阅读器的个数不大于 个体之前阅读器最少个数的情况，则更新当前适应度值最大的个体；否则，结束当前目 标函数的重要程度排序；

6b)将适应度值最大的个体的顺序更新为当前目标函数的重要程度排序。

步骤7.对重要程度最强的个体按照适应度值从大到小进行排序，将适应度值最大的 个体信息存放在结构体数组B[m][M]中。

步骤8.更新第gen代个体的位置坐标。

8a)将当前的个体位置信息更新为局部的最优个体pBest_i；

8b)对当前代中适应度值最大的个体按照适应度值的大小排序，将适应度值最大的 个体更新为全局的最优个体gBest；

8c)计算每个的个体速度矢量V_i：

V_i＝(ω×V_i+c₁×rand₁)×(pBest_i-X_i)+c₂×rand₂×(gBest-X_i)，

其中，i是每个粒子的索引，i＝1,2,...,M，ω是惯性权重惰性系数，取值为0.4～0.9， c₁，c₂是两个加速系数，c₁＝c₂＝2.0，rand₁和rand₂是在[0,1]之间的两个随机数，X_i是 每个个体的当代位置信息；

8d)利用个体速度矢量V_i更新每个的个体位置信息X′_i：X′_i＝X_i+V_i。

步骤9.计算出全局的最优个体，将其信息存于结构体数组G[M]中，并进行试探性 的删除计算。

9a)计算全局最优个体的标签的覆盖率；如果覆盖率大于90％，则执行9b)；否则， 继续保留全局最优个体对应的阅读器；

9b)先试探性地减少读写器的个数，再计算删除后标签的覆盖率，若删除标签后覆 盖率依然大于90％，则删除全局最优个体对应的阅读器；否则，继续保留全局最优个体 对应的阅读器。

步骤10.判断是否满足终止条件：如果是，则输出结构体数组G[M]中阅读器的最 优位置，否则，将gen自加1，返回步骤4。

本发明的效果可以通过以下仿真实验进行验证：

1.实验运行环境和条件设置

实验运行的环境：处理器为Intel(R)Core(TM)2 Duo CPU E6550@2.33GHz，内存为 1.99GB，硬盘为500G，操作系统为Microsoft windows XP Professional 2002，编程环境为 MATLAB 7.13。

设置粒子群算法种群的大小M＝20，最大的迭代代数设置为1000，惰性系数ω设置 为0.4～0.9，加速系数c₁＝c₂＝2.0；阅读器的发射功率调节范围20～33dBm；电磁波的波 长λ＝0.328m；阅读器与标签通信的门槛功率R_q＝-14dBm；阅读器的天线的增益 G₁＝6.7dBi；标签的天线增益G₂＝3.7dBi。

2.实验内容和结果分析

仿真实验1，用本发明对在二维平面的分布是非均匀的30个标签、50个标签和100 个标签的情况下，分别进行测试仿真，其中C30表示有30个标签，C50表示有50个标 签，C100表示有100个标签，为了排除初始化的随机性，对每种实例都计算20次，得 到四个目标函数的平均值和最优值的结果报告，结果如表1所示。

表1标签非均匀分布测试结果

从表1可以看出，所有的实例标签的覆盖率的平均值范围是大于95％，并且所 有实例标签的覆盖率最优值都达到100％；干扰平均值和最优值都达到了0.000；对 实例C30阅读器的个数基本在4个，对实例C50阅读器的个数基本在5个，对实例 C100阅读器的个数基本在5个；同时，对于所有的实例，负载指数平均值都大于 0.8,最优值达到1，即在保证其他的目标函数的情况下，每一个阅读器都尽可能的 负载了相同数量的标签。

仿真实验2，用本发明对在二维平面的分布是均匀的30个标签、50个标签和 100个标签的情况下，分别进行测试仿真，为了排除初始化的随机性，对每种实例 都计算20次，得到四个目标函数的平均值和最优值的结果报告，结果如表2所示。

表2标签均匀分布测试结果

从表2可以看出，所有的实例标签的覆盖率的平均值范围是大于93％，并且所 有实例标签的覆盖率最优值都达到100％；干扰平均值和最优值都达到了0.000；对 实例C30阅读器的个数基本在6个，对实例C50阅读器的个数基本在8个，对实例 C100阅读器的个数基本在9个；同时，对于所有的实例，负载指数平均值都大于 0.9,最优值达到1，即在保证其他的目标函数的情况下，每一个阅读器都尽可能的 负载了相同数量的标签。