基于序數(shù)勢(shì)博弈的WSN拓?fù)淇刂扑惴?/h1>

2016-08-31 09:06:24馬林華黃紹城孫康寧空軍工程大學(xué)航空航天工程學(xué)院西安70038中國人民解放軍95876部隊(duì)

計(jì)算機(jī)與生活訂閱 2016年8期 收藏

關(guān)鍵詞：納什均衡無線傳感器網(wǎng)絡(luò)

蔡　釗，馬林華，黃紹城，孫康寧，田　雨.空軍工程大學(xué) 航空航天工程學(xué)院，西安 70038.中國人民解放軍95876部隊(duì)

基于序數(shù)勢(shì)博弈的WSN拓?fù)淇刂扑惴?/p>

蔡釗1+，馬林華1，黃紹城1，孫康寧1，田雨2
1.空軍工程大學(xué) 航空航天工程學(xué)院，西安 710038
2.中國人民解放軍95876部隊(duì)

CAI Zhao,MA Linhua,HUANG Shaocheng,et al.Ordinal potential game based topology control algorithm for WSN.Journal of Frontiers of Computer Science and Technology,2016,10(8)：1112-1121.

摘要：由于傳感器節(jié)點(diǎn)能量有限且不易更換，故能量效率一直是制約傳感網(wǎng)生存周期的重要因素。構(gòu)建一種基于勢(shì)博弈的拓?fù)淇刂疲╬otential game topology control，PGTC）模型，將最短潛在壽命和節(jié)點(diǎn)度取值分別作為首要、次要效用函數(shù)。節(jié)點(diǎn)調(diào)整自身的發(fā)射功率，降低反向鏈路集中潛在壽命最短節(jié)點(diǎn)的發(fā)射功率，延長其潛在壽命，同時(shí)控制節(jié)點(diǎn)度取值以減小鏈路平均跳數(shù)和總能耗。理論分析可知，PGTC模型屬于序數(shù)勢(shì)博弈，存在納什均衡，且納什均衡點(diǎn)即為帕累托最優(yōu)解。仿真表明，PGTC模型相較于其他基于博弈論的拓?fù)淇刂扑惴?，網(wǎng)絡(luò)總能耗更低，并且能量均衡性更強(qiáng)。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)（WSN）；拓?fù)淇刂?；?shì)博弈；納什均衡

1　引言

傳感器網(wǎng)絡(luò)由于成本低，便于部署的特點(diǎn)，在軍事探測(cè)、環(huán)境監(jiān)測(cè)、災(zāi)難預(yù)警領(lǐng)域被廣泛地使用。但由于傳感器一般采用電池供電，且通常布設(shè)在嚴(yán)苛、不易更換的環(huán)境中，故能量效率問題一直以來都是制約傳感網(wǎng)生存周期的重要因素[1-2]。同時(shí)，在節(jié)點(diǎn)數(shù)量多，分布密集的傳感網(wǎng)中，處于主干路線上的節(jié)點(diǎn)負(fù)載較重，存在過早死亡的風(fēng)險(xiǎn)，使得網(wǎng)絡(luò)的連通性和健壯性急劇下降。故能耗均衡問題同樣也應(yīng)作為延長網(wǎng)絡(luò)生存周期的重要因素被加以考慮。拓?fù)淇刂扑惴ㄖ荚诒ＷC網(wǎng)絡(luò)連通性和健壯性的情況下，提升能量效率和能量均衡度。網(wǎng)絡(luò)中各節(jié)點(diǎn)用優(yōu)化的傳輸功率代替最大傳輸功率，構(gòu)建能效更高的拓?fù)浣Y(jié)構(gòu)，極大地提升了網(wǎng)絡(luò)性能。但是傳統(tǒng)Ad-hoc網(wǎng)絡(luò)的拓?fù)淇刂萍夹g(shù)不能直接應(yīng)用在無線傳感網(wǎng)中，需要研究適合的高效拓?fù)淇刂扑惴ā?/p>

勢(shì)博弈作為一種特殊的策略博弈，由于節(jié)點(diǎn)效用函數(shù)與全局勢(shì)函數(shù)具有同樣的變化趨勢(shì)，故博弈會(huì)不斷朝著最優(yōu)的目標(biāo)函數(shù)前進(jìn)，經(jīng)過有限次的迭代決策就能找到最優(yōu)解。勢(shì)博弈因其良好屬性，作為分布式動(dòng)態(tài)優(yōu)化理論在網(wǎng)絡(luò)擁塞控制、功率控制以及資源調(diào)度等方面得到了大量應(yīng)用[3-6]。文獻(xiàn)[7]構(gòu)建了基于博弈論的自適應(yīng)協(xié)作拓?fù)淇刂疲╟ooperative topology control with adaptation，CTCA）算法，將提升反向鏈路集中節(jié)點(diǎn)最短壽命和自身壽命分別作為首要、次要效用函數(shù)。文獻(xiàn)[8]針對(duì)能量采集傳感網(wǎng)提出了一種綜合考慮節(jié)點(diǎn)的能量狀況和能量采集能力的拓?fù)淇刂扑惴?，把最大化網(wǎng)絡(luò)生存周期的問題轉(zhuǎn)化為序數(shù)勢(shì)博弈過程。

此外，通過優(yōu)化節(jié)點(diǎn)度取值減小總能耗也成為延長網(wǎng)絡(luò)生存周期的重要方向，代表算法有BCG-TC[9]（Borel Cayley graph topology control）、LMPT[10]（local minimum spanning tree）、EETA[11]（energy efficiency topology algorithm）等。文獻(xiàn)[9]針對(duì)密集傳感網(wǎng)提出了一種基于節(jié)點(diǎn)度限制的功率控制策略，并運(yùn)用Borel Cayley圖構(gòu)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，得到了平均鏈路長度更短，總能耗更低的拓?fù)浣Y(jié)構(gòu)。文獻(xiàn)[11]從構(gòu)建網(wǎng)絡(luò)能量優(yōu)化模型入手，結(jié)合單跳路徑能耗和鏈路平均跳數(shù)的信息，分析滿足網(wǎng)絡(luò)通信能耗最小情況的節(jié)點(diǎn)度取值規(guī)律，得出最優(yōu)節(jié)點(diǎn)度取值分布。

本文構(gòu)建基于勢(shì)博弈的拓?fù)淇刂疲╬otential game topology control，PGTC）算法，定義網(wǎng)絡(luò)中的最短潛在壽命為首要效用函數(shù)，節(jié)點(diǎn)度取值是否滿足最優(yōu)節(jié)點(diǎn)度區(qū)間為次要效用函數(shù)。PGTC算法通過提高最短潛在壽命均衡網(wǎng)絡(luò)能耗，通過優(yōu)化節(jié)點(diǎn)度取值降低鏈路總能耗，極大地提升了網(wǎng)絡(luò)的整體性能。此外，本文的綜合效用函數(shù)摒除了傳統(tǒng)的加權(quán)形式，引入次要因素考慮因子，確保節(jié)點(diǎn)僅在首要效用函數(shù)取最大值時(shí)考慮次要因素，進(jìn)一步延長了網(wǎng)絡(luò)的生存周期。

2　序數(shù)勢(shì)博弈模型

2.1概念定義

定義1（節(jié)點(diǎn)集和鏈路集）無線傳感器網(wǎng)絡(luò)可以用有向圖來表示G=，其中N代表節(jié)點(diǎn)集，E表示鏈路集。鏈路集中元素的取值表示節(jié)點(diǎn)間連通性，“1”表示連通，“0”表示不連通。

定義2（反向鏈路集）定義以當(dāng)前發(fā)射功率能覆蓋節(jié)點(diǎn)i的集合為i的反向鏈路集，記為Oi或Oi(t)。Oi(t)={|j i∈n(j)}，其中n(j)表示 j的鄰居節(jié)點(diǎn)。此外，定義節(jié)點(diǎn)i及其反向鏈路集的并集為O?i=Oi?i。

定義3（可達(dá)鄰居集）節(jié)點(diǎn)i在t時(shí)刻發(fā)射功率可以到達(dá)的節(jié)點(diǎn)集被稱作可達(dá)鄰居集，簡稱鄰居集，記為Ri或Ri(t)。定義節(jié)點(diǎn)i及其可達(dá)鄰居集的并集

定義4（連通性）若節(jié)點(diǎn) j既屬于i的反向鏈路集，又屬于i的鄰居集，則i、j之間的鏈路是連通的。

定義5（映射）P代表網(wǎng)絡(luò)中各節(jié)點(diǎn)到其發(fā)送功率的映射，即{N1→p1,N2→p2,…}。P-i為整個(gè)網(wǎng)絡(luò)除去節(jié)點(diǎn)i的功率映射，Pi為R?i集內(nèi)節(jié)點(diǎn)的功率映射。

定義6（可用功率集）假設(shè)節(jié)點(diǎn)i最多有k個(gè)鄰居，到達(dá)它們的最小功率由小到大依次為 pi[1],pi[2],…, pi[k]，則定義可用功率集為Ai={pi[1],pi[2],…,pi[k]}。需要注意的是，節(jié)點(diǎn)發(fā)射功率 pi(t)或潛在功率 pi′(t)的取值只能在可用功率集Ai中選取。

定義7（估計(jì)壽命）假設(shè)節(jié)點(diǎn)i的剩余能量為Wi(t)，發(fā)射功率為 pi(t)，定義t時(shí)刻節(jié)點(diǎn)i的估計(jì)壽命為Li(pi(t),t)=Wi(t)/pi(t)。

定義8（潛在發(fā)射功率和潛在壽命）當(dāng)節(jié)點(diǎn)i及其鄰居集滿足映射Pi時(shí)，在不影響網(wǎng)絡(luò)連通性的條件下，將i的最小可用發(fā)射功率定義為潛在發(fā)射功率pi′(t)。節(jié)點(diǎn)剩余能量與潛在發(fā)射功率的比值為潛在壽命，即Li′(pi(t),t)=Wi(t)/pi′(t)。定義m(i,t)或m(i)為Oi集內(nèi)最短潛在壽命對(duì)應(yīng)的節(jié)點(diǎn)，即m(t)=argminj∈Oi(t){Lj′(Pj,t)}。

2.2效用函數(shù)

對(duì)于網(wǎng)絡(luò)中的任意節(jié)點(diǎn)i而言，通過改變發(fā)射功率可在Oi集內(nèi)其他節(jié)點(diǎn)策略不變的情況下，改變自身的對(duì)稱鄰居個(gè)數(shù)。當(dāng)節(jié)點(diǎn)增加發(fā)射功率時(shí)，其反向鏈路集中的對(duì)稱鄰居個(gè)數(shù)也相應(yīng)增加。新增的部分對(duì)稱鄰居節(jié)點(diǎn)可在保證自身與全網(wǎng)連通性的情況下（至少有一個(gè)對(duì)稱鄰居節(jié)點(diǎn)），適當(dāng)減小發(fā)射功率，延長潛在壽命。如圖1中，節(jié)點(diǎn)j增加自身發(fā)射功率，使i成為其對(duì)稱鄰居。對(duì)i而言，原先距離其最近的對(duì)稱鄰居為k，而現(xiàn)在最近的對(duì)稱鄰居變?yōu)閖。故i在保證其與全網(wǎng)連通性的前提下，可減小自身發(fā)射功率。

Fig.1　Schematic diagram of adjusting transmission power圖1　發(fā)射功率調(diào)整示意圖

節(jié)點(diǎn)的估計(jì)壽命僅由當(dāng)前功率決定，但潛在壽命會(huì)受到鄰居功率策略的影響。由于從當(dāng)前功率向潛在功率轉(zhuǎn)變的過程中，節(jié)點(diǎn)鄰居集無變化，故當(dāng)前功率存在向潛在功率變化的趨勢(shì)，從而潛在功率將直接影響當(dāng)前功率。由定義7、定義8可知，估計(jì)壽命和潛在壽命的表達(dá)式分子相同，僅分母不同，且當(dāng)前功率與潛在功率存在直接聯(lián)系，故估計(jì)壽命與潛在壽命之間也存在直接關(guān)系。網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)可以通過改變反向鏈路集內(nèi)節(jié)點(diǎn)潛在壽命的方式改變其估計(jì)壽命。為了提高網(wǎng)絡(luò)內(nèi)最短估計(jì)壽命，將首要效用函數(shù)定義為節(jié)點(diǎn)自身及反向鏈路集內(nèi)的最短潛在壽命，見下式：

式中，Lm(i)′(P,t)為節(jié)點(diǎn)i反向鏈路內(nèi)的最短潛在壽命；Li′(pi,t)為節(jié)點(diǎn)i的潛在壽命。

需要注意的是，節(jié)點(diǎn)的功率策略（或潛在壽命）只能描述單跳的能耗，而不能代表網(wǎng)絡(luò)總能耗，因?yàn)榭偰芎氖瞧骄l(fā)射功率與鏈路平均跳數(shù)的乘積。而平均跳數(shù)很大程度上取決于節(jié)點(diǎn)度的大小，節(jié)點(diǎn)度過低會(huì)造成平均跳數(shù)的顯著增加。例如圖2中，當(dāng)s的節(jié)點(diǎn)度為1時(shí)，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)需要3跳，如路徑1所示；而當(dāng)s的節(jié)點(diǎn)度為2時(shí)，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)需要1跳，如路徑2所示。明顯地，路徑1的能耗要大于路徑2。

同時(shí)節(jié)點(diǎn)度數(shù)也不能過高，主要有以下原因：

（1）加重高節(jié)點(diǎn)度節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)負(fù)擔(dān)，使其易由于能量消耗過快而過早死亡。

（2）增加通信半徑，由于發(fā)射功率與通信半徑的α次方成正比（2≤α≤4），易造成發(fā)射功率顯著增大。

（3）造成傳輸信號(hào)之間的沖突和干擾，增加數(shù)據(jù)包重傳次數(shù)。

Fig.2　Forwarding paths at different node degrees圖2　不同節(jié)點(diǎn)度情況下的通信路徑

為了提高拓?fù)浣Y(jié)構(gòu)的能量效率，提高信道復(fù)用率，降低干擾，節(jié)點(diǎn)度應(yīng)該處于特定區(qū)間[kmin,kmax]。文獻(xiàn)[9-10]通過仿真得出，當(dāng)最大節(jié)點(diǎn)度為4時(shí)，網(wǎng)絡(luò)的鏈路總能耗最低。本文結(jié)合能量均衡性的問題，適當(dāng)增加高電量節(jié)點(diǎn)的能量消耗，將最大節(jié)點(diǎn)度設(shè)為5。最小節(jié)點(diǎn)度在考慮網(wǎng)絡(luò)健壯性和能量均衡博弈效果的情況下，參照文獻(xiàn)[12]設(shè)置為2。

當(dāng)節(jié)點(diǎn)既要提高O?i集內(nèi)最短潛在壽命，又要改變節(jié)點(diǎn)度數(shù)時(shí)，即首要因素與次要因素相互沖突時(shí)，為確保節(jié)點(diǎn)優(yōu)先考慮首要因素，本文摒棄傳統(tǒng)的加權(quán)形式，轉(zhuǎn)而采用次要因素考慮因子li(pi,t)。在引入它之前，先定義節(jié)點(diǎn)i的優(yōu)先功率集Fi。

遍歷i所有功率取值，將O?i集內(nèi)最短潛在壽命所能取得的最大值定義為σ(i,t)，即：

定義使得Oi集內(nèi)最短潛在壽命取值為σ(i,t)的所有功率取值均屬于節(jié)點(diǎn)i的優(yōu)先功率集。

當(dāng)節(jié)點(diǎn)i的功率屬于其優(yōu)先功率集時(shí)，次要因素考慮因子li(pi,t)取1，否則取0。

結(jié)合i的次要因素考慮因子和首要、次要效用函數(shù)表達(dá)式，可得綜合效用函數(shù)：

式中，C(P,t)是二進(jìn)制連通函數(shù)，當(dāng)節(jié)點(diǎn)i至少有一個(gè)對(duì)稱鄰居時(shí)此項(xiàng)取1，否則取0。根據(jù)綜合效用函數(shù)表達(dá)式可知，只有當(dāng)節(jié)點(diǎn)功率處于其優(yōu)先功率集內(nèi)，即li(pi,t)=1時(shí)，才會(huì)考慮次要因素，否則只考慮首要因素。

2.3序數(shù)勢(shì)博弈

定義策略博弈Γ=[N,A,{ui(?)}i∈N]，它包含以下3部分：

（1）節(jié)點(diǎn)域N，i∈N={1,2,…,n}，其中n代表網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)。

（3）效用函數(shù){ui(?)}i∈N，效用函數(shù)的取值由兩部分組成，分別與節(jié)點(diǎn)O?i集內(nèi)的最短潛在壽命和當(dāng)前節(jié)點(diǎn)度數(shù)有關(guān)，見式（6）。節(jié)點(diǎn)將依據(jù)效用函數(shù)取值的大小選取最優(yōu)的功率等級(jí)。

此外，將第一個(gè)節(jié)點(diǎn)死亡的時(shí)間定義為網(wǎng)絡(luò)生存周期，利用最短的節(jié)點(diǎn)潛在壽命對(duì)其進(jìn)行近似，并將最短潛在壽命定義為博弈的勢(shì)函數(shù)，見下式：

3　理論證明

定理1博弈Γ=[N,P,{ui(?)}i∈N]為序數(shù)勢(shì)博弈，且V(P,t)為序數(shù)勢(shì)函數(shù)。

證明 假設(shè)t時(shí)刻的功率映射情況為P,t+1時(shí)刻的功率映射情況為P′。由于映射情況本身就能代表時(shí)間順序，故為簡化表達(dá)，省略時(shí)刻t和t+1。將Lm(i)′(P,t)寫為Lm(i)′(P)，Li′(pi,t)寫為Li′(pi)，li(pi,t)寫為li(pi)，C(P,t)寫為C(P)。

根據(jù)t和t+1時(shí)刻功率映射所對(duì)應(yīng)的網(wǎng)絡(luò)連通性變化情況，可分為4種情況：（1）C(P)=C(P′)=0；（2）C(P)=1?C(P′)=0；（3）C(P)=0?C(P′)=1；（4）C(P)= C(P′)=1。顯然前3種情況滿足節(jié)點(diǎn)效用函數(shù)與序數(shù)勢(shì)函數(shù)取值同號(hào)的條件，故僅討論第4種情況。這種情況下，從t時(shí)刻到t+1時(shí)刻節(jié)點(diǎn)效用函數(shù)以及總體的勢(shì)函數(shù)變化值分別為：

由于i只能改變MLi(P)的取值，故可以認(rèn)為ML-i(P)=ML-i(P′)。根據(jù)t和t+1時(shí)刻全網(wǎng)最短壽命的變化情況，可分為4種情況：

Case(a)min{MLi(P′),ML-i(P′)}=MLi(P′)且

min{MLi(P),ML-i(P)}=MLi(P)

首先考慮Case(a)的情形，并根據(jù)次要因素考慮因子的取值情況，將其進(jìn)一步劃分為4種子情況：

Case(a-i)li(pi′)=li(pi)=1

節(jié)點(diǎn)i的功率策略一直處于其優(yōu)先功率集內(nèi)，故O?i集內(nèi)的最短潛在壽命可視為不變，即有MLi(P′)= MLi(P)，故勢(shì)函數(shù)ΔV(P)=0。

節(jié)點(diǎn)保證當(dāng)前功率處于優(yōu)先功率集的前提下，會(huì)調(diào)整自身節(jié)點(diǎn)度，提升效用函數(shù)取值：Δui(pi)= D(ki′)-D(ki)≥0，由于勢(shì)函數(shù)取值為0，故節(jié)點(diǎn)效用函數(shù)與勢(shì)函數(shù)同號(hào)。

由i的次要因素考慮因子取值可知，ai?Fi且ai′∈Fi，故對(duì)應(yīng)功率映射P和P′的最短潛在壽命滿足MLi(P′)>MLi(P)。

因?yàn)閜i∈Fi且pi′?Fi，故節(jié)點(diǎn)i的功率映射關(guān)系由P變?yōu)镻′后，其Oi集內(nèi)的最小潛在壽命減小，即MLi(P′)

由于節(jié)點(diǎn)只能改變自身及反向鏈路集內(nèi)的潛在壽命，故O?i集外的潛在壽命不受i功率策略的影響，可將其視為不變，故有ML-i(P)=ML-i(P′)。

由min{MLi(P′),ML-i(P′)}=MLi(P′)且min{MLi(P), ML-i(P)}=ML-i(P)可知，節(jié)點(diǎn)i調(diào)整功率后其O?i集的最短潛在壽命變短，故ai′?Fi，t+1時(shí)刻的次要因素考慮因子取0，即li(pi′ )=0。

同理Case(c)滿足Δui(pi)≥0?ΔV(P)≥0，即效用函數(shù)與勢(shì)函數(shù)同號(hào)。

Case(d)min{MLi(P′),ML-i(P′)}=ML-i(P′)且min{MLi(P),ML-i(P)}=ML-i(P)

由于全網(wǎng)最短潛在壽命滿足上述條件，故從t到t+1時(shí)刻網(wǎng)絡(luò)的勢(shì)函數(shù)變化值為ΔV(P)=ML-i(P)-ML-i(P′)=0。由于勢(shì)函數(shù)取值不變，故不論節(jié)點(diǎn)效用函數(shù)取值如何變化，效用函數(shù)與勢(shì)函數(shù)同號(hào)。

通過上面的分析可知，函數(shù)ΔV(P)與節(jié)點(diǎn)效用函數(shù)變化值Δui(pi)始終同號(hào)，故Γ=[N,P,{ui(?)}i∈N]為序數(shù)勢(shì)博弈，而ΔV(P)是Δui(pi)的序數(shù)勢(shì)函數(shù)。

定理2有限序數(shù)勢(shì)博弈具有有限改進(jìn)路徑特性。

證明 由于網(wǎng)絡(luò)中節(jié)點(diǎn)不具有運(yùn)動(dòng)性，每個(gè)節(jié)點(diǎn)相對(duì)其各鄰居的距離恒定不變，故對(duì)應(yīng)的發(fā)射功率也恒定不變。由于每個(gè)節(jié)點(diǎn)的鄰居個(gè)數(shù)是有限的，故其可選擇的功率等級(jí)也是有限的，從而本文的序數(shù)勢(shì)博弈為有限序數(shù)勢(shì)博弈。

假設(shè){P0,P1,P2,…}是一個(gè)改進(jìn)路徑。對(duì)于所有的k>0，有ui(Pk)>ui(Pk-1)；同時(shí)，對(duì)于所有的k>0，也有V(Pk)>V(Pk-1)，因此{(lán)V(P0),V(P1),V(P2),…}是一個(gè)嚴(yán)格遞增序列。由于S是一個(gè)有限集合，序列{P0,P1,P2,…}也一定是有限的，故本文的PGTC模型在有限次數(shù)內(nèi)就能達(dá)到納什均衡。

定理3 PGTC模型的納什均衡即帕累托最優(yōu)。

證明 在勢(shì)博弈中，納什均衡點(diǎn)對(duì)應(yīng)的就是勢(shì)函數(shù)最大值點(diǎn)。本文將網(wǎng)絡(luò)內(nèi)最短潛在壽命作為序數(shù)勢(shì)函數(shù)，并定義網(wǎng)絡(luò)生存周期為第一個(gè)節(jié)點(diǎn)死亡的時(shí)間，故序數(shù)勢(shì)函數(shù)取最大值時(shí)即為網(wǎng)絡(luò)生存周期最大的情況。因此納什均衡點(diǎn)就是優(yōu)化問題的最優(yōu)解，即帕累托最優(yōu)解。

4　算法流程

4.1鄰居信息探測(cè)階段

（1）節(jié)點(diǎn)i用最大功率pmax廣播Hello消息（Hello消息包括自身位置信息）；

（2）確定最大可達(dá)鄰居集Ri及集合中節(jié)點(diǎn)數(shù)k；

（3）計(jì)算自身到最大鄰居集中所有節(jié)點(diǎn)的功率，構(gòu)成策略集Ai；

（4）將到達(dá)各節(jié)點(diǎn)的功率從小到大進(jìn)行排序，即pi[1]

（5）用pi[k]的功率廣播策略集Ai；

（6）接收自身最大鄰居集中節(jié)點(diǎn)發(fā)送的信息；

（7）運(yùn)行DLSS[12]（directedlocalspanningsubgraph）算法確定發(fā)送功率pi；

（8）用pi[k]的功率廣播自身的發(fā)射功率pi；

（9）接收最大鄰居集中各節(jié)點(diǎn)的發(fā)射功率pj；

（10）構(gòu)建反向鏈路集Oi；

（11）判斷能否降低發(fā)射功率，并將新策略記為pi′；

（12）節(jié)點(diǎn)用pi廣播自身的策略pi′；

（13）接收Oi集內(nèi)各節(jié)點(diǎn)策略pj′。

4.2節(jié)點(diǎn)功率調(diào)整流程

節(jié)點(diǎn)增大自身發(fā)射功率需同時(shí)滿足4個(gè)條件：

（1）節(jié)點(diǎn)O?i集內(nèi)的最短潛在壽命在Oi集內(nèi)；

（2）m(i)現(xiàn)有功率不是其可用功率集內(nèi)的最低功率；

（3）i在Ai內(nèi)調(diào)整功率能增加m(i)的潛在壽命；

（4）i提高功率后其壽命依然高于m(i)潛在壽命。

當(dāng)這4個(gè)條件均被滿足時(shí)，節(jié)點(diǎn)將增大自身功率，并用新功率更新優(yōu)先功率集。在保證Li′(pi′)≥Lm(i)′(P)的情況下，i將調(diào)整發(fā)射功率，使自身節(jié)點(diǎn)度取值滿足本文規(guī)定的區(qū)間。i將用新的功率廣播鄰居請(qǐng)求信息，并等待鄰居節(jié)點(diǎn)的應(yīng)答信息，對(duì)鄰居集Ri進(jìn)行更新。總體流程見圖3。

當(dāng)節(jié)點(diǎn)接收到鄰居調(diào)整功率的信息后，判斷自身能否減小發(fā)射功率。首先找到當(dāng)前功率所對(duì)應(yīng)的最遠(yuǎn)節(jié)點(diǎn)r（節(jié)點(diǎn)轉(zhuǎn)發(fā)的下一跳節(jié)點(diǎn)），判斷Ri內(nèi)是否有距離更近且可以到達(dá)節(jié)點(diǎn)r的鄰居。若有則調(diào)整潛在發(fā)射功率，反之維持當(dāng)前功率。自適應(yīng)減小功率等級(jí)的具體流程見圖4。

4.3拓?fù)渚S護(hù)階段

（1）節(jié)點(diǎn)i收到j(luò)的信息后，提取j的功率信息pj；

（2）若 j∈Oi，判斷pj>p(i,j)是否成立，若成立則更新Oi中j的功率信息，反之將j從Oi中移除；

（3）若j?Oi，將j加入到Oi中并寫入其功率信息；

（4）若 j=m(i)，i判斷能否通過提高自身發(fā)射功率延長Lm(i)′(P)，流程見4.2節(jié)；

（5）若可以則提高自身發(fā)射功率并向鄰居廣播策略改變信息；

（6）若j∈Ri，更新Ri集內(nèi)j的功率信息；

（7）更新Ri集后節(jié)點(diǎn)判斷能否降低自身發(fā)射功率，流程見4.2節(jié)；

（8）若可以則降低自身發(fā)射功率并向鄰居廣播策略改變信息。

Fig.3　Schematic diagram of increasing transmission power圖3　提高發(fā)射功率示意圖

5　仿真分析

為衡量本文算法的效率，選取兩種基于博弈論的拓?fù)淇刂扑惴ㄟM(jìn)行對(duì)比。能量福利拓?fù)淇刂疲╡nergy welfare topology control，EWTC）模型[13]利用Atkinson不等式構(gòu)建能量福利函數(shù)，提高了能量的平均值和均衡度。虛擬博弈能量均衡算法（virtual gamebased energy balanced topology control，VGEB）[14]構(gòu)建了虛擬博弈，節(jié)點(diǎn)通過選擇剩余能量較高的節(jié)點(diǎn)作為鄰居，減小低電量節(jié)點(diǎn)的負(fù)載，延長網(wǎng)絡(luò)的生存周期。本文將PGTC算法與EWTC、VGEB算法在節(jié)點(diǎn)度、發(fā)射功率、鏈路平均跳數(shù)、平均剩余能量、最低剩余能量5方面進(jìn)行對(duì)比。

本文選用NS2和Matlab作為仿真平臺(tái)，區(qū)域大小設(shè)為500 m×500 m，節(jié)點(diǎn)隨機(jī)布設(shè)且不具有移動(dòng)性。節(jié)點(diǎn)初始能量均為50 J，最大通信半徑為150 m，節(jié)點(diǎn)間的最小通信功率利用下式確定：p(i,j)=，其中系統(tǒng)損耗L取1，發(fā)射天線增益Gt為1，接收天線增益Gr為7×10-10w，波長λ為0.122 4 m。

由圖5～圖7可知，考慮節(jié)點(diǎn)度取值因素的PGTC模型，不管是節(jié)點(diǎn)度還是平均發(fā)射功率均高于EWTC 和VGEB算法。不過需要注意的是，其鏈路平均跳數(shù)是最低的。由于網(wǎng)絡(luò)總能耗是由鏈路平均跳數(shù)和平均發(fā)射功率共同決定的，故為進(jìn)一步判斷各算法的性能，在不同節(jié)點(diǎn)數(shù)量的場景下，仿真了3種算法在網(wǎng)絡(luò)運(yùn)行時(shí)間為150 s時(shí)的平均剩余能量和最小剩余能量，分別見圖8和圖9。

Fig.4　Schematic diagram of decreasing transmission power圖4　減小發(fā)射功率示意圖

Fig.5　Comparison of average transmission power at different number of nodes圖5　平均發(fā)射功率隨節(jié)點(diǎn)數(shù)量的變化情況

Fig.6　Comparison of average node degree at different number of nodes圖6　平均節(jié)點(diǎn)度隨節(jié)點(diǎn)數(shù)量的變化情況

Fig.7　Comparison of link average hop at different number of nodes圖7　鏈路平均跳數(shù)隨節(jié)點(diǎn)數(shù)量的變化情況

根據(jù)圖8和圖9可知，VGEB算法過度關(guān)注能量均衡而忽視了能量效率，客觀上增大了節(jié)點(diǎn)平均發(fā)射功率和鏈路總能耗，故不管是節(jié)點(diǎn)的平均剩余能量還是最小剩余能量均處于較低的水平。EWTC算法通過構(gòu)建福利函數(shù)，綜合考慮了平均剩余能量和均衡度，但是網(wǎng)絡(luò)性能與不等式指標(biāo)的選取休戚相關(guān)，故在不同的網(wǎng)絡(luò)分布中算法的性能也有較大的差異，總體性能并不很盡如人意。反觀PGTC算法，勢(shì)博弈僅在首要效用函數(shù)取最大值時(shí)考慮次要因素，網(wǎng)絡(luò)中節(jié)點(diǎn)壽命的均衡度要高于另兩種算法。并且通過對(duì)節(jié)點(diǎn)度的控制降低了鏈路總能耗，進(jìn)一步提高了平均剩余能量。故PGTC算法相較于另兩種算法，具有更高的能量效率和更強(qiáng)的壽命均衡度。

Fig.9　Comparison of minimum energy at different number of nodes圖9　不同節(jié)點(diǎn)數(shù)量下的最小剩余能量的比較

6　結(jié)束語

本文針對(duì)無線傳感器網(wǎng)絡(luò)，構(gòu)建了一種基于勢(shì)博弈的拓?fù)淇刂扑惴ǎ≒GTC）。在算法中，節(jié)點(diǎn)綜合考慮了反向鏈路集中的最短潛在壽命和當(dāng)前節(jié)點(diǎn)度數(shù)，均衡能耗的同時(shí)，降低了鏈路總能耗。并通過勢(shì)博弈理論，證明了PGTC模型存在納什均衡，且納什均衡趨近于帕累托最優(yōu)。仿真結(jié)果表明，PGTC模型相較于其他拓?fù)淇刂扑惴苄Ц?，壽命均衡性和網(wǎng)絡(luò)健壯性更強(qiáng)。

References:

[1]Alskafi T,Zapata M G,Bellata B.Game theory for energy efficiency in wireless sensor networks:latest trends[J].Journal of Network and ComputerApplications,2015,54:33-61.

[2]Lee C Y,Shiu L C,Lin F T,et al.Distributed topology control algorithm on broadcasting in wireless sensor networks[J]. Journal of Network and Computer Applications,2013,36 (4):1186-1195.

[3]Han Zhu,Niyato D,Saad W,et al.Game theory in wireless and communication networks:theory,models,and applications[M].Cambridge,UK:Cambridge University Press, 2012.

[4]Neves T F,Bordim J L.Topology control in cooperative Ad hoc wireless networks[J].Electronic Notes in Theoretical Computer Science,2014,302:29-51.

[5]Nahir A,Orda A,Freund A.Topology design and control:a game-theoretic perspective[C]//Proceedings of the 2009 International Conference on Computer Communications,Rio de janeiro,Brazil,Apr 19-25,2009.Piscataway,USA:IEEE, 2009:1620-1628.

[6]Sengupta S,Chatterjee M,Kwiat K A.A game theoretic framework for power control in wireless sensor networks[J]. IEEE Transactions on Computers,2010,59(2):231-242.

[7]Chu Xiaoyu,Sethu H.Cooperative topology control with adaptation for improved lifetime in wireless sensor networks[J].Ad Hoc Networks,2015,30:99-114.

[8]Tan Qian,An Wei,Han Yanni,et al.Energy harvesting aware topology control with power adaptation in wireless sensor networks[J].Ad Hoc Networks,2015,27:44-56.

[9]Yu J,Noel E,Tang K W.Degree constrained topology control for very dense wireless sensor networks[C]//Proceedings of the 2010 IEEE Global Telecommunications Conference,Miami,USA,Dec 6-10,2010.Piscataway,USA:IEEE, 2010:1-6.

[10]Liu Haoran,Zhai Ming,Hao Xiaochen,et al.Degree-optimized LMPT topology control algorithm of wireless sensor networks[C]//Proceedings of the 2008 International Conference on Intelligent System and Knowledge Engineering, Xiamen,China,Nov 17-19,2008.Piscataway,USA:IEEE, 2008:55-60.

[11]Liu Haoran,Han Tao,Li Yaqian,et al.Scale-free fault-tolerant topology control algorithm in wireless sensor network with optimization of path energy consumption[J].Journal on Communications,2014,35(6):64-72.

[12]Chen Xianming,Cai Yueming,Zhang Yu,et al.Topology control algorithm based on game theory in wireless sensor networkss[J].Journal of PLA University of Science and Technology,2011,12(5):414-418.

[13]Abbasi M,Fisal N.Noncooperative game-based energy welfare topology control for wireless sensor networks[J].IEEESensor Journal,2015,15(4):2344-2354.

[14]Hao Xiaochen,Zhang Yaxiao,Jia Nan,et al.Virtual gamebased energy balanced topology control algorithm for wireless sensor networks[J].Wireless Personal Communications,2013,69(4):1289-1308.

附中文參考文獻(xiàn)：

[11]劉浩然,韓濤,李雅倩,等.具有路徑能耗優(yōu)化特性的WSN無標(biāo)度容錯(cuò)拓?fù)淇刂扑惴╗J].通信學(xué)報(bào),2014,35(6):64-72.

[12]陳賢明,蔡躍明,張余,等.WSN中一種基于博弈論的拓?fù)淇刂扑惴╗J].解放軍理工大學(xué)學(xué)報(bào),2011,12(5):414-418.

CAI Zhao was born in 1990.He is an M.S candidate at College of Aeronautics and Astronautics Engineering,Air Force Engineering University.His research interests include ad hoc networks and game theory,etc.

蔡釗（1990—），男，北京人，空軍工程大學(xué)航空航天工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閍d hoc網(wǎng)絡(luò)，博弈論等。

MA Linhua was born in 1965.He received the Ph.D.degree from Xidian University in 1993.Now he is a professor and Ph.D.supervisor at College of Aeronautics and Astronautics Engineering,Air Force Engineering University. His research interests include ad hoc networks and coding theory,etc.

馬林華（1965—），男，陜西漢中人，1993年于西安電子科技大學(xué)獲得博士學(xué)位，現(xiàn)為空軍工程大學(xué)航空航天工程學(xué)院教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)閍d hoc網(wǎng)絡(luò)，編碼理論等。

HUANG Shaocheng was born in 1990.He is an M.S candidate at College of Aeronautics and Astronautics Engineering,Air Force Engineering University.His research interests include ad hoc networks and unmanned aerial vehicle,etc.

黃紹成（1990—），男，廣西貴港人，空軍工程大學(xué)航空航天工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閍d hoc網(wǎng)絡(luò)，無人機(jī)等。

SUN Kangning was born in 1991.He is an M.S candidate at College of Aeronautics and Astronautics Engineering, Air Force Engineering University.His research interest is coding theory.

孫康寧（1991—），男，山東淄博人，空軍工程大學(xué)航空航天工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)榫幋a理論。

TIAN Yu was born in 1985.He received the Ph.D.degree from Air Force Engineering University in 2014.Now he is an engineer at Unit 95876 of PLA.His research interests include ad hoc networks and unmanned aerial vehicle,etc.

田雨（1985—），男，山東濟(jì)南人，2014年于空軍工程大學(xué)獲得博士學(xué)位，現(xiàn)為95876部隊(duì)工程師，主要研究領(lǐng)域?yàn)閍d hoc網(wǎng)絡(luò)，無人機(jī)等。

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-09-02,http://www.cnki.net/kcms/detail/11.5602.TP.20150902.1102.004.html

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TP393

doi:10.3778/j.issn.1673-9418.1507021

Ordinal Potential Game Based Topology ControlAlgorithm for WSN

CAI Zhao1+,MALinhua1,HUANG Shaocheng1,SUN Kangning1,TIAN Yu2
1.College ofAeronautics andAstronautics Engineering,Air Force Engineering University,Xi’an 710038,China
2.Unit 95876 of the Chinese People?s LiberationArmy,China
+Corresponding author:E-mail:laziofly1214@163.com

Abstract:Since the energy of sensor node is limited,and node is not easily replaced,energy efficiency issue has been an important factor that restricting sensor network lifetime.This paper constructs a topology control algorithm based on a potential game(potential game topology control,PGTC),and takes the smallest potential lifetime and degree respectively as primary and secondary utility functions.By adjusting transmitting power,nodes reduce the power of the node which has the shortest potential lifetime in reverse-link set to extend its potential lifetime,while controlling the node degree to reduce the average hops of link and total energy consumption.This paper analyzes that the PGTC model is an ordinal potential game and possesses a Nash equilibrium which is Pareto optimal.The simulation results indicate that the PGTC algorithm reduces the total energy consumption of network and the difference in energy between nodes compared with other topology control algorithms based on game theory.

Key words:wireless sensor network(WSN);topology control;potential game;Nash equilibrium

猜你喜歡

納什均衡無線傳感器網(wǎng)絡(luò)

去產(chǎn)能政策的激勵(lì)相容安排與系統(tǒng)風(fēng)險(xiǎn)防范

金融發(fā)展研究(2016年11期)2017-01-12 19:27:14

基于納什均衡的充電樁建設(shè)博弈分析

現(xiàn)代商貿(mào)工業(yè)(2016年14期)2016-12-27 15:49:15

基于無線傳感器網(wǎng)絡(luò)的綠色蔬菜生長環(huán)境監(jiān)控系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

軟件導(dǎo)刊(2016年11期)2016-12-22 21:57:17

基于無線傳感器網(wǎng)絡(luò)的葡萄生長環(huán)境測(cè)控系統(tǒng)設(shè)計(jì)與應(yīng)用

山東農(nóng)業(yè)科學(xué)(2016年11期)2016-12-17 22:18:05

一種改進(jìn)的基于RSSI最小二乘法和擬牛頓法的WSN節(jié)點(diǎn)定位算法

電腦知識(shí)與技術(shù)(2016年27期)2016-12-15 20:30:53

無線傳感器網(wǎng)絡(luò)定位技術(shù)可靠性分析

軟件導(dǎo)刊(2016年9期)2016-11-07 17:46:50

對(duì)無線傳感器網(wǎng)絡(luò)MAC層協(xié)議優(yōu)化的研究與設(shè)計(jì)

科技視界(2016年22期)2016-10-18 15:25:08

囚徒困境、契約和懲罰

中國市場(2016年33期)2016-10-18 12:05:11

無線傳感器網(wǎng)絡(luò)技術(shù)綜述

科學(xué)與財(cái)富(2016年28期)2016-10-14 00:49:07

基于納什均衡的中小企業(yè)融資問題探討

商業(yè)經(jīng)濟(jì)研究(2016年7期)2016-04-19 16:37:10

計(jì)算機(jī)與生活2016年8期

計(jì)算機(jī)與生活的其它文章

坡代數(shù)的(,∨(λ,μ))-模糊理想*

lp范數(shù)下具有等級(jí)約束的負(fù)載均衡問題*

組塊3×2交叉驗(yàn)證的F1度量的方差分析*

結(jié)合各向異性中值擴(kuò)散的PET圖像重建算法*

紋理圖像中重復(fù)紋理元素提取方法*

第三方支付粗糙復(fù)雜網(wǎng)絡(luò)知識(shí)發(fā)現(xiàn)方法研究*