基于分級鄰近節點的無線傳感器網絡分簇路由算法

李洪兵,劉子路,陳 強,2,劉 莎,劉小龍,梁裕巧,楊 震,陳立萬

(1.三峽庫區地質環境監測與災害預警協同創新分中心,重慶 404120;2.智能信息處理與控制重慶高校市級重點實驗室,重慶 404120; 3.物聯網與智能控制技術重慶市工程研究中心,重慶 404120)

0 概述

隨著泛在信息社會的到來,無線傳感器網絡[1](Wireless Sensor Network,WSN)已成為目前研究的熱點之一,其通常由大量的低能耗低成本的微型傳感器節點構成,通過這些傳感器組成無線網絡實現對各種環境的監控。作為泛在信息社會的基礎,無線傳感器網絡被應用于軍事領域、醫療領域、安防領域、智能家居[2]領域等。然而,其有限的能量資源和惡劣的環境為無線傳感器網絡的應用帶來了巨大的挑戰[3]。其中,網絡的生存周期是無線傳感器網絡的主要問題,嚴重影響著網絡的服務質量,因此,高效的路由協議[4]成為目前重要的研究方向。

無線傳感器網絡的路由協議根據拓撲結構可以分為平面路由協議[5]和層次路由協議[6]。平面路由協議中節點間沒有等級劃分且作用相同,然而網絡中節點間距離比較小使得同一范圍內節點的采集數據出現了大量重疊,在信息傳輸時浪費了大量能量[7],同時其網絡拓補靈活性也很差,隨著無線傳感器網絡規模的擴大,這些問題更加嚴重,導致平面路由協議不再適合大規模網絡,層次路由協議[8]開始占據主導地位。層次路由協議是將網絡分為不同層次的簇,由簇首管理簇群,同時可以采用輪循的方式優化簇的形成。其中LEACH[8-11](Low Energy Adaptive Clustering Hierarchy)協議是第一個層次性路由協議,通過根據概率選取簇首,并依據簇首建立簇群的方式將整個網絡分成了多個子網絡。

本文提出一種基于分級鄰近節點的分簇路由(Clustering Routing Based on Hierarchical Neighbor Nodes,CRBHNN)算法。該算法考慮鄰近節點狀態對初步選取的簇首進行再優化,節點間通信采用中繼的方式,選取中繼節點對數據傳輸路徑進行優化,以避免遠處孤立節點能耗過大的問題,同時通過中繼節點的選取均衡網絡能耗。

1 相關研究

在所有的分簇路由協議中,LEACH協議是第一個層次型路由協議,其輪循成簇的思想被諸多層次型路由協議所引用。

PROPOSED[12]協議是一種基于粒子群算法聚類的路由協議,該協議通過粒子群算法先對網絡節點進行聚類分簇,再對已形成的簇群進行簇首選取,仿真結果表明該協議提高了網絡的能量利用率,延長了網絡壽命。然而先成簇后選取簇首的操作使得簇首成為其鄰近節點的最優簇首,但未必是其他簇群成員節點的最優簇首,本文通過先選取簇首再成簇的方式,優化簇群的形成來提高簇首的優越性。NR-LEACH[13]協議是一種基于節點排序的改進LEACH協議,該協議通過節點間路徑開銷和節點間鏈路數來確定簇首,克服了簇首依概率選取的缺點,仿真結果表明該協議延長了網絡壽命。然而,該協議過于倚重特殊節點會導致網絡能耗均衡上的劣勢,本文通過對簇首進行再選取的方式來避免簇首選取的完全隨機性,在提高網絡壽命的同時有效地均衡了網絡能耗。SEPFL[14]協議是一種基于模糊邏輯控制的分級路由協議,通過對節點到基站的位置、節點密度以及節點能量這3個變量進行模糊邏輯控制,提高了網絡壽命和吞吐量,然而因為該算法使用了模糊控制導致感知節點計算量增大,本文通過對這些變量進行分級排序來進行控制,有效地減低了感知節點的計算量。

OCRP[15]協議是一種基于最優分簇的能量異構路由協議,該協議通過最優簇首數K將待測區域劃分為K個固定分區,改進簇頭選舉機制,減少了網絡能耗,提高了網絡壽命,然而該算法的固定分區導致了整個網絡成簇的固定,一定程度上限制了網絡拓撲結構的變化,本文通過簇首的輪循選取對簇群進行調整,使簇群的形成更加多樣和靈活,有效地提高了網絡拓撲結構的靈活性。ABC[16]協議是一種基于蜂群算法的能量優化路由協議,該協議通過蜂群算法計算出傳感器網絡中能量最優的簇首節點組合,同時簇首節點輪流選擇最近的簇內節點構建路由,仿真結果表明該協議具有能量消耗速度慢、能量均衡等優點,有效地延長了無線傳感器網絡壽命,然而該算法需要整合整個網絡的信息并應用蜂群算法計算,使得該網絡需要極大的計算能力,本文通過依據概率選取簇首,并使每個節點可以借助鄰近節點信息進行分布式計算的方式,有效地降低了整個網絡的計算負載。

2 網絡模型

2.1 部署模型

場景部署模型[17-18]是由一個基站和部署在一片區域內的多個傳感器節點構成,如圖1所示,傳感器感知節點從監測區域內收集數據,然后將數據發送給基站。其中節點的位置是隨機固定的,并且每個傳感器節點都是相同的,所有的傳感器節點具有相同的初始能量,當初始能量耗盡后傳感器節點死亡,基站的能量是無限的,傳感器節點可以依據傳輸距離調整傳輸功率。

圖1 部署模型

2.2 能耗模型

本文使用一種簡單的無線電模型[19]作為能耗模型,如圖2所示,在發射數據時,節點使用發射電路發射數據,同時使用放大電路對信號進行功放;在接收數據時,節點使用接收電路接收數據。

圖2 能耗模型

傳輸[20]d距離的k比特數據的能耗ETx(k)為:

(1)

門限距離d0為:

(2)

接收k比特數據的能耗ERx(k)為:

ERx(k)=kEelec

(3)

融合k比特數據的能耗Ef(k)為:

Ef(k)=kEda

(4)

因此,節點發射控制報文的能耗ETx_CM為:

(5)

節點接收控制報文的能耗ERx_CM為:

ERx_CM=CMEelec

(6)

簇首節點接收本簇內n個簇成員節點(不經過中繼,直接向簇首通信的成員節點)的數據并融合的能耗ERx_f_CH(k,n)為:

ERx_f_CH(k,n)=nkEelec+(n+1)kEda

(7)

簇首向上一級節點發射數據的能耗ETx_CH(k)為:

(8)

成員節點向上一級節點發射數據的能耗ETx_non_CH(k)為:

(9)

中繼節點接收n個下級成員節點的數據并融合的能耗ERx_f_RE(k,n)為:

ERx_f_RE(k,n)=nkEelec+(n+1)kEda

(10)

其中,Eelec表示運行發射機和接收機(ETx和ERx)所消耗的能量,εfs和εmp分別為發射機放大器的自由空間模型和多徑衰減模型功率能耗。數據發送低于d0距離時使用自由空間模型,否則使用多徑模型,Eda為融合1 bit數據的能耗。

為了分析和驗證本文算法的優越性、有效性和合理性,從簇首分布密度、網絡能量利用率、節點剩余能量等因素對算法進行評價。

以簇首間距來映射,間距越大密度越小,n個簇首的簇首間距dCH(n)為:

(11)

第n輪后i節點剩余能量Ei_n為:

Ei_n=Ei_n-1-Ei_ues

(12)

其中,Ei_ues為節點i在本輪中消耗的能量。

以網絡剩余總能量映射,相同周期內網絡剩余總能量越大,利用率越高,網絡剩余總能量Etotal為:

Etotal=∑Ei_n

(13)

2.3 模型參數

本文仿真分析所用的模型參數如表1所示。

表1 模型參數

依據n、M、εfs和εmp可得簇首最優個數kopt[21-22]為:

(14)

其中,dtoBS為節點到基站的距離。

由n和kopt得到簇首選簇概率p為:

(15)

3 無線傳感器網絡分簇路由算法

3.1 分簇優化

3.1.1 LEACH分簇算法

經典LEACH協議是通過閾值T(n)隨機選取網絡簇首,并通過已選取的簇首形成簇群,再通過簇首調度自身簇群成員節點,最終將數據傳輸到基站,這樣網絡工作一輪。LEACH協議通過這樣不斷輪循來均衡和節約網絡能耗,延長網絡壽命。

閾值T(n)為:

(16)

其中,p為簇首在網絡總節點中存在的數量百分比,r為當前進行的輪數,G為上一個1/p輪中沒有成為過簇首的感知節點集合。

3.1.2 分簇優化思路

通過最優簇首個數kopt可以知道理想的簇群數量,假設感知區域是M×M,則理想中的最優簇群面積SCH為:

SCH=M2/kopt

(17)

進而得到理想中每個簇首節點所管理的簇群半徑R為:

(18)

本文算法中將距離某個簇首節點R0(設R0=3R/4)距離的普通節點視為一級簇群成員節點,如圖3所示。其中,A、B、C為3個簇首節點,理論上其最優簇群范圍分別對應圖3中的3個虛線線圈。可以看到,簇首A、B的一級簇群成員節點范圍(實線圈)出現了重疊區(AB區,2個實線圈的重疊部分)。通過避免這種重疊區的出現來避免簇首選取過密造成的簇群不均勻,進而提高簇首節點的工作效率。

圖3 簇首和理想簇群分布

3.1.3 分簇算法描述

算法1分簇算法

輸入n個感知節點隨機部署在M×M的感知區域上,基站位于感知區域的中心

輸出簇首分布位置和簇群成員

步驟1在每輪開始時,采取和LEACH協議相同的方法確定候選簇首,其中簇首概率為2p(避免候選簇首選取過少)。

步驟2候選簇首節點與鄰近的候選簇首節點通信,如果2個鄰近簇首節點距離小于3R/2,則表示不同簇內的一級成員節點出現重合,將其中一個候選簇首節點定為一級簇首節點,另一個定為二級簇首節點,確定一級簇首的簇成員范圍和二級簇首的簇成員范圍,其中一級成員確定有更高的優先級,即如果一個普通節點是一級簇首的成員同時也是一個二級簇首的成員,則視其為一級簇首的成員。

步驟3如果存在二級簇首的成員節點,則這些二級簇首的成員節點進行第一步操作,即再次進行候選簇首選取,新選取的候選簇首節點和已確定的一級候選簇首進行鄰近簇首間通信,根據步驟2的規則對新的候選簇首節點進行一級簇首節點和二級簇首節點的分類,同時確定相應的成員節點范圍。重復步驟3直到不存在二級簇首的成員節點或無法選出新的候選簇首節點。

步驟4確定一級簇首為優化后的最終簇首,進行成簇操作。

步驟5輪循前4步操作,實現簇首和簇群的不斷更新。

3.1.4 分簇優化仿真分析

為分析和驗證分簇優化的合理性和有效性,下面從簇首的分布位置、簇首分布密度、網絡剩余總能量分析其合理性,從網絡壽命驗證其有效性。

圖4為CRBHNN算法30輪時的簇首分布示意圖,圖4(a)為依據CRBHNN算法的初次候選簇首分布(簇首概率為2p),圖4(b)為依據CRBHNN算法優化完成后的簇首分布,圖5為LEACH算法在30輪時的簇首分布(簇首概率為p)。由圖4(b)與圖5的對比可知,LEACH算法因為簇首是完全隨機選擇的,所以造成有些簇首間相互距離過近,而CRBHNN算法將簇首的成員節點進行了分級,對某些密集的簇首進行再選舉,使得新算法得到的簇首分布更加均勻。圖6為簇首間距隨周期的變化,簇首間距映射簇首密度的變化。從圖6可以看出,實線大部分分布于虛線上方,表明CRBHNN算法生成的簇首密度明顯小于LEACH算法,驗證了圖4、圖5的分析結果,證實了CRBHNN算法生成的簇首分布更加均勻;同時圖6中周期的最后不再出現實線線條并不是CRBHNN算法沒有產生簇首,可能是只產生了一個簇首,這主要是因為大量節點死亡,存活節點過少,使得簇首出現的概率大幅下降。

圖4 CRBHNN算法在30輪時的簇首分布

圖5 LEACH算法在30輪時的簇首分布

圖6 簇首間距隨周期的變化

圖7為網絡剩余總能量隨周期的變化,網絡剩余總能量映射網絡能量利用率。由圖7可知,實線在初始時位于虛線的上方并保持較長的周期,表明CRBHNN算法在相同的周期內消耗的能量更少,證實了CRBHNN算法的網絡能量利用率比LEACH算法更高,說明CRBHNN的成簇更加合理,簇內成員通信的能耗更少;同時周期的最后實線與虛線出現相交,一部分實線處于虛線的下方,這是因為節點大量死亡后,節點成為簇首的概率大幅下降,使得一部分節點直接向基站通信,LEACH算法中這些節點集中在基站附近,RBHNN算法則分布比較均勻,表明了RBHNN算法選取的簇首更加合理,網絡能量更加均衡。

圖7 網絡剩余總能量隨周期的變化

圖8為節點生存周期。從圖8可以看出,實線在初始時位于虛線的上方并保持了很長的周期,由此可知,在CRBHNN算法中第一個節點(First Node,FND)死亡和半數節點 (Half of all Node,HND) 死亡的出現比在LEACH中更晚,這驗證了算法優化的有效性,證明CRBHNN算法的簇首選取優于LEACH算法;同時在周期的最后實線與虛線出現相交,實線出現在了虛線的下方,主要是因為節點存活過少,并且LEACH算法中存活節點大部分都分布在基站附近,進一步證明了RBHNN算法選取的簇首更加均勻,基站附近的節點選為簇首的概率大于LEACH算法。該算法優化的局限性是遠處的節點向簇首或者基站通信時會造成能耗的不必要浪費。

圖8 分簇算法節點生存周期

3.2 路由優化

3.2.1 LEACH路由優化方法

在經典的LEACH算法中,簇首節點與基站之間和成員節點與簇首之間是直接通信的,不存在中繼節點。

本文算法通過將鄰近節點進行分級來確定節點的中繼節點。將距離某個節點小于d的節點視為該節點的鄰近節點,將節點剩余能量劃分為6個等級,大于E1(E1=0.8×E0,E0為節點初始能量)的為一級,小于E1大于E2(E2=0.6×E0)的為二級,小于E2大于E3(E3=0.4×E0)的為三級,小于E3大于E4(E4=0.2×E0)的為四級,小于E4大于E5(E5=0.1×E0)的為五級,小于E5的為六級。同時將節點i的鄰近節點中所有Ei_j(Ei_j為節點i向節點j通信的能耗)與Ej_BS(Ej_BS為節點j向基站通信的能耗)的和小于Ei_BS(Ei_BS為節點i向基站通信的能耗)的節點j視為節點i的前向節點,否則視為后向節點。

3.2.2 路由算法描述

算法2路由算法

輸入n個感知節點隨機部署在M×M的感知區域上,基站位于感知區域的中心

輸出每個節點的中繼節點

步驟1節點進行鄰近節點廣播并接收鄰近節點(通過信號強度確定距離)的廣播信息。

步驟2根據鄰近節點信息確定前向節點和后向節點,同時對節點剩余能量進行分級,建立包含前后向節點標識、能量等級、節點間距離的鄰近節點信息表。

步驟3在鄰近節點中依據一定的規則確定自身的中繼節點或確定自身直接向基站通信。最小能級節點擁有一級優先權,前繼節點擁有二級優先權,自身擁有三級優先權,后繼節點擁有四級優先權,節點距離(中繼節點離自身的距離)為五級優先權,其中距離越短優選級越高。以此規則確定中繼節點,若最終確定為自身則直接向基站通信,否則向中繼節點通信。

步驟4輪循前3步操作,實現中繼節點的不斷更新。

3.2.3 路由優化仿真分析

為分析和驗證路由優化的合理性和有效性,下文從路由路徑、網絡剩余能量分析其合理性,從網絡壽命驗證其有效性。

圖9和圖10分別為CRBHNN和LEACH算法的路由路徑。從圖9和圖10可以看出,CRBHNN算法中遠處的節點都是通過多個中繼節點向基站進行通信,而LEACH算法中簇群成員節點是經過簇首向基站通信,簇首節點是直接向基站通信,因此LEACH算法中遠處的節點能耗更大;同時CRBHNN算法中數據在眾多中繼節點處進行數據融合,進一步提高了能量利用效率。

圖9 CRBHNN算法路由路徑

圖10 LEACH算法路由路徑

圖11為網絡剩余總能量隨周期的變化。從圖11可以看出,實線在初始時位于虛線的上方并保持了較長的周期,由此可知,CRBHNN算法的能量利用率比LEACH算法更高,進一步證實了圖9和圖10的分析結果,同時圖中實線與虛線發生相交后,虛線處在了實線上方,這是因為節點大量死亡后LEACH算法中留下的節點大部分位于基站附近,進一步證實了RBHNN算法能量均衡性優于LEACH算法。

圖11 路由算法中網絡剩余總能量隨周期的變化

圖12為第一個節點死亡時的節點剩余能量。從圖12可以看出,虛線大部分位于實線上方并且虛線起伏明顯大于實線,由此可知,CRBHNN算法的能量均衡性明顯優于LEACH算法,這是由于CRBHNN算法在選取中繼節點時對節點剩余能量進行了分級,使高能量節點有更大的概率為負載的中繼節點工作,通過增大高能量節點的負載、減少低能量節點的能耗來均衡網絡能耗,而LEACH算法是完全隨機選取的簇首,并未考慮能耗方面,進一步證實了圖11的分析結果。

圖12 第一個節點死亡時的節點剩余能量

圖13為節點生存周期。從圖13可以看出,實線在初始時位于虛線的上方并保持了很長的周期,由此可知,CRBHNN算法的FND和HND比LEACH算法晚出現很多,這驗證了CRBHNN算法可以更有效地均衡節點能耗,提高節點的能量利用率,延長網絡壽命,證實了CRBHNN算法在路由方面優于LEACH算法;同時在網絡后期實線與虛線出現相交并且實線處于虛線的下方,這是因為節點大量死亡后,LEACH算法中存活的節點大部分位于基站附近,使其死亡速度減緩,而CRBHNN算法存活的節點更加均勻,進一步證實了RBHNN算法有更好的能量均衡性。該路由優化的局限性是當鄰近節點范圍定義過大時會造成一定程度的通信延遲。

圖13 路由算法節點生存周期

3.3 CRBHNN算法

3.3.1 CRBHNN算法優化方法

本文算法綜合考慮簇首優化算法和路由優化算法的優缺點,通過整合這2種算法來達到最優化。在簇首選取階段是通過改進的分簇優化方法對整個無線傳感器網絡中的節點進行分簇,通過限定簇群范圍來限定鄰近節點范圍;在簇內成員與簇首的通信階段是依據路由優化算法對數據傳輸路徑進行優化,如圖14所示,將圖10中的虛線路徑優化為圖14中的虛線路徑,使遠處的成員節點通過中繼節點向簇首通信;在簇首與基站間通信階段同樣是依據路由優化算法對數據傳輸路徑進行優化,如圖14所示,將圖10中的虛點線路徑優化為圖14中的虛點線路徑,使遠處的簇首通過中繼節點向基站通信,最終達到延長網絡壽命的目的。

圖14 CRBHNN算法的數據傳輸路徑

3.3.2 CRBHNN算法描述

算法3CRBHNN算法

輸入n個感知節點隨機部署在M×M的感知區域上,基站位于感知區域的中心

輸出簇首分布位置、簇群成員和每個節點的中繼節點

步驟1依據CRBHNN分簇算法選取簇首同時確定各自的簇群成員。

步驟2依據CRBHNN路由算法確定每個簇群中成員節點的中繼節點,簇群成員以此路徑向簇首傳輸數據;依據CRBHNN路由算法確定每個簇首的中繼節點,簇首以此路徑向基站傳輸數據。

步驟3輪循步驟1、步驟2的操作,實現網絡拓撲的不斷更新。

3.3.3 仿真結果與分析

為驗證本文CRBHNN算法的有效性、可行性和優越性,從網絡剩余總能量、節點剩余能量和節點生存周期來對算法進行評價,并與LEACH算法、LEACHC算法、DEEC算法和CECA算法進行對比。

圖15為網絡剩余總能量隨周期的變化。從圖15可以看出,無標記的實線在初始時位于其他線的上方并保持了很長的周期,在網絡能量利用率上CRBHNN算法明顯優于其他算法,這是因為在數據傳輸階段,數據的傳輸經過了大量的中繼節點,只需相對短的路徑就可以完成傳輸,同時數據也在中繼節點進行了融合,進一步減少了數據傳輸的能耗,明顯優于其他算法的直傳方式,同時在后期無標記的實線與其他線相交后處于其他線下方,也是因為其他算法的存活節點大部分位于基站附近,進一步證明了CRBHNN算法的能量均衡性優于其他算法。

圖15 不同算法網絡剩余總能量隨周期的變化

圖16為首節點死亡時的節點剩余能量。從圖16可以看出,無標記的實線大部分位于其他線的下方并且無標記的實線的起伏明顯小于其他線,由此可知,在能量負載均衡上CRBHNN算法明顯優于其他算法,這是因為對節點剩余能量進行了分級,使得剩余能量多的節點更易于成為中繼節點,減少剩余能量少的節點的通信負載,對節點能量進行了一定程度的均衡,而其他算法只在簇首選取時考慮了能量這一因素,并未進行全面考慮。

圖16 首節點死亡時的節點剩余能量

圖17為節點生存周期。從圖17可以看出,無標記的實線在初始時位于其他線的上方并保持了很長的周期,由此可知,CRBHNN算法的FND和HND比其他算法晚出現很多,證實了其生存周期明顯優于其他算法,這也充分證明了CRBHNN算法的有效性和優越性,這主要是因為CRBHNN算法在進行隨機選取簇首后又對其分布位置進行優化,使其分簇更加均勻,實現了簇首選取的優化,同時考慮能量等因素采用中繼方式進行信息傳輸,均衡了網絡負載,提高了能量利用率;同時在后期無標記的實線與其他線相交后處于其他線的下方,也是因為其他算法的存活節點大部分位于基站附近,這進一步證明了CRNHNN算法能量均衡性優于其他算法。

圖17 CRBHNN算法節點生存周期

4 結束語

為延長網絡壽命提高網絡服務質量,本文對無線傳感器網絡的數據傳輸能耗模型進行研究,提出一種基于分級鄰近節點的分簇路由算法。在分簇階段通過對簇群成員進行分級,對不合理的簇首進行再選舉,解決了簇首分布的完全隨機性問題,使得簇首可以更均勻地分布在感知區域中。在數據傳輸階段通過對鄰近節點進行分級,確立各個節點對應的中繼節點,解決遠處孤立節點傳輸能耗過大和網絡能量不均衡的問題,同時多次的數據融合也提高了能量利用率。仿真結果表明,與LEACH、CECA、DEEC等算法進行對比,該算法可以有效減少和均衡網絡負載能耗,提高能量利用率,最終達到延長網絡壽命的目的。CRBHNN為分布式路由算法,是基于一定范圍內的鄰近節點信息進行的優化,可能會導致部分范圍內的優化在整體上不夠突出,下一步將與集中式算法結合來優化路由算法。