基于貪婪—改進果蠅算法的無線傳感器網絡路由協議*

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

(貴州大學 大數據與信息工程學院，貴州 貴陽550025)

0 引 言

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

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

1 算法設計

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

1.1 改進果蠅算法

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

然而，由于WSNs 內節點坐標值是離散和固定的，不利于果蠅算法的隨機擴散尋優，傳統果蠅算法的擴散迭代如式(1)

其中，X_axis，Y_axis 為當前最優分簇簇頭坐標，h 為步長。

根據實際情況，改進如下:

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

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

3)該簇頭位置變換為

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

4)改進果蠅算法擴散尋優迭代式為

1.2 適值函數

假設在一個二維監測區域，傳感器網絡有N 個節點，根據文獻［8］，對于一個邊長為a 的正方形區域，最優簇頭數目為

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

式中 M 為對應簇頭的簇內普通節點數。在改進果蠅算法每次種群擴散尋優時，計算簇頭到簇內節點的歐氏距離和為

為了實現網絡能量的平衡，以免節點提前死亡，每個簇頭節點的能量必須考慮在適值函數中。因此，改進后的適值函數如下

其中，Dismax為該輪最大的歐氏距離和，w 為調節因子。

1.3 基于貪婪—改進果蠅算法的WSNs

改進果蠅算法應用于WSNs 算法如下:

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

2)根據果蠅位置和簇頭節點能量計算適值函數(式(7))，求出適值最大的果蠅及其位置，如下式

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

則所有果蠅飛向該位置

且

4)根據改進果蠅算法擴散尋優迭代式(3)，每個果蠅隨機向四周搜尋食物。

由于自由空間無線傳輸的能耗為式(13)，d0=sqrt(εfs/εmp)，當d ＞d0時，采用多徑衰擾模式，如式(14);當d ＜d0時，選用自由空間模式［9］，如式(15)

一般情況下，節點的間距小于d0，節點與基站的間距大于d0。為避免直接傳輸造成的能量嚴重損耗，采用基于貪婪算法的多跳方式向基站轉發數據，貪婪算法是一種求最優解的簡單、高效的算法，通常包含一個用以尋找最優解的迭代過程［10］。

具體算法為:

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

2)根據Dmax對應的簇頭節點c 的位置，計算其與集合A中其他值對應簇頭的最短距離dmin，若A 中無其他值，則dmin為無窮大;

3)若dmin＜Dmax，則簇頭c 將數據轉發給該最短距離的簇頭;否則，轉發給Sink;

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

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

2 仿真結果

為了驗證CRP－FOAGA 算法的有效性，利用Matlab 進行仿真分析。設WSNs 中節點總數為100 個，監測區域為100 m×100 m，Sink 節點位置為(－50，50)m。網絡模型為:

1)Sink 節點固定，計算力強且能量供應充足;

2)節點能獲取自身位置信息，并發送給Sink;

3)傳感器節點能量有限，位置固定，不能移動;

4)節點均有唯一編號，隨機分布于監測域內。

算法參數如表1。

表1 算法參數Tab 1 Algorithm parameters

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

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

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

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

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

圖3 節點壽命比較Fig 3 Comparison of node lifetime

圖4 網絡剩余能量比較Fig 4 Comparison of remained energy of networks

圖5 不同w 值的節點壽命Fig 5 Node lifetime of different w value

3 結束語

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

［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－hop communications in wireless sensor networks［J］.IEEE Journal on Selected Areas in Communications，2010，28(7):1055－1062.

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

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

［5］ 潘文超.應用果蠅優化算法優化廣義回歸神經網絡進行企業經營績效評估［J］.太原理工大學學報，2011，29(4):1－5.

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

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

［8］ 郭 劍，孫力娟，王汝傳.基于最佳簇數的無線傳感器網絡粒子群分簇協議［J］.南京郵電大學學報，2010，30(2):36－40.

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

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