無線傳感器網(wǎng)絡(luò)改進(jìn)的GAF算法研究

盧欣　朱正禮　朱紅紅

摘要：傳感器節(jié)點能量有限一直以來都是無線傳感器網(wǎng)絡(luò)的關(guān)鍵所在。針對該問題對傳統(tǒng)的GAF（geographic adaptive fidelity，GAF）算法進(jìn)行了改進(jìn)。改進(jìn)的GAF算法引入了支持向量回歸機(jī)（Support Vector Regression，SVR）來優(yōu)化虛擬單元格的劃分，同時將正方形網(wǎng)格改為圓形區(qū)域；另外，通過改變圓形區(qū)域的半徑來加強(qiáng)相鄰區(qū)域的連通性。結(jié)果顯示，與傳統(tǒng)的GAF算法相比，改進(jìn)后的算法具有更大的優(yōu)勢，降低了節(jié)點能耗。

關(guān)鍵詞： 支持向量回歸機(jī)；GAF算法；虛擬單元格；節(jié)點能耗

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）05-0194-04

Abstract： The limited energy of sensor nodes had been the key of Wireless Sensor Networks.To solve the problem，traditional GAF algorithm was improved.Improved GAF algorithm introduced SVR to optimize virtual cells division and paints circular areas to replace the square grids.In addition，connectivity between adjacent areas were strengthened by changing the radius of the circular areas.Results showed that compared with the traditional GAF algorithm， the improved algorithm had a greater advantage， and reduced the energy consumption of nodes.

Key words： support vector regression；GAF algorithm；virtual cell；energy consumption of nodes

1 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）是由眾多傳感器節(jié)點以自組織和多跳方式組成的傳感網(wǎng)絡(luò)[1]。隨著技術(shù)的進(jìn)步，WSN廣泛應(yīng)用于軍事、環(huán)境監(jiān)測、城市交通和智能家居等領(lǐng)域。由于傳感器節(jié)點的體積小，攜帶的能量是有限的，通常部署在復(fù)雜的無人值守的環(huán)境中，因此WSN面臨的重要挑戰(zhàn)是如何提高能量的利用率來延長整個網(wǎng)絡(luò)的生存時間。

GAF算法[2]是一種拓?fù)淇刂扑惴?，是由Xu等人針對無線傳感器網(wǎng)絡(luò)節(jié)點部署復(fù)雜且密集的這一特性提出來的[3]。該算法是基于單元格分簇的拓?fù)渌惴?，不足之處在于它的簇首選擇機(jī)制和節(jié)點能耗不均。在本文中，采用了支持向量回歸機(jī)（Support Vector Regression，SVR）虛擬單元格的劃分進(jìn)行優(yōu)化，并借助MATLAB工具對改進(jìn)之后的算法進(jìn)行了性能分析與實驗仿真。

2 支持向量回歸機(jī)

支持向量機(jī)（Support Vector Machine，SVM）主要用于研究分類和回歸這兩大問題，1995年Vapnik提出的一種新的通用學(xué)習(xí)方法[4]。在許多領(lǐng)域都得到了長足的發(fā)展， 例如非線性系統(tǒng)控制、人臉檢測技術(shù)、計算機(jī)入侵檢測、基因分類、函數(shù)回歸估計、數(shù)據(jù)挖掘等等。本文主要采用SVM中的回歸估計方法（即SVR），無線傳感器網(wǎng)絡(luò)中節(jié)點的分布滿足某一函數(shù)，針對這一函數(shù)應(yīng)用SVR尋找其屬于支持向量（Support Vector，SV）的點，以該點作為圓心進(jìn)行區(qū)域劃分。

SVM方法首先是從解決分類問題發(fā)展起來的，把該方法推廣到回歸領(lǐng)域時，則提出了SVR。SVR仍然保持著分類問題中的稀疏性，即可以用少量SV來表示決策函數(shù)[5]。

3 GAF算法

3.1 傳統(tǒng)的GAF算法

GAF算法[6]基于節(jié)點的位置信息，監(jiān)測區(qū)域劃分成方形的虛擬單元格，根據(jù)算法本身的簇首選擇機(jī)制進(jìn)行分簇。該算法主要有兩個階段的執(zhí)行過程。

第一階段，為保證相鄰單元格中任意兩個節(jié)點可以直接通信，根據(jù)傳感器節(jié)點的位置信息和通信半徑來劃分虛擬單元格。在已知位置和通信半徑的情況下，可以計算出該節(jié)點所在的單元格。

所有節(jié)點的初始狀態(tài)的都是發(fā)現(xiàn)狀態(tài)，每一個節(jié)點發(fā)送自己的位置信息來獲得本單元格內(nèi)其他節(jié)點的信息。每個節(jié)點設(shè)置一個定時器，一旦定時器超過T1，節(jié)點進(jìn)入活動狀態(tài)，同時發(fā)送消息聲明成為簇頭節(jié)點；若超時前收到本單元格內(nèi)其他節(jié)點成為簇頭的消息，則進(jìn)入睡眠狀態(tài)，說明該節(jié)點簇頭競爭失敗。當(dāng)簇頭節(jié)點處于活動狀態(tài)，定時器時間設(shè)置為T2（即活動狀態(tài)的時間）。一旦定時器超過T2，簇頭節(jié)點就重新進(jìn)入發(fā)現(xiàn)狀態(tài)；在超過T2之前，簇頭節(jié)點周期性地發(fā)送廣播包，從而抑制其他發(fā)現(xiàn)狀態(tài)的節(jié)點進(jìn)入活躍狀態(tài)。當(dāng)節(jié)點進(jìn)入睡眠狀態(tài)，設(shè)置定時器時間為T3，在定時器超過T3之后進(jìn)入發(fā)現(xiàn)狀態(tài)。

3.2 改進(jìn)的GAF算法

在GAF算法中，考慮WSN連通度的問題，對監(jiān)測區(qū)域進(jìn)行單元格劃分，算法要使得相鄰單元格內(nèi)任意兩個節(jié)點可以直接通信。因此單元格邊長需要滿足[r≤R5]。文獻(xiàn)[7]提出另一種相鄰區(qū)域的關(guān)系如圖6，為保證每個單元格節(jié)點與周圍相鄰區(qū)域能直接通信。

3.3 基于SVR的GAF算法改進(jìn)

GAF算法是WSN中較早采用讓部分節(jié)點進(jìn)入睡眠狀態(tài)以節(jié)省能耗的分簇算法。它的優(yōu)點在于采用了節(jié)點狀態(tài)轉(zhuǎn)換機(jī)制和按虛擬單元格劃分簇。不過GAF算法也有它的不足之處，忽略了提供損失的節(jié)點，而且在實際應(yīng)用中節(jié)點容易移動，可能從一個單元格移動到另一個單元格，這些移動的節(jié)點很可能是某個單元格內(nèi)的簇頭節(jié)點，這會導(dǎo)致有些單元格內(nèi)沒有簇首節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)消息，從而導(dǎo)致網(wǎng)絡(luò)中大量的丟包和重復(fù)發(fā)包，增加網(wǎng)絡(luò)中不必要的能量消耗。為此，引入SVM技術(shù)中的SVR，對GAF算法進(jìn)行預(yù)處理，當(dāng)節(jié)點在ε-帶范圍之外則舍棄，減少能量消耗。SVR產(chǎn)生的支持向量作為虛擬單元格的圓心畫圓形區(qū)域，當(dāng)劃分的圓形區(qū)域相交是就產(chǎn)生了重疊區(qū)域。重疊區(qū)域內(nèi)的節(jié)點將屬于兩個或兩個以上的單元格，這樣勢必會引起節(jié)點分區(qū)的矛盾和節(jié)點的能量消耗。為了避免這樣的能量消耗和矛盾，將這些節(jié)點作為兩個單元格中的中轉(zhuǎn)節(jié)點。

算法流程如下：

（1）初始化：確定傳感器節(jié)點個數(shù)n，隨機(jī)產(chǎn)生每個節(jié)點的位置和初始能量；

（2）通過SVR，選取出屬于支持向量的傳感器節(jié)點；

（3）以支持向量節(jié)點為圓心，半徑為r畫圓形區(qū)域，每一個區(qū)域為一個整體；

（4）每個區(qū)域利用圖5中節(jié)點狀態(tài)轉(zhuǎn)換選取簇首，非簇首節(jié)點加入相應(yīng)的簇；

（5）節(jié)點成為簇首后，給單元格內(nèi)其他節(jié)點發(fā)布聲明消息，并進(jìn)入活動狀態(tài)；

（6）若T2超時，則返回（4）繼續(xù)，直至節(jié)點全部死亡；

（7）網(wǎng)絡(luò)穩(wěn)定運行。

4 實驗與分析

4.1 實驗環(huán)境

在[x∈[-10，10]]，且[y]滿足式（1-4）的監(jiān)測區(qū)域中，隨機(jī)分布100個傳感器節(jié)點和一個基站節(jié)點（0，0）（基站位置不變）。高能量節(jié)點超出一般節(jié)點能量的百分比a為1，則監(jiān)測區(qū)域內(nèi)節(jié)點初始能量為[E0]的[（1+rand?a）]倍，其中[E0]為0.5J。傳感器節(jié)點采集的數(shù)據(jù)的長度為4000bit，周期為5000輪。SVR模型中優(yōu)先考慮線性回歸函數(shù)，其中核參數(shù)k為0.05，懲罰參數(shù)C為100.0，精度參數(shù)ε為1。實驗采用MATLAB7.0進(jìn)行，將基于SVR的GAF算法（r不變）、基于SVR的GAF算法（r改變）與原始的GAF算法進(jìn)行對比，主要對比死亡節(jié)點數(shù)和能量消耗這兩方面。

4.2 實驗結(jié)果

從圖8和圖9可以更明確地看出算法在相應(yīng)輪數(shù)的死亡節(jié)點數(shù)。GAF算法在第2486輪附近出現(xiàn)第一個死亡節(jié)點，在第4842輪附近節(jié)點全部死亡；基于SVR的GAF改進(jìn)（r不變）算法第一個死亡節(jié)點出現(xiàn)在第2525附近，節(jié)點全部死亡在第4900輪附近；基于SVR的GAF改進(jìn)算法第一個死亡節(jié)點出現(xiàn)在第2490輪附近，最后一個死亡節(jié)點出現(xiàn)在第4955輪附近?；赟VR的GAF改進(jìn)比傳統(tǒng)的GAF算法以及基于SVR的GAF改進(jìn)（r不變）算法的網(wǎng)絡(luò)生命周期長，更能避免節(jié)點過早死亡。

5 結(jié)束語

本文在無線傳感器網(wǎng)絡(luò)中的GAF算法上引入SVR技術(shù)，對算法進(jìn)行預(yù)處理，利用ε-帶去除無效節(jié)點。以支持向量為圓心畫圓形區(qū)域來劃分單元格，通過改變半徑來保持連通性。通過反復(fù)的實驗驗證，可以看出該算法能有效減少節(jié)點能耗，改善能量有限問題。這只是對GAF算法一方面的改進(jìn)，該算法在實際應(yīng)用中還有更多問題需要解決，比如節(jié)點分布范圍很廣的時候，如何減少外界因素對通信的干擾等，還有待進(jìn)一步研究。

參考文獻(xiàn)：

[1]陳林星. 無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M]. 北京：電子工業(yè)出版社，2009：4-5.

[2]Xu Y，Heidemann J，Estrin D. Geography-informed energy conservation for ad hoc routing[C]. 7th Annual Int.l Conf on Mobile Computing and Networking. Rome，Italy： ACM Press， 2001：70-84.

[3]景博，張劼，孫勇. 智能網(wǎng)絡(luò)傳感器與無線傳感器網(wǎng)絡(luò)[M]. 北京：國防工業(yè)出版社，2011：109-110.

[4]鄧乃揚，田英杰.數(shù)據(jù)挖掘中的新方法——支持向量機(jī)[M].北京：科學(xué)出版社，2004.

[5]朱紅紅，朱正禮，盧欣，侯迎坤.基于SVM的LEACH分簇算法優(yōu)化[J]. 常州大學(xué)學(xué)報（自然科學(xué)版），2014：18-23.

[6]孫利民，李建中，等.無線傳感器網(wǎng)絡(luò)[M]. 北京：清華大學(xué)出版社，2005：97-98.

[7]梁青，李卓冉，韓昊澎，熊偉. 基于最優(yōu)簇首數(shù)劃分單元格的改進(jìn)GAF算法[J]. 計算機(jī)應(yīng)用研究，2014，30（12）：3622-3624.