實時局域網(wǎng)協(xié)作對稱算法建模及性能分析

胡 艷

北京農(nóng)業(yè)職業(yè)學(xué)院信息技術(shù)系，北京 102442

0 引言

實時局域網(wǎng)的首要目標(biāo)是“實時”，因此無法容忍超過閾值的延遲。現(xiàn)有算法要么增加額外的復(fù)雜程度，要么降低信道的利用率。傳統(tǒng)的ALOHA和CSMA算法隨著試圖獲得信道節(jié)點(diǎn)的增多，沖突數(shù)量將上升并導(dǎo)致節(jié)點(diǎn)重發(fā)，此效應(yīng)將擴(kuò)散至幾乎所有信道，最終導(dǎo)致整個信道癱瘓，無法傳輸有效數(shù)據(jù)包[1-2]。

本文在分析沖突預(yù)留技術(shù)基礎(chǔ)上[3-4]，提出簡易協(xié)作對稱算法SCSA。證明了該算法在有時隙和無時隙網(wǎng)絡(luò)中對于實時環(huán)境的適應(yīng)性。

1 協(xié)作對稱算法建模

1.1 SCSA原理

簡易協(xié)作對稱算法SCSA是一種低流量的異步CSMA，當(dāng)流量增加時，該算法與時分多址TDMA算法類似[5-6]。該算法具有簡便性、魯棒性、穩(wěn)定性、響應(yīng)時間有限性等特點(diǎn)。

如果網(wǎng)絡(luò)中所有節(jié)點(diǎn)都監(jiān)控信道，能夠偵測到是否有傳輸。任一時刻，網(wǎng)絡(luò)節(jié)點(diǎn)存在一條可隨實際情況變化的命令，節(jié)點(diǎn)得到命令時就播報數(shù)據(jù)包。

如果在δ時間內(nèi)一旦偵測到媒介上的沖突（δ與端對端傳輸延遲時間τ相關(guān)，通常不超過2τ），便通過干擾頻道或播放特殊頻率信號的方式通知其他站點(diǎn)，此節(jié)點(diǎn)沖突未解決時所有其他站點(diǎn)都將停止進(jìn)一步工作。實時指令前的節(jié)點(diǎn)在站點(diǎn)間強(qiáng)加一個時間基準(zhǔn)（長度為δ的時隙），在此期間，卷入沖突的節(jié)點(diǎn)在各自時隙內(nèi)提出請求。

這個時期將持續(xù)Nδ（N為總節(jié)點(diǎn)數(shù)），直到所有沖突信息實現(xiàn)成功傳輸。此算法允許數(shù)據(jù)包長度變化，通過監(jiān)測是否有載波的方式探測數(shù)據(jù)包傳輸?shù)慕K止，載波消失時傳輸節(jié)點(diǎn)取消數(shù)據(jù)包傳輸。所有擁有數(shù)據(jù)包的節(jié)點(diǎn)都希望在當(dāng)前時隙終止時完成數(shù)據(jù)包傳輸。

SCSA采用先入先出模式，高負(fù)載條件時，每個節(jié)點(diǎn)可以不考慮當(dāng)前命令直接在各時隙參與傳輸。穩(wěn)態(tài)工作時所有節(jié)點(diǎn)的等待時間分布相同。

1.2 SCSA建模

采用具有變化服務(wù)時間的半馬爾克夫過程對SCSA進(jìn)行建模，采用計算密集型先求近似解。

用表示第i個節(jié)點(diǎn)，則有

式（1）表明Si節(jié)點(diǎn)傳輸數(shù)據(jù)包的優(yōu)先權(quán)高于Si+1節(jié)點(diǎn)。節(jié)點(diǎn)如在預(yù)設(shè)時間內(nèi)無信號輸出則表明發(fā)生沖突，沖突分辨周期CRP為沖突檢測與系統(tǒng)同步時間之和，CRP不包括使系統(tǒng)處于同步狀態(tài)所需的時間。

CRP的第一個時隙為節(jié)點(diǎn)的當(dāng)前順序頭，接下來的第i個時隙屬于第i個成員。

如果節(jié)點(diǎn)i傳輸Ti時長的包所需時隙持續(xù)時間E為

其中，i是時隙開始時準(zhǔn)備傳輸?shù)墓?jié)點(diǎn)數(shù)，當(dāng)流量較高時系統(tǒng)容量漸漸趨近于

時隙周期隨加入傳輸隊列沖突節(jié)點(diǎn)數(shù)的變化而變化。CRP只依賴網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)和時隙長度δ，因此為固定值。每個時隙只有一個CRP，每個CRP期間參與的節(jié)點(diǎn)數(shù)越少則通道利用率越低。

現(xiàn)在計算絕對下限，最差情況時一個時隙中只有兩個節(jié)點(diǎn)，此時的持續(xù)時間E為

其中，Tmin為最短數(shù)據(jù)包長度；Tmin為下一個最短數(shù)據(jù)包長度。

因此系統(tǒng)容量的絕對下界C1b為

2 穩(wěn)定性分析

針對實時通信局域網(wǎng)，穩(wěn)定性需滿足輸出為輸入的非減函數(shù)和最大平均等待時間為有限值兩個條件。

為保證等待時間有限，則要求系統(tǒng)利用率ρ小于1?？傻?/p>

將式式（37）對Q進(jìn)行歸一化處理，可得數(shù)據(jù)包到達(dá)率的約束條件為

令

式（9）和式（10）相比，前者更嚴(yán)格的將范圍限制在0～1范圍內(nèi)。

事實上，式（6）將在式（7）起作用前不成立，因此導(dǎo)致式（7）并不是真正的界限。

3 容量高負(fù)荷上界

隨著越來越多的數(shù)據(jù)包到達(dá)節(jié)點(diǎn)，獲取時隙的時間變長。因為CRP為固定值，時隙長度的增加會提高系統(tǒng)的利用率，系統(tǒng)容量被高負(fù)荷系統(tǒng)容量Ch1限制，Ch1為

為給到達(dá)率相等的所有節(jié)點(diǎn)設(shè)置一個上限，使用相同模型重新定義服務(wù)時間r為

如果只有一個節(jié)點(diǎn)試圖獲得數(shù)據(jù)則要求系統(tǒng)模型中時隙持續(xù)時間為1，否則持續(xù)時間大于1。如果隊列中剩下N個客戶，則為它們服務(wù)所需時間為

圖1 SCSA性能界限

圖2 平均等待時間上限和下限

當(dāng)所有節(jié)點(diǎn)到達(dá)率相等時，實際的系統(tǒng)利用率和平均等待時間將介于求得的上限值和下限值之間。

當(dāng)節(jié)點(diǎn)數(shù)為32，δ=0.01時，SCSA的性能界限如圖1所示。圖2為節(jié)點(diǎn)數(shù)和δ與圖1相同時，系統(tǒng)數(shù)據(jù)包在節(jié)點(diǎn)處平均等待時間的上限和下限，λ為總平均到達(dá)率的函數(shù)。仿真表明隨著系統(tǒng)負(fù)載的增加，節(jié)點(diǎn)平均到達(dá)率相同時，曲線漸漸接近于容量上限而不是下限。驗證了算法性能接近TDMA。

當(dāng)節(jié)點(diǎn)數(shù)為16、32、48和64，δ=0.1時的系統(tǒng)利用率見圖3。由圖知：當(dāng)λ＜0.08時（歸一化），最壞情況的平均等待時間為4個數(shù)據(jù)包的傳輸時間，且該系統(tǒng)容量的退化情況不會低于0.85。

圖3 系統(tǒng)利用率

4 結(jié)論

對不要求完全同步網(wǎng)絡(luò)的沖突保留算法進(jìn)行變換提出簡單的協(xié)作對稱算法SCSA。分析了SCSA在節(jié)點(diǎn)處有/無緩沖能力的情況。此算法遵守先進(jìn)先出原則，在高通信量傳輸時性能接近TDMA。此算法數(shù)據(jù)包的傳輸時間變化較小，結(jié)合強(qiáng)加的延時上限，使得SCSA算法在實時通信方面盡顯優(yōu)勢。

[1]L.Kleinrock，S.S.Lain, Packet Switching in a Multi-Access Broad-cast Channel: Performance Evaluation[J].IEEETransactions on Communications，1975，COM 23：410-423.

[2]何偉,南敬昌,潘峰.改進(jìn)的動態(tài)p-堅持CSMA協(xié)議[J].計算機(jī)工程，2010，36(21)：118-120.

[3]R. H. Sherman, M.G.Gable, G.McClure.Concepts,Strategies for Local Data Network Architectures[J].Data Communications，1978，7(7):39-49.

[4]Leonard Kleinrock and Simon Lam.Packet switching in a multiaccess broadcast channel: performance evaluation[J].IEEE Trans.Communications.1975, COM-23(4)：410-423.

[5]丁心泉, 吳介一.RLAN:一種面積CIMS的實時局域網(wǎng)[J].小型微型計算機(jī)系統(tǒng)，1997，18(8)：19-22.

[6]馬錦榮.一種短距離無線傳輸?shù)腃SMA/CA協(xié)議實現(xiàn)方法[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2010(5)：18-19.