基于序數勢博弈的WSN拓撲控制算法

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

基于序數勢博弈的WSN拓撲控制算法

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

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.

摘要：由于傳感器節點能量有限且不易更換，故能量效率一直是制約傳感網生存周期的重要因素。構建一種基于勢博弈的拓撲控制（potential game topology control，PGTC）模型，將最短潛在壽命和節點度取值分別作為首要、次要效用函數。節點調整自身的發射功率，降低反向鏈路集中潛在壽命最短節點的發射功率，延長其潛在壽命，同時控制節點度取值以減小鏈路平均跳數和總能耗。理論分析可知，PGTC模型屬于序數勢博弈，存在納什均衡，且納什均衡點即為帕累托最優解。仿真表明，PGTC模型相較于其他基于博弈論的拓撲控制算法，網絡總能耗更低，并且能量均衡性更強。

關鍵詞：無線傳感器網絡（WSN）；拓撲控制；勢博弈；納什均衡

1　引言

傳感器網絡由于成本低，便于部署的特點，在軍事探測、環境監測、災難預警領域被廣泛地使用。但由于傳感器一般采用電池供電，且通常布設在嚴苛、不易更換的環境中，故能量效率問題一直以來都是制約傳感網生存周期的重要因素[1-2]。同時，在節點數量多，分布密集的傳感網中，處于主干路線上的節點負載較重，存在過早死亡的風險，使得網絡的連通性和健壯性急劇下降。故能耗均衡問題同樣也應作為延長網絡生存周期的重要因素被加以考慮。拓撲控制算法旨在保證網絡連通性和健壯性的情況下，提升能量效率和能量均衡度。網絡中各節點用優化的傳輸功率代替最大傳輸功率，構建能效更高的拓撲結構，極大地提升了網絡性能。但是傳統Ad-hoc網絡的拓撲控制技術不能直接應用在無線傳感網中，需要研究適合的高效拓撲控制算法。

勢博弈作為一種特殊的策略博弈，由于節點效用函數與全局勢函數具有同樣的變化趨勢，故博弈會不斷朝著最優的目標函數前進，經過有限次的迭代決策就能找到最優解。勢博弈因其良好屬性，作為分布式動態優化理論在網絡擁塞控制、功率控制以及資源調度等方面得到了大量應用[3-6]。文獻[7]構建了基于博弈論的自適應協作拓撲控制（cooperative topology control with adaptation，CTCA）算法，將提升反向鏈路集中節點最短壽命和自身壽命分別作為首要、次要效用函數。文獻[8]針對能量采集傳感網提出了一種綜合考慮節點的能量狀況和能量采集能力的拓撲控制算法，把最大化網絡生存周期的問題轉化為序數勢博弈過程。

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

本文構建基于勢博弈的拓撲控制（potential game topology control，PGTC）算法，定義網絡中的最短潛在壽命為首要效用函數，節點度取值是否滿足最優節點度區間為次要效用函數。PGTC算法通過提高最短潛在壽命均衡網絡能耗，通過優化節點度取值降低鏈路總能耗，極大地提升了網絡的整體性能。此外，本文的綜合效用函數摒除了傳統的加權形式，引入次要因素考慮因子，確保節點僅在首要效用函數取最大值時考慮次要因素，進一步延長了網絡的生存周期。

2　序數勢博弈模型

2.1概念定義

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

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

定義3（可達鄰居集）節點i在t時刻發射功率可以到達的節點集被稱作可達鄰居集，簡稱鄰居集，記為Ri或Ri(t)。定義節點i及其可達鄰居集的并集

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

定義5（映射）P代表網絡中各節點到其發送功率的映射，即{N1→p1,N2→p2,…}。P-i為整個網絡除去節點i的功率映射，Pi為R?i集內節點的功率映射。

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

定義7（估計壽命）假設節點i的剩余能量為Wi(t)，發射功率為 pi(t)，定義t時刻節點i的估計壽命為Li(pi(t),t)=Wi(t)/pi(t)。

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

2.2效用函數

對于網絡中的任意節點i而言，通過改變發射功率可在Oi集內其他節點策略不變的情況下，改變自身的對稱鄰居個數。當節點增加發射功率時，其反向鏈路集中的對稱鄰居個數也相應增加。新增的部分對稱鄰居節點可在保證自身與全網連通性的情況下（至少有一個對稱鄰居節點），適當減小發射功率，延長潛在壽命。如圖1中，節點j增加自身發射功率，使i成為其對稱鄰居。對i而言，原先距離其最近的對稱鄰居為k，而現在最近的對稱鄰居變為j。故i在保證其與全網連通性的前提下，可減小自身發射功率。

Fig.1　Schematic diagram of adjusting transmission power圖1　發射功率調整示意圖

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

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

需要注意的是，節點的功率策略（或潛在壽命）只能描述單跳的能耗，而不能代表網絡總能耗，因為總能耗是平均發射功率與鏈路平均跳數的乘積。而平均跳數很大程度上取決于節點度的大小，節點度過低會造成平均跳數的顯著增加。例如圖2中，當s的節點度為1時，從源節點到目的節點需要3跳，如路徑1所示；而當s的節點度為2時，從源節點到目的節點需要1跳，如路徑2所示。明顯地，路徑1的能耗要大于路徑2。

同時節點度數也不能過高，主要有以下原因：

（1）加重高節點度節點的數據轉發負擔，使其易由于能量消耗過快而過早死亡。

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

（3）造成傳輸信號之間的沖突和干擾，增加數據包重傳次數。

Fig.2　Forwarding paths at different node degrees圖2　不同節點度情況下的通信路徑

為了提高拓撲結構的能量效率，提高信道復用率，降低干擾，節點度應該處于特定區間[kmin,kmax]。文獻[9-10]通過仿真得出，當最大節點度為4時，網絡的鏈路總能耗最低。本文結合能量均衡性的問題，適當增加高電量節點的能量消耗，將最大節點度設為5。最小節點度在考慮網絡健壯性和能量均衡博弈效果的情況下，參照文獻[12]設置為2。

當節點既要提高O?i集內最短潛在壽命，又要改變節點度數時，即首要因素與次要因素相互沖突時，為確保節點優先考慮首要因素，本文摒棄傳統的加權形式，轉而采用次要因素考慮因子li(pi,t)。在引入它之前，先定義節點i的優先功率集Fi。

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

定義使得Oi集內最短潛在壽命取值為σ(i,t)的所有功率取值均屬于節點i的優先功率集。

當節點i的功率屬于其優先功率集時，次要因素考慮因子li(pi,t)取1，否則取0。

結合i的次要因素考慮因子和首要、次要效用函數表達式，可得綜合效用函數：

式中，C(P,t)是二進制連通函數，當節點i至少有一個對稱鄰居時此項取1，否則取0。根據綜合效用函數表達式可知，只有當節點功率處于其優先功率集內，即li(pi,t)=1時，才會考慮次要因素，否則只考慮首要因素。

2.3序數勢博弈

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

（1）節點域N，i∈N={1,2,…,n}，其中n代表網絡中的節點個數。

（3）效用函數{ui(?)}i∈N，效用函數的取值由兩部分組成，分別與節點O?i集內的最短潛在壽命和當前節點度數有關，見式（6）。節點將依據效用函數取值的大小選取最優的功率等級。

此外，將第一個節點死亡的時間定義為網絡生存周期，利用最短的節點潛在壽命對其進行近似，并將最短潛在壽命定義為博弈的勢函數，見下式：

3　理論證明

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

證明 假設t時刻的功率映射情況為P,t+1時刻的功率映射情況為P′。由于映射情況本身就能代表時間順序，故為簡化表達，省略時刻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)。

根據t和t+1時刻功率映射所對應的網絡連通性變化情況，可分為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種情況滿足節點效用函數與序數勢函數取值同號的條件，故僅討論第4種情況。這種情況下，從t時刻到t+1時刻節點效用函數以及總體的勢函數變化值分別為：

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

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

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

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

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

節點i的功率策略一直處于其優先功率集內，故O?i集內的最短潛在壽命可視為不變，即有MLi(P′)= MLi(P)，故勢函數ΔV(P)=0。

節點保證當前功率處于優先功率集的前提下，會調整自身節點度，提升效用函數取值：Δui(pi)= D(ki′)-D(ki)≥0，由于勢函數取值為0，故節點效用函數與勢函數同號。

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

因為pi∈Fi且pi′?Fi，故節點i的功率映射關系由P變為P′后，其Oi集內的最小潛在壽命減小，即MLi(P′)

由于節點只能改變自身及反向鏈路集內的潛在壽命，故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)可知，節點i調整功率后其O?i集的最短潛在壽命變短，故ai′?Fi，t+1時刻的次要因素考慮因子取0，即li(pi′ )=0。

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

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

由于全網最短潛在壽命滿足上述條件，故從t到t+1時刻網絡的勢函數變化值為ΔV(P)=ML-i(P)-ML-i(P′)=0。由于勢函數取值不變，故不論節點效用函數取值如何變化，效用函數與勢函數同號。

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

定理2有限序數勢博弈具有有限改進路徑特性。

證明 由于網絡中節點不具有運動性，每個節點相對其各鄰居的距離恒定不變，故對應的發射功率也恒定不變。由于每個節點的鄰居個數是有限的，故其可選擇的功率等級也是有限的，從而本文的序數勢博弈為有限序數勢博弈。

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

定理3 PGTC模型的納什均衡即帕累托最優。

證明 在勢博弈中，納什均衡點對應的就是勢函數最大值點。本文將網絡內最短潛在壽命作為序數勢函數，并定義網絡生存周期為第一個節點死亡的時間，故序數勢函數取最大值時即為網絡生存周期最大的情況。因此納什均衡點就是優化問題的最優解，即帕累托最優解。

4　算法流程

4.1鄰居信息探測階段

（1）節點i用最大功率pmax廣播Hello消息（Hello消息包括自身位置信息）；

（2）確定最大可達鄰居集Ri及集合中節點數k；

（3）計算自身到最大鄰居集中所有節點的功率，構成策略集Ai；

（4）將到達各節點的功率從小到大進行排序，即pi[1]

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

（6）接收自身最大鄰居集中節點發送的信息；

（7）運行DLSS[12]（directedlocalspanningsubgraph）算法確定發送功率pi；

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

（9）接收最大鄰居集中各節點的發射功率pj；

（10）構建反向鏈路集Oi；

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

（12）節點用pi廣播自身的策略pi′；

（13）接收Oi集內各節點策略pj′。

4.2節點功率調整流程

節點增大自身發射功率需同時滿足4個條件：

（1）節點O?i集內的最短潛在壽命在Oi集內；

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

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

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

當這4個條件均被滿足時，節點將增大自身功率，并用新功率更新優先功率集。在保證Li′(pi′)≥Lm(i)′(P)的情況下，i將調整發射功率，使自身節點度取值滿足本文規定的區間。i將用新的功率廣播鄰居請求信息，并等待鄰居節點的應答信息，對鄰居集Ri進行更新。總體流程見圖3。

當節點接收到鄰居調整功率的信息后，判斷自身能否減小發射功率。首先找到當前功率所對應的最遠節點r（節點轉發的下一跳節點），判斷Ri內是否有距離更近且可以到達節點r的鄰居。若有則調整潛在發射功率，反之維持當前功率。自適應減小功率等級的具體流程見圖4。

4.3拓撲維護階段

（1）節點i收到j的信息后，提取j的功率信息pj；

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

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

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

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

（6）若j∈Ri，更新Ri集內j的功率信息；

（7）更新Ri集后節點判斷能否降低自身發射功率，流程見4.2節；

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

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

5　仿真分析

為衡量本文算法的效率，選取兩種基于博弈論的拓撲控制算法進行對比。能量福利拓撲控制（energy welfare topology control，EWTC）模型[13]利用Atkinson不等式構建能量福利函數，提高了能量的平均值和均衡度。虛擬博弈能量均衡算法（virtual gamebased energy balanced topology control，VGEB）[14]構建了虛擬博弈，節點通過選擇剩余能量較高的節點作為鄰居，減小低電量節點的負載，延長網絡的生存周期。本文將PGTC算法與EWTC、VGEB算法在節點度、發射功率、鏈路平均跳數、平均剩余能量、最低剩余能量5方面進行對比。

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

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

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

Fig.5　Comparison of average transmission power at different number of nodes圖5　平均發射功率隨節點數量的變化情況

Fig.6　Comparison of average node degree at different number of nodes圖6　平均節點度隨節點數量的變化情況

Fig.7　Comparison of link average hop at different number of nodes圖7　鏈路平均跳數隨節點數量的變化情況

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

Fig.9　Comparison of minimum energy at different number of nodes圖9　不同節點數量下的最小剩余能量的比較

6　結束語

本文針對無線傳感器網絡，構建了一種基于勢博弈的拓撲控制算法（PGTC）。在算法中，節點綜合考慮了反向鏈路集中的最短潛在壽命和當前節點度數，均衡能耗的同時，降低了鏈路總能耗。并通過勢博弈理論，證明了PGTC模型存在納什均衡，且納什均衡趨近于帕累托最優。仿真結果表明，PGTC模型相較于其他拓撲控制算法能效更高，壽命均衡性和網絡健壯性更強。

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.

附中文參考文獻：

[11]劉浩然,韓濤,李雅倩,等.具有路徑能耗優化特性的WSN無標度容錯拓撲控制算法[J].通信學報,2014,35(6):64-72.

[12]陳賢明,蔡躍明,張余,等.WSN中一種基于博弈論的拓撲控制算法[J].解放軍理工大學學報,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—），男，北京人，空軍工程大學航空航天工程學院碩士研究生，主要研究領域為ad hoc網絡，博弈論等。

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年于西安電子科技大學獲得博士學位，現為空軍工程大學航空航天工程學院教授、博士生導師，主要研究領域為ad hoc網絡，編碼理論等。

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—），男，廣西貴港人，空軍工程大學航空航天工程學院碩士研究生，主要研究領域為ad hoc網絡，無人機等。

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—），男，山東淄博人，空軍工程大學航空航天工程學院碩士研究生，主要研究領域為編碼理論。

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—），男，山東濟南人，2014年于空軍工程大學獲得博士學位，現為95876部隊工程師，主要研究領域為ad hoc網絡，無人機等。

Received 2015-06,Accepted 2015-08.

CNKI網絡優先出版:2015-09-02,http://www.cnki.net/kcms/detail/11.5602.TP.20150902.1102.004.html

文獻標志碼：A

中圖分類號：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