一種面向最小能耗自適應匯聚路由判定算法

2022-05-28 04:19:22孫澤宇廖桂生

西安電子科技大學學報 2022年2期

關鍵詞：融合

孫澤宇，蘭嵐，曾操，廖桂生

(1.西安電子科技大學雷達信號處理國家重點實驗室，陜西西安 710071；2.洛陽理工學院計算機與信息工程學院，河南洛陽 471023；3.西安電子科技大學信息感知協同創新中心，陜西西安 710071)

無線傳感器網絡通過自組織方式將大量的傳感器節點連接成大規模的網絡系統[1-3]。該網絡系統具有較強的適應性和魯棒性，傳感器節點之間可以通過無線方式進行數據傳輸與通信，以協同方式完成對某種特定事件的監測[4-5]。傳感器節點雖然具有一定的通信能力、計算能力、存儲能力和感知能力，但其能力范圍有限，極易受外部環境、自然因素等方面制約，如電能無法補充、通信鏈路擁塞等[6-8]。在傳統的數據傳輸階段，主要是依靠傳感器節點將數據上傳到Sink節點后，再進行數據融合和計算，其不足主要體現在兩個方面：(1) 傳輸效率低。由于大量傳感器節點同時向Sink節點發送數據，必然要在信道內產生大量的冗余數據，增加了數據延時時間，造成了數據沖突與碰撞，降低了數據傳輸效率。(2) 網絡能耗增加。無線傳感器網絡在節點部署階段采用密集型部署方式，導致節點之間相鄰區域出現大面積的重疊區間，故節點在發送與接收數據時無故地消耗了大量網絡能量，造成了節點能量快速消耗與節點失效，縮短了網絡生存周期。因此，如何更好地提高可靠性數據傳輸效率和節約網絡能量，已成為無線傳感器網絡目前研究的主要問題。

近些年，國內外諸多專家學者對無線傳感器網絡的節能問題和可靠性數據傳輸做了大量研究工作。文獻[9]通過路由鏈表完成路徑選擇過程，其算法是將目標節點位置信息和當前節點的下一跳節點的路由寫入路由鏈表。當數據在傳至下一跳節點時，更新路由鏈表下一跳的節點信息，以保證傳輸數據的可靠性。文獻[10]中提出一種自適應的分層路由協議，可以減少參與路由計算的節點數量，縮減路由表長度，降低了交換路由信息所需能量的開銷，利用分簇機制形成了較穩定的子圖網絡，減少了網絡拓撲變化，延長了網絡生存周期。文獻[11]中提出了一種基于數據為中心的路由選擇算法，以節點到Sink節點之間的距離進行分類，確定不同類別的優先權；不同類別的節點在單位時間內向Sink節點發送數據；當所有不同類別的節點完成本輪任務后，再繼續下一輪操作。該算法避免了數據沖突與碰撞，減少了數據冗余，提高了數據傳輸效率。文獻[12]提出了一種基于凸殼的快速聚合規劃策略(Quick Convex Hull-Based Rendezvous Planning，QCHBRP)，以實現不相交的無線傳感器網絡的完全連通，并構建移動匯聚的短路徑。一方面，該策略可以通過移動Sink節點，快速地在監測區域內尋找多個數據“聚合點”，用以完成不相交區域的互連互通；另一方面，QCHBRP策略將整個網絡劃分為多個子網絡，并保證每個子網之間的距離近似相等或小于距離閾值；利用子網中的簇首節點轉發數據至Sink節點，從而規劃了從子網至Sink節點之間的路徑。文獻[13]中提出了一種基于壓縮感知丟包匹配數據收集算法(packet loss Matching Data Gathering Algorithm based on Compressive Sensing，CS-MDGA)，通過壓縮感知技術構建了全網節點的“關聯效應”，分析了樹狀路由在嚴重丟包情況下的重構精度，證明觀測矩陣近似于“1”時的等距約束條件，最后給出了多路徑備份路由傳輸機制。文獻[14]中提出了一種基于壓縮感知的聚類聯合環形路由數據收集方案(Compressive Sensing Clustering joint Annular Routing Data Gathering scheme，CS-CARDG)，采用集群采集數據方法完成數據傳輸過程。首先，對全網進行分簇，利用壓縮感知技術將簇成員節點所采集到的數據構成多維數據包，發送給簇首節點。當簇首節點將多維數據路由到Sink時，CS-CARDG方案將會從最外環開始，由外到內依次壓縮相同的分形數據，并通過最短路徑路由到基站。

上述研究雖然在一定程度上優化了路由選擇過程，但由于忽視了全網能量以及數據融合等因素，將會導致數據在傳輸和聚合時，網絡能量消耗較大，數據融合效率降低，網絡延時增加以及網絡生存周期縮短等不足。針對上述問題，筆者提出了一種面向最小能耗自適應匯聚路由判定算法(Adaptive Sink-routing Decision algorithm for Minimum-energy Consumption，ASD-MC)。ASD-MC算法利用節點之間的歐氏距離相關系數給出了匯聚增益表達方法以及數據融合度與能量開銷的函數關系；計算了數據融合度介于最小值和最大值之間時，與距離相關參數之間的比例關系；利用數據壓縮能耗比函數關系，證明了兩類不同節點提供可靠性傳輸距離滿足的必要條件，從而確定了數據傳輸最優路徑，達到了優化匯聚路由的目的。

1 問題描述

1.1 網絡模型

文中的網絡模型借助于圖論理論中圖的概念加以表示，即G=(V，E)，其中V表示所有傳感器節點集合，E表示任意兩個節點之間所有可能傳輸數據的鏈路集合[15]。可以把整個網絡的路由搜索空間減少到由多個子簇所形成的子網。在簇內，只有簇首節點可以主動維護網絡的路由信息，簇成員節點不參與路由維護過程，從而減少了路由更新的開銷。當沒有數據發送時，簇成員節點轉休眠狀態，這樣就保證網絡在正常連通條件下，減少轉發節點的數目和數據傳輸總量，降低擁塞和干擾發生的概率。為了更好地解決問題，筆者做如下規定：(1) 在全網內，任意節點都可以完成數據匯聚任務，把所有數據匯聚成一個數據包。(2) 簇內或簇間節點接收到相鄰節點發送的數據后，將自身數據與接收數據進行融合，并把融合后的數據作為新數據傳送給下一跳節點，直至把最終數據發送給Sink節點。

融合后的數據量應不大于節點m和節點n的原始數據量之和，不小于節點m和節點n中的任意節點的原始數據：

max{g0(m)，g0(n)}≤g1(n)≤g0(m)+g0(n) ，

(1)

其中，g0(m)和g0(n)表示數據融合前的數據量；g1(n)表示數據在節點n處融合后的數據量。

能量模型采用Heinzelman提出的自由空間和多路衰減模型。當傳輸距離d小于距離閾值d0時，路徑損耗指數為2；當傳輸距離d大于或等于距離閾值d0時，路徑損耗指數為4，則能量模型數學定義為[16]

(2)

(3)

其中，ETx表示發射模塊消耗的能耗；ERx表示接收模塊消耗的能耗；Eelec表示發送或接收1 bit數據量時所消耗的能量；Efu表示節點進行融合時所消耗的能量；Zdata_pa表示融合數據包的總量；Eda表示融合1 bit數據量所消耗的能量；k表示發送或接收的數據量；εfs，εmp是功率放大時的能耗系數。

1.2 匯聚增益模型

在無線傳感器網絡中，傳感器節點應根據數據匯聚增益自適應地調節數據融合位置信息，這樣才能更好地抑制能量消耗。用cmn表示數據融合度，表示在節點n處融合后數據量g1(n)較融合前數據量[g0(m)+g0(n)]減少了cmn，其數學模型為

(4)

感知數據從源節點傳至Sink節點時，路徑上單位數據能量開銷記作E(n，S)，任意節點在進行數據融合時能量開銷記作q(e)。根據式(4)，得到匯聚增益Δ(m，n)為

Δ(m，n)=[g0(m)+g0(n)][E(n，S)-(1-cmn)E(n，S)+q(e)] 。

(5)

當傳感器節點通信半徑為感知半徑的2倍時，記作Rc=2Rs。當任意兩節點之間歐氏距離do大于Rc時，則兩個節點之間相關參數為0；當任意兩節點之間歐氏距離d小于或等于Rc時，則兩個節點之間的相關參數為τ，數學表示式為

(6)

2 解決方案

2.1 融合度分析

基于對匯聚增益模型的分析，節點m和n之間的距離相關參數為τ且不等于0，則在節點n匯聚后，其匯聚后的數據量可表示為

g1(n)=max[g0(m)，g0(n)]+min[g0(m)，g0(n)](1-τ) 。

(7)

根據式(5)和式(7)，可得數據匯聚后的增益為

Δ(m，n)=[g0(m)+g0(n)][E(n，S)-q(e)]-
max[g0(m)，g0(n)]+min[g0(m)，g0(n)](1-τ)E(n，S) 。

(8)

如圖1所示，如果節點n的子節點只有一個節點m，則可以通過式(7)直接計算匯聚增益。

圖1 單節點與多節點數據傳輸鏈路圖

當節點n存在多個子節點時，則匯聚增益數學表達式為

Δ(m1，m2，…，mk，nk)=[g0(m1)+g0(m2)+…+g0(mk)]-
{E(n，S)-[(1-c(m1，m2，…，mk，nk))E(n，S)+q(e)]} 。

(9)

當匯聚增益大于0時，化簡式(9)，可得

(10)

當數據融合度滿足式(10)，數據在任意節點處進行融合時：

(11)

當數據融合度滿足式(11)時，節點將數據直接上傳給Sink節點，不需要進行匯聚處理。由于節點之間對數據融合能力存在一定差異，因此令cmin為數據融合度最小值，cmax為數據融合度最大值。

討論1當cmin

max[g0(m)，g0(n)]+min[g0(m)，g0(n)](1-τ)=(1-cmn)[g0(m)+g0(n)] 。

(12)

計算cmn，可得

(13)

由式(13)可得，數據融合度與距離相關參數成正比。由式(6)可得，當τ=0時，說明兩個節點為正切狀態；當τ<0時，說明兩個節點為相離狀態；當τ>0時，說明兩個節點為相交狀態。因此，在滿足式(10)和式(11)時，可以自適應地判斷出節點是否進行匯聚操作。對于cmin

(14)

利用式(13)和式(14)分別計算出數據融合度和距離相關系數后，對原始子節點n1，n2，…，nk進行迭代更新操作，直至迭代更新所有子節點后，判斷此時數據融合度是否滿足式(10)。如果滿足式(10)，則進行匯聚融合操作；如果不滿足，則不進行匯聚操作。

定理1多節點在進行數據傳輸時，如果沒有在下一跳節點進行融合，那么在后繼節點中，也不會再進行數據融合處理。

證明現以圖2為例進行說明。

圖2 多節點數據傳輸鏈路圖

除根節點之外的節點分為兩類：第1類節點是沿最短路徑將數據信息發送給Sink節點，不考慮匯聚增益；第2類節點則是根據匯聚增益判斷是否進行匯聚處理。設節點集合為M，mi∈M。由于數據并沒有在節點n0處進行融合操作，所以在節點n0處匯聚增益應小于零，即

c(m1，m2，…，mk，nk)E(n0，nk)≤q(e) 。

(15)

mk作為n0的下一跳節點，距目的節點mk的距離長度要小于n0，故E(mk，nk)

c(m1，m2，…，mk，nk)≤c(m1，m2，…，mk，n0) 。

(16)

由此類推，下一跳匯聚節點的數據融合度均小于或等于上一跳節點的數據融合度。因為最外層節點n0尚未進行數據融合，而其他節點的融合度又小于或等于n0融合度。因此，其他節點也不會進行數據融合操作。此時，兩個節點的歐氏距離大于或等于Rc時，數據傳輸過程只能采用多跳方式將數據信息傳至Sink節點。

證明完畢。

2.2 歐氏距離分析

數據在無線傳感器網絡進行融合操作時，往往伴隨著數據壓縮，如數據信息為圖像、音頻、視頻等[17-18]。當傳感器節點采集數據量較大，又在某節點進行數據融合時，其壓縮能耗不能忽略。這是因為數據在壓縮和解壓過程中會消耗較多的節點能量。為了方便地研究問題，筆者認為數據壓縮時所消耗的能量與數據解壓時所消耗的能量相等，即Eco=Ede，壓縮比定義為γ。基于節2.1的分析可以看出，在數據傳輸過程中采用兩種方式進行傳輸：第1種方式先匯聚后傳輸，即數據按照路由規劃將數據傳輸給下一跳節點并進行數據融合，在后繼傳輸過程中，按照前面的處理繼續此操作；第2種方式是數據按照路由規劃的最優路徑將數據以多跳形式直接發送給Sink節點。在此過程中，不需要做數據融合處理。

討論2數據在傳輸過程中，首先要在源節點做壓縮操作，而后將壓縮后的數據傳輸給下一跳節點；當下一跳節點接收到該數據包時要先做解壓操作，再進行融合操作。當數據發送與接收時所消耗的能量大于壓縮與解壓的能量時，此壓縮與解壓操作是有效的；否則是無效的。當壓縮與解壓處于無效時，數據信息不會在下一跳節點進行匯聚，而是將數據以多跳形式直接傳輸給Sink節點。假設從源節點到Sink節點存在N個節點，當數據信息從節點m傳至節點n時，根據式(2)和式(3)計算網絡能耗為

(17)

其中，di表示節點i到相鄰節點之間的距離。

當數據信息在節點m處進行壓縮，在n處進行解壓時，此時網絡能耗為

(18)

當E[(m，n)，d]>Ecd[(m，n)，di]時，數據的壓縮和解壓對整個鏈路才有效，即

(19)

計算di，得

(20)

(21)

根據上述分析可知，當數據進行首次壓縮和解壓時，網絡總能耗為

(22)

(23)

計算上式，可得

(24)

上述討論給出了數據在后繼傳輸路徑中，進行壓縮與解壓以及不被后繼節點進行壓縮與解壓時，任意兩節點之間距離滿足的必要條件。從討論2和討論3中可以看出，ASD-MC算法不僅確保數據傳輸時所需能量最少，同時也實現了傳輸距離的最優設計。在數據傳輸時，ASD-MC算法均衡了全網能量，以匯聚增益值較大的節點完成了數據轉發過程，減少了數據傳輸的跳數，實現了動態實時處理，減少了網絡時延，抑制了節點能量消耗，延長了網絡生存周期。

2.3 ASD-MC算法分析

在滿足全網能耗最少的前提下，如果全網中所有傳感器節點的融合度均達到100%，即完全融合，則cmax=1；數據在通信鏈路中進行傳輸時，數據包的大小始終不會發生改變，數據傳輸鏈路則是以Sink為根節點的最小生成樹(Minimum Spanning Tree，MST)。反之，如果全網中所有傳感器節點的融合度均為零，即零融合，則cmin=0。數據在通信鏈路中進行傳輸時，Sink節點融合后的數據包的大小等于各個節點數據包總量之和，數據傳輸鏈路則是以Sink為根節點的最短路徑樹(Shortest Path Tree，SPT)。一般來說，在無線傳感器網絡數據傳輸過程中，上述兩種極端情況很難出現，數據融合度c介于[0，1]，其ASD-MC算法描述如下：

步驟1 給定無線傳感器網絡G=(V，E)，任意邊集E中存在通信鏈路e=(m，n)；利用式(17)計算在通信鏈路e上傳輸k比特數據時所消耗的網絡能量E[(m，n)，di]。

步驟2 根據式(10)和式(11)計算數據融合度。

① 當數據融合度滿足式(10)，且保證全網節點均達到100%，即cmax=1時，此時全網構成的是以Sink節點為根的最小生成樹MST。

② 當數據融合度滿足式(11)，即cmin=0時，此時全網構成的是以Sink節點為根的最短路徑樹SPT。

步驟3 當數據融合度介于[cmin，cmax]時，根據式(14)和節點距離相關系數τ計算此時的數據融合度。

步驟4 利用式(17)和式(18)判斷鏈路中的數據是否要完成壓縮與解壓過程。

① 當E[(m，n)，d]>Ecd[(m，n)，di]時，要對鏈路中的數據進行壓縮與解壓操作。

② 當E[(m，n)，d]≤Ecd[(m，n)，di]時，除源節點與Sink節點外，數據不在任意節點進行壓縮與解壓操作。

步驟5 在滿足式(20)，數據在傳輸給下一跳節點時，將當前節點與下一跳節點的di以及該節點與下一跳節點的位置存儲在該鏈表中；當數據遍歷完該路徑上所有節點時，該鏈表中的節點集合構成了最小生成路徑。

步驟6 在滿足式(21)時，數據壓縮與解壓過程在源節點與Sink上完成，在其他節點上均不再進行壓縮與解壓操作。數據在源節點上完成壓縮操作后，將數據包沿dv方向傳輸至下一跳節點；此時，鏈表記錄dv以及該節點與下一跳節點的位置信息；當數據遍歷完該路徑上所有節點時，在Sink節點上進行解壓操作后，該鏈表中的節點集合構成了最短生成路徑。

基于上述分析，ASD-MC算法所生成的聚合樹性能介于MST和SPT之間，因此ASD-MC算法適應用于具有不同數據融合度的無線傳感器網絡。ASD-MC算法既兼顧了MST和SPT的特性，又具有自適應數據匯聚能力。在ASD-MC算法中，數據傳輸的下一跳節點將根據數據增益原則，判斷是否對該數據進行匯聚。如果滿足匯聚條件，則對該數據進行匯聚，以減少節點數據的傳輸量，抑制節點能量的消耗；反之，則對該數據選擇最短路徑進行傳輸，以獲取最佳傳輸方式。

3 性能評價

為了進一步驗證ASD-MC算法的性能，實驗采用Matlab2019b作為仿真平臺，參數設定如表1所示。當節點的通信半徑Rc增大時，節點距離相關系數τ也會隨之增大，即τ→1，數據融合方式趨于完全融合；當節點的通信半徑Rc減少時，節點距離相關系數τ也會隨之減少，即τ→0，數據融合方式趨于零融合。因此，τ的取值范圍定義為τ∈[0.2，8]。為了保證數據的可靠性，在數據傳輸過程中，筆者采用無損壓縮方式對數據進行壓縮與解壓處理，利用第2代小波分解的零樹編碼算法(Embedded Zerotree Coding based on Second Generation Wavelets，EZC_SGW)[18]對傳輸數據進行無損壓縮處理，因此數據壓縮比定義為γ∈[6，10]。在仿真實驗中，將ASD-MC算法與QCHBRP[12]和CS-MDGA[13]以及CS-CARDG[14]在網絡能量開銷和平均時延方面進行對比，能量模型采用Heinzelman自由空間和多路衰減模型[19]。

表1 仿真參數說明

3.1 網絡剩余能量

圖3給出了4種算法在不同參數以及不同監測區域作用下的網絡剩余能量對比示意圖。

隨著時間的推移，圖3(a)至圖3(d)的網絡剩余能量均有所下降；而圖3(e)至圖3(f)的則趨于平穩。現以圖3(c)和圖3(f)為例進行說明。圖3(c)是以200 m×200 m作為監測區域，τ=0.4，γ=7。當網絡運行時間在650 s時，ASD-MC算法網絡剩余能量約為1 245 J，QCHBRP算法網絡剩余能量約為1 068 J，CS-MDGA算法網絡剩余能量約為848 J，CS-CARDG算法網絡剩余能量約為635 J；當網絡運行至800 s時，ASD-MC算法網絡剩余能量約為1 155 J，QCHBRP算法網絡剩余能量約為960 J，CS-MDGA算法網絡剩余能量約為740 J，CS-CARDG算法網絡剩余能量約為500 J。從上述分析可以得到，隨著網絡運行時間的增加，4種算法的網絡剩余能量均有所下降，但ASD-MC算法下降幅度小于其他算法。圖3(f)給出了在400 m×400 m監測區域下，τ=0.6，γ=8時，4種算法網絡剩余能量對比示意圖。從圖3(f)可以看出，隨著網絡運行時間的增加，4種算法的網絡剩余能量均趨于平衡，變化的幅度較小。

(a) 200 m×200 m，τ=0.2，γ=6

(d) 400 m×400 m，τ=0.4，γ=7

綜合上述分析，當網絡剩余能量隨著不同情況發生變化時，其主要原因在于ASD-MC算法優先考慮了傳輸數據是否在某節點處發生匯聚。第1種情況，數據未匯聚，即數據在零融合網絡中進行傳輸時，ASD-MC算法不考慮匯聚開銷，則按照最短路徑原則將數據信息從源節點發送至Sink節點；第2種情況，數據完全匯聚，即數據在非零融合網絡中進行傳輸時，ASD-MC算法在考慮匯聚開銷的同時，利用無損壓縮對傳輸數據的長度進行動態調節，以減少傳輸數據量，抑制了節點能量的快速消耗，延長了網絡生存周期。其他算法并沒有考慮匯聚與壓縮等因素，只是依靠節點自身能量完成數據信息的傳輸。因此，在網絡剩余能量對比中，那3種算法的網絡剩余能量均小于ASD-MC算法，其平均數值減少約10.29%。

3.2 網絡時延

圖4給出了4種算法在不同監測區域下的網絡時延對比示意圖。

隨著傳感器節點數量的增加，4種算法的網絡時延也隨之增加，但ASD-MC算法增加幅度最小。現以圖4(a)和圖4(d)為例進行分析。圖4(a)是以200 m×200 m作為監測區域，當傳感器節點數量為120時，ASD-MC算法的網絡時延約為0.09 s，QCHBRP算法的網絡時延約為0.13 s，CS-MDGA算法的網絡時延約為0.16 s，CS-CARDG算法的網絡延時為0.22 s多；當傳感器節點數量為180時，ASD-MC算法的網絡時延約為0.11 s，QCHBRP算法的網絡延時約為0.15 s，CS-MDGA算法的網絡延時約為0.17 s，CS-CARDG算法的網絡延時少于0.23 s。圖4(d)是以400 m×400 m作為監測區域，當傳感器節點數量為1 600時，ASD-MC算法的網絡時延約為0.235 s，QCHBRP算法的網絡延時約為0.263 s，CS-MDGA算法的網絡延時約為0.270 s，CS-CARDG算法的網絡延時約為0.293 s；當傳感器節點數量為1 900時，ASD-MC算法的網絡時延約為0.235 s，QCHBRP算法的網絡延時約為0.263 s，CS-MDGA算法的網絡延時約為0.273 s，CS-CARDG算法的網絡延時約為0.295 s。

綜合上述分析，ASD-MC算法網絡時延優于其他算法的原因在于：隨著傳感器節點數量的增加，將會導致匯聚增益和全網能量開銷E(n，S)隨之增加。ASD-MC算法根據每一跳節點的匯聚增益數值自適應地確定是否進行匯聚。當匯聚開銷過大時，ASD-MC算法可以通過動態調整參數大小來改變路由策略，以減少數據匯聚次數，抑制節點能量的開銷，達到全網節點能量均衡化的目的。在網絡時延對比中，ASD-MC算法網絡時延均小于其他算法的網絡時延，其平均數值減少約12.57%。