基于花粉算法的廣域無線傳感器網絡最優(yōu)數(shù)據(jù)聚合設計

蘭婷婷, 秦丹陽, 孫冠宇

(黑龍江大學 電子工程學院, 哈爾濱 150080)

0 引 言

無線傳感器的廣泛使用以及將其組織到網絡中時會存在許多部署問題，能量的高效利用是最主要問題之一。因此，需要有效地使用傳感器中有限的能量來維持網絡性能，使服務質量(Qualit of seyrvice, QoS)不會受到影響[1]。為此，研究者開發(fā)了許多節(jié)能技術，如媒體接入控制(Media access control, MAC)協(xié)議、路由協(xié)議和數(shù)據(jù)聚合技術等，其中數(shù)據(jù)聚合是最常用的技術，能夠有效降低網絡能耗，減少網絡擁塞[2]。除了提高系統(tǒng)效率之外，數(shù)據(jù)聚合還有助于培養(yǎng)可擴展的網絡[3]，能夠輕松擴展到大型系統(tǒng)。

目前，無線傳感器網絡(Wireless sensor network,WSN)中的聚類協(xié)議已被廣泛研究，典型的聚類協(xié)議LEACH是一種基于數(shù)據(jù)聚合的層次型路由協(xié)議，通過隨機方式進行簇頭(Cluster head, CH)的選擇，來避免簇首能量消耗過度，同時將數(shù)據(jù)進行聚合處理能夠有效地減少網絡中的通信量[4]，但是LEACH不能使用任何目標函數(shù)提供CH的最佳選擇，且僅在小覆蓋區(qū)域上進行有效工作，所以不能用于大規(guī)模的WSN中。HEED是一種分簇聚類協(xié)議[5]，其分簇速度更快，能產生分布更加均勻的簇頭、更合理的網絡拓撲[6]。HEED算法中簇頭會直接和基站進行通信，由于沒有考慮它們之間的距離，會造成節(jié)點能量快速消耗[7]。在解決廣域的無線傳感器網絡聚類問題時，采用扇形聚類協(xié)議(Fan-shaped clustering, FSC)進行簇頭的選擇既簡單又很有效，有利于降低網絡中通信成本，但是FSC算法在執(zhí)行的時候不強調所需的QoS[8]。也可以在網絡中使用其他聚類方法，包括K均值和模糊C均值[9]，這兩種方法都是采用隨機選擇k個中心點，剩余節(jié)點與最近的中心點分組，但是如果沒有謹慎地選擇起始點，則這兩種聚類方法都可能產生較大的分歧或收斂到局部最優(yōu)。文獻[10]提出了一種適用于大規(guī)模傳感器網絡的聚類算法，該算法在實現(xiàn)過程中考慮了聚合網絡規(guī)模，信息表達能力和能量消耗情況，能夠提供更好的網絡性能。在廣域的無線傳感器網絡中研究聚類算法和路由協(xié)議時，由于接收器附近的節(jié)點經歷更多的數(shù)據(jù)量，會出現(xiàn)能耗不平衡問題[11-12]。因此，文獻[13]提出了一種基于能量感知的聚類路由協(xié)議，該協(xié)議能夠對網絡進行聚類并選擇最優(yōu)的簇頭，并通過改進的布谷鳥搜索算法進行了優(yōu)化。

本文基于WSN數(shù)據(jù)聚合技術，設計一種最優(yōu)廣域無線傳感器網絡數(shù)據(jù)聚合模型(Optimal data aggregation model, ODAM)。研究和分析了標準花粉算法的搜索性能，利用花粉算法在基站(Base station, BS)進行集中式聚類，通過目標函數(shù)能夠獲得性能最佳的聚合簇。利用相關數(shù)據(jù)進行仿真實驗，驗證算法的有效性及可行性。

1 模型的設計與描述

1.1 花粉算法

自然界中植物的授粉過程包括自花授粉和異花授粉兩種方式，花粉算法是根據(jù)植物花朵授粉行為機理進行模擬而設計的一種新型啟發(fā)式優(yōu)化算法，算法的局部搜索和全局搜索過程分別模擬自花授粉和異花授粉行為[14]。將花粉算法建立以下規(guī)則：

規(guī)則 1:植物的異花授粉過程被模擬為全局搜索過程，其中花粉個體服從Levy飛行機制；

規(guī)則 2:植物的自花授粉被模擬為局部搜索過程；

規(guī)則 3:花的恒常性與授粉過程中兩朵花的繁殖概率或相似度成比例。

規(guī)則 4:局部搜索和全局搜索由轉換概率p∈[0,1]控制，當Rand>p時，進行全局搜索，反之進行局部搜索。

對于全局搜索過程，花粉粒子由昆蟲和鳥類等傳粉者攜帶，能夠傳播較遠距離，因為昆蟲，鳥類等生物媒介可以飛行或移動較長距離。將上述規(guī)則用數(shù)學表達式進行表示，規(guī)則(R1)和(R4)表示為：

(1)

(2)

而對于局部搜索，可以把上述規(guī)則(R2)和(R3)定義為：

(3)

1.2 最優(yōu)數(shù)據(jù)聚合模型

假設給定的網絡區(qū)域中存在N個節(jié)點或網絡設備，將傳感器網絡區(qū)域劃分為N個同心圓，也可以稱為層，基站位于圓心處，如圖1所示。在聚合網絡中，簇節(jié)點間的通信開銷比較大，會減少網絡的生命周期。在最優(yōu)數(shù)據(jù)聚合模型(ODAM)中，通過在基站中使用花粉算法可以對網絡區(qū)域中每一層的節(jié)點進行聚類，能夠使得節(jié)點和BS之間進行有效的通信。對于每一層中的聚合簇，簇節(jié)點將收集到的數(shù)據(jù)信息發(fā)送給簇頭節(jié)點，簇頭將對收到數(shù)據(jù)信息進行聚合，并且還可以作為中繼節(jié)點將聚合后的數(shù)據(jù)包中繼給下一層的簇頭節(jié)點，最終會形成簇頭覆蓋的網絡。

圖1 最優(yōu)廣域傳感器網絡數(shù)據(jù)聚合模型Fig.1 Aggregation model of optimal wide-area sensor network data

與其他類似網絡不同的是，ODAM將聚類、簇頭選擇、簇頭重選、信令以及重新聚類[15-16]等過程限制在基站中進行，目的是為了減少節(jié)點間的計算開銷，有助于延長傳感器節(jié)點的壽命。具體實現(xiàn)過程如下：

Step 1 簇的形成BS根據(jù)收到的節(jié)點位置和節(jié)點剩余能量等信息，執(zhí)行聚類過程并把給定簇中的簇頭ID發(fā)送給節(jié)點，節(jié)點在此基礎上形成簇。節(jié)點和BS之間的所有通信都通過簇頭進行，由于每個節(jié)點的ID、位置信息和剩余能量都會保存在BS中，因此可以根據(jù)節(jié)點的狀態(tài)進行實時的更新，如圖2所示。當現(xiàn)有簇中沒有節(jié)點能滿足設定的閾值時，則觸發(fā)重新聚類，在此期間，新的閾值會重新被設定。在BS中進行簇節(jié)點間距離和能量的計算，能夠降低節(jié)點間的能量消耗。

Step 2 數(shù)據(jù)聚合在成簇階段完成后，第N層的節(jié)點將數(shù)據(jù)發(fā)送給簇頭，簇頭將收集到的數(shù)據(jù)進行聚合并將聚合后的數(shù)據(jù)發(fā)送給鄰近的簇頭，作為來自第(N-1)個環(huán)的中繼節(jié)點，直到數(shù)據(jù)被中繼到BS為止。數(shù)據(jù)聚合的模型如圖3所示。

圖3 數(shù)據(jù)聚合Fig.3 Data aggregation

Step 3 簇頭重選隨著節(jié)點工作時間的增加，節(jié)點自身的能量不斷減少，當CH的能量逐漸接近所設定閾值時，將通過廣播的方式來提示所有節(jié)點啟動簇頭重選過程。此時節(jié)點將自身剩余能量的信息發(fā)送給CH，CH將其和這一輪的相關數(shù)據(jù)一起中繼到BS。當基站接收到數(shù)據(jù)后，則更新傳感器節(jié)點的相關信息，并利用FPA對簇頭進行重選。簇頭重選如圖4所示。

Step 4 逐層重新聚類在傳感器網絡中，如果給定簇中沒有節(jié)點具有足夠的能量來充當簇頭，則節(jié)點與網絡中的其他簇進行重新分組。當網絡中每一層的聚合簇接近飽和時，BS通過設置簇頭滿足的閾值，對整個層執(zhí)行重新聚類。

1.3 最優(yōu)聚合目標函數(shù)

假設在不影響數(shù)據(jù)包傳輸?shù)那闆r下，成員節(jié)點可以直接向簇頭傳遞數(shù)據(jù)。在廣域的無線傳感器網絡中，為了形成具有高能效的簇，把在單位時間內消耗單位能量所傳輸?shù)目偙忍財?shù)，即效率E設定為ODAM模型所需的目標函數(shù)為：

(4)

式中：P為網絡中消耗的總功率；DR1和DR2分別代表簇頭和節(jié)點的數(shù)據(jù)傳輸速率。

式(4)中的簇頭和簇節(jié)點的數(shù)據(jù)傳輸速率滿足:

(5)

(6)

式中：N和Nc分別為傳感器節(jié)點和聚合簇的數(shù)量；Ze和Za分別代表簇頭和節(jié)點上的陰影；β1為簇頭發(fā)送包的數(shù)量；PTx為簇頭的傳輸功率；D1和D2分別為節(jié)點與基站和簇頭之間的距離；w1為簇頭的帶寬；w2為簇中每個節(jié)點的帶寬；Pla為簇頭經歷的路徑損耗，Ple為節(jié)點經歷的路徑損耗，如式(7)和式(8)所示。

Ple=128.1+37.6·log2(D1/1 000)

(7)

Pla=38.5+20·log2D2

(8)

簇通過最小化節(jié)點、簇頭和基站之間的陰影效應被更換，因此，形成的簇具有較高的能效，且在不影響QoS的情況下有助于延長網絡生命周期。立足于所構建的ODAM模型，結合花粉算法設計的最優(yōu)聚合算法，如算法1所示。

算法1 最優(yōu)聚合算法Algorithm 1 Optimal aggregation algorithm

2 仿真結果與性能分析

在仿真實驗中，無線傳感器節(jié)點被均勻地分布在100 m×100 m的區(qū)域上，其中BS位于網絡區(qū)域中心，仿真參數(shù)如表1所示。本文在評估ODAM性能時考慮了以下指標：

(1) 數(shù)據(jù)包收集率： 在基站處每輪傳輸后所收集的數(shù)據(jù)包數(shù)量與所傳輸總的數(shù)據(jù)包數(shù)量的比值，在無線傳感器網絡中常采用輪數(shù)表示網絡工作時長；

(2) 網絡節(jié)點平均剩余能量： 每輪傳輸結束后網絡中所有節(jié)點的剩余能量與節(jié)點數(shù)量的比值；

(3) 生存節(jié)點數(shù)量： 在每輪傳輸后網絡中運行的節(jié)點總數(shù)。

2.1 數(shù)據(jù)包收集率

數(shù)據(jù)包收集率與輪數(shù)之間的關系如圖5所示?？梢钥闯觯琌DAM在接收器處可以提供更穩(wěn)定且連續(xù)的數(shù)據(jù)包收集率。當數(shù)據(jù)包收集率降至0.9時，HEED和FSC分別出現(xiàn)在網絡生命周期的35%和75%左右，而在網絡生命周期的86%之后，ODAM中數(shù)據(jù)包收集率才降至0.9，可以看出ODAM的網絡壽命明顯優(yōu)于HEED和FSC。雖然曲線適用于較短的網絡工作時間，但在數(shù)據(jù)包收集率方面可以看出所提出的ODAM模型要比其他兩種算法更加穩(wěn)定。

圖5 數(shù)據(jù)包收集率的比較

2.2 網絡節(jié)點平均剩余能量

節(jié)點平均剩余能量(Residual energy of nodes, REN)隨著輪數(shù)的變化情況如圖6所示。對比三條曲線，在節(jié)點經歷3 000輪左右傳輸時，HEED和FSC的節(jié)點的平均剩余能量值均降為0，網絡開始失效，而ODAM系統(tǒng)中的平均剩余能量還有900 mJ左右，因此,網絡工作時間要比其他兩種聚合算法更長。在初始階段，F(xiàn)SC中節(jié)點的平均剩余能量下降的較為緩慢，但在1 400輪后開始迅速下降，而ODAM中節(jié)點的能量減少速度要相比于HEED和FSC要更加地穩(wěn)定。在ODAM模型中，網絡區(qū)域采用分層結構的設計，使得簇頭傳輸數(shù)據(jù)時所跨越的距離進一步減少，節(jié)省了傳感器節(jié)點的能量。

圖6 節(jié)點平均剩余能量的比較Fig.6 Comparison of average REN

2.3 網絡生存節(jié)點數(shù)量

三種算法隨著輪數(shù)的增加，網絡中運行節(jié)點數(shù)量的比較圖如7所示?？梢钥闯?，相比于HEED和FSC來說，ODAM在初始階段節(jié)點數(shù)量的減少更為緩慢。由于ODAM試圖將聚合簇中大多數(shù)計算限制在基站中進行，因此，可以減少節(jié)點間因計算產生的能量消耗，有助于增加節(jié)點的壽命。圖中當FSC和HEED進行4 000輪時，幾乎已無節(jié)點存活，此時,ODAM依然有將近2 000個節(jié)點存活，說明ODAM的網絡生命周期要遠優(yōu)于HEED和FSC。

3 花粉算法的特征分析

為了驗證采用花粉算法是否為聚類網絡中節(jié)點的最佳選擇，本節(jié)將通過研究不同簇數(shù)的能效和節(jié)點數(shù)量的關系來證明FPA的選擇。其中聚合簇Cluster的簇數(shù)n分別取值2、4和6，如圖8所示。可以看出，聚合簇Cluster中節(jié)點數(shù)較少時，n=4時具有能效最高，如當聚合簇Cluster中有20個節(jié)點時，三種簇數(shù)(n=6、4、2)的能效分別近似為12.5、13.5和12.2Mbits·J-1。但是隨著聚合簇Cluster中的節(jié)點數(shù)量不斷增加，這種變化趨勢將發(fā)生改變。比如當節(jié)點增加到200個時，三種簇數(shù)(n=6、4、2)的能效分別近似1.55、1.5和1.45Mbits·J-1。三種簇數(shù)的能效值隨著節(jié)點的增加會大大收斂，在聚類網絡中，應用FPA算法能夠獲得更高的能效，而且不受聚合簇數(shù)量的影響。因此，網絡可以根據(jù)其他特征需求選擇簇的數(shù)量，同時不會影響聚類網絡中的能效。

圖8 花粉算法的特征分析Fig.8 Characteristic analysis of flower pollination algorithm

4 聚合簇數(shù)量的分析

在ODAM中，聚合簇的數(shù)量對無線傳感器網絡的性能也產生一定的影響。為了獲得最佳數(shù)量的聚合簇，通過對不同數(shù)量的簇在平均數(shù)傳輸速率和計算時間上進行比較能夠有效地進行聚合簇的選擇。

三種不同簇數(shù)的平均數(shù)據(jù)傳輸速率的比較如圖9所示，可以看出，三種簇數(shù)的平均數(shù)據(jù)傳輸速率隨著節(jié)點數(shù)量的增加均呈逐漸遞減的趨勢，而且簇數(shù)越大，平均數(shù)據(jù)傳輸速率越大，即6個簇中的的平均數(shù)據(jù)傳輸速率最高，當聚合簇中有50個節(jié)點時，三種簇數(shù)(n=6、4、2)的平均數(shù)據(jù)傳輸速率分別為125、75和25 kbps。雖然這種趨勢隨著節(jié)點數(shù)量的增加而繼續(xù)保持著，但是速率值變化的差異卻減小了。

三種簇數(shù)隨著節(jié)點數(shù)量的增加，形成聚合簇所需計算時間的比較情況如圖10所示。三種簇數(shù)的計算時間均隨著節(jié)點數(shù)量的增加而增加，同時，聚合簇的簇數(shù)越大所需的計算時間也越多，即聚合簇數(shù)量為6時，發(fā)現(xiàn)所計算時間最多。當聚合簇中有200個節(jié)點時，三種簇數(shù)(n=6、4、2)所需的計算時間分別為0.9、0.75和0.6 s。

圖10 計算時間的比較Fig.10 Comparison of computational time

為了達到這個平衡的要求，需要去平衡網絡支持的平均數(shù)據(jù)傳輸速率與其運行過程中所涉及的計算時間，在分析聚合模型時選擇簇數(shù)為4的聚合簇。所提出的ODAM模型使用有效的FPA算法進行聚類，使得單位能耗下能夠獲得最大的數(shù)據(jù)速率，實現(xiàn)在不影響QoS的情況下獲得較高的能效。

5 結 論

設計了一種最優(yōu)廣域無線傳感器網絡數(shù)據(jù)聚合模型，該模型通過采用FPA算法與目標函數(shù)結合進行簇頭的最佳選擇，從而獲得最優(yōu)的簇集合，并能夠在簇間和簇內的通信成本上取得平衡。進一步將聚類和簇頭重選等類似活動限制在BS，使得節(jié)點不受開銷的影響，同時，將數(shù)據(jù)進行分層傳輸，有助于提高數(shù)據(jù)傳輸?shù)臏蚀_性和節(jié)省網絡中的能量。在考慮節(jié)點的傳輸功率和帶寬的情況下，實驗結果表明，ODAM較其他聚類算法能夠有效地延長網絡壽命，由于使用了優(yōu)化功能，在接收端能夠接收到連續(xù)的數(shù)據(jù)包，在不影響QoS的情況下，使得傳感器網絡中能量能夠被高效地利用。但是由于對花粉算法的提出時間較短，花粉算法的理論還需進一步的完善，在后續(xù)的研究中，可以考慮借鑒智能優(yōu)化算法的改進來提高花粉算法的性能。