RFID讀寫(xiě)器的防碰撞技術(shù)
       RFID系統(tǒng)中的讀寫(xiě)器和標(biāo)簽通信具有空間受限的特性。在某些RFID系統(tǒng)的應(yīng)用中，需要RFID讀寫(xiě)器能在一個(gè)大的范圍內(nèi)的任何地方都能閱讀RFID標(biāo)簽，因此必須在整個(gè)范圍內(nèi)配置很多閱讀器。RFID系統(tǒng)的不斷增多增加了閱讀器沖突的概率。隨著RFID應(yīng)用的不斷增長(zhǎng)，人們逐漸重視RFID讀寫(xiě)器沖突的問(wèn)題，并進(jìn)行了一些研究。Daniel及Engels等最早提出了RFID閱讀器沖突問(wèn)題，他們指出閱讀器沖突是一種類(lèi)似于簡(jiǎn)單圖著色的問(wèn)題。隨后WMdmp和Engels等提出了一種閱讀器防沖突算法Colorwave。Colorwave是一種基于時(shí)分多址（TDMA）原理的分布式防沖突算法，當(dāng)網(wǎng)絡(luò)中的閱讀器數(shù)量比較小時(shí)該方法是有效的和可行的。歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)（ETSI）發(fā)布的EN 302 208標(biāo)準(zhǔn)采用一種基于載波偵聽(tīng)多路訪問(wèn)（Carrier Sense Multi.Access，CSMA）原理的先偵聽(tīng)后發(fā)言的方法（Listen Before Talk，LBT）來(lái)減少閱讀器沖突的情況。盡管該方法的實(shí)現(xiàn)簡(jiǎn)單，但是可能導(dǎo)致某些閱讀器長(zhǎng)時(shí)間無(wú)法獲得信道。EPC Class1 Gen2標(biāo)準(zhǔn)闡述了采用頻分多址（FDMA）原理來(lái)避免讀寫(xiě)器沖突的算法。但是由于大部分的標(biāo)簽不具備頻率分辨能力，所以在該標(biāo)準(zhǔn)中仍然存在閱讀器沖突的情況?；ヂ?lián)RFID閱讀器沖突模型（Interconnected RFID Reader Collision Model，IRCM）是一種基于P2P結(jié)構(gòu)的無(wú)須中央服務(wù)器參與的閱讀器信息交互模型。閱讀器之間通過(guò)協(xié)商和調(diào)整讀取速度、讀取時(shí)間等參數(shù)來(lái)減少?zèng)_突發(fā)生的概率。盡管不需要中央服務(wù)器，但是IRCM使得閱讀器經(jīng)常陷于互相交互與協(xié)商的過(guò)程，這顯然會(huì)大大減少閱讀器的標(biāo)簽掃描時(shí)間和工作效率。
      針對(duì)上述情況，本節(jié)提出了通過(guò)中央服務(wù)器集中控制閱讀器分時(shí)隙操作來(lái)實(shí)現(xiàn)避免閱讀器沖突的方法，并建立了一種基于模擬退火策略的混沌神經(jīng)網(wǎng)絡(luò)進(jìn)行閱讀器時(shí)隙分配問(wèn)題求解的模型。這是一種基于TDMA原理的集中控制式防沖突方法，可以根據(jù)閱讀器沖突關(guān)系的變化在線進(jìn)行閱讀器的時(shí)隙分配求解與控制，而且在不影響閱讀器工作效率的同時(shí)，可以消除密集閱讀器環(huán)境下的閱讀器沖突問(wèn)題。

1.RFID閱讀器沖突及解決途徑
1）密集閱讀器環(huán)境中的閱讀器沖突
     密集閱讀器環(huán)境就是指在RFID系統(tǒng)應(yīng)用中，在預(yù)定區(qū)域內(nèi)部署多個(gè)RFID閱讀器，以滿足對(duì)區(qū)域內(nèi)的所有標(biāo)簽進(jìn)行完全的、高可靠的讀取要求。系統(tǒng)網(wǎng)絡(luò)中包含多個(gè)閱讀器和一個(gè)中央計(jì)算機(jī)，閱讀器與中央計(jì)算機(jī)之間一般采用局域網(wǎng)（LAN）或無(wú)線局域網(wǎng)（WLAN）方式進(jìn)行通信連接。網(wǎng)絡(luò)中的每個(gè)閱讀器通常具有不同范圍的識(shí)讀區(qū)域，各閱讀器的識(shí)讀區(qū)域可能有交集，即識(shí)讀區(qū)域有相互重疊的部分。為了便于說(shuō)明，描繪了集閱讀器環(huán)境下的閱讀器沖突。每個(gè)圓圈代表一個(gè)閱讀器的識(shí)讀區(qū)域（實(shí)際應(yīng)用中的識(shí)讀區(qū)域可能為不規(guī)則形狀），圓點(diǎn)代表相應(yīng)的閱讀器。如果兩個(gè)閱讀器的識(shí)讀區(qū)域有相互重疊,R1和R2，則當(dāng)R1、R2同時(shí)工作時(shí)，如果不采取防沖突措施，就會(huì)產(chǎn)生閱讀器沖突，甚至使整個(gè)RFID系統(tǒng)無(wú)法正常工作。
2）分時(shí)傳輸解決閱讀器沖突
      標(biāo)簽是通過(guò)電磁耦合的方式從閱讀器獲得能量的，由于獲得的能量非常有限，所以無(wú)源標(biāo)簽只具備簡(jiǎn)單的功能而不具備區(qū)分不同頻率信號(hào)的能力。因此，RFID 閱讀器的防沖突無(wú)法通過(guò) FDMA 來(lái)實(shí)現(xiàn)，而只能靠 TDMA 方法解決?？梢詫㈤喿x器的防沖突看成閱讀器時(shí)隙分配問(wèn)題。時(shí)隙分配可能的實(shí)現(xiàn)方法可分為分布式時(shí)隙控制與集中式時(shí)隙控制兩種。分布式時(shí)隙控制方法以防沖突算法Colorwave 和 IRCM 為代表，時(shí)隙分配過(guò)程以網(wǎng)絡(luò)中的每個(gè)閱讀器為中心，各閱讀器之間相互反復(fù)通信協(xié)商來(lái)確定各自的工作時(shí)隙，發(fā)生沖突時(shí)往往通過(guò)增加新的時(shí)隙來(lái)解決，結(jié)果使得時(shí)隙分配過(guò)程較長(zhǎng)且需要的總時(shí)隙數(shù)目多；集中式時(shí)隙控制方法幾乎不占用閱讀器的資源，通過(guò)中央計(jì)算機(jī)或服務(wù)器運(yùn)行優(yōu)化算法進(jìn)行時(shí)隙分配問(wèn)題的求解，這種方法求解速度快且不占用閱讀器資源。
     因此，這里采用集中式時(shí)隙控制，即根據(jù)閱讀器之間的沖突關(guān)系，由中央計(jì)算機(jī)執(zhí)行時(shí)隙分配的優(yōu)化算法。在得到時(shí)隙分配結(jié)果后，中央計(jì)算機(jī)指定各個(gè)閱讀器在分配到的時(shí)隙內(nèi)進(jìn)行讀寫(xiě)操作，從而消除閱讀器沖突情況。2.平面圖著色與閱讀器防沖突
RFID閱讀器沖突問(wèn)題類(lèi)似于一個(gè)簡(jiǎn)單的平面圖G=（R，E）。頂點(diǎn)集合R是RFID閱讀器集合，即R={r1，r2，…，rn）。邊集合E描述了RFID系統(tǒng)中閱讀器之間的沖突關(guān)系。也就是說(shuō)，
如果閱讀器Ri和閱讀器Rj的識(shí)讀區(qū)域之間存在交集，就將頂點(diǎn)ri和rj用一個(gè)無(wú)向線段連接起來(lái)。據(jù)此建立中的閱讀器沖突問(wèn)題的平面圖G=（R，E)
有關(guān)文獻(xiàn)已經(jīng)證明了任意一個(gè)平面圖均可用 4 種顏色來(lái)進(jìn)行著色。因此，一個(gè)閱讀器網(wǎng)絡(luò)的防沖突問(wèn)題即類(lèi)似于一個(gè)平面圖的四色著色問(wèn)題。因此，閱讀器防沖突問(wèn)題可以看成閱讀器網(wǎng)絡(luò)的四時(shí)隙分配問(wèn)題。這里采用基于退火策略的混沌神經(jīng)網(wǎng)絡(luò)模型來(lái)進(jìn)行閱讀器四時(shí)隙分配問(wèn)題的求解。
3.閱讀器防沖突問(wèn)題的混沌神經(jīng)網(wǎng)絡(luò)模型
    采用神經(jīng)網(wǎng)絡(luò)方法求解閱讀器網(wǎng)絡(luò)防沖突問(wèn)題前，需要確定網(wǎng)絡(luò)中閱讀器之間可能存在的沖突關(guān)系，即獲得平面圖G=（R，E）的邊集E。
1）Hopfieid神經(jīng)網(wǎng)絡(luò)模型
     下面采用二維Hopfield神經(jīng)網(wǎng)絡(luò)（HNN）模型對(duì)閱讀器防沖突問(wèn)題進(jìn)行建模。
     首先，為了獲得閱讀器防沖突神經(jīng)網(wǎng)絡(luò)的能量函數(shù)，需要建立一個(gè)二維Hopfield神經(jīng)網(wǎng)絡(luò)，構(gòu)造一個(gè)n×4階的矩陣v。其中，n為網(wǎng)絡(luò)中閱讀器的數(shù)目，矩陣v的每一行包括4個(gè)神經(jīng)元，代表一種時(shí)隙，4個(gè)時(shí)隙T1，T2，T3，T4分別表示為‘1000’，‘0100’，‘0010’，‘0001’，那么n個(gè)閱讀器的四時(shí)隙分配結(jié)果就可以由n×4個(gè)神經(jīng)元表示出來(lái)。
     設(shè)n×n階對(duì)稱(chēng)矩陣d為閱讀器沖突關(guān)系矩陣，它描述網(wǎng)絡(luò)中閱讀器之間是否存在沖突，當(dāng)閱讀器Ri和閱讀器Rj之間具有沖突關(guān)系時(shí)，dij=1，否則dij=0。對(duì)于圖7-14所示的閱讀器網(wǎng)絡(luò)，可以構(gòu)造的閱讀器沖突關(guān)系矩陣為
為了消除網(wǎng)絡(luò)中的閱讀器沖突問(wèn)題，必須使網(wǎng)絡(luò)中存在沖突關(guān)系的閱讀器工作在不同的時(shí)隙。根據(jù)這樣的約束要求，建立如下閱讀器防沖突神經(jīng)網(wǎng)絡(luò)的能量函數(shù)：
    式中，A、B、C是常數(shù)；n×n階對(duì)稱(chēng)矩陣d為閱讀器沖突關(guān)系矩陣；矩陣v是神經(jīng)網(wǎng)絡(luò)的輸出矩陣。
     在式（7-3）中，第一項(xiàng)是行約束，在矩陣v的每一行4個(gè)神經(jīng)元中，只有一個(gè)神經(jīng)元的值為“1”，其余3個(gè)神經(jīng)元的值全部為0。也就是說(shuō)，當(dāng)每個(gè)閱讀器都分配了T1、T2、T3、T4、四個(gè)時(shí)隙中的任意一個(gè)時(shí)，該項(xiàng)的值為 0。式（7-3）中的第二項(xiàng)是一個(gè)全局約束，它有助于神經(jīng)網(wǎng)絡(luò)收斂于有效解，即當(dāng)神經(jīng)網(wǎng)絡(luò)收斂于有效解時(shí)，輸出矩陣 v 中每行只有一個(gè)神經(jīng)元的值為 1，對(duì) n×4 神經(jīng)元矩陣 v 來(lái)說(shuō)，所有值為 1 的神經(jīng)元的個(gè)數(shù)是 n，這時(shí)該項(xiàng)的值為0。式中最后一項(xiàng)為邊界懲罰函數(shù)，只有當(dāng)任意兩個(gè)存在沖突關(guān)系的閱讀器被分配了不同的工作時(shí)隙時(shí)，該項(xiàng)的值為 0。因此，當(dāng)神經(jīng)網(wǎng)絡(luò)的能量函數(shù) E 的值等于 0 時(shí)，當(dāng)前的輸出矩陣v的值就是閱讀器防沖突神經(jīng)網(wǎng)絡(luò)的可行解。
根據(jù)二維Hopfield神經(jīng)網(wǎng)絡(luò)能量函數(shù)的一般表達(dá)形式：
式中，wxi，yj表示神經(jīng)元vxi和vyj之
之間的連接權(quán)重；Ixi表示神經(jīng)元vxi的外部輸入偏差。比較式（7-3）和式（7-4），可以得到
因此，閱讀器防沖突神經(jīng)網(wǎng)絡(luò)的微分方程為
式中，f為神經(jīng)元的輸入/輸出函數(shù)；u為神經(jīng)元的內(nèi)部輸入；t為時(shí)間常數(shù)。解這個(gè)微分方程組就可以得到閱讀器防沖突神經(jīng)網(wǎng)絡(luò)的有效解。根據(jù)輸出矩陣的每行各個(gè)元素的值就可以確定分配給每個(gè)閱讀器的時(shí)隙。
2）基于退火策略的混沌神經(jīng)網(wǎng)絡(luò)模型
Hopfield神經(jīng)網(wǎng)絡(luò)模型可以收斂到一個(gè)穩(wěn)定的平衡解上，但會(huì)經(jīng)常陷入局部最優(yōu)。因此，在前面所建立的Hopfield神經(jīng)網(wǎng)絡(luò)模型基礎(chǔ)上引入混沌機(jī)制和模擬退火策略，為閱讀器防沖突建立基于退火策略的混沌神經(jīng)網(wǎng)絡(luò)模型，如下所示。
式中，vxi，uxi 和 Ixi 分別為神經(jīng)元的輸出、輸入和外部輸入偏差；wxi，yj 為神經(jīng)元連接權(quán)重系統(tǒng)；I0是一個(gè)正的常數(shù)；a 為比例系數(shù)；k 是神經(jīng)元的退火速度系數(shù)；z（t）為自反饋權(quán)重系數(shù)，β是z（t）的衰減系數(shù)。
式（7-12）中的 z（t）（vxi-I0）
項(xiàng)起自抑制反饋?zhàn)饔?，從而為系統(tǒng)帶來(lái)混沌狀態(tài)。而混沌具有隨機(jī)搜索的特質(zhì)，因此可以避免算法陷入局部最優(yōu)。同時(shí)為了有效地控制混沌行為，引入模擬溫度 z（t）。z（t）在算法搜索過(guò)程中按照式（7-13）逐漸衰減，這樣使得神經(jīng)網(wǎng)絡(luò)經(jīng)過(guò)一個(gè)倒分岔過(guò)程而逐漸趨于穩(wěn)定的平衡點(diǎn)。當(dāng)模擬溫度衰減至趨近于‘0’時(shí)，混沌狀態(tài)消失，此后算法獲得一個(gè)較好的初值，并按照 Hopfield 神經(jīng)網(wǎng)絡(luò)算法繼續(xù)進(jìn)行搜索并逐漸收斂于有效解。4.仿真實(shí)驗(yàn)
1）仿真流程
采用MATLAB對(duì)基于退火策略的混沌神經(jīng)網(wǎng)絡(luò)閱讀器時(shí)隙分配算法進(jìn)行仿
仿真。仿真流程如下：
步驟 1：設(shè)置 A，B，C，I0，ε，k，α，z（0），β，uxi（0）等參數(shù)的值，如表 7-4所示。實(shí)驗(yàn)中，uxi（0）取[0，1]區(qū)間的隨機(jī)數(shù)。
步驟2：根據(jù)式（7-10）和式（7-11）計(jì)算vxi（t）。
步驟3：根據(jù)式（7-3）計(jì)算能量函數(shù)E。
步驟4：根據(jù)式（7-12）計(jì)算uxi（t+1）。
步驟 5：判斷能量函數(shù)是否滿足穩(wěn)定條件。如果滿足進(jìn)行步驟 6，否則進(jìn)行步驟 2。能量函數(shù)的穩(wěn)定判據(jù)為：E 的值在連續(xù) l0 次迭代中的變化量小于 0
01；如果 E ≤10-6，則停止迭代；如果算法在1000次迭代中無(wú)法收斂到有效解，則停止仿真。
步驟6：輸出仿真結(jié)果，即輸出v和E。
2）仿真實(shí)驗(yàn)結(jié)果
      對(duì)于圖7-13和圖7-14所示的閱讀器沖突網(wǎng)絡(luò)，用基于退火策略的混沌神經(jīng)網(wǎng)絡(luò)算法經(jīng)過(guò)162次迭代后，便得到了閱讀器防沖突的時(shí)隙分配有效解。輸出矩陣的值為、T2、T3、T4，對(duì)圖7-14所示的閱讀器網(wǎng)絡(luò)按照表7-5的結(jié)果進(jìn)行著色填充的結(jié)果
從圖7-16可以看出，任意兩個(gè)識(shí)讀區(qū)域存在交集的閱讀器（即存在沖突約束的閱讀器）的識(shí)讀區(qū)域分別采用了不同的填充方式，由此表明了求解結(jié)果的正確性。vout盡管與式Hopfieid神經(jīng)網(wǎng)
神經(jīng)網(wǎng)絡(luò)模型的矩陣值不同，但仍然是閱讀器防沖突時(shí)隙分配問(wèn)題的可行解。
     為了驗(yàn)證算法的可靠性和效率，對(duì)不同的閱讀器網(wǎng)絡(luò)規(guī)模（閱讀器數(shù)目）n=10、15、20、25、30進(jìn)行了50次實(shí)驗(yàn)，所有50次實(shí)驗(yàn)均得到了閱讀器防沖突問(wèn)題的有效解。對(duì)于不同網(wǎng)絡(luò)規(guī)模，算法求解的平均迭代次數(shù)分別為171次、236次、282次、314次及375次。實(shí)驗(yàn)結(jié)果表明了算法的可靠性及高效性。
3）算法性能分析
    首先，基于退火策略的混沌神經(jīng)網(wǎng)絡(luò)閱讀器防沖突算法是基于TDMA原理的，因此運(yùn)用該算法來(lái)解決閱讀器沖突問(wèn)題從原理上講是可行的。
    其次，該算法屬于集中式控制算法，算法的執(zhí)行過(guò)程在中央計(jì)算機(jī)上實(shí)現(xiàn)，幾乎不占用閱讀器的掃描時(shí)間（只在確定閱讀器之間的沖突關(guān)系時(shí)占用極少的時(shí)間）。而分布式算法在執(zhí)行的全過(guò)程中，所有的閱讀器要相互通信來(lái)協(xié)調(diào)時(shí)隙分配，在時(shí)隙分配完成前無(wú)法掃描標(biāo)簽。因此，從應(yīng)用的角度來(lái)說(shuō)，本節(jié)提出的方法更具有合理性和實(shí)用性。
     最后，在密集閱讀器環(huán)境中，Colorwave和IRCM算法大概需要10個(gè)時(shí)隙數(shù)量才能得到96%以上的傳輸成功率，而本節(jié)提出的新算法僅需4個(gè)時(shí)隙即可完成幾乎100%的傳輸成功率（除去算法執(zhí)行時(shí)間外都可以成功傳輸），
     顯然這里提出的新算法使得每個(gè)閱讀器具有更大的標(biāo)簽吞吐能力。