劉東平，馬利亞，楊 軍

(1.寧夏大學(xué) 數(shù)學(xué)計算機(jī)學(xué)院，寧夏 銀川750021;2.寧夏醫(yī)科大學(xué) 總醫(yī)院，寧夏 銀川750000;3.寧夏大學(xué) 計算機(jī)網(wǎng)絡(luò)管理中心，寧夏 銀川750021)

0 引 言

傳統(tǒng)無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)監(jiān)測區(qū)域范圍有限、節(jié)點類型與感知數(shù)據(jù)類型單一、節(jié)點產(chǎn)生感知數(shù)據(jù)量小，網(wǎng)絡(luò)異構(gòu)性不突出。在大規(guī)模WSNs 中網(wǎng)絡(luò)異構(gòu)性較傳統(tǒng)WSNs 更加突出，表現(xiàn)為網(wǎng)絡(luò)監(jiān)測區(qū)域變大、節(jié)點數(shù)量眾多、感知數(shù)據(jù)格式、節(jié)點地位不同［1］，對節(jié)點調(diào)度提出了新的要求。

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

通過對以上文獻(xiàn)總結(jié)得出，在大規(guī)模WSNs 環(huán)境下，云計算與節(jié)點調(diào)度結(jié)合算法主要針對數(shù)據(jù)處理，對WSNs 節(jié)點能量與簇分布研究較少。本文在此研究基礎(chǔ)上，提出基于云計算的異構(gòu)WSNs 節(jié)點調(diào)度模型及其改進(jìn)算法，模型通過將本地節(jié)點的算法執(zhí)行遷移至云端，云端利用節(jié)點調(diào)度改進(jìn)算法，動態(tài)生成節(jié)點調(diào)度方案，對節(jié)點進(jìn)行動態(tài)調(diào)度。

1 改進(jìn)調(diào)度模型與算法設(shè)計

1.1 改進(jìn)節(jié)點調(diào)度模型設(shè)計

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

圖1 調(diào)度模型Fig 1 Schedule model

由于節(jié)點異構(gòu)性，不同節(jié)點產(chǎn)生的數(shù)據(jù)類型格式不同，會影響云端算法執(zhí)行的效率。算法對不同節(jié)點數(shù)據(jù)類型進(jìn)行了統(tǒng)一，分為融合數(shù)據(jù)與控制數(shù)據(jù)。融合數(shù)據(jù)為簇頭融合數(shù)據(jù)，控制數(shù)據(jù)為云端調(diào)度方案數(shù)據(jù)。

1.2 改進(jìn)調(diào)度算法

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

1)剩余能量

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

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

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

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

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

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

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

2)均勻分簇

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

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

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

3)預(yù)測傳輸

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

2 仿真模型搭建

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

表1 硬件基本參數(shù)Fig 1 Basic parameters of hardware

3 結(jié)果與分析

3.1 節(jié)點調(diào)度結(jié)果與分析

實驗將50 個節(jié)點隨機(jī)分布在500 m×500 m 的正方形場景中，設(shè)置簇頭個數(shù)為5，各節(jié)點初始能量相同，各個節(jié)點分別對LEACH、LEACH—C、改進(jìn)調(diào)度算法進(jìn)行仿真，當(dāng)所有節(jié)點能量耗盡時仿真結(jié)束，結(jié)果如圖5 ～圖10 所示。

圖4 改進(jìn)算法流程圖Fig 4 Flow chart of improved algorithm

圖5 剩余節(jié)點信息Fig 5 Remaining node information

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

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

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

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

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

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

3.2 融合數(shù)據(jù)處理結(jié)果與分析

3.2.1 融合數(shù)據(jù)處理

融合數(shù)據(jù)處理主要統(tǒng)計在不同融合數(shù)據(jù)量情況下，云端并行處理融合數(shù)據(jù)耗時，并由此推測大數(shù)據(jù)環(huán)境下異構(gòu)數(shù)據(jù)處理效率。

數(shù)據(jù)由網(wǎng)關(guān)上傳至云端HDFS 采用分塊進(jìn)行存儲，實驗數(shù)據(jù)對比見表2，實驗結(jié)果見圖11。

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

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

3.2.2 融合數(shù)據(jù)處理結(jié)果分析

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

4 結(jié) 論

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

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

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

［3］ 孫韓林，張 鵬，閆 崢，等.一種基于云計算的無線傳感網(wǎng)體系結(jié)構(gòu)［J］.計算機(jī)應(yīng)用研究，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］ 劉宏宇.基于無線傳感器網(wǎng)絡(luò)的森林環(huán)境監(jiān)測云平臺研究與實現(xiàn)［D］.北京:中國林業(yè)科學(xué)研究院，2012.

［6］ 方 震，郭 鵬，張玉國.基于RSSI 測距分析［J］.傳感技術(shù)學(xué)報，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ì)書杰.一種無線傳感器網(wǎng)絡(luò)節(jié)點的設(shè)計與實現(xiàn)［［J］.東北大學(xué)學(xué)報:自然科學(xué)版，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.