基于加權(quán)二分圖的網(wǎng)絡(luò)選擇最新算法
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：張毅
1 引言
隨著用戶對無線通信業(yè)務(wù)質(zhì)量需求的不斷增長，現(xiàn)存的單一無線移動網(wǎng)絡(luò)很難滿足多種類型服務(wù)的需要。無線通信技術(shù)的迅猛發(fā)展促使終端多�；徒尤爰夹g(shù)多樣化，構(gòu)成了異構(gòu)網(wǎng)絡(luò)融合環(huán)境。在異構(gòu)網(wǎng)絡(luò)無線資源管理方面，網(wǎng)絡(luò)選擇算法是保障無線服務(wù)質(zhì)量(quality of service，QoS)的關(guān)鍵技術(shù)之一。
影響網(wǎng)絡(luò)選擇算法性能的因素很多，不僅要考慮網(wǎng)絡(luò)服務(wù)的質(zhì)量，還要考慮選擇代價和網(wǎng)絡(luò)資源的合理利用。當(dāng)考慮用戶端性能時，用戶QoS是評估網(wǎng)絡(luò)選擇效果的主要因素之一。參考文獻[1]中提出以用戶QoS和偏好為主要考慮因素的網(wǎng)絡(luò)選擇算法。參考文獻[2]將用戶的喜好和使用網(wǎng)絡(luò)成本等作為選擇最優(yōu)網(wǎng)絡(luò)的參數(shù)。參考文獻[3]在異構(gòu)融合網(wǎng)絡(luò)應(yīng)用層QoS保證的基礎(chǔ)上，采用添加索引和隨機最優(yōu)化思想進行最優(yōu)網(wǎng)絡(luò)選擇。參考文獻[4]將用戶性能與代價的比值作為用戶端的優(yōu)化目標，以最大化用戶性價比(performance-cost ratio，PCR)進行最優(yōu)網(wǎng)絡(luò)選擇。在很多研究網(wǎng)絡(luò)選擇算法的文獻中，基于博弈理論和代價函數(shù)的方法非常普遍。參考文獻[5]站在系統(tǒng)角度提出了一種基于代價函數(shù)的網(wǎng)絡(luò)選擇算法，結(jié)合流量平衡和接收信號強度，在呼叫阻塞概率和平均接收信號強度之間找到折中點。參考文獻[6]提出種群進化和強化學(xué)習(xí)兩種基于進化博弈論的網(wǎng)絡(luò)選擇算法。另外多目標優(yōu)化也會應(yīng)用在網(wǎng)絡(luò)選擇算法中。參考文獻[7]提出了一種多目標優(yōu)化函數(shù)最大化用戶體驗質(zhì)量，同時也作為網(wǎng)絡(luò)資源管理的接收概率，但是最終選擇網(wǎng)絡(luò)的最優(yōu)化目標還是最大化網(wǎng)絡(luò)端的收益，若用戶需求不在網(wǎng)絡(luò)設(shè)定的最優(yōu)范圍內(nèi)，用戶接入被拒絕。參考文獻[8]以可接入網(wǎng)絡(luò)的接入阻塞率相等為模糊神經(jīng)網(wǎng)絡(luò)參數(shù)強化學(xué)習(xí)的目標，提出動態(tài)適應(yīng)網(wǎng)絡(luò)負載的異構(gòu)無線網(wǎng)絡(luò)接人選擇算法，但是沒有考慮如何利用有限負載能力實現(xiàn)用戶和網(wǎng)絡(luò)端雙贏的局面。
從最優(yōu)選擇的判決條件來看，以上參考文獻在做網(wǎng)絡(luò)最優(yōu)選擇時較偏向于一方，如用戶的最佳QoS或者網(wǎng)絡(luò)的最大收益，沒有側(cè)重如何實現(xiàn)雙贏效果。本文提出一種基于加權(quán)最優(yōu)二分圖的網(wǎng)絡(luò)選擇算法，對不同用戶的不同QoS要求以及網(wǎng)絡(luò)的服務(wù)指標等參數(shù)進行數(shù)學(xué)建模，將QoS指標與服務(wù)指標進行比對，將具有最大匹配度的用戶和網(wǎng)絡(luò)作為網(wǎng)絡(luò)選擇的最優(yōu)結(jié)果。用戶與網(wǎng)絡(luò)之間的指標值越相似，匹配的可能性越大，為實現(xiàn)用戶效用和網(wǎng)絡(luò)收益的雙贏結(jié)果，尋找優(yōu)化分配全網(wǎng)資源的目標函數(shù)和分配方法。
2 網(wǎng)絡(luò)選擇場景模型
在異構(gòu)網(wǎng)絡(luò)融合場景中，假設(shè)不同網(wǎng)絡(luò)之間是重疊覆蓋的關(guān)系，且參與網(wǎng)絡(luò)選擇的用戶均處于網(wǎng)絡(luò)重疊覆蓋區(qū)域內(nèi)，不會移動到重疊區(qū)域外。為了綜合考慮用戶的QoS要求和網(wǎng)絡(luò)端的收益，動態(tài)調(diào)節(jié)網(wǎng)絡(luò)資源，考慮將用戶和網(wǎng)絡(luò)之間進行參數(shù)匹配，選取匹配度最大的鏈接作為網(wǎng)絡(luò)選擇結(jié)果。
首先考慮采用分布式算法，每個用戶從可接入網(wǎng)絡(luò)中選擇滿意度最高的網(wǎng)絡(luò)請求接入，一個網(wǎng)絡(luò)可能有多個用戶申請接人，也可能沒有用戶申請接人，網(wǎng)絡(luò)從申請接人的用戶中選擇帶來最大收益的用戶允許其接入。第一次選擇時沒有成功接入網(wǎng)絡(luò)的用戶，就會選擇滿意度次高的網(wǎng)絡(luò)請求接入，收到多個申請的網(wǎng)絡(luò)選擇帶來收益最大的用戶允許其接入。如此循環(huán)直到所有用戶都成功接入網(wǎng)絡(luò)。該方式有幾個缺陷：第一，如果重新選擇次數(shù)太多，用戶的接入時延會變長：第二，用戶和網(wǎng)絡(luò)來回選擇時都是單方面最優(yōu)化自己的利益，容易導(dǎo)致用戶在幾個網(wǎng)絡(luò)間來回切換始終不能成功接入網(wǎng)絡(luò)；第三，單方面滿足用戶或網(wǎng)絡(luò)的利益要求，容易導(dǎo)致資源浪費或網(wǎng)絡(luò)過載影響總體性能，若用戶和網(wǎng)絡(luò)端可以隨意修改接人價格，更有可能造成惡性競爭。
因此單純的分布式算法在此情況下很難保證網(wǎng)絡(luò)選擇的最優(yōu)性。考慮第三方介入的情況，如圖1所示，在用戶和網(wǎng)絡(luò)之間建立云端處理中心，收集用戶和網(wǎng)絡(luò)雙方的服務(wù)質(zhì)量需求和性能參數(shù)，比較雙方要求的相似度，尋找全局最優(yōu)的匹配結(jié)果。如果用戶需求或網(wǎng)絡(luò)參數(shù)有變化，能夠快速動態(tài)地改變下次匹配的計算參數(shù)，得出新的全局最優(yōu)選擇結(jié)果。本文后續(xù)提出的算法流程和計算均在云端處理中心進行，每次網(wǎng)絡(luò)選擇后，如果有網(wǎng)絡(luò)過載的情況，可以對接入過載網(wǎng)絡(luò)的新用戶重新進行次優(yōu)的網(wǎng)絡(luò)選擇，平衡網(wǎng)絡(luò)負載。
3 網(wǎng)絡(luò)選擇過程建模
綜合考慮用戶對多業(yè)務(wù)服務(wù)的QoS需求和網(wǎng)絡(luò)的負載壓力，本文提出一種基于加權(quán)二分圖最優(yōu)匹配的網(wǎng)絡(luò)選擇算法，將網(wǎng)絡(luò)選擇過程建模為加權(quán)二分圖最優(yōu)匹配過程，尋找兼顧雙方利益的最優(yōu)匹配結(jié)果。
3.1 加權(quán)二分圖建模
將異構(gòu)網(wǎng)絡(luò)融合場景中的網(wǎng)絡(luò)選擇問題建模為加權(quán)二分圖模型G=(X，Y，，E)。其中，G表示一個完整的二分圖；X表示異構(gòu)網(wǎng)絡(luò)中請求接入網(wǎng)絡(luò)的用戶，一共有m個呼叫請求；Y表示所有備選異構(gòu)網(wǎng)絡(luò)，一共有n個備選網(wǎng)絡(luò)，每個呼叫請求都至少可以接人其中一個網(wǎng)絡(luò)：E為二分圖中邊的集合，表示每一條呼叫請求與網(wǎng)絡(luò)之間的鏈路，如圖2所示，邊的權(quán)值表示為ei，網(wǎng)絡(luò)選擇的過程就是尋找該加權(quán)二分圖中邊的權(quán)值和最大的完備匹配。
3.2參數(shù)相似度和匹配度
求出加權(quán)二分圖最優(yōu)匹配的關(guān)鍵步驟是計算每條邊的權(quán)值ei，為了綜合考慮用戶和網(wǎng)絡(luò)兩者的利益，邊的權(quán)值對應(yīng)為用戶QoS需求和網(wǎng)絡(luò)服務(wù)指標之間的匹配度。匹配度表示了用戶和網(wǎng)絡(luò)雙方參數(shù)的相似及適合程度。
用戶根據(jù)不同的業(yè)務(wù)類型需要不同的QoS性能，時延、誤碼率、分組丟失率、隊列長度等QoS要求都可以在一定條件下轉(zhuǎn)換成速率要求。因此帶寬、速率、功率、價格等資源參數(shù)可以同時作為用戶呼叫和網(wǎng)絡(luò)的需求參數(shù)進行配對比較，將用戶呼叫和網(wǎng)絡(luò)的性能需求以矢量形式表示如下：
其中，葉衷示用戶呼叫的QoS矢量，”。表示網(wǎng)絡(luò)的性能
矢量，后是參數(shù)種類。首先對用戶呼叫和網(wǎng)絡(luò)需求矢量進行
相似度計算。利用夾角余弦求兩向量之間的相似度為：
根據(jù)業(yè)務(wù)類型和網(wǎng)絡(luò)運行情況變化，用戶和網(wǎng)絡(luò)對矢
量參數(shù)的偏好權(quán)重也會改變，因此令ajk表示用戶呼叫j對
參數(shù)k的偏好權(quán)重，nih表示網(wǎng)絡(luò)i對參數(shù)k的偏好權(quán)重。
用戶呼叫需求與網(wǎng)絡(luò)參數(shù)的匹配度可以表示為：
令
，下面求取該二分圖的最優(yōu)匹配。
3.3最優(yōu)加權(quán)二分圖匹配
尋找加權(quán)二分圖最優(yōu)匹配(weighted bipartite graphoptimal matching, WBGOM)，實際上是尋找子圖G’=(x，Y，E’)，E’∈E，滿足對任意一個子圖G"，子圖G’的任意兩條邊不相鄰，且邊數(shù)最多，邊的權(quán)值和最大。該匹配過程可以用以下優(yōu)化模型描述：
其中，
是二進制變量，
=1表示網(wǎng)絡(luò)i與呼叫請求j的鏈路連通，否則鏈路不通，Cl和C3保證每個呼叫請求同時只能匹配一個網(wǎng)絡(luò)；z。是二分圖中每條邊的權(quán)值，由式(4)計算得到。
從這個優(yōu)化問題可以看出，呼叫請求與網(wǎng)絡(luò)之間是一一對應(yīng)的匹配關(guān)系，當(dāng)每個網(wǎng)絡(luò)都匹配了一個用戶，或者每個用戶都匹配了一個網(wǎng)絡(luò)，且該匹配得到的權(quán)值和最大時，優(yōu)化問題有最優(yōu)解。求解過程雖然不難但是復(fù)雜度高，若使用窮舉法則時間復(fù)雜度為
。求解加權(quán)二分圖的最優(yōu)匹配還可以采用Kuhn-Munkrcs算法，流程如下：
(1)初始化頂標，令X集合中每個元素的頂標為對應(yīng)邊的最大權(quán)值，y集合中每個元素頂標為零；
(2)用匈牙利算法尋找完備匹配；
(3)若未找到完備匹配則更改可行頂標的值；
(4)重復(fù)步驟(2)和步驟(3)直至找到相等子圖的完備匹配。
Kuhn-Munkres算法的時間復(fù)雜度最大為0(n4)，因此當(dāng)m>4時用Kuhn-Munkres算法求解優(yōu)化問題(5)能夠降低復(fù)雜度。
3.4基于負載均衡的網(wǎng)絡(luò)重選擇
在第3.1節(jié)中，備選網(wǎng)絡(luò)可以通過調(diào)節(jié)參數(shù)的偏好權(quán)重來調(diào)整網(wǎng)絡(luò)內(nèi)的資源使用情況。例如，若備選網(wǎng)絡(luò)只能接受低速率的服務(wù)要求，則增大速率的權(quán)重以選取低速率的用戶；若備選網(wǎng)絡(luò)帶寬有限，則增大帶寬的權(quán)重以選取帶寬要求不高的用戶。但是也不能排除經(jīng)過匹配后出現(xiàn)網(wǎng)絡(luò)擁擠的情況。因此考慮當(dāng)網(wǎng)絡(luò)的負載情況不能保證用戶服務(wù)需求時，匹配到該網(wǎng)絡(luò)的用戶可以重新進行匹配，在二分圖中尋找次優(yōu)的網(wǎng)絡(luò)進行接入，實現(xiàn)網(wǎng)絡(luò)負載平衡。
假設(shè)網(wǎng)絡(luò)i的資源容量為鼠，定義網(wǎng)絡(luò)空閑資源占有率為：
其中，眩是接入網(wǎng)絡(luò)i的用戶呼叫集合，bj(t)是用戶呼叫j使用的網(wǎng)絡(luò)資源。
假設(shè)網(wǎng)絡(luò)設(shè)有空閑資源占有率的警戒門限p．，當(dāng)n≥pit)時，網(wǎng)絡(luò)i可以拒絕二分圖匹配結(jié)果，選擇接入網(wǎng)絡(luò)i的用戶可以重新選擇次優(yōu)的網(wǎng)絡(luò)。重選擇過程如圖3所示，選擇結(jié)果可以表示為：
其中，
表示接入網(wǎng)絡(luò)i’的用戶呼叫j’需要重新選擇接入網(wǎng)絡(luò)。
4仿真及結(jié)果分析
為了分析驗證本文提出的WBGOM網(wǎng)絡(luò)選擇算法，將所提算法與參考文獻[4]中PCR算法和參考文獻[7]中多目標優(yōu)化接人選擇 (multicriteria optimization of accessselection，MOAS)算法進行仿真比較。假設(shè)3個網(wǎng)絡(luò)重疊覆蓋，重疊覆蓋區(qū)域內(nèi)有60個多模用戶，用戶呼叫到達過程服從泊松分布，為不同業(yè)務(wù)統(tǒng)計方便，設(shè)置等效呼叫到達
率a。例舉3種用戶呼叫業(yè)務(wù)需求見表1，考慮到時延敏感業(yè)務(wù)和高速業(yè)務(wù)在網(wǎng)絡(luò)選擇中的權(quán)重可能較高，因此針對時延和帶寬要求不是最高的業(yè)務(wù)，定義最高價格預(yù)算以提高其網(wǎng)絡(luò)選擇的權(quán)重，也防止這類業(yè)務(wù)在網(wǎng)絡(luò)選擇過程中被忽略。網(wǎng)絡(luò)根據(jù)實際情況提供不同的傳輸速率，并根據(jù)速率調(diào)整價格，網(wǎng)絡(luò)參數(shù)見表2。
根據(jù)式(1)、式(2)建立用戶和網(wǎng)絡(luò)的參數(shù)模型，然后根據(jù)式(4)計算出匹配度帶人加權(quán)二分圖模型，根據(jù)第3節(jié)給出的網(wǎng)絡(luò)選擇過程，利用Kuhn-Munkres算法求解最優(yōu)匹配和次優(yōu)重匹配后，考察以下參數(shù)來比較算法性能。
(1)接入阻塞概率
定義為網(wǎng)絡(luò)選擇過程中，呼叫接入請求沒有被任何網(wǎng)絡(luò)接受，接入失敗的概率。該參數(shù)主要考察對時延敏感性不同的業(yè)務(wù)接入網(wǎng)絡(luò)的情況。
其中，Ⅳ是網(wǎng)絡(luò)選擇次數(shù)，因為每次選擇都是一一對
應(yīng)，所以接入失敗時
。
(2)QoS滿意度
定義為業(yè)務(wù)呼叫接入所選網(wǎng)絡(luò)的性價比與期望性價比的比值，其中性價比定義為速率與代價的比值。該參數(shù)主要考察業(yè)務(wù)呼叫接人所選網(wǎng)絡(luò)的服務(wù)情況。
其中，
分別表示業(yè)務(wù)呼叫接入網(wǎng)絡(luò)后得到的傳輸期望的速率和代價；
分別代表業(yè)務(wù)呼叫接入網(wǎng)絡(luò)前期望的速率和代價。
(3)網(wǎng)絡(luò)負載變化
網(wǎng)絡(luò)負載定義為接人用戶的總符號速率與網(wǎng)絡(luò)符號速
率的比值。
其中，η是網(wǎng)絡(luò)i的負載，Ω是接入網(wǎng)絡(luò)i的用戶集合，ri是用戶i的數(shù)據(jù)速率，rm是用戶的調(diào)制編碼速率，SF是擴頻因子，非擴頻時設(shè)置為1，R。是網(wǎng)絡(luò)的符號速率。他值越大表示網(wǎng)絡(luò)負載越重。
圖4給出了3種業(yè)務(wù)接入阻塞概率隨呼叫到達率變化的情況。3種算法都保證業(yè)務(wù)1（時延敏感業(yè)務(wù)）的接入阻塞概率最低，業(yè)務(wù)3（時延不敏感業(yè)務(wù)）的接入阻塞概率最高，有利于實時業(yè)務(wù)的QoS保障。從單一業(yè)務(wù)看，本文提出的WBGOM算法得到的接入阻塞概率為0．符合算法一一匹配并可負載均衡重選擇的特點：PCR算法的接入阻塞概率在呼叫到達率升高后稍高于WBGOM算法：MOAS算法的呼叫接入阻塞概率最高，這是算法中隨機分配預(yù)測資源過程引起的。
圖5給出3種業(yè)務(wù)QoS滿意度隨呼叫到達率變化的情況。業(yè)務(wù)2（時延較敏感業(yè)務(wù)）的QoS滿意度最高，這是因為業(yè)務(wù)2的QoS需求不是最高的，且出價最高，在網(wǎng)絡(luò)選擇時容易匹配到網(wǎng)絡(luò)；業(yè)務(wù)1和業(yè)務(wù)3對QoS要求較高，出價相對較低，所以網(wǎng)絡(luò)選擇時匹配網(wǎng)絡(luò)不一定能滿足期望的性價比。這個問題可以利用博弈競價理論進一步研究解決，因篇幅限制本文不再做深入分析。從單一業(yè)務(wù)看，PCR算法以最大化用戶的性價比為網(wǎng)絡(luò)選擇依據(jù)，因此業(yè)務(wù)呼叫的QoS滿意度很高，而本文提出的WBGOM算法的QoS滿意度與其相近，甚至業(yè)務(wù)2和業(yè)務(wù)3的QoS滿意度超過PCR算法。這是因為在PCR算法中有些呼叫請求被分配了多余的網(wǎng)絡(luò)資源，而有些呼叫請求分配不到足夠的網(wǎng)絡(luò)資源。WBGOM算法充分考慮用戶和網(wǎng)絡(luò)雙方的利益，盡可能按需合理分配，使業(yè)務(wù)呼叫與網(wǎng)絡(luò)之間的匹配度最大。MOAS算法的QoS滿意度最低，算法中只有預(yù)測的資源滿足用戶呼叫的資源需求時才能接入網(wǎng)絡(luò)。
圖6給出網(wǎng)絡(luò)負載隨呼叫到達率變化的情況。在WBGOM算法和MOAS算法中，每個網(wǎng)絡(luò)的負載隨呼叫到達率的增大而增大，WBGOM算法中根據(jù)負載門限調(diào)節(jié)每個網(wǎng)絡(luò)的負載情況，因此網(wǎng)絡(luò)間負載交替上升，MOAS算法中無法滿足的業(yè)務(wù)呼叫被拒絕接入網(wǎng)絡(luò)導(dǎo)致總體網(wǎng)絡(luò)負載較低。PCR算法中網(wǎng)絡(luò)負載較高，網(wǎng)絡(luò)1的負載經(jīng)常處于最高狀態(tài)，而網(wǎng)絡(luò)2和網(wǎng)絡(luò)3有時卻幾乎沒有負載。從以上分析可以看出．WBGOM算法能夠動態(tài)調(diào)整不同網(wǎng)絡(luò)之間的負載，MOAS算法的網(wǎng)絡(luò)負載雖然低于WBGOM，接入阻塞概率卻遠遠高于后者，接人的呼叫數(shù)量少，網(wǎng)絡(luò)負載也低，但是負載均衡能力較弱。PCR算法的負載均衡能力最差，用戶呼叫請求易偏向于單個網(wǎng)絡(luò)。
將網(wǎng)絡(luò)間最大負載值與最小負載值的差作為進一步分析算法負載均衡能力的參數(shù)，圖7給出3種算法的網(wǎng)絡(luò)負載差異隨呼叫到達率變化的情況。顯然PCR算法的負載均衡能力最差，網(wǎng)絡(luò)間負載差異最高。WBGOM算法與MOAS算法的負載差異相近，如圖6所示，MOAS算法中呼叫請求易偏向單個網(wǎng)絡(luò)，使得該網(wǎng)絡(luò)的負載始終高于其他網(wǎng)絡(luò)。
5 結(jié)束語
本文提出了一種基于加權(quán)二分圖最優(yōu)匹配的網(wǎng)絡(luò)選擇算法，選擇供需最匹配的用戶和網(wǎng)絡(luò)，優(yōu)化異構(gòu)網(wǎng)絡(luò)中的資源分配。將用戶業(yè)務(wù)需求和網(wǎng)絡(luò)參數(shù)進行匹配度計算，以最大化匹配度為目標建立加權(quán)二分圖模型并求解最優(yōu)網(wǎng)絡(luò)選擇結(jié)果，對擁擠網(wǎng)絡(luò)中的呼叫請求重新匹配次優(yōu)網(wǎng)絡(luò)，實現(xiàn)網(wǎng)絡(luò)負載均衡。與其他算法相比，本文提出的WBGOM算法能夠在保障呼叫請求接人概率和QoS需求的同時動態(tài)調(diào)整網(wǎng)絡(luò)負載，實現(xiàn)負載均衡的異構(gòu)網(wǎng)絡(luò)資源分配。未來可進一步考慮業(yè)務(wù)優(yōu)先級調(diào)度、網(wǎng)絡(luò)負載超限等情況下所提算法的性能和改進。
6摘要：
在異構(gòu)網(wǎng)絡(luò)融合場景中，為r合理利用異構(gòu)網(wǎng)絡(luò)資源，提出了一種基于加權(quán)二分圖的網(wǎng)絡(luò)選擇算法。將網(wǎng)絡(luò)選擇過程映射為尋找最優(yōu)加權(quán)二分圖的過程，用戶和網(wǎng)絡(luò)雙方的需求經(jīng)數(shù)學(xué)建模后進行供需最優(yōu)匹配，供需匹配有二次選擇機會以平衡網(wǎng)絡(luò)負載。與其他算法相比，提出的算法可以為不同QoS業(yè)務(wù)提供滿足需求的匹配結(jié)果，并且能夠動態(tài)調(diào)整網(wǎng)絡(luò)負載，實現(xiàn)異構(gòu)網(wǎng)絡(luò)融合場景中用戶需求和網(wǎng)絡(luò)資源的合理匹配。
