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