孫 超，彭 力，朱雪芳

(1.物聯(lián)網(wǎng)應用技術(shù)教育部工程研究中心(江南大學)，江蘇 無錫 214122； 2.江蘇省聯(lián)合職業(yè)技術(shù)學院，江蘇 無錫 214028)

基于環(huán)的節(jié)點非均勻分布分簇算法

孫 超1*，彭 力1，朱雪芳2

(1.物聯(lián)網(wǎng)應用技術(shù)教育部工程研究中心(江南大學)，江蘇 無錫 214122； 2.江蘇省聯(lián)合職業(yè)技術(shù)學院，江蘇 無錫 214028)

(*通信作者電子郵箱841963798@qq.com)

針對無線傳感器網(wǎng)絡(WSN)中基于環(huán)的節(jié)點非均勻分布網(wǎng)絡模型下的能量空洞問題，提出了一種基于環(huán)的節(jié)點非均勻分布分簇算法(RCANND)。該算法在節(jié)點非均勻分布的網(wǎng)絡模型下，通過每環(huán)的能耗最小化，計算每一環(huán)的最優(yōu)簇首數(shù)；通過節(jié)點剩余能量、距基站距離以及與鄰居節(jié)點的平均距離計算簇首選擇度。在簇內(nèi)以簇首選擇度序列表進行簇首輪轉(zhuǎn)，降低分簇次數(shù)，提高網(wǎng)絡能量的利用效率。對提出的算法進行仿真對比實驗，仿真結(jié)果表明，相同半徑、不同分布模型下節(jié)點的平均能耗波動很?。幌嗤植寄Ｐ?、不同半徑下節(jié)點的平均能耗波動也不明顯。以網(wǎng)絡中50%節(jié)點存活作為網(wǎng)絡生命周期，在節(jié)點非均勻分布情況下，所提算法的網(wǎng)絡生命周期比混合能量高效分布式不等分簇算法(UHEED)和輪轉(zhuǎn)的混合能量高效分布式不等分簇算法(RUHEED)分別提高約18.1%和11.5%；在節(jié)點均勻分布模型下,所提算法的網(wǎng)絡生命周期比基于分環(huán)的能量高效無線傳感器網(wǎng)絡分簇路由(RECR)協(xié)議提高約6.4%。所提算法有效均衡了不同分布模型下的能耗，有效延長了網(wǎng)絡生命周期。

非均勻分布；分環(huán)；分簇；能量空洞；無線傳感器網(wǎng)絡

0 引言

無線傳感網(wǎng)絡(Wireless Sensor Network, WSN)是由大量的廉價微型傳感器節(jié)點以無線通信方式組成的一個多跳自組織網(wǎng)絡[1]。環(huán)境信息的采集和管理是無線傳感器網(wǎng)絡的主要功能，在工業(yè)、農(nóng)業(yè)、軍事、安全、醫(yī)療等很多領(lǐng)域都有廣泛應用。隨著無線傳感器網(wǎng)絡的應用越來越廣泛，WSN中能量的高效利用成為需要解決的關(guān)鍵問題。大量散布的無線傳感器節(jié)點一般由有限能量的電池供電，而節(jié)點電池更換困難，節(jié)點壽命有限。為了延長網(wǎng)絡生命周期，需要能量高效、能耗均衡的無線傳感器網(wǎng)絡路由協(xié)議，否則會產(chǎn)生能量空洞現(xiàn)象[2]。在WSN中傳感器節(jié)點采用多跳的方式將采集的數(shù)據(jù)發(fā)送給基站。一般情況下，傳感器節(jié)點在檢測區(qū)域內(nèi)的分布是隨機的，它們可以自組織網(wǎng)絡。當一個節(jié)點因為能量消耗殆盡或者其他原因?qū)е虏荒芄ぷ?，稱之為節(jié)點死亡，節(jié)點死亡就可能導致出現(xiàn)能量空洞現(xiàn)象。

能量空洞現(xiàn)象的避免是延長網(wǎng)絡生命周期的重要方面，而要避免部分節(jié)點過早死亡就要很好地均衡整個網(wǎng)絡的節(jié)點能耗[3]。在無線傳感器網(wǎng)絡中分簇路由算法相比平面路由算法具有更好的節(jié)能性，因此分簇的路由協(xié)議是研究重點。低功耗自適應集簇分層型(Low Energy Adaptive Clustering Hierarchy, LEACH)算法[4]是最早的分簇路由協(xié)議，之后很多文獻對分簇協(xié)議進行了大量研究，文獻[5]中提出的混合能量高效分布式不等分簇算法(Unequal Hybrid Energy Efficient Distributed algorithm, UHEED)在一種混合能量高效分布式自組織網(wǎng)分簇(Hybrid, Energy-Efficient, Distributed clustering approach for ad-hoc sensor network, HEED)方法[6]的基礎(chǔ)上采用基于非均勻分簇的無線傳感器網(wǎng)絡路由(Energy-Efficient Uneven Clustering, EEUC)協(xié)議[7]的競爭半徑計算方法，通過綜合考慮節(jié)點到基站的距離因素進行非均勻的分簇以解決HEED算法在能量空洞問題上的不足。文獻[8]中輪轉(zhuǎn)的混合能量高效分布式不等分簇算法(Rotated Unequal Hybrid Energy Efficient Distributed algorithm, RUHEED)對UHEED作了進一步的改進，通過成簇后簇首輪轉(zhuǎn)的方式減少簇首選舉與成簇過程中的能量開銷達到延長網(wǎng)絡生命周期的目的；但是算法在簇首輪轉(zhuǎn)階段僅考慮了節(jié)點剩余能量，直到出現(xiàn)節(jié)點死亡才進行重新分簇，不能很好地均衡能耗，這導致節(jié)點一旦出現(xiàn)死亡整個網(wǎng)絡的節(jié)點迅速死亡。

除了通過分簇路由協(xié)議提高網(wǎng)絡的生命周期，克服能量空洞現(xiàn)象，也有文獻提出采用同心環(huán)模型對能量空洞現(xiàn)象進行分析。文獻[9]提出了在節(jié)點均勻分布的WSN中采用同心環(huán)模型分析能量空洞現(xiàn)象，驗證了圓環(huán)寬度相等的情況下，路由上的能量消耗最小。文獻[10]為了均衡節(jié)點能量，在同心環(huán)模型上提出部署算法，使每一環(huán)上的節(jié)點數(shù)目相等，這造成了靠近基站環(huán)的節(jié)點密度過大，浪費了能量和成本。文獻[11]提出了基于同心環(huán)的分簇路由協(xié)議，對簇頭位置初始化、簇頭輪轉(zhuǎn)選擇、簇間路由協(xié)議進行了優(yōu)化，沒有對每環(huán)的簇首數(shù)進行優(yōu)化處理；文獻[12]提出了一種基于分環(huán)的能量高效無線傳感器網(wǎng)絡分簇路由(sub-Ring-based Energy-efficient Clustering Routing for WSN, RECR)算法，算法對各環(huán)的簇首數(shù)進行了優(yōu)化，采用了主次簇首輪換的方式降低節(jié)點能耗。以上基于分環(huán)的算法研究仍然在均勻分布的WSN網(wǎng)絡模型下，或者對網(wǎng)絡節(jié)點采用部署策略，只能應用到小部分的實際環(huán)境。

現(xiàn)有研究主要集中在網(wǎng)絡節(jié)點均勻分布情況或者通過采用節(jié)點部署策略來解決網(wǎng)絡能耗不均產(chǎn)生的能量空洞問題。本文針對同構(gòu)網(wǎng)絡中，節(jié)點非均勻分布前提下的能量空洞問題，提出了非均勻分布的同心環(huán)傳感器網(wǎng)絡模型分簇路由算法——基于環(huán)的節(jié)點非均勻分布分簇算法(Ring-based Clustering Algorithm for Nodes Non-uniform Deployment, RCANND)。該算法在同心環(huán)網(wǎng)絡模型基礎(chǔ)上，針對節(jié)點非均勻分布的傳感器網(wǎng)絡研究能量均衡的分簇路由協(xié)議。在網(wǎng)絡初始化階段根據(jù)網(wǎng)絡總能耗最低的原則以及每一環(huán)的節(jié)點數(shù)目對簇首數(shù)優(yōu)化，得到最優(yōu)簇首數(shù)后再計算每一環(huán)各自的簇首競爭半徑。在簇首選舉階段，通過競爭獲得最佳簇首，同時對簇內(nèi)的各個成員節(jié)點計算簇首選擇度，通過簇首輪轉(zhuǎn)來均衡各節(jié)點能耗，減少了每輪進行簇首選舉的網(wǎng)絡能耗。最后通過簇間多跳路由實現(xiàn)數(shù)據(jù)傳輸?shù)交?，完成通信?/p>

1 無線傳感器網(wǎng)絡采用的模型

1.1 網(wǎng)絡模型

在本文，對無線傳感器網(wǎng)絡模型作如下假設(shè)：1)節(jié)點同構(gòu)，基站外的所有節(jié)點具有相同的特性，如初始能量、通信半徑等。2)監(jiān)測區(qū)域內(nèi)的同構(gòu)傳感器節(jié)點具有唯一ID，規(guī)定以j為下標的參數(shù)均表示第j個傳感器節(jié)點的參數(shù)。3)所有節(jié)點和基站部署之后都是靜止的，都能根據(jù)距離調(diào)節(jié)它們的發(fā)射功率。4)同構(gòu)傳感器網(wǎng)絡節(jié)點隨機分布在半徑為R的區(qū)域內(nèi)，圓形區(qū)域內(nèi)分為M個寬度相等的環(huán)形帶，并且每個環(huán)形帶內(nèi)的傳感器節(jié)點的密度是隨機的；對環(huán)形帶進行編號，規(guī)定用i表示第i(i=1,2,…，M)個環(huán)形帶，文中下標為i的均表示第i個環(huán)形帶中的參數(shù)。5)這些環(huán)形帶之間節(jié)點的分布是非均勻的，每個環(huán)形帶中都有著不同的節(jié)點密度參數(shù)ρi，ρi的值可以隨不同的部署模型而改變。在一個環(huán)形帶中，節(jié)點的個數(shù)Ni=ρi×Si，Si為該環(huán)形面積。網(wǎng)絡節(jié)點分布模型如圖1所示。

圖1 網(wǎng)絡節(jié)點分布模型

1.2 能量消耗模型

本文采用與LEACH算法相同的無線電模型。發(fā)送lb的信息量到距離d處需要消耗的能量如下：

(1)

式中：εfs表示自由空間模型的能耗系數(shù)；εamp表示多路徑放大電路的能耗系數(shù)；d0是節(jié)點可以直接與基站通信的距離。為了接收lb的信息量，消耗的能量為：

ERx(l)=l×Eelec

(2)

此外，對網(wǎng)絡中的其他能量消耗作如下假設(shè)：1)節(jié)點感知環(huán)境信息的能量消耗為Es；2)簇首消耗EDA用于數(shù)據(jù)融合。

2 RCANND設(shè)計

本文提出的WSN分簇路由算法以輪為周期運行，每一輪由優(yōu)化分簇和數(shù)據(jù)傳輸兩部分組成。優(yōu)化分簇部分由三個階段組成：第一階段，初始化網(wǎng)絡，對網(wǎng)絡中每環(huán)簇首數(shù)進行優(yōu)化；第二階段，由簇首選舉和簇建立組成的分簇過程階段；第三階段，每完成一次數(shù)據(jù)采集過程進行簇首輪轉(zhuǎn)以均衡節(jié)點能耗，輪轉(zhuǎn)一定次數(shù)后重新循環(huán)第二階段到第三階段。數(shù)據(jù)傳輸部分，通過簇間多跳的路由方式將數(shù)據(jù)傳輸?shù)交尽?/p>

2.1 簇首數(shù)優(yōu)化

在傳感器網(wǎng)絡區(qū)域內(nèi)，獲得最優(yōu)簇首數(shù)是有效均衡網(wǎng)絡能耗、延長網(wǎng)絡生命周期的重要因素。在基于環(huán)的分簇路由算法中，都有對簇首數(shù)優(yōu)化，但是這些算法主要是在均勻分布的網(wǎng)絡模型基礎(chǔ)之上。現(xiàn)在用k來表示期望的最優(yōu)簇首數(shù)目，根據(jù)文獻[13]中每簇平均面積的計算方法以及本文中的網(wǎng)絡模型，網(wǎng)絡監(jiān)測區(qū)域內(nèi)每簇的平均面積為πR2/k，那么每簇節(jié)點平均密度ρ=1/(πR2/k)，那么可以得到節(jié)點到簇首距離的平方期望是：

(3)

根據(jù)本文的能量消耗模型，當基站距離節(jié)點很近時，通信損耗認為是自由空間損耗。當傳感器節(jié)點距離基站較遠時認為是多路徑損耗。現(xiàn)在總的能量損耗由文獻[14]可得：

(4)

(5)

簇首到基站的平均距離估算公式為：

(6)

式中：Ri表示每一環(huán)到基站的最大半徑。由此，kopt可以求得：

(7)

現(xiàn)在讓每個環(huán)里的簇的數(shù)目是ki,ki-1,…,k1，那么：

(8)

式中：

(9)

2.2 分簇過程

Pj=c1Er/Einit+c2di/dj-toBS+c3/dj-avg

(10)

(11)

式中：Er為節(jié)點剩余能量；Einit為節(jié)點初始能量；di為該圓環(huán)到基站的平均期望距離；dj-toBS為節(jié)點到基站的距離；dj-avg為各節(jié)點與競爭半徑內(nèi)各節(jié)點的平均距離；c1、c2、c3為權(quán)重系數(shù)且c1+c2+c3=1。

選擇度Pj考慮了節(jié)點的剩余能量、到基站的距離因素，以及與鄰居節(jié)點間的距離。如果在競爭半徑內(nèi)，某個節(jié)點簇首選擇度Pj最大，那么該節(jié)點被選為簇首。

2.3 簇頭輪轉(zhuǎn)策略

成簇過程完成后，簇首已經(jīng)獲得了各個簇成員的Pj，簇首按照Pj大小排序形成一個簇首選擇序列表。簇首選擇序列表作為下一輪的簇首選擇依據(jù)。每一輪數(shù)據(jù)傳輸結(jié)束后，根據(jù)簇首選擇序列中排在下一位次的節(jié)點成為簇首并在簇內(nèi)廣播消息，其他節(jié)點接收到消息后，下一輪將數(shù)據(jù)傳送給新簇首。每經(jīng)過n輪，重新進行分簇過程，產(chǎn)生新的簇首選擇序列，以均衡網(wǎng)絡能耗；這里n取各環(huán)中的最小值，n由式(13)給出。雖然有些節(jié)點未在本次輪轉(zhuǎn)擔當簇首，但是在下次競爭簇首時具備更大優(yōu)勢，依然能夠保證整個網(wǎng)絡的能耗均衡。

劉雁衡遲遲不動，被一個警員推了個趔趄。寒流果然來了，冷風吹到臉上，徹骨生寒。劉雁衡、吳邦雄，還有兩個男生，被四個警員上上下下搜查一遍，沒搜出什么。那胖大警官獨自留在室內(nèi)，目光猶如鼻涕蟲，潮濕黏糊，在四名女學生身上刷來刷去。最后他挑出身材高挑的黃鶯：“你，過來。”黃鶯的臉一下子白了，站著不動。警官探出粗大的右手，目標明確地按到她腰上。

ni=Ni/ki

(12)

n=min{n1,n2，…，ni}

(13)

數(shù)據(jù)傳輸過程，簇首對簇內(nèi)數(shù)據(jù)進行融合后，將數(shù)據(jù)傳輸?shù)交?。當簇首到基站的距離小于等于直接傳輸距離d0時，簇首直接與基站進行通信;當距離大于d0時，采用多跳的路由方式將數(shù)據(jù)傳送到基站。仿真中的具體路由算法采用文獻[11]中的簇間多跳路由算法。

3 算法仿真與分析

為了驗證本文算法在能耗均衡以及延長網(wǎng)絡生命周期方面的性能，通過Matlab仿真平臺，對算法進行仿真和對比。仿真中使用的網(wǎng)絡節(jié)點分布模型如1.1節(jié)所述，傳感器網(wǎng)絡部署在一個圓形監(jiān)測區(qū)域內(nèi)，基站位于監(jiān)測區(qū)域的中心位置。本文主要的仿真參數(shù)均采自LEACH算法[4]，主要的仿真參數(shù)如表1所示。

表1 主要仿真參數(shù)

3.1 能耗均衡性

將監(jiān)測區(qū)域分成寬度相等的3環(huán)，針對不同的節(jié)點分布情況，作網(wǎng)絡能耗變化的仿真。當節(jié)點分布模型不同時，簇首產(chǎn)生的數(shù)目必然不同，為了驗證算法在節(jié)點分布密度變化時依然能有良好的能耗均衡性能，現(xiàn)在選取四種典型節(jié)點分布模型進行仿真對比。這四種分布模型分別是case1(ρ1>ρ2>ρ3)、case2(ρ2>ρ3=ρ1)、case3(ρ1<ρ2<ρ3)以及case4(ρ1=ρ2=ρ3)，本次仿真的具體取值如表2，仿真結(jié)果如圖2所示。

表2 典型節(jié)點分布模型

圖2 不同半徑和分布情況下節(jié)點平均能耗

從圖2中可以看出，相同半徑下，在網(wǎng)絡節(jié)點分布密度不同的情況下，網(wǎng)絡的節(jié)點平均能耗的波動并不明顯；算法最優(yōu)簇首數(shù)的動態(tài)選擇發(fā)揮了均衡整個網(wǎng)絡能耗的作用，使得不同分布模型下的網(wǎng)絡能耗未出現(xiàn)大幅變化；當半徑不同時，由于半徑越大，平均傳輸距離越大，較大半徑平均能耗會略有提升。對比各個半徑下、相同分布密度的網(wǎng)絡節(jié)點平均能耗，依然波動不明顯。從圖2中還可以看出：不同半徑下，均在第三種節(jié)點分布模型(case3)下的平均能耗最高，第三種分布模型的各環(huán)節(jié)點密度系數(shù)的關(guān)系是ρ1<ρ2<ρ3，可見最外環(huán)的節(jié)點數(shù)目最多，而最內(nèi)環(huán)的節(jié)點數(shù)目最少，這導致節(jié)點與基站的平均通信距離最大，能耗自然會略有提高。

3.2 分環(huán)數(shù)與網(wǎng)絡生命周期

討論網(wǎng)絡半徑變化時，網(wǎng)絡的最佳分環(huán)數(shù)。針對本文的網(wǎng)絡模型，在網(wǎng)絡節(jié)點分布情況不變以及半徑不變的情況下，改變同心環(huán)的數(shù)量。在100m、180m、320m的半徑下進行仿真，討論不同的分環(huán)數(shù)與網(wǎng)絡生命周期的關(guān)系，仿真結(jié)果如圖3所示。從圖3中可以看出，整體上，分環(huán)數(shù)過多會導致網(wǎng)絡生命周期減少，但是同半徑下使網(wǎng)絡生命周期最長的最優(yōu)分環(huán)數(shù)總是存在的。由于算法對于簇首數(shù)的優(yōu)化，分環(huán)數(shù)開始增加時，網(wǎng)絡生命周期的減少并不明顯。隨著同心環(huán)數(shù)量的增加，同心環(huán)的面積在減小，必然會產(chǎn)生更多的簇，節(jié)點的能量消耗增加，網(wǎng)絡生命周期減少。

從3.1節(jié)中的仿真結(jié)果可知，本文算法的最優(yōu)簇首數(shù)的動態(tài)選擇，可以有效地均衡不同密度下的網(wǎng)絡能耗以避免能量空洞、延長網(wǎng)絡生命周期；但是當分環(huán)數(shù)變多導致的簇首數(shù)增加，路由的轉(zhuǎn)發(fā)能量增加，仍然使網(wǎng)絡總能耗增加，減少了網(wǎng)絡生命周期?？梢?，本文算法仍然需要合理選擇分環(huán)數(shù)量以有效延長網(wǎng)絡生命周期。

圖3 不同半徑下分環(huán)數(shù)與網(wǎng)絡生命周期的關(guān)系

3.3 網(wǎng)絡生命周期對比

為了驗證算法在延長網(wǎng)絡生命周期方面的有效性，在非均勻分布的模型中，將本文算法與算法UHEED和RUHEED進行了對比；在均勻分布情況下，將本文算法與分環(huán)算法RECR進行對比，仿真結(jié)果如圖4所示。

從圖4(a)可以看出，本文算法解決了RUHEED在簇首輪轉(zhuǎn)上導致的能耗不均衡、節(jié)點迅速死亡的問題；由于本文算法的不定周期分簇，部分輪轉(zhuǎn)過程會產(chǎn)生較大能耗，死亡節(jié)點在后期會產(chǎn)生死亡速度增加現(xiàn)象。以50%節(jié)點存活作為網(wǎng)絡的生命周期，在非均勻分布情況下，本文算法的網(wǎng)絡生命周期比UHEED和RUHEED分別提高約18.1%和11.5%。由圖4(b)可以看出，RECR算法采用主次簇首輪換的方式減少分簇的能耗，本文算法采用的簇首輪換機制比RECR減少了更多的分簇能耗，因而網(wǎng)絡生命周期上比RECR算法提高了約6.4%，可見在均勻分布的情況下，本文算法在網(wǎng)絡生命周期上也略有提高。由此可得，所提算法相比傳統(tǒng)的分環(huán)算法，主要優(yōu)勢在于能適應不同的節(jié)點分布情況，能夠適應更多的實際應用環(huán)境。

圖4 不同算法生命周期對比

4 結(jié)語

本文在已有的分環(huán)分簇算法基礎(chǔ)上提出了一種節(jié)點非均勻分布情況下的算法。該算法主要解決在節(jié)點非均勻分布的網(wǎng)絡模型下的能耗均衡問題，避免產(chǎn)生能量空洞現(xiàn)象，延長了網(wǎng)絡的生命周期。在網(wǎng)絡初始化階段，根據(jù)每一環(huán)的節(jié)點數(shù)目進行簇首數(shù)優(yōu)化；在簇首選舉階段，通過競爭獲得最佳簇首，同時對簇內(nèi)的各個成員節(jié)點計算簇首選擇度Pj，通過簇首輪轉(zhuǎn)來均衡各節(jié)點能耗，同時避免了每輪進行簇首選舉，降低了網(wǎng)絡能耗。仿真結(jié)果表明，本文算法在不同分布模型下有效地均衡了網(wǎng)絡能耗，延長了網(wǎng)絡生命周期。今后可考慮針對分環(huán)的大規(guī)模網(wǎng)絡中多跳的簇間路由算法進行進一步的研究。

)

[1]RAWATP,SINGHKD,CHAOUCHIH,etal.Wirelesssensornetworks:asurveyonrecentdevelopmentsandpotentialsynergies[J].TheJournalofSupercomputing, 2014, 68(1): 1-48.

[2]LIUXX.Asurveyonclusteringroutingprotocolsinwirelesssensornetworks[J].Sensors, 2012, 12(8): 11113-11153.

[3]PANTAZISNA,NIKOLIDAKISSA,VERGADOSDD.Energy-efficientroutingprotocolsinwirelesssensornetworks:asurvey[J].IEEECommunicationsSurveys&Tutorials, 2013, 15(2): 551-591.

[4]HEINZELMANWR,CHANDRAKASANA,BALAKRISHNANETH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C]//HICSS’00:Proceedingsofthe33rdHawaiiInternationalConferenceonSystemSciences.Washington,DC:IEEEComputerSociety, 2000: 8020.

[5]EVERE,LUCHMUNR,MOSTARDAL,etal.UHEED:anunequalclusteringalgorithmforwirelesssensornetworks[EB/OL]. [2016- 11- 10].https://core.ac.uk/download/pdf/17301738.pdf.

[6]YOUNISO,FAHMYS.HEED:ahybrid,energy-efficient,distributedclusteringapproachforadhocsensornetworks[J].IEEETransactionsonMobileComputing, 2004, 3(4): 366-379.

[7] 李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議[J].計算機學報,2007,30(1):27-36.(LICF,CHENGH,YEM,etal.Anunevencluster-basedroutingprotocolforwirelesssensornetworks[J].ChineseJournalofComputers, 2007, 30(1): 27-36.)

[8]AIERKENN,GAGLIARDIR,MOSTARDAL,etal.RUHEED—rotatedunequalclusteringalgorithmforwirelesssensornetworks[C]//Proceedingsofthe2015IEEE29thInternationalConferenceonAdvancedInformationNetworkingandApplicationsWorkshops.Piscataway,NJ:IEEE, 2015: 170-174.

[9]OLARIUS,STOJMENOVICI.Designguidelinesformaximizinglifetimeandavoidingenergyholesinsensornetworkswithuniformdistributionanduniformreporting[C]//INFOCOM2006:Proceedingsofthe2006 25thIEEEInternationalConferenceonComputerCommunications.Piscataway,NJ:IEEE, 2006: 1-12.

[10] 任麗婕,郭忠文,唐瑞春.無線傳感器網(wǎng)絡中基于能量平衡的部署算法[J].中國海洋大學學報(自然科學版),2008,38(5):841-844.(RENLJ,GUOZW,TANGRC.Anodeplacementstrategybasedonenergy-balanceforwirelesssensornetworks[J].PeriodicalofOceanUniversityofChina, 2008, 38(5): 841-844.)

[11] 劉震,郭航.基于同心環(huán)分簇網(wǎng)絡模型的WSN能量空洞避免方法研究[J].計算機科學,2013,40(12):147-151.(LIUZ,GUOH.Studyonconcentric-ringandcluster-basedenergyholeavoidingmethodinwirelesssensornetworks[J].ComputerScience, 2013, 40(12): 147-151.)

[12] 吳玉成,李偉琪, 胡真,等.一種基于分環(huán)的能量高效無線傳感器網(wǎng)絡分簇路由協(xié)議[J].傳感器與微系統(tǒng),2015,34(5):8-11.(WUYC,LIWQ,HUZ,etal.Asub-ring-basedclusteringroutingprotocolforenergy-efficientWSNs[J].TransducerandMicrosystemTechnologies, 2015, 34(5): 8-11.)

[13]HEINZELMANWB,CHANDRAKASANAP,BALAKRISHNANH.Anapplication-specificprotocolarchitectureforwirelessmicrosensornetworks[J].IEEETransactionsonWirelessCommunications, 2002, 1(4): 660-670.

[14]TRIPATHIRK,SINGHYN,VERMANK.Two-tieredwirelesssensornetworks-basestationoptimalpositioningcasestudy[J].IETWirelessSensorSystems, 2012, 2(4): 351-360.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61502204),theUniversityNaturalScienceResearchSurfaceProjectofJiangsu(16KJB510044).

SUN Chao, born in 1991, M. S. candidate. His research interests include wireless sensor network.

PENG Li, born in 1967, Ph. D., professor. His research interests include vision sensor network, artificial intelligence.

ZHU Xuefang, born in 1967, M. S., associate professor. Her research interests include communication and control.

Ring-based clustering algorithm for nodes non-uniform deployment

SUN Chao1*, PENG Li1, ZHU Xuefang2

(1.EngineeringResearchCenterofInternetofThingsApplicationTechnologyoftheMinistryofEducation(JiangnanUniversity),WuxiJiangsu214122,China; 2.JiangsuUnionTechnicalInstitute,WuxiJiangsu214028,China)

Aiming at the problem of energy hole in the nodes non-uniform deployment network model based on the ring in Wireless Sensor Network (WSN), a Ring-based Clustering Algorithm for Nodes Non-uniform Deployment (RCANND) was proposed. The number of the optimal cluster heads in each ring was calculated by minimizing the energy consumption of each ring in the nodes non-uniform deployment network model. The cluster head selectivity was calculated by using the residual energy of the nodes, the distance from the base station, and the average distance from the neighbor nodes. The cluster head rotation was carried out with the cluster head selection sequence in cluster, and the number of cluster formation phases was reduced to improve the efficiency of network energy utilization. The proposed algorithm was tested in the simulation experiments, the experimental results show that, the average energy consumption fluctuation of nodes under the same radius but different nodes deployment models is very small. The average energy consumption fluctuation of nodes under the same nodes deployment model but different radiuses is not obvious. The network lifetime was defined as the survivability of 50% network nodes. In the case of non-uniform deployment of nodes, the network lifetime of the proposed algorithm is higher than that of Unequal Hybrid Energy Efficient Distributed algorithm (UHEED) by about 18.1% while it is also higher than that of Rotated Unequal Hybrid Energy Efficient Distributed algorithm (RUHEED) by about 11.5%. In the case of uniform deployment of nodes, the network lifetime of the proposed algorithm is higher than that of sub-Ring-based Energy-efficient Clustering Routing for WSN (RECR) by about 6.4%. The proposed algorithm can effectively balance the energy consumption under different nodes deployment models and prolong the network lifetime.

non-uniform deployment; sub-ring; clustering; energy hole; Wireless Sensor Network (WSN)

2016- 12- 12;

2017- 03- 01。

國家自然科學基金資助項目(61502204);江蘇省高校自然科學研究面上項目(16KJB510044)。

孫超(1991—)，男，山東青島人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡； 彭力(1967—),男,河北唐山人, 教授, 博士, 主要研究方向:視覺傳感器網(wǎng)絡、人工智能； 朱雪芳(1967—)，女，江蘇常熟人，副教授，碩士，主要研究方向：通信與控制。

1001- 9081(2017)06- 1527- 05

10.11772/j.issn.1001- 9081.2017.06.1527

TP

A