基于W LAN流調(diào)控機(jī)制的無線自組織網(wǎng)絡(luò)資源調(diào)度算法研究

郝 平（陜西工業(yè)職業(yè)技術(shù)學(xué)院信息工程學(xué)院，陜西咸陽(yáng) 712000）

?

基于W LAN流調(diào)控機(jī)制的無線自組織網(wǎng)絡(luò)資源調(diào)度算法研究

郝 平
（陜西工業(yè)職業(yè)技術(shù)學(xué)院信息工程學(xué)院，陜西咸陽(yáng) 712000）

摘 要：為解決WLan資源調(diào)度算法中網(wǎng)絡(luò)資源受限與調(diào)度不良，難以實(shí)現(xiàn)有效資源控制等問題，本文提出了一種基于WLAN流調(diào)控機(jī)制的無線自組織網(wǎng)絡(luò)資源調(diào)度技術(shù)。首先，結(jié)合梯度概念對(duì)資源量、接入帶寬有效占有量以及接入點(diǎn)資源等指標(biāo)進(jìn)行排序處理，按照用戶訪問資源最佳及接入帶寬質(zhì)量最低的原則進(jìn)行反復(fù)匹配；然后基于資源訪問概率，當(dāng)僅當(dāng)訪問概率大于一定數(shù)值時(shí)方提供用戶訪問服務(wù)，從而實(shí)現(xiàn)各個(gè)資源流在網(wǎng)絡(luò)中的均衡化分配及調(diào)度。仿真實(shí)驗(yàn)表明：與RRPS、PR_RRPS算法相比，所提機(jī)制具備更好的擁塞控制及資源調(diào)度性能。

關(guān)鍵詞：無線自組織網(wǎng)絡(luò)；資源調(diào)度；流調(diào)控；帶寬占有；均衡分配；接入控制

1　引 言

隨著W lan技術(shù)的不斷發(fā)展，各種智能化接入終端技術(shù)也日新月異，采取諸如wifi技術(shù)等將智能用戶終端設(shè)備接入到無線網(wǎng)絡(luò)之內(nèi)，且提供相應(yīng)帶寬占用資源的無線服務(wù)能力，成為一種有前途的用戶服務(wù)業(yè)務(wù)［1］。不過由于用戶終端接入往往存在一定的流動(dòng)性，難以實(shí)現(xiàn)對(duì)用戶WLan流的有效調(diào)度和利用，因此需要使用一些網(wǎng)絡(luò)資源調(diào)度機(jī)制，以便滿足用戶對(duì)諸如高清視頻業(yè)務(wù)等高質(zhì)量無線移動(dòng)業(yè)務(wù)的滿足［2］。

由WLan技術(shù)存在不穩(wěn)定性，且在資源調(diào)度過程中以流形式對(duì)網(wǎng)絡(luò)業(yè)務(wù)資源進(jìn)行調(diào)度。因此，諸多學(xué)者通過一定手段對(duì)用戶資源流進(jìn)行調(diào)度，實(shí)現(xiàn)網(wǎng)絡(luò)環(huán)境對(duì)用戶資源的定向匹配［3］。如Ahlswede R［4］等提出了一種基于隨機(jī)資源流檢測(cè)的用戶資源調(diào)度策略，采取通過隨機(jī)發(fā)送用戶資源調(diào)度指令，以便按照最低服務(wù)保障質(zhì)量實(shí)現(xiàn)對(duì)用戶資源的有效調(diào)度，在仿真過程中實(shí)現(xiàn)了低烈度用戶資源競(jìng)爭(zhēng)環(huán)境下的資源調(diào)度。但是，由于該策略沒有考慮到wifi環(huán)境中用戶資源調(diào)度的烈度極高，因此在此等用戶環(huán)境之下資源往往調(diào)度受阻。Niu B［5］等提出了一種基于擁塞控制機(jī)制的局域網(wǎng)資源調(diào)度技術(shù)，驗(yàn)證了在實(shí)現(xiàn)擁塞有效控制的基礎(chǔ)上網(wǎng)絡(luò)有效帶寬資源對(duì)用戶資源的近似100%的全覆蓋，仿真實(shí)驗(yàn)表明當(dāng)無線局域網(wǎng)環(huán)境處于靜止?fàn)顟B(tài)時(shí)能夠有效的滿足用戶資源的調(diào)度。然而，該技術(shù)未能考慮網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性，當(dāng)用戶終端設(shè)備處于高速移動(dòng)狀態(tài)時(shí)，隨著網(wǎng)絡(luò)擁塞效應(yīng)的不斷增加，往往導(dǎo)致嚴(yán)重的用戶體驗(yàn)下降現(xiàn)象的發(fā)生。羅守山［6］等針對(duì)WLAN網(wǎng)絡(luò)中用戶終端分布的隨機(jī)性，提出可以根據(jù)隨機(jī)分布的模型來實(shí)現(xiàn)網(wǎng)絡(luò)資源對(duì)用戶的匹配，實(shí)現(xiàn)了在小范圍內(nèi)網(wǎng)絡(luò)資源的高性能匹配調(diào)度。然而，由于該算法難以適應(yīng)擾動(dòng)因素較強(qiáng)的情況下網(wǎng)絡(luò)資源調(diào)度的特點(diǎn)，導(dǎo)致當(dāng)用戶資源流數(shù)量急劇增加時(shí)，網(wǎng)絡(luò)擁塞現(xiàn)象也非常突出，降低了用戶訪問體驗(yàn)。

為了解決上述不足，提出了一種基于WLAN流調(diào)控機(jī)制的無線自組織網(wǎng)絡(luò)資源調(diào)度技術(shù)，采取基于梯度和有效接入帶寬的排列策略，對(duì)網(wǎng)絡(luò)資源流接入時(shí)間的長(zhǎng)度及資源進(jìn)行控制；并在控制過程中對(duì)難以滿足策略的路數(shù)進(jìn)行預(yù)警，從而實(shí)現(xiàn)了資源在網(wǎng)絡(luò)中的均衡化調(diào)度。最后測(cè)試了本文算法的調(diào)度性能。

2　本文無線自組織網(wǎng)絡(luò)資源調(diào)度算法

2.1網(wǎng)絡(luò)資源流轉(zhuǎn)移排序與計(jì)算

當(dāng)用戶處于WLAN網(wǎng)絡(luò)進(jìn)行用戶體驗(yàn)時(shí)，對(duì)于資源的調(diào)度請(qǐng)求是以流的形式存在，使其可以使用一定的調(diào)度技術(shù)實(shí)現(xiàn)匹配［7］。如果當(dāng)前網(wǎng)絡(luò)狀況不足以支持網(wǎng)絡(luò)資源的有效調(diào)度，則會(huì)出現(xiàn)大范圍的用戶訪問受阻現(xiàn)象，且某些基礎(chǔ)支持設(shè)施往往會(huì)因?yàn)橛脩粼L問受阻而出現(xiàn)嚴(yán)重的DDOS癱瘓現(xiàn)象，因此需要對(duì)網(wǎng)絡(luò)資源流、接入帶寬以及訪問點(diǎn)的用戶訪問情況進(jìn)行合理匹配，以便實(shí)現(xiàn)資源的充分調(diào)度［8］。

對(duì)于任意一路網(wǎng)絡(luò)資源流而言，其調(diào)度過程可以根據(jù)資源量、接入帶寬有效占有量、接入點(diǎn)資源三種指標(biāo)唯一的決定［9］。故本文采用三種指標(biāo)，引入梯度排序概念，以便實(shí)現(xiàn)調(diào)度過程的最優(yōu)匹配。整個(gè)調(diào)度過程由接入控制和服務(wù)控制兩個(gè)過程構(gòu)成。

（1）依據(jù)有效調(diào)度概率PT（x）進(jìn)行接入控制。

資源在路徑上的匹配程度，可以根據(jù)在一定時(shí)間之內(nèi)被傳輸至某個(gè)接入點(diǎn)上的資源梯度及帶寬粒度來決定［9］。在某個(gè)時(shí)間點(diǎn)t0抵達(dá)接入點(diǎn)上的資源流滿足泊松分布，且分布指數(shù)為λ，整個(gè)資源包組的節(jié)點(diǎn)服務(wù)時(shí)間X服從相同的分布且資源包之間及資源包組之間處于互相獨(dú)立的狀態(tài)。因此整個(gè)資源流的期望程度NQ為：

其中E X2為泊松分布的二階矩，E X為泊松分布的期望。

首先判斷接入點(diǎn)資源時(shí)間長(zhǎng)度，假如接入點(diǎn)資源時(shí)間長(zhǎng)度情況良好，則網(wǎng)絡(luò)資源在路徑上被有效調(diào)度的概率PT（x）則處于良好的水平。倘若接入點(diǎn)能分配的資源時(shí)間長(zhǎng)度不佳，且接入有效帶寬情況不良，則資源的調(diào)度處于失效狀態(tài)，即：

（2）依據(jù)帶寬占有率進(jìn)行提供服務(wù)控制。

首先根據(jù)資源流在具體接入點(diǎn)上的帶寬占有率p?來確定接入概率Pr（x），確保資源流能夠以該概率被用戶進(jìn)行有效體驗(yàn)。

由于接入概率Pr（x）對(duì)帶寬占有率p?不敏感，因此可以利用該性能來保持Pr（x）的轉(zhuǎn)移穩(wěn)定性能長(zhǎng)期不變，即：

其中帶寬占有率p?為時(shí)間函數(shù)，該函數(shù)的數(shù)學(xué)形式如下所示：

其中p為帶寬占有率p?對(duì)時(shí)間的轉(zhuǎn)移概率，該轉(zhuǎn)移概率滿足一維高斯平穩(wěn)隨機(jī)過程。

不妨設(shè)目前資源流為Fc接入點(diǎn)的帶寬資源量為Fp，接入點(diǎn)的資源轉(zhuǎn)移概率為Nnest，則當(dāng)前資源流Fc的用戶體驗(yàn)滿足轉(zhuǎn)移概率PFC滿足：

接入點(diǎn)的帶寬資源量與用戶梯度Δ為覆蓋關(guān)系，及用戶梯度Δ越大，則接入帶寬資源量的體驗(yàn)也就越佳，因此抽取用戶梯度最大的時(shí)刻Δt，整個(gè)覆蓋關(guān)系Δs滿足如下表達(dá)式：

經(jīng)簡(jiǎn)化，模型（6）可以寫為：

其中p?為帶寬占用率

故目前資源量Fc在接入點(diǎn)的帶寬資源量Fp固定時(shí)，接入點(diǎn)的資源轉(zhuǎn)移概率Nnest滿足：

相應(yīng)的控制概率Nnest滿足

據(jù)此可求得資源在最佳用戶梯度及覆蓋關(guān)系確定的情況下被用戶成功訪問的概率P max滿足：

據(jù)模型（10）訪問概率P max大于0.5時(shí)，則說明當(dāng)前資源流可以成功提供服務(wù)，調(diào)度流程結(jié)束。

整個(gè)資源調(diào)度步驟為：

SteP1：根據(jù)網(wǎng)絡(luò)資源流的流量資源大小，以較低成本傳輸?shù)浇尤朦c(diǎn)資源最佳的處理節(jié)點(diǎn)進(jìn)行處理；

SteP2：對(duì)用戶訪問資源及接入帶寬的大小進(jìn)行排序，按照用戶訪問資源最佳及接入帶寬質(zhì)量最低的原則進(jìn)行第一次資源匹配；

SteP3：進(jìn)行完上述兩個(gè)過程的資源調(diào)度過程后，在每一次網(wǎng)絡(luò)資源流進(jìn)行切換的時(shí)刻，直到下一次網(wǎng)絡(luò)資源流被調(diào)度為止，完成本次資源的調(diào)度工作；

SteP4：繼續(xù)進(jìn)行下一周期內(nèi)的資源調(diào)度，直到用戶訪問結(jié)束。

2.2本文算法詳細(xì)描述

考慮到資源流為Fc接入點(diǎn)的帶寬資源量為Fp，接入點(diǎn)的資源轉(zhuǎn)移概率為Nnest，則本文資源調(diào)度算法流程見圖1，其步驟為：

SteP1：初始接入點(diǎn)資源鏈路匹配開始，當(dāng)僅當(dāng)匹配成功進(jìn)行才進(jìn)行下一步；

SteP2：接入點(diǎn)在接收到網(wǎng)絡(luò)資源有效請(qǐng)求之后，在一定時(shí)期能若持續(xù)收到網(wǎng)絡(luò)資源流的請(qǐng)求，則轉(zhuǎn)SteP3；否則返回SteP 1中繼續(xù)進(jìn)行初始接入資源鏈路匹配；

SteP3：當(dāng)僅當(dāng)接入點(diǎn)確認(rèn)網(wǎng)絡(luò)資源流是持續(xù)狀態(tài)時(shí)，才繼續(xù)轉(zhuǎn)下一步，否則回SteP2繼續(xù)進(jìn)行有效請(qǐng)求的確認(rèn)與匹配；

SteP4：按模型（8）～（10）所示計(jì)算資源在最佳用戶梯度及覆蓋關(guān)系確定的情況下被用戶成功訪問的概率Pmax，當(dāng)僅當(dāng)Pmax大于0.5時(shí)，則持續(xù)進(jìn)行SteP1～SteP3

SteP5：算法結(jié)束。

圖1　本文算法流程圖Fig.1 The flow chart of this algorithm

3　仿真實(shí)驗(yàn)

3.1仿真環(huán)境設(shè)置

為評(píng)估本文提出的算法性能，仿真實(shí)驗(yàn)中使用NS -2仿真平臺(tái)對(duì)RRPS［10］、PR_RRPS［11］算法與本文算法進(jìn)行仿真對(duì)比。實(shí)驗(yàn)仿真參數(shù)如下：

表1　仿真參數(shù)表Tab.1 Sim u lation param eters

仿真實(shí)驗(yàn)中，為驗(yàn)證本文方案的有效性，實(shí)驗(yàn)重點(diǎn)從移動(dòng)節(jié)點(diǎn)個(gè)數(shù)、網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)個(gè)數(shù)以及節(jié)點(diǎn)初始能量大小這三個(gè)變量，與RRPS、PR_RRPS算法在W ifi成功接入率、用戶資源體驗(yàn)滿意程度兩個(gè)指標(biāo)上進(jìn)行對(duì)比。

3.2結(jié)果比對(duì)

（1）W IFI成功接入率。

圖2顯示了在不同節(jié)點(diǎn)功率情況下本文算法與RRPS、PR_RRPS算法在W IFI成功接入率上的對(duì)比，從圖中可以看到，隨著用戶終端節(jié)點(diǎn)功率的不斷提高，本文算法始終保持較高的W IFI成功接入率，而對(duì)照組算法的W IFI的接入率隨著用戶終端節(jié)點(diǎn)功率的不斷提高而呈現(xiàn)下降的趨勢(shì)，這是因?yàn)楸疚乃惴ú扇』谔荻鹊姆绞?，在用戶終端節(jié)點(diǎn)功率不斷上升的情況下能夠有效的保障接入點(diǎn)以較高的比例滿足用戶需求，因此大大提高了WIFI的成功接入率，而對(duì)比組算法未考慮功率因素，因此當(dāng)用戶終端節(jié)點(diǎn)功率不斷上升時(shí)難以緩解接入點(diǎn)帶寬資源對(duì)接入的有效性。

圖2　不同節(jié)點(diǎn)功率下的W IFI成功接入率Fig.2 W IFI successfu l access rate under different node pow er

圖3顯示了在不同節(jié)點(diǎn)密度情況下本文算法與RRPS、PR_RRPS算法在W IFI成功接入率上的對(duì)比，從圖中可以看到，隨著用戶終端節(jié)點(diǎn)密度的不斷提高，本文算法始終保持較高的wifi成功接入率，而對(duì)比組算法的W IFI的接入率隨著用戶終端節(jié)點(diǎn)密度的不斷提高而呈現(xiàn)下降的趨勢(shì)，這是因?yàn)楸疚乃惴ú扇』谔荻扰判虻荣Y源調(diào)度模式，在用戶終端節(jié)點(diǎn)密度不斷上升的情況下能夠有效的保障接入點(diǎn)以較高的比例滿足用戶需求，而對(duì)比組算法未考慮用戶終端節(jié)點(diǎn)密度提高對(duì)網(wǎng)絡(luò)資源的影響，因此難以在用戶節(jié)點(diǎn)密度對(duì)資源進(jìn)行爭(zhēng)奪時(shí)有效改善網(wǎng)絡(luò)接入質(zhì)量。

（2）用戶資源滿意體驗(yàn)度。

圖3　不同節(jié)點(diǎn)密度下的W ifi成功接入率Fig.3 W ifi successfu l access rate under d ifferent node density

圖4顯示了在不同節(jié)點(diǎn)功率情況下本文算法與RRPS、PR_RRPS算法在用戶資源滿意體驗(yàn)度上的對(duì)比，從圖中可以看到，隨著用戶終端節(jié)點(diǎn)功率的不斷提高，本文算法始終保持較高的用戶資源滿意體驗(yàn)度，而對(duì)比組算法的用戶資源滿意體驗(yàn)度隨著用戶終端節(jié)點(diǎn)功率的不斷提高而呈現(xiàn)下降的趨勢(shì)，這是因?yàn)楸疚乃惴ú扇』谔荻扰判虻荣Y源調(diào)度模式，在用戶終端節(jié)點(diǎn)功率不斷上升的情況下能夠有效的滿足用戶帶寬需求，因此能夠?qū)崿F(xiàn)較高的用戶資源滿意體驗(yàn)度，而對(duì)比組算法未考慮用戶終端節(jié)點(diǎn)功率提高對(duì)網(wǎng)絡(luò)資源的影響，因此難以在用戶節(jié)點(diǎn)功率上升時(shí)對(duì)用戶資源滿意體驗(yàn)度有嚴(yán)重的影響。

圖4　不同節(jié)點(diǎn)功率下的用戶資源滿意體驗(yàn)度Fig.4 User satisfaction experience under d ifferen t node power

圖5顯示了在不同節(jié)點(diǎn)密度情況下本文算法與RRPS、PR_RRPS算法用戶資源滿意體驗(yàn)度上的對(duì)比，從圖中可以看到，隨著用節(jié)點(diǎn)密度的不斷提高，本文算法始終保持較高的用戶資源滿意體驗(yàn)度，而對(duì)比組算法的用戶資源滿意體驗(yàn)度隨著用戶節(jié)點(diǎn)密度的不斷提高而呈現(xiàn)下降的趨勢(shì)，這是因?yàn)楸疚乃惴ú扇』谔荻鹊姆绞剑谟脩艚K端節(jié)點(diǎn)密度不斷上升的情況下能夠有效的保障接入點(diǎn)以較高的比例滿足用戶需求，因此大大提高了用戶資源滿意體驗(yàn)度，而對(duì)比組算法未考慮節(jié)點(diǎn)密度，因此當(dāng)用戶終端節(jié)點(diǎn)密度不斷上升時(shí)難以提高用戶資源滿意體驗(yàn)度。

圖5　不同節(jié)點(diǎn)密度下的用戶資源滿意體驗(yàn)度Fig.5 User satisfaction experience under different node density

5　結(jié)束語(yǔ)

由于WLAN網(wǎng)絡(luò)中資源調(diào)度過程中網(wǎng)絡(luò)資源受限，調(diào)度不良，及難以實(shí)現(xiàn)有效資源控制，易造成嚴(yán)重的數(shù)據(jù)擁塞現(xiàn)象，從而降低資源調(diào)度性能及用戶體驗(yàn)程度。對(duì)此，本文提出了一種新的基于WLAN多流調(diào)控機(jī)制的無線自組織網(wǎng)絡(luò)資源調(diào)度算法，該算法考慮接入網(wǎng)絡(luò)的梯度及有效帶寬，采取基于接入點(diǎn)的資源時(shí)間長(zhǎng)度進(jìn)行控制，然后根據(jù)帶寬占有率進(jìn)行接入控制，有效的改善了資源流的分配質(zhì)量，提高了用戶體驗(yàn)度。

參考文獻(xiàn)：

［1］ 闕鋆淑，謝葳，黃幫明.高校WLAN優(yōu)化方案研究［J］.電視技術(shù)，2012，36（5）：70 -72.

QUE Yunshu，XIE Wei，HUANG Bangming.Research on WLAN oPtimization scheme in Universities［J］.Video Technology，2012，36（5）：70 -72.

［2］ 劉琪，袁堅(jiān)，山秀明.3G/WLAN網(wǎng)絡(luò)中基于終端移動(dòng)與業(yè)務(wù)認(rèn)知的動(dòng)態(tài)負(fù)載均衡機(jī)制［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33（9）：1569 -1573.

LIU Qi，YUAN Jian，SHAN Xiuming.Dynam ic load balancing mechanism based on term inal mobility and service cognition in WLAN 3G/networks［J］.Journal of ComPuter Science，2010，33（9）：1569 -1573.

［3］ Heinzellnan W B，Chandrakasan A P，Balakrishnan.An APPlication SPecific Protocol Architecture for W ireless Networks［J］. IEEE Transactions on W ireless Communications，2012，1（4）：660 -670.

［4］ Ahlswede R，Cai N，Li S Y R，et al.Network informationflow［J］.IEEE Trans.on Information Theory，2014，46（4）：1204 -1216.

［5］ Niu B，Zhao H V，Jiang H.A cooPeration stimulation strategy in wireless multicastnetworks［J］.Signal Processing，IEEE Transactions on，2011，59（5）：2355 -2369.

［6］ 羅守山，楊文川，蕭薔.基于WLAN傳輸評(píng)估的模型及研究［J］.北京郵電大學(xué)學(xué)報(bào)，2013，31（3）：5 -9.

LUO Shoushan，YANG Wenchuan，XIAO Qiang.The model and research based on WLAN transm ission evaluation［J］.Journal of Beijing University of Posts and Telecommunications，2013，31（3）：5 -9.

［7］ LOPEZ D，GUVENC I，ROCHE G.Enhanced intercell interference coordination challenges in heterogeneous networks［J］. IEEE Transactions on W ireless Communications，2011，18（3）：22 -30.

［8］ Wu F，Chen T，Zhong S，et al.A Game-Theoretic APProach to Stimulate CooPeration for Probabilistic Routing in OPPortunistic Networks［J］.2013：1 -11.

［9］ Kimiaei F，Chabok S J S M，Moghadam R A.A Distributed and Energy Efficient Routing based Game Theory to Congestion Avoidance in WLAN［J］.The International Journal of Soft ComPuting and Software Engineering，2013，3（3）：441 -445.

［10］ Lin J，Xiong N，Vasilakos A V，et al.Evolutionary game - based data aggregation model forWLAN［J］. Communications，IET，2011，5（12）：1691 -1697.

［11］ Mejia M，Pe?a N，Mu?oz J L，et al.A game theoretic trust model for on - line distributed evolution of cooPeration inMANETs［J］.Journal of Network and ComPuter APPlications，2014，34（1）：39 -51.

郝 平 男（1981 -），陜西清澗人，講師，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、信息安全、圖像處理。

The Research on Resource Scheduling Algorithm in W ireless ad hoc Networks Based on WLAN flow Control Mechanism

HA0 ping
（College of Information Engineering，Shaanxi Polytechnic University，Xianyang 712000，China）

Abstract：In order to solve the lim itation of network resources and Poor scheduling of WLAN resource scheduling algorithm，as well as difficulty of achieving efficient resource controlling，the new resource scheduling algorithm of w ireless ad hoc networks based on WLAN multi flow control mechanism was ProPosed in this PaPer.Firstly，resource quantity，access bandw idth effective share and access Point resource，and other indicators were sorted by combining w ith the concePt of gradient，and matching were rePeated by the PrinciPle of the best user access to resources and access to the lowest bandw idth quality；the equilibrium allocation and scheduling of each resource flow in the netw ork w as achieved based on resource access Probability only w hen the access Probability was greater than a certain value.The simulation results show that this ProPosed scheme had better congestion control and resource scheduling Performance com Pared w ith RRPS and PR_RRPS algorithm s.

Key wo rds：w ireless ad hoc networks；resource scheduling；flow control；bandw idth Possession；balanced allocation；access control

中圖分類號(hào)：TP 393

文獻(xiàn)標(biāo)識(shí)碼：A

基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目（2012JQ1017）