陳 歡,沙 超,2,黃海平,王汝傳
(1.南京郵電大學 計算機學院,江蘇 南京 210003; 2.蘇州大學 江蘇省計算機信息處理技術(shù)重點實驗室,江蘇 蘇州 215006)
一種非均勻部署傳感網(wǎng)的能量空洞緩解方法
陳 歡1,沙 超1,2,黃海平1,王汝傳1
(1.南京郵電大學 計算機學院,江蘇 南京 210003; 2.蘇州大學 江蘇省計算機信息處理技術(shù)重點實驗室,江蘇 蘇州 215006)
在無線傳感網(wǎng)中,網(wǎng)絡(luò)中心附近的節(jié)點由于要負責全網(wǎng)數(shù)據(jù)的接收和轉(zhuǎn)發(fā),將會消耗更多能量,從而造成節(jié)點間能耗不均,產(chǎn)生“能量空洞問題”。為延長簇樹狀無線傳感網(wǎng)的網(wǎng)絡(luò)生命期并均衡網(wǎng)內(nèi)各節(jié)點能耗,提出了一種面向圓形傳感器網(wǎng)絡(luò)的能量空洞緩解方法。該方法將網(wǎng)絡(luò)劃分為虛擬的環(huán)狀結(jié)構(gòu)以滿足多跳數(shù)據(jù)傳輸?shù)囊?,感知?jié)點非均勻地分布在該圓形網(wǎng)絡(luò)中,內(nèi)環(huán)中的節(jié)點數(shù)總是多于外環(huán),以確保數(shù)據(jù)上傳過程中的能耗均衡性,各節(jié)點根據(jù)其鄰近節(jié)點的剩余能量和通信距離,選擇相鄰環(huán)內(nèi)的最優(yōu)節(jié)點作為父節(jié)點上傳數(shù)據(jù)。仿真實驗結(jié)果表明,與其他典型的能量空洞避免方法相比,所提出的方法有效延長了網(wǎng)絡(luò)生命期,在多跳傳感網(wǎng)中較好地實現(xiàn)了能耗均衡,有效地緩解了能量空洞的產(chǎn)生。
無線傳感網(wǎng);能量空洞;能耗均衡;非均勻部署
近年來,無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)成為研究熱點[1-3]。并且許多配備了無線傳感器網(wǎng)絡(luò)的消費產(chǎn)品已被部署在家庭網(wǎng)絡(luò)之中[4-5]。使用環(huán)形拓撲均勻分布節(jié)點的無線傳感器網(wǎng)絡(luò)通常是由一組傳感器節(jié)點和一個sink節(jié)點組成的,采用多對一的數(shù)據(jù)收集模式[6]。
然而,越靠近sink的節(jié)點攜帶越多的流量負載,導致更多的能量消耗。由于節(jié)點能量的有限供應(yīng),因此靠近sink布置的節(jié)點將比遠離sink布置的節(jié)點更快地耗盡自身能量。節(jié)點能量的不平衡消耗將會在sink周圍引起能量空洞(Energy Hole)現(xiàn)象[7-8]。能量空洞現(xiàn)象是指網(wǎng)絡(luò)中由于部分節(jié)點過早耗盡自身能量導致網(wǎng)絡(luò)原有覆蓋區(qū)域缺失或者數(shù)據(jù)無法送達sink的現(xiàn)象[9]。在能量空洞問題產(chǎn)生后,將會不再有數(shù)據(jù)發(fā)送給sink,從而使得網(wǎng)絡(luò)的生命周期過早結(jié)束。然而當分布在sink第一半徑范圍內(nèi)的節(jié)點耗盡了自身能量時,那些遠離sink的節(jié)點大部分初始能量還沒有被使用。Lian等[10]指出,無線傳感器網(wǎng)絡(luò)的生命周期在提前結(jié)束時,大約有90%的初始能量還沒有被使用。因此上述的能量空洞問題在無線傳感器網(wǎng)絡(luò)中已經(jīng)成為最顯著的問題之一[11-12]。
文獻[13]認為,在負載量大的節(jié)點周圍布置更多數(shù)量的節(jié)點可以減輕節(jié)點的負載量,從而緩解能量空洞的出現(xiàn)。與這個思路相同的是,吳小兵等[14]證明了無線傳感器網(wǎng)絡(luò)的能量均衡耗盡的不可能性,并提出了“次優(yōu)網(wǎng)絡(luò)能耗均衡”(Sub-balanced Energy Depletion)的概念,提出了一種非均勻的節(jié)點分布策略,用于實現(xiàn)網(wǎng)絡(luò)中的次平衡能量消耗,即從外環(huán)CR-1到內(nèi)環(huán)C1中的節(jié)點數(shù)量按照比率為q>1的幾何級增長,并且在最外環(huán)CR中有NR-1/(q-1)個節(jié)點,從而實現(xiàn)了網(wǎng)絡(luò)的次平衡能量消耗。其中,R為總環(huán)數(shù),Ni為環(huán)Ci中的節(jié)點數(shù)。然而在此策略中,節(jié)點在相鄰環(huán)中選擇數(shù)據(jù)傳輸方式時,未定義明確的標準,且環(huán)間節(jié)點選擇具有隨機性,使得節(jié)點消耗不平衡,仍會造成能量空洞的出現(xiàn)。
在文獻[14]的基礎(chǔ)上,利用功率自適應(yīng)機制,對節(jié)點的傳輸半徑進行動態(tài)調(diào)節(jié),以降低其多跳通信的能耗開銷。同時,設(shè)計實現(xiàn)了環(huán)間節(jié)點協(xié)同數(shù)據(jù)上傳方案,降低了簇樹狀傳感網(wǎng)“多對一”數(shù)據(jù)上傳過程中出現(xiàn)“近中心負載過高”現(xiàn)象的可能性,有效緩解了能量空洞問題。實驗結(jié)果表明,網(wǎng)絡(luò)運行結(jié)束后,各節(jié)點剩余能量均小于自身初始能量的8%,體現(xiàn)出了較好的能耗均衡性,且節(jié)點剩余能量的下降速度小于所對比的網(wǎng)絡(luò)模型,網(wǎng)絡(luò)生命期得到了有效延長。
1.1 節(jié)點能耗模型
不失一般性,采用同文獻[15]相同的節(jié)點能耗模型。節(jié)點發(fā)送數(shù)據(jù)時,其功率損耗如式(1)所示:
Etx(k,d)=kEelec+kεampd2
(1)
在接收數(shù)據(jù)時,節(jié)點功率損耗如式(2)所示:
Erx(k)=kEelec
(2)
其中,Etx、Erx分別為發(fā)送、接收數(shù)據(jù)損耗的功率;k為數(shù)據(jù)比特數(shù);d為接收端和發(fā)射端之間的通信距離;Eelec為發(fā)送或接收單位比特數(shù)據(jù)電路損耗的功耗系數(shù);εamp為功率放大電路的放大系數(shù)。
由式(1)和式(2)可知,一個節(jié)點發(fā)送單位比特的數(shù)據(jù)量所耗費的能量要大于接收單位比特的數(shù)據(jù)量。這主要是由于發(fā)射數(shù)據(jù)損耗功率是與發(fā)射端和接收端的距離有直接關(guān)系的。而且在通信距離較大時,Etx隨d的變化會產(chǎn)生巨增。若此時采用單跳直接傳輸數(shù)據(jù)的策略,反而會增加節(jié)點的能量消耗,而采用多跳數(shù)據(jù)上傳方案則可將負載均衡到網(wǎng)絡(luò)中其他節(jié)點,有利于均衡能耗,推遲能量空洞現(xiàn)象的產(chǎn)生。因此,重點針對多跳傳輸下的簇樹狀無線傳感網(wǎng)的能量效率問題進行研究。
1.2 網(wǎng)絡(luò)模型
假設(shè)網(wǎng)絡(luò)中所有的節(jié)點分布在一個半徑為R的圓形區(qū)域中。網(wǎng)絡(luò)中只有唯一的sink節(jié)點,且置于圓心處。令網(wǎng)絡(luò)中有n個感知節(jié)點,定義其標號為Aj(j=1,2,…,n)。該圓形區(qū)域使用以sink為原點的直角坐標系,故以A0(0,0)表示sink的位置。為便于選擇最優(yōu)父節(jié)點,進一步將網(wǎng)絡(luò)劃分為N(N>1)個寬度均為dw的虛擬環(huán)狀區(qū)域,從內(nèi)環(huán)向外環(huán)依次使用Ci(i=1,2,…,N)表示第i個圓環(huán)。節(jié)點在各環(huán)中均勻部署[14]。
由文獻[14]可知,圓環(huán)CN-1到圓環(huán)C1內(nèi)的節(jié)點數(shù)目以等比系數(shù)q(q>1)遞增。而圓環(huán)CN和CN-1中的節(jié)點數(shù)目之比為1/(q-1),即:
(3)
令所有節(jié)點一經(jīng)部署后便不能移動,其初始能量均為E0且無法進行后續(xù)補充。
1.3 相關(guān)定義
定義1:最大通信傳輸距離dx。
處于圓環(huán)Ci(2
(a)最大通信傳輸距離dx (b)節(jié)點的最大考察區(qū)域
由定義1及圖1(a)易知:
(4)
而處于圓環(huán)Ci(i<2)內(nèi)的節(jié)點的最大通信傳輸距離dx,即為其與sink的最短距離。
(5)
定義2:節(jié)點最大考察區(qū)域B。
以處于圓環(huán)Ci(1
定義3:P代價。
P代價是處于圓環(huán)Ci(1
(6)
其中,djk表示節(jié)點Aj與考察區(qū)域B內(nèi)的節(jié)點Ak的距離;Ck表示節(jié)點Ak被選擇為后繼節(jié)點的次數(shù);α和β是常量,滿足α+β=1。
令節(jié)點工作一輪的時間單位為一個時間片T,節(jié)點在每個時間片內(nèi)分為三個階段:數(shù)據(jù)采集階段、數(shù)據(jù)發(fā)送階段和數(shù)據(jù)接收階段,其持續(xù)時間分別為t1、t2和t3。網(wǎng)絡(luò)中每個處于工作狀態(tài)的節(jié)點以相同的數(shù)據(jù)采集率采集數(shù)據(jù),并在這個時間片內(nèi)進行發(fā)送或者接收其他節(jié)點數(shù)據(jù)的工作。處于圓環(huán)Ci(i 2.1 最優(yōu)父節(jié)點選擇方法 節(jié)點分布策略采用文獻[14]的非均勻分布方案,其基本思想是在靠近sink的圓環(huán)布置較多的節(jié)點。因此對于某一圓環(huán)在其相鄰內(nèi)環(huán)選擇一個節(jié)點傳輸數(shù)據(jù)顯得尤為重要。這里,給出節(jié)點選擇其最優(yōu)下一跳父節(jié)點的方法。 (1)網(wǎng)絡(luò)中的各節(jié)點,根據(jù)1.3節(jié)的定義,構(gòu)建其各自的最大考察區(qū)域。由于已令各環(huán)的寬度均相等,故該最大考察區(qū)域B的面積將主要取決于節(jié)點在環(huán)中的位置及環(huán)的寬度值dw。在節(jié)點部署密度ρ一定的情況下,該面積大小將直接決定可供選擇的下一跳父節(jié)點個數(shù)。 (2)位于最外環(huán)中的節(jié)點,對于其所構(gòu)建的B區(qū)域中的各節(jié)點,分別根據(jù)式(6)計算其P值,并從中選取P值最大的一個節(jié)點作為其下一跳父節(jié)點,向其發(fā)送一個包含自身ID和位置信息的消息包。 (3)若當前節(jié)點的B區(qū)域中無可供選擇的父節(jié)點,則其選擇距離其最近的一個同層節(jié)點,作為其父節(jié)點。 (4)當最外層節(jié)點均完成父節(jié)點的選擇后,位于次外環(huán)的各節(jié)點按照上述方式,從第N-2環(huán)中(或從與其位于同一環(huán)的兄弟節(jié)點中)選擇P值最大的節(jié)點,作為其父節(jié)點,并以此類推,最終構(gòu)建一個以網(wǎng)絡(luò)中心sink為根,以虛擬圓環(huán)和B區(qū)域為約束條件的簇樹狀數(shù)據(jù)收集結(jié)構(gòu)。 2.2 緩解能量空洞的環(huán)間數(shù)據(jù)上傳策略 如前所述,在簇樹狀無線傳感網(wǎng)中,若對于數(shù)據(jù)上傳時機不加限制,則很容易造成信道沖突、加重“近網(wǎng)絡(luò)中心”的負載,降低數(shù)據(jù)收集效率且產(chǎn)生能量空洞。為此,在2.1節(jié)所選取的最優(yōu)父節(jié)點基礎(chǔ)上,進一步給出提升能耗均衡性的環(huán)間數(shù)據(jù)上傳策略。 在時間片開始后,各虛擬圓環(huán)內(nèi)的節(jié)點首先都以相同的數(shù)據(jù)采集率在t1時間內(nèi)采集數(shù)據(jù)。數(shù)據(jù)采集結(jié)束后,位于圓環(huán)Ci(i=N,N-2,N-4…)內(nèi)的各節(jié)點首先向其父節(jié)點發(fā)送數(shù)據(jù),持續(xù)時間為t2,如圖2(a)所示。此時,位于第Ci-1環(huán)內(nèi)的節(jié)點將存在兩種可能: (1)若該節(jié)點存在子節(jié)點,則其將進入接收模式,等待來自于其Ci環(huán)中子節(jié)點的數(shù)據(jù)。 (2)若該節(jié)點無子節(jié)點,則其將處于休眠狀態(tài),以節(jié)約能量。 在t2時間片結(jié)束后,由位于圓環(huán)Ci-1內(nèi)的節(jié)點向其父節(jié)點發(fā)送數(shù)據(jù),此時,位于圓環(huán)Ci-2內(nèi)的父節(jié)點將處于接收狀態(tài)。若該父節(jié)點無子節(jié)點,則處于休眠狀態(tài)以節(jié)約能量,如圖2(b)所示。 (a)Ci環(huán)節(jié)點向父節(jié)點發(fā)數(shù)據(jù) (b)Ci-1環(huán)節(jié)點向父節(jié)點發(fā)數(shù)據(jù) 為驗證算法性能,在Matlab2013中進行實驗,參數(shù)如表1所示。 表1 仿真參數(shù)值 不失一般性,這里認為,當網(wǎng)絡(luò)中出現(xiàn)第一個死亡節(jié)點時,網(wǎng)絡(luò)便停止運行。在網(wǎng)絡(luò)生命期、各節(jié)點剩余能量方差、網(wǎng)內(nèi)節(jié)點剩余能量綜合等三方面,同文獻[14]中提出的環(huán)狀網(wǎng)絡(luò)節(jié)點非均勻分布下的能量空洞避免方法進行比較。能耗分析采用文獻[15]中所提出的傳感網(wǎng)能量消耗模型。 當網(wǎng)絡(luò)生命期結(jié)束時,網(wǎng)內(nèi)各節(jié)點剩余能量如圖3所示。所采用的圓形網(wǎng)絡(luò)中非均勻部署了50個節(jié)點。 圖3 網(wǎng)絡(luò)中節(jié)點剩余能量 由圖3可知,在網(wǎng)絡(luò)停止運行時,各節(jié)點的剩余能量都未超過1.5 J,即各節(jié)點剩余能量均小于自身初始能量的8%,體現(xiàn)了較好的能耗均衡性。 表2為在環(huán)內(nèi)部署不同數(shù)量節(jié)點后的節(jié)點剩余能量標準差、網(wǎng)絡(luò)生命期和數(shù)據(jù)吞吐量。 表2 不同部署情況下節(jié)點的能量效率比較 由表2可知,采用的方法對于不同部署模式下的適應(yīng)性較強,其能耗均衡性和網(wǎng)絡(luò)生命期的實驗效果均較好。而在NumN=10,q=1.3這個方案部署下,網(wǎng)絡(luò)的能效性能最好,可最大限度地緩解能量空洞現(xiàn)象的產(chǎn)生。 圖4為所提出的非均勻部署網(wǎng)絡(luò)下的能量空洞緩解方法(Energy Hole Mitigation Strategy for non-uniform deployed sensor networks,EHMS)同節(jié)點非均勻分布的能量空洞避免方法(Avoiding Energy Holes in sensor networks with non-uniform node distribution,AEH)[14]在節(jié)點剩余能量之和方面的實驗結(jié)果。 圖4 節(jié)點剩余能量之和的變化比較 由圖4可知,在網(wǎng)絡(luò)運行時間內(nèi),由于EHMS方法中的各節(jié)點均在t1、t2和t3時間段內(nèi)均衡地消耗能量,故其剩余能量總和隨著網(wǎng)絡(luò)的運行,基本呈線性下降的趨勢。AEH方法也采用環(huán)狀的非均勻部署方式,以均衡網(wǎng)絡(luò)能耗,故在網(wǎng)絡(luò)運行前期,其網(wǎng)內(nèi)節(jié)點剩余能量的下降趨勢和EHMS方法基本一致。但其僅考慮到了相鄰圓環(huán)間的節(jié)點分布情況,未能夠進一步對父節(jié)點的選擇做出必要約束。節(jié)點每次僅選擇剩余能量最多的節(jié)點作為其下一跳父節(jié)點,未考慮跳距和環(huán)數(shù)的影響。故在網(wǎng)路運行后期,其網(wǎng)內(nèi)節(jié)點剩余能量之和略低于EHMS方法。而在1 600~1 800 s之間,AEH方法的節(jié)點剩余能量總和未發(fā)生變化,說明此時該網(wǎng)絡(luò)已經(jīng)停止工作。即EHMS方法的網(wǎng)絡(luò)生命期相對較長。 圖5是節(jié)點剩余能量方差隨網(wǎng)絡(luò)運行時間變化的比較曲線。 圖5 節(jié)點剩余能量方差的變化比較 由圖5可知,在網(wǎng)絡(luò)運行初期,兩種方法的節(jié)點剩余能量方差均較小,體現(xiàn)出了較好的能耗均衡性。然而,隨著網(wǎng)絡(luò)的運行,盡管兩種方法下的方差均可有效地控制在0.35 J2以內(nèi),但EHMS方法的能耗均衡性相對更好一些。這是由于該方法采用了環(huán)間數(shù)據(jù)交替上傳的策略,在避免傳輸沖突的同時,有效保存了環(huán)內(nèi)各節(jié)點的能量,可進一步推遲能量空洞的產(chǎn)生。 以緩解能量空洞出現(xiàn)為目標,在非均勻部署的無線傳感網(wǎng)中,提出了一種選擇最優(yōu)父節(jié)點開展層間數(shù)據(jù)上傳的方案。同時考慮到了后繼父節(jié)點的剩余能量、相鄰層間節(jié)點的通信距離及環(huán)內(nèi)節(jié)點密度等因素。與典型的非均勻無線傳感網(wǎng)數(shù)據(jù)收集方式相比,該方案在實現(xiàn)能耗均衡性的同時,較為有效地緩解了能量空洞的產(chǎn)生,延長了網(wǎng)絡(luò)生命期。 [1] 劉 唐,彭 艦,陳 果,等.基于密度控制的傳感器網(wǎng)絡(luò)能量空洞避免策略[J].計算機學報,2016,39(5):993-1006. [2] 張 樂,李 棟,崔 莉.一種針對移動全覆蓋問題的節(jié)點移動策略[J].計算機研究與發(fā)展,2013,50(5):901-911. [3] 田賢忠,陽 勝.基于網(wǎng)絡(luò)編碼的無線傳感器網(wǎng)絡(luò)瓶頸區(qū)域生存時間優(yōu)化策略[J].計算機學報,2016,39(5):1039-1050. [4] Wang J,Yin Y,Zhang J,et al.Mobility based energy efficient and multi-sink algorithms for consumer home networks[J].IEEE Transactions on Consumer Electronics,2013,59(1):77-84. [5] Bellido-Outeirino F J,Flores-Arias J M,Linan-Reyes M,et al.Wireless sensor network and stochastic models for household power management[J].IEEE Transactions on Consumer Electronics,2013,59(3):483-491. [6] 夏先進,李士寧,張 羽,等.一維傳感網(wǎng)中混合數(shù)據(jù)傳輸?shù)哪芰烤鈁J].軟件學報,2015,26(8):1983-2006. [7] 唐冰清,張玲華.GEAR協(xié)議中貪婪算法及查詢消息傳播優(yōu)化方法[J].計算機技術(shù)與發(fā)展,2013,23(1):135-138. [8] 曾志文,陳志剛,劉安豐.無線傳感器網(wǎng)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J].計算機學報,2010,33(1):12-22. [9] 李繼樓,柯家龍.基于壓縮感知的WSN數(shù)據(jù)壓縮與重構(gòu)[J].計算機技術(shù)與發(fā)展,2015,25(9):111-114. [10] Lian J,Naik K,Agnew G B.Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J].International Journal of Distributed Sensor Networks,2006,2(2):121-145. [11] 劉安豐,任 炬,徐 娟,等.異構(gòu)傳感器網(wǎng)絡(luò)能量空洞分析與避免研究[J].軟件學報,2012,23(9):2438-2448. [12] 張 琪,管有慶.基于網(wǎng)絡(luò)編碼的無線傳感網(wǎng)絡(luò)自適應(yīng)數(shù)據(jù)聚集[J].計算機技術(shù)與發(fā)展,2015,25(10):123-126. [13] Ferng H W,Hadiputro M S,Kurniawan A.Design of novel node distribution strategies in corona-based wireless sensor networks[J].IEEE Transactions on Mobile Computing,2011,10(9):1297-1311. [14] Wu X,Chen G,Das S K.Avoiding energy holes in wireless sensor networks with nonuniform node distribution[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(5):710-720. [15] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless micro-sensor networks[C]//Proceedings of the 33rd annual Hawaii international conference on system sciences.[s.l.]:IEEE,2000:1-10. A Type of Energy Hole Mitigation Strategy for Non-uniform Deployed Sensor Networks CHEN Huan1,SHA Chao1,2,HUANG Hai-ping1,WANG Ru-chuan1 (1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China; 2.Key Laboratory for Computer Information Processing Technology of Jiangsu Province, Soochow University,Suzhou 215006,China) In Wireless Sensor Networks (WSN),nodes near the center tend to consume more energy as they are responsible for receiving and forwarding data from the whole network,which leads to a non-uniform energy consumption among nodes,that is so called the “energy hole problem”.To prolong network lifetime and balance energy consumption in the cluster-tree based sensor network,a type of energy hole mitigation strategy in a circular network has been proposed.Network has been divided into several virtual annuluses for multi-hop transmission and nodes have been non-uniformly deployed in it.Moreover,for balancing energy consumption on data uploading,the number of nodes in the inner annulus is more than that in the outer one.According to the residual energy and the communication distance of its neighbor,each node has chosen an optimal parent in the adjacent annulus for data uploading.Simulation results have shown that this method could effectively prolong network lifetime by comparing with other energy hole avoidance algorithms and has also performed well on balancing energy consumption in the multi-hop transmission network and could effectively mitigate the energy hole problem. wireless sensor networks;energy hole;balance of energy consumption;non-uniform deployment 2016-07-05 2016-10-13 網(wǎng)絡(luò)出版時間:2017-04-28 國家自然科學基金資助項目(61572260);江蘇省自然科學優(yōu)秀青年基金(BK20160089);江蘇省普通高校研究生培養(yǎng)創(chuàng)新工程(SJLX15_0382,SJLX15_0383,KYLX15_0842);江蘇省計算機信息處理技術(shù)重點實驗室開放課題(KJS1327) 陳 歡(1991-),男,碩士研究生,研究方向為無線傳感網(wǎng)能量空洞緩解技術(shù);沙 超,副教授,碩士生導師,通信作者,研究方向為無線傳感網(wǎng)能耗均衡技術(shù);黃海平,教授,碩士生導師,研究方向為物聯(lián)網(wǎng)隱私保護技術(shù);王汝傳,教授,博士生導師,研究方向為物聯(lián)網(wǎng)信息處理技術(shù)。 http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1703.042.html TP393 A 1673-629X(2017)06-022-05 10.3969/j.issn.1673-629X.2017.06.052 環(huán)間數(shù)據(jù)上傳模式
3 實驗及結(jié)果分析
4 結(jié)束語