摘 要: 提出了一種結合預留資源進行補償的無線公平調度算法。當系統呼叫切換頻率很低時，將預留資源的空閑部分中的一部分用于補償，以提高系統的資源利用率；當系統呼叫切換頻率很高時，進行補償的業務流均為那些獲得額外服務的業務流，本算法應用在系統呼叫的切換頻率很低的情況下，可以充分利用頻帶資源的優勢。
關鍵詞: 預留資源；無線網絡；算法
隨著無線網絡的發展，移動通信用戶數和Internet用戶數急劇增加，人們期望新一代移動通信系統不僅具有更大的容量，還要支持移動多媒體業務，除了提供話音業務外，還支持低/高速數據、圖像等非話音業務的傳輸。不同業務有不同的服務質量(QoS)要求，如對時延、誤比特率、數據速率的要求不同。無線網絡設計有兩大目標:一是保證各類業務的QoS要求，二是使網絡的資源利用率達到最大，這就需要借助于無線資源管理。而目前的無線分組調度算法主要集中在保障各連接的QoS前提下，追求系統吞吐量極大化，也就是系統利用率的提高。但是系統吞吐量極大化與公平服務是一對矛盾。大多數算法的公平性主要體現在長期上，而未考慮短期公平性的問題，也就是未考慮無線信道特殊性引入的補償問題:當一個連接的鏈路從故障恢復后，如何對這個連接進行有效的補償是值得研究的。這些補償方式從某種程度上說也是不公平的，因為從完全公平的角度出發，應該是那些得到額外服務的連接對滯后流做出補償。因此，在無線網絡中對預留資源進行補償的無線公平調度算法進行研究具有重要意義。
1 應用預留資源進行補償的無線網絡公平調度算法的描述
由于采用了加權的調度算法，額外帶寬的分配直接隱含在連接獲得的總帶寬分配中，這是由于加權調度算法中每一個連接獲得的帶寬滿足公式(1)。
算法描述如下:
(1)當進入系統的切換呼叫頻率不高時, 此時預留資源有部分資源處于空閑狀態，將這部分資源的一部分用于補償；
(2)當進入系統的切換呼叫頻率很高時，預留資源的使用率很高，采用領先流釋放一部分帶寬用于補償，而不是將其所有帶寬都用于補償，直至這個領先流變成同步流。這樣做的好處是補償時并不中斷對領先流的服務。補償方式采用針對滯后流固定比例獲得補償的方式[1]。
為了簡化計算，算法定義一個預留資源空閑率參數S=空閑預留資源/總預留資源，并且設定一個預留資源空閑率門限St，當t時刻S(t) ≥St時，采用方式1進行補償；當t時刻S(t) <St時，采用方式2進行補償[2]。
方式1 的計算較為簡單，滯后流直接獲得一定比例(λ)的空閑預留資源(BFR)用于補償，即獲得λ×BFR的額外帶寬。不將全部預留資源用于補償的目的是為了避免在補償過程中系統拒絕新的切換呼叫。
可以推得理想模式下(即所有領先流都完全進行了補償)補償所需要的時間為：
假設fi連接從t1時刻開始故障，故障時間為Ti，補償時間為Xi，那么fi在Ti時刻以及補償結束時刻均為同步流狀態。未發生故障時間在此期間(Ti+Xi)得到的服務Si應該等于發生故障后fi在補償過程中(Xi)總共得到的服務Si*。
方式2中，算法采用了滯后流固定比例獲得補償的無線公平調度算法。針對一個滯后流l，當它的鏈路恢復正常時，算法直接分配其預約帶寬的固定比例Δi(0<Δi<1)用于補償。這部分補償帶寬由領先流按照各自權重分配。其方法如下列關系式所示:
式中wla*和wle*代表更新后的滯后流和領先流的權重，wla和wle代表更新前的滯后流和領先流的權重。每當有連接狀態發生變化時(包括監測到故障恢復、滯后流或者領先流恢復成同步流)，各個相應流的權重都根據公式進行調整。
由公式(1)可知補償時滯后流實際得到的帶寬變大，而領先流得到的帶寬變小[3]。
2 應用預留資源進行補償的無線網絡公平調度算法的仿真結果及分析
傳統調度算法采用了WF2Q+，并且各個連接的權重直接等于其預約速率的大小，未做歸一化處理。
2.1 所有連接均無差錯
根據其分配的權重，根據式(1)，可知，其和有線網絡狀況基本一致，這證明了系統在無差錯狀態下工作是正常的。
2.2 有連接出現鏈路故障
選擇分組數據流3來代表出現信道故障的連接，鏈路在時間12 s時出現故障，14 s時恢復正常。
(1)考慮特殊情況，此時預留帶寬未被使用，即系統中無預約切換呼叫，采用方式1進行補償，λ=3/4，BFR=200 kb/s， Flow3獲得的補償帶寬為3/4×200=150 kb/s。圖1為采用本算法時的仿真結果。通過圖1可以看到，當Flow3的連接發生故障時（12 s～14 s），這部分額外帶寬將被分配給無故障的連接，Flowl、Flow2、Flow4獲得的發送速率均得到了提高(從圖線的斜率變化可以看出，斜率變大)，這種變化一直持續到Flow3的連接恢復(t= 14 s)。此時Flow3開始獲得補償(發送速率提高)，直至補償結束(t=22 s)。整個補償過程中所有領先流均未對Flow3進行補償(發送速率維持在初始狀態)[4]。
Flow 2、3的傳輸速率曲線如圖2所示。Flow 1、Flow4與Flow 3類似。
根據式(2)可以計算補償時間為8 s，即補償在14+8=22 s時結束，圖1和圖2說明了這一點。從圖2中可以看到，Flow 3在鏈路故障時傳輸速率降為0，其額外帶寬被分配給了其他鏈路狀態良好的連接，Flow 2的傳輸速率因此得到了提升，根據式(1)可以計算出此時Flow 2的傳輸速率為570 kb/s，這也在圖2中得到印證。當Flow 3的鏈路恢復時，補償開始，Flow 3得到了150 kb/s的補償帶寬，因此速率上升到750 kb/s，而此時Flow 2并未對Flow 3進行補償，故它的速率仍然保持為初始傳輸速率400 kb/s。在補償結束后(22 s)，Flow 3的速率恢復到初始傳輸速率600 kb/s. Flow 1、Flow4的傳輸速率曲線與Flow 2的類似，這里略過[5]。
(2)系統中無空閑預留資源，采用方式2進行補償(針對滯后流固定比例獲得補償的方式)，Δ3=1/3。圖3為仿真結果。通過圖3可以看到，當Flow3的連接恢復時，獲得額外服務的連接將自己的部分帶寬用于補償(斜率變小)，直到補償結束，各個連接的發送速率均恢復到初始狀態(斜率與原來一致)。由于采用補償策略為針對滯后流固定比例獲得補償，補償耗費時間為1/Δ3倍故障時間，即6 s。Flow 3在14+6=20 s時恢復同步流狀態。
由于這里采用的是滯后流固定比例獲得補償的無線公平調度算法，因此其結果與圖1的仿真結果一致。
圖4比較了無差錯狀態與有差錯狀態(采用方式1和方式2進行補償)時Flow 4的仿真結果。
由圖4可見，系統一直無差錯時，仿真結果為一條直線；當系統有差錯時，Flow 4將在差錯狀態時獲得額外服務(12 s～14 s)。當采用方式1進行補償時，Flow 4并未受影響，其獲得的額外服務未用于補償，這意味著整個系統的資源利用率得到了提高。當采用方式2進行補償后，補償結束時Flow 4狀態和無差錯狀態的仿真結果一致，也就是說采用方式2補償后連接所得到的實際服務在補償結束后與其預約的服務是一致的。這對所有的連接都是公平的。Flowl、Flow2的結果與Flow4類似。
這里沒有比較Flow 3在無差錯狀態和有差錯狀態的結果，需要指出的是，無論采用方式1還是方式2，在補償結束后，Flow 3得到的實際服務與其預約的服務是一致的。
3 應用預留資源進行補償的無線網絡公平調度算法復雜性分析
從空間復雜度上看，算法有3N個固定存儲空間。當采用方式1進行補償時，時間復雜度上僅需計算一次乘法和一次加法。當采用方式2進行補償時，時間復雜度的計算與采用的算法有關，由于本算法采用了無線公平調度算法，因此調整權重時最差情況下的時間復雜度為0(N2)。
綜上所述，該文提出了一種無線公平調度算法——應用預留資源進行補償的無線公平調度算法。當系統呼叫切換頻率很低時，將預留資源的空閑部分中的一部分用于補償；當系統呼叫切換頻率很高時，進行補償的業務流均為那些獲得額外服務的業務流。
當采用方式1進行補償時，直接利用預留資源中的部分空閑帶寬進行補償，這樣可以提高系統的資源利用率。
當采用方式2進行補償時，算法實際是通過補償算法和再分配算法對各個連接的權重進行調整，從而實現補償。該算法對于系統呼叫的切換頻率很低的情況下，可以充分利用頻帶資源的優勢。
參考文獻
[1] 紀陽,李迎陽,鄧鋼,等.一種適用于寬帶無線IP網絡的分組調度算法[J].電子學報,2003,31(05): 103-107.
[2] 宣孝英,石冰心,鄒玲.無線網絡包調度算法綜述[J].計算機工程與應用,2003,39(17):23-24+58.
[3] 任艷穎,張文軍,王彬. 無線調度算法[J].計算機工程,2004,30(15):102-103+126.
[4] 王燕,伍博,楊豪強,等.一種支持多業務的調度算法的研究與仿真[J].河南師范大學學報(自然科學版),2006，34(04):195-197.
[5] 宋艦,李樂民.一種支持服務類別的無線公平調度算法[J].電子學報,2004,32(01):60-64.