基于W LAN流調控機制的無線自組織網絡資源調度算法研究

郝 平（陜西工業職業技術學院信息工程學院，陜西咸陽 712000）

?

基于W LAN流調控機制的無線自組織網絡資源調度算法研究

郝 平
（陜西工業職業技術學院信息工程學院，陜西咸陽 712000）

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

關鍵詞：無線自組織網絡；資源調度；流調控；帶寬占有；均衡分配；接入控制

1　引 言

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

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

為了解決上述不足，提出了一種基于WLAN流調控機制的無線自組織網絡資源調度技術，采取基于梯度和有效接入帶寬的排列策略，對網絡資源流接入時間的長度及資源進行控制；并在控制過程中對難以滿足策略的路數進行預警，從而實現了資源在網絡中的均衡化調度。最后測試了本文算法的調度性能。

2　本文無線自組織網絡資源調度算法

2.1網絡資源流轉移排序與計算

當用戶處于WLAN網絡進行用戶體驗時，對于資源的調度請求是以流的形式存在，使其可以使用一定的調度技術實現匹配［7］。如果當前網絡狀況不足以支持網絡資源的有效調度，則會出現大范圍的用戶訪問受阻現象，且某些基礎支持設施往往會因為用戶訪問受阻而出現嚴重的DDOS癱瘓現象，因此需要對網絡資源流、接入帶寬以及訪問點的用戶訪問情況進行合理匹配，以便實現資源的充分調度［8］。

對于任意一路網絡資源流而言，其調度過程可以根據資源量、接入帶寬有效占有量、接入點資源三種指標唯一的決定［9］。故本文采用三種指標，引入梯度排序概念，以便實現調度過程的最優匹配。整個調度過程由接入控制和服務控制兩個過程構成。

（1）依據有效調度概率PT（x）進行接入控制。

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

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

首先判斷接入點資源時間長度，假如接入點資源時間長度情況良好，則網絡資源在路徑上被有效調度的概率PT（x）則處于良好的水平。倘若接入點能分配的資源時間長度不佳，且接入有效帶寬情況不良，則資源的調度處于失效狀態，即：

（2）依據帶寬占有率進行提供服務控制。

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

由于接入概率Pr（x）對帶寬占有率p?不敏感，因此可以利用該性能來保持Pr（x）的轉移穩定性能長期不變，即：

其中帶寬占有率p?為時間函數，該函數的數學形式如下所示：

其中p為帶寬占有率p?對時間的轉移概率，該轉移概率滿足一維高斯平穩隨機過程。

不妨設目前資源流為Fc接入點的帶寬資源量為Fp，接入點的資源轉移概率為Nnest，則當前資源流Fc的用戶體驗滿足轉移概率PFC滿足：

接入點的帶寬資源量與用戶梯度Δ為覆蓋關系，及用戶梯度Δ越大，則接入帶寬資源量的體驗也就越佳，因此抽取用戶梯度最大的時刻Δt，整個覆蓋關系Δs滿足如下表達式：

經簡化，模型（6）可以寫為：

其中p?為帶寬占用率

故目前資源量Fc在接入點的帶寬資源量Fp固定時，接入點的資源轉移概率Nnest滿足：

相應的控制概率Nnest滿足

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

據模型（10）訪問概率P max大于0.5時，則說明當前資源流可以成功提供服務，調度流程結束。

整個資源調度步驟為：

SteP1：根據網絡資源流的流量資源大小，以較低成本傳輸到接入點資源最佳的處理節點進行處理；

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

SteP3：進行完上述兩個過程的資源調度過程后，在每一次網絡資源流進行切換的時刻，直到下一次網絡資源流被調度為止，完成本次資源的調度工作；

SteP4：繼續進行下一周期內的資源調度，直到用戶訪問結束。

2.2本文算法詳細描述

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

SteP1：初始接入點資源鏈路匹配開始，當僅當匹配成功進行才進行下一步；

SteP2：接入點在接收到網絡資源有效請求之后，在一定時期能若持續收到網絡資源流的請求，則轉SteP3；否則返回SteP 1中繼續進行初始接入資源鏈路匹配；

SteP3：當僅當接入點確認網絡資源流是持續狀態時，才繼續轉下一步，否則回SteP2繼續進行有效請求的確認與匹配；

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

SteP5：算法結束。

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

3　仿真實驗

3.1仿真環境設置

為評估本文提出的算法性能，仿真實驗中使用NS -2仿真平臺對RRPS［10］、PR_RRPS［11］算法與本文算法進行仿真對比。實驗仿真參數如下：

表1　仿真參數表Tab.1 Sim u lation param eters

仿真實驗中，為驗證本文方案的有效性，實驗重點從移動節點個數、網絡內節點個數以及節點初始能量大小這三個變量，與RRPS、PR_RRPS算法在W ifi成功接入率、用戶資源體驗滿意程度兩個指標上進行對比。

3.2結果比對

（1）W IFI成功接入率。

圖2顯示了在不同節點功率情況下本文算法與RRPS、PR_RRPS算法在W IFI成功接入率上的對比，從圖中可以看到，隨著用戶終端節點功率的不斷提高，本文算法始終保持較高的W IFI成功接入率，而對照組算法的W IFI的接入率隨著用戶終端節點功率的不斷提高而呈現下降的趨勢，這是因為本文算法采取基于梯度的方式，在用戶終端節點功率不斷上升的情況下能夠有效的保障接入點以較高的比例滿足用戶需求，因此大大提高了WIFI的成功接入率，而對比組算法未考慮功率因素，因此當用戶終端節點功率不斷上升時難以緩解接入點帶寬資源對接入的有效性。

圖2　不同節點功率下的W IFI成功接入率Fig.2 W IFI successfu l access rate under different node pow er

圖3顯示了在不同節點密度情況下本文算法與RRPS、PR_RRPS算法在W IFI成功接入率上的對比，從圖中可以看到，隨著用戶終端節點密度的不斷提高，本文算法始終保持較高的wifi成功接入率，而對比組算法的W IFI的接入率隨著用戶終端節點密度的不斷提高而呈現下降的趨勢，這是因為本文算法采取基于梯度排序等資源調度模式，在用戶終端節點密度不斷上升的情況下能夠有效的保障接入點以較高的比例滿足用戶需求，而對比組算法未考慮用戶終端節點密度提高對網絡資源的影響，因此難以在用戶節點密度對資源進行爭奪時有效改善網絡接入質量。

（2）用戶資源滿意體驗度。

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

圖4顯示了在不同節點功率情況下本文算法與RRPS、PR_RRPS算法在用戶資源滿意體驗度上的對比，從圖中可以看到，隨著用戶終端節點功率的不斷提高，本文算法始終保持較高的用戶資源滿意體驗度，而對比組算法的用戶資源滿意體驗度隨著用戶終端節點功率的不斷提高而呈現下降的趨勢，這是因為本文算法采取基于梯度排序等資源調度模式，在用戶終端節點功率不斷上升的情況下能夠有效的滿足用戶帶寬需求，因此能夠實現較高的用戶資源滿意體驗度，而對比組算法未考慮用戶終端節點功率提高對網絡資源的影響，因此難以在用戶節點功率上升時對用戶資源滿意體驗度有嚴重的影響。

圖4　不同節點功率下的用戶資源滿意體驗度Fig.4 User satisfaction experience under d ifferen t node power

圖5顯示了在不同節點密度情況下本文算法與RRPS、PR_RRPS算法用戶資源滿意體驗度上的對比，從圖中可以看到，隨著用節點密度的不斷提高，本文算法始終保持較高的用戶資源滿意體驗度，而對比組算法的用戶資源滿意體驗度隨著用戶節點密度的不斷提高而呈現下降的趨勢，這是因為本文算法采取基于梯度的方式，在用戶終端節點密度不斷上升的情況下能夠有效的保障接入點以較高的比例滿足用戶需求，因此大大提高了用戶資源滿意體驗度，而對比組算法未考慮節點密度，因此當用戶終端節點密度不斷上升時難以提高用戶資源滿意體驗度。

圖5　不同節點密度下的用戶資源滿意體驗度Fig.5 User satisfaction experience under different node density

5　結束語

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

參考文獻：

［1］ 闕鋆淑，謝葳，黃幫明.高校WLAN優化方案研究［J］.電視技術，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］ 劉琪，袁堅，山秀明.3G/WLAN網絡中基于終端移動與業務認知的動態負載均衡機制［J］.計算機學報，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傳輸評估的模型及研究［J］.北京郵電大學學報，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 -），陜西清澗人，講師，主要研究方向為計算機網絡、信息安全、圖像處理。

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

中圖分類號：TP 393

文獻標識碼：A

基金項目：陜西省自然科學基金資助項目（2012JQ1017）