認(rèn)知異構(gòu)無線網(wǎng)絡(luò)中傳輸速率最大化的頻譜資源分配方法

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

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

1 引言

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

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

綜上所述，本文基于基礎(chǔ)設(shè)施的認(rèn)知異構(gòu)無線網(wǎng)絡(luò)結(jié)構(gòu)，重點(diǎn)關(guān)注認(rèn)知無線網(wǎng)絡(luò)感知到空閑頻譜信息及用戶業(yè)務(wù)需求后頻譜資源分配方法的研究，綜合考慮不同網(wǎng)絡(luò)頻譜資源屬性、不同業(yè)務(wù)需求的差異化及信道條件動(dòng)態(tài)性，以所有用戶總傳輸速率最大化為目標(biāo)，以業(yè)務(wù)需求及頻譜資源為約束條件，對(duì)頻譜資源進(jìn)行有效分配，主要貢獻(xiàn)如下。

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

3.1 網(wǎng)絡(luò)模型

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

圖1 認(rèn)知異構(gòu)無線網(wǎng)絡(luò)結(jié)構(gòu)

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

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

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

3.2 問題建模

不同網(wǎng)絡(luò)間頻譜的帶寬、時(shí)延、分組丟失率等特征屬性差異較大，同一網(wǎng)絡(luò)內(nèi)的頻譜塊差異較小，在一定范圍內(nèi)波動(dòng)；次用戶存在語音、視頻、文件傳輸?shù)榷喾N不同的業(yè)務(wù)需求，不同業(yè)務(wù)對(duì)價(jià)格、速率、時(shí)延、分組丟失率等要求不一樣，因此，本文的頻譜資源分配需綜合考慮頻譜資源的屬性、信道條件及次用戶的業(yè)務(wù)需求。

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

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

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

4 求解方法

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

4.1 化簡(jiǎn)方法

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

4.1.1 構(gòu)造效益矩陣及決策矩陣

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

表1 效益矩陣

表2 決策矩陣

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

4.1.2 化簡(jiǎn)約束條件

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

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

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

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

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

4.1.3 標(biāo)準(zhǔn)化處理

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

1)當(dāng)n=m時(shí)，不用處理。

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

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

同時(shí)，標(biāo)準(zhǔn)化還包括把效益最大化問題轉(zhuǎn)化為最小化問題，首先找到效益矩陣中的所有元素的最大值rmax，然后用該最大值減去效益矩陣的每一個(gè)元素得到新的效益βjk=rmax-rjk。

4.1.4 改進(jìn)匈牙利算法

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

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

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

計(jì)算已分配0 元素?cái)?shù)量num，如果num 等于效益矩陣維數(shù)n，則該分配問題的解已找到，否則轉(zhuǎn)至步驟3。

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

步驟4設(shè)未被步驟3 直線覆蓋的元素中的最小值為β，對(duì)未劃線的行減去β，劃線的列加上β，轉(zhuǎn)至步驟2 再次進(jìn)行指派。

化簡(jiǎn)方法

輸入

SU：請(qǐng)求業(yè)務(wù)接入的次用戶集合

PN：主網(wǎng)絡(luò)集合

csu：次用戶愿意支付的頻譜價(jià)格

rsu：次用戶最低速率需求

dsu：次用戶時(shí)延要求

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

csp：空閑頻譜資源價(jià)格

bsp：空閑頻譜資源帶寬

dsp：空閑頻譜資源時(shí)延

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

Bpn：各主網(wǎng)絡(luò)空閑頻譜資源帶寬

輸出

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

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

1)初始化。根據(jù)空閑頻譜信息、信道條件、應(yīng)用請(qǐng)求、過往分配決策結(jié)果等信息，生成對(duì)應(yīng)的數(shù)據(jù)表并初始化決策矩陣。

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

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

4)約束條件化簡(jiǎn)。將效益矩陣修正過程中所依據(jù)的服務(wù)質(zhì)量需求對(duì)應(yīng)的約束條件刪去。

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

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

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

4.2 改進(jìn)遺傳算法

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

圖2 改進(jìn)的遺傳算法流程

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

4.2.1 染色體編碼

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

圖3 染色體編碼示意

圖3 中，基因與次用戶對(duì)應(yīng)，m個(gè)基因?qū)?yīng)m個(gè)次用戶；基因值表示選擇接入的頻譜，3 個(gè)主網(wǎng)絡(luò)用2 個(gè)二進(jìn)制位n1n2表示，14 個(gè)空閑頻譜用5 個(gè)二進(jìn)制位s1…s5表示。因此，m個(gè)基因及其值表達(dá)了所有m個(gè)次用戶的頻譜分配方案。

4.2.2 修正操作

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

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

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

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

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

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

若經(jīng)過交叉、變異運(yùn)算的染色體符合上述任一條件則調(diào)用修正程序進(jìn)行修正，染色體判斷及修正過程具體如下。

步驟1計(jì)算染色體中基因所對(duì)應(yīng)的網(wǎng)絡(luò)及頻譜，提取該頻譜相應(yīng)的帶寬、價(jià)格、時(shí)延等屬性值。

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

步驟3基因修正。根據(jù)網(wǎng)絡(luò)及頻譜的取值范圍，將該基因的網(wǎng)絡(luò)及頻譜值隨機(jī)調(diào)整到其他網(wǎng)絡(luò)及頻譜，并返回步驟2 再次檢測(cè)該基因是否符合要求。

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

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

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

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

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

5 仿真

5.1 實(shí)驗(yàn)參數(shù)及方法

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

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果分析

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

5.2.1 傳輸速率對(duì)比

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

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

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

圖5 不同迭代數(shù)的傳輸速率對(duì)比

5.2.2 頻譜接入分析

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

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

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

圖7 基于化簡(jiǎn)方法的不同業(yè)務(wù)的網(wǎng)絡(luò)頻譜選擇概率

圖8 基于改進(jìn)遺傳算法的不同業(yè)務(wù)的網(wǎng)絡(luò)頻譜選擇概率

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

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

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

圖10 不同策略選擇接入不同網(wǎng)絡(luò)的概率

5.2.3 執(zhí)行效率比較

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

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

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

6 結(jié)束語

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

本文主要針對(duì)語音、視頻及文件傳輸?shù)确菍?shí)時(shí)業(yè)務(wù)，利用集中式網(wǎng)絡(luò)架構(gòu)進(jìn)行頻譜資源分配。然而，集中式網(wǎng)絡(luò)架構(gòu)信息交互和處理所帶來的交互時(shí)延和開銷會(huì)增加用戶接入時(shí)延，對(duì)于存在大規(guī)模用戶終端的場(chǎng)景或?qū)崟r(shí)業(yè)務(wù)具有局限性。因此，設(shè)計(jì)高效的用戶與基站的信息交互機(jī)制、研究分布式的頻譜分配方法或集中式、分布式相結(jié)合的混合結(jié)構(gòu)以提高分配效率是未來需要重點(diǎn)研究的問題。