蘭婷婷, 秦丹陽, 孫冠宇

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

0 引 言

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

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

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

1 模型的設(shè)計與描述

1.1 花粉算法

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

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

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

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

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

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

(1)

(2)

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

(3)

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

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

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

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

Step 1 簇的形成BS根據(jù)收到的節(jié)點位置和節(jié)點剩余能量等信息，執(zhí)行聚類過程并把給定簇中的簇頭ID發(fā)送給節(jié)點，節(jié)點在此基礎(chǔ)上形成簇。節(jié)點和BS之間的所有通信都通過簇頭進行，由于每個節(jié)點的ID、位置信息和剩余能量都會保存在BS中，因此可以根據(jù)節(jié)點的狀態(tài)進行實時的更新，如圖2所示。當現(xiàn)有簇中沒有節(jié)點能滿足設(shè)定的閾值時，則觸發(fā)重新聚類，在此期間，新的閾值會重新被設(shè)定。在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的能量逐漸接近所設(shè)定閾值時，將通過廣播的方式來提示所有節(jié)點啟動簇頭重選過程。此時節(jié)點將自身剩余能量的信息發(fā)送給CH，CH將其和這一輪的相關(guān)數(shù)據(jù)一起中繼到BS。當基站接收到數(shù)據(jù)后，則更新傳感器節(jié)點的相關(guān)信息，并利用FPA對簇頭進行重選。簇頭重選如圖4所示。

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

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

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

(4)

式中：P為網(wǎng)絡中消耗的總功率；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為簇頭經(jīng)歷的路徑損耗，Ple為節(jié)點經(jīng)歷的路徑損耗，如式(7)和式(8)所示。

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

(7)

Pla=38.5+20·log2D2

(8)

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

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

2 仿真結(jié)果與性能分析

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

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

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

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

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

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

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

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

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

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

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

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

3 花粉算法的特征分析

為了驗證采用花粉算法是否為聚類網(wǎng)絡中節(jié)點的最佳選擇，本節(jié)將通過研究不同簇數(shù)的能效和節(jié)點數(shù)量的關(guān)系來證明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é)點的增加會大大收斂，在聚類網(wǎng)絡中，應用FPA算法能夠獲得更高的能效，而且不受聚合簇數(shù)量的影響。因此，網(wǎng)絡可以根據(jù)其他特征需求選擇簇的數(shù)量，同時不會影響聚類網(wǎng)絡中的能效。

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

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

在ODAM中，聚合簇的數(shù)量對無線傳感器網(wǎng)絡的性能也產(chǎn)生一定的影響。為了獲得最佳數(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

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

5 結(jié) 論

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