無線射頻識別技術(RFID)是一種利用射頻信號進行非接觸自動識別的技術，廣泛應用於物流、供應鏈管理、商業零售和交通運輸等領域。RFID系統一般由具有電子編碼(ID)的標籤和閱讀器組成，它們利用無線信道實現相互通信來交換信息。當系統中有多個標籤同時向閱讀器發送數據時，將會產生相互幹擾，使閱讀器不能正確接收信息，這就是標籤碰撞。防碰撞算法能夠有效解決標籤的碰撞問題，實現閱讀器高效、快速地讀取標籤信息。
目前主要存在兩種類型的標籤：有源標籤和無源標籤。前者通過電源提供能量來計算和發送信息，計算能力強，但使用成本高;後者通過接收閱讀器發送的電磁波獲得能量，計算能力有限，所以傳統網絡中的許多防碰撞技術難以直接應用，但較低的成本更利於其在RFID系統中推廣使用。本文研究的是無源標籤在RFID系統中的防碰撞問題，並基於ALOHA提出了一種改進算法，它能夠迅速處理當前識別循環中發生的碰撞，從而有效降低此後在循環中發生標籤碰撞的概率。仿真結果表明該方法效率較高，尤其在標籤數量較大時相比動態幀時隙算法(DFSA)消耗時隙更少。
1 幾種主要的防碰撞算法
目前，RFID系統中的標籤防碰撞算法主要分為基於ALOHA的算法和基於樹的算法兩大類。基於ALOHA的算法是隨機算法，該算法中標籤利用隨機時間響應閱讀器的命令。此類算法主要有時隙ALOHA算法、固定幀時隙算法、動態幀時隙算法等，其中系統效率最高的是動態幀時隙算法(DFSA)。算法中的「幀」是由閱讀器定義的一段時間長度，其中包含若干時隙，每個時隙長度等於標籤的數據幀長度。在ALOHA算法中標籤需要具備產生隨機數的功能。
固定幀時隙算法是一種基本算法，每幀的時隙數相同。在開始識別時，由閱讀器向作用範圍內所有標籤發送包含時隙數N的命令。標籤收到命令後，將其時隙計數器置為1，開始記錄時隙數，同時產生一個介於1和N的數作為其隨機選擇的時隙數值。當時隙計數器值與標籤隨機選擇的時隙數值相同時，向閱讀器發送應答消息。若標籤被閱讀器成功識別，則以後不再響應閱讀器。一個幀結束後，閱讀器開始識別時隙數同樣為N的新幀。該算法雖然簡單但識別效率不高，由於幀長固定，當標籤數遠小於時隙數時，會產生較多的空閒時隙，浪費系統資源;反之，則會產生過多的碰撞，大大降低系統效率。只有在標籤數目與時隙數相差不大時，才會有較好的系統效率。由於該算法的時隙數不能隨著標籤數目的變化而改變，因此，無法獲得穩定的系統效率。
動態幀時隙算法(DFSA)是一種改進的幀時隙算法，具有較高的效率。其每幀的時隙數會根據標籤數目的不同而變化，主要執行過程如下：(1)閱讀器估計在其作用範圍內未識別的標籤數目，從而決定下一幀需要的時隙數值N;(2)閱讀器發送包含N個時隙的幀，標籤隨機選擇一個時隙向閱讀器發送應答消息，在此過程中已被成功識別的標籤將不再響應閱讀器。重複執行(1)、(2)的操作直至成功識別所有標籤。該算法的效率在34.6%和36.8%之間[1]。
二進位樹算法系統效率高，但系統的設計複雜。其算法的基本思想是：將處於碰撞的標籤分為左右兩個子集0和1，先查詢子集0，如果沒有碰撞，則正確識別標籤，若仍然存在碰撞則再次分裂，把子集0分成00和01兩個子集，以此類推直到成功識別子集0中的所有標籤，再按上述步驟查詢子集1。該算法雖然不存在錯誤判決，但是整個識別過程需要逐一檢查標籤ID前綴是否匹配，如果一個標籤集中各個標籤的ID非常相近，則完成整個識別過程需要花費過長的時間。
2 改進的方法
本文提出一種基於ALOHA協議的簡單高效防碰撞算法，該算法能夠迅速處理標籤發生的碰撞。當發生碰撞時，系統會立刻開始一個新的識別過程，此時閱讀器需要先估計發生碰撞的標籤數目，然後向碰撞標籤發送重新設置的時隙數值，而標籤也會產生一個隨機選擇的時隙數值，當該隨機數等於其時隙計數器時，向閱讀器發送應答消息。如果在這個新的識別過程中再次發生碰撞，則重複執行上述步驟，這樣可以減少如下情況的發生：當前發生碰撞的標籤在下一次循環中可能再次發生碰撞從而在系統中產生更多的碰撞。
實驗中假定有n個不同電子編碼(ID)的無源標籤，閱讀器可以估計標籤數目但是不知道其確切的值。設初始時隙數為Ni，當開始識別時，閱讀器向所有標籤發送包含Ni的消息，標籤收到後將產生一個介於1和Ni之間的隨機數，當標籤的時隙計數器值與其隨機產生的時隙數值相同時，將向閱讀器發送應答消息。若此過程中沒有發生碰撞，則閱讀器就能成功識別標籤。上述過程與ALOHA算法類似。但如果標籤發生碰撞，閱讀器則放棄之前已經成功識別的時隙，開始一個新的識別過程(此處假定閱讀器和標籤能夠成功完成規定的動作)。在此過程中，閱讀器估計發生碰撞的標籤數目nc[2]，通過nc來確定新設置的時隙數Nc，標籤收到包含該數的消息後產生一個介於1和Nc之間的隨機數，重複執行此過程直到不再發生碰撞。圖1是本文方法的流程圖，圖中閱讀器初始時發送包含Ni的消息，當發生碰撞時，能夠迅速進行處理。剩餘的標籤將在第一組碰撞標籤處理完成後再進行識別。
前面在描述DFSA算法時提到，閱讀器會在第一輪識別完成後發送一個新設置的時隙數值給所有發生碰撞的標籤，這些標籤分別產生隨機選擇的時隙數。但是可以發現，第一輪識別中發生碰撞的標籤同樣可能在之後的識別輪次中再次發生碰撞，而本文的方法能夠迅速處理標籤的碰撞，降低碰撞標籤以後再次發生碰撞的概率。閱讀器本身無法知道發生碰撞標籤數目，但是可以通過估計得到nc，由nc確定重新設置的時隙數值Nc並開始新的循環。為了獲得較優的系統吞吐率，本文根據不同範圍的標籤數由表1來確定Nc[3]。
當未被識別的標籤數目很少時就不需要採用過大的時隙數值，反之如果標籤數目很多而時隙數過小時，則發生碰撞的概率將會增加。當設置的時隙數與需要識別的標籤數目相等時，可以獲得最大系統效率[4]。因此，選擇合適的時隙數非常重要。在本文的方法中，將根據表1的數據來確定識別過程中不斷改變的時隙數值。
為了執行本文的方法，需先定義一個特殊的命令「throw_away」，它表示開始執行該方法的各個步驟，程序1所示是閱讀器需執行程序的偽碼，描述了當閱讀器檢測到標籤碰撞時將會發生的動作。當c>0時，表示發生碰撞，閱讀器將發送throw_away命令給碰撞標籤;ad是針對碰撞標籤的計數值，當發生碰撞時，ad的值加1;在此之後閱讀器將通過估計碰撞標籤數目來確定Nc。
程序1 檢測到碰撞時閱讀器執行的程序
/*Reader:*/
/*發送」throw_away」命令*/
if (c>0) /* 發生碰撞*/
/* 閱讀器發送throw_away命令給發生碰撞的標籤 */
tag_respond = tag (throw_away);
if ( tag_respond > 0 ) /* 命令發送成功 */
ad = ad + 1; /*當發生碰撞時ad的值增加1 */
tag (ad); /* 將ad的值發送給標籤 */
start a new round;
broadcast Nc;
程序2所示是標籤需執行程序的偽碼，描述了碰撞標籤收到閱讀器發送的throw_away命令後將會發生的動作。通過設置ct的值來限制碰撞標籤應答閱讀器，當標籤接收到throw_away命令時其值加1;當標籤隨機選擇的時隙數等於其時隙計數器值，並且ad與ct相等時，發送應答消息給閱讀器，同時ct值置0，標籤再次收到throw_away命令之前不再響應閱讀器。
程序2 接收到throw_away命令時標籤執行的程序
/* Tag: */
/* 從閱讀器處獲取初始參數 */
ct = 1;
transmission;
receive the number of slots;
generate random numbers;
if ( slot = = ti && ct = = ad )
transmit message; /* 標籤發送應答消息 */
ct = 0; /* 發送完成後ct置0 */
if (receive 「throw_away」)
ct = ct + 1;
goto transmission;
如果在最後一個時隙中發生標籤碰撞，系統將會放棄之前已經成功識別的時隙。若此情況經常出現，則系統效率會降低很多，這是應用本文方法理論上可能會發生的最壞情況。圖2的仿真結果是這種情況發生的概率，從中可以看出當標籤數量較大時，這種最壞的情況發生概率其實很小。因此，當標籤數目較多時，這種最壞的情況幾乎不會發生，而應用本文的方法就可以減少識別過程中的時隙消耗。
3 仿真結果
大量標籤向閱讀器發送消息時產生碰撞，假定標籤數從10增加到300，圖3是應用本文方法進行仿真得到的結果。從中可以看出本文方法比DFSA算法耗費的時隙少，並且標籤數目越多差別越明顯。這表明對比DFSA算法，本文方法節約了時隙資源。
為獲得較高的系統效率，仿真時設初始時隙數Ni為16，約為開始時的標籤數目。可以通過改變初始時隙數Ni來觀察所產生的影響，圖4表明，當初始時隙數變為64時，即使標籤數目增加，系統效率也不會有明顯的變化;但標籤數目較少時，較大的初始時隙數Ni對應較小的碰撞發生概率,此時，Ni=128時的系統效率比Ni=16和Ni=64時低。上述結果表明初始時隙數Ni設為16，可以應用於標籤數較多的情況。
設初始幀長Ni為16，持續增加標籤數目，仿真結果如圖5所示。可以看出，當標籤數持續增加時，本文方法耗費的時隙數明顯小於DFSA算法;而當標籤數較少時，這種差異並不明顯。綜上，本文提出的方法系統效率優於DFSA算法，並且耗費更少的時隙。
本文提出了一種基於ALOHA協議的簡單高效RFID系統防碰撞算法。閱讀器先給標籤發送一個包含初始時隙數的消息，標籤收到後隨機選擇一個時隙同時將自己的時隙計數器置為1。當標籤隨機選擇的時隙數等於時隙計數器時，回復其電子編碼(ID)給閱讀器，如果發生碰撞，閱讀器將放棄已經成功識別的時隙而開始新的識別循環，這樣使碰撞標籤能得到迅速處理。該方法中閱讀器能夠在新的識別循環中首先鑑別出碰撞標籤，然後再識別其餘的標籤。當標籤數增加到1 000時，本文方法比DFSA算法少耗費約54%的時隙，並且系統效率可以穩定在35%左右，相比DFSA算法此時約20%[5]的效率也有較大提高。
1