一種面向最小能耗自適應(yīng)匯聚路由判定算法

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

(1.西安電子科技大學(xué) 雷達(dá)信號(hào)處理國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2.洛陽(yáng)理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，河南 洛陽(yáng) 471023；3.西安電子科技大學(xué) 信息感知協(xié)同創(chuàng)新中心，陜西 西安 710071)

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

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

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

1 問(wèn)題描述

1.1 網(wǎng)絡(luò)模型

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

融合后的數(shù)據(jù)量應(yīng)不大于節(jié)點(diǎn)m和節(jié)點(diǎn)n的原始數(shù)據(jù)量之和，不小于節(jié)點(diǎn)m和節(jié)點(diǎn)n中的任意節(jié)點(diǎn)的原始數(shù)據(jù)：

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

(1)

其中，g0(m)和g0(n)表示數(shù)據(jù)融合前的數(shù)據(jù)量；g1(n)表示數(shù)據(jù)在節(jié)點(diǎn)n處融合后的數(shù)據(jù)量。

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

(2)

(3)

其中，ETx表示發(fā)射模塊消耗的能耗；ERx表示接收模塊消耗的能耗；Eelec表示發(fā)送或接收1 bit數(shù)據(jù)量時(shí)所消耗的能量；Efu表示節(jié)點(diǎn)進(jìn)行融合時(shí)所消耗的能量；Zdata_pa表示融合數(shù)據(jù)包的總量；Eda表示融合1 bit數(shù)據(jù)量所消耗的能量；k表示發(fā)送或接收的數(shù)據(jù)量；εfs，εmp是功率放大時(shí)的能耗系數(shù)。

1.2 匯聚增益模型

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

(4)

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

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

(5)

當(dāng)傳感器節(jié)點(diǎn)通信半徑為感知半徑的2倍時(shí)，記作Rc=2Rs。當(dāng)任意兩節(jié)點(diǎn)之間歐氏距離do大于Rc時(shí)，則兩個(gè)節(jié)點(diǎn)之間相關(guān)參數(shù)為0；當(dāng)任意兩節(jié)點(diǎn)之間歐氏距離d小于或等于Rc時(shí)，則兩個(gè)節(jié)點(diǎn)之間的相關(guān)參數(shù)為τ，數(shù)學(xué)表示式為

(6)

2 解決方案

2.1 融合度分析

基于對(duì)匯聚增益模型的分析，節(jié)點(diǎn)m和n之間的距離相關(guān)參數(shù)為τ且不等于0，則在節(jié)點(diǎn)n匯聚后，其匯聚后的數(shù)據(jù)量可表示為

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

(7)

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

Δ(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所示，如果節(jié)點(diǎn)n的子節(jié)點(diǎn)只有一個(gè)節(jié)點(diǎn)m，則可以通過(guò)式(7)直接計(jì)算匯聚增益。

圖1 單節(jié)點(diǎn)與多節(jié)點(diǎn)數(shù)據(jù)傳輸鏈路圖

當(dāng)節(jié)點(diǎn)n存在多個(gè)子節(jié)點(diǎn)時(shí)，則匯聚增益數(shù)學(xué)表達(dá)式為

Δ(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)

當(dāng)匯聚增益大于0時(shí)，化簡(jiǎn)式(9)，可得

(10)

當(dāng)數(shù)據(jù)融合度滿足式(10)，數(shù)據(jù)在任意節(jié)點(diǎn)處進(jìn)行融合時(shí)：

(11)

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

討論1當(dāng)cmin

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

(12)

計(jì)算cmn，可得

(13)

由式(13)可得，數(shù)據(jù)融合度與距離相關(guān)參數(shù)成正比。由式(6)可得，當(dāng)τ=0時(shí)，說(shuō)明兩個(gè)節(jié)點(diǎn)為正切狀態(tài)；當(dāng)τ<0時(shí)，說(shuō)明兩個(gè)節(jié)點(diǎn)為相離狀態(tài)；當(dāng)τ>0時(shí)，說(shuō)明兩個(gè)節(jié)點(diǎn)為相交狀態(tài)。因此，在滿足式(10)和式(11)時(shí)，可以自適應(yīng)地判斷出節(jié)點(diǎn)是否進(jìn)行匯聚操作。對(duì)于cmin

(14)

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

定理1多節(jié)點(diǎn)在進(jìn)行數(shù)據(jù)傳輸時(shí)，如果沒(méi)有在下一跳節(jié)點(diǎn)進(jìn)行融合，那么在后繼節(jié)點(diǎn)中，也不會(huì)再進(jìn)行數(shù)據(jù)融合處理。

證明 現(xiàn)以圖2為例進(jìn)行說(shuō)明。

圖2 多節(jié)點(diǎn)數(shù)據(jù)傳輸鏈路圖

除根節(jié)點(diǎn)之外的節(jié)點(diǎn)分為兩類：第1類節(jié)點(diǎn)是沿最短路徑將數(shù)據(jù)信息發(fā)送給Sink節(jié)點(diǎn)，不考慮匯聚增益；第2類節(jié)點(diǎn)則是根據(jù)匯聚增益判斷是否進(jìn)行匯聚處理。設(shè)節(jié)點(diǎn)集合為M，mi∈M。由于數(shù)據(jù)并沒(méi)有在節(jié)點(diǎn)n0處進(jìn)行融合操作，所以在節(jié)點(diǎn)n0處匯聚增益應(yīng)小于零，即

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

(15)

mk作為n0的下一跳節(jié)點(diǎn)，距目的節(jié)點(diǎn)mk的距離長(zhǎng)度要小于n0，故E(mk，nk)

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

(16)

由此類推，下一跳匯聚節(jié)點(diǎn)的數(shù)據(jù)融合度均小于或等于上一跳節(jié)點(diǎn)的數(shù)據(jù)融合度。因?yàn)樽钔鈱庸?jié)點(diǎn)n0尚未進(jìn)行數(shù)據(jù)融合，而其他節(jié)點(diǎn)的融合度又小于或等于n0融合度。因此，其他節(jié)點(diǎn)也不會(huì)進(jìn)行數(shù)據(jù)融合操作。此時(shí)，兩個(gè)節(jié)點(diǎn)的歐氏距離大于或等于Rc時(shí)，數(shù)據(jù)傳輸過(guò)程只能采用多跳方式將數(shù)據(jù)信息傳至Sink節(jié)點(diǎn)。

證明完畢。

2.2 歐氏距離分析

數(shù)據(jù)在無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行融合操作時(shí)，往往伴隨著數(shù)據(jù)壓縮，如數(shù)據(jù)信息為圖像、音頻、視頻等[17-18]。當(dāng)傳感器節(jié)點(diǎn)采集數(shù)據(jù)量較大，又在某節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合時(shí)，其壓縮能耗不能忽略。這是因?yàn)閿?shù)據(jù)在壓縮和解壓過(guò)程中會(huì)消耗較多的節(jié)點(diǎn)能量。為了方便地研究問(wèn)題，筆者認(rèn)為數(shù)據(jù)壓縮時(shí)所消耗的能量與數(shù)據(jù)解壓時(shí)所消耗的能量相等，即Eco=Ede，壓縮比定義為γ?；诠?jié)2.1的分析可以看出，在數(shù)據(jù)傳輸過(guò)程中采用兩種方式進(jìn)行傳輸：第1種方式先匯聚后傳輸，即數(shù)據(jù)按照路由規(guī)劃將數(shù)據(jù)傳輸給下一跳節(jié)點(diǎn)并進(jìn)行數(shù)據(jù)融合，在后繼傳輸過(guò)程中，按照前面的處理繼續(xù)此操作；第2種方式是數(shù)據(jù)按照路由規(guī)劃的最優(yōu)路徑將數(shù)據(jù)以多跳形式直接發(fā)送給Sink節(jié)點(diǎn)。在此過(guò)程中，不需要做數(shù)據(jù)融合處理。

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

(17)

其中，di表示節(jié)點(diǎn)i到相鄰節(jié)點(diǎn)之間的距離。

當(dāng)數(shù)據(jù)信息在節(jié)點(diǎn)m處進(jìn)行壓縮，在n處進(jìn)行解壓時(shí)，此時(shí)網(wǎng)絡(luò)能耗為

(18)

當(dāng)E[(m，n)，d]>Ecd[(m，n)，di]時(shí)，數(shù)據(jù)的壓縮和解壓對(duì)整個(gè)鏈路才有效，即

(19)

計(jì)算di，得

(20)

(21)

根據(jù)上述分析可知，當(dāng)數(shù)據(jù)進(jìn)行首次壓縮和解壓時(shí)，網(wǎng)絡(luò)總能耗為

(22)

(23)

計(jì)算上式，可得

(24)

上述討論給出了數(shù)據(jù)在后繼傳輸路徑中，進(jìn)行壓縮與解壓以及不被后繼節(jié)點(diǎn)進(jìn)行壓縮與解壓時(shí)，任意兩節(jié)點(diǎn)之間距離滿足的必要條件。從討論2和討論3中可以看出，ASD-MC算法不僅確保數(shù)據(jù)傳輸時(shí)所需能量最少，同時(shí)也實(shí)現(xiàn)了傳輸距離的最優(yōu)設(shè)計(jì)。在數(shù)據(jù)傳輸時(shí)，ASD-MC算法均衡了全網(wǎng)能量，以匯聚增益值較大的節(jié)點(diǎn)完成了數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程，減少了數(shù)據(jù)傳輸?shù)奶鴶?shù)，實(shí)現(xiàn)了動(dòng)態(tài)實(shí)時(shí)處理，減少了網(wǎng)絡(luò)時(shí)延，抑制了節(jié)點(diǎn)能量消耗，延長(zhǎng)了網(wǎng)絡(luò)生存周期。

2.3 ASD-MC算法分析

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

步驟1 給定無(wú)線傳感器網(wǎng)絡(luò)G=(V，E)，任意邊集E中存在通信鏈路e=(m，n)；利用式(17)計(jì)算在通信鏈路e上傳輸k比特?cái)?shù)據(jù)時(shí)所消耗的網(wǎng)絡(luò)能量E[(m，n)，di]。

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

① 當(dāng)數(shù)據(jù)融合度滿足式(10)，且保證全網(wǎng)節(jié)點(diǎn)均達(dá)到100%，即cmax=1時(shí)，此時(shí)全網(wǎng)構(gòu)成的是以Sink節(jié)點(diǎn)為根的最小生成樹(shù)MST。

② 當(dāng)數(shù)據(jù)融合度滿足式(11)，即cmin=0時(shí)，此時(shí)全網(wǎng)構(gòu)成的是以Sink節(jié)點(diǎn)為根的最短路徑樹(shù)SPT。

步驟3 當(dāng)數(shù)據(jù)融合度介于[cmin，cmax]時(shí)，根據(jù)式(14)和節(jié)點(diǎn)距離相關(guān)系數(shù)τ計(jì)算此時(shí)的數(shù)據(jù)融合度。

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

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

② 當(dāng)E[(m，n)，d]≤Ecd[(m，n)，di]時(shí)，除源節(jié)點(diǎn)與Sink節(jié)點(diǎn)外，數(shù)據(jù)不在任意節(jié)點(diǎn)進(jìn)行壓縮與解壓操作。

步驟5 在滿足式(20)，數(shù)據(jù)在傳輸給下一跳節(jié)點(diǎn)時(shí)，將當(dāng)前節(jié)點(diǎn)與下一跳節(jié)點(diǎn)的di以及該節(jié)點(diǎn)與下一跳節(jié)點(diǎn)的位置存儲(chǔ)在該鏈表中；當(dāng)數(shù)據(jù)遍歷完該路徑上所有節(jié)點(diǎn)時(shí)，該鏈表中的節(jié)點(diǎn)集合構(gòu)成了最小生成路徑。

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

基于上述分析，ASD-MC算法所生成的聚合樹(shù)性能介于MST和SPT之間，因此ASD-MC算法適應(yīng)用于具有不同數(shù)據(jù)融合度的無(wú)線傳感器網(wǎng)絡(luò)。ASD-MC算法既兼顧了MST和SPT的特性，又具有自適應(yīng)數(shù)據(jù)匯聚能力。在ASD-MC算法中，數(shù)據(jù)傳輸?shù)南乱惶?jié)點(diǎn)將根據(jù)數(shù)據(jù)增益原則，判斷是否對(duì)該數(shù)據(jù)進(jìn)行匯聚。如果滿足匯聚條件，則對(duì)該數(shù)據(jù)進(jìn)行匯聚，以減少節(jié)點(diǎn)數(shù)據(jù)的傳輸量，抑制節(jié)點(diǎn)能量的消耗；反之，則對(duì)該數(shù)據(jù)選擇最短路徑進(jìn)行傳輸，以獲取最佳傳輸方式。

3 性能評(píng)價(jià)

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

表1 仿真參數(shù)說(shuō)明

3.1 網(wǎng)絡(luò)剩余能量

圖3給出了4種算法在不同參數(shù)以及不同監(jiān)測(cè)區(qū)域作用下的網(wǎng)絡(luò)剩余能量對(duì)比示意圖。

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

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

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

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

3.2 網(wǎng)絡(luò)時(shí)延

圖4給出了4種算法在不同監(jiān)測(cè)區(qū)域下的網(wǎng)絡(luò)時(shí)延對(duì)比示意圖。

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

綜合上述分析，ASD-MC算法網(wǎng)絡(luò)時(shí)延優(yōu)于其他算法的原因在于：隨著傳感器節(jié)點(diǎn)數(shù)量的增加，將會(huì)導(dǎo)致匯聚增益和全網(wǎng)能量開(kāi)銷E(n，S)隨之增加。ASD-MC算法根據(jù)每一跳節(jié)點(diǎn)的匯聚增益數(shù)值自適應(yīng)地確定是否進(jìn)行匯聚。當(dāng)匯聚開(kāi)銷過(guò)大時(shí)，ASD-MC算法可以通過(guò)動(dòng)態(tài)調(diào)整參數(shù)大小來(lái)改變路由策略，以減少數(shù)據(jù)匯聚次數(shù)，抑制節(jié)點(diǎn)能量的開(kāi)銷，達(dá)到全網(wǎng)節(jié)點(diǎn)能量均衡化的目的。在網(wǎng)絡(luò)時(shí)延對(duì)比中，ASD-MC算法網(wǎng)絡(luò)時(shí)延均小于其他算法的網(wǎng)絡(luò)時(shí)延，其平均數(shù)值減少約12.57%。

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

(b) 400 m×40 m，τ=0.2，γ=6

4 總 結(jié)

針對(duì)信道內(nèi)數(shù)據(jù)沖突與碰撞等不穩(wěn)定因素，提出了一種面向最小能耗自適應(yīng)匯聚路由判定算法。ASD-MC算法首先分析了匯聚增益和數(shù)據(jù)融合度之間的函數(shù)關(guān)系，給出了距離相關(guān)參數(shù)與通信半徑之間的比例關(guān)系；而后討論了數(shù)據(jù)融合度介于最小值與最大值之間的函數(shù)關(guān)系，證明了在下一跳節(jié)點(diǎn)非融合時(shí)的后繼節(jié)點(diǎn)中，也不會(huì)再進(jìn)行數(shù)據(jù)融合處理。利用能量關(guān)系，討論了壓縮與解壓、連續(xù)性傳輸?shù)姆菈嚎s與非解壓時(shí)的任意兩節(jié)點(diǎn)距離的函數(shù)關(guān)系，分析了ASD-MC算法的實(shí)現(xiàn)過(guò)程與方法；最后，通過(guò)仿真實(shí)驗(yàn)與其他算法在網(wǎng)絡(luò)剩余能量和網(wǎng)絡(luò)時(shí)延上進(jìn)行比對(duì)實(shí)驗(yàn)，驗(yàn)證了ASD-MC算法的有效性和實(shí)效性。

未來(lái)工作主要集中在借助于壓縮感知理論實(shí)現(xiàn)備份路由的優(yōu)化以及如何提高不可靠鏈路對(duì)數(shù)據(jù)重構(gòu)精度等方面。