齊世霞 薛小偉

（1.延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 陜西省延安市 716000 2.延安大學(xué)附屬醫(yī)院 陜西省延安市 716000）

1 引言

無線傳感器網(wǎng)絡(luò)是當(dāng)前眾多學(xué)科研究的熱點(diǎn)，是實(shí)現(xiàn)數(shù)據(jù)的采集、處理和傳輸于一體的綜合型智能網(wǎng)絡(luò)，目前正處于蓬勃發(fā)展的階段，隨著其應(yīng)用越來越廣泛，對諸多領(lǐng)域都具有巨大影響。無線傳感器網(wǎng)絡(luò)由微傳感器節(jié)點(diǎn)組成，這些節(jié)點(diǎn)既可以獲取信息數(shù)據(jù)，也可以進(jìn)行網(wǎng)絡(luò)中繼。每個(gè)傳感器節(jié)點(diǎn)都由傳感器、微處理器以及無線收發(fā)機(jī)組成，傳感器節(jié)點(diǎn)與節(jié)點(diǎn)之間互相緊密相連以獲取物理數(shù)據(jù)。傳感器節(jié)點(diǎn)通過片上微處理器完成復(fù)雜任務(wù)，通過無線收發(fā)機(jī)實(shí)現(xiàn)互連及數(shù)據(jù)傳輸。傳感器節(jié)點(diǎn)一般都是非動(dòng)態(tài)的，由能量有限的電池提供能源，從而導(dǎo)致網(wǎng)絡(luò)拓?fù)湓诠?jié)點(diǎn)位置不變的情況下也可能會因?yàn)槠淠芰抗芾聿僮鞫l(fā)生動(dòng)態(tài)變化。在這種情況下，使傳感器節(jié)點(diǎn)功耗最小并保持通信是最重要的，高能效機(jī)制的無線傳感器網(wǎng)絡(luò)相對于還依舊依賴電池的系統(tǒng)具有更長的生存周期。在無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)協(xié)議棧中，網(wǎng)絡(luò)層的研究最多，其路由協(xié)議的分類以及具體的解決算法主要分為以下四類，如圖1 所示。

圖1 ：WSN 路由協(xié)議分類

2 基于分層結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)路由協(xié)議

基于分層結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)路由協(xié)議在分層結(jié)構(gòu)中組成簇，分簇算法將通信限制在局部區(qū)域且只向剩余的網(wǎng)絡(luò)部分發(fā)送必要的信息，一組節(jié)點(diǎn)形成一個(gè)簇，簇成員之間通過簇頭進(jìn)行交互。無線通信的不穩(wěn)定性和傳感器網(wǎng)絡(luò)的特點(diǎn)等這些問題阻礙了應(yīng)用于WSN 中針對無線自組織網(wǎng)絡(luò)的路由協(xié)議的發(fā)展。為了盡可能的降低能耗，使WSN 的生存周期更長，已經(jīng)提出了許多基于分層結(jié)構(gòu)的路由算法協(xié)議，主要包括以下幾種常見算法：高效自治算法LEACH，執(zhí)行過程按“輪”進(jìn)行，每輪包括兩個(gè)階段，即簇的形成階段和穩(wěn)定工作階段，由每個(gè)節(jié)點(diǎn)根據(jù)隨機(jī)數(shù)自主決定是否當(dāng)簇頭，保證各個(gè)節(jié)點(diǎn)等概率的擔(dān)任簇頭；以節(jié)點(diǎn)地理位置為依據(jù)的分簇算法GAF，最初應(yīng)用在Ad Hoc 網(wǎng)絡(luò)中，采用虛擬單元格劃分機(jī)制，根據(jù)地理位置信息將整個(gè)網(wǎng)絡(luò)劃分成很多虛擬小區(qū)域，每個(gè)小區(qū)域內(nèi)定期選舉一個(gè)簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)為正常工作狀態(tài)，剩余節(jié)點(diǎn)為休眠狀態(tài)，每個(gè)小區(qū)域內(nèi)的節(jié)點(diǎn)互相協(xié)作；PEGASIS 算法提出了構(gòu)造節(jié)點(diǎn)鏈來解決簇重疊區(qū)域的問題，鏈的創(chuàng)建采用貪婪算法，選擇距離自己最近的鄰居節(jié)點(diǎn)進(jìn)行下一跳；混合能量效率分布式分簇HEED算法是，以節(jié)點(diǎn)的剩余能量作為首要因素，簇內(nèi)的通信代價(jià)作為次要因素來進(jìn)行簇頭的選擇和分簇，按輪進(jìn)行，每輪包括分簇階段和網(wǎng)絡(luò)運(yùn)行階段；TEEN 算法采用多級分簇結(jié)構(gòu)，簇內(nèi)節(jié)點(diǎn)將采集到的數(shù)據(jù)傳送給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)對數(shù)據(jù)進(jìn)行進(jìn)一步處理后，再傳送給比它高一級的簇頭，層層遞進(jìn)，最終將數(shù)據(jù)傳送到匯聚節(jié)點(diǎn)，通過設(shè)計(jì)設(shè)置硬門限和軟門限兩種門限值來提供基于響應(yīng)的應(yīng)用，以減少發(fā)送數(shù)據(jù)的次數(shù)；APTEEN 算法是在TEEN 算法基礎(chǔ)上發(fā)展起來的，簇內(nèi)節(jié)點(diǎn)采用時(shí)分復(fù)用的方式進(jìn)行數(shù)據(jù)傳輸，通過設(shè)置軟硬兩種門限值確定發(fā)送數(shù)據(jù)的時(shí)間和頻率；TopDisc算法是基于最小支配集模型提出的分簇算法，采用啟發(fā)式的方法建立骨干網(wǎng)絡(luò)拓?fù)?，采用顏色?biāo)記理論來選擇簇頭節(jié)點(diǎn)，該算法可以在密集部署的傳感器網(wǎng)絡(luò)中快速的形成分簇，但在產(chǎn)生簇頭時(shí)沒有考慮剩余能量的問題；SOP 算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為兩類，傳感器節(jié)點(diǎn)是動(dòng)態(tài)的并負(fù)責(zé)收集數(shù)據(jù)，路由節(jié)點(diǎn)是靜態(tài)的用于形成主干網(wǎng)；EARSN 協(xié)議算法是基于三層體系結(jié)構(gòu)的路由協(xié)議，由終端用戶在網(wǎng)絡(luò)運(yùn)行前就對傳感器節(jié)點(diǎn)進(jìn)行分簇且簇頭不受能量控制，算法依據(jù)兩個(gè)節(jié)點(diǎn)間的能量消耗、延遲最優(yōu)化等性能指標(biāo)計(jì)算路徑代價(jià)函數(shù)，簇頭節(jié)點(diǎn)再以此作為鏈路成本選擇最優(yōu)路徑；除了上述算法外，還有GEAR、SPAN、MECH 等分簇算法，各種基于分層結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)路由協(xié)議的性能比較如表1 所示。

表1 ： WSN 路由協(xié)議的性能比較

武小年等通過定義節(jié)點(diǎn)的能量因子和位置均衡因子建立新的適應(yīng)度函數(shù)，選擇出優(yōu)秀的候選簇頭節(jié)點(diǎn)，之后再通過優(yōu)化的自適應(yīng)學(xué)習(xí)因子加快其位置更新速度；王宗山等提出一種基于人工蜂群算法的能量高效分簇路由協(xié)議，在簇頭選舉時(shí)通過定義能量因子、位置因子和向心率因子設(shè)計(jì)高效的適應(yīng)度函數(shù)，在穩(wěn)定傳輸時(shí)通過在每個(gè)簇頭和基站間尋找合適路徑并引入了輪詢控制機(jī)制來平衡且降低網(wǎng)絡(luò)能耗；趙東方等提出了基于路由樹的分布式自適應(yīng)動(dòng)態(tài)多跳分簇路由協(xié)議DABMC，設(shè)置剩余能量和延遲時(shí)間來選擇簇首，簇間路由為以sink 節(jié)點(diǎn)為根節(jié)點(diǎn)的動(dòng)態(tài)路由樹來選擇下一跳；茍平章等通過AGNES 算法進(jìn)行均勻分簇，然后根據(jù)剩余能量、節(jié)點(diǎn)與基站之間的距離以及兩者的權(quán)重因子進(jìn)行分布式簇頭選舉，并采用改進(jìn)后的最短路徑優(yōu)先算法進(jìn)行多跳路由；王海浪等通過對整個(gè)網(wǎng)絡(luò)區(qū)域進(jìn)行均勻分區(qū)優(yōu)化以及改進(jìn)綜合節(jié)點(diǎn)的剩余能量、區(qū)域內(nèi)平均能量、距離基站的距離等多個(gè)因素來作為判斷是否選擇成為簇頭節(jié)點(diǎn)；張本宏等提出一種基于二分K-means 的均勻分簇算法UCOA，利用二分K-means 算法對整個(gè)網(wǎng)絡(luò)均勻分簇，加入節(jié)點(diǎn)的剩余能量、距離因子對簇頭選舉閾值公式進(jìn)行改進(jìn)；王出航等提出一種基于改進(jìn)遺傳算法的WSN 信任感知安全路由方法，采用單個(gè)染色體編碼進(jìn)行簇頭選擇和路由搜索；胡黃水等提出一種結(jié)合近鄰傳播算法AP 和遺傳算法的分簇路由協(xié)議EAPGA，根據(jù)剩余能量、節(jié)點(diǎn)間距離、節(jié)點(diǎn)到基站的距離以及節(jié)點(diǎn)中心度選擇最優(yōu)簇頭，再通過簇頭能耗偏差和遺傳算法進(jìn)行尋優(yōu)；和煦等提出一種基于改進(jìn)正弦余弦算法的分簇路由協(xié)議CRISCA，將正弦余弦算法和慣性權(quán)重因子進(jìn)行結(jié)合，得到改進(jìn)的正弦余弦算法進(jìn)行最優(yōu)簇頭的選擇；蘭婷婷等設(shè)計(jì)了一種最優(yōu)廣域WSN 數(shù)據(jù)聚合模型ODAM，在無線接收器中進(jìn)行節(jié)點(diǎn)間的計(jì)算，采用花粉算法FPA 對聚合模型進(jìn)行優(yōu)化來確保簇中能量的有效排列；趙小強(qiáng)等提出了一種基于模擬退火SA 算法和改進(jìn)灰狼優(yōu)化器GWO的HWSN 路由協(xié)議SA-MGWO，在選取簇時(shí)根據(jù)節(jié)點(diǎn)能量的異構(gòu)性對節(jié)點(diǎn)定義不同的適應(yīng)度函數(shù)來計(jì)算適應(yīng)值，之后根據(jù)狼群與獵物的距離以及系數(shù)向量對該值進(jìn)行動(dòng)態(tài)更新，最后利用模擬退火算法選取最優(yōu)簇集；余修武等提出了一種基于螢火蟲算法優(yōu)化模糊C 均值的WSN 路由算法FFACM,在分簇時(shí)采用螢火蟲算法計(jì)算初始聚類中心，建立適應(yīng)度函數(shù)選取簇首節(jié)點(diǎn)并動(dòng)態(tài)更新，建立代價(jià)函數(shù)選擇簇間多跳路由，降低簇首節(jié)點(diǎn)的負(fù)載；李蕾等提出一種基于證據(jù)理論加權(quán)融合的無線傳感器網(wǎng)絡(luò)路由算法，引入聚類分析算法進(jìn)行分簇，之后后采用證據(jù)理論計(jì)算剩余能量、節(jié)點(diǎn)間通信距離、通信能耗的權(quán)值進(jìn)行綜合評價(jià)才選出簇首。

3 基于LEACH協(xié)議的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議優(yōu)化設(shè)計(jì)思路

3.1 LEACH協(xié)議概述

LEACH 主要通過基于簇的操作使WSN 減少功耗，按照輪次周期性的進(jìn)行執(zhí)行，每個(gè)輪次由分為兩個(gè)階段，在一個(gè)輪次中保持簇不變但重新選擇簇頭，每個(gè)輪次分為建立階段和穩(wěn)態(tài)階段兩個(gè)階段。

在建立階段主要進(jìn)行簇頭選舉并進(jìn)行分簇，在簇的形成階段，采用循環(huán)選舉機(jī)制，使得各個(gè)節(jié)點(diǎn)等概率的擔(dān)任簇頭。其選舉簇頭的過程為：假設(shè)網(wǎng)絡(luò)中有N 個(gè)節(jié)點(diǎn)，每輪執(zhí)行過程生產(chǎn)k 個(gè)簇。每個(gè)節(jié)點(diǎn)i 在第r+1 輪選舉開始時(shí)產(chǎn)生一個(gè)0～1 之間的隨機(jī)數(shù)，如果這個(gè)數(shù)小于設(shè)定的閾值P(t)，則該節(jié)點(diǎn)被選為簇頭節(jié)點(diǎn)。閾值P(t)的計(jì)算公式為：

在式（1）中，r 表示選舉輪次數(shù)，k 表示選舉的簇頭數(shù)目，N 表示網(wǎng)絡(luò)中的總節(jié)點(diǎn)數(shù)，C(t)=0 表示節(jié)點(diǎn)i 已經(jīng)當(dāng)選過簇頭，C(t)=1 表示還未當(dāng)選過簇頭，即只有在以前的輪次中沒有做過簇頭的節(jié)點(diǎn)才能成為當(dāng)前輪次的簇頭；在式（2）中，R(i)為0～1 之間的一個(gè)隨機(jī)數(shù)，P(i,r)表示節(jié)點(diǎn)i 在第r 輪次成為簇頭的概率。當(dāng)選舉輪次數(shù)r=N/k 時(shí)，一個(gè)循環(huán)選舉周期結(jié)束，所有節(jié)點(diǎn)都正好當(dāng)選過一次簇頭。在節(jié)點(diǎn)成為簇頭后，采用CSMA 的MAC 協(xié)議向鄰居節(jié)點(diǎn)廣播通告自己成為簇頭的消息，避免多個(gè)簇頭的廣播發(fā)生碰撞。

在穩(wěn)定階段，進(jìn)行數(shù)據(jù)傳輸，簇內(nèi)節(jié)點(diǎn)在各自分配的時(shí)隙內(nèi)向簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)，其他時(shí)間睡眠以減少消耗，簇頭節(jié)點(diǎn)一直保持活躍，進(jìn)行數(shù)據(jù)融合等任務(wù)并將處理結(jié)果發(fā)送給匯聚節(jié)點(diǎn)。在持續(xù)工作一段時(shí)間后，網(wǎng)絡(luò)重新選取下一輪次的簇頭并建立新簇。為了節(jié)省資源降低功耗，LEACH 穩(wěn)定階段的持續(xù)時(shí)間要比建立階段的時(shí)間長。

3.2 LEACH算法的優(yōu)化思路

LEACH 算法將簇頭責(zé)任分配給具有更高剩余能量的節(jié)點(diǎn)，且使所有節(jié)點(diǎn)可以等概率的擔(dān)任簇頭，避免了簇頭過分消耗能量，提高了整個(gè)網(wǎng)絡(luò)的生存時(shí)間，但是它由每個(gè)節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)對比設(shè)定的閾值來確定是否成為簇頭節(jié)點(diǎn)，每個(gè)周期選舉生成的簇頭的數(shù)量和位置都會發(fā)生改變，除此之外，周期性的選舉簇頭過于頻繁，引發(fā)的通信量也耗費(fèi)了大量能量。

在LEACH 協(xié)議的基礎(chǔ)上，在簇頭節(jié)點(diǎn)選取時(shí)引入成本函數(shù)，每個(gè)節(jié)點(diǎn)的成本被定義為一個(gè)函數(shù)，這個(gè)函數(shù)表示為：

在式（3）和（4）中，E(s)表示節(jié)點(diǎn)j 的剩余能量，E(x,y)為節(jié)點(diǎn)所在感知區(qū)域的剩余總能量，C 為節(jié)點(diǎn)i 的感知區(qū)域。

簇頭的選擇基于每個(gè)節(jié)點(diǎn)的感知成本，一個(gè)簇內(nèi)成員的節(jié)點(diǎn)只能發(fā)送信息到相應(yīng)的簇頭，從節(jié)點(diǎn)i 到匯聚節(jié)點(diǎn)的一條路的感知成本可以定義為：

在式（5）和（6）中，C(s,s)是每條鏈路的成本，C(s)是基于成本函數(shù)的節(jié)點(diǎn)成本，E(s,s)和E(s,s)分別是發(fā)送和接收一個(gè)分組數(shù)據(jù)消耗的能量。通過在式（5）和（6）就可以得到一條簇頭到匯聚節(jié)點(diǎn)的最小成本路徑。

基于成本函數(shù)的操作執(zhí)行可以分為六個(gè)階段：

第一階段：節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)交換剩余的能量信息，每個(gè)節(jié)點(diǎn)計(jì)算自己的感知成本。

第二階段：簇頭選擇階段，鄰居范圍內(nèi)最小成本且能量大于一定閾值的節(jié)點(diǎn)被選為簇頭。

第三階段：建立簇頭和匯聚節(jié)點(diǎn)之間的端到端路徑，網(wǎng)絡(luò)中任何節(jié)點(diǎn)通過最小成本路徑從匯聚節(jié)點(diǎn)收到路由并發(fā)現(xiàn)消息。

第四階段：形成簇，每個(gè)非簇頭節(jié)點(diǎn)選擇最近的簇頭然后通過發(fā)送一個(gè)入簇消息加入該簇。

第五階段：激活傳感器節(jié)點(diǎn)。

第六階段：每個(gè)活動(dòng)節(jié)點(diǎn)收集自身信息并上報(bào)給簇頭，簇頭匯聚來自簇內(nèi)多個(gè)傳感器節(jié)點(diǎn)的數(shù)據(jù)并發(fā)送給匯聚節(jié)點(diǎn)。

4 結(jié)語

從無線傳感器網(wǎng)絡(luò)的發(fā)展現(xiàn)狀來看，在國內(nèi)外，基于分層結(jié)構(gòu)的WSN 路由協(xié)議一直在不斷地發(fā)展且取得了不錯(cuò)的研究成果。本文針對傳統(tǒng)的LEACH 協(xié)議在簇頭節(jié)點(diǎn)的選擇及拓?fù)浣Y(jié)構(gòu)上的缺點(diǎn)，提出了一種改進(jìn)的LEACH 算法的優(yōu)化設(shè)計(jì)思路，采用基于成本函數(shù)的方法進(jìn)行簇頭的選擇和路由的建立，得到簇頭節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的最小成本路徑，在感知范圍和生命周期之間有一個(gè)較好的平衡。在今后的研究工作中，需要在有限的條件下，實(shí)現(xiàn)真實(shí)WSN 系統(tǒng)的搭建，以便進(jìn)一步研究該優(yōu)化改進(jìn)算法的性能，從而使簇頭節(jié)點(diǎn)的通信路徑選擇更加科學(xué)合理。