紀(jì)辛然

(山西大學(xué)商務(wù)學(xué)院，山西 太原 030031)

1 引言

無線傳感器網(wǎng)絡(luò)由多個(gè)具有通信、計(jì)算能力的傳感器節(jié)點(diǎn)以無線方式連接在一起構(gòu)成[1-2]，同時(shí)與實(shí)際網(wǎng)絡(luò)設(shè)備互相連接，共同完成特殊應(yīng)用及工作。因無線傳感器的節(jié)點(diǎn)方位無需提前設(shè)定且維護(hù)成本更低，與傳統(tǒng)有線傳感器相比無線傳感器更具靈活性。

在涉及范圍較廣的傳感器網(wǎng)絡(luò)中，利用等級(jí)化成簇路由協(xié)議是一種有效的解決方法，目前也出現(xiàn)了較多的研究成果。文獻(xiàn)[3]以潮間帶無線傳感器網(wǎng)絡(luò)(IT-WSN)為例進(jìn)行深入研究，提出期望剩余傳輸次數(shù)(PRTX)算法。 PRTX算法充分考慮網(wǎng)絡(luò)端到端延遲時(shí)間、節(jié)點(diǎn)剩余能量、鄰居節(jié)點(diǎn)之間的距離，以及鏈路質(zhì)量，并利用指數(shù)加權(quán)平均算法加強(qiáng)路由選擇的穩(wěn)定性。PRTX路由算法在節(jié)點(diǎn)通信距離變化時(shí)具有較好的性能穩(wěn)定性，但運(yùn)行能耗較高。文獻(xiàn)[4]提出基于改進(jìn)自適應(yīng)離散粒子群算法的異構(gòu)無線傳感器網(wǎng)絡(luò)路由算法，構(gòu)建綜合性目標(biāo)函數(shù)及確定評(píng)價(jià)指標(biāo)。改進(jìn)算法由于在適值函數(shù)上充分考慮簇頭節(jié)點(diǎn)能耗及簇間負(fù)載均衡因子，使得算法性能得以改良，但該算法節(jié)點(diǎn)存活率較低。文獻(xiàn)[5]提出一種基于虛擬網(wǎng)格的動(dòng)態(tài)聚簇策略IDCS，考慮數(shù)據(jù)轉(zhuǎn)發(fā)延遲的最大化網(wǎng)絡(luò)生命周期的動(dòng)態(tài)負(fù)載均衡路由算法DCDLB。IDCS依據(jù)節(jié)點(diǎn)的通信半徑將網(wǎng)絡(luò)劃分成若干虛擬網(wǎng)格，采用考慮節(jié)點(diǎn)能量和位置因素的分布式簇首選舉策略，并引入基于簇首能量水平的動(dòng)態(tài)簇首輪換機(jī)制。DCDLB綜合考慮簇首間能耗均衡和數(shù)據(jù)多跳轉(zhuǎn)發(fā)延遲來構(gòu)建路由，實(shí)現(xiàn)網(wǎng)絡(luò)生命周期的最大化，但該方法運(yùn)行能耗較高。

針對(duì)上述傳統(tǒng)方法存在的問題，本次研究提出動(dòng)態(tài)自適應(yīng)路由HDAR(Hybrid Dynamic Adaptive Routing)算法。建立雙重路由網(wǎng)絡(luò)框架，該框架將平面路由與等級(jí)路由相結(jié)合，有效降低路由數(shù)據(jù)傳輸能耗，在數(shù)據(jù)獲取過程中選取等級(jí)路由能夠有效匯總數(shù)據(jù)，。實(shí)驗(yàn)證明，采用HDAR計(jì)算方法，提高了實(shí)際操作效率，改變了路由在選擇上所受的限制，大幅度降低了網(wǎng)絡(luò)平均能耗。

2 無線傳感器網(wǎng)絡(luò)路由模型

在對(duì)平面型路由、等級(jí)型路由進(jìn)行應(yīng)用及檢測(cè)時(shí)，其各自的功能與缺陷逐漸表現(xiàn)出來，為此研發(fā)了無線傳感器網(wǎng)絡(luò)路由框架，如圖1所示，該框架主要由兩大模塊組成，即數(shù)據(jù)獲取模塊與數(shù)據(jù)傳輸模塊。

圖1 無線傳感器網(wǎng)絡(luò)路由模型

無線傳感器網(wǎng)絡(luò)在運(yùn)行時(shí)存在大量多余信息，所以每個(gè)節(jié)點(diǎn)含有大量冗余信息。若將這些數(shù)據(jù)全部傳輸至Sink節(jié)點(diǎn)，則消耗大量傳輸節(jié)點(diǎn)能量?；诖耍跀?shù)據(jù)傳輸前需對(duì)節(jié)點(diǎn)數(shù)目進(jìn)行高效率采集與融合。利用層簇方法有效地融合數(shù)據(jù)，由簇首提供制定區(qū)域范圍內(nèi)數(shù)據(jù)收集與融合的必要條件，從而在數(shù)據(jù)獲取模塊中采用成簇形式的層次路由。同時(shí)，在此模塊中選擇合適的簇首為首要任務(wù)，從而提高一定范圍內(nèi)數(shù)據(jù)的收集與融合效率，從而大幅度降低傳輸?shù)絊ink節(jié)點(diǎn)的信息量。若信息在傳輸過程中與某些節(jié)點(diǎn)傳輸形成了信息疊加，則信息量的降低能夠大量減少數(shù)據(jù)節(jié)點(diǎn)的承載量，這不僅提高了工作效率，還減少了能量的消耗，實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)的節(jié)能運(yùn)行。

由于所有融合后的數(shù)據(jù)最終都會(huì)傳送到Sink節(jié)點(diǎn)，但在傳輸過程中，會(huì)消耗大量網(wǎng)絡(luò)節(jié)點(diǎn)的能耗量。為此可通過平面路由來解決此問題，平面路由相對(duì)來說更加具有靈活性，能夠篩選出誤差較小、效率較高的方式來傳出數(shù)據(jù)，增加各個(gè)節(jié)點(diǎn)能量的均衡使用，同時(shí)能夠利用能量感知途徑選取方式實(shí)現(xiàn)所有節(jié)點(diǎn)的能量均衡，防止某個(gè)節(jié)點(diǎn)產(chǎn)生較高的能量消耗及檢測(cè)誤區(qū)[6]。

3 自適應(yīng)動(dòng)態(tài)路由算法HDAR的實(shí)現(xiàn)

根據(jù)所改進(jìn)的無線傳感器網(wǎng)絡(luò)路由模型，結(jié)合無線傳感器網(wǎng)絡(luò)運(yùn)行特性，提出一種動(dòng)態(tài)自適應(yīng)路由算法HDAR。HDAR算法主要通過兩種算法完成，一種是動(dòng)態(tài)成簇算法(APSOCH)，另一種是自適應(yīng)選擇路由算法(ASR)。在數(shù)據(jù)采集模塊中，采用改進(jìn)自適用粒子群優(yōu)化動(dòng)態(tài)成簇算法(APSOCH)[7]。基于此在數(shù)據(jù)傳輸模塊中，提出了一種由網(wǎng)絡(luò)生命階段產(chǎn)生動(dòng)態(tài)轉(zhuǎn)變的自適應(yīng)選擇路由算法(ASR)[8]。

3.1 基于ASR算法的路由節(jié)能優(yōu)化

ASR算法通過節(jié)點(diǎn)附近鄰域的能量消耗情況，來決定下一跳節(jié)點(diǎn)的重點(diǎn)研究問題，即能耗與跳數(shù)數(shù)量。

當(dāng)ASR算法選取最優(yōu)路徑時(shí)，距離最接近Sink位置的節(jié)點(diǎn)被稱為前期節(jié)點(diǎn)，相對(duì)于距Sink較遠(yuǎn)的節(jié)點(diǎn)被稱為后期節(jié)點(diǎn)，通過前期節(jié)點(diǎn)數(shù)據(jù)求出所有節(jié)點(diǎn)軌跡選取函數(shù)F，選取函數(shù)最大值當(dāng)作下一跳。該函數(shù)公式如下所示：

F(E′，Hmin)=a(E′/E)×(1-Hmin/Hmax)

+b(Hmin/Hmax)(1-E′/E)

(1)

其中，Hmin表示節(jié)點(diǎn)i到Sink的極小跳數(shù)，Hmax表示網(wǎng)絡(luò)到Sink最長距離的極小跳數(shù)。a、b表示平衡粒子，根據(jù)傳感器節(jié)點(diǎn)的疏密程度以及能量消耗情況來選擇。

ASR具體算法如下：

Step1：Sink節(jié)點(diǎn)發(fā)出一個(gè)信號(hào)，然后網(wǎng)絡(luò)節(jié)點(diǎn)根據(jù)這個(gè)信號(hào)來確定自身所在相應(yīng)點(diǎn)位。同時(shí)能夠獲得節(jié)點(diǎn)的跳數(shù)數(shù)量。

Step2：所有收到信號(hào)的節(jié)點(diǎn)都會(huì)發(fā)出指定信息，包含此節(jié)點(diǎn)的基礎(chǔ)信息、ID以及能量消耗情況，表示自己已成為Sink節(jié)點(diǎn)的一個(gè)后期節(jié)點(diǎn)。

Step3：當(dāng)節(jié)點(diǎn)處在運(yùn)行后期時(shí)，會(huì)發(fā)出新的信號(hào)，待其它節(jié)點(diǎn)的指定回復(fù)信息。若沒有收到回復(fù)信息，則轉(zhuǎn)換到Step5。

Step4：節(jié)點(diǎn)收到上游節(jié)點(diǎn)的信號(hào)后，在某一時(shí)間段內(nèi)若獲得若干個(gè)前期運(yùn)行節(jié)點(diǎn)信號(hào)，那么節(jié)點(diǎn)可通過前期節(jié)點(diǎn)信號(hào)中的能量狀況和跳數(shù)來求出函數(shù)值，然后選取最大值當(dāng)作自身前一跳節(jié)點(diǎn)，同時(shí)發(fā)出信號(hào)指定指令。

Step5：運(yùn)作一輪回結(jié)束后，再返回Step1，不斷重復(fù)，建立網(wǎng)絡(luò)核心。

綜上所述，若節(jié)點(diǎn)間能耗較為接近，那么ASR鄰近極小跳數(shù)，采用極小跳數(shù)來完成數(shù)據(jù)的轉(zhuǎn)運(yùn)，若能耗差距大，則ASR算法會(huì)通過路由選擇函數(shù)，設(shè)定新的跳數(shù)節(jié)點(diǎn)，同時(shí)在選取時(shí)要分析節(jié)點(diǎn)使用能耗狀況。在不影響節(jié)點(diǎn)所在網(wǎng)絡(luò)中過多的消耗能量，導(dǎo)致網(wǎng)絡(luò)檢測(cè)信息缺失的情況下，需要定期重新建立網(wǎng)絡(luò)核心路由，節(jié)省網(wǎng)絡(luò)耗能。

3.2 動(dòng)態(tài)成簇算法

全局優(yōu)化是算法應(yīng)用的關(guān)鍵性參數(shù)[9]。算法收斂程度會(huì)受到迭代權(quán)重的影響，權(quán)重越大越容易跳出局部最優(yōu)，權(quán)重越小越有利于加速運(yùn)轉(zhuǎn)。所以，權(quán)重會(huì)根據(jù)迭代的進(jìn)行而不斷降低，經(jīng)典的線性迭代權(quán)重如式(2)所示

(2)

式中，w代表迭代權(quán)重。當(dāng)權(quán)重不夠大時(shí)，線性的降低不能夠確保粒子跳出局部最優(yōu)，基于此，進(jìn)行非線性自適應(yīng)權(quán)重調(diào)整[10]，定義函數(shù)如式(3)所示

(3)

(4)

式中，pid代表粒子i當(dāng)前所在的最優(yōu)位置，pgd代表在進(jìn)化過程中全部粒子的最優(yōu)位置。通過自適應(yīng)函數(shù)定義[11]可知，pid大于pgd。式(3)能夠確保權(quán)重隨迭代過程不斷進(jìn)行而降低，對(duì)于權(quán)重來說，局部最優(yōu)與全局最優(yōu)是相互制約的，可根據(jù)權(quán)重的轉(zhuǎn)化進(jìn)行自適應(yīng)調(diào)節(jié)。

為實(shí)現(xiàn)均衡能耗，采用與LEACH同樣的操作模式，構(gòu)建階段優(yōu)點(diǎn)，并通過APSO來選取最優(yōu)簇首，這種方式被叫做自適應(yīng)粒子群分簇多層(Adaptive Particle Swarm Optimizational Clustering Hierarchy，APSOCH)協(xié)議建立，步驟如下：

1)預(yù)簇首初始化。利用LEACH來挑選出預(yù)簇首，但預(yù)簇首不能夠解決能量負(fù)載平衡問題。簇內(nèi)所有非簇首節(jié)點(diǎn)把它們的能量由預(yù)簇首傳輸?shù)街行墓?jié)點(diǎn)，初始化節(jié)點(diǎn)的局部最優(yōu)與全局最優(yōu)。局部最優(yōu)是指節(jié)點(diǎn)所在位置，全局最優(yōu)是指目前全部粒子的局部最優(yōu)。為了能夠讓PSO達(dá)到此問題空間，提出適應(yīng)度函數(shù)如下所示

fitness=a×f1+β×f2+γ×f3

(5)

(6)

(7)

f3=min{d(ni，BS)}

(8)

式中，f1代表能量消耗，f2表示簇間距離，f3表示節(jié)點(diǎn)到中心節(jié)點(diǎn)的距離，根據(jù)上述定義可知，f1，f2與f3都能夠確保選擇最優(yōu)簇首。S代表一定范圍內(nèi)的簇空間，E表示節(jié)點(diǎn)的能耗情況，E′表示剩余能量，|Cs|代表簇空間節(jié)點(diǎn)數(shù)量。

2)節(jié)點(diǎn)的傳輸速率更新。由于問題空間是二維[12]的，因此要將速率進(jìn)行更新，然后根據(jù)如下迭代公式進(jìn)行計(jì)算。

vid(t)=w×vid(t-1)+c1φ1(pid-xid(t-1))

+c2φ2(pgd-xid(t-1))

(9)

xid(t)=xid(t-1)+vid(t)

(10)

式中，vid和xid代表粒子i的速率與位置，c1，c2代表學(xué)習(xí)因子，φ1和φ2表示隨機(jī)數(shù)，通常取值在[0，1]之間。要確保節(jié)點(diǎn)的傳輸路徑在問題空間中，如果偏離問題空間，需要用人為方式將其控制在空間內(nèi)邊界上。

3)更新適應(yīng)度函數(shù)，若節(jié)點(diǎn)適應(yīng)度函數(shù)小于上代局部最優(yōu)函數(shù)，則更新局部最優(yōu)函數(shù)，若節(jié)點(diǎn)中最小局部最優(yōu)函數(shù)小于全局最優(yōu)函數(shù)，則更新全局最優(yōu)函數(shù)。

4)循環(huán)檢索，直到找到最初制定的最大迭代值。迭代完成后，把最優(yōu)全局函數(shù)放到適合的鄰域節(jié)點(diǎn)上，然后選取此節(jié)點(diǎn)為簇首。

5)由簇首向其它節(jié)點(diǎn)傳輸信息，由此建立動(dòng)態(tài)成簇。

在傳感器網(wǎng)絡(luò)中，已構(gòu)建的簇結(jié)構(gòu)也有可能產(chǎn)生動(dòng)態(tài)變化，如圖2(a)所示，網(wǎng)絡(luò)運(yùn)行中又產(chǎn)生了新的節(jié)點(diǎn)，則需將它融入到此運(yùn)行過程中，如圖2(b)所示，融入后的節(jié)點(diǎn)向原簇A中傳出信息，若數(shù)據(jù)傳輸?shù)乃俣葷M足目前情況時(shí)，則會(huì)向附近節(jié)點(diǎn)發(fā)出查找信息，隨著事件的不斷發(fā)展，節(jié)點(diǎn)逐漸擴(kuò)展到兩個(gè)簇結(jié)構(gòu)如圖2(c)。每一輪的簇首任務(wù)結(jié)束后，則該簇解散，簇內(nèi)節(jié)點(diǎn)又重新恢復(fù)到平等關(guān)系，并進(jìn)入抑制狀態(tài)。同時(shí)節(jié)點(diǎn)可根據(jù)事件發(fā)展情況，重新設(shè)定簇首。根據(jù)以上步驟完成無線傳感器網(wǎng)絡(luò)自適應(yīng)動(dòng)態(tài)路由算法的優(yōu)化設(shè)計(jì)。

圖2 簇動(dòng)態(tài)擴(kuò)展示意圖

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)設(shè)備采用Tiny-OS傳感器網(wǎng)絡(luò)的硬件級(jí)別仿真軟件power TOSSIM，實(shí)驗(yàn)指標(biāo)為能量消耗和節(jié)點(diǎn)存活率，以傳統(tǒng)的TEEN算法和傳統(tǒng)LEACH算法作為實(shí)驗(yàn)對(duì)照組，與研究方法的實(shí)驗(yàn)結(jié)果做對(duì)比，具體分析如下。

4.1 網(wǎng)絡(luò)耗能對(duì)比分析

將研究所提的HDAR算法與兩種傳統(tǒng)算法進(jìn)行對(duì)比分析。實(shí)驗(yàn)設(shè)置某地區(qū)無線傳感器網(wǎng)絡(luò)的100個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)作為實(shí)驗(yàn)對(duì)象，獲得30分鐘內(nèi)的平均能量消耗情況，將所提算法與兩種傳統(tǒng)方法進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果如圖3所示。

圖3 平均耗能對(duì)比

實(shí)驗(yàn)開始階段，三種方法的能耗非常接近。隨著各節(jié)點(diǎn)的傳輸，傳統(tǒng)TEEN算法和傳統(tǒng)LEACH算法消耗的能量明顯增加，主要是由于兩種傳統(tǒng)算法的全部節(jié)點(diǎn)都要在一定時(shí)間內(nèi)重新選定簇首，但在HDNA算法中，當(dāng)節(jié)點(diǎn)在傳輸過程中含有數(shù)據(jù)時(shí)，簇首由運(yùn)行數(shù)據(jù)來完成，當(dāng)節(jié)點(diǎn)在傳輸中沒有攜帶數(shù)據(jù)時(shí)則無需參與成簇的任務(wù)，從而節(jié)省了能量，同時(shí)HDAR算法中運(yùn)用了動(dòng)態(tài)成簇的方法，使融合的效率有所提高，降低了傳輸?shù)絊INK節(jié)點(diǎn)的數(shù)據(jù)量，所以傳統(tǒng)算法的能量消耗要高于HDAD。

隨著網(wǎng)絡(luò)的不斷運(yùn)行，這種優(yōu)勢(shì)會(huì)變得更加明顯，如圖4所示，描述了在相同網(wǎng)絡(luò)范圍內(nèi)，HDAR、LEACH算法與TEEN的能量消耗情況。當(dāng)網(wǎng)絡(luò)范圍較大時(shí)，能量消耗都在不斷增加，由于數(shù)據(jù)傳輸?shù)絊ink節(jié)點(diǎn)的過程存活時(shí)間變長，導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)平均能耗加強(qiáng)。當(dāng)網(wǎng)絡(luò)范圍擴(kuò)大時(shí)，TEEN算法和LEACH算法的能量消耗上升速度高于HDAR，這是因?yàn)閭鹘y(tǒng)算法下節(jié)點(diǎn)的能耗量持續(xù)增強(qiáng)，但HDAR中的能量主要用在數(shù)據(jù)匯總與融合上，所以能耗上升幅度較小，由此可以證明HDAR算法有利于大范圍網(wǎng)絡(luò)的實(shí)際應(yīng)用。

圖4 不同網(wǎng)絡(luò)規(guī)模下的能耗對(duì)比

4.2 不同算法下死亡節(jié)點(diǎn)分布對(duì)比分析

為進(jìn)一步驗(yàn)證所提算法的適用性，在相同實(shí)驗(yàn)時(shí)長1000s內(nèi)，設(shè)置600m×600m的無線網(wǎng)絡(luò)范圍內(nèi)，對(duì)不同算法應(yīng)用下的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)存活率進(jìn)行實(shí)驗(yàn)，在實(shí)驗(yàn)結(jié)果圖中，圓圈形狀標(biāo)志代表正常存活節(jié)點(diǎn)，星星形狀標(biāo)志代表死亡節(jié)點(diǎn)。具體實(shí)驗(yàn)結(jié)果如下：

圖5 死亡節(jié)點(diǎn)分布情況對(duì)比

由于TEEN算法和LEACH算法是利用在一定時(shí)間內(nèi)簇首輪換的方法來降低耗能量，導(dǎo)致運(yùn)行過程中消耗了大量能量，尤其在成簇?zé)o線傳感器網(wǎng)絡(luò)100m×400m范圍內(nèi)，死亡的節(jié)點(diǎn)數(shù)量較多。

相比之下，研究算法在整個(gè)傳感器網(wǎng)絡(luò)范圍內(nèi)死亡節(jié)點(diǎn)數(shù)量非常少，

HDAR算法在將數(shù)據(jù)傳輸?shù)絊ink時(shí)，通過自適應(yīng)路由選擇方式，分析節(jié)點(diǎn)能耗狀況，利用動(dòng)態(tài)的路由選擇算法，保留含有較少能量的節(jié)點(diǎn)，提高了網(wǎng)絡(luò)傳感器的實(shí)用性，也又減緩了傳感器節(jié)點(diǎn)衰敗的速率，一直持續(xù)到全部節(jié)點(diǎn)消失。通過實(shí)驗(yàn)結(jié)果可以說明，HDAR提高了網(wǎng)絡(luò)傳感器運(yùn)轉(zhuǎn)效率，更加適用于現(xiàn)實(shí)生活中。

5 結(jié)論

此次研究建立了兩種路由互相合作的無線傳感器網(wǎng)絡(luò)路由框架，分別為層次路由和平面路由，同時(shí)結(jié)合了動(dòng)態(tài)成簇自適應(yīng)路由算法HDAR。該算法包含運(yùn)行數(shù)據(jù)動(dòng)態(tài)成簇算法和能量自適應(yīng)路由選擇算法。實(shí)驗(yàn)分析證明HDAR算法具有較高的適用性，利于大范圍的網(wǎng)絡(luò)操作，能夠降低網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗，并有效提升網(wǎng)絡(luò)的運(yùn)行時(shí)長。