一種抗干擾半靜態(tài)分簇路由算法*

?！∶?，李敬兆，葛　斌

(1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001；2.安徽理工大學(xué) 電氣與信息工程學(xué)院，安徽 淮南 232001)

?

一種抗干擾半靜態(tài)分簇路由算法*

祝敏1，李敬兆2，葛斌1

(1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001；2.安徽理工大學(xué) 電氣與信息工程學(xué)院，安徽 淮南 232001)

摘要:針對(duì)無(wú)線傳感器網(wǎng)絡(luò)(WSNs)分簇路由算法中的能量洞、熱點(diǎn)和抗干擾問(wèn)題，設(shè)計(jì)一種抗干擾半靜態(tài)分簇(AISSC)路由算法，給無(wú)線傳感器網(wǎng)絡(luò)提供能量多、距離短、鏈路質(zhì)量好的路徑來(lái)傳輸數(shù)據(jù)。該算法利用節(jié)點(diǎn)定位獲取節(jié)點(diǎn)地理位置，綜合考慮傳感器節(jié)點(diǎn)剩余能量和干擾信噪比，通過(guò)節(jié)點(diǎn)距離度量、節(jié)點(diǎn)聚簇、簇間融合、簇頭選舉和簇頭輪換五個(gè)步驟進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的分簇。仿真結(jié)果表明:這種路由算法可以提高無(wú)線傳感器網(wǎng)絡(luò)通信鏈路質(zhì)量，均衡網(wǎng)絡(luò)能量消耗。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)； 抗干擾半靜態(tài)分簇(AISSC)路由算法； 信噪比

0引言

無(wú)線傳感器網(wǎng)絡(luò)[1](wireless sensor networks，WSNs)具有組網(wǎng)快速、方便且不受有線網(wǎng)絡(luò)約束的特點(diǎn)，廣泛應(yīng)用于軍事安全、環(huán)境監(jiān)測(cè)和智能交通等領(lǐng)域。但傳感器節(jié)點(diǎn)一般分布在人無(wú)法接近的特殊環(huán)境中，無(wú)法補(bǔ)充能量，導(dǎo)致網(wǎng)絡(luò)能源受限；規(guī)模大、密度高的傳感器節(jié)點(diǎn)，導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)間通信干擾問(wèn)題。傳感器節(jié)點(diǎn)能量主要消耗在采集數(shù)據(jù)、處理數(shù)據(jù)、接收和發(fā)送數(shù)據(jù)上。其中，接收和發(fā)送數(shù)據(jù)消耗的能量最多。因此，路由算法在無(wú)線傳感器網(wǎng)絡(luò)能量方面起著重要作用，優(yōu)化路徑和抗干擾是路由算法兩個(gè)重點(diǎn)研究的問(wèn)題。

本文在傳統(tǒng)分簇路由算法[2]的基礎(chǔ)上，創(chuàng)新地將傳感器節(jié)點(diǎn)干擾信噪比(SNR)和節(jié)點(diǎn)剩余能量加入節(jié)點(diǎn)距離度量的計(jì)算，綜合考慮網(wǎng)絡(luò)開(kāi)銷和網(wǎng)絡(luò)抗干擾性能，設(shè)計(jì)一種抗干擾半靜態(tài)分簇(anti-interference semi static clustering，AISSC)路由算法，可以有效均衡網(wǎng)絡(luò)能量消耗。

1無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法現(xiàn)狀分析

現(xiàn)有分簇路由算法主要為了解決三類問(wèn)題：一是能量洞問(wèn)題，二是熱點(diǎn)問(wèn)題，三是鏈路質(zhì)量問(wèn)題。

1)關(guān)于能量洞問(wèn)題

2000年,Heizelman W提出第一種分簇路由算法LEACH[3]，算法主要思想是：在無(wú)線傳感器網(wǎng)絡(luò)中隨機(jī)選擇幾個(gè)簇頭，向非簇頭節(jié)點(diǎn)發(fā)布邀請(qǐng)信息，節(jié)點(diǎn)根據(jù)邀請(qǐng)信號(hào)強(qiáng)度決定加入哪個(gè)簇。在LEACH基礎(chǔ)上，Heizelman W又提出一種算法LEACH—C，節(jié)點(diǎn)把自身地理位置、能量和鄰接關(guān)系等信息直接發(fā)送給Sink節(jié)點(diǎn)，Sink節(jié)點(diǎn)擇優(yōu)選擇簇頭。所有節(jié)點(diǎn)直接與Sink節(jié)點(diǎn)通信，導(dǎo)致離Sink節(jié)點(diǎn)較遠(yuǎn),節(jié)點(diǎn)能耗過(guò)大。HEED算法簇頭選舉主要參考節(jié)點(diǎn)的剩余能量信息，但是，每次選舉簇頭需要簇內(nèi)節(jié)點(diǎn)通過(guò)大量通信來(lái)反饋結(jié)果，節(jié)點(diǎn)能耗較大。TEEN算法按照LEACH算法進(jìn)行節(jié)點(diǎn)的聚簇和簇頭選擇，在簇頭節(jié)點(diǎn)設(shè)置軟硬兩個(gè)閾值以減少發(fā)送數(shù)據(jù)次數(shù)，降低網(wǎng)絡(luò)能耗，但是閾值的設(shè)置缺少理論依據(jù)。

2)關(guān)于熱點(diǎn)問(wèn)題

針對(duì)熱點(diǎn)問(wèn)題，文獻(xiàn)[4]提出很多分簇路由算法,主要思想都是采用非均勻半徑聚簇方法進(jìn)行傳感器節(jié)點(diǎn)分簇。距離Sink節(jié)點(diǎn)較近的簇頭，不僅要接收簇內(nèi)節(jié)點(diǎn)的信息，還要轉(zhuǎn)發(fā)外層簇的信息。因此，需要形成較多簇，分擔(dān)轉(zhuǎn)發(fā)信息的任務(wù)；距離Sink節(jié)點(diǎn)較遠(yuǎn)的簇頭，主要負(fù)責(zé)收集簇內(nèi)信息，轉(zhuǎn)發(fā)消息的任務(wù)較少，可以形成較少簇。但是，聚簇半徑大小的設(shè)置缺少理論依據(jù)，而且這種算法比較復(fù)雜，能耗過(guò)大。

3)關(guān)于鏈路質(zhì)量問(wèn)題

一些算法是在泛洪算法的基礎(chǔ)上，利用鏈路空間相關(guān)性或者構(gòu)造最優(yōu)鏈路樹(shù)，優(yōu)化轉(zhuǎn)發(fā)路徑。文獻(xiàn)[5]提出一種考慮鏈路質(zhì)量的路由選擇機(jī)制算法EXT，把期望傳輸次數(shù)作為路由選擇參考。文獻(xiàn)[6]在EXT算法基礎(chǔ)上進(jìn)行改進(jìn)，選擇路徑時(shí)考慮累計(jì)鏈路質(zhì)量，進(jìn)一步優(yōu)化路徑，但是，算法未考慮傳感器節(jié)點(diǎn)能量問(wèn)題，導(dǎo)致節(jié)點(diǎn)成為傳輸熱點(diǎn)。文獻(xiàn)[7]提出一種較為全面且考慮鏈路質(zhì)量的分簇路由算法，算法采用多路徑轉(zhuǎn)發(fā)機(jī)制，但是傳感器節(jié)點(diǎn)需要經(jīng)常計(jì)算和保存不同路徑的權(quán)重，能耗較大。

2AISSC路由算法

2.1干擾信噪比的計(jì)算

衡量一個(gè)無(wú)線傳感器網(wǎng)絡(luò)鏈路質(zhì)量的參數(shù)評(píng)估可以分為兩類：基于軟件的參數(shù)評(píng)估和基于硬件的參數(shù)評(píng)估，如圖1所示。

圖1　鏈路質(zhì)量評(píng)估的參數(shù)分類Fig 1　Parameters classification of link quality assessment

基于軟件的評(píng)估參數(shù)有：包接收率(packet reception rate,PRR),需要的包數(shù)(required number of packet,RNP),基于分?jǐn)?shù)(score-based)?；谲浖逆溌焚|(zhì)量評(píng)估參數(shù)需要通過(guò)網(wǎng)絡(luò)長(zhǎng)期發(fā)送和接收探測(cè)包來(lái)進(jìn)行估值，導(dǎo)致較大網(wǎng)絡(luò)通信量。

本文采用基于硬件的評(píng)估參數(shù)SNR來(lái)衡量網(wǎng)絡(luò)鏈路質(zhì)量，它的值可以直接通過(guò)讀取接收信號(hào)強(qiáng)度指標(biāo)寄存器的值計(jì)算出來(lái)。SNR表示接收到有用信號(hào)的強(qiáng)度與干擾信號(hào)的強(qiáng)度比值。SNR計(jì)算公式為

(1)

其中，Power為接收到有用數(shù)據(jù)幀的信號(hào)強(qiáng)度，Noise包括壞境噪聲和其他節(jié)點(diǎn)形成的干擾信號(hào)噪聲。實(shí)驗(yàn)中，傳播模型采用雙徑地面反射模型，接收端Powerr為

(2)

式中d為接收端到發(fā)送端的實(shí)際距離，Powert為發(fā)送端數(shù)據(jù)幀的信號(hào)強(qiáng)度，Gt和Gr分別為發(fā)送端和接收端的天線收益，ht和hr為發(fā)送端和接收端天線的高度，L為系統(tǒng)損耗。在本文實(shí)驗(yàn)中，Powert可以進(jìn)行設(shè)置，Gt,Gr和L均設(shè)為1，ht和hr設(shè)為1.5m。

因此，當(dāng)節(jié)點(diǎn)正接收數(shù)據(jù)幀，其他數(shù)據(jù)幀也到來(lái)時(shí)，接收端對(duì)應(yīng)的SNR為

(3)

式中Power為根據(jù)式(2)計(jì)算的接收到有用數(shù)據(jù)幀信號(hào)強(qiáng)度，Poweri為其他數(shù)據(jù)幀的信號(hào)強(qiáng)度。

2.2AISSC路由策略

AISSC主要思想是：利用節(jié)點(diǎn)定位算法獲取節(jié)點(diǎn)地理位置信息為基礎(chǔ)，在傳感器節(jié)點(diǎn)分簇時(shí)，綜合考慮節(jié)點(diǎn)剩余能量、干擾信噪比和節(jié)點(diǎn)間實(shí)際地理距離，在每個(gè)簇頭節(jié)點(diǎn)增加一個(gè)簇內(nèi)節(jié)點(diǎn)鏈表存儲(chǔ)節(jié)點(diǎn)實(shí)時(shí)信息，包括地理位置信息、剩余能量和SNR值。根據(jù)各個(gè)節(jié)點(diǎn)的“簇內(nèi)節(jié)點(diǎn)距離和(SEPC)”的值，在簇頭鏈表中節(jié)點(diǎn)按照倒序排列。當(dāng)簇頭能量低于一定閾值，按照SEPC值順序，自動(dòng)進(jìn)行簇頭輪換。具體步驟如下：

1)節(jié)點(diǎn)間距離的度量

在二維歐氏距離公式基礎(chǔ)上，加入節(jié)點(diǎn)剩余能量和干擾信噪比。改進(jìn)后傳感器節(jié)點(diǎn)間距離計(jì)算如式(4)所示

(4)

式中E為傳感器節(jié)點(diǎn)初始能量，Ea和Eb為任意兩節(jié)點(diǎn)當(dāng)前能量值，SNRa和SNRb為節(jié)點(diǎn)當(dāng)前信噪比。

2)初始節(jié)點(diǎn)聚簇

聚簇時(shí)，每個(gè)節(jié)點(diǎn)把自己看作簇頭，向其他節(jié)點(diǎn)發(fā)送簇融合的信息包，收到信息包的節(jié)點(diǎn)計(jì)算與信息來(lái)源簇之間的距離，計(jì)算如式(5)所示

(5)

式中DPGMA為簇間的平均距離，m，n為任意兩個(gè)簇的節(jié)點(diǎn)數(shù)，D(i,j)為式(4)中節(jié)點(diǎn)i和j之間的距離。

聚簇的同時(shí)由簇頭創(chuàng)建并維護(hù)一個(gè)簇內(nèi)節(jié)點(diǎn)鏈接表，動(dòng)態(tài)更新簇內(nèi)節(jié)點(diǎn)剩余能量、SNR信息和地理位置信息，表內(nèi)節(jié)點(diǎn)的順序按照SEPC的值倒序排列，SEPC計(jì)算方式如式(6)所示

(6)

式中m為簇內(nèi)節(jié)點(diǎn)數(shù)，i和j為簇內(nèi)任意兩節(jié)點(diǎn)。

3)簇間融合、簇頭選舉和簇頭輪換

根據(jù)步驟(2)，距離最近的兩個(gè)簇進(jìn)行融合，合并簇內(nèi)節(jié)點(diǎn)鏈接表。按式(6)計(jì)算簇內(nèi)每個(gè)節(jié)點(diǎn)SEPC值，更新鏈接表，SEPC值最小的節(jié)點(diǎn)當(dāng)選為簇頭。如果網(wǎng)絡(luò)中所有簇都滿足簇的規(guī)模閾值限定，則停止聚簇；否則，簇頭發(fā)送含有新的簇內(nèi)節(jié)點(diǎn)信息的融合數(shù)據(jù)包，重新計(jì)算與其他簇的距離，進(jìn)行簇間融合，按照式(6)推選出新的簇頭。

當(dāng)前簇頭的能量低于一定的閾值后，鏈接表傳遞給下一個(gè)將要擔(dān)任簇頭的節(jié)點(diǎn)，簇內(nèi)自動(dòng)執(zhí)行簇頭輪換操作。

4)重新聚簇

一段時(shí)間后，簇內(nèi)所有節(jié)點(diǎn)都不滿足擔(dān)任簇頭的要求時(shí)，當(dāng)前簇頭向Sink節(jié)點(diǎn)發(fā)送重新聚簇的信號(hào)，所有節(jié)點(diǎn)重新聚簇。步驟同樣可以分為節(jié)點(diǎn)距離度量、初始聚簇、簇間融合、簇頭選舉和簇頭輪換。

3仿真結(jié)果分析

實(shí)驗(yàn)采用NS2仿真軟件，在相同場(chǎng)景參數(shù)下分別對(duì)LEACH算法、LEACH—C算法和AISSC算法的性能進(jìn)行比較，驗(yàn)證AISSC算法的有效性和可行性。網(wǎng)絡(luò)性能分析指標(biāo)采用網(wǎng)絡(luò)丟包率和網(wǎng)絡(luò)中剩余節(jié)點(diǎn)數(shù)。仿真場(chǎng)景參數(shù)設(shè)置如表1所示。選用802.11MAC層協(xié)議，無(wú)線傳播模型采用雙徑地面反射模型。

表1　場(chǎng)景參數(shù)

1)網(wǎng)絡(luò)丟包率比較

圖2顯示了LEACH,LEACH—C,AISSC算法在相同場(chǎng)景下網(wǎng)絡(luò)丟包率的比較，未考慮節(jié)點(diǎn)干擾SNR的分簇路由算法LEACH和LEACH—C算法網(wǎng)絡(luò)丟包率近似。仿真進(jìn)行1 800 s時(shí)，LEACH算法丟包率是4.6 %，LEACH—C算法丟包率是4.2 %，綜合考慮節(jié)點(diǎn)剩余能量、干擾SNR和地理位置的AISSC算法丟包率是2.5 %，相比LEACH—C算法降低了2.1 %。實(shí)驗(yàn)結(jié)果表明:AISSC算法降低了網(wǎng)絡(luò)丟包率。

圖2　不同算法的網(wǎng)絡(luò)丟包率比較Fig 2　Comparison of network packet loss rate ofdifferent algorithms

2)網(wǎng)絡(luò)剩余節(jié)點(diǎn)數(shù)比較

圖3顯示了不同算法在相同場(chǎng)景下網(wǎng)絡(luò)剩余節(jié)點(diǎn)數(shù)的比較，實(shí)驗(yàn)進(jìn)行到1 800 s時(shí)，LEACH算法中剩余節(jié)點(diǎn)數(shù)為80個(gè)，改進(jìn)算法LEACH—C中剩余節(jié)點(diǎn)數(shù)為99個(gè)，AISSC算法中節(jié)點(diǎn)剩余數(shù)為112個(gè)。AISSC算法相比LEACH—C算法，剩余節(jié)點(diǎn)數(shù)增加13個(gè)，相比LEACH算法，增加32個(gè)。圖中每個(gè)算法消亡速率曲線變化也不同， AISSC算法曲線斜率最大，說(shuō)明節(jié)點(diǎn)能量均衡性較好。因此，表明 AISSC算法有效均衡網(wǎng)絡(luò)能量消耗。

圖3　不同算法的網(wǎng)絡(luò)剩余節(jié)點(diǎn)數(shù)比較Fig 3　Comparison of network alive nodes number ofdifferent algorithms

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

本文分析了現(xiàn)有分簇路由算法，針對(duì)這些算法的優(yōu)勢(shì)和缺陷，設(shè)計(jì)一種能量有效的AISSC路由算法。首先，算法通過(guò)在計(jì)算節(jié)點(diǎn)距離時(shí)加入節(jié)點(diǎn)剩余能量和干擾SNR，有效減緩網(wǎng)絡(luò)中能量洞問(wèn)題和干擾問(wèn)題；其次，算法制定特殊的簇內(nèi)節(jié)點(diǎn)管理機(jī)制，使無(wú)線傳感器網(wǎng)絡(luò)在聚簇的同時(shí)進(jìn)行簇內(nèi)節(jié)點(diǎn)的排序，自動(dòng)進(jìn)行簇頭的輪換；最后，設(shè)計(jì)再次聚簇的機(jī)制，將能耗小的節(jié)點(diǎn)置于簇的中心，增加其充當(dāng)簇頭的概率，有效改善了網(wǎng)絡(luò)熱點(diǎn)問(wèn)題。因此，AISSC算法綜合考慮干擾問(wèn)題、能量洞問(wèn)題和熱點(diǎn)問(wèn)題，能有效降低網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。

參考文獻(xiàn):

[1]任豐原,黃海寧,林闖.無(wú)線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào),2003,14(7):1282-1291.

[2]沈波,張世永,鐘亦平.無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報(bào),2006,17(7):1588-1600.

[3]HeinzelmanW,ChandrakasanA,BalakrishnanH.Energy-efficientcommunicationprotocolforwirelesssensornetworks[C]∥2000IEEEProceedingsoftheHawaiiInternationalConferenceonSystemSciences,Hawaii,2000:3005-3014.

[4]申志遠(yuǎn),劉方愛(ài),侯冰俏,等.節(jié)能高效的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].傳感器與微系統(tǒng),2013,32(12):67-70,77.

[5]CoutoD,AguayoD,BicketJ,et,al.Ahigh-throughputpathmetricformulti-hopwirelessrouting[J].WirelessNetworks,2005,11(4):419-434.

[6]袁正午,梁均軍.累積鏈路質(zhì)量無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議研究[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(14):66-69.

[7]DialloC,MarotM,BeckerM.Linkqualityandlocalloadbalancingroutingmechanismsinwirelesssensornetworks[C]∥2010TheSixthAdvancedInternationalConferenceonTelecommunications(AICT),2010:306-315.

An anti-interference semi static clustering routing algorithm*

ZHU Min1， LI Jing-zhao2， GE Bin1

(1.School of Computer Science and Engineering,Anhui University of Science and Technology,Huainan 232001,China; 2.College of Electrical and Information Engineering,Anhui University of Science and Technology,Huainan 232001,China)

Abstract:To solve energy hole,hot issue and anti-interference problem in clustering routing algorithm for wireless sensor networks(WSNs),an anti-interference semi static clustering(AISSC) routing algorithm is proposed.A path of more energy,short distance and good link quality is provided to transmit datas.The algorithm obtains geographical position of nodes by node localization,the residual energy of sensor node and signal noise ratio are synthetically considered,clustering of WSNs node is carried out through five steps,which are distance measurement,nodes clustering,clusters fusion,the cluster head election and cluster head rotation.Simulation result indicates that the algorithm can improve the link quality of WSNs communication,balance the network energy consumption.

Key words:wireless sensor networks(WSNs); anti-interference semi static clustering(AISSC) routing algorithm; signal noise ratio(SNR)

DOI:10.13873/J.1000—9787(2016)02—0147—03

收稿日期：2015—05—15

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(6117060)；安徽省自然科學(xué)基金資助項(xiàng)目(1408085ME110)

中圖分類號(hào)：TP 393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1000—9787(2016)02—0147—03

作者簡(jiǎn)介:

祝敏(1989- )，女，安徽安慶人，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。