基于免疫PID算法的無線網(wǎng)絡(luò)擁塞控制優(yōu)化

王倪

摘要：無線網(wǎng)絡(luò)由于其傳輸方式的獨(dú)特性，導(dǎo)致在有線網(wǎng)絡(luò)中表現(xiàn)良好的各種擁塞控制方法無法在無線網(wǎng)絡(luò)中得到有效的應(yīng)用，尤其是數(shù)據(jù)通信在存在干擾的情況下，丟包率遠(yuǎn)遠(yuǎn)超過有線網(wǎng)絡(luò)，因此必須加以改進(jìn)。該文對無線網(wǎng)絡(luò)擁塞控制方法進(jìn)行深入的研究，引入了工業(yè)控制領(lǐng)域常用的PID控制方式來實(shí)現(xiàn)對無線通信節(jié)點(diǎn)中的緩存隊(duì)列進(jìn)行有效的管理，并結(jié)合免疫算法實(shí)現(xiàn)了對PID控制器的參數(shù)尋優(yōu)，極大提高了控制的實(shí)時(shí)性和準(zhǔn)確性，經(jīng)過仿真驗(yàn)證，該算法在保證網(wǎng)絡(luò)吞吐量的前提下，表現(xiàn)出了更強(qiáng)的收斂性，對網(wǎng)絡(luò)數(shù)據(jù)流量變化波動的響應(yīng)速度也大大提高了，有效的調(diào)節(jié)了網(wǎng)絡(luò)擁塞現(xiàn)象，具有一定的借鑒意義和推廣價(jià)值。

關(guān)鍵詞：PID；AQM隊(duì)列控制；免疫算法；擁塞控制

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）02-0044-03

1 引言

無線局域網(wǎng)是指基于IEEE802.11協(xié)議構(gòu)建的無線網(wǎng)絡(luò)，采用無線電波為通信載體，在有限范圍內(nèi)完成數(shù)據(jù)傳輸任務(wù)。隨著智能手機(jī)及其他移動終端設(shè)備的推廣，目前無線局域網(wǎng)得到了最廣泛的應(yīng)用，覆蓋范圍越來越廣，出現(xiàn)的各種矛盾和問題也越來越多，同有線網(wǎng)絡(luò)相比，無線網(wǎng)絡(luò)最明顯的劣勢就在于其帶寬相對有限，而影響其帶寬的主要因素之一就是無線網(wǎng)絡(luò)的擁塞問題，因此，如何有效的解決網(wǎng)絡(luò)擁塞現(xiàn)象，保障無線網(wǎng)絡(luò)的帶寬不受影響，為用戶提供更快捷、更穩(wěn)定的數(shù)據(jù)通信服務(wù)已經(jīng)成為該領(lǐng)域研究的重點(diǎn)。需要明確的是，無線網(wǎng)絡(luò)在底層的組網(wǎng)方式上，存在兩種主要模式，分別是以有源基站為核心的基礎(chǔ)結(jié)構(gòu)集中式和以用戶主機(jī)為節(jié)點(diǎn)的分布對等式，也稱自組式網(wǎng)絡(luò)，本文主要針對第一種網(wǎng)絡(luò)模式進(jìn)行研究，探討其擁塞解決方案。

無線網(wǎng)絡(luò)通信具有其獨(dú)特性，由于通信環(huán)境的復(fù)雜性、通信媒介的低防御性和眾多的干擾因素的存在，使得無線網(wǎng)絡(luò)通信的質(zhì)量波動較大，從而引起通信流量的變化，在這種變化速度快、變化幅度大的環(huán)境下，若要實(shí)現(xiàn)精確的實(shí)時(shí)化擁塞控制是非常困難的，傳統(tǒng)的控制方式雖然能起到一定的效果，但隨著無線網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，通信流量的不斷增加，這些方式都出現(xiàn)了或多或少的問題，必須加以改進(jìn)。

目前在無線網(wǎng)絡(luò)擁塞控制領(lǐng)域，AQM隊(duì)列管理方法得到了廣泛的肯定，該策略屬于網(wǎng)絡(luò)層的調(diào)控方法，通過主動的丟棄數(shù)據(jù)報(bào)來確保網(wǎng)絡(luò)始終有足夠的空閑緩存來應(yīng)對可能出現(xiàn)的擁塞問題。但隊(duì)列管理模式最大的問題就是響應(yīng)速度過慢，無法應(yīng)對網(wǎng)絡(luò)中流量的突發(fā)性波動，本文針對這種情況，提出采用免疫PID算法參與到AQM隊(duì)列管理中，將PID強(qiáng)大的調(diào)節(jié)能力和免疫算法優(yōu)秀的收斂能力相結(jié)合，共同來解決無線網(wǎng)絡(luò)的擁塞問題，實(shí)現(xiàn)全局優(yōu)化。

2 主動緩存隊(duì)列管理方式

主動隊(duì)列管理模式AQM的優(yōu)勢體現(xiàn)在于該算法提前對網(wǎng)絡(luò)中數(shù)據(jù)報(bào)流量趨勢進(jìn)行預(yù)測，在問題出現(xiàn)之前就提前做好預(yù)防工作，采用一定的機(jī)制來減少緩存中隊(duì)列的長度，并提前通過減小擁塞窗口來降低各發(fā)送方的發(fā)送速率，這一算法思維被稱作早期隨機(jī)檢測RED，這也是AQM算法系列中最著名的一種。RED算法包含兩個環(huán)節(jié)，第一是計(jì)算路由器緩存中數(shù)據(jù)報(bào)隊(duì)列的隊(duì)列長度，用來判斷網(wǎng)絡(luò)中是否有出現(xiàn)擁塞的可能；第二是當(dāng)出現(xiàn)擁塞可能的時(shí)候，隨著這個可能性的增加，動態(tài)的調(diào)整丟棄隊(duì)列中數(shù)據(jù)報(bào)的概率，以緩解路由器的通信壓力。

在計(jì)算平均隊(duì)列長度的時(shí)候，RED算法采用的是加權(quán)平均法，因?yàn)楸仨毧紤]到網(wǎng)絡(luò)中數(shù)據(jù)流量的突發(fā)性特點(diǎn)，即網(wǎng)絡(luò)數(shù)據(jù)量是呈大幅度快速變化的：

[Qavg（n+1）=（1-ω）×Qavg（n）+ω×Q（n）] （1）

[ω]為權(quán)值，[Q（n）]為第n次采樣時(shí)得到的隊(duì)列長度。由上述公式可以看出，當(dāng)[ω]趨向于1時(shí)，平均隊(duì)列長度[Qavg（n+1）]的取值更多的依靠本次采樣的結(jié)果，而當(dāng)[ω]趨向于0時(shí)，平均隊(duì)列長度[Qavg（n+1）]的取值則更依賴于上一次的平均值。在實(shí)際應(yīng)用中，這一參數(shù)的設(shè)定是根據(jù)路由器根據(jù)其處理的業(yè)務(wù)特點(diǎn)來靈活設(shè)置的。

緩存平均隊(duì)列長度是反映當(dāng)前路由器緩存使用情況的指標(biāo)，用以決定丟棄數(shù)據(jù)包的概率，具體算法如下：首先RED算法設(shè)定兩個閾值[Lmin]和[Lmax]，然后路由器根據(jù)計(jì)算得到的[Qavg]同這兩個閾值進(jìn)行比較，根據(jù)比較的結(jié)果來決定丟棄報(bào)文的概率，若[Qavg]<[Lmin]，丟包概率為0；若[Qavg]>[Lmax]，丟包概率為1；而當(dāng)[Lmin]<[Qavg]<[Lmax]時(shí)，以某一動態(tài)變化的概率P對新到達(dá)的數(shù)據(jù)報(bào)執(zhí)行丟棄操作。計(jì)算公式如下：

[P=PmaxQavg-LminLmax-Lmin] （2）

[Pmax]為預(yù)設(shè)好的，在到達(dá)1之前的最大丟棄報(bào)文的概率。從公式中可以看出，丟包概率P是呈線性變化的，其趨勢圖如圖1所示。

3 免疫PID控制算法的優(yōu)化作用

3.1 增量PID控制方法

本設(shè)計(jì)采用增量式PID控制為改進(jìn)對象，所謂增量式PID，即使根據(jù)被控對象在某時(shí)間周期內(nèi)的變化率來決定下一輪需要調(diào)節(jié)的相對值，即控制被控對象的增量，氣算法流程如圖2所示。

參照其中第K輪的控制輸出為：

[u（k）=kp（error（k）+TTIj=0kerror（j）+TDT（error（k）-error（k-1）））] （3）

遞推得到第上一輪的控制輸出為：

[u（k-1）=kp（error（k-1）+TTIj=0k-1error（j）+TDT（error（k-1）-error（k-2）））] （4）

將式3與式4做相減操作，得到式5：

[Δu（k）=u（k）-u（k-1）=kp（error（k）-error（k-1）+TTIj=0kerror（j）+TDT（error（k-1）-error（k-2）））]（5）

對增量式PID算法歸并后，得到：

[Δu（k）=q0error（k）+q1error（k-1）+q2error（k-2）] （6）

其中：[q0=Kp1+TTI+TDT]；[q1=-Kp1+2TDT]；[q2=-KpTDT]

通過式6可以看出，增量式PID算法的核心依據(jù)就是通過反饋上一輪調(diào)控所產(chǎn)生的誤差量來修正下一輪調(diào)控時(shí)的輸出控制量，對于數(shù)字化設(shè)備而言，誤差值相對較小，因此上式可以簡化為只保留[e（k）、e（k-1）、e（k-2）]即可得到合理的控制增量。

3.2 免疫PID控制器的設(shè)計(jì)

現(xiàn)將免疫算法同PID控制模式相結(jié)合，按照免疫算法的相關(guān)理論，可假設(shè)：第k代的抗原個體數(shù)量為[n（k）]，增強(qiáng)細(xì)胞[TH]的輸出為[TH（k）]，則有：

[TH（k）=k1n（k）] （7）

假設(shè)抑制細(xì)胞[TS]的影響為[TS（k）]，則：

[TS（k）=k2f（Δs（k））n（k）] （8）

式中[k2是抑制因子]。[f（?）]為[TS]的抑制函數(shù)，取值在[0，1]范圍內(nèi)。

根據(jù)（7）和（8）可得，免疫系統(tǒng)接受的總刺激為：

[S（k）=TH（k）-TS（k）=（k1-k2f（Δs（k）））n（k）] （9）

因此，可將增量式PID控制器離散形式寫為：

[uPID（k）=u（k-1）+KP（e（k）-e（k-1））+KIe（k）+KD（e（k）-2e（k-1）+e（k-2））] （10）

其中P控制器的控制模式為：

[u（k）=KPe（k）] （11）

將免疫反饋引入到控制中，其規(guī)律為：

[u（k）=K（1-ηf（u（k），Δu（k）））e（k）=KPIe（k）] （12）

其中[KP1=K（1-ηf（u（k），Δu（k）））e（k）]，[K=k1]為控制反應(yīng)速度，兩者成正比增長的關(guān)系；[η=k2k1]，為控制穩(wěn)定效果，兩者成反比增大的關(guān)系。[f（?）=f（u（k），Δu（k））]表示對[TS]的抑制程度，其值的大小與機(jī)體內(nèi)抗原當(dāng)前數(shù)量以及變化率相關(guān)。

本設(shè)計(jì)采用免疫控制系統(tǒng)與PID控制器中的參數(shù)[KP]進(jìn)行動態(tài)調(diào)節(jié)，以提高系統(tǒng)的響應(yīng)速度。最終免疫PID控制器的輸出定為：

[u（k）=u（k-1）+KP1（e（k）-e（k-1））+KIe（k）+KD（e（k）-2e（k-1）+e（k-2））] （13）

上式中[KP1=K（1-ηf（u（k），Δu（k）））]

優(yōu)化后的控制系統(tǒng)的結(jié)構(gòu)如圖3所示。

4 仿真驗(yàn)證

為了更好地體現(xiàn)出對本設(shè)計(jì)的優(yōu)化效果，本實(shí)驗(yàn)選取四種不同的控制方法進(jìn)行對比分析，分別為早期隨機(jī)丟棄策略RED，PI，PID和免疫PID，實(shí)驗(yàn)環(huán)境模擬為網(wǎng)絡(luò)流量變化較大的外部環(huán)境，通過監(jiān)測數(shù)據(jù)來查看著四種優(yōu)化算法對AQM隊(duì)列的控制效果。設(shè)定FTP源為100條，分別在0s，10s，20s三個時(shí)間點(diǎn)啟動50條，25條和25條，得到的實(shí)驗(yàn)結(jié)果數(shù)據(jù)及緩存隊(duì)列的瞬時(shí)長度如表1及圖4所示：

通過以上數(shù)據(jù)和曲線對比可以明顯地看出，免疫PID控制算法明顯擁有更高的響應(yīng)速度和控制精度，比傳統(tǒng)的早期隨機(jī)丟棄策略RED有了明顯的改善和提高，同時(shí)相較于PI和PID控制方法也具有一定的優(yōu)勢，尤其是當(dāng)網(wǎng)絡(luò)流量發(fā)生大幅變化時(shí)，免疫PID能夠更早地捕捉到這一變化情況并對控制輸出做了及時(shí)的調(diào)整，無論從丟包率、隊(duì)列長度還是變化幅度上來看都實(shí)現(xiàn)了較高的控制質(zhì)量，從而驗(yàn)證了本控制方案的有效性。

5 總結(jié)

從網(wǎng)絡(luò)的整體發(fā)展趨勢上看，無線網(wǎng)絡(luò)將逐漸成為網(wǎng)絡(luò)發(fā)展的主要方向，而日益增多的用戶勢必會帶來超大規(guī)模的數(shù)據(jù)通行量，在此情況下，網(wǎng)絡(luò)的擁塞控制質(zhì)量將會成為制約無線網(wǎng)絡(luò)發(fā)展的主要瓶頸。本文提出了一種基于免疫PID算法的無線網(wǎng)絡(luò)擁塞控制方法，通過仿真實(shí)驗(yàn)證實(shí)了該算法較為有效地提高了無線網(wǎng)絡(luò)擁塞控制的實(shí)時(shí)性和精確性。相信隨著智能控制技術(shù)和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，將會進(jìn)一步提高無線網(wǎng)絡(luò)的通信效率，為廣大用戶提供更可靠、更快捷的數(shù)據(jù)通信服務(wù)。

參考文獻(xiàn)：

[1] 羅萬明，林闖，閻保平. TCP/IP擁塞控制研究[J].計(jì)算機(jī)學(xué)報(bào)，2011， 24（1）：1-18.

[2] L. Tong，V. Naware，and P. Venkitasubramanima， Signal Processing in random access[J].IEEE Signal Processing Mag.， 2015，21（5）：29-39.

[3] 劉琳瑯.無線網(wǎng)絡(luò)中控制策略的研究[D].杭州：浙江工業(yè)大學(xué)，2012.

[4] Afanasyev A， Tilley N， Reiher P， Kleinrock L. Host-to-Host Congestion Control for TCP [J] .Communications Surveys & Tutorials， 2014， 12（3）： 304-342.

[5] Brown K， Singh S. M-TCP： TCP for mobile cellular networks[J]. ACM Computer CommunicationReview， 2010， 25（5）： 19-43.

[6] 戴曉暉.人工免疫系統(tǒng)的建模研究[D].杭州：浙江大學(xué)，2011.