基于阿基米德螺旋的WSNs節(jié)點(diǎn)部署的能耗均衡算法*

郝小會(huì),申玉霞,趙冬玲

(濟(jì)源職業(yè)技術(shù)學(xué)院,河南 濟(jì)源 459000)

無(wú)線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Netorks)[1]已廣泛應(yīng)用于各個(gè)領(lǐng)域,如環(huán)境、工業(yè)。然而WSNs遭受了較多不可避免的問(wèn)題,如資源受限、隨機(jī)部署。特別是節(jié)點(diǎn)能量受限問(wèn)題。因此,在設(shè)計(jì)WSNs時(shí)應(yīng)重點(diǎn)關(guān)注網(wǎng)絡(luò)能量,進(jìn)而最大化網(wǎng)絡(luò)壽命[2-3]。

而網(wǎng)絡(luò)內(nèi)能量消耗率取決于節(jié)點(diǎn)的部署特性,而部署特性主要取決于應(yīng)用環(huán)境。目前,有兩類(lèi)節(jié)點(diǎn)部署方案:隨機(jī)部署和確定性部署[4]。隨機(jī)部署常應(yīng)用于物理環(huán)境難以接入的區(qū)域,如火山,地震區(qū)域等,常用直升飛機(jī)向這些區(qū)域散落節(jié)點(diǎn)[4-5]。而確定性部署是常應(yīng)用于物理空間可接入的環(huán)境,如目標(biāo)跟蹤、城區(qū)監(jiān)測(cè)。而在這些環(huán)境中,常通過(guò)人工部署節(jié)點(diǎn)[4]。

此外,簇技術(shù)被認(rèn)為是保存能量的有效技術(shù)之一。將網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)劃分多個(gè)簇,每個(gè)簇有一個(gè)簇頭CH(Cluster Head),而簇內(nèi)的其他節(jié)點(diǎn)稱(chēng)為成員節(jié)點(diǎn)MNs(Member Nodes)。MNs感測(cè)環(huán)境,然后將感測(cè)的數(shù)據(jù)傳輸至相關(guān)的簇頭CHs。然后,由CHs融合數(shù)據(jù),再向信宿(基站)傳輸數(shù)據(jù)。常采用周期地重建簇的策略,通過(guò)選擇剩余能量較多的節(jié)點(diǎn)作為CHs,進(jìn)而均衡網(wǎng)絡(luò)能量,使得網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)能量消耗相近。除了保存能量方面的優(yōu)勢(shì)外,簇技術(shù)還可以減少信道競(jìng)爭(zhēng)和數(shù)據(jù)包丟失率,這有利于提高網(wǎng)絡(luò)吞吐量。

盡管簇技術(shù)在保存能量方面具有一定優(yōu)勢(shì),但是若僅依靠簇技術(shù)是難以避免能量空洞問(wèn)題。一旦發(fā)生遭遇能量空洞問(wèn)題,網(wǎng)絡(luò)壽命將受到影響。為此,研究人員從節(jié)點(diǎn)部署角度入手,并結(jié)合簇技術(shù),避免能量空洞問(wèn)題。

為此,本文首先分析能耗均衡在延長(zhǎng)網(wǎng)絡(luò)壽命方面的性能,并發(fā)現(xiàn)每一層的簇?cái)?shù)以及簇成員數(shù)對(duì)網(wǎng)絡(luò)壽命有重要的影響。然后,再提出基于阿基米德螺旋(Archimedes spiral)的節(jié)點(diǎn)部署方案AS-DBEC,通過(guò)有效地部署節(jié)點(diǎn),提高了能量利用率,最終延長(zhǎng)了網(wǎng)絡(luò)壽命。實(shí)驗(yàn)結(jié)果表明,AS-DBEC方案在保存能量和網(wǎng)絡(luò)壽命方面具有一定的優(yōu)勢(shì)。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

考慮a×a方形的網(wǎng)絡(luò)區(qū)域,且其由一系列的電暈覆蓋[6-7]構(gòu)成,如圖1所示。假定信宿位于網(wǎng)絡(luò)區(qū)域中心,并由信宿負(fù)責(zé)從傳感節(jié)點(diǎn)收集數(shù)據(jù)。而傳感節(jié)點(diǎn)以隨機(jī)方式分布于不同層內(nèi)。

圖1 網(wǎng)絡(luò)模型

整個(gè)網(wǎng)絡(luò)劃分為N層。因此,網(wǎng)絡(luò)內(nèi)存在N個(gè)簇。據(jù)此,離信宿最近的簇位于第1層Layer-1(第1類(lèi)),而離信宿最遠(yuǎn)的簇位于第N層Layer-N(第N類(lèi))。最后,假定在第i層的節(jié)點(diǎn)有j個(gè)簇(j>1)。

假定網(wǎng)絡(luò)為靜態(tài)的異構(gòu)網(wǎng)絡(luò),同時(shí)依據(jù)文獻(xiàn)[8]將網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)劃分許多簇,其中異構(gòu)性是指節(jié)點(diǎn)的功能和電池容量的不同。所謂功能上的異構(gòu)是指網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)為兩類(lèi):成員節(jié)點(diǎn)MNs(非簇頭節(jié)點(diǎn))和簇頭CHs。而在電池容量方面,MNs具有有限的電量,而CHs裝備了更充足的電量。不失一般性,假定CHs位于它的簇中心[7]。

1.2 感測(cè)和通信模型

如果區(qū)域內(nèi)的每個(gè)節(jié)點(diǎn)至少有一個(gè)活動(dòng)MN覆蓋[4],則認(rèn)為此區(qū)域被覆蓋。節(jié)點(diǎn)MN的感測(cè)區(qū)域半徑為Rs。而通信半徑為Rc。假定如果兩個(gè)節(jié)點(diǎn)的歐式距離不超過(guò)Rc,則它們能直接交互消息。

1.3 能量模型

考慮文獻(xiàn)[9]的一級(jí)無(wú)線電模型作為能量模型,其中節(jié)點(diǎn)能量主要由無(wú)線傳輸和接收方面上進(jìn)行消耗。因此,忽略其他能耗因素。

在傳輸范圍Rc內(nèi),傳輸n比特?cái)?shù)據(jù)所消耗的能量etr(n,Rc)可表示為:

(1)

式中:et表示傳輸一比特?cái)?shù)據(jù)所消耗的能量。相反,接收n比特?cái)?shù)據(jù)所消耗的能量ere(n):

ere(n)=eelec×n=er×n

(2)

式中:eelec=er,其表示接收一比特?cái)?shù)據(jù)所消耗的能量。

最后,融合n比特?cái)?shù)據(jù)所消耗的能量eda(n)可表示為:

eda(n)=ea×n

(3)

式中:ea表示融合一比特?cái)?shù)據(jù)所消耗的能量。

1.4 信道傳播模型

引用瑞利衰落信道模型[7]描述CHs間和CH與信宿間的通信信道。假定發(fā)射器與接收器間距離為,信道增益可表示為:

h()/0)-ηξ=L(0)(/0)-ηξ

(4)

此外,本文認(rèn)為:可靠接收信號(hào)可表述為Pr{erx≥τ}≥δr,其中erx為接收信號(hào)的能量,而τ是預(yù)定能量的閾值,δr為所需的鏈路可靠值。

1.5 網(wǎng)絡(luò)壽命

本文規(guī)定,網(wǎng)絡(luò)壽命是指從節(jié)點(diǎn)部署開(kāi)始直至失效節(jié)點(diǎn)的比例超過(guò)一定門(mén)限值的時(shí)間[10]。當(dāng)失效節(jié)點(diǎn)超過(guò)一定比例后,就無(wú)法提供網(wǎng)絡(luò)覆蓋和連通。所謂失效節(jié)點(diǎn)是指節(jié)點(diǎn)剩余能量少于預(yù)定值,且不能傳輸任何數(shù)據(jù)或接收任何數(shù)據(jù)。

2 問(wèn)題描述

平衡能量消耗有利于網(wǎng)絡(luò)壽命的提高。所謂平衡能量消耗是指網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)的能耗速度相同或相近。而本節(jié)的目的就是通過(guò)推導(dǎo)說(shuō)明:可通過(guò)部署節(jié)點(diǎn),平衡節(jié)點(diǎn)間的能量消耗。為后續(xù)的節(jié)點(diǎn)部署策略提供理論依據(jù)。

(5)

類(lèi)似地,Layer-N層的第j個(gè)CH所消耗的能量ENj:

(6)

(7)

令eti表示為從Layer-i層第j個(gè)CH傳輸一比特?cái)?shù)據(jù) 至Layer-(i-1)層第j個(gè)CH所消耗的能量,式(6)可以重寫(xiě):

(8)

依據(jù)網(wǎng)絡(luò)模型,處于Layer-i、Layer-(i-1)的兩CH間的距離li:

(9)

接收單比特的能量消耗eri如式(10)所示:

eri=etiL(l0)(li/l0)-ηξ

(10)

此外,對(duì)于瑞利衰落信道[11-12],鏈路可靠要求可表述為:

(11)

依據(jù)式(11)可得:

(12)

依據(jù)最短路徑協(xié)議,每條路徑含有的最大鏈路數(shù)為N。因此,為了產(chǎn)生對(duì)路徑可靠性的限制,即最小鏈路可靠值δp:

(13)

最后,處于Layer-i的第j個(gè)CH所消耗的能量為:

(14)

由于我們目的就是減少CH的能量消耗率,可建立式(15)所式的優(yōu)化問(wèn)題:

(15)

式中:ε為CH的初始能量。由于所有CHs的初始能量相同,式(15)可寫(xiě)成:

(16)

再利用線性規(guī)劃問(wèn)題定義式(16),如式(17)所示。

(18)

式(18)第1個(gè)約束項(xiàng)保證簇間流量;第2個(gè)約束項(xiàng)限制了在網(wǎng)絡(luò)內(nèi)規(guī)定時(shí)間所有MNs產(chǎn)生的數(shù)據(jù)是常數(shù)。而式(18)的第3個(gè)約束項(xiàng)保證了MNs和CHs的數(shù)量為非負(fù)數(shù)。

每一層的簇?cái)?shù)以及每個(gè)簇的MNs數(shù)可通過(guò)優(yōu)化問(wèn)題進(jìn)行解決。然而,每一層的單一CHs可能仍保持不平衡,并且這種不平衡也會(huì)產(chǎn)生能量空洞問(wèn)題。消除能量不平衡問(wèn)題的有效方式之一就是以預(yù)定位置部署MN和CH[4]。

文獻(xiàn)[13]分析了消除能量空洞問(wèn)題的研究工作。這些預(yù)定節(jié)點(diǎn)部署方案顯示了在端到端時(shí)延、吞吐量、數(shù)據(jù)包丟失率方面均有重要的提高。

為此,考慮到電暈覆蓋的網(wǎng)絡(luò)模型,提出基于阿基米德螺旋(Archimedes spiral)的預(yù)定節(jié)點(diǎn)部署策略。電暈覆蓋的圖形與阿基米德螺旋相似,并且螺線的每條臂的距離相等,進(jìn)而使得節(jié)點(diǎn)部署更趨于均勻化。

3 部署策略AS-DBEC

3.1 部署階段

3.1.1 基于阿基米德螺旋的節(jié)點(diǎn)部署

首先,將螺旋定義為曲線,其從中心點(diǎn)放射,然后圍繞此點(diǎn)旋轉(zhuǎn),并逐漸遠(yuǎn)離。一個(gè)阿基米德螺旋是一階圓圈CT(Circular Turn)的曲線,且極方程為Rd=θB,其中Rd為半徑距離、而θ為極角。B是一個(gè)實(shí)數(shù),且其值為常數(shù)。

兩個(gè)連續(xù)圓圈CT(Circular Turn)的距離可通過(guò)B進(jìn)行計(jì)算。阿基米德螺旋的一個(gè)顯著特點(diǎn)就是兩個(gè)連續(xù)圓圈的距離等于2πB,如圖2所示。

圖2 基于阿基米德螺旋的節(jié)點(diǎn)分布

3.1.2 基于離散的阿基米德螺旋的節(jié)點(diǎn)部署

由于阿基米德螺旋是連續(xù)曲線,將它作為部署節(jié)點(diǎn)的函數(shù)。為此,將此連續(xù)曲線轉(zhuǎn)換為離散形式,致使節(jié)點(diǎn)就部署于這些離散位置上。

首先,利用式(19)和式(20)建立離散曲線。

f(θk)=θkB

(19)

式中:θk∈[2(k-1)π,2kπ],且k=1,…,K。

式(19)中:k表示CT,而θk表示由第k個(gè)CT所覆蓋的總角度。接下來(lái),在每個(gè)CT內(nèi)位置被指定的范圍內(nèi),這些離散點(diǎn)需要被識(shí)別,進(jìn)而才能部署傳感節(jié)點(diǎn)。

據(jù)此,將θk分解為m個(gè)離散位置,再在每個(gè)離散位置上部署節(jié)點(diǎn)。θk的分解如式(20)所示。

θk(m)=[2(k-1)π+mφk]

(20)

式中:k=1,…,K。且對(duì)于每個(gè)k,m=1,…,2π/φk。

式(20)中:φk代表在第k個(gè)CT內(nèi)兩個(gè)相鄰節(jié)點(diǎn)的角度差,如圖3所示。在每個(gè)CT的m個(gè)離散位置部署節(jié)點(diǎn)時(shí),可以從m=2π/φk位置開(kāi)始,在m=1位置結(jié)束。

AS-DBEC算法的目的就是將阿基米德螺旋作為節(jié)點(diǎn)部署函數(shù),致使它能近似地代表分層的網(wǎng)絡(luò)區(qū)域(如圖1所示)。為了實(shí)現(xiàn)這個(gè)目的,將分層的網(wǎng)絡(luò)區(qū)域的Layer-i分解為多個(gè)子區(qū)域ωi×ωi,其中ωi=ri-ri-1。

AS-DBEC算法將每個(gè)螺旋作為一個(gè)簇,且這個(gè)螺旋的初始點(diǎn)為CH,而在每個(gè)CT的離散位置上部署MNs。

圖3 部署CHs和MNs示意圖

3.2 簇建立階段

由于一層有多個(gè)簇,而任意層內(nèi)的MNs數(shù)以及部署位置均為已知,因此,無(wú)需單獨(dú)算法去產(chǎn)生CH。

依據(jù)阿基米德螺旋部署方案,部署了CH和MNs節(jié)點(diǎn)后,就形成了簇。形成簇的偽代碼如表1所示。

表1 部署節(jié)點(diǎn)的偽代碼

圖3顯示了大型網(wǎng)絡(luò)區(qū)域由多個(gè)圓區(qū)域構(gòu)成示意圖。在每個(gè)子區(qū)域內(nèi),就依據(jù)式(12)和式(13)部署MN和CH。

許多現(xiàn)實(shí)生活應(yīng)用,如火山監(jiān)測(cè)和精細(xì)農(nóng)業(yè)。這些應(yīng)用都是利用直升飛機(jī)[5]或空中機(jī)器人按預(yù)定位置部署節(jié)點(diǎn)。考慮這些因素,提出的基于Archimedes spiral 部署節(jié)點(diǎn)算法是可行的,也具有一定的應(yīng)用前景。

3.3 數(shù)據(jù)傳輸過(guò)程

假定每個(gè)MN的數(shù)據(jù)產(chǎn)生率為n bit/s。一旦部署節(jié)點(diǎn)后,每個(gè)MN就向它的簇頭傳輸數(shù)據(jù)。然后由簇頭融合數(shù)據(jù),再向信宿(基站)傳輸數(shù)據(jù)。

顯然,相比MN,CH承擔(dān)了更多的數(shù)據(jù)壓力。因此,CH的能量消耗速度更快。此外,CH在維護(hù)網(wǎng)絡(luò)連通方面的角色比MN更重要。為此,本文著力關(guān)注CHs的能耗。

假定CH以最短路徑向信宿傳輸數(shù)據(jù)。具體而言,處于Layer-i的CH從處于Layer-(i-1)層選擇下一跳節(jié)點(diǎn)。為了保證最短路徑,就選擇離自己最近的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。同樣,處于Layer-(i-1)層的CH再?gòu)腖ayer-(i-2)層選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。此過(guò)程一重復(fù),直到將數(shù)據(jù)傳輸至信宿。

4 性能仿真

4.1 仿真環(huán)境

本節(jié)利用MATLAB 7.0.1仿真軟件建立仿真平臺(tái)。同時(shí)考慮兩個(gè)網(wǎng)絡(luò)尺寸:5層和10層,且a=100 m。每層的節(jié)點(diǎn)數(shù)由式(20)的離散點(diǎn)決定。在仿真過(guò)程中,假定運(yùn)行接收器/接收器無(wú)線電路所消耗能量eelec=50 nJ/bit,而獲取可接收的信噪比(30 dB)的放大器eamp=10 pJ/(bit/m2)。其他的網(wǎng)絡(luò)仿真參數(shù)如表2所示。

表2 仿真參數(shù)

從能量均衡和網(wǎng)絡(luò)壽命方面分析AS-DBEC算法。選擇每CH所消耗的能量ECR per CH(Energy Consumption Rate per CH)表述能量均衡。

為了分析AS-DBEC算法在延長(zhǎng)網(wǎng)絡(luò)壽命方面上的性能,選擇基于能量均衡的簇算法EBCA(Energy-Balanced Clustering Approach)[7]和基于靜態(tài)簇頭的簇算法SHCS(Static-Head Clustering Strategy)[8]進(jìn)行比較。

在仿真中,在實(shí)施EBCA時(shí),與文獻(xiàn)[7]類(lèi)似,考慮均勻的圓形簇,且簇頭部署于簇內(nèi)中心,而MNs圍繞簇頭隨機(jī)分布,仿真過(guò)程中,在5層內(nèi)隨機(jī)部署30個(gè)節(jié)點(diǎn);在10層內(nèi),隨機(jī)部署65個(gè)節(jié)點(diǎn)。而在部署SHCS方案時(shí),考慮均勻的方形簇,且簇頭位于方形區(qū)域中心,而MNs圍繞CH,并按確定性部署,且形成網(wǎng)格拓?fù)?總。此外,AS-DBEC、EBCA和SHCS算法所考慮的網(wǎng)絡(luò)模型為基于Corona的網(wǎng)絡(luò)模型,如圖1所示。

圖4 能量均衡

4.2 數(shù)據(jù)分析

首先分析算法的能量均衡性能,實(shí)驗(yàn)數(shù)據(jù)如圖4所示,其中圖4(a)為5層網(wǎng)絡(luò)結(jié)構(gòu)、4(b)為10層網(wǎng)絡(luò)結(jié)構(gòu)。

首先,將圖4(a)和圖4(b)相比發(fā)現(xiàn),網(wǎng)絡(luò)層數(shù)的增加,提高了能量消耗。例如,在5層網(wǎng)絡(luò)結(jié)構(gòu)內(nèi),AS-DBEC算法的ECR per CH為62.48 μJ/s,而當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)達(dá)到10層時(shí),AS-DBEC算法的ECR per CH為84.29 μJ/s。原因在于:網(wǎng)絡(luò)尺寸的增加,提高了數(shù)據(jù)流量,導(dǎo)致了能耗的增加。

然后,在給定網(wǎng)絡(luò)層次環(huán)境下,AS-DBEC算法的ECR per CH 隨層數(shù)接收直線。這說(shuō)明簇技術(shù)能夠有效地均衡能量。而EBCA和SHCS算法的ECR per CH隨層次數(shù)的增加,呈下降趨勢(shì)。注意到,在Layer-1時(shí),ECR per CH最大。這也說(shuō)明離信宿最近的CH承擔(dān)了更多數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)。與EBCA和SHCS算法,提出的AS-DBEC算法的ECR per CH得到有效控制,且曲線平穩(wěn),這說(shuō)明AS-DBEC算法在均衡CH的能耗具有較大的優(yōu)勢(shì)。

接下來(lái),分析AS-DBEC算法的網(wǎng)絡(luò)壽命,實(shí)驗(yàn)數(shù)據(jù)如圖5所示,其中圖5(a)為5層網(wǎng)絡(luò)結(jié)構(gòu)、圖5(b)為10層網(wǎng)絡(luò)結(jié)構(gòu)。

圖5 網(wǎng)絡(luò)壽命

從圖5(a)可知,與EBCA和SHCS算法相比,提出的AS-DBEC算法的網(wǎng)絡(luò)壽命分別提高了28.57%和18.73%。原因在于:EBCA和SHCS算法遭受能量空洞問(wèn)題。此外,AS-DBEC算法的網(wǎng)絡(luò)壽命隨層數(shù)變化曲線更為平坦,這也再一次說(shuō)明,AS-DBEC算法的能耗更為更為均衡。

5 總結(jié)

本文針對(duì)無(wú)線傳感網(wǎng)絡(luò)的能耗問(wèn)題,先分析了均衡能耗對(duì)網(wǎng)絡(luò)壽命的影響,然后提出阿基米德螺旋的節(jié)點(diǎn)部署策略AS-DBEC。將阿基米德螺旋作為部署函數(shù),并進(jìn)行離散化,最后通過(guò)這些離散位置部署節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明,與同類(lèi)算法相比,提出的AS-DBEC算法能夠均衡簇頭間的能耗,延長(zhǎng)網(wǎng)絡(luò)壽命。

[1] Chi Q,Yan H,Zhang C,et al. A Reconfigurable Smart Sensor Interface for Industrial WSN in Io T Environment[J]. IEEE Trans Ind Inf,2014,10(2):1417-1425.

[2] 范敏,謝思佳. 基于空洞模型的地理位置路由改進(jìn)算法研究[J]. 傳感技術(shù)學(xué)報(bào),2012,25(11):1556-1561.

[3] Stine J A. Exploiting Smart Antennas in Wireless Mesh Networks Using Contention Access[J]. IEEE Wireless Commun,2016,13(2):38-49.

[4] Halder S,Ghosal A,Das Bit S. A Pre-Determined Node Deployment Strategy to Prolong Network Lifetime in Wireless Sensor Network[J]. Comput Commun,2011,34(11):1294-1306.

[5] Huang R,Song W Z,Xu M,et al. Real-World Sensor Network for Long-Term Volcano Monitoring:Design and Findings[J]. IEEE Trans Parallel Distrib Syst,2011,23(2):321-329.

[6] Shu T,Krunz M,Vrudhula S. Power Balanced Coverage-Time Optimization for Clustered Wireless Sensor Networks[C]//Proc ACM Mobi Hoc,2015:111-120.

[7] Shu T,Krunz M. Coverage-Time Optimization for Clustered Wireless Sensor Networks:A Power-Balancing Approach[J]. IEEE/ACM Trans Netw,2012,18(1):202-215.

[8] Darabkh K A. Performance Evaluation of Selective and Adaptive Heads Clustering Algorithms over Wireless Sensor Networks[J]. J Netw Comput Appl,2014,35(6):2068-2080.

[9] Li H. COCA:Constructing Optimal Clustering Architecture to Maximize Sensor Network Lifetime[J]. Comput Commun,2013,36(3):256-268.

[10] Stine J A. Exploiting Smart Antennas in Wireless Mesh Networks Using Contention Access[J]. IEEE Wireless Communication Mag,2016,13(2):38-49.

[11] Wang X,Tan M. A Load-Balancing Routing Algorithm for Multichannel Wireless Mesh Networks[J]. IJSNet,2015,17(4):249-255.

[12] Diab R. Chalhoub G,Misson M. Enhanced Multi-Channel MAC Protocol for Multi-Hop Wireless Sensor Networks[J]. IEEE Wireless Days,2014,5(6):34-41.

[13] Halder S,Das BitC S. Enhancement of Wireless Sensor Network Lifetime by Deploying Heterogeneous Nodes[J]. J Netw Comput Appl,2014,38(2):106-124.