基于博弈论的无线传感器网络能耗均衡分簇协议
2019-01-02许湘扬
李 朋,陶 洋,许湘扬,杨 柳
(重庆邮电大学 通信与信息工程学院,重庆 400065)
0 概述
典型的无线传感器网络(Wireless Sensor Network,WSN)由大量具有数据收集和无线通信功能的廉价传感器构成[1]。这些传感器大量布置于感知区域,能够自组织成为Ad Hoc网络[2]。WSN广泛应用于各种领域以达到监测目的。无线传感器的能量主要来源于其自身携带的微小电池。在现实情况下,对电池进行充电或者更换非常不方便,有时甚至无法更换电池和重复充电,这会限制整个网络的性能。传感器节点执行计算时消耗的能量远小于传输信息时消耗的能量,经测量,1 bit信息传输100 m消耗的能量大致和传感器执行3 000次计算指令消耗的能量相等[3]。
分簇的基本思想是让部分节点充当簇头,簇头和其他普通节点形成一个簇。簇头节点通常具有更多的能量,更强的通信和计算能力,从而可以承担处理更多通信和信息的任务。在簇中,普通节点收集并转发数据给簇头,簇头收到大量重复数据,为减少发送不必要的数据,簇头需要先对数据去冗余后再传输到基站。
近年来,众多研究者将博弈论的思想应用于无线传感器网络中。文献[4]将互联网类网络的创建模型化为由自私节点当选博弈者参与的一场博弈。
本文基于博弈论思想进一步研究节点分簇问题,提出一种基于分布式分簇的节点能耗均衡分簇协议。结合节点剩余能量定义每个节点选择不同决策时收益v和损耗c的概念,在此基础上,计算每个节点博弈的均衡概率,同时在提供有效服务和最小化能耗之间取得好的权衡;提出一种基于博弈论的能耗均衡节点分簇协议,每个节点通过局部分簇博弈获得均衡概率,然后决定是否当选簇头,从而保证每个节点的收益相对平衡;给出一种迭代算法,从候选簇头集合中筛选真正簇头,避免在近距离内选出多个簇头,并考虑节点剩余能量,以确保剩余能量多的节点能够优先成为簇头。
1 相关工作
文献[5]提出利用非合作博弈论来选簇头,建立一种基于纳什均衡的路由机制。但是,它假设每个参与人即每个节点都能和其余所有节点互相交换信息是不合理的。同时,CROSS协议[5]给出节点当选簇头的均衡概率p是指数衰减函数,因此CROSS不适用于大型无线传感器网络。
为了解决在CROSS中出现的问题,文献[6]提出LGCA协议。在LGCA协议中,每个节点根据局部分簇博弈得到的均衡概率决定是否成为簇头。LGCA完全分布且易于扩展,然而仍存在许多不足[7]:首先,参量v和c不够明确,且LGCA假设每个节点的v和c都相同是不合理的;其次,许多能够提高协议性能的重要参数没有考虑,例如剩余能量、节点度数以及到基站的距离;然后,一旦一个节点成为簇头,它再次成为簇头的概率将会设置为零,直到每个节点都当选过簇头,即每个节点成为簇头的概率没有和均衡概率完全一致,并且节点无法一直保持收益均衡;最后,使用真正簇头竞选机制使结果趋于随机,且对于剩余能量多的潜在簇头,将会有成为簇头的优先权。
本文基于LGCA协议,提出一个能耗更加均衡的协议,使无线传感器网络整体寿命延长。
2 系统模型及理论分析
2.1 网络模型
本文使用多跳式网络拓扑结构[8],如图1所示。多跳式分簇路由结构不需要维护大量路由表信息,因此,适用于大规模无线传感器网络。此外,多跳通信也弥补了单跳通信导致的簇头节点耗能过快的缺陷。多跳式分簇路由拓扑结构由普通节点、簇头节点和基站构成。普通节点收集感知区域的数据,然后发送到簇头节点,簇头节点处理数据后将数据通过其他簇头节点传到基站。
图1 多跳式网络拓扑结构
为方便协议的展开,本文将对传感器节点做如下假设:
1)每个节点都有唯一的ID来识别数据来源。
2)这些传感器节点一旦部署在感知区域,位置将不再变化[9]。
3)所有节点的电池电量都相同,且不能充电,基站无能量限制。
4)每个节点能够根据到目标的距离调整传输功率。
2.2 无线能耗模型
本文采用的无线能耗模型[5,10]如图2所示。
图2 无线能耗模型
节点传输kbit数据包消耗的能量如下:
(1)
接收器接收kbit数据包消耗的能量表示如下:
ERx(k)=kEelec+kEDA
(2)
其中,EDA是簇头每压缩1 bit数据消耗的能量。
2.3 收益和损耗分析
本文把簇头选举模拟成一个局部博弈{N,S,U},其中,N是参与博弈的节点集合,S={Si}为节点可选的决策集合,U={Ui}是与决策集合相对应的节点收益集合。传感器节点参加簇头选举博弈从中选择部分节点当选簇头,并且至少选取一个节点当选簇头。簇头将普通节点收集到的数据进行处理、整合,以数据包的形式发送到基站。从收益角度来说,如果一个节点选择当普通节点时,又有其他至少一个节点成为簇头,那么这个节点的收益是v,可以认为其是数据成功转发到基站带来的收益。如果节点选择当选簇头,那么它的收益是v-c,其中c是当选簇头的损耗,由于簇头往往会收集整合多个普通节点发送给自己的数据,因此需要消耗较多的能量。同时,为防止没有节点成为簇头而导致普通节点收集到的数据无法转发情况,引入惩罚机制[12-13],r可以认为是对普通节点的惩罚,则节点选择做普通节点的收益为v-r。
首先讨论只有2个参与者的情况,节点的收益如表1所示。
表1 两节点博弈收益
从表1可以看出,该博弈是一个对称博弈,在对称博弈中,博弈的收益只依赖选手所选择的决策而不依赖进行博弈的参与者。本文假设r
(3)
则有如下结论:
1)当所有节点都选择当选簇头时,此时的决策S={CH,CH,…,CH}不是一个纳什均衡。
2)当所有节点都选择当普通节点时,此时的决策S={CM,CM,…,CM}不是一个纳什均衡。
为平衡节点的能耗,希望能量较充足且损耗更低的节点能够更大可能性地充当簇头,从而使能量较少的节点不会过早地消耗完能量,影响网络的覆盖范围。节点当选簇头的损耗和节点剩余能量有关,若节点的剩余能量较高,那么充当簇头的损耗相对较低,从而能有效地保存节点数目,延长WSN的寿命。节点成为簇头的几率和参数c有关,也和参加博弈的节点数目有关。假定c与v成比例关系,c与节点的剩余能量有关,剩余能量越高,损耗越小。
2.4 均衡概率计算
本文引用LGCA协议中对邻居节点的定义和对节点通信范围的假设。对节点i,若在博弈时选择当选簇头,且邻居节点选择当选普通节点的决策,则节点i成为簇头的损耗可表示如下:
(4)
其中,k>1,Eres是节点当选簇头时的剩余能量。由于节点i收益和损耗成比例,因此收益函数可计算如下:
(5)
其中,m为比例系数,且m>1。在此情况下,节点i当选簇头的收益可表示为:
(6)
节点i当选普通节点的收益可表示为:
(7)
其中,r为节点根据利己性选择当选普通节点时做出的惩罚,它小于当选簇头的损耗,即r (8) 其中,N是在半径R范围内包括节点i在内的所有节点数,N-1表示以节点i为中心,半径为R范围内的节点数。令w=(c-r)/(v-r),因为r (9) 本文采用两轮竞选机制,同时在第二轮引入惩罚机制,可防止无限迭代现象的发生。如果簇头在首轮就竞选成功,则任意节点i的平均收益可计算如下: vPr{si=ND∩∃js.t.sj=D,j≠i}= (v-c)p+v(1-p)(1-(1-p)N-1)⟹ (10) (11) 如果首轮未竞选出簇头,则自动进入第二轮,同时引入惩罚值r,则选择当选普通节点决策的节点收益为v-r,由此,任意节点i的平均收益可计算如下: [1-(1-p)N-1]=(1-p)[(v-c)p+ (v-r)(1-p)-(v-r)(1-p)N] N(N+1)(v-r)(1-P)N= (N+1)(v-r)(1-p)N- 2(c-r)(1-p)+(v-c) (12) 式(12)无法确定是否存在p∈(0,1),使得该方程有解。但是,可以根据一轮竞选时的最大平均收益做出推断,即当节点个数趋近于无穷大时,最大平均收益趋近于v-c。除此之外,可以考虑是否存在最优解的情况。因为本文对博弈参与者不做区分,所以最优解的情况应该是在半径R内,每轮竞选有且只有一个节点选择成为簇头,而其余节点选择当选普通节点。在此情况下的平均收益为: (13) 当节点个数N趋于无穷大时: (14) (15) 通过分析可知,PoA的值只和节点选择成为簇头的损耗c和选择成为普通节点时受到的惩罚r有关,而和收益v不相关。当N=2时,PoA有最小值,相反,当节点个数无穷大时,PoA有最大值。 PoAmin=(c-r)/2 (16) PoAmax=c-r (17) 无论节点的数量如何变化,PoA的值总是在区间[(c-r)/2,(c-r)]内。 本节对本文提出的基于博弈论和节点分簇的无线传感器网络能耗均衡协议(Energy Consumption Balance Based on the Game Theory and Clustering,EGTC)进行详细叙述。图3为协议每一轮簇头竞选的流程,主要包括节点初始化阶段、设置阶段以及成簇后的稳态阶段。其中,设置阶段又分为候选簇头竞选、真正簇头竞选和成簇;稳态阶段的主要任务是负责数据的收集、处理和传输。 图3 簇头竞选流程 初始化阶段的主要任务是收集每个节点的信息,包括地理位置、ID等,同时计算其到基站的距离[15]。假设节点的最大传输功率足够节点和基站之间传输数据,节点能够根据通信距离调整传输功率。首先,基站广播“开始”信息,同时假设这条信息能够被所有节点接收。然后,每个节点根据接收到信号的强度计算它到基站的距离。此外,节点i在传输半径R范围内广播“hello”包,每个节点即可得知其传输半径R范围内的所有邻居节点。 候选簇头竞选阶段是每一轮的开始阶段,每个节点当选博弈者参与包括自己和邻居节点在内的多个分簇博弈。通过自己参与的博弈,每个节点根据自身均衡概率决定是否成为簇头。在每一轮的竞选中,对于任何节点i,首先计算其均衡概率。如果不存在耗尽能量的邻居节点,则根据式(14)计算均衡概率;否则,计算均衡概率如下: pi=1-(w)1/(|Nb(i)|-|Nd(i)|) (18) 其中,Nd(i)是传输半径内能量耗尽的节点集合,则|Nd(i)|是集合中元素个数。同时,由于两轮竞选机制和惩罚函数的引入,节点能够快速求取节点收益最大时的均衡概率值。 为防止出现半径R范围内有多个簇头节点的情况,如果一个节点决定成为簇头,则其状态变为候选簇头。一个候选簇头必须进行下一轮的竞选才能成为真正的簇头,而最后没能成为真正簇头的候选簇头将重新变成普通节点,等待下一轮的簇头竞选。此外,如果一个节点成为真正的簇头,则其下一轮成为簇头的概率不会变为0,即LGCA中的零概率准则在此不适用。节点竞选簇头的概率和节点的剩余能量有关。 由于在前一个子阶段的候选簇头竞选中,可能存在多个簇头互为邻居节点的情况[16],从而导致簇头分布不均。为避免这个问题,引入最后的簇头选举子阶段。另外,如果一个剩余能量较少的候选簇头被选为最终的簇头,则该节点会提前耗尽能量,产生能量空洞,且影响网络整体的寿命。因此,剩余能量较多的候选节点有较大的概率当选最终的簇头。 针对上述问题,本文提出一种迭代算法,根据节点剩余能量和损耗选择真正簇头,达到能耗均衡的目的。对于任何处于候选状态的簇头节点i,如果没有相邻的候选簇头,即设置的NTCH(i)是空集,则它将自动成为最终的簇头并广播最终簇头选举消息“CH_msg2”(包括节点ID、簇头状态和节点剩余能量)。如果设置NTCH(i)不是空集,则候选簇头节点i将尝试执行多次迭代以选择最终的簇头,最大迭代次数可计算如下: (19) 其中,NTCH(i)是除节点i外的邻居候选簇头节点的集合,则|NTCH(i)|是集合NTCH(i)中的元素个数,即节点i的邻居候选簇头节点的个数。为方便迭代过程的描述,将整个网络中需要进行迭代的候选簇头看做一个集合,记为STCH,则: STCH={i|i∈ATCH,NTCH(i)≠Ø} (20) 其中,ATCH为所有候选簇头的集合。 在迭代过程中,集合STCH中的每个节点仍然处于候选簇头状态,每个节点与邻居节点相比较,从而在以自己为中心且半径为R的范围内选出损耗最低的候选簇头节点当选自己的簇头。如果选择自己当选簇头的节点将在半径R内广播消息“CH_msg1”,并在下一次迭代中成为临时的簇头,集合ATCH中的和其相邻的其他节点在收到消息“CH_msg1”后将返回到正常节点的状态。选择其他节点当选簇头的候选簇头节点,其状态不变,进入下一次迭代。每次迭代完成后对集合STCH进行更新,删除返回到正常状态的节点。 这一子阶段对候选簇头进行迭代的算法伪代码如下: 算法真正簇头竞选迭代算法 if(is_candidate_CH = TRUE) NTCH(i)←{s|s is a cluster head,s∈Nb(i)} if NTCH(i) = Ø) is_final_CH ← TRUE CH_msg2(NodeID,final_CH,Eres) else nmax(i) ← [|NTCH(i)|/2] while(k≤nmax(i) )do CH(i)←{s|s is CH,s∈[NTCH(i),i} if(CH(i)≠Ø) my_CH ← min_Cost(CH(i)) if (my_CH = i) NTCH(i) ← Ø Update STCH(i) CH_msg1(NodeID,final_CH,Eres) else my_CH ← min_Cost(CH(i)) end if end if k ← k+1 end while end if end if 在确定所有的最终簇头之后,正常节点将在自己的传输半径范围内选择具有最小节点度的簇头节点加入簇。加入消息“join_cluster”(包括节点的剩余能量Eres)由半径R内的每个正常节点广播,相应的簇头和没有邻居簇头的节点接收。没有邻居簇头的节点将选择其邻居中具有最大剩余能量的普通节点当选中继节点加入相应的集群。每个簇头创建一个时间表并将其广播到它的成员节点。 本文通过Matlab软件对EGTC进行仿真分析,并与CROSS和LGCA协议进行比较。 首先,对仿真环境进行设定,把感知区域设定为面积为S(L×W)m2的正方形区域,100个传感器节点均匀分布在该感知区域内。节点初始能量为0.5 J,其他主要网络参数设定如表2所示。 表2 仿真参数设置 本文将在2种情况下对提出的分簇协议进行分析。首先,在不同面积的感知区域内比较CROSS、LGCA和EGTC协议的簇头数量和感知面积的关系,感知区域的面积分别是5 000 m2、10 000 m2、15 000 m2、22 500 m2、30 000 m2和40 000 m2,基站的位置可表示为(L/2,W+50)。其次,选择面积为100 m×100 m的感知区域,在此感知区域中,比较CROSS、LGCA和EGTC协议中博弈论次和生存节点数的关系。 图4为不同规模网络下各协议网络寿命对比。从图4可以看出,EGTC在上述多种网络规模中的网络寿命均优于LGCA和CROSS协议。此外,随着网络规模的增大,3种协议的寿命都呈下降趋势,这是因为随着面积的增大,节点的通信损耗增加。当面积小于15 000 m2时,CROSS的寿命大于LGCA,当面积大于15 000 m2时则相反,说明LGCA更适用于大规模网络。 图4 不同规模网络下各协议网络寿命比较 图5显示了EGTC、LGCA和CROSS协议在不同规模的感知网络中每轮平均簇数的差异。从图5可以看出,随着网络面积的增大,CROSS协议的每轮平均成簇数有所下降。这是因为CROSS协议采用全局博弈的方式,传感器节点数随着网络面积的增大而增加,而该协议中节点的均衡概率p是衰减函数,所以簇头数量会随着传感器节点数量的增加而减少。LGCA和EGTC协议中平均簇数随着网络面积增大而缓慢增长,这是因为尽管网络面积逐渐增大,但是网络中节点的通信半径也随之增大,如图6所示。在一定程度上,通信半径的增大减缓了平均簇数量的增长速度。 图5 不同规模网络下各协议平均成簇数量比较 图6 不同规模网络下的节点通信半径比较 为突出本文协议的特点,图7显示了当感知区域面积为100 m×100 m时,CROSS、LGCA和HGTD在每轮中存活的节点数比例。从图7可以看出,EGTC的曲线斜率最大,即网络中各节点能量耗尽的时间差较小,说明EGTC协议很好地平均了各个节点的能量消耗,从而解决了部分节点能量耗尽导致的能量空洞问题。 图7 各协议存活节点数比较 本文在博弈论的基础上,提出一种基于分布式分簇的节点能耗均衡分簇协议,以降低节点能耗分布的不均衡性,提高网络生命周期。结合节点剩余能量对普通节点和簇头节点的收益作出定义;在此基础上根据纳什均衡理论计算出每个节点的均衡概率,由于节点剩余能量较多或节点损耗较小的节点成为簇头的概率较大,因此可以在最小化能耗和有效提供所需业务之间取得良好的平衡;为避免相邻节点同时成为簇头,考虑节点剩余能量和损耗,提出一个迭代算法从候选的簇头中选择最终的簇头。仿真结果证明,与CROSS和LGCA协议相比,本文协议有效降低了能耗的不均衡性,能够在不同的网络规模中延长网络寿命。下一步将从加快簇首选举收敛速率的角度出发,减少簇首推举过程中消耗的能量。
3 两轮竞选分簇协议
3.1 节点初始化阶段
3.2 候选簇头阶段
3.3 真正簇头阶段
3.4 簇形成阶段
4 仿真与结果分析
4.1 仿真参数设置
4.2 结果分析
5 结束语
