防碰撞算法

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

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

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

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

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

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

Q值算法

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

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

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

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

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

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

基于分組的位隙Aloha算法

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

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

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

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

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

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

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

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

分群時隙Aloha算法

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

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

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

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

在最簡單的情況下，設(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ù)值，因而，微分碰撞截面的普遍表達(dá)式可寫作：

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

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

碰撞正碰（direct impact )

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

碰撞斜碰（oblique impact)

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

碰撞物體對障礙物的碰撞

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

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

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

散射

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

碰撞反應(yīng)碰撞

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

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