【正文】 節(jié)點因能量消耗過快而過早罷工，導(dǎo)致網(wǎng)絡(luò)分裂甚至死亡，從而嚴(yán)重縮短網(wǎng)絡(luò)壽命；而此時網(wǎng)絡(luò)中其他節(jié)點可能還有很多剩余能量。由于無線傳感器網(wǎng)絡(luò)節(jié)點能量有限且一般沒有能量補充，所以網(wǎng)絡(luò)節(jié)點能量消耗的快慢就成了影響無線傳感器網(wǎng)絡(luò)壽命長短的決定性因素。由于ZigBee網(wǎng)絡(luò)中節(jié)點的能量資源、計算能力和帶寬都非常有限，且ZigBee節(jié)點一般由電池供電，ZigBee網(wǎng)絡(luò)的壽命嚴(yán)重依賴節(jié)點電池能量的有效利用，因此節(jié)點電池能量的有效利用從而延長網(wǎng)絡(luò)壽命在ZigBee網(wǎng)絡(luò)中是至關(guān)重要的。蟻群優(yōu)化作為一個啟發(fā)搜索算法，具有分布性好、全局尋優(yōu)能力強、算法簡單易實現(xiàn)等優(yōu)點。我們通過應(yīng)用ZigBee技術(shù)來構(gòu)建無線傳感器網(wǎng)絡(luò)。且可以嵌入到各種電子信息設(shè)備中。 蟻群優(yōu)化算法在路由中的應(yīng)用ZigBee是一種全新的低復(fù)雜度、低成本和低功耗的雙向無線通信技術(shù)。對于隨機優(yōu)化算法而言，解收斂的強度比值收斂強，但是通常只需要證明算法能夠找到最優(yōu)解，因此真正需要研究的是值收斂問題。研究收斂性一般遵從從易到難原則。值收斂，就是指算法至少有一次機會生成～個最優(yōu)解。對于一個隨機優(yōu)化算法，有兩種收斂類型：值收斂(convergence in value)和解收斂(convergence in solution)。 蟻群優(yōu)化算法的值與點的收斂一個算法首先要考慮的典型問題是收斂性問題(Convergence problem)，也就是算法能否在給定足夠資源的情況下找到最優(yōu)解。上的信息素濃度隨著時間的推移遵循下式被逐漸蒸發(fā)： (33)這里，執(zhí)行一次蒸發(fā)的時間間隔為，P是蒸發(fā)系數(shù)。如果，使螞蟻偏愛具有高信息素濃度的路徑；反之則使螞蟻選擇具有更大優(yōu)化啟發(fā)值的路徑。在頂點Vi的螞蟻使用信息濃度和局部啟發(fā)值來計算選擇下一個相鄰頂點,的概率: (31)其中，v是頂點的所有相距一步的相鄰頂點集合；和β分別表示和的可調(diào)權(quán)重；t表示時刻。；令表示邊上的信息素濃度，表示上預(yù)知的局部啟發(fā)值。模擬仿真方法啟發(fā)我們設(shè)計一種人工螞蟻用相似的思路去解決優(yōu)化問題。在計算機上實現(xiàn)以上模型時，一般有兩種方法：第一種是通過定義差分方程或微分方程來逐步計算構(gòu)建解，這樣可以得到系統(tǒng)的期望行為，如蒙特卡洛方法，這樣定義的模型比較有數(shù)學(xué)依據(jù)，嚴(yán)謹(jǐn)而又有實際意義，然而對這樣的方程計算有時也會帶來計算量大的問題；另一種是模擬再現(xiàn)螞蟻群體，即設(shè)計一種人工螞蟻(artifical ant)來模擬真實螞蟻，其通過一個分布式學(xué)習(xí)過程來自適應(yīng)地獨立并行地構(gòu)建解，然后通過對(部分)解進行評估，來修改信息素濃度(信息素的釋放和蒸發(fā))，以此對以后搜索過程實施一定的導(dǎo)相似)作用。還可以通過多條備選路徑均衡了各節(jié)點的能耗，盡可能地延長節(jié)點生命期，該算法在螞蟻數(shù)據(jù)包結(jié)構(gòu)、概率選擇公式及信息素更新公式等方面做了改進。在覓食路徑選擇時，起初由于每只螞蟻僅知道局部信息，無法找到從巢穴到食源的最短路徑，但是螞蟻通過在覓食路徑釋放信息素，間接地完成了與其他螞蟻的路徑信息交換，最終整個蟻群獲得了全局最優(yōu)路徑(全局優(yōu)化結(jié)果)。第3章 無線網(wǎng)絡(luò)蟻群優(yōu)化算法路由技術(shù)蟻群優(yōu)化ACO算法是一門發(fā)展中的學(xué)科的一個組成部分。在這個框架下，螞蟻系統(tǒng)是作為算法的一個實例，并可以衍生出其他算法，盡管其他衍生算法是單獨提出，但是ACO元啟發(fā)式框架是對它們的最好概括。 本章小結(jié)本章詳細(xì)描述了第一個ACO算法一螞蟻系統(tǒng)的現(xiàn)實原理和算法模型及描述，螞蟻系統(tǒng)為闡明ACO元啟發(fā)式算法的基本思想做了最好的解釋。參數(shù)p始終小于1的意義在于，每一個周期后，所有邊上的信息素必須衰減，不能無限制積累，這樣可義在于，每一個周期后，所有邊上的信息素必須衰減，不能無限制積累，這樣可以讓系統(tǒng)“遺忘比較差的路徑，增加后繼搜索的發(fā)散性。剩余能量越低，則增加的信息素就越少，選擇此路徑的可能性就會降低，從而達到繞開節(jié)點能量低的節(jié)點，使得網(wǎng)絡(luò)中節(jié)點能量消耗均衡。的值由式(24)進行更新。 蟻群算法中信息素的更新原則當(dāng)信息包在路徑上傳輸時，信息素的值會發(fā)生變化。后來的螞蟻能感知信息素的存在及其濃度，以此指導(dǎo)自己的運動方向，并傾向于朝著信息素濃度高的方向移動。它具有較強的魯棒性，優(yōu)良的分布計算機制，易于與其他方法相結(jié)合等優(yōu)點，其思想來源于自然界中蟻群尋找食物過程的觀察。通過這種方式，能較好地達到均衡使用能量的效果。我們采用閾值觸發(fā)方式啟動能量通知過程，即當(dāng)能量降低超過一定量，或降低到一定值時，啟動通知機制通知鄰居節(jié)點。(1) 信息素增強．當(dāng)從節(jié)點 轉(zhuǎn)發(fā)數(shù)據(jù)到鄰居節(jié)點 時，從到的路徑被加強， 路由表中相應(yīng)的按式增加，從而實現(xiàn)優(yōu)勢路徑增強；(2) 信息素蒸發(fā)，為了避免統(tǒng)治地位路徑的產(chǎn)生而使某些節(jié)點的能量消耗過快，網(wǎng)絡(luò)中所有單跳路徑的信息素濃度按式增加；(3) 進行周期性蒸發(fā)，以減小過去的信息素的影響，促進新路徑的使用。和真實蟻群一樣，所建立的信息素濃度，并不是永久不變的。優(yōu)化路徑在這個過程中會自動出現(xiàn)。 路由維護與信息素更改每個從源節(jié)點 向目的節(jié)點 傳輸?shù)臄?shù)據(jù)包，相當(dāng)于一個路徑增強螞蟻。(2) 簡單相關(guān)多路徑的多條路徑是從目的節(jié)點在規(guī)定時間內(nèi)接受到的多條Zigbee路由內(nèi)產(chǎn)生的，在這段時間內(nèi)不一定能尋到最優(yōu)路徑。目的節(jié)點根據(jù)規(guī)定時間內(nèi)接收到的所有RREQ報文提取出網(wǎng)絡(luò)拓?fù)湫畔?，?gòu)建簡單相關(guān)多路徑Zigbee路由。源節(jié)點泛洪Zigbee路由請求報文RREQ。 簡單相關(guān)路徑Zigbee路由算法概述 簡單相關(guān)多路Zigbee路由算法的基本思想就是所建立的所有替換路徑都靠近主路徑，更進一步講就是替換路徑上的節(jié)點要么就是主路徑上的節(jié)點，要么是主路徑上節(jié)點的鄰節(jié)點。同時應(yīng)用揮發(fā)機制，就可以做到系統(tǒng)信息的更新，從而使得那些過期的路由信息不再保留。將蟻群算法應(yīng)用在網(wǎng)絡(luò)路由上，算法中的每只螞蟻，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗與性能，動態(tài)更新路由表項。(4)易于與其它方法結(jié)合。(3)群算法具有較強的魯棒性。(2)蟻群算法是一種正反饋算法。單個螞蟻的搜索過程是彼此獨立的，容易陷入局部最優(yōu)。在隨機搜索方面，蟻群算法是一種行之有效的算法。此路徑即為到達V1的最短路徑。 Upper Upper障礙物 A0 A0V1V1V0V0障礙物 A1 A1 Down Down 圖 24 蟻群算法迭代圖初始時，A0走Upper路徑，Al走Down路徑，各自釋放在路徑上的信息素為:,。假設(shè)初始時刻每條路徑均有相同的概率()被選擇，信息素初值。 蟻群算法迭代過程以下圖為例說明蟻群算法的迭代運算過程。當(dāng)城市個數(shù)n和螞蟻個數(shù)m成線性關(guān)系時，這個算法的復(fù)雜度為。For to m do根據(jù)式(24)、(25)，更新邊上的信息素濃度；(5) 根據(jù)式(23)，對每一條邊計算Set Set set (6) 如果并且(不是所有的螞蟻選擇同一條路徑)那么；清空所有的tabu list；轉(zhuǎn)到第(2)步；否則；初始化，設(shè)置時間計數(shù)器，循環(huán)計數(shù)器，每條邊信息素濃度初值，將m只螞蟻隨機放到n個城市 初始化tabu列表，將所有螞蟻的初始城市放置到tabu列表中Tab列表滿？ Y計算機轉(zhuǎn)移概率p，按概率將每只螞蟻從第i個城市移到第j個，寧見j插入tabu列表中 N封閉回路，分別計算每只螞蟻走過的總長度，記錄最短路徑，計算信息素濃度該變量達到最大環(huán)次數(shù)求解度 N Y 顯示并打印最短路徑圖 23 蟻群算法流程圖打印出最短路徑，終止整個程序。可見antcycle system模型性能較好。初始時刻。當(dāng)所有螞蟻完成各自路徑的選擇過程，必須對各邊上的信息素按公式(23)作一次全局更新，此時根據(jù)具體算法的不同，表達形式可以不同，要根據(jù)具體問題而定。與實際蟻群不同，人工蟻群系統(tǒng)具有記憶功能，用以記錄螞蟻當(dāng)前所走過的城市，集合隨著進化過程作動態(tài)調(diào)整。螞蟻在運動過程中，根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向，時刻位于某一城市的螞蟻一次只能選擇其中一個目標(biāo)城市，次后回到起點，完成一次循環(huán)。從公式我們看出，螞蟻更有可能選擇時延小、可利用帶寬大、信息素強度較強的鏈路。 pnm表1中的n為某個節(jié)點可以選擇的目的節(jié)點數(shù)，m為該節(jié)點的相鄰節(jié)點數(shù)。 p1m d2 p21 p22 表21 信息素路由選擇表信息素路由選擇表 鄰節(jié)點目的節(jié)點 a b 而強度大的分泌物會吸引更多的螞蟻，從而形成一種正反饋通過這種正反饋，螞蟻最終可以發(fā)現(xiàn)最短路徑。這種能力是靠其在所經(jīng)過的路徑上留下一種揮發(fā)性分泌物來實現(xiàn)的。可以使信息素濃度低、能量低的節(jié)點進入休眠模式，進一步降低能耗。蟻群算法的自組織特性使該算法能自動適應(yīng)網(wǎng)絡(luò)狀態(tài)和節(jié)點能量的動態(tài)變化，算法魯棒性強；(3)支持多路徑。圖 22 蟻群原理圖 蟻群算法特點本文提出的算法具有以下特點：(1)路由代價低。若繼續(xù)進行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄ACD路線，而都選擇ABD 路線。若按以上規(guī)則繼續(xù)，蟻群在ABD 路線上再增派一只螞蟻(共3只)，而ACD 路線上仍然為一只螞蟻。假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36 個時間單位后, 所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點取得了食物，此時ABD的路線往返了2 趟，每一處的信息素為4個單位，而ACD的路線往返了一趟, 每一處的信息素為2 個單位，其比值為2:1。假設(shè)初始時每條分配路線一只螞蟻, 每個時間單位行走一步, 圖中上圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。信息素模型由一系列模型參數(shù)組成，這里的模型參數(shù)值被稱為信息素值。通過這種正反饋，螞蟻最終可以發(fā)現(xiàn)最短路徑。在回程中，螞蟻在地面上留下一種被成為信息素的揮發(fā)性分泌物，留下的信息素數(shù)量取決于食物的數(shù)量和質(zhì)量。人工蟻群是受到真實螞蟻覓食行為的啟示而提出的，這個行為使螞蟻可以在食物源和蟻巢之間找到最短路徑。 蟻群算法簡介 蟻群算法基本概念蟻群算法是一種基于蟻群系統(tǒng)原理的、具有自組織能力的、新型的啟發(fā)式優(yōu)化算法。1979年，Dougls R．Hofstadter首次提出了人工螞蟻的概念，探討了具有較低智能的簡單個體間能否通過相互作用而產(chǎn)生較高的群體智能行為。根據(jù)zigbee路由策略和蟻群優(yōu)化的特點，構(gòu)造了傳感器結(jié)點使算法具有較好的節(jié)能性和全局尋優(yōu)能力，并改善網(wǎng)絡(luò)的性能，達到網(wǎng)絡(luò)優(yōu)化的目的。因此基于蟻群算法的傳感器網(wǎng)路由協(xié)議得到了國內(nèi)外學(xué)者的大量的關(guān)注。提出自己的思路和做法，達到網(wǎng)絡(luò)優(yōu)化的目的。蟻群算法顯示出它在無線傳感器網(wǎng)絡(luò)路由方面的優(yōu)勢。本文探討了蟻群算法的原理、特點及功能；對基本蟻群算法的有關(guān)參數(shù)的合理選擇進行實驗分析；提出了相應(yīng)的改進策略，并通過仿真實驗，驗證了改進算法的有效性，提高了尋求最優(yōu)路徑能力；分析了基于蟻群算法的網(wǎng)絡(luò)路由優(yōu)化。但是蟻群算法畢竟是一種新興的模擬進化算法，還缺乏堅實的數(shù)學(xué)理論基礎(chǔ)，算法的參數(shù)選擇、收斂性等還有待進一步研究，算法的最優(yōu)停止條件也是值得研究的地方。蟻群算法的正反饋性和協(xié)同性使其可用于分布式系統(tǒng)，隱含的并行性更使之具有極強的發(fā)展?jié)摿Α；诖耍覀儼褌鞲衅鹘Y(jié)點模擬成螞蟻，把傳感器的路徑選擇模擬成螞蟻的覓食路徑選擇路徑的啟發(fā)式信息模擬成螞蟻在路徑上釋放的信息素，提出了一種基于蟻群優(yōu)化的路由算法。WSN綜合了嵌入式技術(shù)、傳感器技術(shù)、通信技術(shù)和分布式信息處理技術(shù)，能夠協(xié)作實時感知、監(jiān)測、采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境的信息，并對數(shù)據(jù)進行適當(dāng)?shù)奶幚硪垣@得精簡準(zhǔn)確的信息，并傳送給最終的用戶。但是DAR算法要讓螞蟻記錄經(jīng)過的節(jié)點，不適用于大型網(wǎng)絡(luò)，同時也容易陷入局部最優(yōu)解，網(wǎng)絡(luò)的收斂速度也不快。每個路由節(jié)點中路由表都是隨機的：下一跳節(jié)點是依據(jù)概率值的大小進行選擇的。而后向螞蟻在返回過程途中只釋放常量值的信息素值。Laura Rosati 等人在2008年提出DAR(Distributed Ant Routing)協(xié)議，它是一種按需的路由協(xié)議，相對于主動式路由，它可以減少路由時的網(wǎng)絡(luò)負(fù)載。蟻群優(yōu)化(ACO)是由意大利學(xué)者M．Dorigo等人作為求解著名旅行商問題(TSP)的啟發(fā)式算法而提出的，它是模擬自然界中螞蟻搜索食物行為而提出的一種啟發(fā)式智能進化算法。在這篇論文中M Dorigo引入了antcode模型，并針對TSP問題做了一系列實驗，和其他只能算法做了比較，闡明了AS的強壯性(robust)，多適應(yīng)性(versatile)和基于群體性(populationbased)。這三種模型的主要差別是在于對信息素濃度的變化采取不同的數(shù)學(xué)公式。生物界的昆蟲和其他群居動物的群體智能(swarm intelligence)行為一直是科學(xué)家進行科學(xué)研究的靈感源泉。媒介質(zhì)的這種特性在著名的雙橋?qū)嶒炛杏性敿?xì)的研究，并成為激發(fā)計算機科學(xué)家提出螞蟻系統(tǒng)陽(第一個ACO算法)的直接源泉。 國外蟻群算法研究現(xiàn)狀20世紀(jì)40年代到50年代期間，法國昆蟲學(xué)家Grasse在研究白蟻的生物群體行為時，首次提出了媒介質(zhì)網(wǎng)(stigmergy)的概念，來描述白蟻個體之間間接交流信息的特殊方式。有的文獻通過在螞蟻算法的下一跳選擇公式中引入偏轉(zhuǎn)角的概念來優(yōu)化路徑并利用螞蟻算法的正反饋效應(yīng)來完成數(shù)據(jù)匯聚從而達到節(jié)省能量的目的。然而，并沒有針對WSN的特定需求做出相應(yīng)改變，而且沒有考慮對于WSN性能至關(guān)重要的能耗問題。目前，在將