分布式融合算法在WSANs中的性能分析

伍昕宇，李才對，李亞秀，楊春曦

昆明理工大學化學工程學院，昆明 650500

分布式融合算法在WSANs中的性能分析

伍昕宇，李才對，李亞秀，楊春曦

昆明理工大學化學工程學院，昆明 650500

在無線傳感器執行器中，執行器節點接收傳感器節點傳來的信息并執行相應的動作。為了滿足執行器節點及時地采取行動，無線傳感器執行器網絡對時延有嚴格的限制。構建了一種一般性的分布式融合算法并與集中式融合算法比較。通過從網絡傳輸時延、節點能量消耗、網絡壽命、有效傳輸次數等方面分析了這種算法在無線傳感器執行器網絡中的特性。在三種典型拓撲結構下的仿真實驗表明，在相同條件下，分布式融合算法比集中式融合算法具有更小的網絡傳輸時延，更長的網絡壽命，同時節點的能量消耗更加均勻。

無線傳感器執行器網絡；分布式融合；集中式融合

1 引言

無線傳感器執行器網絡[1]（Wireless Sensor and Actor Networks，WSANs）是由大量能量較少、計算能力有限的傳感器節點和少量能量較多、計算能力較強的執行器節點組成的一個多跳自組織異構網絡。與無線傳感器網絡不同的是，無線傳感器執行器網絡具有分布式檢測、數據多跳傳輸和控制的功能，所以其研究的問題不僅是節能[2-3]、網絡覆蓋[4-5]、數據完整性[6]等，而且必須考慮數據的傳輸時延限制[7-9]。為了有效減小網絡傳輸時延，通常采用分簇[10-12]的方法：以能量較多的執行器節點固定充當簇頭，其他無線傳感器節點圍繞簇頭進行數據采集與傳輸。

圖1是一個無線傳感器執行器網絡結構圖。在監控區域中，圓點代表能量有限、計算能力有限和通信范圍有限的傳感器節點，三角形代表能量較多、計算能力較強和通信范圍較大的執行器節點。傳感器節點與執行器節點自組織成為包含多條鏈路結構的簇狀網絡，并由能量多、計算能力強和通信范圍大的執行器節點充當簇頭。

無線傳感器執行器網絡工作時，大量分布在監控區域的傳感器節點檢測環境數據，并把數據沿鏈路傳遞直至執行器節點（即Sink節點）。執行器節點根據傳感器節點檢測到的數據并及時作出反應，從而達到控制的目的。

圖1 WSANs網絡模型

來自不同無線傳感器節點的數據在傳輸過程中被疊加了大量干擾，甚至同一時刻采樣的數據傳輸到執行器節點不完整。數據融合的目的在于刪除冗余、無效、可信度差的數據，減少網絡數據傳輸量，從而減少節點能量消耗，延長網絡壽命。融合按照結構的不同，分為集中式融合和分布式融合。集中式融合是將所有信息進行一次融合計算完成，其優點是能夠選擇合適的融合算法進行最優融合。缺點是采集的數據受干擾影響較大，融合所需的計算能力較強，能量消耗較大，所需時間較長[13]；分布式融合把信息分散到傳感器各自的處理器進行多次融合完成，其優點是各節點能量消耗較均勻，采集的數據就近融合，受干擾較少。缺點是節點能量和計算能力有限，不能采用較復雜的融合算法，同時因為采取局部融合的方法，導致不容易得到全局最優值。近年來，在數據融合策略方面已有大量研究[14-16]，但這些研究均未考慮到在WSANs中的應用特點。

為定量比較分布式融合算法與集中式融合算法在WSANs中的動態特性，本文采用MATLAB構建了一般性的分布式融合算法和集中式融合算法各一種，以三種典型的拓撲結構為對象，從網絡傳輸時延、節點能量消耗、緩存位數、網絡壽命和傳輸過程中的失敗概率五個方面分析了兩種融合算法在網絡中的差異，為后續的WSANs融合算法研究奠定了基礎。

2 理論基礎

2.1 定義

（1）有效傳輸：所有節點同一個周期內采集的數據都成功發送至執行器節點，稱為一次有效傳輸。

（2）有效時延：各個傳感器節點在同一個周期Tm采集的所有數據，最后一包數據發送至執行器節點的周期為Tn，則時間間隔(Tn-Tm)稱為有效時延。

（3）平均時延：在一段采樣時間內，所有有效時延之和除以有效傳輸次數稱為平均時延。

（4）網絡壽命：網絡中出現任意一個節點能量消耗完畢時的網絡所經歷的周期數為網絡壽命。

（5）失敗概率：由于不確定因素的影響，導致兩個節點不能正常通信的隨機概率（這里隨機概率服從均勻分布）。

2.2 算法分析

（1）分布式融合

①每個采樣周期T可以發送p輪數據（這里取p= 3），記為Ti1、Ti2和Ti3，其中周期數i=1，2，3，4…。

②周期Ti開始，Ti1時刻，各節點同時采集當前數據并放入緩存的第一位，上游節點首先發送第一位緩存中的數據至相鄰的節點，與相鄰節點中的數據融合后再發送至下游節點，依次進行至執行器節點，若其中某個節點中的數據沒有發送成功，則放入當前節點的緩存。

③Ti2時刻，節點首先發送緩存中的數據至相鄰的節點，發送和融合過程如Ti1時刻。若此節點緩存的第一位不為空，則發送第一位緩存中的數據，若此節點緩存的第一位為空，則發送下一位緩存中的數據，依次類推，若此節點緩存都為空，則不發送數據，若其中某個節點中的數據沒有發送成功，則放入當前節點的緩存。

④Ti3時刻，重復Ti2時刻的過程，完畢后，周期Ti結束。

⑤周期Ti+1開始，循環上述過程至所有周期結束。

（2）集中式融合

①每個采樣周期T可以發送z輪數據（這里取z= 3），記為Ti1、Ti2和Ti3，其中周期數i=1，2，3，4…。

②周期Ti開始，Ti1時刻，各節點同時采集當前數據并放入緩存的第一位，數據通過相鄰節點依次發送第一位緩存中的數據至執行器節點，若其中某個節點中的數據沒有發送成功，則放入當前節點的緩存。

③Ti2時刻，數據通過相鄰節點依次發送緩存中的數據至執行器節點，發送過程如Ti1時刻。若此節點緩存的第一位不為空，則發送第一位緩存中的數據，若緩存的第一位為空，則發送下一位緩存中的數據，依次類推，若此節點緩存都為空，則不發送數據，若其中某個節點中的數據沒有發送成功，則放入當前節點的緩存。

④Ti3時刻，重復Ti2時刻的過程，所有節點的數據都成功發送至執行器節點時進行集中式融合，周期Ti結束。

⑤周期Ti+1開始，循環上述過程至所有周期結束。

3 仿真比較

3.1 條件假設

（1）所有節點的初始狀態相同，初始能量為E（執行器節點也不例外），傳感器節點具有簡單的數據融合功能，所有節點均不發生移動。

（2）若節點上游沒有其他節點，則此節點只發送不接收數據，執行器節點只接收不發送數據。

（3）每個節點只與相鄰節點通信，數據通過相鄰節點發送至執行器節點，該節點擁有較強的計算能力和較大的存儲空間。

（4）每一位緩存的容量正好存放一次傳感器采集的數據，緩存采用后進先出的堆棧方式存取數據。

（5）為便于計算，忽略節點的喚醒和睡眠的時間延遲和能量消耗。

（6）為研究方便，取相鄰節點間的數據傳輸失敗概率相同，均服從均勻分布。

3.2 網絡模型

本節以7個節點所組成的三種不同的拓撲結構作為網絡模型，即：一字拓撲模型、復合拓撲模型和樹形拓撲模型。數據按照箭頭指向從左至右依次傳遞，如圖2所示。

圖2 三種拓撲模型示意圖

3.3 能耗模型

一個典型的傳感器節點由數據處理單元、微型傳感器、電源和無線電通信單元組成。本文使用W.B. Heinzelman論文中的能耗模型[17]，如圖3所示。

圖3 能耗模型

傳輸l比特信息到距離d的節點，發送端消耗的能量為：

接收端消耗的能量為：

其中，電路消耗能量Eelec與數字編碼、調制、濾波和信號傳播情況有關。放大器消耗能量εfsd2或εmpd4取決于與接收器的距離和誤碼率。d0為臨界距離。數據融合所需要的能量為EDA。

3.4 仿真參數

仿真各主要參數如表1所示。

表1 仿真參數表

3.5 仿真結果

本文采用MATLAB軟件進行仿真，通過平均時延、節點能量消耗、網絡壽命、有效傳輸次數等方面定量比較分布式融合算法和集中式融合算法在網絡中的傳輸效果。

圖4表示三種拓撲結構在節點發送5 000次數據且節點間具有相同失敗概率0.4的條件下，緩存位數對分布式融合和集中式融合有效傳輸次數的影響。對于分布式融合，緩存位數較少時，一字拓撲結構的有效傳輸次數最小。但隨著緩存位數的增大，三種拓撲模型的有效傳輸都趨于100%。對于集中式融合，樹形拓撲模型和復合拓撲模型的有效傳輸次數有較大差異，這主要是因為樹形拓撲模型的分支節點較多，在節點5處造成數據的丟失，從而降低了有效傳輸次數。隨著緩存位數的增加，三種拓撲模型的有效傳輸趨向值也有較大差異。可見集中式融合的有效傳輸次數不僅與拓撲模型的鏈路長度有關，還受分支節點多少影響。

圖4 有效傳輸次數隨緩存位數變化比較圖

圖5表示三種拓撲結構在節點發送5 000次數據且節點緩存為10位的條件下，失敗概率對于網絡平均時延的影響。對于分布式融合，由于一字拓撲結構的鏈路長度的不同，故其平均時延遠大于其他兩種拓撲模型的平均時延。對于集中式融合，一字拓撲結構的鏈路長度依然最大，故其平均時延最大；同時，受分支節點數的影響，樹形拓撲模型導致的平均時延大于復合拓撲模型。

圖5 平均時延隨失敗概率變化比較圖

圖6表示三種拓撲結構在節點發送5 000次數據、節點緩存為4位且節點間的失敗概率都為0.3的條件下，各節點剩余能量分布的情況。對于分布式融合，一字拓撲模型的每個節點只需與其相鄰的前一節點數據進行融合，故節點2到節點6間的節點剩余能量分布非常均衡；樹形拓撲模型的節點5需與節點1到節點4的數據進行融合，能量消耗最嚴重；對于復合拓撲模型，節點5和節點6都需要與兩個節點的數據融合，能量消耗相近，節點4只需與節點3中數據融合，能量消耗少。對于集中式融合，無論是哪種拓撲模型，當節點需要轉發的數據越多，該節點消耗的能量也越多。

圖6 節點能量分布圖

圖7表示三種拓撲結構在節點發送5 000次數據且節點的緩存都為2位的條件下，失敗概率對分布式融合和集中式融合有效傳輸次數的影響。對于分布式融合，隨著失敗概率在區間0.3～0.7內增長，三種拓撲模型的有效傳輸次數均大幅度減少。對于集中式融合，隨著失敗概率在區間0.2～0.5內增長，三種拓撲模型的有效傳輸次數也大幅度減少。這表明，在惡劣的環境下，分布式融合算法比集中式融合算法有更好的魯棒性。

圖7 有效傳輸次數隨失敗概率變化比較圖

圖8表示緩存位數和失敗概率對網絡壽命的影響，其中下面的曲面代表集中式融合算法的網絡壽命，上面的曲面代表分布式融合算法的網絡壽命。表面上看，對于集中式融合，隨著失敗概率的增加，網絡的壽命也隨之增加，但這是由于失敗概率太大導致數據大量丟失使得節點能量消耗降低，實際意義不大。對于分布式融合，隨著失敗概率的增加，網絡壽命大體上隨之降低。在失敗概率大于0.8時，曲面出現“翹尾”現象，其原因也是由于失敗概率太大導致數據大量丟失使得節點消耗降低。在緩存為1、失敗概率為0.8附近時，曲面出現“卷邊”現象，這是因為在數據大量丟失的情況下，節點的數據無法發送至相鄰節點，相鄰節點的數據在沒有融合時無法發送，后續節點也無法發送，網絡壽命獲得了“暫時性”提高，需要指出的是，這種網絡壽命的提高是以數據的大量丟失為代價的。

圖8 網絡壽命比較圖

4 結束語

為了比較分布式融合算法和集中式融合算法在無線傳感器執行器網絡的傳輸效果，本文構建了一種一般性的分布式融合算法，其核心思想是把采集的數據分散到各個節點進行融合，從而減少了網絡的傳輸量，降低了節點能量消耗，延長了網絡壽命。通過對分布式融合算法和集中式融合算法在三種不同的網絡拓撲模型下進行仿真實驗，得出如下結論：

（1）同等條件下，分布式融合算法的有效傳輸次數明顯高于集中式融合的有效傳輸。

（2）分布式融合算法使節點能量消耗更加平均，從而延長了網絡壽命。

（3）在失敗概率較大的情況下，分布式融合算法的平均時延遠小于集中式融合的平均時延。

（4）同等條件下，分布式融合算法的有效傳輸次數和平均時延主要受到鏈路長度的影響，而集中式融合算法的有效傳輸次數和平均時延與鏈路長度和分支節點數兩個因素相關。

（5）在分布式融合算法下，節點能量消耗的差異是由于融合數據包數量的不同，而在集中式融合算法下，節點能量消耗的差異是由于轉發數據包的不同。

（6）在實際應用中，每個簇單元應盡量減少終端節點到執行器節點間鏈路過長和分支節點數過多的情況出現。

總體上看，分布式融合算法比集中式融合算法具有更小的網絡傳輸時延，更長的網絡壽命，同時節點的能量消耗更加均勻。綜合以上幾點，分布式融合算法更加適用于WSANs。

[1]Akyildiz I F，Kasimoglu I H.W ireless sensor and actor networks：research challenges[J].Ad Hoc Netw orks，2004，2（4）：351-367.

[2]李方敏，徐文君，劉新華，等.無限傳感器/執行器網絡中能量有效的實時分簇路由協議[J].計算機研究與發展，2008，45（1）：26-33.

[3]Sankarasubramaniam Y，Akyildiz I F，M cLaughlin S W. Energy efficiency based packet size optimization in wireless sensor networks[C]//2003 IEEE International Workshop on Sensor Network Protocols and Applications，2003：1-8.

[4]任彥，張思東，張宏科.無限傳感器網絡中覆蓋控制理論與算法[J].軟件學報，2006，17（3）：422-433.

[5]蔣杰，方力，張鶴穎，等.無線傳感器網絡最小連通覆蓋問題求解算法[J].軟件學報，2006，17（2）：175-184.

[6]曹遠福，孫星明，王保衛，等.基于關聯數字水印的無線傳感器網絡數據完整性保護[J].計算機研究與發展，2009，46 （Suppl）：71-79.

[7]楊春曦，關治洪，黃劍，等.時延加權融合技術的無線傳感器網絡控制[J].控制理論與應用，2011，28（2）：157-165.

[8]楊春曦，黃劍，張金龍.具有馬爾科夫時變時延的REM擁塞算法局部穩定性[J].華中科技大學學報，2010，38（6）：19-22.

[9]Gungor V C.Real-time and reliable communication in wireless sensor and actor networks[D].Georgia：School of Electrical and Computing Engineering，2007.

[10]戴志誠，冉啟月，汪秉文.帶執行器節點的無線傳感器網絡的分簇算法[J].計算機工程與應用，2007，43（10）：145-147.

[11]陳聞杰，陳迅，高麗強，等.無線傳感網網絡成簇算法研究[J].小型微型計算機系統，2008，29（2）：219-225.

[12]沈波，張世永，鐘亦平.無線傳感器網絡分簇路由協議[J].軟件學報，2006，17（7）：1588-1600.

[13]葉寧，王汝傳.無線傳感器網絡數據融合模型研究[J].計算機科學，2006，33（6）：58-60.

[14]尹慧琳，王磊，馮占軍.無線傳感器網絡節點分布式信息融合算法研究[J].計算機工程與應用，2007，43（17）：18-20.

[15]黃旗明，劉笑.基于博弈理論的無線傳感器網絡融合路由研究[J].傳感器學報，2008，21（11）：1905-1908.

[16]王天荊，楊震，胡海峰.基于遺傳算法的無線傳感器網絡自適應數據融合路由算法[J].電子與信息學報，2007，29 （9）：2244-2247.

[17]Heinzelman W B，Chandrakasan A P，Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1（4）：660-670.

WU Xinyu,LI Caidui,LI Yaxiu,YANG Chunxi

Faculty of Chemical Engineering,Kunming University of Science and Technology,Kunming 650500,China

Wireless Sensor and Actor Networks（WSANs）employ actor nodes that can collect data from sensors and perform application specific actions.To meet the demand of taking actions promptly,minimizing the time of gathering data is desirable.A general distributed fusion algorithm is proposed to com pare with a general centralized fusion algorithm. This paper analyzes its features in transmission delay,node energy consumption,network lifetime and the probability of transmission failure.The simulation results on three different typical topological structures indicate that the distributed fusion algorithm can achieve less transmission delay,longer network lifetime and distribute energy dissipation more evenly throughout the sensors than the centralized fusion algorithm under the same conditions.

wireless sensor and actor networks;distributed fusion;centralized fusion

A

TP393

10.3778/j.issn.1002-8331.1208-0484

WU Xinyu,LI Caidui,LI Yaxiu,et al.Performance analysis of distributed fusion algorithm in W SANs.Computer Engineering and Applications,2014,50（16）：118-122.

國家自然科學基金（No.610040330）；云南省自然科學基金（No.2010ZC035）。

伍昕宇（1989—），男，碩士研究生，主要研究方向為無線傳感器執行器網絡；楊春曦（1976—），通訊作者，男，博士，副教授，主要研究方向為網絡控制系統，魯棒控制，無線傳感器網絡。E-mail：ycx@kmust.edu.cn

2012-09-05

2012-10-26

1002-8331（2014）16-0118-05

CNKI網絡優先出版：2012-11-21，http://www.cnki.net/kcm s/detail/11.2127.TP.20121121.1103.043.htm l