曹 寶,郭 爽,劉心迪
(中國電子科技集團(tuán)公司第三十研究所,四川成都610041)
基于混沌時間序列預(yù)測模型的改進(jìn)CFDAMA協(xié)議*
曹 寶,郭 爽,劉心迪
(中國電子科技集團(tuán)公司第三十研究所,四川成都610041)
混合自由/按需分配多址接入?yún)f(xié)議(CFDAMA)將按需分配方式和自由分配方式相結(jié)合,可以確保資源分配的合理性和公平性。在總結(jié)現(xiàn)有CFDAMA協(xié)議的基礎(chǔ)上,以提高網(wǎng)絡(luò)吞吐量,降低平均時延為目標(biāo),提出了一種CFDAMA改進(jìn)協(xié)議,采用基于最大Lyapunov指數(shù)的信源預(yù)測模型對用戶在下一時刻發(fā)送隊列中即將到來的突發(fā)數(shù)據(jù)分組進(jìn)行預(yù)測,使用戶在發(fā)送時隙請求到獲得時隙分配之間的數(shù)據(jù)分組能夠及時的發(fā)送出去,減小平均端到端時延。
多址接入 CFDAMA協(xié)議 信源預(yù)測 突發(fā)數(shù)據(jù)
衛(wèi)星通信系統(tǒng)的一個基本特點(diǎn)就是,處在一顆衛(wèi)星波束覆蓋區(qū)域內(nèi)的所有用戶都能向衛(wèi)星收發(fā)信號,即具有多址接入能力,多址接入技術(shù)是指多個用戶利用同一個傳播信道在同一時間進(jìn)行相互通信的傳輸方式。多址接入技術(shù)根據(jù)信號分割原理把頻率資源按照頻帶、時間、碼型等參數(shù)分成相互正交或準(zhǔn)正交的信道,并把這些信道以適當(dāng)?shù)姆绞椒峙浣o需要進(jìn)行接入的用戶。多址接入能力是衛(wèi)星通信的一個特點(diǎn),必須加以實(shí)施必要的控制策略,使其能夠有效利用現(xiàn)有的頻譜和系統(tǒng)資源,因此,對多址接入技術(shù)的研究主要在于能夠?qū)崿F(xiàn)用戶的實(shí)時接入和數(shù)據(jù)業(yè)務(wù)的合理分配,在保證QoS的同時使得衛(wèi)星信道利用率達(dá)到最佳。
1.1 協(xié)議描述
在寬帶衛(wèi)星通信系統(tǒng)中,CFDAMA協(xié)議的資源調(diào)度器工作在集中控制方式,稱為集中控制調(diào)度器,考慮到往返時延RTD(Round Trip Delay),CFDAMA的資源調(diào)度器通常放置在衛(wèi)星上。衛(wèi)星資源調(diào)度器中存放了兩張表,按需分配表(表1)和自由分配表(表2),按需分配表包括當(dāng)前申請了預(yù)約時隙資源的用戶ID號、申請的時隙資源數(shù)以及每個用戶實(shí)際得到的分配時隙數(shù)目;自由分配表包括衛(wèi)星通信系統(tǒng)中所有的活躍用戶終端ID號以及衛(wèi)星為每個用戶終端平均分配的時隙數(shù)[1],其中X≤N。
表1 按需分配表Table 1 On-demand allocation table
表2 自由分配表Table 2 Free allocation table
衛(wèi)星在收到用戶第一次發(fā)出的上行幀之后,資源調(diào)度器從當(dāng)前幀的最開始階段進(jìn)行處理,首先計算系統(tǒng)中所有的用戶終端,將這些用戶的ID號寫入自由分配表中,分析上行幀中有哪些用戶申請了預(yù)約時隙資源請求,將這些用戶的ID號以及申請的預(yù)約時隙請求數(shù)目寫入按需分配表中。然后,資源調(diào)度器在當(dāng)前幀中優(yōu)先處理按需分配表,以先到先服務(wù)(FIFS)的形式為按需分配表中的用戶分配時隙,如果當(dāng)前用戶有a個預(yù)約請求時隙數(shù)目,在未超過系統(tǒng)總?cè)萘康臈l件下為用戶分配a個時隙,并將該用戶從按需分配表中刪除,同時在自由分配表中將該用戶移到表的尾端,這樣一直持續(xù)到按需分配表中沒有預(yù)約申請的用戶。接著,資源調(diào)度器開始處理自由分配表,以輪詢的方式從自由分配表的頭部依次為所有活躍的用戶分配一個時隙,目的是讓每一個用戶都能獲得公平的剩余時隙分配,同時給那些沒有發(fā)出預(yù)約請求的用戶較高的剩余時隙分配優(yōu)先權(quán)。當(dāng)輪詢完一次后如果當(dāng)前幀中還有剩余時隙,則立即進(jìn)行下一次的輪詢,直到將幀中的剩余時隙分配完,此時星上調(diào)度器處理完畢,將分配好的時隙裝入下行幀中發(fā)送給各個用戶,當(dāng)下一個上行幀到來的時候衛(wèi)星再次更新按需分配表和自由分配表中的條目進(jìn)行資源分配[2]。另外,如果在按需分配過程中已經(jīng)超出當(dāng)前幀的系統(tǒng)容量,則將剩余按需分配的用戶申請累計至下一幀進(jìn)行處理,此時也不會進(jìn)行自由分配過程。
1.2 問題研究
目前,國內(nèi)外學(xué)者對CFDAMA協(xié)議進(jìn)行了相應(yīng)的改進(jìn),國外的學(xué)者如Mitchell和Tozer等人在提出了一系列改進(jìn)協(xié)議,如CFDAMA-CR、CFDAMA-RR等,對用戶公平接入和接入時延控制做了相關(guān)優(yōu)化; Neale等根據(jù)CFDAMA中自由分配時隙的不同調(diào)度策略,深入分析了TCP/IP協(xié)議在CFDAMA下的性能。國內(nèi)的學(xué)者如Yuheng Li等人提出了基于反饋預(yù)約的CFDAMA優(yōu)化分配協(xié)議CFDAMA-PRR,在為申請資源預(yù)約的節(jié)點(diǎn)分配了時隙之后,資源調(diào)度器將剩余的時隙分配給接收了TCP分組的接入節(jié)點(diǎn);周熙等人提出了關(guān)于CFDAMA協(xié)議的改進(jìn)方法CFDAMA-PR,通過計算用戶端發(fā)送隊列數(shù)據(jù)分組的堆積狀況,采用加權(quán)的方式向星上調(diào)度器發(fā)送更多的預(yù)約時隙請求,以及CFDAMA-CFA[3],根據(jù)限制條件對自由分配部分采用輪詢或者權(quán)重方式進(jìn)行分配。然而,這些改進(jìn)協(xié)議大多是在Constant信源或者低突發(fā)的Poisson信源模型下進(jìn)行傳輸,信源傳播方式較為平穩(wěn),而如今的數(shù)據(jù)傳輸業(yè)務(wù)多為突發(fā)性較強(qiáng)且不能準(zhǔn)確統(tǒng)計的,這些具有突發(fā)特征的數(shù)據(jù)業(yè)務(wù)通常用ON-OFF信源模型來表示,在業(yè)務(wù)突發(fā)性較大的情況下,用戶發(fā)送的預(yù)約時隙請求也存在著很強(qiáng)的不確定性[4]。對于CFDAMA來說,由于預(yù)約時隙請求方式的限制,在ON-OFF信源高信道負(fù)荷的時候,用戶在接入的公平性和接入時延方面存在著很大的影響,因此,如何保證用戶在突發(fā)信源模型下的時延/吞吐量性能,成為本文研究的一個很重要的問題。
2.1 設(shè)計思想
在用戶時隙申請方面,CFDAMA改進(jìn)協(xié)議采用了一種基于最大Lyapunov指數(shù)的混沌時間序列預(yù)測模型[5]。通常情況下,用戶在申請預(yù)約時隙后,從發(fā)出預(yù)約時隙申請到獲得相應(yīng)的分配時隙還有一段時間T,而在T時間內(nèi)如果用戶仍然處于持續(xù)突發(fā)狀態(tài),突發(fā)信源將會有一定數(shù)量的數(shù)據(jù)分組到達(dá)發(fā)送隊列中,現(xiàn)有的協(xié)議并沒有對這段時間內(nèi)的突發(fā)數(shù)據(jù)分組進(jìn)行處理,隨著信道負(fù)荷的不斷增大,會造成在下一個預(yù)約時隙申請階段數(shù)據(jù)分組在隊列中的不斷堆積,平均時延性能下降。而通過預(yù)測的方法,如果當(dāng)前用戶處于突發(fā)信源的ON階段并且有預(yù)約時隙的申請需求,那么該用戶在申請預(yù)約時隙的同時對下一時刻將要到來的突發(fā)數(shù)據(jù)分組量進(jìn)行預(yù)測,總共發(fā)出的時隙申請數(shù)為當(dāng)前的預(yù)約時隙數(shù)加上通過預(yù)測算法得到的下一時刻預(yù)約時隙數(shù),這樣可以有效的降低數(shù)據(jù)分組在隊列中的堆積。
2.2 信源預(yù)測模型
近年來,對大量的高速網(wǎng)絡(luò)業(yè)務(wù)分組數(shù)據(jù)的統(tǒng)計研究表明,網(wǎng)絡(luò)數(shù)據(jù)流具有明顯的自相似特性,而自相似也是混沌的一個重要特性,因此利用混沌時間序列預(yù)測模型能夠很好的預(yù)測網(wǎng)絡(luò)中的實(shí)際業(yè)務(wù)流量。本文采用的整個預(yù)測模型構(gòu)建分為3個階段:
第一個階段為相空間重構(gòu),采用坐標(biāo)延遲的方法,通過一維時間序列dN的不同延遲來構(gòu)造實(shí)際系統(tǒng)的相空間,我們假設(shè)m為嵌入維數(shù),τ為時間延遲,當(dāng)前的時間序列為d1,d2,…dN,該序列可以表示為m維相空間中N-(m-1)τ個相點(diǎn),則第i個相點(diǎn)可由式(1)得到。
有關(guān)τ與m的選取方法,目前主要有兩種觀點(diǎn)。一種觀點(diǎn)認(rèn)為τ與m是相互獨(dú)立的,先求出τ后再對m的取值進(jìn)行合理的選擇,這樣做是為了使得原有的時間序列XN經(jīng)過τ的延遲后可以當(dāng)成獨(dú)立的坐標(biāo)。另一種觀點(diǎn)認(rèn)為τ與m是相互聯(lián)系的, Kugiumtzis提出了嵌入時間窗法[6],認(rèn)為時間窗的長度是考慮τ與m的重要因素,并提出嵌入時間窗口τw=(m-1)τ的概念;Kim等人在嵌入時間窗法的基礎(chǔ)上提出了使用關(guān)聯(lián)積分同時估計出時延與嵌入窗的方法,稱為C-C方法[7]。本文參照文獻(xiàn)[5],根據(jù)嵌入時間窗τw=(m-1)τ不變的概念,采用均勻嵌入方式,并選取m=4,τ=1作為相空間重構(gòu)的參數(shù),這種方法能夠簡化相空間重構(gòu)時參數(shù)的選取過程。
第二個階段為最大Lyapunov指數(shù)的計算?;煦缦到y(tǒng)對初始值有著極為敏感的察覺性,因此就算兩個初始值相差很小,但隨著時間的推移這兩個初始值產(chǎn)生的軌跡也會出現(xiàn)以指數(shù)方式分離的狀態(tài),而Lyapunov指數(shù)就是通過定量的方式來描述這一現(xiàn)象,Lyapunov指數(shù)代表系統(tǒng)在相空間中相鄰軌道之間發(fā)散或收斂的平均指數(shù)率。而在所有Lyapunov的指數(shù)中,只要有大于零的值出現(xiàn),那么整個系統(tǒng)都將是混沌的。因此在實(shí)際應(yīng)用中只要計算出最大Lyapunov指數(shù)的值,并通過觀察計算出的值即可判斷系統(tǒng)是否混沌。另外,在應(yīng)用中計算最大值也要比計算所有的值更加容易和精確。
本文采用一種軌道跟蹤算法來計算最大Lyapunov指數(shù)[8]。在滿足約束條件(m-1)τ<<α(m-1)τ,1<α<10的前提下,根據(jù)式(2.2)求得Xi的最近相鄰點(diǎn)Xnear_i。其中j<N-(m-1)τ,‖·‖為歐式范數(shù),‖Xj-Xi‖代表Xj和Xi之間的歐幾里德距離。約束條件(m-1)τ<能夠保證Xi和其相鄰點(diǎn)Xnear_i在不同的軌道上,而<α(m-1)τ則能夠保證計算Lyapunov指數(shù)的次數(shù)在合理的范圍之內(nèi),減小了系統(tǒng)的負(fù)荷。α過大會造成相鄰點(diǎn)的相關(guān)性變小,過小則會造成相鄰點(diǎn)的噪聲影響變大,因此取約束條件1<α<10能夠保證相鄰點(diǎn)之間良好的系統(tǒng)性能。
由此,在設(shè)定約束條件1≤h≤N-(m-1)τ-i的情況下通過式(3)得到Xi在擴(kuò)展的最大方向上的Lyapunov指數(shù)。約束條件保證了演化之后的最近相鄰點(diǎn)仍能夠保持在各自的軌道之上且Xi和其相鄰點(diǎn)Xnear_i的夾角不會太大。
最后通過式(4)求出相點(diǎn)的平均最大Lyapunov指數(shù)值。
第三個階段為信源預(yù)測,由前兩個階段的推斷可得,當(dāng)前相空間中最后一個相點(diǎn)由式(5)得到。
推導(dǎo)可得:
由XN-(m-1)τ的最近相鄰點(diǎn)為Xnear,我們可以得知XN+1-(m-1)τ的最近相鄰點(diǎn)為Xnear+1,并且因為Lyapunov指數(shù)為空間中一步變換的指數(shù)增長率,所以得到式(7)。由此可通過前N個時間序列d1,d2,…dN求得第N+1個時間序列dN+1的值。
對突發(fā)信源預(yù)測的實(shí)際操作中設(shè)置如下參數(shù):
突發(fā)狀態(tài)下用戶預(yù)約時隙請求周期數(shù):N;每個預(yù)約時隙請求周期內(nèi)數(shù)據(jù)分組到達(dá)數(shù):w;第i個用戶當(dāng)前需要的預(yù)約時隙數(shù):reqslots_i;第i個用戶通過信源預(yù)測模型獲得的下一時刻預(yù)約時隙數(shù):foreslots_i。
如果某用戶處于突發(fā)數(shù)據(jù)狀態(tài),在每次發(fā)送預(yù)約時隙請求的時候,用戶首先獲取當(dāng)前周期內(nèi)的預(yù)約時隙數(shù)reqslots_i,并計算得到隊列在突發(fā)狀態(tài)下N個預(yù)約時隙請求周期內(nèi)每次的數(shù)據(jù)分組到達(dá)數(shù)w,w的計算方法在設(shè)計思想中已經(jīng)介紹,此處不再贅述。然后,根據(jù)式(1)和參數(shù)m=4,τ=1得到突發(fā)分組數(shù)相空間的相點(diǎn)Xl={wl,wl+1,wl+2,wl+3},l=1,2,…,N-3,從而相空間中的最后一個相點(diǎn)為XN-3= {wN-3,wN-2,wN-1,wN},由式(6)可以得到一步變換后的相點(diǎn)XN-2={wN-2,wN-1,wN,wN+1},其中wN+1即為所要預(yù)測的下一個周期的預(yù)約請求時隙數(shù)foreslots_i。在求最大Lyapunov指數(shù)時,假定選取參數(shù)α=3,則式(2)的約束條件為l-9<j<l-3,+3<j<l+9,j<N-3,由此求出每一個相點(diǎn)的最近鄰點(diǎn)Xnear_l,包括XN-3的最近鄰Xnear和XN-2的最近鄰Xnear+1。最后根據(jù)式(3)求出滿足約束條件1≤h≤N-3-l每一個相點(diǎn)的Lyapunov指數(shù)λ(l),并計算出平均值λ,通過式(7)得出wN+1的值。此時用戶通過捎帶的方式將總共的預(yù)約時隙數(shù)通過上行鏈路數(shù)據(jù)幀發(fā)送給星上集中調(diào)度器。
3.1 信源模型
本文采用Pareto ON-OFF信源模型進(jìn)行性能分析。
ON-OFF信源模型的狀態(tài)轉(zhuǎn)換如圖1,信源模型由多個獨(dú)立的ON和OFF信源持續(xù)時間構(gòu)成。數(shù)據(jù)分組產(chǎn)生過程在ON狀態(tài)和OFF狀態(tài)之間不斷跳變,在ON狀態(tài)下產(chǎn)生數(shù)據(jù)分組,轉(zhuǎn)移概率為β1, OFF狀態(tài)下無數(shù)據(jù)分組產(chǎn)生,轉(zhuǎn)移概率為β2。在ON狀態(tài)條件下的數(shù)據(jù)分組大小由某種既定的分布函數(shù)來確定,分組到達(dá)的間隔時間同樣服從某種分布條件。
圖1 ON-OFF信源模型Fig.1 ON-OFF source model
3.2 仿真結(jié)果
采用OPENT仿真軟件,將基本的CFDAMAPA、CFDAMA-PB和改進(jìn)的CFDAMA協(xié)議在相同網(wǎng)絡(luò)模型和測試參數(shù)的條件下進(jìn)行對比仿真測試,此時接入用戶數(shù)目固定。首先,在信道負(fù)荷變化條件下測試平均端到端時延,測試結(jié)果如圖2所示,仿真環(huán)境中的信道負(fù)荷定義為信道內(nèi)數(shù)據(jù)的比特數(shù)除以信道總的時隙數(shù),平均時延單位為秒。
圖2 平均端到端時延/吞吐量性能測試Fig.2 Mean end-to-end delay/throughput performance test
其次,在信道負(fù)荷變化條件下測試隊列中的分組平均累積數(shù),測試結(jié)果如圖3所示。
圖3 隊列分組平均累積數(shù)/吞吐量性能測試Fig.3 Mean accumulation/throughput performance of queue packets test
仿真測試結(jié)果表明,在信道負(fù)荷較小的情況下, 3種接入方式表現(xiàn)出相似的平均端到端時延性能,這是因為在信道負(fù)荷不高的情況下,信源的突發(fā)性不強(qiáng),到達(dá)隊列中的分組數(shù)目也較少,因此發(fā)出預(yù)約時隙請求的用戶也不多,星上調(diào)度器主要工作在自由分配狀態(tài),一幀中有足夠的時隙可供用戶進(jìn)行數(shù)據(jù)分組的轉(zhuǎn)發(fā)。而當(dāng)信源突發(fā)性增強(qiáng)、信道負(fù)荷增大時,系統(tǒng)中發(fā)出預(yù)約時隙請求的用戶數(shù)也不斷增大,而這些用戶在每個幀到來時的預(yù)約時隙請求又帶有很強(qiáng)的不確定性,普通CFDAMA協(xié)議沒有對突發(fā)數(shù)據(jù)源采取一定的措施,在高突發(fā)的情況下只能對當(dāng)前隊列中的數(shù)據(jù)分組進(jìn)行計算,造成了分組的不斷累積和時延增大。而改進(jìn)協(xié)議通過對信源模型進(jìn)行預(yù)測,如果下一時刻有突發(fā)的數(shù)據(jù)分組到來,則在當(dāng)前時刻發(fā)出的預(yù)約請求時隙為隊列中現(xiàn)有的數(shù)據(jù)分組更多和預(yù)測產(chǎn)生的數(shù)據(jù)分組,這樣就可以在下一時刻到來時隊列中有更多一部分?jǐn)?shù)據(jù)分組被發(fā)送出去。
本文通過分析當(dāng)前衛(wèi)星通信系統(tǒng)中的CFDAMA接入?yún)f(xié)議,并總結(jié)其優(yōu)缺點(diǎn),提出了基于混沌時間序列預(yù)測模型的改進(jìn)CFDAMA協(xié)議。該協(xié)議采用基于最大Lyapunov指數(shù)的混沌時間序列信源預(yù)測模型,在現(xiàn)有預(yù)約時隙申請的基礎(chǔ)上通過對下一時刻突發(fā)信源的預(yù)測來獲取更多的時隙分配請求,以減小數(shù)據(jù)分組在發(fā)送隊列中的堆積。最后,在突發(fā)信源模型下的實(shí)際應(yīng)用測試結(jié)果表明,改進(jìn)CFDAMA協(xié)議通過預(yù)測算法準(zhǔn)確獲取時隙分配,在突發(fā)增強(qiáng)、信道負(fù)荷加大的情況下降低接入時延,提高協(xié)議性能。
[1] ZHOU X,JIA S L,SHE Y.Delay Performance of the Improved CFDAMA MAC Protocol via Satellite[J]. Journal of Nanjing University of Science and Technology, 2005,1(29):77-80.
[2] 胡圓圓,宋高俊.Ka頻段下多波束衛(wèi)星通信的資源分配[J].通信技術(shù),2013,46(10):22-25.
HU Y Y,SONG G J.Resource Allocation of Ka Band Multi-beam Satellite Communication[J].Communications Technology,2013,46(10):22-25.
[3] 佘陽,周熙,周山泉,等.GEO衛(wèi)星網(wǎng)絡(luò)CFDAMA—CFA協(xié)議性能分析[J].無線電通信技術(shù),2005,31 (05):12-13.
SHE Y,ZHOU X,ZHOU S Q,etc.Performance Analysis of CFDAMA-CFA Protocol in GEO Satellite Network[J]. RadioCommunications technology,2005,31(5):12-13.
[4] WALKER T O,TUMMALA M,MCEACHEN J.Flow-Specific Medium Access for Networked Satellite System [J].IEEE Systems Journal,2011,5(03):427-434.
[5] 李斗,姬冰輝,王峰,等.基于混沌預(yù)測的寬帶DVBRCS衛(wèi)星接入信道動態(tài)分配方案研究[J].電子與信息學(xué)報,2008,30(03):607-611.
LI D,JI B H,WANG F,etc.The Dynamic Allocation of Broadband DVB-RCS Satellite Access Channel Based on Chaotic Prediction[J].Journal ofElectronics&Information Technology,2008,30(3):607-611.
[6] KUGIUMTZIS D.State Space Reconstruction Parameters in the Analysis of Chaotic Time Series---the Role of the Time Window Length[J].Physical D:Nonlinear Phenomena,1996,95(01):13-28.
[7] KIM H S,EYKHOLT R,SALAS J D.Nonlinear Dynamics,Delay Times,and Embedding Windows[J].Physica D:Nonlinear Phenomena,1999,127(01):48-60.
[8] 楊紹清,章新華,趙長安.一種最大李雅普諾夫指數(shù)估計的穩(wěn)健算法[J].物理學(xué)報,2000,49(04):636-640.
YANG S Q,ZHANG X H,ZHAO C A.An Robust Algorithm Based on Largest Lyapunov Exponent Estimate[J]. Acta Physica Sinica,2000,49(04):636-640.
CAO Bao(1981-),male,B.Sci.,engineer,majoring in network and communication device R&D.
郭 爽(1981—),男,碩士,工程師,主要研究方向為網(wǎng)絡(luò)與通信設(shè)備研發(fā);
GUO Shuang(1981-),male,M.Sci.,engineer,majoring in network and communication device R&D.
劉心迪(1988—),男,碩士,助理工程師,主要研究方向為網(wǎng)絡(luò)與通信設(shè)備研發(fā)。
LIU Xin-di(1988-),male,M.Sci,assistant engineer, majoring in network and communication device R&D.
Improved CFDAMA Protocol based on Chaotic Time Series Prediction Model
CAO Bao,GUO Shuang,LIU Xin-di
(No.30 Institute of CETC,Chengdu Sichuan 610041,China)
Combined Free/Demand Assignment Multiple Access(CFDAMA)integrates assignment-on-demand with free assignment to ensure the rationality and equity of resource assignment.Based on current CFDAMA protocol,targeting at improving network throughput and reducing average time-delaying,this paper proposes an improved CFDAMA protocol,which adopts the source prediction model with the largest Lyapunov exponent to predict burst data packets in users'transmit queue which would be sent out in next moment,thus making the data packets within the period from sending timeslot request to timeslot acquisition be sent timely and reducing the average end-to-end time-delaying.
multiple access;CFDAMA protocol;source prediction;burst data
TN927
A
1002-0802(2014)10-1173-05
10.3969/j.issn.1002-0802.2014.10.013
曹 寶(1981—),男,學(xué)士,工程師,主要研究方向為網(wǎng)絡(luò)與通信設(shè)備研發(fā);
2014-07-11;
2014-09-01 Received date:2014-07-11;Revised date:2014-09-01