基于阿基米德螺旋的WSNs節點部署的能耗均衡算法*

郝小會,申玉霞,趙冬玲

(濟源職業技術學院,河南 濟源 459000)

無線傳感網絡WSNs(Wireless Sensor Netorks)[1]已廣泛應用于各個領域,如環境、工業。然而WSNs遭受了較多不可避免的問題,如資源受限、隨機部署。特別是節點能量受限問題。因此,在設計WSNs時應重點關注網絡能量,進而最大化網絡壽命[2-3]。

而網絡內能量消耗率取決于節點的部署特性,而部署特性主要取決于應用環境。目前,有兩類節點部署方案:隨機部署和確定性部署[4]。隨機部署常應用于物理環境難以接入的區域,如火山,地震區域等,常用直升飛機向這些區域散落節點[4-5]。而確定性部署是常應用于物理空間可接入的環境,如目標跟蹤、城區監測。而在這些環境中,常通過人工部署節點[4]。

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

盡管簇技術在保存能量方面具有一定優勢,但是若僅依靠簇技術是難以避免能量空洞問題。一旦發生遭遇能量空洞問題,網絡壽命將受到影響。為此,研究人員從節點部署角度入手,并結合簇技術,避免能量空洞問題。

為此,本文首先分析能耗均衡在延長網絡壽命方面的性能,并發現每一層的簇數以及簇成員數對網絡壽命有重要的影響。然后,再提出基于阿基米德螺旋(Archimedes spiral)的節點部署方案AS-DBEC,通過有效地部署節點,提高了能量利用率,最終延長了網絡壽命。實驗結果表明,AS-DBEC方案在保存能量和網絡壽命方面具有一定的優勢。

1 系統模型

1.1 網絡模型

考慮a×a方形的網絡區域,且其由一系列的電暈覆蓋[6-7]構成,如圖1所示。假定信宿位于網絡區域中心,并由信宿負責從傳感節點收集數據。而傳感節點以隨機方式分布于不同層內。

圖1 網絡模型

整個網絡劃分為N層。因此,網絡內存在N個簇。據此,離信宿最近的簇位于第1層Layer-1(第1類),而離信宿最遠的簇位于第N層Layer-N(第N類)。最后,假定在第i層的節點有j個簇(j>1)。

假定網絡為靜態的異構網絡,同時依據文獻[8]將網絡內所有節點劃分許多簇,其中異構性是指節點的功能和電池容量的不同。所謂功能上的異構是指網絡內節點為兩類:成員節點MNs(非簇頭節點)和簇頭CHs。而在電池容量方面,MNs具有有限的電量,而CHs裝備了更充足的電量。不失一般性,假定CHs位于它的簇中心[7]。

1.2 感測和通信模型

如果區域內的每個節點至少有一個活動MN覆蓋[4],則認為此區域被覆蓋。節點MN的感測區域半徑為Rs。而通信半徑為Rc。假定如果兩個節點的歐式距離不超過Rc,則它們能直接交互消息。

1.3 能量模型

考慮文獻[9]的一級無線電模型作為能量模型,其中節點能量主要由無線傳輸和接收方面上進行消耗。因此,忽略其他能耗因素。

在傳輸范圍Rc內,傳輸n比特數據所消耗的能量etr(n,Rc)可表示為:

(1)

式中:et表示傳輸一比特數據所消耗的能量。相反,接收n比特數據所消耗的能量ere(n):

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

(2)

式中:eelec=er,其表示接收一比特數據所消耗的能量。

最后,融合n比特數據所消耗的能量eda(n)可表示為:

eda(n)=ea×n

(3)

式中:ea表示融合一比特數據所消耗的能量。

1.4 信道傳播模型

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

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

(4)

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

1.5 網絡壽命

本文規定,網絡壽命是指從節點部署開始直至失效節點的比例超過一定門限值的時間[10]。當失效節點超過一定比例后,就無法提供網絡覆蓋和連通。所謂失效節點是指節點剩余能量少于預定值,且不能傳輸任何數據或接收任何數據。

2 問題描述

平衡能量消耗有利于網絡壽命的提高。所謂平衡能量消耗是指網絡內所有節點的能耗速度相同或相近。而本節的目的就是通過推導說明:可通過部署節點,平衡節點間的能量消耗。為后續的節點部署策略提供理論依據。

(5)

類似地,Layer-N層的第j個CH所消耗的能量ENj:

(6)

(7)

令eti表示為從Layer-i層第j個CH傳輸一比特數據 至Layer-(i-1)層第j個CH所消耗的能量,式(6)可以重寫:

(8)

依據網絡模型,處于Layer-i、Layer-(i-1)的兩CH間的距離li:

(9)

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

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

(10)

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

(11)

依據式(11)可得:

(12)

依據最短路徑協議,每條路徑含有的最大鏈路數為N。因此,為了產生對路徑可靠性的限制,即最小鏈路可靠值δp:

(13)

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

(14)

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

(15)

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

(16)

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

(18)

式(18)第1個約束項保證簇間流量;第2個約束項限制了在網絡內規定時間所有MNs產生的數據是常數。而式(18)的第3個約束項保證了MNs和CHs的數量為非負數。

每一層的簇數以及每個簇的MNs數可通過優化問題進行解決。然而,每一層的單一CHs可能仍保持不平衡,并且這種不平衡也會產生能量空洞問題。消除能量不平衡問題的有效方式之一就是以預定位置部署MN和CH[4]。

文獻[13]分析了消除能量空洞問題的研究工作。這些預定節點部署方案顯示了在端到端時延、吞吐量、數據包丟失率方面均有重要的提高。

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

3 部署策略AS-DBEC

3.1 部署階段

3.1.1 基于阿基米德螺旋的節點部署

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

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

圖2 基于阿基米德螺旋的節點分布

3.1.2 基于離散的阿基米德螺旋的節點部署

由于阿基米德螺旋是連續曲線,將它作為部署節點的函數。為此,將此連續曲線轉換為離散形式,致使節點就部署于這些離散位置上。

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

f(θk)=θkB

(19)

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

式(19)中:k表示CT,而θk表示由第k個CT所覆蓋的總角度。接下來,在每個CT內位置被指定的范圍內,這些離散點需要被識別,進而才能部署傳感節點。

據此,將θk分解為m個離散位置,再在每個離散位置上部署節點。θk的分解如式(20)所示。

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

(20)

式中:k=1,…,K。且對于每個k,m=1,…,2π/φk。

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

AS-DBEC算法的目的就是將阿基米德螺旋作為節點部署函數,致使它能近似地代表分層的網絡區域(如圖1所示)。為了實現這個目的,將分層的網絡區域的Layer-i分解為多個子區域ωi×ωi,其中ωi=ri-ri-1。

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

圖3 部署CHs和MNs示意圖

3.2 簇建立階段

由于一層有多個簇,而任意層內的MNs數以及部署位置均為已知,因此,無需單獨算法去產生CH。

依據阿基米德螺旋部署方案,部署了CH和MNs節點后,就形成了簇。形成簇的偽代碼如表1所示。

表1 部署節點的偽代碼

圖3顯示了大型網絡區域由多個圓區域構成示意圖。在每個子區域內,就依據式(12)和式(13)部署MN和CH。

許多現實生活應用,如火山監測和精細農業。這些應用都是利用直升飛機[5]或空中機器人按預定位置部署節點。考慮這些因素,提出的基于Archimedes spiral 部署節點算法是可行的,也具有一定的應用前景。

3.3 數據傳輸過程

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

顯然,相比MN,CH承擔了更多的數據壓力。因此,CH的能量消耗速度更快。此外,CH在維護網絡連通方面的角色比MN更重要。為此,本文著力關注CHs的能耗。

假定CH以最短路徑向信宿傳輸數據。具體而言,處于Layer-i的CH從處于Layer-(i-1)層選擇下一跳節點。為了保證最短路徑,就選擇離自己最近的節點作為轉發節點。同樣,處于Layer-(i-1)層的CH再從Layer-(i-2)層選擇下一跳轉發節點。此過程一重復,直到將數據傳輸至信宿。

4 性能仿真

4.1 仿真環境

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

表2 仿真參數

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

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

在仿真中,在實施EBCA時,與文獻[7]類似,考慮均勻的圓形簇,且簇頭部署于簇內中心,而MNs圍繞簇頭隨機分布,仿真過程中,在5層內隨機部署30個節點;在10層內,隨機部署65個節點。而在部署SHCS方案時,考慮均勻的方形簇,且簇頭位于方形區域中心,而MNs圍繞CH,并按確定性部署,且形成網格拓撲,總。此外,AS-DBEC、EBCA和SHCS算法所考慮的網絡模型為基于Corona的網絡模型,如圖1所示。

圖4 能量均衡

4.2 數據分析

首先分析算法的能量均衡性能,實驗數據如圖4所示,其中圖4(a)為5層網絡結構、4(b)為10層網絡結構。

首先,將圖4(a)和圖4(b)相比發現,網絡層數的增加,提高了能量消耗。例如,在5層網絡結構內,AS-DBEC算法的ECR per CH為62.48 μJ/s,而當網絡結構達到10層時,AS-DBEC算法的ECR per CH為84.29 μJ/s。原因在于:網絡尺寸的增加,提高了數據流量,導致了能耗的增加。

然后,在給定網絡層次環境下,AS-DBEC算法的ECR per CH 隨層數接收直線。這說明簇技術能夠有效地均衡能量。而EBCA和SHCS算法的ECR per CH隨層次數的增加,呈下降趨勢。注意到,在Layer-1時,ECR per CH最大。這也說明離信宿最近的CH承擔了更多數據轉發任務。與EBCA和SHCS算法,提出的AS-DBEC算法的ECR per CH得到有效控制,且曲線平穩,這說明AS-DBEC算法在均衡CH的能耗具有較大的優勢。

接下來,分析AS-DBEC算法的網絡壽命,實驗數據如圖5所示,其中圖5(a)為5層網絡結構、圖5(b)為10層網絡結構。

圖5 網絡壽命

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

5 總結

本文針對無線傳感網絡的能耗問題,先分析了均衡能耗對網絡壽命的影響,然后提出阿基米德螺旋的節點部署策略AS-DBEC。將阿基米德螺旋作為部署函數,并進行離散化,最后通過這些離散位置部署節點。實驗結果表明,與同類算法相比,提出的AS-DBEC算法能夠均衡簇頭間的能耗,延長網絡壽命。

[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]. 傳感技術學報,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.