[發明專利]一種集中式的多路徑效用公平帶寬分配方法

有效

• 申請號: 202011054508.1
• 申請日: 2020-09-29
• 公開（公告）號: CN112422455B
• 公開（公告）日: 2023-05-23
• 發明（設計）人: 鄭嘉琦;余浩宇;陳貴海
• 申請（專利權）人: 南京大學
• 主分類號: H04L47/78
• 分類號: H04L47/78;H04L47/80
• 代理公司: 南京鐘山專利代理有限公司 32252
• 代理人: 陳月菊

1.一種集中式的多路徑效用公平帶寬分配方法，其特征在于，所述分配方法包括以下步驟：

S1，為每個用戶/應用指定分段線性效用函數；

S2，結合分段線性效用函數，采用預設的分段最大最小規劃算法計算得到一個部分分配方案，在所述部分分配方案中，分到帶寬最少的k％的用戶獲得的帶寬是最大最小公平的，其余的用戶獲得的帶寬不少于這k％用戶中單個用戶分到的最大帶寬，其中，k大于等于0小于等于100，且動態可調；

其中，所述結合分段線性效用函數，采用預設的分段最大最小規劃算法計算得到一個部分分配方案的過程包括以下步驟：

S21，將輸入的分段線性效用函數中的各個斷點對應的效用值排序，得到一個效用值向量在[u_i,u_i+1]這個效用值區間內，每個用戶獲得的效用值與分配得到的帶寬呈線性關系，i＝1,2,…,n-1；

S22，自效用值區間[u₁,u₂]開始，以最大化獲得效用值最少的用戶獲得的效用值為目標，列出線性規劃，并交由線性規劃求解器求解；

如果求得的最優值等于u_i+1，將效用值區間轉為[u_i+1,u_i+2]，否則判斷網絡中出現了飽和鏈路，將使用了飽和鏈路的用戶移出待分配帶寬的用戶集合，并將其效用值固定為求解出的最優值；

S23，重復在效用值區間內求解線性規劃，直到求解出的最優值等于u_n，或是已有不少于k％的用戶被移出待分配帶寬的用戶集合；

S3，根據步驟S2得到的部分分配方案，計算得到初始劃分，劃分是指同一用戶使用的多條路徑中，各條路徑上分配到的帶寬占總帶寬的比例；將該初始劃分作為輸入，不斷迭代執行預設的效用迭代填水算法，每輪迭代產生一個新的分配方案，直至連續兩輪產生的分配方案的差別小于既定閾值時，停止迭代，返回當前輪的分配結果作為最終的分配方案。

2.根據權利要求1所述的集中式的多路徑效用公平帶寬分配方法，其特征在于，步驟S1中，所述為每個用戶/應用指定分段線性效用函數包括以下兩種方式：

(1)根據實際需求選取對應的效用函數，結合選取的效用函數直接為每個用戶/應用指定分段線性效用函數，(2)采用分段線性函數擬合一般的效用函數得到分段線性效用函數。

3.根據權利要求2所述的集中式的多路徑效用公平帶寬分配方法，其特征在于，步驟S1中，所述根據實際需求選取對應的效用函數包括：對服務質量建模的數學函數、從以往歷史數據中獲取的各類用戶的需求概率累積分布函數，以及根據用戶優先級自主設置的分段線性效用函數。

4.根據權利要求1-3任意一項中所述的集中式的多路徑效用公平帶寬分配方法，其特征在于，所述分段線性效用函數的斜率與計算設備的允許精度范圍相關。

5.根據權利要求1所述的集中式的多路徑效用公平帶寬分配方法，其特征在于，步驟S3中，所述效用迭代填水算法的迭代過程包括：

S31，將輸入的分段線性效用函數中的各個斷點對應的效用值排序，得到一個效用值向量

S32，計算得到最大的效用值區間[u_i,u_i+1]，滿足所有活躍用戶在不違反鏈路容量約束的前提下取得至少u_i的效用值，在該效用值區間內，每個用戶效用值的增加與帶寬的增加成比例，這一比例即用戶的權值，i＝1,2,…,n-1；

S33，根據用戶的權值，進行帶權填水：按權增加每個用戶分配得的帶寬，用戶新增的帶寬按劃分分配到其各個路徑上，直到出現鏈路飽和，使用了飽和鏈路的路徑被稱為飽和路徑，調整未飽和路徑的劃分，繼續按權增加帶寬，直到所有路徑飽和為止。

6.根據權利要求1所述的集中式的多路徑效用公平帶寬分配方法，其特征在于，步驟S32中，采用二分搜索法，從當前效用值區間出發，計算得到最大的可行效用值區間[u_i,u_i+1]，計算過程包括以下步驟：

S211，指數搜索一個不可行的下標，即若當前下標可行，則將當前下標乘以二得到新的下標，直到不可行為止；

S212，在可行下標即當前區間的左端點與指數搜索得到的不可行下標之間做二分搜索，找到目標下標。