拓撲感知的無線傳感網絡數據聚合方法①

熊 英,李 蕓

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

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

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

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

綜上所述,為了解決上述基于CS 方法的挑戰,本文提出了一種拓撲感知的無線傳感網絡數據聚合方案(TADA).主要是利用拓撲信息以高精度重建原始數據,構造測量矩陣對無線傳感網絡多路徑轉發,從而進行全網絡矢量分配,并提出了基于平衡最小生成樹的數據聚合算法,使數據聚合更能適應拓撲結構的動態變化.

1 問題描述

在數據聚合過程中,編碼集D是一組權重向量,用于對傳感器節點的原始數據進行編碼.在接收器端,該過程可以表示為:

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

2 通信過程

2.1 TADA 數據流

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

圖1 哈希表

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

圖2 TADA 數據傳輸

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

2.2 數據檢測

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

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

原始數據向量的維數為N,即為網絡中的傳感器節點數,任何路徑的原始數據向量只在路徑上與這些節點對應的位置具有非零值.對于上述示例中的x1,這些節點是節點R1、R3、R4、R7和R10.根據矩陣,收集過程表示為:

3 向量分配策略

3.1 編碼集D 構造

從一個編碼集D構造映射為矩陣ΦM×N,然后進一步解釋網絡中加入更多節點時如何擴展映射矩陣.對編碼集建模為:

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

圖3 并行分解的數據轉發過程

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

3.2 全網矢量分配策略

在構造編碼集D之后,下一步就需要將D擴散到整個網絡,利用哈希表進行矢量分配,由于BMST 總會生成一個樹結構,因此從接收器到任何節點的路徑都是唯一的,向量分配過程由Sink 節點執行.

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

圖4 權重向量分配和策略矩陣構造

4 基于BMST的數據聚合算法

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

其中,α是D'(d)的正系數,控制距離對路徑選擇的影響,選擇附近的節點加入網絡可以促進降低能耗.因此,函數D'定義為:

式中,函數J(hn)表示節點n到達接收器的跳數函數,而跳數越多會導致拓撲不平衡,即對網絡貢獻的一種懲罰.因此,為了讓J(h)隨著跳數h的增加而增長得更快,加入系數λ為懲罰度,使函數J(h)定義為:

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

算法1.BMST 生成1.輸入:N//節點數量,Tt//拓撲表,Ft//未連接節點集合,hj//從節點j 到Sink的單跳數量,pj//父類節點索引2.搜索最近的節點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 實驗結果分析

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

5.1 數據聚合能耗

假設N個傳感器節點隨機均勻地分布在一個正方形區域中,準備將其讀數發送到Sink 節點.這時,將網絡通信能量消耗表示為E,表示與權重向量大小和傳輸次數有關.計算為:

式中,MTU表示由通信協議確定的最大傳輸單元,如果在所考慮的數據聚合網絡中由M確定的向量大小大于MTU,則將每個加權向量分割成個包.讓每一輪數據表示每個節點完成將其緩沖區的第一次讀取上載到Sink 節點的時間段,傳輸數是指每一輪數據聚合中的點對點傳輸的總數.

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

圖5 本文所提方法與ICS、RW在節點數的能耗比較

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

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

5.2 數據重建恢復率

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

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

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

6 結論與展望

本文構造測量矩陣將數據分解為多個路徑轉發,從而進行全網絡矢量分配,并提出了基于平衡最小生成樹的數據聚合算法,緩解了無線傳感網絡中數據聚合能耗和重建誤差問題.但本文方法對數據的構造還不夠精確,在聚合過程中較難把握通信數據的語義方向,在下步工作中需要進一步完善編碼集D的構造和矢量分配,以優化整個算法性能,進一步適應動態拓撲的變化.