WSNs中一種基于閾值修正的多跳分簇路由算法?

徐會彬(.湖州師范學院信息工程學院,浙江 湖州33000；.浙江省現代農業(yè)資源智慧管理與應用研究重點實驗室,浙江 湖州33000)

隨著無線傳感技術的發(fā)展,無線傳感網絡(Wireless Sensor Networks,WSNs)已在軍事偵察、智能家居、智慧農業(yè)等領域廣泛使用[1－2]。WSNs由多個節(jié)點組成的無線網絡。這些節(jié)點能感知環(huán)境的一些物理特性,進而獲取如壓力、溫濕度等各類數據。節(jié)點將其采集到的數據以多跳方式傳輸至匯聚節(jié)點。

WSNs內節(jié)點屬于微型傳感節(jié)點,它們的計算能力、內存和電源功率有限。通常,節(jié)點是由電池供電。一旦電池能量消耗殆盡,節(jié)點就無法繼續(xù)工作。由于應用環(huán)境復雜多變,難以更換節(jié)點電池或者以其他方式補給能量。因此,能量成為制約WSNs長時間運行的瓶頸[3]。

相比于其他操作,傳輸數據消耗了節(jié)點的大部分能量。因此,學者通過優(yōu)化數據傳輸策略降低節(jié)點的能耗。其中,分簇的策略受到廣泛關注。低功耗自適應集簇分層型(Low Energy Adaptive Clustering Hierarchy,LEACH)[4]是最初的分簇路由。LEACH路由將WSN分成若干簇群。每個簇群由一個簇頭。簇頭收集本簇內感測的數據,再將數據傳輸至匯聚節(jié)點。LEACH路由通過分簇思想,提高數據傳輸效率,緩解了網絡的能耗。

LEACH路由采用隨機方式產生簇頭,沒有考慮節(jié)點能量以及距離等信息,存在一些不足。為此,研究人員針對這些不足,提出一些改進策略[5－7]。例如,文獻[8]針對簇頭的選擇閾值進行改進。在閾值函數中引入能量,使剩余能量大的節(jié)點更容易成為簇頭。但是該路由沒有考慮節(jié)點離匯聚節(jié)點的距離。文獻[9]通過距離和剩余能量信息對簇頭的選擇閾值進行修正,降低能耗。盡管該路由在選舉簇頭只考慮了距離和能量信息,沒有考慮到節(jié)點分布情況。同時,該路由也沒有優(yōu)化簇間路由。

由于選擇簇頭的復雜性,研究人員將一些智能算法引入分簇路由。文獻[10]提出的基于改進螢火蟲聚類的能效路由(Energy Efficient Routing based on Improved Firefly Clustering,EIFC)。EIFC路由利用聚類算法構建簇,使簇分布更合理。但是節(jié)點運行聚類算法也增加了節(jié)點的能耗。

為此,本文提出基于閾值修正的多跳分簇路由(Threshold Correction-based Multi-hop Clustering Routing,TCCR)。TCCR路由在分簇過程中綜合考慮了節(jié)點的能量、離匯聚節(jié)點的距離以及節(jié)點的分布密度信息,并通過構建適度因子優(yōu)化簇間路由。

1 系統模型

1.1 網絡模型

n個節(jié)點分布于區(qū)域內Θ。令S＝{s0,s1,…,sn}表示節(jié)點集,其中s0表示匯聚節(jié)點,其位于區(qū)域中心位置；其他節(jié)點隨機分布于區(qū)域內,且n＝｜S｜－1。本文對WSNs內節(jié)點進行如下約束[11]:①所有節(jié)點是靜態(tài)的。在區(qū)域Θ內部署了節(jié)點后,節(jié)點不再移動；②所有節(jié)點的初始能量相同Einit。所有節(jié)點的通信半徑相同R。每個節(jié)點具有唯一的ID號。令si表示第i個節(jié)點的ID號,其中i＝1,2,…,n。③匯聚節(jié)點的能量不受限,且具有足夠的數據處理能量；④只考慮因節(jié)點能量消耗殆盡而導致的節(jié)點死亡。

1.2 能量消耗模型

采用圖1所示的一階無線電模型[12]作為節(jié)點的能量消耗模型。

圖1 一階無線電模型

節(jié)點傳輸?比特數據,且傳輸距離為d時所消耗能量為ETx(?,d):

式中:Eelec表示傳輸一比特數據所消耗的能量；εfs、εmp分別表示自由空間損耗系數、多徑衰落損耗系數；d0表示多徑衰落與自由空間衰落兩種衰落的切換閾值,其定義如式(2)所示:

相應地,若節(jié)點接收?比特數據所消耗的能量為ERx(?):

2 TCCR路由

TCCR路由先依據網絡區(qū)域面積、匯聚節(jié)點位置以及節(jié)點通信半徑估計簇頭數。再依據節(jié)點剩余能量、相對距離和節(jié)點密度信息選擇簇頭。最后,構建簇間路由。

2.1 簇頭數

為了更好地均衡網絡能耗,使簇頭分布更均勻,利用節(jié)點分布情況,估計簇頭數k。節(jié)點部署后,先計算(n－1)個節(jié)點離s0的最大距離dmax和最小距離dmin:

式中:di,o表示節(jié)點si離s0的距離。

再將(dmax＋dmin)/R與n值進行比較,如果(dmax＋dmin)/R≤n,則k＝(dmax＋dmin)/2R,否則,k＝,如式(5)所示:

2.2 選擇簇頭

利用節(jié)點的剩余能量,離匯聚節(jié)點距離和節(jié)點密度三個因子選擇簇頭。

首先,計算節(jié)點的剩余能量因子[13]。令(r)表示節(jié)點si在r輪時的能量。節(jié)點si的剩余能量因子為:

然后,計算節(jié)點的距離因子。采用了隨機方式部署節(jié)點,導致節(jié)點離匯聚節(jié)點的距離不盡相同。有些節(jié)點離匯聚節(jié)點距離較遠,有些離匯聚節(jié)點距離較短。因此,定義節(jié)點的距離因子,評估節(jié)點離匯聚節(jié)點的較近:

除了能量和距離因子外,節(jié)點分布密度對簇頭的選擇有重要作用。若節(jié)點位于密集區(qū)域,理當增加成為簇頭的概率；反之,在節(jié)點位于稀疏區(qū)域,應降低節(jié)點成為簇頭的概率。因此,定義節(jié)點密度因子:

式中:Ni表示節(jié)點si的一跳鄰居節(jié)點,其定義如式(10)所示:

依據式(9)可知,節(jié)點分布密度越大,密度因子。引用LEACH協議所采用的閾值函數,并對其進行改進,形成簇頭選擇閾值函數:

式中:Pi表示簇頭比例,即Pi＝k/(n－1)；r表示當前執(zhí)行的輪數；G表示上一輪為非簇頭的節(jié)點集合；若上一輪已成為簇頭,本輪不再參與簇頭的競選；Υi表示由節(jié)點的能量因子、距離因子和密度因子構建適度因子,其定義如式(12)所示:

式中:λ1,λ2和λ3為權重系數,且0<λ1,λ2,λ3<1,λ1＋λ2＋λ3＝1。

節(jié)點在競爭簇頭時,先產生一個隨機數。再將所產生的隨機數與閾值比較。若隨機數小于閾值,節(jié)點就宣稱自己為本輪的簇頭。并向鄰居節(jié)點廣播通告消息Avd_Mes。

2.3 形成簇的流程

利用2.2節(jié)產生k個簇頭{Ch1,Ch2,…,Chk}。這些簇頭就鄰居節(jié)點廣播Avd_Mes。非簇頭節(jié)點收到Avd_Mes消息后,就選擇接收信號最強的簇頭加入。具體的流程如圖2所示。

圖2 簇的形成流程

最初,匯聚節(jié)點向全網廣播Hello消息,其包含自匯聚節(jié)點的位置。接收Hello消息后,節(jié)點計算離匯聚節(jié)點的距離。然后,進入簇頭選擇階段。在新一輪開始,節(jié)點先判斷本輪是否為簇頭。若本輪已是簇頭,節(jié)點就不參與新一輪的簇頭競爭。若不是,就產生隨機數,并與閾值進行比較。

若產生的隨機數小于閾值,就廣播Avd_Mes消息,并接收非簇頭節(jié)點發(fā)送的請求消息Join_Mes。若產生的隨機數大于閾值,就等待接收由簇頭廣播的Avd_Mes消息。當接收了來自多個簇頭廣播的Avd_Mes消息后,非簇頭節(jié)點就從中選擇信號強度的簇頭加入。重復上述過程,直到執(zhí)行到最大輪數。

2.4 基于距離和能效的簇間路由

若簇頭離匯聚節(jié)點距離小于R,該簇頭就直接將數據傳輸至匯聚節(jié)點。若簇頭離匯聚節(jié)點距離大于R,簇頭就需構建多跳路徑通往匯聚節(jié)點[14]。為了方便描述,將離匯聚節(jié)點距離大于R的簇頭從R＝{Ch1,Ch2,…,Chk}中刪除,構建新的簇頭集R′＝{Ch1,Ch2,…,Chk′},且R′?R。

對于R′集中任意一個簇頭Chi,若Chi需要向匯聚節(jié)點傳輸數據,它就從它的鄰居簇頭中選擇具有最大適度因子的簇頭作為下一跳轉發(fā)節(jié)點:

式中:Q(j)表示簇頭Chj的適度因子；dChj,o表示簇頭Chj離匯聚節(jié)點距離；dCh,o表示簇頭離匯聚節(jié)點的最大距離；(r)表示在當前r輪時簇頭Chj的剩余能量；Einit表示簇頭的初始能量；N(Chi)表示簇頭Chi的鄰居簇頭集；α和β為距離因子和能效因子的權重系數。通過α、β系數控制距離、能量效率對適度因子的影響比重,且α＋β＝1?？梢罁煌膽铆h(huán)境,設定α和β的值。

依據式(13)可知,離匯聚節(jié)點距離越大以及剩余能量越大的簇頭,其適度因子越大。為此,簇頭Chi就從其鄰居簇頭選擇具有最大適度因子的簇頭作為下一跳轉發(fā)節(jié)點。利用適度因子選擇下一跳轉發(fā)節(jié)點,縮短數據傳輸路徑,同時避免能量過低的簇頭擔任下一跳轉發(fā)節(jié)點。

3 性能仿真

3.1 仿真參數

本文在MATLAB 2016b軟件上建立仿真平臺,分析TCCR路由性能。在100 m×100 m方形區(qū)域內隨機部署100個傳感節(jié)點和一個匯聚節(jié)點,匯聚節(jié)點位于匯聚區(qū)域中心,即匯聚節(jié)點位置坐標為(50,50),初始分布圖如圖3所示。

圖3 初始節(jié)點分布圖

仿真參數如表1所示。利用這些參數進行Monte Carlo實驗,每次實驗進行2000輪,共進行50次,取平均值作為最終的實驗數據。

表1 仿真參數

為了更好地分析TCCR路由性能,選擇經典的LEACH路由和EIFC路由作為參照,分析死亡節(jié)點數,剩余能量,匯聚節(jié)點接收的數據量和數據包傳輸時延性能。

3.2 死亡節(jié)點數

首先分析TCCR路由、LEACH和EIFC路由的死亡節(jié)點數情況,如圖4所示。顯然,死亡節(jié)點數越多,路由的能耗性能越差。

圖4 死亡節(jié)點數

從圖4可知,相比于EIFC路由和LEACH路由,提出的TCCR路由降低了死亡節(jié)點數的增長速度。LEACH路由最早出現死亡節(jié)點數,其約在350輪就出現一個死亡節(jié)點。相比于LEACH路由,EIFC路由約在580輪時出現一個死亡節(jié)點。而TCCR路由的第一個死亡節(jié)點出現的輪數最晚,約在630輪,分別比LEACH路由和EIFC路由延遲了約80%和8.6%。

除了延遲第一個死亡節(jié)點出現的輪數,TCCR路由也推遲了全部死亡節(jié)點數出的輪數。TCCR路由直到約2000輪時100個節(jié)點才全部死亡。而LEACH路由在1200輪時100個節(jié)點就基本上全部死亡。上述數據表明,提出的TCCR路由通過優(yōu)化簇頭的分布,并選擇離剩余能量高,離匯聚節(jié)點距離短和節(jié)點密度高的節(jié)點作為簇頭,均衡網絡能耗。

3.3 網絡剩余能量

本小節(jié)分析三個路由協議的網絡剩余能量。節(jié)點的初始能量為0.5 J,共100個節(jié)點,因此網絡的初始為50 J,也是網絡的擁有的最大能量。圖5顯示了網絡剩余能量隨輪數的變化情況。

圖5 網絡剩余能量

從圖5可知,最初,三個路由的網絡剩余能量均為50 J。隨著輪數的增加,三個路由的網絡剩余能量迅速下降,但是它們的下降速度并不相同。其中LEACH路由的網絡剩余能量下降速度最快。執(zhí)行到300輪,LEACH路由的網絡剩余能量就下降了50%。而TCCR路由的網絡剩余能量是三者之中能量下降最慢的。

在網絡能量損耗了90%時,LEACH路由執(zhí)行的輪數約640；EIFC路由執(zhí)行的輪數約682；TCCR路由執(zhí)行的輪數約845。相比于LEACH路由和EIFC路由,TCCR路由有效地延緩了能量損耗速度。

上述數據表明,相比于LEACH路由和EIFC路由,TCCR路由平衡網絡能耗。這得益于TCCR路由合理地選擇簇頭,沒有過度浪費能量。

3.4 匯聚節(jié)點接收的數據量

匯聚節(jié)點接收的數據量反映了路由傳輸數據包的性能。在限定的輪數內,匯聚節(jié)點接收的數據量越大,傳輸數據包的性能越好,所構建的路由越穩(wěn)定。

圖6給出了在600輪內,LEACH路由、EIFC路由和TCCR路由中匯聚節(jié)點接收的數據量情況。從圖可知,TCCR路由的匯聚節(jié)點接收的數據量最大,優(yōu)于LEACH路由和EIFC路由,提升了數據傳輸效率。這主要原因在于:TCCR路由在構建簇間路由時,充分考慮了簇頭的剩余能量以及離匯聚節(jié)點距離。一方面盡量縮短數據傳輸路徑,另一方面盡量選擇剩余能量高的簇頭傳輸數據,避免能量過低的簇頭參與路由。

圖6 匯聚節(jié)點接收的數據量

4 結束語

針對WSNs現有分簇路由算法的不足,提出基于閾值修正的多跳分簇路由TCCR。TCCR路由的核心是對選擇簇頭的閾值進行修正。即在傳統的LEACH簇頭選擇閾值的基礎上,加入節(jié)點的剩余能量、離匯聚節(jié)點距離和節(jié)點密度,對產生簇頭閾值進行修正,進而解決簇頭分布不合理以及能耗不均衡問題。在簇間通信階段,利用距離和能量構建適度因子選擇下一跳轉發(fā)節(jié)點。

仿真結果表明,提出的TCCR路由具有較好的穩(wěn)定性,均衡了節(jié)點間能耗,降低了節(jié)點的能耗速度,延長了網絡壽命,也提升了數據傳輸效率。本文只考慮了同構網絡,并沒有考慮到節(jié)點間的差異性。后期,將研究異構網絡的分簇路由,這是后期的研究工作。