低冗余度WSN 非均勻分簇算法應(yīng)用研究

陳 樹，韓 進，蔣 偉

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

1 概述

無線傳感器網(wǎng)絡(luò)理論研究模型大都基于高節(jié)點冗余度的網(wǎng)絡(luò)，但在很多應(yīng)用場景中，部署高冗余度的無線傳感網(wǎng)絡(luò)是不現(xiàn)實的。通常用于工業(yè)生產(chǎn)的無線傳感網(wǎng)絡(luò)節(jié)點價格比較高，不會有大量的冗余節(jié)點，這就造成了整個網(wǎng)絡(luò)節(jié)點的低冗余度。這種低冗余度要求整個系統(tǒng)數(shù)據(jù)傳輸?shù)哪芎木鶆蚍植己蛡鞲泄?jié)點之間的能耗均勻，避免出現(xiàn)節(jié)點早衰現(xiàn)象。作為傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸路徑選擇的路由策略對均衡節(jié)點能耗負載、節(jié)省通信能量、延長網(wǎng)絡(luò)生存時間起決定作用［1］。但常規(guī)的路由協(xié)議不能簡單直接地應(yīng)用到低冗余度的網(wǎng)絡(luò)中，必須選擇基本的路由算法并進行適當(dāng)?shù)匦薷?，以符合實際應(yīng)用場景。通過對現(xiàn)有無線傳感器網(wǎng)絡(luò)路由算法的研究，發(fā)現(xiàn)分簇路由協(xié)議技術(shù)能顯著降低數(shù)據(jù)延遲，提高能量利用率，有效延長網(wǎng)絡(luò)生命周期，相比之下具有更好的適用性。目前，研究者已就如何延長無線傳感器網(wǎng)絡(luò)生存時間提出多種分簇路由協(xié)議。例如，Heinzelman 等人提出了經(jīng)典的低功耗自適應(yīng)分簇協(xié)議LEACH［2］，設(shè)計思想是隨機按“輪”的形式以一定概率周期性的循環(huán)選擇簇首節(jié)點，即讓節(jié)點輪流擔(dān)任簇首，從而將網(wǎng)絡(luò)中的能量負載平均分配到每個傳感器節(jié)點，延長網(wǎng)絡(luò)生存周期。但此算法是隨機選取簇頭，難以保證每輪的簇頭數(shù)目一致和簇頭在網(wǎng)絡(luò)中均勻分布，無法確保整個網(wǎng)絡(luò)能耗的均衡性，可能會出現(xiàn)節(jié)點成堆死亡的情況。之后Heinzelman 等人又提出了LEACH-C 算法［3］，該算法雖然提高了成簇質(zhì)量，采用多跳的簇間路由機制，但是其網(wǎng)絡(luò)流量、時間延遲及信號干擾的概率會增加，成簇開銷也增大，存在嚴重“熱區(qū)”問題。文獻［4］提出了一種EECS 的非均勻分簇算法，該算法通過選舉得到簇首節(jié)點，剩余節(jié)點根據(jù)通信代價公式，選擇加入到代價最小的簇中，從而構(gòu)造大小不同的簇以均衡簇首負載，然后簇首以單跳的方式與基站通信。之后文獻［5］又提出了一種新的非均勻分簇路由算法EEUC，構(gòu)造不同規(guī)模的簇來改善多跳路由的“熱區(qū)”問題。但上述2 種算法都存在簇首數(shù)目隨機和簇間傳輸方式單一的問題，造成簇首能耗不易控制。

對于低冗余度網(wǎng)絡(luò)，任何節(jié)點的過早死亡、能耗不均和不穩(wěn)定因素都會給工業(yè)生產(chǎn)過程造成較大影響。由于上述各種分簇協(xié)議均存在一些問題，因此不能直接應(yīng)用到低冗余度的網(wǎng)絡(luò)。針對該問題，本文提出一種基于粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法和最短路由樹的分簇路由算法。該算法在EEUC 協(xié)議基礎(chǔ)上引入粒子群算法優(yōu)化非均勻分簇過程，并將所有簇首節(jié)點以基站為根構(gòu)成最短路由樹，樹內(nèi)節(jié)點通過多跳路由將數(shù)據(jù)傳輸給基站。

2 網(wǎng)絡(luò)模型

2.1 前提假設(shè)

假設(shè)無線傳感器網(wǎng)絡(luò)的特性如下:

(1)節(jié)點均勻部署在方形網(wǎng)絡(luò)中，且位置不再變動;基站位于網(wǎng)絡(luò)空間外側(cè)，其能量和計算能力不受限制，傳輸范圍覆蓋整個網(wǎng)絡(luò)。

(2)簇首節(jié)點和普通節(jié)點的ID 號均唯一，且簇首節(jié)點具有數(shù)據(jù)融合和轉(zhuǎn)發(fā)能力。

(3)節(jié)點位置坐標(biāo)已事先測得，發(fā)射功率可根據(jù)接收節(jié)點的距離自動調(diào)節(jié)。

(4)每個普通節(jié)點最大通信半徑設(shè)為Rmax，簇首節(jié)點的競爭半徑設(shè)為Rc。

(5)算法無需周期性地從普通節(jié)點中選取簇首節(jié)點，由控制中心根據(jù)選簇機制一次性選取固定數(shù)目的簇首節(jié)點，最后可由工作人員根據(jù)選好的最優(yōu)簇首組合的位置部署簇首節(jié)點。

2.2 能量模型

無線傳感器網(wǎng)絡(luò)的能耗大部分來自通信，通信所消耗的能量比感知和計算所消耗的能量要大得多，本文不考慮節(jié)點運算和存儲所消耗的能量，參考文獻［2］得到本文算法的無線通信能耗模型，發(fā)送和接收l 字節(jié)數(shù)據(jù)的消耗能量分別為:

其中，l 表示收發(fā)的字節(jié)數(shù);d 表示通信距離;在文獻［5］中若通信距離小于閾值d0，功率放大損耗采用自由空間模型;若通信距離不小于閾值d0時，采用多路徑衰減模型;Eelec表示收發(fā)電路的基本功耗系數(shù);Efs，Eamp表示功率放大電路的功耗系數(shù)。

3 本文算法

基于粒子群和最短路由樹的非均勻分簇路由算法采用集中式控制策略［6］，簇首選舉和最短路由樹建立過程的能量開銷都由能量不受限制的基站承擔(dān)執(zhí)行，從而減少網(wǎng)絡(luò)傳感節(jié)點的能耗，較好地適應(yīng)了低冗余度無線傳感網(wǎng)絡(luò)。整個算法過程分為3 個階段:粒子群優(yōu)化的非均勻分簇階段;基站和簇首節(jié)點之間建立最短路由樹階段;數(shù)據(jù)傳輸和路由更新階段。

3.1 非均勻分簇

非均勻分簇階段分為簇首選取和普通節(jié)點加入簇，而簇首選取引入粒子群優(yōu)化算法完成非均勻分簇。PSO 算法具有收斂速度快、算法簡單和易于實現(xiàn)等優(yōu)點，在求解單目標(biāo)優(yōu)化問題上是一種有效的方法［7］，將其引入簇首選取階段可以減少非均勻分簇算法的復(fù)雜度。

首先，為達到非均勻分簇效果，分簇時引入大小不同的競爭半徑，如式(3)所示，競爭半徑是根據(jù)簇首到基站距離計算得到，使得遠離基站的簇首數(shù)量少，成簇規(guī)模大;靠近基站的簇首數(shù)量多，成簇規(guī)模?。?］。

其中，λ 屬于［0，1］的常數(shù);Dmax和Dmin分別表示簇首節(jié)點和基站之間距離的最大值和最小值;d(Cm，BS)表示簇首節(jié)點Cm到基站的距離;R0為競爭半徑最大值。

其次，在PSO 算法優(yōu)化分簇過程時，適應(yīng)值函數(shù)設(shè)定是否理想直接決定最終選取的簇首優(yōu)劣。根據(jù)本文研究背景，算法將簇內(nèi)通信代價和簇首位置作為適應(yīng)值函數(shù)的影響因子。因此，PSO 算法的適應(yīng)值函數(shù)可構(gòu)造為:

其中，f1(pi)為成簇緊湊性評價因子，等于普通節(jié)點至其簇首的最大平均歐式距離;Cpi，m表示粒子pi中簇首Cm所屬普通節(jié)點數(shù)目;f2(pi)為所有簇首包含節(jié)點數(shù)之和與節(jié)點總數(shù)比值的倒數(shù)，表示簇首節(jié)點覆蓋范圍的大小;α 和β 屬于［0，1］且α+β=1，通過調(diào)節(jié)f1(pi)和f2(pi)在適應(yīng)值函數(shù)中所占比例，從而優(yōu)化簇分布及簇選擇。根據(jù)適應(yīng)值函數(shù)的定義，本文PSO 優(yōu)化分簇過程可以簡單描述為:在假定的網(wǎng)絡(luò)搜索空間中，找到一個最優(yōu)簇首組合(M 個簇首)，使得適應(yīng)函數(shù)值最小。PSO 優(yōu)化分簇算法基本步驟如下:

(1)初始化Q 個粒子，每個粒子包含M 個簇首節(jié)點，代表一種可能的分簇方式。

(2)初始化每個粒子pi:

1)初始化粒子pi的位置，即從［0，L］內(nèi)隨機產(chǎn)生一個實數(shù)作為每個粒子位置向量中每一維的值。

2)初始化粒子pi的速度，即從［-V，V］內(nèi)隨機產(chǎn)生一個實數(shù)作為每個粒子速度向量中每一維的值。

(3)計算每個粒子的適應(yīng)函數(shù)值:

1)對于每個普通節(jié)點ci(i=1，2，…，N)，計算其到所有簇首節(jié)點Cm(m=1，2，…，M)的距離d(ci，CHpi，m);根據(jù)式(3)計算每個簇首的競爭半徑，并計算其競爭半徑范圍內(nèi)所包含的的節(jié)點數(shù)Cpi，m。

2)運用式(4)～式(6)計算粒子的適應(yīng)函數(shù)值fit(pi)。

(4)確定每個粒子的局部最優(yōu)解和種群最優(yōu)解。

(5)根據(jù)文獻［7］中的粒子群算法基本公式更新每個粒子的位置和速度。

(6)重復(fù)步驟(3)～步驟(5)，直至達到最大迭代次數(shù)。

最后，當(dāng)基站從上位機得到最優(yōu)簇首組合及簇成員信息后，廣播非均勻分簇結(jié)果給每個節(jié)點，普通節(jié)點加入簇，組建網(wǎng)絡(luò)的分簇階段基本完成。

3.2 最短路由樹的建立

本文采用Dijkstra 算法建立基站和簇首之間的最短路由樹。Dijkstra 算法是解決關(guān)于帶權(quán)有向圖的最短路徑問題的一種貪心算法，它要逐個地找出從源節(jié)點出發(fā)到所有其他節(jié)點的最短路徑，算法的本質(zhì)特征是能夠確定路徑順序，按照加權(quán)長度順序首先找出最短路徑，直至最后找出從源節(jié)點到所有節(jié)點的最短路徑［9］。

為了均衡簇間多跳傳輸?shù)哪芎?，將?jié)點的傳輸能耗、剩余能量和成簇規(guī)模作為路由樹邊的權(quán)值公式影響因子，公式如式(7)所示。

其中，W(i，j)表示圖中連接相鄰簇首節(jié)點i 和節(jié)點j的邊的權(quán)值;Etx(l，d)表示節(jié)點j 向節(jié)點i 發(fā)送l 比特數(shù)據(jù)所消耗的能量，其大小可根據(jù)式(1)計算得到;Re(i)，Re(j)分別表示節(jié)點i 和節(jié)點j 的剩余能量;Cn(i)和N 分別表示節(jié)點i 的簇成員數(shù)和網(wǎng)絡(luò)普通節(jié)點總數(shù);ε 和θ 是屬于［0，1］的常數(shù);ω 為公式歸一化常數(shù)。

根據(jù)前提假設(shè)，網(wǎng)絡(luò)中簇首一旦選定，其拓撲結(jié)構(gòu)不再改變，因此，在每輪采集周期中，所有簇首節(jié)點間的拓撲結(jié)構(gòu)可用一個帶權(quán)值的有向連通圖G=(V，E)表示，其中，V 表示網(wǎng)絡(luò)中所有的簇首節(jié)點(包括基站)的集合;E 表示圖中所有邊的集合。本文為了便于簇間多跳路徑的建立，根據(jù)簇首到基站的距離將所有簇首節(jié)點分屬不同的層次，處于n 層的簇首和基站通信需要n -1 層的簇首節(jié)點進行轉(zhuǎn)發(fā)，且簇首節(jié)點不對來自上一層的簇首數(shù)據(jù)包進行融合處理，只是轉(zhuǎn)發(fā)給自己的下一跳簇首，這樣可以形成較好的樹型結(jié)構(gòu)［10］。假設(shè)源頂點到某個節(jié)點v的通信代價為D(v)，表示從源頂點到節(jié)點v 所經(jīng)過的整條鏈路權(quán)值之和。則利用Dijkstra 算法構(gòu)造最短路由樹的步驟如下:

(1)初始化。設(shè)網(wǎng)絡(luò)頂點集合為U，選擇基站為源頂點S0，并加入到集合U 中，此時U={S0}，對于所有不在U 中的節(jié)點v，有如下公式:

其中，W(s0，v)可根據(jù)式(7)計算得到;∞可以用一很大的數(shù)值代替，只要比樹中任何邊的權(quán)值大就行。

(2)從V-U 的集合中找到節(jié)點u，且其D(u)的值最小，然后將其加入到U 中。接著對所有其他V-U中的節(jié)點v，用{D(v)，D(u)+W(u，v)}中的較小的值去更新原有的D(v)值，即:

(3)重復(fù)步驟(2)，直至所有簇首節(jié)點都在U 中為止，即U=V。

最終建立完成以基站為根的最短路由樹?；緞t根據(jù)最短路由樹計算出每個簇首節(jié)點的路由表信息并將其廣播給所有簇首節(jié)點，然后簇首節(jié)點可以按照路由表，將數(shù)據(jù)發(fā)送給各自的下一跳節(jié)點，最終將數(shù)據(jù)轉(zhuǎn)發(fā)給基站。網(wǎng)絡(luò)模型如圖1 所示。

圖1 最短路由樹網(wǎng)絡(luò)模型

3.3 數(shù)據(jù)傳輸和路由更新

數(shù)據(jù)傳輸主要分為簇內(nèi)傳輸和簇間傳輸2 個階段。簇內(nèi)傳輸時，節(jié)點按照時分多址(Time Division Multiple Address，TDMA)的方式將檢測數(shù)據(jù)傳輸給簇首節(jié)點;簇間傳輸時，簇首節(jié)點根據(jù)已經(jīng)建立好的最短路由樹將融合好的數(shù)據(jù)傳輸給自己的父節(jié)點，然后經(jīng)過轉(zhuǎn)發(fā)，最終到達基站［11］。

簇間多跳傳輸階段，必須考慮某一條路徑中轉(zhuǎn)發(fā)節(jié)點能耗過快而提早死亡的情況。因此，在每一輪傳輸結(jié)束后，基站重新計算路由樹中各邊的權(quán)值，當(dāng)某條邊的權(quán)值高于設(shè)定的閾值時，則對最短路由樹進行動態(tài)更新。參考文獻［12］得到本文算法動態(tài)路由更新的基本過程如下:

(1)網(wǎng)絡(luò)中某條邊的權(quán)值過高導(dǎo)致網(wǎng)絡(luò)路徑被割斷，原來的最短路由樹被分為了2 棵獨立的樹，此時需要變更路徑。

(2)將原來最短路由樹中到源頂點的最短路徑?jīng)]有改變的樹中節(jié)點構(gòu)成集合TN1，而被切斷的樹中的節(jié)點構(gòu)成集合TN2。

(3)將集合TN2 中的節(jié)點再按照上一節(jié)中Dijkstra 算法的基本思路逐個地加入到集合TN1 中，同時將對應(yīng)節(jié)點從TN2 中刪除，直到集合TN2為空。

最后便得到了動態(tài)更新后的最短路由樹。利用此方法不需要重新計算生成整個網(wǎng)絡(luò)的最短路由樹，不但節(jié)省了計算時間，而且還避免了不必要的網(wǎng)絡(luò)能耗。

4 實驗結(jié)果及分析

為評估本文算法在低冗余度的無線傳感器網(wǎng)絡(luò)中的可用性和有效性，筆者引入EECS 和EEUC 算法與之比較。仿真環(huán)境和具體參數(shù)如下:在100 ×100的方形區(qū)域均勻部署200 個傳感器節(jié)點;控制包大小200 bit;數(shù)據(jù)包大小4 000 bit;節(jié)點初始能量總和100 J，簇首數(shù)目M=10，基站坐標(biāo)(50，125);λ=0.5，R0=70 m;ε=0.3，θ=0.5，ω=1 000。PSO 參數(shù)設(shè)置［7］:種群規(guī)模Q=50;學(xué)習(xí)因子c1=c2=2;慣性因子w=0.8;r1，r2 隨機給出;α=0.7，β=0.3;最大迭代次數(shù)為100。

將本文算法和EECS、EEUC 算法進行比較后可知，EECS 算法為均衡節(jié)點能耗，將節(jié)點分成大小不同的簇，但是簇首與基站的通信采用簡單的單跳機制，容易過快地消耗簇首能量，而導(dǎo)致整個網(wǎng)絡(luò)的生存周期變短。EEUC 算法則在非均勻分簇的基礎(chǔ)上，簇間采用多跳路由方式傳輸和轉(zhuǎn)發(fā)數(shù)據(jù)，所以消耗的能量更少，一定程度上延長了網(wǎng)絡(luò)生命周期。不同于上述2 種算法，本文算法不僅在分簇階段引入粒子群算法優(yōu)化選簇過程，而且在數(shù)據(jù)傳輸和轉(zhuǎn)發(fā)階段，采用多跳路由并通過建立最短路由樹的形式尋求最優(yōu)路徑，以及動態(tài)路由更新機制，使得能量消耗比其他算法要慢的多，顯著地延長了網(wǎng)絡(luò)有效生命時間。

EEUS、EECS 和本文算法存活節(jié)點數(shù)隨著網(wǎng)絡(luò)生命時間的變化情況如圖2 所示。

圖2 網(wǎng)絡(luò)節(jié)點存活數(shù)量比較

可以看出，在相對有效的網(wǎng)絡(luò)生命時間里(存活節(jié)點數(shù)大于100)，EECS 和EEUC 算法分別在243 輪和345 輪時開始出現(xiàn)第1 個節(jié)點的死亡，而本文算法將第1 個節(jié)點的死亡時間推遲到649 輪，這是因為本文算法相比于其他2 種算法有如下優(yōu)勢:

(1)為了均衡網(wǎng)絡(luò)能耗，在選擇簇首時，利用PSO 算法選取最優(yōu)簇首組合分布信息，而EECS 和EEUC 的簇首數(shù)目都是隨機的，很容易造成能耗不均的問題。

(2)通過在基站與簇首之間建立最短路由樹的形式尋找最優(yōu)路徑以及采用動態(tài)更新路由機制，減少了多跳傳輸?shù)哪芎模行У匮娱L了網(wǎng)絡(luò)生命周期。

(3)根據(jù)低冗余度WSN 的特點，本文算法在WSN 初始能量相同的情況下，采用簇首和普通節(jié)點能量差異化分配機制，使得簇首節(jié)點的初始能量略高于普通節(jié)點的初始能量，這樣可以延長固定簇首生命時間，保證網(wǎng)絡(luò)有效運行。

EEUS、EECS 和本文算法前100 輪采集周期各個協(xié)議簇首平均能耗變化如圖3 所示?？梢钥闯觯珽ECS 算法的簇首平均能耗處于偏高的位置振蕩，原因是EECS 算法中所有簇首采用單跳方式與基站通信，比EEUC 算法和本文算法的簇間多跳傳輸方式要消耗更多的能量。而EECS 和EEUC 算法簇首平均能耗出現(xiàn)不穩(wěn)定的振蕩現(xiàn)象，則是由于2 種算法在選擇簇首時數(shù)目是隨機的，導(dǎo)致簇首多時，能耗低;反之，能耗高的問題，造成節(jié)點能耗不均衡。所以，本文算法所采用的選簇方式和簇間多跳路徑選擇機制使得簇首平均能耗處于低位穩(wěn)定的狀態(tài)，能夠較好地均衡節(jié)點能耗，延長網(wǎng)絡(luò)壽命。

圖3 網(wǎng)絡(luò)簇首平均能耗比較

5 結(jié)束語

本文針對低冗余度的無線傳感器網(wǎng)絡(luò)，提出一種基于粒子群和最短路由樹的非均勻分簇路由算法，該算法具有如下特點:(1)利用PSO 算法優(yōu)化分簇過程，一次性選擇固定數(shù)目簇首，不僅滿足實際網(wǎng)絡(luò)簡單穩(wěn)定的要求，還降低了算法復(fù)雜度，提高了分簇效率;(2)通過建立最短路由樹的方式進行數(shù)據(jù)的傳輸和轉(zhuǎn)發(fā)以及動態(tài)地更新最短路由樹，能夠很好地均衡網(wǎng)絡(luò)節(jié)點能耗;(3)用來檢測參數(shù)的普通節(jié)點不擔(dān)任簇首，節(jié)點能耗更均衡、壽命更長，保證了檢測質(zhì)量。仿真結(jié)果表明，本文算法在應(yīng)用到節(jié)點冗余度低的無線傳感器網(wǎng)絡(luò)中時，能有效降低節(jié)點死亡速度，延長網(wǎng)絡(luò)有效生存時間，為進一步應(yīng)用到工業(yè)生產(chǎn)中的低冗余度無線傳感器網(wǎng)絡(luò)提供理論依據(jù)。

［1］沈 波，張世永，鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.軟件學(xué)報，2006，17(7):1588-1600.

［2］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Sensor Networks ［C］//Proceedings of the 33rd Hawaii International Conference on System Sciences.Hawaii，USA:［s.n.］，2000:3005-3014.

［3］Heinzelman W.An Application-specific Protocol Architecture for Wireless MicroSensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［4］Ye Mao，Li Chengfa，Chen Guihai，et al.EECS:An Energy Efficient Cluster Scheme in Wireless Senor Networks［C］//Proceedings of the 24th IEEE Inter-national Conference on Performance，Computing，and Communications.Phoenix，USA:IEEE Press，2005:535-540.

［5］李成法，陳貴海，吳 杰，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計算機學(xué)報，2007，30(1):27-36.

［6］蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議［J］.軟件學(xué)報，2012，23(5):1223-1231.

［7］蘇 兵，黃冠發(fā).基于粒子群優(yōu)化的WSN 非均勻分簇路由算法［J］.計算機應(yīng)用，2011，31(9):2340-2343.

［8］李 鑒，石 馨，劉賀平.煤礦巷道無線傳感器網(wǎng)絡(luò)非均勻分簇數(shù)據(jù)傳送機制［J］.中國地質(zhì)大學(xué)學(xué)報，2013，38(1):196-200.

［9］Conmen T H，Leiserson C E，Rivest R L，et al.算法導(dǎo)論［M］.2 版.潘金貴，顧鐵成，李成法，等，譯.北京:機械工業(yè)出版社，2006.

［10］尚鳳軍，任東海.無線傳感器網(wǎng)絡(luò)中分布式多跳路由算法研究［J］.傳感技術(shù)學(xué)報，2012，25(4):530-534.

［11］張明才，薛安榮，王 偉.基于最小生成樹的非均勻分簇路由算法［J］.計算機應(yīng)用，2012，32(3):787-790.

［12］Narvaez P，Siu K Y，Tzeng H Y.New Dynamic Algorithms for Shortest Path Tree Computation［J］.IEEE/ACM Transactions on Networking，2000，8(9):734-746.