基于能量受限的無線傳感器網(wǎng)絡路由設計

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

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

0 引言

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

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

1.1 WSN的體系結(jié)構

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

1.2 LEACH路由協(xié)議

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

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

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

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

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

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

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

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

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

為此，我們采用蟻群算法來解決這些問題，因為蟻群算法作為一種用來尋找優(yōu)化路徑技術[7]，其所擁有的魯棒性、可擴展性和本質(zhì)的并行性正適合于網(wǎng)絡路由的設計.

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

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

1）選舉簇頭

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

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

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

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

2）成簇

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

3）簇間通信

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

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

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

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

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

2.2 仿真實驗場景

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

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

2.3 仿真分析

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

圖3為LEACH與蟻群算法的能量消耗對比圖，從圖中我們可以看到，蟻群算法的能量消耗較LEACH有所減小.這表明基于蟻群算法的WSN路由算法使網(wǎng)絡的生命周期得到延長，且使能耗均勻分布到每個節(jié)點.這是因為采用基于蟻群算法的WSN路由算法使所有簇頭均勻分布，這樣網(wǎng)絡負載也得到均衡.

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

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

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

3 結(jié)論

針對傳感器節(jié)點在能量受限情況下，現(xiàn)有LEACH協(xié)議存在簇頭分配不均勻和能量消耗較大等問題，本文采用蟻群算法進行WSN路由的優(yōu)化設計.基于蟻群算法的路由改進算法可以解決LEACH算法存在的問題，仿真實驗也表明了在網(wǎng)絡的能量消耗、網(wǎng)絡生命周期等方面要優(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)絡系統(tǒng) [M].北京：科學出版社，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)絡節(jié)能的高效路由算法 [J].微計算機信息，2007，23（19）：188-189.

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

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