優化網絡生命周期和最短化路徑的WSN移動sink路徑規劃算法

莫文杰，鄭 霖

(1.廣西無線寬帶通信與信號處理重點實驗室(桂林電子科技大學)，廣西 桂林 541004；2.桂林電子科技大學 信息與通信學院，廣西 桂林 541004)

(*通信作者電子郵箱gwzheng@gmail.com)

優化網絡生命周期和最短化路徑的WSN移動sink路徑規劃算法

莫文杰1,2，鄭 霖1,2*

(1.廣西無線寬帶通信與信號處理重點實驗室(桂林電子科技大學)，廣西 桂林 541004；2.桂林電子科技大學 信息與通信學院，廣西 桂林 541004)

(*通信作者電子郵箱gwzheng@gmail.com)

為了緩解無線傳感器網絡(WSN)中傳感器節點分布不均勻、傳感器節點感知數據量不同而造成能耗不均衡、“熱區”等問題，提出一種優化網絡生命周期和最短化路徑的WSN移動sink路徑規劃算法(MSPPA)。首先，通過監測區域網格化，在每個網格內分布若干個移動sink候選訪問站點，sink在每個網格中選擇一個站點停留收集網格中節點數據；然后，分析所有傳感器節點的生命周期與sink站點選擇的關系，建立權衡網絡生命周期和sink移動路徑的優化模型；最后，使用雙鏈遺傳算法規劃移動sink遍歷網格的順序和選擇每個網格中移動sink訪問站點，得到移動sink節點遍歷所有網格收集數據的路徑。仿真結果顯示，與已有的低功耗自適應分簇(LEACH)算法與基于移動sink節點與集合節點(RN)的優化LEACH分簇算法(MS-LEACH-RN)相比，MSPPA在網絡生命周期方面提高了60%，且具有良好的能耗均衡性。實驗結果表明，MSPPA能有效緩解能量不均衡、“熱區”問題，延長網絡生命周期。

無線傳感器網絡；移動sink；數據收集；雙鏈遺傳算法；路徑規劃；網絡生命周期

0 引言

當前，基于移動sink節點的數據收集優化是無線傳感器網絡(Wireless Sensor Network, WSN)研究的關鍵問題之一[1]。WSN引入移動sink節點不僅可均衡節點流量負載，還可以平衡節點能量消耗，從而可以有效避免“熱區”問題并延長網絡的生存時間[2-3]。但是使用移動sink節點收集數據也帶來了新的挑戰：一是sink位置更新問題，頻繁泛洪sink位置信息將過多消耗節點能量；二是由于sink移動，網絡拓撲頻繁改變，這會加劇網絡拓撲構建的開銷[4-5]。因此，優化基于移動sink節點的路由協議以及規劃移動sink軌跡的算法受到學術和應用領域的廣泛關注。根據sink移動模型，Gu等[6]將基于移動sink的路由協議分成四類：不可控移動模型、路徑限制移動模型、站點限制移動模型和不限制移動模型。基于上述四種sink移動模型，下面分別介紹國內外研究者提出的有關基于移動sink的路由協議。

不可控移動模型是指sink節點安裝在移動單元上(如動物)，故其位置、速度和軌跡都未知。基于此模型，Lin等[7]提出了基于分簇的分層數據傳輸(Hierarchical Cluster-based Data Dissemination, HCDD)協議，使用K-means算法將網絡劃分成簇，簇頭處于較高層，負責收集簇內傳感器節點數據和轉發數據。當sink駐留在其中一個簇時，該簇的簇頭通知其他簇頭sink的位置，各個簇頭以其他簇頭為中繼節點多跳將數據傳輸到sink節點。Hamida 等[8]提出了基于虛擬線的數據傳輸(Line-Based Data Dissemination, LBDD)協議，該協議在網絡中央構建一條寬度為w的虛擬線(virtual line)，虛擬線內的傳感器節點負責收集和緩存虛擬線外節點的數據，并將sink感興趣的數據以多跳方式傳輸給隨機游走的sink節點。文獻[7-8]采用了sink節點不可控移動模型，能很好地解決隨機移動sink位置更新問題，但是無論是HCDD協議的簇頭，還是LBDD協議的虛擬線內節點，都存在較高的控制開銷與路由開銷，其縮短了網絡生命周期。

路徑限制模型是指sink節點被安置在路徑被約束的移動單元上(如公交車)。基于此模型，Mottaghi等[9]結合移動sink節點、低功耗自適應分簇(Low-Energy Adaptive Clustering Hierarchy, LEACH)算法[10]和集合節點(Rendezvous Node，RN)，提出一種基于移動sink節點與集合節點RN的優化LEACH分簇算法(optimizing LEACH clustering algorithm with Mobile Sink and Rendezvous Nodes, MS-LEACH-RN)。該協議在網絡中央構建一條寬度為w的虛擬線，移動sink在線內作往返直線移動，然后設置一個簇頭到sink節點的距離閾值d0，當簇頭到sink節點的距離小于d0時，虛擬線外以LEACH協議選取的簇頭直接將簇內收集到的數據發送到sink節點，否則，將數據發送到最近的虛擬線內RN，最后RN將數據傳輸給靠近的移動sink節點。Bhatti等[11]提出一種基于虛擬網格與移動sink節點的動態路由調整方案，該方案將正方形監測區域劃分成多個大小一致的網格，sink節點在正方形區域外移動，網格內選取頭節點負責收集網格數據，并以其他頭節點為中繼多跳傳輸給移動sink節點。該方案以維護sink最新位置的次優路由來達到最小化路由重構開銷的目的。梁青等[12]提出基于二分法與移動 sink 的無線傳感器網絡數據收集協議，該協議將網絡分為面積相等的兩個子域，子域交線為移動sink的軌跡，隨節點死亡率的增加，對子域內部進行二分，確定并改變移動sink的軌跡。移動sink與固定 sink并存，簇頭收集簇內興趣事件并發送至距自己跳數最小的sink。文獻[9，11-12]采用了移動sink路徑限制模型，都存在關鍵性節點(如文獻[8]的RN與簇頭和文獻[10]的網格頭節點)能耗過大問題，導致其快速死亡。

站點限制移動模型是指移動sink節點只能停留在某些固定位置收集數據。基于此模型，Yun等[13]提出了一種延遲容忍最大化生命周期的單移動sink路由協議。該協議將網絡區域分成多個子區域，在每個子區域布置一個固定的sink駐留站點，移動sink遍歷所有站點收集數據；然后采用線性規劃(Linear Programming, LP)優化移動sink每輪駐留在每個站點的時間，從而最大化網絡生命周期。林德鈺等[14]提出移動與靜態sink相結合的節能策略，該策略使靜態 sink節點位于檢測區域的中心采用單跳傳輸方式收集區域中心處節點的數據，移動sink位于距離靜態sink節點一定距離處作快速移動，到達固定站點后停留并采集區域外圍節點數據。王章權等[15]提出一種移動無線傳感網絡的sink節點移動路徑選擇算法，在該算法中，sink節點采用分布式最短路徑樹算法收集傳感節點的相關信息和感知數據，采用虛擬力理論計算所有虛擬力的合力， 根據停留次數、合力大小和方向等信息計算當前網格中心的停留時間和下一個停留網格中心。文獻[13-15]采用站點限制移動模型，故其單跳通信傳輸方式使遠離移動sink站點的傳感器節點能耗較大，易出現“熱區”現象。

不限制移動模型是在不限制sink移動路徑與停留站點的情況下規劃sink移動路徑。基于此模型，Pavithra等[16]基于集合點(Rendezvous Point, RP)提出一種加權集合規劃算法，該協議基于源節點到固定sink的數據轉發路由，計算每個傳感器節點的權重(其轉發數據量與其到固定sink的跳數)動態選擇節點作為集合點，sink遍歷所有集合點收集數據。王薇等[17]提出了一種基于二次柵格劃分的可變長編碼單親遺傳算法的最佳路徑構建方法。該算法首先在網絡區域中使用粗粒度柵格進行劃分，并利用可變長度編碼的單親遺傳算法獲得最佳途經柵格，從而構造出初始最佳路徑；然后對于每一個途經柵格再次使用細粒度柵格進行劃分以優化收集路徑。于志博等[18]針對sink移動速度限制從而導致時延較大的問題，提出了時延約束下的移動 sink 路徑優化策略，根據時延和網絡能耗之間的關系設計了可調節的節點權重，通過模擬退火遺傳算法得到最優節點權重，并依據此權重通過迭代得到匯聚節點和最佳移動路徑。

許多研究者都考慮到了節點不均勻分布與 “多對一”路由負載不均衡帶來的“熱區”問題，但大多數移動sink路由協議都沒有考慮節點數據分布不均勻問題(節點數據產生速率非恒定)。在WSN現實情況中，節點數據產生速率非恒定也是“熱區”問題產生的原因之一。而上述文獻中都存在“熱區”問題，縮短了網絡生命周期。本文根據WSN節點不均勻分布、節點數據分布不均勻以及移動sink收集數據路徑長短不同等因素，提出了優化網絡生命周期與最短化路徑的WSN移動sink路徑規劃算法MSPPA(Path Planning Algorithm of Mobile Sink)。將網絡分成多個網格，在每個網格中分布多個候選站點，根據上述造成“熱區”問題的因素，建立權衡網絡生命周期和sink移動路徑的優化模型。使用雙鏈遺傳算法對該優化模型進行求解，得到移動sink節點遍歷所有網格收集數據最優路徑。該算法均衡了全網數據收集的能耗開銷，顯著緩解了網絡“熱區”問題，延長了網絡生命周期。

1 系統模型

1.1 優化目標與模型假設

針對sink節點移動軌跡可控的無線傳感器網絡，本文提出的MSPPA綜合考慮了網絡生命周期和sink節點移動路徑長短兩項指標。算法具體包含以下兩個優化目標：1)最大化網絡的生命周期；2)在目標1)的基礎上，使sink移動距離最短化。

在MSPPA中，假設：1)所有傳感器節點隨機分布在二維的監測區域中，傳感器節點位置固定不變，但是sink節點可在監測區域中移動并且停留收集數據；2)所有傳感器節點具有相同的性能(如通信半徑、初始能量、能耗模型等)，但節點的數據產生速率非恒定，即節點感知數據不均勻；3)所有節點可安裝全球定位系統(Global Positioning System, GPS)模塊或采用其他定位方法獲知自身的位置坐標；4)sink節點能量不受限制，但是每個傳感器節點的能量有限且不能補充。

1.2 優化模型

如圖1所示，將監測區域分成G個大小一致的網格，網格邊長為L(L

圖1 網絡模型Fig. 1 Network model

本文采用的無線通信能量消耗模型與文獻[20-21]相似，由于只考慮傳感器節點發送數據到sink節點的單跳路由，故節點i單位時間內發送1 bit數據到sink節點的能耗如下：

(1)

定義節點生命周期Tnet為其能量耗盡所經過的時間，故節點i的生存時間[22-23]為：

(2)

根據上述分析，本文方法的目的是既要最大化網絡生命周期，又要最小化sink移動路徑長度[24]，故本文提出的優化模型可公式化為：

(3)

(4)

(5)

Ti>0,di→ms≥0;i=1,2,…,n

(6)

2 模型求解

本文問題模型中包含移動sink站點選址問題與移動sink遍歷網格問題(即旅行商問題)，但是無論選址問題，還是TSP，都是NP-hard問題，求解存在困難，故采用雙鏈遺傳算法對本文模型進行求解。

2.1 染色體編碼和解碼

移動sink節點在每個網格中選取一個站點停留收集該網格中的傳感器節點數據，并以此遍歷所有網格，采用雙鏈遺傳算法對此問題進行編碼。在此雙鏈染色體編碼中，一條基因鏈包含sink遍歷所有網格的順序，如{3,1,6,4,5,2}，另一條是使用0-1編碼方式標記sink節點在網格中選取的站點，如{010,100,010,001,001,100}，則染色體和子鏈之間的關系[25]如圖2所示。這兩條子鏈組合成染色體，染色體的每一個基因由一個網格和其內站點組合而成，代表移動sink節點從網格中選取其中一個站點停留收集數據。子鏈一可得到移動sink節點遍歷所有網格的順序，子鏈二可得到子鏈一對應網格中sink選取的停留站點，這樣，通過對每個基因進行相應的解碼，就可以得到移動sink節點遍歷網格收集數據的最優路徑。

圖2 子鏈、染色體關系Fig. 2 Relationship between sub-chain and chromosome

2.2 雙鏈遺傳算法求解過程

如圖3所示，雙鏈遺傳算法求解優化模型(3)～(6)，迭代執行染色體評估、選擇、交叉、變異等步驟[24]，最終獲得優化網絡生命周期的sink移動路徑選擇方案。

圖3 MSPPA流程Fig. 3 Flow chart of MAPPA

令C表示染色體數量，c表示染色體操作數，α1表示交叉概率，α2表示變異概率，g表示迭代次數。根據優化模型，雙鏈遺傳算法的適應度函數為：

(7)

根據適應度函數，采用以下步驟求解優化模型。

步驟1 初始化。初始化C個雙鏈染色體，迭代次數g=0，染色體操作數c=0，算法中α1、α2等參數。

步驟2 染色體評估。計算所有染色體的適應度，直接選擇適應度最大的染色體繼承到下一代種群中。

步驟3 選擇。根據輪盤賭策略選擇需要交叉的2個染色體。

步驟4 交叉。產生一個0～1的隨機數，如果其大于α1，對已選擇的2個染色體進行交叉操作。交叉操作采用部分匹配交叉法，先隨機產生兩個交叉點，定義這兩點的區域為匹配區域，并交換兩個父代的匹配區域，如圖4所示。

對TEMP A、TEMP B中匹配區域以外出現的數碼重復，要依據匹配區域內的位置逐一進行替代，匹配關系為{6?1, 4?5}，產生子代A、子代B，如圖5所示。

步驟5 變異。產生一個0～1的隨機數，如果其大于α2，對已交叉的2個染色體進行變異操作。隨機產生兩個變異位，交換染色體兩個變異位的基因，再對子鏈二(sink站點鏈)的變異位相應的值進行位變異，如圖6所示。

圖4 父代匹配區域交換Fig. 4 Exchange of parental matching regions

圖5 匹配關系替代圖Fig. 5 Substitution map of matching relationship

圖6 變異操作Fig. 6 Mutation operation

步驟6 返回或結束。c=c+1，如果c

3 仿真實現和分析

3.1 仿真參數設置

為了方便比較算法性能，網絡生命周期與LEACH協議[10]相似，使用移動sink數據采集輪數計量。如表1所示，選擇表中參數，在Matlab軟件上編程實現MSPPA、 MS-LEACH-RN和LEACH算法。LEACH算法是典型的分簇數據收集協議，而MS-LEACH-RN[9]是基于移動sink節點與集合節點RN的優化LEACH分簇算法。將100個傳感器節點隨機分布在120 m×160 m的監測區域，通信半徑60 m，節點感知數據量變化范圍為0～8 000 bit，節點的初始能量為0.2 J。最后將監測區域劃分成12個均等的網格，每個網格中以網格中心點、網格中節點分布密度重心和網格中數據分布質心為sink站點，仿真分析MSPPA的收斂性，并比較MSPPA、MS-LEACH-RN和LEACH算法。

表1 仿真參數Tab. 1 Simulation parameters

3.2 MSPPA收斂性仿真分析

為了驗證MSPPA的收斂性，對MSPPA的最大適應度值和平均適應度值進行仿真計算，其收斂速度、尋優結果如圖7所示。從圖中最優解和平均解的對比，可知MSPPA具有較好的收斂性。

圖7 MSPPA收斂性Fig. 7 Convergence of MSPPA

3.3 算法仿真結果分析

3.3.1 網絡生命周期性能分析

為了比較MSPPA和MS-LEACH-RN、LEACH算法的網絡生命周期性能，在仿真區域內隨機分布50、100、150、200、250、300個傳感器節點，并假設網絡生命周期為網絡中第一個節點死亡對應的輪數。如圖8所示，MSPPA的網絡生命周期是MS-LEACH-RN的1～2倍，是LEACH算法的8倍，可見MSPPA能延長網絡生存時間。

3.3.2 存活節點數量性能分析

圖9對比了上述三種算法的網絡中存活節點數量隨著仿真輪數的變化情況。LEACH協議中sink節點固定，簇頭的負載過大，故在400輪時節點全部死亡；MS-LEACH-RN協議中sink移動軌跡固定在網絡額度中線，在sink移動軌跡附近存在集合節點(RN)，RN雖然減小了一部分簇頭節點能耗，但是遠離sink移動軌跡的簇頭能耗沒有降低多少，故此類簇頭節點過早死亡，網絡壽命較短；MSPPA在800～950輪死亡的傳感器節點驟然增加，可見其網絡能量較為均衡，所以MSPPA在延長網絡生命周期方面優于其他兩個算法。

圖8 網絡生命周期Fig. 8 Network lifetime

圖9 節點存活數量Fig. 9 Number of surviving nodes

3.3.3 節點剩余能量標準差分析

無線傳感器網絡中，全網所有節點所有能量的標準差是評價能量均衡路由協議的一個非常明了的指標。標準差反映了各節點剩余能量的分布狀況，如果網內所有節點的能量水平相當，即它們之間的能量差異很小，則節點剩余能量的標準差較小；若標準差的值較大，則表示網絡內各節點的能量情況差異較大，有些節點有充足的能量，而有些節點則因為能耗過快而過早死亡，縮短了網絡壽命。因此，節點剩余能量的標準差(Standard Deviation)越小，網絡中能量的分布越均勻，說明能量均衡路由協議的性能也越好。節點剩余能量的標準差σE的計算公式[26]如下：

(8)

如圖10所示，在仿真150輪時，LEACH、MS-LEACH-RN和MSPPA傳感器節點剩余能量標準差的斜率分別約為0.08/150，0.35/150和0.01/150，故MSPPA節點剩余能量標準差的斜率要遠小于LEACH與MS-LEACH-RN，所以MSPPA在能量均衡方面優于其他兩個算法。

3.3.4 “熱區”情況分析

圖11為MSPPA與LEACH和MS-LEACH-RN在仿真300輪時的節點能量消耗圖，該圖描繪了網絡中所有傳感器節點的能耗分布。盡管LEACH算法采用自適應簇頭選取機制(選擇剩余能量大的節點充當簇頭)，稍微均衡了網絡能耗，但是由于其簇內采用“多對一”通信，簇內所有數據都通過簇頭傳輸到sink節點，導致簇頭負載較大，如圖11(a)所示，許多節點已耗盡0.2 J能量，“熱區”效應嚴重。MS-LEACH-RN集合了移動sink節點、LEACH分簇算法、集合節點的優點，大大縮短了簇頭節點到sink節點的通信距離，降低了簇頭的能耗，但是網絡邊界的簇頭由于距離移動sink軌跡較遠，故其傳輸數據能耗較大，所以網絡邊界易出現“熱區”，如圖11(b)所示，網絡邊界節點能耗已達到0.1～0.14 J，出現“熱區”效應。而MSPPA根據網絡壽命動態選取每個網絡中移動sink停留站點，故傳感器節點與sink節點的通信距離不固定，能更好地均衡網絡能耗，緩解“熱區”效應，如圖11(c)所示，網絡還沒出現“熱區”現象，故可得出MSPPA在緩解“熱區”問題上優于另外兩個算法。

圖10 節點剩余能量標準差Fig. 10 Residual energy standard deviation of nodes

圖11 “熱區”情況對比Fig. 11 Hotspot situation comparison

4 結語

本文針對節點分布不均勻、節點感知數據非均勻而造成能耗不均衡、“熱區”能量空洞問題，設計了面向延長網絡壽命和最短路徑的WSN移動sink路徑規劃算法(MSPPA)。該算法將WSN監測區域劃分成網格，根據網絡實際情況，在每個網格中定義若干個sink候選站點(如網格中心點、網格中節點分布密度重心、網格中數據分布質心等)，使用雙鏈遺傳算法規劃移動sink遍歷網格的順序和選擇每個網格中移動sink訪問站點，得到移動sink節點遍歷所有網格收集數據的移動路徑。該算法在能耗均衡性與緩解“熱區”效應等方面，均表現良好，其網絡生命周期優于LEACH和MS-LEACH-RN。

References)

[1] XING G, WANG T, XIE Z, et al. Rendezvous planning in wireless sensor networks with mobile elements [J]. IEEE Transactions on Mobile Computing, 2008, 7(12): 1430-1443.

[2] CHATZIGIANNAKIS I, KINALIS A, NIKOLETSEAS S. Efficient data propagation strategies in wireless sensor networks using a single mobile sink [J]. Computer Communications, 2008, 31(5): 896-914.

[3] KHAN A W, ABDULLAH A H, ANISI M H, et al. A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks [J]. Sensors, 2014, 14(2): 2510-2548.

[4] SUN W, YANG Z, ZHANG X, et al. Energy-efficient neighbor discovery in mobile Ad Hoc and wireless sensor networks: a survey [J]. IEEE Communications Surveys & Tutorials, 2014, 16(3): 1448-1459.

[5] 張惠麒,林志貴,李敏,等.基于移動sink節點的路由協議的比較與分析[J].計算機科學,2014,41(S1):276-280. (ZHANG H Q, LIN Z G, LI M, et al. Comparison and analysis of routing protocol based on mobile sink [J]. Computer Science, 2014, 41(S1): 276-280.)

[6] GU Y, REN F, JI Y, et al. The evolution of sink mobility management in wireless sensor networks: a survey [J]. IEEE Communications Surveys & Tutorials, 2016, 18(1): 507-524.

[7] LIN C-J, CHOU P-L, CHOU C-F. HCDD: hierarchical cluster-based data dissemination in wireless sensor networks with mobile sink [C]// IWCMC ’06: Proceedings of the 2006 International Conference on Wireless Communications and Mobile Computing. New York: ACM, 2006: 1189-1194.

[8] HAMIDA E B, CHELIUS G. A line-based data dissemination protocol for wireless sensor networks with mobile sink [C]// ICC ’08: Proceedings of the 2008 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2008: 2201-2205.

[9] MOTTAGHI S, ZAHABI M R. Optimizing LEACH clustering algorithm with mobile sink and rendezvous nodes [J]. AEU — International Journal of Electronics and Communications, 2015, 69(2): 507-514.

[10] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocols for wireless microsensor networks [C]// HICSS ’00: Proceedings of the 33rd Hawaii International Conference on Systems Sciences. Washington, DC: IEEE Computer Society, 2000, 8: 8020.

[11] BHATTI R, KAUR G. Virtual grid based energy efficient mobile sink routing algorithm for WSN [C]// Proceedings of the 11th International Conference on Intelligent Systems and Control. Piscataway, NJ: IEEE, 2017:30-33.

[12] 梁青,焦峰.WSN中基于二分法與移動Sink的數據收集協議[J].計算機工程,2016,42(12):39-43. (LIANG Q, JIAO F. Data collection protocol for WSN based on dichotomy and mobile sink [J]. Computer Engineering, 2016, 42(12): 39-43.)

[13] YUN Y, XIA Y. Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications [J]. IEEE Transactions on Mobile Computing, 2010, 9(9): 1308-1318.

[14] 林德鈺,王泉,劉伎昭.無線傳感網的移動與靜態sink相結合的節能策略[J].哈爾濱工業大學學報,2016,48(11):162-168. (LIN D Y, WANG Q, LIU J Z. Energy-saving strategy by combining mobile and static sink schemes for wireless sensor networks [J]. Journal of Harbin Institute of Technology, 2016, 48(11): 162-168.)

[15] 王章權,陳友榮,任條娟,等.數據傳輸時延和跳數受限的Sink節點移動路徑選擇算法[J]. 傳感技術學報,2016,29(4):583-592. (WANG Z Q, CHEN Y R, REN T J, et al. Sink node moving path selection algorithm limited by data transmission delay and hops [J]. Chinese Journal of Sensor and Actuators, 2016, 29(4): 583-592.)

[16] PAVITHRA H, SHIVASHANKAR, POORNIMA G R. An efficient mobile sink path selection approach for WSN’s [C]// Proceedings of the 2016 IEEE International Conference on Recent Trends in Electronics Information Communication Technology. Piscataway, NJ: IEEE, 2016: 151-155.

[17] 王薇,史浩山,黃鵬宇,等.基于二次柵格劃分的移動sink最小路徑構建算法[J].西北工業大學學報,2016,34(6):1016-1021. (WANG W, SHI H S, HUANG P Y, et al. A constructing mobile path minimal path algorithm based on quadratic grid [J]. Journal of Northwestern Polytechnical University, 2016, 34(6): 1016-1021.)

[18] 于志博,孔祥雪,裴金金.移動Sink的傳感器網絡路徑優化策略[J].傳感器與微系統,2016,35(11):44-46. (YU Z B, KONG X X, PEI J J. Mobile sink-based path optimization strategy in wireless sensor networks [J]. Transducer and Microsystem Technologies, 2016, 35(11): 44-46.)

[19] 陶志勇,蔣守鳳.基于簇首移動的無線傳感器網絡路由算法[J].計算機工程與應用,2016,52(5):75-78. (TAO Z Y, JIANG S F. Clustering algorithm for wireless sensor networks with mobile cluster heads [J]. Computer Engineering and Applications, 2016, 52(5): 75-78.)

[20] SHI Y, HOU Y T. Theoretical results on base station movement problem for sensor network [C]// INFOCOM 2008: Proceedings of the 27th Conference on Computer Communications. Piscataway, NJ: IEEE, 2008:1-5.

[21] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications, 2000, 1(4): 660-670.

[22] TASHTARIAN F, MOGHADDAM M H Y, SOHRABY K, et al. ODT: optimal deadline-based trajectory for mobile sinks in WSN: a decision tree and dynamic programming approach [J]. Computer Networks, 2015, 77: 128-143.

[23] TASHTARIAN F, HOSSEIN Y M M, SOHRABY K, et al. On maximizing the lifetime of wireless sensor networks in event-driven applications with mobile sinks [J]. IEEE Transactions on Vehicular Technology, 2015, 64(7): 3177-3189.

[24] 王章權,陳友榮,尉理哲,等.優化網絡生存時間的Sink節點移動路徑選擇算法[J]. 傳感技術學報,2014,27(3):409-415. (WANG Z Q, CHEN Y R, YU L Z, et al. Mobile path selection algorithm of sink node for optimizing network lifetime [J]. Chinese Journal of Sensor and Actuators, 2014, 27(3): 409-415.)

[25] 曾又姣,金燁.基于遺傳算法的貼片機貼裝順序優化[J].計算機集成制造系統,2004,10(2):205-208. (ZENG Y J, JIN Y. Optimization of placement order of placement machine based on genetic algorithm [J]. Computer Integrated Manufacturing Systems, 2004, 10(2):205-208.)

[26] ZENG K, REN K, LOU W, et al. Energy aware efficient geographic routing in lossy wireless sensor networks with environmental energy supply [J]. Wireless Networks, 2009, 15(1): 39-51.

This work is partially supported by the National Natural Science Foundation of China (61371107), the Foundation of Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing (GXKL061501).

MOWenjie, born in 1990, M. S. candidate. His research interests include wireless sensor network, routing protocol.

ZHENGLin, born in 1973, Ph. D., professor. His research interests include wireless UWB communication, wireless sensor network, mobile communication, adaptive signal processing, spread spectrum communication, packet wireless network.

Pathplanningalgorithmformobilesinkwithoptimizednetworklifetimeandshortestpathinwirelesssensornetwork

MO Wenjie1,2, ZHENG Lin1,2*

(1.GuangxiKeyLaboratoryofWirelessWidebandCommunicationandSignalProcessing(GuilinUniversityofElectronicTechnology),
GuilinGuangxi541004,China；2.SchoolofInformationandCommunication,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China)

In order to alleviate the problem of the imbalance energy consumption and hotspot due to the uneven distribution of nodes and the different amount of perception data in the Wireless Sensor Network (WSN), a Path Planning Algorithm of Mobile Sink named MSPPA was proposed to optimize network lifetime and shortest path in WSN. Firstly, by defining the grids in the network area, several candidate sites of mobile sink were distributed in each grid, and then sink node selected a site for sojourning and collecting data of nodes in each grid. Secondly, based on the relationship between network lifetime and the selection of sink sites, an optimization model was established to weigh network lifetime and mobile journey of sink. Finally, the double-stranded genetic algorithm was proposed to plan the order of mobile sink traversing grids and selecting site of the mobile sink in each grid, then the optimal path of mobile sink was obtained. The simulation results show that, compared with Low-Energy Adaptive Clustering Hierarchy (LEACH) algorithm and optimizing LEACH clustering algorithm with Mobile Sink and Rendezvous Nodes (MS-LEACH-RN), the network lifetime of MSPPA was increased by 60%. The proposed MSPPA has a good balance of energy consumption as well. The experimental results indicate that the proposed MSPPA can effectively alleviate the imbalance of energy consumption and the hotspot problems, prolonging the network lifetime.

Wireless Sensor Network (WSN); mobile sink; data collection; double-stranded genetic algorithm; path planning; network lifetime

TN926

A

2017- 02- 08;

2017- 02- 26。

國家自然科學基金資助項目(61371107)；廣西無線寬帶通信與信號處理重點實驗室基金資助項目(GXKL061501)。

莫文杰(1990—)，男，廣西柳州人，碩士研究生，主要研究方向：無線傳感器網絡、路由協議； 鄭霖(1973—)，男，廣西桂林人，教授，博士，主要研究方向：無線超寬帶通信、無線傳感器網絡、移動通信、自適應信號處理、擴頻通信、分組無線網絡。

1001- 9081(2017)08- 2150- 07

10.11772/j.issn.1001- 9081.2017.08.2150