[發(fā)明專利]認(rèn)知無(wú)線電網(wǎng)絡(luò)中基于重復(fù)博弈的組播路由算法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201010181769.X
• 申請(qǐng)日: 2010-05-19
• 公開（公告）號(hào): CN101860798A
• 公開（公告）日: 2010-10-13
• 發(fā)明（設(shè)計(jì)）人: 周賢偉;胡佳慧;劉濤;王超;陳月云
• 申請(qǐng)（專利權(quán)）人: 北京科技大學(xué)
• 主分類號(hào): H04W4/06
• 分類號(hào): H04W4/06;H04W16/02;H04W16/18;H04W40/04
• 代理公司: 北京東方匯眾知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11296
• 代理人: 劉淑芬

1.認(rèn)知無(wú)線電網(wǎng)絡(luò)中基于重復(fù)博弈的組播路由算法，所述算法具體步驟如下：

1.1建立組播路由算法的單階段博弈模型：

在該博弈模型中，博弈的參與者是認(rèn)知無(wú)線電網(wǎng)絡(luò)中的所有理性認(rèn)知節(jié)點(diǎn)，行動(dòng)策略是參與選路的節(jié)點(diǎn)選擇路徑的集合，效用函數(shù)是實(shí)現(xiàn)從認(rèn)知節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間所選路徑的端到端延時(shí)最小，針對(duì)認(rèn)知無(wú)線電網(wǎng)絡(luò)中的路由選擇博弈過(guò)程，形式化定義如下：

①博弈G中的每個(gè)階段子博弈為Γ；

②網(wǎng)絡(luò)中共有n個(gè)理性認(rèn)知節(jié)點(diǎn)，它們組成博弈參與者集合N，N＝{1，2，...，n}；

③S_i表示參與節(jié)點(diǎn)i的策略集，定義集合S＝{S₁，S₂，...，S_n}；

④定義效用函數(shù)集U_i：S→R，效用函數(shù)U_i(v_ij)；

⑤在博弈G中，對(duì)于每一個(gè)參與節(jié)點(diǎn)i，效用函數(shù)U_i是S_i和其對(duì)手S_-i的函數(shù)，其中，S_i是參與節(jié)點(diǎn)i的策略，S_-i是其對(duì)手的策略；

⑥貼現(xiàn)因子δ看成是認(rèn)知節(jié)點(diǎn)關(guān)于歷史偏好的變量；

基于以上說(shuō)明，該博弈模型如下：

G＝{Γ，N，{S_i}_i∈N，{U_i}_i∈N，δ}；

1.2參與節(jié)點(diǎn)i的端到端延遲時(shí)間；

假定參與節(jié)點(diǎn)i選擇路徑j(luò)，假設(shè)鏈路的容量為c_j，鏈路上數(shù)據(jù)流的速率為v_j，則單個(gè)包在路徑上的延遲時(shí)間為1/(c_j-v_j)；認(rèn)知網(wǎng)絡(luò)中有多個(gè)參與節(jié)點(diǎn)，所以考慮多個(gè)數(shù)據(jù)流的情況，假設(shè)網(wǎng)絡(luò)有n個(gè)理性路由器R₁，R₂，...，R_n，即博弈的參與者，這些路由器分別以λ₁，λ₂，...，λ_n的泊松分布形式向網(wǎng)絡(luò)發(fā)送數(shù)據(jù)；假設(shè)R_i所選擇的路徑為l_j，則其處理能力，即鏈路容量為μ_ij；v_ij表示認(rèn)知節(jié)點(diǎn)i沿路徑j(luò)轉(zhuǎn)發(fā)數(shù)據(jù)流的速率；

定義數(shù)據(jù)流在每條路徑上的延遲時(shí)間為

Dij(vij)=1/(cij-Σk=1nvkjλk)]]>

則參與節(jié)點(diǎn)i的端到端延遲時(shí)間為

Ui(vij)=Σj=1nvijDij(vij)=Σj=1n[vij/(cij-Σk=1nvkjλk)]]]>

1.3建立組播路由算法的多階段博弈模型；

假定，表示節(jié)點(diǎn)i在t時(shí)間的行動(dòng)策略，每一個(gè)階段的策略t時(shí)間的歷史h^t＝(a⁰，a¹，...，aⁿ)，則節(jié)點(diǎn)i在t階段博弈中的行動(dòng)策略可以表示為這里

在t階段的重復(fù)博弈中，節(jié)點(diǎn)的效用函數(shù)為

Uit(vijt)=Σj=1nvijtDijt(vijt)=Σj=1n[vijt/(cij-Σk=1nvkjtλk)]]]>

則

其中，ρ_ij(k)表示節(jié)點(diǎn)i選擇鏈路j的概率，且ρ_ij∈[-1，1]

上式中，表示認(rèn)知節(jié)點(diǎn)i選擇的鏈路j在t時(shí)間時(shí)的聲譽(yù)定義此時(shí)節(jié)點(diǎn)的效用函數(shù)為

其中，α，β為加權(quán)因子

對(duì)于每一時(shí)間t，參與者i的效用是則效用流可以表示成

(1-δ)Σt=0∞δtsit]]>

1.4驗(yàn)證算法可靠性

由步驟1.1得到了該博弈的效用函數(shù)U_i，每個(gè)參與節(jié)點(diǎn)選擇延遲時(shí)間最短的路徑，要求延遲時(shí)間最小，即

min{U_i(v_ij)}

利用規(guī)劃求解法，該博弈模型中參與節(jié)點(diǎn)i的最優(yōu)解為：

vij=[cij-(cij)1/2(Σj=1ncij-λi)/Σj=1n(cij)1/2]/λi]]>

即，當(dāng)v_ij取該值時(shí)，參與節(jié)點(diǎn)所選擇的路徑延遲時(shí)間最小。

2.根據(jù)權(quán)利要求1所述的認(rèn)知無(wú)線電網(wǎng)絡(luò)中基于重復(fù)博弈的組播路由算法，其特征在于：在所述步驟1.3的多階段博弈模型中，還可以通過(guò)將路由選擇的歷史參與到路由選擇中，從而為下次路由選擇提供了參考，并節(jié)省了大量計(jì)算相同路徑延遲時(shí)間的帶寬，進(jìn)而有效地簡(jiǎn)化了算法的冗余度，具體步驟如下：

分析算法冗余度

根據(jù)節(jié)點(diǎn)與鏈路之間可能的情況，假設(shè)：

U(鏈路不是最優(yōu)，節(jié)點(diǎn)未選擇)＝U(N，N)＝v′，

U(鏈路最優(yōu)，節(jié)點(diǎn)未選擇)＝U(Y，N)＝v″，

U(鏈路不是最優(yōu)，節(jié)點(diǎn)選擇)＝U(N，Y)＝v″′，

U(鏈路最優(yōu)，節(jié)點(diǎn)選擇)＝U(Y，Y)＝v″″；

假設(shè)在t＝0時(shí)刻博弈參與的雙方，即節(jié)點(diǎn)和鏈路通過(guò)合作達(dá)到納什均衡，則在t＝1時(shí)刻，歷史h¹＝(N，N)，因此，雙方再次合作，t＝2時(shí)刻，h²＝((N，N)，(N，N))，以此類推到之后所經(jīng)過(guò)的時(shí)刻；

在前t時(shí)間里，節(jié)點(diǎn)獲得的收益是v′，假設(shè)在t時(shí)刻節(jié)點(diǎn)首先選擇了偏離之前所達(dá)到的均衡狀態(tài)，即，節(jié)點(diǎn)選擇該鏈路進(jìn)行數(shù)據(jù)傳輸，此時(shí)，節(jié)點(diǎn)的收益為v″；由于節(jié)點(diǎn)的選擇，誘使鏈路最優(yōu)，從而在之后的t+1，t+2，...時(shí)刻，節(jié)點(diǎn)獲得的收益是v″″；

由于前t時(shí)間參與者的收益為v′_i，t時(shí)刻的收益是v″_i，t之后的每一時(shí)刻收益為v_i″″，因此，此時(shí)的平均貼現(xiàn)值為

(1-δ^t)v′_i+δ^t[(1-δ)v″_i+δv″″_i]

針對(duì)不同的δ值計(jì)算節(jié)點(diǎn)的平均貼現(xiàn)值，發(fā)現(xiàn)，對(duì)于v″″＞v″＞v′＞v″′，當(dāng)δ≥1/2時(shí)博弈的雙方才能維持合作，即，在有限次重復(fù)博弈中，如果節(jié)點(diǎn)一直不選擇特定的鏈路，則納什均衡將會(huì)一直持續(xù)下去。