基于博弈論的無線傳感器網絡能耗均衡分簇協議

李 朋,陶 洋,許湘揚,楊 柳

(重慶郵電大學 通信與信息工程學院,重慶 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可以看出,該博弈是一個對稱博弈,在對稱博弈中,博弈的收益只依賴選手所選擇的決策而不依賴進行博弈的參與者。本文假設rc,則v-c>v-r,當選簇頭能夠獲得更大的收益,那么節點都會做出當選簇頭的決策,此時沒有普通節點來監聽收集數據。接下來,把博弈拓展到N個參與者,令S={S1,S2,…,SN}為所有節點的決策組合集,如果沒有節點愿意充當簇頭,那么收益為0;如果至少有一個節點i愿意當簇頭,那么節點i的收益為v-c,其他節點的收益為v-r。節點i的收益函數如下:

(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)]內。

3 兩輪競選分簇協議

本節對本文提出的基于博弈論和節點分簇的無線傳感器網絡能耗均衡協議(Energy Consumption Balance Based on the Game Theory and Clustering,EGTC)進行詳細敘述。圖3為協議每一輪簇頭競選的流程,主要包括節點初始化階段、設置階段以及成簇后的穩態階段。其中,設置階段又分為候選簇頭競選、真正簇頭競選和成簇;穩態階段的主要任務是負責數據的收集、處理和傳輸。

圖3 簇頭競選流程

3.1 節點初始化階段

初始化階段的主要任務是收集每個節點的信息,包括地理位置、ID等,同時計算其到基站的距離[15]。假設節點的最大傳輸功率足夠節點和基站之間傳輸數據,節點能夠根據通信距離調整傳輸功率。首先,基站廣播“開始”信息,同時假設這條信息能夠被所有節點接收。然后,每個節點根據接收到信號的強度計算它到基站的距離。此外,節點i在傳輸半徑R范圍內廣播“hello”包,每個節點即可得知其傳輸半徑R范圍內的所有鄰居節點。

3.2 候選簇頭階段

候選簇頭競選階段是每一輪的開始階段,每個節點當選博弈者參與包括自己和鄰居節點在內的多個分簇博弈。通過自己參與的博弈,每個節點根據自身均衡概率決定是否成為簇頭。在每一輪的競選中,對于任何節點i,首先計算其均衡概率。如果不存在耗盡能量的鄰居節點,則根據式(14)計算均衡概率;否則,計算均衡概率如下:

pi=1-(w)1/(|Nb(i)|-|Nd(i)|)

(18)

其中,Nd(i)是傳輸半徑內能量耗盡的節點集合,則|Nd(i)|是集合中元素個數。同時,由于兩輪競選機制和懲罰函數的引入,節點能夠快速求取節點收益最大時的均衡概率值。

為防止出現半徑R范圍內有多個簇頭節點的情況,如果一個節點決定成為簇頭,則其狀態變為候選簇頭。一個候選簇頭必須進行下一輪的競選才能成為真正的簇頭,而最后沒能成為真正簇頭的候選簇頭將重新變成普通節點,等待下一輪的簇頭競選。此外,如果一個節點成為真正的簇頭,則其下一輪成為簇頭的概率不會變為0,即LGCA中的零概率準則在此不適用。節點競選簇頭的概率和節點的剩余能量有關。

3.3 真正簇頭階段

由于在前一個子階段的候選簇頭競選中,可能存在多個簇頭互為鄰居節點的情況[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

3.4 簇形成階段

在確定所有的最終簇頭之后,正常節點將在自己的傳輸半徑范圍內選擇具有最小節點度的簇頭節點加入簇。加入消息“join_cluster”(包括節點的剩余能量Eres)由半徑R內的每個正常節點廣播,相應的簇頭和沒有鄰居簇頭的節點接收。沒有鄰居簇頭的節點將選擇其鄰居中具有最大剩余能量的普通節點當選中繼節點加入相應的集群。每個簇頭創建一個時間表并將其廣播到它的成員節點。

4 仿真與結果分析

本文通過Matlab軟件對EGTC進行仿真分析,并與CROSS和LGCA協議進行比較。

4.1 仿真參數設置

首先,對仿真環境進行設定,把感知區域設定為面積為S(L×W)m2的正方形區域,100個傳感器節點均勻分布在該感知區域內。節點初始能量為0.5 J,其他主要網絡參數設定如表2所示。

表2 仿真參數設置

4.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 各協議存活節點數比較

5 結束語

本文在博弈論的基礎上,提出一種基于分布式分簇的節點能耗均衡分簇協議,以降低節點能耗分布的不均衡性,提高網絡生命周期。結合節點剩余能量對普通節點和簇頭節點的收益作出定義;在此基礎上根據納什均衡理論計算出每個節點的均衡概率,由于節點剩余能量較多或節點損耗較小的節點成為簇頭的概率較大,因此可以在最小化能耗和有效提供所需業務之間取得良好的平衡;為避免相鄰節點同時成為簇頭,考慮節點剩余能量和損耗,提出一個迭代算法從候選的簇頭中選擇最終的簇頭。仿真結果證明,與CROSS和LGCA協議相比,本文協議有效降低了能耗的不均衡性,能夠在不同的網絡規模中延長網絡壽命。下一步將從加快簇首選舉收斂速率的角度出發,減少簇首推舉過程中消耗的能量。