一種減小網絡資源開銷的業務調度方法
2023-12-06 18:56:36 1
專利名稱：一種減小網絡資源開銷的業務調度方法
技術領域：
本發明涉及無線通信技術領域，特別是涉及無線傳輸和進化理論。
背景技術：
為保證業務的高效傳輸，需採用合適的QoS保障機制。QoS —方面指業務流管理， 它提供了一種實現上、下行QoS管理的機制，是MAC層的核心功能，包括QoS參數集、業務流的定義與分類、動態業務流管理、帶寬請求與分配、輪詢等，其在IEEE 802. 16中進行了詳細規定；另一方面指相應的QoS保證機制，包括接入控制、調度算法、流量監控等。業務流是一個提供特定QoS的單向數據流。802. 16協議MAC層對QoS的支持分為三部分一是創建最初的業務流並對其QoS參數進行配置；二是在通信過程中對業務流進行動態管理，包括動態業務增加(DSA)、動態業務改變(DSC)和動態業務刪除(DSD) 』三是在通信過程中對MAC PDU進行分類，並依據業務流的類別區分優先級進行調度，實現了將 QoS機制內置於IEEE 802. 16 MAC協議內部，現有的業務調度參考模型如
圖1所示。業務調度是實現QoS保證機制的一個重要的組成部分，其體現了基於連接的MAC 層對業務流的處理機制。每一個連接都與一個業務流相聯繫，每一個業務流又與一組量化其行為的QoS參數相聯繫。業務調度算法的性能指標可以從三個方面來衡量，即有效性、公平性和複雜性。各種衡量標準之間往往是矛盾的，某一個指標性能的提高可能是以犧牲另一個指標性能為代價。因此，實際應用中使用的算法是需要綜合考慮各種因素，根據實際情況協調各方面的特性。業務調度的特點主要為
(1)有效性。其主要包括對系統資源的利用率以及時延方面的特性。從系統和用戶兩方面考慮，系統要求資源利用率高，而用戶的要求主要在時延方面。在一個可以為用戶應用提供服務質量保證的系統中，每個用戶業務流都有其與系統約定的一系列服務參數，如帶寬要求、時延要求等，業務調度方法應該能夠滿足每個業務流對服務質量的要求；
(2)公平性。指以公平的方式對各業務流分配可用的帶寬資源，並且不同的業務流之間應該相互隔離，以防止突發業務或惡意流對正常業務流的影響；
(3)複雜性。指業務調度方法是否容易實現。如果調度方法過於複雜，那麼在高速網絡中，就不能快速的調度並對分組進行轉發，這樣調度模塊將成為網絡系統中的瓶頸，影響到整個系統的使用效率。因此，調度方法應該儘可能簡單、易實現，並且還應有較好的可擴展性，能適應動態變化的應用環境。
發明內容
本發明所要解決的技術問題是在減小網絡資源開銷的條件下，實現業務資源的
高效調度。本發明為解決上述技術問題提供一種減小網絡資源開銷的業務調度方法，其特徵在於
A、建立網絡中的路徑、業務信號和控制信號一體化陣列模型；B、設置混合遺傳單元(即業務信號)的輸入和輸出變量；
C、對混合遺傳單元中的染色體(Chromosome)種群進行初始化；
D、使用遺傳算法獲得最優業務調度。所述步驟A中，在此陣列模型中，每一條路徑由多個微單元組成，並且每一條路徑有一個獨立的ID號，使用微單元的數目表示路徑的長度，令每一條路徑的微單元數量為 15，一個微單元的大小為對拉4，且每個業務信號佔用3個微單元；所有的業務信號都經過預處理，使其進過處理後具有虛擬固定長度，令業務信號的長度為30，每個業務信號有獨立的ID號，並且各自有固定的傳輸路徑，圖2描述了業務信號佔用路徑大小的情況，業務信號的傳輸速率為0至最大傳輸速率之間的任意值，最大傳輸速率為每秒5個微單元。所述步驟A中，在業務交換單元處，設置5個業務傳輸指示器，每個業務傳輸指示器具有相同功能，其中任意4個用於對業務信號的傳輸進行控制，剩餘1個用於對控制信號的傳輸進行控制。每一個傳輸指示器都有用於識別的獨立ID號，並且有暫停傳輸和允許傳輸兩種模式，我們使用陣列模型中的存儲單元來存儲這兩種模式相應的狀態信息，總體運行流程如圖3所示。所述步驟B中，混合遺傳單元(即業務信號)的輸入變量為 VP 當傳輸指示器出現允許傳輸模式時，經過的業務信號數目；
②PP當傳輸指示器出現允許傳輸模式時，經過的控制信號數目；
③呢當傳輸指示器出現暫停傳輸模式時，處於等待狀態的業務信號的數目；
④Ρβ:當傳輸指示器出現暫停傳輸模式時，處於等待狀態的控制信號的數目； 混合遺傳單元(即業務信號)的輸出變量為
①&^ :當傳輸指示器出現暫停傳輸模式時，在交換單元緩存中和處於即將到達狀態的業務信號數目；當傳輸指示器出現暫停傳輸模式時，在交換單元緩存中和處於即將到達狀態的控制信號數目；
③業務信號從起始點到終點的傳輸時間。所述步驟C中，採用混合遺傳算法對混合遺傳單元中的染色體(Chromosome)種群進行初始化，即業務調度優化預處理。染色體為此優化問題的備選解集。令每一個染色體具有兩個基因，第一個基因為傳輸指示器出現暫停傳輸模式的時間2 ，第二個基因為傳
輸指示器出現允許傳輸模式的時間G^，其中ι為業務信號τ或控制信號ρ。設染色體的
初始種群數量為100，使用二進位編碼方式對染色體進行編碼，每一個染色體都具有一串0 或1。如圖4所示，給出了例子。採用混合遺傳算法的輸入輸出結構示意圖如圖5所示。所述步驟D中，對混合遺傳單元中的染色體進行種群評估。此步驟用於評估每個染色體如何對業務調度優化問題進行求解，其包括對染色體解碼為變量空間問題，以及使用這些參數核查此問題的解。在染色體交叉處理階段時，設置交叉係數為0. 8，在父代染色體上執行控制信號允許傳輸操作，其結果存儲於陣列模型中的存儲單元中，並且將父代染色體的信息與子代染色體的信息融合，重複上述步驟，當在染色體交叉處理階段使用的種群數目為種群初始化數目的一半時，則停止計算，此時交叉處理階段完成；在變異階段，設置在父輩染色體上執行的變異係數為0. 2，根據在陣列模型中存儲的結果判斷，所產生的隨機數值和此數值與變異係數的比較結果由已發生變異或未發生變異的功能單元決定。重複上述步驟，當在變異階段使用的種群數目為種群初始化數目的一半時，則停止計算，此時變異階段完成。所述步驟D中，對混合遺傳單元中的染色體進行選擇。使用Roulette-wheel選擇概率方法選擇具有高健壯性的染色體，基於前面在變異階段獲得的結果，計算健壯性函數， 此步驟用於識別基於參數的解，其中參數包括隊列大小、業務信號數目、傳輸指示器出現暫停傳輸模式的時間和傳輸指示器出現允許傳輸模式時時間。健壯性函數包括以下兩部分
a.計算業務1的通行時間Grr和業務2的通行時間0 ,
權利要求
1.一種減小網絡資源開銷的業務調度方法，在減小網絡資源開銷的條件下，實現業務資源的高效調度，包括如下步驟A、建立網絡中的路徑、業務信號和控制信號一體化陣列模型；B、設置混合遺傳單元(即業務信號)的輸入和輸出變量；C、對混合遺傳單元中的染色體(Chromosome)種群進行初始化；D、使用遺傳算法獲得最優業務調度。
2.根據權利要求1的方法，對於所述步驟A其特徵在於在此陣列模型中，每一條路徑由多個微單元組成，並且每一條路徑有一個獨立的ID號，使用微單元的數目表示路徑的長度，令每一條路徑的微單元數量為15，一個微單元的大小為對拉4，且每個業務信號佔用3 個微單元；所有的業務信號都經過預處理，使其進過處理後具有虛擬固定長度，令業務信號的長度為30，每個業務信號有獨立的ID號，並且各自有固定的傳輸路徑，業務信號的傳輸速率為0至最大傳輸速率之間的任意值，最大傳輸速率為每秒5個微單元。
3.根據權利要求1的方法，對於所述步驟A其特徵在於在業務交換單元處，設置5個業務傳輸指示器，每個業務傳輸指示器具有相同功能，其中任意4個用於對業務信號的傳輸進行控制，剩餘1個用於對控制信號的傳輸進行控制，每一個傳輸指示器都有用於識別的獨立ID號，並且有暫停傳輸和允許傳輸兩種模式，使用陣列模型中的存儲單元來存儲這兩種模式相應的狀態信息。
4.根據權利要求1的方法，對於所述步驟B其特徵在於混合遺傳單元(即業務信號) 的輸入變量為①VP當傳輸指示器出現允許傳輸模式時，經過的業務信號數目；②PP當傳輸指示器出現允許傳輸模式時，經過的控制信號數目；③m:當傳輸指示器出現暫停傳輸模式時，處於等待狀態的業務信號的數目；④Ρβ:當傳輸指示器出現暫停傳輸模式時，處於等待狀態的控制信號的數目；混合遺傳單元(即業務信號)的輸出變量為①β :當傳輸指示器出現暫停傳輸模式時，在交換單元緩存中和處於即將到達狀態的業務信號數目； Q 、f 當傳輸指示器出現暫停傳輸模式時，在交換單元緩存中和處於即將到達狀態的控制信號數目；③ 業務信號從起始點到終點的傳輸時間。
5.根據權利要求1的方法，對於所述步驟C其特徵在於採用混合遺傳算法對混合遺傳單元中的染色體(Chromosome)種群進行初始化，即業務調度優化預處理，染色體為此優化問題的備選解集，令每一個染色體具有兩個基因，第一個基因為傳輸指示器出現暫停傳輸模式的時間，第二個基因為傳輸指示器出現允許傳輸模式的時間，其中I為業務信號或控制信號設染色體的初始種群數量為100，使用二進位編碼方式對染色體進行編碼，每一個染色體都具有一串0或1。
6.根據權利要求1的方法，對於所述步驟D其特徵在於對混合遺傳單元中的染色體進行種群評估，此步驟用於評估每個染色體如何對業務調度優化問題進行求解，其包括對染色體解碼為變量空間問題，以及使用這些參數核查此問題的解，在染色體交叉處理階段時，設置交叉係數為0. 8，在父代染色體上執行控制信號允許傳輸操作，其結果存儲於陣列模型中的存儲單元中，並且將父代染色體的信息與子代染色體的信息融合，重複上述步驟， 當在染色體交叉處理階段使用的種群數目為種群初始化數目的一半時，則停止計算，此時交叉處理階段完成；在變異階段，設置在父輩染色體上執行的變異係數為0. 2，根據在陣列模型中存儲的結果判斷，所產生的隨機數值和此數值與變異係數的比較結果由已發生變異或未發生變異的功能單元決定，重複上述步驟，當在變異階段使用的種群數目為種群初始化數目的一半時，則停止計算，此時變異階段完成。
7.根據權利要求1的方法，對於所述步驟D其特徵在於對混合遺傳單元中的染色體進行選擇，使用Roulette-wheel選擇概率方法選擇具有高健壯性的染色體，基於前面在變異階段獲得的結果，計算健壯性函數，此步驟用於識別基於參數的解，其中參數包括隊列大小、業務信號數目、傳輸指示器出現暫停傳輸模式的時間和傳輸指示器出現允許傳輸模式時時間，健壯性函數包括以下兩部分a.計算業務1的通行時間GTf和業務2的通行時間GTi, Gr7 = (Fg*通過時間)( 』= 通過吋間){ι 』其中Ρβ為當業務信號在交換單元中進行傳輸時，處於等待狀態的控制信號的數目； 『①為當控制信號在交換單元中進行傳輸時，處於等待狀態的業務信號的數目；b.計算在交換單元中處於等待狀態的業務信號的隊列長度和控制信號的隊列長度,β，FQ 哪* 「㈤)，PQ = {PP*RK、(ιν),其中i rr為業務信號在交換單元中處於等待狀態的時間，為控制信號在交換單元中處於等待狀態的時間，Gre為業務信號在交換單元的平均到達速率，為控制信號在交換單元的平均到達速率，相應的健壯性函數為{KP*RTx*Xmg)^ -通過時間」2 ,其中χρ =賊ρρ表示在交換單元中傳輸指示器出現允許傳輸模式時沒有業務信號或控制信號進行傳輸，RTx = RTy^RTf為/I·；交換單元中業務信號或控制信號處於等待狀態的時間，I卿='^VG^AVG為業務信號或控制信號在交換單元的平均到達速率，GTx=GTv^GTll為業務信號或控制信號在交換單元的傳輸時間，IQ = VmPQ為在交換單元中處於等待狀態的業務信號或控制信號的隊列長度。
8.根據權利要求1的方法，對於所述步驟D其特徵在於對混合遺傳單元中的染色體進行重組，並將重組後的染色體放置於當前染色體種群後，作為下一代染色體，重複上述步驟，直至當前染色體的迭代次數達到最大值，則停止計算，然後通過設置陣列模型中的存儲單元的元素對本次染色體個體的質量與前一代個體的質量進行比較，並進行本次染色體的評估。
全文摘要
本發明提供一種減小網絡資源開銷的業務調度方法，通過建立網絡中的路徑、業務信號和控制信號一體化陣列模型，和使用遺傳算法獲得在減小網絡資源消耗的條件下，實現業務的高效調度。
文檔編號H04W72/12GK102548010SQ20121005326
公開日2012年7月4日 申請日期2012年3月2日 優先權日2012年3月2日
發明者黃東 申請人:黃東