基于粒子群與圖著色的RFID閱讀器網(wǎng)絡(luò)優(yōu)化

劉 鷹，趙小晴，張開偉

（哈爾濱工程大學(xué)自動(dòng)化學(xué)院，黑龍江哈爾濱150001）

0 引 言

射頻識(shí)別（radio frequency identification，RFID）是一種無需在識(shí)別系統(tǒng)與目標(biāo)之間建立接觸，僅通過無線射頻信號(hào)就能識(shí)別目標(biāo)并讀寫相關(guān)數(shù)據(jù)的非接觸式自動(dòng)識(shí)別系統(tǒng)［1］。隨著RFID的大范圍應(yīng)用，它也出現(xiàn)了一些未解決的問題。多個(gè)閱讀器感知范圍有重疊時(shí)，對(duì)處于重疊區(qū)中的標(biāo)簽有干擾，會(huì)影響閱讀器與其各自感知范圍內(nèi)的標(biāo)簽之間的通訊，甚至使得整個(gè)定位系統(tǒng)崩潰，所以就需要對(duì)RFID無線網(wǎng)絡(luò)中的閱讀器進(jìn)行規(guī)劃。RFID閱讀器網(wǎng)絡(luò)的合理規(guī)劃可以大大減少網(wǎng)絡(luò)消耗、節(jié)約節(jié)點(diǎn)能量、提高信號(hào)的覆蓋率，減少閱讀器之間的數(shù)據(jù)沖突，同時(shí)還能改善網(wǎng)絡(luò)的安全性和可靠性。當(dāng)閱讀器網(wǎng)絡(luò)規(guī)劃首次被提出時(shí)，Daniel及Engels他們將閱讀器碰撞看成一種類似于簡(jiǎn)單圖著色的問題，隨后S.K.Padhi等提出了一種閱讀器防碰撞算法Colorwave，J.Ho和S.M.Birari分別提出Q－learning算法和Pulse算法來解決閱讀器碰撞問題［2－4］。當(dāng)前對(duì)閱讀器網(wǎng)絡(luò)規(guī)劃都整體對(duì)閱讀器建模，需要同時(shí)考慮很多方面，環(huán)境、標(biāo)簽分布、閱讀器分布、干擾等問題，這使得建模復(fù)雜且效果不理想［5－7］。例如田景賀、范玉順等針對(duì)密集閱讀器環(huán)境中的RFID閱讀器碰撞提出了一種閱讀器集中控制方法，主要根據(jù)圖著色理論，將密集閱讀器網(wǎng)絡(luò)的閱讀器防碰撞等效為閱讀器網(wǎng)絡(luò)的時(shí)隙分配問題。高彥芬，宋革聯(lián)對(duì)RFID系統(tǒng)在考慮閱讀器數(shù)量、時(shí)隙分配及總處理時(shí)間，建立系統(tǒng)規(guī)劃的目標(biāo)函數(shù)［8，9］。

針對(duì)上述的情況，本文結(jié)合粒子群優(yōu)化算法和圖著色理論提出了將閱讀器布局與閱讀器分配時(shí)隙分解為兩步進(jìn)行仿真，利用粒子群算法對(duì)閱讀器進(jìn)行布局，再利用圖著色最小著色對(duì)閱讀器進(jìn)行時(shí)隙分配，如此進(jìn)行規(guī)劃，使得整個(gè)閱讀器網(wǎng)絡(luò)規(guī)劃簡(jiǎn)單可行，提高閱讀器的讀取率，從而完成閱讀器的防碰撞處理。

1 閱讀器模型

閱讀器網(wǎng)絡(luò)覆蓋問題的研究依賴于每個(gè)閱讀器的覆蓋模型和放置位置，要對(duì)閱讀器進(jìn)行布局，首先需要選定閱讀器模型。

最常用的閱讀器模型是布爾模型，即0－1模型。若標(biāo)簽?zāi)鼙婚喿x器覆蓋到，則閱讀器的作用狀態(tài)為1，否則為0。當(dāng)閱讀器感知特性為全向時(shí)，布爾模型就簡(jiǎn)化成圓盤布爾模型。如圖1所示，以閱讀器為中心的圓盤，在感知半徑R下，只要標(biāo)簽處于圓盤內(nèi)即認(rèn)為標(biāo)簽被閱讀器覆蓋，圓盤之外的標(biāo)簽則在閱讀器覆蓋區(qū)域之外。模型表示閱讀器能夠覆蓋到圓盤內(nèi)標(biāo)簽發(fā)生的概率恒為1，覆蓋到圓盤外的概率恒為0，即假設(shè)閱讀器坐標(biāo)為r（xr，yr），任意標(biāo)簽坐標(biāo)為t（xt，yt），閱讀器能夠覆蓋標(biāo)簽的概率為

圖1 閱讀器布爾模型

2 粒子群算法

2.1 粒子群算法原理

粒子群優(yōu)化算法（particle swarm optimization，PSO）是一種多維優(yōu)化的群體智能算法，通過抽象、模擬自然界鳥群覓食過程時(shí)的遷徙和群聚行為而提出。這種全局隨機(jī)搜索算法簡(jiǎn)單且易于實(shí)現(xiàn)，求解質(zhì)量高，所以自從提出后迅速被應(yīng)用于各個(gè)領(lǐng)域。PSO中，搜索空間中的每一個(gè)粒子就是優(yōu)化問題的潛在解。

初始化時(shí)PSO隨機(jī)定義一群粒子，然后模擬鳥類群居的方式飛行。粒子群算法有兩個(gè)極值，一個(gè)稱為個(gè)體極值（pbest），是個(gè)體自身找到的當(dāng)前最優(yōu)解；另一個(gè)稱為全局極值（gbest），是整個(gè)種群找到的當(dāng)前最優(yōu)解。進(jìn)行每次迭代時(shí)，粒子通過跟蹤這兩個(gè)極值來不斷更新自己。同時(shí)每個(gè)粒子都有一個(gè)適應(yīng)度值（fitness value）以及決定其飛翔的方向和距離的速度，每次迭代之后，粒子根據(jù)其適應(yīng)度值改變自身的飛行速度，使得粒子能夠飛向pbest和gbest，從而追隨當(dāng)前的最優(yōu)粒子在解空間中進(jìn)行搜索［10，11］。

2.2 粒子群算法數(shù)學(xué)描述

粒子群算法的數(shù)學(xué)描述:每個(gè)粒子i包含一個(gè)m維的位置向量xi＝（xi1，xi2，……，xim）和速度向量vi＝（vi1，vi2，……，vim）。粒子i搜索解空間時(shí)，保存其搜索到的最優(yōu)經(jīng)歷位置pi＝（pi1，pi2，……，pim）。在每次迭代開始時(shí)，粒子根據(jù)自身慣性和經(jīng)驗(yàn)及群體最優(yōu)經(jīng)歷位置pg＝（pg1，pg2，……，pgm）來調(diào)整自己的速度向量以調(diào)整自身位置。Ω稱為慣性權(quán)重，其值用于反映下一刻對(duì)當(dāng)前速度的繼承程度，合理地設(shè)置慣性權(quán)重可以使粒子具有均衡的探索能力和開發(fā)能力；c1、c2是正的常數(shù)，稱之為加速因子；r1、r2為［0，1］上均勻分布的隨機(jī)數(shù)，d為維數(shù)。其中，粒子的位置和速度更新按下式

3 圖論以及圖著色

3.1 圖著色起源

圖著色問題起源于四色猜想，所謂四色猜想就是證明:給一個(gè)平面或者球面上的地圖著色，至多只要4種顏色就可以完成，并且能夠保證任意相鄰兩個(gè)國(guó)家是不同的顏色，使得各國(guó)家之間可以很明顯的辨認(rèn)。由地圖著色問題引申的圖著色理論在結(jié)合計(jì)算機(jī)的情況下已得以證明，如今已廣泛應(yīng)用于各種領(lǐng)域:排課表問題，考試安排問題，化學(xué)藥品貯藏問題，無線電頻譜分配等。

3.2 圖著色相關(guān)概念

要應(yīng)用圖著色理論對(duì)各種問題進(jìn)行解決，就需要知道圖著色的相關(guān)概念，定義如下:

（1）正常頂點(diǎn)著色:給圖的頂點(diǎn)進(jìn)行著色，滿足任意相鄰的頂點(diǎn)顏色不同的條件；

（2）k－頂點(diǎn)著色:用k種顏色對(duì)圖中所有頂點(diǎn)正常頂點(diǎn)著色；

（3）圖的最小著色數(shù):對(duì)圖進(jìn)行正常頂點(diǎn)著色所需顏色的最小數(shù)［12］。

3.3 圖的矩陣表示

一個(gè)給定圖G＝（V，E）既可以由它的頂點(diǎn)與頂點(diǎn)之間的鄰接關(guān)系唯一確定，也可以由它的頂點(diǎn)與邊之間的關(guān)聯(lián)關(guān)系唯一確定。所以下面就對(duì)鄰接矩陣、關(guān)聯(lián)矩陣定義。

鄰接矩陣的定義:設(shè)（無向）圖G＝（V，E），其中頂點(diǎn)集V＝｛v1，v2，……，vn｝，邊集E＝｛e1，e2，……，en｝。用aij表示頂點(diǎn)vi與頂點(diǎn)vj之間的邊數(shù)，可能取值為0，1，2，稱所得矩陣A＝A（G）＝（aij）n×n為圖G的鄰接矩陣。

關(guān)聯(lián)矩陣的定義:設(shè)（無向）圖G＝（V，E），其中頂點(diǎn)集V＝｛v1，v2，……，vn｝，邊集E＝｛e1，e2，……，en｝。用mij表示頂點(diǎn)vi與邊ej關(guān)聯(lián)的次數(shù)，可以取值0，1，2，稱所得矩陣M（G）＝（mij）n×l為圖G的關(guān)聯(lián)矩陣。

圖G＝（V，E）在計(jì)算機(jī)中存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)必須完全等價(jià)于圖本身的頂點(diǎn)與頂點(diǎn)或頂點(diǎn)與邊之間的結(jié)構(gòu)關(guān)系，而圖的表示矩陣就承擔(dān)了這種重要媒介角色。通過對(duì)圖的表示矩陣進(jìn)行討論就可以得到圖的若干性質(zhì)。作為圖的一個(gè)關(guān)鍵矩陣，鄰接矩陣有其自身的一些特定性質(zhì)。

根據(jù)鄰接矩陣的定義，易得到若干性質(zhì)如下:

（1）A（G）是對(duì)稱矩陣；

（2）若G為無環(huán)圖，則A（G）中第i行（列）的元素之和等于頂點(diǎn)vi的度；

（3）兩圖G和H同構(gòu)的充分必要條件是存在置換矩陣P使得A（G）＝PTA（G）P。

RFID閱讀器系統(tǒng)中各閱讀器的工作范圍可能會(huì)有重疊，這與地圖中各個(gè)部分可能相鄰相似；當(dāng)有重疊區(qū)的閱讀器同時(shí)工作時(shí)，如果不采取措施，就會(huì)產(chǎn)生閱讀器碰撞，甚至使整個(gè)RFID系統(tǒng)無法正常工作。而RFID系統(tǒng)能夠正常工作需要相互有重疊區(qū)的閱讀器工作于不同的時(shí)隙來避免碰撞，這與圖著色所希望的各相鄰國(guó)家著不同的顏色以便可以明顯辨認(rèn)的想法相似。綜上，閱讀器時(shí)隙分配與圖著色具有同樣的前提和期望有相同的結(jié)果，所以本文運(yùn)用圖著色理論進(jìn)行時(shí)隙分配進(jìn)行閱讀器碰撞處理。

在對(duì)閱讀器布局圖進(jìn)行時(shí)隙分配時(shí)將每個(gè)閱讀器視為一個(gè)頂點(diǎn)，閱讀器之間是否碰撞視為是否相鄰。即若閱讀器若R1、R2同時(shí)工作，則其重疊區(qū)域發(fā)生碰撞，可視為閱讀器1，2相鄰，此時(shí)其鄰接矩陣W中w12＝w21＝1。

4 算法設(shè)計(jì)

4.1 RFID閱讀器布局

其中:n為被閱讀器覆蓋的標(biāo)簽個(gè)數(shù)，N為設(shè)置的標(biāo)簽的個(gè)數(shù)設(shè)計(jì)的具體步驟:

（1）初始化種群。設(shè)定如下參數(shù):加速因子，迭代次數(shù)maxgen，種群規(guī)模sizepop，粒子位置（即閱讀器位置），標(biāo)簽位置tag，速度；

（2）粒子進(jìn)行適應(yīng)度值計(jì)算；

（3）尋找個(gè)體極值和群體極值；

（4）速度和位置更新，計(jì)算粒子適應(yīng)度值；

（5）個(gè)體極值和群體極值更新，若滿足終止條件，結(jié)束，否則轉(zhuǎn)到（4）。

4.2 閱讀器著色

具體設(shè)計(jì)步驟:

（1）根據(jù)所得閱讀器位置求得鄰接矩陣；

（2）求出閱讀器布局圖簡(jiǎn)化圖各頂點(diǎn)度數(shù)；

（3）從頂點(diǎn)度數(shù)最小的未著色頂點(diǎn)開始著色，找到與其不相鄰的頂點(diǎn)并選擇其中一個(gè)頂點(diǎn)進(jìn)行著色；

（4）找到與前兩個(gè)頂點(diǎn)都不相鄰的頂點(diǎn)集合，并對(duì)其中一個(gè)頂點(diǎn)著色，重復(fù)當(dāng)前步驟，直到找不到為止；

（5）所有頂點(diǎn)均已著色，則結(jié)束，否則轉(zhuǎn)到步驟（3）。

5 實(shí)驗(yàn)仿真

5.1 RFID閱讀器布局仿真結(jié)果

使用MATLAB對(duì)RFID閱讀器網(wǎng)絡(luò)進(jìn)行布局仿真。指定區(qū)域大小為18m×18m，在其中隨機(jī)地布置50個(gè)電子標(biāo)簽，使用9個(gè)可以移動(dòng)的閱讀器對(duì)RFID網(wǎng)絡(luò)中的標(biāo)簽進(jìn)行數(shù)據(jù)采集。工作頻率在433MHz的RFID系統(tǒng)，通信距離長(zhǎng)，信號(hào)繞射能力強(qiáng)，故本文的閱讀器工作頻率選用433MHz，假定閱讀器的感知范圍為一個(gè)半徑為3m的圓（實(shí)際應(yīng)用中感知范圍可能為不規(guī)則形狀）。

表1 參數(shù)初始化

利用粒子群算法對(duì)閱讀器進(jìn)行布局時(shí)粒子的維數(shù)即等于閱讀器的個(gè)數(shù)，仿真結(jié)果如圖2、圖3所示，其中圖2為粒子群算法求得的標(biāo)簽被閱讀器覆蓋的覆蓋率，圖3為閱讀器對(duì)標(biāo)簽進(jìn)行覆蓋的示意圖。

圖2 PSO優(yōu)化閱讀器對(duì)標(biāo)簽的覆蓋率

5.2 圖著色對(duì)閱讀器分配時(shí)隙

圖論中鄰接矩陣W＝（wij）n×n中各元素的標(biāo)示方法如下

其中閱讀器編號(hào)i和j滿足1≤i，j≤n的條件，則可以得到圖3所示閱讀器分布圖的鄰接矩陣W

圖3 PSO優(yōu)化閱讀器及標(biāo)簽位置

根據(jù)圖著色算法得到

將矩陣W作為程序的輸入矩陣，即為給定的圖的鄰接矩陣，通過仿真可以得到各閱讀器著色狀態(tài)，color為最終給閱讀器著色所需的最少顏色，C為閱讀器的著色方案。

由PSO所得的閱讀器布局圖和圖著色所得的著色方案，可以給出RFID網(wǎng)絡(luò)優(yōu)化的整個(gè)閱讀器防碰撞方案，如圖4所示。

圖4 RFID閱讀器網(wǎng)絡(luò)規(guī)劃

6 結(jié)束語(yǔ)

通過直接對(duì)閱讀器網(wǎng)絡(luò)進(jìn)行整體建模，實(shí)現(xiàn)布局、防碰撞處理，仍然會(huì)存在閱讀盲區(qū)，從而無法達(dá)到避碰效果，影響整個(gè)系統(tǒng)工作。簡(jiǎn)化閱讀器防碰撞的過程，對(duì)其進(jìn)行兩步處理，首先利用粒子群算法對(duì)閱讀器的位置進(jìn)行布局，再利用圖著色算法對(duì)每個(gè)閱讀器著色，使其與其周圍的顏色都不同，可以達(dá)到時(shí)隙分配的效果，仿真結(jié)果表明，通過上述的網(wǎng)絡(luò)規(guī)劃可以減少閱讀器的碰撞。采用分步時(shí)隙分配可以降低處理復(fù)雜度，并且能夠使得網(wǎng)絡(luò)規(guī)劃簡(jiǎn)單可行。

［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）.［韓下林，趙衛(wèi)東，季軍，等.基于RFID技術(shù)的室內(nèi)定位算法及其改進(jìn)［J］.計(jì)算機(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）.［徐雪慧，李玲遠(yuǎn)，王正強(qiáng)，等.用自適應(yīng)圖著色算法解決RFID閱讀器沖突問題［J］.現(xiàn)代電子技術(shù)，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）.［陳瀚寧，朱云龍，胡琨元.基于多種群共生進(jìn)化的RFID網(wǎng)絡(luò)優(yōu)化［J］.解放軍理工大學(xué)學(xué)報(bào)（自然科學(xué)版），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）.［劉快，沈艷霞，紀(jì)志成.基于改進(jìn)粒子群算法的RFID網(wǎng)絡(luò)系統(tǒng)的優(yōu)化［J］.中南大學(xué)學(xué)報(bào)（自然科學(xué)版），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）.［劉快，紀(jì)志成.基于混合粒子群的RFID網(wǎng)絡(luò)的優(yōu)化部署［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（4）:1326－1328.］

［8］TIAN Jinghe，F(xiàn)AN 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īng)網(wǎng)絡(luò)建模與求解［J］.高技術(shù)通訊，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）.［高彥芬，宋革聯(lián).基于GCPSO算法的RFID讀寫器網(wǎng)絡(luò)規(guī)劃的研究［J］.工業(yè)控制計(jì)算機(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）.［秦全德，李麗，程適，等.交互學(xué)習(xí)的粒子群優(yōu)化算法［J］.智能系統(tǒng)學(xué)報(bào)，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）.［高政威，龐哈利，汪定偉，等.基于共生粒子群優(yōu)化的RFID網(wǎng)絡(luò)調(diào)度［J］.信息與控制，2012，41（5）:564－577.］

［12］WEN Shiguang.Coloring research and application［D］.Shenyang:Northeastern University，2009（in Chinese）.［聞時(shí)光.圖著色的研究與應(yīng)用［D］.沈陽(yáng):東北大學(xué)，2009.］