一種ALOHA算法的幀長度改進方法

陳夫桂 姜志峰 朱利娟 云中華

摘 要： 基于動態幀時隙ALOHA算法，運用擬牛頓法，使用某種近似矩陣代替牛頓法中的Hessian矩陣，解決牛頓法中復雜度計算的問題，由此縮短計算時間并提高計算精度。統計出不同時隙數下可識別的標簽數，進而建立專家庫，使讀寫器根據標簽數目更準確地設定時隙數，達到全局搜索的目的，進而縮短匹配識別時間。仿真結果表明，運用擬牛頓法明顯提高了數據交換量和識別效率。

關鍵詞： ALOHA； 擬牛頓法； 近似矩陣； 專家庫； 全局搜索； 識別效率

中圖分類號： TN911.1?34； TP301 文獻標識碼： A 文章編號： 1004?373X（2018）15?0097?04

A frame length improved method based on ALOHA algorithm

CHEN Fugui1， JIANG Zhifeng2， ZHU Lijuan3， YUN Zhonghua2

（1. Office of Academic Affairs， Tibet University， Lhasa 850012， China； 2. School of Engineering， Tibet University， Lhasa 850012， China；

3. Tibetan Information Technology Research Center， Tibet University， Lhasa 850012， China）

Abstract： On the basis of dynamic frame slotted ALOHA algorithm， the Hessian matrix in the Newton method is replaced by a certain approximate matrix in quasi?Newton method to solve the problem of complexity calculation in Newton method， which can shorten the computation time and improve the calculation precision. The number of identifiable tags under different time slots is calculated to establish the expert library， so as to make the reader?writer set the number of time slots more accurately according to the number of tags， achieve the purpose of global search， and shorten the matching and recognition time. The simulation results show that the quasi?Newton method can improve the data exchange capacity and recognition efficiency effectively.

Keywords： ALOHA； quasi?Newton method； approximate matrix； expert library； global search； recognition efficiency

0 引 言

射頻識別技術（Radio Frequency Identification，RFID）是一種非接觸式自動識別技術，具有安全性、便捷性和高效性等優點，被廣泛應用在農業、控制業和交通運輸業等各個領域，成為物聯網應用的熱門技術之一。另外，RFID技術的普遍推廣和應用，RFID系統存在的問題也日漸凸顯，如多個標簽同時占用一個信道或者多個讀寫器爭搶一個標簽。其中讀寫器同時識別多個標簽時發生的碰撞尤為嚴重，即讀寫器同時接收2個或2個以上標簽數據。目前對于解決多標簽碰撞問題有三大類算法[1?2]：基于確定性的二進制算法、基于概率性的ALOHA算法和這兩者的混合改進算法。

ALOHA算法中標簽隨機向讀寫器發送數據，在同一時間內讀寫器接收到多個標簽發送的數據時就會發生數據重疊，發生碰撞的標簽等待一段時間再次發送，直到標簽完全被讀寫器成功識別，其他改進方法是把時間長度進行劃分調整。此類算法操作性強，但識別效率相對較低。由于每個標簽都有一個特定的ID號，二進制算法通過分類的思想，對發生碰撞標簽的碰撞位進行劃分為“0”和“1”兩個子ID，進行標簽再識別。這種算法識別效率相對較高，在實際應用中比較普遍。但這兩種算法在實際應用中都會受到不同因素的約束，而本文考慮在節約經濟成本和提高系統識別效率的前提下對ALOHA算法進行數學改進，通過建立專家庫的方法構建不同時隙數所能識別的匹配標簽數，有效縮短識別時間并提高了平均數據包交換量。

1 ALOHA算法

ALOHA算法[3?4]包括純ALOHA算法、時隙ALOHA算法、幀時隙ALOHA算法和動態幀時隙ALOHA算法。純ALOHA算法在連續的時間內隨機選擇某個時間點發送數據；時隙ALOHA算法是在純ALOHA算法的基礎上把時間長度劃分為離散的時隙間隔，隨機選擇某個時隙發送數據；幀時隙ALOHA算法是把離散化的某幾個時隙組合成一幀，進而改進為本文中動態的改進幀長度算法，即動態幀時隙ALOHA算法。

2 改進方法

2.1 估計標簽數

動態幀時隙ALOHA算法是根據標簽數目變化動態地改變幀長數目的大小，而本文根據已有動態幀時隙ALOHA算法研究[5?6]成果進行改進。通過仿真分析上一幀讀寫器的識別情況，動態地調整下一幀所需的時隙數。統計出每一幀所需的最佳時隙數，建立專家庫，進行全局搜索匹配，準確地設定時隙數目，縮短識別匹配時間。

假設動態幀時隙ALOHA算法中幀時隙數和標簽的數目分別為[s]和[n]，其中一個標簽占用某個時隙的概率服從二項分布。在時隙數范圍內，標簽選擇占用某個時隙的概率相等，[m]個標簽選擇同一個時隙的概率為：

經過一輪識別后，統計出成功識別的時隙數、碰撞時隙數和空閑時隙數的數目分別為[Ns]，[Nc]和[Nf]。其中發生碰撞的概率為[Nfs]。由式（5）可得：

式中：碰撞時隙數[Nf]和幀時隙數[s]已知，利用數學方法求解出標簽數[n]。本文在牛頓法的基礎上采用擬牛頓法進行數學改進。由于牛頓法每迭代1次，牛頓法結果的有效數字將會增加1倍，而且每次都要計算迭代函數的Hessian矩陣和它的逆矩陣，當計算維數較大時，復雜度也會增加，而擬牛頓法[7]中使用某種近似矩陣代替Hessian矩陣，可以解決牛頓法中復雜度計算的問題，縮短計算時間并提高計算精度。

基本步驟如下：

1） 取初始值為[n0]，收斂精度[ε>0]；

2） 設[H0=I]，[k=0]，計算出目標函數在[nk]處的梯度[gk=?f（nk）]，若[gk≤ε]，計算終止；否則轉步驟3）；

3） 確定搜索方向[pk]，[pk=Hk?gk]；

4） 從[nk]開始，沿[pk]做一維搜索，滿足[f（nk+tk?pk）=mint≥0f（nk+tk?pk）]且[nk+1=nk+tk?pk]；

5） 若[f（nk+1）≤ε]，計算終止；否則轉步驟6）；

6） 若[k=m]，則令[n0=nm+1]，轉步驟2）；否則令[Δnk=][nk+1-nk]，[Δpk=pk+1-pk]，[Δgk=gk+1-gk]，計算出[Hk+1]；

7） 令[k=k+1]，轉步驟3）。

上述步驟為擬牛頓迭代算法的基本過程，但在實際應用中，很多標簽的寄存器位數小于8位，故對應的幀長數[8]小于256（[L≤28]），同時在整個系統中碰撞時隙數小于幀長數。因此，對進行擬牛頓迭代算法式（7）中的[Nc]和[L]是在一定數目內的，可以通過上述方法求解出對應不同幀時隙數的標簽數。擬牛頓法基本流程圖如圖1所示。

2.2 算法流程改進

標簽識別時，每次完全識別都會耗費大量時間，造成整個系統總的識別時間較長。故在上述基礎上通過構建專家庫的思想，可進行全局匹配，即不同時隙數與對應標簽數進行匹配。這樣可以大大縮短因匹配不佳或者不符合而耗費時間，提高整個系統的識別時間。改進算法流程如圖2所示。

讀寫器首先發送請求命令，等待標簽響應回復，并初始化空閑時隙計數器[Nf]、碰撞時隙計數器[Nc]和成功識別時隙計數器[Ns]為0，以及幀長數[9][L=2Q（Q=1，2，8）]。此時經過一輪識別后，判斷時隙可響應狀態為空閑、碰撞或成功，對于成功識別或者發生碰撞的時隙計數器加1，同時幀長數減1。數次循環后，判斷幀長數是否為零；若幀長數不為零，調整標簽應答命令；若為零，此時判斷碰撞時隙計數器[Nc]是否為零，若為零，識別結束，否則通過查詢專家庫調整幀長數，循環上述過程，直至標簽完全識別。

上述識別過程中假定標簽數小于256，而在實際應用場合中標簽數目遠大于256。當標簽數大于256時，求解出不同時隙數所對應的標簽數時計算復雜度會增加，同時，識別大量標簽時，整個系統的功率損耗也會增加，識別時間也會變長。此時，就需要對標簽數進行分組處理。表1為標簽分組處理原則[10]。

3 仿真結果與分析

通過對動態幀時隙ALOHA算法中幀長度進行改進，提出一種操作性強、經濟成本低的方法。但在實際應用中首先考慮標簽的數目，在最優標簽數的情況下建立專家庫。然后直接依據專家庫設定不同時隙數下可識別的標簽數，這樣可大大縮短系統識別時間，有效提高系統識別效率。

本文中選取100個標簽，分別對固定幀時隙算法和改進算法進行Matlab實驗仿真。固定幀時隙算法中幀長數目是固定的，無法改變。由于改進算法能動態的反應時隙數的變化情況，從而動態地設定標簽數，使得讀寫器周圍存在的標簽可以完全被成功識別。

圖3中的兩種算法分別是固定幀時隙算法和改進后的動態幀時隙算法。前者的幀長數目是固定的，通過大量的Matlab實驗仿真發現，當幀長數為64時系統的識別性能最高。識別100個標簽大約需要370個時隙，即平均每3.7個時隙識別一個標簽。對于改進算法，識別100個標簽大約需要300個時隙，平均每3個時隙成功識別一個標簽，相比固定幀時隙算法識別效率有所提高。

圖4為平均數據包交換量與吞吐率的關系。從圖中可以看出：當平均數據包交換量小于0.4時，兩種算法的吞吐率相近；當大于0.4時，改進算法的吞吐率明顯高于固定幀時隙ALOHA算法的吞吐率；而改進算法的平均數據包交換量達到4.5，固定幀時隙ALOHA算法的吞吐率僅持續到3.4左右，相比于固定幀時隙ALOHA算法的平均數據包交換量大約提高了36.3%。另外從圖5中可以看出，當標簽數在100～300之間時，系統的識別效率在25%～40%之間浮動。所以本文中的改進算法在數據交換量和吞吐效率方面都有所提高。

4 結 論

本文在動態幀時隙ALOHA算法的基礎上，利用數學思想提出一種改進幀長度的方法。改進算法的核心在于建立專家庫進行全局搜索，動態地依據專家庫設定不同時隙數下所對應匹配的標簽數，相比固定幀時隙ALOHA算法，提高了系統平均數據交換量并縮短系統識別時間。因此，本文改進的方法有效提高了標簽識別效率。

注：本文通訊作者為云中華。

參考文獻

[1] 王飛，張武.基于分組的動態時隙ALOHA算法[J].計算機系統應用，2013，22（7）：77?80.

WANG Fei， ZHANG Wu. Algorithm based on packet dynamic time slot ALOHA [J]. Computer systems & applications， 2013， 22（7）： 77?80.

[2] 馬翠紅，趙躍，楊友良，等.一種改進的RFID防碰撞時隙ALOHA算法[J].河北聯合大學學報（自然科學版），2014，36（2）：54?57.

MA Cuihong， ZHAO Yue， YANG Youliang， et al. An improved RFID anti?collision slot ALOHA algorithm [J]. Journal of Hebei United University （natural science）， 2014， 36（2）： 54?57.

[3] 陳坤，蘇寒松，孫尚龍.RFID中基于分組動態A?LOHA防碰撞算法的研究[J].電子測量技術，2011，34（11）：55?57.

CHEN Kun， SU Hansong， SUN Shanglong. Research on A?LOHA anti?collision algorithm based on packet dynamic type in RFID [J]. Electronic measurement technology， 2011， 34（11）： 55?57.

[4] 張小紅，胡應夢.分組自適應分配時隙的RFID防碰撞算法研究[J].電子學報，2016，44（6）：1328?1335.

ZHANG Xiaohong， HU Yingmeng. Research on RFID anti?collision algorithm for adaptive allocation of time slots [J]. Acta electronica sinica， 2016， 44（6）： 1328?1335.

[5] 陳平華，王康順，李超，等.基于線性回歸的動態幀時隙ALOHA算法[J].計算機仿真，2014，31（7）：259?263.

CHEN Pinghua， WANG Kangshun， LI Chao， et al. Dynamic frame slot ALOHA algorrithm based on linear regression [J]. Computer simulation， 2014， 31（7）： 259?263.

[6] 管小衛，傅偉，蔣道霞.一種改進的分組幀時隙ALOHA算法[J].制造業自動化，2014，36（14）：1?4.

GUAN Xiaowei， FU Wei， JIANG Daoxia. An improved packet frame time slot ALOHA algorithm [J]. Manufacturing automation， 2014， 36（14）： 1?4.

[7] 馬琰，蔡麗霞，任曉娜.一種自適應幀長RFID標簽防碰撞算法[J].計算機與現代化學，2014（11）：113?116.

MA Yan， CAI Lixia， REN Xiaona. A collision avoidance algorithm for adaptive frame?length RFID tags [J]. Computer and modern chemistry， 2014（11）： 113?116.

[8] 黃仁，張靜，程平.一種ALOHA算法的幀長度調整方法[J].計算機工程與應用，2011，47（9）：115?117.

HUANG Ren， ZHANG Jing， CHENG Ping. A frame length adjustment method for ALOHA algorithm [J]. Computer engineering and applications， 2011， 47（9）： 115?117.

[9] 高樂，吳援明，王曉磊.一種用于RFID系統中的幀長度調整方法[J].微計算機信息，2007（5）：213?215.

GAO Le， WU Yuanming， WANG Xiaolei. A frame length adjustment method used in RFID system [J]. Microcomputer information， 2007（5）： 213?215.

[10] 李晶.一種改進的RFID防碰撞時隙ALOHA算法[D].長春：吉林大學，2009.

LI Jing. An improved RFID anti?collision slot ALOHA algorithm [D]. Changchun： Jilin University， 2009.