基于雙簇頭網格調度的WSNs能量空洞緩解*

張人上, 曲開社

(1.山西財經大學,山西 太原 030006；2.山西大學 計算機與信息技術學院，山西 太原 030006)

基于雙簇頭網格調度的WSNs能量空洞緩解*

張人上1, 曲開社2

(1.山西財經大學,山西 太原 030006；2.山西大學 計算機與信息技術學院，山西 太原 030006)

設計了基于雙簇頭網格調度反饋結構的無線傳感器網絡(WSNs)非均布節點能量空洞緩解機制，并設計了主副簇頭網格聚類算法，形成網格單元；依據節點身份(ID)與網格ID，定義鑒定規則，確定網格中的WSNs節點；構造了網格單元中心點的計算數學模型，依據該中心點坐標確定每個網格單元的簇頭，調度網格內的節點；構建了主—副—相鄰簇頭的數據調度傳輸結構，有效分散了節點所承擔的負載,并對本機制性能進行理論分析。仿真結果表明：與其他機制相比，在非均布節點環境下，該算法更能有效避免網絡能量空洞，其節點持續時間最長，顯著消除了“漏斗效應”。

能量空洞；雙簇頭網格聚類；漏斗效應；數據收集；網絡效率

0 引 言

無線傳感器網絡(wireless sensor networks,WSNs)已經在目標追蹤、國防等領域得到了飛快發展，成為當前的研究熱點[1]。 在WSNs中，靜態Sink節點在收集數據時，其附近的節點都有可能參與數據轉發，使得其能量迅速消耗，導致網絡時效與癱瘓，產生了“能量空洞”，顯著降低了網絡壽命[2]。能量空洞形成后，會形成“漏斗效應”[3]。對此，余育青等人[4]構造設計了基于時空特性的網絡能量空洞研究，測試結果表明其算法能夠顯著提高網絡壽命。李斌等人[5]提出了基于蟻群算法的WSNs節點能量空洞規避機制，實驗結果顯示其機制顯著提高了網絡壽命。劉安豐等人[6]提出了異構傳感器網絡能量空洞分析與避免機制，實驗結果體現了該算法的合理性。

但是這些算法的優異性都是在節點以均勻分布條件下取得的，在非均勻分布情況下，這些機制容易形成嚴重的能量分布不均，無法有效地規避能量空洞現象；且這些算法都是隨機擇取主簇頭，導致網絡效率降低[7～9]。

為了解決上述不足，本文設計了基于雙簇頭網格調度反饋結構的WSNs非均布節點能量空洞緩解機制,并在仿真平臺上測試本文機制性能。

1 基于雙簇頭網格聚類算法設計

1.1 網格單元的形成

將整個網絡區域分割成尺寸相等的2D靜態Sink網格，見圖1。每個網格都是尺寸為d×d的方形單元；且每個網格的鑒定都是依據自身的IDCi來完成，其中，i=0,1,2,…，n代表網格單元ID的引擎。在圖中，從左到右，第一行的網格單元ID依次為C0,C1,C2,…,C5；同樣的，第二行的網格單元ID依次為C6,C7,C8,…,C11，其他的，依此類推。整個網絡區域面積為X×Y(X=Y)，(圖中X=Y=30)。起初，每個網格單元的長度為固定值d(圖中d=5)，則定義2個變量α,β

(1)

(2)

其中，X,Y分別代表網絡區域的長度與寬度。

若網絡區域內所形成的網格單元數量為Z,則

Z=α×β.

(3)

由于每個網格單元的IDCi與網絡區域面積相關,故網格單元的IDCi的坐標如下

(4)

其中，x,y分別代表與網格單元的ID引擎i相關的坐標值

x=i%a,

(5)

y=i/α.

(6)

如圖1所示，X=Y=30，d=5，Z=36，網格引擎i=0,1,2,…,36。為了找出C10的坐標，依據模型(5)～模型(6)，求得x=10 %6=4,y=10/6=1；依據模型(4)，求得C10坐標為

(7)

通過上述程序，可計算出所有網格單元的ID；根據網格單元位置引擎i可得到每個網格單元的坐標。

圖1 網格的形成及其引擎Fig 1 Formation of grid and its engine

1.2 網格單元中心點的數學模型的構造

依據1.1小節得到的網格單元，計算每個單元的中心點坐標，以便確定簇頭

(8)

(9)

其中，Xmid,Ymid分別代表中心點的橫、縱坐標；其余參數與模型(4)相同。

根據圖1，則C10的中心點坐標為(45,15)。

1.3 網格單元中的WSNs節點鑒定

(10)

其中，x(j)代表節點j的橫坐標x值；y(j)代表節點j的縱坐標y值；&代表按位與運算。

按照模型(10),即可確定每個網格單元內的節點，并且將其歸入相應的簇群內。

1.4 簇頭的擇取

1)主簇頭的擇取

本文將與網格單元中心最近的節點視為簇頭。每個節點j坐標(xj,yj)與中心點(Xmid,Ymid)之間的距離D為

(11)

當D最小時，此時的j被擇取為主簇頭；然后借助靜態Sink廣播網格ID、網格單元ID的中心點以及每個網格內的節點ID。通過靜態Sink更新主簇頭信息，以便用于副簇頭的擇取。

2)副簇頭的擇取

主簇頭會擇取能量與之相近，且距離中心點(Xmid,Ymid)最近的節點視為副簇頭

(12)

其中，Esecond代表副簇頭的能量；MT()為取最接近值運算；Eprimary為主簇頭的能量；Di代表節點i與中心點(Xmid,Ymid)之間的最小距離。

3)相鄰簇頭的擇取

由于每個簇頭都包含了靜態Sink的信息，故每個簇頭都會擇取與靜態Sink最近的節點視為相鄰簇頭。

通過主簇頭—副簇頭—相鄰簇頭的數據調度傳輸結構，有效分散了節點所承受的負載，降低了能量消耗速度，有效增加了網絡壽命,見圖2。

圖2 主簇頭—副簇頭—相鄰簇頭調度結構Fig 2 Scheduling structure with main-vice-adjacent cluster head

1.5 數據收集階段

1.6 更新階段

在此階段，當前簇頭會查詢每個節點的能量。根據每個節點的能量ei，對節點進行排序，形成集合A={e1,e2,…，en}；再計算網格單元內所有節點能量的均值Eaverage,并挑選出能量大于Eaverage的節點，當然這些節點均離中心點最近

(13)

令B∈A代表這些能量大于Eaverage的節點。對于B而言，其距離網格單元中心點最近的節點被擇取為簇頭；下一個與中心點最近的節點被視為副簇頭。通過這樣的方式，可確保選取的簇頭始終具有最大的能量，且與網格單元中心點最近。

2 能量空洞緩解機制性能分析

假設整個網絡區域是由n個同心正方形構成，每個同心正方形都是由尺寸為r×r的小網格單元構成。靜態Sink位于網絡區域中心。由圖3，獲取第i個同心正方形面積為

Ai=(2i-1)A1,i≠0,i≥1.

(14)

其中，Ai代表第i個同心正方形面積，則整個網絡區域面積為

(15)

對于A1來說，若其網格單元的數量g,則整個網絡的網格單元總數N為

(16)

最內側同心方形的每個簇頭節點的負載W計算如下

(17)

其中，W為簇頭負載；M為最內側同心方形中簇頭節點數量；Cost為所有簇頭的簇內通信成本。

若ρ為網絡區域內的節點密度；每個節點的數據傳輸率為β,則簇內通信成本c為

c=r2ρβ.

(18)

如圖3所示，最內側同心正方形的簇通信成本為4r2ρβ。因此，第i個同心正方形的簇通信成本為

Cost(i)=(2i-1)×4r2ρβ.

(19)

聯合模型(17)～式(19)，得到所有簇頭的簇內通信成本Cost和負載W為

(20)

(21)

對于本文算法，總的通信跳數V應該是簇間通信成本與簇內通信成本的總和。

簇內通信總成本Z

(22)

簇間通信總成本J

(23)

則V為

(24)

總的通信跳數V體現了節點在網絡中的能量消耗程度，故V越大，則能量消耗越大。對于非均勻節點分布，是不斷變化的；但總的通信跳數V是不變的。

圖3 從Sink中心將網絡劃分為同心方形Fig 3 Divide grid into concentric square from Sink centre

3 仿真結果與分析

借助NS—2平臺來測試本文機制。仿真環境為：采用因特爾I7,2.3 GH z 雙核CPU，400 GB硬盤，8 GB的內存,操作系統為Windows Xp,并設置對照組：文獻[6]與文獻[7]。采用非均勻分布節點進行實驗，其拓撲結構見圖4，實驗參數為：模擬面積500 m×500 m；傳感器節點為200個；靜態Sink為1個；100個網格單元；無線射頻范圍[20,180]m；數據包大小為512 bytes；天線類別為全向；流量類型為CBR；初始能量為1 J；Tx,Rx功率耗散分別為0.0156,0.012 8 W；網格大小為50×50；起初節點的傳輸范圍為[40,150]m。

圖4 仿真所用的拓撲結構Fig 4 Topology structure used in simulation

3.1 網絡效率對比分析

網絡效率是直觀體現能量空洞現象的指標之一[10,11],不同能量空洞避免機制對應的網絡效率見圖5。從圖5中可知，本文設計的能量空洞規避機制具有更高的網絡效率；而對照組兩種算法的網絡效率較低。原因是本文算法設計了雙簇頭網格聚類算法，使簇頭的能量始終保持在較高水平，延長了網絡壽命；而對照組的簇頭擇取方式是隨機的，無法使擇取的新簇頭能量始終保持較大值，導致網絡效率低下。

圖5 不用能量規避機制的網絡效率Fig 5 Network efficiency without using energy evasion mechanisms

3.2 網絡壽命對比分析

本文測試了節點距離與節點壽命的關系曲線，見圖6。從圖中可知，本文機制可有效規避能量空洞，如圖中箭頭所指(曲線凹部分)，節點壽命持續時間達到92 s；而對照組的兩種機制在非均勻分布節點條件下，其能量空洞緩解效果有限，“漏斗效應”出現的比較早。可見本文機制具有更好的能量空洞緩解效果。

圖6 網絡持續時間仿真結果Fig 6 Simulation results of network duration time

為了直觀反映網絡壽命，本文測試不同機制的網絡壽命，見圖7。從圖中可知，隨著節點數量的增加，三種不同機制對應的網絡壽命都在延長；但本文機制的網絡壽命最長。主要原因是本文構造了雙簇頭網格調度反饋結構，有效分散了節點的負載，通過相鄰簇頭的反饋，達到簇頭能量持續更新。

圖7 網絡壽命測試結果Fig 7 Tests results of network lifetime

3.3 基于Sink的數據收集率對比分析

圖8為不同緩解機制的數據收集率測試結果。從圖中可知，隨著節點數量的增加，其數據收集率先增大后下降；但本文機制在節點數據為75個時，其收集率達到最大值，約為95.86 %；而對照組都是100個節點時，達到最大收集率，分別為93.75 %(文獻[6])，91.07 %(文獻[7])。

圖8 不同能量空洞緩解機制的數據收集率測試結果Fig 8 Result of data collection rate test of different energy hole alleviation mechanisms

3.4 平均能量耗散對比分析

圖9為距離靜態Sink的不同位置節點的能量耗散測試結果。從圖中可知，隨著距離的增大，能量耗散逐步減小，見圖中箭頭所指；但本文機制的能量耗散最小，約為0.63 J；文獻[6]算法的能量耗散最大，為0.86 J。可見本文機制能夠有效緩解能量空洞。

圖9 能量耗散測試結果Fig 9 Tests results of energy dissipation

圖10為網絡平局能量耗散測試結果。從圖中可以看到，隨著節點數量則增加，三種不同機制的平均能量耗散都在增大；但是本文機制的能量耗散始終是最小。這與圖9得到的結論是一致。根據模式(22)～模式(24)可知，由于文獻[6,7]算法所需的節點密度較大，直接使得簇內通信總成本增大，最終使得總的通信跳數V增多，從而造成平均能量耗散比本文大。

4 結 論

本文設計了雙簇頭網格聚類算法，并將其用于WSNs非均布節點能量空洞緩解問題，且構造了主簇頭—副簇頭—相鄰簇頭的數據調度傳輸結構，由主簇頭調度簇間通信，由副簇頭調度簇內通信，通過相鄰簇頭將能量與位置信息反饋給主簇頭，分散了節點所承擔的負載，完成數據更新與廣播。測試結果驗證了本文機制的優越性。

圖10 不同能量空洞緩解機制的平均能量耗散測試結果Fig 10 Average energy dissipation tests results of different energy hole alleviation mechanisms

[1] Arora R,Sandhu S S ,Agarwal P.A proposal for deployment of wireless sensor network in day-to-day home and industrial app-liances for a greener environment[J].Advances in Intelligent Systems and Computing，2014，236(78)：1081-1086.

[2] LU Yuting,Wang Weiyang.Energy hole solution algorithm in wireless sensor network[J].Journal of Networks,2014,9(4)：956-963.

[3] Diwakaran S.Energy efficient scheduling in wireless sensor networks[J].International Journal of Scientific Engineering and Research，2014，2(1)：48-51.

[4] 余育青，郝 平.WSNs中基于時空特性的網絡能量空洞研究[J].計算機工程與應用，2013，49(15)：105-112.

[5] 李 斌，王 鎮，劉學軍.無線傳感器網絡中基于蟻群算法的能量空洞規避策略[J].計算機科學，2013，40(8)：66-71.

[6] 劉安豐,任 炬,徐 娟.異構傳感器網絡能量空洞分析與避免研究[J].軟件學報，2012，23(9)：2438-2448.

[7] Zhang X,Wu Z.The balance of routing energy consumption in wireless sensor networks[J].ACM Journal of Parallel and Distributed Computing,2011,71(7):1024-1033.

[8] Lin K,Chen M.Balancing energy consumption with mobile agents in wireless sensor networks[J].Journal of Future Generation Computer Systems,2012,28(2):446-456.

[9] Martaa M,Cardei M.Improved sensor network lifetime with multiple mobile sinks[J].Journal of Pervasive and Mobile Computing,2009,5(5):542-555.

[10] Yan R,Yang Y,Kong X P.A non-uniform node distribution policy for routing holes avoidance[J].Achievements in Engineering Sciences，2014，13(6)：1424-1429.

[11] Liu A,Liu Z H,Nurudeen M.An elaborate chronological and spatial analysis of energy hole for wireless sensor networks[J].Computer Standards & Interfaces，2013，35(1)：132-149.

Energy hole alleviation of WSNs based on dual cluster head grid scheduling*

ZHANG Ren-shang1, QU Kai-she2

(1.Shaanxi University of Finance and Economics,Taiyuan 030006,China;2.School of Computer & Information Technology,Shanaxi University,Taiyuan 030006,China)

WSNs energy hole alleviate algorithm based on dual cluster grid-based scheduling is designed,primary and secondary cluster head grid clustering algorithm is designed to form grid cells; nodes are identified according to nodes ID and grid ID; and the computer math model of centre point of grid cell is constructed to determine the cluster head of each cell grid for scheduling the node in cell; as well as data scheduling transmission structure with primary-secondary-neighboring cluster heads is constructed to effectively disperse load of nodes,and theory analysis is carried out on performance of this scheme.Simulation results show that compared with others mechanism,this algorithm effectively avoid energy hole,and node duration time is longest under the conditions of non-uniformly distributed nodes,remarkably eliminate‘funnel effect’.

energy hole; dual cluster head grid clustering; funnel effect; data gathering; network efficiency

10.13873/J.1000—9787(2014)10—0133—04

2014—07—11

山西省自然科學基金資助項目(20120005)

TP 393

A

1000—9787(2014)10—0133—04

張人上(1978-)，男，山西忻州人，碩士，講師，主要研究方向為無線傳感器網絡。