面向數(shù)據(jù)聚集有向分簇算法在傳感器網(wǎng)絡(luò)中的應(yīng)用

麥曉冬

(廣東輕工職業(yè)技術(shù)學院，廣州510300)

傳感器網(wǎng)絡(luò)中使用面向數(shù)據(jù)聚集算法，網(wǎng)絡(luò)能量的節(jié)省通常通過分簇機制來完成。TEEN、LEACH和HEED等是傳統(tǒng)的分組算法。動態(tài)分簇算法和分布式成簇算法等是目前出現(xiàn)的一些新的分簇算法，這些新的算法優(yōu)化了簇頭選擇和節(jié)點能耗均衡性等方面，但是節(jié)點能量利用效率和網(wǎng)絡(luò)中存在的數(shù)據(jù)回傳問題卻沒有得到很好的優(yōu)化。文章提出的有向分簇算法能很好的解決這些問題，此算法的思想是有效控制簇的結(jié)構(gòu)，使網(wǎng)絡(luò)中所有的節(jié)點傳輸方向全部都沿著接近Sink的方向進行，這樣數(shù)據(jù)回傳造成的能量浪費問題得到了解決，所以節(jié)點能量利用效率得就提高了［1-2］。

1 有向分簇的相關(guān)內(nèi)容

數(shù)據(jù)回傳 網(wǎng)絡(luò)中所有的節(jié)點傳輸方向全部都沿著接近Sink的方向進行，部分數(shù)據(jù)沿著遠離Sink節(jié)點的方向傳輸。

無向分簇 網(wǎng)絡(luò)中所有的簇的結(jié)構(gòu)沒有固定的方向，任何節(jié)點都能是簇頭。

有向分簇 傳感器網(wǎng)絡(luò)中簇的結(jié)構(gòu)有固定的方向，節(jié)點上報的全部數(shù)據(jù)都沿著接近Sink的方向傳輸，簇內(nèi)其他節(jié)點的位置都沒有簇頭的位置離Sink節(jié)點近。

無向分簇示意圖如圖1所示，有向分簇的示意圖如圖2所示。

圖1 無向分簇示意圖

通過圖1可以看出，節(jié)點的數(shù)據(jù)沒有完全沿著Sink的方向進行傳輸，存在數(shù)據(jù)回傳問題，通過圖2可以看出沒有節(jié)點的數(shù)據(jù)沿著遠離Sink的方向傳輸，不存在數(shù)據(jù)回傳問題［3-4］。

圖2 有向分簇示意圖

有向分簇時，不但簇的劃分區(qū)域是固定的，而且簇頭也是唯一的。為了解決簇頭節(jié)點的能量消耗不均衡問題，動態(tài)劃分簇的區(qū)域，節(jié)點可以處于不同的簇中，不但能擔任某一簇簇頭，而且還能是其他的簇的普通節(jié)點。

2 有向分簇的能耗分析

設(shè)節(jié)點x向節(jié)點y發(fā)送nbit的數(shù)據(jù)，兩節(jié)點之間的距離為L，則在傳輸過程中發(fā)送

能耗為Qtr(n，L)可表示為:

式(1)中，Qel是接收能量損耗;Qam是功放能耗;L0是閾值;如果滿足L＜L0的條件則采用自由空間模型，該模型功率放大能耗系數(shù)為εfs;L≥L0時采用多經(jīng)衰減模型，該模型功率放大能耗系數(shù)為εmp。

接收能耗Qr(n，L)可表示為:

根據(jù)上面所述能耗模型，下面對有向分簇的能耗特點進行了一般性的分析。設(shè)把某個區(qū)域劃分為1個簇，這個簇中包含x個傳感器節(jié)點，其中傳感器節(jié)點y和Sink節(jié)點的距離是最近的，此距離設(shè)為Li;設(shè)L0是無線傳輸距離閾值，并且不小于任何兩個節(jié)點之間的距離;族內(nèi)任何一個節(jié)點的數(shù)據(jù)采集量都是一樣的，假設(shè)都是sbit，同時把這些數(shù)據(jù)都傳輸?shù)?Sink 節(jié)點［5-6］。

設(shè)節(jié)點y是簇頭，節(jié)點數(shù)量為x，如果采用有向分簇，則總的數(shù)據(jù)傳輸能耗可表示為:

式(3)中:Qi→y是節(jié)點i發(fā)送給y的數(shù)據(jù)收發(fā)能耗;Lyi是此兩個節(jié)點的距離;Qy→k是y發(fā)送給Sink節(jié)點的能耗。

無向分簇時，任何節(jié)點都能是簇頭，這和有向分簇是不一樣的。設(shè)簇內(nèi)的節(jié)點o(o≠y)為簇頭，其中o不等于y，設(shè)L0為節(jié)點o到Sink節(jié)點的距離，同時滿足L0=Ly+ΔL的條件。此時簇頭o的數(shù)據(jù)傳輸能耗可表示為:

兩種不同分簇方法下的數(shù)據(jù)傳輸能耗之差為:

因傳感器節(jié)點兩兩之間距離均小于L0，故

3 DCA算法設(shè)計

3.1 全局分簇算法

只有滿足以下2個條件才行。

條件1分簇時，所有節(jié)點必須要進行當前能量的檢測，此能量為Qc(i)(i=1，2，…，n)，同時還需要設(shè)定相應(yīng)定時器，設(shè)hi=h0［Q0-Qc(i)/Q0］是時間長度，此式中h0是基準時間，

條件2如果x節(jié)點未收到其他節(jié)點發(fā)送的申請簇頭消息HAM(Head Application Message)，或者雖然收到了y節(jié)點的HAM消息，前提是定時器截止，但y節(jié)點與Sink節(jié)點的距離Lyl比i節(jié)點到Sink節(jié)點的距離Lxl遠，則x節(jié)點傳出本身的HAM消息。

全局分簇的算法流程如下。

(1)根據(jù)hi=h0［Q0-Qc(i)/Q0］設(shè)置一個計數(shù)器timer;

(2)根據(jù)L0調(diào)整the signal power;

(3)C_timer(i)=0;S_CQM(i)=0;Timer_exp=0;

(4)當 C_timer(i)!=1＆Timer_exp==0

(5)N_HAM(i)=0;

(6)等待并接受HAM信息;

(7)假如節(jié)點x接收到節(jié)點y的HAM消息則N_HAM(i)=1;

(8)如果 N_HAM(i)==1＆Lyl＜Lxl，那么給節(jié)點y發(fā)送1個CAM信息且設(shè)S_CAM(i)=1;

其他情況使N_HAM(i)=0;

(9)如果S_CAM(i)==1則C_timer(i)=1;

(10)如果當前時間h＞hi則Timer_exp=1;

(11)如果 C_timer(i)!=1＆Timer_exp==1

則節(jié)點x發(fā)送出去一個HAM信息;

3.2 局部調(diào)整策略

簇頭向簇內(nèi)節(jié)點轉(zhuǎn)發(fā)任務(wù)都是在分簇之后進行的。個別簇頭節(jié)點的能量消耗可能會比較大，這是由節(jié)點部署密度和部署位置不同造成的。更換簇頭可以讓族內(nèi)節(jié)點能量消耗達到平衡。可以通過2種方式更換簇頭，第1種更換方式是重啟全局性的分簇算法，第2種更換方式是對局部簇頭進行調(diào)整。在只有少部分簇頭節(jié)點消耗能量較多的情況下，用第2種更換方式即可，但是如果大部分簇頭的消耗能量都很多的時候，則需要使用第1種方式對簇頭進行更換，具體的步驟分為3步［8］:各個簇頭首先自查本身的消耗能量情況。設(shè)x是其中的某個簇頭，Qr(x)是這個簇頭的初始能量，當前剩余能量為Qc(x)，若Qr(x)-Qc(x)＞(Q0((為調(diào)節(jié)參數(shù))，此時假設(shè)的簇頭x會向其他的節(jié)點和Sink節(jié)點發(fā)送一個信號，這個信號就是其不再擔任簇頭;然后節(jié)點x會選擇加入其他的族，這個族是靠近自己的鄰近簇，節(jié)點x原先所在的簇會重新選擇一個簇頭;最后Sink節(jié)點會把不再擔任簇頭的節(jié)點數(shù)Ns統(tǒng)計出來，如果出現(xiàn)Ns＞1/2Nt的情況(Nt是簇頭總數(shù))，此時原來存在的簇結(jié)構(gòu)就會自動解散，同時在全網(wǎng)內(nèi)重新選舉簇頭。

4 測試結(jié)果

文章使用的測試平臺是OMNeT++。設(shè)節(jié)點所分布面積為1 km×1 km;各個節(jié)點的初始能量是3 J，數(shù)據(jù)量為1 kbit/min;Qel=50 nJ/bit，無線傳輸距離閾值L0=100 m;功率放大能耗系數(shù) εfs和 εmp的取值為:εfs=10 pJ/(bit·m2)，εmp=0.001 3 pJ/(bit·m4)。試驗中，如果節(jié)點的剩下的能量非常低的時候，也就是還達不到原始能量的5%，此時這個節(jié)點會被認為死亡。

DCA算法的性能受到了調(diào)節(jié)參數(shù)λ影響，實驗測試了該影響，結(jié)果如圖3和圖4所示。由此可知，DCA算法的穩(wěn)定成簇的時間越與參數(shù)λ的值及節(jié)點剩余能量的均方差成正比。而且，DCA算法的性能也受節(jié)點分布密度的影響。當節(jié)點密度較大時，簇頭的能量消耗速度與穩(wěn)定成簇時間成反比。

通過對圖3和圖4的分析，λ的值設(shè)置為0.1～0.2較為合理。

圖3 穩(wěn)定成簇時間受參數(shù)λ的影響

圖4 參數(shù)λ對能量均衡性的影響

權(quán)衡考慮參數(shù)λ的取值結(jié)合圖3和圖4，λ的值設(shè)置為0.1～0.2較為合理。

圖5 算法能量效率比較

GESC、HEED和DCA算法三種分簇算法的能量效率比較結(jié)果如圖5所示。當數(shù)據(jù)傳輸量一定時，DCA算法有較低總能耗，是因為該算法消除了數(shù)據(jù)回傳造成的能量浪費。所以節(jié)點有較高的平均剩余能量。

由圖6可以看出當網(wǎng)絡(luò)運行一定時間后，對HEED算法和GESC算法來說，雖然節(jié)點出現(xiàn)死亡的時間靠后，但節(jié)點死亡率上升很快。主要原因是因為這兩種算法中節(jié)點能量利用較均衡，但在數(shù)據(jù)回傳中能量浪費較多，一段時間后，許多節(jié)點會死亡。

圖6 節(jié)點存活率比較

DCA算法和HEED算法以及GESC算法相比來說較死亡率上升的速度是非常緩慢的，但是節(jié)點死亡時間較早，這對網(wǎng)絡(luò)的影響是可以忽略不計的，由此可知該算法可以延長網(wǎng)絡(luò)的生存周期。

5 結(jié)論

作者針對現(xiàn)存?zhèn)鹘y(tǒng)分簇方法中存在的數(shù)據(jù)回傳問題，文章分析有向分簇的能量高效性，提出了DCA算法，經(jīng)過仿真實驗，證實該算法確實能克服以往算法存在的不足，提高能量的利用率，并將其應(yīng)用于面向數(shù)據(jù)聚集的傳感器網(wǎng)絡(luò)中。

［1］Yu Ming，Kin K Leung，Aniket Malvankar.A Dynamic Clustering and Energy Efficient Routing Technique for Sensor Networks［J］.IEEE Trans on Wireless Communications，2007，6(8):3069-3079.

［2］張品，孫巖.一種新的無線傳感器網(wǎng)絡(luò)DV-Hop算法［J］.電子器件，2010，33(1):117-120.

［3］尚鳳軍，Mehran Abolhasan，Tadeusz Wysocki.無線傳感器網(wǎng)絡(luò)的分布式能量有效非均勻成簇算法［J］.通信學報，2009，30(10):34-43.

［4］Dimokas N，Katsaros D，Manolopoulos Y.Energyefficient Distributed Clustering in Wireless Sensor Networks［J］.Journal of Parallel and Distributed Computing，2010，70:371-383.

［5］胡倩，陳新.分簇無線傳感器網(wǎng)絡(luò)中密度感知的自適應(yīng)占空比機制的研究［J］.傳感技術(shù)學報，2013，26(1):105-109.

［6］柳絮，李金寶，紀守領(lǐng)，等.傳感器網(wǎng)絡(luò)簇頭選舉與調(diào)度策略研究［J］.電子學報，2010，38(8):1770-1775.

［7］沈琳，是湘全.無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)融合對分簇網(wǎng)絡(luò)壽命的影響［J］.電子器件，2009，32(2)43-46.

［8］Heinzelman W R，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wirelessmicrosensor Networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660-670.