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

(重慶郵電大學 通信與信息工程學院,重慶 400065)

0 概述

典型的無線傳感器網(wǎng)絡(Wireless Sensor Network,WSN)由大量具有數(shù)據(jù)收集和無線通信功能的廉價傳感器構成[1]。這些傳感器大量布置于感知區(qū)域,能夠自組織成為Ad Hoc網(wǎng)絡[2]。WSN廣泛應用于各種領域以達到監(jiān)測目的。無線傳感器的能量主要來源于其自身攜帶的微小電池。在現(xiàn)實情況下,對電池進行充電或者更換非常不方便,有時甚至無法更換電池和重復充電,這會限制整個網(wǎng)絡的性能。傳感器節(jié)點執(zhí)行計算時消耗的能量遠小于傳輸信息時消耗的能量,經(jīng)測量,1 bit信息傳輸100 m消耗的能量大致和傳感器執(zhí)行3 000次計算指令消耗的能量相等[3]。

分簇的基本思想是讓部分節(jié)點充當簇頭,簇頭和其他普通節(jié)點形成一個簇。簇頭節(jié)點通常具有更多的能量,更強的通信和計算能力,從而可以承擔處理更多通信和信息的任務。在簇中,普通節(jié)點收集并轉發(fā)數(shù)據(jù)給簇頭,簇頭收到大量重復數(shù)據(jù),為減少發(fā)送不必要的數(shù)據(jù),簇頭需要先對數(shù)據(jù)去冗余后再傳輸?shù)交尽?/p>

近年來,眾多研究者將博弈論的思想應用于無線傳感器網(wǎng)絡中。文獻[4]將互聯(lián)網(wǎng)類網(wǎng)絡的創(chuàng)建模型化為由自私節(jié)點當選博弈者參與的一場博弈。

本文基于博弈論思想進一步研究節(jié)點分簇問題,提出一種基于分布式分簇的節(jié)點能耗均衡分簇協(xié)議。結合節(jié)點剩余能量定義每個節(jié)點選擇不同決策時收益v和損耗c的概念,在此基礎上,計算每個節(jié)點博弈的均衡概率,同時在提供有效服務和最小化能耗之間取得好的權衡;提出一種基于博弈論的能耗均衡節(jié)點分簇協(xié)議,每個節(jié)點通過局部分簇博弈獲得均衡概率,然后決定是否當選簇頭,從而保證每個節(jié)點的收益相對平衡;給出一種迭代算法,從候選簇頭集合中篩選真正簇頭,避免在近距離內選出多個簇頭,并考慮節(jié)點剩余能量,以確保剩余能量多的節(jié)點能夠優(yōu)先成為簇頭。

1 相關工作

文獻[5]提出利用非合作博弈論來選簇頭,建立一種基于納什均衡的路由機制。但是,它假設每個參與人即每個節(jié)點都能和其余所有節(jié)點互相交換信息是不合理的。同時,CROSS協(xié)議[5]給出節(jié)點當選簇頭的均衡概率p是指數(shù)衰減函數(shù),因此CROSS不適用于大型無線傳感器網(wǎng)絡。

為了解決在CROSS中出現(xiàn)的問題,文獻[6]提出LGCA協(xié)議。在LGCA協(xié)議中,每個節(jié)點根據(jù)局部分簇博弈得到的均衡概率決定是否成為簇頭。LGCA完全分布且易于擴展,然而仍存在許多不足[7]:首先,參量v和c不夠明確,且LGCA假設每個節(jié)點的v和c都相同是不合理的;其次,許多能夠提高協(xié)議性能的重要參數(shù)沒有考慮,例如剩余能量、節(jié)點度數(shù)以及到基站的距離;然后,一旦一個節(jié)點成為簇頭,它再次成為簇頭的概率將會設置為零,直到每個節(jié)點都當選過簇頭,即每個節(jié)點成為簇頭的概率沒有和均衡概率完全一致,并且節(jié)點無法一直保持收益均衡;最后,使用真正簇頭競選機制使結果趨于隨機,且對于剩余能量多的潛在簇頭,將會有成為簇頭的優(yōu)先權。

本文基于LGCA協(xié)議,提出一個能耗更加均衡的協(xié)議,使無線傳感器網(wǎng)絡整體壽命延長。

2 系統(tǒng)模型及理論分析

2.1 網(wǎng)絡模型

本文使用多跳式網(wǎng)絡拓撲結構[8],如圖1所示。多跳式分簇路由結構不需要維護大量路由表信息,因此,適用于大規(guī)模無線傳感器網(wǎng)絡。此外,多跳通信也彌補了單跳通信導致的簇頭節(jié)點耗能過快的缺陷。多跳式分簇路由拓撲結構由普通節(jié)點、簇頭節(jié)點和基站構成。普通節(jié)點收集感知區(qū)域的數(shù)據(jù),然后發(fā)送到簇頭節(jié)點,簇頭節(jié)點處理數(shù)據(jù)后將數(shù)據(jù)通過其他簇頭節(jié)點傳到基站。

圖1 多跳式網(wǎng)絡拓撲結構

為方便協(xié)議的展開,本文將對傳感器節(jié)點做如下假設:

1)每個節(jié)點都有唯一的ID來識別數(shù)據(jù)來源。

2)這些傳感器節(jié)點一旦部署在感知區(qū)域,位置將不再變化[9]。

3)所有節(jié)點的電池電量都相同,且不能充電,基站無能量限制。

4)每個節(jié)點能夠根據(jù)到目標的距離調整傳輸功率。

2.2 無線能耗模型

本文采用的無線能耗模型[5,10]如圖2所示。

圖2 無線能耗模型

節(jié)點傳輸kbit數(shù)據(jù)包消耗的能量如下:

(1)

接收器接收kbit數(shù)據(jù)包消耗的能量表示如下:

ERx(k)=kEelec+kEDA

(2)

其中,EDA是簇頭每壓縮1 bit數(shù)據(jù)消耗的能量。

2.3 收益和損耗分析

本文把簇頭選舉模擬成一個局部博弈{N,S,U},其中,N是參與博弈的節(jié)點集合,S={Si}為節(jié)點可選的決策集合,U={Ui}是與決策集合相對應的節(jié)點收益集合。傳感器節(jié)點參加簇頭選舉博弈從中選擇部分節(jié)點當選簇頭,并且至少選取一個節(jié)點當選簇頭。簇頭將普通節(jié)點收集到的數(shù)據(jù)進行處理、整合,以數(shù)據(jù)包的形式發(fā)送到基站。從收益角度來說,如果一個節(jié)點選擇當普通節(jié)點時,又有其他至少一個節(jié)點成為簇頭,那么這個節(jié)點的收益是v,可以認為其是數(shù)據(jù)成功轉發(fā)到基站帶來的收益。如果節(jié)點選擇當選簇頭,那么它的收益是v-c,其中c是當選簇頭的損耗,由于簇頭往往會收集整合多個普通節(jié)點發(fā)送給自己的數(shù)據(jù),因此需要消耗較多的能量。同時,為防止沒有節(jié)點成為簇頭而導致普通節(jié)點收集到的數(shù)據(jù)無法轉發(fā)情況,引入懲罰機制[12-13],r可以認為是對普通節(jié)點的懲罰,則節(jié)點選擇做普通節(jié)點的收益為v-r。

首先討論只有2個參與者的情況,節(jié)點的收益如表1所示。

表1 兩節(jié)點博弈收益

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

(3)

則有如下結論:

1)當所有節(jié)點都選擇當選簇頭時,此時的決策S={CH,CH,…,CH}不是一個納什均衡。

2)當所有節(jié)點都選擇當普通節(jié)點時,此時的決策S={CM,CM,…,CM}不是一個納什均衡。

為平衡節(jié)點的能耗,希望能量較充足且損耗更低的節(jié)點能夠更大可能性地充當簇頭,從而使能量較少的節(jié)點不會過早地消耗完能量,影響網(wǎng)絡的覆蓋范圍。節(jié)點當選簇頭的損耗和節(jié)點剩余能量有關,若節(jié)點的剩余能量較高,那么充當簇頭的損耗相對較低,從而能有效地保存節(jié)點數(shù)目,延長WSN的壽命。節(jié)點成為簇頭的幾率和參數(shù)c有關,也和參加博弈的節(jié)點數(shù)目有關。假定c與v成比例關系,c與節(jié)點的剩余能量有關,剩余能量越高,損耗越小。

2.4 均衡概率計算

本文引用LGCA協(xié)議中對鄰居節(jié)點的定義和對節(jié)點通信范圍的假設。對節(jié)點i,若在博弈時選擇當選簇頭,且鄰居節(jié)點選擇當選普通節(jié)點的決策,則節(jié)點i成為簇頭的損耗可表示如下:

(4)

其中,k>1,Eres是節(jié)點當選簇頭時的剩余能量。由于節(jié)點i收益和損耗成比例,因此收益函數(shù)可計算如下:

(5)

其中,m為比例系數(shù),且m>1。在此情況下,節(jié)點i當選簇頭的收益可表示為:

(6)

節(jié)點i當選普通節(jié)點的收益可表示為:

(7)

其中,r為節(jié)點根據(jù)利己性選擇當選普通節(jié)點時做出的懲罰,它小于當選簇頭的損耗,即r

(8)

其中,N是在半徑R范圍內包括節(jié)點i在內的所有節(jié)點數(shù),N-1表示以節(jié)點i為中心,半徑為R范圍內的節(jié)點數(shù)。令w=(c-r)/(v-r),因為r

(9)

本文采用兩輪競選機制,同時在第二輪引入懲罰機制,可防止無限迭代現(xiàn)象的發(fā)生。如果簇頭在首輪就競選成功,則任意節(jié)點i的平均收益可計算如下:

vPr{si=ND∩?js.t.sj=D,j≠i}=

(v-c)p+v(1-p)(1-(1-p)N-1)?

(10)

(11)

如果首輪未競選出簇頭,則自動進入第二輪,同時引入懲罰值r,則選擇當選普通節(jié)點決策的節(jié)點收益為v-r,由此,任意節(jié)點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),使得該方程有解。但是,可以根據(jù)一輪競選時的最大平均收益做出推斷,即當節(jié)點個數(shù)趨近于無窮大時,最大平均收益趨近于v-c。除此之外,可以考慮是否存在最優(yōu)解的情況。因為本文對博弈參與者不做區(qū)分,所以最優(yōu)解的情況應該是在半徑R內,每輪競選有且只有一個節(jié)點選擇成為簇頭,而其余節(jié)點選擇當選普通節(jié)點。在此情況下的平均收益為:

(13)

當節(jié)點個數(shù)N趨于無窮大時:

(14)

(15)

通過分析可知,PoA的值只和節(jié)點選擇成為簇頭的損耗c和選擇成為普通節(jié)點時受到的懲罰r有關,而和收益v不相關。當N=2時,PoA有最小值,相反,當節(jié)點個數(shù)無窮大時,PoA有最大值。

PoAmin=(c-r)/2

(16)

PoAmax=c-r

(17)

無論節(jié)點的數(shù)量如何變化,PoA的值總是在區(qū)間[(c-r)/2,(c-r)]內。

3 兩輪競選分簇協(xié)議

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

圖3 簇頭競選流程

3.1 節(jié)點初始化階段

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

3.2 候選簇頭階段

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

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

(18)

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

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

3.3 真正簇頭階段

由于在前一個子階段的候選簇頭競選中,可能存在多個簇頭互為鄰居節(jié)點的情況[16],從而導致簇頭分布不均。為避免這個問題,引入最后的簇頭選舉子階段。另外,如果一個剩余能量較少的候選簇頭被選為最終的簇頭,則該節(jié)點會提前耗盡能量,產(chǎn)生能量空洞,且影響網(wǎng)絡整體的壽命。因此,剩余能量較多的候選節(jié)點有較大的概率當選最終的簇頭。

針對上述問題,本文提出一種迭代算法,根據(jù)節(jié)點剩余能量和損耗選擇真正簇頭,達到能耗均衡的目的。對于任何處于候選狀態(tài)的簇頭節(jié)點i,如果沒有相鄰的候選簇頭,即設置的NTCH(i)是空集,則它將自動成為最終的簇頭并廣播最終簇頭選舉消息“CH_msg2”(包括節(jié)點ID、簇頭狀態(tài)和節(jié)點剩余能量)。如果設置NTCH(i)不是空集,則候選簇頭節(jié)點i將嘗試執(zhí)行多次迭代以選擇最終的簇頭,最大迭代次數(shù)可計算如下:

(19)

其中,NTCH(i)是除節(jié)點i外的鄰居候選簇頭節(jié)點的集合,則|NTCH(i)|是集合NTCH(i)中的元素個數(shù),即節(jié)點i的鄰居候選簇頭節(jié)點的個數(shù)。為方便迭代過程的描述,將整個網(wǎng)絡中需要進行迭代的候選簇頭看做一個集合,記為STCH,則:

STCH={i|i∈ATCH,NTCH(i)≠?}

(20)

其中,ATCH為所有候選簇頭的集合。

在迭代過程中,集合STCH中的每個節(jié)點仍然處于候選簇頭狀態(tài),每個節(jié)點與鄰居節(jié)點相比較,從而在以自己為中心且半徑為R的范圍內選出損耗最低的候選簇頭節(jié)點當選自己的簇頭。如果選擇自己當選簇頭的節(jié)點將在半徑R內廣播消息“CH_msg1”,并在下一次迭代中成為臨時的簇頭,集合ATCH中的和其相鄰的其他節(jié)點在收到消息“CH_msg1”后將返回到正常節(jié)點的狀態(tài)。選擇其他節(jié)點當選簇頭的候選簇頭節(jié)點,其狀態(tài)不變,進入下一次迭代。每次迭代完成后對集合STCH進行更新,刪除返回到正常狀態(tài)的節(jié)點。

這一子階段對候選簇頭進行迭代的算法偽代碼如下:

算法真正簇頭競選迭代算法

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 簇形成階段

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

4 仿真與結果分析

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

4.1 仿真參數(shù)設置

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

表2 仿真參數(shù)設置

4.2 結果分析

本文將在2種情況下對提出的分簇協(xié)議進行分析。首先,在不同面積的感知區(qū)域內比較CROSS、LGCA和EGTC協(xié)議的簇頭數(shù)量和感知面積的關系,感知區(qū)域的面積分別是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的感知區(qū)域,在此感知區(qū)域中,比較CROSS、LGCA和EGTC協(xié)議中博弈論次和生存節(jié)點數(shù)的關系。

圖4為不同規(guī)模網(wǎng)絡下各協(xié)議網(wǎng)絡壽命對比。從圖4可以看出,EGTC在上述多種網(wǎng)絡規(guī)模中的網(wǎng)絡壽命均優(yōu)于LGCA和CROSS協(xié)議。此外,隨著網(wǎng)絡規(guī)模的增大,3種協(xié)議的壽命都呈下降趨勢,這是因為隨著面積的增大,節(jié)點的通信損耗增加。當面積小于15 000 m2時,CROSS的壽命大于LGCA,當面積大于15 000 m2時則相反,說明LGCA更適用于大規(guī)模網(wǎng)絡。

圖4 不同規(guī)模網(wǎng)絡下各協(xié)議網(wǎng)絡壽命比較

圖5顯示了EGTC、LGCA和CROSS協(xié)議在不同規(guī)模的感知網(wǎng)絡中每輪平均簇數(shù)的差異。從圖5可以看出,隨著網(wǎng)絡面積的增大,CROSS協(xié)議的每輪平均成簇數(shù)有所下降。這是因為CROSS協(xié)議采用全局博弈的方式,傳感器節(jié)點數(shù)隨著網(wǎng)絡面積的增大而增加,而該協(xié)議中節(jié)點的均衡概率p是衰減函數(shù),所以簇頭數(shù)量會隨著傳感器節(jié)點數(shù)量的增加而減少。LGCA和EGTC協(xié)議中平均簇數(shù)隨著網(wǎng)絡面積增大而緩慢增長,這是因為盡管網(wǎng)絡面積逐漸增大,但是網(wǎng)絡中節(jié)點的通信半徑也隨之增大,如圖6所示。在一定程度上,通信半徑的增大減緩了平均簇數(shù)量的增長速度。

圖5 不同規(guī)模網(wǎng)絡下各協(xié)議平均成簇數(shù)量比較

圖6 不同規(guī)模網(wǎng)絡下的節(jié)點通信半徑比較

為突出本文協(xié)議的特點,圖7顯示了當感知區(qū)域面積為100 m×100 m時,CROSS、LGCA和HGTD在每輪中存活的節(jié)點數(shù)比例。從圖7可以看出,EGTC的曲線斜率最大,即網(wǎng)絡中各節(jié)點能量耗盡的時間差較小,說明EGTC協(xié)議很好地平均了各個節(jié)點的能量消耗,從而解決了部分節(jié)點能量耗盡導致的能量空洞問題。

圖7 各協(xié)議存活節(jié)點數(shù)比較

5 結束語

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