移動Sink的傳感器網(wǎng)絡(luò)路徑優(yōu)化策略

于志博，孔祥雪，裴金金

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

?

移動Sink的傳感器網(wǎng)絡(luò)路徑優(yōu)化策略

于志博，孔祥雪，裴金金

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

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

無線傳感器網(wǎng)絡(luò)； 移動Sink； 節(jié)點(diǎn)權(quán)重； 模擬退火遺傳算法； 路徑優(yōu)化

0 引 言

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

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

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

1 網(wǎng)絡(luò)模型

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

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

最大數(shù)據(jù)時延是Sink訪問所有匯聚節(jié)點(diǎn)所需的時間。路徑越長，時延就越大。對于給定的時延t，滿足

(1)

式中 hs為起點(diǎn)。

傳輸能耗占網(wǎng)絡(luò)能耗比重很大，故本文僅考慮傳輸能耗。節(jié)點(diǎn)si單輪中采集的數(shù)據(jù)量為p，該數(shù)據(jù)傳輸至匯聚節(jié)點(diǎn)并由Sink收集過程中所有節(jié)點(diǎn)能耗為

Eci=cip(et+er)+pet

(2)

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

(3)

式中 c為所有節(jié)點(diǎn)到其所屬匯聚節(jié)點(diǎn)的總跳數(shù)。

(4)

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

(5)

2 算法設(shè)計(jì)

2.1 節(jié)點(diǎn)權(quán)重

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

(6)

式中 c(H)和LTSP(H)分別為匯聚節(jié)點(diǎn)集為H時的總跳數(shù)和最短路徑長度。分子表示si加入到H中總跳數(shù)的減少量，減少量越多，si被選為匯聚節(jié)點(diǎn)的機(jī)會越大；分母表示si加入到H中路徑長度的增加量，增加量越少，si被選為匯聚節(jié)點(diǎn)的概率越大。u ∈(0,1)為調(diào)節(jié)因子，負(fù)責(zé)調(diào)節(jié)路徑長度增加量與總跳數(shù)減少量的影響程度，使節(jié)點(diǎn)權(quán)重發(fā)生變化，根據(jù)權(quán)重得到的匯聚節(jié)點(diǎn)及對應(yīng)的路徑和網(wǎng)絡(luò)能耗會改變。

2.2 基于u值的權(quán)重優(yōu)化

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

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

2)隨機(jī)產(chǎn)生初始種群：對種群中的每個個體進(jìn)行二進(jìn)制編碼；

3)將每個種群中的個體帶入式(6)中，并得到每個個體對應(yīng)的匯聚節(jié)點(diǎn)、路徑及網(wǎng)絡(luò)能耗，并計(jì)算適應(yīng)度；

4)進(jìn)行交叉、變異操作；

5)使用SA對個體進(jìn)行選擇操作；

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

2.3 基于SAGA權(quán)重的路徑優(yōu)化算法

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

3 仿真分析

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

3.1 時延上限對網(wǎng)絡(luò)能耗的影響

時延上限會限制移動路徑的長度，進(jìn)而影響匯聚節(jié)點(diǎn)的選擇，導(dǎo)致所有節(jié)點(diǎn)到其所屬匯聚節(jié)點(diǎn)跳數(shù)和發(fā)生變化。當(dāng)移動速度不變時，隨著時延上限的增加，Sink可移動的路徑長度增加，所有節(jié)點(diǎn)到其所屬匯聚節(jié)點(diǎn)跳數(shù)和減少，從而網(wǎng)絡(luò)能耗降低。從圖2可以看出:兩種算法隨著時延上限的增加網(wǎng)絡(luò)能耗降低，并且SWPO算法性能優(yōu)于CPUG。

圖2 時延上限與網(wǎng)絡(luò)能耗的關(guān)系Fig 2 Relationship between delay bound and energy consumption of network

3.2 移動速度對網(wǎng)絡(luò)能耗的影響

隨著Sink移動速度的增加，在規(guī)定的時延要求下，可移動的路徑長度增加，所有節(jié)點(diǎn)到其所屬匯聚節(jié)點(diǎn)跳數(shù)和減少，從而網(wǎng)絡(luò)能耗降低。圖3給出了不同移動速度下網(wǎng)絡(luò)能耗的變化。兩種算法的網(wǎng)絡(luò)能耗均隨著Sink速度的增加而降低，且SWPO算法性能優(yōu)于CPUG。

圖3 移動速度與網(wǎng)絡(luò)能耗的關(guān)系Fig 3 Relationship between moving speed and energy consumption of network

3.3 節(jié)點(diǎn)數(shù)量對網(wǎng)絡(luò)能耗的影響

隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的增加，由于路徑長度沒有變化，匯聚節(jié)點(diǎn)所屬的節(jié)點(diǎn)數(shù)量增加，全網(wǎng)傳輸總跳數(shù)增加，導(dǎo)致網(wǎng)絡(luò)能耗增加。圖4反映了兩種算法下網(wǎng)絡(luò)能耗均隨著節(jié)點(diǎn)數(shù)量的增加而增加，且SWPO算法性能優(yōu)于CPUG。

圖4 節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)能耗的關(guān)系Fig 4 Relationship between number of nodes and energy consumption of networks

3.4 SAGA與GA對比

由圖5可以看出使用本文SAGA求解，在30代已經(jīng)穩(wěn)定在最優(yōu)解，而使用GA求解，在38代時獲得穩(wěn)定最優(yōu)解。這是由于本文在SAGA中，使用SA替代GA中的選擇操作，實(shí)現(xiàn)全局快速尋優(yōu)，收斂速度較快。

圖5 遺傳代數(shù)與網(wǎng)絡(luò)能耗的關(guān)系Fig 5 Relationship between genetic algebra and energy consumption of networks

4 結(jié) 論

本文研究了基于移動Sink的傳感器網(wǎng)絡(luò)時延受限的路徑優(yōu)化策略，并提出了SWPO算法。根據(jù)數(shù)據(jù)時延和網(wǎng)絡(luò)能耗的關(guān)系設(shè)計(jì)了可調(diào)節(jié)的節(jié)點(diǎn)權(quán)重，采用SAGA算法得到最優(yōu)的節(jié)點(diǎn)權(quán)重，根據(jù)該權(quán)重得到匯聚節(jié)點(diǎn)，從而得到網(wǎng)絡(luò)能耗最小的移動路徑。仿真結(jié)果表明，該算法能有效地選擇匯聚節(jié)點(diǎn)，規(guī)劃移動路徑，降低網(wǎng)絡(luò)能耗，且收斂速度快。

[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環(huán)境下的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集節(jié)能算法[J].北京郵電大學(xué)學(xué)報,2013,36(5):51-55.

[7] 張希偉,沈 琳,蔣益峰.移動協(xié)助傳感器網(wǎng)絡(luò)中Sink的路徑優(yōu)化策略[J].通信學(xué)報,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-)，男，滿族，河北秦皇島人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。