基于距離分簇算法的WSN組網(wǎng)方法

華江鋒,呂艷輝，付 垚，劉潔琳

(沈陽理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110159)

基于距離分簇算法的WSN組網(wǎng)方法

華江鋒,呂艷輝，付 垚，劉潔琳

(沈陽理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110159)

針對無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點能量受限不能及時供給的問題，提出一種基于距離分簇算法的無線傳感器網(wǎng)絡(luò)組網(wǎng)方法，旨在均衡節(jié)點負載，提高通信效率。算法由Sink節(jié)點發(fā)起，主要通過設(shè)置Sink節(jié)點的不同通信距離來劃分傳感器網(wǎng)絡(luò)，根據(jù)網(wǎng)絡(luò)層數(shù)設(shè)定每個簇的最大節(jié)點數(shù)目，引入簇首輪換機制保證網(wǎng)絡(luò)存活周期，根據(jù)多跳通信路由函數(shù)選取簇間通信最佳路由。仿真結(jié)果驗證了算法能夠有效降低網(wǎng)絡(luò)能耗和延長網(wǎng)絡(luò)生存周期。

無線傳感器網(wǎng)絡(luò)；分簇組網(wǎng)；均衡負載

無線傳感器網(wǎng)絡(luò)(WSN)是一種由大量隨機分布的低成本、低功耗的微小傳感器節(jié)點組成的分布式網(wǎng)絡(luò)，它通常采用節(jié)點多跳路由和自組織的方式構(gòu)成網(wǎng)絡(luò)系統(tǒng)，被廣泛應(yīng)用于軍事偵察、環(huán)境監(jiān)測、醫(yī)療監(jiān)護、商業(yè)開發(fā)等領(lǐng)域[1]。

目前，無線傳感器網(wǎng)絡(luò)的分簇算法研究主要集中在均衡節(jié)點能量負載和延長網(wǎng)絡(luò)生存周期兩個方面。針對這些問題，國內(nèi)外展開了大量的理論與實踐研究。LEACH(Low-Energy Adaptive Cluster Hierarchy)協(xié)議[2]采用周期循環(huán)隨機選舉的方式產(chǎn)生簇首節(jié)點，通過簇首輪換機制來均衡WSN中節(jié)點能耗，簇首單跳通信將數(shù)據(jù)傳送給Sink節(jié)點。該協(xié)議避免了節(jié)點能量過分消耗，但隨機產(chǎn)生的簇首個數(shù)和位置無法確定；另外，簇首的頻繁選舉會造成較大的數(shù)據(jù)傳輸量，單跳通信需要節(jié)點支持射頻功率動態(tài)調(diào)整。PEGASIS(Power-Efficient Gathering in Sensor Information System)協(xié)議[3]中普通節(jié)點采用簇間多跳通信的方式，將數(shù)據(jù)傳送給最高層級的簇首，然后由該簇首將數(shù)據(jù)單跳傳送給Sink節(jié)點。該協(xié)議避免了因簇首頻繁選舉造成的通信開銷，但由于要傳遞大量的數(shù)據(jù)信息，距離Sink節(jié)點較近的簇首負載過重，會導(dǎo)致網(wǎng)絡(luò)提前死亡，同樣也會影響整個網(wǎng)絡(luò)的數(shù)據(jù)監(jiān)測和生存周期。蘇金樹等人提出負載均衡感知的容錯分簇算法，采用自適應(yīng)離散粒子群優(yōu)化的簇首選舉機制確保簇首負載均衡與能耗最低，但沒有解決簇首因距離不同造成的負載不均衡問題[4]。周東鑫等人提出基于分層多跳的WSN分簇路由算法。與其他算法相比，它具有更好的數(shù)據(jù)傳輸效率與網(wǎng)絡(luò)生存周期，但該算法的分層閾值選取偏大，且沒有對簇首的分布進行合理布局[5]。Busse等人分析了在不同能量消耗模型下的網(wǎng)絡(luò)生命周期最大化問題，給出了傳輸功率特定時的線性算法，但沒有考慮到大部分場景下該算法是一個NP完全問題[6]。

從上述分析可以看出，現(xiàn)有研究在設(shè)計組網(wǎng)時并未充分考慮節(jié)點能耗均衡與網(wǎng)絡(luò)生存周期的問題。因此，本文提出的DCA(Distance-Clustering Algorithm)算法在節(jié)點負載相對均衡、最優(yōu)網(wǎng)絡(luò)能耗和提高數(shù)據(jù)傳輸效率的基礎(chǔ)上建立了無線傳感器網(wǎng)絡(luò)的分簇組網(wǎng)方案。

1 組網(wǎng)模型

1.1 能耗模型

無線通信能耗是基于Heinzelman[7]的研究成果。首先確定模型的距離閾值d0，如果發(fā)送節(jié)點到目標(biāo)節(jié)點的距離d

(1)

節(jié)點j接收節(jié)點i發(fā)送的kbit數(shù)據(jù)能耗為

ERX(k,d)=Eelec·k

(2)

式中：Eeleck表示無線收發(fā)電路的能耗；Eampk,d表示放大器消耗的能量；εamp和εfs分別是信號放大器的多徑放大倍數(shù)和自由放大倍數(shù)。

1.2 網(wǎng)絡(luò)設(shè)定

本文假設(shè)無線傳感器網(wǎng)絡(luò)具有如下性質(zhì)：

(1) 網(wǎng)絡(luò)監(jiān)測區(qū)域范圍已知，傳感器節(jié)點隨機部署；

(2) 網(wǎng)絡(luò)觀測區(qū)域外圍只有一個Sink節(jié)點，位置固定已知；

(3) 所有節(jié)點具有相同的初始能量，部署好后不可移動；

(4) 節(jié)點采用數(shù)據(jù)融合技術(shù)減少數(shù)據(jù)傳輸流量，融合度為100%；

(5) 節(jié)點通信模塊能耗遠遠大于其他模塊，故只考慮數(shù)據(jù)通信能耗。

2 算法概述

2.1 相關(guān)定義

本文所涉及的相關(guān)定義描述如下：

(1) 網(wǎng)絡(luò)層級NLvl：網(wǎng)絡(luò)中各節(jié)點通過與Sink節(jié)點的距離值劃分到不同的層級，層級值記為i.NLvl=k，其中1≤k≤K，K為最大層級值，1≤i≤N，i為網(wǎng)絡(luò)中某節(jié)點，N為網(wǎng)絡(luò)中節(jié)點總數(shù)，NLvl值根據(jù)Sink節(jié)點圓心不同輻射半徑計算得到；

(2) 節(jié)點標(biāo)識NodeId：用于標(biāo)識網(wǎng)絡(luò)中的傳感器節(jié)點；

(3) 節(jié)點剩余能量值NodeEn：用于記錄傳感器節(jié)點的剩余能量值；

(4) 簇首標(biāo)志IsCH：用于記錄節(jié)點是否為簇首，若該值為0，則為普通節(jié)點，該值若為1，則為簇首；

(5) 節(jié)點距離標(biāo)識SinkDis：用于記錄傳感器節(jié)點與Sink節(jié)點的距離值；

(6) 簇首能量閾值ENgate：用以判定節(jié)點是否可以成為簇首；

(7) 簇首節(jié)點的成員信息MemberInfo：用于存儲其成員節(jié)點的具體信息，包括成員節(jié)點的節(jié)點距離標(biāo)識、網(wǎng)絡(luò)層級標(biāo)識和剩余能量值；

(8) 簇成員數(shù)最大值CMemberNumi：用于設(shè)置每層級網(wǎng)絡(luò)簇的成員數(shù)目；

(9) 簇首競爭消息ClusterHead：用于標(biāo)明節(jié)點競選簇首，包含該節(jié)點的網(wǎng)絡(luò)層級、節(jié)點標(biāo)識、節(jié)點剩余能量值和節(jié)點距離標(biāo)識等信息。

具體算法流程如圖1所示。

圖1 DCA算法流程

2.2 基于距離分簇

2.2.1 網(wǎng)絡(luò)分層

系統(tǒng)初始階段，Sink節(jié)點向網(wǎng)絡(luò)發(fā)送廣播消息。網(wǎng)絡(luò)中的傳感器節(jié)點根據(jù)接收Sink節(jié)點的RSSI值(接收信號強度指示)計算出自身到Sink節(jié)點之間的距離，然后系統(tǒng)按照距離值將節(jié)點進行網(wǎng)絡(luò)層級分類，具體工作如下：

(1) Sink節(jié)點向網(wǎng)絡(luò)廣播初始化DLHello消息；

(2) 網(wǎng)絡(luò)中的傳感器節(jié)點i收到DLHello消息后，根據(jù)RSSI值求出自身與Sink節(jié)點之間的距離i.SinkDis；

(3) 節(jié)點i根據(jù)預(yù)先設(shè)定的K值和各層距離閾值Li，依定義與i.SinkDis進行計算比較，求出節(jié)點的網(wǎng)絡(luò)層級值i.NLvl。

分層后的傳感器網(wǎng)絡(luò)如圖2所示。

圖2 傳感器網(wǎng)絡(luò)分層

2.2.2 網(wǎng)絡(luò)分簇

對傳感器網(wǎng)絡(luò)進行分層后，進入分簇階段。具體過程如下：

(1)所有節(jié)點在競爭簇首之前，將自身的簇首標(biāo)志值設(shè)為0，即i.IsCH=0；

(2)判斷節(jié)點剩余能量是否大于閾值ENgate，即if(i.NodeEn>ENgate)，只有大于閾值的節(jié)點才可以競選簇首；

(3)滿足競選簇首條件的節(jié)點設(shè)置簇首競爭周期t，廣播簇首競爭消息，即i.ClusterHead(i.NLvl,i.NodeEn,i.NodeId,i.SinkDis)；

(4)若節(jié)點在簇首周期內(nèi)收到其他節(jié)點的簇首競爭消息，比較它們的網(wǎng)絡(luò)層級數(shù)，即if(i.NLvl!=j.NLvl)，若層級值不同，丟棄該消息，若層級值相同，引入簇首評價函數(shù)競選：

(3)

式中：α、β為比例因子；P是簇首在本輪所有節(jié)點中所占的百分比；r是選舉輪數(shù)；rmod(1/P)為這一輪循環(huán)中當(dāng)選為簇首的節(jié)點個數(shù)；D是節(jié)點與Sink節(jié)點的距離值；E是節(jié)點本輪剩余能量，具體計算公式為

E=Erest(r)-ETX(k,d)-ERX(k,d)

(4)

Erest(r)代表第r輪該節(jié)點的初始能量，ETX(k,d)和ERX(k,d)分別與式(1)、式(2)中參數(shù)一致；

(5)若節(jié)點在競爭周期內(nèi)沒有收到競選值高于自身的消息，將IsCH值改為1，設(shè)置建簇周期t，然后在本網(wǎng)絡(luò)層級內(nèi)廣播建簇消息，聲明自己為簇首；

(6)普通節(jié)點收到建簇消息后，向信號最強的簇首發(fā)送申請加入信息，申請加入該簇，如果此時該簇節(jié)點數(shù)目沒有超過設(shè)置的簇成員數(shù)最大值CMemberNumi，則簇首同意該節(jié)點加入，如果該簇已滿則向其他簇首發(fā)送信息申請加入；

(7)若建簇周期結(jié)束或簇已滿員，則建簇完畢。

通過上述工作，傳感器網(wǎng)絡(luò)被劃分成多個層級。在每一層級中，選舉剩余能量值高且距離Sink近的節(jié)點為簇首，然后以它為核心構(gòu)建新簇，分簇后的網(wǎng)絡(luò)拓撲如圖3所示。

圖3 網(wǎng)絡(luò)分簇拓撲

2.3 節(jié)點通信

2.3.1 簇內(nèi)通信

網(wǎng)絡(luò)分簇后，需要進行簇內(nèi)通信，通過以下步驟實現(xiàn)：

(1)簇首生成一個TDMA時隙表，向簇內(nèi)成員節(jié)點廣播發(fā)送時隙信息；

(2)簇內(nèi)成員節(jié)點接收信息，在相應(yīng)的時隙進行數(shù)據(jù)傳輸，其他時間則進入休眠狀態(tài)，以便減少能量消耗和數(shù)據(jù)沖突；

(3)簇首接收并融合所有成員節(jié)點的數(shù)據(jù)信息后轉(zhuǎn)發(fā)給下一跳簇首。

2.3.2 簇間通信

簇首與Sink節(jié)點之間的數(shù)據(jù)傳輸采用多跳通信的方式，具體步驟如下：

(1) 基于距離分簇完成后，從網(wǎng)絡(luò)層級值最大的簇首開始進行數(shù)據(jù)傳輸；

(2) 根據(jù)多跳通信路由函數(shù)P依次計算上一層網(wǎng)絡(luò)區(qū)域內(nèi)簇首的函數(shù)值p，函數(shù)公式為：

(5)

式中：φ、θ是權(quán)重系數(shù)；i.SinkDis是簇首到Sink節(jié)點的距離；Eelec和E分別與式(1)、式(4)中參數(shù)一致；

(3)選取p值最大的簇首作為下一跳轉(zhuǎn)發(fā)節(jié)點，若p值相等，則選擇距離本次轉(zhuǎn)發(fā)節(jié)點較近的簇首作為下一跳轉(zhuǎn)發(fā)節(jié)點，然后轉(zhuǎn)向(2)；

(4)當(dāng)網(wǎng)絡(luò)層級NLvl=1時，下一跳直接轉(zhuǎn)發(fā)給Sink節(jié)點。

簇間通信的過程如圖4所示。

圖4 簇間通信

2.4 簇首輪換

在網(wǎng)絡(luò)通信中，當(dāng)簇首節(jié)點的剩余能量低于閾值時，觸發(fā)簇首輪換機制。具體實現(xiàn)過程如下：

(1)當(dāng)前簇首檢查其簇內(nèi)成員信息，調(diào)用簇首選舉函數(shù)，選舉能量值大且距離Sink節(jié)點近的成員節(jié)點為新簇首；

(2)若選舉成功，則建立新簇，若該簇中所有節(jié)點的能量值都低于ENgate，則告知Sink節(jié)點進行漏洞修補。

3 仿真與性能分析

本文采用Matlab對LEACH、PEGASIS和DCA算法進行仿真實驗，從網(wǎng)絡(luò)能量消耗、網(wǎng)絡(luò)生存周期兩個方面進行對比，同時對簇首選舉權(quán)重系數(shù)、多跳通信路由系數(shù)進行仿真試驗，選定最終系數(shù)值。仿真參數(shù)設(shè)置見表1。

表1 仿真參數(shù)設(shè)置

圖5為在LEACH、PEGASIS和DCA三種算法下，網(wǎng)絡(luò)能耗隨時間變化的仿真情況。

圖5 網(wǎng)絡(luò)能耗

從圖5可以看出，隨著時間的推移，DCA算法相比其他兩種算法的網(wǎng)絡(luò)能耗更低。DCA算法由于采用基于距離的節(jié)點分簇和多跳路由數(shù)據(jù)轉(zhuǎn)發(fā)技術(shù)，使得節(jié)點間的通信量大幅度減少，從而降低了網(wǎng)絡(luò)能耗。

圖6為網(wǎng)絡(luò)生存周期算法仿真比較圖。

圖6 網(wǎng)絡(luò)生存周期

由圖6可知，采用LEACH算法的傳感器節(jié)點在網(wǎng)絡(luò)運行到500輪時已經(jīng)全部死亡；PEGASIS算法下的節(jié)點最多可以存活到700輪；而DCA算法的節(jié)點最大存活時間為1000輪。通過對比可以發(fā)現(xiàn)，DCA算法大大增加了網(wǎng)絡(luò)中的存活節(jié)點個數(shù)，提高了網(wǎng)絡(luò)生存周期。

4 結(jié)論

本文以無線傳感器網(wǎng)絡(luò)為研究對象，針對WSN中節(jié)點能量有限，數(shù)據(jù)通信傳輸效率低的問題，提出一種基于距離分簇的無線傳感器網(wǎng)絡(luò)組網(wǎng)方法。根據(jù)節(jié)點剩余能量、與Sink節(jié)點通信距離等指標(biāo)來選取簇首，通過簇首輪換機制與設(shè)定每個簇的最大節(jié)點數(shù)目來均衡節(jié)點能耗，以合理選取簇間通信路由來提高網(wǎng)絡(luò)通信效率。最后，仿真結(jié)果從網(wǎng)絡(luò)能耗、網(wǎng)絡(luò)生存周期兩個方面驗證本文所提出算法的有效性。

[1] 蔣暢江,石為人,唐賢能,等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學(xué)報,2012,23(5):1222-1232.

[2] HEINZELMAN W,CHANDRAKASAN A.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Scineces.Muai:IEEE Computer Society,2000:3005-3014.

[3] LINDSEY S,RAGHAVENDRA C S.PEGASIS:Power-Efficient Gathering in Sensor Information Systems[J].IEEE Aerospace and Electronic Systems Society,2002(3):1125-1130.

[4] 蘇金樹,郭文忠,余朝龍.負載均衡感知的無線傳感器網(wǎng)絡(luò)容錯分簇算法[J].計算機學(xué)報,2014,37(2)445-456.

[5] 周東鑫,金文光,容志能.基于分層的無線傳感器網(wǎng)絡(luò)多跳分簇路由算法[J].傳感器技術(shù)學(xué)報,2011,24(1):73-78.

[6] Busse M,Haenselman T,Effelsberg W.A Comparison of Lifetime-efficient Forwarding Strategies for Wireless Sensor Networks[C]//Proceedings of the 4th International Symposium on Information Proceesing in Sensor Networks.New York,USA:[s.n.],2005:13-19.

[7] W B Heinzelman.Application specific protocol architecture for wireless microsensor networks[J].IEEE Transaction on Wireless Communications,2002,1(4):660-670.

[8] 李萌,孫恩昌,張延華.無線信道模型研究與展望(一)[J].中國電子科學(xué)研究院學(xué)報,2012,7(4):362-364.

[9] 李臘遠,李方云.一種基于低能量的雙簇首WSN路由算法[J].武漢理工大學(xué)學(xué)報,2009,33(3):450-453.

NetworkingMeasureBasedonDistance-clusteringAlgorithminWirelessSensorNetwork

HUA Jiangfeng,LV Yanhui,FU Yao,LIU Jielin

(Shenyang Ligong University，Shenyang 110159，China)

In order to solve the problem that the sensor nodes in the wireless sensor network can not supply the energy in time,a new method based on distance clustering algorithm in wireless sensor networks is proposed.Its purpose is to balance the node load and improve communication efficiency.The algorithm is initiated by the Sink node,setting up the different communication distance of the Sink node,sensor networks is divided.According to maximum number of nodes per cluster based on network layer,the network survival period is ensured by cluster head change mechanism.The inter cluster communication optimal routing is selected according to the multi hop routing function.The simulation results show that the algorithm can effectively reduce the network energy consumption and prolong the network lifetime.

wireless sensor network；clustering network；load balancing

2017-01-12

遼寧省自然科學(xué)基金資助項目(20170540777)

華江鋒(1991—),男，碩士研究生；通訊作者：呂艷輝(1971—)，女，教授，博士，研究方向：無線傳感器網(wǎng)絡(luò)、數(shù)據(jù)融合、系統(tǒng)仿真技術(shù)。

1003-1251(2017)06-0031-06

TP393

A

馬金發(fā))