基于動態概率休眠調度機制的WSNs 拓撲控制算法*

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

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

0 引 言

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

為了有效恢復休眠節點引起的連通受損的局部拓撲結構，在保障網絡連通性的基礎上延長網絡的生命周期，本文提出一種融合了隨機調度(randomized scheduling，RS)［6］算法和層次型低能耗自適應分簇(low－energy adaptive clustering hierarchy，LEACH)算法［7］的動態概率休眠調度機制的拓撲控制(dynamic probability sleep－scheduling based topology control，DPSS—TC)算法。

1 算法設計

1.1 設計思想

本文采用讓成員節點以一定的概率進入休眠的休眠調度機制來均衡節點的能量消耗。算法的設計思想如圖1 所示。其中，n0為簇頭所屬簇內的成員節點數量，n'為可執行休眠調度的成員節點數量的閾值，p 為休眠概率的取值范圍;節點的工作狀態用標識符S.state 表示如下

遍歷節點的初始狀態，即S.state=1。簇頭根據所屬簇內的成員節點數量n0自適應地設定休眠概率p，執行隨機休眠調度，并有效恢復連通受損的局部拓撲。

1.2 DPSS—TC 算法的實現步驟

1.2.1 分簇并獲取鄰居信息

執行LEACH 算法后，簇內的每個成員節點向簇頭分別發送報文{ID，Er，Dt}，包括節點信息ID、節點當前剩余能量信息Er、成員節點與簇頭的距離Dt。簇頭統計成員節點的數量n0，而且，每個節點將獲得其所有1 跳鄰居完整的信息和自己所處位置到簇頭節點的通信跳數r。

1.2.2 休眠調度

為了實現簇內的連通，簇頭需根據簇內的成員節點數量n0動態地設置休眠概率p，以確保簇內有一定量的活躍節點。執行休眠調度后，為避免某些簇內的成員節點全休眠，因此，執行休眠調度后的成員節點中應至少存在n(n∈N+)個活躍節點

其中，標識符S.flag=1 表示簇內成員節點不執行休眠調度;S.flag=0 表示簇內成員節點執行休眠調度。當S.flag=0時，簇頭根據n0動態地設置休眠概率p，并向簇內的成員節點發送攜帶p 的hello—2 報文。

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

1.2.3 連通性的恢復

由于休眠節點會導致網絡的部分拓撲結構變化，因此，需要對連通失效的拓撲部分進行恢復，以便網絡保持良好的通信狀態。連通性判據如下

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

直至簇內相鄰兩跳內的活躍節點間正常通信，節點在該輪次的剩余時間內保持當前狀態，網絡轉入穩定的數據通信階段，節點周期性地執行該算法。

2 算法的仿真分析

2.1 節點休眠概率的設定

由于節點執行休眠判決時，每個節點獨立地以概率方式判斷該輪次中自身的狀態，每個節點做一次貝努利實驗。那么簇內存在n0個成員節點時，需做n0次貝努利實驗。

簇內的節點個數設為nt，休眠概率設為p，則節點的活躍概率為q=1－p;簇頭需保持在活躍狀態，故休眠調度的節點個數為n0=nt－1。簇內存在n(n=0，1，2，…，n0)個活躍節點的概率設為p(n)，則

簇內n0個成員節點中至少存在k(k=1，2，3，…，n0)個活躍節點的概率設為q(k)，則

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

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

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

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

2.2 性能分析

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

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

若n 的取值過大，某些簇內的成員節點經休眠調度后依然全處在活躍狀態，不能最大化節約節點的能量消耗。因此，n 的仿真參數取值為n∈［3，9］，n 與閾值n'的取值關系如表3 所示。

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

本文將網絡生命周期定義為網絡中所有節點全部進入死亡狀態時網絡持續的有效工作時間，分析 取不同參數值時對網絡生命周期的影響，如圖2 所示。

圖2 n 的取值對網絡生命周期的影響Fig 2 Influences of value of n on network lifetime

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

圖3 網絡生命周期的分析Fig 3 Analysis on network lifetime

通過仿真實驗可知，網絡的生命周期與網絡中節點的數量為近似線性比例關系。由于DPSS—TC 算法可進一步均衡節點的能量消耗，其在節能效果上優于LEACH 算法，并且在保障網絡連通的基礎上有效地延長了網絡的生命周期。

3 結 論

拓撲控制作為WSNs 的一種關鍵節能技術，通常在保持網絡重要特性如連通和覆蓋的前提下改變、簡化或優化網絡的拓撲來節省能量。仿真實驗表明:DPSS—TC 算法不僅能保證網絡的連通性，而且有效延長了網絡的存活周期。

［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］ 董 蕾，于宏毅，張 霞.一種無線傳感器網絡全連通群的休眠調度算法［J］.電子與信息學報，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］ 丁雷雷，高 飛，韓瑞艷.基于節點休眠機制的無線傳感器網絡覆蓋控制算法［J］.云南民族大學學報:自然科學版，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.