一種抗干擾半靜態分簇路由算法*

祝　敏，李敬兆，葛　斌

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

?

一種抗干擾半靜態分簇路由算法*

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

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

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

關鍵詞：無線傳感器網絡； 抗干擾半靜態分簇(AISSC)路由算法； 信噪比

0引言

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

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

1無線傳感器網絡分簇路由算法現狀分析

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

1)關于能量洞問題

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

2)關于熱點問題

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

3)關于鏈路質量問題

一些算法是在泛洪算法的基礎上，利用鏈路空間相關性或者構造最優鏈路樹，優化轉發路徑。文獻[5]提出一種考慮鏈路質量的路由選擇機制算法EXT，把期望傳輸次數作為路由選擇參考。文獻[6]在EXT算法基礎上進行改進，選擇路徑時考慮累計鏈路質量，進一步優化路徑，但是，算法未考慮傳感器節點能量問題，導致節點成為傳輸熱點。文獻[7]提出一種較為全面且考慮鏈路質量的分簇路由算法，算法采用多路徑轉發機制，但是傳感器節點需要經常計算和保存不同路徑的權重，能耗較大。

2AISSC路由算法

2.1干擾信噪比的計算

衡量一個無線傳感器網絡鏈路質量的參數評估可以分為兩類：基于軟件的參數評估和基于硬件的參數評估，如圖1所示。

圖1　鏈路質量評估的參數分類Fig 1　Parameters classification of link quality assessment

基于軟件的評估參數有：包接收率(packet reception rate,PRR),需要的包數(required number of packet,RNP),基于分數(score-based)。基于軟件的鏈路質量評估參數需要通過網絡長期發送和接收探測包來進行估值，導致較大網絡通信量。

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

(1)

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

(2)

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

因此，當節點正接收數據幀，其他數據幀也到來時，接收端對應的SNR為

(3)

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

2.2AISSC路由策略

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

1)節點間距離的度量

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

(4)

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

2)初始節點聚簇

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

(5)

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

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

(6)

式中m為簇內節點數，i和j為簇內任意兩節點。

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

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

當前簇頭的能量低于一定的閾值后，鏈接表傳遞給下一個將要擔任簇頭的節點，簇內自動執行簇頭輪換操作。

4)重新聚簇

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

3仿真結果分析

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

表1　場景參數

1)網絡丟包率比較

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

圖2　不同算法的網絡丟包率比較Fig 2　Comparison of network packet loss rate ofdifferent algorithms

2)網絡剩余節點數比較

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

圖3　不同算法的網絡剩余節點數比較Fig 3　Comparison of network alive nodes number ofdifferent algorithms

4結束語

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

參考文獻:

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

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

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

[4]申志遠,劉方愛,侯冰俏,等.節能高效的無線傳感器網絡非均勻分簇路由協議[J].傳感器與微系統,2013,32(12):67-70,77.

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

[6]袁正午,梁均軍.累積鏈路質量無線傳感器網絡路由協議研究[J].計算機工程與應用,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

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

中圖分類號：TP 393

文獻標識碼：A

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

作者簡介:

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