基于貪婪—改進(jìn)果蠅算法的無線傳感器網(wǎng)絡(luò)路由協(xié)議*

徐躍州，張 欣，張 濤，李 陽

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽550025)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)［1，2］是由大量、微型、廉價的傳感器節(jié)點(diǎn)組成的一種自組織多跳的無線網(wǎng)絡(luò)，作為物聯(lián)網(wǎng)的支撐技術(shù)，具有廣闊的發(fā)展前景。然而，由于傳感器節(jié)點(diǎn)所攜帶的能量十分有限，如何有效地延長網(wǎng)絡(luò)生存時間一直是研究的熱點(diǎn)［3］。由于WSNs分簇協(xié)議能降低能量消耗，提高數(shù)據(jù)轉(zhuǎn)發(fā)速率，得到了深入的研究。最經(jīng)典的分簇協(xié)議有LEACH，HEED，EECS［4］等。傳統(tǒng)的分簇協(xié)議沒有考慮簇頭節(jié)點(diǎn)的合理分布和能量的均衡，致使網(wǎng)絡(luò)可能產(chǎn)生更多的能耗。

基于此，本文提出一種新型WSNs 路由算法CRP－FOAGA(a clustered routing protocol based on improvement of fruit fly optimization and greedy algorithm for wireless sensor networks)，該算法結(jié)合果蠅和貪婪算法的高效尋優(yōu)性，對WSNs 的傳統(tǒng)分簇路由協(xié)議進(jìn)行改進(jìn)。根據(jù)WSNs 簇頭節(jié)點(diǎn)的布局和剩余能量，建立簇頭節(jié)點(diǎn)規(guī)劃的適值函數(shù)，通過改進(jìn)果蠅算法優(yōu)化分簇結(jié)構(gòu)，利用貪婪算法實(shí)現(xiàn)多跳傳輸，降低簇頭能耗，延長網(wǎng)絡(luò)壽命。

1 算法設(shè)計(jì)

CRP－FOAGA 算法是充分利用果蠅算法和貪婪算法的動態(tài)尋優(yōu)性，選擇能耗最低的路徑進(jìn)行WSNs 與基站的數(shù)據(jù)傳輸。本文先對傳統(tǒng)果蠅算法進(jìn)行改進(jìn)使之適用于WSNs，然后建立一種合理的適值函數(shù)，最終，提出基于貪婪—改進(jìn)果蠅算法的WSNs。

1.1 改進(jìn)果蠅算法

果蠅優(yōu)化算法［5］(fruit fly optimization algorithm，F(xiàn)OA)是臺灣學(xué)者潘文超從果蠅覓食行為中得到啟發(fā)，提出的一種尋求全局優(yōu)化的新型仿生學(xué)算法，廣泛運(yùn)用于求解函數(shù)極值、Z－SCORE 模型的系數(shù)調(diào)整以及各類神經(jīng)網(wǎng)絡(luò)等［6］。與其他智能算法(如蛙跳和粒子群算法)相比，算法簡單、收斂速度快，且FOA 僅需調(diào)整3 個參數(shù)，算法復(fù)雜度低［7］。

然而，由于WSNs 內(nèi)節(jié)點(diǎn)坐標(biāo)值是離散和固定的，不利于果蠅算法的隨機(jī)擴(kuò)散尋優(yōu)，傳統(tǒng)果蠅算法的擴(kuò)散迭代如式(1)

其中，X_axis，Y_axis 為當(dāng)前最優(yōu)分簇簇頭坐標(biāo)，h 為步長。

根據(jù)實(shí)際情況，改進(jìn)如下:

1)在選出分簇后，簇頭坐標(biāo)為(X，Y)，對于該分簇中每一個簇頭(x，y)，計(jì)算所有節(jié)點(diǎn)(包括自身)到其距離distance;

2)根據(jù)公式(2)對距離進(jìn)行升序排列，并生成隨機(jī)數(shù)r=unidrnd(sizepop)，sizepop 為果蠅算法種群數(shù)為

3)該簇頭位置變換為

(x(index(r))，y(index(r)));

4)改進(jìn)果蠅算法擴(kuò)散尋優(yōu)迭代式為

1.2 適值函數(shù)

假設(shè)在一個二維監(jiān)測區(qū)域，傳感器網(wǎng)絡(luò)有N 個節(jié)點(diǎn)，根據(jù)文獻(xiàn)［8］，對于一個邊長為a 的正方形區(qū)域，最優(yōu)簇頭數(shù)目為

其中，εfs，εamp分別為自由空間和多徑衰減下的功率放大恒參;d 為簇首到匯聚節(jié)點(diǎn)的距離，由此，本文選取K 個簇頭節(jié)點(diǎn)，記為Ci，i=1，…，K，坐標(biāo)為(Cxi，Cyi)，簇頭節(jié)點(diǎn)初始能量為E0，實(shí)時能量為Ei，i=1，…，K。普通節(jié)點(diǎn)的坐標(biāo)設(shè)為

式中 M 為對應(yīng)簇頭的簇內(nèi)普通節(jié)點(diǎn)數(shù)。在改進(jìn)果蠅算法每次種群擴(kuò)散尋優(yōu)時，計(jì)算簇頭到簇內(nèi)節(jié)點(diǎn)的歐氏距離和為

為了實(shí)現(xiàn)網(wǎng)絡(luò)能量的平衡，以免節(jié)點(diǎn)提前死亡，每個簇頭節(jié)點(diǎn)的能量必須考慮在適值函數(shù)中。因此，改進(jìn)后的適值函數(shù)如下

其中，Dismax為該輪最大的歐氏距離和，w 為調(diào)節(jié)因子。

1.3 基于貪婪—改進(jìn)果蠅算法的WSNs

改進(jìn)果蠅算法應(yīng)用于WSNs 算法如下:

1)初始化果蠅，種群數(shù)為sizepop，果蠅位置為(initX(t)，initY(t))，t∈(1，sizepop)，bestSmell=0。

2)根據(jù)果蠅位置和簇頭節(jié)點(diǎn)能量計(jì)算適值函數(shù)(式(7))，求出適值最大的果蠅及其位置，如下式

3)記錄當(dāng)前果蠅位置和最大適值bestSmell，若

則所有果蠅飛向該位置

且

4)根據(jù)改進(jìn)果蠅算法擴(kuò)散尋優(yōu)迭代式(3)，每個果蠅隨機(jī)向四周搜尋食物。

由于自由空間無線傳輸?shù)哪芎臑槭?13)，d0=sqrt(εfs/εmp)，當(dāng)d ＞d0時，采用多徑衰擾模式，如式(14);當(dāng)d ＜d0時，選用自由空間模式［9］，如式(15)

一般情況下，節(jié)點(diǎn)的間距小于d0，節(jié)點(diǎn)與基站的間距大于d0。為避免直接傳輸造成的能量嚴(yán)重?fù)p耗，采用基于貪婪算法的多跳方式向基站轉(zhuǎn)發(fā)數(shù)據(jù)，貪婪算法是一種求最優(yōu)解的簡單、高效的算法，通常包含一個用以尋找最優(yōu)解的迭代過程［10］。

具體算法為:

1)計(jì)算各個簇頭至Sink 節(jié)點(diǎn)的距離D，放入集合A 中，進(jìn)行降序排序:A=［Dmax，D2，…，Dmin］;

2)根據(jù)Dmax對應(yīng)的簇頭節(jié)點(diǎn)c 的位置，計(jì)算其與集合A中其他值對應(yīng)簇頭的最短距離dmin，若A 中無其他值，則dmin為無窮大;

3)若dmin＜Dmax，則簇頭c 將數(shù)據(jù)轉(zhuǎn)發(fā)給該最短距離的簇頭;否則，轉(zhuǎn)發(fā)給Sink;

4)從集合A 中剔除簇頭c，并進(jìn)行降序排列;

5)重復(fù)步驟(2)～(4)，直至集合A 為空集。

2 仿真結(jié)果

為了驗(yàn)證CRP－FOAGA 算法的有效性，利用Matlab 進(jìn)行仿真分析。設(shè)WSNs 中節(jié)點(diǎn)總數(shù)為100 個，監(jiān)測區(qū)域?yàn)?00 m×100 m，Sink 節(jié)點(diǎn)位置為(－50，50)m。網(wǎng)絡(luò)模型為:

1)Sink 節(jié)點(diǎn)固定，計(jì)算力強(qiáng)且能量供應(yīng)充足;

2)節(jié)點(diǎn)能獲取自身位置信息，并發(fā)送給Sink;

3)傳感器節(jié)點(diǎn)能量有限，位置固定，不能移動;

4)節(jié)點(diǎn)均有唯一編號，隨機(jī)分布于監(jiān)測域內(nèi)。

算法參數(shù)如表1。

表1 算法參數(shù)Tab 1 Algorithm parameters

圖1、圖2 為仿真任意時刻LEACH 與CRP－FOAGA 算法的分簇和路由情況比較圖，可以看出CRP－FOAGA 算法的分簇和路由更加合理，能顯著的降低網(wǎng)絡(luò)能耗。

圖1 LEACH 算法分簇與路由情況Fig 1 Clustering and routing of LEACH algortithm

圖2 CRP-FOAGA 算法分簇與路由情況Fig 2 Clustering and routing of CRP-FOAGA algorithm

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)壽命和網(wǎng)絡(luò)剩余能量如圖3、圖4，從圖3 可以看出:CRP－FOAGA 算法節(jié)點(diǎn)的壽命要遠(yuǎn)高于LEACH 算法，其首個節(jié)點(diǎn)和50%節(jié)點(diǎn)死亡的時間分別延長41%和17%;從圖4 可以看出:CRP－FOAGA 算法的網(wǎng)絡(luò)剩余能量的減少速度要明顯小于LEACH 算法。這說明CRPFOAGA 算法在分簇時的果蠅算法尋優(yōu)和利用貪婪算法進(jìn)行多跳轉(zhuǎn)發(fā)在每一輪中降低了節(jié)點(diǎn)能耗，減緩網(wǎng)絡(luò)能量消耗的速度，從而延長網(wǎng)絡(luò)生命周期。

圖5 給出了不同w 值對應(yīng)的節(jié)點(diǎn)壽命?？梢钥闯?增大w 值可以延長網(wǎng)絡(luò)的生存時間，但卻提前網(wǎng)絡(luò)簇頭節(jié)點(diǎn)的死亡時間。這是由于在式(7)中增大w 值節(jié)省了網(wǎng)絡(luò)能耗而犧牲了系統(tǒng)的可靠性。

圖3 節(jié)點(diǎn)壽命比較Fig 3 Comparison of node lifetime

圖4 網(wǎng)絡(luò)剩余能量比較Fig 4 Comparison of remained energy of networks

圖5 不同w 值的節(jié)點(diǎn)壽命Fig 5 Node lifetime of different w value

3 結(jié)束語

本文針對WSNs 的分簇方法和多跳傳輸問題，提出了一種基于貪婪和改進(jìn)果蠅算法的新型網(wǎng)絡(luò)路由協(xié)議CRPFOAGA。首先，根據(jù)節(jié)點(diǎn)位置和剩余能量定義了簇頭選擇的適值函數(shù)，同時，利用改進(jìn)果蠅算法對該適值函數(shù)進(jìn)行快速求解，并利用貪婪算法實(shí)現(xiàn)簇頭節(jié)點(diǎn)的多跳傳輸。通過Matlab 仿真得出:相對于傳統(tǒng)路由算法，CRP－FOAGA 算法合理規(guī)劃了簇頭節(jié)點(diǎn)分布，降低網(wǎng)絡(luò)能耗，提升了網(wǎng)絡(luò)的壽命，具有更好的性能。

［1］ Liu A F，Wu X Y，Chen Z G，et al.Research on the energy hole problem based on unequal cluster－radius for wireless sensor networks［J］.Computer Communications，2010，33(3):302－321.

［2］ Kalis A，Kanatas A G，Efthymoglou G P.A cooperative beam forming solution for eliminating multi－h(huán)op communications in wireless sensor networks［J］.IEEE Journal on Selected Areas in Communications，2010，28(7):1055－1062.

［3］ 陳良銀，王金磊，張靖宇，等.低占空比WSNs 中一種節(jié)點(diǎn)休眠調(diào)度算法［J］.軟件學(xué)報，2014，25(3):631－641.

［4］ 陳志軍，李 明.基于免疫退火的WSNs 簇首節(jié)點(diǎn)選擇方法研究［J］.重慶師范大學(xué)學(xué)報，2014，31(2):72－76.

［5］ 潘文超.應(yīng)用果蠅優(yōu)化算法優(yōu)化廣義回歸神經(jīng)網(wǎng)絡(luò)進(jìn)行企業(yè)經(jīng)營績效評估［J］.太原理工大學(xué)學(xué)報，2011，29(4):1－5.

［6］ 程 慧，劉成忠，基于混沌映射的混合果蠅優(yōu)化算法［J］.計(jì)算機(jī)工程，2013，39(5):218－221.

［7］ 韓俊英，劉成忠，自適應(yīng)變異的果蠅優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用研究，2013，30(9):2641－2644.

［8］ 郭 劍，孫力娟，王汝傳.基于最佳簇?cái)?shù)的無線傳感器網(wǎng)絡(luò)粒子群分簇協(xié)議［J］.南京郵電大學(xué)學(xué)報，2010，30(2):36－40.

［9］ 胡 靜，沈連豐，宋鐵成，等.新的無線傳感器網(wǎng)絡(luò)分簇算法［J］.通信學(xué)報，2008，29(7):20－26.

［10］汪魯才，張 健.無線傳感器網(wǎng)絡(luò)的多跳路由協(xié)議［J］.傳感器與微系統(tǒng)，2013，32(8):14－17.