?！∶?，李敬兆，葛　斌

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

?

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

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

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

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

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

0引言

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

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

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

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

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

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

2)關(guān)于熱點問題

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

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

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

2AISSC路由算法

2.1干擾信噪比的計算

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

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

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

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

(1)

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

(2)

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

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

(3)

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

2.2AISSC路由策略

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

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

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

(4)

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

2)初始節(jié)點聚簇

聚簇時，每個節(jié)點把自己看作簇頭，向其他節(jié)點發(fā)送簇融合的信息包，收到信息包的節(jié)點計算與信息來源簇之間的距離，計算如式(5)所示

(5)

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

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

(6)

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

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

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

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

4)重新聚簇

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

3仿真結(jié)果分析

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

表1　場景參數(shù)

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

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

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

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

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

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

4結(jié)束語

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

參考文獻:

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

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

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

[4]申志遠,劉方愛,侯冰俏,等.節(jié)能高效的無線傳感器網(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ǎng)絡(luò)路由協(xié)議研究[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

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

中圖分類號：TP 393

文獻標(biāo)識碼：A

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

作者簡介:

祝敏(1989- )，女，安徽安慶人，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)。