樹型鏈?zhǔn)椒蔷鶆蚍执鼗旌隙嗵酚伤惴?

胡中棟， 張 康， 王振東

(江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是一種集傳感器技術(shù)、信息處理技術(shù)、通信技術(shù)等于一體的新型網(wǎng)絡(luò)，現(xiàn)已廣泛應(yīng)用于環(huán)境監(jiān)測(cè)[1]、智能家居、國(guó)防軍事[2]等多個(gè)領(lǐng)域[3]。由于節(jié)點(diǎn)初始能量有限[4]，且后期無(wú)法補(bǔ)充，因此，充分利用節(jié)點(diǎn)有限能量、延長(zhǎng)網(wǎng)絡(luò)整體壽命成為WSNs的重點(diǎn)研究方向。

層次路由協(xié)議中的分簇思想能有效聚合數(shù)據(jù)，提高網(wǎng)絡(luò)連通率[5]，實(shí)現(xiàn)負(fù)載均衡。文獻(xiàn)[6,7]中簇頭隨機(jī)選取未考慮位置分布，簇內(nèi)節(jié)點(diǎn)與簇頭、簇頭與簇頭間均以單跳方式通信，易產(chǎn)生遠(yuǎn)距離傳輸；文獻(xiàn)[8]中算法獲取所有節(jié)點(diǎn)相關(guān)信息會(huì)消耗大量能量、占用大量的帶寬；文獻(xiàn)[9]中靜態(tài)劃分成鏈區(qū)域，有可能使用原本相鄰的節(jié)點(diǎn)因劃分區(qū)域不同而成鏈不同，造成能耗浪費(fèi)；文獻(xiàn)[10]中算法如果距離Sink較遠(yuǎn)的簇密度較大，就會(huì)導(dǎo)致其簇頭負(fù)載不均，其在大面積網(wǎng)絡(luò)中的表現(xiàn)也較一般。

本文通過(guò)引入候選簇頭之間的角度控制優(yōu)化簇頭選取，構(gòu)建樹型鏈?zhǔn)椒蔷鶆虼亟Y(jié)構(gòu)優(yōu)化成簇策略，利用混合層次網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，結(jié)合改進(jìn)后的蟻群算法提出一種樹型鏈?zhǔn)椒蔷鶆蚍执鼗旌隙嗵酚伤惴?a tree-chain uneven cluster hybrid multi-hop routing algorithm,TUCHM)。

1 相關(guān)研究

1.1 能耗模型

本文文獻(xiàn)[8]中的無(wú)線通信能耗模型[11]，假設(shè)每個(gè)數(shù)據(jù)包有kbit的數(shù)據(jù)，則發(fā)送端消耗的能量為

(1)

(2)

接收端消耗的能量為

ERX=KEelec

(3)

數(shù)據(jù)匯聚融合消耗的能量為

EDA=kEda

(4)

式中Eelec=50 nJ/bit，為收發(fā)電路能耗；Eda=5 nJ/bit，為單位數(shù)據(jù)融合能耗；Efs=10 pJ/bit/m2，Eamp=0.001 3 pJ/bit/m4，d0為能量損耗的界限值。

1.2 蟻群算法

基本蟻群算法[13]路徑選擇概率模型未能考慮節(jié)點(diǎn)的剩余能量和位置等因素，會(huì)導(dǎo)致位于路徑上的節(jié)點(diǎn)因頻繁傳遞數(shù)據(jù)而過(guò)快死亡信息素更新緩慢，且不斷揮發(fā)，所以,基本蟻群算法路徑搜索時(shí)間長(zhǎng)，易出現(xiàn)“停滯”現(xiàn)象。Dorigo M提出的Ant-Cycle模型利用全局信息更新路徑上信息素，運(yùn)算量大，時(shí)間復(fù)雜度高，尋找最優(yōu)路徑的收斂速度較慢。Stutzle T等人提出了最大最小[14]蟻群系統(tǒng)，其每一次循環(huán)只對(duì)本次循環(huán)最優(yōu)解或到目前為止找出最優(yōu)解的路徑進(jìn)行信息素更新，導(dǎo)致較長(zhǎng)時(shí)間內(nèi)多條路徑上信息素濃度相同。

2 TUCHM算法

2.1 簇頭選取

為了均衡網(wǎng)絡(luò)能耗，TUCHM算法在簇頭選擇時(shí)綜合考慮了當(dāng)前節(jié)點(diǎn)的剩余能量和簇頭之間的位置關(guān)系，提出了新的閾值函數(shù)計(jì)算公式

(5)

(6)

式中p為存活節(jié)點(diǎn)中簇頭占比；r為當(dāng)前循環(huán)輪數(shù)；G為最近1/p輪中未被選為簇頭的節(jié)點(diǎn)集合[15]；Ei為當(dāng)前節(jié)點(diǎn)i的剩余能量；Eavg為所有節(jié)點(diǎn)的平均剩余能量；χ1，χ2為式(6)兩項(xiàng)的權(quán)重值且χ1+χ2=1。

如圖1，以Sink節(jié)點(diǎn)為原點(diǎn)建立二維直角坐標(biāo)系，各簇頭與Sink節(jié)點(diǎn)連線，當(dāng)其中的BS和CS為候選簇頭a與Sink節(jié)點(diǎn)連線aS的左右鄰線時(shí)，射線l為的角平分線，θ為aS和l的夾角；當(dāng)網(wǎng)絡(luò)中還沒(méi)有選取出簇頭時(shí)，θ=0°；當(dāng)a′S只有一側(cè)存在簇頭與Sink的連線，另一側(cè)為坐標(biāo)軸時(shí)，射線l′為坐標(biāo)軸X或Y與AS形成的較小夾角的角平分線，θ′為a′S和l′的夾角。

圖1 θ角示意

2.2 構(gòu)建簇結(jié)構(gòu)

設(shè)全網(wǎng)共N個(gè)節(jié)點(diǎn)，構(gòu)建簇結(jié)構(gòu)的步驟如下：

Di=φi

(7)

式中φ為長(zhǎng)距離系數(shù)。根據(jù)文獻(xiàn)[15]可知，φ初始值一般取1.5，但當(dāng)遇到以下兩種情況時(shí)，長(zhǎng)距離系數(shù)的取值應(yīng)該適當(dāng)增大：WSNs稀疏、節(jié)點(diǎn)密度低時(shí)，長(zhǎng)距離較多，此時(shí)應(yīng)增大長(zhǎng)距離系數(shù)以適應(yīng)TUCHM算法;在WSNs運(yùn)行的中后期，由于出現(xiàn)了大量節(jié)點(diǎn)死亡，導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)間距增大，此時(shí)應(yīng)適當(dāng)增大長(zhǎng)距離系數(shù)以加快TUCHM算法收斂速度。

2)以簇頭CHi為簇中心，半徑在Di內(nèi)的鄰居節(jié)點(diǎn)以單跳形式加入簇，若同一鄰居節(jié)點(diǎn)在多個(gè)簇頭的成簇范圍內(nèi)，則選擇距離最近的簇頭加入。

δ用來(lái)控制建簇階段的收斂速度，如圖2，節(jié)點(diǎn)d,e和f各自尋找到距離自身最近的已成簇節(jié)點(diǎn)b和c，但節(jié)點(diǎn)e和f并不位于以b或c為中心、D4為半徑的范圍內(nèi)，則節(jié)點(diǎn)d首先加入簇4；然后節(jié)點(diǎn)e，f再次尋找到距離自身最近的已成簇節(jié)點(diǎn)d，但只有節(jié)點(diǎn)f位于以d為中心、D4為半徑的范圍內(nèi)，所以節(jié)點(diǎn)f加入簇4；經(jīng)過(guò)多次循環(huán)，節(jié)點(diǎn)e連續(xù)δ次尋找到距離自身最近的已成簇節(jié)點(diǎn)d，卻仍然沒(méi)有加入簇4，此時(shí)令節(jié)點(diǎn)e直接以單跳方式與節(jié)點(diǎn)d建立連接加入簇4。δ定義為

(8)

式中Nalive為當(dāng)前存活節(jié)點(diǎn)數(shù)，成簇完成后，確定一個(gè)T時(shí)隙，以降低數(shù)據(jù)冗余和傳輸沖突，簇內(nèi)節(jié)點(diǎn)根據(jù)T時(shí)隙將數(shù)據(jù)傳輸?shù)酱仡^節(jié)點(diǎn)。如圖2所示，簇內(nèi)產(chǎn)生樹型鏈?zhǔn)浇Y(jié)構(gòu)，距離簇頭較遠(yuǎn)的節(jié)點(diǎn)通過(guò)鏈中其它節(jié)點(diǎn)中轉(zhuǎn)，降低了數(shù)據(jù)傳遞路徑長(zhǎng)度。

圖2 混合層次網(wǎng)絡(luò)多跳路由

2.3 路徑選擇概率模型

如圖2，TUCHM算法采用平面網(wǎng)絡(luò)結(jié)構(gòu)與層次網(wǎng)絡(luò)結(jié)構(gòu)相結(jié)合的混合層次網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，普通節(jié)點(diǎn)間可以直接進(jìn)行通信，不需要通過(guò)簇頭節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，因此，穩(wěn)定性更好，魯棒性更高[16]；結(jié)合改進(jìn)后的蟻群算法，將簇頭的數(shù)據(jù)通過(guò)其它簇頭或普通節(jié)點(diǎn)多跳傳遞至Sink節(jié)點(diǎn)。算法首先修改路徑選擇概率模型，當(dāng)螞蟻k位于節(jié)點(diǎn)i時(shí)，計(jì)算到下一跳節(jié)點(diǎn)j的概率

(9)

式中τ為信息素濃度；η，ψ為啟發(fā)式因子

(10)

(11)

式中α和β分別為信息素和期望啟發(fā)式因子的相對(duì)重要程度；Jk(t)為螞蟻還未經(jīng)過(guò)的節(jié)點(diǎn)集合。

可以看出，啟發(fā)式因子η主要考慮當(dāng)前節(jié)點(diǎn)i的剩余能量Ei、向下一跳節(jié)點(diǎn)j發(fā)送數(shù)據(jù)需要的能量Ecost(i,j)、節(jié)點(diǎn)間距離dij與傳感器節(jié)點(diǎn)通信半徑R的比值等參數(shù)；啟發(fā)式因子ψ主要考慮下一跳節(jié)點(diǎn)j的剩余能量Ej與節(jié)點(diǎn)初始能量Einit的比值、dij與節(jié)點(diǎn)j到Sink的距離diS之和以γ角等參數(shù)。γ表示當(dāng)前節(jié)點(diǎn)到Sink的連線與當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的連線的夾角，夾角越小，下一節(jié)點(diǎn)越有可能在當(dāng)前節(jié)點(diǎn)到Sink的傳輸路徑上，啟發(fā)式因子ψ通過(guò)γ角引導(dǎo)螞蟻方向以降低經(jīng)過(guò)的節(jié)點(diǎn)數(shù)量。通過(guò)設(shè)置合理的權(quán)重值ξ1,ξ2,ξ3和ξ4可有效降低傳輸路徑長(zhǎng)度和節(jié)點(diǎn)能耗。

2.4 信息素更新

TUCHM算法在路徑信息素更新前，螞蟻先按照信息傳遞路徑長(zhǎng)度進(jìn)行排名，排名靠前的螞蟻在每次循環(huán)中額外釋放更多的信息素，給予已知最優(yōu)路徑最強(qiáng)的正反饋，加快路徑尋找速度，根據(jù)式(12)、式(13)更新路徑ij的信息素濃度值

τij(t+n)=(1-ρ)·τij(t)+Δτij

(12)

(13)

(14)

3 算法仿真與分析

3.1 仿真參數(shù)設(shè)置

為了驗(yàn)證TUCHM算法的性能，應(yīng)用MATLAB軟件與LEACH和DEEC算法進(jìn)行仿真實(shí)驗(yàn)。假設(shè)100個(gè)同構(gòu)無(wú)線傳感器節(jié)點(diǎn)在仿真區(qū)域內(nèi)隨機(jī)分布且不能移動(dòng)，當(dāng)節(jié)點(diǎn)剩余能量低于1 %后,則認(rèn)為該節(jié)點(diǎn)死亡，每個(gè)節(jié)點(diǎn)的初始能量為0.5 J，廣播包大小為25 bit，數(shù)據(jù)包大小為4 000 bit，Sink節(jié)點(diǎn)坐標(biāo)位于(0,0)m處。

3.2 仿真結(jié)果分析

圖3(a)～(d)給出了在不同大小的正方形仿真區(qū)域下存活節(jié)點(diǎn)數(shù)的對(duì)比，其邊長(zhǎng)分別為100,200,300,400 m。隨著仿真區(qū)域的不斷變大，LEACH算法越來(lái)越早出現(xiàn)斷崖式的節(jié)點(diǎn)死亡，這是因?yàn)槠浯貎?nèi)節(jié)點(diǎn)到簇頭、簇頭到Sink節(jié)點(diǎn)皆以單跳形式傳遞數(shù)據(jù)，DEEC算法由于在簇頭層采用路由樹多跳傳輸數(shù)據(jù)而比LEACH算法節(jié)約能量，但隨著仿真面積的加大，簇頭間的距離越來(lái)越遠(yuǎn)。由圖3(c)、(d)可知在大面積仿真環(huán)境下，網(wǎng)絡(luò)后期LEACH算法存在許多節(jié)點(diǎn)未完全死亡，只有個(gè)別節(jié)點(diǎn)在收集數(shù)據(jù)，但此時(shí)網(wǎng)絡(luò)已經(jīng)失效。

圖3 不同仿真區(qū)域下存活節(jié)點(diǎn)曲線對(duì)比

可以看出TUCHM算法可以在更長(zhǎng)的時(shí)間內(nèi)保證所有的節(jié)點(diǎn)都存活，這是由于非簇頭層的節(jié)點(diǎn)參與中轉(zhuǎn)數(shù)據(jù)。

從WSNs開始運(yùn)行到第一個(gè)節(jié)點(diǎn)死亡時(shí)所經(jīng)歷的輪數(shù)稱為網(wǎng)絡(luò)的穩(wěn)定周期。如圖4(a)所示，TUCHM算法的穩(wěn)定周期在邊長(zhǎng)100,200,300,400 m的正方形仿真區(qū)域下比LEACH算法分別提升大約32 %,63 %,193 %,286 %，比DEEC算法分別提升大約14 %,17 %,27 %,39 %。設(shè)網(wǎng)絡(luò)開始運(yùn)行到50 %的節(jié)點(diǎn)死亡所經(jīng)歷的輪數(shù)稱為網(wǎng)絡(luò)的生命周期。如圖4(b)所示，TUCHM算法的生命周期在邊長(zhǎng)100～400 m的正方形仿真區(qū)域下比LEACH算法分別提升大約66 %，67 %，86 %，197 %，比DEEC算法分別提升大約14 %，15 %，46 %，123 %。這是因?yàn)門UCHM算法簇內(nèi)遠(yuǎn)距離節(jié)點(diǎn)借助鏈內(nèi)節(jié)點(diǎn)中轉(zhuǎn)傳遞數(shù)據(jù)，簇頭到Sink節(jié)點(diǎn)借助普通節(jié)點(diǎn)多跳傳遞數(shù)據(jù)，有效避免了部分節(jié)點(diǎn)因遠(yuǎn)距離單跳傳遞能耗過(guò)高而失效過(guò)快。

圖4 不同仿真區(qū)域下網(wǎng)絡(luò)的穩(wěn)定周期和生命周期

圖5為網(wǎng)絡(luò)在200 m×200 m的仿真區(qū)域下消耗總能量以及網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量方差隨輪數(shù)變化的對(duì)比圖。

圖5 網(wǎng)絡(luò)消耗總能量與節(jié)點(diǎn)剩余能量方差曲線

由圖5(a)可知，LEACH和DEEC算法的曲線斜率均比TUCHM算法高，說(shuō)明LEACH和DEEC算法每輪傳輸數(shù)據(jù)消耗能量要比TUCHM高，TUCHM算法借助改進(jìn)的蟻群算法多跳傳遞數(shù)據(jù)，優(yōu)化各簇頭到Sink節(jié)點(diǎn)之間的路徑因此更加節(jié)約能量。由圖5(b)看出：LEACH算法剩余能量方差變化幅度較大，DEEC算法剩余能量方差比較穩(wěn)定但整體比TUCHM高，TUCHM算法剩余能量方差一直較低且穩(wěn)定，表明TUCHM算法能夠更好地均衡網(wǎng)絡(luò)能量，這是因?yàn)榇仡^選取同時(shí)考慮了節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)之間的位置關(guān)系，避免了螞蟻路徑重疊過(guò)多。

4 結(jié)束語(yǔ)

TUCHM算法在以下三點(diǎn)進(jìn)行改進(jìn)：1)在選取簇頭時(shí)，綜合考慮了候選節(jié)點(diǎn)的剩余能量及其位置對(duì)傳輸階段網(wǎng)絡(luò)能耗均衡的影響，使剩余能量大和螞蟻路徑重合率低的節(jié)點(diǎn)更容易當(dāng)選為簇頭；2)優(yōu)化了成簇策略，由原來(lái)的簇內(nèi)單跳、均勻分簇變?yōu)闃湫玩準(zhǔn)蕉嗵?、非均勻分簇，合理定義了成簇區(qū)域半徑，減少了遠(yuǎn)距離單跳傳遞的能量浪費(fèi)；3)采用混合層次網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，打通網(wǎng)絡(luò)下層節(jié)點(diǎn)之間的聯(lián)系，改進(jìn)路徑選擇概率模型和信息素更新模型，更好發(fā)揮蟻群算法優(yōu)化路徑的優(yōu)勢(shì)，消除了簇頭直接與Sink節(jié)點(diǎn)單跳傳遞的缺點(diǎn)。仿真結(jié)果表明：TUCHM算法在節(jié)點(diǎn)存活數(shù)量、網(wǎng)絡(luò)的穩(wěn)定周期和生命周期、均衡網(wǎng)絡(luò)能量消耗等方面有明顯的提升。