0 引言  

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

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

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

1．2 分時(shí)傳輸解決讀寫(xiě)器沖突  

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

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

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

1．3 平面圖著色與讀寫(xiě)器防沖突  

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

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

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

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

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

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

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

是一種可行的四時(shí)隙分配結(jié)果。 

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

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

　　其中，A， B，C是常數(shù)，n×n階對(duì)稱矩陣d為讀寫(xiě)器沖突關(guān)系矩陣，矩陣v是神經(jīng)網(wǎng)絡(luò)的輸出矩陣。在式(3)的能量函數(shù)中，第一項(xiàng)是行約束，在矩陣v的每一行的4個(gè)神經(jīng)元當(dāng)中，只有一個(gè)神經(jīng)元的值為‘1’，其余3個(gè)神經(jīng)元的值全部為0。也就是說(shuō)，當(dāng)每個(gè)讀寫(xiě)器都分配了T1,T2,T3,T4,4個(gè)時(shí)隙中的任意一個(gè)的時(shí)候，該項(xiàng)的值為 
0。第二項(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í)式(3)中的第二項(xiàng)的值為0。最后一項(xiàng)為邊界懲罰函數(shù)，只有當(dāng)任意兩個(gè)存在沖突關(guān)系的讀寫(xiě)器被分配了不同的工作時(shí)隙的情況下，該項(xiàng)的值為0。因此，當(dāng)神經(jīng)網(wǎng)絡(luò)的能量函數(shù)E的值等于‘0’時(shí)，當(dāng)前的輸出矩陣v的值就是讀寫(xiě)器防沖突神經(jīng)網(wǎng)絡(luò)的可行解。

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

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

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

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

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

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

　　其中Vxi，Uxi和Ixi 分別為神經(jīng)元的輸出、輸入和外部輸入偏差Vxi，yj 為神經(jīng)元連接權(quán)重系統(tǒng)，Io是一個(gè)正的常數(shù)，a為比例系數(shù)，k是神經(jīng)元的退火速度系數(shù)，z(t)自反饋權(quán)重系數(shù)， 是z(t)的衰減系數(shù)。式(12)中的z(t)(％ 一Io)項(xiàng)起自抑制反饋?zhàn)饔?，從而為系統(tǒng)帶來(lái)混沌狀態(tài)。而混沌具有隨機(jī)搜索的特質(zhì)，因此可以避免算法陷入局部最優(yōu)。同時(shí)為了有效地控制混沌行為，引入模擬溫度z(t)，z(t) 在算法搜索過(guò)程中按照式(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)行搜索并逐漸收斂于有效解。

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

3．2 仿真實(shí)驗(yàn)結(jié)果 

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

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

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

　　若以4種形狀分別代表時(shí)隙 T1, T2, T3, T4,對(duì)圖2所示的讀寫(xiě)器網(wǎng)絡(luò)按照表2的結(jié)果進(jìn)行著色填充的結(jié)果如圖5所示。

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

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

3．3 算法性能分析 

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

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

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

4 結(jié)論

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

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

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