一種ALOHA算法的幀長度改進(jìn)方法

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

摘 要： 基于動(dòng)態(tài)幀時(shí)隙ALOHA算法，運(yùn)用擬牛頓法，使用某種近似矩陣代替牛頓法中的Hessian矩陣，解決牛頓法中復(fù)雜度計(jì)算的問題，由此縮短計(jì)算時(shí)間并提高計(jì)算精度。統(tǒng)計(jì)出不同時(shí)隙數(shù)下可識(shí)別的標(biāo)簽數(shù)，進(jìn)而建立專家?guī)?，使讀寫器根據(jù)標(biāo)簽數(shù)目更準(zhǔn)確地設(shè)定時(shí)隙數(shù)，達(dá)到全局搜索的目的，進(jìn)而縮短匹配識(shí)別時(shí)間。仿真結(jié)果表明，運(yùn)用擬牛頓法明顯提高了數(shù)據(jù)交換量和識(shí)別效率。

關(guān)鍵詞： ALOHA； 擬牛頓法； 近似矩陣； 專家?guī)欤?全局搜索； 識(shí)別效率

中圖分類號： TN911.1?34； TP301 文獻(xiàn)標(biāo)識(shí)碼： 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 引 言

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

ALOHA算法中標(biāo)簽隨機(jī)向讀寫器發(fā)送數(shù)據(jù)，在同一時(shí)間內(nèi)讀寫器接收到多個(gè)標(biāo)簽發(fā)送的數(shù)據(jù)時(shí)就會(huì)發(fā)生數(shù)據(jù)重疊，發(fā)生碰撞的標(biāo)簽等待一段時(shí)間再次發(fā)送，直到標(biāo)簽完全被讀寫器成功識(shí)別，其他改進(jìn)方法是把時(shí)間長度進(jìn)行劃分調(diào)整。此類算法操作性強(qiáng)，但識(shí)別效率相對較低。由于每個(gè)標(biāo)簽都有一個(gè)特定的ID號，二進(jìn)制算法通過分類的思想，對發(fā)生碰撞標(biāo)簽的碰撞位進(jìn)行劃分為“0”和“1”兩個(gè)子ID，進(jìn)行標(biāo)簽再識(shí)別。這種算法識(shí)別效率相對較高，在實(shí)際應(yīng)用中比較普遍。但這兩種算法在實(shí)際應(yīng)用中都會(huì)受到不同因素的約束，而本文考慮在節(jié)約經(jīng)濟(jì)成本和提高系統(tǒng)識(shí)別效率的前提下對ALOHA算法進(jìn)行數(shù)學(xué)改進(jìn)，通過建立專家?guī)斓姆椒?gòu)建不同時(shí)隙數(shù)所能識(shí)別的匹配標(biāo)簽數(shù)，有效縮短識(shí)別時(shí)間并提高了平均數(shù)據(jù)包交換量。

1 ALOHA算法

ALOHA算法[3?4]包括純ALOHA算法、時(shí)隙ALOHA算法、幀時(shí)隙ALOHA算法和動(dòng)態(tài)幀時(shí)隙ALOHA算法。純ALOHA算法在連續(xù)的時(shí)間內(nèi)隨機(jī)選擇某個(gè)時(shí)間點(diǎn)發(fā)送數(shù)據(jù)；時(shí)隙ALOHA算法是在純ALOHA算法的基礎(chǔ)上把時(shí)間長度劃分為離散的時(shí)隙間隔，隨機(jī)選擇某個(gè)時(shí)隙發(fā)送數(shù)據(jù)；幀時(shí)隙ALOHA算法是把離散化的某幾個(gè)時(shí)隙組合成一幀，進(jìn)而改進(jìn)為本文中動(dòng)態(tài)的改進(jìn)幀長度算法，即動(dòng)態(tài)幀時(shí)隙ALOHA算法。

2 改進(jìn)方法

2.1 估計(jì)標(biāo)簽數(shù)

動(dòng)態(tài)幀時(shí)隙ALOHA算法是根據(jù)標(biāo)簽數(shù)目變化動(dòng)態(tài)地改變幀長數(shù)目的大小，而本文根據(jù)已有動(dòng)態(tài)幀時(shí)隙ALOHA算法研究[5?6]成果進(jìn)行改進(jìn)。通過仿真分析上一幀讀寫器的識(shí)別情況，動(dòng)態(tài)地調(diào)整下一幀所需的時(shí)隙數(shù)。統(tǒng)計(jì)出每一幀所需的最佳時(shí)隙數(shù)，建立專家?guī)?，進(jìn)行全局搜索匹配，準(zhǔn)確地設(shè)定時(shí)隙數(shù)目，縮短識(shí)別匹配時(shí)間。

假設(shè)動(dòng)態(tài)幀時(shí)隙ALOHA算法中幀時(shí)隙數(shù)和標(biāo)簽的數(shù)目分別為[s]和[n]，其中一個(gè)標(biāo)簽占用某個(gè)時(shí)隙的概率服從二項(xiàng)分布。在時(shí)隙數(shù)范圍內(nèi)，標(biāo)簽選擇占用某個(gè)時(shí)隙的概率相等，[m]個(gè)標(biāo)簽選擇同一個(gè)時(shí)隙的概率為：

經(jīng)過一輪識(shí)別后，統(tǒng)計(jì)出成功識(shí)別的時(shí)隙數(shù)、碰撞時(shí)隙數(shù)和空閑時(shí)隙數(shù)的數(shù)目分別為[Ns]，[Nc]和[Nf]。其中發(fā)生碰撞的概率為[Nfs]。由式（5）可得：

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

基本步驟如下：

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

2） 設(shè)[H0=I]，[k=0]，計(jì)算出目標(biāo)函數(shù)在[nk]處的梯度[gk=?f（nk）]，若[gk≤ε]，計(jì)算終止；否則轉(zhuǎn)步驟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）≤ε]，計(jì)算終止；否則轉(zhuǎn)步驟6）；

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

7） 令[k=k+1]，轉(zhuǎn)步驟3）。

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

2.2 算法流程改進(jìn)

標(biāo)簽識(shí)別時(shí)，每次完全識(shí)別都會(huì)耗費(fèi)大量時(shí)間，造成整個(gè)系統(tǒng)總的識(shí)別時(shí)間較長。故在上述基礎(chǔ)上通過構(gòu)建專家?guī)斓乃枷耄蛇M(jìn)行全局匹配，即不同時(shí)隙數(shù)與對應(yīng)標(biāo)簽數(shù)進(jìn)行匹配。這樣可以大大縮短因匹配不佳或者不符合而耗費(fèi)時(shí)間，提高整個(gè)系統(tǒng)的識(shí)別時(shí)間。改進(jìn)算法流程如圖2所示。

讀寫器首先發(fā)送請求命令，等待標(biāo)簽響應(yīng)回復(fù)，并初始化空閑時(shí)隙計(jì)數(shù)器[Nf]、碰撞時(shí)隙計(jì)數(shù)器[Nc]和成功識(shí)別時(shí)隙計(jì)數(shù)器[Ns]為0，以及幀長數(shù)[9][L=2Q（Q=1，2，8）]。此時(shí)經(jīng)過一輪識(shí)別后，判斷時(shí)隙可響應(yīng)狀態(tài)為空閑、碰撞或成功，對于成功識(shí)別或者發(fā)生碰撞的時(shí)隙計(jì)數(shù)器加1，同時(shí)幀長數(shù)減1。數(shù)次循環(huán)后，判斷幀長數(shù)是否為零；若幀長數(shù)不為零，調(diào)整標(biāo)簽應(yīng)答命令；若為零，此時(shí)判斷碰撞時(shí)隙計(jì)數(shù)器[Nc]是否為零，若為零，識(shí)別結(jié)束，否則通過查詢專家?guī)煺{(diào)整幀長數(shù)，循環(huán)上述過程，直至標(biāo)簽完全識(shí)別。

上述識(shí)別過程中假定標(biāo)簽數(shù)小于256，而在實(shí)際應(yīng)用場合中標(biāo)簽數(shù)目遠(yuǎn)大于256。當(dāng)標(biāo)簽數(shù)大于256時(shí)，求解出不同時(shí)隙數(shù)所對應(yīng)的標(biāo)簽數(shù)時(shí)計(jì)算復(fù)雜度會(huì)增加，同時(shí)，識(shí)別大量標(biāo)簽時(shí)，整個(gè)系統(tǒng)的功率損耗也會(huì)增加，識(shí)別時(shí)間也會(huì)變長。此時(shí)，就需要對標(biāo)簽數(shù)進(jìn)行分組處理。表1為標(biāo)簽分組處理原則[10]。

3 仿真結(jié)果與分析

通過對動(dòng)態(tài)幀時(shí)隙ALOHA算法中幀長度進(jìn)行改進(jìn)，提出一種操作性強(qiáng)、經(jīng)濟(jì)成本低的方法。但在實(shí)際應(yīng)用中首先考慮標(biāo)簽的數(shù)目，在最優(yōu)標(biāo)簽數(shù)的情況下建立專家?guī)?。然后直接依?jù)專家?guī)煸O(shè)定不同時(shí)隙數(shù)下可識(shí)別的標(biāo)簽數(shù)，這樣可大大縮短系統(tǒng)識(shí)別時(shí)間，有效提高系統(tǒng)識(shí)別效率。

本文中選取100個(gè)標(biāo)簽，分別對固定幀時(shí)隙算法和改進(jìn)算法進(jìn)行Matlab實(shí)驗(yàn)仿真。固定幀時(shí)隙算法中幀長數(shù)目是固定的，無法改變。由于改進(jìn)算法能動(dòng)態(tài)的反應(yīng)時(shí)隙數(shù)的變化情況，從而動(dòng)態(tài)地設(shè)定標(biāo)簽數(shù)，使得讀寫器周圍存在的標(biāo)簽可以完全被成功識(shí)別。

圖3中的兩種算法分別是固定幀時(shí)隙算法和改進(jìn)后的動(dòng)態(tài)幀時(shí)隙算法。前者的幀長數(shù)目是固定的，通過大量的Matlab實(shí)驗(yàn)仿真發(fā)現(xiàn)，當(dāng)幀長數(shù)為64時(shí)系統(tǒng)的識(shí)別性能最高。識(shí)別100個(gè)標(biāo)簽大約需要370個(gè)時(shí)隙，即平均每3.7個(gè)時(shí)隙識(shí)別一個(gè)標(biāo)簽。對于改進(jìn)算法，識(shí)別100個(gè)標(biāo)簽大約需要300個(gè)時(shí)隙，平均每3個(gè)時(shí)隙成功識(shí)別一個(gè)標(biāo)簽，相比固定幀時(shí)隙算法識(shí)別效率有所提高。

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

4 結(jié) 論

本文在動(dòng)態(tài)幀時(shí)隙ALOHA算法的基礎(chǔ)上，利用數(shù)學(xué)思想提出一種改進(jìn)幀長度的方法。改進(jìn)算法的核心在于建立專家?guī)爝M(jìn)行全局搜索，動(dòng)態(tài)地依據(jù)專家?guī)煸O(shè)定不同時(shí)隙數(shù)下所對應(yīng)匹配的標(biāo)簽數(shù)，相比固定幀時(shí)隙ALOHA算法，提高了系統(tǒng)平均數(shù)據(jù)交換量并縮短系統(tǒng)識(shí)別時(shí)間。因此，本文改進(jìn)的方法有效提高了標(biāo)簽識(shí)別效率。

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

參考文獻(xiàn)

[1] 王飛，張武.基于分組的動(dòng)態(tài)時(shí)隙ALOHA算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，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] 馬翠紅，趙躍，楊友良，等.一種改進(jìn)的RFID防碰撞時(shí)隙ALOHA算法[J].河北聯(lián)合大學(xué)學(xué)報(bào)（自然科學(xué)版），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中基于分組動(dòng)態(tài)A?LOHA防碰撞算法的研究[J].電子測量技術(shù)，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] 張小紅，胡應(yīng)夢.分組自適應(yīng)分配時(shí)隙的RFID防碰撞算法研究[J].電子學(xué)報(bào)，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] 陳平華，王康順，李超，等.基于線性回歸的動(dòng)態(tài)幀時(shí)隙ALOHA算法[J].計(jì)算機(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] 管小衛(wèi)，傅偉，蔣道霞.一種改進(jìn)的分組幀時(shí)隙ALOHA算法[J].制造業(yè)自動(dòng)化，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] 馬琰，蔡麗霞，任曉娜.一種自適應(yīng)幀長RFID標(biāo)簽防碰撞算法[J].計(jì)算機(jī)與現(xiàn)代化學(xué)，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算法的幀長度調(diào)整方法[J].計(jì)算機(jī)工程與應(yīng)用，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系統(tǒng)中的幀長度調(diào)整方法[J].微計(jì)算機(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] 李晶.一種改進(jìn)的RFID防碰撞時(shí)隙ALOHA算法[D].長春：吉林大學(xué)，2009.

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