正六邊形分區(qū)的混合差分進(jìn)化螢火蟲路由算法

劉宏，何鴻燊

（江西理工大學(xué) 電氣工程與自動(dòng)化學(xué)院，江西 贛州341000）

0 引言

無線傳感器網(wǎng)絡(luò)中使用合理的路由協(xié)議能夠顯著地均衡網(wǎng)絡(luò)的能量負(fù)載，提升各個(gè)傳感器節(jié)點(diǎn)的能量利用率，延遲節(jié)點(diǎn)死亡時(shí)刻進(jìn)而使網(wǎng)絡(luò)的整體存活周期得到延長(zhǎng)。目前，群體智能算法在路由協(xié)議中應(yīng)用廣泛并且取得了很好的能耗優(yōu)化效果。S-PSO將一種基于正弦調(diào)整的粒子群算法應(yīng)用于路由協(xié)議中的簇頭選舉部分中，有效降低了能量的消耗速度，在一定程度上緩解和改善了“熱點(diǎn)區(qū)域”的問題，但沒有優(yōu)化簇間傳輸部分；文獻(xiàn)[3]提出一種基于人工蜂群算法的分簇路由協(xié)議，通過考慮剩余能量和節(jié)點(diǎn)位置篩選簇頭節(jié)點(diǎn)，延長(zhǎng)了網(wǎng)絡(luò)壽命，保證了網(wǎng)絡(luò)通信質(zhì)量，但各簇頭采用貪婪策略僅根據(jù)距離輪流選擇離自己最近的簇內(nèi)節(jié)點(diǎn)建立路由，導(dǎo)致簇間數(shù)據(jù)傳輸?shù)哪芎倪^大；NWOA-CT將一種非線性收斂因子的鯨魚算法引入至協(xié)議，調(diào)節(jié)收縮概率，優(yōu)化簇頭選舉步驟；文獻(xiàn)[5]通過果蠅算法對(duì)簇頭規(guī)劃函數(shù)進(jìn)行求解，找出最優(yōu)分簇后在數(shù)據(jù)傳輸過程中應(yīng)用貪婪算法，保證了簇頭分布的合理性；文獻(xiàn)[6]為了平衡粒子群算法的局部搜索能力和全局搜索能力，對(duì)算法的慣性系數(shù)和學(xué)習(xí)因子進(jìn)行改進(jìn)，找到最優(yōu)分簇方案。

基于此設(shè)計(jì)一種正六邊形分區(qū)的混合差分進(jìn)化螢火蟲路由算法（Hybrid Differential Evolutionary Firefly Routing Algorithm Based on Hexagonal Partition，HDEFA-HP）。算法首先對(duì)網(wǎng)絡(luò)劃分虛擬正六邊形網(wǎng)格，在每個(gè)網(wǎng)格中分別遍歷選出剩余能量最大的節(jié)點(diǎn)作備選簇頭；引入混合差分進(jìn)化螢火蟲算法，對(duì)螢火蟲算法引入差分進(jìn)化算法中的變異和交叉操作，改善局部搜索能力、提高收斂速度，在備選簇頭中考慮剩余能量、簇內(nèi)位置和與Sink節(jié)點(diǎn)的距離三個(gè)因素，根據(jù)最優(yōu)簇頭數(shù)篩選最優(yōu)的簇頭集合；然后各節(jié)點(diǎn)利用非連續(xù)性CSMA協(xié)議廣播ADV消息，普通節(jié)點(diǎn)根據(jù)間距和簇頭剩余能量選擇簇頭節(jié)點(diǎn)入簇；在數(shù)據(jù)傳輸部分，簇頭節(jié)點(diǎn)在本簇建立TDMA調(diào)度單跳收集簇內(nèi)數(shù)據(jù)；最后綜合考慮通信距離和剩余能量選擇合理的中繼節(jié)點(diǎn)進(jìn)行簇間多跳傳輸。

1 模型與假設(shè)

對(duì)無線傳感器網(wǎng)絡(luò)做出如下5個(gè)假設(shè)：

1）網(wǎng)絡(luò)中有個(gè)傳感器隨機(jī)散布在邊長(zhǎng)為的正方形監(jiān)測(cè)區(qū)域里。

2）節(jié)點(diǎn)部署之后都是靜止的，不隨時(shí)間的變化而移動(dòng)。

3）節(jié)點(diǎn)的初始能量相同，與此同時(shí)它們都具有唯一地址和ID。

4）節(jié)點(diǎn)都具有通信模塊，可以和基站直接通信。

5）節(jié)點(diǎn)能量耗盡則死亡。

協(xié)議中選用一階無線電能耗模型：多徑衰減模型和自由空間模型對(duì)所消耗的能量進(jìn)行計(jì)算，兩種模型的選取方式依賴于發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間通信距離的大小，當(dāng)通信距離小于閾值時(shí)使用自由空間模型，反之，則使用多徑衰減模型計(jì)算。通信距離為，節(jié)點(diǎn)發(fā)送bit數(shù)據(jù)消費(fèi)的能量具體描述如下：

節(jié)點(diǎn)接收bit數(shù)據(jù)消耗的能量為：

2 正六邊形分區(qū)的混合差分進(jìn)化螢火蟲路由算法

2.1 簇頭選舉

2.1.1 初步網(wǎng)格劃分

圖1 虛擬網(wǎng)格劃分

圖2 節(jié)點(diǎn)坐標(biāo)與網(wǎng)格編碼

確定節(jié)點(diǎn)(,)處網(wǎng)格編碼的偽代碼描述如下：

輸入：正六邊形邊長(zhǎng)；節(jié)點(diǎn)坐標(biāo)(,)

輸出：節(jié)點(diǎn)(,)所在網(wǎng)格編碼(,)

=3*2；=sqrt(3)2；=int()；=int()；=-(*)；=-(*)

if(+)%2==0

if+≤(-)+(-)

節(jié)點(diǎn)所在網(wǎng)格編碼為(,)

else

節(jié)點(diǎn)所在網(wǎng)格編碼為(+1,+1)

end if

else

if(-)+≤(-)+

節(jié)點(diǎn)所在網(wǎng)格編碼為(+1,)

else

節(jié)點(diǎn)所在網(wǎng)格的編碼為(,+1)

end if

end if

在每個(gè)網(wǎng)格內(nèi)，以格內(nèi)節(jié)點(diǎn)平均剩余能量作為能量閾值，將各個(gè)節(jié)點(diǎn)的剩余能量與能量閾值進(jìn)行比較，選出剩余能量最大的節(jié)點(diǎn)標(biāo)記為備選簇頭；然后，在所有備選簇頭集合中使用混合差分進(jìn)化螢火蟲算法進(jìn)一步選擇最優(yōu)節(jié)點(diǎn)擔(dān)任簇頭。

2.1.2 參數(shù)初始化

首先應(yīng)用文獻(xiàn)[11]推導(dǎo)出最優(yōu)簇頭數(shù)目為：

式中：為Sink節(jié)點(diǎn)與最外層正六邊形中心點(diǎn)的距離；為數(shù)據(jù)融合率（DAR），本文取0.5。

在備選簇頭中生成初始種群，對(duì)每個(gè)備選簇頭根據(jù)所屬網(wǎng)格編碼由內(nèi)層向外層順時(shí)針以自然數(shù)重新命名ID，最優(yōu)簇頭數(shù)作為螢火蟲個(gè)體的維數(shù)，螢火蟲個(gè)體定義為ID由小到大的排序。對(duì)應(yīng)關(guān)系如表1所示。

表1 對(duì)應(yīng)關(guān)系

2.1.3 混合差分進(jìn)化螢火蟲算法

螢火蟲算法（Firefly Algorithm，F(xiàn)A）是亮度高的螢火蟲自己進(jìn)行隨機(jī)移動(dòng)，亮度低的螢火蟲則朝著亮度最高的螢火蟲位置進(jìn)行移動(dòng)的一種智能仿生算法，通過模仿螢火蟲之間因個(gè)體的亮度而相互吸引，找出最優(yōu)位置的個(gè)體。

該算法做出如下3個(gè)假設(shè)：

1）假定所有螢火蟲都不分辨雌雄，都可以通過亮度吸引其他螢火蟲；

2）隨著螢火蟲個(gè)體之間距離的增加，個(gè)體亮度和吸引度會(huì)逐漸降低，而亮度低的螢火蟲受到亮度高的個(gè)體的招引而移動(dòng)；

3）螢火蟲的亮度定義為：I=(x)，其中，(x)為設(shè)計(jì)的目標(biāo)函數(shù)。

螢火蟲算法在搜索過程中的重要參數(shù)分別定義為：

螢火蟲個(gè)體對(duì)相對(duì)的亮度表達(dá)式為：

式中：表示個(gè)體在=0處的亮度值；表示光吸系數(shù)。

r表示螢火蟲，的間距，采用歐氏距離計(jì)算，表達(dá)式為：

式中：在維空間中第個(gè)螢火蟲的位置為x=(x,x,…,x)，x表示個(gè)體的第個(gè)分量。

螢火蟲之間的吸引度表達(dá)式為：

式中表示螢火蟲之間最大相互吸引度。

螢火蟲個(gè)體受亮度更大的個(gè)體吸引而進(jìn)行的位置更新公式如下：

差分進(jìn)化算法（Differential Evolution Algorithm，DE）包含四個(gè)步驟：初始化種群、變異、交叉和選擇。

首先初始化種群個(gè)體，表達(dá)式為：

式中：=1,2,…,；rand[0,1]為0～1之間的隨機(jī)數(shù)；和分別為第個(gè)分量的上限和下限。

rand/1：

best/1：

式中：，，分別為1～np之間不等于隨機(jī)選擇的整數(shù)；x為當(dāng)前迭代次數(shù)下最好目標(biāo)函數(shù)值對(duì)應(yīng)的最佳個(gè)體向量；為（0，1]的縮放因子，通過實(shí)驗(yàn)，本文取=0.8。

式中：CR為交叉控制參數(shù)；為[1，]內(nèi)的隨機(jī)整數(shù)。

選擇操作通過比較實(shí)驗(yàn)個(gè)體和目標(biāo)個(gè)體的函數(shù)值，選擇更優(yōu)的個(gè)體作為新的個(gè)體向量：

由于變異算子和交叉算子的存在，將DE與FA混合可以使螢火蟲算法具備擺脫局部最優(yōu)的能力，提高種群多樣性，避免過早收斂，獲得較強(qiáng)的魯棒性。引入變異算子和交叉算子的混合差分進(jìn)化螢火蟲算法（Hybrid Differential Evolutionary Firefly Algorithm，HDEFA）的描述如下：

1）在螢火蟲算法運(yùn)行之后，判斷當(dāng)前種群的平均亮度和最大亮度的差距= |-1|，本文設(shè)定精度=10；

3）當(dāng)＜，此時(shí)搜索空間縮小，由best/1策略的差分進(jìn)化算法改進(jìn)螢火蟲算法，此時(shí)位置更新的第三項(xiàng)可直接忽略，引入變異算子后新的位置更新公式如下：

4）進(jìn)行交叉操作，確保在設(shè)定范圍內(nèi)得到實(shí)驗(yàn)個(gè)體；

5）進(jìn)行選擇操作，保留目標(biāo)函數(shù)值更優(yōu)的個(gè)體。

2.1.4 目標(biāo)函數(shù)

簇頭的選舉應(yīng)每次考慮節(jié)點(diǎn)的剩余能量、簇內(nèi)密度以及與簇間位置三個(gè)重要因素，預(yù)定分簇個(gè)，設(shè)計(jì)目標(biāo)函數(shù)如下：

1）節(jié)點(diǎn)剩余能量因子

式中：(CH)為待選簇頭節(jié)點(diǎn)當(dāng)前剩下的能量；為節(jié)點(diǎn)的初始能量。

2）簇內(nèi)節(jié)點(diǎn)密度因子

式中：為節(jié)點(diǎn)與待選簇頭監(jiān)測(cè)半徑內(nèi)節(jié)點(diǎn)個(gè)數(shù)；|Cluster|為待選簇頭本簇中節(jié)點(diǎn)個(gè)數(shù)。

3）簇間位置因子

式中(CH,Sink)為待選簇頭到Sink節(jié)點(diǎn)之間的距離。

綜上所述，目標(biāo)函數(shù)的設(shè)計(jì)如下：

式中：，，為權(quán)重參數(shù)，滿足++=1，權(quán)重參數(shù)的大小決定3個(gè)評(píng)價(jià)因子對(duì)簇頭選舉的影響程度，根據(jù)實(shí)際應(yīng)用環(huán)境進(jìn)行取值，本文，，分別取值為0.5，0.3，0.2。

由此得出基于混合差分進(jìn)化螢火蟲算法的簇頭選舉流程圖如圖3所示。

圖3 簇頭選舉流程圖

2.2 節(jié)點(diǎn)入簇

簇頭節(jié)點(diǎn)采用非連續(xù)性CSMA協(xié)議廣播ADV信息，ADV信息的內(nèi)容有：簇頭節(jié)點(diǎn)的ID編號(hào)、該簇頭的剩余能量大小以及該簇頭與Sink節(jié)點(diǎn)的間距大小。

入簇過程描述如下：

簇頭首先向網(wǎng)絡(luò)播送Head_Msg信息，如果普通節(jié)點(diǎn)只收到一條Head_Msg信息：此情況下，普通節(jié)點(diǎn)向此簇頭節(jié)點(diǎn)回傳含有自己序號(hào)的Join_OK(n)信息，加入收到廣播的簇頭所在簇；如果普通節(jié)點(diǎn)收到兩條或兩條以上Head_Msg信息：此情況下，節(jié)點(diǎn)通過比較距離和簇頭剩余能量，如果簇頭的距離相同，則選擇剩余能量更大的進(jìn)行入簇，向此簇頭節(jié)點(diǎn)回傳Join_OK(n)信息，并向其他簇頭節(jié)點(diǎn)發(fā)送Ref_Msg消息拒絕入簇。

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

在HDEFA-HP協(xié)議中，若簇頭與Sink節(jié)點(diǎn)之間的距離小于或等于臨界距離，簇頭將數(shù)據(jù)直接傳輸給Sink節(jié)點(diǎn)；若簇頭與Sink節(jié)點(diǎn)的距離大于，簇頭則在里層的簇頭中選取中繼節(jié)點(diǎn)，將數(shù)據(jù)多跳傳輸給Sink節(jié)點(diǎn)。中繼節(jié)點(diǎn)由式（20）設(shè)計(jì)的中繼選舉函數(shù)綜合考慮與Sink節(jié)點(diǎn)的通信距離和剩余能量進(jìn)行選擇。

式中：(CH,CH)表示簇頭到簇頭的距離；(CH,Sink)表 示 簇 頭到Sink節(jié) 點(diǎn) 的 距 離；(CH,Sink)表示簇頭到Sink的距離；(CH)表示簇頭的剩余能量；表示初始能量；可調(diào)節(jié)權(quán)重系數(shù)∈[0,1]。中繼選舉函數(shù)的值越小，表示該簇頭節(jié)點(diǎn)更適合當(dāng)選中繼節(jié)點(diǎn)，本文設(shè)置的值為0.3。

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

實(shí)驗(yàn)采用Matlab軟件進(jìn)行仿真，分別從存活節(jié)點(diǎn)數(shù)、能量消耗、接收數(shù)據(jù)包量三個(gè)方面對(duì)本協(xié)議進(jìn)行評(píng)估，將本文的HDEFA-HP算法與文獻(xiàn)[14]基于粒子群的分簇路由算法（PSO-ECHS）、文獻(xiàn)[15]基于螢火蟲算法的路由算法（FARW）進(jìn)行對(duì)比。設(shè)置參數(shù)如表2所示。

表2 仿真參數(shù)設(shè)置

圖4表示傳感器網(wǎng)絡(luò)初始化階段，100個(gè)節(jié)點(diǎn)隨機(jī)分布在邊界為100 m的正方形區(qū)域內(nèi)，Sink節(jié)點(diǎn)放置在中心位置，對(duì)區(qū)域進(jìn)行六邊形網(wǎng)格劃分后，篩選出每個(gè)網(wǎng)格內(nèi)剩余能量最大的節(jié)點(diǎn)作為備選簇頭節(jié)點(diǎn)。

圖4 正六邊形網(wǎng)格初始化

圖5表示三種協(xié)議在仿真中節(jié)點(diǎn)存活的狀況，其中，PSO-ECHS算法由于在數(shù)據(jù)傳輸階段未對(duì)LEACH算法做出改進(jìn)，仍由簇頭直接單跳傳輸數(shù)據(jù)至Sink節(jié)點(diǎn)，距離Sink節(jié)點(diǎn)遠(yuǎn)的節(jié)點(diǎn)能耗比距離近的更大，網(wǎng)絡(luò)負(fù)載不均衡，所以最早出現(xiàn)死亡節(jié)點(diǎn)，在第725輪就開始出現(xiàn)第一個(gè)節(jié)點(diǎn)死亡的現(xiàn)象，到第1 261輪所有節(jié)點(diǎn)死亡完畢；文獻(xiàn)[15]的FARW算法在選擇簇頭時(shí)未對(duì)分簇進(jìn)行優(yōu)化，數(shù)據(jù)傳輸階段未考慮螢火蟲算法的求解精度問題，出現(xiàn)死亡節(jié)點(diǎn)的輪數(shù)僅次于PSO-ECHS算法，在第825輪出現(xiàn)第一個(gè)節(jié)點(diǎn)死亡，到1 242輪所有節(jié)點(diǎn)死亡完畢；而HDEFA-HP算法經(jīng)過975輪第一個(gè)節(jié)點(diǎn)開始死亡，直至1 422輪節(jié)點(diǎn)全部死亡。以所有節(jié)點(diǎn)死亡的輪數(shù)作為協(xié)議的生命周期，通過對(duì)比可知：HDEFA-HP協(xié)議較PSO-ECHS算法延長(zhǎng)了約12.8%的生命周期；較FARW算法延長(zhǎng)了約14.5%的生命周期。

圖5 存活節(jié)點(diǎn)數(shù)

圖6為仿真中全網(wǎng)剩余能量的狀況。FARW算法能量消耗的最快，在1 242輪全網(wǎng)剩余能量被消耗至零；PSO-ECHS算法次之，在1 261輪耗盡全網(wǎng)能量；由于HDEFA-HP算法能夠避免選擇能量過低的節(jié)點(diǎn)作為簇頭，進(jìn)行高效率的簇內(nèi)數(shù)據(jù)傳輸，在找出最優(yōu)簇頭后，根據(jù)與Sink節(jié)點(diǎn)的距離，綜合考慮節(jié)點(diǎn)的距離指標(biāo)與能量指標(biāo)，選擇合理的中繼轉(zhuǎn)發(fā)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，建立傳輸路徑，數(shù)據(jù)沿著適宜的路徑進(jìn)行簇間傳輸，防止能量產(chǎn)生不必要的損失，所以剩余能量下降較慢，直至1 422輪才耗盡全部能量。

圖6 剩余能量

圖7仿真了Sink節(jié)點(diǎn)接收數(shù)據(jù)包的情況。隨著輪數(shù)的增加，由于PSO-ECHS算法對(duì)數(shù)據(jù)傳輸階段未做出改進(jìn)，HDEFA-HP算法在全部節(jié)點(diǎn)死亡之后所傳輸?shù)臄?shù)據(jù)包量約為PSO-ECHS算法的1.22倍，約為FARW算法的1.15倍。通過對(duì)比可知，由于HDEFA-HP算法在選舉簇頭環(huán)節(jié)時(shí)已經(jīng)考慮了待選的簇頭節(jié)點(diǎn)與Sink節(jié)點(diǎn)的距離，同時(shí)在數(shù)據(jù)傳輸部分綜合考慮了路徑中待選節(jié)點(diǎn)的剩余能量因素和距離因素，相比PSO-ECHS算法與FARW算法能夠形成適宜的路徑以傳輸數(shù)據(jù)包，避免了傳輸過程中數(shù)據(jù)包的丟失，所以在仿真結(jié)果中Sink節(jié)點(diǎn)接收到的數(shù)據(jù)包量最大。

圖7 接收數(shù)據(jù)包量

4 結(jié)語

基于混合差分進(jìn)化螢火蟲路由算法，在簇頭選舉中首先劃分網(wǎng)絡(luò)，初步選出剩余能量高的節(jié)點(diǎn)作為備選簇頭，通過衡量待選簇頭節(jié)點(diǎn)的剩余能量、簇內(nèi)節(jié)點(diǎn)密度以及與Sink節(jié)點(diǎn)的間距，選舉出適宜的簇頭節(jié)點(diǎn)，延長(zhǎng)簇頭節(jié)點(diǎn)的存活時(shí)間；綜合考慮路徑中待選節(jié)點(diǎn)的距離指標(biāo)和能量指標(biāo)，將合適的中繼節(jié)點(diǎn)分配給距離Sink節(jié)點(diǎn)較遠(yuǎn)的簇頭。實(shí)驗(yàn)結(jié)果表明，HDEFA-HP算法性能優(yōu)于PSO-ECHS算法與FARW算法，在網(wǎng)絡(luò)中較為準(zhǔn)確地選舉簇頭，降低不適宜節(jié)點(diǎn)當(dāng)選簇頭導(dǎo)致的死亡率，延長(zhǎng)了整體網(wǎng)絡(luò)的運(yùn)行時(shí)間，均衡了整體網(wǎng)絡(luò)節(jié)點(diǎn)的能量損耗。