張雅瓊，張 慧，鄭歡歡

(榆林學(xué)院 信息工程學(xué)院，陜西 榆林 719000)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSN)是物聯(lián)網(wǎng)中監(jiān)測環(huán)境與感知數(shù)據(jù)的重要技術(shù)，由大量的長時(shí)間持續(xù)工作的靜態(tài)無線節(jié)點(diǎn)自治組成。因?yàn)闊o線傳感器節(jié)點(diǎn)使用電池供電且通常不會更換，所以無線傳感器網(wǎng)絡(luò)的能量消耗和網(wǎng)絡(luò)生存時(shí)間成為研究的熱點(diǎn)，而節(jié)能路由策略可以顯著延長網(wǎng)絡(luò)生存時(shí)間。近年來，有四種不同類型的路由協(xié)議不斷發(fā)展，每種類型下都有大量的路由協(xié)議。這些路由協(xié)議包括地理路由協(xié)議、以數(shù)據(jù)為中心的路由協(xié)議、基于分簇的路由協(xié)議和混合路由協(xié)議。在這些路由協(xié)議中，基于分簇的分層路由協(xié)議由于其可擴(kuò)展性而得到了廣泛應(yīng)用?；诜执氐穆酚蓞f(xié)議將無線傳感器節(jié)點(diǎn)分成若干組，這些組(即分簇)連接到本地基站(BS)或匯聚(sink)節(jié)點(diǎn)。文獻(xiàn)[4-7]中提出了大量基于分簇的路由協(xié)議，如LEACH、LEACH-C、KLEACH、EEE-LEACH等。其中，LEACH(low-energy adaptive clustering hierarchy)是第一個(gè)也是最流行的基于分簇的無線傳感器網(wǎng)絡(luò)分層路由協(xié)議。LEACH是一種自組織的自適應(yīng)分簇協(xié)議，利用基于隨機(jī)性的概率將負(fù)載平均分配給網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)。在LEACH協(xié)議中，節(jié)點(diǎn)能夠?qū)⒆约航M織成簇，其中一個(gè)節(jié)點(diǎn)充當(dāng)簇頭，為其他節(jié)點(diǎn)匯聚數(shù)據(jù)后再將數(shù)據(jù)發(fā)送給sink節(jié)點(diǎn)。這使得高能量的節(jié)點(diǎn)隨機(jī)作為簇頭，從而節(jié)省所有傳感器節(jié)點(diǎn)的能量(或電池消耗)，進(jìn)而延長網(wǎng)絡(luò)生存期。通常LEACH在將數(shù)據(jù)傳輸?shù)絪ink節(jié)點(diǎn)之前，在簇頭進(jìn)行數(shù)據(jù)聚合和數(shù)據(jù)融合(數(shù)據(jù)壓縮)，通過特定于應(yīng)用的數(shù)據(jù)處理，進(jìn)一步降低能耗，延長網(wǎng)絡(luò)生存期。

LEACH協(xié)議分為兩個(gè)階段：

(1)建立階段，包括簇頭選擇、簇建立；

(2)穩(wěn)定階段，包括數(shù)據(jù)感知、聚合、壓縮和傳輸。

然而，LEACH在建立階段是不穩(wěn)定的，因?yàn)樗蕾囉趥鞲衅鞴?jié)點(diǎn)的密度。由于不采用多跳通信，在大型網(wǎng)絡(luò)中在從遠(yuǎn)離匯聚節(jié)點(diǎn)的簇頭節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)會消耗大量的能量，導(dǎo)致節(jié)點(diǎn)過早死亡。影響能量消耗的主要因素有：感知數(shù)據(jù)、數(shù)據(jù)處理和無線通信，其中最重要的是無線通信。該文提出了兩級分簇，簇內(nèi)單跳數(shù)據(jù)傳輸和簇間多跳傳輸，大大提高了網(wǎng)絡(luò)生存期。

1 無線傳感器網(wǎng)絡(luò)模型

1.1 網(wǎng)絡(luò)假設(shè)

無線傳感器網(wǎng)絡(luò)由大量隨機(jī)分布的無線傳感器節(jié)點(diǎn)組成。根據(jù)節(jié)點(diǎn)密度將區(qū)域劃分為若干個(gè)簇，每個(gè)簇都有一個(gè)簇頭，簇內(nèi)成員節(jié)點(diǎn)將數(shù)據(jù)發(fā)給簇頭，簇頭將數(shù)據(jù)轉(zhuǎn)發(fā)給sink節(jié)點(diǎn)，如圖1所示。

圖1 無線傳感器網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型中做出以下假設(shè)：

(1)有一個(gè)無線傳感器節(jié)點(diǎn)隨機(jī)部署并緊密相連的網(wǎng)絡(luò)；

(2)每個(gè)傳感器節(jié)點(diǎn)具有相同的初始能量與計(jì)算能力；

(3)具有不同ID的每個(gè)傳感器節(jié)點(diǎn)將沿著其相鄰鏈路/邊緣發(fā)送/接收消息；

(4)每個(gè)節(jié)點(diǎn)知道它自己的坐標(biāo)值；

(5)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都知道圖中其鄰居節(jié)點(diǎn)的ID；

(6)每個(gè)節(jié)點(diǎn)都可以按照網(wǎng)絡(luò)能耗模型單獨(dú)發(fā)送和接收數(shù)據(jù)包。

1.2 網(wǎng)絡(luò)能耗

無線傳感器網(wǎng)絡(luò)的傳輸采用無線通信系統(tǒng)中的能耗模型，如圖2所示。

圖2 無線通信能耗模型

發(fā)送數(shù)據(jù)的能耗包括射頻模塊和信號放大器的能耗，接收節(jié)點(diǎn)的能耗僅包括接收電路的能耗。信號放大器的能耗根據(jù)收發(fā)雙方之間的距離

d

可以采用自由空間衰落模型和多路徑衰落模型。自由空間衰落模型中，路徑損耗指數(shù)為2，即

d

能量損耗；多路徑衰落模型中，路徑損耗指數(shù)為4，即

d

能量損耗。參數(shù)

ξ

代表數(shù)據(jù)在自由空間模型傳輸過程中的損耗，參數(shù)

ξ

代表數(shù)據(jù)在多路徑衰落模型傳輸過程中的損耗。

E

表示發(fā)送或接收1比特?cái)?shù)據(jù)時(shí)發(fā)送電路或接收電路的能耗。假設(shè)無線信道是對稱的，即節(jié)點(diǎn)1向節(jié)點(diǎn)2發(fā)送數(shù)據(jù)的能耗與節(jié)點(diǎn)2向節(jié)點(diǎn)1發(fā)送數(shù)據(jù)的能耗完全相同。發(fā)送

L

比特?cái)?shù)據(jù)所消耗的能量如式(1)所示：

(1)

其中，

d

表示無線收發(fā)節(jié)點(diǎn)之間的距離，如式(2)所示：

(2)

(

x

,

y

)與(

x

,

y

)分別表示發(fā)送節(jié)點(diǎn)

i

與接收節(jié)點(diǎn)

j

的坐標(biāo)值。能耗與所使用的傳輸放大模型有關(guān)，

d

是一個(gè)距離常量，如式(3)所示。通常傳感器節(jié)點(diǎn)到sink的距離大于閾值

d

，而節(jié)點(diǎn)之間的距離小于閾值

d

。

(3)

數(shù)據(jù)傳輸距離為

d

，接收方接收

L

比特?cái)?shù)據(jù)消耗的能量如式(4)所示，與傳輸距離無關(guān)。

E

(

M

)=

E

*

L

(4)

1.3 路由策略

基于圖論的優(yōu)化算法已經(jīng)被用于無線傳感器網(wǎng)絡(luò)的路由。圖論方法的主要目標(biāo)是最小化無線傳感器網(wǎng)絡(luò)(WSN)的總功耗。蟻群優(yōu)化(ant colony optimization，ACO)可以用于路由建立，即所有簇頭節(jié)點(diǎn)都試圖建立一條到sink節(jié)點(diǎn)的最優(yōu)路徑。

在該文提出的策略中，使用ACO算法在簇頭和sink節(jié)點(diǎn)之間進(jìn)行最小代價(jià)路由，而不是將所有簇頭與sink節(jié)點(diǎn)并行單跳連接。此外，由于能量最小化是無線傳感器網(wǎng)絡(luò)最關(guān)心的問題，使用基于鄰近度簇半徑劃分方法，以便跟蹤廣播和多跳鏈路并提供最大地形覆蓋的能量優(yōu)化。

2 改進(jìn)的路由方案

采用分簇的二級分層網(wǎng)絡(luò)，該文提出了一種改進(jìn)的LEACH算法，該算法在最大限度降低網(wǎng)絡(luò)總能耗的同時(shí)，實(shí)現(xiàn)了網(wǎng)絡(luò)流量的最大化。

為了實(shí)現(xiàn)目標(biāo)，匯聚節(jié)點(diǎn)向網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)廣播信標(biāo)Beacon信號，以得到節(jié)點(diǎn)到sink的距離?；诠?jié)點(diǎn)密度形成分簇的邊界。在LEACH中，簇頭是在一段時(shí)間后隨機(jī)選擇的。因此，每當(dāng)隨機(jī)選擇一個(gè)新的簇頭時(shí)，在sink節(jié)點(diǎn)處再次形成簇邊界。一旦確定了簇邊界，在多跳通信模式下，在sink節(jié)點(diǎn)上運(yùn)行蟻群優(yōu)化算法(ACO)以最小能耗代價(jià)確定從簇頭到匯聚節(jié)點(diǎn)的多跳路徑。

無線傳感器網(wǎng)絡(luò)的工作過程如圖3所示。

圖3 網(wǎng)絡(luò)運(yùn)行過程

無線傳感器網(wǎng)絡(luò)開始工作后，sink節(jié)點(diǎn)向網(wǎng)絡(luò)中的所有傳感器節(jié)點(diǎn)廣播消息并接收回信標(biāo)信號。它基于接收到的信號強(qiáng)度值以及收到的節(jié)點(diǎn)坐標(biāo)值確認(rèn)與傳感器節(jié)點(diǎn)的距離。然后，隨機(jī)競選簇頭并劃分簇，在之后的網(wǎng)絡(luò)運(yùn)行時(shí)，在每個(gè)簇中，簇成員節(jié)點(diǎn)周期性地在啟動階段生成隨機(jī)數(shù)以用于簇頭重新選擇，如果生成的該隨機(jī)值小于隨機(jī)閾值，則基于簇內(nèi)節(jié)點(diǎn)的可用能量資源來重新選擇簇頭。簇成員節(jié)點(diǎn)通過廣播消息通知sink新的簇頭。簇頭選擇后，在sink節(jié)點(diǎn)重新劃分簇半徑。如果生成的隨機(jī)值大于閾值，則sink節(jié)點(diǎn)將等待下一次簇頭重選活動。此后，為了節(jié)省從簇頭到sink節(jié)點(diǎn)傳輸所需的能量，采用ACO來尋找從簇頭到sink節(jié)點(diǎn)的最佳路徑。

2.1 簇頭選舉與簇的形成

無線傳感器網(wǎng)絡(luò)采用集中式簇間網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。sink節(jié)點(diǎn)決定簇頭、簇邊界以及不同簇之間的路由。下面一一解釋。

(1)簇頭的選擇：一旦傳感器節(jié)點(diǎn)開始工作，使用公式(5)競選簇頭。

(5)

其中，

p

是期望的簇頭占所有節(jié)點(diǎn)的百分比，即每個(gè)節(jié)點(diǎn)成為簇頭的概率；

r

是當(dāng)前運(yùn)行的輪數(shù)；

E

是節(jié)點(diǎn)的剩余能量；

E

是節(jié)點(diǎn)的初始能量。網(wǎng)絡(luò)中的所有節(jié)點(diǎn)計(jì)算上述函數(shù)的值，并選擇

T

(

n

)最大的節(jié)點(diǎn)作為簇頭。一旦選擇了新的簇頭，sink節(jié)點(diǎn)就會通過廣播消息通知新的簇頭集合。(2)計(jì)算簇邊界：對于給定網(wǎng)絡(luò)，

d

和

d

分別為最大和最小的節(jié)點(diǎn)間距離，簇半徑根據(jù)每個(gè)節(jié)點(diǎn)與sink節(jié)點(diǎn)之間的距離(SN)計(jì)算，使用公式(6)。

(6)

2.2 簇內(nèi)數(shù)據(jù)傳輸

簇頭競選成功以及簇劃分結(jié)束后，各個(gè)簇內(nèi)傳感器節(jié)點(diǎn)發(fā)送加入消息給簇頭，消息中包含自己的剩余能量以及節(jié)點(diǎn)ID。簇頭節(jié)點(diǎn)根據(jù)簇內(nèi)成員節(jié)點(diǎn)數(shù)量劃分時(shí)隙，即采用TDMA機(jī)制給每個(gè)成員分配對應(yīng)時(shí)隙，各個(gè)節(jié)點(diǎn)在自己的時(shí)隙采集并將采集數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)，在非自己時(shí)隙時(shí)休眠，以節(jié)省能耗。

簇頭收到簇成員發(fā)送的感知數(shù)據(jù)后進(jìn)行數(shù)據(jù)融合，然后采用簇間多跳路由將信息發(fā)送給sink節(jié)點(diǎn)。

2.3 基于ACO的簇間路由

蟻群優(yōu)化(ACO)是一種基于群體的優(yōu)化技術(shù)，以有效地解決組合優(yōu)化問題。蟻群算法的靈感來自蟻群的食物收集模式，螞蟻在探訪同伴時(shí)會留下信息素激素的蹤跡來識別目標(biāo)(食物)。在每一點(diǎn)上，螞蟻都有兩種選擇，要么試探性地探索目標(biāo)，要么利用其他同伴留下的信息素軌跡。在ACO算法中，螞蟻根據(jù)信息素濃度、能量等啟發(fā)式信息來規(guī)劃最優(yōu)路徑。將ACO應(yīng)用到無線傳感器網(wǎng)絡(luò)中是為了利用ACO的自組織性、正反饋性和魯棒性等，降低路由過程中的能量消耗。在無線傳感器網(wǎng)絡(luò)中引入ACO的原因主要有以下4點(diǎn)：

(1)無線節(jié)點(diǎn)能力有限。

無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的能量、存儲容量和計(jì)算能力均有限，在設(shè)計(jì)路由協(xié)議時(shí)，需優(yōu)先考慮路由過程中的能耗與負(fù)載均衡問題。將ACO引入到無線傳感器網(wǎng)絡(luò)路由中，根據(jù)其算法簡單易于實(shí)現(xiàn)和群體智能特征可自主地尋找最優(yōu)路徑，節(jié)省節(jié)點(diǎn)能量，平衡網(wǎng)絡(luò)負(fù)載。

(2)自組織網(wǎng)絡(luò)。

無線傳感器網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)通常是隨機(jī)部署的，節(jié)點(diǎn)之間自組織形成網(wǎng)絡(luò)。ACO中的螞蟻通過正向反饋原則逐步探索，獲取最優(yōu)路徑，在得到最優(yōu)路徑的同時(shí)，提高節(jié)點(diǎn)能量的利用率。

(3)網(wǎng)絡(luò)結(jié)構(gòu)的動態(tài)性。

無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)由于能量耗盡而死亡，以及重新選舉簇頭等因素使得網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)會經(jīng)常發(fā)生變化，ACO利用其本身的魯棒性，能夠很好地應(yīng)對這一情況。在網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，螞蟻采用啟發(fā)式的路徑搜索方式，及時(shí)做出調(diào)整并再次尋找最優(yōu)路徑，其適應(yīng)性較好且反應(yīng)速度較快。

本算法中，在每個(gè)簇頭點(diǎn)上設(shè)置一組概率規(guī)則，有助于最小化訪問的總成本，并以最佳方式找到通過多個(gè)點(diǎn)的最佳路徑。假設(shè)螞蟻是一個(gè)基于短時(shí)記憶的隨機(jī)路徑分配器，在每一步中，為了找到從簇頭到sink節(jié)點(diǎn)的最小路徑，螞蟻應(yīng)用隨機(jī)比例規(guī)則來決定下一個(gè)訪問哪個(gè)簇頭。當(dāng)前在簇頭

i

的螞蟻選擇去簇頭

j

的概率由式(7)給出：

(7)

其中，

γ

是介于0和1之間的常數(shù)，

τ

表示信息素軌跡，

η

表示先驗(yàn)可用的啟發(fā)值，

α

和

β

確定信息素軌跡和啟發(fā)式信息的相對影響。如果

α

=0，則更可能選擇更接近的簇頭，這表明存在隨機(jī)貪婪算法。如果

β

=0，則只放大信息素，不使用啟發(fā)式方法。兩個(gè)相鄰的簇頭

i

和

j

的啟發(fā)值由式(8)定義：

(8)

τ

(

t

+1)=(1-

v

)*

τ

(

t

)+

δ

*

v

*

τ

(

t

+1,

t

)

(9)

通過反復(fù)計(jì)算獲取從簇頭到sink節(jié)點(diǎn)的最優(yōu)路徑。

3 算法仿真與性能分析

3.1 仿真環(huán)境

對文中算法LEACH-ACO與經(jīng)典LEACH算法使用MATLAB進(jìn)行仿真比較并進(jìn)行性能評估。兩個(gè)算法都采用了二級路由策略進(jìn)行數(shù)據(jù)的傳輸。仿真參數(shù)如表1所示。無線傳感器節(jié)點(diǎn)隨機(jī)部署在400 m×400 m的矩形區(qū)域。傳感器節(jié)點(diǎn)在0到10個(gè)包之間隨機(jī)生成數(shù)據(jù)，每個(gè)包的大小為4 kb。為了驗(yàn)證提出的簇間優(yōu)化方法，實(shí)現(xiàn)了一個(gè)由200個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)，從中選擇20個(gè)節(jié)點(diǎn)作為簇頭。

表1 仿真參數(shù)

3.2 性能分析

在建立簇后，LEACH-ACO策略利用ACO算法對簇頭間的路由進(jìn)行優(yōu)化，以解決到sink節(jié)點(diǎn)的多跳數(shù)據(jù)傳輸。仿真性能評價(jià)采用的指標(biāo)是網(wǎng)絡(luò)生存期(死亡節(jié)點(diǎn)數(shù)與輪數(shù)的關(guān)系)與網(wǎng)絡(luò)吞吐量(網(wǎng)絡(luò)生存期內(nèi)所有節(jié)點(diǎn)發(fā)送到sink節(jié)點(diǎn)的數(shù)據(jù)包總數(shù))。

(1)網(wǎng)絡(luò)生存期。

定義當(dāng)無線傳感器網(wǎng)絡(luò)中有一半的傳感器節(jié)點(diǎn)死亡時(shí)，即認(rèn)為網(wǎng)絡(luò)已死亡(在本例中為100)。隨著網(wǎng)絡(luò)運(yùn)行，系統(tǒng)的總能量將衰減，死亡節(jié)點(diǎn)隨時(shí)間增加，但能量分布是隨機(jī)的。如圖4所示，在LEACH路由算法中，第一個(gè)死亡節(jié)點(diǎn)在網(wǎng)絡(luò)運(yùn)行20輪后便出現(xiàn)，而在LEACH-ACO中第一個(gè)死亡節(jié)點(diǎn)在大約120輪后出現(xiàn)。在LEACH中，第70輪左右有一半的節(jié)點(diǎn)死亡，網(wǎng)絡(luò)生存期僅為70輪，而在LEACH-ACO中，大約第200輪時(shí)網(wǎng)絡(luò)死亡。因此，提出的LEACH-ACO相比LEACH顯著地延長了網(wǎng)絡(luò)的生存期。

圖4 隨著網(wǎng)絡(luò)運(yùn)行而增加的死亡節(jié)點(diǎn)數(shù)

(2)網(wǎng)絡(luò)吞吐量。

以網(wǎng)絡(luò)生存期內(nèi)所有無線傳感器節(jié)點(diǎn)發(fā)送給sink節(jié)點(diǎn)的數(shù)據(jù)包總數(shù)來衡量網(wǎng)絡(luò)吞吐量。

如圖5所示，因?yàn)椴捎肔EACH-ACO算法后無線傳感器網(wǎng)絡(luò)的生存期延長，sink節(jié)點(diǎn)收到的數(shù)據(jù)包總量顯著大于采用LEACH算法的無線傳感器網(wǎng)絡(luò)收到的數(shù)據(jù)包總量，其網(wǎng)絡(luò)吞吐量是采用LEACH的網(wǎng)絡(luò)的3倍多。因此，采用LEACH-ACO算法后，sink節(jié)點(diǎn)可以收到更多的感知數(shù)據(jù)，無線傳感器網(wǎng)絡(luò)可以更好地發(fā)揮感知作用。

圖5 隨著網(wǎng)絡(luò)運(yùn)行發(fā)送給sink節(jié)點(diǎn)的數(shù)據(jù)包總數(shù)

4 結(jié)束語

隨著物聯(lián)網(wǎng)的發(fā)展，作為物聯(lián)網(wǎng)感知層的無線傳感器網(wǎng)絡(luò)也得到了廣泛應(yīng)用，而無線傳感器網(wǎng)絡(luò)的能耗一直是制約其發(fā)展的因素。該文提出了一種應(yīng)用于無線傳感器網(wǎng)絡(luò)的基于LEACH算法的節(jié)能路由，即LEACH-ACO數(shù)據(jù)傳輸策略。該方法優(yōu)先選擇剩余能量較高的節(jié)點(diǎn)作為簇頭，然后sink節(jié)點(diǎn)根據(jù)無線傳感器節(jié)點(diǎn)與簇頭的距離形成簇邊界，一旦選定了簇頭并確定了簇的邊界即完成了分簇，之后利用ACO算法以最小能耗代價(jià)確定從簇頭到sink節(jié)點(diǎn)的多跳路徑。網(wǎng)絡(luò)采用二級分層結(jié)構(gòu)，簇內(nèi)基于TDMA進(jìn)行數(shù)據(jù)發(fā)送，簇間采用多跳路由發(fā)送數(shù)據(jù)到sink節(jié)點(diǎn)。仿真結(jié)果表明，采用LEACH-ACO算法的無線傳感器網(wǎng)絡(luò)比使用LEACH算法的網(wǎng)絡(luò)極大地提高了生存時(shí)間，同時(shí)也大幅提升了網(wǎng)絡(luò)的吞吐量，sink節(jié)點(diǎn)可以獲取更多的感知數(shù)據(jù)。