基于沖突分解的短波頻點真實在線雙拍賣算法

楊 博, 王葉群, 黃國策, 孫啟祿, 王桂勝

(空軍工程大學信息與導航學院, 陜西 西安 710077)

0 引 言

隨著認知無線電(cognitive radio, CR)技術的發展,短波寬帶頻譜感知(spectrum sensing, SS)能力顯著提升,在第四代自動鏈路建立(automatic link establishment, ALE)模式下建鏈速度提升明顯,構建以短波認知電臺為基礎的短波認知通信網(high frequency cognitive communication networks, HFCCN)成為可能。短波頻譜管理(high frequency spectrum management, HFSM)是指根據用戶需求提供最佳可用頻率,滿足用戶服務質量要求。短波信道具有時變特性,小區域、窄頻段內大量用戶同時在線會導致嚴重的頻點干擾,如何有效提高頻譜資源分配效率、提高數據鏈路可靠性成為亟需解決的問題。動態頻譜接入(dynamic spectrum access, DSA)能夠有效利用頻譜空穴,設計良好的頻譜接入策略,不僅能夠有效降低電臺間的干擾,提高頻譜利用率,還可以通過頻譜探測發現新的可用頻點,滿足實時通信需求。

當前短波頻譜指配主要以靜態分配為主,依據各地垂測站數據,構建電波傳播模型,以降低頻間干擾為優化約束條件,研究了不同算法對于系統頻率指配性能的影響,該類算法對固定鏈路性能良好,然而在動態變化的環境中實時性差、可靠性低。HFCCN實時動態頻率指配受到頻點可用性影響,網絡高負載情況下存在部分鏈路可用頻點少、鏈路間同頻干擾強等問題,需要運用DSA進行網絡內不同鏈路的通信頻點切換調整,進而提升系統通信性能。

國內外針對CR網絡進行了大量研究,文獻[18]對CR網絡進行了概述,其中集中式網絡采用在線拍賣能夠實現DSA,有效提高頻譜利用效率。針對頻譜的在線拍賣,文獻[19]提出了真實在線雙拍賣(trueful online double auction, TODA)算法,在不允許搶占已分配的頻譜的情況下,分析了次級用戶(second-user, SU)沖突圖完整時的拍賣過程。由于頻點價值對各個用戶存在差異,文獻[20]采用了可搶占在線拍賣算法。相對于TODA算法,通過頻譜可搶占策略,采用平滑臨界值的定價方式,能夠更加有效地分配頻譜。文獻[21]研究了動態頻譜拍賣系統中的召回機制問題,提出了一種基于局部召回的動態雙頻譜拍賣機制。短波認知電臺隨機接入,難以確定買家、賣家數量,文獻[22]設計了一個頻譜雙重拍賣框架,適用多個賣家和買家同時出價的情況,綜合考慮了頻譜的可重用性、真實性和利潤最大化。短波信道受到時間、空間因素影響,同頻干擾也相應發生變化,文獻[23]考慮了頻率分集可能導致頻譜購買者之間的沖突關系不相同,并解決了干涉圖變化的問題。

短波頻點拍賣相較于傳統頻點拍賣,存在可用拍賣頻點個數不確定和用戶數不確定的雙重不確定情形,因此既要考慮用戶業務需求,又要兼顧探測時間資源分配,TODA模型能夠平衡兩方面收益,適用于短波頻點DSA。同時,在網絡高負載情況下,頻點沖突嚴重,為減少搶占過程中網絡內頻點切換次數,需要分析沖突關系,構建新的頻率指配模型。

本文提出一種基于沖突分解的TODA(TODA based on conflict decomposition, TODA-CD)短波頻率指配方法,通過設計賣方策略和買方策略,最大化買家收益,提高頻譜使用效率,同時確保算法的真實性、公平性和預算均衡。TODA-CD算法重點分析了頻譜搶占對于現有網絡內頻譜切換次數的影響,通過對沖突頻點生成頻譜沖突圖,分析了頻點沖突狀況,設置懲罰函數,完成對買家收益的建模。通過仿真發現,TODA-CD算法相比傳統拍賣算法,能夠提高交易成功率,有效減少切換頻次,提高買家收益。

1 系統模型

1.1 HFCCN

在HFCCN中,當前獲得頻譜授權的用戶被稱為主用戶(primary user, PU),也就是網絡內靜態分配的用戶,未獲得頻譜授權的用戶被稱為SU,SU通過SS,動態接入網絡。其中,SU所構成的CR網絡能夠利用寬帶接收機實現全頻段接收,使得發射端頻點探測范圍跳出預置頻點集,實現DSA。

在SU構成的認知網絡中,SU主動探測頻點質量,其中為避免不同網絡探測間的干擾,采用碼分多址的信道接入策略,采用64階的Wlash碼進行不同網絡間探測信號的區分識別。

在一個區域內,多個動態移動的短波認知電臺和中心節點進行通信,完成數據的上傳下達,其網絡拓撲為集中式網絡,如圖1所示。即一個中心控制節點和多個節點相連接。在拍賣過程中,當業務請求到達時,各個節點發起鏈路建立請求,中心節點進行全頻段掃描檢測探測信號,在發現探測信號后開始建鏈過程,形成買方報價,提交給中心節點,中心節點根據拍賣策略,分配合適的頻點給該條鏈路,建立鏈接,傳輸業務。業務傳輸結束后,拆除鏈接,釋放頻點,網絡內空閑頻點集增加。

圖1 集中式HFCCNFig.1 Centralized HFCCN

1.2 在線雙拍賣模型

文中假設集中式HFCCN存在個CR用戶{SU1,SU2,…,SU}和1個中心節點SU0。SU0與其他認知用戶通過頻譜探測個可用頻率,構成頻譜賣方=[,,…,]。在1個拍賣周期內,個用戶請求建鏈,提出頻譜申請,構成頻譜買方=[,,…,]。在拍賣過程中,存在中間拍賣商,決定中標人和支付價格。拍賣采用密封第二價格拍賣,所有投標人提交密封價格,以未中標最高價格作為支付價格。假設頻譜賣家提供1個空閑可用信道,頻譜買方購買1個可用信道。用戶到達符合參數為的泊松分布。

因此,單條鏈路單個周期內買方收益為

(1)

單條鏈路單個周期內賣方收益為

(2)

網絡中個周期內買家總收益為

(3)

網絡中個周期內賣方總收益為

(4)

2 TODA-CD

由于短波鏈路質量受時間、地點等因素影響明顯,不同時刻變化較大,即不同站點的不同。其中,賣家收益表征了中心節點資源的利用效率,買家收益表征各條鏈路收益之和,即網絡內頻點指配效率。因此,通過設計定價策略,兼顧賣家收益,同時,確保買家收益最大化,算法優化目標為max。

2.1 基于鏈路差異性的賣方模型

由于認知電臺所處地理位置的不同,各條鏈路間差異巨大,為保證鏈路可靠性,需要突出關鍵鏈路的頻點價值,由此構建了以鏈路差異化定價的賣家模型。

定義每條鏈路當前時刻的可用空白頻點數量()=[MUF()-MLF()],其中MUF()為某時刻最高可用頻率,MLF()為某時刻最低可用頻率,為信道帶寬。

去除干擾頻點(),得到當前空白可用頻點:

′()=()-()

(5)

式中:中心節點在′()進行頻點質量探測。

(6)

(7)

2.2 基于沖突分解的買方模型

假設業務真實估值符合參數為的均勻分布,持續時間=-,符合參數為的均勻分布。

(8)

傳統在線雙拍賣過程中,交易商通過Mcafee算法撮合買家與賣家,采用Kuhn-Munkres二部圖最優匹配算法進行頻率指配,完成交易,達到當前時刻預期收益最大值。但是,短波頻點可用頻點數目少,頻譜擁擠程度高,在網絡負載較高的情況下,使得網絡內成功交易的概率急劇下降,網絡頻譜利用率降低。

由于買家對應的多個賣家的頻點占用情況不同,最優SINR可能存在頻點占用情況,在頻點缺乏的情況下存在所有可用頻點均被占用的情況。在鏈路申請頻繁、占用時間較長的高負載情況下,可用頻點減少,網絡內擁堵,導致部分鏈路可用頻點已被完全分配,造成通信中斷。允許頻點搶占能夠適應高負載網絡條件下的頻點指配,即通過調整過往分配結果來滿足新鏈路建鏈需求。在此過程中,需要平衡頻點指配收益與切換次數的關系,達到相對最優,即在一定限制下通過反向切換網絡內頻點獲得最大收益,提高頻點使用率,提升系統整體收益。

(9)

搶占的切換過程通過買家報價實現。針對頻點指配結果進行廣度優先搜索,進而生成頻點沖突樹,通過最大化頻點切換帶來的預期收益,改變買方的拍賣價格。切換過程為雙方確認過程,額外的網絡開銷小。

根據買家期望收益計算,定義最優切換賣家,形成買方報價:

(10)

當頻點調整時,系統通過競價來進行補償,進而完成頻點的搶占最優切換:

(11)

競價過程采用第二密封價格進行競價,即采用競價失敗的最高收益價格。同時,為保證最優匹配,提高值為的報價,形成新的價格。針對新的競價價格的期望收益為

(12)

由于切換頻次對系統整體性能存在一定影響,會引起系統傳輸的延時增大,因此對收益進行一定的罰函數處理,懲罰度為,懲罰收益為

(13)

預期收益的計算采用逐步計算法,通過廣度優先算法進行預期收益的逐步遞歸求解。

(14)

由于切換帶來的每次收益的值降低,為遞減函數,當搜索到空閑頻點時,即取得當前切換收益的最大值,停止搜索。

由于每次切換過程帶來的收益遞減,搜索過程采用廣度優先算法進行,通過生成當前頻點切換生成樹,計算最優切換方案,樹的深度受空閑頻點數量影響,即空閑頻點越多,樹的深度越小,切換次數越少,總體收益越高。

當空閑頻點極少時,切換成本急劇增大,新鏈建鏈成功對總體收益影響減小,可以隨機延遲一段時間重新進行鏈路申請,保證網絡內整體收益最高。

3 算法性能分析

3.1 真實性分析

首先證明基于搶占的在線雙拍賣算法是真實的,即投標人不能通過操縱其報價來提高其效用。

切換過程中,系統的競爭價格由過往系統的頻點分配狀況決定,由系統主導,不存在欺詐。賣方報價由系統探測時間生成,不存在欺詐性。因此,該算法是真實的。

3.2 公平性分析

從買家和賣家兩個方面討論公平性。由于頻譜具有可搶占性,申請時間先后順序對于頻點的選擇影響降低,保證了后接入節點的公平性。同時,通過競爭方式接入,保證了各個站點之間的公平性,可平衡各個節點業務量和頻譜使用的關系。

賣方策略通過對每個頻點分配相同的時間進行頻點探測,保證各個站點對整個系統探測資源的公平使用,通過差異化定價,體現不同頻點的探測成本。

3.3 預算平衡分析

由于系統內買方的收益始終高于賣方的成本,預算初始會保持平衡。拍賣過程中,由于買方和賣方通過競價完成交易,使得報價趨于真實,不會出現買方整體壓低報價或者賣方整體抬高報價而導致的預算失衡。

3.4 頻譜利用率

通過采用可搶占的頻點選擇策略,提高了交易的成功率,進而提高了空閑頻點的利用效率。空閑頻點狀態的獲取取決于賣家探測時間資源的分配,通過設置不同的探測時間,可以達到不同的頻譜利用率極限,進而容納更多的用戶。

4 仿真實驗與結果分析

4.1 實驗配置環境

實驗使用隨機函數生成買家的業務需求,買家的通信請求時間符合泊松分布,申請的業務時間符合均勻分布,買家通過新接入不同負載條件下的HFCCN,分析TODA-CD 算法性能,買方的信道質量模型和賣方的探測可用頻點個數模型遵循隨機分布模型。根據武漢垂測站2020年11月7日電離層垂測公開數據,每隔15 min采集一次數據,一天(24 h)的短波可用頻段分布如圖2所示。由圖2可以看出,任意兩點可通過武漢地區電離層作為反射點的通信鏈路,在通信距離不同時可用頻段分布不同,在頻點擁擠的時段,以3 kHz劃分頻點,頻點個數約為500。

圖2 短波可用頻段范圍隨時間變化圖(24 h)Fig.2 Variation of available high frequency frequency range over time (24 h)

本實驗在頻點擁擠情況下進行算法性能分析,在線拍賣過程持續45個周期,每1個周期進行1次網絡內頻點拍賣,時間長度為15 min。實驗參數如表1所示。由于各個屬性的隨機性較強,運行結果較為曲折,但是并不影響拍賣機制性能分析。

表1 仿真實驗參數Table 1 Simulation experiment parameters

在拍賣過程中主要分析了頻譜效率(spectrum effectiveness, SE)、切換頻次、買家收益3個指標。

4.2 SE

SE是頻點使用個數占總頻點的比值。當網絡負載過重時,沖突增大,傳統TODA算法由于不可搶占、不可切換,頻譜利用率較低。文獻[20]中的Topaz算法和本文提出的TODA-CD算法屬于可搶占拍賣算法,能夠實現頻譜搶占切換,極大地提升了交易成功率。在TODA-CD模型中,由于買家可通過切換、搶占選擇空閑頻點,理論上而言,只要存在可用空閑頻點,必定能夠找到空閑頻點并進行切換。因此,阻礙頻率利用率提高的因素轉變為賣家的頻譜狀態探測能力。由于賣家探測時間資源有限,通過調整賣家模型,分配不同的探測時間,即探測可用頻點的數目不同,能夠改變網絡內頻譜利用的上限。仿真分析如圖3～圖6所示,在不同網絡負載條件下,探測最大可用頻點個數為2～5時,每條新加入鏈路拍賣交易的失敗率各不相同。可以看出,由于傳統TODA不可搶占,在鏈路隨機加入的情況下,每次拍賣中各鏈路建鏈成功率不穩定且成功率較低,而TODA-CD算法隨著單鏈路探測時間分配增加,鏈路最大可用頻點數增多,HFCCN的交易成功率上限不斷提高且成功率較穩定:當=2時,即每條鏈路探測感知到2個可用頻點,頻譜利用率可達到80%;當單鏈路探測感知可用頻點達到5,即=5時,頻譜利用率可達到98%以上。賣家中心節點可根據網絡系統性能,選擇合適的賣家探測資源分配方式,提高系統頻譜利用率。

圖3 不同頻譜利用率下的交易失敗率(mf=2)Fig.3 Transaction failure rate at different spectrum utilization rates (mf=2)

圖4 不同頻譜利用率下的交易失敗率(mf=3)Fig.4 Transaction failure rate at different spectrum utilization rates (mf=3)

圖5 不同頻譜利用率下的交易失敗率(mf=4)Fig.5 Transaction failure rate at different spectrum utilization rates (mf=4)

圖6 不同頻譜利用率下的交易失敗率(mf=5)Fig.6 Transaction failure rate at different spectrum utilization rates (mf=5)

4.3 頻譜切換

切換頻次表明了整個系統的搶占程度以及個體買家對整體系統的影響程度。在保證拍賣成功率的前提下,買家模型通過廣度優先搜索生成當前頻點與過往頻點的同頻沖突生成樹,對過往沖突進行分析。TODA-CD算法構建了交易頻點的沖突拓撲圖,如圖7所示。其中,每個紅點代表一條通信鏈路,每條連線表示鏈路頻點存在可能沖突,用不同顏色區分沖突樹的層數。圖7中沖突樹共分為4層,涉及30條相關鏈路,最少切換次數為1,最多切換次數為4,通過計算不同切換方案所產生的買家收益,決定最終的切換方式。

圖7 頻譜沖突拓撲圖Fig.7 Spectrum conflicting topology

在不同的頻譜利用率下,隨著頻譜利用率的提升,傳統的Topaz算法的頻譜切換次數顯著增加。通過模擬10個拍賣周期,得到Topaz和TODA-CD兩種算法的平均切換次數,如圖8所示。可以看出,在頻譜利用率較高的情況下,TODA-CD算法相比Topaz算法能夠有效降低網絡內切換次數,且分布較為均衡。由于拍賣周期內用戶到達和可用頻點的隨機性,曲線出現部分曲折,可以看出,隨著頻譜利用率提高,Topaz算法導致切換次數急劇上升,TODA-CD算法能夠保持較低的切換次數。

圖8 不同頻譜利用率下網絡內切換次數Fig.8 Intra-network handoff times under different spectrum utilization

在整個在線動態拍賣過程中,通過模擬仿真45個拍賣周期,分析了用戶隨機到達情況下, 不同網絡負載時的網絡內頻譜切換次數,動態過程如圖9～圖11所示。可以看出,在SE=0.75,SE=0.85,SE=0.95的狀況下,整個動態過程中,TODA-CD算法的切換次數低于Topaz算法,并且保持在一定的范圍內波動。部分頻點切換次數略高于Topaz算法,是由動態隨機接入沖突關系的不同累積導致的。由于采用頻分多址的方式進行網絡構建,可用頻點個數決定了網絡的用戶承載數量,頻譜利用率反映了網絡負載情況,圖12分析了不同頻譜占用率下網絡內鏈路切換次數分布情況,其中“td-0.75”表示在頻譜占用率為75%的情況下TODA-CD算法的切換次數。“tz-0.75”表示頻譜占用率為75%的情況下Topaz算法的切換次數。可以明顯看出,在頻譜占用率為75%、85%、95%時,TODA-CD算法切換次數最高為10、10、9,中位數為4、4、5;Topaz算法最高切換次數為27、40、75,中位數為10、18、28,TODA-CD算法切換次數明顯低于Topaz算法,同時在頻譜利用率發生變化時,切換次數波動維持在一定范圍內且明顯較少。

圖9 動態頻譜切換次數(SE=0.75)Fig.9 Dynamic frequency spectrum switching times (SE=0.75)

圖10 動態頻譜切換次數(SE=0.85)Fig.10 Dynamic frequency spectrum switching times (SE=0.85)

圖11 動態頻譜切換次數(SE=0.95)Fig.11 Dynamic frequency spectrum switching times (SE=0.95)

圖12 不同網絡負載情況切換次數分布圖Fig.12 Distribution diagram of switching times under different network loads

4.4 賣家收益

在保證拍賣的真實性和公平性的基礎上考慮賣家收益最大化。買家收益表明了頻點信噪比與用戶需求的最優匹配,收益越高,表明整個網絡的匹配程度越高。收益對比差異主要取決于懲罰度的不同,即網絡系統對于鏈路頻點切換的敏感程度不同。買家收益趨勢變化反應了當前動態頻譜接入鏈路的增長或降低的趨勢。Limitation門限是網絡內單條鏈路的最優選擇組合構成的網絡最優選擇,是1個理想值。在1%、5%、10%不同懲罰度下,算法收益如圖13～圖15所示,可以看出,在HFCCN動態接入的過程中,用戶收益在不斷波動,在運行42個周期后,為0.01、0.05、0.10時,TODA-CD買家收益相比于買家收益極限分別降低了1.29%、2.67%、5.53%。Topaz算法買家收益相比于買家收益極限分別降低了1.89%、4.82、15.32%,在對網絡切換敏感的網絡中,TODA-CD算法相比Topaz算法優勢明顯,隨著動態過程的持續進行,收益差距進一步拉大,在對網絡切換相對不敏感的網絡中,TODA-CD算法略優于Topaz算法,買家收益增益相對較少。

圖13 動態頻譜拍賣買家收益(ζ=0.01)Fig.13 Dynamic spectrum auction buyer revenue (ζ=0.01)

圖14 動態頻譜拍賣買家收益(ζ=0.05)Fig.14 Dynamic spectrum auction buyer revenue (ζ=0.05)

圖15 動態頻譜拍賣買家收益(ζ=0.1)Fig.15 Dynamic spectrum auction buyer revenue (ζ=0.1)

5 結 論

本文對短波認知電臺動態頻點接入特性進行了分析,在拍賣過程中,針對高網絡負載條件下頻點沖突嚴重的問題,提出了TODA-CD模型。TODA-CD通過構建頻點沖突圖,構建合適的懲罰函數,完成頻點路徑切換的最優選擇,從而有效降低網絡切換次數,提高系統收益。仿真實驗表明,本文所構建的在線雙拍賣模型相對TODA算法,提高了頻譜利用率上限,通過利用沖突圖分解算法,在網絡高負載情況下切換次數相對Topaz算法明顯減少,有效提高了系統收益,具有一定的應用價值。