移動Sink的傳感器網絡路徑優化策略

于志博，孔祥雪，裴金金

(天津大學 電氣與自動化工程學院，天津 300072)

?

移動Sink的傳感器網絡路徑優化策略

于志博，孔祥雪，裴金金

(天津大學 電氣與自動化工程學院，天津 300072)

在無線傳感器網絡(WSNs)中引入移動Sink可以避免網絡擁塞和能量空洞并降低網絡能耗，但由于移動速度的限制導致時延較大。針對這一問題，提出了時延約束下的移動Sink路徑優化策略，根據時延和網絡能耗之間的關系設計了可調節的節點權重，通過模擬退火遺傳算法得到最優節點權重，并依據此權重通過迭代得到匯聚節點和最佳移動路徑。仿真結果表明:該策略能保證在滿足時延約束的前提下降低網絡能耗，且收斂速度快。

無線傳感器網絡； 移動Sink； 節點權重； 模擬退火遺傳算法； 路徑優化

0 引 言

在無線傳感器網絡(wireless sensor networks，WSNs)中，如何降低能耗是該領域研究重點。設計高效節能的軟硬件和通信協議在一定程度上降低了能耗[1,2]，但不能改變由于Sink位置固定導致的網絡擁塞和能量空洞問題。

采用移動Sink不僅避免了上述問題，還極大提高了網絡生存時間[3]，但會產生較大時延。為了取得能耗與時延的折中，文獻[4,5]通過限制每個節點數據轉發跳數選擇匯聚節點并通過匯聚節點建立路徑。文獻[4]在最短路徑樹上從最遠葉節點開始迭代地尋找滿足跳數要求的匯聚節點，而文獻[5]從根節點開始根據跳數尋找匯聚節點，再根據匯聚節點之間及與其他節點間的拓撲關系調整匯聚節點的位置和個數。文獻[6,7]從全網范圍內考慮所有節點距離各自所屬匯聚節點的總跳數，使得滿足時延條件下總跳數最少。文獻[6]建立最小連通支配集作為匯聚節點的候選節點，再根據候選節點權重進行刪減直到滿足時延要求。文獻[7]則根據節點權重從所有節點中選擇匯聚節點，直到達到時延要求。

時延和網絡能耗是基于移動Sink的WSNs重要性能指標。鑒于此，本文研究了滿足時延約束下網絡能耗最小的移動Sink路徑優化策略。根據能耗和時延的關系建立了優化模型，并設計了可調節的節點權重，通過模擬退火遺傳算法(simulated annealing genetic algorithm，SAGA)尋找最優節點權重，提出了基于SAGA權重的路徑優化(SAGA weight-based path optimization，SWPO)算法得到Sink移動路徑。該策略能有效降低網絡能耗，且收斂速度快。

1 網絡模型

本文考慮由一個移動Sink和n個傳感器節點組成的WSNs，節點通信半徑為R，網絡是全連通的，允許時延為t。匯聚節點由網絡周期性地選取，并緩存普通節點傳輸的數據。Sink以恒定速度v從監測區域邊緣出發，依次訪問匯聚節點收集數據，并最終返回起點，該過程稱為一輪。該網絡可用圖G=(S,B)表示。其中S={si}為節點集合，B={(si,sj)|D(si,sj)≤R}為通信鏈路集合，D(si,sj)為兩節點間歐式距離。H={hi}為匯聚節點集合，且H?S。圖1為基于移動Sink的WSNs示意圖。在基于移動Sink的WSNs中，要綜合考慮網絡能耗與時延。本文目標是滿足數據時延的前提下，實現網絡能耗的最小化。

圖1 基于移動Sink的WSNs示意圖Fig 1 Illustration of mobile sink-based WSNs

最大數據時延是Sink訪問所有匯聚節點所需的時間。路徑越長，時延就越大。對于給定的時延t，滿足

(1)

式中 hs為起點。

傳輸能耗占網絡能耗比重很大，故本文僅考慮傳輸能耗。節點si單輪中采集的數據量為p，該數據傳輸至匯聚節點并由Sink收集過程中所有節點能耗為

Eci=cip(et+er)+pet

(2)

式中 ci為si到其所屬匯聚節點的跳數，節點通過最短路由方式將數據傳輸給距自己跳數最少的匯聚節點，et和er分別表示發送和接收1 bit數據的能耗。單輪中所有節點數據最終被Sink收集過程中全網能耗為

(3)

式中 c為所有節點到其所屬匯聚節點的總跳數。

(4)

由式(3)可得，全網能耗取決于c。故時延約束下的網絡能耗最小化問題等價于時延受限的最小跳數問題(minimum hop counts under the delay constrains，MHCDC)，即從S中選取一組節點加入到H中，滿足Sink遍歷H中節點并返回的路徑長度少于規定時延內的距離，并使得總跳數最小，如式(5)所示

(5)

2 算法設計

2.1 節點權重

由于在MHCDC問題中需要最小化總跳數，并限制路徑長度。本文定義節點si的權重如式(6)所示

(6)

式中 c(H)和LTSP(H)分別為匯聚節點集為H時的總跳數和最短路徑長度。分子表示si加入到H中總跳數的減少量，減少量越多，si被選為匯聚節點的機會越大；分母表示si加入到H中路徑長度的增加量，增加量越少，si被選為匯聚節點的概率越大。u ∈(0,1)為調節因子，負責調節路徑長度增加量與總跳數減少量的影響程度，使節點權重發生變化，根據權重得到的匯聚節點及對應的路徑和網絡能耗會改變。

2.2 基于u值的權重優化

考慮到u值變化會改變路徑長度增加量和總跳數減少量的影響程度，采用SAGA對權重的u值進行優化，以獲得優化的Sink路徑。優化過程中，將SA法作為GA求解過程中的個體替換策略，實現全局最優，同時收斂速度較快。步驟如下：

1)初始化：初始化GA種群數目、遺傳代數、變異概率及SA初始溫度、終止溫度和每個溫度下迭代次數等；

2)隨機產生初始種群：對種群中的每個個體進行二進制編碼；

3)將每個種群中的個體帶入式(6)中，并得到每個個體對應的匯聚節點、路徑及網絡能耗，并計算適應度；

4)進行交叉、變異操作；

5)使用SA對個體進行選擇操作；

6)判斷是否達到最大代數，若滿足，則結束；若不滿足，則將步驟(5)得到的個體重新進行步驟(3)操作。

2.3 基于SAGA權重的路徑優化算法

本文采用Floyd Warshall算法求取路由，得到總跳數c。為求取最短路徑，采用文獻[8]中方法求解TSP問題。首先，所有節點根據最優u值和式(6)計算各自權重。然后，將權重最大的節點加入到H中。隨著H中節點變化，S中節點的權重也會變化，更新S中所有節點權重，再將權重最大的節點加入到H中，不斷迭代，直到滿足式(1)結束。最后得到最小網絡能耗下的匯聚節點和路徑。

3 仿真分析

為考察算法性能，對本文提出的SWPO算法進行性能分析，并與基于效用的貪心算法來選擇CP節點(utility-based greedy heuristic for choosing collection point,CPUG)算法[7]進行了比較。在仿真實驗中，200個節點隨機部署在200 m×200 m區域內，節點初始電量為500 J，通信半徑為30 m，Sink速度為1 m/s，每輪從每個節點收集30 kbit數據，時延上限為5 min。采用文獻[6]的能耗模型。

3.1 時延上限對網絡能耗的影響

時延上限會限制移動路徑的長度，進而影響匯聚節點的選擇，導致所有節點到其所屬匯聚節點跳數和發生變化。當移動速度不變時，隨著時延上限的增加，Sink可移動的路徑長度增加，所有節點到其所屬匯聚節點跳數和減少，從而網絡能耗降低。從圖2可以看出:兩種算法隨著時延上限的增加網絡能耗降低，并且SWPO算法性能優于CPUG。

圖2 時延上限與網絡能耗的關系Fig 2 Relationship between delay bound and energy consumption of network

3.2 移動速度對網絡能耗的影響

隨著Sink移動速度的增加，在規定的時延要求下，可移動的路徑長度增加，所有節點到其所屬匯聚節點跳數和減少，從而網絡能耗降低。圖3給出了不同移動速度下網絡能耗的變化。兩種算法的網絡能耗均隨著Sink速度的增加而降低，且SWPO算法性能優于CPUG。

圖3 移動速度與網絡能耗的關系Fig 3 Relationship between moving speed and energy consumption of network

3.3 節點數量對網絡能耗的影響

隨著網絡節點數量的增加，由于路徑長度沒有變化，匯聚節點所屬的節點數量增加，全網傳輸總跳數增加，導致網絡能耗增加。圖4反映了兩種算法下網絡能耗均隨著節點數量的增加而增加，且SWPO算法性能優于CPUG。

圖4 節點數量與網絡能耗的關系Fig 4 Relationship between number of nodes and energy consumption of networks

3.4 SAGA與GA對比

由圖5可以看出使用本文SAGA求解，在30代已經穩定在最優解，而使用GA求解，在38代時獲得穩定最優解。這是由于本文在SAGA中，使用SA替代GA中的選擇操作，實現全局快速尋優，收斂速度較快。

圖5 遺傳代數與網絡能耗的關系Fig 5 Relationship between genetic algebra and energy consumption of networks

4 結 論

本文研究了基于移動Sink的傳感器網絡時延受限的路徑優化策略，并提出了SWPO算法。根據數據時延和網絡能耗的關系設計了可調節的節點權重，采用SAGA算法得到最優的節點權重，根據該權重得到匯聚節點，從而得到網絡能耗最小的移動路徑。仿真結果表明，該算法能有效地選擇匯聚節點，規劃移動路徑，降低網絡能耗，且收斂速度快。

[1] Tang Lei,Sun Yanjun,Gurewitz O,et al.PW-MAC:An energy-efficient predictive-wakeup MAC protocol for wireless sensor networks[C]∥IEEE INFOCOM 2011 Proceedings,Shanghai,China:IEEE,2011:1305-1313.

[2] Mikhaylov K,Tervonen J.Optimization of microcontroller hardware parameters for wireless sensor networks node power consumption and lifetime improvement[C]∥2010 International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT),Moscow,Russia:IEEE,2010:1150-1156.

[3] Salarian H,Chin K W,Naghdy F.An energy-efficient mobile-sink path selection strategy for wireless sensor networks[J].IEEE Transactions on Vehicular Technology,2014,63(5):2407-2419.

[4] Zhao Miao,Yang Yuanyuan.Bounded relay hop mobile data ga-thering in wireless sensor networks[J].IEEE Transactions on Computers,2012,61(2):265-277.[5] Chowdhury S,Giri C.Data collection point based mobile data gathering scheme with relay hop constraint[C]∥2013 International Conference on Advances in Computing,Communications and Informatics(ICACCI),Mysore,India:IEEE,2013:282-287.

[6] 丁 杰,劉丹譜.移動Sink環境下的無線傳感器網絡數據收集節能算法[J].北京郵電大學學報,2013,36(5):51-55.

[7] 張希偉,沈 琳,蔣益峰.移動協助傳感器網絡中Sink的路徑優化策略[J].通信學報,2013,34(2):85-93.

[8] Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms[M].3rd ed.Cambridge,America:The MIT Press,2009:404-405.

Mobile sink-based path optimization strategy in wireless sensor networks

YU Zhi-bo,KONG Xiang-xue,PEI Jin-jin

(School of Electrical Engineering and Automation,Tianjin University,Tianjin 300072,China)

Introducing mobile sink in wireless sensor networks(WSNs)can avoid network congestion and energy hole and reduce energy consumption of network,but it lead to large delay because of limitation of moving speed.Aiming at this problem,path optimization strategy of mobile sink under delay constrains is proposed.Adjustable node weight is designed according to relationship between delay and energy consumption of network.The optimal node weight is obtained through simulated annealing genetic algorithm.The sink nodes and the optimal moving path are acquired through iteration procedure based on the optimal node weight.Simulation results show that the strategy can reduce energy consumption network and have fast convergence under the premise of meeting delay constrains.

wireless sensor networks(WSNs);mobile sink;node weight;simulated annealing genetic algorithm;path optimization

10.13873/J.1000—9787(2016)11—0044—03

2016—01—04

TP 393

A

1000—9787(2016)11—0044—03

于志博(1990-)，男，滿族，河北秦皇島人，碩士研究生，研究方向為無線傳感器網絡。