電系統(tǒng)（Micro-Electro-Mechanism System, MEMS）、片上系統(tǒng)（SOC， System on Chip）、無(wú)線通信和低功耗嵌入式技術(shù)的飛速發(fā)展，孕育出無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks, WSN），并以其低功耗、低成本、分布式和自組織的特點(diǎn)帶來(lái)了信息感知的一場(chǎng)變革。無(wú)線傳感器網(wǎng)絡(luò)就是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過無(wú)線通信方式形成的一個(gè)多跳自組織網(wǎng)絡(luò)。

　　隨著無(wú)線通信技術(shù)、電子技術(shù)、傳感器技術(shù)和微電系統(tǒng)的飛速發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)的研究越來(lái)越受到人們的重視。傳感器網(wǎng)絡(luò)是由部署在觀測(cè)環(huán)境內(nèi)的大量微型傳感器節(jié)點(diǎn)通過無(wú)線通信方式組成的一種無(wú)線網(wǎng)絡(luò)。組成傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)包括傳感器和匯聚節(jié)點(diǎn)（Sink）。傳感器節(jié)點(diǎn)的能量十分有限，并且在部署后難以再次補(bǔ)充能量，因此傳感器網(wǎng)絡(luò)存在嚴(yán)重的能量約束問題。

　　參考文獻(xiàn)2提出一種無(wú)線傳感器網(wǎng)絡(luò)AODV（Ad hoc On-Dernand Distance Vector）路由協(xié)議改進(jìn)方案，通過改進(jìn)RREQ協(xié)議幀，使節(jié)點(diǎn)的剩余能量值參與到路徑中，優(yōu)化RREQ洪泛傳播。但該算法是基于單路徑數(shù)據(jù)傳輸，沒有考慮節(jié)點(diǎn)的負(fù)載狀況，節(jié)點(diǎn)容易產(chǎn)生擁塞，導(dǎo)致數(shù)據(jù)包的重傳或數(shù)據(jù)丟失的情況。參考文獻(xiàn)3提出了一種基于蟻群優(yōu)化的路由算法ARAWSN（ACO-Based Routing Algorithm for Wireless Sensor Networks），該算法在定向擴(kuò)散協(xié)議的基礎(chǔ)上，通過搜尋螞蟻以廣播的方式在網(wǎng)絡(luò)中擴(kuò)散建立起源節(jié)點(diǎn)到目的節(jié)點(diǎn)的多條路徑的路由表。利用蟻群算法的轉(zhuǎn)移概率的方式來(lái)進(jìn)行路徑的選擇，從而平衡網(wǎng)絡(luò)中節(jié)點(diǎn)能量的消耗。該算法建立了所有到目的節(jié)點(diǎn)的路徑，存在很大的冗余，影響網(wǎng)絡(luò)的實(shí)時(shí)性，且在路由建立過程中采用洪泛的方式導(dǎo)致網(wǎng)絡(luò)的路由開銷比較大。參考文獻(xiàn)4綜合考慮了均衡傳輸能量消耗和節(jié)點(diǎn)剩余能量，提出了多種群蟻群優(yōu)化路由算法MACO（Multi Ant Colony Optimization）。該算法優(yōu)化了基本蟻群算法的螞蟻前向移動(dòng)的選擇概率模型，同時(shí)利用多種群獲得多條優(yōu)化路徑。但該算法需要進(jìn)行多次迭代，且可能陷入局部解，影響網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性。

　　針對(duì)上述路由算法及其存在的不足，本文提出了基于蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)按需多路節(jié)能路由算法MP-ACA（On-demand Multi-path and Power-saving Ant Colony Algorithm）。該算法結(jié)合蟻群算法和AODV路由協(xié)議，能夠在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立起多條鏈路不相關(guān)路由，并改善了蟻群算法在無(wú)線傳感器網(wǎng)絡(luò)中查找路由的多次迭代的策略，有效地減少了擁塞頻率、降低了路由的開銷，同時(shí)均衡了節(jié)點(diǎn)的能量開銷，延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

　　1 蟻群算法簡(jiǎn)介

　　蟻群算法（ant colony optimization, ACO），又稱螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來(lái)源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。針對(duì)PID控制器參數(shù)優(yōu)化設(shè)計(jì)問題，將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)行了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價(jià)值。

　　1.1 基本蟻群算法原理

　　蟻群算法ACA（Ant Colony Algorithm）是一種模擬昆蟲王國(guó)中螞蟻群體智能行為的仿生優(yōu)化算法，其基本原理可大致描述如下：自然界螞蟻會(huì)在所經(jīng)過的路徑上釋放一定的信息素，后來(lái)的螞蟻會(huì)根據(jù)信息素強(qiáng)度來(lái)選擇路徑，信息素強(qiáng)度越大的路徑被選擇的概率越大，于是就形成了一種正反饋機(jī)制，終螞蟻會(huì)選擇信息素的短路徑。蟻群算法通過釋放“人工螞蟻”來(lái)模擬自然螞蟻的行為以完成上述的選優(yōu)過程。

　　1.2 蟻群算法

　　根據(jù)螞蟻覓食的基本原理，科學(xué)家們?cè)O(shè)計(jì)了尋找路徑的蟻群算法，其主要步驟為：

　　2 按需多路節(jié)能路由算法設(shè)計(jì)

　　針對(duì)無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)多跳傳輸、節(jié)點(diǎn)能量有限等特性，本文對(duì)基本蟻群算法和MACO算法進(jìn)行改進(jìn)，并結(jié)合AODV路由協(xié)議，賦予螞蟻新的特性和路徑搜索方式。下面介紹本文研究中使用的相關(guān)定義。

　　定義1：從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑搜索螞蟻稱作前向螞蟻，它執(zhí)行路徑搜索功能，并建立反向信息素表。

　　定義2：前向螞蟻到達(dá)目的節(jié)點(diǎn)后，從目的節(jié)點(diǎn)返回到源節(jié)點(diǎn)的螞蟻稱作后向螞蟻，它執(zhí)行信息素更新功能，并建立路由表。

　　定義3：前向螞蟻在路徑搜索過程中，到達(dá)某一節(jié)點(diǎn)后建立的指向源節(jié)點(diǎn)的路由表稱作反向信息素表，該表包括源節(jié)點(diǎn)、下一個(gè)節(jié)點(diǎn)、反向節(jié)點(diǎn)信息素τ（j，i）。

　　2.1 算法設(shè)計(jì)思想

　　MP-ACA算法在Ant-Net算法的基礎(chǔ)上，將螞蟻分為前向螞蟻和后向螞蟻。為了實(shí)現(xiàn)不同節(jié)點(diǎn)的能量消耗均衡，MP-ACA算法中，將前向螞蟻要訪問的節(jié)點(diǎn)的剩余能量作為影響信息素濃度的一個(gè)參數(shù)。MP-ACA算法通過m只前向螞蟻同時(shí)獨(dú)立地進(jìn)行路徑搜索，并建立反向信息素表。當(dāng)每個(gè)前向螞蟻到達(dá)目的節(jié)點(diǎn)時(shí)，它們將立即轉(zhuǎn)化成一個(gè)后向螞蟻，后向螞蟻根據(jù)反向信息素表反向回到源節(jié)點(diǎn)后路由建立完畢，建立起信息素路由表以代替?zhèn)鹘y(tǒng)的網(wǎng)絡(luò)節(jié)點(diǎn)路由表，并采用一種新的信息素規(guī)則進(jìn)行信息素更新。同時(shí)MP-ACA算法在極大-極小蟻群算法上將各條路徑上的信息素濃度限制在[τmin，τmax]之間，τmin可以有效地避免算法停滯，τmax避免某條路徑上的信息素遠(yuǎn)大于其他路徑，使所有的螞蟻都集中到同一條路徑上面，限制算法的擴(kuò)散。在MP-ACA算法中，前向螞蟻轉(zhuǎn)移規(guī)則、信息素更新規(guī)則詳細(xì)設(shè)計(jì)如下。

　　2.2 前向螞蟻轉(zhuǎn)移規(guī)則

　　為了均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗，MP-ACA算法在蟻群算法的基礎(chǔ)上，新加入兩節(jié)點(diǎn)間的剩余能量因子改進(jìn)前向螞蟻轉(zhuǎn)移規(guī)則。改進(jìn)后的算法在螞蟻尋找短路徑的同時(shí)受到了節(jié)點(diǎn)能量消耗的限制。MP-ACA算法中處于節(jié)點(diǎn)i的螞蟻k選擇下一節(jié)點(diǎn)j進(jìn)行訪問的概率pkij使用以下公式確定：

　　式中，W（ j）是節(jié)點(diǎn)j的剩余能量；JK（i）代表了位于節(jié)點(diǎn)i的前向螞蟻k允許訪問的鄰居節(jié)點(diǎn)集合。在這里定義滿足以下兩個(gè)要求的節(jié)點(diǎn)j將會(huì)屬于JK（i）：（1）節(jié)點(diǎn)j還未被螞蟻k訪問；（2）節(jié)點(diǎn)j比前一節(jié)點(diǎn)i距離目的節(jié)點(diǎn)更近，且距離源節(jié)點(diǎn)更遠(yuǎn)。

　　MP-ACA算法采用改進(jìn)的轉(zhuǎn)移規(guī)則，簡(jiǎn)化了MACO算法使得MP-ACA更適用于無(wú)線傳感器網(wǎng)絡(luò)。同時(shí)前向螞蟻在尋找路徑的同時(shí)受到了節(jié)點(diǎn)能量消耗的限制，平衡了節(jié)點(diǎn)的能量消耗。

    2.3蟻群算法的實(shí)現(xiàn)

　　下面的程序開始運(yùn)行之后，螞蟻們開始從窩里出動(dòng)了，尋找食物；他們會(huì)順著屏幕爬滿整個(gè)畫面，直到找到食物再返回窩。

　　其中，‘F’點(diǎn)表示食物，‘H’表示窩，白色塊表示障礙物，‘+’就是螞蟻了。

　　參數(shù)說明：

　　信息素：螞蟻在一開始擁有的信息素總量，越大表示程序在較長(zhǎng)一段時(shí)間能夠存在信息素。信息素消減的速度：隨著時(shí)間的流逝，已經(jīng)存在于世界上的信息素會(huì)消減，這個(gè)數(shù)值越大，那么消減的越快。

　　錯(cuò)誤概率表示這個(gè)螞蟻不往信息素的區(qū)域走的概率，越大則表示這個(gè)螞蟻越有創(chuàng)新性。

　　速度半徑表示螞蟻能走的長(zhǎng)度，也表示這個(gè)螞蟻的感知范圍。

　　記憶能力表示螞蟻能記住多少個(gè)剛剛走過點(diǎn)的坐標(biāo)，這個(gè)值避免了螞蟻在本地打轉(zhuǎn)，停滯不前。而這個(gè)值越大那么整個(gè)系統(tǒng)運(yùn)行速度就慢，越小則螞蟻越容易原地轉(zhuǎn)圈。

　　2.3 信息素更新規(guī)則

　　如果節(jié)點(diǎn)i，j是前向螞蟻k選擇路徑上的相鄰節(jié)點(diǎn)，當(dāng)每個(gè)前向螞蟻到達(dá)目的節(jié)點(diǎn)時(shí)，它們將通過式（5）、式（6）來(lái)調(diào)節(jié)。對(duì)前向螞蟻到達(dá)目的節(jié)點(diǎn)后立即轉(zhuǎn)化成一個(gè)后向螞蟻，并且它將沿著反向信息素表回到源節(jié)點(diǎn)。中間節(jié)點(diǎn)收到后向螞蟻時(shí)，將按照式（5）、式（7）更新相鄰節(jié)點(diǎn)信息素強(qiáng)度。

　　MP-ACA算法改進(jìn)了MACO算法信息素更新規(guī)則，可以加快搜索路徑的速度，提高網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性，同時(shí)更進(jìn)一步平衡了網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗。

　　2.4 MP-ACA算法步驟

　　（1）初始化時(shí)，Sink節(jié)點(diǎn)跳數(shù)設(shè)置為0，其他節(jié)點(diǎn)跳數(shù)設(shè)置為100。Sink節(jié)點(diǎn)在全網(wǎng)范圍內(nèi)廣播跳數(shù)廣播報(bào)文，該報(bào)文包括數(shù)據(jù)包類型、距Sink節(jié)點(diǎn)跳數(shù)、剩余能量和源地址。該報(bào)文初始值為：跳數(shù)為0，源地址為0。中間節(jié)點(diǎn)收到該報(bào)文后，保存報(bào)文中節(jié)點(diǎn)的地址、跳數(shù)和能量狀態(tài)。如果收到的報(bào)文中跳數(shù)小于節(jié)點(diǎn)自身的跳數(shù)，則將自身的跳數(shù)設(shè)置為報(bào)文中的跳數(shù)加1，并轉(zhuǎn)發(fā)自己新的跳數(shù)信息和能量信息的報(bào)文，否則不廣播。 節(jié)點(diǎn)在轉(zhuǎn)發(fā)該報(bào)文的過程中收集、存儲(chǔ)鄰居節(jié)點(diǎn)相關(guān)信息，終在全網(wǎng)內(nèi)建立了到Sink節(jié)點(diǎn)的跳數(shù)信息。

　?。?）路徑搜索初始時(shí)，賦予每條路徑上相等數(shù)量的初始信息素τ0，本文設(shè)置為信息素濃度下限τmin。

　?。?）路徑搜索開始時(shí)，m只前向螞蟻從源節(jié)點(diǎn)S處出發(fā)，前向螞蟻所要攜帶的信息有：源節(jié)點(diǎn)ID號(hào)、目的節(jié)點(diǎn)ID號(hào)、節(jié)點(diǎn)i到節(jié)點(diǎn)j的信息素強(qiáng)度τ（i，j）、經(jīng)過節(jié)點(diǎn)的剩余能量的總和以及當(dāng)前總跳數(shù)。

　　（4）位于節(jié)點(diǎn)i的前向螞蟻k，依據(jù)轉(zhuǎn)移規(guī)則從相鄰的下一跳節(jié)點(diǎn)集合中選擇一個(gè)節(jié)點(diǎn)，并根據(jù)式（5）、式（6）更新路徑上信息素強(qiáng)度。

　?。?）當(dāng)中間節(jié)點(diǎn)j收到來(lái)自鄰居節(jié)點(diǎn)的螞蟻節(jié)點(diǎn)時(shí)：①更新前向螞蟻搜索包跳數(shù)h（i）=h（i）+1，i∈[1，m]。如果前向螞蟻沒有到達(dá)目的節(jié)點(diǎn)，且h<hmax，則轉(zhuǎn)入下一步，否則丟棄該數(shù)據(jù)包；②檢查自己是否比節(jié)點(diǎn)i距離目的節(jié)點(diǎn)更近，且距離源節(jié)點(diǎn)更遠(yuǎn)。若是，轉(zhuǎn)入下一步，否則簡(jiǎn)單丟棄；③然后檢查是否已收到同一目的節(jié)點(diǎn)前向螞蟻搜索包。若是，則此節(jié)點(diǎn)只接收早到達(dá)而且信息素的前向螞蟻搜索包，將其余的丟棄。當(dāng)前向螞蟻從節(jié)點(diǎn)i到達(dá)節(jié)點(diǎn)j后，根據(jù)前向螞蟻所攜帶的信息值建立到源節(jié)點(diǎn)的反向點(diǎn)信息素表，跳轉(zhuǎn)到第（4）步。

　　（6）當(dāng)每個(gè)前向螞蟻到達(dá)目的節(jié)點(diǎn)時(shí)，它們將立即轉(zhuǎn)化成一個(gè)后向螞蟻，并且它將沿著反向信息素表回到源節(jié)點(diǎn)。中間節(jié)點(diǎn)收到后向螞蟻數(shù)據(jù)包時(shí)，按照式（5）、式（7）將更新相鄰節(jié)點(diǎn)信息素強(qiáng)度，并建立到目的節(jié)點(diǎn)的路由表，路由表是一個(gè)三元組包括：目的節(jié)點(diǎn)、下一個(gè)節(jié)點(diǎn)、信息素。

　?。?）后向螞蟻到達(dá)源節(jié)點(diǎn)后路由建立完畢。

　　2.5 網(wǎng)絡(luò)的維護(hù)

　　在無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的故障和能量的耗盡都將導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，這使得路由維護(hù)顯得十分重要。路由斷路和節(jié)點(diǎn)能量的消耗是路由維護(hù)中必須解決的兩個(gè)關(guān)鍵問題。

　?。?）路由斷路。當(dāng)中間節(jié)點(diǎn)發(fā)現(xiàn)路徑不通或收到路由斷路的消息后，它首先根據(jù)斷路的路徑信息刪除自己對(duì)應(yīng)的路由表?xiàng)l目，然后查詢可能性路由表?xiàng)l目，看是否能找到到達(dá)同一目的地的其他路徑。如果有，則根據(jù)路由表中信息素的條目作為的路徑進(jìn)行通信；如果沒有到達(dá)對(duì)應(yīng)目的地的可選路徑后，即向其他節(jié)點(diǎn)繼續(xù)發(fā)送路由斷路消息。當(dāng)源節(jié)點(diǎn)在通信完成前收到路由斷路消息后，如果沒有到目的地的其他路徑，則將發(fā)起新的路徑探索過程，直到通信完成。

　?。?）節(jié)點(diǎn)能量的消耗。為了不頻繁地重建路由表，節(jié)省能量，MP-ACA算法根據(jù)每個(gè)節(jié)電的剩余能量自動(dòng)更新路由表，這樣就使得節(jié)點(diǎn)的能耗盡可能保持平衡。節(jié)點(diǎn)能量每下降10%，節(jié)點(diǎn)就會(huì)向周圍節(jié)點(diǎn)廣播自己的剩余能量，收到廣播的節(jié)點(diǎn)用式（8）更新路由表：

　　3.1 接收到數(shù)據(jù)包的平均延時(shí)

　　圖1反映了三種算法網(wǎng)絡(luò)傳輸數(shù)據(jù)的平均傳輸延時(shí)隨時(shí)間的變化關(guān)系。由圖可知，各算法的時(shí)延呈現(xiàn)先降后增的趨勢(shì)，主要是由于網(wǎng)絡(luò)剛建立時(shí)，節(jié)點(diǎn)需要建立路由表，然后時(shí)延呈下降趨勢(shì)。網(wǎng)絡(luò)運(yùn)行一段時(shí)間后，由于網(wǎng)絡(luò)中部分節(jié)點(diǎn)死亡，導(dǎo)致路由的重建，致使時(shí)延呈上升趨勢(shì)?？偟膩?lái)說，MP-ACA的平均傳輸延時(shí)要小于MACO和ACA的平均傳輸延遲，主要是因?yàn)樵贛ACO和ACA其路由是通過多次迭代而建立起來(lái)的，需要的時(shí)間長(zhǎng)，從而增加了網(wǎng)絡(luò)延時(shí)。

　　3.2 能量不為零的節(jié)點(diǎn)數(shù)目

　　圖2反映了三種算法在整個(gè)網(wǎng)絡(luò)時(shí)間內(nèi)能量不為零的節(jié)點(diǎn)數(shù)目隨時(shí)間的變化關(guān)系。由圖可知，節(jié)點(diǎn)一直運(yùn)行到110 s的時(shí)候，三種算法下有效的節(jié)點(diǎn)數(shù)目都為總的節(jié)點(diǎn)數(shù)目，但隨著時(shí)間的推移，由于ACA算法沒有考慮到節(jié)點(diǎn)剩余能量的情況，造成了某些節(jié)點(diǎn)耗能不均衡而過早的能量耗盡。

　　蟻群算法作為一種新的仿生優(yōu)化算法，具有分布計(jì)算、信息正反饋和啟發(fā)式搜索等特點(diǎn)。本文在對(duì)現(xiàn)有無(wú)線傳感器網(wǎng)絡(luò)蟻群改進(jìn)路由算法的基礎(chǔ)上，改進(jìn)了現(xiàn)有路由算法路徑搜索方式，很好地權(quán)衡了路由收斂速度與網(wǎng)絡(luò)生命周期的相互制約關(guān)系。同時(shí)將其應(yīng)用在無(wú)線傳感器網(wǎng)絡(luò)中進(jìn)行路由選擇，對(duì)于提高無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)效率、延長(zhǎng)網(wǎng)絡(luò)的生存周期具有很高的應(yīng)用價(jià)值。