摘 要： 針對無線傳感器網絡路徑優化問題，提出了一種改進的最優保存的遺傳模擬退火算法。利用LEACH算法構建初始路由表，使用GASA的高效率搜索，將路由計算和遺傳演化計算同時進行，并直至尋找到近似最優路徑為止。將最優保存遺傳算法和模擬退火算法相結合，引入自適應的概率變化，有效地解決了這兩種算法的早熟現象和時間問題。仿真實驗表明，該算法有效地解決了無線傳感器路徑優化問題，具有定位準確、節能和搜索能力較強等優點。
關鍵詞： 無線傳感器網絡；定位；最佳路徑；遺傳模擬退火算法
隨著計算機網絡的飛速發展，無線傳感器網絡WSN(Wireless Sensor Networks)由于其良好的特性而成為研究的熱點。WSN由許多功能相同或不同的廉價微型傳感器節點以自組網絡的方式構成，是計算機技術、通信技術和傳感技術交叉融合的產物[1-2]。這些節點通常被撒播于無人監控或難以到達的區域，通過傳感、數據采集、傳送和融合來實現特定的應用，因此其在軍事、工業、家居、環境、生態等諸多領域都有著廣闊的應用前景。WSN的路徑優化目標是尋找并建立節能高效的、從傳感器節點到接收器節點(Sink)的數據傳輸的可靠路徑，使WSN的壽命最大化。考慮到WSN節點能量有限且不能補充，WSN的路徑優化不僅與路徑長度有關，還與節省能量和整個網絡能量的均衡消耗有關。
WSN路徑優化問題的關鍵技術是多目標優化求解，即采用何種方法來確定最優路徑方案，以及如何評估所選路徑方案的優劣程度，因此這個問題是一個NP-hard問題。
對于此類問題，比較常用的優化算法有遺傳算法和模擬退火算法。遺傳算法很容易陷入局部最優解，而不能搜索到全局最優解。模擬退火算法雖然能夠跳出局部最優解，但它是一種個體尋優算法，且搜索空間很大，這導致搜索效率很低。因此還需要在現有的優化方法基礎上進一步研究尋找更優化的方法。
1 WSN模型及拓撲描述
在WSN中，獲得監測數據的傳感器節點為源節點，其數據經過多跳聚集到匯聚節點(Sink Node)或基站(Base Station)，再通過互聯網或衛星到達管理節點或用戶。本文采用的基于被動分簇算法的能源有效WSN模型是目前無線傳感器網絡中最適用于數據交換的一種[3]，即僅當網絡中有數據通信要求時才在網絡中建立分簇網絡拓撲，而且網絡拓撲的建立與維護都在本地完成，不需要單獨的控制命令，以節省能量開銷。分簇策略中最重要的是簇首選舉機制和網關節點的選擇機制，簇首選舉采用“先聲明者勝”的選舉機制，網關節點的選擇則是根據在網絡健壯性和能源有效性之間平衡的原則來確定選擇機制。在網絡模型建立過程中設定了一些與網絡拓撲的建立相關的處理機制，主要包括包的處理機制、簇首聲明機制、簇成員形成機制以及網關節點聲明機制，這些機制能有效地保證網絡拓撲的建立。
2 遺傳模擬退火算法
遺傳退火算法是一種混合的優化算法，它將模擬退火算法融入到遺傳算法當中[4]。與基于遺傳算法的總體運行過程類似，遺傳模擬退火算法也是一組隨機產生的初始種群中全局最優解的搜尋過程。它首先通過選擇、交叉、變異等遺傳操作產生一組新的個體，然后再獨立地對所產生的個體進行模擬退火過程，并將結果作為下一代種群中的個體[4]。反復迭代地進行這個過程，直到滿足某個終止條件為止。利用模擬退火算法的收斂性以避免出現“早熟”的收斂現象，可以提高算法的優化性能。同時，本文對變異算子引入了自適應變異的思想，使變異概率能夠自適應地變化。
當溫度較高時，擁有較高的變異率，隨著降溫過程的繼續，變異率不斷地縮小以避免破壞優秀的基因。當退火進行到種群里的各個基因的適應度差距很小時，重置退火溫度T，使種群的變異率加大，以豐富種群的多樣性，加速能夠使算法脫離局部最優點，提高了算法的搜索性能。根據問題求解的實際接近程度，對每一個染色體指定一個適應度的值。本文的遺傳退火算法采用保留部分最佳染色體的方法，以保護當前最優染色體，提高算法的收斂性能。同時，為了解決由于采取保留最優解而使算法收斂于局部最優解的問題，在問題的解適應度的值相差較小時，用提高變異概率的方法來增強種群的多樣性，使得問題跳出局部最優解。通過多次的上述操作，問題將最終收斂于全局最優解。
2.1 適應度函數的選取
在本文的適應度函數中，為了避免“早熟”現象，即降低適應度較高的個體與其他個體適應度之間的差異，保持了群體具有多樣性。遺傳模擬退火算法的適應度函數[5]采用啟發式方法，將其定義為：
2.3 選擇
設計選擇算子時采用排序選擇，選擇策略為轉盤式選擇，同時使用最佳個體保留策略，即從當前種群中選擇D%的最佳染色體直接復制到下一代種群中。
2.4 交叉和變異
交叉采用算術交叉，它是指兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。通過對父代染色體間區域進行多次交叉操作，然后利用包含在新個體集合中的信息進行信息最大化的選擇，對每一代個體進行基于適應度的選擇。
變異采用離散單點變異。本文采用替換路徑中的節點和刪除路徑中多余節點兩種方法。替換方法為：(1)尋找路徑仍未達到目的節點時，把路徑的最后一個節點替換為可以與其前一個節點構成鏈路的節點。(2)在適應度值滿足并已達到目標節點的路徑中，引入自適應的概率變化進行替換，替換準則為尋找既能與其前一節點又能與其后一節點構成鏈路的節點替換當前節點。刪除多余節點的方法為：對任選的一條路徑，隨機選擇一個變異節點，尋找路徑中所選擇變異節點之后的節點中是否有能與其構成鏈路的節點，如果有，則與之相連，將中間的節點舍棄。
2.5 終止條件
本文的遺傳模擬退火算法(GASA)終止條件采用復合準則：迭代次數達到預設要求和種群成熟度滿足一定條件，且種群的平均適應值提高不足1%；或進化代數已達到預先設定的最大值，停止迭代。
3 改進的遺傳模擬退火算法IGASA
根據上述改進算法的基本思想，建立一種適用于WSN路徑尋優的遺傳退火算法。
(1)種群的初始化。設定種群大小、初始溫度、染色體長度、交叉概率、變異概率。重置T的次數、各個個體差異度。隨機初始化種群，為了改善初始化搜索性能，為每一個染色體指定一個適應度的值。
(2)適應度函數的判斷。篩選當前最好的個體進入下一代種群。
(3)進行遺傳操作。選擇策略采用輪盤賭算子和最優保存策略相結合，交叉采用實數編碼的算術交叉，變異采用離散單點變異。
(4)模擬退火操作。新解接受條件采用Metropolis準則。
(5)更新、迭代過程。根據已篩選的當前最好個體和遺傳退火操作新生成的染色體，加速種群的進化，生成下一代新種群。計算種群中各個個體的適應度值，當小于給定值時，重置T，以增大變異的概率，更新父代個體中最優個體和最差個體，避免陷入局部最優解。
(6)判斷重置T的次數是否等于設定值，如果等于，轉到(7)，否則，轉到(2)。
(7)如果保留下來的個體中包含全局最優值，或者計算的代數大于限定值，算法結束；否則，轉到(2)。
(8)輸出最佳目標函數值。
本文提出的IGASA算法偽代碼如下：
上述代碼中，P(t)是GA的種群大小，Tt是初始溫度，noONodes是未知節點的個數，noOAnchors是錨節點的個數，R是節點的無線射程距離，L是每個T值的迭代次數。
4 仿真結果
為了評價IGASA算法在WSN路徑選擇上的性能，本文將此算法與相關的算法應用Matlab仿真進行了比較。仿真中，設實驗的WSN有500個節點，將未知節點隨機部署到一個100×100的規則正方形區域內，無線射程R設為10。根據參考文獻[5]-[6]對兩種算法的種群適應度值和網絡生命周期進行比較，再通過運行時間的變化，均能證明應用本方法可以實現對WSN路徑的優化。
(1)應用IGASA算法對WSN進行路徑優化仿真，種群適應度均值及最優個體的進化如圖1所示。從多次仿真結果可以看出，IGASA算法在種群均值變化的同時，最優個體的適應度值均能在較小的范圍浮動，全部成功地找到了優秀可行路徑，接近最優結果。
(2)應用IGASA算法和GA算法的路由路徑在網絡中運行，通過對如圖2所示的網絡生命周期的比較可以看出，隨著源節點個數的增加，基于IGASA的網絡生命周期一直大于基于GA的網絡生命周期，從而有效均衡了網絡能耗。
將IGASA與基于GA的WSN路徑優化進行比較，運行結果如表1所示，目標為通過降低搜索時間以使能耗減小。各參數如下：交叉率為0.38，變異率為0.2，種群大小為20，保存最優解占4%，對每種情況均運行20次。
本文引入GASA解決WSN的路徑優化問題，采用循環策略改進了WSN的遺傳路徑優化算法，并將改進后的IGASA算法應用于WSN路徑優化上。IGASA在確保遺傳算法有效性的前提下，增強了收斂效率，防止了“早熟”現象的發生。相對于標準模擬退火算法以及最優保存遺傳算法，該算法提高了算法的收斂效率又不失算法的收斂速度，具有相對的優越性。仿真結果表明，該方法取得了良好的定位效果，實現了最佳路徑尋優的目的，可以滿足實際運行需要。下一步將繼續對模擬退火和選擇部分進行改進，以獲得更好的效果。
參考文獻
[1] 周洪偉，原錦輝，張來順.遺傳算法“早熟”現象的改進策略[J].計算機工程，2007，33(19)：201-203.
[2] 劉泉，梁小宇.一種基于被動分簇算法的能源有效WSN模型[J].計算機工程與應用，2007，43(16)：142-145.
[3] 李陶深，李朔，陳松喬，等.基于遺傳算法的網絡選播路由算法的研究[J].小型微型計算機系統，2005，26(1)：50-55.
[4] 曹恒智，余先川.單親遺傳模擬退火及在組合優化問題中的應用[J].北京郵電大學學報，2008，31(3)：38-41.
[5] 雷霖，李偉峰，王厚軍.基于遺傳算法的無線傳感器網絡路徑優化[J].電子科技大學學報，2009，38(2)：227-230.
[6] TAM V， CHENG K Y， LUI K S. Using micro-genetic algorithms to improve localization in wireless sensor networks[J]. Journal of Communications， Academy， 2006(7)：47-52.