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

劉奇奇，張曦煌

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

0 引言

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

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

1 螢火蟲算法

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

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

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

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

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

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

2.1 螢火蟲的選取

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

假設在M×M的區(qū)域內存在N個傳感器節(jié)點，對于每個傳感器節(jié)點 C(i)，其對應的屬性為(xi，yi，Ei)，其中 xi為節(jié)點X軸坐標，yi為Y軸坐標，Ei為節(jié)點當前剩余能量。

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

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

2.2 基于螢火蟲算法的分簇

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

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

而對于G個螢火蟲樣本，可以有以下定義:

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

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

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

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

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

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

螢火蟲的吸引度決定了移動的距離，其計算公式為

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

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

其中，β為步長因子，x為坐標。

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

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

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

3)對于每一個螢火蟲，計算其他螢火蟲的相對亮度，選擇亮度大于自身的螢火蟲，作為其移動的方向。

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

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

6)輸出簇頭結果。

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

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

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

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

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

3 仿真與結果分析

3.1 仿真環(huán)境

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

3.2 仿真結果

實驗中隨機生成200個網(wǎng)絡節(jié)點。

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

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

第一個節(jié)點死亡、第50個死亡、第100個節(jié)點死亡、所有節(jié)點死亡時間如表1所示。

表1 節(jié)點死亡時間Tab 1 Death time of nodes

圖2為經(jīng)典LEACH算法和本文算法的比較，通過仿真實驗可以看出:本文算法第一個節(jié)點死亡時間相對推遲，這是因為本文算法的分簇相對于LEACH來說更加的合理:LEACH算法的簇頭選舉是隨機的，導致分簇可能不是最優(yōu)，而本文通過螢火蟲算法尋求最優(yōu)解，使分簇更加合理。

4 結束語

圖2 算法比較Fig 2 Comparison of algorithms

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

［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)絡技術與應用［M］.北京:電子工業(yè)出版社，2007.

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

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

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

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

［7］劉長平，葉春明.一種新穎的仿生群智能優(yōu)化算法:螢火蟲算法［J］.計算機應用研究，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.