物聯(lián)網(wǎng)環(huán)境下基于演化博弈的動(dòng)態(tài)頻譜分配算法

黎寶華

摘 要：研究物聯(lián)網(wǎng)環(huán)境下壟斷頻譜市場中兩個(gè)有限理性的服務(wù)提供商基于需求響應(yīng)的價(jià)格競爭。服務(wù)提供商購買頻譜擁有者提供的頻譜，相互動(dòng)態(tài)競爭提供給次用戶使用以謀求自身利益的最大化。引入動(dòng)態(tài)頻譜接入，同時(shí)考慮次用戶對價(jià)格的反應(yīng)，將服務(wù)提供商的動(dòng)態(tài)價(jià)格策略選擇建模為演化博弈模型。通過復(fù)制動(dòng)態(tài)，提出的算法收斂到演化穩(wěn)定均衡（ESS）。仿真結(jié)果表明所該算法是收斂的，可以達(dá)到ESS，分析結(jié)果驗(yàn)證了演化博弈算法的穩(wěn)定性和有效性。

關(guān)鍵詞：動(dòng)態(tài)頻譜接入;有限理性;演化穩(wěn)定均衡;復(fù)制動(dòng)態(tài)

中圖分類號(hào)：TP277 ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ?文章編號(hào)：2095-1302（2015）01-00-03

0 ?引 ?言

在通信技術(shù)與計(jì)算機(jī)技術(shù)飛速發(fā)展的今天，智能化以超出想象的速度發(fā)展迅猛，使得信息技術(shù)對人的支撐擴(kuò)展到了對物體的支撐，實(shí)現(xiàn)了物與物之間的通信與協(xié)作，物聯(lián)網(wǎng)就是在互聯(lián)網(wǎng)的基礎(chǔ)上，將其用戶端延伸和擴(kuò)展到任何物品，進(jìn)行信息交換和通信的一種網(wǎng)絡(luò)[1]。目前業(yè)界普遍認(rèn)為，物聯(lián)網(wǎng)將會(huì)在未來得到更大規(guī)模的應(yīng)用，將會(huì)引起繼計(jì)算機(jī)、Internet之后，世界信息產(chǎn)業(yè)的第三次浪潮。物聯(lián)網(wǎng)將物體攜帶信息實(shí)時(shí)采集上來，并進(jìn)行信息共享和交互，實(shí)現(xiàn)時(shí)時(shí)、處處的“物物相連”[2，3]。物聯(lián)網(wǎng)最早起源于1999年美國MIT“自動(dòng)識(shí)別中心”提出的“萬物皆可通過網(wǎng)絡(luò)進(jìn)行互聯(lián)”的觀念[4]。2005年， 國際電信聯(lián)盟（ITU）在當(dāng)年的ITU互聯(lián)網(wǎng)報(bào)告中正式對物聯(lián)網(wǎng)做出了定義[5]。隨后，各個(gè)國家與地區(qū)都相繼開啟了物聯(lián)網(wǎng)的發(fā)展之路，其中包括IBM“智慧地球”的理念，日本的“u-Japan”戰(zhàn)略、韓國為期十年的“u-Korea”戰(zhàn)略規(guī)劃以及中國的“感知中國”等，成為各國國家級(jí)發(fā)展規(guī)劃中的重要一環(huán)[6]。

在物聯(lián)網(wǎng)存在與發(fā)展的諸多資源要素中，無線電頻譜是當(dāng)之無愧的基礎(chǔ)性支撐資源[7-9]。認(rèn)知無線電是一種提高無線通信頻譜利用率的技術(shù)，為解決物聯(lián)網(wǎng)頻譜資源短缺與頻譜需求旺盛之間的矛盾提供了有效的解決途徑。由于涉及競爭問題，物聯(lián)網(wǎng)的頻譜資源管理屬于策略的對抗，運(yùn)用博弈論來解決是一種非常奏效的辦法。借助博弈論，物聯(lián)網(wǎng)和現(xiàn)有的無線系統(tǒng)之間的頻譜共享在提高頻譜利用率的同時(shí)也為現(xiàn)有的無線系統(tǒng)獲得了更高的收益[10]。

本文考慮物聯(lián)網(wǎng)環(huán)境下兩個(gè)有限理性的無線網(wǎng)絡(luò)服務(wù)提供商和次用戶之間的動(dòng)態(tài)頻譜接入。無線網(wǎng)絡(luò)服務(wù)提供商向頻譜擁有者（如美國聯(lián)邦通訊委員會(huì)FCC）租借頻譜，再將未使用的頻譜提供給次用戶共享以最大化自己的利益[11]。我們假設(shè)這兩個(gè)服務(wù)提供商可以通過價(jià)格策略動(dòng)態(tài)競爭潛在的次用戶。次用戶的響應(yīng)通過接受概率建模，反應(yīng)其購買服務(wù)商提供的服務(wù)的意愿。同時(shí)引入演化穩(wěn)定策略從動(dòng)態(tài)的角度研究服務(wù)提供商的價(jià)格選擇過程，并且考慮了次用戶的響應(yīng);此外，有限理性的服務(wù)提供商可以根據(jù)我們提出的演化算法動(dòng)態(tài)調(diào)整他們的策略達(dá)到演化穩(wěn)定均衡。

1 ?系統(tǒng)模型

考慮含有兩個(gè)有限理性認(rèn)知移動(dòng)服務(wù)提供商的壟斷無線通信系統(tǒng)，兩個(gè)服務(wù)提供商向同一個(gè)頻譜擁有者租借頻譜，并且在有限區(qū)域內(nèi)相互進(jìn)行價(jià)格競爭提供服務(wù)給終端的次用戶。假設(shè)次用戶都具有認(rèn)知功能，模型如圖1所示。在競爭過程中，兩個(gè)服務(wù)提供商都最大化各自的收益，因而兩者是非合作博弈。此外，假設(shè)次用戶可以自由選擇任一個(gè)虛擬服務(wù)提供商。

圖 1 ?系統(tǒng)模型

考慮次用戶對服務(wù)提供商定價(jià)策略的反應(yīng)十分重要。因此，引入接受概率B（v，p），其中v為次用戶的效用函數(shù)，p是服務(wù)提供商公布的價(jià)格。接受概率應(yīng)具有以下屬性：即隨效用的增加或價(jià)格的減少而增加[12]：

（1）

因此，次用戶的接受概率可以定義如下：

（2）

其中β為次用戶對價(jià)格的敏感度， γ表示次用戶對效用的敏感度， α是常數(shù)。

而次用戶的效用函數(shù)定義為：

（3）

其中R為服務(wù)提供商提供的速率，p是服務(wù)提供商發(fā)布給次用戶的價(jià)格，K，ε和δ是確定上述效用函數(shù)精確形狀的正常數(shù)。

為了便于分析，我們假設(shè)α=1，β=γ=4，ε=10和δ=12。所以，接受概率可以改寫為：

B（v，p）=e-p/v ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

對應(yīng)次用戶的效用函數(shù)為：

（5）

2 ?基于價(jià)格的演化博弈算法和策略分析

我們假設(shè)兩個(gè)有限理性服務(wù)提供商同時(shí)宣布他們的價(jià)格，并且互相不知道對方的價(jià)格。具有較高的接受概率的服務(wù)提供商將獲得利潤，而另一個(gè)服務(wù)提供商將沒有利潤。此外，如果兩個(gè)供應(yīng)商的接受概率是相同的，則他們都能獲得利潤。因此，服務(wù)提供商的效用函數(shù)定義為：

（6）

其中：Ci是服務(wù)提供商產(chǎn)生的固定成本。

在這個(gè)動(dòng)態(tài)頻譜接入的過程中， 每一個(gè)服務(wù)提供商都有兩種價(jià)格策略的選擇：高價(jià)策略ph或者低價(jià)策略pl。由于接受概率是價(jià)格的減函數(shù)，因此低價(jià)策略的接受概率Bl的值高于高價(jià)策略的接受概率Bh的值。

根據(jù)式（6）計(jì)算出的不同價(jià)格策略的收益，上述對稱的博弈過程可由表1的2×2矩陣來表示。其中Bh是服務(wù)提供商選擇高價(jià)策略ph的接受概率，Bl是服務(wù)提供商選擇低價(jià)策略pl的接受概率，C是服務(wù)提供商產(chǎn)生的固定成本。

表 1 ?服務(wù)提供商的收益矩陣

服務(wù)提供商 2

服務(wù)提供商 1 ph pl

ph 1/2（ph-C）Bh，1/2（ph-C）Bh 0， （pl-C）Bl

pl （pl-C）Bl，0 1/2（pl-C）Bl，

1/2（pl-C）Bl

如表1所示，若兩個(gè)服務(wù)提供商都選擇高價(jià)策略ph，他們獲得的收益為1/2（ph-C）Bh，否則，若同時(shí)選擇低價(jià)策略pl，他們將分別獲得收益1/2（pl-C）Bl;若一方服務(wù)提供商選擇低價(jià)策略，而另一方選擇高價(jià)策略，則選擇低價(jià)策略的服務(wù)提供商將獲得收益（pl-C）Bl，選擇高價(jià)策略的服務(wù)提供商將獲得零收益，反之亦然。

3 ?演化穩(wěn)定均衡解

在動(dòng)態(tài)頻譜接入的競爭博弈中，博弈雙方都以最大化自己的利益為目標(biāo)，每個(gè)博弈者的均衡策略都是為了達(dá)到自己期望收益的最大值，與此同時(shí)，其他所有博弈者也遵循這樣的策略，則這樣的策略組合被稱為納什均衡[13]。

定義服務(wù)提供商選擇高價(jià)策略ph的概率為x（0≤x≤1），則選擇低價(jià)策略pl的概率為1-x。利用上述演化博弈模型，服務(wù)提供商選擇高價(jià)策略和低價(jià)策略的期望收益分別為：

v（ph，x）=vh=1/2x（ph-C）Bh ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

v（pl，l-x）=vl=1/2（1+x）（pl-C）Bl ? ? ? ? ? ? ? ? ? ? ?（8）

因此服務(wù)提供商的平均收益為：

（9）

根據(jù)vh=vl，即式（7）等于式（8），可以得到完全理性條件下的納什均衡解：

（10）

然而在有限理性條件下，如果選擇高價(jià)策略的收益高于平均收益，則根據(jù)復(fù)制動(dòng)態(tài)定義，選擇高價(jià)策略的概率x將會(huì)增長。所以依照復(fù)制動(dòng)態(tài)方程，有限理性的服務(wù)提供商選擇高價(jià)策略的變化率可以表示為：

（11）

基于復(fù)制動(dòng)態(tài)，演化均衡定義為復(fù)制動(dòng)態(tài)穩(wěn)定的不動(dòng)點(diǎn)集。演化均衡是演化博弈的理想解，因?yàn)椴┺恼叩姆N群隨著時(shí)間的演化會(huì)收斂到演化均衡。此外，當(dāng)博弈者的收益等于平均收益，他們都不會(huì)再改變自己的策略，從而達(dá)到演化均衡時(shí)。

令式（11）等于0，從而可以得到穩(wěn)定均衡點(diǎn)：

x=0，x=1或 ? ? ? ? ? ? ?（12）

其中x=0表示服務(wù)提供商在博弈中最終會(huì)選擇低價(jià)策略， x=1表示服務(wù)提供商在博弈中最終會(huì)選擇高價(jià)策略，而是動(dòng)態(tài)頻譜接入博弈的混合策略均衡，即按一定的比例選擇高價(jià)策略和低價(jià)策略。

有限理性服務(wù)提供商的策略是根據(jù)他們的當(dāng)前收益和平均收益進(jìn)行選擇的。所以基于演化博弈的動(dòng)態(tài)頻譜接入算法可以描述如下：

（1）有限理性服務(wù)提供商隨機(jī)地選擇高價(jià)策略和低價(jià)策略。

（2）迭代： t = 1， 2， 3， ……

①服務(wù)提供商根據(jù)式（1）在時(shí)刻t計(jì)算選擇策略后所獲得的收益v（ph，x）以及平均收益

②if v（ph，x）<

if rand （ ） < [-v（ph，x）] /

選擇低價(jià)策略

end

end

③結(jié)束。選擇低價(jià)策略的比例達(dá)到穩(wěn)定，即進(jìn)化均衡。其中rand（）∈[0，1]在這里表示一個(gè)隨機(jī)數(shù)。

4 ?仿真結(jié)果

考慮動(dòng)態(tài)頻譜共享的認(rèn)知無線系統(tǒng)包含兩個(gè)有限理性移動(dòng)虛擬服務(wù)提供商，其中仿真參數(shù)設(shè)置如下：服務(wù)提供商的固定成本為0.1，提供的速率為20 Mb/s，參數(shù)K為5×106。為了不失一般性，服務(wù)提供商的高價(jià)和低價(jià)分別假設(shè)為5和1。

本算法在不同初始策略選擇概率條件下的收斂情況如圖2所示?？梢钥闯觯疚乃岢龅难莼惴ㄊ鞘諗康?，并且最終收斂到0，這表示服務(wù)提供商最終選擇低價(jià)策略，即不論初始選擇低價(jià)策略還是高價(jià)策略，隨著時(shí)間的迭代，有限理性的服務(wù)提供商最終會(huì)選擇低價(jià)策略以吸引潛在的次用戶，所以低價(jià)策略是收斂點(diǎn)。

圖2 ?策略選擇的收斂過程

圖3給出了不同初始策略選擇概率條件下服務(wù)提供商的收益演化情況。服務(wù)提供商選擇低價(jià)策略的收益等于平均收益，此時(shí)博弈達(dá)到演化均衡，一旦達(dá)到演化均衡，博弈者都不會(huì)再改變此時(shí)的選擇，而選擇高價(jià)策略的服務(wù)提供商最終將會(huì)獲得零收益。這表示服務(wù)提供商在初始公布的價(jià)格越低，次用戶的接受概率則越高，即更多的次用戶會(huì)選擇低價(jià)策略的服務(wù)提供商，因此服務(wù)提供商獲得的收益更多;相反，選擇高價(jià)策略的服務(wù)提供商最終不會(huì)獲得收益。

6 ?結(jié) ?語

本文研究了物聯(lián)網(wǎng)環(huán)境下雙寡頭壟斷市場中兩個(gè)有限理性的服務(wù)提供商的需求響應(yīng)價(jià)格競爭。為了實(shí)現(xiàn)利益最大化，服務(wù)提供商動(dòng)態(tài)的相互競爭以吸引次用戶。我們提出了演化博弈理論來建模服務(wù)提供商的動(dòng)態(tài)價(jià)格策略選擇，利用接受概率B（v，p）映射次用戶對服務(wù)提供商提供服務(wù)和公布價(jià)格的反應(yīng)，通過復(fù)制動(dòng)態(tài)，算法達(dá)到演化均衡。仿真結(jié)果表明，本文所提出的算法是收斂的，并且可以達(dá)到演化均衡，這可能為物聯(lián)網(wǎng)環(huán)境下的無線網(wǎng)絡(luò)供應(yīng)商提供一些見解。

圖3 ?服務(wù)提供商的收益演化過程

參考文獻(xiàn)

[1] 李會(huì)平. 物聯(lián)網(wǎng)：實(shí)現(xiàn)中國飛躍的一次機(jī)會(huì)[J]. 創(chuàng)新科技， 2010（5）：10-12

[2] 劉愛軍. 物聯(lián)網(wǎng)技術(shù)現(xiàn)狀及應(yīng)用前景展望[J]. 物聯(lián)網(wǎng)技術(shù)，2012，2（1）：69-73.

[3] 楊博雄，倪玉華，劉琨，等. 現(xiàn)代物聯(lián)網(wǎng)體系架構(gòu)中核心技術(shù)標(biāo)準(zhǔn)及其發(fā)展應(yīng)用研究[J]. 物聯(lián)網(wǎng)技術(shù)， 2013，3（1）：71-76.

[4] Gershenfeld N，Krikorian R，Cohen D. The Internet of Things[J]. Scientific American， 2004（4）：76-81.

[5] International Telecommunication Union. ITU Internet Reports 2005： The Internet of Things[R]. 2005.

[6] 劉強(qiáng)，崔莉，陳海明. 物聯(lián)網(wǎng)關(guān)鍵技術(shù)與應(yīng)用[J]. 計(jì)算機(jī)科學(xué)，2010， 37（6）：1-4.

[7] Akyildiz I F，Su W，Sankars Y.Wireless sensor networks： a survey[J].Computer Networks，2002，38（ 4） ： 393-422.

[8] 孫其博，劉杰，黎羴.物聯(lián)網(wǎng)： 概念、架構(gòu)與關(guān)鍵技術(shù)研究綜述[J].北京郵電大學(xué)學(xué)報(bào)，2010，33（ 3） ：43-47.

[9] 姚海鵬，張智江.異構(gòu)環(huán)境下物聯(lián)網(wǎng)頻譜規(guī)劃研究[J].電信科學(xué)，2012， 35（ 3） ： 81-85.

[10] Lin Fuhong，Liu Qian，Zhou Xianwei，et al.Cooperative differential game for model energy-bandwidth efficiency tradeoff in the internet of things[J]. China Communications，2014（1）：92-102.

[11] S. Sengupta， M. Chatterjee. An economic framework for dynamic spectrum access and service pricing[J]. IEEE/ACM Trans. on Networking， 2009， 17（4）： 1200-1213.

[12] L. Badia， M. Lindstrom， J. Zander， et al. Demand and pricing effects on the radio resource allocation of multimedia communication systems[J]. IEEE Globecom，2003（7）： 4116-4121.

[13] 朱·弗登博格，讓·梯若爾.博弈論[M].北京：中國人民大學(xué)出版社，1996.