學士學位論文基于蟻群優化的zigbee路由算法研究-資料下載頁

　　

【正文】 數據包轉發給節點，同時增加表項信息素值，通向目的路徑將因為傳送數據包而被加強。 路由維護由于自組網節點的移動性，網絡拓撲結構發生改變，因而路由要連通必須進行路由維護。其思想是每個節點周期性地向鄰節點廣播Hello報文。如果在給定時間t后，鄰節點還沒有收到確認連接的Hello報文，則認為該節點已經與自己斷開連接，將自己路由表中所有以該節點為下一條節點的路由都設為失效狀態。AODV路由協議允許進行本地鏈路修復，失效前一跳節點將啟動路由發現過程，廣播RREQ以便建立新路由。如果在給定時問里能重新建立起有效路由，就接著發送數據；如果建立路由不成功，則向上游節點發送RERR。路由失敗后先進行本地鏈路修復可以減少數據傳送的延時，提高數據包的發送率。 蟻群路由實現與結果仿真具體的仿真條件設為：在160m x 160m的正方形區域內隨機散布200個節點；1個數據源節點位于(0，0)；1個目的節點位于(160，160)；節點的通信距離是40m。假設節點的發送能耗660mw ，接收能耗395mw；所有節點的初始能量均相同，為1 000(J為能量單位)。目的節點要求數據源以2幀/s的速度發送數據．為了簡化并加快能量的消耗，設網絡中傳輸的所有數據幀(包括探測螞蟻)大小均相同，為64K字節；。算法中，網絡中的信息素每每秒蒸發一次,節點能量每減少5J，啟動一次剩余能量通知機制。對路徑最優仿真，取；對能量均衡最優仿真，取．我們分別對這兩種情況進行比。即以第一個節點因能量耗盡(取低于10J)而死亡的時間為網絡壽命。 圖42 路徑最優情況下能量消耗（T=1000s）圖43 能量均衡情況下能量消耗（T=1000s）上兩個圖分別是在路徑最優和能量均衡最優兩種情況下，仿真運行1000s時的網絡能量消耗分布。從圖43中，我們發現最短路徑上的節點能量消耗很大。這是由于最短路徑上的節點被頻繁使用的原因。而不在最短路徑上的節點幾乎沒有消耗， 6J。這是初始階段螞蟻擴散的時候產生的。最大最小能耗相差670J以上。從圖3中，我們發現能量消耗非常均勻， 4J， 6J，最大最小能耗相差只有1J左右。這是因為能量均衡優化時，路由選擇剩余能量多的節點，從而實現能量的均衡消耗。我們也看到能量均衡最優情況下的平均能耗大于路徑最優的情況。這是因為在能量均衡最優情況下，傳輸數據使用較遠路徑，增加轉發次數，從而增加能量消耗。圖44 路徑最優情況下能量分布圖45 能量均衡最優情況下剩余能量分布，實驗中使用的AODV和DSR協議是NS內置的。在網絡場景設置中，我嗯設定了20個固定節點和50個移動節點。這些節點之間通過IEEE ，場景中有3個服務節點，而客戶端節點的數量會隨機改變，每個客戶節點以通過改變包的大小以形成網絡擁塞的場景。通過吞吐量、平均延遲、傳送率三個指標來比較蟻群優化路由算法與AODV和DSR算法的性能。 圖46 三種路由協議的吞吐量比較從圖中可明顯看出，DSR算法的吞吐量曲線置于最下方，不僅較低，且隨著網絡負載的增加幾乎沒有變化；AODV算法的吞吐量曲線居中，隨著網絡負載的增加吞吐量有所增加，但增長緩慢；而AntRouting吞吐量曲線置于最上方，不僅較高，且隨著網絡負載的增加吞吐量增長很快。三種算法當網絡負載超過240 kbps以后，吞吐量呈衰減趨勢。圖47 三種路由協議的平均延遲比較當網絡負載較低的時候，AODV協議和Ant Routing算法平均時延較短，而DSR時延比較長。而隨著網絡負載的增加，DSR的平均延遲越來越大，但是AODV和AntRouting算法則變化不大。當網絡負載較小時，AODV和Ant Routing算法能傳送超過90％的數據包。而隨著網絡負載的不斷增加，三種路由算法都表現了不同程度的傳送率性能下降，相對來說，DSR下降速度最快，AODV其次，Ant Routing算法要好一些。因此，通過吞吐量、平均延遲、傳送率三個指標進行比較，隨著網絡負載的增加，蟻群路由算法相比AODV和DSR有比較明顯的優勢。圖48 三種路由協議的數據包的傳送率比較 本章小結針對移動自組網提出了一種基于蟻群優化的路由算法，該算法很好地利用了蟻群算法的自適應性，能有效地承載移動自組網的負載。在NS2平臺下的算法仿真表明，該算法在移動自組網環境下表現了較好的性能，從吞吐量、平均延遲、傳送率三個指標比較來看，比AODV和DSR的性能都要好。蟻群優化方法的自組織、動態和多路徑的特性使其特別適合應用于無線傳感器網絡的路由．本文提出的基于蟻群優化的能量均衡路由算法具有路由代價低、自適應性好、支持多路徑和支持休眠模式等特點．仿真分析表明，該算法能有效實現節點能量的均衡消耗，采用能量均衡優化與路徑優化相比能顯著延長網絡壽命．該算法能夠通過調整信息素濃度和局部啟發值的權重，在路徑和能量均衡方面進行綜合優化，以滿足各種不同應用的需要。第5章 課題研究中的難點及解決方法本章主要是對過去幾個月中的制作論文過程的總結，蟻群算法有演變成蟻群優化算法，甚至魚群算法，有它需要解決的難題。而本文主要是研究蟻群優化算法在無線網絡中的應用，基于無線網絡的不確定性，能耗低性，數據延遲性，我主要做出一下幾點。 有關螞蟻構建過程與難點分析每只螞蟻都關聯一個叫做禁忌表(tabu list)的數據結構，可記為，用于存儲到目前為止螞蟻已經訪問過的結點編號，這樣可以防止螞蟻在一次環游中走重復的結點。這樣，禁忌表記錄了螞蟻的路徑痕跡，在一次環游結束時，禁忌表可用來計算出這只螞蟻的當前解以及和解相關的估價信息(例如這條路徑的權值)。進入下一個周期前，禁忌表又被清空，螞蟻進入下一輪搜尋。從數據結構觀點來看，是一個動態增長的向量，在路徑構建過程中動態增長，而表示螞蟻k的禁忌表的第S個元素，例如螞蟻k后在當前環游中的第S個經過的結點。禁忌表通常用來定義提到過的鄰域結構，它們之間的關系是： (51)在螞蟻構建解過程中，除了要考慮螞蟻釋放信息素對于構建的影響，還要考慮問題本身也就是圖的結構，盡可能的把圖結構本身信息加入到構建因素中，實現了貪心式啟發信息和螞蟻群體智能的統一。因此，可以定義邊可視性為邊的權值的倒數，這個值依賴于問題本身的性質，如在靜態TSP問題中，可視性是個常量。如何有效使用無線傳感器節點有限的能量來最大化網絡的壽命是無線傳感器網絡研究的重要問題及解決方法如下：網絡能量是否均衡消耗對網絡壽命有著決定性的影響。針對無線傳感器網絡中節點能量受限的特點，把蟻群優化算法應用于無線傳感器網絡，考慮通信路徑長度和節點剩余能量等因素，提出具有能量意識，從多方面解決節點間的能耗不均衡問題。該算法在能耗不均衡和傳輸延遲等方面將有很大改進，實現全網節點的能耗均衡，將有效延長網絡生命期，減小傳輸時延。蟻群算法道路最優規劃問題：螞蟻更傾向于走寬敞順暢的大道，有的路徑雖然短，但可能崎嶇不平、道路狹窄，因而需要較長時間通過，全面考慮這些因素怎樣規劃出不僅路徑短而且省時的最優路徑？針對這個問題要求對蟻群算法進行優化改進， 在蟻群算法中，人工螞蟻在運動過程中會根據各路徑上的信息素軌跡量決定下一步的轉移方向，采用如下公式進行選擇： (52)其中，表示人工螞蟻從轉移到節點的概率表示人工螞蟻下一步允許選擇的節點，禁忌表用來記錄人工螞蟻當前走過的點，隨進化過程作動態調整，表示邊上的信息素濃度，表示節點相對節點的可見度，表示節點到節點的距離，和是 信息素濃度和控制可見度的權衡。 改進的狀態轉移規則為： (53)表示道路的寬敞，暢通程度，是道路的寬敞，暢通度的權衡，其余參數同基本蟻群算法。它是將m只螞蟻定位于起點，向目標點靠攏，每個螞蟻使用改進后的狀態（即從一個節點到另一個節點），直到最后終達到目標，完成一條路徑導航。到節點 (54)其中是一個參數，1表示在時刻和+之間信息素消逝程度。，表示在時刻和之間第k只螞蟻在路徑上留下的信息素量，表示在時刻和之間路徑上信息素增量。當所有螞蟻完成各自路徑的選擇過程，必須對各邊上的信息素按公式作一次全局更新，此時為： (55)其中，F為目標函數，路徑越優，F值越小，該路徑上增加的信息素量就越多。蟻群算法中怎樣調和一味選取最近的結點而造成的易陷于局部最優解的問題？在蟻群算法系統中，當螞蟻從結點i選擇下一結點j，首先要比較禁忌表，然后再計算每個相鄰結點的轉移概率，這需要較長的計算時間。而根據ACO算法的原理，被選擇的結點通常為比較鄰近的結點，為了達到調和的目的，對于要計算轉移概率的結點，設為K個，按距離的遠近取最近的10個連續的和次近的10個連續的結點計算概率，兩者相隔的距離為K/5，如K20則取所有的相鄰結點來計算，例如距離從近到遠的結點為，，；則選擇計算的結點，和。這樣既可有效地減少結點計算的數量，提高計算的速度。 基于遺傳算法的Zigbee路由研究與改進遺傳算法是由美國的John Holland教授于1975年首先提出的一類仿生型優化算法，具有大范圍快速全局搜索能力。與自然界相似，遺傳算法對求解問題的本身一無所知。遺傳算法是從代表問題可能潛在解集的種群開始的，而種群則由經過基因編碼的一定數目的個體組成。每個個體實際上是染色體帶有特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現(即基因型)是某種基因組合，它決定了個體形狀的外部表現。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代(generation)演化產生出越來越好的近似解。在每一代進化過程中，根據問題域中個體適應度大小來挑選(selection)個體，借助于自然遺傳學的遺傳算子進行組合交叉(erossover)和變異(mutation)，產生出代表新解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼(decoding)，可以作為問題近似最優解，這就是遺傳算法基本思想。遺傳算法應用于Zigbee路由問題需要確定以下要素：(1) 編碼規則：需要針對具體的物理模型提出合適的編碼方法；(2) 創建初始群體：即確定路徑解集；(3) 確定遺傳算子：即確定選擇、交叉、變異的方法；(4) 確定適應度函數：即確定Zigbee路由是根據那些參數的優化并確定參數。將傳統遺傳算法直接應用于Zigbee路由選擇存在以下問題：(1) 傳統的編碼不能很好的反應實際物理模型；(2) 簡單的初始種群形成方法和交叉、變異操作容易產生非法路徑；(3) 通用的遺傳算法在解決Qos問題時具有單一約束上的困難。對于以上幾點現有的文獻已有很好的解決。但在已有的遺傳算法應用于Zigbee路由的文獻中，選擇，交叉，變異的過程都是采用按概率隨機選擇的方法，這種方法具有多樣性好和全局性好的優點，但針對具體的Zigbee路由問題具有以下缺點：(1) 每次迭代前需要遍歷所有父代個體，并計算每條染色體的概率，增加了算法復雜度；(2) 按概率隨機性選擇會存在統計誤差，導致一些本來優秀的染色體丟失。由于本算法僅需要保存最優的幾條路徑，對多樣性要求不高，針對Zigbee路由問題，解集多樣化固然重要，但減小Zigbee路由開銷和縮短Zigbee路由尋找時間才是最重要的，基于以上原因，本文擬對基本遺傳算法進行改進，提出一種確定性按比例遺傳算法，即按比例確定參與遺傳算子操作的個體。確定性選擇既保留了傳統遺傳算法可產生多樣化解集的優點，又能保證算法可以以最快速度收斂到最優，同時減小了算法的復雜度，具有易實施的優點。 課題的可行性評估蟻群算法憑借其簡單的算法結構和突出的問題求解能力, 以及靈活、穩定、分布式控制和自組織能力等特點，吸引了很多研究者, 并取得了令人注目的成果。該理論很適合于工程問題中日益復雜的信息處理需求，尤其是動態特性突出的問題。然而, 由于其理論依據來源于對生物群落社會性的模擬, 因此其相關數學分析還比較薄弱, 這就導致了現有研究還存在以下幾個主要問題：(1) 蟻群算法的數學理論基礎薄弱, 缺乏普遍意義的理論性分析。算法中涉及的參數設置沒有確切的理論依據, 一般按照經驗確定, 對具體問題的依賴性大；(2) 比較性研究不足, 與各種成熟的優化算法之間的基本特性及性能特點的對比研究還不是十分充分。將來的研究工作應加強算法特性的分析, 進一步明確與算法原理相關的重要意義。如：單個個體的復雜性、學習能力和推理能力等。還應擴展蟻群算法與其神經網絡、禁忌搜索和支持向量機等先進技術的融合, 以改善其自身的性能。作為一種新型的模擬進化算法, 蟻群算法研究時間較短, 不像其他啟發式算法那樣具有系統的分析方法和堅實的數學理論。揮發因子等參數的選擇基本是依靠實驗和經驗, 目前尚無通用及確定的理論方法來確定, 因此理論和實踐方面尚有許多問題需要更深入的研究與探討。 但是該算法的并行特性和強魯棒性等優點吸引著許多學者不斷對其進行深入研究。 隨著理論研究和實踐經驗的積累, 蟻群算法必將成為求解復雜組合優化問題的高效算法。Ad hoc網絡在未來幾年有著極其誘人的前景和潛在的巨大市場。國內外均有大量相關資料可供查閱，這些研究為迄今為止的Ad Hoc的Zigbee路由技術開發和系統設計提供了必要的參考依據和理論指導，也為本研究提供了豐富的基礎數據。現在，螞蟻算法和遺傳算法受到廣泛關注，作為一種新興的仿生學算法由于其良好的并行性對解決完全問題起到了良好的效果。并在車間作業調度問題，聚類分析、車輛路徑問題等方面取得了一系列成果。尤其螞蟻算法在網絡Zigbee路由問題方面的研究與本課題學科領域相近，可為本課題在方法論和技術路線上提供指導。迄今為止，課題研究人一直從事螞蟻算法，遺傳算法以及Ad Ho