【正文】 蟻群算法應(yīng)用于無線傳感器網(wǎng)絡(luò)路由方面，提出了許多新的算法。文耀鋒等針對(duì)傳感網(wǎng)絡(luò)中簇頭采用單跳通信時(shí)距離轉(zhuǎn)化為線性規(guī)劃問題，提出了一種基于粒子群優(yōu)化的有效能量空洞避免的無線傳感器路由算法。這種傳感器節(jié)點(diǎn)集成了無線通信技術(shù)、傳感器技術(shù)、分布式信息處理技術(shù)和嵌入式計(jì)算機(jī)技術(shù)等功能。最近幾年來，隨著人類在無線通信技術(shù)、微傳感器技術(shù)、微機(jī)電技術(shù)等方面取得的進(jìn)步，一種集成了感知、通信能力的傳感器節(jié)點(diǎn)被發(fā)明出來。部分研究者將ACO 用于了武器攻擊目標(biāo)分配和優(yōu)化問題、車輛運(yùn)行路徑規(guī)劃、區(qū)域性無線電頻率自動(dòng)分配Bayesian networks 的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問題。目前這方面的應(yīng)用研究仍在升溫，因?yàn)橥ㄐ啪W(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機(jī)動(dòng)態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與ACO的算法本質(zhì)和特性非常相似。同時(shí)根據(jù)信息素?fù)]發(fā)機(jī)制實(shí)現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。在該算法中，每只螞蟻就像蟻群優(yōu)化算法中一樣,根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應(yīng)用到其它組合優(yōu)化問題中。蟻群算法可以理解為一種特殊的強(qiáng)化學(xué)習(xí)算法。 課題國內(nèi)外研究的意義蟻群算法是一種仿生智能算法，它從現(xiàn)實(shí)生活中螞蟻尋食的過程得到啟發(fā)，采用概率選擇機(jī)制控制路徑的走向，同時(shí)也加入了隨著時(shí)間的延長，信息素?fù)]發(fā)的因子。隨著各種智能算法的相繼出現(xiàn)。將蟻群算法應(yīng)用于路由協(xié)議的設(shè)計(jì)中，利用蟻群算法的網(wǎng)絡(luò)分布式、個(gè)體簡單而群體智能表現(xiàn)出優(yōu)化等特點(diǎn)很好的均衡了網(wǎng)絡(luò)負(fù)載，延長了網(wǎng)絡(luò)壽命。無線傳感器網(wǎng)絡(luò)路由設(shè)計(jì)的指標(biāo)之一就是盡可能的節(jié)省能量，延長網(wǎng)絡(luò)壽命。本課題研究基于蟻群優(yōu)化zigbee路由算法，采用該算法提高網(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ò)的普及，人們對(duì)網(wǎng)絡(luò)的需求越來越豐富，對(duì)網(wǎng)絡(luò)技術(shù)的要求也越來越高。由于該網(wǎng)絡(luò)組網(wǎng)快速、靈活，抗毀性強(qiáng)，使用方便而且應(yīng)用范圍廣泛，因此是當(dāng)前網(wǎng)絡(luò)和通信技術(shù)領(lǐng)域的研究熱點(diǎn)之一。為了能夠在沒有固定基礎(chǔ)設(shè)施的地方進(jìn)行通信，一種被稱作Ad hoc(Mobile Ad Hoc Networks)網(wǎng)絡(luò)的技術(shù)應(yīng)運(yùn)而生。哈爾濱遠(yuǎn)東理工學(xué)院學(xué)士學(xué)位論文基于蟻群優(yōu)化的zigbee路由算法研究畢業(yè)論文 目 錄摘 要 IAbstract II目 錄 III第1章 緒 論 1 課題研究的目的和意義 1 課題國內(nèi)外研究的意義 1 國內(nèi)蟻群算法應(yīng)用現(xiàn)狀 1 國外蟻群算法研究現(xiàn)狀 2 課題研究內(nèi)容 3 本章小結(jié) 4第2章 無線網(wǎng)絡(luò)蟻群算法路由技術(shù) 5 蟻群算法簡介 5 蟻群算法基本概念 5 蟻群算法特點(diǎn) 6 蟻群算法基本數(shù)學(xué)模型 6 蟻群算法的實(shí)現(xiàn) 8 蟻群算法迭代過程 10 無線網(wǎng)絡(luò)蟻群算法路由技術(shù)分析 11 簡單相關(guān)路徑Zigbee路由算法概述 11 路由維護(hù)與信息素更改 11 基于蟻群算法的Zigbee路由研究與改進(jìn) 12 蟻群算法中信息素的更新原則 12 本章小結(jié) 12第3章 無線網(wǎng)絡(luò)蟻群優(yōu)化算法路由技術(shù) 13 蟻群優(yōu)化算法基本原理 13 蟻群優(yōu)化算法基本概念 13 蟻群優(yōu)化算法數(shù)學(xué)模型 13 蟻群優(yōu)化算法的值與點(diǎn)的收斂 14 蟻群優(yōu)化算法在路由中的應(yīng)用 14 蟻群算法中參數(shù)的最優(yōu)選擇 15 蟻群信息素?fù)]發(fā)度的選擇 15 蟻群數(shù)量的選擇 16 啟發(fā)因子的選擇 18 總信息量的選擇 18 本章小結(jié) 19第4章 實(shí)驗(yàn)分析與結(jié)果仿真 20 蟻群路由定義 20 蟻群優(yōu)化網(wǎng)絡(luò)算法流程 20 路由發(fā)現(xiàn) 20 路由選擇 21 路由維護(hù) 22 蟻群路由實(shí)現(xiàn)與結(jié)果仿真 22 本章小結(jié) 26第5章 課題研究中的難點(diǎn)及解決方法 27 有關(guān)螞蟻構(gòu)建過程與難點(diǎn)分析 27 基于遺傳算法的Zigbee路由研究與改進(jìn) 28 課題的可行性評(píng)估 29 本章小結(jié) 30結(jié) 論 31致 謝 32參考文獻(xiàn) 33附 錄 A 34附 錄 B 35附 錄 C 36I第1章 緒 論無線通信技術(shù)的迅速發(fā)展，使得人們對(duì)移動(dòng)通信的需求越來越強(qiáng)烈，人們通過配有無線接口的便攜式計(jì)算機(jī)或個(gè)人數(shù)字助理(PDA)來實(shí)現(xiàn)移動(dòng)中的通信，目前的移動(dòng)通信往往需要有固定基礎(chǔ)設(shè)施的支持才能實(shí)現(xiàn)，例如全球通信系統(tǒng)(GSM)。但是當(dāng)遇到醫(yī)療搶險(xiǎn)、抗洪救災(zāi)以及軍事戰(zhàn)場等特殊緊急環(huán)境的時(shí)候，傳統(tǒng)的無線網(wǎng)絡(luò)就不可用了。移動(dòng)Ad Hoc網(wǎng)絡(luò)是一種新的移動(dòng)無線網(wǎng)絡(luò)系統(tǒng)，它不需任何固定基站設(shè)施，節(jié)點(diǎn)之間的通信可借助于其他的移動(dòng)節(jié)點(diǎn)形成多跳通信完成。從研究內(nèi)容看，Ad Hoc的網(wǎng)絡(luò)層協(xié)議是研究的難點(diǎn)和重點(diǎn)，而Zigbee路由算法又是網(wǎng)絡(luò)層協(xié)議的核心技術(shù)問題。開始只是簡單的文字傳輸，而現(xiàn)在人們對(duì)視頻、音頻等多樣化實(shí)時(shí)傳輸有了更多的需求。蟻群算法顯示出它在無線傳感網(wǎng)絡(luò)路由方面的優(yōu)勢。這給傳感器網(wǎng)絡(luò)路由協(xié)議的設(shè)計(jì)提出了巨大挑戰(zhàn)。近年來引起了中外研究人員的廣泛關(guān)注，并且已逐漸成為當(dāng)前無線傳感器網(wǎng)絡(luò)路由設(shè)計(jì)研究領(lǐng)域的熱點(diǎn)。越來越多的學(xué)者將它們應(yīng)用于無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究中，而螞蟻尋找食物的行為與網(wǎng)絡(luò)中節(jié)點(diǎn)尋找路由的過程十分相似，因此基于蟻群算法的傳感器網(wǎng)路由協(xié)議得到了大量的關(guān)注。眾多的研究證明，蟻群算法具有很強(qiáng)的發(fā)現(xiàn)較好解的能力，該算法不僅利用了正反饋原理，在一定程度上加快了進(jìn)化過程，而且在本質(zhì)上也可并行實(shí)現(xiàn)，不同個(gè)體之間通過不斷的信息交流和傳遞，能夠相互協(xié)作，有利于發(fā)現(xiàn)較好解。 國內(nèi)蟻群算法應(yīng)用現(xiàn)狀隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，蟻群算法在離散求解空間問題中表現(xiàn)出良好的搜索效果。比較典型的應(yīng)用研究包括： 網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。HP公司和英國電信公司設(shè)計(jì)了蟻群路由算法。如果一只螞蟻因?yàn)榻?jīng)過了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對(duì)該表項(xiàng)做較大的增強(qiáng)。這樣，在當(dāng)前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時(shí)，ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、負(fù)荷量和利用率。ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應(yīng)用, 如二次規(guī)劃問題(QAP) 、機(jī)器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色(Graph Coloring) 等問題。Costa和Herz還提出了一種AS 在規(guī)劃問題方面的擴(kuò)展應(yīng)用圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。這種節(jié)點(diǎn)具有低成本、低功耗、多功能、體積小和短距離無線通信的特點(diǎn)，由這種節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)引起了人們越來越多的關(guān)注。目前來說，無線傳感器網(wǎng)絡(luò)路由算法已經(jīng)成為國內(nèi)外學(xué)者的一個(gè)研究熱點(diǎn)。這些改進(jìn)的路由算法在節(jié)省結(jié)點(diǎn)能源方面取得了很多進(jìn)展，但缺少對(duì)路徑全局尋優(yōu)方面的考慮，降低了WSN的整體吞吐量。有的文獻(xiàn)中提出了一種針對(duì)斯坦納樹的蟻群算法，該算法可被移植到WSN路由中。Zhang等人在研究了三種不同的基于螞蟻的WSN算法，然而，作者僅僅關(guān)注信息素初始分布的建立，在系統(tǒng)啟動(dòng)效率方面具有一定的優(yōu)勢。但是，該算法要求每個(gè)節(jié)點(diǎn)都必須配備有定位設(shè)備如GPS系統(tǒng)，很大程度上限制了它的適用范圍。媒介質(zhì)與其他的交流方式主要有兩點(diǎn)不同：首先，它是昆蟲間接感受周圍物質(zhì)世界的改變而釋放出來的物理的(physical)、非符號(hào)化(nonsymbolic)、非語言層次上的溝通媒介；其次，它只能被接觸到媒介質(zhì)的昆蟲感知，也就是它具有局部被感知的特性。， 等人在20世紀(jì)90年代初首先提出來的它是繼模擬退火算法、遺傳算法、禁忌搜索算法，人工神經(jīng)網(wǎng)絡(luò)算法后的有一種應(yīng)用于組合優(yōu)化問題的啟發(fā)式搜索算法。1979年，R．Hofstadter首次提出了人工螞蟻的概念，蟻群的鏈?zhǔn)椒磻?yīng)行為(autocatalytic behavior)或正反饋(positive feedback)特性受到越來越多的關(guān)注。從1991年到1996年，M Dorigo等人就蟻群搜索食物的過程與旅行商問題(TSP) 之間的相似性, 通過人工螞蟻搜索食物的過程做了一定的研究，先后提出了三種模型：antquantity, antdensity和antcycle。直到1996年，M Dorigo在發(fā)表了系統(tǒng)的關(guān)于螞蟻系統(tǒng)(AS)的全面論述，總結(jié)了這三種模型。2009年，P．Deepalakshmill 提出了ARMAN算法，在原有蟻群算法數(shù)學(xué)模型上，加入了路徑選擇偏好概率，通過偏好概率選擇移動(dòng)網(wǎng)絡(luò)中從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的多重路徑，最終得到的路徑時(shí)延更小、帶寬更高、抖動(dòng)更少。由于蟻群優(yōu)化算法具有正反饋性、分布式并行計(jì)算機(jī)制、較強(qiáng)的魯棒性等特點(diǎn) ，可用于求解基于分布式網(wǎng)絡(luò)的最優(yōu)路徑計(jì)算，如路由、負(fù)載平衡和計(jì)算機(jī)網(wǎng)絡(luò)中的多路傳輸?shù)确矫?。前向螞蟻只?fù)責(zé)收集關(guān)于交叉節(jié)點(diǎn)的ID信息，它在使用概率公式計(jì)算選擇下一跳節(jié)點(diǎn)的概率時(shí)只使用信息素值作為參數(shù)。在DAR中。這個(gè)概率值是通過以前螞蟻?zhàn)哌^時(shí)留下的信息素進(jìn)行計(jì)算的。 課題研究內(nèi)容無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network．WSN)是繼Internet之后隨著無線通信技術(shù)、傳感器技術(shù)、微電子技術(shù)和分布信息處理技術(shù)發(fā)展起來的一種新興信息獲取技術(shù)。在WSN中，每個(gè)傳感器結(jié)點(diǎn)的路由選擇過程和螞蟻的覓食尋優(yōu)行為具有極大的相似性，因此，利用蟻群優(yōu)化來設(shè)計(jì)WSN的路由算法具有理論上的可行性。蟻群算法是一種來自大自然的隨機(jī)搜索尋優(yōu)方法，是生物界的群體啟發(fā)式行為，現(xiàn)己陸續(xù)應(yīng)用到組合優(yōu)化、人工智能、通訊等多個(gè)領(lǐng)域。從數(shù)值仿真結(jié)果來看，它比目前風(fēng)行一時(shí)的遺傳算法、模擬退火算法等有更好的適應(yīng)性。目前，關(guān)于算法的參數(shù)選擇大都與具體問題的應(yīng)用結(jié)合，通過實(shí)驗(yàn)進(jìn)行確定，而算法的停止條件則采用固定循環(huán)次數(shù)或當(dāng)進(jìn)化不明顯時(shí)停止迭代作為條件。采用該算法并把該算法應(yīng)用于zigbee無線網(wǎng)絡(luò)中，平衡了zigbee網(wǎng)絡(luò)的缺點(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ù)不受延遲或丟棄。所以利用蟻群優(yōu)化的特點(diǎn)和優(yōu)勢提出了一種基于蟻群優(yōu)化的zigbee路由算法，根據(jù)zigbee路由策略和蟻群優(yōu)化的特點(diǎn)，構(gòu)造了人工螞蟻使算法具有較好的節(jié)能性和全局尋優(yōu)能力，并改善網(wǎng)絡(luò)的性能。 本章小結(jié)采用在無線傳感網(wǎng)絡(luò)路由方面顯示出獨(dú)特優(yōu)勢的蟻群優(yōu)化zigbee路由算法，可以提高網(wǎng)絡(luò)服務(wù)質(zhì)量，延長壽命，節(jié)省費(fèi)用。由于利用了正反饋原理，協(xié)同性以及隱含的并行性更使之具有極強(qiáng)的發(fā)展?jié)摿?，并且可以理解為一種特殊的強(qiáng)化學(xué)習(xí)算法。第2章 無線網(wǎng)絡(luò)蟻群算法路由技術(shù)生物界的昆蟲和其他群居動(dòng)物的群體智能，行為一直是科學(xué)家進(jìn)行科學(xué)研究的靈感源泉，隨著各學(xué)科門類的交叉綜合，群體智能已經(jīng)成為解決計(jì)算問題的新興的方法。從此，正反饋特性受到越來越多的關(guān)注。蟻群系統(tǒng)基本原理，人工蟻群系統(tǒng)(通常簡稱蟻群系統(tǒng))用于通過信息素痕跡和啟發(fā)信息的指引來構(gòu)造解。最初，螞蟻以隨機(jī)的方式探索蟻巢周圍的區(qū)域，一旦一只螞蟻找到食物源，它會(huì)評(píng)估食物的數(shù)量和質(zhì)量，并搬運(yùn)一些食物回到蟻巢。圖21 蟻群覓食源點(diǎn)到結(jié)點(diǎn)的路徑選擇對(duì)于一條路徑，選擇它的螞蟻越多，則在該路徑上螞蟻所留下的信息素的強(qiáng)度就越大，而強(qiáng)度大的信息素會(huì)吸引更多的螞蟻，從而形成一種正反饋。在ACO算法中，信息素軌跡通過一個(gè)被稱為信息素模型的參數(shù)化概率模型模擬。如圖所示, 螞蟻從A 點(diǎn)(蟻巢) 出發(fā), 速度相同, 目的地在D點(diǎn)(食物) , 可能隨機(jī)選擇路線ABD 或ACD。圖中下圖為經(jīng)過18 個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。 尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD 路線上增派一只螞蟻(共2只)，而ACD路線上仍然為一只螞蟻. 再經(jīng)過36個(gè)時(shí)間單位后, 兩條線路上的信息素單位積累為12 和4，比值為3B1。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24 和6，比值為4B1。這就是蟻群的自催化效應(yīng)。采用分布式路由決策，避免了在網(wǎng)絡(luò)中傳輸路由表，路徑維護(hù)在數(shù)據(jù)傳輸過程中自動(dòng)進(jìn)行，不需要使用額外的數(shù)據(jù)包和數(shù)據(jù)傳輸?shù)膫鬏斶^程來進(jìn)行路徑維護(hù)；(2)自適應(yīng)性好。每個(gè)節(jié)點(diǎn)有多個(gè)通向目標(biāo)的路徑，路經(jīng)的選擇取決于路徑的質(zhì)量，多路徑提高路由的可靠性；(4)支持休眠模式。 蟻群算法基本數(shù)學(xué)模型螞蟻具有找到蟻巢與食物之間最短路徑的能力。螞蟻在一條路徑上前進(jìn)時(shí)，會(huì)留下?lián)]發(fā)性分泌物，后來的螞蟻選擇該路徑的概率與當(dāng)時(shí)這條路徑上揮發(fā)性物質(zhì)強(qiáng)度成正比對(duì)于一條路徑，選擇它的螞蟻越多，則在該路徑上螞蟻所留下的分泌物的強(qiáng)度就越大。我們通過釋放人工螞蟻群來創(chuàng)建基于螞蟻算法的網(wǎng)絡(luò)模型，為了把通信網(wǎng)絡(luò)和螞蟻算法理論聯(lián)系起來，我們利用信息素表，如表21來取代網(wǎng)絡(luò)節(jié)點(diǎn)中的路由選擇表。 k d1 p11 p12 p2m d3 dm pn1 pn2 “信包素表”給出了以某個(gè)節(jié)點(diǎn)為目的節(jié)點(diǎn)時(shí)選擇下一節(jié)點(diǎn)的概率，同時(shí)表1中的概率值按照某種規(guī)則周期性地刷新：下面的公式給出了在節(jié)點(diǎn)u中的螞蟻k選擇到相鄰節(jié)點(diǎn)v的概率： (21)其中為鏈路上的“信息素”；為與節(jié)點(diǎn) 直接相連的所有節(jié)點(diǎn)的集合； = ，其中為鏈路的傳輸代價(jià)可能是鏈路的距離或鏈路的傳輸成本等；為鏈路上的剩余帶寬；和是決定時(shí)延和剩余帶寬相對(duì)重要的參數(shù)。螞蟻開始搜索的初始時(shí)刻，各條路徑上分布的信息量相等，即(C為常數(shù))。那么