防碰撞算法FSA與DFSA

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

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

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

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

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

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

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

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

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

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

分群時(shí)隙Aloha算法

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

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

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

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

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

Q值算法

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

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

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

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

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

這些參數(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時(shí)，閱讀器僅需調(diào)用2Q－1次QueryRep命令，而不需要在接下來(lái)的盤存周期中調(diào)整Q值。當(dāng)吞吐量小于0．368時(shí)，根據(jù)未識(shí)別的標(biāo)簽個(gè)數(shù)nu來(lái)調(diào)整Q值 .

基于分組的位隙Aloha算法

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

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

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

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

dΩ =2πsinθdθ

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

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

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

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

或

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

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

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

碰撞正碰（direct impact )

一個(gè)運(yùn)動(dòng)的球與一個(gè)靜止的球碰撞，碰撞之前球的運(yùn)動(dòng)速度與兩球心的連線在同一條直線上，碰撞之后兩球的速度仍會(huì)沿著這條直線。這種碰撞稱為正碰，也叫對(duì)心碰撞。

碰撞斜碰（oblique impact)

一個(gè)運(yùn)動(dòng)的球與一個(gè)靜止的球碰撞，如果碰撞之前球的運(yùn)動(dòng)速度與兩球心的連線不在同一條直線上，碰撞之后兩球的速度都會(huì)偏離原來(lái)兩球心的連線。這種碰撞稱為斜碰，也叫非對(duì)心碰撞。

碰撞物體對(duì)障礙物的碰撞

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

碰撞物體對(duì)可轉(zhuǎn)動(dòng)物體的碰撞

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

散射

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

碰撞反應(yīng)碰撞

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

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