改進蟻群算法的環境能源采集型WSN多目標路由研究

曹 迪，謝敏杰，黃霆豪，雷艷靜，李 偉，周加峰

1(浙江工業大學 計算機科學與技術學院，杭州 310023)

2(英國利物浦大學 電氣工程系，利物浦 英國)

1 引 言

無線傳感器網絡是一種分布式傳感網絡，它由大量可以感知和檢查外部世界的傳感器節點自組網組成.由于其應用場景不斷擴展，以及無線傳感器網絡節點規模不斷增加，使得采用傳統電池供電方式的傳感器網絡節點維護成本變得更加高昂，而能源采集為無線傳感器網絡的供能提供了一個新的解決方案[1].隨著微能源采集技術MEH(Micropower Energy Harvesting)的逐步成熟[2]，越來越多的研究將能源采集技術應用于無線傳感器網絡中，從而延長整體網絡的工作壽命.

目前針對能源采集型無線傳感器網絡的主要研究方向有：能源的收集模型，能源的優化調度，數據路由，拓撲管理和設備控制等[3-6].其中，路由在優化能源效率方面發揮著重要作用，進而使得網絡壽命得以延長[7,8].然而，對于環境能源采集型無線傳感器網絡來說，設計合適的路由協議面臨更多的挑戰.這些挑戰來自于相較傳統無線傳感器網絡更加復雜多變的外部環境.其外部環境能源在空間分布方面，以及時間變化方面都存在隨機性，使得對節點采集功率的預測難以實現.其次，網絡節點模型發生了改變.節點本身除了傳輸數據外，還兼顧采集能量的充放電及存儲，其物理模型變得更加復雜.因此，設計復雜度低、自適應性強和易于維護的路由協議，可以為能源采集型無線傳感器網絡實現穩定自供電提供基礎保障.

目前針對環境能源采集型無線傳感器網絡路由算法的研究主要集中在節點從外界環境吸收能量的速率大于等于節點消耗能量速率的前提下實現最大化網絡吞吐量.文獻[9-11]將損耗感知的概念加入到傳統WSN路由協議中，將無線傳感器網絡的能量損耗分為路由消耗和電池過充損耗兩個部分，通過綜合分析節點的能量損耗狀態決定數據包的路由路徑，降低了網絡路由的能量損耗.考慮到能源采集型無線傳感器網絡面臨環境能源分布不均勻的問題，文獻[12，13]將節點的能源采集功率作為影響因素之一加入到路由設計之中，使得無線傳感器網絡對外部環境能源變化具備了一定的自適應性.但由于外界環境變化的隨機性，通過設計統一模型難以應對各個節點所處環境差異大的問題，其自適應性仍然存在較多局限.

啟發式算法具備通過個體或全局狀態在隨機的群體中尋得最優解的特性，所以采用啟發式算法設計路由對于應對各節點所處環境的變化具有優異作用.其中文獻[14]將節點能量水平和傳輸距離結合到蟻群路由協議中，提出了EEABR路由算法，各個節點通過向sink節點發送前進螞蟻，并將路徑中的中繼節點記錄在數據包中，待前進螞蟻到達sink節點后，進行路徑適應值計算，并通過后向螞蟻進行路徑上的信息素更新.該路由協議可以更好的適應網絡中節點能量狀態的變化，并找到最優路徑，但其前進螞蟻路徑試探的過程是全局的，并且存在盲目性，使得算法收斂較慢并造成不必要的能量浪費.ACOHCM在經典蟻群路由的基礎上結合了最小跳算法，對路徑搜索集進行了篩選，并在信息素更新方案上進行了改進，使得蟻群算法的收斂速度變得更快，有效降低了路徑搜索階段的能量消耗[15].但針對能源采集型無線傳感器網絡存在能量波動無法預測的問題，仍然沒有成熟的應對方法.

針對以上問題，本文采用能源采集型無線傳感器網絡節點的能量狀態信息，對蟻群路由進行了改進，改進后的蟻群路由ESMACO(Energy state Multi-objective ant colony optimization)通過設計能量波動狀態的光傳播篩選算法EFLPS(Energy fluctuate light Propagation Selecting)，在綜合評估網絡節點能量狀態的前提下，有效減少蟻群路徑搜索的節點范圍.ESMACO路由算法進一步針對能源采集型WSN路由中的多目標平衡優化問題，提出了新的啟發因子及信息素更新策略，使得改進后的算法在能耗、能量均衡及網絡生存期多個維度得到協調優化.改進后的路由算法實現了路由路徑搜索的快速收斂，并且在有效降低網絡功耗的同時使得網絡節點能量均衡度得到提升，使得無線傳感器網絡長期保持穩定自供電.

2 系統模型

2.1 能源采集型WSN網絡模型

環境能源采集無線傳感器網絡是一種自組織網絡，由多個分布式無線傳感器節點和一個sink節點組成.傳感器節點可以從周圍環境中收集能源，并進行環境感知；進一步對采集數據在節點進行基本計算，并通過無線電發射機與通信范圍內節點進行通信.傳感器節點從目標區域采集到的數據，最終通過路由轉發到sink節點，并上傳到服務器作進一步深度處理，在我們的算法中的網絡模型具備以下5個特征：

1)所有傳感器節點符合隨機分布規律，任意兩個節點均不在同一位置.

2)所有傳感器節點的坐標位置已知，且sink節點了解整個網絡的拓撲信息.

3)所有傳感器節點同構，且節點的初始狀態都相同.

4)所有傳感器節點均可以從周圍環境中采集能源，其各自的采集功率因環境變動而變動.

5)sink節點具備無限能源，且一直保持接收狀態.

2.2 節點能源采集模型

本文采用混合能源采集形式，其混合能源采集系統框架如圖1所示，其中外部環境能源的采集方式有電磁感應，光電效應，溫差取電等不同方式.混合后能源的采集功率并非是多個單能源采集功率的簡單算術疊加，而是多能源之間相互取舍后，對混合能源最大功率點的逼近所得.為了提高能量的轉化及使用效率，需通過帶有MPPT(Maximum Power Point Tracking)跟蹤功能的功率管理單元PMU(Power Management Unit)對混合能源的最大功率點進行跟蹤[16].

圖1 混合能源采集系統框架

由于網絡中不同地理位置的節點，在某個特定時刻的采集功率是不同的，并且同一個節點在不同時段的采集功率也是不同的.所以本文采用HPi_t(Harvesting Power)表示節點i在t時刻的采集功率，其單位為毫瓦.

2.3 路由能量消耗模型

在無線傳感器網絡中，數據發送所消耗的節點能量遠遠高于數據接收(包括數據處理和數據接收)所消耗的能量，因此，研究主要集中在數據發送的能量消耗上.我們主要參考文獻[17]中對數據傳輸的能量損耗估算模型，其中，發送節點的能量消耗包括運行電子設備(包括數據接收)和發送模塊的功放能耗，而接收節點的能量消耗，為運行電子設備(包括數據接收)的功耗.因此，發送kbit數據到距離為d的接收節點，其能量損耗為：

ETγ(k,d)=ETγ-elec(i,j)+ETγ-amp(k,d)=k(Eelec+εfsd2)

(1)

其中ETγ-elec為運行電子設備的能耗，包括傳感器模塊的數據采集以及MCU對數據的計算處理，ETγ-amp為無線模塊發送數據的功耗，其功耗大小與數據包大小及傳輸距離相關，及數據越多，傳輸距離越遠能耗越高.

數據接收節點由于其數據接收功耗遠低于數據發送功耗，與其他電子設備運行處于同一級別能耗數量級，因此將接收節點的能耗用運行電子設備的能耗進行歸一化表示，其接收kbit能耗公式為：

ERe(k)=ERe-elec(k)=kEelec

(2)

2.4 能量波動項

區別于傳統的無線傳感器網絡，基于環境能源采集的無線傳感器網絡，節點中存儲的能量會隨著節點外部環境變化以及工作狀態在時間和空間上呈現波動性.

本文將傳感器節點IDi通信范圍內，所有節點的能量狀態，歸一化表示到同一平面，稱為節點IDi視角中的能量波動平面.通過采用鋰電池的荷電狀態SOC(State of charge)以及能源采集功率HPi_t作為衡量節點能量波動性的參數指標.SOC主要反映鋰電池的剩余容量,其數值上定義為剩余容量占電池容量的比值,常用百分數表示.根據鋰電池的充放電特性，在充放電前期以及后期開路電壓與SOC呈明顯的線性對應關系，但是在充放電的中期開路電壓處于一個穩定狀態，因此難以直接使用開路電壓轉換為節點能量狀態，而需要進行估算修正處理[18].常用的SOC估算方法有開路電壓法、內阻法、負載電壓法、線性模型法等.

根據文獻[19]中支配等級排序的方法，通過將節點IDi通信范圍內所有節點的兩個參數，采集功率HPi_t和SOCi進行歸一化處理后，作為共同衡量當前節點周邊能量波動的指標.具體方法：首先，將當前節點IDi通信范圍內各節點的SOCi和采集功率HPi_t進行歸一化處理后分別作為能量波動平面的X軸值和Y軸值(由于HPi_t和SOC都是線性變量，因此本文忽略其個體擁擠距離計算的步驟).

進一步，如圖2所示將節點IDi通信范圍內的節點分別向X軸和Y軸作垂線，若節點與坐標軸所圍成的矩形內不包含任何其他相鄰節點，則該節點的支配等級Grade為0；若節點與坐標軸所圍成的矩形內包含其他節點，則取包含節點中支配等級最大的節點，將其支配等級值Grade+1后作為該節點的支配等級.支配等級Grade值越大，表示該節點的能量狀態在當前節點IDi的能量波動平面中的優秀程度越高.

圖2 能量波動平面

根據節點IDi能量波動平面計算得出所有通信范圍內節點的支配等級后，進一步的，可根據通信范圍內各節點對應的坐標位置，進一步得到節點的能量波動分布圖，如圖3所示.其中四角星號代表節點IDi所在位置，并以節點IDi作為圓心，以最大通信距離作為半徑，標記在通信范圍內所有相鄰節點的支配等級Grade值及坐標位置，共同組合成節點IDi的能量波動分布圖，該圖可作為衡量對應區域網絡能量平衡的指標，用于節點下一跳路由節點的評價參數之一.進一步重復該動作，構建網絡中所有同構節點相對應的能量波動分布圖.

圖3 通信范圍內節點能量波動分布圖

3 ESMACO路由概述

3.1 網絡拓撲建立

網絡拓撲建立的具體實現方法是：從匯聚節點sink開始，攜帶節點自身層次號level、ID、坐標位置、及SOC和HPi_t，按照下述機制遍及整個網絡：

1)通過從sink開始向外廣播，廣播數據包內容包括節點自身的層次號level、ID、坐標位置及SOC和HPi_t.其中sink節點的level值為0.

2)接收到廣播的節點將該數據包的源節點記錄在通信范圍內節點的集合中，并判斷有無新路由信息，若有則更新其路由信息數據表，進一步判斷源節點level值與本節點level大小.

3)若源節點的level值小于本節點level，則將源節點的level值加一作為本節點level值，并繼續向外廣播.

4)若源節點的level值大于本節點level，則只更新路由信息.

3.2 路由候選集篩選

本節提出了一種基于能量波動狀態的光傳播轉發候選集篩選算法EFLPS(Energy fluctuate light PropagationSelecting).根據上文所述的能量波動平面，將節點IDi通信范圍內的節點根據其對應的支配等級分級.進一步的使用EFLPS算法對節點IDi能量波動分布圖內節點進行篩選，算法示意如圖4所示.

圖4 EFLPS篩選算法示意圖

其中(xi，yi)是當前節點IDi坐標，(xj，yj)是待篩選節點坐標，(xo，yo)是sink節點坐標，B為可視角大小，運算過程中可視角大小可變化，可視角上限值為B_max，A為源節點到sink節點的向量IO與源節點到鄰節點向量IJ的夾角，R是節點通信范圍半徑.

可視角B及可視角的上限B_max的初始化閾值可根據無線傳感器網絡所處的外部環境進行調整，當無線傳感器網絡外部環境能量越充足，可視角的初始化閾值可相應減小，以提高路徑搜索速度；當無線傳感器網絡能量不充足時，可視角的初始化閾值可相應加大，以提高更優解得出的概率.

源節點到sink節點的向量IO與源節點到鄰節點向量IJ的夾角A：

(3)

∠A=

(4)

EFLPS算法偽代碼如算法1所示.

算法1.能量波動光傳播篩選算法EFLPS

輸入：通信范圍內節點路由信息Node(SOC，HP，x，y，ID)，可視角B，可視角上限值B_max

輸出：符合條件的節點集合EFLPS()

1.初始化Node數組及B、B_max

2.根據支配排序方法計算Node各節點Grade值，保存至Node數組

3.計算源節點到Sink向量IO與源節點到鄰節點向量IJ的夾角A,保存至Node數組

4.計算Node數組中Grade最大值，保存為Grade_max

5.while(EFLPS()!=NULL)

6.fori=Grade_max；i>-1；i--do

7. 篩選出Grade=i的節點

8.forj=B;j

9.if數組Node中存在A

10. 節點保存至EFLPS()；break；

11.else

12.continue；

13.endfor

14.endfor

15. 輸出周圍無節點；break；

16.end

3.3 路由發現機制

路由發現機制由蟻群算法進行實現，其中蟻群算法的概率轉移主要有兩個關鍵部分決定，即路徑上的信息素濃度以及啟發因子.本節根據能源采集型WSN節點特有的能量波動特性，提出了基于能量波動性的啟發因子，可以使得網絡能量均衡性得到優化，并提升采集能源的利用率.

3.3.1 啟發函數

螞蟻從節點i轉移到節點j的期望程度用啟發函數ηij表示：

(5)

3.3.2 路徑概率選擇

螞蟻的概率選擇采用傳統的輪盤算法：

(6)

3.3.3 信息素更新

考慮到能源采集型無線傳感器網絡的路由優化目標不是單一的，需要同時對能量利用的高效性以及整個網絡能量分布的均衡性進行優化，因此在信息素更新的方式上，參考文獻[19]中對多目標問題優化的方法，分別將優化目標歸一化表示為3個最大化目標函數：

1)若所有i∈(1，2，3)，都有fi(ma)≥fi(mb)成立.

2)且存在i∈(1，2，3)，使得fi(ma)>fi(mb)成立.

3)則稱ma路徑支配mb.

若螞蟻所經過路徑不支配任何其他路徑，則該路徑的優秀程度最低，則該路徑的路徑等級RGm(Route Grade)為0，若螞蟻m的路徑支配多個其他路徑，則將支配路徑中最大的路徑等級加1后作為該路徑的RG值，其中RG值越大則路徑的優秀程度越高.

因此路徑的中繼節點越少，該路徑的能量消耗越小；路徑中節點的平均SOC和采集功率越大，則所選節點的能量狀態越好，這樣的改進方式不僅可以保證能源采集傳感器網絡能耗的節約，并且同時提高了采集能源的有效利用效率和網絡節點能量的分布均衡度.

其信息素更新公式如公式(7)、公式(8)所示，其中：λ1，λ2，λ3為多目標的歸一化系數.

τij(t+1)=(1-ρ)τij(t)+Δτ

(7)

(8)

(9)

(10)

3.4 ESMACO路由算法實現

在ESMACO路由算法的實現過程中，主要包括3個步驟，即網絡信息初始化、網絡拓撲生成和路由查找.首先通過sink節點進行廣播擴散建立整體網絡拓撲結構.進一步在路由發現機制中，對所有同構節點采用以下3步進行路徑探索：第一步采用候選集篩選算法EFLPS篩選出蟻群探索候選節點集合EFLPS().第二步根據公式(6)計算得出下一跳節點ID，并對螞蟻位置進行更新.最后重復上述兩部，直到得出前往下一跳節點IDi的最優路徑m.進一步地根據多目標優化信息素更新方法，通過計算每只螞蟻的路徑等級RGm，獲得反向更新路徑信息素濃度，通過迭代輸出最優路徑.

算法2.能源狀態多目標蟻群路由算法ESMACO

1.初始化(荷電狀態SOC，采集功率HP，可視角閾值B，可視角上限值B_max，節點的通信半徑R)

2.網絡拓撲生成(包含周圍節點的ID，SOC，HP，坐標)

3.while(路由發現)

4.fornode i=1 to Number_of _Nodesdo

5.foriter=1 to Number_of _Iterationdo

6.forant=1 to Number_of _Antsdo

7. 根據EFLPS算法篩選出下一跳節點候選集

8. 根據公式(6)蟻群轉移概率P得出中繼節點ID

9. 更新螞蟻當前位置

10.endfor

11. 根據多目標優化方法計算各螞蟻路徑等級RG

12. 結合各路徑等級值，通過公式(7)、公式(8)計算反向更新路徑信息素濃度

13.endfor

14. 從迭代中選出最優路徑

15.endfor

16.輸出最佳路由路徑

17.end

4 實驗仿真與分析

4.1 仿真設置

為了評估ESMACO算法的性能，在MATLAB中對WSN環境及網絡運行進行了仿真.在我們的模擬網絡中，區域面積為100m×100m，生成200個節點隨機分布于區域中，假設sink節點位于整個區域的中心.

其中所有普通節點的初始能量C相同，各節點采集功率HP的變化規律及變化范圍，通過設計的混合低頻電磁場及太陽能采集的無線傳感器自供電系統在不同環境中采集所得.混合低頻電磁場及太陽能采集的無線傳感器自供電系統實驗平臺如圖5所示，其中光電轉化模擬環境，采用84.5mm×55mm的單晶硅光伏板在不同的光照強度下進行；磁電轉化模擬環境，采用內部為強導磁材質的緊密纏繞工型螺線圈，在亥姆霍茲線圈發生的不同強度的勻強磁場中進行.

圖5 混合能源采集供電系統

算法中其余各參數的優選值均由實驗所得，具體數值如表1所示.

表1 仿真參數表

4.2 路由收斂速度分析

在無線傳感器網絡中，由于節點的能量有限，以及動態的網絡拓撲，因此至關重要的是，路由協議需以低成本計算出最佳路徑.所以路由算法的收斂速度快慢和搜索成功率高低，是重要的評價指標.經過實驗，比較幾種算法的收斂速度，包括經典的ACO，EEABR，ACOHCM[14，15]和ESMACO.這4種算法分別運行100次，每種算法的平均迭代次數如圖6所示.結果表明ESMACO算法平均經過20次迭代后找到最優解；ACOHCM算法平均經過38次迭代后找到了最優解，而EEABR則需要102次迭代，經典算法ACO則平均需要170次迭代.因此，證明就收斂速度而言，ESMACO算法優于其他3種算法.

圖6 路由收斂速度對比圖

ESMACO算法收斂速度的提高主要包括以下兩個原因.一方面，通過使用EFLPS算法對周圍節點進行篩選，大大減少了蟻群搜索集合的元素個數.另一方面是因為信息素更新的方式采用了，多目標優化支配排序的方法，在多目標平衡優化的基礎上，使得最優路徑的信息素濃度增加更快，進一步使得算法收斂更快.

進一步的由于算法收斂速度的提升，可以大幅度降低路由探索階段的能量浪費，從而將能量更多的用于數據上傳，提高網絡能量利用率.

4.3 網絡能量均衡度分析

在能源采集型的無線傳感器網絡中，由于節點外部采集環境的隨機性使得各個節點的采集功率變化，并且相互之間的差異較大，如果各節點的能量水平SOC變化較大，則會引起路由路徑的頻繁變動.間接的提高了路由維護的能量消耗，以及降低了網絡的穩定性.因此無線傳感器網絡各節點SOC的均衡度至關重要.

通過比較幾種算法在不同的網絡規模下，各節點SOC的方差值，以用于比較網絡能量的均衡度，包括經典的ACO，EEABR，ACOHCM[14，15]和ESMACO.這4種算法分別在相同網絡規模及外部環境條件下模擬運行200天，每種算法的節點SOC方差變化如圖7所示.結果表明經典蟻群算法隨著運行時間，節點能量均衡度逐漸變差；EEABR 和ACOHCM算法也隨著時間節點能量均衡度慢慢變差，但由于這兩個算法中考慮到了能量的因素，所以其均衡度優于經典ACO算法；ESMACO算法的方差最小,可長期保持在100以內，因為ESMACO算法在啟發函數中不僅考慮了節點的SOC，同時也考慮了節點的采集功率，并且在信息素更新方式上也使用了多目標優化的方法，使得在優化網絡能效的同時也對網絡能量均衡度進行很好的優化.并且可以從圖中看出，ESMACO算法在網絡能量均衡度變差的情況下，自適應的進行了調整，使得節點SOC方差自適應的逐漸減小.

圖7 網絡能量均衡度對比圖

網絡各節點之間的能量均衡，可以進一步的說明，能源充足的節點更多的分擔了網絡數據路由任務，即提高了整個網絡的能量利用率.

5 總 結

無線傳感器節點節能技術近年來已成為傳感器網絡方向研究的熱點，采用能量采集技術，利用環境中的微弱能量對無線傳感器節點進行能量補充，是提高無線傳感器節點使用壽命的重要手段.本文針對能源采集型的無線傳感器網絡外部環境差異大且隨機性強的問題，提出了一種改進蟻群算法的多目標優化路由算法.通過設計能量波動狀態的光傳播轉發候選集篩選算法EFLPS減少蟻群搜索的節點范圍，顯著提高了路由算法的收斂速度.并通過結合多目標優化支配排序的方法，提出了新的啟發因子及信息素更新策略，使得蟻群路由算法可以在能耗和能量均衡兩方面得到協調的優化，使得改進后的蟻群路由ESMACO不僅提高采集能源的有效利用率及功耗的優化，且使得網絡節點之間能量均衡度較好，使得無線傳感器網絡可以保持長期的穩定自供電.在未來的工作里，本文可進一步在能量管理模型上做出相應分析，結合無線傳感器節點的低功耗設計進一步優化節能效果，同樣可以擴展到多節點的無線傳感器網絡中進行網絡整體優化.