基于多閱讀器避碰的雙層規(guī)劃及其混合智能優(yōu)化

王垚 張著洪

收稿日期：2020-04-15

基金項目：國家自然科學(xué)基金資助項目（61563009）

作者簡介：王 垚（1995-），男，在讀碩士，研究方向：智能信息處理，Email：1531431965@qq.com.

通訊作者：張著洪，Email：zhzhang@gzu.edu.cn.

摘 要：針對多閱讀器競爭共享介質(zhì)和覆蓋區(qū)域重疊造成射頻信號干擾和碰撞的問題，依據(jù)閱讀器在識別范圍內(nèi)受干擾的程度，將其設(shè)定為稀疏或稠密閱讀器，給出雙層規(guī)劃閱讀器避碰模型，并提出相應(yīng)的雙層規(guī)劃混合智能優(yōu)化算法。將魚群算法的擁擠度和追尾行為引入免疫優(yōu)化算法中，增強(qiáng)群體的局部勘探能力，獲得免疫魚群優(yōu)化算法;進(jìn)而，將此算法作為算子模塊嵌入到遺傳算法中，得到求解此避碰模型的混合智能優(yōu)化算法。比較性的數(shù)值實驗顯示，該算法的搜索效果穩(wěn)定且具有明顯優(yōu)勢。

關(guān)鍵詞：多閱讀器;避碰;免疫優(yōu)化;魚群算法;識別范圍

中圖分類號：TP391?? 文獻(xiàn)標(biāo)識碼： A

物聯(lián)網(wǎng)將信號感知、接入網(wǎng)、互聯(lián)網(wǎng)、射頻識別技術(shù)有機(jī)融合，可實現(xiàn)對具有信息交互功能的事物進(jìn)行遠(yuǎn)程監(jiān)測和控制[1]。它以無線傳感器和射頻識別作為底層，通過信號傳送實現(xiàn)供應(yīng)鏈管理、倉儲盤點(diǎn)、目標(biāo)監(jiān)測、物體追蹤等功能。然而，為了識別信號完全覆蓋的功能區(qū)域，信號覆蓋區(qū)內(nèi)需部署眾多共存的閱讀器。此不可避免會導(dǎo)致多閱讀器競爭共享介質(zhì)，進(jìn)而產(chǎn)生覆蓋區(qū)內(nèi)射頻信號相互交疊或閱讀器碰撞。就此，近來的研究主要集中于探討閱讀器的調(diào)度模型和高效的求解算法。在模型設(shè)計方面，代表性模型包括資源競爭分配模型[1-6]、信干噪比模型[7-8]及基于時隙的避碰模型[9-10]。此類模型中，前者是依據(jù)閱讀器的優(yōu)先級及邊界資源競爭的建模思想而獲得。陳瀚寧等[1]在閱讀器不發(fā)生碰撞限制下，針對網(wǎng)絡(luò)中頻道數(shù)量、時隙分配以及處理效率問題，獲得基于生物行為的射頻識別模型;Roberto等[2]在多閱讀器環(huán)境下，以時隙內(nèi)閱讀器所能覆蓋的標(biāo)簽作為刻畫網(wǎng)絡(luò)能量損耗的性能指標(biāo)，獲得RFID（radio frequency identification， 射頻識別）模型;文獻(xiàn)[3，5]在文獻(xiàn)[1]的模型基礎(chǔ)上，以網(wǎng)絡(luò)讀寫器調(diào)度的效率為性能指標(biāo)，獲得能滿足網(wǎng)絡(luò)讀寫器沖突約束限制的最小化模型;徐進(jìn)[4]建立了基于資源競爭的閱讀器調(diào)度任務(wù)模型，其將閱讀器間的沖突轉(zhuǎn)化為系統(tǒng)資源的競爭，借鑒操作系統(tǒng)的資源管理思想，給出閱讀器調(diào)度問題的形式化描述。信干噪比模型是一種以閱讀器的功率和干擾功率為性能指標(biāo)、頻率和時間為限制條件的模型，可刻畫RFID閱讀器在一個時間段內(nèi)的識別范圍。Li等[7-8]在多閱讀器環(huán)境下，將信干噪比（signal to interference plus noise ratio，SINR）模型獲得的閱讀器覆蓋范圍作為性能指標(biāo)，以閱讀器頻道的選擇間隔為約束限制，獲得RFID 閱讀器避碰模型。基于時隙的避碰模型是在固定頻率下，根據(jù)閱讀器的相對位置而設(shè)計的一種閱讀器分配和調(diào)度模型。Liang等[9]在假定每個閱讀器僅有一個頻道前提下，在時間上對閱讀器的狀態(tài)作嚴(yán)格限制，獲得鄰居避碰模型。

在算法研究方面，可解決閱讀器避碰模型的智能優(yōu)化算法大致有3種類型，即粒子群優(yōu)化[3，5，10]，免疫優(yōu)化[7-8]以及增強(qiáng)學(xué)習(xí)[6]。陳瀚寧等[3]在基本粒子群算法基礎(chǔ)上引入多種群共生的更新策略，獲得能有效求解的多種群共生進(jìn)化粒子群算法，其搜索效果穩(wěn)定，但種群多樣性有待增強(qiáng)。Li等[7-8]基于混合編碼、資源分配策略及免疫網(wǎng)絡(luò)原理，獲得可求解避碰模型的人工免疫網(wǎng)絡(luò)算法。該算法在確定閱讀器識別范圍方面優(yōu)于粒子群優(yōu)化和遺傳算法，但獲得的最佳避碰方案難以確保受干擾小、干擾大的閱讀器均處于最佳狀態(tài)。袁源等[6]結(jié)合RFID系統(tǒng)中閱讀器碰撞問題自身的固有特性，利用Q-學(xué)習(xí)增強(qiáng)算法，獲得閱讀器的頻率最佳分配方案。

綜上，由于RFID系統(tǒng)下閱讀器的布局涉及的約束限制較多且受干擾較為嚴(yán)重，使設(shè)計貼近實際的閱讀器避碰模型較為困難。與此同時，此類模型常為雙層或多級規(guī)劃模型，導(dǎo)致探討求解的算法有一定難度。為此，本文將閱讀器界定為稀疏和稠密兩種類型的基礎(chǔ)上，給出雙層規(guī)劃避碰模型，進(jìn)而探討基于遺傳算法、免疫優(yōu)化和人工魚群算法的雙層混合智能優(yōu)化算法（bi-level programming based hybrid intelligent optimization approach， BPBHIOA），并用于求解稀疏和稠密閱讀器的最大識別半徑。

1 避碰模型描述

給定長、寬分別為L1、L2的矩形內(nèi)N個閱讀器R1、R2、…、RN，第i、j閱讀器Ri、Rj之間的歐氏距離為dij。一般地，根據(jù)閱讀器之間的遠(yuǎn)近，可將閱讀器劃分為兩種類型，即稀疏閱讀器和稠密閱讀器。假定閱讀器的最小、最大識別半徑分別為rd和rD。稱閱讀器Ri為稀疏閱讀器，若Ri的最大識別范圍內(nèi)（半徑為rD）至多包含兩個閱讀器，同時，Ri及其包含的閱讀器的最小識別范圍（半徑為rd）之間不能交疊;否則，將非稀疏閱讀器稱為稠密閱讀器。在此，建立閱讀器避碰模型來表征各閱讀器在最小識別范圍不重疊前提下，最大化各閱讀器的識別范圍。將以上N個閱讀器劃分為兩個集合A和B，即稀疏集A={X1，X2，…，Xp}和稠密集B={Y1，Y2，…，Yq}，p+q=m。當(dāng)A中閱讀器的位置已知時，B中所有閱讀器的最大識別面積之和即為

s（x1，x2，…，xp）=maxy1，y2，…，yq∑qj=1πyj2，（1）

其中，xi和yj分別表示稀疏閱讀器i和稠密閱讀器j的識別半徑，它們之和應(yīng)不小于它們之間的距離dij，即

dij≤xi+yj，rd≤xi，yi≤rD。（2）

另一方面，易知A中所有閱讀器的識別面積之和為

s′=∑pi=1πx2i。（3）

于是，經(jīng)由簡化文[11]中刻畫閱讀器分布特征的性能指標(biāo)，可獲表征使稀疏閱讀器和稠密閱讀器的識別范圍最大的雙層規(guī)劃模型（bi-level programming model， BPM）：

maxx1，x2，…，xpS=∑pi=1πx2i+s（x1，x2，…，xp），

s.t.s（x1，x2，…，xp）=maxy1，y2，…，yq∑qj=1πyj2

dij≤xi+yj，rd≤xi，yj≤rD

1≤i≤p，1≤j≤q。

2 算法設(shè)計與分析

2.1 免疫優(yōu)化算法

免疫優(yōu)化是受生物免疫應(yīng)答理論啟發(fā)而建立的啟發(fā)式隨機(jī)搜索算法，其具有局部探測與全局開采能力強(qiáng)、群體多樣性好且獲全局最優(yōu)解的概率高等優(yōu)點(diǎn)。針對目標(biāo)函數(shù)為f（x）的最大化問題，基本免疫優(yōu)化算法[12]的簡要描述如下：

步1 參數(shù)設(shè)置：種群規(guī)模N，繁殖數(shù)M，閾值濃度σ，選擇率α，突變率η，調(diào)節(jié)因子β，插入率μ。

步2

置n←1。隨機(jī)生成N個抗體，構(gòu)成初始抗體群An，初始記憶池Mset為空集。

步3

依據(jù)下式計算An中抗體的親和度：

a（x）=1/（1+e-ηf（x）），0<η<1。（4）

步4

依據(jù)選擇率α，在An中選取親和度較高的抗體構(gòu)成群體Bn，且更新記憶池Mset。

步5

依據(jù)繁殖規(guī)模M，Bn中每個抗體x依據(jù)下式（5）繁殖m（x）個克?。?/p>

m（x）=M×ax∑z∈Bnaz。（5）

步6

對于每個抗體x的克隆，依據(jù)自適應(yīng)變異概率p（x）=e-a（x）實施均勻變異，獲已變異的克隆集Cn，并計算克隆的親和度。

步7

依據(jù)克隆的親和度和抑制半徑σ，清除 Cn中冗余的克隆，獲克隆集C′n。

步8

依據(jù)下式

cx=axe-{v∈XA（x，v）≤σ}N（6）

計算Bn∪C′n中親和度較高的N個抗體，并按類似于比例選擇的方式選擇N-d個抗體，此與隨機(jī)生成的d個抗體構(gòu)成群體An+1，其中d=「μN(yùn)。

步9

n←n+1。 若n小于給定的最大迭代數(shù)，則返步3;否則，輸出An中親和度最大的抗體。

以上算法具有群體多樣性好、魯棒性強(qiáng)的優(yōu)點(diǎn)。比較相關(guān)的幾種啟發(fā)式算法，該算法的搜索效果具有一定的優(yōu)勢，但搜索效率受到抗體的克隆規(guī)模和抑制半徑的影響較大，且算法結(jié)構(gòu)有待進(jìn)一步優(yōu)化。

2.2 人工魚群算法

人工魚群算法是一種基于魚群覓食行為特性而設(shè)計的群智能優(yōu)化算法。算法步驟描述[13]如下：

步1

參數(shù)設(shè)置：魚群規(guī)模N，嘗試次數(shù)Nt，移動步長s，感知范圍V，擁擠度δ。

步2

置迭代數(shù)n←1。隨機(jī)生成規(guī)模為N的人工魚群A，人工魚i的狀態(tài)為xi=（x1，x2，…，xn）， xj為f（x）的決策向量中第j個分量。

步3

覓食行為：對A中每條人工魚xi，經(jīng)由y=xi+rand（）·V，在xi的感知域內(nèi)隨機(jī)生成人工魚y。若f（xi）>f（y），則重復(fù)嘗試至多Nt次生成y;若f（xi）

x′i←xi+rand（）·s·y-xi‖y-xi‖，

（7）

由此獲得的N條人工魚x′i構(gòu)成群體B。

步4

聚群行為：在群體B中每條人工魚x′i的V鄰域內(nèi)，確定其伙伴數(shù)目nf及中心伙伴xc。若f（xc）<δnff（x′i），則經(jīng)由下式確定x′i的移動位置x″i：

x″i←x′i+rand（）·s·

xc-x′ixc-x′i;（8）

否則，x″i←x′i。由此產(chǎn)生的人工魚x″i構(gòu)成群體C。

步5

追尾行為：在C中每條人工魚x″i的V鄰域內(nèi)，確定其伙伴數(shù)目nf及伙伴中目標(biāo)值最大的伙伴xc，進(jìn)而按照步4的方式更新群體C，獲得新群體D。

步6

在D中，每條人工魚在其半徑為V的鄰域內(nèi)，隨機(jī)生成新的人工魚更新此人工魚，獲得的群體更新當(dāng)前群體A。

步7

n←n+1。若n小于最大迭代數(shù)Gmax，則返回步3;否則，輸出A中目標(biāo)值最大的人工魚。

以上人工魚群算法在運(yùn)行初期，由于人工魚較為分散，步4～5的計算量較小，算法運(yùn)行速度快;可是，在運(yùn)行中、后期，因人工魚過分擁擠，導(dǎo)致步4～5的計算量較大，從而算法的運(yùn)行效率低。另一方面，算法運(yùn)行后期因人工魚過度擁擠，加之步6促使人工魚隨機(jī)游動，使得算法的收斂速度變慢且易于陷入局部搜索。

2.3 雙層規(guī)劃混合智能優(yōu)化算法

依據(jù)以上雙層規(guī)劃模型BPM，BPBHIOA由內(nèi)、外兩個尋優(yōu)模塊構(gòu)成，算法流程圖如圖1所示。圖1（a）是免疫魚群算法（immune fish swarm approach， IFSA）的流程圖，其作為BPBHIOA的內(nèi)循環(huán)，被用于尋找BPM的各密集閱讀器在滿足約束限制下的最大識別半徑。它是由以上免疫優(yōu)化算法中的克隆選擇、繁殖、記憶更新、群體更新，以及人工魚群算法中人工魚的位置移動策略構(gòu)成的算法。此算法中，人工魚的位置更新策略被用于增強(qiáng)算法的局部勘探能力和群體多樣性，同時抗體的選擇與更新的主要作用在于增強(qiáng)群體的開采能力。另外，圖1（b）是以遺傳算法GA作為算法框架且IFSA作為內(nèi)嵌模塊的BPBHIOA流程圖。在此，GA由比例選擇、單點(diǎn)隨機(jī)交叉和均勻變異構(gòu)成，其作用是尋找BPM的稀疏閱讀器的最大識別半徑。

針對模型BMP，為便于算法表述，讓x和y分別表示p個稀疏閱讀器及q個稠密閱讀器的識別半徑變量構(gòu)成的向量，即（x1， x2，…，xp）和（y1，y2，…，yq），且分別被視為個體和抗體?？贵w和人工魚被視為同一說法。結(jié)合以上的算法流程圖，BPBHIOA的詳細(xì)步驟描述如下：

步1

輸入?yún)?shù)的設(shè)置。GA的參數(shù)：群體規(guī)模Nout，交叉概率pc、變異概率pm;IFSA的參數(shù)：群體規(guī)模Nin，繁殖數(shù)M，更新率τ，記憶池規(guī)模m，插入率μ， 擁擠度δ，感知距離V，移動步長s， 內(nèi)、外最大迭代數(shù)gmax及Gmax。

步2

置n←1。初始化規(guī)模為N的個體群P={x1，x2，…，xNout}。

步3

（算法IFSA的描述）對P中每個個體xi，1≤i≤N，執(zhí)行步3.1～3.7，獲取相應(yīng)的最優(yōu)的抗體yi*。

步3.1

置n←1，Mset←。 初始化規(guī)模為Nin的抗體群A={y1， y 2，…，yNin}，計算抗體的親和度。

步3.2

依據(jù)式（5）降冪排列A中的抗體，將A等分為B、C兩個種群，其中B由親和度較高的抗體構(gòu)成;在A中抽取親和度較高的前m個抗體更新記憶池Mset，其中，m

步3.3

B中各抗體依據(jù)下式計算濃度：

c（y）=2N∑z∈B，z≠y1‖z-y‖。（9）

類似地，計算C中各抗體的濃度。

步3.4

確定B中每條人工魚y在其V鄰域內(nèi)的伙伴數(shù)目nf及伙伴中親和度最大的伙伴z;若c

（y）<δnfc（z），則y的移動位置y′由下式確定：

y′=y+rand（）·s·y-zy-z。

（10）

且滿足BMP的約束限制y′j≥dij-xi;否則，由下式計算y的繁殖概率：

P=λa（y）∑z∈Aa（z）+（1-λ）C（y）∑z∈AC（z）。

（11）

若繁殖概率小于τ，則在記憶池中隨機(jī)抽取記憶抗體y′替代y。

步3.5

對C中親和度較低的前m條人工魚，利用記憶池Mset中的抗體按下式更新：

y′=yMset+rand（）·V。（12）

其中，yMset為記憶池中隨機(jī)選取的抗體。

步3.6

在B∪C的親和度較高的N個抗體中，經(jīng)由比例選擇挑選N-d個抗體與隨機(jī)生成的d個抗體構(gòu)成群體D，計算此隨機(jī)生成的新抗體的親和度，其中d=「μN(yùn)。

步3.7

k←k+1。如果k

步4

依據(jù)yi*計算個體xi的適應(yīng)度，1≤i≤Nout。

步5

群體P經(jīng)由比例選擇、單點(diǎn)隨機(jī)交叉、均勻變異作用后，獲規(guī)模為Nout的群體Q。

步6

對于Q中每個個體x，利用步3.1～3.7計算相應(yīng)的最優(yōu)抗體y*。

步7

計算Q中個體的適應(yīng)度，其適應(yīng)度最低的個體被P中適應(yīng)度最高的個體取代。

步8

P←Q;n←n+1。若n

以上算法中，步3 是算法IFSA的描述，其用于在給定一個個體（稀疏閱讀器的識別半徑）前提下，尋找對應(yīng)的最優(yōu)抗體（稠密閱讀器的最好識別半徑），其中步3.4需結(jié)合模型BMP的約束限制更新抗體群;步4～7是GA進(jìn)化的一個迭代周期，其用于更新個體進(jìn)化群。

經(jīng)由以上算法的設(shè)計，BPBHIOA的計算復(fù)雜度由步3.2～3.4確定，如此3步的復(fù)雜度分別為O（Nin2）、O（N12q）及O（N12+q）。因此，該算法在最差情形下的計算復(fù)雜度為O（Nin2+ N12q）。

3 數(shù)值實驗

Windows7/ CPU 3.70 GHz/RAW4.0 GB/ VC++環(huán)境下執(zhí)行數(shù)值實驗。為驗證BPBHIOA解決BMP的有效性，首先檢測其包含的算法IFSA能否有效處理一般連續(xù)函數(shù)優(yōu)化問題，然后通過事例測試其能否有效確定稀疏、稠密閱讀器的最大識別范圍。參與IFSA比較的算法包括人工魚群算法AFS[14]、多種群遺傳算法MPGA[15]及粒子群優(yōu)化算法PSO[16]。測試事例為文獻(xiàn)[12-13]中的最大化測試函數(shù)f1—f6，其最大值依次為38.85、1.005 4、1.0、3 600、0.632 69及3.647 9。為回避隨機(jī)因素對算法性能評價的影響，各算法在最大迭代數(shù)為500下獨(dú)立求解每種測試問題100次。參與比較的算法的參數(shù)設(shè)置源自相應(yīng)的文獻(xiàn)。算法調(diào)試后，IFSA的參數(shù)設(shè)置是N=30，pc=0.6，pm=0.06，M=100，τ=0.3，λ=0.55，δ=0.618，d=1，s=0.2。

3.1 標(biāo)準(zhǔn)測試問題的實驗結(jié)果與分析

算法IFSA、AFS、MPGA、PSO分別求解函數(shù)f1—f6 100次后，獲得的統(tǒng)計結(jié)果如表1所示。由此表可知，相比于參與比較的算法，IFSA求解每種測試函數(shù)均能整體上獲得最大的平均目標(biāo)值。同時經(jīng)由min、max及St.Dev的值可知，此算法的收斂精度高且搜索效果穩(wěn)定。另外，MPGA比PSO和FSA獲得的解質(zhì)量好，且搜索效果也相對較穩(wěn)定;除函數(shù)f4外，PSO比FSA獲得的解質(zhì)量要好，且得到的解的精度要高。通過比較此4種算法的方差獲知，它們求解除函數(shù)f4外的其它測試函數(shù)均能獲得次優(yōu)解，特別IFSA獲得的解逼近最優(yōu)解的精度高。對于函數(shù)f4，IFSA具有較好的收斂性，搜索效果好，但其它算法的搜索效果的波動性較大且獲得的解的質(zhì)量欠理想。

3.2 避碰問題的實驗結(jié)果與分析

在靜態(tài)環(huán)境下，選取100×100的正方形區(qū)域。在此區(qū)域內(nèi)隨機(jī)投放的閱讀器數(shù)目m取80或200。當(dāng)m=80時，選取rd=1.0，rD=10;當(dāng)m=200時，選取rd=1.5，rD=10。在此，將BPBHIOA中的內(nèi)循環(huán)算法IFSA依次用PSO、FSA、MPGA取替之后，獲得的算法也與原算法同名，并將此3種算法與BPBHIOA在此測試情形進(jìn)行比較。在給定的閱讀器數(shù)目下，各算法求解模型BMP獲得的最好解（m個閱讀器的識別半徑向量）對應(yīng)的目標(biāo)函數(shù)值比較如表2所示。各算法獲得各閱讀器的識別范圍及算法搜索曲線如圖2～4所示。

由表2獲知，無論閱讀器的規(guī)模偏小還是偏大，BPBHIOA獲得的解的目標(biāo)值，即所有閱讀器的識別范圍的面積總和，均比其它算法獲得的目標(biāo)值大。此表明，該算法在人工魚位置更新策略下，能較好地勘探具有潛在價值的解，同時算法的變異操作有助于回避約束條件的處理。其次，其它算法獲得的目標(biāo)值之間的偏差較小，因此它們的搜索能力較為相近。另外，圖2～3表明，BPBHIOA獲得的閱讀器調(diào)度方案幾乎能滿足每個閱讀器的識別圓圈（即識別范圍）與多個識別圓圈相切，因此該算法的解能盡可能使閱讀器之間不能被識別的區(qū)域（即閑置區(qū)域）變得窄;MPGA的解導(dǎo)致閑置區(qū)域較寬;PSO和FSA獲得的解的質(zhì)量比MPGA的高，因而產(chǎn)生的閑置區(qū)域比MPGA的窄。圖4說明，以上算法的收斂性不受閱讀器規(guī)模的影響，但收斂速度有差異。BPBHIOA易于在短時間內(nèi)收斂且獲得的解質(zhì)量好，其它算法的進(jìn)化能力偏弱，易于陷入局部搜索，導(dǎo)致獲得的解質(zhì)量偏低。

4 結(jié)論

受閱讀器的射頻信號之間易于發(fā)生沖突的啟發(fā)，研究刻畫閱讀器群的射頻信號避碰的雙層規(guī)劃模型。將免疫優(yōu)化與人工魚群優(yōu)化算法有機(jī)結(jié)合，得到可解決連續(xù)函數(shù)優(yōu)化的免疫魚群算法（IFSA），進(jìn)而將IFSA融入遺傳算法中，得到可解決閱讀器避碰的雙層規(guī)劃混合智能優(yōu)化算法（BPBHIOA）。算法的計算復(fù)雜度主要由IFSA的群體規(guī)模和稠密閱讀器的規(guī)模確定。實驗結(jié)果已驗證，已獲的閱讀器避碰模型是合理的，且BPBHIOA是有效的。

參考文獻(xiàn)：

[1]陳瀚寧， 朱云龍， 胡琨元.? 基于多種群共生進(jìn)化的 RFID 網(wǎng)絡(luò)優(yōu)化[J].? 解放軍理工大學(xué)學(xué)報（自然科學(xué)版），? 2008，? 9（5）：? 413-416.

[2]ROBERTO A，? PIERGIUSEPPE D M，? FORTUNATO S，? et al.? Backscattering UWB/UHF hybrid solutions for multi-reader multi-tag passive RFID systems[J].? EURASIP Journal on Embedded Systems，? 2016，? 2016（1）：? 214-219.

[3]劉微.? 基于生物行為的射頻識別系統(tǒng)優(yōu)化模型與算法研究[D].? 長春：? 吉林大學(xué)，? 2011.

[4]徐進(jìn).? 復(fù)雜環(huán)境中RFID閱讀器管理技術(shù)研究[D]. 成都：? 電子科技大學(xué)， 2016.

[5]陳繼光.? 高速公路RFID讀寫器的可靠組網(wǎng)方[J].? 物聯(lián)網(wǎng)技術(shù)，? 2014，? 4（5）： 16-18.

[6]袁源， 鄭嘉利， 石靜， 等.? 基于Q-learning的RFID多閱讀器防碰撞算法[J].? 計算機(jī)科學(xué)，? 2019， 46（6）：? 124-127.

[7]LI Z H，? HE C H.? Optimal scheduling-based RFID reader-to-reader collision avoidance method using artificial immune system[J].? Applied soft computing，? 2013， 13（5）：? 2557-2568.

[8]LI Z H，? LI J M，? HE C H.? Artificial immune network-based anti-collision algorithm for dense RFID readers[J].? Expert Systems with Applications，? 2014，? 41（10）：? 4798-4810.

[9]LIANG C G，? LIN H M.? Using dynamic slots collision tracking tree technique towards an efficient tag anti-collision algorithm in RFID systems[J].? Mathematics and Computation，? 2014，? 233：? 260-271.

[10]

ZHAO J，?? LI N，?? LI D，? et al.? Collision alignment：? an RFID anti-collision algorithm assisted by orthogonal signal detection and analogy principle[J].?? IEEE? International? Conference on Networking，? 2017， 66（13），? 131-144.

[11]段力畑.? RFID系統(tǒng)優(yōu)化調(diào)度模型及算法研究[D]. 太原： 太原理工大學(xué)，? 2017.

[12]黃席樾， 張著洪， 何傳江， 等.? 現(xiàn)代智能算法理論及應(yīng)用[M].? 北京： 科學(xué)出版社，? 2005

[13]李曉磊.? 一種新型的智能優(yōu)化方法-人工魚群算法[D].? 杭州：? 浙江大學(xué)，? 2003.

[14]傅彬.? 基于改進(jìn)人工魚群算法在無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化中的研究[J]. 計算機(jī)系統(tǒng)應(yīng)用，? 2015，? 24 （12）：? 223-227.

[15]張妍.? 基于多種群遺傳算法的模糊測試方法研究[D].? 北京： 北京理工大學(xué)，? 2017.

[16]梁櫻馨.? WSN粒子群覆蓋優(yōu)化算法研究[D].? 蘭州： 蘭州交通大學(xué)，? 2018.

（責(zé)任編輯：曾 晶）

Multi-Reader Collision Avoidance-based Bi-Level Programming and

its Hybrid Intelligent Optimization

WANG Yao， ZHANG Zhuhong*

（College of Big Data and Information Engineering， Guizhou University， Guiyang 550025， China）

Abstract：

Aiming at the problem of radio-frequency signal interference and collision caused by multi-reader's competing shared communications medium and coverage area overlap， this study designs a bi-level programming reader collision avoidance model and proposes a new bi-level hybrid intelligent optimization approach to solve the optimal collision avoidance scheme. The model includes sparse and dense readers defined in virtue of readers' interference degree within their identification regions. Based on the basic framework of genetic algorithm， the approach also includes a new immune fish swarm approach， acquired by embedding the fish swarm algorithm's crowding degree and rear-end behavior into a basic immune optimization algorithm in order to promote the local exploitation of population. Numerically comparative experiments have validated that the proposed bi-level optimization approach is of strong stability and can win over the compared approaches.

Key words：

multi-reader; collision avoidance; immune optimization; fish swarm algorithm; identification range