基于改進ACO的WSN感知數(shù)據(jù)傳輸策略研究

張雅瓊，張 慧，鄭歡歡

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

(2)每個傳感器節(jié)點具有相同的初始能量與計算能力；

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

(4)每個節(jié)點知道它自己的坐標值；

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

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

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

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

圖2 無線通信能耗模型

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

d

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

d

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

d

能量損耗。參數(shù)

ξ

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

ξ

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

E

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

L

比特數(shù)據(jù)所消耗的能量如式(1)所示：

(1)

其中，

d

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

(2)

(

x

,

y

)與(

x

,

y

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

i

與接收節(jié)點

j

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

d

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

d

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

d

。

(3)

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

d

，接收方接收

L

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

E

(

M

)=

E

*

L

(4)

1.3 路由策略

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

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

2 改進的路由方案

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

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

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

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

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

2.1 簇頭選舉與簇的形成

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

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

(5)

其中，

p

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

r

是當前運行的輪數(shù)；

E

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

E

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

T

(

n

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

d

和

d

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

(6)

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

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

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

2.3 基于ACO的簇間路由

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

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

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

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

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

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

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

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

i

的螞蟻選擇去簇頭

j

的概率由式(7)給出：

(7)

其中，

γ

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

τ

表示信息素軌跡，

η

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

α

和

β

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

α

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

β

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

i

和

j

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

(8)

τ

(

t

+1)=(1-

v

)*

τ

(

t

)+

δ

*

v

*

τ

(

t

+1,

t

)

(9)

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

3 算法仿真與性能分析

3.1 仿真環(huán)境

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

表1 仿真參數(shù)

3.2 性能分析

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

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

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

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

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

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

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

圖5 隨著網(wǎng)絡(luò)運行發(fā)送給sink節(jié)點的數(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é)點作為簇頭，然后sink節(jié)點根據(jù)無線傳感器節(jié)點與簇頭的距離形成簇邊界，一旦選定了簇頭并確定了簇的邊界即完成了分簇，之后利用ACO算法以最小能耗代價確定從簇頭到sink節(jié)點的多跳路徑。網(wǎng)絡(luò)采用二級分層結(jié)構(gòu)，簇內(nèi)基于TDMA進行數(shù)據(jù)發(fā)送，簇間采用多跳路由發(fā)送數(shù)據(jù)到sink節(jié)點。仿真結(jié)果表明，采用LEACH-ACO算法的無線傳感器網(wǎng)絡(luò)比使用LEACH算法的網(wǎng)絡(luò)極大地提高了生存時間，同時也大幅提升了網(wǎng)絡(luò)的吞吐量，sink節(jié)點可以獲取更多的感知數(shù)據(jù)。