云環境下異構無線傳感器網絡節點調度改進算法*

劉東平，馬利亞，楊 軍

(1.寧夏大學 數學計算機學院，寧夏 銀川750021;2.寧夏醫科大學 總醫院，寧夏 銀川750000;3.寧夏大學 計算機網絡管理中心，寧夏 銀川750021)

0 引 言

傳統無線傳感器網絡(wireless sensor networks，WSNs)監測區域范圍有限、節點類型與感知數據類型單一、節點產生感知數據量小，網絡異構性不突出。在大規模WSNs 中網絡異構性較傳統WSNs 更加突出，表現為網絡監測區域變大、節點數量眾多、感知數據格式、節點地位不同［1］，對節點調度提出了新的要求。

傳統節點調度算法比如LEACH［2］算法在簇頭生成階段未考慮節點剩余能量信息，成簇不均勻，沒有對融合數據有效性判斷，并且在大規模WSNs 環境下隨著數據量增加，算法執行時間必定延長，無法及時對節點進行調度。為解決大規模WSNs 環境下節點能耗過快，算法效率低等問題，孫韓林等人［3］提出一種基于云計算的WSNs 體系架構，通過在WSNs 中加入云節點并將其組織成云，云端進行數據處理。不足是架構只給出了數據處理，未對WSNs 中能量與簇分布進行研究。Khandakar Ahmed 等人［4］提出一種云計算與WSNs 結合模式，通過事件匹配器與代理在云端查找對應存儲數據，不足是模式僅給出了數據如何進行存儲與查詢，未對WSNs 具體的能量與簇分布進行研究。劉宏宇等人［5］提出通過云計算對WSNs 數據進行統一管理，用戶直接通過云平臺管理數據，不足是該方案未對WSNs 能量與分簇進行研究。

通過對以上文獻總結得出，在大規模WSNs 環境下，云計算與節點調度結合算法主要針對數據處理，對WSNs 節點能量與簇分布研究較少。本文在此研究基礎上，提出基于云計算的異構WSNs 節點調度模型及其改進算法，模型通過將本地節點的算法執行遷移至云端，云端利用節點調度改進算法，動態生成節點調度方案，對節點進行動態調度。

1 改進調度模型與算法設計

1.1 改進節點調度模型設計

在初始階段，節點將自己狀態信息發送到基站，基站通過網關將狀態信息上傳到云端，云端運行改進調度算法，生成節點調度方案控制信息，通過網關與基站下發至對應節點，控制相應節點成簇。成簇后，節點首先將感知數據進行簇頭融合(考慮在簇頭融合是為減少無效信息傳輸，降低對網絡帶寬要求)，并上傳到該簇頭所在區域基站，基站將融合數據上傳至網關，最終由網關上傳數據至云端并在云端進行處理。同時，云端記錄接收上傳網關編號，在下次控制數據發送時通過該網關下達。調度模型如圖1 所示。

圖1 調度模型Fig 1 Schedule model

由于節點異構性，不同節點產生的數據類型格式不同，會影響云端算法執行的效率。算法對不同節點數據類型進行了統一，分為融合數據與控制數據。融合數據為簇頭融合數據，控制數據為云端調度方案數據。

1.2 改進調度算法

改進算法中，節點將自己的狀態信息通過網關上傳至云端，云端根據狀態信息判斷節點當前簇頭選舉輪數是否滿足第一輪或未收到簇頭通告次數是否等于最大規定次數。如滿足，則選用只考慮添加剩余能量因子的算法選取簇頭;如不滿足，則除考慮節點剩余能量外，還考慮節點與簇頭距離、節點與基站距離、上一輪與節點處于同一簇成員個數等因素，通過云端對每個節點執行評估函數選取簇頭。簇頭選取成功后，云端通過網關發送控制消息，指定相應節點成為簇頭，控制簇頭發送簇頭通告給其它節點，節點如未收到簇頭通告信息，則節點未收到簇頭通告值(NO_CH_ROUND++)自增1。節點收到通告后，根據通告信號強度，發送加入請求給簇頭，同時，在請求中攜帶自己的剩余能量、與簇頭和基站距離(距離可以使用RSSI［6］定位算法求出)、與節點上一輪處于同一簇成員個數等信息。簇頭收到信息后經過網關直接上傳至云端并更新自己狀態信息，云端根據節點加入請求中攜帶的與簇頭距離信息，判斷請求節點是否處于均勻分簇半徑R(R 為簇最優半徑)內，如果小于等于R，則記錄該節點編號，以便控制該節點加入簇，同時記錄加入簇的簇成員數目。如果簇成員數目達到(1－f)/f 個(f 為簇頭節點比例)，則云端控制簇頭不再接受其它節點加入該簇。當簇成員數目達到規定數目后，云端控制簇頭發送TDMA 時隙片段給簇成員，簇成員根據TDMA 消息，發送數據給簇頭，云端對該簇頭收集的歷史數據進行分析，生成發送閾值θ，并發送給簇頭。簇頭將融合數據與θ 作比較，如大于θ，則發送;否則，不發送。

1)剩余能量

算法在初始簇頭選取時，云端僅參考剩余能量因子Energys/Energyt，具體見公式(1)

從式(1)可知，能量因子在第一輪節點能量相同時相同，在后期簇頭選取時，剩余能量多的節點能量因子較大，對閾值T(ni)的影響就大，有更大概率當選為簇頭。

在下輪簇頭選取時，簇頭及時將節點加入簇請求報文中攜帶的剩余能量、與待加入簇頭距離、基站距離、上一輪與該節點同簇節點數目等信息上傳至云端并更新自己狀態信息，云端參考更新信息，結合模擬退火算法，利用評估函數，即式(2)，求取每個節點的評估函數值，云端優先選取評估函數值較大者為下一輪簇頭。

記E(ni)為節點ni目前的剩余能量，Dtosink(ni)為節點i 與基站距離，Dtocluster(ni)為節點i 與待加入簇頭距離，N(ni)表示與節點i 上一輪處于同一簇的成員數目，屬于簇cj的節點ni被選為下一輪簇頭的評估函數為

式中 pe，pd，pc，pn分別代表節點的剩余能量、節點距基站距離、節點距待加入簇頭距離、上一輪與節點同簇成員數，fe，fd，fc，fn分別為各自的權重，pe，pd，pc，pn如下式

式(3)求取在cj簇內各個簇成員節點的剩余能量信息;式(4)求取在cj簇內節點距離基站的信息，采用倒數是因為離基站越近的簇成員越有可能成為簇頭;式(5)求取在cj簇內節點距離簇頭的信息，采用倒數是因為距離簇頭越近的簇成員越有可能成為下一輪簇頭，因為距離越近能量消耗越少，而且下輪簇成員距離新簇頭距離更加接近;式(6)求取在cj簇內各個節點上一輪處于同一簇成員數，求取倒數是因為上一輪處于同一簇成員越多，該節點擔任簇頭后消耗的能量就越多，所以，Nni∈cj(ni)的選取應該越小越好，pn(ni，cj)對評估函數的影響就會更大，即上一輪同簇成員少的節點有更大概率擔任簇頭。

與第一輪簇頭選取算法不同的是，第一輪以后的簇頭選取算法不單考慮節點的剩余能量，還兼容考慮簇頭更新信息。網絡運行一段時間后可能出現網絡無簇頭的情況，云端判斷NO_CH_ROUND 是否達到設定的閾值，如達到則重新利用式(1)進行簇頭選取。

2)均勻分簇

首先，介紹有效覆蓋面積，在WSNs 中，一塊區域有可能被多個節點所覆蓋，如圖2 所示，節點n1的有效覆蓋面積Sn1為節點n1的覆蓋面積減去重復覆蓋區域面積Sc的50%，即。其次，如圖3 所示，在相鄰節點的覆蓋拓撲中，當節點ni所覆蓋的區域是一個邊長為r 的正六邊形時，節點ni所覆蓋的無縫面積最大［7］，即Sa=6×在改進算法中，假設簇頭比例為f，監測節點個數為n，則簇頭個數為f×n，每一個簇包含簇成員數目為，假設節點分布在一個面積為S的監測區域中，則每一個簇所占區域面積為S/(f×n)，根據最大覆蓋面積，每一個簇的面積為Sa，則Sa=S/(f×n)，所以可得簇最優半徑為所以，為達到對監測區域的完整覆蓋，需要設置簇頭間距在［2R(1－sin α)，2R(1+sin α)］之間，規定只有在簇頭R 以內的節點才能成為該簇成員，而且，簇頭記錄加入簇請求節點數目，直到節點數目達到個，然后，拒絕其它節點加入，這樣，不僅簇成員與簇頭之間的距離被限制在一個理想范圍內，而且，簇被均勻分布在監測區域，彌補了隨機成簇的缺點。

圖2 節點有效覆蓋面積Fig 2 Effective area covered by node

圖3 節點最大覆蓋面積Fig 3 The maximum coverage area of node

3)預測傳輸

改進數據傳輸算法使用單跳與多跳結合的帶預測的傳輸方式傳輸融合數據。云端對簇頭歷史數據進行并行分析，生成允許發送閾值θ，然后將閾值發送給簇頭，簇頭將待發送融合數據與閾值相比較，如大于閾值，則發送;否則，不發送。算法執行流程如圖4 所示。

2 仿真模型搭建

仿真軟件使用OMNET++，配合使用無線傳感器仿真框架MiXim 來實現能量模型和信號衰減。硬件模型使用德州儀器提供的2.4 GHz IEEE802.15.4 無線收發芯片CC2420［8］，其它參數根據文獻［9］設定見表1。

表1 硬件基本參數Fig 1 Basic parameters of hardware

3 結果與分析

3.1 節點調度結果與分析

實驗將50 個節點隨機分布在500 m×500 m 的正方形場景中，設置簇頭個數為5，各節點初始能量相同，各個節點分別對LEACH、LEACH—C、改進調度算法進行仿真，當所有節點能量耗盡時仿真結束，結果如圖5 ～圖10 所示。

圖4 改進算法流程圖Fig 4 Flow chart of improved algorithm

圖5 剩余節點信息Fig 5 Remaining node information

圖6 剩余能量信息Fig 6 Remaining energy information

圖7 均勻分簇作用后剩余節點信息Fig 7 Remaining node information after uniform clustering

圖8 均勻分簇作用后剩余能量信息Fig 8 Residual energy information after uniform clustering effect

圖9 剩余能量作用后剩余節點信息Fig 9 Remaining node information after remaining energy effect

圖10 剩余能量作用后剩余能量信息Fig 10 Remaining energy information after remaining energy effect

從圖5 與圖6 可以看出:三種算法中效果最好的是LEACH—C 算法，其次為改進算法，最差為LEACH 算法。LEACH—C 算法使用集中式簇頭選擇，避免了簇頭通告與節點加入請求，節省了能量，由于節點能耗大致相同，所以，在后期節點幾乎在同一時間死亡。改進算法節點在第一輪剩余能量因子相同，在開始效果與LEACH 算法相同，在第一輪后由于不只考慮節點的剩余能量，而且加入了距離和同一簇成員數目等信息，從剩余能量和數據傳輸能耗上降低了節點能耗。在成簇上使用均勻分簇，均衡了簇頭負載，在后期傳輸數據上更加注重數據有效性，節省了能量，在剩余節點與能量上效果優于LEACH 算法。由于采用了云計算，節點需要傳輸狀態與位置信息給云端，會造成部分能量消耗，效果沒有LEACH—C 算法好，不過在大規模WSNs 環境下，改進算法能夠比LEACH—C 算法更快地實現對WSNs的控制和數據的高效處理。從圖7 與圖8 可以看出:單獨在均勻分簇方面進行改進效果略優于LEACH 算法，由于單獨考慮均勻分簇，沒有加入剩余能量，會出現剩余能量少的節點擔任簇頭，但由于采用了均勻分簇，每個簇成員數目都大致相同，簇頭負載相對均衡，減少了某些簇內簇成員多，對簇頭負載過重的情況，與LEACH 算法相比降低了簇頭能量消耗的速度，在效果上略優于LEACH 算法。從圖9和圖10 可以看出:單獨在剩余能量方面進行改進效果優于LEACH 算法，由于簇頭選擇時每次都選擇能量多的、位置距離簇頭和基站近的節點擔任簇頭，避免了能量少的節點優先擔任簇頭，縮短了數據傳輸距離，降低了發送能耗，最終降低了簇頭死亡率。由于降低了簇頭死亡率，所以，整個簇內的能耗均勻地分布到每個節點上，提高了節點存活率。

3.2 融合數據處理結果與分析

3.2.1 融合數據處理

融合數據處理主要統計在不同融合數據量情況下，云端并行處理融合數據耗時，并由此推測大數據環境下異構數據處理效率。

數據由網關上傳至云端HDFS 采用分塊進行存儲，實驗數據對比見表2，實驗結果見圖11。

表2 融合數據處理耗時對比表Fig 2 Time consuming comparison of fused data processing

圖11 融合數據處理耗時對比Fig 11 Comparison of time consuming of fused data processing

3.2.2 融合數據處理結果分析

從圖11 可以看出:隨著數據量增大，并行環境下數據處理耗時相對穩定，維持在50 s 左右，但對于單機串行環境下數據處理耗時會隨著數據量增加而上升。這是由于云端環境基于Hadoop 分布式并行處理，當數據量增加時，耗時并不會顯著增加;相反，對于單機串行處理環境，主機之間的任務并行程度低，隨著數據量增加，任務耗時也會相應上升。實驗結果說明:并行數據處理相對單機串行數據處理在處理大規模環境下海量數據效率更高。

4 結 論

從實驗結果可以得出:改進調度算法在剩余能量與存活節點數目上，相比于LEACH 算法分別提高了28%和34%左右。說明改進算法確實可以有效地減少節點能量消耗，延長網絡生存周期。在融合數據處理耗時方面，并行環境下數據量的大小變化對處理耗時的影響比較小，單機串行環境下處理耗時受數據量大小變化影響較大。通過實驗對比，得出云環境下的融合數據處理對大規模WSNs 下產生的海量數據具有很好的處理效率。

［1］ 潘巨龍.無線傳感器網絡的異構性研究［J］.航空計算技術，2007，37(2):124－126.

［2］ 魏玉宏，孔韋韋.一種基于LEACH 協議高效節能的數據融合算法［J］.傳感器與微系統，2015，34(6):148－150.

［3］ 孫韓林，張 鵬，閆 崢，等.一種基于云計算的無線傳感網體系結構［J］.計算機應用研究，2013，30(12):3720－3723.

［4］ Ahmed K，Gregory M.Integrating wireless sensor networks with cloud computing［C］∥Seventh International Conference on Mobile Ad－Hoc and Sensor Networks，IEEE，2011:364－366.

［5］ 劉宏宇.基于無線傳感器網絡的森林環境監測云平臺研究與實現［D］.北京:中國林業科學研究院，2012.

［6］ 方 震，郭 鵬，張玉國.基于RSSI 測距分析［J］.傳感技術學報，2007，20(11):2526－2530.

［7］ Wang X，Yang Y，Zhang Z.A virtual rhomb grid－based movement－assisted sensor deployment algorithm in wireless sensor networks［C］∥International Multi－Symposiums on Computer and Computational Sciences，Harbin:IEEE Computer Society，2006:491－495.

［8］ 趙 海，劉 錚，紀書杰.一種無線傳感器網絡節點的設計與實現［［J］.東北大學學報:自然科學版，2009，30(6):809－812.

［9］ TI Instruments.2.4 GHz IEEE 802.15.4/Zig Bee－ready RF transceiver(Rev.B)Datasheet［EB/OL］.［2012—10—15］.http:∥www.ti.com/product/cc2420.