沙娓娓，劉增力

（1. 昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500；2. 昆明理工大學(xué) 民航學(xué)院，云南 昆明 650500）

0 引言

無(wú)線傳感器網(wǎng)絡(luò)：指利用無(wú)線通信的方法，將微型傳感器節(jié)點(diǎn)（被感知對(duì)象的內(nèi)部、附件之中）組成多跳自組織網(wǎng)絡(luò)，在環(huán)境監(jiān)測(cè)、國(guó)家安全以及軍事偵察等相關(guān)領(lǐng)域得以普遍應(yīng)用[1]。傳感器節(jié)點(diǎn)由電池提供能量，同時(shí)具有數(shù)量多、體積小等特點(diǎn)，一旦完成部署，即難以繼續(xù)補(bǔ)充能量。所以在設(shè)計(jì)無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議時(shí)，要充分考慮節(jié)點(diǎn)能量問(wèn)題，以延長(zhǎng)網(wǎng)絡(luò)生存周期達(dá)到傳輸大量數(shù)據(jù)的要求[2]。

Dorigo針對(duì)TSP的問(wèn)題，提出全新的模擬進(jìn)化算法——蟻群優(yōu)化算法[3]。與此同時(shí)隨著該算法的應(yīng)用，有效解決指派、調(diào)度以及旅行商等各類優(yōu)化組合問(wèn)題[4]。

Kassabalidis等潛心多年研究，結(jié)合蟻群算法，提出Ant-Net算法[5]，該算法中螞蟻主要可分為兩大類：其一是具有收集節(jié)點(diǎn)信息作用的前向螞蟻；其二為返回螞蟻，將前向螞蟻收集的信息，反饋在路由表之中。

Schoonderwoerd R等人通過(guò)概率選擇和更新路徑的方式，提出ABC算法[6]，此算法中螞蟻從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)后就死亡，同時(shí)更新路由表。文獻(xiàn)[7]基于 DD算法[8]提出一種全新的算法——ARAWSN，有助于改善能耗問(wèn)題，可找到源節(jié)點(diǎn)到目的節(jié)點(diǎn)間最短的路徑。

本文提出IARA這一全新優(yōu)化的算法，在源節(jié)點(diǎn)選擇下一跳節(jié)點(diǎn)，兼顧了節(jié)點(diǎn)的能量、傳輸方向、節(jié)點(diǎn)間距離等因素，通過(guò)改進(jìn)的信息素更新公式、啟發(fā)函數(shù)、選擇概率這三個(gè)方面，不僅降低了節(jié)點(diǎn)能耗，同時(shí)有助于延長(zhǎng)網(wǎng)絡(luò)生存周期。

1 無(wú)線傳感器網(wǎng)絡(luò)通信的能耗模型

在能耗模型方面，本文考慮選擇同文獻(xiàn)[9]的模型，將k bit的數(shù)據(jù)發(fā)送到d節(jié)點(diǎn)時(shí)，可用如下公式表示這一過(guò)程消耗的能量。

此時(shí)接收節(jié)點(diǎn)消耗能量：

融合數(shù)據(jù)消耗能量：

式（1）～（3）中：elecE、ampE、fuseE分別指發(fā)送和接收、傳輸放大以及融合數(shù)據(jù)等單元功耗，如果傳輸距離較大，則通常建議選擇運(yùn)用多路徑衰減模型，相反的如果較小，則一般運(yùn)用自由能量模型。

2 改進(jìn)的WSN蟻群路由算法描述

在具體設(shè)計(jì) WSN路由時(shí)，應(yīng)充分考慮到無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的特殊性，即其能量有限。針對(duì)這一問(wèn)題，本文緊扣“有效性”這一原則，充分考慮下一跳節(jié)點(diǎn)的能量參數(shù)以及實(shí)際傳輸距離、方向等問(wèn)題，使蟻群在自動(dòng)尋優(yōu)的同時(shí)，也具有能量感知意識(shí)。

2.1 路徑概率選擇

從路徑探索的角度出發(fā)，非常有必要結(jié)合某種概率訪問(wèn)周圍節(jié)點(diǎn)：而從路徑尋優(yōu)這一層面分析，為避免局部最優(yōu)解，在訪問(wèn)時(shí)節(jié)點(diǎn)時(shí)，如果僅以概率為基礎(chǔ)，其獲得的最優(yōu)解并非都有意義[10]。因此，引入傳輸方向參數(shù)，改進(jìn)后的轉(zhuǎn)移概率公式如下：

式（4）中，表示第k只螞蟻從節(jié)點(diǎn)i向節(jié)點(diǎn)j轉(zhuǎn)移的概率；用于表示k可通信節(jié)點(diǎn)集合，如果其通信節(jié)點(diǎn)并非可允許的節(jié)點(diǎn)，那么此時(shí)概率應(yīng)等于0；這里τij、ηij分別表示信息素濃度、啟發(fā)函數(shù)，兩者的權(quán)重值分別為α、β。假設(shè)α值較大，則對(duì)應(yīng)的信息素濃度發(fā)揮的作用相對(duì)較大，換言之即螞蟻會(huì)以已經(jīng)走過(guò)的路徑為主，彼此間具有較強(qiáng)的協(xié)同能力；相反的如果β值較大，則對(duì)應(yīng)說(shuō)明啟發(fā)函數(shù)可發(fā)揮更大的作用，此時(shí)以未探索過(guò)的節(jié)點(diǎn)為主，換言之即螞蟻具有較強(qiáng)的探索能力，可探索新節(jié)點(diǎn)。θ為下一跳節(jié)點(diǎn) next,源節(jié)點(diǎn) source和目的節(jié)點(diǎn)destination的夾角；γ為定義的常量，指明了傳輸方向?qū)?jié)點(diǎn)路由選擇的影響程度。

如圖1所示，即為θ的示意圖，通過(guò)該圖可充分說(shuō)明，假設(shè)θ越小，那么對(duì)應(yīng)的d1+d3越小，傳輸方向越接近于節(jié)點(diǎn)next到destination節(jié)點(diǎn)的連線方向，且

圖1 傳輸方向Fig.1 Direction of communication

2.2 本地啟發(fā)函數(shù)

螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的期望程度用啟發(fā)函數(shù)ijη表示。由于最初是針對(duì)TSP的問(wèn)題而提出該算法，所以啟發(fā)函數(shù)并未充分考慮其它因素，僅以兩節(jié)點(diǎn)的距離為考量重點(diǎn)。而無(wú)線傳感器網(wǎng)絡(luò)，除應(yīng)充分重視距離因素之外，還需綜合考慮諸如節(jié)點(diǎn)、鄰居節(jié)點(diǎn)剩余能量等多方面的問(wèn)題?；诖耍缡剑?）所示，即為本文的啟發(fā)函數(shù)定義：

式（6）中，Ecurrent(j)為節(jié)點(diǎn) i的鄰居節(jié)點(diǎn) j當(dāng)前剩余能量；Ni(k)表示集合節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合；(k)為節(jié)點(diǎn)i所有鄰居節(jié)點(diǎn)的剩余能量。節(jié)點(diǎn)剩余能量與該節(jié)點(diǎn)是否會(huì)被選擇有直接的關(guān)系，節(jié)點(diǎn)的能量水平越低，被選擇的概率也會(huì)越低；dij表示的是節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離。

2.3 信息素更新

螞蟻選擇下一跳節(jié)點(diǎn)時(shí)，會(huì)在經(jīng)過(guò)路徑上釋放出信息素，從而形成并增加可用于引導(dǎo)后來(lái)螞蟻的信息素濃度。由改進(jìn)后的公式可知，節(jié)點(diǎn)剩余能量越多的路徑上累積的信息素濃度也會(huì)越高，這樣有助于避免由于路徑（最短）的信息素濃度過(guò)大，而出現(xiàn)螞蟻過(guò)分集中的問(wèn)題，有助于避免節(jié)點(diǎn)能量消耗過(guò)快。給出信息素更新公式如下：

其中：Lk為螞蟻k從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所經(jīng)過(guò)的路徑長(zhǎng)度；λ為一個(gè)全局設(shè)定的常量； Ek_min、Ek_avg分別可用于表示螞蟻k經(jīng)過(guò)路徑節(jié)點(diǎn)的最小能量、平均能量。如式（8）所示，綜合考慮了路徑中最小能量、平均能量以及路徑總長(zhǎng)度這三個(gè)因素。假設(shè)在更新路徑信息素時(shí)，未充分考慮這一情況 ，僅以節(jié)點(diǎn)能量為依據(jù)，那么運(yùn)用此算法，則路徑不一定最短。

2.4 IARA算法的實(shí)現(xiàn)

具體實(shí)現(xiàn)步驟如下：

（1）初始化。清空螞蟻路徑，初始化訪問(wèn)標(biāo)志，顯示為未訪問(wèn)；在源節(jié)點(diǎn)中放m只螞蟻，同時(shí)設(shè)置為已訪問(wèn)，此為路線的第一個(gè)節(jié)點(diǎn)，另外各節(jié)點(diǎn)的初始值均為常數(shù)，且包含同樣的信息素；信息素增量在初始時(shí)為0；

（2）Antnum等于0，即到達(dá)目的節(jié)點(diǎn)的螞蟻數(shù)為0；

（3）螞蟻數(shù)k等于0；

（4）通過(guò)計(jì)算求出節(jié)點(diǎn)間距離；

（5）運(yùn)用（4）式計(jì)算轉(zhuǎn)移概率，并確定節(jié)點(diǎn)j，把螞蟻k轉(zhuǎn)移至此j，同時(shí)設(shè)置該節(jié)點(diǎn)為已訪問(wèn)，除了要修改螞蟻節(jié)點(diǎn)的能量外，還應(yīng)對(duì)應(yīng)修改前一節(jié)點(diǎn)能量；

（6）如果有節(jié)點(diǎn)能量耗盡，則直接跳至（9），如果沒(méi)有則依據(jù)（7）進(jìn)行；

（7）k等于k+1，對(duì)比該值與m大小，較小轉(zhuǎn)（5），否則轉(zhuǎn)（8）；

（8）判斷Antnum是否等于m，若兩者相等，即此時(shí)螞蟻都到目的節(jié)點(diǎn)，則轉(zhuǎn)（9），如果沒(méi)有則轉(zhuǎn)（3）；

（9）計(jì)算螞蟻經(jīng)過(guò)的整個(gè)路徑的長(zhǎng)度，比較得出最優(yōu)路徑；

（10）如果通過(guò)計(jì)算，并未有節(jié)點(diǎn)耗盡能量，則根據(jù)式（7）、（8）進(jìn)行信息素的全局更新后轉(zhuǎn)（2）執(zhí)行；否則轉(zhuǎn)（11）；

（11）如上述循環(huán)結(jié)束，最終輸出結(jié)果。

3 仿真及結(jié)果分析

通過(guò)Matlab訪真、驗(yàn)證IARA算法，在此基礎(chǔ)上對(duì)比分析了 ACO算法（文獻(xiàn)[3]），仿真范圍為100 m×100 m，并在這一范圍內(nèi)播撒（隨機(jī)）50個(gè)節(jié)點(diǎn)，將設(shè)定目標(biāo)節(jié)點(diǎn)（50,50）。

考慮到測(cè)試的方便性，本文中設(shè)螞蟻總數(shù)為50只，即等于節(jié)點(diǎn)個(gè)數(shù)；無(wú)線傳感器節(jié)點(diǎn)每次傳輸相同大小的數(shù)據(jù)包，參數(shù)初值為：α=1，β=2，γ=1，λ =1，rmax=50，每個(gè)節(jié)點(diǎn)初始能量為0.5J。

正如上文所述，引入本算法的目的，即在延長(zhǎng)網(wǎng)絡(luò)使用時(shí)長(zhǎng)的同時(shí)，最小化能量消耗。所以本文基于螞蟻群算法，提出IACA法，該法改進(jìn)了相關(guān)參數(shù)，通過(guò)傳輸距離、節(jié)點(diǎn)能量、傳輸方向這三者的綜合考慮，從而找到理想的延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的方法。因此，為了驗(yàn)證算法的性能，對(duì)比ACO算法，具體體現(xiàn)在如下兩個(gè)方面：其一網(wǎng)絡(luò)節(jié)點(diǎn)能耗總量；其二死亡節(jié)點(diǎn)數(shù)。

3.1 節(jié)點(diǎn)能耗

本文中的網(wǎng)絡(luò)生存時(shí)間，由所有節(jié)點(diǎn)消耗的能量之和反映，假設(shè)能耗越大，那么其生存時(shí)間就會(huì)越短；也就是說(shuō)，一定時(shí)間內(nèi)消耗大量的能量，則其對(duì)應(yīng)的網(wǎng)絡(luò)生存時(shí)間較短；相反的，如果能量消耗較小，則說(shuō)明具有較長(zhǎng)的生存時(shí)間，全網(wǎng)節(jié)點(diǎn)共計(jì)50個(gè)，每個(gè)節(jié)點(diǎn)的初始能量為0.5J，因此全網(wǎng)總能量為25J，圖2 IARA和ACO能量消耗對(duì)比圖。從圖2中可以看出，IARA和ACO分別在930、710輪時(shí)全網(wǎng)能量消耗殆盡。

3.2 死亡節(jié)點(diǎn)數(shù)

能耗與死亡節(jié)點(diǎn)有一定關(guān)系，但是兩者又存在一定差異性。通過(guò)能耗量可充分說(shuō)明在接收或者發(fā)送數(shù)據(jù)的消耗量，但是節(jié)點(diǎn)平均能耗與死亡節(jié)點(diǎn)數(shù)沒(méi)有必然的聯(lián)系，即死亡節(jié)點(diǎn)數(shù)不會(huì)單純因?yàn)楣?jié)點(diǎn)平均能耗多而增多。假設(shè)僅少數(shù)節(jié)點(diǎn)消耗了能量，其它節(jié)點(diǎn)并未消耗或者基本沒(méi)有消耗能量，這種情況下死亡節(jié)點(diǎn)數(shù)較少，但是不可忽視的是極有可能死亡節(jié)點(diǎn)均處于關(guān)鍵路徑上，即使得整個(gè)網(wǎng)絡(luò)癱瘓，對(duì)應(yīng)的其網(wǎng)絡(luò)生存的時(shí)間必然也會(huì)很短；假設(shè)由多個(gè)節(jié)點(diǎn)共同消耗節(jié)點(diǎn)能量，即屬于平均消耗，那么就算最后有很多死亡節(jié)點(diǎn)，也不易出現(xiàn)關(guān)鍵節(jié)點(diǎn)完全失效的問(wèn)題，即相應(yīng)的出現(xiàn)網(wǎng)絡(luò)癱瘓的機(jī)率也會(huì)較小，這樣一來(lái)，即有延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的作用。從圖3中可以看出，IARA和ACO分別在930、710輪時(shí)全部節(jié)點(diǎn)死亡，因此IARA算法的生命周期比ACO要長(zhǎng)，達(dá)到了預(yù)期的效果，證明了算法的有效性。

圖2 能量消耗Fig.2 Energy consumption

圖3 死亡節(jié)點(diǎn)數(shù)Fig.3 Nodes death

4 總結(jié)

本文基于無(wú)線傳感器網(wǎng)絡(luò)的特殊性，即節(jié)點(diǎn)能量少，引入具有健壯性、自組織性、自治性等優(yōu)點(diǎn)的蟻群算法，提出改進(jìn)的蟻群路由算法 IARA，在基本蟻群算法的基礎(chǔ)上綜合考慮了節(jié)點(diǎn)的能量、距離、傳輸方向等參數(shù)。仿真結(jié)果表明：通過(guò)該算法解決了無(wú)線傳感器網(wǎng)絡(luò)瓶頸問(wèn)題，即能耗大、網(wǎng)絡(luò)生存時(shí)間短，形成了節(jié)能、快速的路由來(lái)滿足網(wǎng)絡(luò)使用需要。

[1] 段海濱. 蟻群算法及其應(yīng)用[M]. 北京: 科學(xué)出版社2007:1389.DUAN H B, Ant colony algorithm and its application[M].Beijing: Science Press 2007: 1389.

[2] 陳宇, 等. 基于改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)路由的研究[D]. 廣州: 華南理工大學(xué), 2012.CHEN Y, et al. Research on routing of wireless sensor networks based on improved ant colony algorithm[D]. Guangzhou:South China University of Technology, 2012.

[3] Dorigo M, Gambardella L M. Ant colony system a cooperative learning approach to the travelling salesman problem[J].IEEE Transactions on Evolutionary Computation. 1997, 1(1): 53-66.

[4] Sim K M, Sun W H. Multiple ant-colony optimization for network routing[C]//Proceedings of the 1st International Symposium on Cyber Worlds, Washington DC, USA, 2001:277-281.

[5] Kassabalidis I, El-Sharkaw M A, Marks R J. Swarm intelligence for routing in communication networks[J]. Global telecommunications 2001, 6(6): 3613-3617.

[6] Schoonderwoerd R, Holland O, Bruten J, et al. Ants for load balancing in telecommunication networks[R]. Bristol: Hewlett Packard Lab, 1996. M. Goldfarb. Analog baseband IC for use in direct conversion W-CDMA receivers. IEEE.

[7] 梁華為, 陳萬(wàn)明, 李帥, 等．一種無(wú)線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算法[J]. 傳感器技術(shù)學(xué)報(bào), 2007, 20(11): 2450-2455.LIANG W H, CHEN W M, LI S et al. Ant colony optimization routing algorithm for Wireless Sensor Networks[J]. Journal of sensor technology, 2007, 20(11): 2450-2455.

[8] Intanagonmimwt C, Govindan R, Estrin D. Directed diffusion for wireless sensor networking[J]. IEEE/ACM Trans on Networking, 2003, 11(1): 2-16.

[9] Heinzelman W R. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communication, 2002, 1(4): 660-670.

[10] 滑楠, 史浩山, 高程, 等． 一種適用于無(wú)線傳感器網(wǎng)絡(luò)路由的改進(jìn)蟻群算法[J]. 傳感技術(shù)學(xué)報(bào), 2007, 20(7):1063-1069.HUA N, SHIH S, GAO C, et al. An improved ant colony algorithm for routing in Wireless Sensor Networks[J]. Journal of sensor technology, 2007, 20(7): 1063-1069.