時隙ALOHA

時隙ALOHA（簡稱SA）是射頻識別(RFID)系統中常用的防碰撞算法。1972年，Roberts提出了時隙Aloha，它是對純Aloha的一種改進，其基本思想是把時間分成若干個相同的時間片，所有用戶在時間片開始時刻同步接入網路信道，若發生衝突，則必須等到下一個時間片開始時刻再傳送。該方法避免用戶傳送數據的隨意性，減少了數據衝突，提高了信道的利用率，並且其吞吐量可以增加到純Aloha的一倍。

基本介紹

• 中文名：時隙ALOHA
• 外文名：slotted-aloha
• 簡稱：SA
• 學科：計算機
• 提出時間：1972年
• 提出者：Roberts

重要參數

（1）G：表示系統的輸入負載，即 T 時間內所有標籤 N 向閱讀器傳送的總的數據包量。

（2）S：表示系統的吞吐率，也稱為識別效率，即所有標籤成功傳送的、有效的總的數據包量，也就是在時間 T 內標籤與閱讀器成功通信的平均次數，因此吞吐率S 等於 G 與成功傳送機率的乘積。對於 RFID 系統內標籤與閱讀器來說，S=1 表示每個標籤的數據都被成功傳送給閱讀器，沒有發生標籤碰撞的情況；S=0 表示數據在傳送過程中發生了碰撞，閱讀器沒有接收到任何數據信息，也可能是無數據傳輸的情況。由此可以看出，在 RFID 系統中，系統的吞吐率與信道的利用率和標籤成功傳輸的機率成正比關係，與數據錯誤傳輸的機率成反比關係。

純ALOHA算法

純 ALOHA 算法（PA）是 ALOHA 類算法中最基礎、最易實現的一種隨機性標籤防碰撞算法，也就是說該算法對標籤的識別是基於隨機機率的，所以不能保證所有標籤都能被識別出來，所以這類算法套用領域比較少，只套用在一些標籤數量較少且簡單的唯讀標籤中。

PA 算法的工作原理是基於“標籤先發言機制”的方法，也就是說標籤進入閱讀器產生的磁場區域後，通過天線接收到電磁波而被激活，激活後的標籤主動向閱讀器傳送訊息，這個主動傳送不受時間的先後限制。如果標籤未能被閱讀器所成功接收，也就是說此時時間信道內有多個標籤在傳輸數據，由於信道的限制和某些因素產生了數據間的碰撞，一旦此情況發生，閱讀器會傳送一指令命令所有標籤延遲傳送數據。由於標籤傳送數據時間的隨機性和延遲時間的隨機性，使得信道內標籤的數據呈現三種形式，即完成碰撞、部分碰撞和成功識別。如下圖1所示為純 ALOHA 算法的碰撞原理圖。閱讀器識別範圍內有三個標籤，當標籤 1 和標籤 2 發生碰撞後，閱讀器命令他們隨機延遲一段時間後再傳送訊息，直到閱讀器檢測出只有一個標籤3與其通信，則成功識別出該標籤。

圖1 純 ALOHA 算法碰撞原理示意圖

時隙ALOHA 算法

時隙 ALOHA 算法（SA）是在 PA 算法的基礎上考慮了時間因素，以此限制條件將其分成若干個具有一定時間間隔的時隙段的改進方法。在 PA 算法中，由於標籤選擇時間的隨機性，使得標籤的碰撞周期為 2T，標籤之間的碰撞還有部分碰撞的情況，所以為了減少碰撞周期，避免部分碰撞情況的發生，SA 算法由此應運而生。SA 算法增加了時隙的概念，將傳輸時間離散化，標籤隨機的選擇某一時隙進行數據的傳送，如圖 2 所示。當標籤進入閱讀器的識別範圍後，標籤自身攜帶的隨機數發生器產生一隨機數，標籤按此隨機數選擇時隙，若查詢時的時隙數與標籤選擇的時隙相匹配時標籤即回響，並立即傳送自身的數據信息；若時隙內有碰撞時，閱讀器將終止標籤繼續傳送信息並令標籤等待下一次查詢。在 SA 算法中，標籤只能選擇在每個時隙的開始階段傳送數據，而不是隨機的選擇時間傳送數據，所以需要一個同步機制來控制標籤，這個同步時鐘的控制由閱讀器來完成，並且每個時隙的長度要滿足標籤成功傳輸完一數據包所需的時間。

圖2 時隙 ALOHA 算法碰撞原理圖

由圖2可以看出，在 SA 算法中，由於同步時鐘的控制，標籤只能在時隙開始的時間點傳送數據信息，並且標籤在單獨的每個時隙內進行數據傳輸，所以只有在同一時隙的同一時間點傳送數據的標籤才會發生碰撞，即標籤之間的碰撞只有完全碰撞，而沒有部分碰撞情況，所以標籤的衝突周期由 PA 算法的 2T 減少為 T。

圖3 PA 和 SA 算法吞吐率與輸入負載的對比關係圖

SA 算法的系統效率為： 。

對上式求導後可得，當G=1時，S可取得最大值， ，比 PA 算法的吞吐率提高了一倍。圖3為利用 MATLAB 軟體對 PA 和 SA 算法進行仿真後，吞吐率與輸入負載的對比關係圖。

SA 算法雖然避免了部分碰撞情況的發生，提高了系統的識別效率，但是由於進行數據傳輸所需的時隙數是固定的，不能隨意進行動態調整，當標籤數量多時，時隙數不夠用，導致時隙內標籤的碰撞率急劇上升，也急劇的降低了系統的識別效率和信道利用率；當標籤數量少時，如有的時隙內沒有標籤在傳輸數據，則會產生許多空時隙，造成時隙的浪費。

基本工作流程

時隙 ALOHA 算法的基本工作流程如下：

1）讀寫器先傳送 Query 指令規定幀長 （時隙的個數）；

2）標籤在幀長範圍內隨機地選擇一個時隙回響讀寫器的指令並返回信息包，僅有一個標籤返回信息包的時隙稱為成功時隙，沒有標籤返回信息包的時隙稱為空時隙，有 2 個或更多個標籤返回信息包的時隙稱為碰撞時隙，發生碰撞的標籤會在下一幀繼續嘗試；

3）算法先根據前一幀的反饋（即觀測值：碰撞時隙數量 ，空時隙數量 和成功時隙數量 ），採用一定的標籤估算方法來估算場區內的標籤數量 n，並且據此選擇一個合適的幀長度 ；

4）讀寫器以 為下一輪識別的幀長，直到讀寫器工作場區內的標籤被全部識別完畢。

時隙ALOHA方案

在通信系統的媒質訪問控制協定中,頻寬一定，通常有兩種時隙ALOHA方案可供選擇。一種方案是在特定的時隙中，各個用戶隨機選擇擴頻碼，在碼分信道間競爭接入，這就是時隙ALOHA DS/CDMA(簡稱S-ALOHA-DS/CDMA)接入方案。另一種方案是把信道在頻域上分為多個窄帶子信道，這些子信道既可以採用傳統的頻分復用方法(整個頻帶劃分為互不重疊的子信道)，也可以採用正交頻分復用(各子載波有重疊，但保持正交)；對於後者，在特定的時隙中，各個用戶在子信道間競爭傳輸分組，這就是多載波時隙ALOHA(簡稱MC-S-ALOHA)方案。

在S-ALOHA-DS/CDMA中，若每個傳送用戶有唯一的擴頻碼字，不同的傳送方使用不同的擴頻碼來以時隙ALOHA方式傳送信息，則稱為基於傳送方的擴頻傳輸協定(T-SSA)，它的特點是沒有碼字選擇的衝突；若系統中的碼字總數受限於接收方的解調器總數 ，各個傳送方在碼集中競爭碼字傳送分組，則稱為基於接收方的擴頻傳輸協定(R-SSA)，它的特點是可以節省碼字數，減少碼字的同步時間,但有可能出現碼字競爭衝突。在MC-S-ALOHA中，假設有N個窄帶時隙ALOHA並行正交子信道，這些子信道的頻寬之和等於CDMA系統的頻寬。忽略熱噪聲的影響及載波間的干擾，則可以在時隙ALOHA方案中不採用糾錯編碼。