基于優(yōu)化簇頭選舉的WSN分簇路由協(xié)議研究

梁 壯，李 剛,2,3，雷麗婷

(1.蘭州交通大學機電技術研究所，甘肅蘭州 730070；2.甘肅省物流及運輸裝備信息化工程技術研究中心，甘肅蘭州 730070；3.甘肅省物流與運輸裝備行業(yè)技術中心，甘肅蘭州 730070)

隨著電子學、無線通訊以及傳感器等相關技術的快速進步，傳感器網(wǎng)絡也在朝著大規(guī)模、自組織、高可靠性的方向發(fā)展[1].傳感器從早期只具有點到點的傳輸功能，逐步發(fā)展到當代的智能無線傳感器網(wǎng)絡.無線傳感器網(wǎng)絡應用極為廣泛，其技術也是物聯(lián)網(wǎng)工程的核心要素，已經(jīng)被公認為是僅次于互聯(lián)網(wǎng)的又一重要網(wǎng)絡[2].無線傳感器網(wǎng)絡（Wireless Sensor Network, WSN）運行方式是由各個傳感器的相互協(xié)調(diào)完成對監(jiān)測區(qū)域相關信息的采集和融合，最后將整合后的數(shù)據(jù)發(fā)送給管理人[3].關于無線傳感器網(wǎng)絡研究的內(nèi)容也很豐富，但是由于節(jié)點具有能源、存儲容量和功率制約的明顯缺點，因而耗能依然是WSN研究的重要部分.

無線傳感器網(wǎng)絡路由協(xié)議根據(jù)網(wǎng)絡結構可以分為平面路由協(xié)議和層次路由協(xié)議，后者也稱為分簇路由協(xié)議.分簇路由協(xié)議相比于平面路由協(xié)議的不同之處在于整個網(wǎng)絡包含幾種不同類型的傳感器，分別來完成各自的功能，網(wǎng)絡性能優(yōu)良[4].LEACH[5]（Low Energy Adaptive Clustering Hierarch）協(xié)議是Heinzelman等人提出最早的分簇路由協(xié)議，首次引入“輪”的概念，并賦予其含義.在網(wǎng)絡運行的每一輪都選舉新的簇頭，規(guī)避某些節(jié)點能量持續(xù)消耗情況的出現(xiàn)，實現(xiàn)網(wǎng)絡能耗盡可能均衡的目標.其在網(wǎng)絡壽命方面的突出表現(xiàn)，使得層次路由協(xié)議逐步成為學者們研究的熱點.

LEACH類協(xié)議簇頭選舉的過程中，由于推選簇頭的隨機性相對較大，忽視了各個節(jié)點的特異性，就會導致每一輪選舉出的簇頭數(shù)相差甚遠，即不能產(chǎn)生穩(wěn)定的最佳簇頭數(shù)量.甚至在WSN運行的最后階段，將不會產(chǎn)生一個簇頭.按照網(wǎng)絡性能的優(yōu)良可將整個無線傳感器網(wǎng)絡周期劃分為三個時期 ：穩(wěn)定周期[6]（Stable Period, SP）、半數(shù)死亡節(jié)點期[7]（Half Surviving nodes, HSN）和弱感知周期①Liu J J, Hu Y J. A balanced andenergy-efficient clustering algorithm for heterogeneous wireless sensornetworks [C] //Proceedings of the 6th International Conference on Wireless Communications and Signal Processing. Hefei, China: IEEE,2014: 1-6.（Weak Perception Cycle, WPC）.在無線傳感器網(wǎng)絡運行的早期，沒有節(jié)點的死亡，所有節(jié)點都穩(wěn)定運行，這段時間網(wǎng)絡具有很強的感知能力，稱之為穩(wěn)定期.從網(wǎng)絡運行開始直到有一半節(jié)點死亡或者存活時，此階段為半數(shù)死亡節(jié)點期，該階段網(wǎng)絡的感知能力逐步降低但仍能維持網(wǎng)絡的正常運行.從死亡半數(shù)節(jié)點開始到無線傳感器網(wǎng)絡運行結束，稱為弱感知周期，整個網(wǎng)絡的感知能力逐漸下降到一個很低的水平，尤其在弱感知后期，大多數(shù)的節(jié)點處于死亡狀態(tài)，網(wǎng)絡的感知能力極差，網(wǎng)絡基本處于癱瘓狀態(tài)以致無法正常工作.因此，保持網(wǎng)絡運行的前兩個時期（SP和HSN）越長，網(wǎng)絡性能越好.

在許多WSN分層路由協(xié)議研究中，眾多學者[8-10]將網(wǎng)絡壽命作為首要目標，而忽略了WSN性能的其它重要指標，比如穩(wěn)定期、有效輪數(shù)等.對此，本文在WSN簇頭選舉階段進行了改進，提出一種基于優(yōu)化簇頭選舉的分層路由協(xié)議（Cluster Routing Protocol Based on Optimized Cluster Head Election, CBOCHE）.目的是為了提高簇頭選舉的的穩(wěn)定性，并在更大程度延長無線傳感器網(wǎng)絡的穩(wěn)定期和半數(shù)死亡節(jié)點周期，并不僅僅是一味追求網(wǎng)絡的絕對壽命.

1 網(wǎng)絡模型

1.1 無線傳感器結構

假設WSN的監(jiān)測區(qū)域為正方形，邊長為M，傳感器的總個數(shù)為N，隨機部署在監(jiān)測范圍內(nèi)，網(wǎng)絡的成簇數(shù)量與簇頭數(shù)目相對應.組成網(wǎng)絡的節(jié)點類型分為三種，按照數(shù)據(jù)傳輸?shù)穆窂揭来畏謩e是普通傳感器節(jié)點、簇頭節(jié)點、匯聚節(jié)點.匯聚節(jié)點的下一級傳輸?shù)竭_的是管理節(jié)點，管理節(jié)點是用戶和網(wǎng)絡的交互平臺.圖1為典型的WSN結構（不包括管理節(jié)點）示意圖.

1.2 異構網(wǎng)絡模型

選用多級異構傳感器中的兩級異構傳感器，按照原有能量的多少分成普通傳感器節(jié)點和高級傳感器節(jié)點.假設高級節(jié)點在傳感器總數(shù)中占比為m，普通節(jié)點的初始能量較低，為Es，高級節(jié)點的初始能量為Es(1 + a)，a表示高級節(jié)點超過普通節(jié)點能量的倍數(shù).

圖1 WSN結構示意圖

1.3 能量消耗模型

傳感器操作和存儲器訪問所消耗的能量相對于無線電傳輸而言非常小并且可以被忽略.因此，分層無線傳感器網(wǎng)絡的能量消耗主要來自于數(shù)據(jù)傳輸和簇頭節(jié)點對數(shù)據(jù)的分析融合兩大部分.本文采用文獻[11]能量消耗模型，公式如（1）式.

其中，ETx(k,d)和ERx(k)分別表示傳感器節(jié)點發(fā)送接收k-bit數(shù)據(jù)包的能耗；ECH和EDA分別表示簇頭節(jié)點發(fā)送和融合數(shù)據(jù)的能耗；Eelec表示發(fā)射電路或接收電路每bit數(shù)據(jù)的消耗能量，Efs為自由空間模型的傳輸系數(shù)，Eamp為多徑衰落模型傳輸系數(shù)；d 表示傳輸距離，d＜d0是自由空間能耗模型，d ≥ d0是多徑衰落能耗模型.

2 基于優(yōu)化簇頭選舉的分簇路由協(xié)議（CBOCHE）

2.1 簇頭選舉算法流程

在分層路由算法中，Gnode來標識節(jié)點是否屬于候選簇頭集G.若一個節(jié)點在最近1/Popt（Popt為簇頭比例）輪內(nèi)做過簇頭，令Gnode=0，此節(jié)點不能用作簇頭的候選節(jié)點；若一個節(jié)點在1/Popt內(nèi)沒有做過簇頭，令Gnode=1，此節(jié)點就可以作為簇頭的候選節(jié)點.在每1/Popt輪后，重置1/Popt前當選簇頭節(jié)點的值Gnode值為1.

這種更新規(guī)則在網(wǎng)絡運行前期，由于沒有死亡節(jié)點的出現(xiàn)，簇頭的候選節(jié)點數(shù)目大于最佳簇頭數(shù)目，可以選舉出最佳簇頭數(shù).隨著網(wǎng)絡的運行，節(jié)點數(shù)目將會不斷減少，就會出現(xiàn)候選簇頭數(shù)目等于甚至小于最優(yōu)簇頭數(shù)目的情況.當二者相等時，所有的候選簇頭數(shù)都會被選舉為簇頭，當候選簇頭的數(shù)量小于最佳簇頭數(shù)目時，不能選出合理數(shù)量的簇頭，導致簇頭選舉數(shù)目不穩(wěn)定問題的出現(xiàn).

為改善簇頭數(shù)目選舉不穩(wěn)定的缺陷，本文提出的CBOCHE協(xié)議在簇頭選舉流程中Gnode的跟新策略進行優(yōu)化.G值含義仍然為是否屬于候選簇頭集，當出現(xiàn)候選簇頭數(shù)等于最佳簇頭數(shù)時，直接跳過閾值比較的過程，將所有的候選簇頭全部當選為簇頭節(jié)點.當候選簇頭數(shù)小于最佳簇頭數(shù)時，即將所有的候選節(jié)點全部成為簇頭時，仍不能選舉出足夠的簇頭數(shù)，本文采取的方法是立即更新節(jié)點Gnode的值，通過提前值更新Gnode時間來補充足夠的候選節(jié)點數(shù)目，直到候選簇頭數(shù)目等于或者大于最佳簇頭數(shù).這樣就可以保證每一輪選舉出合理穩(wěn)定的簇首數(shù)目，改進后的流程圖如2所示.

圖2 CBOCHE協(xié)議簇頭選舉流程

2.2 節(jié)點閾值修正

經(jīng)典的LEACH協(xié)議中，簇頭的選舉是通過產(chǎn)生的隨機數(shù)與設定的閾值比較來確定節(jié)點是否擔任簇頭，隨機數(shù)的取值范圍為0 - 1，當隨機數(shù)小于閾值時，節(jié)點被選為簇頭，反之為普通節(jié)點.閾值的公式如下[12]：

其中，p=k/n；n和k表示網(wǎng)絡中的節(jié)點和簇首數(shù)，p和r分別是節(jié)點中簇頭所占比例和網(wǎng)絡正在運作的輪數(shù)，G是近來1/p輪內(nèi)未擔任過簇首的一個集合.LEACH協(xié)議由于運行過程產(chǎn)生隨機數(shù)帶來的隨機性，會使整個網(wǎng)絡的負載不均勻.

DEEC（Distribute Energy-Efficient Clustering）是在LEACH協(xié)議基礎上進一步修改后的又一種分簇路由協(xié)議[13]，其閾值公式與LEACH協(xié)議的閾值公式基本相同，但原式子中的簇頭占比P改變?yōu)楣?jié)點當選為簇頭的幾率Pi，Pi的計算公式為：

其中，Popt為簇頭占比，Er(i)為節(jié)點i運行到r輪時的剩余能量，整個網(wǎng)絡的平均剩余能量.

與LEACH協(xié)議相比，DEEC路由協(xié)議引入了兩個因子，即節(jié)點的剩余能量和網(wǎng)絡的平均剩余能量，相對增加了WSN的網(wǎng)絡壽命.但在每一輪的簇頭選舉中仍然會出現(xiàn)選舉出的簇頭數(shù)不穩(wěn)定的情況，簇頭數(shù)目過多或者過少都會造成節(jié)點能耗增加.同時，DEEC協(xié)議也忽略了節(jié)點間相互距離這一重要因子，因為傳輸距離也是影響能耗的一個關鍵因素.

TSEP①Kashaf A, Javaid N, Khan Z A, et al. TSEP: Thresh-old-Sensitive Stable Election Protocol for WSNs [C] //International Conference on Frontiers of Information Technology. IEEE, 2012: 164-168.（Threshold-sensitive Stable Election Protocol）協(xié)議是LEACH基礎上改進的一種協(xié)議，但它的著重點不同于LEACH和DEEC兩種協(xié)議，它更加關注數(shù)據(jù)的傳輸而非簇的形成.TSEP中閾值包括硬門限和軟門限倆個參數(shù)，當感測值達到硬閾值時，發(fā)射機被打開，數(shù)據(jù)傳輸?shù)酱仡^，該感測值被儲存在節(jié)點的變量中，這是第一次滿足條件.之后，當且僅當感測值大于硬閾值或者當前感測值與儲存的感測值之間的差等于或大于軟閾值時，節(jié)點將發(fā)送數(shù)據(jù).通過考慮這兩個閾值來調(diào)節(jié)數(shù)據(jù)傳輸?shù)臅r機，可以有效減少數(shù)據(jù)傳輸?shù)拇螖?shù)，某些方面網(wǎng)絡性能得到顯著提升.因此，本文將TSEP也作為結果對比分析的一種協(xié)議，其閾值具體計算見本頁腳注①.

在簇頭選舉中，本文既將節(jié)點的初始能量和剩余能量納入考量，也兼顧到節(jié)點到基站的距離,來避免因二者距離較大而造成負載增加的情況.修正后的閾值公式如式（4）.

式中：r是網(wǎng)絡正在運行的輪次，G是近來1/pi輪沒有擔任簇頭的節(jié)點集，α和β為調(diào)節(jié)參數(shù)，α、β具有相同的取值范圍[0,1]，且滿足α + β = 1，Eres和Eini分別是節(jié)點的剩余能量和節(jié)點的初始能別是全網(wǎng)的剩余能量和全網(wǎng)的初始能量，Si表示節(jié)點i，davg和di分別表示全部節(jié)點到基站的平均距離和節(jié)點i與基站的距離，pi是節(jié)點i成為簇頭的概率.

由于網(wǎng)絡包含不同能量類型的節(jié)點，故不同類型節(jié)點成為簇頭的機率并不相同，具體計算公式如下：

其中Popt是簇頭比例，m表示高級節(jié)點在全部節(jié)點中的占比.

3 實驗仿真及分析

本文選用 MATLAB2016a軟件為仿真實驗平臺，在兩級異構網(wǎng)絡環(huán)境下驗證算法的網(wǎng)絡性能.在邊長為100的方形平坦區(qū)域中隨機布置100個節(jié)點，網(wǎng)絡的范圍為（0,0）～（100,100），基站的位置為（50, 50），詳細的實驗參數(shù)如表1所示.與TSEP、LEACH、DEEC協(xié)議作對比，分析改進協(xié)議CBOCHE的性能，圖3為CBOCHE協(xié)議運行示意圖.

表1 實驗參數(shù)

3.1 簇頭的選舉穩(wěn)定性分析

本文研究和分析了LEACH類協(xié)議中簇頭選舉的不穩(wěn)定性，并改進和優(yōu)化了其缺陷，以確保在WSN運行早期階段產(chǎn)生更穩(wěn)定的簇頭數(shù).本文實驗總節(jié)點數(shù)是100，最優(yōu)簇頭數(shù)目是5，故在不受任何干擾因素條件下每輪產(chǎn)生的簇頭數(shù)都應該為5.表2為幾種協(xié)議在網(wǎng)絡運行不同時期簇頭數(shù)目的均值和方差.圖4為簇頭穩(wěn)定性柱狀對比圖.

由表2和圖4可知，CBOCHE協(xié)議在穩(wěn)定期選舉出的簇頭數(shù)目均值為5，方差為0，表明協(xié)議在WSN運行前期簇頭數(shù)目非常穩(wěn)定.同時，在相同時期，新算法在半數(shù)死亡點和網(wǎng)絡壽命期間簇頭數(shù)的均值相比于其它協(xié)議更高，并且方差較低.表明在網(wǎng)絡運行的整個生命周期內(nèi)，產(chǎn)生穩(wěn)定簇頭數(shù)的性能均得到全面顯著改善.

圖3 CBOCHE運行示意圖

表2 各協(xié)議產(chǎn)生簇頭數(shù)分析

3.2 網(wǎng)絡有效生命周期對比分析

本協(xié)議在調(diào)整Gnode值的更新規(guī)則來優(yōu)化簇頭選舉數(shù)目的同時，也對閾值進行了修訂.考慮了節(jié)點的初始能量和剩余能量、全網(wǎng)的初始能量和剩余能量、節(jié)點到基站的距離等因素，延長了WSN網(wǎng)絡有效生命周期.利用MATLAB對協(xié)議進行仿真實驗，統(tǒng)計不同協(xié)議的各個運行時期的運行情況，結果如表3所示.

圖4 簇頭穩(wěn)定性對比圖

表3 各協(xié)議在不同階段的運行輪數(shù)

通過對表3數(shù)據(jù)分析可得，改進后的CBOCHE協(xié)議在穩(wěn)定期以及半數(shù)存活節(jié)點期的運行輪數(shù)和有效輪數(shù)明顯優(yōu)于其它幾種協(xié)議.在穩(wěn)定期的有效運作輪數(shù)相對于LEACH、DEEC和TSEP分別增加了36.35%、28.77%、23.25%，在半數(shù)存活點也分別增加了 41.72%、29.63%、15.16%.改進后的協(xié)議在簇頭穩(wěn)定性方面有較大提高，幾乎避免了零簇頭情況的出現(xiàn)，故網(wǎng)絡的整體壽命下降較大，但生命周期的有效輪數(shù)仍然明顯提高，相對于 LEACH、DEEC和 TSEP分別提升了75.54%、71.05%、53.19%.

圖5 不同時期網(wǎng)絡生命周期對比圖

圖5 為表3部分數(shù)據(jù)繪制的柱狀圖，更加直觀地顯示了改進算法延長了網(wǎng)絡的穩(wěn)定期和半數(shù)存活點期，同時網(wǎng)絡生命周期有效輪數(shù)的提高使得其在整個網(wǎng)絡壽命的占比幾乎達到100%.

4 結 論

本文針對無線傳感器網(wǎng)絡簇頭數(shù)目選舉不穩(wěn)定以及穩(wěn)定期、半數(shù)節(jié)點存活期不夠長的缺點進行研究，提出了一種新的基于簇頭選舉階段路由算法.仿真驗證表明，新協(xié)議CBOCHE相關性能明顯改善.

1）通過修改簇頭選舉流程中的Gnode值與新策略來保證網(wǎng)絡運行的每一輪都可以產(chǎn)生合理的簇頭數(shù)，盡量規(guī)避出現(xiàn)沒有簇頭的狀況，并且顯著增加了網(wǎng)絡運行有效輪數(shù).

2）閾值修正過程中，兼顧節(jié)點的初始能量和剩余能量、全網(wǎng)的初始能量和剩余能量、節(jié)點到基站的距離等與能耗相關的因素，擴展的WSN性能表現(xiàn)出更佳的穩(wěn)定期和半數(shù)存活節(jié)點期.