基于蟻群優化的zigbee路由算法研究畢業論文(編輯修改稿)

　

【文章內容簡介】 2) 信息素蒸發，為了避免統治地位路徑的產生而使某些節點的能量消耗過快，網絡中所有單跳路徑的信息素濃度按式增加；(3) 進行周期性蒸發，以減小過去的信息素的影響，促進新路徑的使用。網絡中的各節點實時檢測自己的剩余能量，并將剩余能量通知鄰居節點。我們采用閾值觸發方式啟動能量通知過程，即當能量降低超過一定量，或降低到一定值時，啟動通知機制通知鄰居節點。具體的通知機制類似于網絡初始化時的做法：欲發出能量通知的節點以一個一跳的消息，將它的剩余能量發給鄰居節點，各鄰居節點根據收到的能量值更新本地路由表中該節點對應的剩余能量值，從而降低該節點被選中的概率，減少該節點的能量消耗。通過這種方式，能較好地達到均衡使用能量的效果。 基于蟻群算法的Zigbee路由研究與改進蟻群算法是最新發展的一種模擬昆蟲王國中螞蟻群體智能行為的仿生優化算法。它具有較強的魯棒性，優良的分布計算機制，易于與其他方法相結合等優點，其思想來源于自然界中蟻群尋找食物過程的觀察。在覓食過程中,螞蟻在它所經過的路徑上會釋放出與路徑長度有關的信息素, 路徑越長，釋放的信息量越小。后來的螞蟻能感知信息素的存在及其濃度，以此指導自己的運動方向，并傾向于朝著信息素濃度高的方向移動。于是，螞蟻的集體行為便表現出一種信息正反饋傾向。 蟻群算法中信息素的更新原則當信息包在路徑上傳輸時，信息素的值會發生變化。如有信息包經過，路徑上信息素的值就會增加，而沒有信息包經過的路徑的信息素會揮發。的值由式(24)進行更新。 (28)其中：是信息素揮發因子；為在鏈路上增加的信息素值，Q為常數，表示剩余能量，為初始能量。剩余能量越低，則增加的信息素就越少，選擇此路徑的可能性就會降低，從而達到繞開節點能量低的節點，使得網絡中節點能量消耗均衡。是信息素保持率，而表示衰減率。參數p始終小于1的意義在于，每一個周期后，所有邊上的信息素必須衰減，不能無限制積累，這樣可義在于，每一個周期后，所有邊上的信息素必須衰減，不能無限制積累，這樣可以讓系統“遺忘比較差的路徑，增加后繼搜索的發散性。顯然衰減是以指數級速度進行的。 本章小結本章詳細描述了第一個ACO算法一螞蟻系統的現實原理和算法模型及描述，螞蟻系統為闡明ACO元啟發式算法的基本思想做了最好的解釋。有了螞蟻系統的基本原理做鋪墊，融合元啟發式算法的特點，就可以提出ACO的元啟發式框架，通過對組合優化問題的算法關聯定義，ACO元啟發式就順其自然的有了基本的構件組成和運行模式。在這個框架下，螞蟻系統是作為算法的一個實例，并可以衍生出其他算法，盡管其他衍生算法是單獨提出，但是ACO元啟發式框架是對它們的最好概括。接著講述了幾種典型的ACO算法變種，這些都比原始的蟻群系統的性能有了大幅度提升。第3章 無線網絡蟻群優化算法路由技術蟻群優化ACO算法是一門發展中的學科的一個組成部分。 蟻群優化算法基本原理 蟻群優化算法基本概念蟻群優化算法是Marco Dorigo等學者受螞蟻覓食行為啟發提出的一種啟發式算法。在覓食路徑選擇時，起初由于每只螞蟻僅知道局部信息，無法找到從巢穴到食源的最短路徑，但是螞蟻通過在覓食路徑釋放信息素，間接地完成了與其他螞蟻的路徑信息交換，最終整個蟻群獲得了全局最優路徑(全局優化結果)。蟻群優化(ACO)的啟發式搜索方法具有較好的分布性和自適應性，可以根據要優化對象的特點改變優化策略。還可以通過多條備選路徑均衡了各節點的能耗，盡可能地延長節點生命期，該算法在螞蟻數據包結構、概率選擇公式及信息素更新公式等方面做了改進。該算法將延長網絡壽命，提高能量有效性。在計算機上實現以上模型時，一般有兩種方法：第一種是通過定義差分方程或微分方程來逐步計算構建解，這樣可以得到系統的期望行為，如蒙特卡洛方法，這樣定義的模型比較有數學依據，嚴謹而又有實際意義，然而對這樣的方程計算有時也會帶來計算量大的問題；另一種是模擬再現螞蟻群體，即設計一種人工螞蟻(artifical ant)來模擬真實螞蟻，其通過一個分布式學習過程來自適應地獨立并行地構建解，然后通過對(部分)解進行評估，來修改信息素濃度(信息素的釋放和蒸發)，以此對以后搜索過程實施一定的導相似)作用。為提高算法的性能，可以在一次迭代之后進行后臺處理，進行局部優化和全局信息收集等集中行動。模擬仿真方法啟發我們設計一種人工螞蟻用相似的思路去解決優化問題。 蟻群優化算法數學模型基本的蟻群優化算法，設是一個連通的無向圖，V是圖G中頂點的集合，E是邊的集合。；令表示邊上的信息素濃度，表示上預知的局部啟發值。局部啟發值可以是任何形式的代價，如距離、費用等。在頂點Vi的螞蟻使用信息濃度和局部啟發值來計算選擇下一個相鄰頂點,的概率: (31)其中，v是頂點的所有相距一步的相鄰頂點集合；和β分別表示和的可調權重；t表示時刻。因此，螞蟻的路由傾向可以通過選擇不同的和β值進行調整。如果，使螞蟻偏愛具有高信息素濃度的路徑；反之則使螞蟻選擇具有更大優化啟發值的路徑。當螞蟻從經過到時，上的信息素濃度如下進行修改： (32)其中 是螞蟻施放的信息素量。上的信息素濃度隨著時間的推移遵循下式被逐漸蒸發： (33)這里，執行一次蒸發的時間間隔為，P是蒸發系數。 該算法利用蟻群的動態適應性和尋優能力在網絡最短路徑和能量均衡消耗之間進行平衡，以達到網絡能量的優化均衡消耗，進而延長整個網絡的壽命。 蟻群優化算法的值與點的收斂一個算法首先要考慮的典型問題是收斂性問題(Convergence problem)，也就是算法能否在給定足夠資源的情況下找到最優解。因為ACO是一個隨機搜索過程，加上信息素更新的不確定性，也許會使算法永遠無法找到最優解。對于一個隨機優化算法，有兩種收斂類型：值收斂(convergence in value)和解收斂(convergence in solution)。因為問題的最優解一般都不止一個，那么收斂性研究的目的就是要證明算法能否收斂到某個最優值。值收斂，就是指算法至少有一次機會生成～個最優解。而解收斂研究的是，算法能否達到持續地生成某一相同最優解的狀態。研究收斂性一般遵從從易到難原則。證明ACO算法的特殊子集的收斂性是個不錯的入門方法。對于隨機優化算法而言，解收斂的強度比值收斂強，但是通常只需要證明算法能夠找到最優解，因此真正需要研究的是值收斂問題。對于理論研究結果，由特殊子集算法擴展到普通ACO算法是可行的。 蟻群優化算法在路由中的應用ZigBee是一種全新的低復雜度、低成本和低功耗的雙向無線通信技術。完整的協議棧只有32 KB。且可以嵌入到各種電子信息設備中。由于無線傳感器網絡本身要求的技術特點，所以ZigBee技術作為無線傳感器節點的無線通訊是切實可行的。我們通過應用ZigBee技術來構建無線傳感器網絡。由于無線傳感器網絡具有結點計算能力弱、結點電能(電池提供的)有限等特點，在設計無線傳感器網絡路由算法時，必須考慮算法的節能性和簡單性。蟻群優化作為一個啟發搜索算法，具有分布性好、全局尋優能力強、算法簡單易實現等優點。目前，針對ZigBee網絡自身的特點和用途設計能量有效的路由算法已成為ZigBee網絡研究的一個重要課題。由于ZigBee網絡中節點的能量資源、計算能力和帶寬都非常有限，且ZigBee節點一般由電池供電，ZigBee網絡的壽命嚴重依賴節點電池能量的有效利用，因此節點電池能量的有效利用從而延長網絡壽命在ZigBee網絡中是至關重要的。無線傳感器網絡由眾多具有感知、通信和計算能力的傳感器節點，以無線方式連接而成，在軍事、災難救援、環境監測、醫療健康、家庭監護以及其他眾多領域有著廣泛的應用前景。由于無線傳感器網絡節點能量有限且一般沒有能量補充，所以網絡節點能量消耗的快慢就成了影響無線傳感器網絡壽命長短的決定性因素。很多路由協議選擇能量消耗小的數據傳輸路徑，相應的路由算法往往只優化一個參數——跳數，使數據沿最短路徑傳輸。但如果頻繁使用同一條路徑傳輸數據，就會使這些路徑上的節點因能量消耗過快而過早罷工，導致網絡分裂甚至死亡，從而嚴重縮短網絡壽命；而此時網絡中其他節點可能還有很多剩余能量。因此，如何高效使用無線傳感器網絡有限的能量來最大化網絡壽命成為無線傳感器網絡及其路由設計的首要目標和面臨的首要挑戰。 蟻群算法中參數的最優選擇蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優良的性質。本文介紹了蟻群算法基本模型AS的原理、特點、構成和實現方法，對基本蟻群算法參數的合理選取進行了實驗分析，給出了算法參數選取的基本原則，有利于蟻群算法在優化問題中的推廣和應用。關于蟻群算法中信息素揮發度對算法性能的影響及其在實際應用中的選擇，可以通過計算機仿真實驗來分析和確定。對此，本文取如下的TSP問題及算法參數進行仿真比較距離矩陣如下表所示：表31 信息素殘留系數對算法性能影響殘留系數最優路徑長度搜索循環次數172644115165567 蟻群信息素揮發度的選擇在蟻群算法中，人工螞蟻是具有人類記憶功能的，隨著時間的推移, 以前留下的信息將要逐漸消逝。在算法模型中用參數表示信息消逝程度(或稱信息素揮發度) ，而就是信息素殘留系數。圖31 信息素殘留系數與最優解搜索循環次數的關系圖32 信息素殘留系數與算法穩定性的關系由仿真實驗結果不難看出, 在其它參數相同的情況下, 信息素揮發度的大小對蟻群算法的收斂性能影響極大, 特別是當很小時, 由于路徑上的殘留信息占主導地位, 信息正反饋的作用相對較弱, 搜索的隨機性增強, 因而蟻群算法收斂速度很慢；而在比較大時, 由于信息正反饋的作用占主導地位, 搜索的隨機性減弱, 雖然算法收斂速度加快, 但易于陷入局部最優狀態。因而, 關于蟻群算法中信息素揮發度的選擇, 必須綜合考慮算法的全局搜索能力和收斂速度兩項性能指標, 針對具體問題的應用條件和實際要求, 在全局搜索能力和收斂速度兩方面作出合理或折中的選擇。由圖可見, 在= 0. 5~ 0. 7 范圍內, 算法的性能比較穩定和一致, 搜索的全局性和收斂速度都比較好。 所以本文認為, 在蟻群算法中信息素揮發度的選擇宜取為 (即= 0. 7) 。 蟻群數量的選擇蟻群算法是一種隨機搜索算法, 與其它模擬進化算法一樣，通過多個候選解(可行解的一個子集)組成的群體的進化過程來尋求最優解，在該過程中既需要每個個體的自適應能力, 更需要群體的相互協作。 蟻群在搜索過程中之所以表現出復雜而有序的行為, 個體之間的信息交流與相互協作起著至關重要的作用。關于蟻群算法中螞蟻數量m對算法性能的影響及其在實際應用中的選擇, 也可以通過計算機仿真實驗來分析和確定。以上文所列TSP 問題為研究對象, 有關算法參數取為：螞蟻循環一周所釋放的總信息量Q = 1, 信息素殘留常數, 信息啟發式因子, 期望啟發式因子，運算的停止條件為相鄰兩次循環搜索中最優解的差別小于0. 001, 并使螞蟻數量的變化為m={ 2, 3, 4,5, 6, 7}。螞蟻數量對算法性能影響的仿真結果如下圖33所示：由仿真實驗結果不難看出，螞蟻數量m 的大小對蟻群算法循環次數(收斂性能)的影響基本呈線性規律變化，當螞蟻數量過大(如接近問題的規模)時，雖然搜索的穩定性和全局性得到提高，但算法的收斂速度減慢。關于蟻群算法中螞蟻數量m的選擇，也應該綜合考慮算法的全局搜索能力和收斂速度兩項指標，針對具體問題的應用條件和實際要求，在全局搜索能力和收斂速度兩方面作出合理或折中的選擇。圖33 螞蟻數量m與最優解搜索循環次數的關系圖34 螞蟻數量m與算法穩定性的關系 啟發因子的選擇期望值啟發式因子的大小反映了蟻群在路徑搜索中先驗性、確定性因素作用的強度，其值越大，螞蟻在某個局部點上選擇局部最短路徑的可能性越大，雖然搜索的收斂速度得以加快, 但蟻群在最優路徑的搜索過程中隨機性減弱，易于陷入局部最優；而信息啟發式因子的大小則反映了蟻群在路徑搜索中隨機性因素作用的強度, 其值越大, 螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機性減弱，當值過大也會使蟻群的搜索過早陷于局部最優。蟻群算法的全局尋優性能，首先要求蟻群的搜索過程必須有很強的隨機性；而蟻群算法的快速收斂性能, 又要求蟻群的搜索過程必須要有較高的確定性。 因此, 兩者對蟻群算法性能的影響和作用是相互配合、密切相關的。關于蟻群算法中啟發式因子及對算法性能的影響及其在實際應用中的選擇, 也可以通過計算機仿真實驗來分析和確定。以上文所列TSP問題為研究對象, 有關算法參數取為：螞蟻循環一周所釋放的總信息量Q = 1, 信息素殘留常數，螞蟻群體數m = 4, 運算的停止條件為相鄰兩次循環搜索中最優解的差別小于0. 001, 取啟發式因子不同數值的組合。啟發式因子和對算法性能影響的仿真結果如下表所示：表32 總信息量對算法性能影響因子α因子β最優路徑長度搜索循環次數 194 759654從仿真實驗結果不難看出，蟻群算法中啟發式因子及的不同選取對算法性能有極大的影響好的搜索結果：適當的選擇??及??的取值范圍，此時即便參數的組合有所不同(如在本文的問題中,取1. 5 左右, 取0. 5 ~ 5)，蟻群算法均能獲得較好的搜索結果, 算法的循環次數少( 即收斂速度快)，并且性能非常接近。 總信息量的選擇在模型ant cycle中，總信息量Q為螞蟻循環一周時釋放在所經過的路徑上的信息素總量. 一般的理解是：總信息量Q越大, 則在螞蟻已經走過的路徑上信息素的累積加快, 可以加強蟻群搜索時的正反饋性能, 有助于算法的快速收斂。由于在蟻群算法中各個算法參數的作用實際上是緊密耦合的, 其中對算法性能起著主要作用的應該是信息啟發式因子、期望啟發式因子和信息殘留常數等3個參數. 總信息量Q對算法性能的影響則有賴于上述三個參數的配置, 以