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

王 垚，張著洪

(貴州大學 大數據與信息工程學院，貴州 貴陽 550025)

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

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

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

1 避碰模型描述

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

(1)

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

dij≤xi+yj,rd≤xi,yi≤rD。

(2)

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

(3)

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

2 算法設計與分析

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

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

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

步2 置n←1。隨機生成N個抗體，構成初始抗體群An，初始記憶池Mset為空集。

步3 依據下式計算An中抗體的親和度：

a(x)=1/(1+e-ηf(x)),0<η<1。

(4)

步4 依據選擇率α，在An中選取親和度較高的抗體構成群體Bn，且更新記憶池Mset。

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

(5)

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

步8 依據下式

(6)

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

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

2.2 人工魚群算法

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

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

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

步3 覓食行為：對A中每條人工魚xi，經由y=xi+rand()·V，在xi的感知域內隨機生成人工魚y。若f(xi)>f(y)，則重復嘗試至多Nt次生成y；若f(xi)

(7)

由此獲得的N條人工魚x′i構成群體B。

(8)

否則，x″i←x′i。由此產生的人工魚x″i構成群體C。

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

步6 在D中，每條人工魚在其半徑為V的鄰域內，隨機生成新的人工魚更新此人工魚，獲得的群體更新當前群體A。

步7n←n+1。若n小于最大迭代數Gmax，則返回步3；否則，輸出A中目標值最大的人工魚。

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

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

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

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

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

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

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

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

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

圖1 算法流程圖Fig.1 Algorithm flow chart

步3.3B中各抗體依據下式計算濃度：

(9)

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

步3.4確定B中每條人工魚y在其V鄰域內的伙伴數目nf及伙伴中親和度最大的伙伴z；若c(y)<δnfc(z)，則y的移動位置y′由下式確定：

(10)

(11)

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

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

y′=yMset+rand()·V。

(12)

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

步3.6在B∪C的親和度較高的N個抗體中，經由比例選擇挑選N-d個抗體與隨機生成的d個抗體構成群體D，計算此隨機生成的新抗體的親和度，其中d=「μN?。

步3.7k←k+1。如果k

步4 依據yi*計算個體xi的適應度，1≤i≤Nout。

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

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

步7 計算Q中個體的適應度，其適應度最低的個體被P中適應度最高的個體取代。

步8P←Q；n←n+1。若n

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

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

3 數值實驗

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

3.1 標準測試問題的實驗結果與分析

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

3.2 避碰問題的實驗結果與分析

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

表1 各算法求解以上6種測試問題的統(tǒng)計結果比較Tab.1 Comparison of statistical results of algorithm for solving the above six test problems

表2 算法獲得的閱讀器識別面積(目標值)比較Tab.2 Comparison of reader recognition area (target value) obtained by algorithm

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

圖2 m=80：各算法獲得的閱讀器識別范圍比較Fig.2 m=80:The recognition range comparision of reader obtained by each algorithm

圖3 m=200：各算法獲得的閱讀器識別范圍比較Fig.3 m=200:The recognition range comparision of reader obtained by each algorithm

圖4 各算法求解閱讀器為80、200的收斂曲線比較Fig.4 The convergence curves comparison of 80, 200 reader of each algorithm

4 結論

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