基于層次拓撲的無線傳感網絡的數據融合算法

陳志國 滕桂法

關鍵詞： 無線傳感網; 數據融合; 可信度; 層次拓撲; 權重; 傳輸時延

中圖分類號： TN711?34; TP393 ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2018）24?0061?05

Level topology based data aggregation algorithm for wireless sensor networks

CHEN Zhiguo， TENG Guifa

（School of Information Science and Technology， Hebei Agricultural University， Baoding 071000， China）

Abstract： The data authenticity is not considered in the current data aggregation algorithm， and it is possible for sensing nodes to generate wrong sensing measured data in the actual environment. Therefore， a level topology based data aggregation （LTDA） algorithm is proposed for WSNs. In the LTDA algorithm， the confidence level of the sensing measured data is estimated， and only the data whose confidence level is higher than the threshold is allowed to be transmitted. The high?level node with the maximum weight is selected to be the next?hop forwarding node when transmitting data from nodes to the base station. The node weight contains information of distance， residual energy and link quality. The simulation data shows that the proposed LTDA algorithm can reduce the average energy consumption， data packet loss rate and end?to?end transmission time delay.

Keywords： WSN; data aggregation; confidence level; level topology; weight; transmission time delay

0 ?引 ?言

無線傳感網絡 （Wireless Sensor Networks， WSNs）已廣泛應用于各類領域[1]，用于各類事件的檢測，如森林防火、水溫檢測、康復醫療。部署環境中的傳感節點實時地感測數據，然后將感測傳輸到基站[2?3]。這個過程就是數據融合問題。

由于傳感節點屬于微型節點，能量受限。因此，通常密集部署傳感節點，進而防止覆蓋空洞。然而，密集型部署節點會導致多個節點同時感測同一個異常事件，形成大量的數據。而實際上，這些數據存在一定冗余。同時，有些節點也可能會感測錯誤的數據[4]。這些特性影響了數據融合的性能。 此外，傳感節點需要以有效的方式將感測數據傳輸基站，即路由問題。換而言之，數據融合[5]問題涉及到數據可信和數據傳輸兩個問題。

目前針對數據融合問題，研究人員提出多類策略。典型的有文獻[3]提出的可靠數據的融合算法（Reliable Data Aggregation Algorithm，RDAA）算法。RDAA算法考慮了數據包轉發前的時間問題，同時采用組播方式轉發數據包[6]。每個節點在轉發數據包前均需等待一定時間，為數據融合提供時間。盡管組播方式提高了數據傳輸效率，但加大了能耗[7?8]。而文獻[9]也提出非結構的能耗均衡的數據融合（Structure?Free and Energy?Balanced Data Aggregation，SEDA）算法。SEDA算法將每一類異常事件分配唯一號，然后將同一類號的感測數據進行融合。

然而，這些算法并沒有考慮到數據的真實性。在實際環境中，傳感節點可能會產生錯誤的感測數據。例如，受外界噪聲或者硬件故障等問題，會引起傳感節點感測錯誤的數據。

為此，提出基于層次拓撲的無線傳感網絡的數據融合（Level Topology based Data Aggregation，LTDA）算法。LTDA算法首先將網絡劃分為多個子區域，并且每個子區域的監測權重不同。然后，計算數據的可信性，并且將可信度低于閾值的數據排除。在轉發感測數據時，依據距離、剩余能量和鏈路質量信息選擇轉發節點，進而提高數據傳輸效率。仿真數據表明，提出的LTDA算法能夠有效地降低能耗，并降低數據傳輸時延。

1 ?LTDA算法

LTDA算法主要由可信數據轉發和轉發節點的選擇兩部分組成。其中，可信數據轉發是指只轉發真實的感測數據，不轉發不可信的數據。通過可信數據轉發機制降低冗余數據，也能降低網絡開銷。而轉發節點的選擇是指選擇最合適的節點傳輸數據，提高數據傳輸效率。

1.1 ?可信數據轉發

部署WSNs的根本目的在于監測目標區域。目標區域一旦發生異常事件，所感測到的異常事件的節點就將感測數據傳輸至基站，再由基站傳輸至控制中心處理。通常，整個目標區域面積非常寬廣，并且目標區域內不同子區域發生異常事件的概率不同，或者說對不同子區域進行不同等級的監測。例如，基于WSNs的森林防火監測。常將整個森林區域劃分為不同監測等級的子區域，珍貴樹種區域重點監測，而對普通樹種區域并非重點關注。因此，本文將整個區域劃分為多個子區域，這些子區域的監測等級不同。假定整個區域劃分為成[M]個子區域，每個子區域的監測等級為[l]。即第[i]個子區域的監測等級表示為[li]，且[1≤i≤M]。不同等級的監測子區域如圖1所示。

整個感測區域劃分成多個子區域，有的區域監測等級達到91%，即[l=95]，而有的區域低至64%。

LTDA算法不僅對監測區域進行等級劃分，還對傳感節點所感測的數據進行判斷，檢測其可信性。并依據不同子區域，設置不同的可信閾值。只有感測數據的可信度高于閾值，該數據才允許被轉發。

通常，離異常事件發生地越近的傳感節點，它們所感測的數據越可信。反之，離事件發生地越遠，其感測的數據越偏離真實性。為此，給感測數據定義可信度，其定義如下：

[kidata=Ri-de100] ? ? ? ? ? ? （1）

式中：[Ri]表示節點[i]的感測半徑;[de]表示事件的發生地;[kidata]表示節點[i]所感測數據的可信度。只有當節點[i]的[kidata]值大于它所在子區域的可信閾值，才傳輸它所傳輸的感測數據。假定節點[i]在第[j]個子區域，該子區域的可信閾值表示為[Kj]，其定義如下：

[Kj=100-lj100] ? ? ? ? ? ? （2）

1.2 ?轉發節點的選擇

為了縮短數據傳輸路徑，LTDA算法對網絡內的節點進行層次劃分。將離基站跳數最少，且相同的節點稱為第一層。換而言之，離基站一跳距離的節點稱為一層節點，離基站二跳距離的節點稱為二層節點，依次類推。層級數越小，級別越高。即位于一層節點的級別高于二層節點。當低層次節點需要向基站傳輸數據時，它首先從高層次中擇優選擇節點。

為了更好地建立路由，LTDA算法引用基于層次的拓撲。因此，引用控制包HELLO消息。首先由基站以廣播方式傳輸HELLO消息。當一層節點接收HELLO消息后，設定定時器，定時時間隨機。當定時時間定時完畢后，接收節點將自己的ID號、節點位置和能量、離基站跳數嵌入HELLO，再轉發HELLO消息，其格式如圖2所示。

圖中：Position表示節點的位置;Res_en表示節點剩余能量;Hop_count表示節點離基站的跳數。基站廣播時，Hop_count值設為零。然后，每次節點轉發HELLO消息，Hop_count值就加1。 圖3顯示基站廣播HELLO消息的示意圖，S4，S1，S2，S3節點首先接收HELLO消息，它們屬于一層次節點。

然后，一層次節點再對HELLO消息內的字段值進行更新，再向低層次節點傳輸。圖4顯示一層次節點傳輸HELLO消息的過程。

依次類推。每個層次的節點轉發HELLO消息，直至所有節點接收了HELLO消息，進而構建基于層次的網絡拓撲結構，如圖5所示。

值得注意的是，在交互HELLO消息過程中，一個節點可能接收到來自不同層次轉發的HELLO消息。這些HELLO消息內的Hop_count值不同。為此，當接收多條HELLO消息時，節點就從中選擇跳距值最小的HELLO消息，其他HELLO消息丟棄。

1.3 ?轉發節點的選擇

選擇合適的節點轉發數據，有利于提高路由性能。為此，LTDA算法引用節點權重指標，并通過節點權重選擇下一跳的轉發節點。節點權重指標隱含了節點離基站的距離、節點剩余能量，并且反映了鏈路信息。

假定當前數據包的攜帶節點為節點[i]，它需要從更高層次節點中選擇一個節點作為數據包下一跳的轉發節點。若節點[i]位于第[k]層，則節點[i]就從第[k-1]層中選擇一個節點作為轉發節點。假定第[k-1]層內的N個節點，這N個節點所組成的節點集為[Φk-1]。

首先，計算[Φk-1]中每個節點的權重。以節點[j∈Φk-1]為例，它的權重表示為[λj]，定義為：

[λj=Erej+Qlinkijdij] ? ? ? ? ?（3）

式中：[Qlinkij]為由節點[i]與節點[j]構建鏈路的質量;[dij]為節點[i]與節點[j]的距離，[dij=xi-xj2+yi-yj2]，其中[xi，yi]，[xj，yj]分別表示節點[i]、節點[j]的坐標;[Erej]表示節點[j]的剩余能量。

節點的剩余能量等于節點的初始能量減去所消耗的能量。假定每個節點的初始能量相同，且表示為[Einit]。而節點所消耗的能量取決能量消耗模型。為此，引用如圖6所示的能量消耗模型[10]。

具體而言，當節點傳輸[q] bit數據，且傳輸距離為[d]時，所消耗的能量為：

[Etxq，d=qEelec+qεmpd4] ? ? ?（4）

式中：[Eelec]為傳輸單一比特數據時發射器所消耗的能量;[εmp]為雙徑傳播模型條件下的功率放大器所消耗的能量[11]。

相應地，節點接收[q] bit數據所消耗的能量表示為：

[Erxq，d=qEelec] ? ? ? ? ? ? （5）

因此，節點[j]的剩余能量[Erej]可按式（6）計算。假定節點[j]共傳輸了[B] bit，接收了[A] bit數據。

[Erej=Einit-EtxB，d-ErxA，d] ? ? ?（6）

此外，LTDA算法引用信號接收強度指標（Received Signal Strong Index， RSSI）反映鏈路質量。假定節點[i]與節點[j]的鏈路質量[Qlinkij]可表示為：

[Qlinkij=RSSIijNbits] ? ? ? ? ? （7）

式中：[RSSIij]表示節點[j]接收來自節點[i]數據包的信號強度;[Nbits]表示數據包的比特數。

當節點[i]計算了每個節點的權重后，再從中選擇具有最大權重的節點作為轉發節點，如式（8）所示：

[pnext=hmax1≤h≤Nλh，h∈Φk-1] ? ? ? ? （8）

1.4 ?數據傳輸過程

提出的LTDA路由算法主要由數據可信估計和轉發節點的選擇兩個階段構成。LTDA算法的流程如圖7所示。具體而言，首先通過傳輸HELLO消息，建立基于層次的拓撲結構，然后，傳感節點實時地感測異常事件。一旦感測了數據，就估計數據的可信度。再將數據可信度與閾值進行比較。只有大于閾值的數據[12]才允許被傳輸。最后，通過選擇轉發節點，作為下一跳傳輸節點，進而完成數據包的傳輸。

2 ?性能仿真

2.1 ?仿真環境

為了更好地分析LTDA路由性能，利用NS軟件建立仿真平臺。400個傳感節點隨機分布于[400 m×400 m]區域，節點的初始能量為70 J。[Eelec=50 nJ/bit]，[εmp=0.001 3 pJ/bit]。所有節點的感測半徑為50 m。網絡內發生異常事件的頻率為[13]。

此外，同時選擇RDAA和SEDA作為參照，并分析它們的數據包傳遞率、數據傳輸時延以及能耗。每次實驗獨立重復30次，取30次的平均值作為最終實驗數據。

2.2 ?仿真數據分析

首先，分析數據包產生率和節點數對能耗的影響，如圖8、圖9所示。從圖8可知，數據率的增加提高了平均能量消耗。原因在于：數據率越大，網絡內滯留的數據包數就越多，需要更多的節點參與數據包的傳輸或者轉發，加大網絡能耗。與RDAA和SEDA算法相比，LTDA算法的平均能耗得到有效的控制。例如，當數據率在65 packets/s時，LTDA算法的能耗為0.06 J，而RDAA算法、SEDA算法的能耗達到0.093 J，0.08 J。

圖9顯示了節點數對平均能量消耗的影響。從圖可知，平均能耗隨節點數的增加而上升，而提出的LTDA算法的能耗得到下降。這主要是因為LTDA算法有選擇性轉發數據，降低了節點轉發負擔。

接下來，分析數據包丟失率的性能。圖10、圖11分別顯示了數據包產生率、節點數對數據包丟失率的影響。

從圖10可知，數據率的增加提高了數據包丟失率，原因在于數據率的增加，加大了網絡負擔，降低數據包傳輸的流暢性，最終導致數據包的丟失。但相比于RDAA算法和SEDA算法，提出的LTDA算法的數據包丟失率得到有效的下降。這要歸功于LTDA算法在選擇下一跳轉發節點時，充分考慮了節點的能量、鏈路質量信息，提高了路由穩定性。

從圖11可知，節點數的增加提高了數據包丟失率。節點數的增加降低了數據包丟失率的性能。但是，LTDA算法能夠應對節點數的增加，對數據包丟失率進行有效控制。

最后，分析了路由算法的傳輸時延性能，如圖12、圖13所示。

從圖12可知，提出的LTDA路由有效地控制端到端傳輸時延，遠低于RDAA算法的時延。眾所周知，數據包的端到端傳輸時延取決于路徑的連通性和穩定性。而提出的LTDA算法在選擇下一跳轉發節點時，充分考慮了節點穩定性和鏈路的穩定性。與圖12類似，圖13顯示了節點數對端到端傳輸時延的影響。從圖13可知，節點數的增加提高了數據包傳輸的平均時延。原因在于盡管節點數的增加提高網絡連通率，但是也加大對網絡資源的競爭率，必然增加路由斷裂的概率。路由一旦斷裂，就需要重建，最終增加傳輸時延。

3 ?結 ?語

針對WSNs的數據融合問題提出LTDA算法。LTDA算法通過HELLO消息的交互，將網絡內傳感節點劃分為不同的層次，同時將網絡劃分為不同子區域，且每個子區域的監測權重不同。并且從數據可信和數據傳輸兩個角度，提出數據融合性能問題。仿真數據表明，提出的LTDA算法降低了能耗，并且減少了傳輸時延。后期，將進一步優化算法，將基于簇結構引入算法，提高算法的性能。

注：本文通訊作者為滕桂法。

參考文獻

[1] KANSAL A， HSU J， ZAHEDI S， et al. Power management in energy harvesting sensor networks [J]. ACM transactions on embedded computing systems， 2007， 6（4）： 1?40.

[2] MURUGANATHAN S D， MA D C F， BHASIN R I， et al. A centralized energy?efficient routing protocol for wireless sensor networks [J]. IEEE communications magazine， 2005， 43（3）： 8?13.

[3] YOUSE? H， YEGANEH M H， ALINAGHIPOUR N， et al. Structure?free real?time data aggregation in wireless sensor networks [J]. Computer communications， 2012， 35（9）： 1132?1140.

[4] 陳東海，李長庚.基于簇頭功能分化的無線傳感器網絡成簇算法[J].傳感技術學報，2015，28（2）：244?248.

CHEN Donghai， LI Changgeng. A function decomposition algorithms for cluster head for WSNs [J]. Chinese journal of sensors and actuators， 2015， 28（2）： 244?248.

[5] VURAN M C， AKAN O B， AKYILDIZ I F. Spatio?temporal correlation： theory and applications for wireless sensor networks [J]. Computer networks， 2004， 45（3）： 245?259.

[6] 徐曉斌，張光衛，孫其博，等.一種誤差可控傳輸均衡的WSN數據融合算法[J].電子學報，2014，42（6）：1205?1209.

XU Xiaobin， ZHANG Guangwei， SUN Qibo， et al. Precision configurable data aggregation algorithm in WSNs [J]. Acta Electronica Sinica， 2014， 42（6）： 1205?1209.

[7] 宋三華.基于節點度?限制的數據融合樹構建算法[J].傳感技術學報，2018，31（1）：119?124.

SONG Sanhua. Degree?constrained?based data aggregation tree constructing algorithm in wireless sensor networks [J]. Chinese journal of sensors and actuators， 2018， 31（1）： 119?124.

[8] 黃海平，陳九天，王汝傳，等.無線傳感器網絡中基于數據融合樹的壓縮感知算法[J].電子與信息學報，2014，36（10）：2364?2369.

HUANG Haiping， CHEN Jiutian， WANG Ruchuan， et al. Compressed sensing algorithm based on data fusion tree in wireless sensor networks [J]. Journal of electronics & information technology， 2014， 36（10）： 2364?2369.

[9] CHAO C M， HSIAO T Y. Design of structure?free and energy?balanced data aggregation in wireless sensor networks [J]. Journal of network and computer applications， 2014， 37： 229?239.

[10] 高翔，甘昕艷，秦川.基于信任評價的低能耗的數據聚融算法[J].計算機工程與設計，2018，39（4）：1047?1052.

GAO Xiang， GAN Xinyan， QIN Chuan. Trust evaluation based low consumption data fusaggregation algorithm for wireless sensor networks [J]. Computer engineering and design， 2018， 39（4）： 1047?1052.

[11] LIAO Y， QI H， LI W. Load?balanced clustering algorithm with distributed self?organization for wireless sensor networks [J]. IEEE sensors journal， 2013， 13（5）： 1498?1506.

[12] 許建，楊庚，陳正宇，等.基于二次獨立集的數據融合調度算法[J].通信學報，2014，35（1）：62?71.

XU Jian， YANG Geng， CHEN Zhengyu， et al. Data aggregation scheduling algorithm based on twice maximum independent set [J]. Journal on communications， 2014， 35（1）： 62?71.