一種可分負載WSN的能耗均衡負載調度算法*

劉端陽,暴占兵,程　珍

(浙江工業大學計算機科學與技術學院,杭州 310023)

微電子、計算機和無線通信等技術的進步,推動了無線傳感器網絡WSN(Wireless Sensor Network)的快速發展。WSN被廣泛應用于軍事偵察、環境監測等任務[1-2]。在這些應用中,大量無線傳感器節點隨機部署于被監測區域,各節點以自組織的形式協同工作,共同完成監測任務。由于無線傳感器節點的電源能量有限,為延長網絡的生存周期,WSN能耗均衡已成為近年來的研究熱點之一。

WSN能耗均衡的設計與實現可以貫穿于網絡的各個層次,比如,硬件層單個節點結構的設計[3],網絡層路由協議的設計[4-7]和應用層數據融合算法的設計[8]等。但是,應用層的負載調度更有利于WSN設計者系統地把握網絡的整體能耗特征[9-10],從而更有利于WSN的能耗均衡。因此,重點將研究WSN應用層的能耗均衡負載調度算法。

可分負載是一種特殊負載,它可以被分割成任意大小,且每一部分可以各自獨立執行,沒有執行次序限制。由于可分負載的典型性,它在許多科學和工程領域得到了廣泛應用,如信號、傳感器和工程實驗等數據處理,數據密集型計算和數據并行計算等,并形成了比較系統的可分負載理論[11]DLT(Divisible Load Theory)。而且,可分負載也可以廣泛應用于WSN領域,例如,在信號檢測WSN中,單個節點的負載可以定義為任意一部分頻率和方向范圍,因為被檢測信號的頻率和方向范圍是可以任意分割的,沒有執行次序限制[12]。可分負載應用在WSN上的優點在于其可以同時描述感知時間與傳輸時間對負載完成時間的影響。重要的是,可分負載調度一般可以得到解析解,不需要采用啟發式算法進行迭代,這就避免了迭代時間過長或迭代不收斂等情況,從而實現了調度結果的最優[13]。因此,論文將針對可分負載,研究WSN應用層的能耗均衡負載調度問題。

迄今為止,有許多學者研究了WSN可分負載調度,其中文獻[12]提出了星型WSN中不同工作模型下的可分負載調度算法。文獻[13]提出了基于異構群WSN模型的可分負載調度算法。文獻[14-19]等也對可分負載調度進行了研究。但是,以上研究采用的方法均是最短時間調度,即以完成任務的時間最短為負載調度目標,通過這種調度方法以減少整個網絡的總能耗,延長網絡的生存周期。目前,很少有學者研究基于能耗均衡的可分負載調度,但網絡能耗均衡比網絡能耗最小更有利于延長網絡的生存周期。因為網絡能耗最小會增加個別節點的能量消耗,并導致這些節點過早失效,從而使整個網絡的性能下降甚至失效。所以,本文針對可分負載WSN的能耗均衡問題,以常用可分負載調度模型為基礎,設計了一種可分負載WSN的能耗均衡負載調度算法DLEBS(Energy Balance Schedule for Divisible Load),并通過仿真實驗驗證了算法的有效性。

內容安排:第1節說明問題模型;第2節討論算法中用到的兩個重要時間點;整個算法的流程在第3節給出,重點講解算法的3個基本過程;第4節是仿真實驗及分析;第5節進行總結。

1　問題模型

1.1　研究模型及使用符號

論文研究的模型為星型WSN,如圖1。整個網絡由一個Sink節點和n個同構的無線傳感器節點組成。Sink節點負責總負載的調度,并完成感知數據的回收等任務,其本身不擔任感知任務。其余節點負責接收由Sink發出的命令,并完成相應的感知和傳輸數據等任務。在模型中,假設包括Sink在內的所有節點都是沒有前端通信協處理器的節點,即對于單個節點來講,不可以同時進行感知與傳輸任務。由于網絡中只存在Sink與其他節點之間的通信,所以網絡中同時僅可以存在一個通信活動。這就要求各節點傳輸數據時按照一定的時間順序進行。為簡化模型,不考慮傳輸和感知延遲對各節點工作時序的影響。由于接收的命令通常是一個負載量的說明,所以接收時間較短、負載較小,對于接收命令的能耗也不予考慮。網絡工作時,當Sink向所有節點發完調度命令后各節點才同時開始感知數據。該模型、假設與文獻[12]的第1個模型類似。進一步地,假設網絡中傳感器節點具有正常工作模式與Idle模式,并且在Idle模式的能耗相比工作模式可以忽略不計。由于各節點工作模式之間轉換次數較少,所以不考慮工作模式之間轉換的能耗與延遲。因此論文重點研究各節點的感知負載能耗與傳輸負載能耗。這樣就有一個比例特性,即各節點的能耗大小與其所處理的負載量成正比。DLEBS將充分利用這一性質來計算各節點的負載分配量。對于網絡中節點的分布,假設隨著與Sink的距離增加,在該距離附近的節點數也相應地增加。

圖1　星型網絡模型

除特殊說明外,文中將使用如下符號:

n:網絡中傳感器節點的總數;

ni:節點i(i=1,2,3,…,n);按照各節點與Sink的距離進行編號,距離近的編號小,反之,編號大;

di:ni與Sink的距離,單位為m;

αi:ni的負載量,單位為load;

yi:ni的感知速度倒數,單位為s/load。由于網絡中節點是同構的,所以簡記為y;

zi:ni的傳輸速度倒數,單位為s/load。簡記為z,理由同上;

圖2　wait_1i和wait_2i含義示意圖

wait_1i:在順序返回數據的過程中,ni(i=1,2,3,…,n)感知任務完成后等待其前一個節點傳輸結束時所用的時間。如圖2所示的3節點網絡,節點向Sink回傳數據的順序為(n3,n2,n1),wait_12即為n2在感知任務完成后等待n3傳輸結束時所用的時間;

wait_2i:在順序返回數據的過程中,ni(i=1,2,3,…,n)傳輸任務完成后等待其后一個節點開始傳輸時所用的時間;如圖2所示的3節點網絡,wait_22即為n2在傳輸任務完成后等待n1開始傳輸時所用的時間;

timei[1:m]:ni的前m(m=1,2,3,4)個時序段和。從圖2中n2的時序段可以看出,一個節點的工作時序可分為感知時間段,wait_1,傳輸時間段及wait_2。比如,time2[1:2]表示n2的感知時間段與wait_12的和;

Tse:網絡的負載感知強度。即當感知速度為單位1時,完成總感知任務所需時間;

Ttx:網絡的負載傳輸強度。即當傳輸速度為單位1時,完成總傳輸任務所需時間;

Ti:ni完成傳輸時所耗的總時間,Ti=timei[1:3];

Tf:網絡完成負載的總時間,Tf=max(T1,T2,T3,…,Tn);

Tgiven:網絡的給定完成時間;

Ei:ni完成所分配負載時的能耗;

ESi:ni感知單位負載的能耗;

ETi:ni傳輸單位負載的能耗;論文選擇WSN節點常用負載能耗模型[3]:

(1)

ESi=ES-eleci

(2)

其中ET-eleci,ES-eleci,εampi分別表示ni處理單位負載的傳輸電路能耗,感知電路能耗及放大電路能耗。同構節點中各節點的以上參數是相同的。所以式(1)和式(2)簡記為:

(3)

ESi=ES-elec

(4)

則Ei可以表示為:

(5)

其中:A=ET-elec+ES-elec,B=εamp均為常量。

node[i:j]:ni到nj的集合;

L[i:j]:節點集合node[i:j]所分配的負載總和;

L:總負載。

1.2　優化目標及約束條件

論文用網絡中各節點的能耗標準差表示網絡的能耗不均衡程度,能耗標準差越小,則說明能耗越均衡。

優化目標函數:

(6)

約束條件:

(1)Tf≤Tgiven,限定了在給定時間內處理負載;

(2)timej[1:3]≤timek[1:2],對于先后順序傳輸數據的nj和nk,nj表示先傳輸數據的節點,nk表示后一個節點,nk要等待nj傳輸完畢后才可以傳輸。限定了在單信道情況下同時只有一個節點可以與Sink通信;

2　兩個重要時間點

能耗均衡問題的研究需要權衡給定完成時間Tgiven與能耗均衡之間的關系。概括地講,如果給定完成時間Tgiven特別短,則不可能完成負載,談Eσ便沒有意義;另一方面,如果Tgiven足夠長,則一定可以找到一種能耗完全均衡(即Eσ=0)的負載調度策略。因為可以按照各節點距Sink的遠近來分配不同的負載量,使得各節點的能耗完全相同而不用考慮傳輸時間上的時序安排。因此,兩個時間點比較重要,一個是完成負載的最短時間(Tmin),另一個是能耗完全均衡條件下的最短完成時間(Tmin-e)。如果Tgiven

圖3　Tmin情況時序示意圖

2.1　完成負載的最短時間Tmin

如果每個節點負載分配恰當,使得WSN的工作時序如圖3所示,整個網絡完成負載的時間會最短,T1的值即為Tmin[12]。因為假如不按圖3來調度的話,則會出現如圖2所示的wait_1或wait_2時間間隔,這時可以通過適當調整各節點的負載處理量來消除這兩種時間間隔,充分利用網絡的并行處理能力,從而減少完成負載的總時間Tf。圖3中t0時刻前,Sink節點向各節點發送調度命令。在t0時刻,各節點同時開始感知數據。由于僅存在一個信道,所以各節點按照完成感知任務的先后順序依次返回數據到Sink節點。圖3中為距Sink近的節點分配的負載多,反之則少,稱之為順序最短時間負載調度SMTLS(Sequential Minimum Time Load Schedule)。另外,隨機分配圖3中各負載量到不同的節點,按照先完成感知任務先回傳數據的策略,整個網絡處理負載的總時間仍然與圖3相同,也為Tmin,稱這樣的負載調度為隨機最短時間負載調度RMTLS(Random Minimum Time Load Schedule)。顯然,SMTLS是RMTLS的一種特殊形式。

從圖3中可以得出:

α1yTse=α2yTse+α2zTtx
α2yTse=α3yTse+α3zTtx
?
αn-1yTse=αnyTse+αnzTtx

(7)

根據歸一化方法:

(8)

解上述式子得:

α1=(1-k)/(1-kn)

(9)

αi=kn-1α1

(10)

其中i=2,3,4,…,n,k=yTse/(yTse+zTtx)。

Tmin為T1的值:

Tmin=T1=(yTse+zTtx)α1

(11)

2.2　能耗完全均衡條件下的最短完成時間Tmin-e

能耗完全均衡時,能耗標準差(式(6))為零,各節點能耗相等:

(12)

根據式及能耗表達式(式(5))有:

(13)

按歸一化方法:

(14)

解上述式子得:

(15)

αi=(k1/ki)α1

(16)

因此,網絡按式(15)與式(16)所描述的負載調度策略來分配可以使各節點的能耗達到完全均衡。此時,能耗完全均衡條件下的最短完成時間Tmin-e:由式(15)和式(16)知距離Sink越遠則(k1/ki)越小,即節點分配的負載越少;所以,網絡按照(nn,n(n-1),n(n-2),…,n1)的順序返回感知數據可以使得完成時間最短,Tmin-e=T1。具體地,當nj(1≤j

圖4　Tmin-e情況時序示意圖

從上圖可以看出,WSN按能耗完全均衡的負載調度策略工作時,部分節點wait_1不為零,部分節點wait_2不為零,有的節點兩種時序均不為零,這與網絡中各節點的分布有關。根據圖4,各節點完成負載的時間:

Tn=(y+z)αn

(17)

(18)

其中i=1,2,3,…,n-1,式(17)和式(18)與遞歸求得的T1即為Tmin-e。

3　能耗均衡可分負載調度算法DLEBS

DLEBS分為兩階段:第1階段,DLEBS根據第2節的算法計算Tmin和Tmin-e。第2階段,比較Tgiven與Tmin、Tmin-e的關系,如果Tgiven

首先,對Eα的最小值進行分析:將優化目標式按能耗表達式(6)展開,

(19)

算法的設計思想是以能耗完全均衡負載調度(圖4,其能耗完全均衡但不滿足約束條件(1))為基礎,利用節點中不為零的wait_1和wait_2時間段以較小的能耗波動調整各節點負載量使整個網絡滿足所有約束條件。分為3個基本過程:其一,局部能耗均衡下的等比例縮小節點負載量,稱為等比例縮小過程;其二,局部能耗均衡下的等比例放大節點負載量,稱為等比例放大過程;其三,距離Sink較近的節點幫助較遠節點分擔負載量,稱為“幫助”過程。3個過程的共同特征是以符合約束條件(2)的時間順序為前提進行操作,其中等比例縮小過程是為了滿足約束條件(1),等比例放大過程與“幫助”過程是為了滿足約束條件(3)。

3.1　等比例縮小過程

3.2　等比例放大過程

等比例放大過程利用wait_2時間段增加負載處理量,以滿足約束條件(3)。由于利用節點的wait_2放大可用時間相當于同時放大比其遠的所有節點的可用時間,有利于使更多的節點參與擴大了的負載處理,所以,該過程從wait_2不為零的節點中距Sink最近的節點開始,這樣符合能耗波動較小原則。假設nj為wait_2不為零的節點中距離Sink最近的節點,那么節點集node[j:n]的放大比例為timej[1:4]/timej[1:3]。與等比例縮小的原理一樣,等比例放大負載量的節點集的工作時序不變。放大node[j:n]的負載量后,如果L[1:n]≥L,說明放大wait_2j可以完成負載處理,則按能耗完全均衡的調度策略分配(L-L[1:j-1])負載到節點集node[j:n]上,算法結束。如果L[1:n]

3.3　“幫助”過程

幫助過程利用wait_1時間段增加負載處理量,以滿足約束條件(3)。但利用一個節點的wait_1中的一段時間增加該節點的負載量時要相應地等比例縮小比其遠的節點集的負載量,以滿足約束條件(2)。所以,首先要證明該節點增加的負載量要比相應的節點集減少的負載量多才能說明利用wait_1增加負載處理量的設計是有效的。下面給出證明。

定理假如WSN的工作時序中nj(1≤j

圖5　wait_1j中取幫助時間段x

nj增加的負載為Linc=x/(y+z);

節點集node[j+1:n]減少的負載為Ldec=L[j+1:n]·((x·z/(y+z))/timej[1:2])。則變化量Δ:

Δ=Linc-Ldec=((timej[1:2]-L[j+1:n]·z)x)/
((y+z)timej[1:2])

(20)

式中,timej[1:2]是節點集node[j+1:n]原可用時間,而L[j+1:n]·z是節點集node[j+1:n]原傳輸時間總和。所以Δ≥0,得證。

4　仿真實驗及分析

實驗網絡的特征:距Sink節點300 m～400 m范圍內有1個節點,500 m～600 m內有2個節點,700 m～800 m內有3個節點,900 m～1 000 m內有4個節點;y=1,z=0.1;總負載為1 000 bit;每個節點的總能量為10 J;每bit傳輸和感知能耗ES-elec=ET-elec=50 nJ/bit;每bit的放大系數εamp=100 pJ/(bit·m2)。網絡的給定完成時間Tgiven=Tmin+2/3·(Tmin-e-Tmin)。進行五組仿真實驗,實驗中各節點與Sink的距離如表1所示。

表1　隨機生成的實驗網絡

4.1　與最短時間負載調度的比較

取最短時間負載調度與DLEBS的能耗標準差比較以驗證算法的有效性。在最短時間負載調度時測試了兩組數據,一組為RMTLS(2.1節中定義)的能耗標準差,即最短時間負載調度的一般形式;另一組為SMTLS(2.1節中定義)的能耗標準差;選擇SMTLS測試是因為其與能耗完全均衡調度有相似的負載分配形式,即節點距Sink越近分配的負載越多,而后者是本文DLEBS算法的基礎。

圖6　3組能耗標準差的比較

3組調度策略的能耗標準差如圖6所示。從圖6可以看出DLEBS使得WSN能耗標準差明顯下降,雖然SMTLS與其負載分配形式類似,但DLEBS仍然比SMTLS有更好的優化效果。這是因為兩者設計的調度目標不同。最短時間調度側重時間短、總體能耗小,而DLEBS則側重能耗均衡。另一方面,RMTLS與SMTLS之間的較大差異說明,對于最短時間負載調度,不同的處理方法會引起差別較大的能耗波動。

4.2　與按距離比例負載調度的比較

按距離比例負載調度(DPEBS)是指以各節點到Sink的距離比例為依據,比例大的節點少分配負載,反之多分配負載。具體做法是將各節點按其到Sink的距離從遠到近排序,計算各距離的比例,然后依比例從小到大地將負載分配到排序的節點上以達到能耗均衡的目的。DPEBS是一種常用的簡單的能耗均衡負載調度策略。本節取DPEBS與DLEBS的能耗標準差比較以驗證算法的優化效果。如圖7所示,DLEBS算法的能耗不均衡度大概是DPEBS的20%。這是因為,DPEBS算法雖然考慮了各節點的距離對能耗均衡的影響,但是沒有較好地對距離與能耗均衡之間的關系進行建模。簡單地按比例來描述兩者之間的關系使其對能耗均衡的調整效果沒有DLEBS算法好。

圖7　DLEBS與DPEBS的比較

4.3　能耗不均衡度與給定時間的關系

給定完成時間Tgiven(Tmin

圖8　能耗不均衡度隨時間的變化

圖9　對網絡生存周期的影響

4.4　網絡生存周期的影響

DLEBS,DPEBS,RMTLS算法對網絡生存周期的影響如圖9所示。從圖9可以看出,由于針對能耗均衡的設計,DLEBS與DPEBS在延長網絡生存周期方面均優于RMTLS;由于DLEBS在能耗均衡方面優于DPEBS,所以在延長網絡生存周期方面DLEBS表現出較好的性能,比DPEBS提高了近一倍。

5　結束語

針對可分負載WSN的能耗均衡問題提出了DLEBS負載調度算法。以負載的最短完成時間Tmin及能耗完全均衡條件下的最短完成時間Tmin-e為參考,該算法重點對兩個時間點之間的能耗均衡進行了優化。詳細闡述了DLEBS算法的3個基本過程,并從理論上證明了“幫助”過程的有效性。通過仿真實驗,進一步驗證了DLEBS以能耗均衡為目的建模的有效性,其效果明顯優于最短時間負載調度RMTLS及按距離比例負載調度DPEBS,驗證了算法在選取增加負載處理量順序時的合理性及在延長網絡生存周期方面的顯著作用。

參考文獻:

[1]孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005:3-6.

[2]Jennifer Yick,Biswanath Mukherjee,Dipak Ghosal.Wireless Sensor Network Survey[J].Computer Networks,2008,52(12):2292-2330.

[3]Qin Wang,Mark Hempstead,Woodward Yang.A Realistic Power Consumption Model for Wireless Sensor Network Devices[C]//Sensor and Ad Hoc Communications and Networks.Reston:IEEE Conference Publications,2006.

[4]Wendi Rabiner Heinzelman,Anantha Chandrakasan,Hari Balakrishnan.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//System Sciences.Hawaii:IEEE Conference Publications,2000.

[5]黃飛,金心宇,張昱,等.基于GASA的能耗均衡WSN路由協議[J].傳感技術學報,2009,22(4):586-592.

[6]姚玉坤,王冠,任智,等.能耗均衡的自供能無線傳感器網絡分簇路由算法[J].傳感技術學報,2013,26(10):1420-1425.

[7]鄧舟,王國軍,馬征,等.無線傳感器網絡中一種負載均衡的跳躍式路由協議[J].傳感技術學報,2009,22(3):407-412.

[8]Kijeung Choi,Robertazzi T G.Divisible Load Scheduling in Wireless Sensor Networks with Information Utility[C]//Performance,Computing and Communications Conference.Texas:IEEE Conference Publications,2008.

[9]Yang Yu,Viktor K Prasanna.Energy-Balanced Task Allocation for Collaborative Processing in Wireless Sensor Networks[J].Mobile Networks and Applications,2005,10(1):115-131.

[10]Yichao Jin,Dali Wei,Alexander Gluhak,et al.Latency and Energy-Consumption Optimized Task Allocation in Wireless Sensor Networks[C]//Wireless Communications and Networking Conference.Sydney:IEEE Conference Publications,2010.

[11]Thomas G Robertazzi.Ten Reasons to Use Divisible Load Theory[J].Computer,2003,36(5):63-68.

[12]Mequanint Moges,Thomas G Robertazzi.Wireless Sensor Networks:Scheduling for Measurement and Data Reporting[J].IEEE Transactions on Aerospace and Electronic Systems,2006,42(1):327-339.

[13]代亮,許宏科,陳婷.無線傳感器網絡可分負載調度算法[J].西安交通大學學報,2012,46(6):23-28.

[14]康雨,閆相國,鄭崇勛,等.任意可分負載的多輪調度算法[J].西安交通大學學報,2009,43(8):125-129.

[15]代亮,沈中,常義林,等.無線傳感器網絡多輪任務調度算法[J].西安交通大學學報,2010,44(6):27-32.

[16]代亮,沈中,常義林,等.無線傳感器網絡任務調度雙層規劃方法[J].兵工學報,2010,31(12):1697-1701.

[17]Kang H,Guan P,Liu X,et al.Utility-Based Divisible Sensing Task Scheduling in Wireless Sensor Networks[J].Department of Computer Science Oklahoma State University Stillwater,2007:342-348.

[18]Thomas E Carroll,Daniel Grosu.A Strategyproof Mechanism for Scheduling Divisible Loads in Linear Networks[C]//Parallel and Distributed Processing Symposium.Long Beach:IEEE International,2007.

[19]Yuan-Chieh Cheng,Thomas G Robertazzi.Distributed Computation with Communication Delay[J].IEEE Transactions on Aerospace and Electronic Systems,1988,24(6):700-712.

劉端陽(1975-),男,漢族,博士,湖南人,浙江工業大學計算機學院副教授,碩士研究生導師,研究方向為分布式計算、無線傳感器網絡和信息安全,ldy@zjut.edu.cn;

暴占兵(1986-),男,漢族,碩士(在讀),河北人,浙江工業大學計算機學院研究生,研究方向為無線傳感器網絡能耗;

程珍(1981-),女,漢族,湖北人,浙江工業大學計算機學院講師,研究方向為無線傳感器網絡和信息安全。