麥曉冬

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

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

1 有向分簇的相關內容

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

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

有向分簇 傳感器網絡中簇的結構有固定的方向，節(jié)點上報的全部數據都沿著接近Sink的方向傳輸，簇內其他節(jié)點的位置都沒有簇頭的位置離Sink節(jié)點近。

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

圖1 無向分簇示意圖

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

圖2 有向分簇示意圖

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

2 有向分簇的能耗分析

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

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

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

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

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

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

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

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

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

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

3 DCA算法設計

3.1 全局分簇算法

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

條件1分簇時，所有節(jié)點必須要進行當前能量的檢測，此能量為Qc(i)(i=1，2，…，n)，同時還需要設定相應定時器，設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)根據hi=h0［Q0-Qc(i)/Q0］設置一個計數器timer;

(2)根據L0調整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信息且設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 局部調整策略

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

4 測試結果

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

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

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

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

圖4 參數λ對能量均衡性的影響

權衡考慮參數λ的取值結合圖3和圖4，λ的值設置為0.1～0.2較為合理。

圖5 算法能量效率比較

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

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

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

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

5 結論

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

［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］張品，孫巖.一種新的無線傳感器網絡DV-Hop算法［J］.電子器件，2010，33(1):117-120.

［3］尚鳳軍，Mehran Abolhasan，Tadeusz Wysocki.無線傳感器網絡的分布式能量有效非均勻成簇算法［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］胡倩，陳新.分簇無線傳感器網絡中密度感知的自適應占空比機制的研究［J］.傳感技術學報，2013，26(1):105-109.

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

［7］沈琳，是湘全.無線傳感器網絡中數據融合對分簇網絡壽命的影響［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.