董曉慶，程良倫，鄭耿忠，王濤

（1.韓山師范學院物理與電子工程學院，廣東 潮州 521041；2.廣東工業(yè)大學計算機學院，廣東 廣州 510006；3.廣東工業(yè)大學自動化學院，廣東 廣州 510006）

1 引言

隨著無線通信技術和無線業(yè)務的飛速發(fā)展，用戶流量需求激增。根據Cisco 的移動數據業(yè)務預測白皮書，2021 年全球的移動流量需求將達到49 EB，是2016 年的7 倍；同時，國際電信聯盟ITU（International Telecommunication Union）預測，2020 年全球移動通信頻譜需求將達到1 340～1 960 MHz。但是，目前大部分的頻譜資源已分配給不同機構使用，頻譜資源的緊缺成為制約無線網絡發(fā)展的重大瓶頸，即使第五代網絡（5G 網絡）增加可利用頻譜資源，頻譜資源仍然非常珍貴；另一方面，基于授權的靜態(tài)頻譜分配方法將無線頻譜劃分為若干固定寬度的頻譜段，由政府管理部門分配給授權用戶獨占使用，利用率低。德國、荷蘭、美國的部分地區(qū)，在20～3 000 MHz頻段的頻譜利用率僅為46%，新加坡部分地區(qū)在80～5 850 MHz 頻段的利用率僅為4.54%[1]。因此，如何提高頻譜資源利用率，以緩解激增的用戶流量需求與緊缺且利用率低下的頻譜資源的矛盾，是無線網絡需要解決的重要問題。

認知無線網絡為解決頻譜資源緊缺及利用率低的問題提供了有效的技術手段。獲得頻譜授權的用戶稱為主用戶，未獲得頻譜授權的用戶稱為次用戶。主用戶對頻譜擁有優(yōu)先使用權，可隨時使用頻譜；同時，主網絡可將空閑的授權頻段出讓或租賃給次用戶，使次用戶可以共享使用授權頻段[2]。在該網絡中，每個認知無線設備可以感知自己所在區(qū)域的通信環(huán)境，并通過集中式或分布式的方式處理這些感知信息，最后做出最佳的傳輸決策。認知無線電技術主要包括頻譜感知、頻譜管理、頻譜切換等功能。首先，通過認知無線電的頻譜感知功能，周期性地監(jiān)聽目標頻段，捕捉未被利用的空閑頻譜，確定頻譜的使用狀態(tài)；獲得頻譜感知信息之后，頻譜管理模塊根據感知結果分析周圍的頻譜環(huán)境，從中提取可用頻譜的相關信息，根據頻譜分析的結果制定最佳的頻譜使用策略[1]。在認知異構無線網絡環(huán)境下，多個主網絡重疊覆蓋，網絡頻譜資源特性各異，如頻譜價格、頻譜寬度、時延、分組丟失率等；同時，次網絡中分布多個次用戶及多種業(yè)務需求，不同業(yè)務對速率、支付價格、時延等要求也不盡相同，如何同時考慮頻譜資源的異構性、信道條件動態(tài)性及多次用戶的不同需求，高效合理地為各個次用戶選擇接入匹配的頻譜資源是一個挑戰(zhàn)。

綜上所述，本文基于基礎設施的認知異構無線網絡結構，重點關注認知無線網絡感知到空閑頻譜信息及用戶業(yè)務需求后頻譜資源分配方法的研究，綜合考慮不同網絡頻譜資源屬性、不同業(yè)務需求的差異化及信道條件動態(tài)性，以所有用戶總傳輸速率最大化為目標，以業(yè)務需求及頻譜資源為約束條件，對頻譜資源進行有效分配，主要貢獻如下。

1)在未來無線通信網絡密集部署環(huán)境下，基于認知無線網絡技術，綜合考慮多主網絡的異構頻譜特性、多次用戶的需求差異化及信道條件的動態(tài)性，以所有用戶總傳輸速率最大化為目標，以業(yè)務需求及頻譜資源為約束條件，建立了頻譜資源分配的數學模型。

2)設計了一種多項式時間復雜度的化簡求解方法。該方法根據用戶業(yè)務需求及過往周期分配結果修正效益矩陣實現約束條件化簡，將數學模型轉化為標準形式的0-1 規(guī)劃問題，并對傳統(tǒng)匈牙利算法進行改進以求解該頻譜分配問題。

2 相關工作

目前，異構無線網絡動態(tài)頻譜分配主要有基于圖論[2-4]、基于頻譜交易[5-7]、基于博弈論[8-11]、基于智能優(yōu)化算法[12-14]等方法。王欽輝等[2]、Tragos 等[15]、Tsiropoulos 等[16]分別綜述了頻譜資源動態(tài)分配方面的研究進展，總結了目前一些主流方法。

基于圖論的頻譜資源分配方法將認知無線電網絡拓撲結構抽象成無向連接圖。頂點表示參與分配的次用戶，每個頂點有可用信道集合，圖的邊集則由干擾限制決定，當且僅當2 個用戶節(jié)點不能同時使用某信道時，相應頂點用一條邊連接[2]。Peng 等[3]給出了頻譜分配的圖著色模型和算法，對分配的收益和公平性進行了較詳細的探討，并證明頻譜分配是一個非確定性多項式難（NP-hard）問題。朱冰蓮等[4]針對圖論頻譜分配模型下最優(yōu)頻譜分配策略搜索解困難、耗時長的問題，提出一種采用多策略離散人工蜂群的頻譜分配算法，首先根據感知技術得到通信環(huán)境狀況，建立頻譜分配的圖論模型，然后引入多策略離散人工蜂群算法進行最優(yōu)頻譜分配策略的搜索?；趫D論的方法簡單易行，多適用于靜態(tài)的網絡環(huán)境，這意味著拓撲結構的每次改變均需要重新計算分配，如果拓撲結構變化比較頻繁，則算法的有效性將受到很大挑戰(zhàn)[2]。

基于頻譜交易的分配方法借鑒商品交易的思想，將頻譜視為商品在用戶之間進行交易，提供頻譜資源的為頻譜賣家，需要使用頻譜的用戶為頻譜買家[2]。為協調滿意度、利潤及價格三者之間的關系，Ileri 等[5]利用買家接受模型描述買家滿意度與價格之間的關系，買家以一定概率接受賣家的頻譜服務，通過賣家利潤模型來描述賣家利潤與價格的關系。Gandhi 等[6]以最大化賣家利潤為目標、以干擾限制為約束條件，利用線性規(guī)劃對頻譜分配進行了分析，由于考慮干擾限制，求解最優(yōu)結果是一個NP-hard 問題，因此，文獻[6]對干擾限制條件進行線性化處理，可在多項式時間內求得次優(yōu)（suboptimal）解。為了提高認知無線網絡中頻譜共享所產生的效益，張士兵等[7]提出了一種基于代理的頻譜交易算法，該算法以代理商作為頻譜交易和分配的中介，減輕了多主用戶、多次用戶頻譜交易過程中的系統(tǒng)開銷，主用戶服務提供商之間的競爭或合作和次用戶之間的競拍均采用納什均衡作為最終的結果。基于頻譜交易的方法適用于主用戶與次用戶之間基于租用關系的應用場景，該類方法以定價機制為切入點，基于賣家利潤及買家滿意度完成交易。

認知無線電網絡中節(jié)點行為可能是自私和動態(tài)的，動態(tài)頻譜共享算法需要對此做出相應決策。博弈論為研究主體行為直接相互作用時的決策均衡提供了決策模型和理論，為動態(tài)頻譜共享問題提供了可行思路。Cao 等[8]提出一個議價博弈的分布式分配算法，通過議價博弈，使最優(yōu)分配不需要在每次拓撲結構變化時重新計算，同時，為了考慮算法的公平性，還基于Feed Poverty 策略設計了博弈算法，使算法公平性更好，但文獻[8]中的議價博弈交易框架假設網絡節(jié)點相互合作，然而，實際系統(tǒng)中的節(jié)點可能是自私的。用戶行為的自私性使靜態(tài)博弈模型難以獲得高效的納什均衡，重復博弈常被用來分析長期動態(tài)頻譜共享，由于需要多次博弈，重復博弈中的用戶可根據歷史行為做出更為靈活有效的決策，Etkin 等[9]針對非合作用戶之間的博弈，運用Folk 定理[10]分析了重復博弈中的效率，并通過實驗證明了其在長期動態(tài)頻譜共享中的高效性；孫杰等[11]提出了一種適用于次用戶組成的無線多跳網絡的underlay 方式下的全分布式頻譜分配算法，該算法將頻譜分配問題建模成靜態(tài)非合作博弈，證明了納什均衡點的存在，并給出了一種求解納什均衡點的迭代算法，然而當某個主網絡對未來傳輸效用不夠重視時，它會為了獲得比壟斷效用更高的傳輸效用而偏離當前的合作壟斷，從而降低了其他主網絡的當前和未來數據傳輸效用。

進化算法（EA,evolutionary algorithm）由于其進化操作規(guī)則的概率性、固有的并行性及充分利用適應值函數而不需要其他先驗知識等特點，在搜索過程中不易陷入局部最優(yōu)、不局限于單值解，適合求解傳統(tǒng)方法難以解決的復雜優(yōu)化問題。鄺祝芳等[12]針對無線 Mesh 網絡中多目標優(yōu)化的頻譜分配問題，以最大化總帶寬和最小化占用頻譜數為目標，利用粒子群優(yōu)化（PSO,particle swarm optimization）算法在多目標優(yōu)化方面的優(yōu)勢，提出基于 PSO 的多目標優(yōu)化頻譜分配算法 PSOSA，算法考慮頻譜之間的差異并重新定義 PSO 的粒子及粒子的3 種運算規(guī)則。李鑫濱等[13]在人工蜂群算法中引入動態(tài)加速因子和種群自適應比例因子，提出一種新的動態(tài)加速種群自適應人工蜂群算法，并將認知無線電TV 頻段頻譜分配模型中的分配矩陣與動態(tài)加速種群自適應人工蜂群算法中的可行解相對應，實現了空閑TV 頻段頻譜的合理分配。Hasan 等[14]針對第五代網絡（5G 網絡）中多異構主網絡重疊的場景，根據主網絡的頻譜特性及次用戶的需求，利用改進的遺傳算法及粒子群優(yōu)化算法求解頻譜分配問題，取得了較好的效果，但其沒有考慮頻譜資源的異構性，應用場景相對簡單。

綜上所述，異構無線網絡頻譜分配已經取得了較多的研究成果，但仍存在場景適應性的問題，比如基于圖論的分配方法適用于靜態(tài)的網絡環(huán)境；基于頻譜交易的分配方法適合于主用戶、次用戶間為租用關系的認知無線電系統(tǒng)，應用范圍具有局限性；博弈論分配模型一般用于主體行為直接相互作用時分析頻譜用戶之間的競爭與合作關系；對頻譜分配模型較復雜，難以在多項式時間求解的模型，可應用基于進化算法的分配方法進行求解。同時，上述方法研究對象大多是傳統(tǒng)的信道分配問題，即頻譜資源的特性較為單一，沒有考慮多異構主網絡頻譜資源的異構性。本文考慮更多的實際應用需求，包括主網絡間及主網絡內頻譜資源的異構性、次用戶業(yè)務類型及服務質量要求差異化、信道條件的動態(tài)性，上述方法顯然不能直接用于本文的頻譜分配，所以本文工作具有一定的研究意義。

3 頻譜資源分配0-1 規(guī)劃模型

3.1 網絡模型

圖1 為認知異構無線網絡結構，假設存在N個主網絡重疊覆蓋（如蜂窩網、WiMax 網絡），令網絡集為PN={pn1,pn2,…,pnN}，網絡中的主用戶均勻分布，其行為相互獨立，建模為開關二狀態(tài)的泊松過程。因此，頻譜資源可建模為空閑及忙狀態(tài)的獨立隨機二狀態(tài)模型?？臻e表示目前沒有主用戶占用該頻譜資源，可分配給次用戶，但同一時間只可分配給一個次用戶；忙狀態(tài)表示該頻譜資源被主用戶所占用，不能分配給次用戶。

圖1 認知異構無線網絡結構

假設次網絡為基于基礎設施（認知基站）的認知網絡，次用戶為認知網絡（次網絡）中基站覆蓋范圍內的配備認知設備的用戶，同一時間只能接入一個頻譜，次用戶集為SU={su1,su2,…,sum}。頻譜資源包括主網絡中空閑的授權頻譜及非授權的ISM（industrial scientific medical）頻譜，令頻譜集為SP={sp1,sp2,…,spn}。認知用戶周期性地感知識別信道條件、空閑頻譜信息，并將其與用戶業(yè)務請求信息發(fā)給認知基站。頻譜價格可通過頻譜代理獲得并存儲于認知基站中，相比信道條件的動態(tài)變化，頻譜價格可視為靜態(tài)常量。為簡化計算復雜度，假設同一網絡內頻譜資源分組丟失率狀況相近且變化相對緩慢，則分組丟失率等屬性信息可通過次用戶以頻譜使用反饋報告的形式發(fā)給認知基站，形成各網絡頻譜屬性數據。認知基站以次用戶應用請求信息、信道條件、空閑頻譜信息、過往周期的分配決策結果等作為決策依據，進行新一輪的頻譜資源分配決策。這里需要注意，沒有被主用戶占用的頻譜定義為空閑頻譜，認知基站在新一輪分配決策時需根據過往周期分配決策結果，確認頻譜是否已被次用戶所占用，若被占用且滿足用戶業(yè)務需求，則該頻譜不參與新一輪的分配決策。

用戶的傳輸速率與其獲得的頻譜帶寬、傳輸功率及信噪比有關，根據香農定理，用戶j選擇接入頻譜資源k的傳輸速率可表示為

其中，bjk表示用戶j占用頻譜資源k可獲得的帶寬；xjk表示次用戶j占用頻譜資源k的概率，xjk=1 表示占用該頻譜，xjk=0 表示不占用該頻譜；Sjk、Njk分別表示用戶j利用頻譜資源k進行傳輸時的信號功率及噪聲功率。本文研究基于overlay 模式下主網絡空閑頻譜的機會式接入及非授權ISM 頻譜的分配，因此，次用戶對主用戶的干擾可忽略不計，可利用大傳輸功率以獲得較快的傳輸速率；由于次用戶為認知基站覆蓋范圍內配備認知模塊的用戶，相對于與主網絡的距離，次用戶之間的距離可忽略不計。

3.2 問題建模

不同網絡間頻譜的帶寬、時延、分組丟失率等特征屬性差異較大，同一網絡內的頻譜塊差異較小，在一定范圍內波動；次用戶存在語音、視頻、文件傳輸等多種不同的業(yè)務需求，不同業(yè)務對價格、速率、時延、分組丟失率等要求不一樣，因此，本文的頻譜資源分配需綜合考慮頻譜資源的屬性、信道條件及次用戶的業(yè)務需求。

根據式(1)所示用戶的傳輸速率，可推導出所有次用戶的總傳輸速率，如式(2)所示。

如式(2)所示，在空閑頻譜資源受限情況下，根據用戶業(yè)務需求及信道條件，選擇不同的頻譜資源可得到不同的傳輸速率。因此，本文以所有次用戶總傳輸速率最大化為目標，以頻譜資源受限、次用戶服務需求等為約束條件，將頻譜分配問題建模為非線性約束0-1 整數規(guī)劃，具體如式(3)所示。

其中，式(3)表示最大化所有次用戶獲得的傳輸速率；式(4)表示接入頻譜需滿足用戶的速率需求；式(5)表示接入網絡y頻譜資源的所有用戶占用的帶寬總和不能超過該網絡空閑頻譜資源總帶寬，其中，By為網絡y的空閑頻譜資源的總帶寬限制；式(6)表示次用戶j接入頻譜價格不大于其可支付價格；式(7)表示次用戶接入的頻譜時延不大于其時延要求；式(8)表示次用戶接入頻譜分組丟失率不大于其分組丟失率要求；式(9)表示次用戶同一時間最多只能接入一個頻譜；式(10)表示任一頻譜資源不能同時分配給多于1 個的次用戶；式(11)表示次用戶j占用空閑頻譜k的概率，占用值為1，否則值為0。

4 求解方法

由第3 節(jié)可知，本文頻譜分配是一個非線性約束0-1 整數規(guī)劃問題，是NP-hard 問題，不存在多項式時間內求解的算法，因此，本文試圖通過對3.2節(jié)的數學模型進行化簡，尋求簡單的方法進行求解。同時，針對復雜的分配模型，本文還將利用改進的遺傳算法進行求解，以比較2 種基于不同技術途徑解決方法的求解思路。

4.1 化簡方法

如第3 節(jié)系統(tǒng)模型可知，本文將復雜的頻譜分配問題建模為非線性多約束條件0-1 規(guī)劃問題，化簡方法將通過分析約束條件及目標函數，對約束條件進行化簡，并通過改進匈牙利算法進行求解。

4.1.1 構造效益矩陣及決策矩陣

不同的用戶業(yè)務對頻譜資源要求不一樣，不同頻譜資源具有不同的屬性，通過次用戶與頻譜資源的良好匹配，可實現用戶總傳輸速率的最大化。基于此，在每一輪頻譜分配決策周期，本文首先根據認知基站獲得的空閑頻譜集及申請業(yè)務的次用戶，構造效益矩陣及決策矩陣。由于空閑頻譜資源可能在過往決策周期已被分配給其他次用戶，在新一輪頻譜分配決策時，需結合過往決策周期的頻譜分配結果，若空閑頻譜已分配且滿足次用戶的業(yè)務需求，則在構造矩陣時需排除該空閑頻譜。效益矩陣及決策矩陣具體如表1 和表2 所示。

表1 效益矩陣

表2 決策矩陣

如表1 所示，效益矩陣表示次用戶選擇相應頻譜資源獲得的效益值。因為本文的目標函數是用戶總傳輸速率的最大化，所以矩陣中各元素的值（效益值）直接用次用戶選擇對應頻譜資源時的傳輸速率表示。如式(1)所示，傳輸速率取決于頻譜帶寬、信號功率及噪聲功率。表2 所示的決策矩陣用于存儲分配決策結果，表示次用戶與頻譜資源的匹配關系，xjk=1表示次用戶j選擇接入頻譜資源k，xjk=0表示不接入。次用戶是否接入該頻譜，除了考慮該頻譜對應的傳輸速率外，還需考慮頻譜資源屬性是否與用戶業(yè)務需求匹配；同時，由于一個次用戶最多只能接入一個頻譜資源，一個頻譜資源最多只能分配給一個次用戶，所以決策矩陣任一行或列最多只能有一個元素為“1”。由表1 和表2 可知，化簡方法即是根據表1 中各用戶接入對應頻譜獲得的傳輸速率，并結合用戶服務需求選擇匹配的頻譜，以最大化傳輸速率為目標，最終得到表2 所示的決策矩陣中頻譜與次用戶的匹配關系。

4.1.2 化簡約束條件

對于多約束條件的分配問題，無法通過匈牙利算法直接求解，因此，本文試圖對約束條件進行約簡。

不同頻譜資源屬性及用戶業(yè)務需求均不一樣，如第3 節(jié)的數學模型，只有滿足價格、速率、時延等約束條件的頻譜資源才會分配給次用戶。比如對于用戶j及頻譜資源k，比較頻譜k各屬性值是否滿足次用戶j的業(yè)務需求，若不滿足用戶j的價格、速率、時延等任一方面的需求，則次用戶不會選擇接入該頻譜，即可將效益矩陣中第j行第k列的元素rjk置為0，使選擇該頻譜的效益值為0，確保頻譜k不會分配給次用戶j；若頻譜資源k各方面屬性均能滿足用戶k的需求，則效益矩陣中元素rjk值保持不變。依次類推，可將不滿足用戶業(yè)務需求的頻譜對應效益值置為0，確保用戶接入滿足服務需求的頻譜?；诖?，本文根據頻譜屬性與用戶業(yè)務需求關系，即式(4)～式(8)所示的約束條件，將不滿足業(yè)務需求的頻譜效益值置為0，改寫效益矩陣，得到各次用戶可用的空閑頻譜資源，從而消除掉部分約束條件。具體如下，式(4)表示所選頻譜速率大于或等于次用戶帶寬需求，因此可將速率小于次用戶要求的頻譜資源效益值置為0；同理，根據價格、時延及分組丟失率約束條件，分別把不符合次用戶要求的頻譜資源帶寬效益置為0，剩下的非0 部分即為滿足次用戶業(yè)務需求的可用頻譜資源。

通過上述處理，消除了式(4)～式(8)共5 個約束條件，3.2 節(jié)中的優(yōu)化模型可簡化為

【解讀】 跟所有其他檢測項目一樣，檢測前的相關解釋和咨詢應該充分細化和個性化。高通量測序還可能涉及比其他項目更多的隱私信息，因此很有必要對每個參與檢測個體進行充分的知情同意，胎兒的父母作為共同監(jiān)護人原則上應當共同接受檢測前教育。

以上的優(yōu)化模型可表示為如式(16)所示的標準矩陣形式。

4.1.3 標準化處理

由以上分析可知，這是一個典型的0-1 規(guī)劃中的指派問題，可用匈牙利算法進行求解。由于請求服務的次用戶數量跟空閑頻譜數量不一定相等（n≠m），即該分配問題可能為非平衡指派問題，因此使用匈牙利算法求解前需進行標準化預處理，具體如下。

1)當n=m時，不用處理。

2)當n＜m時，增加m-n個虛擬頻譜資源，并令其效益值為0，使次用戶優(yōu)先考慮實際存在的空閑頻譜。

3)當n＞m時，增加n-m個虛擬次用戶，令虛擬次用戶所在行的效益值為0，使實際存在的次用戶優(yōu)先考慮實際存在的空閑頻譜。

同時，標準化還包括把效益最大化問題轉化為最小化問題，首先找到效益矩陣中的所有元素的最大值rmax，然后用該最大值減去效益矩陣的每一個元素得到新的效益βjk=rmax-rjk。

4.1.4 改進匈牙利算法

通過約束條件化簡及標準化處理，將數學模型轉化為標準形式的0-1 規(guī)劃問題，可用匈牙利算法進行求解。傳統(tǒng)匈牙利算法一般包括變換系數矩陣、試指派、用最少直線覆蓋所有0 元素、重新變換系數矩陣并再次試指派。通常情況下，傳統(tǒng)匈牙利算法求解時需要循環(huán)執(zhí)行多次系數矩陣變換并試指派，若能減少循環(huán)次數，則可提高匈牙利算法效率。因此，本文通過對傳統(tǒng)匈牙利算法的關鍵步驟“變換系數矩陣”進行改進，以提高算法效率。該改進匈牙利算法具體步驟如下。

步驟1變換系數矩陣。與傳統(tǒng)匈牙利算法隨機地從行（或列）開始逐行（或列）減去該行（或列）的最小元素以得到0 元素不同，改進方法先統(tǒng)計各行最小元素總個數r及各列最小元素總個數c。當r≤c時，先從系數矩陣的每行中減去該行的最小元素，再從所得系數矩陣的每列中減去該列的最小元素；當r≥c時，先處理列數據再處理行數據。通過該方法可增加0 元素的數量，提高了試指派成功的概率，從而提高了算法的執(zhí)行效率。

步驟2試指派。試指派包括2 個子步驟。1)獨立0 指派。依次找到各行的獨立0 元素，計算該元素所屬主網絡k，如果接入該行對應次用戶后沒有超過主網絡干擾閾值，則把該元素分配給次用戶，并標記該元素所在行列不能再指派0 元素，更新主網絡干擾值；否則把主網絡在該行對應的獨立0 元素去掉。同理，依次搜索各列中的獨立0 元素，并與行獨立0 做同樣的處理。循環(huán)搜索各行列中的獨立0 元素，直到沒有獨立0 元素。2)非獨立0 指派。搜索各行列中是否還有0 元素，如有，則從0 元素最少的行列開始（如果行、列中有相同數量的0 元素，則可隨機選擇序數最小的行或列），計算該0元素所屬主網絡k，依照1)進行干擾值處理，把符合要求且未被指派的0 元素指派給該行對應次用戶，并進行指派標記處理。循環(huán)執(zhí)行，直到沒有搜索到0 元素。

計算已分配0 元素數量num，如果num 等于效益矩陣維數n，則該分配問題的解已找到，否則轉至步驟3。

步驟3用最少直線覆蓋所有0 元素，設直線數量為l，若l=n，表示解已找到，轉至步驟2 重新指派；若l＜n，轉至步驟4。

步驟4設未被步驟3 直線覆蓋的元素中的最小值為β，對未劃線的行減去β，劃線的列加上β，轉至步驟2 再次進行指派。

化簡方法

輸入

SU：請求業(yè)務接入的次用戶集合

PN：主網絡集合

csu：次用戶愿意支付的頻譜價格

rsu：次用戶最低速率需求

dsu：次用戶時延要求

lsu：次用戶分組丟失率要求

csp：空閑頻譜資源價格

bsp：空閑頻譜資源帶寬

dsp：空閑頻譜資源時延

lsp：空閑頻譜資源分組丟失率

Bpn：各主網絡空閑頻譜資源帶寬

輸出

OM：最優(yōu)決策矩陣

R：次用戶獲得總傳輸速率

1)初始化。根據空閑頻譜信息、信道條件、應用請求、過往分配決策結果等信息，生成對應的數據表并初始化決策矩陣。

2)效益矩陣構造。在新一輪頻譜分配周期，根據空閑頻譜信息及請求服務的次用戶構造效益矩陣，矩陣中的效益值為次用戶選擇相應頻譜獲得的傳輸速率，傳輸速率取決于帶寬、傳輸功率及噪聲功率。

3)效益矩陣修正。①若空閑頻譜在過往周期中已分配給次用戶且滿足次用戶需求，則不參與新一輪分配，并刪去效益矩陣中對應的空閑頻譜；②根據次用戶服務質量需求csu、rsu、dsu及l(fā)su，把不符合次用戶服務質量需求的效益值置為0。

4)約束條件化簡。將效益矩陣修正過程中所依據的服務質量需求對應的約束條件刪去。

5)標準化處理。首先，引入|n-m|個虛擬次用戶或頻譜資源，使n=m，以化解非平衡指派問題；然后，將傳輸速率最大化問題轉化為最小化問題，即利用最大效益值rmax減去效益矩陣的每一個值。

6)問題求解。通過改進傳統(tǒng)匈牙利算法的系數矩陣變換策略提高求解速度，并將次用戶與空閑頻譜資源的匹配關系存放于決策矩陣中。

7)返回最優(yōu)決策矩陣OM 及總傳輸速率R。

4.2 改進遺傳算法

本文對傳統(tǒng)遺傳算法進行改進，設計了基于改進遺傳算法的頻譜分配方法，包括適用于本文頻譜分配問題的染色體編碼方式及針對用戶業(yè)務需求等約束條件的染色體修正程序。改進的遺傳算法具體流程如圖2 所示。

圖2 改進的遺傳算法流程

如圖2 所示，改進的遺傳算法首先設計了適用于本文復雜頻譜分配問題的染色體編碼方案，并初始化種群；其次，將用戶獲得的傳輸速率作為評價指標計算適應度值，并依據適應度值大小優(yōu)選部分染色體進行后續(xù)的交叉及變異操作；再次，計算經過交叉、變異運算的個體是否滿足3.2 節(jié)中數學模型的約束條件，若不滿足則進行修正操作；最后，進行適應度評價并判斷是否達到最大迭代次數，達到則輸出優(yōu)化解，否則再次進行遺傳操作。下面重點介紹適用于本文頻譜分配問題的染色體編碼方案及修正操作，具體如下。

4.2.1 染色體編碼

用戶選擇接入匹配的頻譜資源以滿足業(yè)務需求，所有用戶的頻譜選擇結果構成了一個完整的頻譜分配方案，基于此，本文構建了基于二進制編碼的頻譜分配方案（染色體編碼）。例如，3 個主網絡重疊覆蓋，每個主網絡有14 個空閑頻譜，次網絡中有m個用戶，編碼示意如圖3 所示。

圖3 染色體編碼示意

圖3 中，基因與次用戶對應，m個基因對應m個次用戶；基因值表示選擇接入的頻譜，3 個主網絡用2 個二進制位n1n2表示，14 個空閑頻譜用5 個二進制位s1…s5表示。因此，m個基因及其值表達了所有m個次用戶的頻譜分配方案。

4.2.2 修正操作

由于交叉及變異操作的隨機性，會出現不滿足約束條件的染色體，例如同一個頻譜分配給多個次用戶。對于不符合要求的染色體，通常將其從種群中剔除。為避免剔除過多的不符合約束條件染色體而影響尋優(yōu)效果，本文對不滿足如下任一條件的染色體啟動修正程序，修復不符合條件基因。

1)頻譜價格大于用戶可支付價格。

2)頻譜帶寬小于用戶的帶寬需求。

3)時延大于用戶的時延要求。

4)分組丟失率大于用戶的分組丟失率要求。

5)同一頻譜分配給多個用戶。

若經過交叉、變異運算的染色體符合上述任一條件則調用修正程序進行修正，染色體判斷及修正過程具體如下。

步驟1計算染色體中基因所對應的網絡及頻譜，提取該頻譜相應的帶寬、價格、時延等屬性值。

步驟2判斷步驟1 中頻譜各屬性是否滿足其基因對應次用戶的業(yè)務需求，頻譜是否分配給多個次用戶等條件，如不符合要求，則執(zhí)行步驟3 修正該基因；若符合要求則返回步驟1 計算下一個基因，直到全部基因都符合要求并退出。

步驟3基因修正。根據網絡及頻譜的取值范圍，將該基因的網絡及頻譜值隨機調整到其他網絡及頻譜，并返回步驟2 再次檢測該基因是否符合要求。

4.3 化簡方法最優(yōu)性證明

由第3 節(jié)的數學模型可知，本文的頻譜分配是一個多約束條件的0-1 規(guī)劃問題，通過構造效益矩陣，并根據用戶業(yè)務需求等約束條件修正效益矩陣，令不符合約束條件的頻譜資源不會分配給對應的用戶，從而簡化掉部分約束條件，最終把多約束條件的0-1 規(guī)劃問題轉化為典型的0-1規(guī)劃中的指派問題。對于指派問題，匈牙利解法是一種行之有效的方法，匈牙利解法有以下2 個重要的定理。

定理1設一個任務分配問題的效益矩陣為{aij}，若{aij}中每一行元素分別減去一個常數ui，每一列元素分別減去一個常數Vj，得到一個新的效益矩陣{bij}（其中元素bij=aij-ui-Vj），則{bij}的最優(yōu)解等價于{aij}的最優(yōu)解。

定理2在新效益矩陣{bij}中，令對應于不同行、不同列的那組0 元素所對應的xij=1，其余xij=0，得到可行解x*=xij，則x*為效益矩陣{bij}的最優(yōu)解。

由定理1 及定理2 可知，匈牙利解法通過變換效益矩陣，找到不同行、不同列0 元素對應的可行解，該可行解就是該效益矩陣的最優(yōu)解。因此，本文通過化簡數學模型，將頻譜分配問題轉化為典型的指派問題，并利用匈牙利解法求解，可得到其最優(yōu)解。

5 仿真

5.1 實驗參數及方法

假設場景中存在2 種類型的空閑頻譜，一類是授權頻譜，包括蜂窩網絡及WiMax 網絡頻譜；另一類是非授權的ISM 頻譜資源。不同頻譜資源帶寬、價格、時延及分組丟失率不同。例如，蜂窩網頻譜資源時延要小于ISM 頻譜資源的時延；次用戶占用授權頻譜需支付一定費用，但可以免費使用非授權的ISM 頻段頻譜資源。本文頻譜資源屬性及業(yè)務需求相關參數參考文獻[17-20]，空閑頻譜資源屬性具體如表4 所示，其中頻譜帶寬、價格、時延及分組丟失率均處于一定范圍內，實驗中空閑頻譜資源屬性值在該范圍內隨機選取，并獨立實驗200 次取結果平均值作為最后的結果，以消除隨機性、增加可信度。

表4 空閑頻譜資源特征屬性

假設存在3 種類型業(yè)務需求：語音、視頻及文件傳輸。認知用戶到達概率服從泊松分布，不同業(yè)務對傳輸速率、時延、分組丟失率等服務質量要求不同，對價格的接受程度也不同，具體如表5 所示。

為評估所提方法的性能，本文通過實驗對所提化簡方法及改進遺傳算法與粒子群優(yōu)化算法進行對比。假設改進遺傳算法的種群規(guī)模為60，交叉概率為0.5，變異概率為0.01，最大迭代次數500；粒子群優(yōu)化算法的粒子規(guī)模為60，學習因子C1、C2均為2，慣性權重為1。同時，為消除隨機性，實驗進行了200 次，取平均值作為實驗結果。

表5 各業(yè)務類型服務質量要求

5.2 實驗結果分析

本文主要從獲得的傳輸速率、不同業(yè)務的頻譜分配接入及算法的時間效率方面進行評估，同時考察進化算法（下文中，進化算法指改進遺傳算法及粒子群優(yōu)化算法）的收斂性，具體如下。

5.2.1 傳輸速率對比

次用戶根據其服務質量需求，選擇接入不同的頻譜，具有不同的傳輸速率。圖4 顯示了次用戶總傳輸速率與用戶數的變化關系，其中，2 種進化算法取迭代100 次時的結果。如圖4 所示，3 種算法獲得的總傳輸速率均隨著次用戶數量增加而增加，本文所提化簡方法在各個用戶數量下的傳輸速率都最高，改進遺傳算法次之，粒子群優(yōu)化算法最低。這說明化簡方法在滿足用戶服務質量需求的同時，能有效地提高全網的傳輸速率，因為化簡方法將不滿足用戶需求的頻譜效益置為0，避免接入該頻譜，并在試指派時將高傳輸速率的頻譜分配給次用戶。

圖4 所有用戶獲得的傳輸速率

為了進一步觀察2 種進化算法的收斂性，圖5給出不同迭代次數下的傳輸速率,假設申請服務用戶終端數為50。如圖5 所示，在迭代次數小于50時，2 種算法獲得的總傳輸速率增長迅速，特別是改進遺傳算法；在迭代數大于50 時，總傳輸速率增長速度下降很快，改進遺傳算法在迭代次數達到200 次時已趨于收斂，說明了改進遺傳算法比粒子群優(yōu)化方法具有更高的進化效率。

圖5 不同迭代數的傳輸速率對比

5.2.2 頻譜接入分析

圖6給出了采用化簡方法的不同業(yè)務類型在各個分配周期的頻譜選擇接入情況。如圖6 所示，語音業(yè)務在各個不同的分配周期均選擇接入蜂窩網絡的空閑頻譜，因為該頻段頻譜資源能更好地滿足語音業(yè)務的低時延及低分組丟失率需求。視頻業(yè)務優(yōu)先接入到WiMax 網絡的頻譜資源，因為在滿足業(yè)務的價格、時延及分組丟失率要求的情況下，WiMax 頻譜資源具有更高的傳輸速率。文件傳輸服務對時延及分組丟失率要求較低，愿意支付的價格也較低，其主要接入Wi-Fi網絡頻譜。從圖6 中可看出，當接入頻譜資源不能滿足用戶業(yè)務需求時，化簡方法能夠在新一輪分配決策周期將其切換到滿足需求的頻譜資源。

圖6 不同分配周期的頻譜選擇接入

為更深層次分析不同算法傳輸速率差異的原因，下面進一步觀察分析接入不同頻譜的概率。本實驗中，改進遺傳算法及粒子群優(yōu)化算法取迭代100 次的結果，并取用戶數為50 時各個用戶接入不同網絡頻譜段的平均概率。如圖7～圖9 所示，對于申請語音業(yè)務的用戶，3 種方案均將用戶分配到蜂窩網絡1 和蜂窩網絡2 通信頻段的空閑頻譜上，這是因為語音業(yè)務的帶寬要求低而時延及分組丟失率等要求高，蜂窩網絡頻段能更好地滿足用戶的服務需求，同時由于語音業(yè)務可接受支付代價較小，所以申請語音業(yè)務次用戶更多地選擇接入價格較低的蜂窩網絡2 空閑頻譜；對于申請視頻業(yè)務的用戶，其對帶寬、時延、分組丟失率均有一定的要求，也愿意支付較高的價格，從圖7 可看出，采用化簡方法的用戶主要接入WiMax 網絡的頻譜；而圖8 采用改進遺傳算法及圖9 采用粒子群優(yōu)化算法的用戶則同時選擇接入WiMax 及Wi-Fi 網絡的頻譜；對于申請文件傳輸業(yè)務的用戶，其帶寬要求較大，但對時延及分組丟失率要求低，愿支付的代價也低，因此，申請文件傳輸業(yè)務的用戶都選擇接入免費的Wi-Fi 網絡頻譜。

圖7 基于化簡方法的不同業(yè)務的網絡頻譜選擇概率

圖8 基于改進遺傳算法的不同業(yè)務的網絡頻譜選擇概率

圖9 基于粒子群優(yōu)化算法的不同業(yè)務的網絡頻譜選擇概率

由以上分析可知，2 種方法申請語音及文件傳輸服務的用戶選擇接入的頻譜資源大致相同；主要區(qū)別在于申請視頻業(yè)務的用戶，化簡方法選擇接入到能提供更高速率的WiMax 頻譜，2 種進化算法則同時分布在WiMax 及Wi-Fi 網絡的頻譜，因此，化簡方法獲得了更大的用戶傳輸速率。

本文同時統(tǒng)計了3 種方法選擇接入各個網絡頻譜的概率，如圖10 所示。從圖10 中可知，蜂窩網絡1 與蜂窩網絡2 頻譜資源的選擇概率上幾種方法相差不大；在ISM 頻段的Wi-Fi 網絡頻譜資源選擇上，2 種進化算法的選擇概率略高于化簡方法，而在提供更高速率的WiMax 網絡上，化簡方法接入的概率更大，這與圖6～圖9 中各類型業(yè)務選擇接入頻譜資源的結果相符，即3 種方法的語音業(yè)務都接入到蜂窩網絡頻譜，化簡方法的視頻業(yè)務及文件傳輸業(yè)務分別接入到速率更高的WiMax 網絡及Wi-Fi 網絡頻譜，而2 種進化算法的視頻業(yè)務則同時接入到WiMax 網絡及Wi-Fi 網絡頻譜資源。這也進一步說明了圖4 中化簡算法獲得更大傳輸速率的原因。

圖10 不同策略選擇接入不同網絡的概率

5.2.3 執(zhí)行效率比較

圖11 給出了3 種方法的執(zhí)行效率對比情況，其中，改進遺傳算法及粒子群優(yōu)化算法給出不同迭代數下的執(zhí)行時間，化簡方法跟迭代數無關，不隨迭代次數變化。如圖11 所示，化簡方法的運行時間略小于40 ms，大約為2 種進化算法迭代數為30 時的運行時間，具有較高的執(zhí)行效率，因其主要進行較簡單的0 元素搜索運算；同時，粒子群優(yōu)化算法的運行時間稍小于改進遺傳算法，且兩者的運行時間均隨迭代次數的增加而線性增加，這是因為兩者都需一代代地進化來得到更優(yōu)的個體，但粒子群優(yōu)化算法不需要進行遺傳算法的交叉、變異運算，故其執(zhí)行效率稍高于改進遺傳算法。

圖11 執(zhí)行效率對比

從上述3 個實驗可知，化簡方法獲得了最高的傳輸速率，且具有較高的執(zhí)行效率；進化算法在達到一定迭代數時，可獲得接近于化簡方法的傳輸速率，但需較長的運行時間。

6 結束語

激增的流量需求與緊缺且利用率低的頻譜資源是一個矛盾，如何在認知異構無線網絡場景下實現頻譜資源高效分配以滿足用戶流量需求是一個重大挑戰(zhàn)。本文綜合考慮信道條件、空閑頻譜資源屬性及用戶服務需求，提出了基于用戶業(yè)務需求的傳輸速率最大化頻譜資源分配策略。該策略首先以用戶獲得的總傳輸速率最大化為目標，建立了頻譜資源分配的優(yōu)化模型。然后設計了一種多項式時間復雜度的求解化簡方法，該方法在每一輪頻譜分配決策周期，首先根據用戶業(yè)務需求及過往周期分配結果修正效益矩陣實現約束條件化簡，從而將優(yōu)化模型轉化為標準形式的0-1 規(guī)劃模型，并通過改進傳統(tǒng)匈牙利算法的關鍵步驟“系數矩陣變換”以提高算法效率，有效快速地求解出頻譜分配方案。同時，設計了一種基于改進遺傳算法的求解方法，以比較2 種不同技術路徑的求解思路。最后，通過實驗對本文所提方法與粒子群優(yōu)化算法進行對比分析，從實驗結果可知化簡方法在獲得高傳輸速率的同時具有較大效率優(yōu)勢。

本文主要針對語音、視頻及文件傳輸等非實時業(yè)務，利用集中式網絡架構進行頻譜資源分配。然而，集中式網絡架構信息交互和處理所帶來的交互時延和開銷會增加用戶接入時延，對于存在大規(guī)模用戶終端的場景或實時業(yè)務具有局限性。因此，設計高效的用戶與基站的信息交互機制、研究分布式的頻譜分配方法或集中式、分布式相結合的混合結構以提高分配效率是未來需要重點研究的問題。