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