武 睿，夏克文，李國棟，胡釗政

（河北工業(yè)大學(xué) 信息工程學(xué)院，天津，300401）

0 引言

無線傳感器網(wǎng)絡(luò)（WSN,WirelessSensor Network）是當(dāng)今信息科學(xué)中一個新的研究熱點(diǎn)和發(fā)展方向，具有極其廣泛的應(yīng)用前景.它主要由分布在一個監(jiān)測區(qū)域內(nèi)的一系列無線傳感器，通過自組織和多跳方式組成一個無線通信網(wǎng)絡(luò)，協(xié)作感知、采集和處理網(wǎng)絡(luò)區(qū)域內(nèi)的有關(guān)信息，并發(fā)送給用戶.傳統(tǒng)的WSN的路由協(xié)議由于很少考慮傳感器節(jié)點(diǎn)的能量有限問題[1,2]，致使在網(wǎng)絡(luò)優(yōu)化中很難選擇出最優(yōu)路徑.我們知道，設(shè)計WSN路由協(xié)議的重要指標(biāo)就是要使整個網(wǎng)絡(luò)的生存周期得到充分延長[3]，即選取的傳輸路徑能量要小,且整個網(wǎng)絡(luò)的能量是均衡的.鑒于蟻群算法很適宜于求解多維組合優(yōu)化問題，且具有較強(qiáng)的魯棒性、全局性、普遍性、優(yōu)良的分布式并行計算機(jī)制.為此，我們采用蟻群算法來研究WSN的路由設(shè)計.

1 WSN的體系結(jié)構(gòu)與LEACH協(xié)議

1.1 WSN的體系結(jié)構(gòu)

一個典型傳感器網(wǎng)絡(luò)包括監(jiān)視區(qū)域內(nèi)的傳感器節(jié)點(diǎn) (Nodes)、匯聚節(jié)點(diǎn) (SINK)、基本網(wǎng)絡(luò) (Internetamp;Satellite)以及WSN任務(wù)管理節(jié)點(diǎn)[3]，如圖1所示.

1.2 LEACH路由協(xié)議

低功耗自適應(yīng)集簇分層型協(xié)議（LEACH，Low Energy AdaptiveClustering Hierarchy）[4,5]是第一個關(guān)于WSN的層次式路由協(xié)議，之后發(fā)展起來的層次式路由協(xié)議基本都是基于LEACH而改進(jìn)的.LEACH路由算法思想主要以循環(huán)方式隨機(jī)選擇簇頭節(jié)點(diǎn)，再將網(wǎng)絡(luò)能量負(fù)載均分到各個傳感器節(jié)點(diǎn)上，因而使得網(wǎng)絡(luò)能耗降低、網(wǎng)絡(luò)生存周期得到延長[6].

LEACH路由協(xié)議可分為簇的建立（Setup phase）和穩(wěn)定運(yùn)行（Ready phase）兩個階段，兩階段的時間總和記為一輪（Round），簇的建立包括簇頭節(jié)點(diǎn)的選擇、簇頭節(jié)點(diǎn)的廣播、簇頭節(jié)點(diǎn)的建立和調(diào)度機(jī)制的生成等環(huán)節(jié)，而穩(wěn)定階段持續(xù)一段時間后，網(wǎng)絡(luò)又重新進(jìn)入簇的建立，進(jìn)行下一輪的簇重構(gòu).

在簇的建立階段，傳感器節(jié)點(diǎn)隨機(jī)生成一個0、1之間的隨機(jī)數(shù)，并且與閾值 做比較，如果小于該閾值，則該節(jié)點(diǎn)就會當(dāng)選為簇頭[6]. 按照下列公式計算

圖1 典型的無線傳感器網(wǎng)絡(luò)Fig.1 Typicalw irelesssensor network

其中： 為一輪的簇頭節(jié)點(diǎn)數(shù)； 為當(dāng)前輪數(shù)； 為節(jié)點(diǎn)總數(shù)； 為最近 /輪中沒有當(dāng)選簇頭的節(jié)點(diǎn)集合.選定簇頭節(jié)點(diǎn)后，廣播告知整個網(wǎng)絡(luò)，其他節(jié)點(diǎn)根據(jù)接收信息的信號強(qiáng)度決定從屬的簇，完成簇的建立后，節(jié)點(diǎn)通過時分多址（TDMA）和單跳方式將信息傳給簇頭，然后簇頭將融合后的信息傳至SINK.

實(shí)踐表明，該LEACH比與以前的路由協(xié)議具有較長的網(wǎng)絡(luò)生命周期.但是它也存在一些不足，需要改進(jìn)之處主要表現(xiàn)在：

1）簇的建立完全隨機(jī)，由于它與SINK節(jié)點(diǎn)的控制信息無關(guān)，且沒有各節(jié)點(diǎn)之間的協(xié)調(diào)處理，因此每輪中難以實(shí)現(xiàn)簇的優(yōu)化建立.

2）在單跳方式下由于與SINK節(jié)點(diǎn)進(jìn)行通信的節(jié)點(diǎn)數(shù)較多，致使能量消耗加大.

3）簇頭的選舉也是完全隨機(jī)的，應(yīng)該考慮其節(jié)點(diǎn)的能量受限情形.

為此，我們采用蟻群算法來解決這些問題，因?yàn)橄伻核惴ㄗ鳛橐环N用來尋找優(yōu)化路徑技術(shù)[7]，其所擁有的魯棒性、可擴(kuò)展性和本質(zhì)的并行性正適合于網(wǎng)絡(luò)路由的設(shè)計.

2 基于蟻群算法的WSN路由算法及實(shí)現(xiàn)

2.1 基于蟻群算法的WSN路由算法步驟

1）選舉簇頭

簇頭選舉經(jīng)歷以下幾步：

Step1：SINK廣播一個起始成簇信息，包括這一輪的網(wǎng)絡(luò)平均能量 .

Step2：各節(jié)點(diǎn)接收SINK的成簇信息后，計算自身能量，若大于 ，說明自己可以競選簇頭，否則自己為普通節(jié)點(diǎn).

Step3：SINK根據(jù)可參選簇頭的節(jié)點(diǎn)信息作簇分割.

2）成簇

各節(jié)點(diǎn)有可能接收到多個簇頭發(fā)來的信息，節(jié)點(diǎn)依據(jù)各信號強(qiáng)度，將最強(qiáng)信號的節(jié)點(diǎn)作為簇頭，并請求加入其簇.本文中蟻群算法完成簇首到匯聚節(jié)點(diǎn)的路由。

3）簇間通信

Step1：參數(shù)初始化，設(shè)置總的迭代次數(shù)以及每個簇首節(jié)點(diǎn)所派螞蟻的個數(shù)m：每個簇頭節(jié)點(diǎn)分別派m只螞蟻尋找到SINK節(jié)點(diǎn)的路徑，從中選擇最短的路徑并增加該路徑上的信息素；繼續(xù)迭代找到簇首到SINK節(jié)點(diǎn)的最短路徑。

Step2：人工螞蟻找到最優(yōu)路徑后，進(jìn)行數(shù)據(jù)傳輸。在簇間通信階段，各簇首可以根據(jù)本身與下一跳的距離動態(tài)的調(diào)節(jié)發(fā)射功率，在不影響數(shù)據(jù)傳輸?shù)那疤嵯逻_(dá)到節(jié)約系統(tǒng)能量的目的。

Step3：進(jìn)行簇間路由，通過選擇下一跳簇首完成簇間路由，將數(shù)據(jù)發(fā)送給匯聚節(jié)點(diǎn)。

形成或更新的簇頭 與簇頭 間的信息素濃度計算公式為

式中： 為示信息素?fù)]發(fā)量； 為 節(jié)點(diǎn)剩余能量； 為兩簇頭間的距離； 和 分別表示節(jié)點(diǎn)能量和節(jié)點(diǎn)間距離在信息素中所占的比重。

2.2 仿真實(shí)驗(yàn)場景

為檢測WSN傳感器節(jié)點(diǎn)規(guī)模對路由性能的影響，在仿真實(shí)驗(yàn)中設(shè)置100個節(jié)點(diǎn)隨機(jī)分布在100m×100m的區(qū)域內(nèi)，并設(shè)一個基站和一個SINK，其中SINK在區(qū)域中心，圖2為傳感器節(jié)點(diǎn)分布圖.各節(jié)點(diǎn)初始能量設(shè)置為0.5 J，每一輪中選取簇頭節(jié)點(diǎn)為10個，若網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)過少時，網(wǎng)絡(luò)則不能繼續(xù)運(yùn)行.蟻群算法參數(shù)選擇為： 取值0.5， 取值為3，信息素?fù)]發(fā)量 =0.7.

圖2 傳感器節(jié)點(diǎn)分布圖Fig.2 Distribution on sensor nodes

2.3 仿真分析

采用節(jié)點(diǎn)的能量消耗和節(jié)點(diǎn)存活數(shù)等指標(biāo)可以評價WSN的性能.

圖3為LEACH與蟻群算法的能量消耗對比圖，從圖中我們可以看到，蟻群算法的能量消耗較LEACH有所減小.這表明基于蟻群算法的WSN路由算法使網(wǎng)絡(luò)的生命周期得到延長，且使能耗均勻分布到每個節(jié)點(diǎn).這是因?yàn)椴捎没谙伻核惴ǖ腤SN路由算法使所有簇頭均勻分布，這樣網(wǎng)絡(luò)負(fù)載也得到均衡.

圖4為無線傳感器網(wǎng)絡(luò)死亡節(jié)點(diǎn)數(shù)目隨時間的變化情況.從圖4中可以看到基于蟻群算法的WSN路由算法出現(xiàn)死亡節(jié)點(diǎn)的時間晚于LEACH算法，而且所有節(jié)點(diǎn)死亡的時間也明顯晚于LEACH，表明蟻群算法使無線傳感器網(wǎng)絡(luò)的生命周期得到延長.這是因?yàn)檫x取能量大的節(jié)點(diǎn)為簇頭使得能量低的節(jié)點(diǎn)可以延長其生命周期；另外，采用蟻群算法優(yōu)化簇間路由時，其信息素濃度的計算中加入了簇頭能量，這樣能夠保證以一定概率選出較大能量節(jié)點(diǎn)，從而延長了網(wǎng)絡(luò)的生命周期.

圖3 LEACH與蟻群算法的能量消耗對比Fig.3 Comparison on theenergy consumption between LEACH and ACO algorithm

圖4 LEACH和蟻群算法的死亡節(jié)點(diǎn)數(shù)對比Fig.4 Comparison on the death numberof nodes between LEACH and ACO algorithm

3 結(jié)論

針對傳感器節(jié)點(diǎn)在能量受限情況下，現(xiàn)有LEACH協(xié)議存在簇頭分配不均勻和能量消耗較大等問題，本文采用蟻群算法進(jìn)行WSN路由的優(yōu)化設(shè)計.基于蟻群算法的路由改進(jìn)算法可以解決LEACH算法存在的問題，仿真實(shí)驗(yàn)也表明了在網(wǎng)絡(luò)的能量消耗、網(wǎng)絡(luò)生命周期等方面要優(yōu)于LEACH算法.

[1]Akyildiz IF，SuW，Sankarasubramaniam Y.A Survey on Sensor Networks[J].IEEECommunicationsMagazine，2002，8（7）：102-114.

[2]RentalaP，MusunuriR，Gandham S，SaxenaU.Surveyon Sensornetworks[R].TechnicalReport，UTDCS-33-02，University of TexasatDallas，2002.

[3]Md Nafees Rahman,M A Matin.Efficient A lgorithm for Prolonging Network Lifetime of Wireless Sensor Networks[J].TsingHua Science and Technology,2011，16（6）：561-568.

[4]于海斌，曾鵬，梁韡.智能無線傳感器網(wǎng)絡(luò)系統(tǒng) [M].北京：科學(xué)出版社，2006.

[5]Lindsey S，Raghavendra C S.Power efficientgathering in sensor information systems[C]//Proceedings of IEEE Aerospace Conference，2002：1125-1130.

[6]趙喜清，秦奮濤，范青.無線傳感器網(wǎng)絡(luò)節(jié)能的高效路由算法 [J].微計算機(jī)信息，2007，23（19）：188-189.

[7]王鎮(zhèn)，劉學(xué)軍.WSN中基于蟻群算法的Qos路由協(xié)議 [J].傳感技術(shù)學(xué)報，2011，24（11）：1625-1630.

[8]汪祥莉.無線傳感器網(wǎng)絡(luò)中高能效路由技術(shù)的研究 [D].武漢：武漢理工大學(xué)，2011.