基于支持向量機(jī)的WSN能量感知路由算法

王杰 張偉 馬玉潔

摘要：機(jī)器學(xué)習(xí)（ML）技術(shù)在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（WSNs）的路由協(xié)議中應(yīng)用極大地幫助傳感器節(jié)點(diǎn)解決了其能量消耗問(wèn)題。 眾多專(zhuān)家學(xué)者已經(jīng)提出許多相關(guān)的解決方案，該類(lèi)算法有效的優(yōu)化了資源利用率，達(dá)到了延長(zhǎng)網(wǎng)絡(luò)壽命的效果。該文提出了一種基于支持向量的高效分簇協(xié)議，該算法能夠有效地將傳感器節(jié)點(diǎn)分配到最近的Sink節(jié)點(diǎn)，同時(shí)平衡簇頭之間的能量消耗。 該協(xié)議與低功耗自適應(yīng)集簇分層型協(xié)議（LEACH）在NS-2仿真軟件上進(jìn)行仿真和測(cè)試。實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中表現(xiàn)出更好的資源利用率。

關(guān)鍵詞：WSN；路由協(xié)議；分簇；LEACH

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）09-0046-03

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)通常部署在復(fù)雜環(huán)境中，用于監(jiān)測(cè)關(guān)鍵信息；如地震，溫度和洪水情況。因此在傳感器工作的條件下為其補(bǔ)充能量實(shí)現(xiàn)難度較大；意味著優(yōu)秀的路由協(xié)議能夠有效地利用電池資源，有助于延長(zhǎng)WSN的使用壽命。機(jī)器學(xué)習(xí)（ML）算法能夠融合WSN的資源管理，比傳統(tǒng)的路由算法更為有效。先前眾多專(zhuān)家學(xué)者在WSN的路由協(xié)議中引入了幾種ML算法來(lái)在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中規(guī)劃路由； 該方法能夠盡量降低不規(guī)則路線(xiàn)造成的節(jié)點(diǎn)能量消耗。

為了延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間，WSN被劃分成具有一個(gè)簇頭和多個(gè)傳感器節(jié)點(diǎn)的簇域。每個(gè)簇域都會(huì)通過(guò)某種算法產(chǎn)生一個(gè)簇頭（Sink節(jié)點(diǎn)），負(fù)責(zé)收集和處理簇內(nèi)傳感器節(jié)點(diǎn)的原始數(shù)據(jù)，并將處理后的數(shù)據(jù)發(fā)送給基站（BS）。該路由方式能夠降低各個(gè)傳感器節(jié)點(diǎn)的能耗。該類(lèi)型的聚類(lèi)算法被稱(chēng)為分層路由協(xié)議（Hierarchical Routing Protocols）。 本文引入了一個(gè)使用支持向量機(jī)（SVM）的分層路由協(xié)議。并通過(guò)實(shí)驗(yàn)仿真與低功耗自適應(yīng)集簇分層型協(xié)議（LEACH）相比較。

1 相關(guān)工作

Asa Ben-Hur等人提出一種基于支持向量的向量聚類(lèi)算法[1]Support Vector Clustering，SVC），該算法能夠有效保證網(wǎng)絡(luò)中的每個(gè)簇域都擁有平滑的簇邊界。創(chuàng)新性在于：該算法所產(chǎn)生的簇域不同于其他聚類(lèi)算法所生成幾何形狀的簇域。并且支持優(yōu)化聚類(lèi)方案。文獻(xiàn)[2]中，作者提出了使用支持向量機(jī)的聚類(lèi)算法； 并通過(guò)執(zhí)行名詞短語(yǔ)和新聞文章聚類(lèi)對(duì)算法進(jìn)行測(cè)試，并證明該聚類(lèi)是NP-hard問(wèn)題，并評(píng)估了學(xué)習(xí)時(shí)使用的近似方法。實(shí)驗(yàn)證明SVM聚類(lèi)可以提供最優(yōu)的聚類(lèi)解決方案。

支持向量基于學(xué)習(xí)算法，一般用于求解分類(lèi)和回歸問(wèn)題。該技術(shù)由科特斯和瓦普尼克[3]于1995年首先提出。自提出之日起，它一直是解決許多問(wèn)題的學(xué)習(xí)技術(shù)之一。雖然支持向量機(jī)被廣泛用于分類(lèi)和回歸，但是眾多文獻(xiàn)表明它有助于解決聚類(lèi)問(wèn)題。

支持向量機(jī)通過(guò)在平面上繪制一條直線(xiàn)來(lái)分離兩組或多組數(shù)據(jù)點(diǎn)，從而可以求得最佳的分離線(xiàn)（分離線(xiàn)與任何一組的數(shù)據(jù)點(diǎn)都不會(huì)太接近，為了避免造成噪聲，影響泛化；最佳線(xiàn)要盡可能遠(yuǎn)離數(shù)據(jù)點(diǎn)）。通過(guò)以下示例可以更好地理解SVM；假設(shè)我們?cè)诔矫嫔嫌袃山M數(shù)據(jù)，如圖1所示。

從上圖可以看出，平面內(nèi)可以畫(huà)出多條線(xiàn)將兩組數(shù)據(jù)點(diǎn)分開(kāi)。支持向量機(jī)的主要目標(biāo)就是繪制一條線(xiàn)，進(jìn)而可以最優(yōu)地分離兩個(gè)組。由此我們可以得出結(jié)論：SVM訓(xùn)練系統(tǒng)對(duì)數(shù)據(jù)集進(jìn)行分類(lèi)，使得所有組或類(lèi)之間的最小距離更大。該算法通過(guò)迭代直到達(dá)到期望的最優(yōu)線(xiàn)[3]；圖2則描繪了最佳線(xiàn)的選取。

1.1 SVM的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：①與K-Means算法不同，SVM更利于處理高維度的平面；②在提供的數(shù)據(jù)樣本數(shù)量少于維度數(shù)量的情況下，這是相當(dāng)不錯(cuò)的；③支持向量機(jī)被證明是有效的。

缺點(diǎn)：在為分類(lèi)提供的特征數(shù)量超過(guò)提供的數(shù)據(jù)樣本數(shù)量的情況下，SVM的性能下降。

2 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由協(xié)議

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的主要工作是信息監(jiān)測(cè)和評(píng)估。并將有效信息傳輸至基站。如果網(wǎng)絡(luò)內(nèi)的每個(gè)傳感器節(jié)點(diǎn)都將感知到的信息直接發(fā)送至基站（BS），則網(wǎng)絡(luò)生存時(shí)間較短。因此，多跳傳輸?shù)乃枷氡徽J(rèn)為是能夠最大限度地提高遠(yuǎn)離BS傳感器節(jié)點(diǎn)的壽命[4]。 關(guān)于解決WSN能耗問(wèn)題的各類(lèi)算法中，路由算法設(shè)計(jì)是其重要組成部分；該算法負(fù)責(zé)構(gòu)建和維護(hù)節(jié)點(diǎn)之間的路由路徑，優(yōu)良的路由協(xié)議設(shè)計(jì)能夠使 WSN最大限度地減少資源利用率。

2.1 分簇協(xié)議

因?yàn)樗哂辛己玫墓?jié)能行為。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的分簇類(lèi)路由協(xié)議在過(guò)去數(shù)十年的研究中取得了較大進(jìn)展，在分層協(xié)議中，傳感器節(jié)點(diǎn)被分成許多簇，每個(gè)簇選舉一個(gè)簇首。傳感器節(jié)點(diǎn)負(fù)責(zé)檢測(cè)數(shù)據(jù)并將其發(fā)送到各自的簇頭。簇首接收數(shù)據(jù)，匯總并發(fā)送給基站。 一般來(lái)說(shuō)，簇頭比網(wǎng)絡(luò)中的普通傳感器節(jié)點(diǎn)具有更大的權(quán)限。因此，網(wǎng)絡(luò)的總體能量可以保持較高水平。下面列出了一些著名的分層路由協(xié)議：

①低功耗自適應(yīng)集簇分層型協(xié)議（LEACH）

②傳感器信息系統(tǒng)中的低效收（PEGASIS）

③固定簇半徑的分簇協(xié)議（HEED）

④閾值敏感節(jié)能傳感器網(wǎng)絡(luò)協(xié)議（TEEN）

⑤自適應(yīng)周期性閾值敏感節(jié)能傳感器網(wǎng)絡(luò)協(xié)議（APTEEN）

2.2 本文所提算法

本文所提基于支持向量的路由算法步驟說(shuō)明如下：

Step1：Begin

Step2：將每個(gè)傳感器節(jié)點(diǎn)分配到最近的簇頭；

Step3：Set i = 0；

Step4：計(jì)算傳感器節(jié)點(diǎn)到其各自簇頭的平均距離；

Step5：如果（實(shí)際距離）/（最小距離）<1（閥值），則轉(zhuǎn)到Step8，否則繼續(xù)Step6；

Step6：將簇頭移動(dòng)至平均距離坐標(biāo)位置；

Step7：Set i = i + 1；

Step8：如果i ≠ 5，跳轉(zhuǎn)至Step4；

Step9：End

3 實(shí)驗(yàn)仿真

為了測(cè)試性能指標(biāo)，本文所提議協(xié)議在網(wǎng)絡(luò)模擬器2（NS-2）中執(zhí)行。我們將算法放在三種不同場(chǎng)景中進(jìn)行模擬仿真，分別是小型，中型和大型無(wú)線(xiàn)傳感器網(wǎng)絡(luò)， 小規(guī)模網(wǎng)絡(luò)包含5個(gè)簇域，每個(gè)簇域內(nèi)含5個(gè)傳感器節(jié)點(diǎn)，中等規(guī)模網(wǎng)絡(luò)包含7個(gè)簇域，每個(gè)簇域包含7個(gè)傳感器節(jié)點(diǎn)，大規(guī)模網(wǎng)絡(luò)包含10個(gè)簇域，每個(gè)簇域包含10個(gè)傳感器節(jié)點(diǎn)。 圖3，圖4和圖5分別描述了所有三種情景下NS-2仿真的節(jié)點(diǎn)布局。表1示出了分別用于監(jiān)督和無(wú)監(jiān)督學(xué)習(xí)算法的模擬參數(shù)。

4 結(jié)論

通過(guò)分析能量消耗（圖6）和分組延遲比PDR（圖7）來(lái)比較分析兩種算法，仿真結(jié)果表明，在所有的部署場(chǎng)景中SVM的網(wǎng)絡(luò)生存時(shí)間都優(yōu)于LEACH算法，并且，數(shù)據(jù)包延時(shí)時(shí)間更低。

從上面的分析可以得出結(jié)論：基于SVM的路由協(xié)議能夠有效的延長(zhǎng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的生存時(shí)間。并且數(shù)據(jù)報(bào)的通信延時(shí)相較其他同類(lèi)協(xié)議更低，該算法是一種有監(jiān)督的聚類(lèi)算法，與LEACH相比，它提供了一種有效的聚類(lèi)技術(shù)，可以幫助提高無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的資源利用率。

參考文獻(xiàn)：

[1] Ben-Hur A， Horn D， Siegelmann H T， et al. Support vector clustering[J]. Journal of Machine Learning Research， 2002， 2（2）：125-137.

[2] Finley T， Joachims T. Supervised clustering with support

vector machines[C]// ICML. 2005：217-224.

[3] N Cristianini， Shawe-taylor. J An. Introduction to Support Vector Machines[J]. 2000， 32（8）：1-28.

[4] Villalba L J， Orozco A L， Cabrera A T， et al. Routing protocols in wireless sensor networks[J]. Sensors， 2009， 9（11）：8399-421.

[5] Pantazis N A， Nikolidakis S A， Vergados D D. Energy-Efficient Routing Protocols in Wireless Sensor Networks： A Survey[J]. IEEE Communications Surveys & Tutorials， 2013， 15（2）：551-591.

[6] 杜海韜， 李強(qiáng)， 丁廣太，等. WSN中基于鏈路質(zhì)量和節(jié)點(diǎn)能量的AODV路由算法研究[J]. 傳感技術(shù)學(xué)報(bào)， 2016， 29（7）：1042-1048.

[7] 孫彥清， 彭艦， 劉唐，等. 基于動(dòng)態(tài)分區(qū)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)非均勻成簇路由協(xié)議[J]. 通信學(xué)報(bào)， 2014（1）：198-206.

[8] Jiang Y， Shi W， Wang X， et al. A distributed routing for wireless sensor networks with mobile sink based on the greedy embedding[J]. Ad Hoc Networks， 2014， 20（2）：150-162.