RFID防碰撞算法設(shè)計(jì)與實(shí)現(xiàn)教師：xxxx2025/01/01CONTENTS01碰撞危機(jī)：RFID為何頻發(fā)沖突02四大多路策略：空分頻分碼分時分03ALOHA家族：非確定型概率算法04二進(jìn)制樹：確定型精準(zhǔn)識別05查詢樹算法：前綴堆棧遍歷06MATLAB仿真：幀時隙ALOHA實(shí)戰(zhàn)碰撞危機(jī)：RFID為何頻發(fā)沖突01RFID系統(tǒng)兩大碰撞場景拆解多讀寫器碰撞定義在RFID系統(tǒng)中，當(dāng)多個讀寫器同時掃描同一區(qū)域內(nèi)的標(biāo)簽時，讀寫器之間會產(chǎn)生干擾和沖突，導(dǎo)致一些標(biāo)簽無法被讀取或被多個讀寫器同時讀取，這種情況稱為‘多重訪問干擾’。多標(biāo)簽碰撞定義當(dāng)多個RFID標(biāo)簽同時處于閱讀器的覆蓋范圍內(nèi)時，標(biāo)簽之間會發(fā)生干擾和沖突，導(dǎo)致閱讀器無法同時讀取所有標(biāo)簽的數(shù)據(jù)，或者讀取的數(shù)據(jù)出現(xiàn)錯誤，這種情況稱為‘多重標(biāo)簽干擾’。碰撞后果碰撞會導(dǎo)致標(biāo)簽漏讀、讀取速率驟降，嚴(yán)重影響RFID系統(tǒng)的效率和準(zhǔn)確性。因此，研究防碰撞算法至關(guān)重要，以提高系統(tǒng)的吞吐率和信道利用率。多讀寫器碰撞機(jī)理與干擾模型多讀寫器碰撞模型利用圖6-1展示，當(dāng)三讀寫器覆蓋三標(biāo)簽正常時，重疊區(qū)標(biāo)簽4同時收到兩路載波，相位差引發(fā)數(shù)據(jù)混疊，導(dǎo)致讀寫器無法正確解析標(biāo)簽數(shù)據(jù)。影響因素多讀寫器碰撞的程度取決于讀寫器的功率、天線增益、頻率和距離等因素。即使是小功率差異，也可能導(dǎo)致標(biāo)簽解調(diào)失敗。多讀寫器碰撞機(jī)理與干擾模型圖6-1多讀寫器碰撞多讀寫器碰撞是指當(dāng)多個讀寫器同時掃描同一區(qū)域內(nèi)的標(biāo)簽時，這些讀寫器之間會產(chǎn)生干擾和沖突，從而導(dǎo)致一些標(biāo)簽無法被讀取或者被多個讀寫器同時讀取的情況，這種情況也稱為“多重訪問干擾”。多標(biāo)簽碰撞的電磁疊加原理電磁疊加示例以圖6-2為例，三標(biāo)簽同時回波，基帶幀在接收機(jī)前端疊加成非解析波形，導(dǎo)致閱讀器無法正確解析數(shù)據(jù)。碰撞強(qiáng)度碰撞強(qiáng)度隨標(biāo)簽數(shù)量、響應(yīng)速率、場強(qiáng)呈指數(shù)上升，這為算法效率評估提供了量化需求。多標(biāo)簽碰撞的電磁疊加原理在RFID系統(tǒng)中，多標(biāo)簽碰撞是指當(dāng)多個RFID標(biāo)簽同時處于RFID閱讀器的覆蓋范圍內(nèi)時，這些標(biāo)簽之間會發(fā)生干擾和沖突，從而導(dǎo)致閱讀器無法同時讀取所有標(biāo)簽的數(shù)據(jù)，或者讀取的數(shù)據(jù)出現(xiàn)錯誤，這種情況也稱為“多重標(biāo)簽干擾”。圖6-2多標(biāo)簽碰撞四大多路策略：空分頻分碼分時分02空分多路：用空間隔離同時讀取天線陣列分區(qū)把讀寫區(qū)切成蜂窩格，各讀寫器獨(dú)管一格，硬件成本高，但可徹底避免同頻干擾。相控波束利用相控陣實(shí)時指向標(biāo)簽，通過RSSI區(qū)分，適合高端場景，但部署費(fèi)用與施工復(fù)雜度較高?？辗侄嗦罚河每臻g隔離同時讀取空分多路法采用空間分離特性的天線技術(shù)實(shí)現(xiàn)標(biāo)簽的信息讀取，即在分離的空間范圍內(nèi)實(shí)現(xiàn)多個目標(biāo)識別。主要分為兩種實(shí)現(xiàn)方法。一種是按照空間區(qū)域規(guī)則劃分天線的覆蓋范圍，如圖6-3所示圖6-3空分多路法劃分天線的覆蓋范圍頻分多路：每標(biāo)簽獨(dú)占載波信道01頻分模型圖6-4展示四標(biāo)簽各用不同上行頻點(diǎn)，疊加后互不干擾，但需為每信道配獨(dú)立接收機(jī)，成本隨標(biāo)簽規(guī)模線性增加。02適用場景頻分在無線監(jiān)測、航空行李等特許頻段可行，但對普通UHFRFID并不經(jīng)濟(jì)。頻分多路：每標(biāo)簽獨(dú)占載波信道頻分多路法將傳輸通道劃分為若干條信道，同時為每條信道分配不同的載波頻率后分別提供給標(biāo)簽使用，以此實(shí)現(xiàn)不同信道的標(biāo)簽可以同時與讀寫器傳輸數(shù)據(jù)，其模型如圖6-4所示。圖6-4頻分多路法模型碼分多路：擴(kuò)頻地址碼區(qū)分標(biāo)簽擴(kuò)頻與多址發(fā)端用高速偽隨機(jī)碼展寬信號，收端用相同碼解擴(kuò)，每標(biāo)簽分配唯一地址碼，實(shí)現(xiàn)同頻同時回傳。優(yōu)缺點(diǎn)碼分多路具有抗干擾與保密優(yōu)勢，但標(biāo)簽需集成相關(guān)器，功耗與芯片面積翻倍，容量受限于可用碼組數(shù)量。時分多路：把時間切片輪流傳輸時分多路特點(diǎn)將信道按時間軸劃分為時隙，標(biāo)簽被調(diào)度到不同時隙回傳，徹底避免波形疊加。時分可軟件實(shí)現(xiàn)、無需額外射頻硬件，因此成為RFID防碰撞算法的主流選擇。ALOHA家族：非確定型概率算法03純ALOHA：隨機(jī)發(fā)言遇撞再退避01純ALOHA模型圖6-6示意三標(biāo)簽任意時刻發(fā)送，碰撞周期為2T。02吞吐率計(jì)算在泊松過程假設(shè)下，吞吐率η=Ge^{-2G}，在G=0.5時取得極限18.4%。03優(yōu)缺點(diǎn)純ALOHA優(yōu)點(diǎn)為無需同步、實(shí)現(xiàn)極簡，缺點(diǎn)是效率低且存在饑餓，適用于標(biāo)簽少于10的小規(guī)模場景。純ALOHA：隨機(jī)發(fā)言遇撞再退避純ALOHA算法（PureALOHA,PA）是時分多路里一種典型的防碰撞算法，運(yùn)用沖突監(jiān)聽和隨機(jī)避讓策略使得各標(biāo)簽?zāi)軌蛟陔S機(jī)時刻發(fā)送信號。其算法的工作原理是基于“標(biāo)簽先發(fā)言機(jī)制”的方法，也就是說標(biāo)簽進(jìn)入讀寫器產(chǎn)生的磁場區(qū)域后，通過天線接收到電磁波而被激活，激活后的標(biāo)簽主動向讀寫器發(fā)送消息，這個主動發(fā)送不受時間的先后限制。純ALOHA：隨機(jī)發(fā)言遇撞再退避如下圖6-6所示為純ALOHA算法的碰撞原理圖。讀寫器識別范圍內(nèi)有三個標(biāo)簽，當(dāng)標(biāo)簽2和標(biāo)簽3發(fā)生碰撞后，讀寫器命令他們隨機(jī)延遲一段時間后再發(fā)送消息，直到讀寫器檢測出只有一個標(biāo)簽1與其通信，則成功識別出該標(biāo)簽。在這過程中，有沒有發(fā)生碰撞而成功識別，也有在信道中出現(xiàn)部分或完全碰撞后而無法成功識別，這時各標(biāo)簽會隨機(jī)等待一定時長并繼續(xù)傳輸數(shù)據(jù)包，直至讀寫器成功接收完整數(shù)據(jù)包。圖6-6

純ALOHA算法碰撞模型時隙ALOHA：同步時隙削半碰撞窗時隙ALOHA原理引入讀寫器廣播時鐘，標(biāo)簽只能在時隙起點(diǎn)發(fā)送，碰撞周期縮至T。性能提升吞吐率η=Ge^{-G}，極限36.8%，是純ALOHA的兩倍，被EPCGen2標(biāo)準(zhǔn)采納為基準(zhǔn)模式。時隙ALOHA：同步時隙削半碰撞窗SA的原理表現(xiàn)為時隙ALOHA要求所有用戶（在RFID系統(tǒng)中為標(biāo)簽）在每個時間片的開始時刻發(fā)送數(shù)據(jù)，如果在同一時間片內(nèi)有多個用戶嘗試發(fā)送，則會發(fā)生碰撞，用戶必須等待下一個時間片再嘗試。這種機(jī)制減少了數(shù)據(jù)沖突的可能性，使得信道利用率得到提高。時隙ALOHA：同步時隙削半碰撞窗當(dāng)標(biāo)簽進(jìn)入讀寫器的識別范圍后，標(biāo)簽自身攜帶的隨機(jī)數(shù)發(fā)生器產(chǎn)生一隨機(jī)數(shù)，標(biāo)簽按此隨機(jī)數(shù)選擇時隙，若查詢時的時隙數(shù)與標(biāo)簽選擇的時隙相匹配時標(biāo)簽即響應(yīng)，并立即發(fā)送自身的數(shù)據(jù)信息；若時隙內(nèi)有碰撞時，讀寫器將終止標(biāo)簽繼續(xù)發(fā)送信息并令標(biāo)簽等待下一次查詢。在SA算法中，標(biāo)簽只能選擇在每個時隙的開始階段發(fā)送數(shù)據(jù)，而不是隨機(jī)的選擇時間發(fā)送數(shù)據(jù)，所以需要一個同步機(jī)制來控制標(biāo)簽，這個同步時鐘的控制由讀寫器來完成，并且每個時隙的長度要滿足標(biāo)簽成功傳輸完一數(shù)據(jù)包所需的時間。圖6-8

時隙ALOHA算法碰撞模型幀時隙ALOHA：幀長動態(tài)逼近標(biāo)簽數(shù)幀時隙ALOHA模型圖6-10模型把N時隙打包成幀，標(biāo)簽每幀只選一時隙回傳。吞吐率公式吞吐率公式η=(n/L)(1-1/L)^{n-1}，當(dāng)L≈n時效率最高。讀寫器可通過觀察上一幀空/忙比例，動態(tài)調(diào)整L。幀時隙ALOHA：幀長動態(tài)逼近標(biāo)簽數(shù)FAS算法采用了以下策略，將多個時隙組織成一個幀，其中幀長代表了該幀內(nèi)所包含的時隙數(shù)量。閱讀器會將幀長信息傳遞給識別范圍中的標(biāo)簽。在收到幀長信息后，標(biāo)簽會在該幀內(nèi)隨機(jī)選擇一個時隙進(jìn)行響應(yīng)。在這一過程中，如果信息發(fā)生沖突，那么本幀內(nèi)涉及到?jīng)_突的標(biāo)簽將暫停操作，等待下一幀的開始時再次執(zhí)行上述策略。這樣的設(shè)計(jì)有助于減少時隙浪費(fèi)，提高識別和通信的準(zhǔn)確性和效率。FSA算法的碰撞模型如圖6-10所示。圖6-10FSA算法的碰撞模型ALOHA類算法饑餓問題與公平性饑餓問題持續(xù)高負(fù)載下部分標(biāo)簽長期選不到獨(dú)占時隙，導(dǎo)致‘標(biāo)簽饑餓’。公平性解決方案采用指數(shù)退避+隨機(jī)重試的緩解方案，確定性算法能根本解決公平性問題。二進(jìn)制樹：確定型精準(zhǔn)識別04二叉分裂思想與曼徹斯特碰撞位二叉分裂原理讀寫器利用曼徹斯特編碼過零點(diǎn)檢測，可直接定位ID碰撞位。把碰撞最高位置0，其余低位置1，形成新查詢前綴，從而把標(biāo)簽群一分為二。優(yōu)點(diǎn)無需標(biāo)簽隨機(jī)數(shù)，只要ID唯一即可保證收斂，適用于對識別順序有嚴(yán)格要求的場景。二進(jìn)制搜索樹流程八步拆解初始Query廣播全1初始Query，所有標(biāo)簽響應(yīng)。檢測碰撞接收并檢測碰撞，生成新前綴。分裂與Silence若無碰撞則Select+Silence，否則繼續(xù)分裂。循環(huán)搜索回跳繼續(xù)搜索，直到堆?？?，每次分裂至少識別一張標(biāo)簽。二進(jìn)制搜索樹流程八步拆解循環(huán)搜索回跳繼續(xù)搜索，直到堆棧空，每次分裂至少識別一張標(biāo)簽。二進(jìn)制搜索樹算法（BinarySearchTree,BST）的核心思想在于利用曼徹斯特碼檢測到的碰撞位，找尋最高碰撞位置（設(shè)為0）并作為劃分界限。在此基礎(chǔ)上，保持高位不變，將低位全設(shè)為1，從而生成新的身份標(biāo)識（Identitydocument，ID）。隨后，該算法將標(biāo)簽ID與查詢指令中的ID進(jìn)行對照，然后進(jìn)行細(xì)分標(biāo)簽，直到達(dá)到最小單元。將持續(xù)執(zhí)行這一過程，直到閱讀器成功識別區(qū)域內(nèi)的所有標(biāo)簽。BST吞吐率與標(biāo)簽規(guī)模關(guān)系吞吐率公式識別n標(biāo)簽所需平均查詢次數(shù)M=log2(n!)+n，吞吐率η=n/M。性能表現(xiàn)圖6-16顯示n=5時η≈0.42，n=150降至0.15。BST在標(biāo)簽<20時效率優(yōu)于ALOHA，但隨規(guī)模增大開銷顯著。動態(tài)BST：ID長度壓縮與跳躍搜索01優(yōu)化策略一是只傳輸碰撞位以上部分，降低空中比特；二是跳躍式查詢，跳過已知全0子樹。02性能提升可把查詢次數(shù)降至約0.7nlog2n，吞吐率提升20%以上，適用于ID長度>96的超高頻場景。查詢樹算法：前綴堆棧遍歷05QueryTree原理：前綴匹配+堆棧驅(qū)動算法原理QT無需標(biāo)簽隨機(jī)數(shù)，也不在標(biāo)簽端維護(hù)狀態(tài)；讀寫器內(nèi)部維護(hù)查詢前綴堆棧，初始為空。每輪彈出前綴發(fā)Request，標(biāo)簽ID前綴匹配即回送剩余位。碰撞處理若碰撞則在當(dāng)前前綴后追加0、1再壓棧，形成二叉遍歷。算法簡潔，標(biāo)簽功耗極低。QT識別流程四階段示例初始階段發(fā)NULL得全體碰撞。壓棧階段壓入0、1。查詢階段先查0分支再查1分支。識別階段若無碰撞則SELECT+UNSELECT使標(biāo)簽休眠。QT與BST復(fù)雜度對比復(fù)雜度公式QT平均查詢次數(shù)M≈2.88N-1，η穩(wěn)定0.35；BST在N>7后η持續(xù)下降。適用場景QT適合標(biāo)簽ID較長、數(shù)量中等且對公平性要求高的物流盤點(diǎn)；BST適合標(biāo)簽較少、ID短的倉儲抽屜管理。查詢樹改進(jìn)：混合切割與索引壓縮改進(jìn)策略一是結(jié)合碰撞位索引，跳過全空子樹；二是對連續(xù)相同前綴做游程壓縮，減少Request比特。性能提升仿真顯示在256標(biāo)簽、128位ID場景下，查詢次數(shù)可降至1.6N，吞吐率提升至0.45。MATLAB仿真：幀時隙ALOHA實(shí)戰(zhàn)06FSA仿真目標(biāo)與場景設(shè)定仿真目標(biāo)用MATLAB驗(yàn)證5標(biāo)簽、5時隙單幀下的碰撞、重傳過程。預(yù)期結(jié)果通過方波可視化看到時隙占用、碰撞位置及再分配，幫助學(xué)生直觀理解‘碰撞→等待→重選時隙’循環(huán)。FSA仿真目標(biāo)與場景設(shè)定

圖6-185個標(biāo)簽在一幀內(nèi)發(fā)送情況隨機(jī)時隙分配代碼邏輯逐行解讀隨機(jī)數(shù)生成randperm生成1-5不重復(fù)排列，floor/N得0-1發(fā)送指示。方波擴(kuò)展K點(diǎn)擴(kuò)展成方波便于plot，隨機(jī)種子可重復(fù)實(shí)驗(yàn)。代碼功能代碼實(shí)現(xiàn)隨機(jī)時隙分配，為后續(xù)碰撞檢測和重傳提供基礎(chǔ)數(shù)據(jù)。碰撞檢測與沖突標(biāo)簽提取算法碰撞檢測邏輯按列掃描時隙，記錄同一時隙內(nèi)多標(biāo)簽置1的索引，形成沖突數(shù)組Rdx。算法功能該數(shù)組長度即下幀需回傳的標(biāo)簽數(shù)，為動態(tài)幀長提供輸入。多幀重傳過程可視化結(jié)果結(jié)果展示圖6-19、6-20展示第二幀、第三幀波形：第二幀3標(biāo)簽仍碰撞，第三幀成功。性能表現(xiàn)隨著幀數(shù)增加，碰撞概率指數(shù)下降，符合FSA理論1/e收斂速度。參數(shù)擴(kuò)展實(shí)驗(yàn)：幀長與標(biāo)簽數(shù)匹配01擴(kuò)展任務(wù)保持n=40，把L從20調(diào)到80，觀察總時隙消耗曲線出現(xiàn)V型谷底。02實(shí)驗(yàn)意義驗(yàn)證L≈n最優(yōu)，通過仿真學(xué)生可親手復(fù)現(xiàn)圖6-11理論曲線，實(shí)現(xiàn)‘理論-仿真-結(jié)論’閉環(huán)。MATLAB仿真：二進(jìn)制搜索樹實(shí)戰(zhàn)07BST仿真目標(biāo)與ID設(shè)定仿真目標(biāo)4個8位ID標(biāo)簽A~D，走讀完整二叉分裂流程，輸出讀寫器與標(biāo)簽交互順序。預(yù)期結(jié)果通過打印RS數(shù)組，讓學(xué)生看到‘碰撞→分裂→孤立→Silence’全過程，加深對確定型算法無饑餓特性的理解。BST仿真目標(biāo)與ID設(shè)定二進(jìn)制搜索樹算法屬于確定性算法防碰撞算法，其核心思想在于利用曼徹斯特碼檢測到的碰撞位，找尋最高碰撞位置（設(shè)為0）并作為劃分界限。現(xiàn)有4個標(biāo)簽，每個標(biāo)簽的ID長度為8位，分別為A（1010111）、B（10110101）、C（10101111）以及D（10111101）。第一步，讀寫器向其識別范圍內(nèi)的標(biāo)簽發(fā)送查詢指令R(11111111)；第二步，讀寫器對收到的標(biāo)簽進(jìn)行響應(yīng)，如出現(xiàn)不一致的情況（即有的序列號位為0，有的序列號該位為1），則判斷有碰撞，如圖6-21所示；第三步，確定有碰撞后，把不一致位數(shù)的最高位置0后再輸出查詢條件Q，依次排除序列號大于Q的標(biāo)簽。從圖6-1