基于能量感知決策樹和增強boosting的網絡數據聚合模型

杜玉香, 陳 欣

(1.廣州南洋理工職業(yè)學院 智能工程學院, 廣東 廣州 510925; 2.遵義師范學院 信息工程學院, 貴州 遵義 563006)

0 引言

無線傳感器網絡[1](WSN)由多個小型傳感器節(jié)點組成,可對物理環(huán)境信息進行監(jiān)測和采集,并在基站處管理采集到的數據．其優(yōu)點是可靠性較強,數據采集靈活且檢測精度高．廣泛應用于環(huán)境監(jiān)測、災難管理、安全、軍事和醫(yī)療等領域．但傳感器節(jié)點在電量和處理能力方面存在限制,電量約束方面更容易造成WSN的故障[2-3]．由于傳感器節(jié)點的不完美性,需要密集放置傳感器節(jié)點,以提高采集數據的質量．但節(jié)點密度較高會造成很多節(jié)點感測到相同的數據,產生冗余．因此,如何去除冗余,提高WSN數據聚合是一個亟待解決的問題．學者們對此也進行了大量的研究．如Singh[4]通過基于鏈的數據采集和傳輸處理,采用自然啟發(fā)優(yōu)化(NIO)以最小化WSN中的傳輸成本和開銷．Huthiafa等人[5]提出了多移動代理迭代規(guī)劃(SMIP)方法,以改善數據采集性能,最大限度降低能量消耗．陳宏濱等人[6]提出一種基于能量平衡的動態(tài)分簇算法,該方法考慮了節(jié)點基于距離與剩余能量的競爭機制,并將各簇內節(jié)點數據依據競爭進行分級,以提高無線傳感器網絡在數據采集過程中節(jié)點能耗的均衡性．陳琪等人[7]提出了一種基于節(jié)點分級的混合多跳數據采集(HMDC)算法,基于數據量將節(jié)點劃分成簇,簇內采用分級思想進行多跳傳輸．劉持超等人[8]提出了一種基于網狀無線網絡的高爐爐缸溫度場無線數據采集系統(tǒng)．

在設計WSN數據采集方法時,應考慮分布式系統(tǒng)架構和通過無線連接的動態(tài)接入[9-10]．以往方法在數據聚合過程中存在能耗較高、時間消耗過久、數據聚合準確度較低和延遲較高等問題．在對傳感器節(jié)點進行連續(xù)數據聚合的過程中,節(jié)點的能量水平會下降．為此,本文提出了一種能量高效的數據聚合方案,將節(jié)點分為高能量節(jié)點和低能量節(jié)點,低能量傳感器節(jié)點將數據發(fā)送至高能量傳感器節(jié)點,實現能量感知的數據聚合．本文主要工作創(chuàng)新總結如下:

1) 提出了使用決策樹樁和增強boosting的概念來執(zhí)行節(jié)點分類的模型，使用決策樹樁作為模型中的弱分類器,將傳感器節(jié)點分為高能量節(jié)點或低能量節(jié)點；

2) 為降低訓練誤差,提高節(jié)點分類性能,提出的模型中應用了增強boosting提升分類,對弱分類器的結果進行合并,并計算訓練誤差,因此,提供了誤差最小化的強分類結果；

3) 為延長WSN的工作壽命,低能量傳感器節(jié)點將數據包發(fā)送至鄰近的高能量傳感器節(jié)點,匯聚節(jié)點采集來自所有高能量傳感器節(jié)點的數據,由此提高了數據聚合性能,最大限度降低延遲．

1 整體模型

1.1 傳感器節(jié)點與簇頭

(1)

(a) 一般系統(tǒng)模型 (b) 簇頭信息 圖1 模型與簇頭

1.2 模型方法概述

本文方法的整體流程如圖2所示,該模型將傳感器節(jié)點隨機分布在無線網絡中,然后,計算WSN中每個傳感器節(jié)點的剩余能量．模型基于弱分類器的結果執(zhí)行增強boosting來提升分類效果,使用決策樹樁作為弱分類器．決策樹樁通過閾值將傳感器節(jié)點分為高能量節(jié)點和低能量節(jié)點．接著,通過增強boosting對所有弱分類器的結果進行合并,從而以更高的準確率將節(jié)點分為高能量節(jié)點或低能量節(jié)點．在分類操作結束后,WSN中的低能量節(jié)點將聚合數據發(fā)送至高能量節(jié)點．最后,匯聚節(jié)點采集來自高能量傳感器的數據,并將聚合數據發(fā)送至基站．

圖2 整體流程圖

在提出的模型中,利用增強boosting提升分類的模型如圖3所示,其作用是將弱決策樹樁轉變?yōu)閺姺诸惼?使WSN中節(jié)點分類的誤差率最小化[11]．具體來說,增強boosting是一種集成方法,通過合并n個弱決策樹樁的結果來提高節(jié)點分類準確度．具體方法：首先,取一定數量的傳感器節(jié)點作為輸入．然后,計算傳感器節(jié)點的剩余能量,為每個輸入傳感器節(jié)點生成弱決策樹樁結果,這些弱分類器通過增強boosting集成為一個強分類器．最終,投票分類的形式獲得高能量節(jié)點和低能量節(jié)點．

圖3 本文提升分類的流程圖

一般adaboost未排序的特征很多,生成的弱假設也很多,其弱假設的選擇一直棘手問題,與一般adaboost集成不一樣,本文的增強boosting只選擇一個排序特征,因此生成的弱假設數量只有1個,明顯減小了弱假設的搜索空間,其示意圖如圖4所示．這樣處理的優(yōu)點是很少情況下或者不需要進行弱假設選擇,從而加速了整個模型的弱學習過程,可以在更少的輪次獲得更佳結果,從而得到更好的節(jié)點分類結果．

圖4 一般adaboost與本文增強boosting示意圖

2 傳感器節(jié)點分類與數據聚合

2.1 傳感器節(jié)點分類

弱決策樹樁為單級決策樹,包含1棵決策樹,以及連接到多個終端節(jié)點的根節(jié)點,基于剩余能量為每個輸入傳感器節(jié)點生成分類結果[12]．假設WSN中所有傳感器節(jié)點在初始放置時的能量水平相等,在提出的模型中,將每個傳感器節(jié)點的能量計算為功率和時間的乘積,即

ASi=[Power*Time]

(2)

式中ASi為傳感器節(jié)點的能量水平．由于節(jié)點的傳感特性,其能量水平會逐漸降低,傳感器節(jié)點的剩余能量可估計為

RASi=[Atot-Acon]

(3)

式中RASi表示傳感器節(jié)點的剩余能量,Atot表示節(jié)點的總能量,Acon表示節(jié)點已消耗的能量．

根據計算出的剩余能量水平,在所提模型中使用弱決策樹樁對傳感器節(jié)點進行分類．首先,弱決策樹樁先定義剩余能量水平的閾值．然后,將每個傳感器節(jié)點的剩余能量水平與閾值相比,若節(jié)點的剩余能量水平RASi大于閾值δ,則將傳感器節(jié)點Si分類為高能量節(jié)點．否則,將傳感器節(jié)點Si分類為低能量節(jié)點．由此,弱決策樹樁分類器結果[13]可計算為

(4)

式中LighEN為高能量節(jié)點,LowEN為低能量節(jié)點,RASi為傳感器節(jié)點剩余能量水平,δ為閾值．

弱決策樹樁將所有輸入傳感器節(jié)點分入不同類別．然而,弱決策樹樁中包含一些訓練誤差,會降低節(jié)點分類準確度．為了提高準確度,本文在所提模型中采用了增強boosting模型．增強boosting模型將n個弱決策樹樁結果合并為強分類器結果,

(5)

式中β表示強分類器輸出,wi表示所有弱決策樹樁分類器的輸出．其后,增強boosting模型向所有弱決策樹樁分類器結果分配相似權重,

(6)

式中bt表示向弱輸出分配的權值．通過增強boosting模型確定的決策樹樁的訓練誤差為

ter=(yi-wi)2

(7)

式中ter表示訓練誤差,yi表示弱決策樹樁分類器的實際結果．基于評估出的訓練誤差,對增強boosting模型中的每個弱決策樹樁結果的權值進行更新．若弱決策樹樁對傳感器節(jié)點進行了精確分類,則降低其權重．若弱決策樹樁將傳感器節(jié)點錯誤分類,則將其權重最大化．bt表示弱決策樹樁的更新后權重．則強分類結果可計算為

(8)

為改善節(jié)點分類性能,最大限度降低誤差,增強boosting模型增加了不同分類之間的間隔．強分類器的結果遵循以下間隔

(9)

式中an≥0,αn表示松弛變量,y表示分類的間隔．大于間隔的結果意味著將全部傳感器節(jié)點分入某個特定類別時,可實現WSN中準確的節(jié)點分類(誤警率非常低)．

由此,將傳感器節(jié)點分類為高能量節(jié)點和低能量節(jié)點．分類處理后,低能量傳感器節(jié)點通過計算Manhattan距離[14],將數據包發(fā)送至鄰近的高能量傳感器節(jié)點．傳感器節(jié)點之間的距離計算如下

(10)

式中Dij表示兩個傳感器節(jié)點Si和Sj之間的Manhattan距離．計算出距離后,低能量傳感器節(jié)點將數據廣播至鄰近的高能量傳感器節(jié)點．最后,匯聚節(jié)點高效采集無線網絡中高能量傳感器節(jié)點的所有數據包．

2.2 數據聚合

所提數據聚合的步驟流程如以下算法所示．通過上述步驟,所提模型提供較好的節(jié)點分類準確度,消耗較短時間,且將訓練誤差最小化．通過分類得到高能量節(jié)點和低能量節(jié)點后,模型尋找距離最近的高能量節(jié)點,以在WSN中對傳感數據包進行聚合．與傳統(tǒng)方法先比,提出的模型通過較少的能量消耗即可采集所有數據包,可實現能量高效的數據聚合．

算法1 基于能量感知決策樹和增強boosting的數據聚合.

輸入: 傳感器節(jié)點S1,S2,…,SN,數據包dp1,dp2,…,dpM

輸出: 實現能量高效的數據聚合

1.Begin

2.for 每個傳感器節(jié)點si

3.利用式(4)得到弱決策樹樁w結果;

4.利用式(5)合并所有弱決策樹樁結果wi

5.利用式(6)進行加權;

6.利用式(7)估計出訓練誤差ter

7.更新權重bt

8.尋找具有最小訓練誤差的弱分類器;

10.對WSN中所有傳感器節(jié)點si進行分類;

11. End if

12. 利用式(8)和式(9)返回強節(jié)點分類結果;

13. End for

14.利用式(10)計算Manhattan距離;

15.識別距離最近的高能量節(jié)點;

16. 低能量節(jié)點將數據包發(fā)送至高能量節(jié)點;

17.匯聚節(jié)點對來自高能量節(jié)點的數據包進行聚合,

并發(fā)送至基站;

18.End

3 仿真實驗與分析

為進行實驗評估,本文在NS3網絡模擬器[15]中實施了提出的模型,考慮的方形區(qū)域為1200 m×1200 m．仿真參數如表1所示．實驗針對不同數量的傳感器節(jié)點和數據包,從能量消耗、數據聚合準確度、網絡工作壽命、延遲和數據聚合時間方面評估了提出的模型的有效性．并與自然啟發(fā)優(yōu)化(NIO)的數據采集模型[4],以及節(jié)點分級混合多跳數據采集(HMDC)模型[7]進行比較．

表1 仿真參數列表

3.1 能量消耗比較

能量消耗EC決定了WSN中傳感器節(jié)點采集數據包所耗費的能量,其定義為

EC=N*eng(Si)

(11)

式中,N表示仿真過程中的傳感器節(jié)點總數,eng(Si)表示網絡中單個節(jié)點采集數據所耗費的能量．

1) 模型:傳感器節(jié)點數量為50,單個傳感器節(jié)點使用能量為0.45J,則總能耗EC=50×0.45J=23J．

2) NIO方法:傳感器節(jié)點數量為50,單個傳感器節(jié)點使用能量為0.62 J,則總能耗EC=50×0.62J=31 J．

3) HMDC方法:傳感器節(jié)點數量為50,單個傳感器節(jié)點使用能量為0.59 J,則總能耗EC=50×0.59 J=29 J．

對于不同數量的傳感器節(jié)點(范圍50～500個),使用不同方法的能耗結果如表2所示．從中可發(fā)現,在不同數量的傳感器節(jié)點下,與NIO和HMDC相比,本文模型使用最小能量在WSN中完成可靠的數據采集．這得益于增強boosting模型處理,利用增強boosting模型識別出高能量節(jié)點,從而在無線網絡中進行高效的傳感數據包采集．利用選出的高剩余能量節(jié)點,避免鏈路故障,降低了數據包重傳次數．因此,與其他模型相比,所提模型最大限度減少了傳感器節(jié)點在WSN中采集數據包時的能量消耗,數據采集的能耗比NIO和HMDC分別低約26%和17%．

表2 能量消耗仿真結果

3.2 網絡工作壽命比較

網絡工作壽命NL計算為執(zhí)行數據聚合的高能量節(jié)點數量與傳感器節(jié)點總數量之比

(12)

式中,N表示傳感器節(jié)點總數量,NH表示進行數據采集的高能量傳感器節(jié)點數量．

網絡工作壽命的計算結果如下:本文模型傳感器節(jié)點數量為50個,選擇的高能量傳感器節(jié)點數量為48個,則網絡工作壽命計算為96%;NIO傳感器節(jié)點數量為50個,選擇的高能量傳感器節(jié)點數量為41個,網絡工作壽命為82%．HMDC的傳感器節(jié)點數量為50個,選擇的高能量傳感器節(jié)點數量為43個,網絡工作壽命為86%．

表3給出了不同的傳感器節(jié)點數量(范圍50～500個),使用不同模型在數據采集過程中的網絡工作壽命的比較．可發(fā)現,與NIO和HMDC相比,本文模型的網絡工作壽命性能更優(yōu),分別提高了9%和10%．這主要是因為所提方法能夠快速準確尋找到具有更高剩余能量的傳感器節(jié)點以在WSN中進行數據采集,從而獲得更高的網絡工作壽命．

表3 網絡工作壽命的結果比較

3.3 數據聚合準確度比較

數據聚合準確度ACC一般定義為通過匯聚節(jié)點正確聚合的數據包數量在傳輸數據包總數量中的占比．定義如下,

(13)

式中,ND表示正確采集的數據包數量,ndp表示數據包總數量．

本文模型匯聚節(jié)點正確采集的數據包數量為24,發(fā)送的總數據包數量為25,其ACC為96%．依據式(12),NIO和HMDC的ACC分別為84%和76%．表4給出了不同數量的數據包(范圍25～250),各模型的數據聚合準確度結果．從中可發(fā)現,與NIO和HMDC相比,本文模型的數據聚合準確度分別提升了10%和16%．對于不同數量的數據包,所提模型均取得了更高的數據聚合準確度．所提模型使用增強boosting模型,將無線網絡中的每個節(jié)點分類為高能量節(jié)點或低能量節(jié)點．基于節(jié)點分類結果,提出的模型僅使用較高能量的節(jié)點進行WSN中的數據采集,這有助于準確采集不同節(jié)點的數據,防止信息丟失．

表4 數據聚合準確度的仿真結果

3.4 延遲性能比較

延遲定義為在WSN中進行數據聚合時的期望時長與實際時長之差．數據聚合過程中,延遲越低,則效率越高．當數據包數量為25,本文模型完成數據聚合的期望時長為9 ms．實際數據聚合時長為11 ms．則延遲計算為2 ms．對于NIO模型,完成數據聚合的期望時長為15 ms．實際數據聚合時長為20 ms．其延遲為5 ms,HMDC完成數據聚合的期望時長為15 ms,實際數據聚合時長為18 ms,因此延遲為3 ms．

表5給出了對于不同數量的數據包(范圍25～250個),使用不同模型的延遲比較．從中可發(fā)現,本文模型在不同輸入數量下延遲均低于NIO和HMDC,延遲至少縮短了30%．這是主要是因為所提模型可以在較短時間內將WSN中的傳感器節(jié)點分為高能量節(jié)點和低能量節(jié)點,通過將數據包發(fā)送至鄰近高能量節(jié)點執(zhí)行高效數據聚合,減少了延遲時間．

表5 延遲性能比較

3.5 網絡連通性

圖5 各方法的網絡連通性比較

一般情況下,網絡拓撲在相對短的時間內不會發(fā)生變化．網絡連通性基于此條件,用于評估網絡數據傳輸的連通性．在網絡給定時刻,首先,選擇一個初始節(jié)點,然后依次搜索直接連接的節(jié)點、二進制跳連接的節(jié)點和三跳連接的節(jié)點,直到連接到初始節(jié)點的節(jié)點數不再進一步增加,如圖5所示,隨著模擬迭代次數的增加,NIO模型的網絡連通率較低且不穩(wěn)定,介于0.2～0.75之間,這主要是因為自然啟發(fā)方法的解較大程度上取決于初始解的優(yōu)劣．而本文模型的網絡連通率較高且更穩(wěn)定,介于0.5～0.75之間,這主要得益于能量感知樹和增強boosting明顯提升了節(jié)點分類性能,訓練的誤差得到控制,數據的傳輸變得穩(wěn)定．HMDC模型的指數總體上最高且最穩(wěn)定,但在某些點上有一些較大的波動,介于0.45～0.8之間．總體而言,本文模型的網絡連通性最好．

4 結論與展望

本文提出了WSN中基于能量感知決策樹樁和增強boosting提升節(jié)點分類的數據聚合模型,通過節(jié)點分類改善數據采集性能,同時最大限度降低能量消耗,且具有較穩(wěn)定的網絡連通性．此外,與其他方法相比,所提模型降低了WSN中傳感器節(jié)點采集數據包所消耗的能量,增加在WSN中被選擇執(zhí)行數據采集的高能量傳感器節(jié)點的數量占比,在多個方面表現更優(yōu)．