隨機(jī)多址協(xié)議講稿(精品）

1、6隨機(jī)多址協(xié)議6.1隨機(jī)多址協(xié)議的概述70年代，諾曼艾彳j拉姆森（norman abramson）和他的伙伴在夏威夷人學(xué)設(shè)計(jì)出一種 新的解決信道分配問題的方法。他們的成果后來被許多研究者所擴(kuò)充（艾布拉姆森 1985） o盡管艾布拉姆森的稱為aloha系統(tǒng)的這項(xiàng)成果是以地面無線電為基礎(chǔ)的，但英基 本思想?yún)s適用于有多個(gè)彼此無協(xié)調(diào)關(guān)系的用戶競爭單一共事信道使用權(quán)的任何系統(tǒng)。6. 1. 1 純 aloha與時(shí)隙 aloha純aloha系統(tǒng)的基本思想很簡單：讓用戶什么時(shí)候有要送的數(shù)據(jù)就什么時(shí)候發(fā)送。當(dāng) 然會(huì)有沖類，而遭遇沖突的幀受到破壞。但是根據(jù)廣播的反饋性質(zhì)，發(fā)送者總可以靠監(jiān)聽 信道輸出來弄清它發(fā)出的

2、幀是否遭到破壞。在lan情況下，這種反饋是即刻的，但在衛(wèi)星 環(huán)境等無線信道下。要經(jīng)過長（衛(wèi)星270毫秒）延遲之后發(fā)送者才知道發(fā)送是否成功。如果 發(fā)送的幀受到破壞了，發(fā)送者就要等待某個(gè)隨機(jī)時(shí)間之后再次發(fā)送。等待時(shí)間必須是隨機(jī) 的，否則相同的幀必然以整齊的步伐二次乂一次地反復(fù)沖突。在一個(gè)系統(tǒng)中，多個(gè)用戶以 一種會(huì)導(dǎo)致沖突的方式共享一個(gè)公共信道.何群的系統(tǒng)被廣泛稱為爭用系統(tǒng)（contention system）。在一個(gè)aloha系統(tǒng)中，一般假設(shè)所有幀都具有同樣長度，因?yàn)閍loha系統(tǒng)的吞吐量 是在統(tǒng)一幀長情況下而不是有多種幀長的情況下達(dá)到最大。每當(dāng)冇兩個(gè)幀企圖在同一時(shí)刻占據(jù)信道，就產(chǎn)生沖突，兩個(gè)幀都

3、被破壞。必須認(rèn)識(shí) 到，一個(gè)新幀的第1位與要快結(jié)束的一幀的最后位相重疊，這兩個(gè)幀也算全破壞了，因而這 兩個(gè)幀必須都得稍后重發(fā)。校驗(yàn)和不能（也不應(yīng)該）區(qū)分是全部丟失還是丟失一點(diǎn)點(diǎn)。最令人感興趣的是aloha信道效率如何？也就是混在這樣混亂環(huán)境中，發(fā)送出的所有 幀屮逃脫沖突的幀占多大比例？首先讓我們考慮說限多交互式用戶集合都坐在她們的終端 （站）旁。用戶總是處于兩種狀態(tài)z-：發(fā)送與守侯。一開始，所有用戶都處于守侯狀態(tài) z屮。當(dāng)某個(gè)用戶決定進(jìn)行下發(fā)送時(shí)，發(fā)送數(shù)據(jù)幀，并檢查信道，看這幀是否發(fā)送成況一 如呆成功了，返回守侯在狀態(tài)。如杲?jīng)]成功，重發(fā)這個(gè)數(shù)據(jù)，直到發(fā)送成功為止。這里我們假設(shè)無限多普通用戶產(chǎn)生新

4、分組都符合泊松公布，每“時(shí)隙”平均s分組。 （為了確保在用戶變?yōu)榘l(fā)送狀態(tài)時(shí)s不至于減少，上述“無限”的假設(shè)是需要的）。除了產(chǎn)生新幀z外，新到達(dá)和重復(fù)發(fā)送的數(shù)據(jù)綜合起來每“時(shí)隙”中總的數(shù)據(jù)由些 變化，每“時(shí)隙”平均為g。顯然g>s。在低負(fù)荷情況下（即g和s都很?。?沖突很少， 因而重發(fā)也很少，所以gso在高負(fù)荷情況下，情況不同了。數(shù)據(jù)分組數(shù)據(jù)分組數(shù)據(jù)分組數(shù)據(jù)分組圖61隨機(jī)接續(xù)過程示意圖如果分組數(shù)據(jù)長度時(shí)t,貝ij在t時(shí)間內(nèi)到達(dá)的分組數(shù)可以用破送分布表示：p(n = k) = e'at ,對于隨機(jī)aloha系統(tǒng)莫如圖61所示，在2t時(shí)間內(nèi)部只能到達(dá)一個(gè) k!分?jǐn)?shù)，否則會(huì)發(fā)生碰撞，而導(dǎo)

5、致數(shù)據(jù)分?jǐn)?shù)的破壞。信道的利用率可以這樣得到，在2t時(shí)間 內(nèi)到達(dá)1個(gè)數(shù)據(jù)分組的概率為：p(n = 1) = (2at)e-22r ,而且要保證在2t時(shí)間結(jié)束本此數(shù)據(jù)傳 輸，因此要求，在2t時(shí)間內(nèi)到達(dá)一個(gè)分組，分組的數(shù)據(jù)頭必須在第一個(gè)t時(shí)間內(nèi)。而分組 數(shù)據(jù)的頭在第一個(gè)t內(nèi)的概率為0.5 (均勻分布)。所以信道成功傳輸?shù)母怕蕿椋?6-1)pin = 1)= 1 (2加)嚴(yán)=九t e2at 最大數(shù)値為"2=0.18；另外一種方法是連續(xù)觀測信道，統(tǒng)計(jì)第一個(gè)t時(shí)間備到達(dá)一個(gè)分 組，第二個(gè)t時(shí)間內(nèi)沒有分組到達(dá)或第一個(gè)t時(shí)間內(nèi)沒有分組，第二個(gè)t時(shí)間到達(dá)1個(gè)的概率 為p(n = l,t)p(n = 0

6、,t) = (at)eateat = (at)e2at ,這兩種情況的概率和為1,所以信道利用 率1公式相同。當(dāng)系統(tǒng)不是純aloha,而是采用統(tǒng)一的時(shí)隙結(jié)構(gòu)的時(shí)候，信道利用率可以從也可以使 用6.1,但是時(shí)間不是2t。而是t,也沒有1/2的系數(shù)，因此信道利用率為：(6-2)p(n = 1)=(刃)嚴(yán)最大數(shù)值為l/e=0.367o6.1.2局域網(wǎng)絡(luò)協(xié)議使用時(shí)隙aloha nd利用率最好可達(dá)到1/e。這毫不奇怪，因?yàn)辇R站都隨意發(fā)送，從不 顧及其它站在干什么，因而必定發(fā)生許多沖突。但是在局域網(wǎng)絡(luò)中，各站可以檢測苴它站 正在干什么，從而決定相應(yīng)的操作。1. 持久的與非持久的csma各站用于監(jiān)聽載波(即

7、傳送)和活動(dòng)的協(xié)議稱為載波監(jiān)聽協(xié)議csmao第一個(gè)載波監(jiān)聽協(xié)議是1率永久csma (載波監(jiān)聽多重訪問carrier sense multiple access) o當(dāng)有一個(gè)站有數(shù)據(jù)要發(fā)送時(shí)，首先聽一聽信道是否有英它站正在傳送。如杲信 道忙，則這個(gè)站就等著，直到該站變?yōu)榭臻e。當(dāng)信道檢測到信道空閑時(shí)，它就傳送一幀。 如果發(fā)生沖突，這個(gè)站就等待一定隨機(jī)時(shí)間，然后再完全重新開始。這個(gè)協(xié)議稱為1率永久宓議是因?yàn)辇R站在發(fā)現(xiàn)信道空閑時(shí)才發(fā)送，概率為1。傳播延遲嚴(yán)重影響這種協(xié)議的性能。很少有這樣的可能：就在一個(gè)站剛開始發(fā)送z 后，另一個(gè)站就準(zhǔn)備好發(fā)送，并監(jiān)聽信道。如果第一個(gè)站的信號(hào)尚未到達(dá)第二個(gè)站的時(shí) 候，第

8、二個(gè)站檢測出信道空閑，于是也開始發(fā)送，結(jié)杲造成沖突。傳播延遲越長，這種影 響變得越嚴(yán)重，因而協(xié)議的性能越壞。即便是傳播延遲為零，述會(huì)有沖突。如果有兩個(gè)站都在第三個(gè)站傳送過程中準(zhǔn)備好發(fā) 送，兩個(gè)站都“很禮貌”地一直等到傳送結(jié)束，然后準(zhǔn)確地同時(shí)開始發(fā)送，結(jié)果述是發(fā)生 沖突。如果它們不是這樣急切，沖突就會(huì)少些。即使這樣，這個(gè)協(xié)議還是比純aloha好得 多。因而兩個(gè)站因?yàn)槭艿谌齻€(gè)站傳送幀的干擾而不能發(fā)送的可能性要小得多。巴觀看來， 這比納aloha的性能要好。嚴(yán)格說來，與時(shí)隙aloha的性能相同。第二種載波監(jiān)聽協(xié)議稱為非永久csma (nonpcrsistent csma)。在這種協(xié)議中，發(fā)送 嘗試比

9、較有節(jié)制，不像前種協(xié)議那么急切。某站在發(fā)送以前要監(jiān)聽信道。如果沒有其它站 正在發(fā)送，這個(gè)站就開始發(fā)送。但是，如果信道已在使用之中，這個(gè)站不是為了測出傳輸 結(jié)束立即捉住信道而連續(xù)監(jiān)聽信道，而是等待一定隨機(jī)時(shí)間周期之后再重復(fù)發(fā)送操作。 直觀看來，這種方法比工率永久csma的信道利用率要好，延遲也要長些。最后-種協(xié)議稱為p李永久csmao這種協(xié)議用干吋隙信道，工作如下。有一個(gè)站準(zhǔn)備 好發(fā)送吋，就監(jiān)聽信道。如果信道空閑，該站就以概率p發(fā)送。若概率為q=l-p,就推遲到下 個(gè)時(shí)隙。如果那個(gè)時(shí)隙也是空閑的，這個(gè)站要么發(fā)送，要么再次推遲，概率分別p和q。這 個(gè)過程一直重復(fù)下去，直到有一個(gè)幀發(fā)出來，或者其它站

10、已經(jīng)開始傳送。在后一種情況 下，其作用好象產(chǎn)生一次沖突(即要等待一定隨機(jī)時(shí)間，然后再開始)。如果這個(gè)站一開 始就監(jiān)聽到信道繁忙，它就等到下個(gè)時(shí)陡然后使用上述算法。圖6-2不同控制算法的信道利用率2. 帶有沖突避免的csma雖然永久的和非永久的csma都是對aloha的改進(jìn)協(xié)議，因?yàn)槎寄鼙ＷC在監(jiān)聽到信道 忙時(shí)沒冇站開始發(fā)送。另一種改進(jìn)是對各站而言，當(dāng)它們檢測到?jīng)_突，立即把它們的發(fā)送 動(dòng)作廢掉。換句話說，如果兩個(gè)站都聽到信道空閑，因而同時(shí)開始發(fā)送，它們倆使兒乎立 即都檢測到?jīng)_突。不要等到發(fā)送完畢，因?yàn)榘l(fā)送的幀已破碎得不可恢復(fù)，要一旦檢測到?jīng)_ 突就立即停止發(fā)送。迅速結(jié)束損害的幀可以節(jié)省時(shí)間和帶寬。這

11、種i辦議就是著名的 csmacd （帶有沖突檢測的載波監(jiān)聽多重訪問canier sense multivie access with collision dection）,并且在lan小的mac層得到廣泛應(yīng)用。3. 其他協(xié)議使用csma/cd在有一個(gè)越明確占有信道期間不會(huì)出現(xiàn)沖突，但在爭奪期間還可能出現(xiàn) 沖突。這些沖突對系統(tǒng)性能產(chǎn)生有害的影響，尤其在電纜長（即i很大）而幀短的情況下。 由于長度長而頻帶寬的光纖網(wǎng)絡(luò)投入使用，把大r與矩幀結(jié)合起來也不會(huì)產(chǎn)牛嚴(yán)垂問題。木 節(jié)與下邊幾節(jié)討論一些協(xié)議，這些協(xié)議解決信道完全擺脫沖突的問題，甚至在爭奪期間也 不發(fā)生沖突。例如，輪詢是在控制下的無沖突協(xié)議。此外

12、還有有限沖突協(xié)議。可以閱讀參 考書6.2分組數(shù)據(jù)業(yè)務(wù)量分析以及參數(shù)估計(jì)6. 2.1數(shù)據(jù)業(yè)務(wù)量分析本節(jié)以動(dòng)態(tài)時(shí)隙為基礎(chǔ)分析時(shí)隙協(xié)議算法的計(jì)算和佔(zhàn)計(jì)過程。下面分析首先假設(shè)信道上是簡單流，歸一化強(qiáng)度為入，信道接續(xù)方式為時(shí)隙alohai辦 議，在長為n時(shí)隙的一幀小有ne個(gè)空閑時(shí)隙、ng個(gè)碰撞時(shí)隙、ns個(gè)成功時(shí)隙，ns代表執(zhí)行 業(yè)務(wù)量，但ng不能代表損失業(yè)務(wù)量，因?yàn)榕鲎矔r(shí)隙的碰撞數(shù)量未知。現(xiàn)假設(shè)第i個(gè)時(shí)隙碰 撞，在本幀開始前的時(shí)間是t,則k個(gè)用戶選擇第i個(gè)時(shí)隙的概率為：p（k）=eyj（6-3）k!由條件概率pk個(gè)用戶發(fā)送i碰撞陽對所有碰撞時(shí)隙的呼叫數(shù)均值可1 一尸（u丿一尸（1丿表示為每一個(gè)時(shí)隙呼叫數(shù)

13、均值為00co / n t、k£kp(k)= m嚴(yán)£匕丄=at k=0k=0 k!如杲系統(tǒng)工作在最佳條件下，久t應(yīng)為1,即每個(gè)時(shí)隙的呼叫數(shù)均值為1 ,此時(shí)系統(tǒng)的 容量達(dá)到最大。在此條件下碰撞時(shí)隙的呼叫均值應(yīng)為：xt (嚴(yán)一1丿-1-xt-2.39這時(shí)得出無干擾條件下信道的業(yè)務(wù)量指標(biāo)，設(shè)幀長為n、卄、“幻冃 a ns+2.39ng流入業(yè)務(wù)量a =-n執(zhí)行業(yè)務(wù)量a0=ns/n(6-7)(6-8)損失業(yè)務(wù)量aao=z譽(yù)(6-9)(6-12)(6-13)(6-15)當(dāng)信道有干擾存在時(shí)，此時(shí)觀測到的碰撞時(shí)隙一部分是真正碰撞所至，所以觀測到的 碰撞概率耳與真止碰撞概率的關(guān)系可以表示為：

14、00代=工 p(ai) p(i) = p( aio) p(0) + p(ai1) p(l) + p&1(6-10)/=0pg'=化-p(aio) p(0) p(ai1) p(l)(6-11)英屮p(ali)表示有i個(gè)用戶發(fā)送發(fā)生碰撞的條件概率，此條件下的碰撞時(shí)隙的呼叫數(shù)均值co為：如工kpg ,由此式來計(jì)算信道上的業(yè)務(wù)量，真止的碰撞的呼叫數(shù)是ng'/t=l=心 ng pg' i pg o如果信道上發(fā)生捕獲現(xiàn)象，觀測到的成功概率是人，真正一個(gè)時(shí)隙只有一個(gè)分組的概 率為，則c與的關(guān)系可以表示為：88ps = y p(bw) p=+工 p(bi) p/=!22則在成功

15、時(shí)隙中單一用戶的概率ps為：copj=p廠工 p(bli) p(i)r=2如山p(bli)表示i個(gè)用戶發(fā)送發(fā)生捕獲的概率。此時(shí)系統(tǒng)的流入業(yè)務(wù)量:2.39ng pjp& + m + 1.39 n(p, p門/ p、n損失業(yè)務(wù)量:a ao =2.39 m /v / p& + 1 39 m (p、 ")/ &n6. 2. 2非理想信道信令業(yè)務(wù)量分析及參數(shù)估計(jì)在一個(gè)實(shí)際的系統(tǒng)屮，信道不可能是理想的，信道上有噪聲和捕獲效應(yīng)，系統(tǒng)應(yīng)考慮 到這些情況并有相應(yīng)的處理能力。在非理想條件下，系統(tǒng)的觀測情況與實(shí)際情況是有差異 的，下面的討論耍解決的問題是從觀測到的結(jié)果來估計(jì)系統(tǒng)的真

16、實(shí)運(yùn)行情況，以保證系統(tǒng) 動(dòng)態(tài)控制的正確。假設(shè)在一個(gè)系統(tǒng)的覆蓋區(qū)域內(nèi)，設(shè)g是話務(wù)流的密度函數(shù)，r為用戶到基地臺(tái)的距 離，則在0r范殉內(nèi)的業(yè)務(wù)量g(c為：g(廠)=f 27ix- g(x)dxi的空間分布函數(shù)和密度函數(shù)為:fr(k) = pr(/? < r)=x- g(x)dxgo j)fr(r)=：rg(r)g當(dāng)g"丿=芻 (0 vr vr丿時(shí)fr(r)r2(6-17)(6 j 8)(6-19)(6-20)(6-21)在我們設(shè)計(jì)的實(shí)際系統(tǒng)屮，(n,k)線性分組碼編碼格式，系統(tǒng)的誤碼率為pb,令pbc為數(shù) 據(jù)解碼的誤碼率，貝ijpbc可以由下面計(jì)算/ d1 npbc = £

17、; c； p；(1- )1 + £ ic； p；(1-計(jì)(6-22)d為最小碼距，t=int(d-l)/2,采用(n,k)線性分組碼。對一般的陸地移動(dòng)通信系統(tǒng)，正 確接收的概率pc為：pc=d-pbc)l(6-23)對所冇可能的位置求pc的均值r2 r2pcws)=卜"辦0)辦(也)磯心r r由信道流入強(qiáng)度x可求得捕獲的概率為:為 p(w(w)p(正確接收i碰撞尸仏 剛、(6-25)1 一 尸(u丿一 r)其中psli=p(正確接收li個(gè)用戶發(fā)送)，p(i)是i個(gè)用戶選擇木時(shí)隙發(fā)送的概率。對接收失敗時(shí)隙有：n工 p(etroxk) p(k)p(用戶數(shù)大于ii接收失敗尸 (6

18、-26)工 p(em)nk)p(k)=1其中p (errorlk)是有k(k $2)個(gè)用戶發(fā)送血接收錯(cuò)課的概率。用同樣方法求得ps(一個(gè)用戶發(fā)送i發(fā)送成功)的值ps'(一個(gè)用戶i發(fā)送成功)=/(")")(6-27)在上述計(jì)算過程中，要依賴信道的捕獲概率和碰捶概率，血這些值又與信道流入?yún)?shù) 入有關(guān)。實(shí)際上如果知道信道流入?yún)?shù)入，也就得到了信道流入業(yè)務(wù)量，所以如果用某一 點(diǎn)的捕獲概率和碰扌帝概率數(shù)值進(jìn)行信道估計(jì)，顯然不僅不知道謀差而且對信道變化沒有適 應(yīng)能力。這種方式在實(shí)際工程應(yīng)用屮是不適用的，并且計(jì)算量大。對于我們設(shè)計(jì)并已經(jīng)投入使用的集中控制式系統(tǒng)，應(yīng)用了另外一種參數(shù)

19、估計(jì)算法，這 種方法對信道的捕獲和噪聲影響合并考慮，用對一段時(shí)間內(nèi)的數(shù)據(jù)幀進(jìn)行觀測，來決定系 統(tǒng)的流入強(qiáng)度等動(dòng)態(tài)控制參數(shù)，這種方法在實(shí)際應(yīng)用中簡便易行并冋避了對捕獲概率和碰 撞概率的計(jì)算。令psn是長度為n個(gè)時(shí)隙的幀中有i個(gè)時(shí)隙成功傳送的概率，pgn(i)是長度 為n個(gè)時(shí)隙的幀中有i個(gè)時(shí)隙碰撞的概率，pen(i)是長度為n個(gè)時(shí)隙的幀中有i個(gè)時(shí)隙空閑的概 率，在一幀屮成功、碰扌南、空閑的時(shí)隙的期望值分別是：n嚴(yán) ec, 八7(1 一加")1(6-28)/=()nnv = w 八(1一£" 一 幾(" + 幾(6-29)<=0nn嚴(yán)工c：(1 一小)z/=0(6-30)圖63各種時(shí)隙期望值隨流入強(qiáng)度的變化曲線