【文章內(nèi)容簡介】 器網(wǎng)絡(luò)路由設(shè)計研究領(lǐng)域的熱點。隨著 各種智能算法的相繼出現(xiàn)。越來越多的學(xué)者將它們應(yīng)用于無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究中，而螞蟻尋找食物的行為與網(wǎng)絡(luò)中節(jié)點尋找路由的過程十分相似，因此基于蟻群算法的傳感器網(wǎng)路由協(xié)議得到了大量的關(guān)注。 課題國內(nèi)外研究的意義 蟻群算法是一種仿生智能算法，它從現(xiàn)實生活中螞蟻尋食的過程得到啟發(fā)，采用概率選擇機制控制路徑的走向，同時也加入了隨著時間的延長，信息素揮發(fā)的因子。眾多的研究證明，蟻群算法具有很強的發(fā)現(xiàn)較好解的能力，該算法不僅利用了正反饋原理，在一定程度上加快了進化過程，而且在本質(zhì)上也可并行實現(xiàn)，不同個體之間 通過不斷的信息交流和傳遞，能夠相互協(xié)作，有利于發(fā)現(xiàn)較好解。蟻群算法可以理解為一種特殊的強化學(xué)習(xí)算法。 國內(nèi)蟻群算法應(yīng)用現(xiàn)狀 隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，蟻群算法在離散求解空間問題中表現(xiàn)出良好的搜索效果。蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應(yīng)用到其它組合優(yōu)化問題中。比較典型的應(yīng)用研究包括： 網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。蟻群算法在電信路哈爾濱遠東理工學(xué)院學(xué)士學(xué)位論文 2 由優(yōu)化中已取得了一定的應(yīng)用成果。 HP 公司和英國電信公司設(shè)計了蟻群路由算法。在該算法中，每只螞蟻就像蟻群優(yōu)化算法中一樣 ,根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗與性能，動態(tài)更新路由表項。如果一只螞蟻因為經(jīng)過了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對該表項做較大的增強。同時根據(jù)信息素揮發(fā)機制實現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當(dāng)前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時， ACR 算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、負荷量和利用率。目前這方面的應(yīng)用研究仍在升溫，因為通信網(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機動態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與 ACO 的算法本質(zhì)和特性非常相似。 ACO 還在許 多經(jīng)典組合優(yōu)化問題中獲得了成功的應(yīng)用 , 如二次規(guī)劃問題 (QAP) 、機器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色 (Graph Coloring) 等問題。部分研究者將 ACO 用于了武器攻擊目標分配和優(yōu)化問題、車輛運行路徑規(guī)劃、區(qū)域性無線電頻率自動分配Bayesian works 的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問題。 Costa 和 Herz 還提出了一種 AS 在規(guī)劃問題方面的擴展應(yīng)用圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。 最近幾年來，隨著人類在無線通信技術(shù)、微傳感器技術(shù)、微機電技術(shù)等方面取得的進步，一種集成了 感知、通信能力的傳感器節(jié)點被發(fā)明出來。這種節(jié)點具有低成本、低功耗、多功能、體積小和短距離無線通信的特點，由這種節(jié)點構(gòu)成的網(wǎng)絡(luò)引起了人們越來越多的關(guān)注。這種傳感器節(jié)點集成了無線通信技術(shù)、傳感器技術(shù)、分布式信息處理技術(shù)和嵌入式計算機技術(shù)等功能。目前來說，無線傳感器網(wǎng)絡(luò)路由算法已經(jīng)成為國內(nèi)外學(xué)者的一個研究熱點。文耀鋒等針對傳感網(wǎng)絡(luò)中簇頭采用單跳通信時距離轉(zhuǎn)化為線性規(guī)劃問題，提出了一種基于粒子群優(yōu)化的有效能量空洞避免的無線傳感器路由算法。這些改進的路由算法在節(jié)省結(jié)點能源方面取得了很多進展，但缺少對路徑全局尋優(yōu)方面的 考慮，降低了 WSN 的整體吞吐量。 目前，在將蟻群算法應(yīng)用于無線傳感器網(wǎng)絡(luò)路由方面，提出了許多新的算法。有的文獻中提出了一種針對斯坦納樹的蟻群算法，該算法可被移植到 WSN 路由中。然而，并沒有針對 WSN 的特定需求做出相應(yīng)改變，而且沒有考慮對于 WSN 性能至關(guān)重要的能耗問題。 Zhang 等人在研究了三種不同的基于螞蟻的 WSN 算法，然而，作者僅僅關(guān)注信息素初始分布的建立，在系統(tǒng)啟動效率方面具有一定的優(yōu)勢。有的文獻通過在螞蟻算法的下一跳選擇公式中引入偏轉(zhuǎn)角的概念來優(yōu)化路徑并利用螞蟻算法的正反饋效應(yīng)來完成數(shù)據(jù)匯聚從而達到節(jié) 省能量的目的。但是，該算法要求每個節(jié)點都必須配備有定位設(shè)備如 GPS 系統(tǒng)，很大程度上限制了它的適用范圍。 國外蟻群算法研究現(xiàn)狀 20 世紀 40 年代到 50 年代期間，法國昆蟲學(xué)家 Grasse 在研究白蟻的生物群體行為時，首次提出了媒介質(zhì)網(wǎng) (stigmergy)的概念，來描述白蟻個體之間間接交流信息的特殊方式。媒介質(zhì)與其他的交流方式主要有兩點不同：首先，它是昆蟲間接感受周圍物質(zhì)世界的改變而釋放出來的物理的 (physical)、非符號化 (nonsymbolic)、非語言層次上的溝通媒介；其次，它只能被接觸到媒 介質(zhì)的昆蟲感知，也就是它具有局部被感知的特性。媒介質(zhì)的這種特性在著名的雙橋?qū)嶒炛杏性敿毜难芯?，并成為激發(fā)計算機科學(xué)家提出螞蟻系統(tǒng)陽 (第一個 ACO 算法 )的直接源泉。 蟻群算法是有意大利學(xué)者 ， ， 等人在 20 世紀 90 年代初首先提出來的它是繼模擬退火算法、遺傳算法、禁忌搜索算法，人工神經(jīng)網(wǎng)絡(luò)算法后的有一種應(yīng)用于組合優(yōu)化問題的啟發(fā)式搜索算法。生物界的昆蟲和其他群居動物的群體智能 (swarm intelligence) 行為一直是科學(xué)家進行科學(xué)研究的靈感源泉。 1979 年，R． Hofstadter 首次提出了人工螞蟻的概念，探討了具有較低智能的簡單個體間能否通過相互作用而產(chǎn)生較高的群體智能行為 .從此，蟻群的鏈式反應(yīng)行為 (autocatalytic behavior)哈爾濱遠東理工學(xué)院學(xué)士學(xué)位論文 3 或正反饋 (positive feedback)特性受到越來越多的關(guān)注。 ACO的思想是由在意大利米學(xué)者 等人于 1991 年提出的。從 1991 年到 1996年， M Dorigo 等人就蟻群搜索食物的過程與旅行商問題 (TSP) 之間的相似性 , 通過人工螞蟻搜索食物的過程做了一定的研究，先后提出了三種模型： antquantity, antdensity和 antcycle。這三種模型的主要差別是在于對信息素濃度的變化采取不同的數(shù)學(xué)公式。直到 1996 年， M Dorigo 在發(fā)表了系統(tǒng)的關(guān)于螞蟻系統(tǒng) (AS)的全面論述，總結(jié)了這三種模型。在這篇論文中 M Dorigo 引入了 antcode 模型，并針對 TSP 問題做了一系列實驗，和其他只能算法做了比較，闡明了 AS 的強壯性 (robust)，多適應(yīng)性 (versatile)和基于群體性 (populationbased)。 2020 年， P． Deepalakshmill 提出了 ARMAN 算法，在原有蟻群算法數(shù)學(xué)模型上，加入了路徑選擇偏好概率，通過偏好概率選擇移動網(wǎng)絡(luò)中從源節(jié)點到目的節(jié)點的多重路徑，最終得到的路徑時延更小、帶寬更高、抖動更少。 蟻群優(yōu)化 (ACO)是由意大利學(xué)者 M． Dorigo 等人作為求解著名旅行商問題 (TSP)的啟發(fā)式算法而提出的，它是模擬自然界中螞蟻搜索食物行為而提出的一種啟發(fā)式智能進化算法。由于蟻群優(yōu)化算法具有正反饋性、分布式并行計算機制、較強的魯棒性等特點 ，可用于求解基于分布式網(wǎng)絡(luò)的最優(yōu)路徑計算，如路由、負載平衡和計算機網(wǎng)絡(luò)中的多路傳輸?shù)确矫妗?Laura Rosati 等人在 2020 年提出 DAR(Distributed Ant Routing)協(xié)議，它是一種按需的路由協(xié)議，相對于主動式路由，它可以減少路由時的網(wǎng)絡(luò)負載。前向螞蟻只負責(zé)收集關(guān)于交叉節(jié)點的 ID 信息，它在使用概率公式計算選擇下一跳節(jié)點的概率時只使用信息素值作為參數(shù)。而后向螞蟻在返回過程途中只釋放常量值的信息素值。在 DAR中。每個路由節(jié)點中路由表都是隨機的：下一跳節(jié)點是依據(jù)概率值的大小進行選擇的。這個概率值是通過以前螞蟻走過時留下的信息素進行計算的。但是 DAR 算法要讓螞蟻記錄經(jīng)過的節(jié)點，不適用于大型網(wǎng)絡(luò)，同時 也容易陷入局部最優(yōu)解，網(wǎng)絡(luò)的收斂速度也不快。 課題研究內(nèi)容 無線傳感器網(wǎng)絡(luò) (Wireless Sensor Network． WSN)是繼 Inter 之后隨著無線通信技術(shù)、傳感器技術(shù)、微電子技術(shù)和分布信息處理技術(shù)發(fā)展起來的一種新興信息獲取技術(shù)。WSN 綜合了嵌入式技術(shù)、傳感器技術(shù)、通信技術(shù)和分布式信息處理技術(shù)，能夠協(xié)作實時感知、監(jiān)測、采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境的信息，并對數(shù)據(jù)進行適當(dāng)?shù)奶幚硪垣@得精簡準確的信息，并傳送給最終的用戶。 在 WSN 中，每個傳感器結(jié)點的路由選擇過程和螞蟻的覓食尋優(yōu)行為具有極 大的相似性，因此，利用蟻群優(yōu)化來設(shè)計 WSN 的路由算法具有理論上的可行性?；诖耍覀儼褌鞲衅鹘Y(jié)點模擬成螞蟻，把傳感器的路徑選擇模擬成螞蟻的覓食路徑選擇路徑的啟發(fā)式信息模擬成螞蟻在路徑上釋放的信息素，提出了一種基于蟻群優(yōu)化的路由算法。 蟻群算法是一種來自大自然的隨機搜索尋優(yōu)方法，是生物界的群體啟發(fā)式行為，現(xiàn)己陸續(xù)應(yīng)用到組合優(yōu)化、人工智能、通訊等多個領(lǐng)域。蟻群算法的正反饋性和協(xié)同性使其可用于分布式系統(tǒng)，隱含的并行性更使之具有極強的發(fā)展?jié)摿Α臄?shù)值仿真結(jié)果來看，它比目前風(fēng)行一時的遺傳算法、模擬退火算法等有更好的適 應(yīng)性。但是蟻群算法畢竟是一種新興的模擬進化算法，還缺乏堅實的數(shù)學(xué)理論基礎(chǔ)，算法的參數(shù)選擇、收斂性等還有待進一步研究，算法的最優(yōu)停止條件也是值得研究的地方。 目前，關(guān)于算法的參數(shù)選擇大都與具體問題的應(yīng)用結(jié)合，通過實驗進行確定，而算法的停止條件則采用固定循環(huán)次數(shù)或當(dāng)進化不明顯時停止迭代作為條件。本文探討了蟻群算法的原理、特點及功能；對基本蟻群算法的有關(guān)參數(shù)的合理選擇進行實驗分析；提出了相應(yīng)的改進策略，并通過仿真實驗，驗證了改進算法的有效性，提高了尋求最優(yōu)路哈爾濱遠東理工學(xué)院學(xué)士學(xué)位論文 4 徑能力；分析了基于蟻群算法的網(wǎng)絡(luò)路由優(yōu)化。 采用該算法并 把該算法應(yīng)用于 zigbee 無線網(wǎng)絡(luò)中，平衡了 zigbee 網(wǎng)絡(luò)的缺點可以提高網(wǎng)絡(luò)的確定性服務(wù)質(zhì)量，提高網(wǎng)絡(luò)路由節(jié)點的平均壽命，尋求網(wǎng)絡(luò)中任一倆個節(jié)點的最優(yōu)路徑，提高數(shù)據(jù)包成功發(fā)送速度，同時平衡網(wǎng)絡(luò)帶寬、時延節(jié)省費用，并對他們進行限制，保證在網(wǎng)絡(luò)出現(xiàn)過載擁堵情況時，重要數(shù)據(jù)不受延遲或丟棄。蟻群算法顯示出它在無線傳感器網(wǎng)絡(luò)路由方面的優(yōu)勢。所以利用蟻群優(yōu)化的特點和優(yōu)勢提出了一種基于蟻群優(yōu)化的 zigbee 路由算法，根據(jù) zigbee 路由策略和蟻群優(yōu)化的特點，構(gòu)造了人工螞蟻使算法具有較好的節(jié)能性和全局尋優(yōu)能力，并改善網(wǎng)絡(luò) 的性能。提出自己的思路和做法，達到網(wǎng)絡(luò)優(yōu)化的目的。 本章小結(jié) 采用在無線傳感網(wǎng)絡(luò)路由方面顯示出獨特優(yōu)勢的蟻群優(yōu)化 zigbee 路由算法，可以提高網(wǎng)絡(luò)服務(wù)質(zhì)量，延長壽命，節(jié)省費用。因此基于蟻群算法的傳感器網(wǎng)路由協(xié)議得到了國內(nèi)外學(xué)者的大量的關(guān)注。由于利用了正反饋原理，協(xié)同性以及隱含的并行性更使之具有極強的發(fā)展?jié)摿?，并且可以理解為一種特殊的強化學(xué)習(xí)算法。根據(jù) zigbee 路由策略和蟻群優(yōu)化的特點，構(gòu)造了傳感器結(jié)點使算法具有較好的節(jié)能性和全局尋優(yōu)能力，并改善網(wǎng)絡(luò)的性能，達到網(wǎng)絡(luò)優(yōu)化的目的。 哈爾濱遠東理工學(xué)院學(xué)士學(xué)位論文 5 第 2 章 無線網(wǎng)絡(luò)蟻群 算法路由技術(shù) 生物界的昆蟲和其他群居動物的群體智能，行為一直是科學(xué)家進行科學(xué)研究的靈感源泉，隨著各學(xué)科門類的交叉綜合，群體智能已經(jīng)成為解決計算問題的新興的方法。 1979年， Dougls R． Hofstadter 首次提出了人工螞蟻的概念，探討了具有較低智能的簡單個體間能否通過相互作用而產(chǎn)生較高的群體智能行為。從此，正反饋特性受到越來越多的關(guān)注。 蟻群算法簡介 蟻群算法基本概念 蟻群算法是一種基于蟻群系統(tǒng)原理的、具有自組織能力的、新型的啟發(fā)式優(yōu)化算法。蟻群系統(tǒng)基本原理，人工蟻群系統(tǒng) (通常簡稱 蟻群系統(tǒng) )用于通過信息素痕跡和啟發(fā)信息的指引來構(gòu)造解。人工蟻群是受到真實螞蟻覓食行為的啟示而提出的，這個行為使螞蟻可以在食物源和蟻巢之間找到最短路徑。最初，螞蟻以隨機的方式探索蟻巢周圍的區(qū)域，一旦一只螞蟻找到食物源，它會評估食物的數(shù)量和質(zhì)量，并搬運一些食物回到蟻巢。在回程中，螞蟻在地面上留下一種被成為信息素的揮發(fā)性分泌物，留下的信息素數(shù)量取決于食物的數(shù)量和質(zhì)量。 圖 21 蟻群覓食源點到結(jié)點的路徑選擇 對于一條路徑，選擇它的螞蟻越多，則在該路徑上螞蟻所留下的信息素的強度就越大，而強度大的信息素會吸引更 多的螞蟻，從而形成一種正反饋。通過這種正反饋，螞蟻最終可以發(fā)現(xiàn)最短路徑。在 ACO 算法中，信息素軌跡通過一個被稱為信息素模型的參數(shù)化概率模型模擬。信息素模型由一系列模型參數(shù)組成，這里的模型參數(shù)值被稱為信息素值。 如圖所示 , 螞蟻從 A 點 (蟻巢 ) 出發(fā) , 速度相同 , 目的地在 D 點 (食物 ) , 可能隨機選擇路線 ABD 或 ACD。假設(shè)初始時每條分配路線一只螞蟻 , 每個時間單位行走一步 , 圖中上圖為經(jīng)過 9 個時間單位時的情形：走 ABD 的螞蟻到達終點，而走 ACD 的螞蟻剛好走到 C 點，為一半路程。圖中下圖為經(jīng)過 18 個時間單 位時的情形：走 ABD 的螞蟻到達終點后得到食物又返回了起點 A，而走 ACD 的螞蟻剛好走到 D 點。假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過 36 個時間單位后 , 所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從 D 點取得了食物，此時 ABD 的路線往返了 2 趟，每一處的信息素為4 個單位，而 ACD 的路線往返了一趟 , 每一處的信息素為 2 個單位，其比值為 2:1。 尋找食物的過程繼續(xù)進行，則按信息素的指導(dǎo)，蟻群在 ABD 路線上增派一只螞蟻 (共 2只 )，而 ACD 路線上仍然為一只螞蟻 . 再經(jīng)過 36 個時間單位后 , 兩條線路上的信息素單位 積累為 12 和 4，比值為 3B1。若按以上規(guī)則繼續(xù)，蟻群在 ABD 路線上再