湯 榮 郭 劍
(南京郵電大學計算機學院 江蘇 南京 210003)
?
基于(ε,ζ)-近似融合的無線傳感網(wǎng)拓撲控制算法
湯榮郭劍
(南京郵電大學計算機學院江蘇 南京 210003)
對無線傳感器網(wǎng)絡(luò)的拓撲控制問題進行研究。為了節(jié)約網(wǎng)絡(luò)能量,最大化網(wǎng)絡(luò)生命周期,提出一種基于(ε,ζ)-近似數(shù)據(jù)融合的拓撲結(jié)構(gòu)控制算法QGA-UQ(Quantum Genetic Algorithm-Unique Q)。QGA-UQ引入了節(jié)點調(diào)度的思想。它首先根據(jù)用戶的數(shù)據(jù)精度要求,確定網(wǎng)絡(luò)中工作節(jié)點的比例,接著再使用量子遺傳算法,從網(wǎng)絡(luò)中選取合適的節(jié)點,并形成合理的拓撲結(jié)構(gòu)。網(wǎng)絡(luò)在此基礎(chǔ)之上進行數(shù)據(jù)的傳輸和融合處理。仿真試驗表明,QGA-UQ算法可以在保證融合結(jié)果精度的前提下,顯著延長了網(wǎng)絡(luò)生存時間,提高了網(wǎng)絡(luò)能量利用率。
拓撲控制無線傳感器網(wǎng)絡(luò)(ε,ζ)-近似融合節(jié)點調(diào)度量子遺傳算法
近年來,隨著計算機技術(shù)和傳感器技術(shù)的發(fā)展和成熟,無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)成為一個熱門領(lǐng)域,引起了人們的廣泛關(guān)注。無線傳感器網(wǎng)絡(luò)主要是由部署在監(jiān)測區(qū)域內(nèi)的大量傳感器節(jié)點組成,通過無線通信的方式,形成一個多跳式的自組織網(wǎng)絡(luò)。目前主要應用于醫(yī)療衛(wèi)生、環(huán)境監(jiān)測、災難預防、生態(tài)保護、智能家居等各個領(lǐng)域[1-3]。
拓撲控制是無線傳感器網(wǎng)絡(luò)的核心技術(shù)之一,它主要通過節(jié)點調(diào)度、發(fā)射半徑調(diào)節(jié)、通信鏈路選擇等手段,優(yōu)化網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。通過拓撲控制技術(shù),可以實現(xiàn)節(jié)約網(wǎng)絡(luò)能量、提升網(wǎng)絡(luò)通信性能等目標。在這方面,比較經(jīng)典的工作是WBHeinzelman等人[4]提出的LEACH協(xié)議。為了減少數(shù)據(jù)傳輸?shù)哪芎模琇EACH使用了簇結(jié)構(gòu),并在數(shù)據(jù)傳輸?shù)交厩笆褂么仡^節(jié)點來融合數(shù)據(jù),但是它的簇頭選取和數(shù)據(jù)傳輸策略存在一定問題,并且不能很好地兼顧到邊緣節(jié)點。在LEACH算法的基礎(chǔ)上,SDMuruganathan等[5]提出了BCDCP算法,采用迭代集群分裂算法選出多個簇頭節(jié)點,用MST(Minimum Spanning Tree)結(jié)構(gòu)連接簇頭節(jié)點,保證任意兩個節(jié)點之間都存在有向路徑,這樣整體拓撲結(jié)構(gòu)較復雜,能耗偏大。較早提出用MST結(jié)構(gòu)來連接拓撲的是Li N[6],其采用了MST結(jié)構(gòu)來連接所有網(wǎng)內(nèi)傳感器節(jié)點,用MST-Z算法來調(diào)整拓撲,結(jié)構(gòu)得到一定簡化,但依舊能耗較大。同時,拓撲控制還需考慮其他問題,例如Nishiyama H等[7]研究了動態(tài)網(wǎng)絡(luò)中的拓撲控制,Kim D等[8]控制拓撲時避免傳感器節(jié)點監(jiān)測區(qū)域的覆蓋沖突。
在傳感器網(wǎng)絡(luò)的實際應用中,人們往往并不關(guān)心節(jié)點采集的具體數(shù)據(jù),而是更關(guān)心宏觀的統(tǒng)計結(jié)果,如一個地區(qū)的平均溫度、最高濕度等,從而進行評估、決策等處理。這種情況下,就需要對網(wǎng)絡(luò)的采集數(shù)據(jù)進行一定的融合處理[9,10]。由于網(wǎng)絡(luò)拓撲不健壯、節(jié)點調(diào)度休眠等原因,網(wǎng)絡(luò)往往會丟失部分采集數(shù)據(jù),這時候,一些近似融合技術(shù)也就應運而生。ADeligiannakis等[11]和GHartl等[12]分別提出了基于時間的和基于空間的融合算法,它們在進行融合時不需要全部的數(shù)據(jù),但是不能有效地控制誤差范圍。Sergiou C等[13]在近似融合過程中隨機選定傳感器節(jié)點作為活躍節(jié)點,用RANDOM-UQ算法控制節(jié)點的工作與休眠,數(shù)據(jù)精確性依舊得不到滿足。Jianzhong Li等[14]提出的(ε,ζ)-近似融合算法,可以有效地控制融合的精度,但是它采用的網(wǎng)絡(luò)拓撲并不是很好。
上述研究表明,為了達到通信性能、節(jié)能效果與融合精度的平衡,有必要將拓撲控制技術(shù)與數(shù)據(jù)融合技術(shù)結(jié)合起來進行研究。從這個角度出發(fā),本文提出了一種基于(ε,ζ)-近似數(shù)據(jù)融合的拓撲結(jié)構(gòu)控制算法QGA-UQ(Quantum Genetic Algorithm- Unique Q)。QGA-UQ基于節(jié)點調(diào)度的思想,它首先根據(jù)融合結(jié)果精度的要求,確定網(wǎng)絡(luò)中休眠節(jié)點與工作節(jié)點的比例,接著再使用量子遺傳算法,從網(wǎng)絡(luò)中選取合適的節(jié)點,并基于MST樹形成網(wǎng)絡(luò)拓撲結(jié)構(gòu)。網(wǎng)絡(luò)在此基礎(chǔ)之上進行數(shù)據(jù)傳輸和數(shù)據(jù)融合。上述過程可以循環(huán)進行,從而使節(jié)點輪流休息,達到延長網(wǎng)絡(luò)生命周期的目的。實驗結(jié)果表明,QGA-UQ算法較好地實現(xiàn)了設(shè)計的目標。
1.1網(wǎng)絡(luò)模型
現(xiàn)有一塊無線傳感網(wǎng)的監(jiān)測區(qū)域,該區(qū)域部署了大量的傳感器節(jié)點,節(jié)點的部署方式為隨機部署。所有節(jié)點同質(zhì),并且可以調(diào)節(jié)各自的發(fā)射功率。
假設(shè)網(wǎng)絡(luò)初始時共有N個節(jié)點。在時刻t,無線傳感網(wǎng)內(nèi)存活節(jié)點的數(shù)目為Nt。依次對每次傳感器節(jié)點進行編號,編號i從1到Nt。顯然,當t=0時,Nt=N。
傳感器節(jié)點i在t時刻對應的感知數(shù)據(jù)記為kti,把監(jiān)測區(qū)域內(nèi)所有活動節(jié)點的感知數(shù)據(jù)組合成一個數(shù)據(jù)集Kt,即Kt={kt1,kt2,…,ktNt}??紤]到任何實際感知數(shù)據(jù)都是有范圍的,因此假定所有感知數(shù)據(jù)的上下界的值分別記為max(Kt)和min(Kt),并假設(shè)min(Kt)大于0。
本文假定,網(wǎng)絡(luò)要求對監(jiān)測區(qū)域內(nèi)觀測值的平均值A(chǔ)vg進行融合,并且融合結(jié)果要達到(ε,ζ)-近似估計的要求,(ε,ζ)-近似估計的精確定義將在第2節(jié)給出。
1.2能耗模型
本文使用了如下的能耗模型[15]。
無線傳感網(wǎng)內(nèi)的傳感器節(jié)點在發(fā)送和接收1bit數(shù)據(jù)時都需要消耗能量,分別記為Ef和Ej。兩者可通過以下公式計算:
當d 而d≥d0時,Ef=Eelec+μampd4 Ej=Eelec 其中,d為該節(jié)點與相鄰通信節(jié)點的距離,d0為收發(fā)兩端的距離門限值,Eelec是發(fā)射電路與接收電路的能耗,μfs和μamp分別為慢衰落模型和快衰落模型的參數(shù)。 出于節(jié)能的考慮,當網(wǎng)絡(luò)中的節(jié)點較多時,可以只讓部分節(jié)點進入工作狀態(tài),以減少網(wǎng)絡(luò)的能耗。但是另一方面,休眠的那部分節(jié)點也會導致采集數(shù)據(jù)的丟失,從而給數(shù)據(jù)融合的結(jié)果帶來一定的誤差。因此,活躍節(jié)點的比率q與數(shù)據(jù)融合的精度存在一定的約束關(guān)系。本節(jié)首先給出數(shù)據(jù)融合精度的相關(guān)描述,再給出q的計算方法。 關(guān)于近似融合,有如下定義[14]: (1) 假定在時刻t,網(wǎng)絡(luò)采集的數(shù)據(jù)集為Kt,則此刻平均值A(chǔ)vg的融合結(jié)果為: 其中,inf(Nt)表示整個融合過程中無線傳感網(wǎng)內(nèi)活動節(jié)點數(shù)目的最低值,Φζ/4為標準正態(tài)分布的ζ/4分位值。 本文提出了基于(ε,ζ)-近似融合的無線傳感網(wǎng)拓撲結(jié)構(gòu)控制算法QGA-UQ,其總體思路是從網(wǎng)絡(luò)中選擇部分節(jié)點,并對這部分節(jié)點進行一定的運算處理,形成合適的拓撲結(jié)構(gòu)。在拓撲調(diào)整過程中,控制每個傳感器節(jié)點的休眠與工作狀態(tài),不同周期內(nèi)選取不同傳感器節(jié)點進行數(shù)據(jù)融合。 上一節(jié)主要討論了選擇節(jié)點的比例,這一節(jié)將討論根據(jù)這個比例如何來選擇節(jié)點并生成網(wǎng)絡(luò)拓撲。由于無線傳感網(wǎng)內(nèi)傳感器節(jié)點數(shù)目多、密度大,數(shù)據(jù)傳輸?shù)哪芎南喈斂捎^,因此網(wǎng)絡(luò)拓撲的構(gòu)建主要從節(jié)能角度來考慮。QGA-UQ采用MST結(jié)構(gòu)[15]連接工作的傳感器節(jié)點,計算的過程則采用了量子遺傳算法[16]。 3.1染色體編碼及測量 本文把拓撲結(jié)構(gòu)的求解過程看作是量子遺傳算法中的種群演化過程,每一代種群中含有若干條染色體。每條染色體表示當前無線傳感網(wǎng)內(nèi)所有節(jié)點的選擇情況。如圖1所示,染色體由一串二進制數(shù)字表示,長度等于無線傳感網(wǎng)內(nèi)傳感器節(jié)點的總數(shù),即染色體有N位。每一位數(shù)字0代表對應的傳感器節(jié)點未被選取,1代表對應的傳感器節(jié)點被選取。被選取的傳感器節(jié)點參與數(shù)據(jù)信息的傳輸,以及數(shù)據(jù)融合工作,未被選取的傳感器節(jié)點可以暫時休眠。 節(jié)點1節(jié)點2節(jié)點3節(jié)點4節(jié)點5節(jié)點6…節(jié)點N100110…1 圖1染色體結(jié)構(gòu) 染色體的測量與量子比特概率幅有關(guān)。根據(jù)量子比特和量子旋轉(zhuǎn)門的調(diào)整,計算出相應的量子比特概率幅,每一周期的量子比特概率幅不同,測量染色體時,生成一個0到1之間的隨機數(shù),若隨機數(shù)的值大于概率幅的平方,則染色體當前位的二進制數(shù)取1,反之,則染色體當前位取0。 3.2染色體評價 圖2 MST結(jié)構(gòu)示意圖 對染色體進行評價必須從整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)考慮,圖2所示就是MST樹結(jié)構(gòu)的例子。其中,圖2(a)可以看到6個傳感器節(jié)點,節(jié)點b是簇頭節(jié)點,所有鏈路上標明的數(shù)字即為該段鏈路數(shù)據(jù)傳輸?shù)臋?quán)值。圖2(b)是圖2(a)對應的MST拓撲結(jié)構(gòu),它可以保證每個節(jié)點都能將數(shù)據(jù)傳輸?shù)酱仡^節(jié)點b且網(wǎng)絡(luò)總權(quán)值最小。 在此基礎(chǔ)之上,本節(jié)把染色體的評價函數(shù)設(shè)為: f=αEs-βEx+γEmin 其中,α、β和γ是相應的系數(shù),且它們都大于0。染色體評價函數(shù)主要考慮了如下三個方面: (1) 網(wǎng)絡(luò)內(nèi)所有節(jié)點的剩余能量之和Es,若第i個傳感器節(jié)點的剩余能量為Ei,那么Es可由下式得到: (2) 網(wǎng)絡(luò)內(nèi)所有傳感器節(jié)點消耗的能量總和Ex,可由下式計算得到: 其中Ei′是第i個傳感器節(jié)點消耗的能量,該計算可以參考1.2節(jié)的能耗模型。 (3) 該方案中網(wǎng)絡(luò)內(nèi)所剩能量最少節(jié)點的能量Emin,由式(2)可得。加入該項分量是出于網(wǎng)絡(luò)能量分布平衡性的考慮。 Emin=min{E1,E2,…,EqNt} (2) 3.3QGA-UQ的算法流程 (1) 網(wǎng)絡(luò)初始化。在已知的監(jiān)測區(qū)域范圍,隨機部署規(guī)定數(shù)目的傳感器節(jié)點,并且將它們從1到N進行編號,設(shè)定觀測數(shù)據(jù)值的上下界max(Kt)和min(Kt)。 (2) 結(jié)合(ε,ζ)-近似融合的要求,計算傳感器節(jié)點工作比例q。 (3) 使用量子遺傳算法計算出合適的網(wǎng)絡(luò)拓撲結(jié)構(gòu)。 (4) 網(wǎng)絡(luò)運行一定周期。在該周期內(nèi),未被選中的節(jié)點進行休眠,選中的節(jié)點則進入數(shù)據(jù)采集和傳輸?shù)裙ぷ鳡顟B(tài),并由sink節(jié)點進行數(shù)據(jù)融合的處理和估計。 (5) 如果網(wǎng)絡(luò)中的剩余節(jié)點少于qN,算法終止,否則轉(zhuǎn)入(2)。 本節(jié)通過仿真實驗驗證QGA-UQ算法的性能。仿真基于VS2013平臺,參數(shù)設(shè)置見表1。仿真時傳感器節(jié)點位置隨機部署。 表1 實驗仿真參數(shù)設(shè)置 首先,我們通過改變(ε,ζ)-近似融合中的ε和ζ的值,統(tǒng)計傳感器節(jié)點工作比例q的變化情況,表2是max(Kt)、min(Kt)分別為996和902時計算得出的結(jié)果。行代表ε,列代表ζ,數(shù)值代表的是傳感器節(jié)點工作比例q。表中可以看出,ζ相同時,ε越大,傳感器節(jié)點工作比例q越小,那是因為根據(jù)第2節(jié)定義1和2,ε越大融合結(jié)果容許的誤差更大,所以節(jié)點工作比例不必那么大;ε相同時,ζ越大,傳感器節(jié)點工作比例q也越小,同樣也可根據(jù)第2節(jié)定義1和2分析出,ζ越大其實要求的數(shù)據(jù)精確度更低,所以只要抽樣較少的傳感器節(jié)點。ε和ζ越靠近0時,要求的數(shù)據(jù)精確率逐步達到最高,于是傳感器節(jié)點工作比例q也越靠近于1。當ε為0.1、ζ為0.1時,傳感器節(jié)點工作比例q達到0.9835。同時可以進一步發(fā)現(xiàn),ε的值對q的影響較大。 表2 不同ε、ζ對應的傳感器節(jié)點工作比例q 在研究QGA-UQ算法的優(yōu)劣時,主要考慮以下兩個方面:網(wǎng)絡(luò)的生存時間和融合結(jié)果的相對誤差。本文將QGA-UQ算法與如下兩種算法進行對比:(1)MST-Z算法:基于總體進行數(shù)據(jù)融合處理,采用Prim算法的思想將所選節(jié)點用MST樹結(jié)構(gòu)連接,對拓撲結(jié)構(gòu)進行調(diào)整優(yōu)化。(2)RANDOM-UQ算法:基于概率抽樣法進行數(shù)據(jù)融合處理,采用隨機取點算法來控制拓撲結(jié)構(gòu)。三種算法同時在ε和ζ都取0.3的情況下仿真比較。 本文中,網(wǎng)絡(luò)生命周期定義為網(wǎng)絡(luò)內(nèi)存活節(jié)點數(shù)低于qN時所經(jīng)歷的周期數(shù),其中假設(shè)傳感器節(jié)點自身能量Es小于10 mJ時,該節(jié)點已死亡,不能再進入工作狀態(tài)。從圖3中可以看出,QGA-UQ算法下的網(wǎng)絡(luò)生存時長最長, RANDOM-UQ算法次之, MST-Z算法下的網(wǎng)絡(luò)生存時長最短。因此,MST樹結(jié)構(gòu)比隨機拓撲結(jié)構(gòu)更能延長網(wǎng)絡(luò)生命周期。同時利用(ε,ζ)-近似融合來處理感知數(shù)據(jù)時,能極大地提高生存時長。 圖3 三種算法的生存時間對比 在不同周期,對比三種算法融合結(jié)果與實際結(jié)果的相對誤差,如圖4所示,因為MST-Z算法是對無線傳感網(wǎng)中總體的傳感器節(jié)點進行數(shù)據(jù)采集,計算得出的Avg值沒有誤差。而其他兩種算法由于是抽樣采集,所以都存在不同程度的誤差,但總體來看,均遠遠小于預期的容許誤差0.3。 圖4 三種算法融合結(jié)果的相對誤差對比 綜上所述,在本文比較的三個拓撲控制算法中,QGA-UQ算法在保證較低的融合結(jié)果相對誤差下,網(wǎng)絡(luò)生存時間更長并且整體網(wǎng)絡(luò)能耗最少,是最優(yōu)的一種拓撲結(jié)構(gòu)控制算法。 為盡可能地監(jiān)測無線傳感網(wǎng)中的真實數(shù)據(jù)和減少整個網(wǎng)絡(luò)的能耗,本文提出了一種基于(ε,ζ)-近似數(shù)據(jù)融合的無線傳感網(wǎng)拓撲結(jié)構(gòu)控制算法QGA-UQ。首先,根據(jù)(ε,ζ)-近似數(shù)據(jù)融合法計算出抽樣傳感器節(jié)點數(shù)目,然后利用量子遺傳算法,通過種群染色體的不斷演化,基于MST結(jié)構(gòu)不斷調(diào)整,最后得出最優(yōu)拓撲結(jié)構(gòu)。仿真實驗表明,該算法對比已有算法表現(xiàn)出了良好的性能和穩(wěn)定性。 [1] Luís M Borges.Survey on the Characterization and Classification of Wireless Sensor Network Applications[J].IEEE Communication Surveys & Tutorials,2014,16(4):1860-1890. [2] 孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學出版社,2005. [3] Corporation H P.Multihop-Based Optimal Cluster Heads Numbers Considering Relay Node in Transmission Range of Sensor Nodes in Wireless Sensor Networks[J].International Journal of Distributed Sensor Networks,2013,13(2):140-154. [4] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]//The 33rd Annual Hawaii International Conference on System Siences (HICSS-33),Maui,USA,IEEE,Los Alamitos,CA,United States,2000:3005-3014. [5] Muruganathan S D,Bhasin R I.A centralized energy-efficient routing protocol for wireless sensor networks[J].IEEE Communications Magazine,2005,43(3):S8-S13. [6] Li N,Hou J C,Sha L.Design and analysis of an MST-based topology control algorithm[J].Proceedings-IEEE INFOCOM,2002,4(3):1195-1206. [7] Nishiyama H.On minimizing the impact of mobility on topology control in mobile ad hoc networks[J].IEEE Transactions on Wireless Communications,2012,11(3):1158-1166. [8] Kim D,Noel E,Tang K W.WSN communication topology construction with collision avoidance and energy saving[C]//2014 IEEE 11th Consumer Communications and Networking Conference,CCNC 2014,Las Vegas,NV,United states,IEEE Computer Society,2014:398-404. [9] 牛淑芬,王彩芬,杜小妮.無線傳感器數(shù)據(jù)融合技術(shù)中基于同態(tài)哈希函數(shù)的數(shù)據(jù)完整性算法[J].計算機應用與軟件,2013,30(12):48-51. [10] Jose J,Manoj Kumar S,Jose J.Energy efficient recoverable concealed data aggregation in wireless sensor networks[C]//2013 IEEE International Conference on Emerging Trends in Computing,Communication and Nanotechnology,ICE-CCN,2013:322-329. [11] Deligiannakis A,Kotidis Y,Roussopoulos N.Processing approximate aggregate queries in wireless sensor networks [J].Information Systems,2006,31(8):770-792. [12] Hartl G.A Bayesian Inference Approach towards Energy Efficient Data Collection in Dense Sensor Networks[C]//25th IEEE International Conference on Distributed Computing Systems,Columbus,OH,United states,Institute of Electrical and Electronics Engineers Inc,2005:371-380. [13] Sergiou C.Source based routing trees for efficient comgestion control in wireless sensor networks[C]//8th IEEE International Conference on Distributed Computing in Sensor Systems,Hangzhou,China,IEEE Computer Society,2012:378-383. [14] Li J Z,Cheng S Y.(ε,ζ)-Approximate Aggregation Algorithms in Dynamic Sensor Networks.[J].IEEE Transactions on Parallel and Distributed Systems,2011,23(3):385-396. [15] 韓崇,孫力娟,肖甫,等.基于SVD的無線多媒體傳感器網(wǎng)絡(luò)圖像壓縮機制[J].東南大學學報:自然科學版,2012,42(5):814-819. [16] Huang G Y,Li X W,He J.Dynamic Minimal Spanning Tree Routing Protocol for Large Wireless Sensor Networks[C]//2006 1st IEEE Conference on Industrial Electronics and Applications,ICIEA,2006:1-5. [17] 孫力娟,郭劍,陸凱,等.基于量子遺傳算法的傳感器網(wǎng)絡(luò)拓撲結(jié)構(gòu)控制[J].通信學報,2006,27(12):1-5. A TOPOLOGY CONTROL ALGORITHM FOR WIRELESS SENSOR NETWORKS BASED ON (ε,ζ)-APPROXIMATE AGGREGATION Tang RongGuo Jian (School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,Jiangsu,China) We study the topology control of wireless sensor networks in this paper.In order to save network energy and maximise network lifecycle,we propose a (ε,ζ)-approximate aggregation-based topology control algorithm QGA-UQ (quantum genetic algorithm-unique Q).QGA-UQ introduces the idea of node scheduling.It firstly determines the proportion of working nodes in network based on user’s requirement of data accuracy.Then it uses quantum genetic algorithm to select appropriate nodes in network and construct a reasonable topology.On this basis the network carries out the operation of data transmission and data fusion.Stimulation tests show that QGA-UQ can prolong the survival time of the network significantly and improve the utilisation of network energy greatly on the premise of guaranteeing the precision of fusion results. Topology controlWireless sensor networks(ε,ζ)-approximate aggregationNode schedulingQuantum genetic algorithm 2015-04-17。中國博士后科學基金項目(2014M5516 35);江蘇省博士后科研計劃項目(1302085B)。湯榮,碩士生,主研領(lǐng)域:無線傳感網(wǎng)。郭劍,副教授。 TP393 A 10.3969/j.issn.1000-386x.2016.09.0272 活躍節(jié)點比率的確定
3 基于(ε,ζ)-近似數(shù)據(jù)融合的拓撲控制算法
4 仿真實驗
5 結(jié) 語