劉 鷹，趙小晴，張開偉

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

0 引 言

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

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

1 閱讀器模型

閱讀器網絡覆蓋問題的研究依賴于每個閱讀器的覆蓋模型和放置位置，要對閱讀器進行布局，首先需要選定閱讀器模型。

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

圖1 閱讀器布爾模型

2 粒子群算法

2.1 粒子群算法原理

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

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

2.2 粒子群算法數學描述

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

3 圖論以及圖著色

3.1 圖著色起源

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

3.2 圖著色相關概念

要應用圖著色理論對各種問題進行解決，就需要知道圖著色的相關概念，定義如下:

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

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

（3）圖的最小著色數:對圖進行正常頂點著色所需顏色的最小數［12］。

3.3 圖的矩陣表示

一個給定圖G＝（V，E）既可以由它的頂點與頂點之間的鄰接關系唯一確定，也可以由它的頂點與邊之間的關聯關系唯一確定。所以下面就對鄰接矩陣、關聯矩陣定義。

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

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

圖G＝（V，E）在計算機中存儲的數據結構必須完全等價于圖本身的頂點與頂點或頂點與邊之間的結構關系，而圖的表示矩陣就承擔了這種重要媒介角色。通過對圖的表示矩陣進行討論就可以得到圖的若干性質。作為圖的一個關鍵矩陣，鄰接矩陣有其自身的一些特定性質。

根據鄰接矩陣的定義，易得到若干性質如下:

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

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

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

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

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

4 算法設計

4.1 RFID閱讀器布局

其中:n為被閱讀器覆蓋的標簽個數，N為設置的標簽的個數設計的具體步驟:

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

（2）粒子進行適應度值計算；

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

（4）速度和位置更新，計算粒子適應度值；

（5）個體極值和群體極值更新，若滿足終止條件，結束，否則轉到（4）。

4.2 閱讀器著色

具體設計步驟:

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

（2）求出閱讀器布局圖簡化圖各頂點度數；

（3）從頂點度數最小的未著色頂點開始著色，找到與其不相鄰的頂點并選擇其中一個頂點進行著色；

（4）找到與前兩個頂點都不相鄰的頂點集合，并對其中一個頂點著色，重復當前步驟，直到找不到為止；

（5）所有頂點均已著色，則結束，否則轉到步驟（3）。

5 實驗仿真

5.1 RFID閱讀器布局仿真結果

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

表1 參數初始化

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

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

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

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

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

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

根據圖著色算法得到

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

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

圖4 RFID閱讀器網絡規(guī)劃

6 結束語

通過直接對閱讀器網絡進行整體建模，實現布局、防碰撞處理，仍然會存在閱讀盲區(qū)，從而無法達到避碰效果，影響整個系統工作。簡化閱讀器防碰撞的過程，對其進行兩步處理，首先利用粒子群算法對閱讀器的位置進行布局，再利用圖著色算法對每個閱讀器著色，使其與其周圍的顏色都不同，可以達到時隙分配的效果，仿真結果表明，通過上述的網絡規(guī)劃可以減少閱讀器的碰撞。采用分步時隙分配可以降低處理復雜度，并且能夠使得網絡規(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技術的室內定位算法及其改進［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）.［徐雪慧，李玲遠，王正強，等.用自適應圖著色算法解決RFID閱讀器沖突問題［J］.現代電子技術，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）.［陳瀚寧，朱云龍，胡琨元.基于多種群共生進化的RFID網絡優(yōu)化［J］.解放軍理工大學學報（自然科學版），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）.［劉快，沈艷霞，紀志成.基于改進粒子群算法的RFID網絡系統的優(yōu)化［J］.中南大學學報（自然科學版），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）.［劉快，紀志成.基于混合粒子群的RFID網絡的優(yōu)化部署［J］.計算機應用研究，2012，29（4）:1326－1328.］

［8］TIAN Jinghe，FAN 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］.高技術通訊，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）.［高彥芬，宋革聯.基于GCPSO算法的RFID讀寫器網絡規(guī)劃的研究［J］.工業(yè)控制計算機，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）.［秦全德，李麗，程適，等.交互學習的粒子群優(yōu)化算法［J］.智能系統學報，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網絡調度［J］.信息與控制，2012，41（5）:564－577.］

［12］WEN Shiguang.Coloring research and application［D］.Shenyang:Northeastern University，2009（in Chinese）.［聞時光.圖著色的研究與應用［D］.沈陽:東北大學，2009.］