無線傳感網(wǎng)高斯分簇路由算法的研究及實現(xiàn)*

陳寧寧，俞 立，洪 榛，張貴軍

(浙江工業(yè)大學(xué)計算機(jī)學(xué)院，杭州 310023)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)［1－4］是一種集傳感器技術(shù)、計算機(jī)技術(shù)和無線通信技術(shù)的新型無線網(wǎng)絡(luò)。它由部署在監(jiān)測區(qū)域的大量的傳感器節(jié)點組成，通過自組織的方式協(xié)同工作，以獲取惡劣環(huán)境下的外部物理信息。由于傳感器節(jié)點的能量有限并且部署之后難以再次補充，降低傳感器節(jié)點的能量消耗成為延長網(wǎng)絡(luò)生存周期的重要方法。而節(jié)點的能量消耗與網(wǎng)絡(luò)的路由算法又息息相關(guān)，因此對無線傳感器網(wǎng)絡(luò)路由算法的研究具有非常重要的現(xiàn)實意義。

優(yōu)化路由協(xié)議是均衡節(jié)點能量消耗的主要途徑。針對無線傳感器網(wǎng)絡(luò)路由的特點，國內(nèi)外的專家與學(xué)者提出了一些適合無線傳感器網(wǎng)絡(luò)的路由協(xié)議。這些路由協(xié)議的設(shè)計模式大致可以分為以下幾類［5］:泛洪式路由協(xié)議、層次式路由協(xié)議、以數(shù)據(jù)為中心的路由協(xié)議、基于位置信息的路由協(xié)議和基于QoS的路由協(xié)議。在層次式路由協(xié)議中，簇頭的選取應(yīng)同時滿足三個條件:簇頭節(jié)點有足夠的剩余能量來保證數(shù)據(jù)傳遞;簇頭與簇內(nèi)節(jié)點間距離在正常通信距離之內(nèi);簇頭節(jié)點間距離不會太近。由于分簇路由具有拓?fù)浣Y(jié)構(gòu)簡單、易于維護(hù)適合大規(guī)模網(wǎng)絡(luò)等特點，一直是無線傳感器網(wǎng)絡(luò)路由研究的熱點。

LEACH協(xié)議［6］作為最早提出分簇路由算法的協(xié)議，有效地降低了網(wǎng)絡(luò)能耗，延長了網(wǎng)絡(luò)生命。但LEACH協(xié)議在選取簇頭時沒有考慮目標(biāo)節(jié)點的剩余能量的因素，也不能避免簇頭節(jié)點因相距較近產(chǎn)生的重簇現(xiàn)象。HEED［7］、TEEN［8］和 PEGASIS［9］等分簇路由協(xié)議在LEACH協(xié)議的基礎(chǔ)上進(jìn)行了改進(jìn)。HEED通過迭代的方式選取簇頭，增大了簇頭與基站通信的能量消耗;TEEN中的屬性值若一直達(dá)不到軟硬門限用戶將接收不到網(wǎng)絡(luò)的任何數(shù)據(jù);PEGASIS協(xié)議在大規(guī)模網(wǎng)絡(luò)中易增大網(wǎng)絡(luò)數(shù)據(jù)傳輸時延，成簇開銷非常大，不適合實際應(yīng)用。由盧強(qiáng)等提出的CMCRP算法［10］將節(jié)點之間的距離作為簇頭選取的參考因素，但目標(biāo)節(jié)點當(dāng)選簇頭的概率隨著與已知簇頭距離的增大而增大，使得距離適合的能量較大的目標(biāo)節(jié)點失去了競爭力。

針對以上情況，本文提出一種高斯分布分簇路由算法(GCRA)。在簇頭選取過程中充分考慮目標(biāo)簇頭節(jié)點的剩余能量以及簇頭之間的最優(yōu)距離，保證簇頭節(jié)點的均勻分布。節(jié)點根據(jù)通信代價最小的原則選取距離自己最近的簇頭節(jié)點作為其最終簇頭，均衡簇頭節(jié)點的負(fù)載，延長網(wǎng)絡(luò)的生存周期。

1 網(wǎng)絡(luò)模型

在本文中，無線傳感器網(wǎng)絡(luò)節(jié)點具有如下性質(zhì):傳感器節(jié)點隨機(jī)地均勻分布在目標(biāo)區(qū)域范圍內(nèi)，網(wǎng)絡(luò)運行過程中均處于靜止?fàn)顟B(tài);傳感器節(jié)點結(jié)構(gòu)相同，所有傳感器節(jié)點具有相同的功能和屬性;傳感器節(jié)點能夠計算出自己當(dāng)前的剩余能量，并具備數(shù)據(jù)融合功能;基站與每個傳感器節(jié)點都可以直接通信，且基站位置固定，能量不受限。

參考LEACH協(xié)議的能量模型，節(jié)點的能量消耗由發(fā)射電路的能量消耗和功率放大器能量消耗兩部分組成，即如果某一節(jié)點要發(fā)送kbits的數(shù)據(jù)包到距離為d的另一節(jié)點，則該節(jié)點所要消耗的能量模型為:

其中，Eelec表示發(fā)射和接收單位bit數(shù)據(jù)發(fā)射電路消耗的能量。當(dāng)d＜do時，使用放大單位bit數(shù)據(jù)消耗能量為Efs的信號功率放大器，當(dāng)d≥do時使用放大單位bit數(shù)據(jù)消耗能量為Emp的信號功率放大器。節(jié)點接收kbits數(shù)據(jù)的接收電路所消耗的能量模型為:

成員節(jié)點將監(jiān)測數(shù)據(jù)發(fā)送到簇頭，簇頭節(jié)點對數(shù)據(jù)進(jìn)行融合后發(fā)送到基站。數(shù)據(jù)融合單位bit數(shù)據(jù)消耗的能量為

其中Edf表示融合單位bit數(shù)據(jù)所消耗的能量。

2 簇頭選擇機(jī)制

2.1 網(wǎng)絡(luò)最優(yōu)化覆蓋

在分簇路由協(xié)議中，簇頭節(jié)點均勻分布具有以下優(yōu)點:保證每個簇的大小盡量均等;平衡普通節(jié)點與簇頭節(jié)點的能量消耗;降低網(wǎng)絡(luò)的簇內(nèi)通信代價。在成簇過程中，若簇頭節(jié)點距離基站較遠(yuǎn)并且成員節(jié)點距離其所屬簇頭也較遠(yuǎn)，則節(jié)點與簇頭均需消耗較大的能量以維持通信，大大增加整個網(wǎng)絡(luò)的能量消耗。簇頭節(jié)點均勻分布使得各個節(jié)點均可以較小的通信代價與簇頭保持通信，均衡網(wǎng)絡(luò)的能量消耗。因此，在成簇過程中將簇頭的均勻分布作為簇頭選取的重要衡量標(biāo)準(zhǔn)。

在網(wǎng)絡(luò)覆蓋過程中，簇頭節(jié)點以“蜂窩”狀的正六邊形形式分布最優(yōu)［11］，在這種網(wǎng)絡(luò)模型下，網(wǎng)絡(luò)的重復(fù)覆蓋率最低并且無覆蓋漏洞，以較少的簇頭節(jié)點達(dá)到較高的網(wǎng)絡(luò)覆蓋率。如圖1所示。

圖1 網(wǎng)絡(luò)最優(yōu)覆蓋

設(shè)網(wǎng)絡(luò)中每個簇的半徑為R，則簇頭之間的最優(yōu)距離應(yīng)為R，即與已知簇頭之間的距離為R的目標(biāo)節(jié)點優(yōu)先當(dāng)選簇頭。因此，優(yōu)先選取距離已知簇頭R圓上的節(jié)點當(dāng)選簇頭是這一模型得以實現(xiàn)的重要保證。

2.2 LEACH和CMCRP簇頭選取機(jī)制

在LEACH協(xié)議簇頭選取過程中，目標(biāo)節(jié)點隨機(jī)生成一個取值范圍為0～1的小數(shù)，同時節(jié)點根據(jù)自身的閾值函數(shù)生成閾值Pi(t)，若隨機(jī)數(shù)小于閾值，則該節(jié)點當(dāng)選為簇頭。Pi(t)的計算公式為:

其中，p表示簇頭節(jié)點所占比例，r表示當(dāng)前循環(huán)的輪數(shù)，n表示的是第n個節(jié)點，G表示最近1/p輪中仍未當(dāng)選簇頭的節(jié)點集合。LEACH協(xié)議有效降低了網(wǎng)絡(luò)能耗，延長了網(wǎng)絡(luò)生存周期，但仍存在一些缺陷:簇頭節(jié)點的分布不能保證均勻;各個節(jié)點與基站的距離均不相等。從而在數(shù)據(jù)傳輸階段能量消耗不能滿足均等消耗。

CMCRP協(xié)議通過引入擬物力的思想把已產(chǎn)生的簇頭節(jié)點看做是通信半徑為R的“簇頭圓盤”，設(shè)參與簇頭選擇并未被“簇頭圓盤”覆蓋的目標(biāo)節(jié)點對其鄰近的“簇頭圓盤”具有吸引力，而已經(jīng)被“簇頭圓盤”覆蓋的目標(biāo)節(jié)點受“屏蔽效應(yīng)”的影響對“簇頭圓盤”不具有吸引力。參照萬有引力引入“屏蔽效應(yīng)”。改進(jìn)后的簇頭閾值為:

通過對簇頭選擇閾值的改進(jìn)，CMCRP延長了網(wǎng)絡(luò)生存周期。但節(jié)點距離已知簇頭越遠(yuǎn)，當(dāng)選簇頭的概率越高，從而使得距離已知簇頭較遠(yuǎn)的低能量節(jié)點當(dāng)選簇頭的概率高于距離已知簇頭節(jié)點較近的高能量節(jié)點當(dāng)選簇頭的概率，使得高能量節(jié)點喪失了競爭力。

由以上分析可知，LEACH算法沒有考慮節(jié)點的剩余能量因素，對其改進(jìn)的CMCRP也沒有保證簇頭節(jié)點均勻分布。對于以上算法的缺陷和不足，本文提出一種高斯分簇路由算法。

3 高斯分簇路由算法(GCRA)

3.1 簇頭距離因素

在高斯分簇路由算法的模型中，將簇頭節(jié)點的均勻分布作為簇頭選取的重要因素。

如圖2所示，已知節(jié)點A已經(jīng)被選為簇頭節(jié)點，節(jié)點B、C、D、E、F和G均有可能成為下一個簇頭節(jié)點。若簇頭的基本通信范圍為R，根據(jù)網(wǎng)絡(luò)最優(yōu)化覆蓋原理，下一個簇頭的最優(yōu)位置應(yīng)該在與簇頭A的距離為R的圓上，即節(jié)點B所在的圓上。但在實際應(yīng)用中，節(jié)點B可能由于剩余能量太低而不滿足當(dāng)選簇頭的要求，或者在半徑為R的圓上恰好沒有節(jié)點，則與簇頭節(jié)點A的距離在區(qū)間(R－ΔdR+Δd)上的節(jié)點C和D就成為次優(yōu)目標(biāo)簇頭節(jié)點，從而在簇頭節(jié)點A的周圍形成了一條寬度為2Δd的圓環(huán)。在簇頭選取過程中，處于圓環(huán)中的所有節(jié)點組成的概率帶形成下一個簇頭節(jié)點的最優(yōu)目標(biāo)區(qū)域。不在概率帶上的節(jié)點E和F為最差目標(biāo)簇頭。為避免重簇現(xiàn)象的出現(xiàn)，節(jié)點G不應(yīng)當(dāng)選簇頭。

圖2 簇頭選取示意圖

要滿足節(jié)點B當(dāng)選簇頭的概率最大、節(jié)點C、D次之、節(jié)點E、F最小、節(jié)點G為0的條件，剛好滿足高斯分布概率密度函數(shù)的性質(zhì)。由此本文引入高斯分布概率密度函數(shù)作為簇頭選取的閾值函數(shù)。當(dāng)選簇頭的概率閾值函數(shù)為:

即以目標(biāo)簇頭節(jié)點與已知簇頭節(jié)點的距離d為參數(shù)，簇頭之間的最優(yōu)距離R為均值，其函數(shù)曲線如圖3所示。

圖 3 概率閾值函數(shù)(σ1＜σ2＜σ3)

該概率閾值函數(shù)依然保留了高斯分布概率密度函數(shù)的性質(zhì)。在d=R處概率最大。σ值一定的情況下，距離在最優(yōu)目標(biāo)簇頭節(jié)點所在圓的兩側(cè)范圍內(nèi)滿足f(R)≥f(R±Δd)。目標(biāo)簇頭節(jié)點與已知簇頭之間的距離與最優(yōu)距離的差值越小，即‖d－R‖越小，目標(biāo)節(jié)點當(dāng)選簇頭的概率越大，即與已知簇頭節(jié)點的距離越接近最優(yōu)距離的目標(biāo)節(jié)點當(dāng)選簇頭的概率越大，滿足網(wǎng)絡(luò)最優(yōu)化覆蓋的條件。

根據(jù)高斯分布的性質(zhì)［12］，隨機(jī)變量落在橫軸區(qū)間(μ－2.58σ，μ+2.58σ)內(nèi)的面積占總面積的比例約為99%。

由圖3可知，節(jié)點當(dāng)選簇頭的概率隨著與最優(yōu)距離的差值的增大而逐漸降低，趨近于0。由于事件發(fā)生的概率低于1%為小概率事件，為了降低算法的時間復(fù)雜度，在簇頭選取過程中引入最小概率閾值Pmin=0.01，概率低于Pmin的節(jié)點在本輪中不再競爭簇頭，設(shè)定Prob(d=R+Δd)=Pmin，這樣使得概率大于Pmin的節(jié)點落于候選概率帶范圍之內(nèi)，這樣就將簇頭的選取范圍劃定在了寬度為2Δd的圓環(huán)內(nèi)。

假設(shè)節(jié)點在檢測范圍內(nèi)大致均勻分布，網(wǎng)絡(luò)最終形成N個簇，網(wǎng)絡(luò)面積為S，在選取簇頭的過程中，對于任一簇頭，其所在簇的半徑為R，簇的面積為πR2。由高斯分布的性質(zhì)可知，概率帶之外的其他節(jié)點當(dāng)選簇頭的概率遠(yuǎn)遠(yuǎn)小于Pmin趨近于0，若把這些節(jié)點也選定為候選節(jié)點將大大提高算法的時間復(fù)雜度，因此將剩下的S－πR2區(qū)域劃分N－1個簇，在每個候選區(qū)域內(nèi)選取簇頭，則每個簇頭的平均候選面積為(S－πR2)/(N－1)，而由圖2可知候選區(qū)域的面積，因此有:

由圖3可知，σ的值越大，概率大于Pmin的節(jié)點形成的概率帶的寬度也就越大，候選節(jié)點越多;反之亦然。由式(10)可知σ的值與網(wǎng)絡(luò)的簇的數(shù)量息息相關(guān)，由于節(jié)點的通信半徑一定，因此應(yīng)根據(jù)網(wǎng)絡(luò)的大小來選取合適的簇的數(shù)量使得每個簇頭的承受得到均衡。

3.2 能量因素

LEACH算法在簇頭選取的過程中沒有考慮目標(biāo)節(jié)點的剩余能量，使得低能量節(jié)點具有與高能量節(jié)點相同的概率當(dāng)選簇頭，加速節(jié)點的死亡。

本算法在成簇過程中將節(jié)點的剩余能量和目標(biāo)節(jié)點的平均能量作為簇頭選取的參考因素，優(yōu)先選取剩余能量高于平均能量的目標(biāo)節(jié)點當(dāng)選簇頭，使得高能量節(jié)點更具競爭力。對簇頭選取閾值prob引入能量閾值模型:

其中，Eresidual表示當(dāng)前節(jié)點的剩余能量，Nsum表示在概率帶范圍內(nèi)未被覆蓋的存活節(jié)點的個數(shù)，Esum表示該Nsum個節(jié)點的總剩余能量。改進(jìn)后的閾值公式為:

改進(jìn)后的閾值公式使得剩余能量較高且位置較優(yōu)的節(jié)點優(yōu)先當(dāng)選簇頭，既保證簇頭節(jié)點的均勻分布，又保證簇頭節(jié)點的剩余能量，均衡網(wǎng)絡(luò)的整體能量消耗。

3.3 算法流程

在GCRA算法中，首先根據(jù)網(wǎng)絡(luò)的規(guī)模和節(jié)點的數(shù)量選定適當(dāng)?shù)墓?jié)點基本通信范圍R和控制概率帶寬度的σ的值。

簇頭選取過程完成后，當(dāng)選為簇頭的節(jié)點設(shè)定時間片并接收入簇請求，同時，未當(dāng)選簇頭的節(jié)點根據(jù)本地的簇頭信息表選取距離最近的簇頭發(fā)送入簇請求。簇頭時間片到后，簇頭節(jié)點對接收到的入簇請求進(jìn)行信息處理，分配簇內(nèi)節(jié)點TDMA時間表，以R為通信半徑在簇內(nèi)廣播成簇信息。各個成員節(jié)點根據(jù)接收到的成簇信息判斷入簇結(jié)果，然后根據(jù)接收到的TDMA時間表向簇頭節(jié)點發(fā)送監(jiān)測數(shù)據(jù)。簇頭節(jié)點將接收到的數(shù)據(jù)包進(jìn)行數(shù)據(jù)融合后發(fā)送到基站。算法實現(xiàn)流程圖如圖4所示。

圖4 算法流程圖

普通節(jié)點選擇距離最近的簇頭節(jié)點為最終簇頭并請求入簇，簇頭節(jié)點向簇內(nèi)成員節(jié)點一次性廣播簇信息，避免了簇頭節(jié)點與成員節(jié)點之間一對一的通信，有效降低簇頭的能量消耗，均衡各個節(jié)點的能量消耗。

4 仿真實現(xiàn)

本文采用MATLAB仿真平臺對LEACH、CMCRP以及GCRA進(jìn)行仿真比較，以評價GCRA算法的性能。仿真參數(shù)［6］如下表1所示。

表1 仿真數(shù)據(jù)參數(shù)

本文主要選取剩余節(jié)點個數(shù)、網(wǎng)絡(luò)平均剩余能量和基站接收信息量來比較三種算法的性能。在不考慮其他外界因素干擾的情況下，節(jié)點的能量等于零時視為死亡。網(wǎng)絡(luò)生存周期為第一個節(jié)點的死亡時間。三種算法各進(jìn)行仿真實驗50次取平均值。

圖5 簇頭節(jié)點分布圖

圖5為在GCRA算法仿真過程中某次組網(wǎng)時簇頭節(jié)點的基本分布示意圖，從圖中可以看出，網(wǎng)絡(luò)共生成9個簇，與設(shè)置的目標(biāo)數(shù)量10個基本相符，且簇頭節(jié)點分布均勻，簇頭之間的距離滿足GCRA路由協(xié)議的定義，滿足網(wǎng)絡(luò)全局覆蓋的要求。

圖6是三種路由算法在每一輪循環(huán)中剩余節(jié)點個數(shù)的對比情況。具體各個時刻節(jié)點死亡時間如表2所示。

圖6 網(wǎng)絡(luò)剩余節(jié)點個數(shù)

表2 節(jié)點死亡時刻表

顯然，該圖反映了GCRA算法在降低能耗延長網(wǎng)絡(luò)生命周期上的優(yōu)越性。第一個節(jié)點死亡時，CMCRP算法運行了126輪，LEACH算法運行了103輪，而GCRA算法已經(jīng)運行了166輪。GCRA算法的網(wǎng)絡(luò)生存周期比 LEACH算法提高了61%，比CMCRP算法提高了31.7%，并且從曲線的斜率可知，相對于LEACH和CMCRP協(xié)議，GCRA算法每個節(jié)點的網(wǎng)絡(luò)負(fù)載均衡得到明顯地提高。

圖7給出了三種算法的網(wǎng)絡(luò)平均剩余能量的比較情況?？梢钥闯?，MPDFR算法節(jié)點的平均剩余能量比LEACH和CMCRP算法均有顯著的提高。CMCRP算法雖然在簇頭選取的過程中加入了擬物力的思想，距離已知簇頭越遠(yuǎn)的節(jié)點當(dāng)選簇頭的概率越大，沒有考慮到節(jié)點剩余能量的因素使得能量較低的節(jié)點當(dāng)選簇頭，節(jié)點的能量消耗得不到有效均衡，加快了節(jié)點的死亡。圖8則反映了三種算法基站接收到的數(shù)據(jù)量的比較情況，GCRA算法接收到的數(shù)據(jù)量遠(yuǎn)遠(yuǎn)大于LEACH協(xié)議和CMCRP協(xié)議，是CMCRP協(xié)議接收數(shù)據(jù)量的近兩倍。

圖7 節(jié)點平均剩余能量

圖8 基站接收數(shù)據(jù)包

5 結(jié)束語

本文提出了一種高斯分布分簇路由協(xié)議(GCRA)。在簇頭選取過程中將高斯分布概率密度函數(shù)模型應(yīng)用其中，結(jié)合目標(biāo)節(jié)點的剩余能量，優(yōu)先選取與已知簇頭距離最優(yōu)且剩余能量較高的節(jié)點當(dāng)選簇頭。仿真實驗證明，GCRA算法比LEACH和CMCRP路由算法更具優(yōu)越性，有效地解決了LEACH的能量缺陷和CMCRP簇頭選取的不足，均衡節(jié)點的能量消耗，延長網(wǎng)絡(luò)生命周期。

［1］Yick J，Mukherjee B，Ghosal D.Wireless Sensor Network Survey［J］.Computer Networks，2008，52(12):2292－2330.

［2］Al-Karaki J N，Kamal A E.Routing Techniques in Wireless Sensor Networks:A Survey［J］.Wireless Communications，2004，11(6):6－28.

［3］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2006.

［4］Akyildiz IF，SuW，Sankarasubramaniam Y.WirelessSensor Networks:A Survey［J］.Computer Networks，2002，38(4):393－422.

［5］趙強(qiáng)利，蔣艷凰，徐明.無線傳感器網(wǎng)絡(luò)路由協(xié)議的分析與比較［J］.計算機(jī)科學(xué)，2009，36(2):35－41.

［6］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［7］Youni O，F(xiàn)ahmy S.HEED:A Hybrid，Energy-Efficient，Distributed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Transactions on Mobile Computing，2004，3(4):366－379.

［8］Manjeshwar A，Agrawal D P.TEEN:A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks［C］//Proceedings of 15th IEEE International Parallel and Distributed Processing Symposium，San Francisco，2001，2009－2015.

［9］Lindsey S，Raghavendra C S.PEGASIS:Power Efficient Gathering in Sensor Information Systems［C］//Proceedings of the IEEE Aerospace Conference.Los Angeles，2002，1125－1130.

［10］盧強(qiáng)，何熊熊，馮遠(yuǎn)靜，等.基于競爭機(jī)制的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.傳感技術(shù)學(xué)報，2010，23(2):245－250.

［11］趙仕俊，張朝暉.無線傳感器網(wǎng)絡(luò)正六邊形節(jié)點覆蓋模型研究［J］.計算機(jī)工程，2010，36(20):113－115.

［12］李忠范，高文森.應(yīng)用數(shù)理統(tǒng)計［M］.北京:高等教育出版社，2009.

［13］王微，馮靜遠(yuǎn)，俞立.一種高效的無線傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計［J］.傳感技術(shù)學(xué)報，2008，21(12):2061－2066.