Ad-hoc網(wǎng)絡(luò)中基于博弈論和粒子群優(yōu)化的協(xié)作算法

張 闖,張佳巖,趙洪林

(哈爾濱工業(yè)大學(xué)通信技術(shù)研究所,黑龍江哈爾濱150080)

Ad-hoc網(wǎng)絡(luò)中基于博弈論和粒子群優(yōu)化的協(xié)作算法

張 闖,張佳巖,趙洪林

(哈爾濱工業(yè)大學(xué)通信技術(shù)研究所,黑龍江哈爾濱150080)

為了促使Ad-hoc網(wǎng)絡(luò)中的“自私”節(jié)點(diǎn)進(jìn)行合作,提出了一種基于博弈論和粒子群優(yōu)化的協(xié)作算法(Nash Bargaining of game theory and particle swarm optimization,NGPSO)在算法的第一階段,源節(jié)點(diǎn)通過(guò)對(duì)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)進(jìn)行價(jià)格補(bǔ)償,從而達(dá)到使中繼節(jié)點(diǎn)參與合作的目的。將源節(jié)點(diǎn)的最優(yōu)出價(jià)歸結(jié)為納什談判問題,得到具有帕累托最優(yōu)的激勵(lì)價(jià)格,保證源節(jié)點(diǎn)和中繼節(jié)點(diǎn)在合作中同時(shí)獲得最佳收益;在算法的第二階段,中繼節(jié)點(diǎn)在獲得源節(jié)點(diǎn)的最優(yōu)出價(jià)后,通過(guò)粒子群優(yōu)化算法得到最優(yōu)的轉(zhuǎn)發(fā)功率,使其合作收益增益最大。仿真表明,和隨機(jī)價(jià)格激勵(lì)相比,所提出的NGPSO算法能使源節(jié)點(diǎn)和中繼節(jié)點(diǎn)達(dá)到最優(yōu)收益;和中繼節(jié)點(diǎn)固定功率轉(zhuǎn)發(fā)相比,所提出的NGPSO算法,能顯著提高源節(jié)點(diǎn)的能量效率和中繼節(jié)點(diǎn)的收益,同時(shí)在適當(dāng)設(shè)置中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)功率的搜索空間時(shí),可以保證總的能量效率。

協(xié)作算法;博弈論;粒子群優(yōu)化;能量效率

0 引 言

近年來(lái),關(guān)于Ad-hoc網(wǎng)絡(luò)中節(jié)點(diǎn)間的協(xié)作問題得到了越來(lái)越多的關(guān)注。Ad-hoc網(wǎng)絡(luò)除可以表現(xiàn)出“無(wú)私”的合作特性外,還可能表現(xiàn)出不合作的“自私”特性。在Ad-hoc網(wǎng)絡(luò)中,如果節(jié)點(diǎn)既要進(jìn)行自身的數(shù)據(jù)傳輸,又要為其他節(jié)點(diǎn)提供路由選擇和數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù),則當(dāng)其為其他節(jié)點(diǎn)服務(wù)時(shí),勢(shì)必要消耗自身的能量和帶寬資源,節(jié)點(diǎn)往往表現(xiàn)出不合作的行為。研究表明,當(dāng)網(wǎng)絡(luò)中的不合作節(jié)點(diǎn)數(shù)目占到全網(wǎng)總結(jié)點(diǎn)的10%到40%時(shí),網(wǎng)絡(luò)的平均吞吐量會(huì)嚴(yán)重下降16%至32%[1]。因此,如何建立有效的激勵(lì)機(jī)制,促進(jìn)節(jié)點(diǎn)間合作是一個(gè)亟待解決的問題。

為了促使節(jié)點(diǎn)進(jìn)行合作型的數(shù)據(jù)轉(zhuǎn)發(fā),文獻(xiàn)[2-3]提出了針鋒相對(duì)(Tit-for-Tat)的協(xié)作策略,該策略使網(wǎng)絡(luò)中的節(jié)點(diǎn)根據(jù)歷史統(tǒng)計(jì)來(lái)判斷是否進(jìn)行合作。然而,針鋒相對(duì)策略是一種反復(fù)博弈的過(guò)程,當(dāng)節(jié)點(diǎn)在網(wǎng)絡(luò)中出現(xiàn)的次數(shù)很少時(shí),該策略可能失效。文獻(xiàn)[4]提出了一種基于價(jià)格補(bǔ)償?shù)募?lì)合作策略,通過(guò)接入點(diǎn)對(duì)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)量進(jìn)行價(jià)格補(bǔ)償來(lái)激勵(lì)中繼節(jié)點(diǎn)幫助源節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。該策略中,中繼節(jié)點(diǎn)在合作中獲得的收益有時(shí)會(huì)低于非合作時(shí)獲得的收益,這是由該策略最大化接入點(diǎn)收益造成的。文獻(xiàn)[5]對(duì)文獻(xiàn)[4]的工作進(jìn)行了改進(jìn),將接入點(diǎn)對(duì)中繼節(jié)點(diǎn)做出的價(jià)格補(bǔ)償轉(zhuǎn)變?yōu)橛稍垂?jié)點(diǎn)做出,從而使中繼節(jié)點(diǎn)在合作中獲得的收益始終大于非合作中獲得的收益;文獻(xiàn)[6]針對(duì)一個(gè)源節(jié)點(diǎn)和多個(gè)中繼節(jié)點(diǎn)模型,采用非合作博弈方法,首先由中繼節(jié)點(diǎn)作為賣方?jīng)Q定帶寬價(jià)格,之后源節(jié)點(diǎn)根據(jù)帶寬價(jià)格決定其帶寬需求。該策略本質(zhì)上是一個(gè)Stackelberg博弈模型,文獻(xiàn)[6]證明了存在納什均衡,并提出了一種分布式算法計(jì)算納什均衡,但同時(shí)文獻(xiàn)[6]也提到納什均衡并不是最有效率的;文獻(xiàn)[7]針對(duì)一個(gè)時(shí)分復(fù)用系統(tǒng),采用合作博弈的方法,提出了一種基于交換時(shí)隙資源的激勵(lì)合作機(jī)制;文獻(xiàn)[8]對(duì)文獻(xiàn)[7]的工作進(jìn)行擴(kuò)展,提出了一種聯(lián)合時(shí)隙和功率分配的協(xié)作方法;文獻(xiàn)[9]同樣在基于資源交換進(jìn)行協(xié)作的基礎(chǔ)上,提出了一種快速粒子群算法從而獲得合作博弈的納什均衡。文獻(xiàn)[4-6]是基于非合作博弈的方法對(duì)激勵(lì)合作機(jī)制進(jìn)行了研究,非合作博弈的納什均衡有可能是無(wú)效率的,即不具有帕累托最優(yōu)性,不能一定保證所設(shè)計(jì)的效用函數(shù)最優(yōu);文獻(xiàn)[7-9]采用合作博弈理論建立了激勵(lì)合作的機(jī)制,但基于資源交換建立的合作機(jī)制是建立在雙方都有閑置資源的基礎(chǔ)上的,這限制了其應(yīng)用范圍。

不同于以上研究,為了促使Ad-hoc網(wǎng)絡(luò)中的“自私”節(jié)點(diǎn)參與合作,本文提出了一種基于博弈論和粒子群優(yōu)化的協(xié)作算法(Nash bargaining of game theory and particle swarm optimization,NGPSO)。本文主要貢獻(xiàn)是解決了激勵(lì)合作機(jī)制中的兩個(gè)關(guān)鍵問題:如何激勵(lì)合作及何時(shí)合作。①對(duì)于如何激勵(lì)合作問題,通過(guò)源節(jié)點(diǎn)對(duì)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)進(jìn)行價(jià)格補(bǔ)償,從而達(dá)到促使網(wǎng)絡(luò)中的“自私”節(jié)點(diǎn)進(jìn)行合作的目的。本文將源節(jié)點(diǎn)的最優(yōu)激勵(lì)價(jià)格歸結(jié)為納什談判問題,避免了傳統(tǒng)非合作博弈方法得到的納什均衡可能不是最佳策略的問題,確保源節(jié)點(diǎn)的激勵(lì)價(jià)格具有帕累托最優(yōu)性,從而使源節(jié)點(diǎn)和中繼節(jié)點(diǎn)在合作中獲得的收益最優(yōu);②對(duì)于何時(shí)合作問題,通過(guò)基于納什談判的最優(yōu)激勵(lì)算法,當(dāng)源節(jié)點(diǎn)和中繼節(jié)點(diǎn)合作獲得的收益大于非合作的收益時(shí),雙方達(dá)成合作;③進(jìn)一步,為了提高中繼節(jié)點(diǎn)的收益,采用粒子群優(yōu)化算法計(jì)算了中繼節(jié)點(diǎn)的最優(yōu)轉(zhuǎn)發(fā)功率。

1 系統(tǒng)模型

激勵(lì)合作機(jī)制的建立依賴于初始的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),本文主要研究如何得到源節(jié)點(diǎn)的最優(yōu)出價(jià)和中繼節(jié)點(diǎn)的最優(yōu)轉(zhuǎn)發(fā)功率,因此采用一種簡(jiǎn)單的網(wǎng)絡(luò)模型,如文獻(xiàn)[4]所描述,兩個(gè)位置相近的對(duì)等用戶被劃為一簇,其中用戶1作為發(fā)起協(xié)作請(qǐng)求的源節(jié)點(diǎn),用戶2作為中繼節(jié)點(diǎn),具體模型如圖1所示。假設(shè)系統(tǒng)是以頻分復(fù)用的方式工作,用戶之間不產(chǎn)生干擾,并且源節(jié)點(diǎn)和中繼節(jié)點(diǎn)的可用帶寬為W Hz,采用全向天線進(jìn)行數(shù)據(jù)的接收和發(fā)送。為了激勵(lì)中繼節(jié)點(diǎn)進(jìn)行傳輸,源節(jié)點(diǎn)對(duì)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)進(jìn)行價(jià)格補(bǔ)償,從而使中繼節(jié)點(diǎn)有動(dòng)力參與合作。模型中,用戶1的部分?jǐn)?shù)據(jù)被中繼節(jié)點(diǎn)轉(zhuǎn)發(fā),用戶2的數(shù)據(jù)直接傳輸給基站。假設(shè)用戶1請(qǐng)求協(xié)作傳輸?shù)臄?shù)據(jù)帶寬占總帶寬W的比例為n(n∈[0,1]),除了協(xié)作傳輸數(shù)據(jù)之外,用戶1的可用帶寬W全部用來(lái)和基站進(jìn)行數(shù)據(jù)傳輸。為了激勵(lì)用戶2進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā),用戶1對(duì)通過(guò)用戶2傳輸?shù)臄?shù)據(jù)進(jìn)行價(jià)格補(bǔ)償,每單位數(shù)據(jù)補(bǔ)償金額為u。假設(shè)用戶2愿意轉(zhuǎn)發(fā)的數(shù)據(jù)帶寬占總帶寬W的比例為n,用剩下的1-n的帶寬直接向目的節(jié)點(diǎn)發(fā)送其他數(shù)據(jù)。假設(shè)接入點(diǎn)(AP)對(duì)用戶1和用戶2每單位數(shù)據(jù)收費(fèi)為λ。

圖1 系統(tǒng)模型

從用戶1的角度,為了獲得更大的收益,它希望盡可能地減少每單位數(shù)據(jù)價(jià)格u;而從用戶2的角度,則希望盡可能地提高每單位數(shù)據(jù)價(jià)格u,本文采用納什談判的方法達(dá)到一個(gè)最優(yōu)折中。同時(shí),用戶2在獲得用戶1的出價(jià)后,需要考慮其自身性能(功率)及獲得回報(bào)(價(jià)格)之間的平衡,因此需要決定其最佳的轉(zhuǎn)發(fā)功率。下面對(duì)以上兩個(gè)問題進(jìn)行分析以確定這兩個(gè)參數(shù)。

2 能量效率

為了能夠定量地研究系統(tǒng)的性能,需要一個(gè)恰當(dāng)?shù)暮饬繕?biāo)準(zhǔn)。文獻(xiàn)[10-11]在用博弈論研究CDMA系統(tǒng)功率控制時(shí),給出了一種衡量系統(tǒng)性能的能量效率函數(shù),其定義為

該定義可以解釋為:每消耗一單位能量能夠正確接收的數(shù)據(jù)量。為了使該定義能夠符合實(shí)際,文獻(xiàn)[10]規(guī)定了其需要滿足的特性:當(dāng)p→∞時(shí),Ui(pi)→0;當(dāng)p→0時(shí), Ui(pi)→0。也就是說(shuō)當(dāng)發(fā)射功率為無(wú)窮大或者是零時(shí),用戶的能量效率值為0,這是符合常識(shí)的。Ti(pi)為有效傳輸信息量,在文獻(xiàn)中被定義為

式中,M為發(fā)送數(shù)據(jù)量;L為信息比特;M-L比特用作錯(cuò)誤檢測(cè)。f(γi)為效率函數(shù),其定義和傳統(tǒng)的表示一個(gè)數(shù)據(jù)幀被正確接收的概率稍有不同:

式中,γi為接收信噪比;BER(γi)為誤比特率;當(dāng)采用非相干2FSK調(diào)制時(shí)BER(γi)=1/2exp(-γi/2)。f(γi)之所以采取如此定義,是為了使發(fā)射功率為無(wú)窮大或者是零時(shí),用戶的能量效率為0,具體證明可以參照文獻(xiàn)[10]。

為分析方便,有R=ηW,其中η(b/(s·Hz))為頻譜效率,當(dāng)采用2FSK調(diào)制時(shí),η2FSK=1。因此式(2)可以表示為

由此,可以定義用戶1的能量效率為

式中,T1a(p1)為用戶1直接傳輸?shù)浇尤朦c(diǎn)的有效吞吐量,表示為

式中,γ1a為用戶1到接入點(diǎn)的信噪比;T21a(p1)為用戶1通過(guò)用戶2中繼的有效吞吐量,因?yàn)橛脩?中繼的數(shù)據(jù)占自身比例為n,因此)表示為

式中,γ12、γ2a分別為用戶1到中繼節(jié)點(diǎn),中繼節(jié)點(diǎn)到接入點(diǎn)的信噪比。用戶2的效用函數(shù)為

為用戶2用帶寬比例為1-n傳輸自己數(shù)據(jù)時(shí)的有效吞吐量。

3 收益函數(shù)

對(duì)于用戶1來(lái)說(shuō),為了促使用戶2進(jìn)行合作,需要對(duì)用戶2進(jìn)行補(bǔ)償,即支付用戶2每單位數(shù)據(jù)μ的價(jià)格,同時(shí),接入點(diǎn)對(duì)用戶1的收費(fèi)為每單位數(shù)據(jù)λ?？梢钥闯?用戶1獲得的好處為U1(p1),而付出代價(jià)是需要支付λT1a(p1)和(p1)的費(fèi)用。參考文獻(xiàn)[4]中對(duì)收益函數(shù)的定義,定義用戶1的收益函數(shù)為

該定義不同于文獻(xiàn)[2]中對(duì)于用戶2的補(bǔ)償由接入點(diǎn)做出,用戶1直接對(duì)用戶2進(jìn)行價(jià)格補(bǔ)償。

同理,用戶2的收益函數(shù)定義為

4 基于納什談判解的最優(yōu)激勵(lì)算法

本節(jié)將采用合作博弈理論中的納什談判方法對(duì)圖1所描述的系統(tǒng)進(jìn)行分析,并得到源節(jié)點(diǎn)的最優(yōu)激勵(lì)價(jià)格。

4.1 納什談判解的基本概念和定理

定義1 合作博弈論中的談判問題可以定義為:設(shè)k=1,2,…,K,K表示博弈參與者的集合,表示一個(gè)非空的閉合凸子集,用來(lái)表示參與者所有可行解的收益分配集合。令ˉUi為第i個(gè)參與者所期望得到的最小支付。(S,ˉUi)被稱為一個(gè)有K個(gè)參與者的談判問題。如果S滿足納什提出的4條公理,并且這個(gè)解[13]滿足:

這個(gè)解被稱為“納什談判解”(Nash bargaining solution,NBS)?！癗BS”的意義為:K個(gè)參與人選擇一個(gè)策略使得他們收益增益的乘積最大,這個(gè)乘積也稱為“納什乘積”。

定理1 在協(xié)作帶寬一定的條件下,本文提出的激勵(lì)問題為納什談判問題。

證明 兩個(gè)用戶的可行收益分配集合為

因此只需證明μ為凸子集,因?yàn)棣淌侨w實(shí)數(shù)集合,又因?yàn)檎麄€(gè)歐式空間n為凸集,所以μ為凸子集,即αμa+ (1-α)μb∈μ。由此可以證明αUp1(p1)a+(1-α)Up1(p1)b∈S1,同樣可以證明αUp2(p2)a+(1-α)Up2(p2)b∈S2。從而本文提出最優(yōu)激勵(lì)問題可以采用納什談判方法進(jìn)行解決。證畢

4.2 基于NBS的最優(yōu)價(jià)格

根據(jù)納什談判方法,前文所描述問題的NBS的表示方式為

1

2

式(20)可以決定源節(jié)點(diǎn)和中繼節(jié)點(diǎn)何時(shí)進(jìn)行合作:當(dāng)式(20)取值大于零,且UC1(p1)-U1(p1)和UC2(p2)-U2(p2)的值也同時(shí)大于零時(shí),源節(jié)點(diǎn)和中繼節(jié)點(diǎn)可以達(dá)成合作。即,和非合作方式相比,在合作中源節(jié)點(diǎn)和中繼節(jié)點(diǎn)的效用均得到了提高,合作有利可圖。

定理2 針對(duì)圖1所提的系統(tǒng),當(dāng)用戶1的發(fā)射功率為p1,用戶2的發(fā)射功率為p2,且用戶1和用戶2的合作收益為UC1(p1)和UC2(p2),不合作收益為U1(p1)和U2(p2)時(shí),則(UC1(p1)-U1(p1))(UC2(p2)-U2(p2))最優(yōu)價(jià)格的NBS如式(21)所示:

基于以上分析,本文提出了一種基于NBS的最優(yōu)激勵(lì)協(xié)作算法,具體過(guò)程如下。

算法1 基于NBS的最優(yōu)激勵(lì)算法

(1)用戶1和用戶2交換彼此發(fā)射功率信息p1和p2。

(2)用戶1根據(jù)式(21)計(jì)算最優(yōu)激勵(lì)價(jià)格并通知給用戶2。

(3)用戶2判斷UC2(p2)-U2(p2)的值。

①如果UC( p)-U(p)＞0,則用戶2合作并將合作

2222信息反饋給用戶1。

②否則,用戶1終止合作。否則,用戶2不合作。

(4)用戶1根據(jù)用戶2的反饋信息,判斷UC1(p1)-U1(p1)的值。

①如果UC1(p1)-U1(p1)＞0,則用戶1發(fā)送數(shù)據(jù)給用2。

算法1的實(shí)現(xiàn)前提是用戶1和用戶2需要獲知信噪比信息γ1a、γ12和γ2a。

5 基于粒子群優(yōu)化的轉(zhuǎn)發(fā)功率算法

在得到用戶1的最優(yōu)價(jià)格μ*之后,用戶2的合作增益效用可以表示為

由式(22)可以看出,當(dāng)用戶2獲知用戶1的最優(yōu)出價(jià)μ*后,用戶2希望最大化其合作增益效用,用戶2的合作增益效用依賴于效率函數(shù)和自身的發(fā)射功率,同時(shí)效率函數(shù)

f(γ2

1a)和f(γ2a)是p2的函數(shù),因此用戶2的轉(zhuǎn)發(fā)功率決定了其合作增益效用,但f(γ21a)和f(γ2a)中含有e的指數(shù)項(xiàng),故式(22)很難求得閉合解。為了獲得中繼節(jié)點(diǎn)的最優(yōu)轉(zhuǎn)發(fā)功率,本文提出了一種基于粒子群優(yōu)化的最優(yōu)轉(zhuǎn)發(fā)功率算法。

粒子群優(yōu)化算法(particle swarm optimization,PSO)是由文獻(xiàn)[14]提出的一種進(jìn)化計(jì)算技術(shù)。PSO算法首先在可行解空間中隨機(jī)初始化一群粒子,每個(gè)粒子代表優(yōu)化問題的一個(gè)潛在解,并用位置、速度和適應(yīng)度值表示該粒子的特征,適應(yīng)度值由適應(yīng)度函數(shù)計(jì)算得到,其值的大小代表了粒子的優(yōu)劣。粒子在可行解空間中運(yùn)動(dòng),通過(guò)跟蹤個(gè)體極值和群體極值更新個(gè)體位置,個(gè)體極值是指?jìng)€(gè)體所經(jīng)歷的位置中計(jì)算得到的適應(yīng)度值最優(yōu)的位置,群體極值是指所有粒子搜索得到的適應(yīng)度值最優(yōu)的位置。粒子每更新一次位置,就計(jì)算一次適應(yīng)度值,并通過(guò)比較新得到適應(yīng)度值和個(gè)體極值、群體極值的使用度值更新個(gè)體極值和群體極值的位置。

為求解式(22)所提出的優(yōu)化問題,設(shè)適應(yīng)度函數(shù)為fitness(p2)=U2(p2)-UC2(p2)。問題轉(zhuǎn)換為求解:

設(shè)種群的粒子數(shù)為M,種群的位置為Pj(j=1,2,…, M),其搜索空間為[pmin,pmax],粒子速度為Vj,fitness(Pj)為潛在解的適應(yīng)度值,pbest和gbest分別為最優(yōu)個(gè)體位置和最優(yōu)全局位置。本文提出的基于粒子群優(yōu)化的轉(zhuǎn)發(fā)功率算法如下。

算法2 基于粒子群優(yōu)化的轉(zhuǎn)發(fā)功率算法

(1)隨機(jī)初始化種群的位置Pj,Pj～f(pmin,pmax),其中f(·)為均勻分布函數(shù),pmin和pmax分別為最小和最大發(fā)射功率。

(2)隨機(jī)初始化粒子的速度Vj,Vj～f(0,1)。

(3)初始化第j個(gè)粒子的最優(yōu)位置:pbest←Pj,如果fitness(pbest)＞fitness(gbest),更新種群的最優(yōu)位置:gbest←pbest。

(4)初始化r1、r2,ri(i=1,2)～f(0,1)。

(5)按下式更新粒子的速度和位置:

①Vj←w Vj+c1r1(pbest-Pj)+c2r2(gbest-Pj),其中w為慣性權(quán)重,c1、c2為學(xué)習(xí)因子。

②Pj←Pj+Vj

③如果fitness(Pj)＜fitness(pbest),更新粒子的最優(yōu)位置pbest←Pj;如果fitness(pbest)＜fitness(gbest),更新粒子群的最優(yōu)位置gbest←pbest。

(6)若滿足停止條件(運(yùn)算精度或迭代次數(shù)),搜索停止,則gbest為最優(yōu)解。

(7)否則,返回步驟5繼續(xù)搜索。

由于式(22)是γ21a和γ2a的函數(shù),因此用戶2需要知道信道的信噪比狀態(tài)信息γ21a和γ2a。

6 實(shí)驗(yàn)結(jié)果及分析

仿真模型參考文獻(xiàn)[15],具體如圖2所示。

圖2 仿真模型

假設(shè)接入點(diǎn)在原點(diǎn)的位置上,用戶1位于X軸正方向900 m處,即用戶1的坐標(biāo)為(900,0)。用戶2的位置在X軸的方向移動(dòng),其坐標(biāo)為(d,0)。d為用戶2到接入點(diǎn)之間的距離,仿真中的參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)

在圖3中,縱軸表示兩個(gè)用戶的收益增益乘積((UC1(p1)-U1(p1))(UC2(p2)-U2(p2)))的值,橫軸表示用戶2距離接入點(diǎn)的距離,其負(fù)值表示用戶2在接入點(diǎn)左側(cè),正值表示用戶2在接入點(diǎn)右側(cè)。

圖3 用戶的收益增益乘積

從圖3中可以看出,當(dāng)用戶2距離接入點(diǎn)的距離小于260 m或在600～1 000 m時(shí),雙方的收益增益乘積為正,由圖4同時(shí)可以看出,當(dāng)用戶2距離接入點(diǎn)的距離小于260 m時(shí),用戶1和用戶2合作時(shí)的收益小于不合作時(shí)的收益,因此,只有當(dāng)用戶2距離接入點(diǎn)在600～1 000 m時(shí)(此時(shí),UC( p)

11-U1(p1)＞0且UC2(p2)-U2(p2)＞0),用戶1和用戶2通過(guò)合作可以增加彼此的收益,故此距離為協(xié)作距離。

由圖4可以看出,在協(xié)作距離內(nèi),和不合作相比,用戶1和用戶2的收益都明顯增加。圖4中,用戶1不合作時(shí)的收益之所以接近于0,是因?yàn)榉抡鎸⒂脩?距離接入點(diǎn)的距離設(shè)置的較遠(yuǎn),其信道條件較差,這更體現(xiàn)出用戶1需要其他用戶協(xié)作其傳輸。

圖4 協(xié)作與不協(xié)作時(shí)用戶的收益

圖5給出了用戶1協(xié)作時(shí)的收益、能量效率及不合作時(shí)的能量效率,從圖5中可以看出,用戶1的收益曲線包含于能量曲線。因此,在協(xié)作距離內(nèi)總能保證用戶1能量效率的提升,同時(shí)由圖5也可以看出,和不合作相比,用戶1的能量效率有了明顯的提升。

圖5 用戶1的收益和能量效率

圖6給出了用戶1采用納什談判價(jià)格和隨機(jī)價(jià)格時(shí)兩個(gè)用戶的收益增益乘積,由圖6可以看出,當(dāng)用戶1采用隨機(jī)價(jià)格時(shí),兩個(gè)用戶的收益增益乘積在協(xié)作距離內(nèi)不能始終為正,如果達(dá)成合作,一方的得益是以另一方的損失為前提的,因此當(dāng)用戶1采取隨機(jī)價(jià)格激勵(lì)時(shí),不能總是促使合作,并且即使收益增益乘積為正,和本文提出的最優(yōu)出價(jià)相比其值也不保證一定最優(yōu)。

圖6 用戶的收益增益乘積

圖7給出了當(dāng)用戶1采取隨機(jī)價(jià)格激勵(lì)時(shí)用戶1和用戶2的收益,從圖7中可以看出兩個(gè)用戶的收益函數(shù)是隨機(jī)變化的,和圖4中的最優(yōu)價(jià)格激勵(lì)相比,在協(xié)作距離內(nèi),兩個(gè)用戶的收益不能達(dá)到最優(yōu)。

圖8給出了在協(xié)作距離為750 m、800 m和850 m時(shí),適應(yīng)度值和迭代次數(shù)的關(guān)系。從圖8中可以看出,當(dāng)?shù)螖?shù)大于50次時(shí)適應(yīng)度值(即用戶2的合作收益增益)在搜索空間內(nèi)收斂,其收斂速度較快,對(duì)于目前的終端計(jì)算能量來(lái)講是可以完成此計(jì)算任務(wù)的。

圖9給出了當(dāng)用戶2采取不同轉(zhuǎn)發(fā)功率時(shí)用戶1在不同協(xié)作距離的能量效率。由圖9可以看出,本文所提NGPSO算法和用戶2的轉(zhuǎn)發(fā)功率為0.1 mW時(shí)相比顯著的增加了用戶1的能量效率,但同時(shí)也可看出,和用戶2的轉(zhuǎn)發(fā)功率為0.2 mW時(shí)相比,能量效率提升并不明顯,這是因?yàn)楫?dāng)用戶2的轉(zhuǎn)發(fā)功率達(dá)到一定值時(shí),用戶1到達(dá)接入點(diǎn)的有效數(shù)據(jù)量已經(jīng)基本穩(wěn)定,因此即使用戶2增加轉(zhuǎn)發(fā)功率也不會(huì)明顯改善用戶1的能量效率。

圖7 隨機(jī)價(jià)格時(shí)用戶的收益

圖8 適應(yīng)度和迭代次數(shù)

圖9 用戶1的能量效率

圖10給出了當(dāng)用戶2采取不同轉(zhuǎn)發(fā)功率時(shí)其收益在不同協(xié)作距離的變化情況。由圖10可以看出本文所提方法和采用固定功率轉(zhuǎn)發(fā)相比,用戶2的收益有了顯著的提升。

圖11給出了系統(tǒng)總的能量效率采用NGPSO算法和固定功率轉(zhuǎn)發(fā)在不同協(xié)作距離時(shí)的變化情況。從圖11中可以看出,和用戶2的轉(zhuǎn)發(fā)功率為0.1 mW或0.2 mW時(shí)相比,本文所提的NGPSO算法的能量效率不是很高,這是因?yàn)闉榱苏f(shuō)明本文所提算法收斂速度較快,將用戶2的最大轉(zhuǎn)發(fā)功率設(shè)置為用戶1的300倍增大了搜索空間,當(dāng)用戶2的轉(zhuǎn)發(fā)功率大到一定程度時(shí),其對(duì)有效數(shù)據(jù)量的提升并不能帶來(lái)明顯好處,反而降低了能量效率,在實(shí)際應(yīng)用當(dāng)中二者的功率差距不會(huì)如此之大。當(dāng)用戶2的轉(zhuǎn)發(fā)為0.2 mW時(shí),和0.1 mW相比系統(tǒng)總的能量效率有顯著的提升,因此,適當(dāng)減少用戶2的搜索空間時(shí),可以改善系統(tǒng)的能量效率。同時(shí),本文所提算法第二階段的優(yōu)化目標(biāo)為用戶2的合作收益增益,如果考慮系統(tǒng)總的能量效率,可以對(duì)式(22)的目標(biāo)函數(shù)進(jìn)行改進(jìn),進(jìn)行聯(lián)合優(yōu)化,也可以提升系統(tǒng)總的能量效率,這是下一步的工作。

圖10 用戶2的收益

圖11 總的能量效率

7 結(jié) 論

為促使Ad-hoc網(wǎng)絡(luò)中的“自私”節(jié)點(diǎn)進(jìn)行合作,本文提出了一種NGPSO算法,通過(guò)源節(jié)點(diǎn)對(duì)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)進(jìn)行價(jià)格補(bǔ)償,使中繼節(jié)點(diǎn)協(xié)助源節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸。首先,將源節(jié)點(diǎn)的最優(yōu)出價(jià)歸結(jié)為納什談判問題,得到具有帕累托最優(yōu)性的激勵(lì)價(jià)格的納什均衡解,從而保證源節(jié)點(diǎn)和中繼節(jié)點(diǎn)在合作中皆可獲得最佳收益;之后,在獲得源節(jié)點(diǎn)的出價(jià)后,通過(guò)粒子群優(yōu)化算法中繼節(jié)點(diǎn)決定其轉(zhuǎn)發(fā)功率,使其合作收益增益最大。仿真實(shí)驗(yàn)表明,本文所提NGPSO算法,和隨機(jī)價(jià)格激勵(lì)相比,能使源節(jié)點(diǎn)和中繼節(jié)點(diǎn)在合作中獲得的收益達(dá)到最優(yōu);和中繼節(jié)點(diǎn)固定轉(zhuǎn)發(fā)功率相比,能明顯提高中繼節(jié)點(diǎn)的收益和源節(jié)點(diǎn)的能量效率;同時(shí),適當(dāng)設(shè)置中繼節(jié)點(diǎn)的功率搜索范圍,可以保證系統(tǒng)總的能量效率。

[1]Marti S,Giuli T,Lai K,et al.Mitigating routing misbehavior in mobile Ad hoc networks[C]∥Proc.of the IEEE International Conference on Mobile Computing and Networking,2000:255-265.

[2]Srinivasan V,Nuggehalli P,Chiasserini CF,et al.An analytical approach to the study of cooperation in wireless ad hoc networks[J]. IEEE Trans.Wireless Communications,2005,4(2):722-733.

[3]Felegyhazi M,Hubaux J P,Buttyan L.Nash equilibria of packet forwarding strategies in wireless Ad hoc networks[J].IEEE Trans.on Mobile Computingation,2006,5(5):463 476.

[4]Ileri O,Mau S C,Mandayam N B.Pricing for enabling forwarding in self-configuring Ad hoc networks[J].IEEE Journal on Selected Areas Communications,2005,23(1):151-162.

[5]Shastry N,Adve R S.Stimulating cooperative diversity in wireless ad hoc networks through pricing[C]∥Proc.of the IEEE International Conference on Communications,2006:3747-3752.

[6]Cong L,Zhao L,Zhang H,et al.Pricing-based game for spectrum allocation in multi-relay cooperative transmission networks[J].IET Communications,2011,5(4):563-573.

[7]Zhang G,Yang K,Ding E,et al.Fair and efficient resource sharing for selfish cooperative communication networks using cooperative game theory[C]∥Proc.of the IEEE International Conference on Communications,2011:1-5.

[8]Zhang G,Yang K,Liu P,et al.Joint channel bandwidth and power

allocation game for selfish cooperative relaying networks[J].IEEE Trans.on Vehicular Technology,2012,61(9):4142-4156. [9]Zhang G,Yang K,Liu P,et al.Resource-exchange based cooperation stimulating mechanism for wireless ad hoc networks[C]∥Proc. of the IEEE International Conference on Communications,2012:297 -301.

[10]Goodman D J,Mandayam N B.Power control for wireless data[J]. IEEE Personal.Communications,2000,7(2):48-54.

[11]Saraydar C U,Mandayam N B,Goodman D J.Pricing and power control in a multicell wireless data network[J].IEEE Journal on Selected Areas Communications,2001,19(10): 1883-1892.

[12]Krikidis I,Thompson J,Mclaughlin S.et al.Amplify-and-forward with partial relay selection[J].IEEE Communications Letters,2008,12(4):235-238.

[13]Nash J.The bargaining problem[J].Econometrica,1950,28 (2):155-162.

[14]Kennedy J,Eberhart R.Particle swarm optimization[C]∥Proc.of the IEEE International Conference on Neural Networks, 1995:1942-1948.

[15]Zhang Z,Shi J,Chen H,et al.A cooperation strategy based on Nash bargaining solution in cooperative relay networks[J]. IEEE Trans.on Vehicular Technology,2008,57(4):2570- 2577.

Cooperation algorithm based on game theory and particle swarm optimization for Ad-hoc networks

ZHANG Chuang,ZHANG Jia-yan,ZHAO Hong-lin
(Communication Research Center,Harbin Institute of Technology,Harbin 150080,China)

To stimulate the selfish nodes of Ad-hoc networks to participate in cooperation,a cooperation algorithm based on Nash Bargaining of game theory and particle swarm optimization(NGPSO)is proposed.In the first stage of the proposed algorithm,the relay node is paid by the source node for forwarding source nodes’data,then cooperation between the source node and the relay node can be reached.We model the optimal bid of the source node as Nash bargain,and Nash equilibrium of the optimal bid which is Pareto efficient is given. Consequently,the optimal bid can guarantee that the source node and the relay node obtain optimal revenue.In the second stage of the proposed algorithm,after obtaining the optimal bid of the source node,the relay node determines optimal transmit power through particle swarm optimization to maximize its own cooperative gain. Simulation results show that,compared to random price incentive mechanisms,the NGPSO algorithm can make the source node and the relay node obtain optimal revenue.Meanwhile,the proposed algorithm improves the cooperative gain of the relay node and the energy efficiency of the source node compared to the algorithm where the relay node uses constant transmit power.Furthermore,when the relay node appropriately sets its search space, the total energy efficiency of the whole system can be ensured.

cooperation algorithm;game theory;particle swarm optimization;energy efficiency

TP 393.01

A

10.3969/j.issn.1001-506X.2015.03.30

張 闖(1986-),男,博士研究生,主要研究方向?yàn)閰f(xié)作通信、鏈路自適應(yīng)傳輸。

E-mail:cangshanerhai@126.com

張佳巖(1974-),男,講師,博士,主要研究方向?yàn)榭垢蓴_通信技術(shù)、協(xié)作通信。

E-mail:JYzhang@hit.edu.cn

趙洪林(1969-),男,教授,博士研究生導(dǎo)師,主要研究方向?yàn)閿U(kuò)頻通信、軟件無(wú)線電技術(shù)和寬帶無(wú)線通信網(wǎng)絡(luò)研究。

E-mail:hlzhao@hit.edu.cn

網(wǎng)址:www.sys-ele.com

1001-506X(2015)03-0664-07

2013 12 06;

2014 07 08;網(wǎng)絡(luò)優(yōu)先出版日期:2014 10 17。

網(wǎng)絡(luò)優(yōu)先出版地址:http:∥w ww.cnki.net/kcms/detail/11.2422.TN.20141017.1606.004.html

國(guó)家自然科學(xué)基金(61071104)資助課題