劉覺夫，王華鋒，楊 麗

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

0 引 言

在無(wú)線網(wǎng)絡(luò)中，由于頻譜和帶寬等無(wú)線網(wǎng)絡(luò)資源極其有限，根據(jù)FCC的頻譜策略任務(wù)工作報(bào)告顯示，已經(jīng)分配頻譜的利用率在15%到85%之間波動(dòng)，存在開放頻譜資源匱乏和專用授權(quán)頻譜利用率低下的矛盾，因此對(duì)頻譜等網(wǎng)絡(luò)資源進(jìn)行高效地分配及管理是解決頻譜匱乏問題的重要手段。根據(jù)頻譜分配的現(xiàn)狀，不同區(qū)域的部分機(jī)構(gòu)擁有不同帶寬的頻譜并且為認(rèn)知用戶提供通信服務(wù)，因此，對(duì)多個(gè)頻譜服務(wù)提供者和多認(rèn)知用戶共存環(huán)境下的頻譜資源進(jìn)行簡(jiǎn)單、高效地分配與管理和提高動(dòng)態(tài)頻譜訪問的可靠性就成為了一個(gè)關(guān)鍵問題。市場(chǎng)機(jī)制是解決資源競(jìng)爭(zhēng)問題的有效方法，多位學(xué)者針對(duì)頻譜分配的市場(chǎng)機(jī)制進(jìn)行了研究，如劉英挺等人應(yīng)用連續(xù)雙向拍賣和模糊推理建立了分配制模型［1］，吳瓊等人對(duì)競(jìng)價(jià)模型的頻譜分配及其應(yīng)用進(jìn)行了深入研究［2］?，F(xiàn)有認(rèn)知無(wú)線網(wǎng)頻譜分配算法中，多個(gè)頻譜服務(wù)提供者和多認(rèn)知用戶環(huán)境下都存在用戶間關(guān)系復(fù)雜，算法時(shí)間復(fù)雜度過高，頻譜分配方式不夠靈活的問題。針對(duì)上述問題利用市場(chǎng)交易機(jī)制設(shè)計(jì)了動(dòng)態(tài)的頻譜分配算法。市場(chǎng)交易機(jī)制簡(jiǎn)化了復(fù)雜的多對(duì)多關(guān)系，可以使頻譜分配算法實(shí)現(xiàn)較低的時(shí)間復(fù)雜度，加快收斂速度。

1 連續(xù)雙向拍賣與價(jià)格行為

現(xiàn)實(shí)世界的各個(gè)領(lǐng)域里都存在各種各樣的多對(duì)多的競(jìng)爭(zhēng)現(xiàn)象，交易市場(chǎng)就是這種現(xiàn)象的直觀例子。連續(xù)雙向拍賣是交易市場(chǎng)中各方實(shí)現(xiàn)其交易行為的一種有效機(jī)制。交易市場(chǎng)將各方的競(jìng)爭(zhēng)行為轉(zhuǎn)化為各自的價(jià)格行為，價(jià)格信息體現(xiàn)了各方?jīng)Q策行為的結(jié)果。根據(jù)經(jīng)濟(jì)學(xué)理論，各方的競(jìng)爭(zhēng)關(guān)系是一種供需關(guān)系，解決供需關(guān)系的最有效途徑就是交易市場(chǎng)。連續(xù)雙向拍賣作為一個(gè)多邊的討價(jià)還價(jià)過程，能夠快速地收斂到競(jìng)爭(zhēng)均衡，從而產(chǎn)生很高的價(jià)格發(fā)現(xiàn)效率。在這系統(tǒng)中，參與者在市場(chǎng)中的行為完全體現(xiàn)為其價(jià)格行為，所有參與者的價(jià)格行為構(gòu)成市場(chǎng)。參與者的價(jià)格行為就是其決策的結(jié)果，參與者的決策只需要關(guān)心市場(chǎng)價(jià)格和自身收益這兩方面的因素。

連續(xù)雙向拍賣的市場(chǎng)交易機(jī)制是基于指令流的撮合成交機(jī)制，其指令分為限價(jià)指令和市價(jià)指令，這樣在交易市場(chǎng)過程當(dāng)指令稀少時(shí)就有可能產(chǎn)生異常的成交價(jià)格。利用連續(xù)雙向拍賣的進(jìn)行建模時(shí)就要對(duì)交易機(jī)制進(jìn)行重新設(shè)計(jì)，避免產(chǎn)生異常的成交價(jià)格，給頻譜交易者造成損失。

本文設(shè)定：

（1）在建模時(shí)頻譜提供者為賣方，其收益函數(shù)為sell－Pay，頻譜使用者為買方，其收益函數(shù)用buyerPay表示，交易雙方的角色固定；

（2）一個(gè)用戶 （買方）一次只能訪問一條信道，頻譜提供者 （賣方）可以同時(shí)提供多條信道；

（3）網(wǎng)絡(luò)中用戶之間是互相干擾的；

（4）用戶專指在無(wú)線網(wǎng)絡(luò)環(huán)境中的一對(duì)發(fā)射機(jī)和接收機(jī)，干擾來自其他用戶的頻譜使用；

（5）信道作為交易的商品被認(rèn)為是同質(zhì)的。

2 系統(tǒng)模型

考慮如圖1所示的情況：無(wú)線網(wǎng)絡(luò)中存在N個(gè)認(rèn)知結(jié)點(diǎn)用戶組和M個(gè)由不同頻譜出售商提供的可用無(wú)線頻譜帶。每個(gè)用戶均可訪問網(wǎng)絡(luò)中任何一個(gè)空閑頻譜段，即頻譜具有可以交易商品的同質(zhì)性。

將每個(gè)組看作一個(gè)整體，在雙方之間設(shè)置STM （spectrum trade management），這個(gè)模型就是簡(jiǎn)易的頻譜交易市場(chǎng)。

可以在多個(gè)頻譜供應(yīng)商和多個(gè)頻譜使用者之間使用的無(wú)線頻譜訪問形式，是一種必然的趨勢(shì)。用頻譜市場(chǎng)的方式來解決這一問題的核心就是交易機(jī)制的設(shè)計(jì)和交易雙方的報(bào)價(jià)策略。

連續(xù)雙向拍賣交易機(jī)制如圖2所示。

圖1 分布式頻譜訪問

圖2 連續(xù)雙向拍賣交易機(jī)制

STM充當(dāng)拍賣人的角色，通過接收并執(zhí)行雙方提供的交易指令，并對(duì)其進(jìn)行撮合成交來完成交易。指令分為4種：限價(jià)賣出指令、市價(jià)賣出指令、現(xiàn)價(jià)買入指令、市價(jià)買入指令。市價(jià)指令的優(yōu)先級(jí)別高于限價(jià)指令，指令薄上的其中一方的沒有限價(jià)指令時(shí)，禁止另一方提交市價(jià)指令。撮合成交的具體方式：以買入指令為例，STM維護(hù)一份指令薄，對(duì)新到達(dá)的買入指令進(jìn)行判斷，對(duì)于市價(jià)指令按照最低賣出價(jià)格成交相應(yīng)數(shù)量，如果最低賣出價(jià)格指令的數(shù)量不夠，則向上提高一檔，直到提高的檔次達(dá)到買入指令設(shè)置的最大值或買入指令完全成交或者指令薄上的賣出限價(jià)指令項(xiàng)目為空。對(duì)于限價(jià)買入指令，按照價(jià)格優(yōu)先，時(shí)間優(yōu)先的原則進(jìn)行處理，如果價(jià)格高于最低賣出價(jià)格，則按照最低賣出價(jià)格成交相應(yīng)數(shù)量，如果最低賣出價(jià)格的數(shù)量不夠，則向上提高一檔，直到當(dāng)前指令全部成交或者指令薄上低于當(dāng)前執(zhí)行指令價(jià)格的限價(jià)賣出指令為空；如果撮合成交完成后，仍未完全成交，則剩余部分插入指令薄的限價(jià)買入指令的有序隊(duì)列。

頻譜使用者 （買方）的報(bào)價(jià)策略，頻譜使用者通過接收STM廣播價(jià)格消息結(jié)合自身的頻譜使用收益進(jìn)行決策報(bào)價(jià)，并向STM發(fā)送交易指令。頻譜提供者 （賣方）的報(bào)價(jià)策略，頻譜提供者通過接收STM廣播價(jià)格消息結(jié)合自身的頻譜提供成本進(jìn)行決策報(bào)價(jià)，并向STM發(fā)送交易指令。

3 基于連續(xù)雙向拍賣的頻譜分配算法

在具體模型中將i個(gè)頻譜提供者記為集合 M｛m1，m2…mi｝將j個(gè)頻譜使用者記為集合 N｛n1，n2，nj｝。STM 通過接收并處理兩個(gè)集合的元素遞交的指令，確定集合間元素的關(guān)系，這是一種松散，靈活的關(guān)系，雙方通過這種方式都可以隨時(shí)遞交自己的指令。

3.1 效用函數(shù)的設(shè)計(jì)

報(bào)價(jià)策略和交易者的效用函數(shù)密切相關(guān)，選擇一個(gè)合適的效用函數(shù)將對(duì)認(rèn)知用戶價(jià)格行為產(chǎn)生本質(zhì)的影響。假定成交價(jià)格的分布服從正太分布，頻譜提供者i提供頻譜k的收益效用函數(shù)gi（k，p，t），其中k代表頻譜的數(shù)量，p表示i對(duì)當(dāng)前要出售頻譜的報(bào)價(jià)，t表示等待的時(shí)間，i的收益函數(shù)gi（k，p，t）＝f（pi）piki－αki－βt，其中f（pi）＝為報(bào)價(jià)時(shí)p可以成交的概率密度函數(shù)，α，β為常數(shù)，報(bào)價(jià)p和預(yù)期收益ξ直接相關(guān)。頻譜使用者j使用頻譜k的收益函數(shù)其中δ、φ為常數(shù)，報(bào)價(jià)p和預(yù)期收益η直接相關(guān)。

3.2 算法描述

4 仿真實(shí)驗(yàn)與性能分析

應(yīng)用本文分配算法，使用MatLab 7平臺(tái)進(jìn)行仿真。仿真的無(wú)線網(wǎng)絡(luò)環(huán)境為：在半徑為1km的環(huán)境內(nèi)，均勻分布頻譜供應(yīng)商500個(gè)，用戶500個(gè)，每次交易的頻譜為一個(gè)單位，用戶的需求符合泊松分布。

4.1 算法時(shí)間復(fù)雜度收斂情況

根據(jù)偽代碼的描述可以得出算法的時(shí)間復(fù)雜度為Οn（）1.3。圖3為基于連續(xù)雙向拍賣的頻譜分配算法和雙向拍賣的算法的收斂情況。橫坐標(biāo)表示時(shí)間，縱坐標(biāo)表示價(jià)格，可以看出，在執(zhí)行了約20個(gè)算法周期后，雙方的成交價(jià)格趨于穩(wěn)定，系統(tǒng)達(dá)到平衡狀態(tài)，驗(yàn)證了算法的收斂性。

圖3 算法的收斂情況

4.2 交易雙方的收益情況

如圖4所示，頻譜供應(yīng)商的收益和用戶的收益呈現(xiàn)一定的負(fù)相關(guān)性，這符合雙方價(jià)格競(jìng)爭(zhēng)的過程。頻譜供應(yīng)商的收益與成交價(jià)格以及成交量相關(guān)，隨價(jià)格升高而增加，隨成交量的增加而增加，但是成交量和價(jià)格之間沒有確定的關(guān)系。成交價(jià)格和成交量是對(duì)雙方市場(chǎng)行為的記錄，市場(chǎng)雙方未來的行為和其歷史記錄并沒有必然的關(guān)系，只是對(duì)當(dāng)下供需關(guān)系的直觀反映。頻譜用戶的收益顯然和成交的價(jià)格負(fù)相關(guān)，隨著價(jià)格的升高，頻譜用戶收益減少，隨著價(jià)格的降低頻譜用戶的收益增加。從仿真圖中可以看出，當(dāng)成交價(jià)格收斂到一個(gè)穩(wěn)定范圍內(nèi)時(shí)，雙方的收益也趨于穩(wěn)定。

圖4 雙方的收益情況

4.3 系統(tǒng)吞吐量

如圖5所示，系統(tǒng)的吞吐量可以用單位時(shí)間內(nèi)的成交量來表示。用TP來表示吞吐量，本算法中的吞吐量可以表示為其pi代表單位時(shí)間內(nèi)的每一筆的成交數(shù)量，n表示時(shí)間段內(nèi)總共成交的筆數(shù)。成交量的大小直接反應(yīng)當(dāng)前系統(tǒng)的吞吐量，同時(shí)成交量也是市場(chǎng)交易活躍度的實(shí)際反應(yīng)，顯然成交量大的交易活躍，說明用戶需求旺盛，同時(shí)資源也充足。成交量小的交易冷清，說明價(jià)格不合理、用戶需求均較少，或者頻譜供應(yīng)匱乏。

圖5 系統(tǒng)的吞吐量

5 結(jié)束語(yǔ)

本文基于認(rèn)知無(wú)線網(wǎng)絡(luò)環(huán)境，運(yùn)用連續(xù)雙向拍賣的撮合成交機(jī)制，提出了基于連續(xù)雙向拍賣的自適應(yīng)負(fù)載頻譜分配算法。該算法應(yīng)用市場(chǎng)供需機(jī)制來描述頻譜的分配過程，將復(fù)雜的分配過程轉(zhuǎn)化成頻譜供應(yīng)商和用戶雙方的市場(chǎng)行為。通過供需雙方價(jià)格的有效競(jìng)爭(zhēng)來完成頻譜分配過程，降低了算法的復(fù)雜度。仿真結(jié)果顯示，算法可以在較短的時(shí)間內(nèi)達(dá)到均衡，實(shí)現(xiàn)頻譜的有效分配，并且保證了雙方的收益。本文的算法可以有效的進(jìn)行頻譜分配，但是市場(chǎng)化的方法僅僅將頻譜看作同質(zhì)化的商品，沒有考慮相同價(jià)格條件下，頻譜的功率控制、干擾等問題，而現(xiàn)實(shí)場(chǎng)景中，發(fā)射功率、干擾等因數(shù)對(duì)網(wǎng)絡(luò)穩(wěn)定性、網(wǎng)絡(luò)吞吐量、通信質(zhì)量有重要的影響。如何對(duì)無(wú)價(jià)格差異的分配結(jié)果進(jìn)行優(yōu)化已達(dá)合理控制功率，減少干擾需要進(jìn)一步的研究。

［1］WU Qiong，XIAN Yongju，XU Changbiao.Handover spectrum allocation based on bidding model in cognitive networks［J］.Computer Engineering，2011，37 （12）：71－73 （in Chinese）.［吳瓊，鮮永菊，徐昌彪.認(rèn)知網(wǎng)絡(luò)中基于競(jìng)價(jià)模型的切換頻譜分配 ［J］.計(jì)算機(jī)工程，2011，37 （12）：71－73.］

［2］LIU Yingting，CAI Jueping，LI Zan.Dynamic spectrum allocation based on continuous double auctions in cognitive radio networks ［J］.Journal of Xidian University，2009，36 （6）：997－1002 （in Chinese）. ［劉英挺，蔡覺平，李贊.認(rèn)知網(wǎng)絡(luò)中基于連續(xù)雙向拍賣的動(dòng)態(tài)頻譜分配 ［J］.西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，36 （6）：997－1002.］

［3］WENG Chuliang，LU Xinda.A double auction method for resource allocation on computational grids ［J］.Chinese Journal of Computers，2006，36 （6）：1004－1009 （in Chinese）. ［翁楚良，陸鑫達(dá).一種基于雙向拍賣機(jī)制的計(jì)算網(wǎng)格資源分配方法 ［J］.計(jì)算機(jī)學(xué)報(bào)，2006，36 （6）：1004－1009.］

［4］Rosenthal R.A class of games possessing pure－strategy Nash equilibria ［J］.International Journal of Game Theory，1973，2 （1）：65－67.

［5］Fabrikant A，Papadimitriou C，Talwar K.The complexity of pure Nash eauilibria ［C］／／The 36th Annual ACM Symposium on Theory of Computing，2004：604－612.

［6］Chen L.A distributed access point selection algorithm based on no－regret learning for wireless access networks ［C］／／IEEE Vehicular Technology Conference，2010：1－5.

［7］Ercetin O.Association games in IEEE 802.11wireless local area networks ［J］.IEEE Transactions on Wireless Communications，2008，7 （12）：5136－5143.

［8］Altman E，Kumar A，Hayel Y.A potential game approach for uplink resource allocation in a multichannel wireless access network ［C］／／Pisa，Italy：Proceedings of the Fourth International ICST Confere－nce in Performance Evaluation Methodologies and Tools，2009.

［9］Liu Mingyan，Ahmad S H A，Wu Yunnan.Congestion games with resource reuse and applications in spectrum sharing［C ］／／Istanbul， Turkey： Proceedings of International Conference on Game Theory for Networks，2009：171－179.

［10］Sahand Ahmad，Cem Tekin，Liu Mingyan，et al.Spectrum sharing as spatial congestion games ［J］.IEEE Transaction on Networking，2010.

［11］WANG Jinlong，WU Qihui，GONG Yuping，et al.Cognitive wireless networks ［M］.Beijing：China Machine Press，2010：100－120 （in Chinese）. ［王金龍，吳啟輝，龔玉萍，等.認(rèn)知無(wú)線網(wǎng)絡(luò) ［M］.北京：機(jī)械工業(yè)出版社，2010：100－120.］

［12］Saraydar C U，Mandayam N B，Goodman D J.Efficient po－wer control via pricing in wireless data networks ［J］.IEEE Transactions on Communications，2002，50 （2）：291－303.