基于稀疏投影排角分區(qū)的無線傳感器網(wǎng)絡(luò)路由協(xié)議

賈 瓊，喬建華

(太原科技大學 電子信息工程學院，太原 030024)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是一種在其檢測區(qū)域內(nèi)收集數(shù)據(jù)信息的通信網(wǎng)絡(luò)，其主要由通信基站和大量微型傳感器構(gòu)成，能夠快速收集自身監(jiān)測范圍內(nèi)的相關(guān)數(shù)據(jù)，并傳送到相應(yīng)基站中進行處理[1]。因其中的微型傳感器體積很小，不能攜帶很多電池，且更換電池或二次部署十分困難，故其能量有限不可再生，因此如何降低網(wǎng)絡(luò)能耗并延長網(wǎng)絡(luò)生命周期成為關(guān)鍵問題。無線傳感器網(wǎng)絡(luò)中大部分能量在通信部分被消耗，其中信號的發(fā)送和接收的傳輸過程中會消耗大部分能量。如果在傳感器收集信息時充分利用壓縮感知(Compressed Sensing，CS)理論，將能幫助系統(tǒng)減少數(shù)據(jù)傳輸量，進而減少能量的消耗量，使得利用率有顯著的提升，有利于延長網(wǎng)絡(luò)的使用壽命。

雖然利用低功耗自適應(yīng)集簇分層協(xié)議(Low Energy Adaptive Clustering Hierarchy，LEACH)[2]時，由于采用了周期輪換機制，簇頭的選擇只需少量節(jié)點，但簇頭節(jié)點在與匯聚節(jié)點通信時是直接的，因此其能量消耗較快[3]。鏈狀傳輸(Power-Efficient Gathering in Sensor Information System，PEGASIS)[4]協(xié)議中，每個節(jié)點向距離最近的鄰居節(jié)點傳輸信息，數(shù)據(jù)的傳輸方式為點對點，節(jié)點數(shù)據(jù)信息最終被傳送到匯聚節(jié)點，但該協(xié)議具有較長的時延從而消耗更多的能量[5]。兩種方法各有所長，都將無線傳感器網(wǎng)絡(luò)生命周期延長，但在另一些指標方面都有所降低，例如節(jié)點能耗或者時延。本文提出了一種新的基于角度排序分區(qū)的無線傳感器網(wǎng)絡(luò)路由協(xié)議。該協(xié)議通過對監(jiān)控區(qū)域進行劃分，使每個區(qū)域中的傳感器節(jié)點與稀疏矩陣中各非零元素相對應(yīng)進行壓縮數(shù)據(jù)收集，并使用改進精英蟻群算法[6]在每個區(qū)域中尋找節(jié)一條以匯聚節(jié)點為終點且經(jīng)過該區(qū)域全部節(jié)點的最短路徑，因此其可以減少在傳輸路徑上的能耗。精英蟻群算法相比隨機游走算法更能快速直接找到每個分區(qū)節(jié)點的最優(yōu)路徑，而結(jié)合精英蟻群算法的分區(qū)投影和隨機投影分簇法相比，前者的能量利用率更高，網(wǎng)絡(luò)使用壽命得到延長。

圖1 多跳路由壓縮數(shù)據(jù)收集流程圖Fig.1 Schematic diagram of compressive data gathering in a multi-hop routing

1 分區(qū)原理及精英蟻群算法

1.1 壓縮感知基本理論

根據(jù)壓縮感知[7-8]理論在采集可壓縮信號或者稀疏信號時，不必使用通常的高頻率采樣，其采樣頻率可以遠低于Nyquist頻率，只需在后期利用非線性重建算法便能將所采集的信號完美恢復[9]。設(shè)x為N維稀疏信號，利用N×N維稀疏變換矩陣Ψ可將x分解為:

x=Ψθ

(1)

其中：θ是K階稀疏的N×1維列向量，也就是說θ中非零項有K個，且滿足K?N.假設(shè)M×N維度的投影矩陣(或觀測矩陣、測量矩陣)Φ，通過對稀疏信號在測量矩陣Φ下進行投影，即可獲得M個觀測值y，且有M?N，即:

y=Φx=ΦΨθ=Tθ

(2)

因此：T命名為傳感矩陣；y稱之為M×1維的列向量，為測量值。

由壓縮感知理論可得，如果傳感矩陣T符合有限等距性質(zhì)(Restricted Isometry Property，RIP)，那么式(2)存在確定解。假設(shè)存在δ∈(0，1)使所有K階稀疏信號θ滿足下式:

(3)

(4)

1.2 分區(qū)原理

通過壓縮感知理論可得，若測量矩陣Φ為M×N維的矩陣，x是N×1維的列向量，可得：

(5)

(6)

通過式(5)可以得出，針對N個節(jié)點xj(j=1，2，…N)，可將Φ中每行元素與x進行一系列乘加運算，最終獲得M個測量結(jié)果。由于測量矩陣Φ為稀疏矩陣，即Φ的每行會出現(xiàn)很多0元素，將Φ的每行作為無線傳感器網(wǎng)絡(luò)每條路徑的投影，可將Φ分為M塊，每塊為1×N的矩陣，且每塊包含0元素但不全為0，如下：

Φ=

(7)

因每個塊矩陣中包含很多0元素，故每個塊矩陣與x相乘，只需要將塊矩陣中的非零元素與x中對應(yīng)的數(shù)據(jù)相乘再傳輸，可大大減少數(shù)據(jù)的傳輸量，節(jié)省網(wǎng)絡(luò)能消。而每個塊矩陣對應(yīng)分區(qū)后的每條路徑，路徑將數(shù)據(jù)傳輸?shù)絊ink 節(jié)點，M條路徑中所有信息相加后得到最終測量值。上述傳感矩陣可結(jié)合測量值來重構(gòu)信號數(shù)據(jù)。如果只需要其中一部分數(shù)據(jù)，那么在重構(gòu)時只需取其中某些塊即可。測量矩陣是隨機的，所以部分隨機矩陣依舊滿足 RIP，重構(gòu)信號時仍可用。

1.3 精英蟻群算法

蟻群算法(Ant Clony Optimization，ACO)[10]是由意大利學者Dorigo M等人于1991年首先提出并首先使用在解決旅行商問題(Traveling Saleman Problem，TSP)上。蟻群算法的基本原理來源于自然界螞蟻覓食的最短路徑原理：螞蟻在尋找食物源時，能在其走過的路徑上釋放一種螞蟻特有的分泌物即信息素，使得一定范圍內(nèi)的其他螞蟻能夠察覺到其分泌的信息素并由此信息素濃度影響他們以后的行為。當一些路徑上通過的螞蟻越來越多時，其留下的信息素也越來越多，以致信息素濃度增大，所以螞蟻選擇選該路徑的概率也越高，從而更增加了該路徑的信息素強度。蟻群算法如圖2所示。

圖2 蟻群算法示意圖Fig.2 Schematic diagram of the ant colony algorithm

精英蟻群算法是對蟻群算法的改進，其精英策略(Elitist Strategy)的基本思想是：在每次循環(huán)結(jié)束后對所有已經(jīng)發(fā)現(xiàn)的最優(yōu)解給予額外的信息素增強，即強化找到優(yōu)于當前最優(yōu)路徑的螞蟻對信息素濃度的影響，同時消減找到差于當前最優(yōu)路徑的螞蟻對信息素濃度的影響，其目的是為了使到目前為止所找出的最優(yōu)解在下一次循環(huán)中對螞蟻更具有吸引力[11]。引入精英策略以后，收斂速度明顯加快，但是復雜度并沒有增加，仍然等同于經(jīng)典蟻群算法。

2 基于位置的排角分區(qū)方法

2.1 分區(qū)

本文提出一種角度排序分區(qū)法，其建立在節(jié)點的空間位置基礎(chǔ)上，適用于感器節(jié)點隨機分布網(wǎng)絡(luò)。為均勻分布投影節(jié)點，在劃分監(jiān)測區(qū)域時，每個被劃分的區(qū)中節(jié)點個數(shù)相等。所有節(jié)點均為投影節(jié)點，與收集到的數(shù)據(jù)進行加權(quán)處理，然后依次傳給下一節(jié)點，直到傳送到Sink節(jié)點。具體的實施過程如下：

1)確定分區(qū)數(shù)。

2)根據(jù)每個節(jié)點與Sink節(jié)點之間連線與橫軸的角度，依次將各角度按照從小到大的方式進行排序。

3)根據(jù)分區(qū)數(shù)確定每個區(qū)域內(nèi)的節(jié)點個數(shù)，并根據(jù)各節(jié)點的角度找到對應(yīng)節(jié)點。

4)在每個區(qū)域?qū)ふ覀鬏斣搮^(qū)所有節(jié)點數(shù)據(jù)的最優(yōu)路徑。

5)將數(shù)據(jù)投影到節(jié)點上，依次進行乘加，并送至Sink節(jié)點，然后利用上述重構(gòu)算法來恢復原始信號數(shù)據(jù)。

6)回到步驟(1)，開始新的投影重構(gòu)。

2.2 分區(qū)數(shù)目的確定

圖 3 所示為本文在計算過程所采用的網(wǎng)絡(luò)信道模型[12]。

圖3 網(wǎng)絡(luò)信道模型Fig．3 Network channel model

假設(shè)在C×C正方形區(qū)域內(nèi)隨機分布著N個傳感器節(jié)點，并且所有節(jié)點在初始時刻能量儲備是相同的。將正方形區(qū)域劃分為M個子區(qū)域，使每個區(qū)域內(nèi)節(jié)點數(shù)相同，則每個區(qū)域中包含N/M個節(jié)點。假設(shè)每個節(jié)點每跳的傳輸距離為d，造成能量消耗的因素主要有三方面：對上一節(jié)點成員信息進行接收、融合接收到的數(shù)據(jù)、將融合之后的數(shù)據(jù)傳遞到下一個節(jié)點。

2.2.1 能量模型

本文將采用文獻[13]中的二次衰落模型對節(jié)點所造成的能量消耗進行闡述，每個節(jié)點在傳輸信號時，其所消耗的能量與信號傳輸距離之間的關(guān)系如式(8)所示。

Etransmit=kEelect+kEfsd2

(8)

其中：k表示被傳輸數(shù)據(jù)的信息位，單位為bit；d表示節(jié)點間距離；Eelect為在發(fā)射電路或接收電路中處理單位數(shù)據(jù)所消耗的能量；Efs表示耗散能量，其受傳輸信號的模型會影響。

此時每個節(jié)點在接收數(shù)據(jù)時，其消耗的能量由式(9)計算。

Erecieve=kEelect

(9)

此時每個節(jié)點在融合數(shù)據(jù)時，其消耗的能量由式(10)計算。

Efusion=kEDA

(10)

式中：EDA為數(shù)據(jù)融合的能量消耗。

假設(shè)數(shù)據(jù)從某一個節(jié)點發(fā)送到Sink節(jié)點時，其經(jīng)過了x個節(jié)點，那么信號整個傳輸過程消耗的能量計算過程如式(11)所示。

Enode-x=(x+1)Etransmit(k，di)(i=1，2，…x+1)+

xErecieve+xEfusion=(x+1)kEelect+

(11)

由式(11)可知，如果數(shù)據(jù)長度k不變，那么數(shù)據(jù)傳輸過程中主要在發(fā)送信號、接受信號以及最終的融合處理這三部分消耗能量，而影響能量消耗的因素有兩部分：

1)由經(jīng)過的節(jié)點數(shù)x決定的對數(shù)據(jù)進行處理的能量消耗(2x+1)kEelect；

2.2.2 分區(qū)數(shù)目的確定

一條路徑有N/M個節(jié)點，假設(shè)路徑中兩兩節(jié)點間距離均值為d，則一條路徑的能量消耗如式(12)所示。

(12)

M個區(qū)域中M條路徑的總能耗如式(13)所示。

(13)

對Etotal求導，得到最優(yōu)分區(qū)數(shù)為：

(14)

3 仿真

用 Matlab 作為仿真工具，在尋找每個區(qū)域的路徑時用蟻群算法和隨機游走算法進行對比，并且用新路由協(xié)議與LEACH協(xié)議進行性能比較，從死亡節(jié)點數(shù)量對比得出協(xié)議性能。表1給出本次仿真的主要參數(shù)。

表1 仿真數(shù)據(jù)(場景1、場景2)Tab.1 Simulation data (scenario 1，scenario 2)

3.1 仿真研究

在進行仿真時，針對無線傳感器器網(wǎng)絡(luò)以及節(jié)點所提出的假設(shè)如下：

1)在系統(tǒng)所監(jiān)測的區(qū)域中，傳感器節(jié)點的分布均隨即且均勻。

2)傳感器節(jié)點都是靜止的。

3)Sink節(jié)點位置固定在區(qū)域某一處。

4)Sink節(jié)點存儲和計算能力較強，其能量和存儲容量不受限。

5)節(jié)點自己無法測量到自身位置信息。

6)節(jié)點具有相同而通信能力。

7)每個節(jié)點能量受限且在融合單位數(shù)據(jù)上對能量的消耗是相同的。

8)在檢測范圍內(nèi)根據(jù)單位面積所檢測的數(shù)據(jù)量相同。

3.2 仿真分析

仿真過程中，參數(shù)設(shè)置如參數(shù)表。正方形區(qū)域為100×100，其中節(jié)點總數(shù)N為100個，共劃分為M≈8.47區(qū)域，由于分區(qū)數(shù)需為整數(shù)，設(shè)計的稀疏投影矩陣每行中非零元素的個數(shù)相同，且每個區(qū)節(jié)點個數(shù)相同且節(jié)點個數(shù)不宜太少，故在此取M=5，則每個區(qū)的節(jié)點個數(shù)N/M=20.

將檢測區(qū)域內(nèi)的節(jié)點按照上述方法計算得到分區(qū)數(shù)后進行分區(qū)如下。圖4(a)是分區(qū)后，每個區(qū)由隨機游走算法找到的5條路徑。圖4(b)是分割區(qū)域后由精英蟻群算法找到的每個區(qū)的路徑。

圖4 各區(qū)域的路徑圖Fig.4 Road map of each area

從路徑圖以及路徑長度對表均可以看出，通過隨機游走尋找到的路徑并不能有效減少數(shù)據(jù)傳輸?shù)穆窂?，故其能量消耗也不能有效減少，而通過精英蟻群算法找到的路徑相對比隨機游走找的的路徑要更為簡短，更能減少數(shù)據(jù)傳輸中的能耗。

表2 路徑長度對比表Tab.2 Path length comparison table

圖5即根據(jù)均勻分區(qū)的投影以及隨機分簇投影兩種方法針對節(jié)點死亡數(shù)所進行的對比圖。

通過圖5可知，在網(wǎng)絡(luò)運行的初期，死亡節(jié)點出現(xiàn)在均勻分區(qū)的時間就比基于隨機分簇投影出現(xiàn)死亡節(jié)點的時間晚，在網(wǎng)絡(luò)的繼續(xù)運行中，基于均勻分區(qū)的死亡節(jié)點數(shù)都比基于隨機分簇的死亡節(jié)點數(shù)少，但隨著網(wǎng)路的運行，二者之間的差距越來越小，在運行300輪之后，二者的死亡節(jié)點數(shù)均達到90%，可認為網(wǎng)絡(luò)基本癱瘓。

圖5 基于均勻分區(qū)和隨機分簇投影的WSN死亡節(jié)點數(shù)比較Fig.5 Comparison of WSN dead nodes based on uniform partitioning and random clustering projection

假設(shè)正方形區(qū)域為200×200，其中共有400個節(jié)點，M≈16.94，并取M≈16，則每個區(qū)的節(jié)點個數(shù)N/M=25.圖6為其由蟻群算法找到的最優(yōu)路徑圖。

圖6 200×200區(qū)域內(nèi)蟻群算法找到的最優(yōu)路徑圖Fig.6 Optimal path map found by ant colony algorithm in 200×200 area

圖7為在該場景下兩種算法的節(jié)點死亡情況對比圖。

圖7 200×200區(qū)域基于均勻分區(qū)和隨機分簇投影的WSN死亡節(jié)點數(shù)比較Fig.7 Comparison of WSN dead nodes based on uniform partitioning and random clustering projection in 200×200 region

由圖7可以看出，在200×200區(qū)域內(nèi)，隨著網(wǎng)路運行到90輪附近，二種方式的死亡節(jié)點數(shù)幾乎一致，在運行到160輪之時，分簇的死亡節(jié)點數(shù)開始比分區(qū)少，說明此時分區(qū)不再具有優(yōu)勢。

3.3 均勻投影的壓縮數(shù)據(jù)收集

壓縮數(shù)據(jù)收集主要步驟如下:

1)根據(jù)網(wǎng)絡(luò)參數(shù)，確定劃分區(qū)域的數(shù)量，并以此劃分監(jiān)測區(qū)域。

2)在每個區(qū)域內(nèi)利用蟻群算法找到經(jīng)過所有節(jié)點的最優(yōu)路徑。

3)根據(jù)CS理論計算節(jié)點數(shù)據(jù)和稀疏矩陣加權(quán)值，并通過一跳或多跳方式送到Sink節(jié)點。

4)經(jīng)過M次傳輸，Sink 節(jié)點將所有獲得數(shù)據(jù)相加，由此得到M個測量值。然后將測量值代入算法，可以重構(gòu)得到原始信號數(shù)據(jù)。

4 結(jié)語

提出了一種壓縮數(shù)據(jù)收集方法，其建立在排角分區(qū)投影基礎(chǔ)上，能夠解決隨投影節(jié)點機帶來的問題，同時降低能耗。該方法中每個區(qū)域節(jié)點數(shù)量相同，確保了每個區(qū)域投影節(jié)點分布均勻。最后通過仿真分析，發(fā)現(xiàn)該方法比分簇方法在能量消耗和網(wǎng)絡(luò)運行等方面更具優(yōu)勢，延長了網(wǎng)絡(luò)使用壽命。未來工作將進一步完善所提出的路徑協(xié)議，并考慮考相鄰區(qū)域內(nèi)的邊界點節(jié)點位置，有可能部分節(jié)點與所屬區(qū)域內(nèi)節(jié)點的距離較遠但卻距相鄰區(qū)域內(nèi)邊界節(jié)點較近，那么該節(jié)點即所需重新考慮分區(qū)的存在爭議的邊界節(jié)點，對存在爭議的鄰居節(jié)點考慮具體該如何重新分區(qū)問題做進行進一步研究。