基于預售機制的動態頻譜分配算法研究

劉覺夫，陳 曉

（華東交通大學 信息工程學院，江西 南昌330013）

0 引 言

無線業務的迅速增長及高速化和寬帶化的需求使得無線頻譜資源變得日益緊張，甚至成為制約其發展的瓶頸之一［1］。然而，已分配給用戶的頻譜資源卻在時間或空間上存在不同程度的閑置，導致大量 “頻譜空洞”存在。認知無線網絡被認為是下一代無線網絡的核心架構之一，該網絡能解決日益增長的頻譜使用需求和低下的頻譜使用率之間的矛盾［2］。通過伺機接入臨時可用頻譜資源，大幅度提高頻譜利用率。頻譜資源分配是影響頻譜資源利用率的關鍵，因此如何合理高效地管理和分配頻率資源成為一項艱巨而又緊迫的任務。

傳統的靜態頻譜分配（FSM）方法簡單，干擾性小，但頻譜利用效率低，難以滿足日益壯大的無線用戶的各種需求，于是動態頻譜分配（DSM）成為國內外的專家學者的研究重點并提出了多種具體分配模型和算法，例如，Cao等人基于定價拍賣模型，采用公平的業務保證機制并提出了本地議價算法，提高了頻譜分配的公平性，降低了系統的復雜性［3］；zheng等人提出使系統的性能、復雜度和通信成本取得折衷的基于規則的頻譜管理方案［4］；陳杰、張平等人提出的基于討價還價博弈的動態頻譜管理方案等［5］。本文基于認知無線網絡的架構，在動態頻譜分配中引入了經濟活動中的預售機制，提出基于預售機制的動態頻譜管理（PS－DSM Presell－DSM）方案，該機制充分利用了不同網絡在不同時間和空間維度上對頻譜需求的差異及在網絡通信時的閑置計算能力，以提高頻譜資源利用效率。仿真結果表明，該種分配算法能夠減少分配延遲、提高分配效率和頻譜利用率。

1 PS－DSM系統模型

1.1 PS－DSM 架構

PS－DSM的基本架構包括邏輯頻譜交易市場、交易雙方和信息交互信道，其中，頻譜交易市場來源頻譜池［6］的概念并可根據交易對象性質劃分為三級，最高級為不同運營商之間進行頻譜交易的頂級市場（top market，TM），中級為單運營商多個RAT（無線接入網）進行頻譜交易的中級市場（middle market，MM）。第三級為同構網絡內部進行頻譜交易的基礎市場（basic market，BM）。三級市場之間的關系如圖1所示。若某個RAN或網內用戶的頻譜資源在滿足自身業務需求后仍有剩余，則它可以作為 “頻譜出租者（SL）”在頻譜市場上出租額外的空閑頻譜以最大化頻譜利用率和自身利潤；若某個RAN或網內用戶因業務的增長而缺少頻譜資源，它將成為頻譜市場的消費者，即作為“頻譜租借者（SR）”從其頻譜出租者中租用頻譜以繼續自身需求。

圖1 三級市場關系

此外，交易雙方需要了解一些必要的交易信息，如頻譜租借者需要了解當前或下個周期內正在出租的可用頻譜及這些頻譜的質量參數，頻譜出租者需要根據多個周期內的頻譜交易量及其均價來制定預售價格等。作為公共信道，認知導頻信道（CPC）［7］可被用來通知相關的交易信息。

PS－DSM是一種周期和前攝的頻譜管理操作，不同等級的頻譜市場采用不同粒度的時間量做周期單位。基礎市場是本架構的基礎，因此本文主要討論基礎市場中的頻譜交易，其交易周期一般設為秒／分鐘級，而中級和頂級頻譜交易的周期則為小時級甚至天級。用τ表示交易周期，則對于集合T＝｛1，2，3，4……｝，時刻t和t＋1（t∈T）的時間間隔為τ，表示頻譜出租和租用的最大周期為τ，需強調的是，t時刻的DSM對應t＋1時刻各用戶提供的業務是必要的。

1.2 交易角色及其職能與收益

為完成頻譜交易，每個市場中設置一個頻譜服務中介站（spectrum agent，SA）。SA的主要職責為確定交易時鐘并劃分交易周期，在交易過程中，借助CPC廣播本周期及下個周期內正在招租的頻譜信息及其質量參數等，確保交易雙方能夠了解交易信息。SA在交易過程中起中介協調的作用。交易過程中的所涉及角色及其職能、收益計算見表1。

表1 交易角色職能收益

2 PS－DSM方案實現

PS－DSM采用周期運行方式，在頻譜等級劃分確定的基礎上，每個周期內，方案實現主要有4個關鍵環節：SL頻譜定價、SA價格調整、SR博弈選擇、SR評價反饋。

2.1 頻譜等級劃分

SL上報出租的頻譜質量和適用業務狀況各不相同，為減小SR頻譜選擇復雜度，SA將招租頻譜根據其業務參數進行等級劃并按其質量由高到底排序，為簡化計算，本文將頻譜設為4個等級：A1、A2、B1、B2，其中A代表實時性業務，B代表非實時性業務，1代表高質量層，2代表低質量層，例如A2代表適合實時性業務中質量要求稍低的頻譜，如語音業務。頻譜等級劃定后，SR只需計算適合自身業務的頻譜，從而減小了計算范圍，節省時間，提高分配效率。

2.2 SL 頻譜定價

SL將自身的空閑頻譜信息上報至SA進行招租，其中包括描述頻譜質量的各項關鍵參數與頻譜價格c／單位，其制定是影響SL收益的關鍵因素，因此需進行多方面的考慮。根據供求價值規律，SR的頻譜需求量越大，則c值應越高，需求量越少，則c值應越低，否則難以進行成功出租獲取收益。SL進行頻譜定價過程如下：首先收聽SA廣播3條記錄信息：①前一周期的頻譜出租比率Srpre及成功交易的平均價格ACpre；②當前周期已出租頻譜的比率Srnow及成功交易平均價格ACnow，③SA基于時間序列預測算法的所得下一周期的頻譜需求量Qnext；SL根據所收聽的信息，使用定價函數進行頻譜定價。

下一周期的頻譜定價函數如下

式（1）由三部分組成，其中G（Qnext）代表SL自身的對頻譜需求量Qnext的反應價格，不同的SL反應價格不同，c′為SL基于時間序列推測算法得出的推測價格，α和β為調節參數，利用其權重值對反應價格和預測價格進行調和，且α＋β＝1。ε為自定義常數，其取值由SL參考Srpre，ACpre，Srnow，ACnow和自身頻譜質量進行頻譜價格的上調或下降，其取值范圍不超過前兩項之和的百分之十

f（Srpre，ACpre，Srnow，ACnow，θ）（θ為信道質量標值）函數為ε的增函數，其參數值越大，ε的可選范圍越大，代表頻譜市場行情越好，SL可制定高質量的頻譜價格。同時，令w代表SL對出租頻譜的成本衡量，故而，必須保證cnext＞w條件成立，以保證SL頻譜出租的可行性和積極性。

2.3 SA價格調整

頻譜價格對SL收益計算起關鍵作用，定價c越高，則SL收益越大，從博弈論的角度出發，每個活動參與者都是理性的，即以最大化自身收益為目標，如此則會出現SL壟斷市場并肆意制定過高價格的危險，為保證SR的利益和交易公平，SL基于自身判斷制定頻譜價格c，上報到SA中廣播招租，在該信息被廣播前，SA讀取數據庫中該用戶招租信道的評信息進行價格調整。信息評價數據庫設計見表2。

表2 頻譜評價

為方便計算，評價采用百分制，在租用周期結束后，認知用戶對租用信道進行評分并發送給SA，然后，SA更新該信道評價均值及評價次數ni。SA對SL的頻譜出價c的調整策略如下：（ci表示第i條信道的頻譜定價）

由上式可得出，若存在SL為擴大自身利益為故意提高價格或價格與信道質量不相符的情況，SR使用后給予信道真實評價，評價越低，則評價均值越低，SA根據數據進行調整后的價格越低，如此的評價機制和調整機制能更好的保證SR利益和SL的頻譜價格真實合理，維持良好的交易秩序。

值得指出的是，c＊i為下一周期的頻譜i的價格，下一周期開始后，下一周期頻譜招租表自動轉換為當前周期頻譜招租表，若表內仍含有未出租的頻譜，則SA自動將此些頻譜價格提高，由于此時進行招租的頻譜量定會小于等于其作為下一周期進行招租的頻譜量，SR出于自身需求，選擇在本周期內租用頻譜，遵循價值規律，SA將頻譜價格提高3%，并收取2%作為自身收益，如此也保證了SL的收益。

2.4 SR 博弈選擇

PS－DSM方案實現的關鍵環節是SR頻譜選擇，即詳細頻譜分配問題，目前，常見的頻譜分配模型有圖論著色模型、競價拍賣模型和博弈論模型，與其他模型相比，博弈論模型更加適合研究復雜度高，動態變化的分布式認知無線網絡頻譜分配策略選擇問題，其應用嚴格的數學模型來研究參與者之間利益相互制約下的互動決策。國內外的眾多學者也采用多種博弈方法對頻譜分配問題做了大量的研究，如Neel等人首先提出使用博弈理論來研究認知無線電相關問題的基本模型和方法，并使用這些模型分析了頻譜分配、功率控制、呼叫準入控制和干擾避免［8］。其他學者又提出了基于伯川德模型［9］、古諾模型、部分可觀察馬氏鏈決策博弈［10］的頻譜分配模型等。本文首先運用分治思想，讓SR根據自身需求與能力，選擇對口頻譜等級，將整體博弈轉換為4個子博弈，結合公平性，求解子博弈納什均衡。分而治之，加快收斂速度，得出最優選擇。（考慮基礎市場）針對子博弈，設計了基于超模博弈的頻譜分配算法，該算法以最大化系統吞吐量為目標，設計效用函數。詳細內容參加下文 “4基于超模博弈的頻譜分配算法”。

2.5 SR與SL溝通

SR結合自身業務需求及支付能力，從A1、A2、B1、B2這4種頻譜等級的隊列中選擇相符度最高的一列進行排隊，同時收聽廣播，若自己的最優選擇已被他人租用，則立即改變策略，選擇下一最優策略，若在自身得到溝通機會前，可選隊列已空，則退出，重新計算并構建可選隊列后，再次排隊。

在排隊過程中，設優先級，為當前周期排隊的SR屬于Level 1，為租用下一周期頻譜排隊的SR屬于Level 2，Level 1高于Level 2，SR針對自身需求在各自的隊列基于優先級排隊，后到來的高優先級者自動插入到低優先級者前面，同級SR則按照時間順序進行排隊，整個隊列按照優先級由高到低有序排好，保證算法正常進行。

2.6 SR 評價反饋

在交易結束后，由SR對所租用的頻譜進行評價打分，并反饋至SA，SA計算后更新數據庫記錄和ni。

2.7 PS－DSM 方案執行步驟

本文提出的基于預售機制的動態頻譜分配算法具體執行步驟如下：

步驟1 SA確定交易周期τ并廣播，當SL與SR（如無線認知設備）開啟時，接收SA廣播信息，調節自身交易時鐘并確定當前所處的周期，確保與SA時鐘同步。這是進行頻譜交易的第一前提。

步驟2 在于SA時鐘同步的前提下，SL自己對當前及下一周期內的空閑頻譜進行定價，并將該頻譜的相關信息上報至SA進行掛牌招租。

步驟3 SA讀取數據庫中評價信息，對新上報的頻譜價格進行價格調整，然后將該條招租記錄添加至 “招租信息表”并廣播。 “招租信息表”包括 “當前周期招租信息表”和 “下一周期招租信息表”，其設計結構相同，具體如表3所示。

步驟4 SR接收SA廣播信息，根據 “招租信息表”中的數據計算得最優選擇，并選出3個可選SL按最優性由高到低組建自身候選隊列。

步驟5 SR根據頻譜等級排隊競爭公共控制信道，與SL進行溝通。在排隊的同時監聽 “招租信息表”中自身最優選擇的狀態，若該條記錄被其他用戶租用，則立即改變溝通策略，從自身候選隊列中選擇次優策略進行溝通，若在自己得到溝通機會前，自身候選隊列已空，則退出隊列，重新計算并組建新候選隊列后繼續排隊。

步驟6 針對預售機制，提出了雙方安全租借和誠信租借的要求，于是，設計使用交易密鑰。SR與SL進行溝通，商定交易密鑰。然后SL向SA發送該信道已經出租的消息，SA更改該信道狀態為 “已租”，同時接收SR付款。若SR與SL溝通失敗，則跳轉至步驟4繼續執行算法。

步驟7 租用周期開始，SR拿著商定的交易密鑰進行“敲門”，SL核定本周期內的交易密鑰，然后允許SR使用頻譜，保證通信和頻譜交易的安全可行。

步驟8 租用周期結束，SR對使用的信道進行評分，反饋至SA，SA更新該信道評價記錄并將此次交易款額劃撥給SL。

值得指出的是，在步驟6中，同時進行選擇的多個SR均與SL成功溝通后，一次博弈結束。后重復過程，直至系統達到納什均衡。在步驟7中，SR使用頻譜進行通信的同時，繼續收聽廣播信息，為自己下個周期的所需頻譜資源進行租用計算和溝通。將計算能力充分調用，減少時延，提高頻譜利用效率。

表3 招租信息

3 基于超模博弈的頻譜分配算法

SR頻譜選擇是PS－DSM方案實現的關鍵環節，多個SR以自私地競爭的方式來搶占SL出租的頻譜資源，以期最大化自身收益，且其決策時完全獨立，因此，可以將多個SR的頻譜選擇行為描述為的一個結合公平性不完全信息下的博弈模型，博弈的參與者為SR，博弈參與者的策略空間為SR的可選頻譜集，尋找博弈納什均衡解，找出相應分布式的最優解決方案。

3.1 系統模型

僅考慮基礎市場的單認知網絡，設SL和SR個數分別為M個和N個，且隨機分布在D×D的方形區域中。可用信道數為K個，SRi和j在信道K上的發射功率分別為pik和pjk，當k選擇信道時，hiik為SRi的發射機到接收機的鏈路增益，hjik為SRj發射機到SRi的發射機的鏈路增益，Gimk表示SRi到SLm的鏈路增益，A（i，k）為信道分配矩陣元素，其個數為N×K個，若信道k被SRi租用，則A（i，k）＝1，否則A（i，k）＝0。n0為背景噪聲功率。則第i個SR在信道k上接收機處的信噪比定義為

由香農公式可得，第i個SR在信道k上的吞吐量為

SLm受到信道k上的SR干擾Imk為

3.2 頻譜分配博弈模型

頻譜分配問題的博弈數學描述一般形式如下

式中：N——博弈參與者的有限集（在本博弈中為N個SR）；Si——博弈者i的可選策略集合，定義S＝×Si，i∈N為策略空間，則Ui：S→R為效用函數集。在博弈Γ中，每個博弈者i的效用函數Ui為Si及其對手S－i的函數。

由于博弈者獨立進行決策，并受到其他博弈者決策的影響，則博弈結果分析的一個關鍵問題即判斷該信道選擇算法是否存在收斂點，且該收斂點對于任何一個博弈者而言都不會產生偏移，若存在一組策略，S＝｛s1，s2，…sN｝，當且僅 當Ui（si，s－i）≥Ui（si′，s－i），i∈ N，si′∈Si時，該組行動向量就是納什均衡（NE），一般而言，這個納什均衡點便是策略最優點。

3.3 效用函數設計

選擇一個合適的效用函數將對SR的博弈行為產生本質的影響。在本非合作博弈中，每個SR都是理性參與人，選擇對自己收益最大的信道進行選擇后租借，其效用與所選擇的信道質量相關，以系統總吞吐量作為信道效用值，則效用函數描述如下

由于博弈中的每個用戶都是自私的，只關心自身利益的最大化，而不考慮其它用戶的需求，這會使獲得的納什均衡可能不是系統的最優點，于是添加代價函數，既真實的反映出SR租借頻譜獲得收益的同時所付出的代價，也保證了SL的利益，快速找到最優均衡點。SRi在時間段t內的租借信道k的代價函數為

式中：Itotal——SL受到SR的干擾和，α——常量比例系數。——信道k的廣播招租價格，為非負常數。定義效用函數時將代價函數考慮在內，對SR進行懲罰，可以防止其一味增大發射功率，減少對其他用戶造成干擾，引導其合理利用網絡資源。

因此，可得最終效用函數為

3.4 穩態判斷

文獻［11］提到，對于認知無線網絡，設計合適的博弈算法首先要保證網絡存在穩態，而且這種穩態應具有好的性能；其次博弈算法能夠快速地收斂到性能最優的穩態。對于具有有限行為空間的標準形式博弈，可以通過有限改進路徑（FIP）特性及弱有限改進路徑（弱FIP）特性來確定其收斂性。穩態即納什均衡點（NE），在實際中，確認一般標準形式博弈或重復博弈的穩態比較困難，可以使用更高級的博弈模型，如位勢博弈和超模博弈，這兩種博弈模型可以有效地簡化NE確認過程。

所謂超模博弈，是指行為空間組成格子且效用函數具有超模性的博弈模型。通過分析可得，本文所設計的博弈算法屬于超模博弈，以下將分兩步證明：

（1）行為空間組成格子：設集合X，如果其滿足：①X是部分有序集，② min｛x，y｝∈X；max｛x，y｝∈X，x，y∈X；則稱X為格子。本文中，SR根據廣播的頻譜信息進行頻譜選擇，顯然其行為空間可組成格子。

（2）效用函數具有超模性：設函數f：X→，其中X是格子的。如果滿足式（14），則稱f在X上是超模的

本文所設計的效用函數具有超模性，證明如下：

（1）ui（si）＋ui（si′）＝

（2）ui（si∨si′）＋ui（si∧si′）＝

由上可得：（1）＝（2）即：ui（si）＋ui（si′）＝ui（si∨si′）＋ui（si∧si′）滿足超模函數的定義。

證明結束，本博弈為超模博弈。依據超模博弈的性質，任何一個超模博弈必然存在一個純策略納什均衡。

3.5 最優發射功率求解

效用函數受到發射功率影響，當發射功率越大對SR本身的效用越大，同時帶來的干擾越大，如此無法保證整個網絡性能的最優性，因此，需求解一個合適的發射功率，保證SR本身及整個網絡性能的最優化，最佳發射功率求解如下：

對效用函數U2一階求導

SR時時收聽廣播信息，求解發射功率過程隨信道分配矩陣動態變化。

4 仿真實驗與性能分析

應用本文基于預測機制的動態頻譜分配算法，使用matlab 7.0進行算法仿真。仿真的基礎市場認知無線網絡場景為：在300m×300m的范圍內。周期內隨機固定分布50個SR和4個SL。每個SR和SL可看作一個發射—接收點對，不同SR發射機和接收機之間的距離在［50，300］m內隨機取值，同SR的發射機和接收機距離在［1，50］m內隨機取值，下一周期內招租信道有10個，信道1－信道10。SR所選擇信道未被其它用戶占用時其初始發射功率為p0＝80mW。不同通信等級的SR競爭使用4個公共控制信道與SL溝通，控制信道不受主用戶影響。背景噪聲功率n0＝－100dB，鏈路增益為h＝ω／d4，且ω＝0.097，比例系數α＝200。為方便計算，信道頻譜等級初始設定見表4，各SR頻譜等級需求初始設定見表5。

表4 信道頻譜等級初始設定

表5 SR頻譜需求等級初始設定

4.1 算法收斂情況

圖2展現出基于超模博弈的頻譜分配算法作用下，各SR策略收斂情況。橫坐標表示博弈次數，縱坐標表示SR可選擇的策略，信道k＝｛k＝1－10｝。可以看出，在算法執行了約45個算法周期后，各SR選擇選擇信道的策略穩定。系統達到納什均衡狀態，與博弈論的推導結果一致。

4.2 SL所受干擾情況

圖3給出了采用效用函數U1和效用函數U2對SL的干擾曲線圖，結果表明采用U2作為效用函數時，引入抑制SR自私行為的代價函數，SL所受干擾明顯低于采用U1作為效用函數時所受的干擾。

4.3 系統吞吐量比較

在算法仿真過程中，分別對以U1和以U2為效用函數時算法的吞吐量進行測量，驗證了本文提出的算法有助于提高系統性能。如圖4所示。采用效用函數U2，劃分子博弈與沒有劃分子博弈的吞吐量比較如圖5所示，可得，通過子博弈劃分，可加快達到均衡速度，且吞吐量略有提高。

5 結束語

本文基于認知無線網絡環境，提出并詳細闡述了基于預售機制的動態頻譜管理（PS－DSM）方案。在本方案中，頻譜市場被劃分為三級，針對基礎市場的頻譜分配博弈方法和仿真進行了細節描述。結果表明，本方案雖然增加了算法的復雜度，但是有效的提高了頻譜分配效率，減少時延。但是，在分配算法上的細節考慮仍需要進一步的完善，以及高級市場的分配算法成為亦下一步的研究重點。

圖5 系統吞吐量（2）

［1］LI Wenbian，LIN Yuewei，WANG Xiaomeng，et al.A microeconomics based dynamic spectrum management algorithm for cognitive wireless networks［J］.Journal of Electronics ＆ Information Technology，2009，31（4）：897－902（in Chinese）.［黎文邊，林粵偉，王小猛，等.認知無線網絡中基于微觀經濟學的動態頻譜管理算法［J］.電子與信息學報，2009，31（4）：897－902.］

［2］FENG Zhiyong，ZHANG Ping，LANG Baozhen，et al.Cognitive wireless network theory and key technology［M］.Beijing：Posts ＆ Telecom Press，2011（in Chinese）.［馮志勇，張平，郎保真，等.認知無線網絡理論與關鍵技術［M］.北京：人民郵電出版社，2011.］

［3］Cao L.Distributed spectrum allocation via local bargaining［C］／／IEEE Sensor and Ad Hoc Communications and Networks.Santa Clara，USA：IEEE Press，2005：475－486.

［4］Peng Chunyi，Zheng Haitao，Ben Y Zhao.Utilization and fairness in spectrum assignment for opportunistic spectrum access［J］.Mobile Networks and Applications，2006，11（4）：555－576.

［5］CHEN Jie，ZHANG Ping.A game－based dynamic spectrum management for heterogeneous wireless system［J］.Radio Engineering，2008，38（3）：9－12（in Chinese）.［陳杰，張平.異構無線系統中基于博弈的動態頻譜管理［J］.無線電工程，2008，38（3）：9－12.］

［6］JIANG Lie，GAO Yuehong，ZHANG Xin，et al.Spectrum pooling in the cognitive radio［J］.Modern Science ＆ Technology of Telecommunications，2011，4（4）：42－45.（in Chinese）.［江磊，高月紅，張欣，等.頻譜池在認知無線電中的應用［J］.現代電信科技，2011，4（4）：42－45.］

［7］CORDIER.P.E2Rcognitive pilot channel concept［C］／／IST Summit.Mykonos，2006：22－26.

［8］Nie N，Comaniciu C.Adaptive channel allocation spectrum etiquette for cognitive radio networks［C］／／Proceedings of the 1st IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks.Baltimore，MD，USA.Piscataway，NJ，USA：IEEE，2005：269－278.

［9］ZHAO Q，TONG L.Decentralized cognitive MAC for opportunistic spectrum access in ad－hoc networks：a POM DP framework［J］.IEEE Journal on Selected Areas in Communications.2007.25（3）：589－600.

［10］Huang J，Beery R，Hong M，Auction－based sharing［J］.Mobile Networks and Applications，2006，11（3）：405－408.

［11］WANG Jinlong，WU Qihui，GONG Yuping，et al.Cognitive wireless networks［M］.Beijing：China Machine Press，2010（in Chinese）.［王金龍，吳啟輝，龔玉萍，等.認知無線網絡［M］.北京：機械工業出版社，2010.］