-
時隙ALOHA
鎖定
- 中文名
- 時隙ALOHA
- 外文名
- slotted-aloha
- 簡 稱
- SA
- 學 科
- 計算機
- 提出時間
- 1972年
- 提出者
- Roberts
目錄
- 1 重要參數
- 2 純ALOHA算法
- 3 時隙ALOHA 算法
- 4 基本工作流程
- 5 時隙ALOHA方案
時隙ALOHA重要參數
(1)G:表示系統的輸入負載,即 T 時間內所有標籤 N 向閲讀器發送的總的數據包量。
(2)S:表示系統的吞吐率,也稱為識別效率,即所有標籤成功傳送的、有效的總的數據包量,也就是在時間 T 內標籤與閲讀器成功通信的平均次數,因此吞吐率S 等於 G 與成功傳送概率的乘積。對於 RFID 系統內標籤與閲讀器來説,S=1 表示每個標籤的數據都被成功傳送給閲讀器,沒有發生標籤碰撞的情況;S=0 表示數據在傳送過程中發生了碰撞,閲讀器沒有接收到任何數據信息,也可能是無數據傳輸的情況。由此可以看出,在 RFID 系統中,系統的吞吐率與信道的利用率和標籤成功傳輸的機率成正比關係,與數據錯誤傳輸的機率成反比關係。
[1]
時隙ALOHA純ALOHA算法
純 ALOHA 算法(PA)是 ALOHA 類算法中最基礎、最易實現的一種隨機性標籤防碰撞算法,也就是説該算法對標籤的識別是基於隨機概率的,所以不能保證所有標籤都能被識別出來,所以這類算法應用領域比較少,只應用在一些標籤數量較少且簡單的只讀標籤中。
PA 算法的工作原理是基於“標籤先發言機制”的方法,也就是説標籤進入閲讀器產生的磁場區域後,通過天線接收到電磁波而被激活,激活後的標籤主動向閲讀器發送消息,這個主動發送不受時間的先後限制。如果標籤未能被閲讀器所成功接收,也就是説此時時間信道內有多個標籤在傳輸數據,由於信道的限制和某些因素產生了數據間的碰撞,一旦此情況發生,閲讀器會發送一指令命令所有標籤延遲發送數據。由於標籤發送數據時間的隨機性和延遲時間的隨機性,使得信道內標籤的數據呈現三種形式,即完成碰撞、部分碰撞和成功識別。如下圖1所示為純 ALOHA 算法的碰撞原理圖。閲讀器識別範圍內有三個標籤,當標籤 1 和標籤 2 發生碰撞後,閲讀器命令他們隨機延遲一段時間後再發送消息,直到閲讀器檢測出只有一個標籤3與其通信,則成功識別出該標籤。
[1]
時隙ALOHA時隙ALOHA 算法
時隙 ALOHA 算法(SA)是在 PA 算法的基礎上考慮了時間因素,以此限制條件將其分成若干個具有一定時間間隔的時隙段的改進方法。在 PA 算法中,由於標籤選擇時間的隨機性,使得標籤的碰撞週期為 2T,標籤之間的碰撞還有部分碰撞的情況,所以為了減少碰撞週期,避免部分碰撞情況的發生,SA 算法由此應運而生。SA 算法增加了時隙的概念,將傳輸時間離散化,標籤隨機的選擇某一時隙進行數據的傳送,如圖 2 所示。當標籤進入閲讀器的識別範圍後,標籤自身攜帶的隨機數發生器產生一隨機數,標籤按此隨機數選擇時隙,若查詢時的時隙數與標籤選擇的時隙相匹配時標籤即響應,並立即發送自身的數據信息;若時隙內有碰撞時,閲讀器將終止標籤繼續發送信息並令標籤等待下一次查詢。在 SA 算法中,標籤只能選擇在每個時隙的開始階段發送數據,而不是隨機的選擇時間發送數據,所以需要一個同步機制來控制標籤,這個同步時鐘的控制由閲讀器來完成,並且每個時隙的長度要滿足標籤成功傳輸完一數據包所需的時間。
由圖2可以看出,在 SA 算法中,由於同步時鐘的控制,標籤只能在時隙開始的時間點發送數據信息,並且標籤在單獨的每個時隙內進行數據傳輸,所以只有在同一時隙的同一時間點發送數據的標籤才會發生碰撞,即標籤之間的碰撞只有完全碰撞,而沒有部分碰撞情況,所以標籤的衝突週期由 PA 算法的 2T 減少為 T。
SA 算法的系統效率為:
。
對上式求導後可得,當G=1時,S可取得最大值,
,比 PA 算法的吞吐率提高了一倍。圖3為利用 MATLAB 軟件對 PA 和 SA 算法進行仿真後,吞吐率與輸入負載的對比關係圖。
SA 算法雖然避免了部分碰撞情況的發生,提高了系統的識別效率,但是由於進行數據傳輸所需的時隙數是固定的,不能隨意進行動態調整,當標籤數量多時,時隙數不夠用,導致時隙內標籤的碰撞率急劇上升,也急劇的降低了系統的識別效率和信道利用率;當標籤數量少時,如有的時隙內沒有標籤在傳輸數據,則會產生許多空時隙,造成時隙的浪費。
[1]
時隙ALOHA基本工作流程
時隙 ALOHA 算法的基本工作流程如下:
1)讀寫器先發送 Query 指令規定幀長
(時隙的個數);
2)標籤在幀長範圍內隨機地選擇一個時隙響應讀寫器的指令並返回信息包,僅有一個標籤返回信息包的時隙稱為成功時隙,沒有標籤返回信息包的時隙稱為空時隙,有 2 個或更多個標籤返回信息包的時隙稱為碰撞時隙,發生碰撞的標籤會在下一幀繼續嘗試;
3)算法先根據前一幀的反饋(即觀測值:碰撞時隙數量
,空時隙數量
和成功時隙數量
),採用一定的標籤估算方法來估算場區內的標籤數量 n,並且據此選擇一個合適的幀長度
;
時隙ALOHA時隙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方案中不採用糾錯編碼。
[3]