【正文】 數(shù)據(jù)包轉(zhuǎn)發(fā)給節(jié)點(diǎn)，同時(shí)增加表項(xiàng)信息素值，通向目的路徑將因?yàn)閭魉蛿?shù)據(jù)包而被加強(qiáng)。 路由維護(hù)由于自組網(wǎng)節(jié)點(diǎn)的移動(dòng)性，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生改變，因而路由要連通必須進(jìn)行路由維護(hù)。其思想是每個(gè)節(jié)點(diǎn)周期性地向鄰節(jié)點(diǎn)廣播Hello報(bào)文。如果在給定時(shí)間t后，鄰節(jié)點(diǎn)還沒有收到確認(rèn)連接的Hello報(bào)文，則認(rèn)為該節(jié)點(diǎn)已經(jīng)與自己斷開連接，將自己路由表中所有以該節(jié)點(diǎn)為下一條節(jié)點(diǎn)的路由都設(shè)為失效狀態(tài)。AODV路由協(xié)議允許進(jìn)行本地鏈路修復(fù)，失效前一跳節(jié)點(diǎn)將啟動(dòng)路由發(fā)現(xiàn)過程，廣播RREQ以便建立新路由。如果在給定時(shí)問里能重新建立起有效路由，就接著發(fā)送數(shù)據(jù)；如果建立路由不成功，則向上游節(jié)點(diǎn)發(fā)送RERR。路由失敗后先進(jìn)行本地鏈路修復(fù)可以減少數(shù)據(jù)傳送的延時(shí)，提高數(shù)據(jù)包的發(fā)送率。 蟻群路由實(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è)節(jié)點(diǎn)的發(fā)送能耗660mw ，接收能耗395mw；所有節(jié)點(diǎn)的初始能量均相同，為1 000(J為能量單位)。目的節(jié)點(diǎn)要求數(shù)據(jù)源以2幀/s的速度發(fā)送數(shù)據(jù)．為了簡(jiǎn)化并加快能量的消耗，設(shè)網(wǎng)絡(luò)中傳輸?shù)乃袛?shù)據(jù)幀(包括探測(cè)螞蟻)大小均相同，為64K字節(jié)；。算法中，網(wǎng)絡(luò)中的信息素每每秒蒸發(fā)一次,節(jié)點(diǎn)能量每減少5J，啟動(dòng)一次剩余能量通知機(jī)制。對(duì)路徑最優(yōu)仿真，取；對(duì)能量均衡最優(yōu)仿真，取．我們分別對(duì)這兩種情況進(jìn)行比。即以第一個(gè)節(jié)點(diǎn)因能量耗盡(取低于10J)而死亡的時(shí)間為網(wǎng)絡(luò)壽命。 圖42 路徑最優(yōu)情況下能量消耗（T=1000s）圖43 能量均衡情況下能量消耗（T=1000s）上兩個(gè)圖分別是在路徑最優(yōu)和能量均衡最優(yōu)兩種情況下，仿真運(yùn)行1000s時(shí)的網(wǎng)絡(luò)能量消耗分布。從圖43中，我們發(fā)現(xiàn)最短路徑上的節(jié)點(diǎn)能量消耗很大。這是由于最短路徑上的節(jié)點(diǎn)被頻繁使用的原因。而不在最短路徑上的節(jié)點(diǎn)幾乎沒有消耗， 6J。這是初始階段螞蟻擴(kuò)散的時(shí)候產(chǎn)生的。最大最小能耗相差670J以上。從圖3中，我們發(fā)現(xiàn)能量消耗非常均勻， 4J， 6J，最大最小能耗相差只有1J左右。這是因?yàn)槟芰烤鈨?yōu)化時(shí)，路由選擇剩余能量多的節(jié)點(diǎn)，從而實(shí)現(xiàn)能量的均衡消耗。我們也看到能量均衡最優(yōu)情況下的平均能耗大于路徑最優(yōu)的情況。這是因?yàn)樵谀芰烤庾顑?yōu)情況下，傳輸數(shù)據(jù)使用較遠(yuǎn)路徑，增加轉(zhuǎn)發(fā)次數(shù)，從而增加能量消耗。圖44 路徑最優(yōu)情況下能量分布圖45 能量均衡最優(yōu)情況下剩余能量分布，實(shí)驗(yàn)中使用的AODV和DSR協(xié)議是NS內(nèi)置的。在網(wǎng)絡(luò)場(chǎng)景設(shè)置中，我嗯設(shè)定了20個(gè)固定節(jié)點(diǎn)和50個(gè)移動(dòng)節(jié)點(diǎn)。這些節(jié)點(diǎn)之間通過IEEE ，場(chǎng)景中有3個(gè)服務(wù)節(jié)點(diǎn)，而客戶端節(jié)點(diǎn)的數(shù)量會(huì)隨機(jī)改變，每個(gè)客戶節(jié)點(diǎn)以通過改變包的大小以形成網(wǎng)絡(luò)擁塞的場(chǎng)景。通過吞吐量、平均延遲、傳送率三個(gè)指標(biāo)來比較蟻群優(yōu)化路由算法與AODV和DSR算法的性能。 圖46 三種路由協(xié)議的吞吐量比較從圖中可明顯看出，DSR算法的吞吐量曲線置于最下方，不僅較低，且隨著網(wǎng)絡(luò)負(fù)載的增加幾乎沒有變化；AODV算法的吞吐量曲線居中，隨著網(wǎng)絡(luò)負(fù)載的增加吞吐量有所增加，但增長(zhǎng)緩慢；而AntRouting吞吐量曲線置于最上方，不僅較高，且隨著網(wǎng)絡(luò)負(fù)載的增加吞吐量增長(zhǎng)很快。三種算法當(dāng)網(wǎng)絡(luò)負(fù)載超過240 kbps以后，吞吐量呈衰減趨勢(shì)。圖47 三種路由協(xié)議的平均延遲比較當(dāng)網(wǎng)絡(luò)負(fù)載較低的時(shí)候，AODV協(xié)議和Ant Routing算法平均時(shí)延較短，而DSR時(shí)延比較長(zhǎng)。而隨著網(wǎng)絡(luò)負(fù)載的增加，DSR的平均延遲越來越大，但是AODV和AntRouting算法則變化不大。當(dāng)網(wǎng)絡(luò)負(fù)載較小時(shí)，AODV和Ant Routing算法能傳送超過90％的數(shù)據(jù)包。而隨著網(wǎng)絡(luò)負(fù)載的不斷增加，三種路由算法都表現(xiàn)了不同程度的傳送率性能下降，相對(duì)來說，DSR下降速度最快，AODV其次，Ant Routing算法要好一些。因此，通過吞吐量、平均延遲、傳送率三個(gè)指標(biāo)進(jìn)行比較，隨著網(wǎng)絡(luò)負(fù)載的增加，蟻群路由算法相比AODV和DSR有比較明顯的優(yōu)勢(shì)。圖48 三種路由協(xié)議的數(shù)據(jù)包的傳送率比較 本章小結(jié)針對(duì)移動(dòng)自組網(wǎng)提出了一種基于蟻群優(yōu)化的路由算法，該算法很好地利用了蟻群算法的自適應(yīng)性，能有效地承載移動(dòng)自組網(wǎng)的負(fù)載。在NS2平臺(tái)下的算法仿真表明，該算法在移動(dòng)自組網(wǎng)環(huán)境下表現(xiàn)了較好的性能，從吞吐量、平均延遲、傳送率三個(gè)指標(biāo)比較來看，比AODV和DSR的性能都要好。蟻群優(yōu)化方法的自組織、動(dòng)態(tài)和多路徑的特性使其特別適合應(yīng)用于無線傳感器網(wǎng)絡(luò)的路由．本文提出的基于蟻群優(yōu)化的能量均衡路由算法具有路由代價(jià)低、自適應(yīng)性好、支持多路徑和支持休眠模式等特點(diǎn)．仿真分析表明，該算法能有效實(shí)現(xiàn)節(jié)點(diǎn)能量的均衡消耗，采用能量均衡優(yōu)化與路徑優(yōu)化相比能顯著延長(zhǎng)網(wǎng)絡(luò)壽命．該算法能夠通過調(diào)整信息素濃度和局部啟發(fā)值的權(quán)重，在路徑和能量均衡方面進(jìn)行綜合優(yōu)化，以滿足各種不同應(yīng)用的需要。第5章 課題研究中的難點(diǎn)及解決方法本章主要是對(duì)過去幾個(gè)月中的制作論文過程的總結(jié)，蟻群算法有演變成蟻群優(yōu)化算法，甚至魚群算法，有它需要解決的難題。而本文主要是研究蟻群優(yōu)化算法在無線網(wǎng)絡(luò)中的應(yīng)用，基于無線網(wǎng)絡(luò)的不確定性，能耗低性，數(shù)據(jù)延遲性，我主要做出一下幾點(diǎn)。 有關(guān)螞蟻構(gòu)建過程與難點(diǎn)分析每只螞蟻都關(guān)聯(lián)一個(gè)叫做禁忌表(tabu list)的數(shù)據(jù)結(jié)構(gòu)，可記為，用于存儲(chǔ)到目前為止螞蟻已經(jīng)訪問過的結(jié)點(diǎn)編號(hào)，這樣可以防止螞蟻在一次環(huán)游中走重復(fù)的結(jié)點(diǎn)。這樣，禁忌表記錄了螞蟻的路徑痕跡，在一次環(huán)游結(jié)束時(shí)，禁忌表可用來計(jì)算出這只螞蟻的當(dāng)前解以及和解相關(guān)的估價(jià)信息(例如這條路徑的權(quán)值)。進(jìn)入下一個(gè)周期前，禁忌表又被清空，螞蟻進(jìn)入下一輪搜尋。從數(shù)據(jù)結(jié)構(gòu)觀點(diǎn)來看，是一個(gè)動(dòng)態(tài)增長(zhǎng)的向量，在路徑構(gòu)建過程中動(dòng)態(tài)增長(zhǎng)，而表示螞蟻k的禁忌表的第S個(gè)元素，例如螞蟻k后在當(dāng)前環(huán)游中的第S個(gè)經(jīng)過的結(jié)點(diǎn)。禁忌表通常用來定義提到過的鄰域結(jié)構(gòu)，它們之間的關(guān)系是： (51)在螞蟻構(gòu)建解過程中，除了要考慮螞蟻釋放信息素對(duì)于構(gòu)建的影響，還要考慮問題本身也就是圖的結(jié)構(gòu)，盡可能的把圖結(jié)構(gòu)本身信息加入到構(gòu)建因素中，實(shí)現(xiàn)了貪心式啟發(fā)信息和螞蟻群體智能的統(tǒng)一。因此，可以定義邊可視性為邊的權(quán)值的倒數(shù)，這個(gè)值依賴于問題本身的性質(zhì)，如在靜態(tài)TSP問題中，可視性是個(gè)常量。如何有效使用無線傳感器節(jié)點(diǎn)有限的能量來最大化網(wǎng)絡(luò)的壽命是無線傳感器網(wǎng)絡(luò)研究的重要問題及解決方法如下：網(wǎng)絡(luò)能量是否均衡消耗對(duì)網(wǎng)絡(luò)壽命有著決定性的影響。針對(duì)無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能量受限的特點(diǎn)，把蟻群優(yōu)化算法應(yīng)用于無線傳感器網(wǎng)絡(luò)，考慮通信路徑長(zhǎng)度和節(jié)點(diǎn)剩余能量等因素，提出具有能量意識(shí)，從多方面解決節(jié)點(diǎn)間的能耗不均衡問題。該算法在能耗不均衡和傳輸延遲等方面將有很大改進(jìn)，實(shí)現(xiàn)全網(wǎng)節(jié)點(diǎn)的能耗均衡，將有效延長(zhǎng)網(wǎng)絡(luò)生命期，減小傳輸時(shí)延。蟻群算法道路最優(yōu)規(guī)劃問題：螞蟻更傾向于走寬敞順暢的大道，有的路徑雖然短，但可能崎嶇不平、道路狹窄，因而需要較長(zhǎng)時(shí)間通過，全面考慮這些因素怎樣規(guī)劃出不僅路徑短而且省時(shí)的最優(yōu)路徑？針對(duì)這個(gè)問題要求對(duì)蟻群算法進(jìn)行優(yōu)化改進(jìn)， 在蟻群算法中，人工螞蟻在運(yùn)動(dòng)過程中會(huì)根據(jù)各路徑上的信息素軌跡量決定下一步的轉(zhuǎn)移方向，采用如下公式進(jìn)行選擇： (52)其中，表示人工螞蟻從轉(zhuǎn)移到節(jié)點(diǎn)的概率表示人工螞蟻下一步允許選擇的節(jié)點(diǎn)，禁忌表用來記錄人工螞蟻當(dāng)前走過的點(diǎn)，隨進(jìn)化過程作動(dòng)態(tài)調(diào)整，表示邊上的信息素濃度，表示節(jié)點(diǎn)相對(duì)節(jié)點(diǎn)的可見度，表示節(jié)點(diǎn)到節(jié)點(diǎn)的距離，和是 信息素濃度和控制可見度的權(quán)衡。 改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則為： (53)表示道路的寬敞，暢通程度，是道路的寬敞，暢通度的權(quán)衡，其余參數(shù)同基本蟻群算法。它是將m只螞蟻定位于起點(diǎn)，向目標(biāo)點(diǎn)靠攏，每個(gè)螞蟻使用改進(jìn)后的狀態(tài)（即從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)），直到最后終達(dá)到目標(biāo)，完成一條路徑導(dǎo)航。到節(jié)點(diǎn) (54)其中是一個(gè)參數(shù)，1表示在時(shí)刻和+之間信息素消逝程度。，表示在時(shí)刻和之間第k只螞蟻在路徑上留下的信息素量，表示在時(shí)刻和之間路徑上信息素增量。當(dāng)所有螞蟻完成各自路徑的選擇過程，必須對(duì)各邊上的信息素按公式作一次全局更新，此時(shí)為： (55)其中，F(xiàn)為目標(biāo)函數(shù)，路徑越優(yōu)，F(xiàn)值越小，該路徑上增加的信息素量就越多。蟻群算法中怎樣調(diào)和一味選取最近的結(jié)點(diǎn)而造成的易陷于局部最優(yōu)解的問題？在蟻群算法系統(tǒng)中，當(dāng)螞蟻從結(jié)點(diǎn)i選擇下一結(jié)點(diǎn)j，首先要比較禁忌表，然后再計(jì)算每個(gè)相鄰結(jié)點(diǎn)的轉(zhuǎn)移概率，這需要較長(zhǎng)的計(jì)算時(shí)間。而根據(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)來計(jì)算，例如距離從近到遠(yuǎn)的結(jié)點(diǎn)為，，；則選擇計(jì)算的結(jié)點(diǎn)，和。這樣既可有效地減少結(jié)點(diǎn)計(jì)算的數(shù)量，提高計(jì)算的速度。 基于遺傳算法的Zigbee路由研究與改進(jìn)遺傳算法是由美國的John Holland教授于1975年首先提出的一類仿生型優(yōu)化算法，具有大范圍快速全局搜索能力。與自然界相似，遺傳算法對(duì)求解問題的本身一無所知。遺傳算法是從代表問題可能潛在解集的種群開始的，而種群則由經(jīng)過基因編碼的一定數(shù)目的個(gè)體組成。每個(gè)個(gè)體實(shí)際上是染色體帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)(即基因型)是某種基因組合，它決定了個(gè)體形狀的外部表現(xiàn)。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(generation)演化產(chǎn)生出越來越好的近似解。在每一代進(jìn)化過程中，根據(jù)問題域中個(gè)體適應(yīng)度大小來挑選(selection)個(gè)體，借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉(erossover)和變異(mutation)，產(chǎn)生出代表新解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼(decoding)，可以作為問題近似最優(yōu)解，這就是遺傳算法基本思想。遺傳算法應(yīng)用于Zigbee路由問題需要確定以下要素：(1) 編碼規(guī)則：需要針對(duì)具體的物理模型提出合適的編碼方法；(2) 創(chuàng)建初始群體：即確定路徑解集；(3) 確定遺傳算子：即確定選擇、交叉、變異的方法；(4) 確定適應(yīng)度函數(shù)：即確定Zigbee路由是根據(jù)那些參數(shù)的優(yōu)化并確定參數(shù)。將傳統(tǒng)遺傳算法直接應(yīng)用于Zigbee路由選擇存在以下問題：(1) 傳統(tǒng)的編碼不能很好的反應(yīng)實(shí)際物理模型；(2) 簡(jiǎn)單的初始種群形成方法和交叉、變異操作容易產(chǎn)生非法路徑；(3) 通用的遺傳算法在解決Qos問題時(shí)具有單一約束上的困難。對(duì)于以上幾點(diǎn)現(xiàn)有的文獻(xiàn)已有很好的解決。但在已有的遺傳算法應(yīng)用于Zigbee路由的文獻(xiàn)中，選擇，交叉，變異的過程都是采用按概率隨機(jī)選擇的方法，這種方法具有多樣性好和全局性好的優(yōu)點(diǎn)，但針對(duì)具體的Zigbee路由問題具有以下缺點(diǎn)：(1) 每次迭代前需要遍歷所有父代個(gè)體，并計(jì)算每條染色體的概率，增加了算法復(fù)雜度；(2) 按概率隨機(jī)性選擇會(huì)存在統(tǒng)計(jì)誤差，導(dǎo)致一些本來優(yōu)秀的染色體丟失。由于本算法僅需要保存最優(yōu)的幾條路徑，對(duì)多樣性要求不高，針對(duì)Zigbee路由問題，解集多樣化固然重要，但減小Zigbee路由開銷和縮短Zigbee路由尋找時(shí)間才是最重要的，基于以上原因，本文擬對(duì)基本遺傳算法進(jìn)行改進(jìn)，提出一種確定性按比例遺傳算法，即按比例確定參與遺傳算子操作的個(gè)體。確定性選擇既保留了傳統(tǒng)遺傳算法可產(chǎn)生多樣化解集的優(yōu)點(diǎn)，又能保證算法可以以最快速度收斂到最優(yōu)，同時(shí)減小了算法的復(fù)雜度，具有易實(shí)施的優(yōu)點(diǎn)。 課題的可行性評(píng)估蟻群算法憑借其簡(jiǎn)單的算法結(jié)構(gòu)和突出的問題求解能力, 以及靈活、穩(wěn)定、分布式控制和自組織能力等特點(diǎn)，吸引了很多研究者, 并取得了令人注目的成果。該理論很適合于工程問題中日益復(fù)雜的信息處理需求，尤其是動(dòng)態(tài)特性突出的問題。然而, 由于其理論依據(jù)來源于對(duì)生物群落社會(huì)性的模擬, 因此其相關(guān)數(shù)學(xué)分析還比較薄弱, 這就導(dǎo)致了現(xiàn)有研究還存在以下幾個(gè)主要問題：(1) 蟻群算法的數(shù)學(xué)理論基礎(chǔ)薄弱, 缺乏普遍意義的理論性分析。算法中涉及的參數(shù)設(shè)置沒有確切的理論依據(jù), 一般按照經(jīng)驗(yàn)確定, 對(duì)具體問題的依賴性大；(2) 比較性研究不足, 與各種成熟的優(yōu)化算法之間的基本特性及性能特點(diǎn)的對(duì)比研究還不是十分充分。將來的研究工作應(yīng)加強(qiáng)算法特性的分析, 進(jìn)一步明確與算法原理相關(guān)的重要意義。如：?jiǎn)蝹€(gè)個(gè)體的復(fù)雜性、學(xué)習(xí)能力和推理能力等。還應(yīng)擴(kuò)展蟻群算法與其神經(jīng)網(wǎng)絡(luò)、禁忌搜索和支持向量機(jī)等先進(jìn)技術(shù)的融合, 以改善其自身的性能。作為一種新型的模擬進(jìn)化算法, 蟻群算法研究時(shí)間較短, 不像其他啟發(fā)式算法那樣具有系統(tǒng)的分析方法和堅(jiān)實(shí)的數(shù)學(xué)理論。揮發(fā)因子等參數(shù)的選擇基本是依靠實(shí)驗(yàn)和經(jīng)驗(yàn), 目前尚無通用及確定的理論方法來確定, 因此理論和實(shí)踐方面尚有許多問題需要更深入的研究與探討。 但是該算法的并行特性和強(qiáng)魯棒性等優(yōu)點(diǎn)吸引著許多學(xué)者不斷對(duì)其進(jìn)行深入研究。 隨著理論研究和實(shí)踐經(jīng)驗(yàn)的積累, 蟻群算法必將成為求解復(fù)雜組合優(yōu)化問題的高效算法。Ad hoc網(wǎng)絡(luò)在未來幾年有著極其誘人的前景和潛在的巨大市場(chǎng)。國內(nèi)外均有大量相關(guān)資料可供查閱，這些研究為迄今為止的Ad Hoc的Zigbee路由技術(shù)開發(fā)和系統(tǒng)設(shè)計(jì)提供了必要的參考依據(jù)和理論指導(dǎo)，也為本研究提供了豐富的基礎(chǔ)數(shù)據(jù)?，F(xiàn)在，螞蟻算法和遺傳算法受到廣泛關(guān)注，作為一種新興的仿生學(xué)算法由于其良好的并行性對(duì)解決完全問題起到了良好的效果。并在車間作業(yè)調(diào)度問題，聚類分析、車輛路徑問題等方面取得了一系列成果。尤其螞蟻算法在網(wǎng)絡(luò)Zigbee路由問題方面的研究與本課題學(xué)科領(lǐng)域相近，可為本課題在方法論和技術(shù)路線上提供指導(dǎo)。迄今為止，課題研究人一直從事螞蟻算法，遺傳算法以及Ad Ho