基于序数势博弈的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