拓?fù)涓兄臒o線傳感網(wǎng)絡(luò)數(shù)據(jù)聚合方法①

熊 英,李 蕓

1(江門開放大學(xué) 信息技術(shù)部,江門 529234)

2(東華理工大學(xué) 水資源與環(huán)境工程學(xué)院,南昌 330013)

隨著無線通信技術(shù)的不斷發(fā)展,對傳輸數(shù)據(jù)速率和頻譜效率的要求不斷提高[1,2],在這些技術(shù)中,無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)作為數(shù)據(jù)監(jiān)測和數(shù)據(jù)獲取的主要應(yīng)用方式[1],通過多跳路由從傳感器發(fā)送到一個或多個數(shù)據(jù)接收器.同時,隨著移動技術(shù)的進(jìn)步,提出了在數(shù)據(jù)聚合過程中應(yīng)用無人機(jī)的思想[2,3],由于傳感器節(jié)點(diǎn)通常具有有限的計算能力和功率儲備,在數(shù)據(jù)聚合過程中利用無人機(jī)的主要目標(biāo)是以所需的精度收集數(shù)據(jù),同時降低傳感器的消耗[4,5].壓縮感知技術(shù)(Compressive Sensing,CS)[6]對于有限資源的傳感節(jié)點(diǎn),可以實(shí)現(xiàn)采集和壓縮的功能,這是資源有限的傳感器節(jié)點(diǎn)的理想特性[7],文獻(xiàn)[8]在CS 數(shù)據(jù)采集方案中,將WSN的N個傳感器節(jié)點(diǎn)生成的原始數(shù)據(jù)向量表示為x={x1,x2,···,xN}T,聚合過程建模為:

式(1)中,每個原始數(shù)據(jù)xj由權(quán)重向量φj編碼,該權(quán)重向量也是測量矩陣Φ的第j列向量,測量矩陣Φ通常為M×N隨機(jī)矩陣,M為權(quán)重向量數(shù),N為網(wǎng)絡(luò)傳感器節(jié)點(diǎn)數(shù),以下均為此表述.因此,聚合向量y小于未知數(shù)據(jù)的數(shù)目,當(dāng)x滿足k-稀疏時且矩陣ΦM×N滿足限定等矩性[7](Restricted Isometry Property,RIP)條件時,Sink 移動節(jié)點(diǎn)可以從y={y1,y2,···,yN}T中恢復(fù)原始數(shù)據(jù)向量x的精度.文獻(xiàn)[8]采用局部混合CS 方法構(gòu)建簇的大小與傳輸次數(shù)之間的關(guān)系的模型,以找到最優(yōu)簇的大小,以此來提高數(shù)據(jù)聚合的效率,但由于無線傳感網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有動態(tài)性,當(dāng)新增傳感器時,局部CS 方法較難快速構(gòu)造出可行測量矩陣,網(wǎng)絡(luò)向所有傳感器節(jié)點(diǎn)廣播新的測量矩陣會增加能耗且數(shù)據(jù)重建誤差增大;文獻(xiàn)[9]提出了全局CS的方法,將感知數(shù)據(jù)進(jìn)行加權(quán)計算而非將單個原始數(shù)據(jù)傳送到每個Sink 節(jié)點(diǎn),有利于數(shù)據(jù)向量的聚合,但由于全局CS 方法中點(diǎn)到點(diǎn)傳輸?shù)拇螖?shù)一般大于傳感器節(jié)點(diǎn)的最大傳輸單元,需要將每個數(shù)據(jù)編碼的權(quán)重向量分割成多個包,這樣會使傳輸?shù)拇螖?shù)急劇增加,導(dǎo)致更高的能耗.

綜上所述,為了解決上述基于CS 方法的挑戰(zhàn),本文提出了一種拓?fù)涓兄臒o線傳感網(wǎng)絡(luò)數(shù)據(jù)聚合方案(TADA).主要是利用拓?fù)湫畔⒁愿呔戎亟ㄔ紨?shù)據(jù),構(gòu)造測量矩陣對無線傳感網(wǎng)絡(luò)多路徑轉(zhuǎn)發(fā),從而進(jìn)行全網(wǎng)絡(luò)矢量分配,并提出了基于平衡最小生成樹的數(shù)據(jù)聚合算法,使數(shù)據(jù)聚合更能適應(yīng)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化.

1 問題描述

在數(shù)據(jù)聚合過程中,編碼集D是一組權(quán)重向量,用于對傳感器節(jié)點(diǎn)的原始數(shù)據(jù)進(jìn)行編碼.在接收器端,該過程可以表示為:

式(2)中,xJ={x1,x2,···,xN}T表示路徑J的數(shù)據(jù),ΦM×N為映射矩陣,它由D的權(quán)重向量構(gòu)成(即列向量),R為當(dāng)前傳感器節(jié)點(diǎn).當(dāng)數(shù)據(jù)沿著從葉節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的路徑聚合時,每個節(jié)點(diǎn)將它的數(shù)據(jù)加權(quán)向量與從它的子節(jié)點(diǎn)接收的向量組合,然后將組合后的向量轉(zhuǎn)發(fā)給相應(yīng)的父節(jié)點(diǎn);最后通過多跳方式,在接收端收集數(shù)據(jù)向量,利用路徑J的路由信息對xJ進(jìn)行解碼.在式(2)中,測量信號yJ={y1,y2,···,yN}T為在接收器處收集的數(shù)據(jù)編碼矢量.

2 通信過程

2.1 TADA 數(shù)據(jù)流

(1)網(wǎng)絡(luò)初始化:N個傳感器節(jié)點(diǎn)在有限區(qū)域內(nèi)隨機(jī)均勻分布.設(shè)置一個平衡最小生成樹(Balanced Minimum Spanning Tree,BMST)的拓?fù)錁?gòu)造算法(將在第4 小節(jié)中進(jìn)一步闡述),在BMST 形成拓?fù)浣Y(jié)構(gòu)后,每個節(jié)點(diǎn)沿著BMST 給出的路由路徑向Sink 發(fā)送幀跳信號,Sink 收集所有的幀跳并相應(yīng)地生成一個哈希表.如圖1所示,首先,哈希表記錄每個路徑的路徑索引號和路由序列,通過哈希表接收器獲取最長的路由路徑lmax,Sink 生成一個權(quán)重向量數(shù)M≥lmax的向量編碼集D={di},其中di∈RM×1;然后,按照此權(quán)重向量分配策略,從D中為每個節(jié)點(diǎn)分配一個權(quán)重向量,即為矢量分配的策略,將在2.2 節(jié)中闡述.

圖1 哈希表

(2)數(shù)據(jù)分幀:初始化完成后,每個節(jié)點(diǎn)通過將其與指定的權(quán)重向量xi×ΦM×1(i)相乘,對其原始傳感基準(zhǔn)xi進(jìn)行編碼,并將其發(fā)送到其父節(jié)點(diǎn).如果節(jié)點(diǎn)J從節(jié)點(diǎn)i接收到包xi×ΦM×1(i),則將其編碼的分組與接收的分組線性結(jié)合,即xi×ΦM×1(i)+xj×ΦM×1(j).同時,如圖2所示,幀頭記錄已將其向量添加到線性組合中的節(jié)點(diǎn)的索引號,如果節(jié)點(diǎn)上沒有需要上傳的數(shù)據(jù),那么它會轉(zhuǎn)發(fā)接收到的數(shù)據(jù)包,幀頭也不會記錄其節(jié)點(diǎn)的索引號.

圖2 TADA 數(shù)據(jù)傳輸

(3)數(shù)據(jù)預(yù)處理:當(dāng)接收器接收到一個數(shù)據(jù)包時,就會檢查來自幀頭的索引號,然后形成未知的原始數(shù)據(jù)向量,最后運(yùn)行數(shù)據(jù)檢測算法.

2.2 數(shù)據(jù)檢測

上所述過程中,每個節(jié)點(diǎn)在發(fā)送到其父節(jié)點(diǎn)之前用權(quán)重向量 φj對其自身的數(shù)據(jù)xj進(jìn)行編碼,Sink 接收的數(shù)據(jù)包是所有數(shù)據(jù)編碼向量沿路徑的線性組合,如式(3)所示:

圖2描述了TADA 中數(shù)據(jù)轉(zhuǎn)發(fā)和收集處理的示例,節(jié)點(diǎn)R1將其數(shù)據(jù)編碼向量發(fā)送到其父節(jié)點(diǎn)R3.然后,節(jié)點(diǎn)R3將其自身的數(shù)據(jù)向量與從節(jié)點(diǎn)R1接收到的向量線性地組合成一個分組,并將其轉(zhuǎn)發(fā)到節(jié)點(diǎn)R4.這些進(jìn)程不斷重復(fù),直到組合的數(shù)據(jù)到達(dá)接收器為止.在Sink 節(jié)點(diǎn)收集的數(shù)據(jù)向量為:

原始數(shù)據(jù)向量的維數(shù)為N,即為網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)數(shù),任何路徑的原始數(shù)據(jù)向量只在路徑上與這些節(jié)點(diǎn)對應(yīng)的位置具有非零值.對于上述示例中的x1,這些節(jié)點(diǎn)是節(jié)點(diǎn)R1、R3、R4、R7和R10.根據(jù)矩陣,收集過程表示為:

3 向量分配策略

3.1 編碼集D 構(gòu)造

從一個編碼集D構(gòu)造映射為矩陣ΦM×N,然后進(jìn)一步解釋網(wǎng)絡(luò)中加入更多節(jié)點(diǎn)時如何擴(kuò)展映射矩陣.對編碼集建模為:

式中,N為網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)數(shù)或原始數(shù)據(jù)向量維數(shù),ΦM×N是存儲在Sink 節(jié)點(diǎn)中用于數(shù)據(jù)恢復(fù)的映射矩陣.當(dāng)節(jié)點(diǎn)數(shù)N增加時,映射矩陣也隨之改變,使得映射矩陣的構(gòu)造成為關(guān)鍵問題.本文所提出的一種利用編碼集D構(gòu)造 ΦM×N的方法,首先將數(shù)據(jù)聚合過程并行分解為多條路由路徑的數(shù)據(jù)轉(zhuǎn)發(fā)過程.如圖3所示,描述了路徑1 由{x1,x3,x4,x7,x10}組成,借鑒文獻(xiàn)[10]的方法可分析為:如果相應(yīng)的權(quán)重向量{φ1,φ2,φ3,φ7,φ10}為正交,則Sink是具有路徑1的路由表知識,Sink 可以成功地檢索{x1,x3,x4,x7,x10},從而求解檢測方程并得到唯一解.

圖3 并行分解的數(shù)據(jù)轉(zhuǎn)發(fā)過程

基于上述分析,設(shè)計了一個正交向量集D={d1,d2,···,dlmax},其中l(wèi)max=maxi{li},li為路徑i的路徑長度,dj∈RM×1,j∈{1,2,···,lmax}是相互正交.很明顯,任何一個路徑,只要M＞lmax且所有l(wèi)i節(jié)點(diǎn)從集合中選擇它們的權(quán)重向量D,接收器Sink 可以成功檢索原始數(shù)據(jù).

3.2 全網(wǎng)矢量分配策略

在構(gòu)造編碼集D之后,下一步就需要將D擴(kuò)散到整個網(wǎng)絡(luò),利用哈希表進(jìn)行矢量分配,由于BMST 總會生成一個樹結(jié)構(gòu),因此從接收器到任何節(jié)點(diǎn)的路徑都是唯一的,向量分配過程由Sink 節(jié)點(diǎn)執(zhí)行.

如圖4所示,前一示例的權(quán)重向量分配對于任何路徑i,Sink 首先檢查哈希表中的信息,然后Sink 按照節(jié)點(diǎn)存儲在哈希表中的順序逐個分配D的向量.路徑2 由4 個傳感器節(jié)點(diǎn)組成.Sink 首先從哈希表中查詢信息,然后依次將權(quán)重向量d1,d2,d3,d4分配給節(jié)點(diǎn)R10,節(jié)點(diǎn)R7,節(jié)點(diǎn)R6,節(jié)點(diǎn)R5.然后,按照分配給傳感器節(jié)點(diǎn)的權(quán)重向量的順序,通過對齊來構(gòu)建整個網(wǎng)絡(luò)的矩陣ΦM×N.從而構(gòu)造一個了策略矩陣,得出最長路徑完全消耗了編碼集D的權(quán)值向量,由于每個路徑權(quán)值向量的正交性,測量矩陣可以高精度地檢索任意路徑的原始數(shù)據(jù),從而進(jìn)行網(wǎng)絡(luò)擴(kuò)展.

圖4 權(quán)重向量分配和策略矩陣構(gòu)造

4 基于BMST的數(shù)據(jù)聚合算法

上述策略矩陣的構(gòu)造,是通過編碼集D的基數(shù)lmax逐步擴(kuò)展網(wǎng)絡(luò),而lmax則是整個網(wǎng)絡(luò)中最長路徑的長度,為使擴(kuò)展的網(wǎng)絡(luò)達(dá)到平衡狀態(tài),采用平衡最小生成樹(Balanced Minimum Spanning Tree,BMST)[11].網(wǎng)絡(luò)中的節(jié)點(diǎn)i先不發(fā)送原始數(shù)據(jù)di,而是根據(jù)從編碼集D分配的權(quán)重向量對di進(jìn)行編碼,并將長度lmax的權(quán)重數(shù)據(jù)發(fā)送到其父節(jié)點(diǎn).因此,每次傳輸?shù)挠行лd荷是lmax,而本文的主要目的是降低lmax,從而降低數(shù)據(jù)聚合過程中的能耗.在所有路徑長度均為平衡的條件下,在所提方法中考慮了樹構(gòu)造的鄰居節(jié)點(diǎn)選擇跳數(shù).樹的構(gòu)造過程從Sink 節(jié)點(diǎn)開始,Sink 選擇一個最優(yōu)節(jié)點(diǎn),并在每個結(jié)構(gòu)更新步驟中將其添加到網(wǎng)絡(luò)中.此進(jìn)程終止,直到所有節(jié)點(diǎn)都在網(wǎng)絡(luò)上.這里,最優(yōu)節(jié)點(diǎn)是指對平衡樹貢獻(xiàn)值最大的節(jié)點(diǎn).將樹上未連接節(jié)點(diǎn)k與節(jié)點(diǎn)n連接的貢獻(xiàn)評估函數(shù)表示為C(D'(dn,k),J(hn)).其中,D'是編碼集，包含了原始數(shù)據(jù)di到dk的距離,k是節(jié)點(diǎn)k到節(jié)點(diǎn)n的距離,J是hn的函數(shù),hn是連接節(jié)點(diǎn)n到Sink的跳數(shù).用C來表示k到n的連接貢獻(xiàn),定義為:

其中,α是D'(d)的正系數(shù),控制距離對路徑選擇的影響,選擇附近的節(jié)點(diǎn)加入網(wǎng)絡(luò)可以促進(jìn)降低能耗.因此,函數(shù)D'定義為:

式中,函數(shù)J(hn)表示節(jié)點(diǎn)n到達(dá)接收器的跳數(shù)函數(shù),而跳數(shù)越多會導(dǎo)致拓?fù)洳黄胶?即對網(wǎng)絡(luò)貢獻(xiàn)的一種懲罰.因此,為了讓J(h)隨著跳數(shù)h的增加而增長得更快,加入系數(shù)λ為懲罰度,使函數(shù)J(h)定義為:

BMST 生成方法如算法1所示.

算法1.BMST 生成1.輸入:N//節(jié)點(diǎn)數(shù)量,Tt//拓?fù)浔?Ft//未連接節(jié)點(diǎn)集合,hj//從節(jié)點(diǎn)j 到Sink的單跳數(shù)量,pj//父類節(jié)點(diǎn)索引2.搜索最近的節(jié)點(diǎn)j 至Sink 且生成一個路由表3.Tt={Nodej:{hj,pj}};Ft={ Node1,…,NodeN }/ Nodej;4.Set Cmax←-∞5.while i in N-1 do 6.Set Cmax←-∞7.while Nodek in Ft do 8.while Noden in Tt.Node do 9.Count C(dn,k,hn);10.if C(dn,k,hn)≥Cmax then 11.Set Cmax←C(dn,k,hn)12.Set s←k 13.Set hs←hn+1 14.Set ps←n 15.end if 16.end while 17.end while 18.Tt←Tt∪{Nodes:{hs,ps}}19.Ft←Ft/ Nodes 20.end while 21.輸出:Tt

5 實(shí)驗(yàn)結(jié)果分析

將本文所提方法與RW 方法[12]和ICS 方法[13]進(jìn)行比較,并從數(shù)據(jù)聚合能耗、數(shù)據(jù)重建恢復(fù)率和測量矩陣存儲要求3 個方面對本文所提方法進(jìn)行了評估.

5.1 數(shù)據(jù)聚合能耗

假設(shè)N個傳感器節(jié)點(diǎn)隨機(jī)均勻地分布在一個正方形區(qū)域中,準(zhǔn)備將其讀數(shù)發(fā)送到Sink 節(jié)點(diǎn).這時,將網(wǎng)絡(luò)通信能量消耗表示為E,表示與權(quán)重向量大小和傳輸次數(shù)有關(guān).計算為:

式中,MTU表示由通信協(xié)議確定的最大傳輸單元,如果在所考慮的數(shù)據(jù)聚合網(wǎng)絡(luò)中由M確定的向量大小大于MTU,則將每個加權(quán)向量分割成個包.讓每一輪數(shù)據(jù)表示每個節(jié)點(diǎn)完成將其緩沖區(qū)的第一次讀取上載到Sink 節(jié)點(diǎn)的時間段,傳輸數(shù)是指每一輪數(shù)據(jù)聚合中的點(diǎn)對點(diǎn)傳輸?shù)目倲?shù).

(1)第一種情況下:在WiFi 環(huán)境下權(quán)重向量M的遠(yuǎn)遠(yuǎn)小于MTU,E主要由發(fā)送的數(shù)目NT控制.如圖5所示,本文所提方法與ICS和RW 相比,本文方法比RW 能量消耗更低,這是由于本文所提TADA 方法構(gòu)造了一個編碼集D映射為矩陣ΦM×N,進(jìn)而擴(kuò)散到整個網(wǎng)絡(luò),相比RW 方法降低了傳輸?shù)拇螖?shù),讓每一輪數(shù)據(jù)表示在一定正方形區(qū)域內(nèi).但是本文方法與ICS 相比,能量消耗仍然較高,這是由于在形成網(wǎng)絡(luò)過程中,形成了一個BMST 樹形結(jié)構(gòu),每一次通信傳輸均需要計算到葉子節(jié)點(diǎn),增加了每輪數(shù)據(jù)的傳輸計算次數(shù)和時間.

圖5 本文所提方法與ICS、RW在節(jié)點(diǎn)數(shù)的能耗比較

(2)第二種情況下:考慮傳感器節(jié)點(diǎn)正在利用輕量級通信協(xié)議(如藍(lán)牙或ZigBee 網(wǎng)絡(luò)環(huán)境下),其具有較小的MTU,它需要將一個數(shù)據(jù)編碼的權(quán)重向量分割為若干個數(shù)據(jù)包進(jìn)行發(fā)送.考慮包括300 個節(jié)點(diǎn)和MICS＝86和MTADA＝9的場景,能耗比較如圖6所示.由于權(quán)值向量較小,TADA在能耗方面具有更好的性能優(yōu)勢.這是由于本文方法采用了最小平衡樹,使網(wǎng)絡(luò)達(dá)到平衡狀態(tài),用貢獻(xiàn)平衡函數(shù)使Sink 跳到最優(yōu)節(jié)點(diǎn),控制距離對路徑選擇的影響,達(dá)到聚合過程中的能耗.因此,當(dāng)使用輕量級通信協(xié)議時,TADA是首選的.

圖6 本文所提方法與ICS、RW在MUT 大小的能耗比較

5.2 數(shù)據(jù)重建恢復(fù)率

由于數(shù)據(jù)聚合的目標(biāo)是收集感測到的原始數(shù)據(jù),因此會檢查不同協(xié)議的數(shù)據(jù)恢復(fù)率.在CS 中,通過一些貪婪的算法從M維數(shù)據(jù)向量y中恢復(fù)N維信號向量.

考慮一個N=100 節(jié)點(diǎn)的WSN 網(wǎng)絡(luò),假設(shè)原始數(shù)據(jù)x由k∈{4,5,6,7,8,9,10}稀疏源產(chǎn)生,RW,ICS和TADA的權(quán)重向量M=20.如圖7所示,顯示了具有3 個協(xié)議的網(wǎng)絡(luò)的錯誤率曲線.結(jié)果表明:無論稀疏度k有多大,TADA 網(wǎng)絡(luò)的錯誤率都可以忽略不計,但RW和ICS的錯誤率都隨著稀疏度k的增加而增加.參考文獻(xiàn)[14]所得出的證明,CS 隨機(jī)矩陣成功恢復(fù)數(shù)據(jù)的概率為P=1-2e-δ2M/8,其中δ是限定等距常數(shù)(RIC),換言之,RW和ICS的恢復(fù)誤差是不可避免的這是由于本文方法逐步分配權(quán)重向量和策略矩陣,在.貢獻(xiàn)平衡函數(shù)中選擇控制距離,從而使將葉子節(jié)點(diǎn)到父節(jié)點(diǎn)的每條路徑由相應(yīng)的權(quán)重向量子集構(gòu)成正交矩陣的子矩陣,以頑強(qiáng)滿足數(shù)據(jù)恢復(fù)的要求.

圖7 本文所提方法與ICS、RW 數(shù)據(jù)重建錯誤率比較

6 結(jié)論與展望

本文構(gòu)造測量矩陣將數(shù)據(jù)分解為多個路徑轉(zhuǎn)發(fā),從而進(jìn)行全網(wǎng)絡(luò)矢量分配,并提出了基于平衡最小生成樹的數(shù)據(jù)聚合算法,緩解了無線傳感網(wǎng)絡(luò)中數(shù)據(jù)聚合能耗和重建誤差問題.但本文方法對數(shù)據(jù)的構(gòu)造還不夠精確,在聚合過程中較難把握通信數(shù)據(jù)的語義方向,在下步工作中需要進(jìn)一步完善編碼集D的構(gòu)造和矢量分配,以優(yōu)化整個算法性能,進(jìn)一步適應(yīng)動態(tài)拓?fù)涞淖兓?