[發明專利]一種基于弦截迭代的射頻識別標簽防碰撞方法

有效

• 申請號: 201611208480.6
• 申請日: 2016-12-23
• 公開（公告）號: CN106599751B
• 公開（公告）日: 2019-11-29
• 發明（設計）人: 王祖良
• 申請（專利權）人: 西京學院
• 主分類號: G06K7/10
• 分類號: G06K7/10
• 代理公司: 61202 西安西達專利代理有限責任公司
• 代理人: 高亦哲<國際申請>=<國際公布>=<進入

1.一種基于弦截迭代的射頻識別標簽防碰撞方法，其特征在于，包括以下步驟：

假設閱讀器覆蓋范圍內有n個標簽，識別過程由閱讀器控制，首先由閱讀器發起查詢命令Query(Q)，該命令攜帶幀時隙參數Q，即本識別幀包含Q個時隙，收到命令后每個標簽隨機產生一個不大于Q的整數S_i，其中，參數i＝1,2…n，表示期望在第S_i時隙響應閱讀器；

隨后閱讀器發送識讀命令Read，標簽收到Read命令后,將自己的時隙號S_i 減1，如果結果為0則在本時隙響應閱讀器，照此方法發送Q次Read命令，完成第一幀全部Q個時隙的識讀；

對閱讀器而言，初始標簽數n預先并不知道，為了提高整個識別周期全局吞吐量性能，需要對n進行估計，在已知第一幀成功識別標簽數N_s的基礎上，利用弦截法估計初始標簽數在此基礎上將第二幀幀長度設置為實現最優識別效率，后續幀采用類似處理，直至完成所有標簽識別；

所述的初始標簽數估計步驟如下：

假設第一幀幀長度為Q,待識別標簽數為n,每個標簽產生隨機數S_i＝m，并且m小于Q，其概率為P＝1/Q,r個標簽占用一個時隙的概率P(Q,n,r)為：

很明顯，按照r等于1，等于0，或者大于1三種情況可以分別得出有效時隙，空時隙，或者碰撞時隙的概率，當r＝1時的有效時隙的概率為：

所示一幀內的有效時隙期望值為：

式(3)左邊為有效識別標簽的期望值，第一幀識別完成后可以用實際有效值代替，通過解方程求解n的估計式(3)為超越方程，采用弦截迭代法求解；完成第一幀識別后可以獲得有效識別標簽數N_s的值，在式(3)中令E[P(Q,n,1)]＝N_s，并令：

令式(4)等于0解方程，可以得到方程的根x,取整即可得到待識別標簽數的估計值

弦截法是利用在(ξ,f(ξ))處的切線代替曲線y＝f(x),這里ξ是方程的根，假設初始估計根為x₀和x₁，則切線方程為：

g(x)＝ax+b (5)

滿足條件g(x₀)＝f(x₀),g(x₁)＝f(x₁)

這條直線稱為弦截線，可以通過下式獲得

令g(x)＝0,解方程的根為x₂，則

重復此步驟,利用x₁和x₂產生新的弦截線,并用其根近似ξ，這樣就可以產生一般迭代公式

開始啟動迭代之前，需要確定三個參數x₀,x₁,和N，N為最大迭代次數；

假設ε為誤差容限,則迭代終止準則為|f(x_n+1)|≤ε,|x_n+1-x_n|≤ε,或者迭代次數大于等于N；

初始標簽估計方法，必然會產生偽解，需要加以剔除，剔除偽解具體過程如下：

對(4)求一階導數得

在實際應用中Q>>1，所以(1-1/Q)^x-1＞0，用泰勒級數將(9)展開得

令(10)等于0求得極值點x_opt≈Q，即當待識別標簽數大約等于Q時識別效率最大，理論上，實際有效識別標簽數N_s不大于最優成功時隙數的期望值當時，方程(4)有唯一解；由(10)可以看出，當x<Q時，f'(x)＞0，(4)單調遞增；當x>Q時，f'(x)＜0，(4)單調遞減，所以當時方程(4)有兩個解，分別位于x_opt的兩側，必然有一個是偽解，需要將其剔除；用弦截迭代法求解(4)需要設置兩個初始值x₀和x₁，由于Q是已知的，對于存在雙解的情況，通過初始值的設置可以控制解的位置；設置x₀和x₁均小于Q，則迭代產生的解x_l即小于x_opt，反之設置x₀和x₁均大于Q，則迭代產生的解x_u即大于x_opt；令為最接近x_l的整數，即為最接近x_u的整數，即閱讀器分別以和為參數，發送兩個試探命令QueryT(Q)，分別進行兩個試探幀的識別，并統計對應的有效識別標簽數，分別為N_sl和N_su，在試探階段成功識別的標簽并不進入靜默狀態，只是用來統計有效識別標簽數；根據識別效率判斷，如果N_sl/(round(x_l)-N_s)>＝N_su/(round(x_u)-N_s)，則否則剔除偽解之后即可進行后續幀的識別，直到完成所有標簽識別，結束本識別周期；

其中，利用實數x代替式(3)中的整數n，求出方程的實數解以后對實數x取整作為n的估計值假設N為弦截迭代法解超越方程最大迭代次數，x₀、x₁為初始估計根，count為迭代次數計數器，f(x₀)、f(x₁)為對應x₀、x₁的函數值，為了簡化書寫，在算法步驟中用y₀、y₁代替f(x₀)、f(x₁)，ε為誤差容限。