一種改進區域生長法的WSN數據采集算法研究

應可珍,周賢年,毛科技,陳慶章

1(浙江工業大學 計算機科學與技術學院,杭州 310014) 2(浙江財經大學 東方學院,浙江 海寧 314408)

1 引 言

無線傳感器網絡的主要功能是數據采集,在大規模的多跳自組織傳感器網絡中,大量的數據被采集和轉發,導致傳感器節點消耗大量能量而使得傳感器網絡過早死亡.目前的研究主要通過在WSN中進行數據融合從而降低數據冗余量,減少WSN能量消耗.如參考文獻[1]提出了一種多稀疏基分簇壓縮感知的WSN數據融合方法,該方法首先基于多稀疏基對WSN網絡進行分簇,然后選擇能力強的節點出任簇首,在簇首中進行數據融合,最終將融合后的數據發送至Sink節點.文獻[2]提出了一種誤差可控的WSN數據融合算法,該方法在基于WSN分簇的條件下,傳感器節點根據歷史數據動態調整傳輸閾值,實現有效控制數據融合的誤差并減少了網絡中大量的冗余數據.文獻[3]提出了一種基于異常數據驅動的WSN簇內數據融合方法,該方法首先對節點進行分簇,簇首節點判斷是否出現異常數據,當出現異常數據時,將該數據傳輸至Sink節點.文獻[4]提出一種數據融合方法,該方法通過貝葉斯估計與聚類方法將誤差數據進行排除提高融合后數據的準確性,融合后網絡中減少了大量的冗余數據.文獻[5-9]都研究了利用數據融合方法減少傳感器網絡中的數據量從而節約網絡的能耗.

目前在降低傳感器網絡冗余數據量方面的研究,大部分的做法是將傳感器網絡進行分簇,然后簇首節點進行簇內數據融合,最終將融合后的數據發送至Sink節點[10,11],但是這些研究需要傳感器網絡中所有的節點都需要進行數據采集且每次采集數據后簇首節點都需要進行數據融合,導致簇首節點能量和傳感器網絡的平均能量消耗過快.經過分析傳感器網絡采集的數據在小范圍內冗余情況比較嚴重,即小范圍內的采集數據是相關聯的,如果能夠將監測區域劃分為若干個小范圍區域,而每個區域內采集的數據都比較接近,則可在每個區域中選擇一個代表節點進行數據采集,關閉小范圍區域內其他傳感器節點,從而能夠大幅降低傳感器網絡冗余數據的采集.在圖像分割中,區域生長算法能夠較好的完成相近像素區域的劃分,因此本文對區域生長算法進行改進,并提出一種改進區域生長法的WSN數據采集算法,該算法首先在網絡中隨機的選取種子節點,然后利用區域生長法將傳感器網絡分割為若干子區域[12-15],每個子區域中傳感器節點采集的數據相似性極高,接著在子區域中選擇代表節點,最后將代表節點采集的數據發送至Sink節點,完成數據采集.

2 傳感器網絡假設與定義

2.1 相關假設

1)傳感器網絡中節點的位置已經通過GPS、WSN定位等方法獲取,且在小范圍內,傳感器節點采集的數值大小接近.如無線傳感器網絡采集樹林中的溫度,在小范圍內溫度值都是非常接近的.

2)傳感器網絡中所有節點同構,每個節點的初始能量相同且都為E0.

3)本文提出的數據采集算法需要變更路由,但這不是本文研究的重點,假設無線傳感器網絡拓撲結構變化時,能夠自行重新組織路由.

4)本文將N個傳感器節點均勻部署在一個長為L,寬為H的矩形區域中.

2.2 相關定義

1)傳感器節點的感知半徑為r,如圖1所示,傳感器節點i采集的數據能夠代表感知范圍內任一數據采樣點的數據信息,因此本文對傳感器節點i的相鄰傳感器節點的定義N(i,j)如公式(1)所示.

圖1 感知范圍圖Fig.1 Range of sensing

(1)

公式(1)中N(i,j)為1則表示節點i與節點j相鄰,為0則表明節點i與節點j不相鄰,ed(i,j)為歐式距離.

2)冗余數據:假設傳感器節點i與傳感器節點j之間的距離小于節點感知半徑r,且節點i與節點j采集的相對誤差小于10%,則認為傳感器節點i和節點j采集的數據為冗余數據.

3 區域生長法劃分相似區域

根據假設1,小范圍內傳感器網絡采集的數據趨向一致性,因此本文通過區域生長算法將數據接近的區域進行劃分,然后在該區域內選擇一個代表節點,該代表節點采集的數據與該子區域的數值和數據變化趨勢最接近,然后將代表節點的數據傳輸至Sink節點,利用代表節點采集的數據代表子區域的數據.本章3.1小節介紹了區域生長法種子點的選取,3.2小節研究了根據種子節點進行相似區域的生長過程.

3.1 種子節點選擇

種子節點的選取主要考慮分布均勻原則,種子節點在傳感器網絡部署區域中分布均勻,才能全面的采集部署區域的信息.本文采用隨機數方法選取種子節點,傳感器網絡中每個傳感器節點k都能生成一個(0,1)之間均勻分布的隨機數rand(k),當rand(k)大于閾值T時,則該節點稱為種子節點,閾值T如公式(2)所示.

T=1-P

(2)

公式(2)中P為傳感器網絡中需要選取種子節點的百分比.

由于本文的隨機數滿足均勻分布,因此選擇的種子節點能夠均勻分布在部署區域中,保證了監測區域的完整性.在后期重新選擇節種子節點時,由于每個節點生成均勻隨機數,因此所有節點等概率的成為種子節點,避免了某些節點重復成為種子節點的可能性.

3.2 區域生長

區域生長算法能夠較好的進行相似屬性區域的劃分,如圖像研究中可以利用區域生長法分割像素相似的區域,將像素值接近的部分劃分到同一塊區域中,而像素值差距較大的部分劃分為不同區域,且區域生長法劃分的區域在物理位置上是連續的,因此將區域生長法進行相應的改進后能夠適用于WSN相似區域的劃分.

傳統的區域生長法一般用于圖像分割,如圖2所示,圖2(a)為像素點編號,圖2(b)為像素點對應的像素值,首先從種子點1開始生長,判斷種子點4鄰域(2、3、4、5號像素點)的像素點與種子點像素值之差的絕對值是否小于一定閾值(這里閾值為1),如果小于閾值,則往該像素點方向生長,最終結果如圖2(c)所示,區域第一步向4號像素點生長,接著以4號節點為種子節點,向6號像素點生長,直到達到區域生長結束條件,算法停止迭代,完成區域生長.區域生長后,同一片區域的像素值大小非常接近.

圖2 區域生長原理圖Fig.2 Principle of region growing method

上述介紹了區域生長法在圖像分割中的應用,發現區域生長經過改進后同樣可以應用于WSN相似區域生長問題.在WSN網絡中并不采用圖像中的四鄰域或八鄰域等,而是采用相鄰傳感器節點作為區域生長法的鄰域,可通過公式(1)判斷傳感器節點是否相鄰.

在初始時刻,傳感器網絡已經采集了一部分數據,假設節點j采集的數據為datai={d1,d2,d3,…,dm},j∈「1,N?,且節點j是種子節點i的相鄰傳感器節點,當節點j滿足公式(3)時,區域向節點j方向生長.

|avg(dataj)-avg(datai)|≤Td

(3)

公式(3)中Td為閾值,可根據實際情況取值,avg為求集合元素平均值的函數,datai是種子節點采集的歷史數據.

通過3.1小節方法選擇的種子節點編號集合為S={s1,s2,s3,…,sk,…,ssum},具體的WSN相似區域生長算法如表1所示,最終傳感器網絡被分割為sum個子區域,如圖3所示,每個子區域中的傳感器節點采集的數據信息相似性較高.

圖3 區域生長圖Fig.3 Region growing

表1 WSN相似區域生長算法表Table 1 Similar region growing algorithm

4 代表節點

本章第2節研究了傳感器網絡節點相似區域劃分方法,本章主要研究在子區域中選擇一個代表節點,該代表節點采集的數據能夠代表整個子區域的數據信息,因此代表節點采集的數據應該與整個子區域的傳感器節點采集的數據大小最接近且數據變化趨勢也最符合.

代表節點的歷史數據曲線a與子區域中所有傳感器節點歷史數據均值曲線b應該滿足以下兩種情況之一:

1)曲線a與曲線b的變化趨勢始終一致,且數值大小最接近.

2)曲線a與曲線b初始時刻趨勢不一致,且數值大小也不一定接近,但是到后來兩條曲線逐漸逼近,且數值大小也越來越接近.

上述兩種情況如圖4所示,因為隨著環境信息的改變,傳感器節點采集的數據也會隨之改變,因此初始時刻曲線a與曲線b不吻合,但是隨著時間的推移,代表節點的歷史數據曲線a可能與曲線b吻合程度較好.

圖4 歷史數據曲線圖Fig.4 Historical data graph

針對上述兩種曲線相似情況,提出了一種適宜的曲線相似性描述方法,假設某個子區域的歷史數據均值曲線b可描述為點集合avg_data={Y1,Y2,Y3,…,Yt,…,Ym},m為歷史數據數量,子區域中一個傳感器節點的歷史數據曲線a可描述為點集合data={y1,y2,y3,…,yt,…,ym},則曲線a與b的相似度計算方法如公式(4)所示.

(4)

公式(4)中h為子區域中傳感器節點的數量,G是一個常數,表示誤差范圍,S表示曲線相似度,S越接近1,表明兩條曲線的相似度越高,而且該相似度計算公式為較后面的歷史數據分配的權重值越大,因此能夠較好的適用于本文中曲線相似度的描述.

在子區域中選擇代表節點的具體步驟如下:

1)求子區域中所有傳感器節點(h個節點)每個時刻采集數據的平均值,即計算avg_data;

2)遍歷子區域中所有傳感器節點,并利用公式(4)計算每個傳感器節點的歷史數據曲線集合data與集合avg_data的相似度,選擇相似度最高的傳感器節點為代表節點.

5 算法迭代

通過第2章節和第3章節已經完成了相似區域的劃分和代表節點的選擇,最后傳感器網絡只需要將代表節點采集的數據傳輸至Sink節點,然后Sink節點將數據傳輸至服務器端即可完成對整個區域的信息采集,該過程是一輪完整的數據采集過程.為了使代表節點采集的數據能夠更準確的代表子區域的信息以及均衡傳感器節點能耗,本文的數據采集算法運行一定時間后會重新進行下一輪數據采集過程,即相似區域劃分以及代表節點選擇.具體的算法迭代如表2所示.

6 仿真實驗

在一個長為2000m,寬為1500m的矩形區域中均勻部署了1000個傳感器節點,傳感器節點的采集半徑r=40m,假設傳感器網絡采集矩形區域中的溫度數據,由于實際環境中溫度分布是連續的,即在小范圍內溫度值變化微小,比較適宜做本文數據采集方法的研究對象,因此仿真實驗利用matlab的插值函數為每個節點仿真采集的溫度數據,保證溫度分布連續.在插值前,隨機的指定傳感器節點為插值樣本點,且該樣本點的溫度數據通過隨機方法獲得,保證每次仿真溫度數據都不同,實驗中選取種子節點的數量為所有部署節點的10%,將部署區域劃分為100個子區域.假設傳感器節點采集的數據直接發送至Sink節點,如目前的LoRaWAN傳感器網絡、NB-iot傳感器網絡等都是終端節點與網關節點進行直接通訊.

表2 DAA-RGM迭代過程表
Table 2 DAA-RGM iterative process table

DAA-RGM算法迭代Algorithm:1:運行整個傳感器網絡,采集一段時間的數據信息;2:根據步驟1采集的歷史數據,按照第二章的區域生長法進行相似區域劃分;3:按照第三章的代表節點選擇方法為每個子區域選擇代表節點;4:被選擇的代表節點運行一段時間,采集區域信息;5:返回步驟1.

6.1 子區域數據相似性分析

實驗驗證利用區域生長法劃分傳感器網絡部署區域,劃分后每個子區域內傳感器節點采集的數據具有較高的相似性,區域生長法中閾值Td設置為2.實驗隨機的從100個子區域中選擇8個子區域,并統計這些子區域中所有傳感器節點采集的溫度信息,實驗結果以箱線圖表示,如圖5所示,橫坐標為子區域的序號,縱坐標為溫度,圖中每個箱形代表一個子區域內所有傳感器節點采集一次的溫度.

圖5 子區域數據圖Fig.5 Subarea data graph

實驗結果表明每個子區域中的傳感器節點采集的溫度數據最大值與最小值之間的差值小于或等于閾值Td,因此提出的區域生長法對WSN部署區域進行數據相似性劃分是有效的.

6.2 代表節點分析

根據子區域的歷史數據曲線選擇代表節點,代表節點采集的數據與子區域歷史數據均值最接近.本實驗驗證代表節點在后續數據采集階段采集的溫度數據是否能夠代表子區域的溫度信息.實驗結果如圖6所示,實驗對比了代表節點采集的溫度數據與子區域所有傳感器節點采集的溫度數據均值,隨機選取4個子區域進行驗證,橫坐標為數據采集次數,縱坐標為采集的溫度.

圖6 代表節點分析圖Fig.6 Analysis of representative nodes

實驗結果表明代表節點采集的溫度數據與子區域采集的數據均值變化趨勢和數值大小基本相同,區域1的曲線相似度為95.86%,區域2的曲線相似度為98.38%,區域3的曲線相似度為96.01%,區域4的曲線相似度為96.02%,實驗隨機選取的4個子區域都具有較高的相似度,因此通過第三章提出的代表節點選擇方法選擇的代表節點能夠有效的代表子區域,同時也表明本文提出的DAA-RGM數據采集算法能夠減少大量冗余數據且保證采集的數據誤差在5%以內.

當種子節點選取的百分比不同時,代表節點與子區域均值的相似度也會不同,理論上代表節點百分比越大,則劃分的子區域數量越多,每個子區域內包含的傳感器節點數量越少,因此相似度越高,反之則反.種子節點占總節點數百分比與相似度之間的關系如圖7所示,圖中橫坐標為種子節點百分比,縱坐標為代表節點采集的數據與子區域的數據均值相似度.

圖7 相似度圖Fig.7 Similarity analysis

實驗結果與分析一致,當種子節點的比例越大,代表節點采集的數據與子區域數據均值的相似度越高,因為種子節點的比例越大,則劃分的子區域數量越多,每個子區域的面積越小,子區域范圍越小,則代表節點代表該區域的能力越強.隨著種子節點比例的增加,相似度也會逐漸增加,但增加的幅度逐漸變小,且種子節點百分比大于12%時,相似度基本不會繼續升高,因為本文采集區域的溫度信息在一定范圍內是接近的,因此種子節點數量到達一定比例時,相似度并不會繼續提高.

6.3 冗余數據分析

本文提出的數據采集方法目的是減少傳感器網絡的冗余數據,降低網絡的能量消耗,從而達到延長網絡生存時間的目的,同時大量的冗余數據會造成網絡的擁塞.冗余數據的定義如2.2小節定義2所示.本實驗對比本文提出的DAA-RGM數據采集算法與傳統的數據采集方法(所有傳感器節點都進行數據采集并直接發送至Sink節點)、分簇-數據融合的數據采集方法(先對傳感器網絡進行分簇,然后簇首收集簇成員節點的數據進行數據融合,該方法每次簇成員節點都需要采集數據,然后將采集的數據發送至簇首節點進行數據融合,融合后簇首節點將數據直接發送至Sink節點,根據目前WSN數據壓縮方面的研究,假設本文的數據融合后壓縮為原來的70%大小[16,17].),每次實驗重復100次,實驗結果如圖8所示,橫坐標為種子節點百分比,縱坐標為冗余數據百分比.

圖8 冗余數據圖Fig.8 Redundant data

實驗中分簇-融合算法的種子節點比例代表簇首節點比例,傳統采集方法不選擇種子節點,傳感器網絡中所有節點都采集數據.實驗結果表明隨著種子節點比例的增加,分簇-融合采集方法和DAA-RGM采集方法所采集數據的冗余比例會逐漸降低,當達到一定低點后,采集數據冗余比例會逐漸增加,因為在初始時刻種子節點比例較低,隨著種子節點比例的增加,檢測區域被劃分的越來越準確,因此每個區域內采集的冗余數據逐漸降低,而隨著種子節點比例的增加,區域被劃分的越來越小(或簇規模被細分的越來越小),從而導致相鄰的幾個子區域(或簇)采集的數據存在冗余情況,因此傳感器網絡采集的數據冗余比例逐漸增加.DAA-RGM采集方法的最佳種子節點比例為17%,分簇-融合數據采集方法的最佳種子節點比例為16%.

從實驗結果可知,本文提出的DAA-RGM采集方法采集的數據冗余比例低于分簇-融合方法和傳統的采集方法,且傳統的采集方法采集的數據冗余比例最大.

6.4 生存時間分析

為了方便實驗,假設傳感器網絡中每個傳感器節點都可以直接與網關節點進行通訊,傳感器節點采集數據后可直接發送至Sink節點.實驗驗證傳感器網絡的生存時間,實驗對比了提出的DAA-RGM數據采集算法、傳統的數據采集算法和分簇-數據融合方法的網絡生存時間,實驗中第一個節點死亡標志著傳感器網絡死亡.假設傳感器節點的初始能量E0為0.05J,傳感器節點每次采集和發送數據需要消耗500nJ/bit能量,簇首節點融合1bit數據需要消耗的能量為30nJ,為了保證DAA-RGM算法采集的數據準確性大于95%,種子節點的比例分別為10%、12%、14%、16%、18%,實驗結果如圖9所示,橫坐標為種子節點占總節點數量的百分比(對于分簇-數據融合方法,橫坐標為簇首數量),縱坐標為傳感器網絡死亡前總共進行的數據采集次數.

圖9 網絡采集次數圖Fig.9 Frequency of data acquisition

實驗結果表明傳統的數據采集方法能夠采集數據的次數遠遠低于DAA-RGM采集方法和分簇-融合方法,且本文提出的DAA-RGM采集方法使得網絡的生存時間高于目前比較經典的分簇-融合方法.DAA-RGM采集方法的種子節點所占比例為10%時,代表節點采集的數據與子區域數據均值相似度大于95%,數據采集數量約為傳統采集方法的9倍,分簇融合方法的1.5倍.隨著種子節點所占比例的增加,DAA-RGM方法的網絡數據采集次數也會逐漸降低,因為種子節點數量增加,劃分的子區域數量也會增加,則某些節點被重復選擇為代表節點的概率增加,導致能量消耗過快,從而加快了傳感器網絡的死亡速度.

假設傳感器網絡中第一個節點能量耗盡之前,這段時間為傳感器網絡的生存時間,則DAA-RGM方法與其他方法的生存時間對比實驗結果如圖10所示,實驗中傳感器網絡每隔1分鐘采集一次數據,種子節點的比例為14%、16%、18%.

圖10 生存時間圖Fig.10 Lifetime chart

實驗結果表明提出的DAA-RGM在不同種子節點比例下生存時間都高于傳統的“分簇-融合”類型的數據采集算法,且隨著種子節點比例增加,網絡生存時間逐漸降低,因為種子節點比例增加,傳感器網絡被細分的數量越多,種子節點越多,導致消耗的能量越多,因此網絡生存時間會降低.

7 結束語

研究了一種WSN數據采集算法(DAA-RGM),該算法首先根據傳感器網絡采集的歷史數據,利用區域生長法將相似區域進行劃分,然后在每個子區域中選擇最佳的節點作為代表節點,代表節點采集的數據與子區域采集的數據具有較高相似性,最后休眠其他傳感器節點,只運行代表節點采集數據.實驗結果驗證了該方法的可行性和有效性,后續工作希望在此基礎上進一步研究更加準確且節能的WSN數據采集方法.