韓瑞艷，高 飛，李伯宇，劉小雨

(云南民族大學(xué) 電氣信息工程學(xué)院，云南 昆明650500)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)拓?fù)淇刂剖荳SNs 建網(wǎng)和通信的基礎(chǔ)，其控制方法主要采用節(jié)點(diǎn)功率控制和層次型拓?fù)淇刂苾纱箢悾?］。前者為傳感器節(jié)點(diǎn)選擇合適的發(fā)射功率，而后者采用基于休眠調(diào)度的拓?fù)淇刂茩C(jī)制，是一種較為經(jīng)典的方法，全連通群的休眠調(diào)度算法［2］，基于梯度的微傳感器休眠調(diào)度路由協(xié)議(gradient－based micro sensor routing protocol with sleep scheduling，GMSRP－SLE)［3］算法，分簇的地理拓?fù)淇刂?geographical topology control，GTC)［4］算法以 及 分 組 調(diào) 度 協(xié) 議(group－based scheduling protocol，GSP)［5］等算法都屬于此類方法，均可有效減少網(wǎng)絡(luò)總體能量消耗，并延長網(wǎng)絡(luò)的生命周期。上述算法在網(wǎng)絡(luò)節(jié)點(diǎn)密度較大時，所構(gòu)造的簇的數(shù)量較多，簇頭間信息交互量大，會造成能量不必要的開銷。而且，當(dāng)采用非均勻分簇和隨機(jī)休眠調(diào)度機(jī)制時，節(jié)點(diǎn)易出現(xiàn)休眠不均勻的現(xiàn)象，從而不能合理均衡地利用節(jié)點(diǎn)的能量，網(wǎng)絡(luò)的連通性也因此受到影響。

為了有效恢復(fù)休眠節(jié)點(diǎn)引起的連通受損的局部拓?fù)浣Y(jié)構(gòu)，在保障網(wǎng)絡(luò)連通性的基礎(chǔ)上延長網(wǎng)絡(luò)的生命周期，本文提出一種融合了隨機(jī)調(diào)度(randomized scheduling，RS)［6］算法和層次型低能耗自適應(yīng)分簇(low－energy adaptive clustering hierarchy，LEACH)算法［7］的動態(tài)概率休眠調(diào)度機(jī)制的拓?fù)淇刂?dynamic probability sleep－scheduling based topology control，DPSS—TC)算法。

1 算法設(shè)計

1.1 設(shè)計思想

本文采用讓成員節(jié)點(diǎn)以一定的概率進(jìn)入休眠的休眠調(diào)度機(jī)制來均衡節(jié)點(diǎn)的能量消耗。算法的設(shè)計思想如圖1 所示。其中，n0為簇頭所屬簇內(nèi)的成員節(jié)點(diǎn)數(shù)量，n'為可執(zhí)行休眠調(diào)度的成員節(jié)點(diǎn)數(shù)量的閾值，p 為休眠概率的取值范圍;節(jié)點(diǎn)的工作狀態(tài)用標(biāo)識符S.state 表示如下

遍歷節(jié)點(diǎn)的初始狀態(tài)，即S.state=1。簇頭根據(jù)所屬簇內(nèi)的成員節(jié)點(diǎn)數(shù)量n0自適應(yīng)地設(shè)定休眠概率p，執(zhí)行隨機(jī)休眠調(diào)度，并有效恢復(fù)連通受損的局部拓?fù)洹?/p>

1.2 DPSS—TC 算法的實(shí)現(xiàn)步驟

1.2.1 分簇并獲取鄰居信息

執(zhí)行LEACH 算法后，簇內(nèi)的每個成員節(jié)點(diǎn)向簇頭分別發(fā)送報文{ID，Er，Dt}，包括節(jié)點(diǎn)信息ID、節(jié)點(diǎn)當(dāng)前剩余能量信息Er、成員節(jié)點(diǎn)與簇頭的距離Dt。簇頭統(tǒng)計成員節(jié)點(diǎn)的數(shù)量n0，而且，每個節(jié)點(diǎn)將獲得其所有1 跳鄰居完整的信息和自己所處位置到簇頭節(jié)點(diǎn)的通信跳數(shù)r。

1.2.2 休眠調(diào)度

為了實(shí)現(xiàn)簇內(nèi)的連通，簇頭需根據(jù)簇內(nèi)的成員節(jié)點(diǎn)數(shù)量n0動態(tài)地設(shè)置休眠概率p，以確保簇內(nèi)有一定量的活躍節(jié)點(diǎn)。執(zhí)行休眠調(diào)度后，為避免某些簇內(nèi)的成員節(jié)點(diǎn)全休眠，因此，執(zhí)行休眠調(diào)度后的成員節(jié)點(diǎn)中應(yīng)至少存在n(n∈N+)個活躍節(jié)點(diǎn)

其中，標(biāo)識符S.flag=1 表示簇內(nèi)成員節(jié)點(diǎn)不執(zhí)行休眠調(diào)度;S.flag=0 表示簇內(nèi)成員節(jié)點(diǎn)執(zhí)行休眠調(diào)度。當(dāng)S.flag=0時，簇頭根據(jù)n0動態(tài)地設(shè)置休眠概率p，并向簇內(nèi)的成員節(jié)點(diǎn)發(fā)送攜帶p 的hello—2 報文。

由于休眠節(jié)點(diǎn)易造成部分通信鏈路中斷，簇頭無法進(jìn)一步判斷簇內(nèi)的連通性能。因此，節(jié)點(diǎn)在休眠之前，需增加一個預(yù)處理過程，即各個成員節(jié)點(diǎn)向自己所屬簇內(nèi)的簇頭發(fā)送hello—3 報文，報文中攜帶自身的狀態(tài)信息，節(jié)點(diǎn)發(fā)送報文hello—3 之后，節(jié)點(diǎn)才能進(jìn)入到相應(yīng)的休眠狀態(tài)或活躍狀態(tài)。

1.2.3 連通性的恢復(fù)

由于休眠節(jié)點(diǎn)會導(dǎo)致網(wǎng)絡(luò)的部分拓?fù)浣Y(jié)構(gòu)變化，因此，需要對連通失效的拓?fù)洳糠诌M(jìn)行恢復(fù)，以便網(wǎng)絡(luò)保持良好的通信狀態(tài)。連通性判據(jù)如下

其中，標(biāo)識符S.connectivity=1 表示簇內(nèi)的連通性良好，S.connectivity=0 表示簇內(nèi)的連通性有待進(jìn)一步判決;r.active 表示活躍節(jié)點(diǎn)分布在與所屬簇頭相距的r 跳。若S.connectivity，則根據(jù)中斷鏈路是否存在休眠節(jié)點(diǎn)的情況，采取如下調(diào)度措施:1)若兩個不連通的活躍節(jié)點(diǎn)間存在休眠節(jié)點(diǎn)，需強(qiáng)制性喚醒休眠節(jié)點(diǎn);2)若不存在休眠節(jié)點(diǎn)，則提高相應(yīng)活躍節(jié)點(diǎn)的發(fā)射功率。

直至簇內(nèi)相鄰兩跳內(nèi)的活躍節(jié)點(diǎn)間正常通信，節(jié)點(diǎn)在該輪次的剩余時間內(nèi)保持當(dāng)前狀態(tài)，網(wǎng)絡(luò)轉(zhuǎn)入穩(wěn)定的數(shù)據(jù)通信階段，節(jié)點(diǎn)周期性地執(zhí)行該算法。

2 算法的仿真分析

2.1 節(jié)點(diǎn)休眠概率的設(shè)定

由于節(jié)點(diǎn)執(zhí)行休眠判決時，每個節(jié)點(diǎn)獨(dú)立地以概率方式判斷該輪次中自身的狀態(tài)，每個節(jié)點(diǎn)做一次貝努利實(shí)驗(yàn)。那么簇內(nèi)存在n0個成員節(jié)點(diǎn)時，需做n0次貝努利實(shí)驗(yàn)。

簇內(nèi)的節(jié)點(diǎn)個數(shù)設(shè)為nt，休眠概率設(shè)為p，則節(jié)點(diǎn)的活躍概率為q=1－p;簇頭需保持在活躍狀態(tài)，故休眠調(diào)度的節(jié)點(diǎn)個數(shù)為n0=nt－1。簇內(nèi)存在n(n=0，1，2，…，n0)個活躍節(jié)點(diǎn)的概率設(shè)為p(n)，則

簇內(nèi)n0個成員節(jié)點(diǎn)中至少存在k(k=1，2，3，…，n0)個活躍節(jié)點(diǎn)的概率設(shè)為q(k)，則

由k≤n0可知(k－1)＜n0，由于，顯然0≤，故q(k)的取值范圍為(0，1］。為了提高運(yùn)算的精確性，將式(2)所得結(jié)果小數(shù)點(diǎn)后的第四位四舍五入，若取值為1，即q(k)的概率值為1，說明該次實(shí)驗(yàn)為必然事件。

從上述分析可知，由式(2)可知n0與p 的關(guān)系，將“執(zhí)行休眠調(diào)度后的成員節(jié)點(diǎn)中存在至少n 個活躍節(jié)點(diǎn)”設(shè)為事件A。分析n=3 時，事件A 必然發(fā)生時所需p 的取值范圍，如表1 所示。

經(jīng)計算可知，p(A)={n|n0≤n}=Φ;從表中數(shù)據(jù)可知，p(A)={n|n0∈［4，6］，p=0.1}=Φ。因此，p(A)={n|n0＜n'}=Φ。因此，當(dāng)n0＜n'時，則說明簇內(nèi)成員節(jié)點(diǎn)較為稀少，為保證監(jiān)測的有效性和可靠性，節(jié)點(diǎn)均保持在活躍狀態(tài);當(dāng)n0≥n'時，簇內(nèi)成員節(jié)點(diǎn)執(zhí)行休眠調(diào)度。

表1 休眠概率p 的取值范圍Tab 1 Value range of dormant probability

2.2 性能分析

本文采用Matlab 對算法進(jìn)行仿真分析，其中，LEACH算法部分的仿真參數(shù)值一般為固定值，這些參數(shù)的具體設(shè)置如表2 所示。其他仿真參數(shù)值設(shè)置如下:在200 m×200 m的監(jiān)測區(qū)域內(nèi)，隨機(jī)撒布s(100≤s≤200)個傳感器節(jié)點(diǎn)，Sink 節(jié)點(diǎn)位于(0，0)m 處;節(jié)點(diǎn)的能量均等且具有相同的通信半徑，其初始能量E0為0.5 J;節(jié)點(diǎn)在活躍狀態(tài)下單位時間能耗為10 μJ/s，在休眠狀態(tài)下的單位時間能耗為100 nJ/s，節(jié)點(diǎn)失效的能量閾值為10 μJ，節(jié)點(diǎn)提高發(fā)射功率時單位時間能耗為1 nJ/s。此外，不考慮分簇后每一輪次成員節(jié)點(diǎn)進(jìn)行報文信息交互時的能量消耗。

表2 LEACH 算法部分仿真參數(shù)Tab 2 Partial simulation parameters of LEACH algorithm

若n 的取值過大，某些簇內(nèi)的成員節(jié)點(diǎn)經(jīng)休眠調(diào)度后依然全處在活躍狀態(tài)，不能最大化節(jié)約節(jié)點(diǎn)的能量消耗。因此，n 的仿真參數(shù)取值為n∈［3，9］，n 與閾值n'的取值關(guān)系如表3 所示。

表3 滿足n 時n'的最小值Tab 3 The minimum value of n'to meet n

本文將網(wǎng)絡(luò)生命周期定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn)全部進(jìn)入死亡狀態(tài)時網(wǎng)絡(luò)持續(xù)的有效工作時間，分析 取不同參數(shù)值時對網(wǎng)絡(luò)生命周期的影響，如圖2 所示。

圖2 n 的取值對網(wǎng)絡(luò)生命周期的影響Fig 2 Influences of value of n on network lifetime

從圖2 可知，當(dāng)n 一定時，網(wǎng)絡(luò)的存活輪次隨節(jié)點(diǎn)數(shù)量的增加而增加;當(dāng)節(jié)點(diǎn)數(shù)量一定時，n 的取值對網(wǎng)絡(luò)的存活時間影響不大，本文取n=3。比較DPSS—TC 算法和LEACH 算法對網(wǎng)絡(luò)生命周期的影響，如圖3 所示。

圖3 網(wǎng)絡(luò)生命周期的分析Fig 3 Analysis on network lifetime

通過仿真實(shí)驗(yàn)可知，網(wǎng)絡(luò)的生命周期與網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量為近似線性比例關(guān)系。由于DPSS—TC 算法可進(jìn)一步均衡節(jié)點(diǎn)的能量消耗，其在節(jié)能效果上優(yōu)于LEACH 算法，并且在保障網(wǎng)絡(luò)連通的基礎(chǔ)上有效地延長了網(wǎng)絡(luò)的生命周期。

3 結(jié) 論

拓?fù)淇刂谱鳛閃SNs 的一種關(guān)鍵節(jié)能技術(shù)，通常在保持網(wǎng)絡(luò)重要特性如連通和覆蓋的前提下改變、簡化或優(yōu)化網(wǎng)絡(luò)的拓?fù)鋪砉?jié)省能量。仿真實(shí)驗(yàn)表明:DPSS—TC 算法不僅能保證網(wǎng)絡(luò)的連通性，而且有效延長了網(wǎng)絡(luò)的存活周期。

［1］ Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.Communications Magazine，IEEE，2002，40(8):102－114.

［2］ 董 蕾，于宏毅，張 霞.一種無線傳感器網(wǎng)絡(luò)全連通群的休眠調(diào)度算法［J］.電子與信息學(xué)報，2007，29(5):1220－1223.

［3］ Gao D，Zheng T，Zhang S，et al.Improved gradient－based micro sensor routing protocol with node sleep scheduling in wireless sensor networks［C］∥2010 IEEE 72nd Vehicular Technology Conference，VTC 2010 Fall，IEEE，2010:1－5.

［4］ Zebbane B，Chenait M，Badache N.Towards an energy－efficient algorithm based sleep－scheduling for wireless sensor networks［C］∥2012 The 5th International Conference on New Technologies，Mobility and Security(NTMS)，IEEE，2012:1－4.

［5］ Zebbane B，Chenait M，Badache N.Enhancing the sensor network lifetime by topology control and sleep－scheduling［C］∥2013 International Conference on Smart Communications in Network Technologies(SaCoNeT)，IEEE，2013:1－5.

［6］ 丁雷雷，高 飛，韓瑞艷.基于節(jié)點(diǎn)休眠機(jī)制的無線傳感器網(wǎng)絡(luò)覆蓋控制算法［J］.云南民族大學(xué)學(xué)報:自然科學(xué)版，2015，24(3):230－234.

［7］ Xu Y，Heidemann J，Estrin D.Adaptive energy－conserving routing for multihop Ad Hoc networks［R］.Los Angeles:USC，2000.

［8］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.