張人上, 曲開社

(1.山西財經(jīng)大學(xué),山西 太原 030006；2.山西大學(xué) 計算機與信息技術(shù)學(xué)院，山西 太原 030006)

基于雙簇頭網(wǎng)格調(diào)度的WSNs能量空洞緩解*

張人上1, 曲開社2

(1.山西財經(jīng)大學(xué),山西 太原 030006；2.山西大學(xué) 計算機與信息技術(shù)學(xué)院，山西 太原 030006)

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

能量空洞；雙簇頭網(wǎng)格聚類；漏斗效應(yīng)；數(shù)據(jù)收集；網(wǎng)絡(luò)效率

0 引 言

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

但是這些算法的優(yōu)異性都是在節(jié)點以均勻分布條件下取得的，在非均勻分布情況下，這些機制容易形成嚴(yán)重的能量分布不均，無法有效地規(guī)避能量空洞現(xiàn)象；且這些算法都是隨機擇取主簇頭，導(dǎo)致網(wǎng)絡(luò)效率降低[7～9]。

為了解決上述不足，本文設(shè)計了基于雙簇頭網(wǎng)格調(diào)度反饋結(jié)構(gòu)的WSNs非均布節(jié)點能量空洞緩解機制,并在仿真平臺上測試本文機制性能。

1 基于雙簇頭網(wǎng)格聚類算法設(shè)計

1.1 網(wǎng)格單元的形成

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

(1)

(2)

其中，X,Y分別代表網(wǎng)絡(luò)區(qū)域的長度與寬度。

若網(wǎng)絡(luò)區(qū)域內(nèi)所形成的網(wǎng)格單元數(shù)量為Z,則

Z=α×β.

(3)

由于每個網(wǎng)格單元的IDCi與網(wǎng)絡(luò)區(qū)域面積相關(guān),故網(wǎng)格單元的IDCi的坐標(biāo)如下

(4)

其中，x,y分別代表與網(wǎng)格單元的ID引擎i相關(guān)的坐標(biāo)值

x=i%a,

(5)

y=i/α.

(6)

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

(7)

通過上述程序，可計算出所有網(wǎng)格單元的ID；根據(jù)網(wǎng)格單元位置引擎i可得到每個網(wǎng)格單元的坐標(biāo)。

圖1 網(wǎng)格的形成及其引擎Fig 1 Formation of grid and its engine

1.2 網(wǎng)格單元中心點的數(shù)學(xué)模型的構(gòu)造

依據(jù)1.1小節(jié)得到的網(wǎng)格單元，計算每個單元的中心點坐標(biāo)，以便確定簇頭

(8)

(9)

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

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

1.3 網(wǎng)格單元中的WSNs節(jié)點鑒定

(10)

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

按照模型(10),即可確定每個網(wǎng)格單元內(nèi)的節(jié)點，并且將其歸入相應(yīng)的簇群內(nèi)。

1.4 簇頭的擇取

1)主簇頭的擇取

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

(11)

當(dāng)D最小時，此時的j被擇取為主簇頭；然后借助靜態(tài)Sink廣播網(wǎng)格ID、網(wǎng)格單元ID的中心點以及每個網(wǎng)格內(nèi)的節(jié)點ID。通過靜態(tài)Sink更新主簇頭信息，以便用于副簇頭的擇取。

2)副簇頭的擇取

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

(12)

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

3)相鄰簇頭的擇取

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

通過主簇頭—副簇頭—相鄰簇頭的數(shù)據(jù)調(diào)度傳輸結(jié)構(gòu)，有效分散了節(jié)點所承受的負(fù)載，降低了能量消耗速度，有效增加了網(wǎng)絡(luò)壽命,見圖2。

圖2 主簇頭—副簇頭—相鄰簇頭調(diào)度結(jié)構(gòu)Fig 2 Scheduling structure with main-vice-adjacent cluster head

1.5 數(shù)據(jù)收集階段

1.6 更新階段

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

(13)

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

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

假設(shè)整個網(wǎng)絡(luò)區(qū)域是由n個同心正方形構(gòu)成，每個同心正方形都是由尺寸為r×r的小網(wǎng)格單元構(gòu)成。靜態(tài)Sink位于網(wǎng)絡(luò)區(qū)域中心。由圖3，獲取第i個同心正方形面積為

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

(14)

其中，Ai代表第i個同心正方形面積，則整個網(wǎng)絡(luò)區(qū)域面積為

(15)

對于A1來說，若其網(wǎng)格單元的數(shù)量g,則整個網(wǎng)絡(luò)的網(wǎng)格單元總數(shù)N為

(16)

最內(nèi)側(cè)同心方形的每個簇頭節(jié)點的負(fù)載W計算如下

(17)

其中，W為簇頭負(fù)載；M為最內(nèi)側(cè)同心方形中簇頭節(jié)點數(shù)量；Cost為所有簇頭的簇內(nèi)通信成本。

若ρ為網(wǎng)絡(luò)區(qū)域內(nèi)的節(jié)點密度；每個節(jié)點的數(shù)據(jù)傳輸率為β,則簇內(nèi)通信成本c為

c=r2ρβ.

(18)

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

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

(19)

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

(20)

(21)

對于本文算法，總的通信跳數(shù)V應(yīng)該是簇間通信成本與簇內(nèi)通信成本的總和。

簇內(nèi)通信總成本Z

(22)

簇間通信總成本J

(23)

則V為

(24)

總的通信跳數(shù)V體現(xiàn)了節(jié)點在網(wǎng)絡(luò)中的能量消耗程度，故V越大，則能量消耗越大。對于非均勻節(jié)點分布，是不斷變化的；但總的通信跳數(shù)V是不變的。

圖3 從Sink中心將網(wǎng)絡(luò)劃分為同心方形Fig 3 Divide grid into concentric square from Sink centre

3 仿真結(jié)果與分析

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

圖4 仿真所用的拓?fù)浣Y(jié)構(gòu)Fig 4 Topology structure used in simulation

3.1 網(wǎng)絡(luò)效率對比分析

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

圖5 不用能量規(guī)避機制的網(wǎng)絡(luò)效率Fig 5 Network efficiency without using energy evasion mechanisms

3.2 網(wǎng)絡(luò)壽命對比分析

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

圖6 網(wǎng)絡(luò)持續(xù)時間仿真結(jié)果Fig 6 Simulation results of network duration time

為了直觀反映網(wǎng)絡(luò)壽命，本文測試不同機制的網(wǎng)絡(luò)壽命，見圖7。從圖中可知，隨著節(jié)點數(shù)量的增加，三種不同機制對應(yīng)的網(wǎng)絡(luò)壽命都在延長；但本文機制的網(wǎng)絡(luò)壽命最長。主要原因是本文構(gòu)造了雙簇頭網(wǎng)格調(diào)度反饋結(jié)構(gòu)，有效分散了節(jié)點的負(fù)載，通過相鄰簇頭的反饋，達到簇頭能量持續(xù)更新。

圖7 網(wǎng)絡(luò)壽命測試結(jié)果Fig 7 Tests results of network lifetime

3.3 基于Sink的數(shù)據(jù)收集率對比分析

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

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

3.4 平均能量耗散對比分析

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

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

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

4 結(jié) 論

本文設(shè)計了雙簇頭網(wǎng)格聚類算法，并將其用于WSNs非均布節(jié)點能量空洞緩解問題，且構(gòu)造了主簇頭—副簇頭—相鄰簇頭的數(shù)據(jù)調(diào)度傳輸結(jié)構(gòu)，由主簇頭調(diào)度簇間通信，由副簇頭調(diào)度簇內(nèi)通信，通過相鄰簇頭將能量與位置信息反饋給主簇頭，分散了節(jié)點所承擔(dān)的負(fù)載，完成數(shù)據(jù)更新與廣播。測試結(jié)果驗證了本文機制的優(yōu)越性。

圖10 不同能量空洞緩解機制的平均能量耗散測試結(jié)果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中基于時空特性的網(wǎng)絡(luò)能量空洞研究[J].計算機工程與應(yīng)用，2013，49(15)：105-112.

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

[6] 劉安豐,任 炬,徐 娟.異構(gòu)傳感器網(wǎng)絡(luò)能量空洞分析與避免研究[J].軟件學(xué)報，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

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

TP 393

A

1000—9787(2014)10—0133—04

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