精品文檔-下載后可編輯一種無線傳感器網絡路由算法基于蟻群算法

電系統（Micro-Electro-MechanismSystem,MEMS）、片上系統（SOC，SystemonChip）、無線通信和低功耗嵌入式技術的飛速發展，孕育出無線傳感器網絡（WirelessSensorNetworks,WSN），并以其低功耗、低成本、分布式和自組織的特點帶來了信息感知的一場變革。無線傳感器網絡就是由部署在監測區域內大量的廉價微型傳感器節點組成，通過無線通信方式形成的一個多跳自組織網絡。

隨著無線通信技術、電子技術、傳感器技術和微電系統的飛速發展，無線傳感器網絡的研究越來越受到人們的重視。傳感器網絡是由部署在觀測環境內的大量微型傳感器節點通過無線通信方式組成的一種無線網絡。組成傳感器網絡的節點包括傳感器和匯聚節點（Sink）。傳感器節點的能量十分有限，并且在部署后難以再次補充能量，因此傳感器網絡存在嚴重的能量約束問題。

參考文獻2提出一種無線傳感器網絡AODV（AdhocOn-DernandDistanceVector）路由協議改進方案，通過改進RREQ協議幀，使節點的剩余能量值參與到路徑中，優化RREQ洪泛傳播。但該算法是基于單路徑數據傳輸，沒有考慮節點的負載狀況，節點容易產生擁塞，導致數據包的重傳或數據丟失的情況。參考文獻3提出了一種基于蟻群優化的路由算法ARAWSN（ACO-BasedRoutingAlgorithmforWirelessSensorNetworks），該算法在定向擴散協議的基礎上，通過搜尋螞蟻以廣播的方式在網絡中擴散建立起源節點到目的節點的多條路徑的路由表。利用蟻群算法的轉移概率的方式來進行路徑的選擇，從而平衡網絡中節點能量的消耗。該算法建立了所有到目的節點的路徑，存在很大的冗余，影響網絡的實時性，且在路由建立過程中采用洪泛的方式導致網絡的路由開銷比較大。參考文獻4綜合考慮了均衡傳輸能量消耗和節點剩余能量，提出了多種群蟻群優化路由算法MACO（MultiAntColonyOptimization）。該算法優化了基本蟻群算法的螞蟻前向移動的選擇概率模型，同時利用多種群獲得多條優化路徑。但該算法需要進行多次迭代，且可能陷入局部解，影響網絡數據傳輸的實時性。

針對上述路由算法及其存在的不足，本文提出了基于蟻群算法的無線傳感器網絡按需多路節能路由算法MP-ACA（On-demandMulti-pathandPower-savingAntColonyAlgorithm）。該算法結合蟻群算法和AODV路由協議，能夠在源節點和目的節點之間建立起多條鏈路不相關路由，并改善了蟻群算法在無線傳感器網絡中查找路由的多次迭代的策略，有效地減少了擁塞頻率、降低了路由的開銷，同時均衡了節點的能量開銷，延長了網絡的生命周期。

1蟻群算法簡介

蟻群算法（antcolonyoptimization,ACO），又稱螞蟻算法，是一種用來在圖中尋找優化路徑的機率型算法。它由MarcoDorigo于1992年在他的博士論文中提出，其靈感于螞蟻在尋找食物過程中發現路徑的行為。蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優良的性質。針對PID控制器參數優化設計問題，將蟻群算法設計的結果與遺傳算法設計的結果進行了比較，數值仿真結果表明，蟻群算法具有一種新的模擬進化優化方法的有效性和應用價值。

1.1基本蟻群算法原理

蟻群算法ACA（AntColonyAlgorithm）是一種模擬昆蟲王國中螞蟻群體智能行為的仿生優化算法，其基本原理可大致描述如下：自然界螞蟻會在所經過的路徑上釋放一定的信息素，后來的螞蟻會根據信息素強度來選擇路徑，信息素強度越大的路徑被選擇的概率越大，于是就形成了一種正反饋機制，終螞蟻會選擇信息素的短路徑。蟻群算法通過釋放“人工螞蟻”來模擬自然螞蟻的行為以完成上述的選優過程。

1.2蟻群算法

根據螞蟻覓食的基本原理，科學家們設計了尋找路徑的蟻群算法，其主要步驟為：

2按需多路節能路由算法設計

針對無線傳感器網絡數據多跳傳輸、節點能量有限等特性，本文對基本蟻群算法和MACO算法進行改進，并結合AODV路由協議，賦予螞蟻新的特性和路徑搜索方式。下面介紹本文研究中使用的相關定義。

定義1：從源節點到目的節點的路徑搜索螞蟻稱作前向螞蟻，它執行路徑搜索功能，并建立反向信息素表。

定義2：前向螞蟻到達目的節點后，從目的節點返回到源節點的螞蟻稱作后向螞蟻，它執行信息素更新功能，并建立路由表。

定義3：前向螞蟻在路徑搜索過程中，到達某一節點后建立的指向源節點的路由表稱作反向信息素表，該表包括源節點、下一個節點、反向節點信息素τ（j，i）。

2.1算法設計思想

MP-ACA算法在Ant-Net算法的基礎上，將螞蟻分為前向螞蟻和后向螞蟻。為了實現不同節點的能量消耗均衡，MP-ACA算法中，將前向螞蟻要訪問的節點的剩余能量作為影響信息素濃度的一個參數。MP-ACA算法通過m只前向螞蟻同時獨立地進行路徑搜索，并建立反向信息素表。當每個前向螞蟻到達目的節點時，它們將立即轉化成一個后向螞蟻，后向螞蟻根據反向信息素表反向回到源節點后路由建立完畢，建立起信息素路由表以代替傳統的網絡節點路由表，并采用一種新的信息素規則進行信息素更新。同時MP-ACA算法在極大-極小蟻群算法上將各條路徑上的信息素濃度限制在[τmin，τmax]之間，τmin可以有效地避免算法停滯，τmax避免某條路徑上的信息素遠大于其他路徑，使所有的螞蟻都集中到同一條路徑上面，限制算法的擴散。在MP-ACA算法中，前向螞蟻轉移規則、信息素更新規則詳細設計如下。

2.2前向螞蟻轉移規則

為了均衡網絡中節點的能量消耗，MP-ACA算法在蟻群算法的基礎上，新加入兩節點間的剩余能量因子改進前向螞蟻轉移規則。改進后的算法在螞蟻尋找短路徑的同時受到了節點能量消耗的限制。MP-ACA算法中處于節點i的螞蟻k選擇下一節點j進行訪問的概率pkij使用以下公式確定：

式中，W（j）是節點j的剩余能量；JK（i）代表了位于節點i的前向螞蟻k允許訪問的鄰居節點集合。在這里定義滿足以下兩個要求的節點j將會屬于JK（i）：（1）節點j還未被螞蟻k訪問；（2）節點j比前一節點i距離目的節點更近，且距離源節點更遠。

MP-ACA算法采用改進的轉移規則，簡化了MACO算法使得MP-ACA更適用于無線傳感器網絡。同時前向螞蟻在尋找路徑的同時受到了節點能量消耗的限制，平衡了節點的能量消耗。

2.3蟻群算法的實現

下面的程序開始運行之后，螞蟻們開始從窩里出動了，尋找食物；他們會順著屏幕爬滿整個畫面，直到找到食物再返回窩。

其中，‘F’點表示食物，‘H’表示窩，白色塊表示障礙物，‘+’就是螞蟻了。

參數說明：

信息素：螞蟻在一開始擁有的信息素總量，越大表示程序在較長一段時間能夠存在信息素。信息素消減的速度：隨著時間的流逝，已經存在于世界上的信息素會消減，這個數值越大，那么消減的越快。

錯誤概率表示這個螞蟻不往信息素的區域走的概率，越大則表示這個螞蟻越有創新性。

速度半徑表示螞蟻能走的長度，也表示這個螞蟻的感知范圍。

記憶能力表示螞蟻能記住多少個剛剛走過點的坐標，這個值避免了螞蟻在本地打轉，停滯不前。而這個值越大那么整個系統運行速度就慢，越小則螞蟻越容易原地轉圈。

2.3信息素更新規則

如果節點i，j是前向螞蟻k選擇路徑上的相鄰節點，當每個前向螞蟻到達目的節點時，它們將通過式（5）、式（6）來調節。對前向螞蟻到達目的節點后立即轉化成一個后向螞蟻，并且它將沿著反向信息素表回到源節點。中間節點收到后向螞蟻時，將按照式（5）、式（7）更新相鄰節點信息素強度。

MP-ACA算法改進了MACO算法信息素更新規則，可以加快搜索路徑的速度，提高網絡數據傳輸的實時性，同時更進一步平衡了網絡節點的能量消耗。

2.4MP-ACA算法步驟

（1）初始化時，Sink節點跳數設置為0，其他節點跳數設置為100。Sink節點在全網范圍內廣播跳數廣播報文，該報文包括數據包類型、距Sink節點跳數、剩余能量和源地址。該報文初始值為：跳數為0，源地址為0。中間節點收到該報文后，保存報文中節點的地址、跳數和能量狀態。如果收到的報文中跳數小于節點自身的跳數，則將自身的跳數設置為報文中的跳數加1，并轉發自己新的跳數信息和能量信息的報文，否則不廣播。節點在轉發該報文的過程中收集、存儲鄰居節點相關信息，終在全網內建立了到Sink節點的跳數信息。

（2）路徑搜索初始時，賦予每條路徑上相等數量的初始信息素τ0，本文設置為信息素濃度下限τmin。

（3）路徑搜索開始時，m只前向螞蟻從源節點S處出發，前向螞蟻所要攜帶的信息有：源節點ID號、目的節點ID號、節點i到節點j的信息素強度τ（i，j）、經過節點的剩余能量的總和以及當前總跳數。

（4）位于節點i的前向螞蟻k，依據轉移規則從相鄰的下一跳節點集合中選擇一個節點，并根據式（5）、式（6）更新路徑上信息素強度。

（5）當中間節點j收到來自鄰居節點的螞蟻節點時：①更新前向螞蟻搜索包跳數h（i）=h（i）+1，i∈[1，m]。如果前向螞蟻沒有到達目的節點，且hhmax，則轉入下一步，否則丟棄該數據包；②檢查自己是否比節點i距離目的節點更近，且距離源節點更遠。若是，轉入下一步，否則簡單丟棄；③然后檢查是否已收到同一目的節點前向螞蟻搜索包。若是，則此節點只接收早到達而且信息素的前向螞蟻搜索包，將其余的丟棄。當前向螞蟻從節點i到達節點j后，根據前向螞蟻所攜帶的信息值建立到源節點的反向點信息素表，跳轉到第（4）步。

（6）當每個前向螞蟻到達目的節點時，它們將立即轉化成一個后向螞蟻，并且它將沿著反向信息素表回到源節點。中間節點收到后向螞蟻數據包時，按照式（5）、式（7）將更新相鄰節點信息素強度，并建立到目的節點的路由表，路由表是一個三元組包括：目的節點、下一個節點、信息素。

（7）后向螞蟻到達源節點后路由建立完畢。

2.5網絡的維護

在無線傳感器網絡中，節點的故障和能量的耗盡都將導致網絡拓撲結構的變化，這使得路由維護顯得十分重要。路由斷路和節點能量的消耗是路由維護中必須解決的兩個關鍵問題。

（1）路由斷路。當中間節點發現路徑不通或收到路由斷路的消息后，它首先根據斷路的路徑信息刪除自己對應的路由表條目，然后查詢可能性路由表條目，看是否能找到到達同一目的地的其他路徑。如果有，則根據路由表中信息素的條目作為的路徑進行通信；如果沒有到達對應目的地的可選路徑后，即向其他節點繼續發送路由斷路消息。當源節點在通信完成前收到路由斷路消息后，如果沒有到目的地的其他路徑，則將發起新的路徑探索過程，直到通信完成。

（2）節點能量的消耗。為了不頻繁地重建路由表，節省能量，MP-ACA算法根據每個節電的剩余能量自動更新路由表，這樣就使得節點的能耗盡可能保持平衡。節點能量每下降10%，節點就會向周圍節點廣播自己的剩余能量，收到廣播的節點用式（8）更新路由表：

3.1接收到數據包的平均延時

圖1反映了三種算法網絡傳輸數據的平均傳輸延時隨時間的變化關系。由圖可知，各算法的時延呈現先降后增的趨勢，主要是由于網絡剛建立時，節點需要建立路由表，然后時延呈下降趨勢。網絡運行一段時間后，由于網絡中部分節點死亡，導致路由的重建，致使時延呈上升趨勢。總的來說，MP-ACA的平均傳輸延時要小于MACO和ACA的平均傳輸延遲，主要是因為在MACO和ACA其路由是通過多次迭代而建立起來的，需要的時間長，從而增加了網絡延時。

3.2能量不為零的節點數目

圖2反映了三種算法在整個網絡時間內能量不為零的節點數目隨時間的變化關系。由