【導(dǎo)讀】哈爾濱遠(yuǎn)東理工學(xué)院。畢業(yè)設(shè)計(jì)（論文）評(píng)語及成績(jī)。是否同意參加答辯：。是否建議授予學(xué)士學(xué)位：。答辯委員會(huì)成員簽字：1、2、3、答辯委員會(huì)主任簽字。學(xué)生姓名崔繼鵬學(xué)號(hào)09030201. 本文提出了一種基于蟻群優(yōu)化的ZigBee路由算法，該算法很好地利用了蟻群。算法的自適應(yīng)性，結(jié)合蟻群算法和無線傳感網(wǎng)絡(luò)中ZigBee技術(shù)的結(jié)構(gòu)和特點(diǎn)，并根據(jù)。螞蟻尋徑與路由傳輸數(shù)據(jù)節(jié)點(diǎn)的相似性，采用該算法提高網(wǎng)絡(luò)的確定性服務(wù)質(zhì)量，提高。網(wǎng)絡(luò)路由節(jié)點(diǎn)的平均壽命，尋求網(wǎng)絡(luò)中任一倆個(gè)節(jié)點(diǎn)的最優(yōu)路徑，提高數(shù)據(jù)包成功發(fā)送。速度，同時(shí)平衡網(wǎng)絡(luò)帶寬、時(shí)延節(jié)省費(fèi)用，并對(duì)他們進(jìn)行限制以保證在網(wǎng)絡(luò)出現(xiàn)過載擁。堵情況時(shí)，重要數(shù)據(jù)不受延遲或丟棄。蟻群算法顯示出它在無線傳感器網(wǎng)絡(luò)路由方面的。無線傳感器網(wǎng)絡(luò)廣泛應(yīng)。用于軍事領(lǐng)域、環(huán)境監(jiān)測(cè)、醫(yī)療健康等領(lǐng)域，具有重要的實(shí)用價(jià)值。絡(luò)路由算法的關(guān)鍵因素。

　　

【正文】 的性能。 將蟻群算法應(yīng)用在網(wǎng)絡(luò)路由上，算法中的每只螞蟻，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。如果一只螞蟻因?yàn)樗?jīng)過了網(wǎng)絡(luò)中堵塞的路段而導(dǎo)致了比較大的延遲，那么就對(duì)相應(yīng)的表項(xiàng)做較小的增強(qiáng)，如果某條路段比較順利，那么就對(duì)該表項(xiàng)做較大的增強(qiáng)。同時(shí)應(yīng)用揮發(fā)機(jī)制，就可以做到系統(tǒng)信息的更新，從而使得那些過期的路由信息不再保留。這樣，在當(dāng)前最優(yōu)路徑出現(xiàn)阻塞時(shí)，算法能很快找到另一條可替代的較優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、網(wǎng)絡(luò)負(fù) 載量以及網(wǎng)絡(luò)的利用率。 簡(jiǎn)單相關(guān)路徑 Zigbee 路由算法概述 簡(jiǎn)單相關(guān)多路 Zigbee 路由算法的基本思想就是所建立的所有替換路徑都靠近主路徑，更進(jìn)一步講就是替換路徑上的節(jié)點(diǎn)要么就是主路徑上的節(jié)點(diǎn)，要么是主路徑上節(jié)點(diǎn)的鄰節(jié)點(diǎn)。其基本原理可歸納如下。源節(jié)點(diǎn)泛洪 Zigbee 路由請(qǐng)求報(bào)文 RREQ。收到 RREQ的節(jié)點(diǎn)在確認(rèn)本節(jié)點(diǎn)既不是目的節(jié)點(diǎn)，又沒有發(fā)送過該 RREQ 的條件下，計(jì)算本節(jié)點(diǎn)與發(fā)送給它 RREQ的上游節(jié)點(diǎn)鏈路之間的代價(jià)，將其寫入 RREQ的 Cost域后轉(zhuǎn)發(fā)此 RREQ。目的節(jié)點(diǎn)根據(jù)規(guī)定時(shí)間內(nèi)接收到的 所有 RREQ 報(bào)文提取出網(wǎng)絡(luò)拓?fù)湫畔ⅲ瑯?gòu)建簡(jiǎn)單相關(guān)多路徑 Zigbee 路由。 由上述原理可知，現(xiàn)有簡(jiǎn)單相關(guān)多路徑算法采用洪泛方式建立 Zigbee 路由，所以存在以下問題： (1) 建立 Zigbee 路由需要的時(shí)間長，且易產(chǎn)生泛洪，從而導(dǎo)致?lián)砣漠a(chǎn)生。 (2) 簡(jiǎn)單相關(guān)多路徑的多條路徑是從目的節(jié)點(diǎn)在規(guī)定時(shí)間內(nèi)接受到的多條 Zigbee路由內(nèi)產(chǎn)生的，在這段時(shí)間內(nèi)不一定能尋到最優(yōu)路徑。 (3) 算法沒有規(guī)定在特定網(wǎng)絡(luò)約束條件下對(duì) Zigbee 路由進(jìn)行優(yōu)化的機(jī)制。 路由維護(hù)與信息素更改 每個(gè)從源節(jié)點(diǎn) iv 向目的節(jié)點(diǎn) jv 傳輸?shù)臄?shù)據(jù)包，相當(dāng)于一個(gè)路徑增強(qiáng)螞蟻。路徑的增強(qiáng)通過螞蟻施放信息素的機(jī)制實(shí)現(xiàn)，即在數(shù)據(jù)傳輸?shù)倪^程中通過對(duì)所經(jīng)過節(jié)點(diǎn)的信息素的修改來實(shí)現(xiàn)。優(yōu)化路徑在這個(gè)過程中會(huì)自動(dòng)出現(xiàn)。螞蟻的自動(dòng)尋優(yōu)機(jī)制會(huì)保證在數(shù)據(jù)傳輸時(shí)自動(dòng)選擇優(yōu)化路徑。和真實(shí)蟻群一樣，所建立的信息素濃度，并不是永久不變的。信息素濃度的變化通過兩種機(jī)制實(shí)現(xiàn)，信息素增強(qiáng)和信息素蒸發(fā)。 (1) 信息素增強(qiáng)．當(dāng)從節(jié)點(diǎn) iv 轉(zhuǎn)發(fā)數(shù)據(jù) 到鄰居節(jié)點(diǎn) jv 時(shí)，從 iv 到 jv 的路徑被加強(qiáng)， 路由表中相應(yīng)的 ij? 按式增加，從而實(shí)現(xiàn)優(yōu)勢(shì)路徑增強(qiáng)； 哈爾濱遠(yuǎn)東理工學(xué)院學(xué)士學(xué)位論文 12 (2) 信息素蒸發(fā)，為了避免統(tǒng)治地位路徑的產(chǎn)生而使某些節(jié)點(diǎn)的能量消耗過快，網(wǎng)絡(luò)中所有單跳路徑的信息素濃度按式增加； (3) 進(jìn)行周期性蒸發(fā)，以減小過去的信息素的影響，促進(jìn)新路徑的使用。 網(wǎng)絡(luò)中的各節(jié)點(diǎn)實(shí)時(shí)檢測(cè)自己的剩余能量，并將剩余能量通知鄰居 節(jié)點(diǎn)。我們采用閾值觸發(fā)方式啟動(dòng)能量通知過程，即當(dāng)能量降低超過一定量，或降低到一定值時(shí)，啟動(dòng)通知機(jī)制通知鄰居節(jié)點(diǎn)。具體的通知機(jī)制類似于網(wǎng)絡(luò)初始化時(shí)的做法：欲發(fā)出能量通知的節(jié)點(diǎn)以一個(gè)一跳的消息，將它的剩余能量發(fā)給鄰居節(jié)點(diǎn)，各鄰居節(jié)點(diǎn)根據(jù)收到的能量值更新本地路由表中該節(jié)點(diǎn)對(duì)應(yīng)的剩余能量值，從而降低該節(jié)點(diǎn)被選中的概率，減少該節(jié)點(diǎn)的能量消耗。通過這種方式，能較好地達(dá)到均衡使用能量的效果。 基于蟻群算法的 Zigbee 路由研究與改進(jìn) 蟻群算法是最新發(fā)展的一種模擬昆蟲王國中螞蟻群體智能行為的仿生優(yōu)化算法。它具有 較強(qiáng)的魯棒性，優(yōu)良的分布計(jì)算機(jī)制，易于與其他方法相結(jié)合等優(yōu)點(diǎn)，其思想來源于自然界中蟻群尋找食物過程的觀察。在覓食過程中 ,螞蟻在它所經(jīng)過的路徑上會(huì)釋放出與路徑長度有關(guān)的信息素 , 路徑越長，釋放的信息量越小。后來的螞蟻能感知信息素的存在及其濃度，以此指導(dǎo)自己的運(yùn)動(dòng)方向，并傾向于朝著信息素濃度高的方向移動(dòng)。于是，螞蟻的集體行為便表現(xiàn)出一種信息正反饋傾向。 蟻群算法中 信息素的更新原則 當(dāng)信息包在路徑上傳輸時(shí)，信息素的值會(huì)發(fā)生變化。如有信息包經(jīng)過，路徑上信息素的值就會(huì)增加，而沒有 信息包經(jīng)過的路徑的信息素會(huì)揮發(fā) 。 )(, tji? 的值由式 (24)進(jìn)行更新。 )()1()()( , tttt kjijiji ????? ?????? (28) 其中： ? 是信息素?fù)]發(fā)因子； )(, tkji?? 為在鏈路 ),(ji 上增加的信息素值，)()( m a x, EEQt rem a inkji ??? ， Q為常數(shù)， remainE 表示剩余能量， maxE 為初始能量。剩余能量越低，則增加的信息素就越少，選擇此路徑的可能性就會(huì)降低，從而達(dá)到繞開節(jié)點(diǎn)能量低的節(jié)點(diǎn)，使得網(wǎng)絡(luò)中節(jié)點(diǎn)能量消耗均衡。 ）（ 1??? 是信息素保持率，而 ? 表示衰減率。參數(shù) p始終小于 1的意義在于，每一個(gè)周期后，所有邊上的信息素必須衰減，不能無限制積累，這樣可義在于，每一個(gè)周期后，所有邊上的信息素必須衰減，不能無限制積累，這樣可以讓系統(tǒng)“遺忘 比較差的路徑，增加后繼搜索的發(fā)散性。顯然衰減是以指數(shù)級(jí)速度進(jìn)行的。 本章小結(jié) 本章詳細(xì)描述了第一個(gè) ACO 算法一螞蟻系統(tǒng)的現(xiàn)實(shí)原理和算法模型及描述，螞蟻系統(tǒng)為闡明 ACO 元啟發(fā)式算法的基本思想做了最好的解釋。有了螞蟻系統(tǒng)的基本原理做鋪墊，融合元啟發(fā)式算法的特點(diǎn)，就可以提出 ACO 的元啟發(fā)式框架，通過對(duì)組合優(yōu)化問題的算法關(guān)聯(lián)定義， ACO 元啟發(fā)式就順其自然的有了基本的構(gòu)件組成和運(yùn)行模式。在這個(gè)框架下，螞蟻系統(tǒng)是作為算法的一個(gè)實(shí)例，并可以衍生出其他算法，盡管其他衍生算法是單獨(dú)提出，但是 ACO 元啟發(fā)式框架是對(duì)它們的最好概括。接著講述了幾種典型的 ACO 算法變種，這些都比原始的蟻群 系統(tǒng)的性能有了大幅度提升。 哈爾濱遠(yuǎn)東理工學(xué)院學(xué)士學(xué)位論文 13 第 3 章 無線網(wǎng)絡(luò)蟻群優(yōu)化算法路由技術(shù) 蟻群優(yōu)化 ACO 算法是一門發(fā)展中的學(xué)科的一個(gè)組成部分，即螞蟻算法 .蟻群優(yōu)化的創(chuàng)始人 Dorigo 等人把螞蟻算法定義為一種受到真實(shí)蟻群采用媒介質(zhì)進(jìn)行交流的行為啟發(fā)而設(shè)計(jì)的人工多 Agent 系統(tǒng)。 蟻群優(yōu)化算法基本原理 蟻群優(yōu)化算法基本概念 蟻群優(yōu)化算法是 Marco Dorigo 等學(xué)者受螞蟻覓食行為啟發(fā)提出的一種啟發(fā)式算法。在覓食路徑選擇時(shí)，起初由于每只螞蟻僅知道局部信息，無法找到從巢穴到食源的最短路徑，但是螞蟻通過在覓食路徑釋放信 息素，間接地完成了與其他螞蟻的路徑信息交換，最終整個(gè)蟻群獲得了全局最優(yōu)路徑 (全局優(yōu)化結(jié)果 )。 蟻群優(yōu)化 (ACO)的啟發(fā)式搜索方法具有較好的分布性和自適應(yīng)性，可以根據(jù)要優(yōu)化對(duì)象的特點(diǎn)改變優(yōu)化策略。還可以通過多條備選路徑均衡了各節(jié)點(diǎn)的能耗，盡可能地延長節(jié)點(diǎn)生命期，該算法在螞蟻數(shù)據(jù)包結(jié)構(gòu)、概率選擇公式及信息素更新公式等方面做了改進(jìn)。該算法將延長網(wǎng)絡(luò)壽命，提高能量有效性。 在計(jì)算機(jī)上實(shí)現(xiàn)以上模型時(shí)，一般有兩種方法：第一種是通過定義差分方程或微分方程來逐步計(jì)算構(gòu)建解，這樣可以得到系統(tǒng)的期望行為，如蒙特卡洛方法，這樣定 義的模型比較有數(shù)學(xué)依據(jù)，嚴(yán)謹(jǐn)而又有實(shí)際意義，然而對(duì)這樣的方程計(jì)算有時(shí)也會(huì)帶來計(jì)算量大的問題；另一種是模擬再現(xiàn)螞蟻群體，即設(shè)計(jì)一種人工螞蟻 (artifical ant)來模擬真實(shí)螞蟻，其通過一個(gè)分布式學(xué)習(xí)過程來自適應(yīng)地獨(dú)立并行地構(gòu)建解，然后通過對(duì) (部分 )解進(jìn)行評(píng)估，來修改信息素濃度 (信息素的釋放和蒸發(fā) )，以此對(duì)以后搜索過程實(shí)施一定的導(dǎo)相似 )作用。為提高算法的性能，可以在一次迭代之后進(jìn)行后臺(tái)處理，進(jìn)行局部?jī)?yōu)化和全局信息收集等集中行動(dòng)。模擬仿真方法啟發(fā)我們?cè)O(shè)計(jì)一種人工螞蟻用相似的思路去解決優(yōu)化問題。 蟻群優(yōu)化算法數(shù)學(xué)模型 基本的蟻群優(yōu)化算法，設(shè) ),( EVG? 是一個(gè)連通的無向圖， V是圖 G中頂點(diǎn)的集合， E是邊的集合。 vvv ji ?, ； Ejie ?),( 令 iju 表示邊 ),( jie 上的信息素濃度， ij? 表示 ),( jie 上預(yù)知的局部啟發(fā)值。 iv 局部啟發(fā)值可以是任何形式的代價(jià)，如距離、費(fèi)用等。在頂點(diǎn) Vi的螞蟻使用信息濃度 iju 和局部啟發(fā)值 ij? 來計(jì)算選擇下一個(gè)相鄰頂點(diǎn) ,jv 的概率 ijp : ??????? ??? ??其它,0)(,][][][ ][][][ ka l l o w dsisisisijijijkija llo w djzzpk?????????? (31) 其中， vvv ji ?, ， v是頂點(diǎn) iv 的所有相距一步的相鄰頂點(diǎn)集合； ? 和β分別表示 iju 和 ij?的可調(diào)權(quán)重； t表示時(shí)刻。因此，螞蟻的路由傾向可以通過選擇不同的 ? 和β值進(jìn)行調(diào)整。如果，使螞蟻偏愛具有高信息素濃度的路徑；反之則使螞蟻選擇具有更大優(yōu)化啟發(fā)值的路徑。當(dāng)螞蟻從經(jīng)過 ),( jie 到 jv 時(shí)， ),( jie 上的信息素濃度 iju 如下進(jìn)行修改： 哈爾濱遠(yuǎn)東理工學(xué)院學(xué)士學(xué)位論文 14 ,)()( ??? ??? tt ijij (32) 其中 是螞蟻施放的信息素量。 ),( jie 上的信息素濃度隨著時(shí)間的推移遵循下式被逐漸蒸發(fā)： ],1,0(,)()( ???? ????? tt ijij (33) 這里，執(zhí)行一次蒸發(fā)的時(shí)間間隔為 ? ， P 是蒸發(fā)系數(shù)。 該算法利用蟻群的動(dòng)態(tài)適應(yīng)性和尋優(yōu)能力在網(wǎng)絡(luò)最短路徑和能量均衡消耗之間進(jìn)行平衡，以達(dá)到網(wǎng)絡(luò)能量的優(yōu)化均衡消耗，進(jìn)而延長整個(gè)網(wǎng)絡(luò)的壽命。 蟻群優(yōu)化算法的值與點(diǎn)的收斂 一個(gè)算法首先要考慮的典型問題是收斂性問題 (Convergence problem)，也就是算法能否在給定足夠資源的情況下找到最優(yōu)解。因?yàn)?ACO 是一個(gè)隨機(jī)搜索過程，加上信息素更新的不確定性，也許會(huì)使算法永遠(yuǎn)無法找到最優(yōu)解。對(duì)于一個(gè)隨機(jī)優(yōu)化算法，有兩種收斂類型：值收斂 (convergence in value)和解收斂 (convergence in solution)。因?yàn)閱栴}的最優(yōu)解一般都不止一個(gè)，那么收斂性研究的目的就是要證明算法能否收斂到某個(gè)最優(yōu)值。值收斂，就是指算法至少有一次機(jī)會(huì)生成～個(gè)最優(yōu)解。而解收斂研究的是，算法能否達(dá)到持續(xù)地生成某一相同最優(yōu)解的狀態(tài)。 研究收斂性一般遵從從易到難原則。證明 ACO 算法的特殊子集的收斂性是個(gè)不錯(cuò)的入門方法。對(duì)于隨機(jī)優(yōu)化算法而言，解收斂的強(qiáng)度比值收斂強(qiáng)，但是通常只需要證明算法能夠找到最優(yōu)解，因此真正需要研究的是值收斂問題。對(duì)于理論研究結(jié)果，由特殊子集算法擴(kuò)展 到普通 ACO 算法是可行的。 蟻群優(yōu)化算法在路由中的應(yīng)用 ZigBee 是一種全新的低復(fù)雜度、低成本和低功耗的雙向無線通信技術(shù)。完整的協(xié)議棧只有 32 KB。且可以嵌入到各種電子信息設(shè)備中。由于無線傳感器網(wǎng)絡(luò)本身要求的技術(shù)特點(diǎn)，所以 ZigBee 技術(shù)作為無線傳感器節(jié)點(diǎn)的無線通訊是切實(shí)可行的。我們通過應(yīng)用 ZigBee 技術(shù)來構(gòu)建無線傳感器網(wǎng)絡(luò)。由于無線傳感器網(wǎng)絡(luò)具有結(jié)點(diǎn)計(jì)算能力弱、結(jié)點(diǎn)電能 (電池提供的 )有限等特點(diǎn)，在設(shè)計(jì)無線傳感器網(wǎng)絡(luò)路由算法時(shí)，必須考慮算法的節(jié)能性和簡(jiǎn)單性。蟻群優(yōu)化作為一個(gè)啟發(fā)搜索算法，具有分 布性好、全局尋優(yōu)能力強(qiáng)、算法簡(jiǎn)單易實(shí)現(xiàn)等優(yōu)點(diǎn)。 目前，針對(duì) ZigBee 網(wǎng)絡(luò)自身的特點(diǎn)和用途設(shè)計(jì)能量有效的路由算法已成為 ZigBee網(wǎng)絡(luò)研究的一個(gè)重要課題。由于 ZigBee 網(wǎng)絡(luò)中節(jié)點(diǎn)的能量資源、計(jì)算能力和帶寬都非常有限，且 ZigBee 節(jié)點(diǎn)一般由電池供電， ZigBee 網(wǎng)絡(luò)的壽命嚴(yán)重依賴節(jié)點(diǎn)電池能量的有效利用，因此節(jié)點(diǎn)電池能量的有效利用從而延長網(wǎng)絡(luò)壽命在 ZigBee 網(wǎng)絡(luò)中是至關(guān)重要的。 無線傳感器網(wǎng)絡(luò)由眾多具有感知、通信和計(jì)算能力的傳感器節(jié)點(diǎn)，以無線方式連接而成，在軍事、災(zāi)難救援、環(huán)境監(jiān)測(cè)、醫(yī)療健康、家庭監(jiān)護(hù)以及 其他眾多領(lǐng)域有著廣泛的應(yīng)用前景。由于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量有限且一般沒有能量補(bǔ)充，所以網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗的快慢就成了影響無線傳感器網(wǎng)絡(luò)壽命長短的決定性因素。很多路由協(xié)議選擇能量消耗小的數(shù)據(jù)傳輸路徑，相應(yīng)的路由算法往往只優(yōu)化一個(gè)參數(shù) —— 跳數(shù)，使數(shù)據(jù)沿最短路徑傳輸。但如果頻繁使用同一條路徑傳輸數(shù)據(jù)，就會(huì)使這些路徑上的節(jié)點(diǎn)因能量消耗過快而過早罷工，導(dǎo)致網(wǎng)絡(luò)分裂甚至死亡，從而嚴(yán)重縮短網(wǎng)絡(luò)壽命；而此時(shí)網(wǎng)絡(luò)中其他節(jié)點(diǎn)可能還有很多剩余能量。因此，如何高效使用無線傳感器網(wǎng)絡(luò)有限的能量來最大哈爾濱遠(yuǎn)東理工學(xué)院學(xué)士學(xué)位論文 15 化網(wǎng)絡(luò)壽命成為無線傳感器網(wǎng)絡(luò)及其路由 設(shè)計(jì)的首要目標(biāo)和面臨的首要挑戰(zhàn)。 蟻群算法中參數(shù)的最優(yōu)選擇 蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。本文介紹了蟻群算法基本模型 AS 的原理、特點(diǎn)、構(gòu)成和實(shí)現(xiàn)方法，對(duì)基本蟻群算法參數(shù)的合理選取進(jìn)行了實(shí)驗(yàn)分析，給出了算法參數(shù)選取的基本原則，有利于蟻群算法在優(yōu)化問題中的推廣和應(yīng)用。 關(guān)于蟻群算法中信息素?fù)]發(fā)度對(duì)算法性能的影響及其在實(shí)際應(yīng)用中的選擇，可以通過計(jì)算機(jī)仿真實(shí)驗(yàn)來分析和確定。對(duì)此，本文取如下的 TSP 問題及算法參數(shù)進(jìn)行仿真比較距離矩陣如下表所示： 表 31 信息素殘留系數(shù) 對(duì)算法性能影響 殘留系數(shù) 最優(yōu)路徑長度 搜索循環(huán)次數(shù) 17 26 44 115 165 567 蟻群 信息素?fù)]發(fā)度的選擇 在蟻群算法中，人工螞蟻是具有人類記憶功能的，隨著時(shí)間的推移 , 以前留下的信息將要逐漸消逝。在算法模型中用參數(shù) ??1 表示信