劉 鷹，趙小晴，張開偉

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

0 引 言

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

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

1 閱讀器模型

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

最常用的閱讀器模型是布爾模型，即0－1模型。若標(biāo)簽?zāi)鼙婚喿x器覆蓋到，則閱讀器的作用狀態(tài)為1，否則為0。當(dāng)閱讀器感知特性為全向時，布爾模型就簡化成圓盤布爾模型。如圖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)化的群體智能算法，通過抽象、模擬自然界鳥群覓食過程時的遷徙和群聚行為而提出。這種全局隨機(jī)搜索算法簡單且易于實(shí)現(xiàn)，求解質(zhì)量高，所以自從提出后迅速被應(yīng)用于各個領(lǐng)域。PSO中，搜索空間中的每一個粒子就是優(yōu)化問題的潛在解。

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

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

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

3 圖論以及圖著色

3.1 圖著色起源

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

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

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

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

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

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

3.3 圖的矩陣表示

一個給定圖G＝（V，E）既可以由它的頂點(diǎn)與頂點(diǎn)之間的鄰接關(guān)系唯一確定，也可以由它的頂點(diǎn)與邊之間的關(guān)聯(lián)關(guān)系唯一確定。所以下面就對鄰接矩陣、關(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ī)中存儲的數(shù)據(jù)結(jié)構(gòu)必須完全等價于圖本身的頂點(diǎn)與頂點(diǎn)或頂點(diǎn)與邊之間的結(jié)構(gòu)關(guān)系，而圖的表示矩陣就承擔(dān)了這種重要媒介角色。通過對圖的表示矩陣進(jìn)行討論就可以得到圖的若干性質(zhì)。作為圖的一個關(guān)鍵矩陣，鄰接矩陣有其自身的一些特定性質(zhì)。

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

（1）A（G）是對稱矩陣；

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

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

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

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

4 算法設(shè)計

4.1 RFID閱讀器布局

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

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

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

（3）尋找個體極值和群體極值；

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

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

4.2 閱讀器著色

具體設(shè)計步驟:

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

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

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

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

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

5 實(shí)驗仿真

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

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

表1 參數(shù)初始化

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

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

5.2 圖著色對閱讀器分配時隙

圖論中鄰接矩陣W＝（wij）n×n中各元素的標(biā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)化的整個閱讀器防碰撞方案，如圖4所示。

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

6 結(jié)束語

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

［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ī)工程，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é)報（自然科學(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é)報（自然科學(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ī)應(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ī)，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é)報，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）.［聞時光.圖著色的研究與應(yīng)用［D］.沈陽:東北大學(xué)，2009.］