面向編碼機(jī)會(huì)路由的廣播媒體融合的自適應(yīng)協(xié)議設(shè)計(jì)

面向編碼機(jī)會(huì)路由的廣播媒體融合的自適應(yīng)協(xié)議設(shè)計(jì)

無(wú)線傳感器網(wǎng)絡(luò)的易誤和時(shí)間偏移嚴(yán)重降低了傳統(tǒng)協(xié)議的性能。例如，在破壞環(huán)境中，頻繁重傳和路徑檢測(cè)將導(dǎo)致系統(tǒng)性能的下降。然而，無(wú)線傳感器網(wǎng)絡(luò)的傳輸性質(zhì)也顯示出一些獨(dú)特的優(yōu)勢(shì)：多個(gè)節(jié)點(diǎn)共享傳輸通道并獨(dú)立衰減。因此，每個(gè)發(fā)送文件的每個(gè)接收節(jié)點(diǎn)的成功率遠(yuǎn)遠(yuǎn)超過(guò)確定節(jié)點(diǎn)的成功率。這一性質(zhì)被稱為多功能用戶體驗(yàn)（ud）的優(yōu)勢(shì)。近年來(lái)提出的編碼機(jī)會(huì)路徑（oad）結(jié)合了無(wú)線環(huán)境中編碼的優(yōu)勢(shì)和隨機(jī)網(wǎng)絡(luò)編碼的糾紛碼特征，已成為支持高吞吐量可靠網(wǎng)絡(luò)傳輸?shù)挠行Х桨??？紤]圖1有損網(wǎng)絡(luò)中的單播會(huì)話suf0aed,s到任意中間節(jié)點(diǎn)(a,b,c)的交付概率均為50%,中間節(jié)點(diǎn)到d的交付概率為100%.按照傳統(tǒng)確定性路由(如suf0aebuf0aed),吞吐率(不考慮底層調(diào)度延遲)只有0.5.而NCOR機(jī)制通過(guò)源節(jié)點(diǎn)s將報(bào)文分批隨機(jī)編碼并持續(xù)廣播;每個(gè)中間節(jié)點(diǎn)對(duì)接收到的報(bào)文再次隨機(jī)混合后轉(zhuǎn)發(fā)的方式,吞吐達(dá)到1-0.53=0.875,相比前者提高70%以上.此外,隨機(jī)網(wǎng)絡(luò)編碼不僅提供了端到端的糾刪功能,還自然消除了多個(gè)中間節(jié)點(diǎn)需要復(fù)雜協(xié)作以防止冗余轉(zhuǎn)發(fā)的困擾.這些優(yōu)點(diǎn)使NCOR在質(zhì)量低下的無(wú)線網(wǎng)絡(luò)中倍受關(guān)注.但這種新型的路由方法在現(xiàn)實(shí)網(wǎng)絡(luò)中的性能優(yōu)化以及與現(xiàn)有協(xié)議的兼容性仍亟需探討,相關(guān)研究正在起步中.例如,改進(jìn)NCOR的分批編碼與TCP的兼容性,優(yōu)化編碼速率和發(fā)送速率控制方法等.在無(wú)線網(wǎng)絡(luò)中MAC設(shè)計(jì)對(duì)NCOR的總體性能有直接影響.我們注意到,MUD優(yōu)勢(shì)和隨機(jī)編碼的糾刪特性使得NCOR機(jī)制下的廣播信道接入呈現(xiàn)出獨(dú)特的性質(zhì):不需要等待所有接收節(jié)點(diǎn)同時(shí)準(zhǔn)備好,也不需要任何鏈路級(jí)的可靠保證.仍以圖1網(wǎng)絡(luò)為例,在干擾節(jié)點(diǎn)i,j的影響下,廣播鏈路suf0ae{a,b,c}的信道接入時(shí)機(jī)有多種選擇:(1)等待所有的節(jié)點(diǎn){a,b,c}都準(zhǔn)備好,此時(shí)MUD優(yōu)勢(shì)最為顯著,但是接入媒體的延遲可能過(guò)長(zhǎng),造成端到端吞吐量較低;(2)只要有一個(gè)接收節(jié)點(diǎn)可用則接入媒體,盡管接入延遲適中,但NCOR有可能退化為單路徑路由,失去MUD優(yōu)勢(shì);(3)僅根據(jù)發(fā)送端媒體狀況決定是否接入(即IEEE802.11DCF廣播模式),盡管接入延遲最小,但在多跳網(wǎng)絡(luò)中可能存在嚴(yán)重的隱藏終端問(wèn)題.因此,選擇合適的接入時(shí)機(jī)以支持更高的NCOR端到端吞吐量,成為一個(gè)重要的優(yōu)化問(wèn)題,我們稱為機(jī)會(huì)廣播信道接入問(wèn)題.本文從實(shí)際協(xié)議設(shè)計(jì)的角度出發(fā),提出一種完全分布式的機(jī)會(huì)廣播信道接入策略.該策略以單跳的平均有效傳輸速率為優(yōu)化目標(biāo),借助最優(yōu)停止理論獲得接入延遲和信道交付能力之間的最佳平衡點(diǎn).本文的另一個(gè)貢獻(xiàn)是,通過(guò)擴(kuò)展IEEE802.11DCF,設(shè)計(jì)一個(gè)機(jī)會(huì)廣播MAC協(xié)議O-BCast以執(zhí)行上述策略.模擬實(shí)驗(yàn)驗(yàn)證了O-BCast有助于無(wú)線網(wǎng)絡(luò)中傳輸機(jī)會(huì)的有效利用,獲得良好的端到端性能.基于MUD優(yōu)勢(shì)的廣播鏈路調(diào)度問(wèn)題在傳統(tǒng)機(jī)會(huì)路由領(lǐng)域已有一些研究,他們主要致力于解決多個(gè)節(jié)點(diǎn)之間的冗余轉(zhuǎn)發(fā)問(wèn)題.例如:ExOR提出一個(gè)專用MAC協(xié)議,用于串行化調(diào)度所有參與會(huì)話的節(jié)點(diǎn);文獻(xiàn)則設(shè)計(jì)鏈路級(jí)的anycast機(jī)制,通過(guò)DATA/ACK或RTS/CTS握手,從收到同一個(gè)報(bào)文的節(jié)點(diǎn)中選出唯一的轉(zhuǎn)發(fā)者,但他們都沒(méi)有考慮到接入時(shí)機(jī)的靈活性.NCOR機(jī)制下的廣播鏈路調(diào)度對(duì)總體吞吐量的影響也受到研究人員關(guān)注,但他們多是通過(guò)理論建模和優(yōu)化的方法,將該問(wèn)題放到跨層最優(yōu)化框架中綜合考慮.即便在簡(jiǎn)單的干擾模型性下,該問(wèn)題仍是NPC困難的,而且通常需要中心計(jì)算或理想的反饋機(jī)制,因此其結(jié)果很難應(yīng)用到實(shí)際的協(xié)議設(shè)計(jì)中.同樣地,這些工作也沒(méi)有考慮接入時(shí)機(jī)的靈活性.本文的建模和分析建立在分布式隨機(jī)競(jìng)爭(zhēng)接入方式基礎(chǔ)上,輔以局部的探測(cè)機(jī)制來(lái)確定最佳的廣播信道接入時(shí)機(jī),不僅有效提高了吞吐量,而且容易與當(dāng)前的主流無(wú)線標(biāo)準(zhǔn)兼容.本文第1節(jié)建立有損多跳網(wǎng)絡(luò)模型,并提出平均有效速率最優(yōu)的機(jī)會(huì)廣播信道接入問(wèn)題.第2節(jié)通過(guò)最優(yōu)停止理論推導(dǎo)出基于閾值的最優(yōu)接入決策算法.第3節(jié)討論最優(yōu)接入算法的數(shù)值分析結(jié)果.第4節(jié)介紹基于上述算法的機(jī)會(huì)廣播接入?yún)f(xié)議O-Bcast.第5節(jié)討論在ns-2環(huán)境中的模擬實(shí)驗(yàn)結(jié)果.最后總結(jié)全文.1系統(tǒng)模型和問(wèn)題的提出1.1節(jié)點(diǎn)狀態(tài)可用考慮一個(gè)靜態(tài)的無(wú)線Mesh網(wǎng)絡(luò)G=(V,E),V為節(jié)點(diǎn)集合,每個(gè)節(jié)點(diǎn)配備一個(gè)帶有全向天線的收發(fā)器,且工作于同一信道上;E為傳輸質(zhì)量超過(guò)一定閾值的點(diǎn)到點(diǎn)鏈路集合,即E={(i,j)|cij>cthresh,i,juf0ceV}.其中:cthresh為閾值常量;鏈路質(zhì)量cij是指不計(jì)鏈路間干擾時(shí)i到j(luò)的平均交付概率,它與信號(hào)強(qiáng)度、調(diào)制編碼方式、信道衰減特征等因素相關(guān).N(i)={j|juf0ceVuf0d9(i,j)uf0ceE}表示i的鄰居集合.設(shè)網(wǎng)絡(luò)按時(shí)隙(slot)運(yùn)行,節(jié)點(diǎn)j在時(shí)隙t的狀態(tài)記為二元隨機(jī)變量sj(t):sj(t)=0表示節(jié)點(diǎn)j不可用;反之,sj(t)=1.對(duì)于發(fā)送節(jié)點(diǎn),狀態(tài)可用是指節(jié)點(diǎn)空閑且獲得媒體訪問(wèn)權(quán),如在802.11網(wǎng)絡(luò)中感知媒體空閑并完成隨機(jī)退避(CSMA/CA);對(duì)于接收節(jié)點(diǎn),狀態(tài)可用是指節(jié)點(diǎn)不處于收/發(fā)狀態(tài),且不受網(wǎng)絡(luò)中其他正在進(jìn)行的傳輸干擾.若t時(shí)鏈路(i,j)被調(diào)度傳輸,其報(bào)文成功交付的概率pij(t)可以表示為顯然,pij(t)為與sj(t)相關(guān)的隨機(jī)變量,公式(1)反映出實(shí)際的鏈路交付能力是信道自身?xiàng)l件和接收節(jié)點(diǎn)狀態(tài)共同作用的結(jié)果.設(shè)網(wǎng)絡(luò)中存在多個(gè)持續(xù)的單播會(huì)話,均依照NCOR機(jī)制進(jìn)行路由轉(zhuǎn)發(fā).對(duì)于每個(gè)會(huì)話s→d,源節(jié)點(diǎn)s首先從V中選擇傳輸成本小于自己的節(jié)點(diǎn)構(gòu)成候選轉(zhuǎn)發(fā)集合(CFS).接著,源節(jié)點(diǎn)不斷廣播發(fā)送出編碼報(bào)文,并在報(bào)文中攜帶CFS列表;候選轉(zhuǎn)發(fā)節(jié)點(diǎn)緩存所有聽(tīng)到的編碼報(bào)文,并再次編碼后轉(zhuǎn)發(fā)出去;目標(biāo)節(jié)點(diǎn)d收到足夠多的編碼報(bào)文之后解碼恢復(fù)出原始消息.沿用文獻(xiàn)的建模方法,這些節(jié)點(diǎn)構(gòu)成的拓?fù)溆贸瑘DH=(V′,A)表示,其中,節(jié)點(diǎn)集合V￠=CFSè{s,d};超弧集合A包含NCOR傳輸所使用的廣播鏈路(i,J),J稱為i的候選下一跳集合(CNH)J?(N(i)∩V′).1.2信號(hào)接入策略根據(jù)超弧的MUD特性,我們定義超弧(i,J)的即時(shí)交付能力PiJ(t)為t時(shí)隙節(jié)點(diǎn)i廣播的報(bào)文被任意下一跳鄰居成功接收的概率:可見(jiàn),PiJ是與接收節(jié)點(diǎn)狀態(tài)相關(guān)的隨機(jī)變量.在此基礎(chǔ)上,我們定義超弧的平均有效速率(averageeffectiverate,簡(jiǎn)稱AER)為單位時(shí)間內(nèi)i向下一跳集合J成功交付的數(shù)據(jù)量,即其中,zi為時(shí)間T內(nèi)i向超弧注入的報(bào)文數(shù)目,m為報(bào)文尺寸,iJP為T內(nèi)數(shù)據(jù)傳輸階段的平均交付能力.時(shí)間T包括超弧的調(diào)度延遲和實(shí)際的報(bào)文傳輸時(shí)間,因此,AER反映了超弧在網(wǎng)絡(luò)層呈現(xiàn)的傳輸速率,是NCOR端到端吞吐的基礎(chǔ).若發(fā)送速率和鏈路質(zhì)量確定,AER與調(diào)度延遲和被調(diào)度傳輸時(shí)的交付能力相關(guān),這兩個(gè)因素直接依賴于信道接入策略.其中PiJ為隨機(jī)變量,若借助探測(cè)機(jī)制對(duì)其觀察,那么機(jī)會(huì)廣播信道接入的基本過(guò)程為:發(fā)送節(jié)點(diǎn)在狀態(tài)可用即si(t)=1時(shí),首先探測(cè)當(dāng)前超弧的交付能力PiJ;然后依據(jù)某種策略判斷是否立即發(fā)送或執(zhí)行下一輪探測(cè),直到最終發(fā)送出數(shù)據(jù)報(bào)文或超過(guò)最大探測(cè)次數(shù).如圖2所示,超弧經(jīng)過(guò)n輪探測(cè)之后發(fā)送數(shù)據(jù)報(bào)文.第l輪探測(cè)前等待發(fā)送節(jié)點(diǎn)可用的時(shí)間記為Kll=0,1,…,n,探測(cè)獲知超弧交付能力PiJ(l),探測(cè)耗費(fèi)的時(shí)間為常量Tprobe.該過(guò)程總耗費(fèi)時(shí)間為調(diào)度延遲與實(shí)際的數(shù)據(jù)傳輸時(shí)間Tdata之和,即其中,Tdata與發(fā)送速率和報(bào)文尺寸相關(guān),T0為直接發(fā)送、不執(zhí)行任何探測(cè)(類似802.11DCF廣播模式)情況下接入過(guò)程的總耗費(fèi)時(shí)間,Tn為執(zhí)行n輪探測(cè)情況下所耗費(fèi)時(shí)間.借助信道預(yù)留機(jī)制(NAV),超弧的交付能力在探測(cè)期間和緊接著的數(shù)據(jù)傳輸期間(Tdata)維持不變.在不引起歧義的前提下,下面的陳述將省略下標(biāo)iJ.若超弧一直有積壓的數(shù)據(jù)報(bào)文待發(fā)送,統(tǒng)計(jì)Z次連續(xù)接入過(guò)程的AER,有其中,N(z)表示第z次信道接入過(guò)程耗費(fèi)的探測(cè)輪數(shù),TN(z)和P(N(z))為第z次接入過(guò)程的總耗費(fèi)時(shí)間和發(fā)送數(shù)據(jù)報(bào)文期間超弧的交付能力.根據(jù)Lun的工作,鏈路有損的無(wú)線網(wǎng)絡(luò)中,NCOR所支持的端到端容量取決于業(yè)務(wù)流所穿越的關(guān)鍵超弧的網(wǎng)絡(luò)層平均速率,即AER.而且,最大化AER意味著恰當(dāng)?shù)仄胶獬〉慕桓赌芰驼{(diào)度延遲,有助于高效利用無(wú)線網(wǎng)絡(luò)中傳輸機(jī)會(huì).因此,我們提出AER最優(yōu)的機(jī)會(huì)廣播信道接入問(wèn)題(記為ROOMA):設(shè)uf0a5表示所有基于CSMA可行接入策略集合,選擇合適的策略N*uf0ceuf0a5,使得超弧的AER最大,即按照?qǐng)D2所示接入過(guò)程,解決該問(wèn)題就是要選擇恰當(dāng)?shù)臅r(shí)機(jī)停止探測(cè)并發(fā)送數(shù)據(jù)報(bào)文,以使得平均有效速率(AER)最大化.下節(jié)將借助最優(yōu)停止理論給出詳細(xì)的求解.2測(cè)試結(jié)果與分析本節(jié)以最優(yōu)停止理論為基礎(chǔ),將ROOMA映射為最大回報(bào)率(maximumrateofreturn)問(wèn)題并求解相應(yīng)的停止規(guī)則,以控制信道接入過(guò)程.在最優(yōu)停止理論中,停止規(guī)則是一個(gè)根據(jù)觀察到的事件判斷何時(shí)采取特定行動(dòng),以獲得最大期望收益的策略.觀察隨機(jī)變量序列X1,X2,…,假設(shè)已知其聯(lián)合分布和該序列的收益函數(shù):y0,y1(x1),y2(x1,x2),…,yuf0a5(x1,x2,…).在觀察到X1=x1,X2=x2,…,Xn=xn之后,可以選擇停止并獲得收益yn(x1,x2,…,xn),也可繼續(xù)觀察xn+1.停止規(guī)則選擇一個(gè)停止時(shí)間N,使得收益的期望E[YN]最大.在求解ROOMA問(wèn)題之前,我們首先提出一個(gè)假設(shè):超弧的交付能力PiJ在各探測(cè)時(shí)隙服從獨(dú)立一致分布該假設(shè)的合理性在于:(1)本文的信道接入建立在802.11CSMA基礎(chǔ)上,這類多跳網(wǎng)絡(luò)隨機(jī)接入?yún)f(xié)議的建模分析中,信道狀態(tài)(如忙/閑)的變換通常假設(shè)是一個(gè)更新過(guò)程(renewalprocess),亦即在每個(gè)切換時(shí)刻,下一個(gè)狀態(tài)與當(dāng)前狀態(tài)獨(dú)立.我們的探測(cè)發(fā)生在發(fā)送端贏得隨機(jī)信道競(jìng)爭(zhēng)之后,因此各探測(cè)時(shí)隙內(nèi)觀察到的PiJ相關(guān)度很小;(2)Mesh網(wǎng)絡(luò)拓?fù)涔潭?且Mesh業(yè)務(wù)來(lái)自于大量的端用戶業(yè)務(wù)的匯聚,因此在較大時(shí)間尺度上存在一個(gè)穩(wěn)定的業(yè)務(wù)流特征.實(shí)驗(yàn)部分對(duì)此進(jìn)行了驗(yàn)證.在此假設(shè)基礎(chǔ)上,根據(jù)大數(shù)定律,Z次連續(xù)接入過(guò)程的平均有效速率(AER)可以表示為公式(7)將ROOMA問(wèn)題的映射為最大回報(bào)率問(wèn)題,E[mP(N)]/E[TN]為其目標(biāo)函數(shù),N為停止時(shí)間(stoppingtime),P(N)和TN為停止隨機(jī)變量.這樣,ROOMA問(wèn)題可以表述為:觀察隨機(jī)序列{P(n)}和{Tn},尋找一個(gè)停止規(guī)則(即發(fā)送數(shù)據(jù)幀的時(shí)刻)N*uf0ce(34),(34)={N:N≥0,E[TN]<uf0a5},使獲得最大平均有效速率R*,即設(shè)發(fā)送端等待和退避時(shí)間均值為w=E[K],根據(jù)超弧交付能力的獨(dú)立一致性假設(shè),有下面的命題成立:命題1.(1)ROOMA問(wèn)題存在停止規(guī)則N*,且其中,uf0710=uf06c*(w+Tdata),uf071=uf06c*Tdata.(2)N*獲得的最大AER為R*(28)maxuf0ecuf0efuf0edE[uf0efuf0eewm(10)TP]data,uf06c*uf0fcuf0efuf0fduf0efuf0fe,其中,uf06c*為如下定點(diǎn)方程的解:這里,[uf0d7]+表示取正部(證明參見(jiàn)附錄).命題1揭示出ROOMA問(wèn)題的接入策略呈現(xiàn)簡(jiǎn)單的分段閾值結(jié)構(gòu):在發(fā)送端狀態(tài)可用的條件下,若超弧平均交付能力E[mP]超過(guò)閾值uf0710,則不需要執(zhí)行任何探測(cè)(類似IEEE802.11DCF的廣播模式),此時(shí),AER為E[mP]/(w+Tdata);否則,對(duì)接收端發(fā)起探測(cè),直至觀察到超弧交付能力mP(n)超過(guò)閾值uf071則發(fā)送DATA幀,此時(shí),AER為uf06c*.計(jì)算該策略的開(kāi)銷主要在于定點(diǎn)方程(10)的求解,若使用簡(jiǎn)單的窮舉算法,其復(fù)雜度與離散型隨機(jī)變量P的可能取值數(shù)目(通常小于24)呈線性關(guān)系,對(duì)于Mesh節(jié)點(diǎn)可以接受.3節(jié)點(diǎn)接入策略配置本節(jié)利用MATLAB工具計(jì)算命題1所給出的接入策略(N*)的數(shù)值結(jié)果,并與IEEE802.11DCF廣播模式和xReady策略比較.IEEE802.11DCF廣播模式在發(fā)送端的媒體空閑且完成隨機(jī)退避后發(fā)送數(shù)據(jù)報(bào)文,記為CSMA;xReady策略是指在發(fā)送端可用基礎(chǔ)上,通過(guò)探測(cè)獲知至少x(x=1,2,…)個(gè)接收節(jié)點(diǎn)狀態(tài)可用時(shí)才允許發(fā)出數(shù)據(jù)報(bào)文,否則退避后進(jìn)行下一輪探測(cè).考慮多跳網(wǎng)絡(luò)中的某個(gè)超弧(i,J),網(wǎng)絡(luò)其他部分對(duì)它的影響反映為超弧中節(jié)點(diǎn)并不總是準(zhǔn)備好接收或發(fā)送.設(shè)發(fā)送節(jié)點(diǎn)等待可用的平均時(shí)間為w,各接收節(jié)點(diǎn)在每個(gè)探測(cè)時(shí)隙的可用概率均為pr且相互獨(dú)立;探測(cè)每個(gè)接收節(jié)點(diǎn)花費(fèi)時(shí)間為tprobe,一輪探測(cè)時(shí)間Tprobe=|J|uf0b4tprobe;每條點(diǎn)到點(diǎn)鏈路(i,j),juf0ceJ均為單位速率且交付概率為c則超弧的交付能力與可用接收節(jié)點(diǎn)數(shù)目一一對(duì)應(yīng).為簡(jiǎn)單起見(jiàn),進(jìn)一步假設(shè)發(fā)送端的狀態(tài)與接收端狀態(tài)相互獨(dú)立,從而CSMA完全不能預(yù)測(cè)接收端狀態(tài).若無(wú)特殊說(shuō)明,默認(rèn)參數(shù)設(shè)置為|J|=4,Tdata=300,m=2000,c=0.2,Tprobe=4w=1,單位省略.圖3描繪了不同參數(shù)配置下AER隨節(jié)點(diǎn)可用概率pr的變化情況.我們看到,N*在各種條件下均給出所有接入策略的性能上界.圖3(a)顯示,在默認(rèn)參數(shù)下,N*所獲得的AER相比CSMA平均提高86%,而且在不同的網(wǎng)絡(luò)條件下均能選擇合適的接入策略.例如在網(wǎng)絡(luò)條件很好時(shí)(pr>0.8),有E[mP]≥uf0710成立,因此N*=0,其表現(xiàn)與CSMA相同.而一旦pr降低,N*則需要通過(guò)探測(cè)來(lái)減少低質(zhì)量的傳輸,且網(wǎng)絡(luò)條件越好,閾值uf071越大.例如在pr很小時(shí)(pr<0.12),uf071/m等于僅單個(gè)接收節(jié)點(diǎn)可用時(shí)的超弧交付能力P;當(dāng)pr增大,uf071/m則依次提高到2個(gè)、3個(gè)接收節(jié)點(diǎn)可用時(shí)的P,因此,N*的表現(xiàn)依次與xReady:x=1,x=2,x=3相同.該結(jié)果表明,N*能夠在接入延遲和超弧交付能力之間給予恰當(dāng)折衷.圖3(b)和圖3(c)在默認(rèn)參數(shù)基礎(chǔ)上分別增大w和|J|,結(jié)果顯示,N*策略相比CSMA的性能增益有所下降,因?yàn)槎呔鶎?dǎo)致探測(cè)成本增大而抵消掉超弧交付能力提高的好處.我們注意到,在探測(cè)開(kāi)銷增大到與數(shù)據(jù)傳輸時(shí)間相當(dāng)時(shí),xReady(x=2,3)很難勝出,如圖3(b),xReady(x=1)和CSMA分別在前后半段時(shí)表現(xiàn)最優(yōu)最后,圖3(d)顯示,在點(diǎn)到點(diǎn)鏈路質(zhì)量c較高時(shí),N*的優(yōu)勢(shì)也稍有下降(相對(duì)CSMA的平均增益下降到75%).這是因?yàn)镻的波動(dòng)性隨著c的增大而下降,那么N*保證較大的超弧交付能力的優(yōu)勢(shì)會(huì)減小.以上結(jié)果驗(yàn)證了N*策略的AER最優(yōu)性.盡管AER是單跳的超弧性能,但由于兼顧了接入延遲和干擾導(dǎo)致的交付能力的隨機(jī)波動(dòng),我們相信,該策略同樣有益于提高NCOR端到端吞吐.接下來(lái),我們將在實(shí)際的MAC協(xié)議實(shí)現(xiàn)該策略,并檢驗(yàn)它在多跳環(huán)境中的端到端性能.4目標(biāo)函數(shù)和控制幀格式本節(jié)在上述最優(yōu)接入策略基礎(chǔ)上設(shè)計(jì)完整的機(jī)會(huì)廣播信道接入控制協(xié)議O-BCast.O-BCast通過(guò)擴(kuò)展IEEE802.11DCF來(lái)實(shí)現(xiàn),包括沿用基于控制幀交換的狀態(tài)探測(cè)、隨機(jī)退避和NAV機(jī)制等.本節(jié)首先描述協(xié)議所需的控制幀格式,接著介紹協(xié)議的重要組成部分:探測(cè)過(guò)程、超弧性能的統(tǒng)計(jì)和閾值計(jì)算,最后給出機(jī)會(huì)廣播信道接入控制過(guò)程.4.1接收節(jié)點(diǎn)mac地址域控制幀ORTS/OCTS在802.11標(biāo)準(zhǔn)的RTS/CST幀基礎(chǔ)上做少量擴(kuò)展,如圖4所示.其中,ORTS增加一個(gè)NoR域以記錄接收節(jié)點(diǎn)(即CNH節(jié)點(diǎn))數(shù)目|J|,并將接收節(jié)點(diǎn)MAC地址域RA擴(kuò)展為多個(gè),存放CNH節(jié)點(diǎn)列表J.NoR通常限定一個(gè)最大值(如4),以防止ORTS幀長(zhǎng)和探測(cè)開(kāi)銷太高.OCTS在標(biāo)準(zhǔn)CTS幀基礎(chǔ)上增加一個(gè)TA域以標(biāo)識(shí)幀的發(fā)出節(jié)點(diǎn),為了盡量控制OCTS幀的尺寸,TA使用發(fā)出節(jié)點(diǎn)在列表J中的序號(hào)而非MAC地址.其他域含義與標(biāo)準(zhǔn)相同.4.2超弧探測(cè)的過(guò)程節(jié)點(diǎn)狀態(tài)探測(cè)發(fā)生在兩個(gè)階段:一是在傳輸業(yè)務(wù)初始階段用于估計(jì)超弧的統(tǒng)計(jì)性能,二是在傳輸過(guò)程中用于觀測(cè)超弧的即時(shí)交付能力.二者探測(cè)機(jī)制相同,均使用控制幀ORTS/OCTS握手的方式觀察接收端狀態(tài),亦即接收端能成功發(fā)回響應(yīng)則認(rèn)為其處于空閑可用狀態(tài),否則不可用.具體的,超弧(i,J)的探測(cè)過(guò)程如下:1)節(jié)點(diǎn)i在發(fā)送端媒體空閑或完成退避后廣播發(fā)送出ORTS,并設(shè)置計(jì)時(shí)器進(jìn)入等待響應(yīng)狀態(tài),計(jì)時(shí)器WaitTimer=|J|(TSIFS+TOCTS+TMaxPropDelay),其中,TSIFS,TOCTS和TMaxPropDelay分別為短幀間距、OCTS幀發(fā)送時(shí)間和最大傳播延遲;2)任意接收到ORTS幀的節(jié)點(diǎn)juf0ceJ,依照RA列表中指定的順序回送響應(yīng)幀,即等待時(shí)間jTSIFS+(j-1)TOCTS后發(fā)送OCTS,其中j表示節(jié)點(diǎn)在RA列表J中的序號(hào);3)節(jié)點(diǎn)i在WaitTimer計(jì)時(shí)器到期之前,對(duì)每個(gè)接收到的OCTS,都記錄對(duì)應(yīng)的CNH節(jié)點(diǎn)狀態(tài)為可用,即sj=1.WaitTimer到期后,設(shè)置其余CNH節(jié)點(diǎn)狀態(tài)為不可用,完成一輪探測(cè),獲知當(dāng)前超弧的交付能力.4.3pij概率分布O-BCast實(shí)現(xiàn)策略N*的一個(gè)重要前提是超弧性能的測(cè)量與統(tǒng)計(jì)推斷,主要包括超弧交付能力PiJ的概率分布、探測(cè)平均等待時(shí)間w和點(diǎn)到點(diǎn)鏈路的平均交付概率cij.其中,w和cij已有成熟的測(cè)量方法,下面將介紹對(duì)PiJ概率分布的統(tǒng)計(jì)方法.在NCOR數(shù)據(jù)傳輸開(kāi)始之前,每個(gè)參與會(huì)話的節(jié)點(diǎn)發(fā)起H輪ORTS/OCTS交換握手用于采樣CNH節(jié)點(diǎn)的狀態(tài),H稱為估計(jì)窗口.記第h次采樣獲得CNH的狀態(tài)向量為,L=|J|,那么狀態(tài)向量出現(xiàn)的概率估計(jì)為其中,1(uf0d7)為示性函數(shù),suf072為任意L維向量且suf0ce{0,1}L.有2L種可能的取值記狀態(tài)suf072下超弧的交付能力為psuf072,根據(jù)公式(2),得到PiJ概率分布的估計(jì)如果估計(jì)窗口足夠大,則估計(jì)量可以達(dá)到較高的置信水平.在此基礎(chǔ)上,O-BCast根據(jù)公式(9)和公式(10)計(jì)算出閾值以及停止規(guī)則N*.4.4狀態(tài)探測(cè)和狀態(tài)轉(zhuǎn)換O-BCast協(xié)議通過(guò)交換ORTS/OCTS觀察超弧當(dāng)前的交付能力,并根據(jù)策略N*決定是否立即發(fā)送數(shù)據(jù)幀具體的,節(jié)點(diǎn)i從網(wǎng)卡隊(duì)列中取出一個(gè)NCOR類型數(shù)據(jù)包后,首先獲取CNH節(jié)點(diǎn)集合J,封裝DATA幀,并按照以下步驟進(jìn)行信道接入控制:1)節(jié)點(diǎn)i首先檢查超弧的平均交付能力是否超過(guò)閾值uf0710:若E[mP]≥uf0710,則在發(fā)送端可用后直接發(fā)出DATA幀(即802.11DCF廣播模式);否則,生成控制幀ORTS,設(shè)置NoR和RA域?yàn)閨J|和J、Duration域?yàn)閨J|(TOCTS+TSIFS).接著發(fā)起一輪狀態(tài)探測(cè)(類似第4.2節(jié)),并啟動(dòng)計(jì)時(shí)器WaitTimer進(jìn)入等待響應(yīng)狀態(tài);2)任意接收到ORTS的CNH節(jié)點(diǎn)juf0ceJ,依序響應(yīng)OCTS,并設(shè)置Duration域?yàn)?)節(jié)點(diǎn)i在計(jì)時(shí)器WaitTimer到期后,根據(jù)此輪探測(cè)結(jié)果估算當(dāng)前的超弧交付能力然后根據(jù)N*判斷是否發(fā)送DATA幀:若mPiJ≥uf071則立即發(fā)送;否則進(jìn)行下一輪探測(cè)(退避窗口保持不變),直到發(fā)送出DATA幀.期間,若探測(cè)次數(shù)超過(guò)最大值(RetryLimit)則停止,并向上層報(bào)告MAC失敗;4)所有其他旁聽(tīng)到ORTS/OCTS的節(jié)點(diǎn)根據(jù)其中Duration域設(shè)置或更新NAV,并在NAV到期之前避免發(fā)送任何數(shù)據(jù),起到預(yù)留信道的作用.由于O-BCast協(xié)議基于簡(jiǎn)單的閾值策略,其開(kāi)銷主要來(lái)自兩個(gè)方面:一是狀態(tài)探測(cè)過(guò)程中需要多個(gè)接收端依序反饋OCTS,可能會(huì)導(dǎo)致反饋風(fēng)暴問(wèn)題;二是會(huì)話初始階段的信道測(cè)量和閾值計(jì)算所增加的開(kāi)銷.前者本文通過(guò)縮減OCTS幀尺寸和接收節(jié)點(diǎn)數(shù)目(不超過(guò)4個(gè))能夠有效控制;后者由于Mesh網(wǎng)絡(luò)中節(jié)點(diǎn)靜止且在較大的時(shí)間尺度上有穩(wěn)定的業(yè)務(wù)流特征,測(cè)量和計(jì)算的頻度很低,因此增加的網(wǎng)絡(luò)負(fù)載可以接受.5實(shí)際交付性能分析本節(jié)通過(guò)ns-2仿真實(shí)驗(yàn)評(píng)價(jià)O-BCast在多跳無(wú)線網(wǎng)絡(luò)中的性能,并與IEEE802.11DCF廣播模式(簡(jiǎn)記為CSMA)和xReady比較,其中,協(xié)議xReady(x=1,2,…)與第3節(jié)描述相同.性能評(píng)價(jià)指標(biāo)主要包括:(a)端到端吞吐量thX:NCOR單播業(yè)務(wù)的源和目標(biāo)節(jié)點(diǎn)之間單位時(shí)間成功交付并解碼的數(shù)據(jù)量.thX是本文的主要評(píng)價(jià)指標(biāo);(b)實(shí)際交付率,其中TX(i)為節(jié)點(diǎn)i在一輪仿真實(shí)驗(yàn)時(shí)間內(nèi)發(fā)出的報(bào)文總數(shù)RX(j,i)為juf0ceJ在此時(shí)間內(nèi)成功接收到來(lái)自于i的報(bào)文數(shù)量.rd反映了超弧的實(shí)際交付能力,在cij一定的情況下,rd越大,說(shuō)明發(fā)出的報(bào)文被其他傳輸干擾沖撞的比率越少;(c)平均探測(cè)次數(shù)n:發(fā)送每個(gè)數(shù)據(jù)報(bào)文所需要的平均探測(cè)輪數(shù),n≤RetryLimit,RetryLimit為最大探測(cè)次數(shù);(d)平均接入時(shí)間uf064access:從MAC隊(duì)列中取出一個(gè)待發(fā)送數(shù)據(jù)報(bào)文到將該報(bào)文發(fā)送到物理信道之間的時(shí)間差.n和uf064access均反映了信道接入延遲,與網(wǎng)絡(luò)負(fù)載和接入策略相關(guān).5.1實(shí)驗(yàn)數(shù)據(jù)的嵌入我們?cè)趎s-2(version2.34)仿真器中實(shí)現(xiàn)相關(guān)的協(xié)議,主要包括NCOR路由協(xié)議MORE、MAC協(xié)議O-BCast、xReady以及一個(gè)PHY層信道差錯(cuò)模塊,IEEE802.11DCF直接使用模擬器自帶的802.11Ext模塊.MORE采用分批網(wǎng)絡(luò)編碼方法,即源節(jié)點(diǎn)將原始消息分割成等尺寸的批(batch,實(shí)驗(yàn)中尺寸為32個(gè)報(bào)文)并對(duì)批內(nèi)報(bào)文進(jìn)行混合編碼并不斷廣播出去.中間節(jié)點(diǎn)接收并緩存屬于同一批的編碼報(bào)文,對(duì)其進(jìn)行再編碼并轉(zhuǎn)發(fā).目的節(jié)點(diǎn)解碼恢復(fù)出這批原始數(shù)據(jù)后回送ACK,源節(jié)點(diǎn)開(kāi)始下一批數(shù)據(jù)的編碼發(fā)送.由于我們關(guān)心的是底層MAC性能,因此不考慮編解碼延遲、隨機(jī)編碼系數(shù)線性相關(guān)造成的信息冗余.另外注意,吞吐量thX的計(jì)算只計(jì)入batch從源交付到目的節(jié)點(diǎn)的時(shí)間,忽略目的節(jié)點(diǎn)回送ACK的時(shí)間,因?yàn)锳CK的回送使用單播MAC,不在本文討論范疇.O-BCast和xReady在802.11Ext模塊基礎(chǔ)上擴(kuò)展實(shí)現(xiàn),二者使用相同的探測(cè)機(jī)制但依據(jù)不同的接入控制策略.其中,O-BCast中嵌入超弧性能統(tǒng)計(jì)和閾值計(jì)算兩個(gè)子模塊.統(tǒng)計(jì)模塊的初始測(cè)量持續(xù)時(shí)間4s,估計(jì)窗口H=50,ORTS幀尺寸填充到200字節(jié),以提高對(duì)超弧數(shù)據(jù)幀交付能力的測(cè)量準(zhǔn)確度;數(shù)據(jù)傳輸過(guò)程中的ORTS尺寸為46字節(jié),閾值計(jì)算子模塊則調(diào)用MATLAB工具求解公式(10)、得到閾值uf071和uf0710.此外,為了模擬有損無(wú)線通信,物理層插入一個(gè)差錯(cuò)模塊,每條點(diǎn)到點(diǎn)無(wú)線鏈路傳輸?shù)臄?shù)據(jù)幀按照一定概率(1-cij)均勻隨機(jī)出錯(cuò).其他的物理層參數(shù)依據(jù)802.11aBPSK模式,具體見(jiàn)表1.實(shí)驗(yàn)在1000muf0b41000m的區(qū)域中建立3種拓?fù)?無(wú)背景業(yè)務(wù)的簡(jiǎn)單拓?fù)銽A、有背景業(yè)務(wù)的簡(jiǎn)單拓?fù)銽B和網(wǎng)格拓?fù)銽C,分別對(duì)應(yīng)圖5(a)~圖5(c).節(jié)點(diǎn)之間有直接連線表示二者在相互通信范圍內(nèi).TA分為兩個(gè)中間節(jié)點(diǎn){a,c}和3個(gè)中間節(jié)點(diǎn){a,b,c}兩種情況;TB中背景業(yè)務(wù)i,j的放置在距離節(jié)點(diǎn)b正右方150m或300m處,其中距離150m時(shí),i能夠聽(tīng)到主業(yè)務(wù)的控制幀;而300m則超出傳輸范圍而聽(tīng)不到控制幀.每種拓?fù)渲芯到d的單播會(huì)話,源節(jié)點(diǎn)s使用CBR(constantbitrate)模型發(fā)送報(bào)文,傳輸層選用UDP協(xié)議,路由層選用MORE協(xié)議,MAC層則分別使用3種不同的廣播信道接入?yún)f(xié)議以做比較.若無(wú)其他說(shuō)明,每輪實(shí)驗(yàn)持續(xù)時(shí)間40s,報(bào)文尺寸m=2KB,傳輸質(zhì)量cij=0.6.5.2pij的累積分布實(shí)驗(yàn)首先在拓?fù)銽C中驗(yàn)證第2節(jié)假設(shè):隨機(jī)序列{PiJ(t),t=1,2,…}服從一致分布,其中,t表示探測(cè)時(shí)隙.設(shè)置CBR業(yè)務(wù)流的報(bào)文間隔Is=4ms,報(bào)文尺寸為1KB.實(shí)驗(yàn)重復(fù)100次,每次運(yùn)行20s,最后統(tǒng)計(jì)各時(shí)隙PiJ的分布.由于實(shí)驗(yàn)中各點(diǎn)到點(diǎn)鏈路同質(zhì)(即cij相同),根據(jù)公式(2)有PiJ(t)=1-(1-cij)Luf0a2,其中,Luf0a2表示處于可用狀態(tài)的CNH節(jié)點(diǎn)數(shù)量.因此,PiJ與Luf0a2一一對(duì)應(yīng),共|J|+1種取值.圖6描繪超弧suf0ae{v2,v3,v4}的PiJ(t)在不同探測(cè)時(shí)隙的累積分布函數(shù)CDF(清晰起見(jiàn),只顯示部分時(shí)隙結(jié)果).從中可見(jiàn),PiJ在各時(shí)隙的概率分布基本一致.網(wǎng)絡(luò)中其他超弧也有類似的結(jié)果.(2)適度負(fù)載實(shí)驗(yàn)實(shí)驗(yàn)在TA中觀察端到端吞吐隨網(wǎng)絡(luò)負(fù)載的變化情況,網(wǎng)絡(luò)負(fù)載通過(guò)改變CBR報(bào)文發(fā)送間隔Is來(lái)調(diào)節(jié).圖7(a)和圖7(b)分別描繪中間節(jié)點(diǎn)為{a,c}和{a,b,c}兩種場(chǎng)景下O-Bcast,xReady和CSMA所支持的端到端吞吐表2給出Is=3.5ms時(shí)網(wǎng)絡(luò)中各超弧的性能參數(shù)和O-BCast決策,表項(xiàng)含義依照之前陳述.觀察圖7發(fā)現(xiàn),各協(xié)議的性能變化趨勢(shì)相同:吞吐隨源速率增大(即隨Is減小)逐漸上升至最優(yōu)值,然后因大量擁堵和報(bào)文沖突而導(dǎo)致吞吐急劇下降進(jìn)入過(guò)飽和階段.若無(wú)特殊說(shuō)明,以下討論主要關(guān)注更具實(shí)際意義的適度負(fù)載階段,例如圖7(a)中Is=3~5ms階段.在兩個(gè)中間節(jié)點(diǎn){a,c}場(chǎng)景中,O-BCast和xReady(x=1)相對(duì)CSMA吞吐都有顯著提升,分別提高84%和72%,如圖7(a)所示.這是因?yàn)榍皟烧叩目刂茙帐謾C(jī)制有效減輕了節(jié)點(diǎn)d處的報(bào)文碰撞現(xiàn)象.例如,表2顯示,超弧auf0aed和cuf0aed在CSMA機(jī)制下平均交付能力E[P]只有大致0.1和0.2,而經(jīng)過(guò)狀態(tài)探測(cè),實(shí)際的交付率rd提高到0.6,幾乎完全避免了沖撞(因?yàn)閏ij=0.6).而O-BCast進(jìn)一步優(yōu)于xReady(x=1),是因?yàn)槌uf0ae{a,c}的O-BCast發(fā)現(xiàn)平均交付能力足夠好,即E[mP]≥uf0710,因此做出決策N*=0.與xReady相比,該決策在保證較優(yōu)平均交付能力的前提下節(jié)省了探測(cè)時(shí)間,因此端到端吞吐有進(jìn)一步的提高.當(dāng)增加一個(gè)中間節(jié)點(diǎn)后(TA場(chǎng)景2),O-BCast和xReady的性能優(yōu)勢(shì)會(huì)有所下降,但O-BCast仍明顯優(yōu)于其他接入方法,如圖7(b)所示.優(yōu)勢(shì)下降一方面因?yàn)樵搱?chǎng)景中CSMA的性能有大幅提升:節(jié)點(diǎn)b處于非常有利的位置,它的CSMA能夠較好地感知節(jié)點(diǎn)a,c的媒體狀態(tài),使得發(fā)出的報(bào)文很少遭受碰撞.例如,Is=3.5m時(shí),超弧buf0aed的交付能力接近0.6,見(jiàn)表2.另一方面,超弧suf0ae{a,b,c}中CNH節(jié)點(diǎn)增多使得探測(cè)成本開(kāi)銷增大.而O-BCast在這種狀況下讓更多的超弧使用CSMA方法(即N*=0),見(jiàn)表2.相反地,xReady在所有條件下一直探測(cè),會(huì)導(dǎo)致高負(fù)載階段由于控制幀數(shù)量過(guò)多而性能嚴(yán)重惡化.以上兩個(gè)場(chǎng)景中的結(jié)果顯示,O-BCast能夠根據(jù)網(wǎng)絡(luò)負(fù)載和超弧的信道條件做出最優(yōu)的接入決策.(3)o-bcag-csma接收量wf實(shí)驗(yàn)使用TA兩個(gè)中間節(jié)點(diǎn)場(chǎng)景評(píng)價(jià)報(bào)文尺寸和鏈路質(zhì)量對(duì)信道接入控制協(xié)議性能的影響.圖8顯示,數(shù)據(jù)報(bào)文尺寸從1KB增長(zhǎng)到3KB時(shí),O-BCast相對(duì)CSMA吞吐增益從35%提高~90%.圖9顯示,O-BCast吞吐增益隨著鏈路質(zhì)量的提高而下降.例如,當(dāng)cij從0.2提升至0.8時(shí),增益從130%下降到50%.這兩個(gè)結(jié)果及原因分別與第3節(jié)圖3(b)和圖3(d)的分析一致.(4)不同距離的增益實(shí)驗(yàn)在拓?fù)銽B中考察不同背景業(yè)務(wù)下不同接入控制協(xié)議的表現(xiàn).圖10顯示:當(dāng)距離150m時(shí),O-BCast相對(duì)CSMA的吞吐增益最為明顯,高達(dá)2倍;當(dāng)距離較遠(yuǎn)(300m)和無(wú)背景業(yè)務(wù)(距離無(wú)窮大)時(shí),吞吐量增益分別為60%和84%.其中,距離150m時(shí)增益突出,是因?yàn)楸尘肮?jié)點(diǎn)i位于b的傳輸范圍內(nèi),能夠聽(tīng)到控制幀并設(shè)置NAV從而保證主業(yè)務(wù)的狀態(tài)探測(cè)是有效的.亦即,節(jié)點(diǎn)b,d的狀態(tài)在探測(cè)期間和數(shù)據(jù)接收期間保持一致.相反的,當(dāng)距離300m時(shí)增益效果最差,其原因是i聽(tīng)不到控制幀,導(dǎo)致探測(cè)結(jié)果不能反映數(shù)據(jù)傳輸能力.可見(jiàn),O-BCast的優(yōu)勢(shì)與探測(cè)的有效性直接相關(guān).(5)仿真結(jié)果與分析實(shí)驗(yàn)最后考察O-BCast在一般多跳網(wǎng)絡(luò)TC中的表現(xiàn).在此拓?fù)渲?所有實(shí)心節(jié)點(diǎn)都被選擇參與編碼轉(zhuǎn)發(fā)報(bào)文至少經(jīng)過(guò)3跳轉(zhuǎn)發(fā)到達(dá)目的節(jié)點(diǎn),超弧的CNH數(shù)目為2~3個(gè),報(bào)文尺寸設(shè)置為1KB.圖11(a)描繪了不同接入?yún)f(xié)議的端到端吞吐量隨網(wǎng)絡(luò)負(fù)載的變化,從中看到,O-BCast仍提供最優(yōu)的端到端吞吐量,相對(duì)CSMA提高30%~5