基于改進ACO的WSN感知數據傳輸策略研究

張雅瓊，張 慧，鄭歡歡

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

0 引 言

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

LEACH協議分為兩個階段：

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

(2)穩定階段，包括數據感知、聚合、壓縮和傳輸。

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

1 無線傳感器網絡模型

1.1 網絡假設

無線傳感器網絡由大量隨機分布的無線傳感器節點組成。根據節點密度將區域劃分為若干個簇，每個簇都有一個簇頭，簇內成員節點將數據發給簇頭，簇頭將數據轉發給sink節點，如圖1所示。

圖1 無線傳感器網絡模型

網絡模型中做出以下假設：

(1)有一個無線傳感器節點隨機部署并緊密相連的網絡；

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

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

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

(5)網絡中的每個節點都知道圖中其鄰居節點的ID；

(6)每個節點都可以按照網絡能耗模型單獨發送和接收數據包。

1.2 網絡能耗

無線傳感器網絡的傳輸采用無線通信系統中的能耗模型，如圖2所示。

圖2 無線通信能耗模型

發送數據的能耗包括射頻模塊和信號放大器的能耗，接收節點的能耗僅包括接收電路的能耗。信號放大器的能耗根據收發雙方之間的距離

d

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

d

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

d

能量損耗。參數

ξ

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

ξ

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

E

表示發送或接收1比特數據時發送電路或接收電路的能耗。假設無線信道是對稱的，即節點1向節點2發送數據的能耗與節點2向節點1發送數據的能耗完全相同。發送

L

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

(1)

其中，

d

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

(2)

(

x

,

y

)與(

x

,

y

)分別表示發送節點

i

與接收節點

j

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

d

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

d

，而節點之間的距離小于閾值

d

。

(3)

數據傳輸距離為

d

，接收方接收

L

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

E

(

M

)=

E

*

L

(4)

1.3 路由策略

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

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

2 改進的路由方案

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

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

無線傳感器網絡的工作過程如圖3所示。

圖3 網絡運行過程

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

2.1 簇頭選舉與簇的形成

無線傳感器網絡采用集中式簇間網絡拓撲結構。sink節點決定簇頭、簇邊界以及不同簇之間的路由。下面一一解釋。

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

(5)

其中，

p

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

r

是當前運行的輪數；

E

是節點的剩余能量；

E

是節點的初始能量。網絡中的所有節點計算上述函數的值，并選擇

T

(

n

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

d

和

d

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

(6)

2.2 簇內數據傳輸

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

簇頭收到簇成員發送的感知數據后進行數據融合，然后采用簇間多跳路由將信息發送給sink節點。

2.3 基于ACO的簇間路由

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

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

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

(2)自組織網絡。

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

(3)網絡結構的動態性。

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

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

i

的螞蟻選擇去簇頭

j

的概率由式(7)給出：

(7)

其中，

γ

是介于0和1之間的常數，

τ

表示信息素軌跡，

η

表示先驗可用的啟發值，

α

和

β

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

α

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

β

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

i

和

j

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

(8)

τ

(

t

+1)=(1-

v

)*

τ

(

t

)+

δ

*

v

*

τ

(

t

+1,

t

)

(9)

通過反復計算獲取從簇頭到sink節點的最優路徑。

3 算法仿真與性能分析

3.1 仿真環境

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

表1 仿真參數

3.2 性能分析

在建立簇后，LEACH-ACO策略利用ACO算法對簇頭間的路由進行優化，以解決到sink節點的多跳數據傳輸。仿真性能評價采用的指標是網絡生存期(死亡節點數與輪數的關系)與網絡吞吐量(網絡生存期內所有節點發送到sink節點的數據包總數)。

(1)網絡生存期。

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

圖4 隨著網絡運行而增加的死亡節點數

(2)網絡吞吐量。

以網絡生存期內所有無線傳感器節點發送給sink節點的數據包總數來衡量網絡吞吐量。

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

圖5 隨著網絡運行發送給sink節點的數據包總數

4 結束語

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