基于螢火蟲算法的無線傳感器網(wǎng)絡(luò)的分簇路由協(xié)議

劉奇奇，張曦煌

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫214000)

0 引言

無線傳感器網(wǎng)絡(luò)(WSNs)是由在空間上相互離散的各類傳感器相互協(xié)作構(gòu)成的傳感器網(wǎng)絡(luò)系統(tǒng)，使得分布于不同場(chǎng)所的數(shù)量龐大的傳感器之間能夠?qū)崿F(xiàn)更加有效、可靠的通信。由于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的電量有限，且由于條件限制難以補(bǔ)充或更改，故延長(zhǎng)無線傳感器網(wǎng)絡(luò)的存活時(shí)間是目前無線傳感器網(wǎng)絡(luò)研究的主要問題。鑒于無線傳感器網(wǎng)絡(luò)的特殊性，為無線傳感器網(wǎng)絡(luò)設(shè)計(jì)特有的路由協(xié)議具有非常重要的意義。目前研究人員已經(jīng)提出多種路由協(xié)議，其中比較經(jīng)典的路由協(xié)議比如 LEACH［1～4］協(xié)議、PEGASIS協(xié)議等，這些協(xié)議都是基于層次思想，通過分簇等手段減少能量損耗，延長(zhǎng)網(wǎng)絡(luò)存活時(shí)間。

但是由于經(jīng)典LEACH算法簇頭選舉是隨機(jī)的，可能導(dǎo)致最后的分簇的不合理性，使網(wǎng)絡(luò)可能過早死亡，故合理的分簇機(jī)制是十分必要的。本文提出了一種基于螢火蟲算法的分簇機(jī)制，通過螢火蟲算法尋求最優(yōu)解，對(duì)網(wǎng)絡(luò)分簇進(jìn)行優(yōu)化，使網(wǎng)絡(luò)節(jié)點(diǎn)能耗均衡，延長(zhǎng)網(wǎng)絡(luò)壽命。

1 螢火蟲算法

螢火蟲算法［5～7］(firely algorithm，F(xiàn)A)是一種啟發(fā)式算法，靈感來自于螢火蟲的閃光行為。螢火蟲的閃光，其主要目的是作為一個(gè)信號(hào)系統(tǒng)，以吸引其他的螢火蟲。螢火蟲算法是通過模擬螢火蟲的群體行為構(gòu)造出的一類隨機(jī)優(yōu)化算法。其仿生原理是用搜索空間中的點(diǎn)模擬自然界中的螢火蟲個(gè)體，將搜索和優(yōu)化過程模擬成螢火蟲個(gè)體的吸引和移動(dòng)過程，將求解問題的目標(biāo)函數(shù)度量成個(gè)體所處位置的優(yōu)劣，將個(gè)體的優(yōu)勝劣汰過程類比為搜索和優(yōu)化過程中用好的可行解取代較差可行解的迭代過程。其假設(shè)為:

1)螢火蟲不分性別，它將會(huì)被吸引到所有比它更亮的螢火蟲那去;

2)螢火蟲的吸引力和亮度呈正比，對(duì)于任何兩只螢火蟲，其中一只會(huì)向著比它更亮的另一只移動(dòng)，然而，亮度是隨著距離的增加而減少的。

在該算法中，螢火蟲彼此吸引的原因取決于兩個(gè)要素，即自身亮度和吸引度。其中，螢火蟲發(fā)出熒光的亮度取決于自身所在位置的目標(biāo)值，亮度越高表示所處的位置越好，即目標(biāo)值越佳。吸引度與亮度相關(guān)，越亮的螢火蟲擁有越高的吸引力，可以吸引視線范圍內(nèi)亮度比其弱的螢火蟲往自身方向移動(dòng)。如果發(fā)光亮度相同，則螢火蟲各自隨機(jī)移動(dòng)。亮度和吸引度與螢火蟲之間的距離呈反比，都隨著距離的增加而減小，這相當(dāng)于模擬了熒光在空間傳播時(shí)被傳播媒介吸收而逐漸衰減的特性。

2 基于螢火蟲算法的分簇路由協(xié)議

由于開始螢火蟲都是隨機(jī)選擇，可能會(huì)導(dǎo)致算法搜索太慢，故對(duì)于螢火蟲的選取的優(yōu)化是必要的。

2.1 螢火蟲的選取

自組織神經(jīng)網(wǎng)絡(luò)映射(SOM)是一種非監(jiān)督的神經(jīng)網(wǎng)絡(luò)，可以對(duì)樣本數(shù)據(jù)進(jìn)行初步的分類和聚類，故本文采用SOM對(duì)所有傳感器節(jié)點(diǎn)進(jìn)行初步的聚類，進(jìn)而對(duì)螢火蟲的選取進(jìn)行優(yōu)化。

假設(shè)在M×M的區(qū)域內(nèi)存在N個(gè)傳感器節(jié)點(diǎn)，對(duì)于每個(gè)傳感器節(jié)點(diǎn) C(i)，其對(duì)應(yīng)的屬性為(xi，yi，Ei)，其中 xi為節(jié)點(diǎn)X軸坐標(biāo)，yi為Y軸坐標(biāo)，Ei為節(jié)點(diǎn)當(dāng)前剩余能量。

對(duì)于每一個(gè)節(jié)點(diǎn)，通過對(duì)節(jié)點(diǎn)屬性歸一化處理，作為輸入樣本。本文中采用線性歸一轉(zhuǎn)換，即

歸一轉(zhuǎn)換后每個(gè)傳感器節(jié)點(diǎn)C(i)對(duì)應(yīng)于輸入樣本T(i)，通過自組織神經(jīng)網(wǎng)絡(luò)完成初步聚類，獲得輸出集合S={s1，s2，…，sn}，n 為初步聚類中心數(shù)目。

2.2 基于螢火蟲算法的分簇

根據(jù)文獻(xiàn)可知，最優(yōu)簇頭數(shù)為

對(duì)于由SOM獲得的輸出集合S和最優(yōu)簇頭數(shù)K，選取G個(gè)螢火蟲樣本，其中

而對(duì)于G個(gè)螢火蟲樣本，可以有以下定義:

定義1 假設(shè)第i個(gè)螢火蟲定義為F(i)={CH1i，CH2i，…，CHKopti}。

定義2 網(wǎng)絡(luò)簇集合為CCHi，即簇頭CH所在簇集合。

在傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)之間的距離都是影響分簇的重要因素，故給出螢火蟲熒光素函數(shù)YS(F(i))

在螢火蟲算法中，亮度體現(xiàn)了螢火蟲所處位置的優(yōu)劣并決定其移動(dòng)方向，吸引度決定了螢火蟲移動(dòng)的距離，通過亮度和吸引度不斷更新，從而使目標(biāo)值不斷優(yōu)化。

對(duì)于螢火蟲，其亮度會(huì)隨著距離的增加而漸漸減弱，螢火蟲亮度計(jì)算公式為

其中，YS(F(i))為計(jì)算的熒光素，r為距離影響因子，d為兩只螢火蟲的距離，d=‖F(xiàn)(i)-F(j)‖。

螢火蟲的吸引度決定了移動(dòng)的距離，其計(jì)算公式為

其中，H0為最大吸引度，設(shè)為1.0，r和d同上。

通過螢火蟲亮度和吸引度，可以獲得螢火蟲的移動(dòng)更新公式為

其中，β為步長(zhǎng)因子，x為坐標(biāo)。

綜上所述，基于螢火蟲算法的分簇算法流程如下:

1)對(duì)所有傳感器節(jié)點(diǎn)，通過自組織神經(jīng)網(wǎng)絡(luò)將節(jié)點(diǎn)初步聚類，從而獲得螢火蟲樣本集合。

2)根據(jù)最優(yōu)簇頭數(shù)和螢火蟲樣本集合，生成每一個(gè)螢火蟲。

3)對(duì)于每一個(gè)螢火蟲，計(jì)算其他螢火蟲的相對(duì)亮度，選擇亮度大于自身的螢火蟲，作為其移動(dòng)的方向。

4)根據(jù)步驟(3)選擇螢火蟲的吸引度，計(jì)算螢火蟲的更新距離，更新螢火蟲的位置。

5)對(duì)于更新后的螢火蟲，若滿足搜索精度或達(dá)到搜索次數(shù)，則終止搜索;否則，繼續(xù)執(zhí)行步驟(3)。

6)輸出簇頭結(jié)果。

2.3 數(shù)據(jù)傳輸階段

在傳統(tǒng)的Leach協(xié)議中簇頭融合數(shù)據(jù)后一般通過單跳和基站通信，把獲取的數(shù)據(jù)傳輸給基站，這樣導(dǎo)致如果簇頭距離基站很遠(yuǎn)，傳輸消耗能量將非常大，故采用改進(jìn)的簇頭多跳路由協(xié)議［8］是必要的。

路由簇頭:根據(jù)公式(8)選擇距離最近的Route(num)個(gè)簇頭充當(dāng)路由簇頭，路由簇頭將負(fù)責(zé)傳輸其他簇頭傳輸過來的數(shù)據(jù)

對(duì)其他簇頭，則向全局廣播信息，廣播半徑從d0開始依次增加，若在此范圍內(nèi)有其他簇頭CH(i)回應(yīng)廣播簇頭，且d(CH_BS)＞d其他(CH_BS)，則將簇頭CH(i)加入此簇頭的鄰居節(jié)點(diǎn)中，并終止廣播;否則，增大廣播半徑，直到有簇頭回應(yīng)，從而獲得每個(gè)簇頭的鄰居簇頭表。

對(duì)于每個(gè)簇頭，若其鄰居簇頭表中含有路由簇頭，則將數(shù)據(jù)直接發(fā)送給路由簇頭;若沒有鄰居簇頭，則將數(shù)據(jù)發(fā)送給鄰居簇頭，并循環(huán)路由。

3 仿真與結(jié)果分析

3.1 仿真環(huán)境

在邊長(zhǎng)為200 m×200 m的正方形區(qū)域內(nèi)，隨機(jī)分布200個(gè)傳感器節(jié)點(diǎn)，所有傳感器節(jié)點(diǎn)能量有限，位置固定不變。仿真采用Matlab 2010b模擬，仿真具體環(huán)境為:基站坐標(biāo)為(100，250)m;初始能量為0.5 J;發(fā)送與接收消耗能量為50 nJ·bit-1;數(shù)據(jù)包為400 bit;數(shù)據(jù)融合消耗能量為5 nJ·bit-1;光吸引強(qiáng)度系數(shù)為1.0;步長(zhǎng)因子為2。

3.2 仿真結(jié)果

實(shí)驗(yàn)中隨機(jī)生成200個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。

網(wǎng)絡(luò)節(jié)點(diǎn)初始分布如圖1。

圖1 節(jié)點(diǎn)初始分布Fig 1 Initial distribution of node

第一個(gè)節(jié)點(diǎn)死亡、第50個(gè)死亡、第100個(gè)節(jié)點(diǎn)死亡、所有節(jié)點(diǎn)死亡時(shí)間如表1所示。

表1 節(jié)點(diǎn)死亡時(shí)間Tab 1 Death time of nodes

圖2為經(jīng)典LEACH算法和本文算法的比較，通過仿真實(shí)驗(yàn)可以看出:本文算法第一個(gè)節(jié)點(diǎn)死亡時(shí)間相對(duì)推遲，這是因?yàn)楸疚乃惴ǖ姆执叵鄬?duì)于LEACH來說更加的合理:LEACH算法的簇頭選舉是隨機(jī)的，導(dǎo)致分簇可能不是最優(yōu)，而本文通過螢火蟲算法尋求最優(yōu)解，使分簇更加合理。

4 結(jié)束語

圖2 算法比較Fig 2 Comparison of algorithms

本文采用螢火蟲算法，通過迭代獲得最優(yōu)解，以進(jìn)行合適的分簇，同時(shí)由于螢火蟲樣本初始是隨機(jī)的，會(huì)造成最優(yōu)解搜索過慢，故一開始通過自組織映射神經(jīng)網(wǎng)絡(luò)對(duì)樣本數(shù)據(jù)進(jìn)行初步的處理，在數(shù)據(jù)傳輸階段則通過采用多跳路由，仿真表明:本文算法在一定程度上改善了網(wǎng)絡(luò)存活時(shí)間。

［1］Heinzelman W，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［2］宋 文.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用［M］.北京:電子工業(yè)出版社，2007.

［3］孫利民，李建中，陳 渝.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

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

［5］吳昌友，王福林，馬 力.一種新的改進(jìn)粒子群優(yōu)化算法［J］.控制工程，2010，17(3):359-362.

［6］牛小嬌，呂程林.一種基于LEACH協(xié)議的分簇路由算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21(7):13-16.

［7］劉長(zhǎng)平，葉春明.一種新穎的仿生群智能優(yōu)化算法:螢火蟲算法［J］.計(jì)算機(jī)應(yīng)用研究，2009，28(9):3295-3297.

［8］Hooman Ghaffarzadeh.Two-phase data traffic optimization of wireless sensor networks for prolonging network lifetime［J］.Wireless Network，2014，20:671-679.