異質傳感網中基于自適應簇半徑的高效組網算法*

秦寧寧,張偉杰

(江南大學輕工過程先進控制教育部重點實驗室,江蘇 無錫 214122)

無線傳感網WSN(Wireless Sensor Network)中節點能量的利用效率直接影響網絡的生命周期。由于節點分布式的選簇、入簇以及路由的規范劃分在網絡節能中更具優勢,使得網絡的分簇組網與逐級傳輸的工作模式,更適合以電池為能量供給的WSN中。目前同構組網算法已經相對成熟,但實際應用中,由于各種干擾因素的存在,網絡的異構化普遍存在,因此設計面向異構網絡的組網方案對均衡網絡能耗、提高節點能量的利用率以及延長網絡生命周期,具有更重要的現實意義。

分簇組網過程中的能量利用效率,主要受簇首選舉和分簇結構兩方面影響。尤其對于異構的WSN而言,由于節點之間存在能量差異,以高能量節點作為數據轉發的樞紐,顯然可以有效避免個別節點由于負荷過大提前死亡,確保網絡穩定運行,提高能量利用率。文獻[1]采用了一種分布式節能分簇算法,綜合考慮了節點初始能量以及剩余能量對簇首的影響,保證每輪選出的簇首能量最優,降低了簇首節點提前死亡的概率。廖福保等人[2]在簇首選取時綜合考慮節點剩余能量、節點度和節點的能量消耗速度等因素的影響,進一步優化簇首選舉,降低了簇首節點提前死亡的概率。簇首選舉時需要全網進行數據收發,每輪選舉會消耗一定的能量,減少簇首選舉次數,也是減少能量消耗的一種有效手段。文獻[3]提出簇首輪換的概念來減少簇首選舉時的能量損耗。馮咲[4]在此基礎上提出簇首輪換間隔的優化算法,能夠進一步自適應的實現簇首輪換。

優化分簇結構對均衡網絡能耗也具有正向的激勵作用,調整合理的簇內成員數量和通信范圍,可以有效控制簇內能量的消耗速度,從而均衡網絡能耗。兼顧最優簇首數量的條件下,文獻[5]為控制成員數目,以鄰居節點數為參考,回避過多鄰居節點入簇,縮小簇范圍來縮短簇內通信距離,提高能量利用率。文獻[6]根據相鄰節點的數量來選取簇首,通過計算簇內通信代價來調整簇半徑,縮小簇范圍以提高能量利用率。Park等人[7]采用K-means方法對網絡中的節點進行均勻分簇,選擇每個簇中最靠近幾何中心的節點擔任簇首,通過均勻簇的大小實現了均衡簇首能耗。李成法等人[8]反其道行之,提出了一種非均勻分簇算法,通過非均勻分簇來保證簇首能耗均衡,提高能量利用率。余修武等人[9]提出了一種以競爭半徑來配置簇首,設置簇首競爭半徑與到Sink節點的距離成反比,使得離Sink節點近的簇首具有較小的競爭半徑,縮小Sink周圍的簇規模,避免節點由于過勞中轉數據引發提早死亡。

利用幾何知識進行簇首選擇,從物理空間上規劃簇范圍,也是一種提高能量利用效率的有效手段。將網絡在同心圓的基礎上劃分單元格,以單元格為單位進行節點能量分級管理[10]。基于同心圓區域的理念,胡源等人[11]將圓劃分為等扇區,保證同環簇具有相同的通信范圍,均衡網絡能耗。為避免長距單跳通信引發的能量陡降,文獻[12]將以最小單跳距離配置環間距,對每環進行等面積劃分指導成簇,均衡了不同環之間簇的規模和結構,保證網絡能耗平衡,一定程度上延長了網絡生命周期。

客觀上講,已有研究成果中關于能量引導簇首選舉和均衡帶動成簇結構的理念,在本論文的研究中也有體現,但已有研究結論均為針對同構或者單一元素異構的傳感器網絡,而對于實際網絡應用場景中,由于工作環境、網絡負荷、物理器件等隨機因素的影響,節點更多的呈現出多元素化且隨機化的異構特性。這使得從簇首選舉-分簇組網-結構配置-路由規劃的組網全流程中,都應面向傳感器網絡異構性的多級化和隨機化特征展開。

論文面向隨機多級異構傳感器,提出了一種基于自適應簇半徑的高效組網算法ARCN(Adaptive Radius Cluster Networking algorithm)。能量與鄰居聯合影響下的簇首選舉機制,打破概率選舉中節點能力不等,卻機會均等當選簇首的不合理局面;引入適應值半徑的概念,動態控制簇首通信距離,以調節簇的結構與規模;計算簇首間的通信代價,作為通信路徑選擇的依據,實現通信能耗的降低。

1 網絡模型

在數據型傳感器網絡中,為縮短通信路徑的長度,可以充分利于RF信號的全向特征,將數據的匯聚中心Sink安置在網絡的物理中心位置。對于Sink而言,形成一個發散形式的全向數據收集網絡,可以提高數據收集的效率。因此,不失一般性,論文將研究場景設定為以Sink為中心的監測區域,并引入參考圓將網絡場景虛擬為一個圓形區域,如下圖1所示。場景的虛擬劃分,僅為了控制成簇的規模,并不干涉算法的運行,因此基于本場景的研究結論,可以擴展到其他不存在中空區域的網絡場景中。

圖1 網絡模型圖

1.1 節點的隨機異構性

給定監測區域I,以Sink為中心o點,依次向外將I劃分為共計M個準等間距的同心圓環,監測區域內的任意點?∈I,同心圓環的標記:

(1)

式中:c0圓半徑為Ro,其余環間距為Rk,設定Rk=Ro/2,do?表示任意點?與中心Sink點之間的距離。

給定隨機異構傳感器節點μ={μi(xi,yi)|i=1,2,…,N}隨機部署在I內,(xi,yi)表示節點的位置信息,μ的初始能量E={Ei|i=1,2,…,N}和初始半徑r={ri|i=1,2,…,N}滿足Ei∈[Emin,Emax]和ri∈[rmin,rmax]。以環間距離的最大跨度為參考,節點的初始通訊距離ri應滿足rmin≥2Rk=Ro。

1.2 能耗模型

節點通信能耗在固有能耗的基礎上,隨著數據量和通信距離的增長呈正比增長[13]。當節點μi向其通信范圍內的某一接收節點μj傳輸mbit數據,μi與μj之間距離為d,μi所消耗的能量為:

(2)

節點μj接收mbit數據時能耗為:

Erv(m)=mEelec

(3)

融合數據的能耗僅與簇首節點有關,簇首節點μj融合mbit數據時的能耗為:

Eag(m)=mEDA

(4)

式中:EDA是節點數據融合的單位比特能耗。

2 算法的思想與關鍵

2.1 算法思想

無線傳感器網絡中能量的消耗主要集中在數據傳輸階段,如何均衡網絡中節點能量消耗,對提高網絡能量的利用效率以及延長網絡生命周期尤為重要。為提高能量利用效率,設計了ARCN算法。節點基于鄰居信息進行簇首選舉并確定簇的結構規模,采用基于能效的自適應簇規模組網模式,在滿足通信距離的同時縮小簇的物理半徑,使得節點的單跳通信距離短小且有效,有利于縮小簇內數據對簇首節點負荷;尋找最優通信路徑以減小數據轉發時能量消耗,不僅保證了網絡的連通性還減緩了簇首節點能量消耗速度,避免個別節點提前死亡。

2.2 相關定義

定義1(最大可達節點集)節點μi和μj之間若存在通信鏈路,則互為鄰居節點,定義μi關于ri的最大可達節點集

T(μi,ri)={μj|dμiμj≤ri&&i≠j,μj∈μ}

(5)

定義2(適應值半徑)節點μi的適應值半徑為受所在ck影響的動態通信范圍,可定義為:

ri_ck=2γe1/k

(6)

式中:γ為調節參數,且γ∈[0,1]。

2.3 單/多跳通信模式的選擇機制

在分簇組網形成的網絡中,c0環內節點通過單跳或多跳的方式將信息轉發給Sink節點。在理論上,同等距離情況下,多跳通信比單跳通信節能,但在Sink節點周圍,經簇首轉發信息給Sink節點構成多跳通信,與未經簇首轉發的單跳通信相比,節能優勢有待考量;并且在Sink周圍的簇首由于半徑小、數量少容易使轉發負荷過大,造成個別節點(簇首)的業務量過大而過早死亡。因此,為降低c0內部分節點負荷,需要對c0內節點的通信模式(單跳/多跳)進行定性分析,為網絡選擇更為匹配的通信方式。

以Sink為圓心的c0圓內,p、q兩個節點為例,點p到Sink所在o點的通信方式分為兩種:一種是單跳通信模式,即p→o直接通信;另一種是由節點q作為中轉節點形成p→q→o多跳通信模式。

由式(2)可得,傳輸mbit數據量時,單跳p→o通信能耗為Esh,多跳p→q→o通信能耗為Emh,多跳與單跳的能耗差距為:

(7)

定理在給定形如式(1)網絡的c0區域內,基于無固有能耗的自由空間能耗模型,節點向位于o的Sink點發送相同量的數據,存在在一定的區域內,使得節點間采用單跳通信所消耗的能量小于區域內兩跳通信的能耗。

證明

由于節點通信半徑存在ri≥rmin≥Ro,若以Ro/2為半徑將c0圓劃分為內圓(標記為⊙2)和外環(標記為c0/⊙2),c1環內的簇首節點向Sink節點傳輸數據時,最差時必須在c0的外環處應存在某簇首p為其轉發數據。為中和Sink周邊節點的負荷,c0內所有節點q∈⊙2均應作為簇首參與數據通信。

基于無固有能耗的自由空間能耗模型(Eelec=0)和式(7),定理只需證明存在式(8)成立的區域,即

(8)

式中:dpo、dpq和dqo分別表示節點p、q和o之間的距離。

不失一般性,建立Sink節點所在的o點為原點,以op為縱軸的坐標系如圖2所示,設定p(xp,yp),q(xq,yq),由于點p位于y軸上,最差情況位于(0,Ro),將其代入式(8),可得式(9):

(9)

同理,最優情況下p位于內圓圓周上,坐標為(0,Ro/2),可得式(10):

(10)

式(9)～式(10)的等效幾何區域如圖2中圓⊙3和圓⊙1,圓心分別為(0,Ro/2)和(0,Ro/4),半徑分別為Ro/2和Ro/4。節點p的初始半徑為rp≥R0,故圓⊙4表示點p以R0為半徑的通信范圍。

(11)

圖2 c0內節點通信模式幾何等效圖

基于無固有能耗的自由空間模型,存在一定的區域且存在[11%,43%]的概率,節點間采用單跳通信的能耗小于兩跳通信的能耗。

證畢。

結合上述定理,不考慮固有能量消耗時,在c0內,為c1環轉接數據的簇首p∈c0/⊙2存在[11%,43%]的概率,以單跳p→o通信更為節能,且該比例隨固有能耗的加入而增高。

同理,若為c1環轉接數據的簇首p∈⊙2會存在大于43%的概率以單跳p→o通信更為節能。故,論文將⊙2內的節點全部設置為簇首,不僅在通信模式上進行了節能優化,又避免了節點因轉發數據量較大過早死亡,緩解Sink中心區域節點淪陷問題。

3 自適應半徑的分簇組網算法

3.1 組網階段

①動態簇首競爭

網絡中能量消耗主要與簇的物理空間大小和簇內成員數目有關,簇首的管理半徑關系著簇的物理空間大小,因此引入適應值半徑,用以調控簇的跨度大小。考慮到簇首作為簇內和簇間數據的轉發樞紐,因此應盡可能地選擇高能量節點擔當。鑒于上述兩個因素,定義簇首的選舉公式:

(12)

W(i)體現了μi成為簇首的配重價值,值越高則越容易當選簇首。其中調節參數α、β用來調整μi的可達節點集以及其剩余能量對簇首選舉的影響程度,存在α+β=1;|TN(μi,ri_ck)|表示μi關于適應值半徑ri_ck范圍內可達節點集內的鄰居節點數量;|TN(μi,ri)|表示μi關于通信半徑ri范圍內最大可達節點集內的鄰居節點數量。

基于W(i)的配重公式,可以看出該選舉公式綜合考慮了節點的剩余能量Ei以及鄰居節點數量|TN(μi,ri_ck)|對μi當選簇首的積極影響。

②簇架構

對任意節點μi∈TN(μj,rj_ck),若滿足W(j)>W(i),則節點μj當選為簇首;當選節點μj廣播一條簇首消息Message_header(uj,Ej)。普通節點μi收到Message_header(uj,Ej)后,在其通信范圍內選擇距離最近的μj入簇,需要說明的是對于相同距離的簇首,μi優先加入具有高能簇首的簇。具體流程如下。

Join-cluster(μi,ri)Line 1distance=riLine 2μi wait for receive MessageLine 3while Message_header(uj,Ej)Line 4 if distance>distance(μj,μi)Line 5 distance=distance(μj,μi)Line 6 μi_header=μjLine 7end ifLine 8if distance==distance(μj,μi)Line 9μi_header=μfind(max(Eμi_header,Ej))Line 10 end ifLine 11end whileLine 12return μi_header

算法中Line4～7表示μi收到uj的Message_header(uj,Ej)后,選擇距離最近的簇加入;Line8～10在兩個相等距離的簇中,μi選擇具有高能剩余能量簇首的簇加入,其中find[max(Eμi_header,Ej)]表示高能剩余能量簇首的編號。

3.2 數據通信階段

簇首節點負責數據轉發工作,路由決定著數據被轉發次數,因此選擇一條最優路徑進行數據通信,將有利于減緩簇首節點的能耗。ARCN算法采用單跳與多跳結合的路由方式進行數據通信。成員節點首先將采集到數據傳輸給簇首節點,簇首節點進行數據融合并進行數據轉發,選擇一條最優路徑將數據發送至Sink。

c0內⊙2內的簇首節點可以直接與Sink節點進行通信,c0/⊙2內的簇首節點多跳的通信方式更加占據節能優勢。任意兩個可通信的簇首μi,μj?⊙2之間的通信代價為

(13)

對任意簇首節點μi收到消息Message_header(uj,Ej)后,采用最短路徑Dijkstra算法,計算簇首間的通信代價,可以找出向Sink節點數據傳輸的最優路徑,具體流程如下。

Communication(μi,ri)Line 1header_dis=riLine 2μi wait for receive MessageLine 3while μi receive Message_header(uj,Ej)Line 4 if distance(μi,Sink)≥Ro/2Line 5 if distance(μi,Sink)>distance(μj,Sink)Line 6 if header_dis>distance(μj,μi)Line 7 header_dis=distance(μj,μi)Line 8 μi_communication_header=μjLine 9 end ifLine 10 if header_dis==distance(μj,μi)Line 11 μi_communication_header=μfind(max(Eμi_header,Ej))Line 12 end ifLine 13 end ifLine 14 else μi_communication_header=SinkLine 15 end ifLine 16end whileLine 17return μi_communication_header

算法中Line6～9表示簇首節點μi收到其他簇首節點μj廣播的消息后,選擇靠近Sink節點且距離最近的簇作為中轉簇首;Line10～12在兩個相等距離中轉簇首中,選擇剩余能量較高的簇首為中轉簇首;如果節點位于Sink節點周圍Ro/2內,則直接與Sink節點通信。

3.3 算法流程

作為一種分布式工作的算法,ARCN在網絡初始階段,根據簇首選舉公式將節點區分為簇首與普通節點;普通節點根據與簇首節點之間的距離,并參考能量,擇優加入最近的簇。對于每個節點μi通過ARCN算法的調度,最終可以實現對一個隨機異構傳感器網絡的快速、效優的組網,對于網絡中的任意節點μi可采用ARCN算法實現自適應半徑的分簇組網,具體工作流程如下。

ARCN(μi,ck,ri.Ei)Line 1Calculateri_ck,TN(μi,ri_ck),TN(μi,ri),W(i)Line 2Path(μi)=μiLine 3Broadcast(μi,W(i))Line 4for each μj∈TN(μi,ri)Line 5 μi wait for receiver messageLine 6 if (W(i)max(W(j))Line 11 BroadcastMessage_header(μi,Ei)Line 12 Path(μi)=Communication(μi,ri)Line 13end if

算法Line4～9首先判斷節點μi是否可以當選為簇首節點,若不能當選則運行Join-cluster算法,得到普通節點μi的通信鏈路Path(μi);當選簇首的節點μi則執行Communication算法,得到簇間通信的鏈路信息Path(μi)。通過ARCN算法可用得到全局節點的通信鏈路Path(μ),完成對隨機異構傳感器網絡的快速分簇組網與路由配置。

4 仿真實驗

4.1 場景配置

論文采用MATLAB R2016a平臺進行試驗,為驗證算法的性能,實驗在隨機異構網絡中進行分簇組網。通過與LEACH[5]、URCP[9]及EBCP[12]3種經典方法的對比實驗,驗證ARCN在提高能量利用率,減緩節點死亡速度以及延長網絡生命周期方面的效果。算法假設傳感器節點隨機部署在S=πR2(R=500 m)的圓形區域內,環數k=3。節點剩余能量與其通信半徑成正比例關系。場景與網絡參數如表1所示。

為驗證網絡的壽命,引入網絡周期Ts的概念,用于統計網絡的壽命。在每個Ts周期內,網絡更新運行ARCN算法進行分簇、組網,并設定每個節點在Ts內向Sink通信m=4 000 bit數據,簇首節點的能耗分為兩種:一是負責簇內數據的融合和轉發;二是作為其他簇首的中轉節點,能量消耗采用式(2),參數如表1。當節點μi無法與任何節點構成通信鏈路時,則認定μi死亡。考慮到試驗場景和網絡配置的隨機性,所有實驗數據均采用20次獨立實驗的平均值,并且保證不同算法間單次實驗具有一致的初始場景。

表1 實驗參數

4.2 ARCN的分簇效果

對于論文給定的以物理中心位置作為Sink的隨機異構傳感器網絡而言,網絡的分簇情況,直接影響著節點數據的通信效率和能量消耗。圖3給出了500個初始能量(0.250 J～0.375 J)和通信半徑(100 m～150 m)均為異構的傳感器網絡,在ARCN分簇組網算法的調控下,首輪Ts=1工作時形成的網絡結構和通信鏈路的情況。

圖3 分簇效果圖(Ts=1)

ARCN中的節點僅在各自單跳范圍內,基于鄰居信息進行分布式操作,使得簇在位置上應盡可能地分散,從c1～c3環分別形成了9、12和15個簇,基本保證了同環單位空間內具有近似相當數量的簇。作為簇首的高能節點通過適應值半徑控制其管理范圍,保證簇的大小相對均勻,避免簇內過度長跳。c0中心圓內的簇首數量適度增加為20,以更多簇首來均衡靠近Sink區域的高通信負荷。

隨著工作時長的增加,網絡周期內能參與通信的節點數量越多,表明網絡越穩定,節點的能量利用越均衡,效率越高,因此本實驗分別使用LEACH、URCP、EBCP和論文提出的ARCN,通過統計網絡在每個時間周期Ts內的能量利用效率,比較4種算法在組網和通信策略設置時,對節點能耗利用的有效性,實驗數據統計如圖4所示。其中,以當前網絡周期內全網總能耗與全網初始總能量的比值,作為當前周期內能量效率的統計量。

圖4 能量利用率圖

圖4給出了全網能量利用率隨時間變化的情況。在初始階段(Ts<40)時,4種算法彼此相對穩定的運行,全網能量利用率沒有明顯差距。當Ts>40時,由于在LEACH與URCP的簇首選舉過程中,缺少對能量Ei的考慮,導致低能節點占據簇首角色提前死亡,能量利用率近似維持在個自的峰值(LEACH峰值為38%,URCP為35%)不再增長,間接表明參與網絡的節點過少導致鏈路不完整,網絡已經無法穩定運行。EBCP算法通過代價函數的作用,持續到Ts=50時,達到43%的效率峰值,此后由于缺少組網的可用節點,網絡也停止通信工作。ARCN算法能夠穩定運行到Ts=70輪左右,是由于引入適應值半徑來管理分簇跨度,降低單跳能耗,避免簇首節點能耗過大導致剩余能量過低而無法參與網絡構成,從而有效的保證網絡的連通性,延長了網絡的生命周期。

4.3 節點死亡數量

節點是組成傳感器網絡的重要因素,若參與組成網絡的節點過少,則網絡無法穩定運行。本實驗分別統計每個網絡周期內死亡節點數量(如圖5(a))以及中心區域(Sink節點附近)高能耗節點死亡比率(如圖5(b)),比較4種算法的剩余節點數量對網絡生命周期的影響。

圖5 網絡剩余節點與中心區域死亡率圖

圖5(a)可以看出,在Ts<10時,4種算法基本沒有節點死亡,表明節點初始能量大于0.25J與高密度的配置方式,使得網絡中即使存在高耗能節點也能夠維持將近Ts=10輪的生命周期。在Ts>10 輪后,由于沒有對高能耗節點進行優化選擇,LEACH、URCP和EBCP3種算法開始有節點死亡;ARCN算法節點在Ts>20之后才開始有節點死亡,表明算法在簇首選舉時綜合考慮了剩余能量以及鄰居節點集,能夠有效的避免高能耗節點參與較多的數據轉發,延緩死亡;在Ts>60輪之后,LEACH、URCP和EBCP3種算法的節點已經全部死亡,而ARCN算法中的節點運行Ts>70輪后才全部能量耗盡死亡,說明算法的選簇、入簇以及簇間通信的方法能夠有效的均衡節點能耗,減緩節點死亡速度,延長網絡的生命周期。

對于中心⊙2區域的節點壽命情況如圖5(b)中所示,可以看出在Ts>10后LEACH、URCP和EBCP3種算法節點死亡速率攀升較快,ARCN算法在20輪之后中心區域的節點開始死亡,且死亡速度相對緩慢,主要在于ARCN算法在中心區域⊙2采用單跳與多跳混合的方法,改善了高能耗節點過早死亡問題,不會出現因中心區域淪陷而造成網絡中出現大規模節點不連通的現象。

4.4 網絡生命周期

網絡的穩定性也是評估一個算法的重要指標,由于節點能量與半徑的隨機性,網絡壽命也隨機波動。本實驗統計了4種算法的網絡生命周期的分布情況,來驗證算法的穩定運行能力,實驗數據如圖6所示。

圖6 網絡生命周期箱型圖

圖中可以明顯看出LEACH與URCP算法的中值大概在Ts=40輪左右,EBCP算法的壽命中值在Ts=45輪左右,而ARCN算法中值均在Ts=55輪左右;原因在于EBCP與ARCN算法將網絡區域等效為一個圓形的檢測區域,并且引入了參考圓的概念,使得簇大小以及簇數量相對穩定,從而保證了網絡的穩定性。此外 ARCN算法的壽命波動范圍與其他3種算法相比相對較小,并且異常值較少,表明ARCN算法對于場景有著較好的普適性。

5 總結

針對網絡能耗不均衡、能量利用效率低等問題,論文提出了一種基于自適應簇半徑的高效組網算法ARCN。充分利用異構性能引發的鄰居數目和剩余能量的雙重差異,并作為選舉指標,保證高能和服務范圍更廣的優勢節點擔當簇首。引入的適應值半徑、簇首代價函數矩陣和內環通信模式調整,實現了從簇內到簇間能量優化。由于ARCN算法不依賴于全局信息,利用節點間的異構性能作為分簇組網的基礎,提高了方法的適用性。但客觀上講,網絡初始階段對于環數的確定需要預先對服務場景進行了解,未來的研究中,對于自適應環數配置和間距調整也將值得研究。