無線傳感網高斯分簇路由算法的研究及實現*

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

(浙江工業大學計算機學院，杭州 310023)

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

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

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

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

1 網絡模型

在本文中，無線傳感器網絡節點具有如下性質:傳感器節點隨機地均勻分布在目標區域范圍內，網絡運行過程中均處于靜止狀態;傳感器節點結構相同，所有傳感器節點具有相同的功能和屬性;傳感器節點能夠計算出自己當前的剩余能量，并具備數據融合功能;基站與每個傳感器節點都可以直接通信，且基站位置固定，能量不受限。

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

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

成員節點將監測數據發送到簇頭，簇頭節點對數據進行融合后發送到基站。數據融合單位bit數據消耗的能量為

其中Edf表示融合單位bit數據所消耗的能量。

2 簇頭選擇機制

2.1 網絡最優化覆蓋

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

在網絡覆蓋過程中，簇頭節點以“蜂窩”狀的正六邊形形式分布最優［11］，在這種網絡模型下，網絡的重復覆蓋率最低并且無覆蓋漏洞，以較少的簇頭節點達到較高的網絡覆蓋率。如圖1所示。

圖1 網絡最優覆蓋

設網絡中每個簇的半徑為R，則簇頭之間的最優距離應為R，即與已知簇頭之間的距離為R的目標節點優先當選簇頭。因此，優先選取距離已知簇頭R圓上的節點當選簇頭是這一模型得以實現的重要保證。

2.2 LEACH和CMCRP簇頭選取機制

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

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

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

通過對簇頭選擇閾值的改進，CMCRP延長了網絡生存周期。但節點距離已知簇頭越遠，當選簇頭的概率越高，從而使得距離已知簇頭較遠的低能量節點當選簇頭的概率高于距離已知簇頭節點較近的高能量節點當選簇頭的概率，使得高能量節點喪失了競爭力。

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

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

3.1 簇頭距離因素

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

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

圖2 簇頭選取示意圖

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

即以目標簇頭節點與已知簇頭節點的距離d為參數，簇頭之間的最優距離R為均值，其函數曲線如圖3所示。

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

該概率閾值函數依然保留了高斯分布概率密度函數的性質。在d=R處概率最大。σ值一定的情況下，距離在最優目標簇頭節點所在圓的兩側范圍內滿足f(R)≥f(R±Δd)。目標簇頭節點與已知簇頭之間的距離與最優距離的差值越小，即‖d－R‖越小，目標節點當選簇頭的概率越大，即與已知簇頭節點的距離越接近最優距離的目標節點當選簇頭的概率越大，滿足網絡最優化覆蓋的條件。

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

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

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

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

3.2 能量因素

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

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

其中，Eresidual表示當前節點的剩余能量，Nsum表示在概率帶范圍內未被覆蓋的存活節點的個數，Esum表示該Nsum個節點的總剩余能量。改進后的閾值公式為:

改進后的閾值公式使得剩余能量較高且位置較優的節點優先當選簇頭，既保證簇頭節點的均勻分布，又保證簇頭節點的剩余能量，均衡網絡的整體能量消耗。

3.3 算法流程

在GCRA算法中，首先根據網絡的規模和節點的數量選定適當的節點基本通信范圍R和控制概率帶寬度的σ的值。

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

圖4 算法流程圖

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

4 仿真實現

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

表1 仿真數據參數

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

圖5 簇頭節點分布圖

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

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

圖6 網絡剩余節點個數

表2 節點死亡時刻表

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

圖7給出了三種算法的網絡平均剩余能量的比較情況。可以看出，MPDFR算法節點的平均剩余能量比LEACH和CMCRP算法均有顯著的提高。CMCRP算法雖然在簇頭選取的過程中加入了擬物力的思想，距離已知簇頭越遠的節點當選簇頭的概率越大，沒有考慮到節點剩余能量的因素使得能量較低的節點當選簇頭，節點的能量消耗得不到有效均衡，加快了節點的死亡。圖8則反映了三種算法基站接收到的數據量的比較情況，GCRA算法接收到的數據量遠遠大于LEACH協議和CMCRP協議，是CMCRP協議接收數據量的近兩倍。

圖7 節點平均剩余能量

圖8 基站接收數據包

5 結束語

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

［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］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2006.

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

［5］趙強利，蔣艷凰，徐明.無線傳感器網絡路由協議的分析與比較［J］.計算機科學，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，Fahmy 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］盧強，何熊熊，馮遠靜，等.基于競爭機制的無線傳感器網絡分簇路由協議［J］.傳感技術學報，2010，23(2):245－250.

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

［12］李忠范，高文森.應用數理統計［M］.北京:高等教育出版社，2009.

［13］王微，馮靜遠，俞立.一種高效的無線傳感器網絡路由協議設計［J］.傳感技術學報，2008，21(12):2061－2066.