防碰撞算法Q值算法及其改進算法

DFSA算法可采用各種方法預(yù)測待識別的標簽數(shù)量，然后動態(tài)調(diào)整最優(yōu)幀長，與FSA相比，系統(tǒng)效率有明顯改善，接近36．8%。但是，當標簽數(shù)量較多（特別是標簽數(shù)量大于500）時，采用由預(yù)測標簽數(shù)量設(shè)置最優(yōu)幀長的方案會使系統(tǒng)效率急劇下降。因此，在標簽數(shù)量較多的情況下，為了使系統(tǒng)效率得到提高，EPCClass1Gen2標準中采用了Q值算法，該算法可以實時自適應(yīng)地調(diào)整幀長 。

Q值算法

在Q值算法中，閱讀器首先發(fā)送Query命令，該命令中含有一個參數(shù)Q（取值范圍0～15），接收到命令的標簽可在[0，2Q－1]范圍內(nèi)（稱為幀長）隨機選擇時隙，并將選擇的值存入標簽的時隙計數(shù)器中，只有計數(shù)器為0的標簽才能響應(yīng)，其余標簽保持沉默狀態(tài)。當標簽接收到閱讀器發(fā)送的QueryRep命令時，將其時隙計數(shù)器減1，若減為0，則給閱讀器發(fā)送一個應(yīng)答信號。標簽被成功識別后，退出這輪盤存。當有兩個以上標簽的計數(shù)器都為0時，它們會同時對閱讀器進行應(yīng)答，造成碰撞。閱讀器檢測到碰撞后，發(fā)出指令將產(chǎn)生碰撞的標簽時隙計數(shù)器設(shè)為最大值（2Q－1），繼續(xù)留在這一輪盤存周期中，系統(tǒng)繼續(xù)盤存直到所有標簽都被查詢過，然后閱讀器發(fā)送重置命令，使碰撞過的標簽生成新的隨機數(shù) 。

根據(jù)上一輪識別的情況，閱讀器發(fā)送Query－Adjust命令來調(diào)整Q的值，當標簽接收到Query－Adjust命令時，先更新Q值，然后在[0，2Q－1]范圍內(nèi)選擇隨機值。EPCClass1Gen2標準中提供了一種參考算法來確定Q值的范圍.其中：Qfp為浮點數(shù)，其初值一般設(shè)為4．0，對Qfp四舍五入取整后得到的值即為Q；C為調(diào)整步長，其典型取值范圍是0．1

該算法在參數(shù)C的輔助下對Q值進行動態(tài)調(diào)整，但是C太大會造成Q值變化過于頻繁，導(dǎo)致幀長調(diào)整過于頻繁，C太小又不能快速地實現(xiàn)最優(yōu)幀長的選擇。因此，研究者們對Q值的調(diào)整進行了各種優(yōu)化 。

基于最大吞吐量調(diào)整Q值的算法

文獻提出一種基于最大吞吐量對Q值進行調(diào)整的算法，其中定義了以下變量：Nt為已識別的標簽個數(shù)；N為識別標簽所需的總時隙數(shù)；NC為沖突時隙的個數(shù)；nu為上一輪未識別的標簽個數(shù)；e為沖突時隙中的平均標簽個數(shù)；PC為沖突時隙所占的比例 。

這些參數(shù)之間的關(guān)系為PC=NC/N，e=nu/Nc，吞吐量=Nt/N。由于Aloha類算法的最大吞吐量為0．368（e－1）[5]，該算法以此作為調(diào)整Q值的依據(jù)。當系統(tǒng)吞吐量達到或接近0．368時，閱讀器僅需調(diào)用2Q－1次QueryRep命令，而不需要在接下來的盤存周期中調(diào)整Q值。當吞吐量小于0．368時，根據(jù)未識別的標簽個數(shù)nu來調(diào)整Q值 .

基于分組的位隙Aloha算法

文獻提出一種基于分組的位隙Aloha算法，該算法采用位隙Aloha算法中的128位預(yù)定序列，代表128個位隙。若某個標簽選擇了第i個位隙，則將第i位置1，其余各位都置0。當標簽數(shù)量為15時，位隙Aloha算法可獲得最大吞吐率88．38%，但隨著標簽數(shù)量的增加，算法性能急劇下降 。

因此，基于分組的位隙Aloha算法通過對標簽進行分組來提高算法的性能。該算法在查詢命令中設(shè)置了一個位隙計數(shù)器的參數(shù)Q（Q為整數(shù)，且0≤Q≤15），當標簽收到閱讀器發(fā)送的查詢命令后，在[0，2Q－1]范圍內(nèi)生成一個隨機數(shù)，即代表選擇了相應(yīng)的位隙，只有選擇了0的標簽才會立即響應(yīng)。同時，該算法根據(jù)沖突位隙數(shù)動態(tài)地對Q值進行調(diào)整：當沖突位隙數(shù)小于11時，Q減1且最小為0；當沖突位隙數(shù)在11～20之間時，Q保持不變；當沖突位隙數(shù)大于20時，Q加1且最大不超過15 。

綜上所述，基于Aloha的防碰撞算法原理簡單、容易實現(xiàn)，對新到達的標簽具有較好的適應(yīng)性，尤其對于標簽持續(xù)到達的情況有較好的解決方案，但該類算法存在幾個明顯的缺點：①響應(yīng)時間不確定，即同一批標簽在不同時刻進行識別所需要消耗的時間相差很大；②個別標簽可能永遠無法被識別；③Aloha算法達到最佳吞吐率的條件是其幀長等于標簽數(shù)量，當需要識別的標簽數(shù)量較多或選擇的幀長與實際待識別標簽數(shù)量不符時，系統(tǒng)性能將明顯下降。而基于樹的算法則很好地解決了這些問題 。

在固定幀長的Aloha算法中，當標簽數(shù)量太多時，沖突時隙較多；而當標簽數(shù)量太少時，又會有大量的空閑時隙?；谶@一點，各種改進算法被提出 。

分群時隙Aloha算法

分群時隙Aloha算法根據(jù)碰撞時隙在所分配時隙中所占的比例，來確定是否分群。如果碰撞時隙的比例（發(fā)生碰撞的時隙數(shù)/分配的時隙數(shù)）大于分群因子γ，則進行分群。分群后，第一個分群內(nèi)的標簽響應(yīng)閱讀器的查詢命令，另一個分群內(nèi)的標簽處于等待狀態(tài)。當?shù)谝粋€分群內(nèi)的所有標簽識別完畢后，第二個分群內(nèi)的標簽再進行響應(yīng)，直至所有標簽識別完畢 。

仿真結(jié)果表明，分群時隙Aloha算法優(yōu)于固定時隙Aloha算法，且隨著標簽數(shù)量的增加，算法的優(yōu)越性更明顯。同時，分群因子的選擇是影響算法的關(guān)鍵因素，在標簽數(shù)量較多時，分群因子宜選擇較小值 。

自適應(yīng)的動態(tài)幀時隙Aloha算法

文獻考慮某些應(yīng)用場合中閱讀器需要對標簽進行重復(fù)識別的要求，充分利用上一幀已識別標簽的信息，提出自適應(yīng)的動態(tài)幀時隙Aloha算法，該算法每成功識別一個標簽就給標簽分配一個時隙號，該時隙號規(guī)定了標簽被閱讀器識別的順序。如果在下次識別過程中閱讀器要重復(fù)識別這些標簽，則可根據(jù)已分配的時隙號按順序進行，從而避免標簽間的沖突，減少識別時間。當離去標簽和新到達標簽數(shù)量較少時，系統(tǒng)效率較高，但是當有大量的新到達標簽時，僅采用上述方法將導(dǎo)致沖突急劇增加。為減少沖突，閱讀器應(yīng)估計標簽數(shù)，并根據(jù)標簽數(shù)合理調(diào)整幀長。文獻提出了一種最優(yōu)幀長方案，使系統(tǒng)獲得了較大的吞吐量 。

對于SA算法，在發(fā)生碰撞時，標簽延遲的隨機性范圍很大，影響了其平均響應(yīng)速度。為此，規(guī)定若干個時隙為一幀，標簽選擇的隨機延遲必須是幀內(nèi)的某個時隙，這就是幀時隙Aloha（FramedSlottedAloha，F(xiàn)SA）算法 。

FSA算法的缺點是幀長固定，這樣當標簽數(shù)量較少時，存在時隙浪費，而當標簽數(shù)較多時，碰撞解決的效果又不是很好。因此，可以考慮根據(jù)標簽數(shù)量動態(tài)地調(diào)整幀長，即動態(tài)幀時隙Aloha（DynamicFramedSlottedAloha，DFSA）算法。研究結(jié)果表明，最優(yōu)的幀長應(yīng)該等于標簽數(shù)量，因此只要知道了標簽數(shù)量，就可以確定幀長，然而當前幀需識別的標簽數(shù)量通常無法預(yù)知，只能對其進行估算。因此在DFSA算法中，非常重要的一項工作就是標簽數(shù)量的估計，大多數(shù)方法都是根據(jù)上一幀的幀長、標簽個數(shù)、沖突情況來估計當前幀中的標簽數(shù) 。典型方法包括：

（1）Vogt方法設(shè)碰撞時隙數(shù)為Ck，碰撞時隙內(nèi)至少有2個以上的標簽存在，則可以預(yù)測發(fā)生碰撞的標簽數(shù)量至少為2×Ck 。

（2）標簽估計方法Ⅰ（TagEstimationMethodⅠ，TEMⅠ）將碰撞率Cratio定義為碰撞時隙數(shù)與幀長的比值，L為幀長，n為標簽個數(shù)，則它們之間的關(guān)系為Cratio=1－（1-1/L）(1 n/(L-1))（1）由于上一幀的幀長L和碰撞率Cratio已知，可以計算出標簽個數(shù)n 。

（3）TEMⅡ方法設(shè)nest為估算的標簽數(shù)量，Mcoll為上一幀中的碰撞時隙數(shù)，則nest=2．3922×Mcoll 。

基于Aloha的防碰撞算法的基本思想是：在閱讀器發(fā)現(xiàn)多標簽碰撞時，閱讀器命令其作用范圍內(nèi)的所有標簽隨機延遲一段時間再進行響應(yīng)，延遲時間的長度是以某種概率隨機選擇的 。

早期的Aloha算法為純Aloha算法，該算法采用“標簽先發(fā)言”的方式，即標簽一進入閱讀器的作用區(qū)域就自動向閱讀器發(fā)送其自身的信息，對同一個標簽來說，其發(fā)送數(shù)據(jù)的時間是隨機的。在標簽發(fā)送信息的過程中，如果有其他標簽也在發(fā)送數(shù)據(jù)，就會發(fā)生信號重疊，導(dǎo)致部分碰撞或者完全碰撞 。

閱讀器檢測信號并進行判斷，一旦發(fā)現(xiàn)碰撞，閱讀器將發(fā)送命令讓標簽停止發(fā)送數(shù)據(jù)，所有標簽會隨機延遲一段時間再發(fā)送數(shù)據(jù)，由于延遲的隨機時間不同，再次發(fā)生碰撞的概率將明顯降低。如果沒有碰撞，則閱讀器發(fā)送一個應(yīng)答信號給標簽，標簽從此轉(zhuǎn)入休眠狀態(tài)。這種算法簡單，但吞吐率低，最大吞吐率僅能達到18．4% 。

該算法效率低的主要原因是碰撞發(fā)生的時間是隨機的，其中包括：當一個標簽在與閱讀器通信的過程中，有可能因其他標簽的突然響應(yīng)而被破壞，即存在部分碰撞問題。為此，人們提出時隙Aloha算法（SlottedAloha，SA），把時間分成多個離散時隙，標簽只在每個時隙的開始時刻才能發(fā)送數(shù)據(jù)。算法的基本原理是：閱讀器通過發(fā)送命令通知標簽有多少時隙，標簽隨機選擇發(fā)送信息的時隙。如果某個時隙只有一個標簽響應(yīng)，則閱讀器可正確地識別標簽；如果某個時隙有多個標簽響應(yīng)，則會發(fā)生碰撞，閱讀器通知標簽，標簽便在下一輪循環(huán)中重新隨機選擇發(fā)送的時隙，直到所有的標簽都被識別出來。在SA算法中，標簽或成功識別或完全碰撞，避免了純Aloha算法中出現(xiàn)的部分碰撞問題。SA算法的最大吞吐率可達36．8% 。

在最簡單的情況下，設(shè)碰撞粒子間的作用力是球形對稱的，則單位立體角：

dΩ =2πsinθdθ

單位時間內(nèi)在偏轉(zhuǎn)角和 d之間散射的粒子數(shù)為：

dQ=I(θ)dΩ =2πI(θ)sinθdθ

對于一個給定速度的粒子束,散射到和 d（見圖）之間的分子數(shù)等于入射粒子束從寬度為d，面積為2πd的圓環(huán)中通過的分子數(shù)：

dQ=2πbdb=2πI(E,θ)sinθdθ

或

對于給定能量的粒子束，碰撞參數(shù)可有許多不同的數(shù)值，因而，微分碰撞截面的普遍表達式可寫作：

將全部立體角范圍對微分碰撞截面加和就得到總的彈性碰撞截面：

根據(jù)碰撞對相互作用的性質(zhì)，非彈性碰撞和反應(yīng)碰撞也有類似的定義。

碰撞正碰（direct impact )

一個運動的球與一個靜止的球碰撞，碰撞之前球的運動速度與兩球心的連線在同一條直線上，碰撞之后兩球的速度仍會沿著這條直線。這種碰撞稱為正碰，也叫對心碰撞。

碰撞斜碰（oblique impact)

一個運動的球與一個靜止的球碰撞，如果碰撞之前球的運動速度與兩球心的連線不在同一條直線上，碰撞之后兩球的速度都會偏離原來兩球心的連線。這種碰撞稱為斜碰，也叫非對心碰撞。

碰撞物體對障礙物的碰撞

一物體對某固定物體如地面、墻的碰撞屬此類型，也可分為正碰撞和斜碰撞。

碰撞物體對可轉(zhuǎn)動物體的碰撞

當物體甲與可繞O軸轉(zhuǎn)動的物體乙發(fā)生碰撞時，物體乙突然獲得一角速度變化（圖4）。一般在乙的支承O處也立刻產(chǎn)生一碰撞反力，其大小跟碰撞作用的位置，即距離OO₁有關(guān)。但在特殊條件下，懸掛物體雖受沖擊力，其約束力仍可為零。

散射

在粒子物理，原子物理或者當一個光子作為碰撞物之一時，碰撞也稱為散射，散逸或漫射。當一個粒子在碰撞中向另一個能級躍遷時，也稱作非彈性碰撞（非彈性散射）。當多數(shù)光子參與一個非彈性散射時會改變其總波長。相關(guān)請參閱散射和散射原理。

碰撞反應(yīng)碰撞

反應(yīng)碰撞來自反應(yīng)，如化學(xué)反應(yīng)或通過高能粒子在量子物理學(xué)中的碰撞產(chǎn)生新的粒子。在此必須注意，碰撞前后不同的粒子提供了能量和動量。在碰撞過程中速度變化的同時也存在粒子質(zhì)量和數(shù)量的變化。

反應(yīng)碰撞的一種類型如“電負性交換”：一個原子，分子或離子，一個或多個電子交換的原子物理學(xué)過程。很可能在此過程中一個電子給其中一個碰撞物帶上正電性。如太陽風中的正電子（參見高能離子）通過彗星周圍的氣層時被捕獲并發(fā)出x射線。