0 引言  

　　無線射頻識別(radio frequency identification，RFID)系統(tǒng)中讀寫器和標簽通信具有空間受限的特性。在某些RFID系統(tǒng)應用中，需要RFID讀寫器能在一個大的范圍內(nèi)的任何地方都能閱讀標簽，因此必須在整個范圍內(nèi)配置很多讀寫器。RFID系統(tǒng)的不斷增多增加了讀寫器沖突的概率。隨著RFID應用的不斷增長，人們逐漸對RFID讀寫器沖突的問題重視起來，并做了一些研究。Daniel及Engels等最早提出了RFID讀寫器沖突問題，他們指出，讀寫器沖突是一種類似于簡單圖著色的問題。隨后WMdmp和Engels等提出了一種讀寫器防沖突算法Colorwave 。Colorwave是一種基于時分多址(TD．MA)原理的分布式防沖突算法，當網(wǎng)絡中的讀寫器數(shù)量比較小時該方法是有效的和可行的。歐洲電信 標準協(xié)會(ETSI)發(fā)布的EN 302 208標準采用一種 基于載波偵聽多路訪問(carrier sense multi．a(chǎn)ccess，CSMA)原理的先偵聽后發(fā)言的方法(1isten before talk，LBT )來減少讀寫器沖突的情況。該方法盡管實現(xiàn)簡單，但是可能導致某些讀寫器長時間無法獲得信道。EPC Class I Gen2標準闡述了采用頻分多址(FDMA)原理來避免讀寫器沖突的算法。但是由于大部分的標簽不具備頻率分辨能力，因此在該標準中仍然存在讀寫器沖突的情況?；ヂ?lián)RFID讀寫器沖突模型(interconnected RFID reader collision model，IRCM)是一種基于P2P結構的無需中央服務器參與的讀寫器信息交互模型。讀寫器之間通過協(xié)商和調(diào)整讀取速度、讀取時間等參數(shù)來減少沖突發(fā)生的概率。盡管不需要中央服務器，但是IRCM使得讀寫器經(jīng)常陷于互相交互與協(xié)商的過程，顯然會大大減少讀寫器的標簽掃描時間和工作效率。 
  
　　針對上述情況，本文提出了通過中央服務器集中控制讀寫器分時隙操作來實現(xiàn)避免讀寫器沖突的方法，并建立了一種基于模擬退火策略的混沌神經(jīng)網(wǎng)絡進行讀寫器時隙分配問題求解的模型。這是一種基于TDMA原理的集中控制式防沖突方法，可以根據(jù)讀寫器沖突關系的變化在線進行讀寫器的時隙分配求解與控制，在不影響讀寫器工作效率的同時，旨在消除密集讀寫器環(huán)境下的讀寫器沖突問題。 
  
1 RFID讀寫器沖突及解決途徑  

1．1 密集讀寫器環(huán)境中的讀寫器沖突  

　　密集讀寫器環(huán)境就是指在RFID系統(tǒng)應用中，在預定區(qū)域內(nèi)部署多個RFID讀寫器，以滿足對區(qū)域內(nèi)的所有標簽進行完全的高可靠的讀取。讀寫器網(wǎng)絡的拓撲結構通常如圖1所示。網(wǎng)絡中包含多個讀寫器和一個中央計算機，讀寫器與中央計算機之間一般采用局域網(wǎng)(LAN)或無線局域網(wǎng)(WLAN)方式進行通訊連接。網(wǎng)絡中每個讀寫器通常具有不同范圍的識讀區(qū)域，各讀寫器的識讀區(qū)域可能有交集，即識讀區(qū)域有相互重疊的部分。為了便于說明，用圖2近似地描繪了密集讀寫器環(huán)境下的讀寫器沖突。每個圓圈代表一個讀寫器的識讀區(qū)域(實際應用中識讀區(qū)域可能為不規(guī)則形狀)，圓點代表相應的讀寫器。如果兩個讀寫器的識讀區(qū)域有相互重疊，如圖2中的R1和R2，則當R1、R2同時工作時，如果不采取防沖突措施，就會產(chǎn)生讀寫器沖突，甚至使整個RFID系統(tǒng)無法正常工作。 

1．2 分時傳輸解決讀寫器沖突  

　　標簽通過電磁耦合的方式從讀寫器獲得能量，由于獲得的能量非常有限，無源標簽只具備簡單的功能而不具備區(qū)分不同頻率信號的能力，所以RFID讀寫器的防沖突無法通過FDMA來實現(xiàn)，而只能靠TDMA的方法解決。因此可以將讀寫器的防沖突看成讀寫器時隙分配問題。  

　　時隙分配可能的實現(xiàn)方法可分為分布式時隙控制與集中式時隙控制兩種。第一種方法以防沖突算  
法Colorwave和IRCM為代表，時隙分配過程以網(wǎng)絡中的每個讀寫器為中心，各讀寫器之間相互反復通訊協(xié)商來確定各自的工作時隙，發(fā)生沖突時往往通過增加新的時隙來解決，結果是時隙分配過程較長且需要的總時隙數(shù)目多；集中式時隙控制方法幾乎不占用讀寫器的資源，通過中央計算機或服務器運行優(yōu)化算法進行時隙分配問題的求解。這種方法求解速度快且不占用讀寫器資源。  

　　因此，本文采用集中式時隙控制的方法，根據(jù)讀寫器之間的沖突關系，由中央計算機執(zhí)行時隙分配的優(yōu)化算法。在得到時隙分配結果解后，中央計算機指定各個讀寫器在分配到的時隙內(nèi)進行讀寫操作，從而消除讀寫器沖突情況。  

1．3 平面圖著色與讀寫器防沖突  

　　文獻[1,2]指出，RFID讀寫器沖突問題類似于一個簡單的平面圖G= (R，E)。頂點集合R是  RFID讀寫器集合，即R={r1，r2，﹍，r )。邊集合E 描述了RFID系統(tǒng)中讀寫器之間的沖突關系。也就 是說，如果讀寫器Ri 和讀寫器Rj 的識讀區(qū)域之間存在交集，我們就將頂點ri和rj用一個無向線段連接起來。據(jù)此建立圖2中的讀寫器沖突問題的平面圖G＝(R，E)(見圖3)。

　　文獻[8]已經(jīng)證明了任意一個平面圖均可用4種顏色來進行著色。因此，一個讀寫器網(wǎng)絡的防沖突問題即類似于一個平面圖的四色著色問題。因此，讀寫器防沖突問題可以看作讀寫器網(wǎng)絡的四時隙分配問題。在本文中，采用基于退火策略的混沌神經(jīng)網(wǎng)絡模型來進行讀寫器四時隙分配問題的求解。 

2 讀寫器防沖突問題的混沌神經(jīng)網(wǎng)絡模型 

　　采用神經(jīng)網(wǎng)絡方法求解讀寫器網(wǎng)絡防沖突問題前需要確定網(wǎng)絡中讀寫器之間可能存在沖突的關系，即獲得平面圖G=(R，E)的邊集E。本文采用文獻[7]中的算法IRCD來獲得讀寫器的沖突關系矩陣，關于IRCD這里不再詳述。 

2．1 Hopfieid神經(jīng)網(wǎng)絡模型 

　　本文采用二維Hopfield神經(jīng)網(wǎng)絡(HNN)模型對讀寫器防沖突問題進行建模。 

　　首先，為了獲得讀寫器防沖突神經(jīng)網(wǎng)絡的能量函數(shù)，需要建立一個二維Hopfield神經(jīng)網(wǎng)絡，構造一個n×4階的矩陣 。其中，n為網(wǎng)絡中的讀寫器的 數(shù)目，矩陣的每一行包括4個神經(jīng)元，代表一種時隙，4個時隙 ， ， ， 分別表示為‘1000’，‘0100’，‘0010’，‘0001’。那么n個讀寫器的四時隙分配結果就可以由n×4個神經(jīng)元表示出來。對于圖3所示的讀寫器網(wǎng)絡，矩陣

是一種可行的四時隙分配結果。 

　　設n×n階對稱矩陣d為讀寫器沖突關系矩陣，它描述網(wǎng)絡中讀寫器之間是否存在的沖突，當讀寫器i和讀寫器． 之間具有沖突關系時，dij= 1，否則dij =0。對于圖3所示的讀寫器網(wǎng)絡，可以構造讀寫器沖突關系矩陣如下：

　　為了消除網(wǎng)絡中的讀寫器沖突問題，必須使網(wǎng)絡中存在沖突關系的讀寫器工作在不同的時隙。根據(jù)這樣的約束要求，建立如下的讀寫器防沖突神經(jīng)網(wǎng)絡的能量函數(shù)：

　　其中，A， B，C是常數(shù)，n×n階對稱矩陣d為讀寫器沖突關系矩陣，矩陣v是神經(jīng)網(wǎng)絡的輸出矩陣。在式(3)的能量函數(shù)中，第一項是行約束，在矩陣v的每一行的4個神經(jīng)元當中，只有一個神經(jīng)元的值為‘1’，其余3個神經(jīng)元的值全部為0。也就是說，當每個讀寫器都分配了T1,T2,T3,T4,4個時隙中的任意一個的時候，該項的值為 
0。第二項是一個全局約束，它有助于神經(jīng)網(wǎng)絡收斂于有效解。即當神經(jīng)網(wǎng)絡收斂于有效解時，輸出矩陣v中每行只有一個神經(jīng)元的值為1，對n×4神經(jīng)元矩陣v來說，所有值為‘1’的神經(jīng)元的個數(shù)是n，這時式(3)中的第二項的值為0。最后一項為邊界懲罰函數(shù)，只有當任意兩個存在沖突關系的讀寫器被分配了不同的工作時隙的情況下，該項的值為0。因此，當神經(jīng)網(wǎng)絡的能量函數(shù)E的值等于‘0’時，當前的輸出矩陣v的值就是讀寫器防沖突神經(jīng)網(wǎng)絡的可行解。

　　根據(jù)文獻[9]中的二維Hopfield神經(jīng)網(wǎng)絡能量函數(shù)的一般表達形式：

　　其中，Vxi,yj 表示神經(jīng)元Vxi 和Vyj 訂之間的連接權重，厶 表示神經(jīng)元％ 的外部輸入偏差。比較式(3)和式(4)，可以得到：

　　因此，讀寫器防沖突神經(jīng)網(wǎng)絡的微分方程為：

　　其中f為神經(jīng)元的輸入輸出函數(shù)，u為神經(jīng)元的內(nèi)部輸入，t為時間常數(shù)。解這個微分方程組就可以得到讀寫器防沖突神經(jīng)網(wǎng)絡的有效解。根據(jù)輸出矩陣 的每行各個元素的值就可以確定分配給每個讀寫器的時隙。 

2．2 基于退火策略的混沌神經(jīng)網(wǎng)絡模型 

　　Hopfield神經(jīng)網(wǎng)絡模型可以收斂到一個穩(wěn)定的平衡解，但會經(jīng)常陷入局部最優(yōu) 。因此，在2．1節(jié)所建立的Hopfield神經(jīng)網(wǎng)絡模型基礎上，本文通過引入混沌機制和模擬退火策略，為讀寫器防沖突建立基于退火策略的混沌神經(jīng)網(wǎng)絡模型如下：

　　其中Vxi，Uxi和Ixi 分別為神經(jīng)元的輸出、輸入和外部輸入偏差Vxi，yj 為神經(jīng)元連接權重系統(tǒng)，Io是一個正的常數(shù)，a為比例系數(shù)，k是神經(jīng)元的退火速度系數(shù)，z(t)自反饋權重系數(shù)， 是z(t)的衰減系數(shù)。式(12)中的z(t)(％ 一Io)項起自抑制反饋作用，從而為系統(tǒng)帶來混沌狀態(tài)。而混沌具有隨機搜索的特質(zhì)，因此可以避免算法陷入局部最優(yōu)。同時為了有效地控制混沌行為，引入模擬溫度z(t)，z(t) 在算法搜索過程中按照式(13)逐漸衰減，這樣使神經(jīng)網(wǎng)絡經(jīng)過一個倒分岔過程而逐漸趨于穩(wěn)定的平衡點。當模擬溫度衰減至趨近于‘0’時，混沌狀態(tài)消失，此后算法獲得一個較好的初值，并按照Hopfield神經(jīng)網(wǎng)絡算法繼續(xù)進行搜索并逐漸收斂于有效解。

3 仿真實驗 
3．1 仿真流程 
　　采用MATLAB對基于退火策略的混沌神經(jīng)網(wǎng)絡讀寫器時隙分配算法進行仿真。仿真流程如下：
 
　　步驟1：設置A，B，C，，0，￡，k，a，z(0)， ，／Z (0) 等參數(shù)的值，如表1。實驗中， (0)取[0，1]區(qū)間 
的隨機數(shù)。 
　　步驟2：根據(jù)式(10)和(11)計算 (t)。 
　　步驟3：根據(jù)式(3)計算能量函數(shù) 。 
　　步驟4：根據(jù)式(12)計算／Z (t+1)。 
　　步驟5：判斷能量函數(shù) 是否滿足穩(wěn)定條件。如果滿足進行步驟6，否則進行步驟2。能量函數(shù)的穩(wěn)定判據(jù)為：1) 的值在連續(xù)l0次迭代中的變化量小于0．01；2)如果E≤10～，則停止迭代；3)如果算法在1000次迭代中無法收斂到有效解，則停止仿真。 
　　步驟6：輸出仿真結果，即輸出V and E。

3．2 仿真實驗結果 

　　對于圖2和圖3所示的讀寫器沖突網(wǎng)絡，用基于退火策略的混沌神經(jīng)網(wǎng)絡算法在經(jīng)過162次迭代后，得到了讀寫器防沖突的時隙分配有效解。輸出矩陣 的值為：

　　圖4表示當參數(shù)盧=0．02時神經(jīng)元 的演變過程。從圖4中可以看出， 1逐漸地完成由混沌過程到穩(wěn)定輸出的轉變過程，當混沌狀態(tài)消失后，基于退火策略的混沌神經(jīng)網(wǎng)絡的動態(tài)響應就退化為普通的Hopfield神經(jīng)網(wǎng)絡。

　　根據(jù) 中的每行元素，得到各讀寫器的時隙分配結果如表2所示。

　　若以4種形狀分別代表時隙 T1, T2, T3, T4,對圖2所示的讀寫器網(wǎng)絡按照表2的結果進行著色填充的結果如圖5所示。

　　從圖5中可以看出，任意兩個識讀區(qū)域存在交集的讀寫器(即存在沖突約束的讀寫器)的識讀區(qū)域分別采用不同的填充方式，表明了求解結果的正確性。 盡管與式(1)的 的值不同，但仍然是讀寫器防沖突時隙分配問題的可行解。 

　　為了驗證算法可靠性和效率，對不同的讀寫器網(wǎng)絡規(guī)模(讀寫器數(shù)目)n=10，15，20，25，30進行了50次實驗，所有的50次實驗均得到了讀寫器防沖突問題的有效解。對于不同網(wǎng)絡規(guī)模，算法求解的平均迭代次數(shù)分別為171次、236次、282次、314次及375次。實驗結果表明了算法的可靠及高效。 

3．3 算法性能分析 

　　首先，基于退火策略的混沌神經(jīng)網(wǎng)絡讀寫器防沖突算法是基于TDMA原理的，因此運用該算法來解決讀寫器沖突問題原理上是可行的。 

　　其次，本算法屬于集中式控制算法，算法的執(zhí)行過程在中央計算機上實現(xiàn)，幾乎不占用讀寫器的掃描時間(只在確定讀寫器之間沖突關系時占用極少的時間)。而分布式算法在執(zhí)行的全過程中，所有的讀寫器要相互通訊來協(xié)調(diào)時隙分配，在時隙分配完成前無法掃描標簽。因此，從應用的角度來說，本文提出的方法更具有合理性和實用性。

　　最后，在密集讀寫器環(huán)境中，Colorwave和IRCM算法大概需要10個時隙數(shù)量才能得到96％ 以上的傳輸成功率，而本文提出的新算法僅需4個時隙即可完成幾乎100％的傳輸成功率(除去算法執(zhí)行時間都可以成功傳輸)，顯然本文提出的新算法使得每個讀寫器具有更大的標簽吞吐能力。

4 結論

　　本文提出了一種讀寫器沖突問題的集中控制方法。該方法根據(jù)平面圖著色理論，將密集讀寫器網(wǎng)絡的讀寫器防沖突問題等效為讀寫器網(wǎng)絡的四時隙分配問題，并建立了解決讀寫器沖突問題的神經(jīng)網(wǎng)絡模型，并引入了模擬退火策略及混沌思想對讀寫器防沖突神經(jīng)網(wǎng)絡模型進行求解，仿真實驗結果表明該算法是可靠的、高效的。與現(xiàn)有的Colorwave和IRCM等分布式算法相比較，本文提出的方法可以保證RFID網(wǎng)絡中的讀寫器具有更大的對標簽的吞吐能力和實時響應能力。 

　　本文提出的RFID讀寫器防沖突方法是通過讀寫器分時隙操作實現(xiàn)的。因此，讀寫器網(wǎng)絡的時間同步問題將是下一步研究工作的重點。此外，結合具體應用的業(yè)務流程特點，如何合理地確定時隙長度也是下一步研究的內(nèi)容。

　　點擊下載完整版本PDF文檔：RFID讀寫器防沖突問題的混沌神經(jīng)網(wǎng)絡建模與求解.rar