【正文】 在此我還要非常感謝我的父母，是他們含辛茹苦地養(yǎng)育了我，他們的樸實(shí)和奉獻(xiàn)將永存我的心里，衷心地祝福父母永遠(yuǎn)健康和快樂(lè)。在此特別表示感謝，使我的畢業(yè)設(shè)計(jì)有了個(gè)圓滿(mǎn)的結(jié)束。致 謝在論文完成之際，我非常感謝自己的恩師于鄭燦香老師，在論文的完成過(guò)程中一直以來(lái)對(duì)我的悉心指導(dǎo)和多方面的入微關(guān)懷與幫助。蟻群優(yōu)化作為一個(gè)啟發(fā)式搜索算法，具有分布性好、全局尋優(yōu)能力強(qiáng)、算法簡(jiǎn)單易實(shí)現(xiàn)等優(yōu)點(diǎn)。WSN的路由算法必須在節(jié)能的前提下，采用全局尋優(yōu)方式進(jìn)行路徑優(yōu)化，從而提高網(wǎng)絡(luò)的吞吞吐量。但有時(shí)缺少對(duì)路徑全局尋優(yōu)方面的考慮，降低了WSN的整體吞吐量。 由于一般網(wǎng)絡(luò)結(jié)點(diǎn)電池更換成本較高，因此要求每個(gè)結(jié)點(diǎn)都要最小化自身的能量消耗。由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的應(yīng)用環(huán)境以及傳感器節(jié)點(diǎn)的能量有限，使得設(shè)計(jì)高效的WSN路由協(xié)議受到了巨大挑戰(zhàn)，能耗問(wèn)題成了制約傳感器網(wǎng)絡(luò)發(fā)展的重要因素。WSN具有十分廣闊的應(yīng)用前景，能夠廣泛地應(yīng)用于軍事領(lǐng)域、環(huán)境監(jiān)測(cè)、醫(yī)療健康、智能家居、城市交通、空間探索和商業(yè)應(yīng)用等方面。本文將改進(jìn)的遺傳算法應(yīng)用到簡(jiǎn)單相關(guān)多路徑中，在目的節(jié)點(diǎn)搜索到路徑解集后，利用遺傳算法進(jìn)行優(yōu)化，通過(guò)選擇、交叉、變異的過(guò)程實(shí)現(xiàn)在不需要增加任何尋路開(kāi)銷(xiāo)的前提下對(duì)路徑優(yōu)化的目的。假設(shè)某一段時(shí)間的道路交通情況是不變的，而實(shí)際情況確是實(shí)時(shí)動(dòng)態(tài)變化的。 本章小結(jié)本章對(duì)解決全文的最優(yōu)路徑規(guī)劃問(wèn)題有重要的作用，先洗個(gè)長(zhǎng)度和通行時(shí)間的線(xiàn)性組合為目標(biāo)函數(shù)，不僅解決了時(shí)間最短問(wèn)題，還考慮到了螞蟻?zhàn)哌^(guò)路徑的期望程度。此外，本課題著重研究的內(nèi)容已取得階段性的成果，為課題的完成打下了基礎(chǔ)。尤其螞蟻算法在網(wǎng)絡(luò)Zigbee路由問(wèn)題方面的研究與本課題學(xué)科領(lǐng)域相近，可為本課題在方法論和技術(shù)路線(xiàn)上提供指導(dǎo)。現(xiàn)在，螞蟻算法和遺傳算法受到廣泛關(guān)注，作為一種新興的仿生學(xué)算法由于其良好的并行性對(duì)解決完全問(wèn)題起到了良好的效果。Ad hoc網(wǎng)絡(luò)在未來(lái)幾年有著極其誘人的前景和潛在的巨大市場(chǎng)。 但是該算法的并行特性和強(qiáng)魯棒性等優(yōu)點(diǎn)吸引著許多學(xué)者不斷對(duì)其進(jìn)行深入研究。作為一種新型的模擬進(jìn)化算法, 蟻群算法研究時(shí)間較短, 不像其他啟發(fā)式算法那樣具有系統(tǒng)的分析方法和堅(jiān)實(shí)的數(shù)學(xué)理論。如：?jiǎn)蝹€(gè)個(gè)體的復(fù)雜性、學(xué)習(xí)能力和推理能力等。算法中涉及的參數(shù)設(shè)置沒(méi)有確切的理論依據(jù), 一般按照經(jīng)驗(yàn)確定, 對(duì)具體問(wèn)題的依賴(lài)性大；(2) 比較性研究不足, 與各種成熟的優(yōu)化算法之間的基本特性及性能特點(diǎn)的對(duì)比研究還不是十分充分。該理論很適合于工程問(wèn)題中日益復(fù)雜的信息處理需求，尤其是動(dòng)態(tài)特性突出的問(wèn)題。確定性選擇既保留了傳統(tǒng)遺傳算法可產(chǎn)生多樣化解集的優(yōu)點(diǎn)，又能保證算法可以以最快速度收斂到最優(yōu)，同時(shí)減小了算法的復(fù)雜度，具有易實(shí)施的優(yōu)點(diǎn)。但在已有的遺傳算法應(yīng)用于Zigbee路由的文獻(xiàn)中，選擇，交叉，變異的過(guò)程都是采用按概率隨機(jī)選擇的方法，這種方法具有多樣性好和全局性好的優(yōu)點(diǎn)，但針對(duì)具體的Zigbee路由問(wèn)題具有以下缺點(diǎn)：(1) 每次迭代前需要遍歷所有父代個(gè)體，并計(jì)算每條染色體的概率，增加了算法復(fù)雜度；(2) 按概率隨機(jī)性選擇會(huì)存在統(tǒng)計(jì)誤差，導(dǎo)致一些本來(lái)優(yōu)秀的染色體丟失。將傳統(tǒng)遺傳算法直接應(yīng)用于Zigbee路由選擇存在以下問(wèn)題：(1) 傳統(tǒng)的編碼不能很好的反應(yīng)實(shí)際物理模型；(2) 簡(jiǎn)單的初始種群形成方法和交叉、變異操作容易產(chǎn)生非法路徑；(3) 通用的遺傳算法在解決Qos問(wèn)題時(shí)具有單一約束上的困難。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼(decoding)，可以作為問(wèn)題近似最優(yōu)解，這就是遺傳算法基本思想。初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(generation)演化產(chǎn)生出越來(lái)越好的近似解。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)(即基因型)是某種基因組合，它決定了個(gè)體形狀的外部表現(xiàn)。遺傳算法是從代表問(wèn)題可能潛在解集的種群開(kāi)始的，而種群則由經(jīng)過(guò)基因編碼的一定數(shù)目的個(gè)體組成。 基于遺傳算法的Zigbee路由研究與改進(jìn)遺傳算法是由美國(guó)的John Holland教授于1975年首先提出的一類(lèi)仿生型優(yōu)化算法，具有大范圍快速全局搜索能力。而根據(jù)ACO算法的原理，被選擇的結(jié)點(diǎn)通常為比較鄰近的結(jié)點(diǎn)，為了達(dá)到調(diào)和的目的，對(duì)于要計(jì)算轉(zhuǎn)移概率的結(jié)點(diǎn)，設(shè)為K個(gè)，按距離的遠(yuǎn)近取最近的10個(gè)連續(xù)的和次近的10個(gè)連續(xù)的結(jié)點(diǎn)計(jì)算概率，兩者相隔的距離為K/5，如K20則取所有的相鄰結(jié)點(diǎn)來(lái)計(jì)算，例如距離從近到遠(yuǎn)的結(jié)點(diǎn)為，；則選擇計(jì)算的結(jié)點(diǎn)，和。當(dāng)所有螞蟻完成各自路徑的選擇過(guò)程，必須對(duì)各邊上的信息素按公式作一次全局更新，此時(shí)為： (55)其中，F(xiàn)為目標(biāo)函數(shù)，路徑越優(yōu)，F(xiàn)值越小，該路徑上增加的信息素量就越多。到節(jié)點(diǎn) (54)其中是一個(gè)參數(shù)，1表示在時(shí)刻和+之間信息素消逝程度。 改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則為： (53)表示道路的寬敞，暢通程度，是道路的寬敞，暢通度的權(quán)衡，其余參數(shù)同基本蟻群算法。該算法在能耗不均衡和傳輸延遲等方面將有很大改進(jìn)，實(shí)現(xiàn)全網(wǎng)節(jié)點(diǎn)的能耗均衡，將有效延長(zhǎng)網(wǎng)絡(luò)生命期，減小傳輸時(shí)延。如何有效使用無(wú)線(xiàn)傳感器節(jié)點(diǎn)有限的能量來(lái)最大化網(wǎng)絡(luò)的壽命是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)研究的重要問(wèn)題及解決方法如下：網(wǎng)絡(luò)能量是否均衡消耗對(duì)網(wǎng)絡(luò)壽命有著決定性的影響。禁忌表通常用來(lái)定義提到過(guò)的鄰域結(jié)構(gòu)，它們之間的關(guān)系是： (51)在螞蟻構(gòu)建解過(guò)程中，除了要考慮螞蟻釋放信息素對(duì)于構(gòu)建的影響，還要考慮問(wèn)題本身也就是圖的結(jié)構(gòu)，盡可能的把圖結(jié)構(gòu)本身信息加入到構(gòu)建因素中，實(shí)現(xiàn)了貪心式啟發(fā)信息和螞蟻群體智能的統(tǒng)一。進(jìn)入下一個(gè)周期前，禁忌表又被清空，螞蟻進(jìn)入下一輪搜尋。 有關(guān)螞蟻構(gòu)建過(guò)程與難點(diǎn)分析每只螞蟻都關(guān)聯(lián)一個(gè)叫做禁忌表(tabu list)的數(shù)據(jù)結(jié)構(gòu)，可記為，用于存儲(chǔ)到目前為止螞蟻已經(jīng)訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)編號(hào)，這樣可以防止螞蟻在一次環(huán)游中走重復(fù)的結(jié)點(diǎn)。第5章 課題研究中的難點(diǎn)及解決方法本章主要是對(duì)過(guò)去幾個(gè)月中的制作論文過(guò)程的總結(jié)，蟻群算法有演變成蟻群優(yōu)化算法，甚至魚(yú)群算法，有它需要解決的難題。在NS2平臺(tái)下的算法仿真表明，該算法在移動(dòng)自組網(wǎng)環(huán)境下表現(xiàn)了較好的性能，從吞吐量、平均延遲、傳送率三個(gè)指標(biāo)比較來(lái)看，比AODV和DSR的性能都要好。因此，通過(guò)吞吐量、平均延遲、傳送率三個(gè)指標(biāo)進(jìn)行比較，隨著網(wǎng)絡(luò)負(fù)載的增加，蟻群路由算法相比AODV和DSR有比較明顯的優(yōu)勢(shì)。當(dāng)網(wǎng)絡(luò)負(fù)載較小時(shí)，AODV和Ant Routing算法能傳送超過(guò)90％的數(shù)據(jù)包。圖47 三種路由協(xié)議的平均延遲比較當(dāng)網(wǎng)絡(luò)負(fù)載較低的時(shí)候，AODV協(xié)議和Ant Routing算法平均時(shí)延較短，而DSR時(shí)延比較長(zhǎng)。 圖46 三種路由協(xié)議的吞吐量比較從圖中可明顯看出，DSR算法的吞吐量曲線(xiàn)置于最下方，不僅較低，且隨著網(wǎng)絡(luò)負(fù)載的增加幾乎沒(méi)有變化；AODV算法的吞吐量曲線(xiàn)居中，隨著網(wǎng)絡(luò)負(fù)載的增加吞吐量有所增加，但增長(zhǎng)緩慢；而AntRouting吞吐量曲線(xiàn)置于最上方，不僅較高，且隨著網(wǎng)絡(luò)負(fù)載的增加吞吐量增長(zhǎng)很快。這些節(jié)點(diǎn)之間通過(guò)IEEE ，場(chǎng)景中有3個(gè)服務(wù)節(jié)點(diǎn)，而客戶(hù)端節(jié)點(diǎn)的數(shù)量會(huì)隨機(jī)改變，每個(gè)客戶(hù)節(jié)點(diǎn)以通過(guò)改變包的大小以形成網(wǎng)絡(luò)擁塞的場(chǎng)景。圖44 路徑最優(yōu)情況下能量分布圖45 能量均衡最優(yōu)情況下剩余能量分布，實(shí)驗(yàn)中使用的AODV和DSR協(xié)議是NS內(nèi)置的。我們也看到能量均衡最優(yōu)情況下的平均能耗大于路徑最優(yōu)的情況。從圖3中，我們發(fā)現(xiàn)能量消耗非常均勻， 4J， 6J，最大最小能耗相差只有1J左右。這是初始階段螞蟻擴(kuò)散的時(shí)候產(chǎn)生的。這是由于最短路徑上的節(jié)點(diǎn)被頻繁使用的原因。 圖42 路徑最優(yōu)情況下能量消耗（T=1000s）圖43 能量均衡情況下能量消耗（T=1000s）上兩個(gè)圖分別是在路徑最優(yōu)和能量均衡最優(yōu)兩種情況下，仿真運(yùn)行1000s時(shí)的網(wǎng)絡(luò)能量消耗分布。對(duì)路徑最優(yōu)仿真，??；對(duì)能量均衡最優(yōu)仿真，?。覀兎謩e對(duì)這兩種情況進(jìn)行比。目的節(jié)點(diǎn)要求數(shù)據(jù)源以2幀/s的速度發(fā)送數(shù)據(jù)．為了簡(jiǎn)化并加快能量的消耗，設(shè)網(wǎng)絡(luò)中傳輸?shù)乃袛?shù)據(jù)幀(包括探測(cè)螞蟻)大小均相同，為64K字節(jié)；。 蟻群路由實(shí)現(xiàn)與結(jié)果仿真具體的仿真條件設(shè)為：在160m x 160m的正方形區(qū)域內(nèi)隨機(jī)散布200個(gè)節(jié)點(diǎn)；1個(gè)數(shù)據(jù)源節(jié)點(diǎn)位于(0，0)；1個(gè)目的節(jié)點(diǎn)位于(160，160)；節(jié)點(diǎn)的通信距離是40m。如果在給定時(shí)問(wèn)里能重新建立起有效路由，就接著發(fā)送數(shù)據(jù)；如果建立路由不成功，則向上游節(jié)點(diǎn)發(fā)送RERR。如果在給定時(shí)間t后，鄰節(jié)點(diǎn)還沒(méi)有收到確認(rèn)連接的Hello報(bào)文，則認(rèn)為該節(jié)點(diǎn)已經(jīng)與自己斷開(kāi)連接，將自己路由表中所有以該節(jié)點(diǎn)為下一條節(jié)點(diǎn)的路由都設(shè)為失效狀態(tài)。 路由維護(hù)由于自組網(wǎng)節(jié)點(diǎn)的移動(dòng)性，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生改變，因而路由要連通必須進(jìn)行路由維護(hù)。網(wǎng)絡(luò)初始化與路徑搜尋計(jì)算各節(jié)點(diǎn)的初始信息濃度與剩余能量是否目的節(jié)點(diǎn) YN計(jì)算、選擇下一節(jié)點(diǎn)選中的節(jié)點(diǎn)路徑信息素增強(qiáng)周期性T中斷 NY信息素?fù)]發(fā) 能量降低過(guò)閾值 NY將剩余能量通知鄰居傳送數(shù)據(jù)一次數(shù)據(jù)轉(zhuǎn)發(fā)結(jié)束圖41 算法流程圖 路由選擇在每個(gè)節(jié)點(diǎn)，代理基于該節(jié)點(diǎn)上的信息來(lái)決定如何采取行動(dòng)，每個(gè)節(jié)點(diǎn)記錄它的鄰居節(jié)點(diǎn)狀態(tài)有關(guān)的轉(zhuǎn)移概率的統(tǒng)計(jì)信息，每個(gè)節(jié)點(diǎn)維護(hù)著它的最佳路徑的當(dāng)前預(yù)估。源節(jié)點(diǎn)創(chuàng)建一個(gè)路由請(qǐng)求報(bào)文RREQ，并向其鄰節(jié)點(diǎn)廣播。該算法利用蟻群自適應(yīng)尋優(yōu)機(jī)制和螞蟻的分布式記憶機(jī)制進(jìn)行路徑的選擇和路由的維護(hù)，通過(guò)對(duì)數(shù)據(jù)傳輸路徑和節(jié)點(diǎn)剩余能量的組合優(yōu)化，實(shí)現(xiàn)網(wǎng)絡(luò)能量的均衡消耗，延長(zhǎng)網(wǎng)絡(luò)壽命。當(dāng)螞蟻從節(jié)點(diǎn) 移動(dòng)到節(jié)點(diǎn)時(shí)，根據(jù)下面的公式改變邊上的信息素?cái)?shù)量： (43)基于蟻群優(yōu)化的螞蟻路由算法有倆個(gè)階段，分別是路由發(fā)現(xiàn)、路由選擇與路由維護(hù)。選擇概率用式下面來(lái)表示： (41)其中：，目的是控制螞蟻的探索行為。蟻群優(yōu)化被用來(lái)尋找圖G中節(jié)點(diǎn)Vi到目的節(jié)點(diǎn)的最短路徑，每條邊都有一個(gè)信息素變量。目前，該算法已經(jīng)在基金會(huì)現(xiàn)場(chǎng)總線(xiàn)控制系統(tǒng)中得到了應(yīng)用，取得了良好的效果。第4章 實(shí)驗(yàn)分析與結(jié)果仿真本章針對(duì)傳統(tǒng)算法的缺點(diǎn)，提出了基于讀寫(xiě)特征的總線(xiàn)分布式同步算法。這些行為仍舊啟發(fā)計(jì)算機(jī)科學(xué)家和機(jī)器人專(zhuān)家去設(shè)計(jì)其他的螞蟻算法。通常在計(jì)算機(jī)科學(xué)中通常采用模擬仿真的手段，借助數(shù)學(xué)和編程手段，實(shí)現(xiàn)了從真實(shí)蟻群到人工蟻群的轉(zhuǎn)變，設(shè)計(jì)出了簡(jiǎn)單蟻群優(yōu)化算法，從而為設(shè)計(jì)更精確更有效的基于群體的算法打下了基礎(chǔ)。以上文所列TSP問(wèn)題為研究對(duì)象, 有關(guān)算法參數(shù)取為：螞蟻群體數(shù), 信息素殘留常數(shù), 信息啟發(fā)因子, 期望啟發(fā)因子, 運(yùn)算的停止條件為相鄰兩次循環(huán)搜索中最優(yōu)解的差別小于0. 001, 使螞蟻循環(huán)一周所釋放的總信息量分別為Q ={ 1, 10, 100} 。由于在蟻群算法中各個(gè)算法參數(shù)的作用實(shí)際上是緊密耦合的, 其中對(duì)算法性能起著主要作用的應(yīng)該是信息啟發(fā)式因子、期望啟發(fā)式因子和信息殘留常數(shù)等3個(gè)參數(shù). 總信息量Q對(duì)算法性能的影響則有賴(lài)于上述三個(gè)參數(shù)的配置, 以及算法模型的選取, 比如在ant cycle 模型和ant density 模型中, 總信息量Q對(duì)算法性能的影響情況顯然有較大的差異。啟發(fā)式因子和對(duì)算法性能影響的仿真結(jié)果如下表所示：表32 總信息量對(duì)算法性能影響因子α因子β最優(yōu)路徑長(zhǎng)度搜索循環(huán)次數(shù) 194 759654從仿真實(shí)驗(yàn)結(jié)果不難看出，蟻群算法中啟發(fā)式因子及的不同選取對(duì)算法性能有極大的影響好的搜索結(jié)果：適當(dāng)?shù)倪x擇??及??的取值范圍，此時(shí)即便參數(shù)的組合有所不同(如在本文的問(wèn)題中,取1. 5 左右, 取0. 5 ~ 5)，蟻群算法均能獲得較好的搜索結(jié)果, 算法的循環(huán)次數(shù)少( 即收斂速度快)，并且性能非常接近。關(guān)于蟻群算法中啟發(fā)式因子及對(duì)算法性能的影響及其在實(shí)際應(yīng)用中的選擇, 也可以通過(guò)計(jì)算機(jī)仿真實(shí)驗(yàn)來(lái)分析和確定。蟻群算法的全局尋優(yōu)性能，首先要求蟻群的搜索過(guò)程必須有很強(qiáng)的隨機(jī)性；而蟻群算法的快速收斂性能, 又要求蟻群的搜索過(guò)程必須要有較高的確定性。關(guān)于蟻群算法中螞蟻數(shù)量m的選擇，也應(yīng)該綜合考慮算法的全局搜索能力和收斂速度兩項(xiàng)指標(biāo)，針對(duì)具體問(wèn)題的應(yīng)用條件和實(shí)際要求，在全局搜索能力和收斂速度兩方面作出合理或折中的選擇。以上文所列TSP 問(wèn)題為研究對(duì)象, 有關(guān)算法參數(shù)取為：螞蟻循環(huán)一周所釋放的總信息量Q = 1, 信息素殘留常數(shù), 信息啟發(fā)式因子, 期望啟發(fā)式因子，運(yùn)算的停止條件為相鄰兩次循環(huán)搜索中最優(yōu)解的差別小于0. 001, 并使螞蟻數(shù)量的變化為m={ 2, 3, 4,5, 6, 7}。 蟻群在搜索過(guò)程中之所以表現(xiàn)出復(fù)雜而有序的行為, 個(gè)體之間的信息交流與相互協(xié)作起著至關(guān)重要的作用。 所以本文認(rèn)為, 在蟻群算法中信息素?fù)]發(fā)度的選擇宜取為 (即= 0. 7) 。因而, 關(guān)于蟻群算法中信息素?fù)]發(fā)度的選擇, 必須綜合考慮算法的全局搜索能力和收斂速度兩項(xiàng)性能指標(biāo), 針對(duì)具體問(wèn)題的應(yīng)用條件和實(shí)際要求, 在全局搜索能力和收斂速度兩方面作出合理或折中的選擇。在算法模型中用參數(shù)表示信息消逝程度(或稱(chēng)信息素?fù)]發(fā)度) ，而就是信息素殘留系數(shù)。關(guān)于蟻群算法中信息素?fù)]發(fā)度對(duì)算法性能的影響及其在實(shí)際應(yīng)用中的選擇，可以通過(guò)計(jì)算機(jī)仿真實(shí)驗(yàn)來(lái)分析和確定。 蟻群算法中參數(shù)的最優(yōu)選擇蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。但如果頻繁使用同一條路徑傳輸數(shù)據(jù)，就會(huì)使這些路徑上的