王章權(quán)，陳友榮，任條娟，劉耀林

（浙江樹人大學信息科技學院，杭州310015）

數(shù)據(jù)傳輸時延和跳數(shù)受限的Sink節(jié)點移動路徑選擇算法*

王章權(quán)，陳友榮*，任條娟，劉耀林

（浙江樹人大學信息科技學院，杭州310015）

考慮實際無線傳感網(wǎng)系統(tǒng)中數(shù)據(jù)傳輸時延和跳數(shù)受限情況，且為降低算法的時間復雜度，提出一種移動無線傳感網(wǎng)的Sink節(jié)點移動路徑選擇算法（MPSA）。在MPSA算法中，Sink節(jié)點采用分布式最短路徑樹算法收集k+1跳通信范圍內(nèi)傳感節(jié)點的相關信息和感知數(shù)據(jù)，采用虛擬力理論計算邊界、障礙物和空洞區(qū)域的虛擬斥力、第k+1跳未覆蓋傳感節(jié)點的虛擬引力和所有虛擬力的合力，根據(jù)停留次數(shù)、合力大小和方向等信息計算當前網(wǎng)格中心的停留時間和下一個停留網(wǎng)格中心。仿真結(jié)果表明:MPSA算法根據(jù)傳感節(jié)點的位置、剩余能量等信息，尋找到一條較優(yōu)的移動路徑，從而提高Sink節(jié)點的數(shù)據(jù)收集量和節(jié)點覆蓋率，降低傳感節(jié)點的感知數(shù)據(jù)丟棄量。總之，在數(shù)據(jù)傳輸時延和跳數(shù)受限下，MPSA算法比RAND算法、GMRE算法和EASR算法更優(yōu)。

移動無線傳感網(wǎng)；路徑選擇；虛擬力；數(shù)據(jù)傳輸時延；數(shù)據(jù)傳輸跳數(shù)

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2016.04.020

目前在火山、放射區(qū)、有毒化工區(qū)等危險環(huán)境監(jiān)測、災難搜救、軍事領域等應用領域中，通常采用傳感節(jié)點周期性上報數(shù)據(jù)且節(jié)點位置固定不變的靜態(tài)無線傳感網(wǎng)［1］。但是靜態(tài)無線傳感網(wǎng)會出現(xiàn)如下問題:離Sink節(jié)點近的傳感節(jié)點需要發(fā)送較多其它傳感節(jié)點的數(shù)據(jù)，導致這些傳感節(jié)點能量消耗較快，且過早失效。這個問題通常被稱為無線通信的熱點問題或Sink節(jié)點的空穴問題［2］。為了處理這個問題，引入Sink節(jié)點的移動。Sink節(jié)點的移動不僅能平衡傳感節(jié)點之間的能量消耗，而且能連接網(wǎng)絡中的分裂區(qū)域［3］。

近年來，國內(nèi)外學者對Sink節(jié)點的移動路徑選擇方法進行了一些研究，取得一些成果。有些學者研究Sink節(jié)點移動路徑的集中式方法。如Emre Keskin M等考慮靜態(tài)收集和移動收集兩種Sink節(jié)點的數(shù)據(jù)收集方法，建立網(wǎng)絡生存時間的優(yōu)化模型。將該優(yōu)化模型轉(zhuǎn)化成線性模型，通過商業(yè)軟件求解最優(yōu)解［4］。郭劍等將監(jiān)測區(qū)域分成若干個圓盤，在每一個圓盤中尋找一個Sink節(jié)點的采集點，并采用量子遺傳算法求解能遍歷所有采集點的最短路徑［5］。Wang Liu等采用理論推導的方法研究Sink節(jié)點移動到若干個RP點（Rendezvous Point）時的最優(yōu)方案［6］。Arun K Kumar等提出一種分簇算法。即根據(jù)節(jié)點的位置將網(wǎng)絡中所有節(jié)點分成多個簇，獲得若干個簇中心。采用經(jīng)典旅行商算法尋找經(jīng)過所有簇中心的最短路徑［7］。王章權(quán)等將Sink節(jié)點的監(jiān)測區(qū)域劃分為若干個網(wǎng)格，考慮Sink節(jié)點的1跳數(shù)據(jù)收集，建立數(shù)據(jù)傳輸時延受限的目標函數(shù)。采用遺傳算法求解，獲得Sink節(jié)點的最優(yōu)移動路徑［8］。Hamidreza Salarian等提出一種加權(quán)集合規(guī)劃算法WRP（Weighted Rendezvous Planning），即根據(jù)到最近RP點的跳數(shù)和子節(jié)點的數(shù)量，計算所有傳感節(jié)點的權(quán)值，選擇若干個權(quán)值較大的節(jié)點作為RP點，采用旅行商求解算法計算Sink節(jié)點遍歷所有RP點的最短路徑［9］。文獻［4-9］采用集中式方法研究Sink節(jié)點的1跳數(shù)據(jù)收集和多跳數(shù)據(jù)收集、時延是否受限等不同情況下的Sink節(jié)點移動路徑選擇算法。這些算法假設Sink節(jié)點能收集和分析其監(jiān)測區(qū)域內(nèi)所有傳感節(jié)點的信息，其時間復雜度隨傳感節(jié)點數(shù)量的增多而急劇變大，因此這些算法比較適用于傳感節(jié)點數(shù)量和數(shù)據(jù)傳輸跳數(shù)較少的Sink節(jié)點移動的無線傳感網(wǎng)。

另一些學者研究Sink節(jié)點移動路徑的分布式選擇方法，如Keontaek Lee等考慮Sink節(jié)點的起初地址、數(shù)據(jù)收集路由和停留時間等因素，建立混合整數(shù)線性規(guī)劃模型，提出貪婪最大剩余能量算法GMRE（Greedy Maximum Residual Energy）。當鄰居位置周圍的節(jié)點剩余能量比當前位置上的大，則移動到該鄰居節(jié)點［10］。Stefano Basagni等考慮節(jié)點的網(wǎng)格分布和Manhattan路由，建立Sink節(jié)點移動的線性優(yōu)化模型，提出一種啟發(fā)式算法。即根據(jù)節(jié)點的剩余能量和方差，計算變異系數(shù)。當變異系數(shù)小于指定閾值時，Sink節(jié)點移動到下一個停留位置上收集數(shù)據(jù)［11］。Chufu Wang等提出移動Sink節(jié)點的能量感知遷移算法EASR（Energy-Aware Sink Relocation）。EASR使用最大容量路徑MCP（Maximum Capacity Path）協(xié)議收集數(shù)據(jù)。當兩個搬遷條件滿足時，啟動Sink的移動，找到下一個具有最大權(quán)值的移動位置［12］。但是文獻［10-12］沒有考慮實際無線傳感網(wǎng)系統(tǒng)中數(shù)據(jù)傳輸時延和跳數(shù)受限情況。

總之，Sink節(jié)點移動路徑的集中式方法時間復雜度較大。而且在實際的無線傳感網(wǎng)系統(tǒng)中，具有較小數(shù)據(jù)傳輸跳數(shù)的傳感節(jié)點數(shù)據(jù)不容易丟包，具有過大數(shù)據(jù)傳輸跳數(shù)的傳感節(jié)點數(shù)據(jù)容易丟包，甚至不能傳輸?shù)絊ink節(jié)點。同時由于硬件成本的限制，傳感節(jié)點的數(shù)據(jù)存儲空間有限，其數(shù)據(jù)傳輸時延不宜過大，否則會造成大量數(shù)據(jù)的丟失。因此綜合一些學者的觀點，針對實際無線傳感網(wǎng)系統(tǒng)中數(shù)據(jù)傳輸時延和跳數(shù)受限情況，提出了一種數(shù)據(jù)傳輸時延和跳數(shù)受限的Sink節(jié)點移動路徑選擇算法MPSA（Sink Node Moving Path Selection Algorithm Limited by Time Delay and Transmission Hops）。即收集數(shù)據(jù)通信范圍內(nèi)傳感節(jié)點的信息和感知數(shù)據(jù)，采用虛擬力理論計算邊界、障礙物和空洞的虛擬斥力、第最大數(shù)據(jù)傳輸跳數(shù)加1跳未覆蓋傳感節(jié)點的虛擬引力和所有虛擬力的合力，根據(jù)合力大小、方向和周圍鄰居網(wǎng)格中心的停留次數(shù)等信息計算當前網(wǎng)格的停留時間和下一個停留網(wǎng)格中心。重復計算當前網(wǎng)格的停留時間和下一個停留中心，直到所選擇的網(wǎng)格中心停留時間和不小于規(guī)定的最大數(shù)據(jù)傳輸時延，則停止尋找下一個停留網(wǎng)格中心。Sink節(jié)點根據(jù)已選好的移動路徑循環(huán)移動收集其數(shù)據(jù)通信范圍內(nèi)傳感節(jié)點的感知數(shù)據(jù)。MPSA可提高Sink節(jié)點的數(shù)據(jù)收集量和節(jié)點覆蓋率，降低傳感節(jié)點的感知數(shù)據(jù)丟棄量。

1　算法原理

在MPSA算法中，假設:①傳感節(jié)點和Sink節(jié)點都配置GPS或北斗衛(wèi)星定位模塊，可獲知自身的位置信息；②Sink節(jié)點以當前停留位置為中心，將周圍監(jiān)測區(qū)域分成多個邊長相同的網(wǎng)格。當監(jiān)測區(qū)域面積大或傳感節(jié)點數(shù)量少時，網(wǎng)格邊長取較大值，反之取較小值。網(wǎng)格邊長大小可根據(jù)實際無線傳感網(wǎng)項目的監(jiān)測區(qū)域面積和傳感節(jié)點個數(shù)選擇，是一個經(jīng)驗值；③傳感節(jié)點位置固定不變，Sink節(jié)點可停留在任一網(wǎng)格中心上收集數(shù)據(jù)；④所有節(jié)點能量有限且具有統(tǒng)一的能耗模型，但是Sink節(jié)點的能量可更換；⑤所有傳感節(jié)點是同構(gòu)的，即各種性能相同；⑥數(shù)據(jù)傳輸?shù)淖畲筇鴶?shù)不能無限大，是一個常數(shù)k。即如果到Sink節(jié)點的最小數(shù)據(jù)傳輸跳數(shù)不大于k，則將數(shù)據(jù)通過父節(jié)點發(fā)送給Sink節(jié)點，否則進入休眠狀態(tài)，定期喚醒感知數(shù)據(jù)，并將數(shù)據(jù)緩存到存儲器中；⑦在靜止或移動狀態(tài)下，Sink節(jié)點都可收集數(shù)據(jù)。Sink節(jié)點的移動數(shù)據(jù)收集過程被認為由在若干個網(wǎng)格中心上停留一段時間的靜態(tài)數(shù)據(jù)收集過程組成；⑧網(wǎng)絡數(shù)據(jù)傳輸時延定義為Sink節(jié)點從初始位置開始，在不同網(wǎng)格中心的停留時間和。該時延不能無限大，是一個常數(shù)。即當Sink節(jié)點經(jīng)過多個網(wǎng)絡中心的停留時間和不小于規(guī)定的最大數(shù)據(jù)傳輸時延，則不考慮尋找新的停留網(wǎng)格，只沿著已選擇的移動路徑循環(huán)收集數(shù)據(jù)；⑨傳感節(jié)點的存儲容量一定。當其感知且未發(fā)送的數(shù)據(jù)總量超過存儲容量后，傳感節(jié)點丟棄最早感知的數(shù)據(jù)，存儲最新的感知數(shù)據(jù)。

如圖1所示，空心圓表示傳感節(jié)點，淺灰色填充正方形表示Sink節(jié)點未停留的網(wǎng)格中心，深灰色填充正方形表示Sink節(jié)點停留過的網(wǎng)格中心。根據(jù)算法假設，MPSA算法的基本思路如下:Sink節(jié)點在某一地方停留后，廣播發(fā)送數(shù)據(jù)請求包，k跳通信范圍內(nèi)的傳感節(jié)點收到數(shù)據(jù)請求包后，采用分布式最短路徑算法尋找父節(jié)點，并經(jīng)過多跳路徑將自身位置、剩余能量等信息、感知數(shù)據(jù)和第k跳傳感節(jié)點的鄰居傳感節(jié)點位置、剩余能量等信息傳輸給Sink節(jié)點。Sink節(jié)點收集傳感節(jié)點的信息后，判斷可能存在的邊界、障礙物和空洞區(qū)域，計算邊界、障礙物和空洞虛擬斥力，第k+1跳未覆蓋傳感節(jié)點的虛擬引力，計算所有虛擬力的合力。根據(jù)停留次數(shù)、合力的方向和大小，判斷當前網(wǎng)格的停留時間和下一個停留網(wǎng)格中心。當Sink節(jié)點在不同網(wǎng)格中心的停留時間和不小于規(guī)定的最大數(shù)據(jù)傳輸時延時，結(jié)束算法，獲得Sink節(jié)點的移動路徑和停留時間。但是MPSA算法仍需要解決以下3個問題:一是Sink節(jié)點在移動過程中如何有效收集k+1跳通信范圍內(nèi)傳感節(jié)點的相關信息。二是如何計算Sink節(jié)點停留在某一個網(wǎng)格中心的各個虛擬斥力和引力，得到所有虛擬力的合力。三是如何根據(jù)停留次數(shù)和合力信息，確定Sink節(jié)點的當前位置的停留時間和下一次的停留位置。這3個問題的具體解決如下。

圖1　監(jiān)測區(qū)域網(wǎng)格和Sink節(jié)點移動圖

1.1數(shù)據(jù)傳輸算法選擇

當Sink節(jié)點停留在某一個網(wǎng)格中心，Sink節(jié)點和傳感節(jié)點采用分布式最短路徑樹算法傳輸數(shù)據(jù)。即啟動數(shù)據(jù)收集后，不時發(fā)送數(shù)據(jù)請求包（包括Sink節(jié)點的ID、最新停留的位置信息、Sink節(jié)點的最短路徑權(quán)值等信息），每一個傳感節(jié)點執(zhí)行如下步驟，將自身的位置信息，剩余能量等相關信息和其感知的數(shù)據(jù)發(fā)送給Sink節(jié)點。

步驟1如果傳感節(jié)點i接收到Sink節(jié)點的發(fā)送數(shù)據(jù)請求包，則將其地址、最短路徑權(quán)值添加到鄰居節(jié)點的信息表中，并按照式（1）計算該傳感節(jié)點i到Sink節(jié)點的鏈路權(quán)值wis；

其中，s表示Sink節(jié)點，wis表示傳感節(jié)點i到Sink節(jié)點的鏈路權(quán)值，dis表示傳感節(jié)點i到Sink節(jié)點的距離，gis表示傳感節(jié)點i需要發(fā)送給Sink節(jié)點的數(shù)據(jù)量；Eelec表示通信電路能耗參數(shù)；εfs表示信號放大能耗參數(shù)；Ere（j）表示傳感節(jié)點j的剩余能量；y1表示能耗因子；y2表示接收剩余能量因子；

步驟2傳感節(jié)點i的最短路徑權(quán)值如果不是無窮大且到Sink節(jié)點的數(shù)據(jù)傳輸跳數(shù)不大于k，則傳感節(jié)點i不時向其所有鄰居傳感節(jié)點發(fā)送路由信息包。路由信息包的內(nèi)容包括傳感節(jié)點i的地址、到Sink節(jié)點的數(shù)據(jù)傳輸跳數(shù)和傳感節(jié)點i的最短路徑權(quán)值

傳感節(jié)點i如果接收到其鄰居傳感節(jié)點j的路由信息包，并獲知鄰居節(jié)點j的最短路徑權(quán)值，則在鄰居節(jié)點的信息表中更新鄰居節(jié)點j的最短路徑權(quán)值，并執(zhí)行步驟3；

步驟3按式（2）計算傳感節(jié)點i到其鄰居傳感節(jié)點j的鏈路權(quán)值:其中，wij表示傳感節(jié)點i到其鄰居傳感節(jié)點j的鏈路權(quán)值，dij表示傳感節(jié)點i到其鄰居傳感節(jié)點j的距離，gij表示傳感節(jié)點i需要發(fā)送給鄰居傳感節(jié)點j的數(shù)據(jù)量。按式（3）計算傳感節(jié)點i將鄰居節(jié)點j作為其父節(jié)點的最短路徑權(quán)值

通過以上3個步驟，傳感節(jié)點選擇父節(jié)點，將k+1跳通信范圍內(nèi)傳感節(jié)點的剩余能量、位置坐標、到Sink節(jié)點的數(shù)據(jù)傳輸跳數(shù)等信息和k跳通信范圍內(nèi)傳感節(jié)點的感知數(shù)據(jù)傳輸給Sink節(jié)點。但是在傳輸過程中，傳感節(jié)點i如果未收到Sink節(jié)點的數(shù)據(jù)請求包且未收到其它節(jié)點的路由信息包，則傳感節(jié)點i將其最短路徑權(quán)值設為無窮大，并緩存該傳感節(jié)點i的數(shù)據(jù)。當其感知且未發(fā)送的數(shù)據(jù)總量超過存儲容量后，傳感節(jié)點丟棄最早感知數(shù)據(jù)，存儲最新的感知數(shù)據(jù)。如果一段時間內(nèi)連續(xù)發(fā)送幾個數(shù)據(jù)包且沒有接收到該鄰居節(jié)點的反饋包，則認為傳感節(jié)點i到該鄰居節(jié)點的鏈路出現(xiàn)故障，在鄰居節(jié)點信息表中刪去該鄰居節(jié)點的信息。

1.2虛擬力計算

圖2　3個斥力的分析

當Sink節(jié)點收集所需信息后，計算該位置上邊界、障礙物和空洞區(qū)域的虛擬斥力，第k+1跳未覆蓋傳感節(jié)點的虛擬引力等各種虛擬力，最終形成一個合力［13-14］。如圖2所示，以當前停留位置為中心，構(gòu)建一個虛擬網(wǎng)格。首先Sink節(jié)點尋找所在網(wǎng)格水平方向的左邊界網(wǎng)格和右邊界網(wǎng)格，尋找所在網(wǎng)格垂直方向的上邊界網(wǎng)格和下邊界網(wǎng)格。尋找方法如下:在當前網(wǎng)格沿著水平方向向左尋找一個距離最近的網(wǎng)格，其傳感節(jié)點信息表中所有傳感節(jié)點都在該網(wǎng)格的右邊，則該網(wǎng)格為左邊界網(wǎng)格，獲得該網(wǎng)格中心到當前Sink節(jié)點所在網(wǎng)格中心的有向距離向量同理，右邊界網(wǎng)格，上邊界網(wǎng)格和下邊界網(wǎng)格到當前Sink節(jié)點所在網(wǎng)格中心的有向距離向量分別為Sink節(jié)點在移動過程中可通過激光雷達測距、超聲波測距、紅外傳感器測距等方法判斷前方是否存在障礙物和測量自身到障礙物的距離，從而獲知所在水平方向和垂直方向是否存在被障礙物占用的網(wǎng)格。計算該網(wǎng)格中心到當前Sink節(jié)點所在網(wǎng)格中心的有向距離向量dz。如果網(wǎng)格內(nèi)沒有傳感節(jié)點，則定義該網(wǎng)格未被覆蓋。當網(wǎng)格中出現(xiàn)多個以上相鄰且處于不同行的未被覆蓋網(wǎng)格，則認為這些網(wǎng)格所在的區(qū)域為空洞區(qū)域。如果Sink節(jié)點所在網(wǎng)格的水平方向或垂直方向上存在空洞區(qū)域，尋找該空洞區(qū)域內(nèi)離當前Sink節(jié)點所在網(wǎng)格中心距離最近的網(wǎng)格中心，獲得該網(wǎng)格中心到當前Sink節(jié)點所在網(wǎng)格中心的有向距離向量dk。如果上述距離向量的大小大于節(jié)點單跳最大通信距離dmax，則沒有虛擬斥力，否則產(chǎn)生向外推的虛擬斥力。

其中，F(xiàn)x表示邊界虛擬斥力Fb、障礙物虛擬斥力Fz和空洞虛擬斥力Fk。x1表示邊界虛擬斥力系數(shù)xb，障礙物虛擬斥力系數(shù)xz和空洞虛擬斥力系數(shù)xk。dx表示有向距離向量，和dk。dgrid表示網(wǎng)格的邊長。

Sink節(jié)點在數(shù)據(jù)收集過程中，為了擴大Sink節(jié)點的數(shù)據(jù)收集覆蓋范圍，獲得第k+1跳未覆蓋傳感節(jié)點信息。這些傳感節(jié)點對Sink節(jié)點產(chǎn)生虛擬引力Fg。

其中，x2表示傳感節(jié)點的引力系數(shù)，dj表示Sink節(jié)點到傳感節(jié)點j的有向距離向量，Eav表示Sink節(jié)點k跳通信范圍內(nèi)所有傳感節(jié)點剩余能量的平均值。

最終計算所有虛擬力的合力F為

1.3停留時間和下一個停留位置計算

為了擴大Sink節(jié)點的數(shù)據(jù)收集范圍，采用如下方法選擇當前停留網(wǎng)格中心的停留時間和下一個停留網(wǎng)格中心。

當Sink節(jié)點停留在某一網(wǎng)格中心，記錄該網(wǎng)格中心的停留次數(shù)，分析合力F的大小。如果合力值較大，則表示急需Sink節(jié)點移動到下一個停留網(wǎng)格中心，當前網(wǎng)格中心的停留時間較短，否則當前網(wǎng)格中心的停留時間較長。停留時間的具體計算公式如下。

其中，tg表示Sink節(jié)點在網(wǎng)格中心g的停留時間，F(xiàn)th表示判斷閾值，|F|表示合力大小，v表示Sink節(jié)點的移動速率。

當Sink節(jié)點在某一個網(wǎng)格中心停留tg時間后，分析周圍的鄰居網(wǎng)格中心，刪除不可移動的邊界和障礙物所在的網(wǎng)格中心和空洞區(qū)域內(nèi)的網(wǎng)格中心，并根據(jù)Sink節(jié)點的停留次數(shù)，建立停留次數(shù)最小的網(wǎng)格中心集合。分別計算合力F與從Sink節(jié)點的當前停留網(wǎng)格中心到集合中每一個網(wǎng)格中心的距離向量的夾角δ。

其中，abs［］表示取絕對值函數(shù)，acos（）表示反余弦函數(shù)，dsg表示從Sink節(jié)點的當前停留網(wǎng)格中心到網(wǎng)格中心g的距離向量，|dsg|表示向量的大小。根據(jù)向量夾角δ，選擇使夾角最小的網(wǎng)格中心作為Sink節(jié)點的下一個停留網(wǎng)格中心。

2　算法實現(xiàn)

MPSA算法是一個分布式算法。Sink節(jié)點和傳感節(jié)點執(zhí)行各自的程序。

如圖3所示，網(wǎng)絡啟動后，Sink節(jié)點執(zhí)行以下的步驟尋找路徑和收集數(shù)據(jù)。

步驟1Sink節(jié)點廣播信息查詢包，等待一段時間接收其k跳通信范圍內(nèi)傳感節(jié)點的地址、位置坐標、剩余能量和到Sink節(jié)點的數(shù)據(jù)通信跳數(shù)等信息，接收到第k跳傳感節(jié)點的鄰居節(jié)點地址、位置坐標、剩余能量和到Sink節(jié)點的數(shù)據(jù)通信跳數(shù)等信息，根據(jù)接收到的傳感節(jié)點信息更新Sink節(jié)點的傳感節(jié)點信息表。

步驟2當一段時間內(nèi)沒有接收到傳感節(jié)點的信息后，通過式（4）～式（5）計算邊界虛擬斥力、障礙物虛擬斥力、空洞虛擬斥力、第k+1跳傳感節(jié)點虛擬引力，通過式（6）計算虛擬力的合力。

步驟3根據(jù)合力大小，通過式（7）確定Sink節(jié)點在當前網(wǎng)格中心的停留時間。Sink節(jié)點廣播包含自身地址和位置坐標信息的路由信息包，接收其數(shù)據(jù)通信范圍內(nèi)傳感節(jié)點的感知數(shù)據(jù)。

步驟4分析當前停留網(wǎng)格中心的鄰居網(wǎng)格中心，刪除不可移動的邊界和障礙物所在的網(wǎng)格中心和空洞區(qū)域內(nèi)的網(wǎng)格中心，并根據(jù)Sink節(jié)點的停留次數(shù)，建立停留次數(shù)最小的網(wǎng)格中心集合。根據(jù)合力的方向和傳感節(jié)點的剩余能量，計算下一個停留網(wǎng)格中心。

步驟5經(jīng)過Sink節(jié)點在當前停留網(wǎng)格中心的停留時間tg后，Sink節(jié)點移動到下一個停留網(wǎng)格中心。

步驟6如果已選擇的所有網(wǎng)格中心的停留時間和小于最大數(shù)據(jù)傳輸時延，則返回步驟1，否則，停止尋找下一個停留網(wǎng)格中心。此時Sink節(jié)點已尋找到一條移動路徑，在以后一段時間內(nèi)沿著該移動路徑循環(huán)收集數(shù)據(jù)。當Sink節(jié)點根據(jù)傳感節(jié)點信息表中信息判斷出多個傳感節(jié)點能量耗盡，則刪去這些傳感節(jié)點的信息，重新返回步驟1，尋找新的移動路徑。

圖3　Sink節(jié)點的工作流程圖

如圖4所示，網(wǎng)絡啟動時，傳感節(jié)點根據(jù)不同的事件執(zhí)行不同的程序，主要事件如下:

事件1如果接收到Sink節(jié)點的信息查詢包，判斷接收數(shù)據(jù)包的跳數(shù)。如果接收數(shù)據(jù)包的跳數(shù)小于k-1，則將自身節(jié)點的序號、位置坐標、剩余能量等信息發(fā)送給Sink節(jié)點，轉(zhuǎn)發(fā)信息查詢包，否則將自身和周圍鄰居節(jié)點的信息發(fā)送給Sink節(jié)點。

事件2如果接收到鄰居節(jié)點的路由信息包，則更新自身的鄰居節(jié)點信息表，計算該鏈路的權(quán)值，更新到Sink節(jié)點的最短路徑樹權(quán)值，選擇使自身最短路樹權(quán)值最小的節(jié)點為父節(jié)點。如果自身路由信息發(fā)生改變，則廣播最新的路由信息包。

事件3判斷自身節(jié)點是否在Sink節(jié)點的k跳通信范圍內(nèi)。如果是，通過父節(jié)點將存儲器中的數(shù)據(jù)發(fā)送給Sink節(jié)點，釋放該數(shù)據(jù)所占用的存儲空間，否則進入休眠狀態(tài)，并定期喚醒啟動數(shù)據(jù)感知工作，將感知的數(shù)據(jù)緩存到存儲器中。如果存儲器已滿，則丟棄時間最早的感知數(shù)據(jù)，添加最新的感知數(shù)據(jù)。

事件4設置一個定時器，每間隔一段更新自身的剩余能量、父節(jié)點、最短路徑權(quán)值等信息，廣播自身的路由信息。

圖4　Sink節(jié)點的工作流程圖

3　仿真實現(xiàn)和分析

3.1仿真參數(shù)

由于在實際無線傳感網(wǎng)系統(tǒng)中，傳感節(jié)點的數(shù)據(jù)處理和計算能耗、通信控制包如信息查詢包、路由信息包和發(fā)送數(shù)據(jù)請求包等能耗相對較少，因此在仿真過程中只考慮傳感節(jié)點感知數(shù)據(jù)的通信能耗。所有節(jié)點的能耗模型采用目前學術界普遍采用的能耗模型。

其中，Ef表示數(shù)據(jù)發(fā)送能耗，Ej表示數(shù)據(jù)接收能耗。同時，Sink節(jié)點在相鄰網(wǎng)格間的移動時間為dgird/v。為方便表述，仿真中數(shù)據(jù)傳輸時延表示為tddgird/v，其中td表示一個常數(shù)，即Sink節(jié)點的移動路徑由不大于td個網(wǎng)格中心組成。

表1　仿真參數(shù)表

在算法比較過程中，采用表1所示的仿真參數(shù)，仿真計算Sink節(jié)點的一輪數(shù)據(jù)收集量、節(jié)點覆蓋率和平均節(jié)點丟棄數(shù)據(jù)量，Sink節(jié)點數(shù)據(jù)收集總量和平均節(jié)點能耗。其中，Sink節(jié)點的一輪數(shù)據(jù)收集量定義為在規(guī)定的最大數(shù)據(jù)傳輸時延內(nèi)，Sink節(jié)點沿著路徑移動一次所收集的傳感節(jié)點數(shù)據(jù)量。節(jié)點覆蓋率定義為Sink節(jié)點沿著路徑移動，所覆蓋的傳感節(jié)點數(shù)量與總數(shù)量的比。平均節(jié)點丟棄數(shù)據(jù)量定義為在規(guī)定的最大數(shù)據(jù)傳輸時延內(nèi)，傳感節(jié)點丟棄數(shù)據(jù)量的平均值。Sink節(jié)點數(shù)據(jù)收集總量定義為從網(wǎng)絡開始到某一個傳感節(jié)點能耗耗盡為止，在最大數(shù)據(jù)傳輸時延和跳數(shù)約束下，沿著選定路徑循環(huán)移動收集傳感節(jié)點數(shù)據(jù)的總量。平均節(jié)點能耗定義為從網(wǎng)絡開始到某一個傳感節(jié)點能耗耗盡為止，所有傳感節(jié)點能耗的平均值。

3.2仿真結(jié)果和分析

3.2.1關鍵參數(shù)的選擇

由于MPSA算法的主要目的是盡可能提高Sink節(jié)點的數(shù)據(jù)收集量和覆蓋節(jié)點率，因此在仿真中，采用數(shù)據(jù)收集總量和覆蓋節(jié)點數(shù)量的乘積值作為算法參數(shù)分析的性能指標。

首先，分析斥力系數(shù)x1和引力系數(shù)x2對算法性能的影響。最大數(shù)據(jù)傳輸時延60dgird/v，最大數(shù)據(jù)傳輸跳數(shù)2跳，判斷閾值Fth為0和表1中參數(shù)。x1和x2是底數(shù)為10的冪，分別選擇為-3.5，-3，…，6共20個指數(shù)，分析傳感節(jié)點隨機均勻分布下的算法參數(shù)，并以100個傳感節(jié)點的仿真結(jié)果以例說明參數(shù)x1和x2對MPSA算法的影響。

圖5　x1和x2對MPSA算法的影響

如圖5所示，當x1-x2為一個固定常數(shù)時，所得到的仿真結(jié)果值相同。當x1＞x2+2時，仿真結(jié)果值較大。總之，x1取較大值和x2取較小值時，算法性能較好。

其次，由于規(guī)定的最大數(shù)據(jù)傳輸時延對Fth有一定的影響，因此分析Fth和最大數(shù)據(jù)傳輸時延對算法性能的影響。最大數(shù)據(jù)傳輸跳數(shù)2跳，x1=104，x2=103和表1中參數(shù)，分別選擇最大數(shù)據(jù)傳輸時延為20dgird/v，24dgird/v，…，96dgird/v共 20個值，分別選擇判斷閾值Fth為0，4×105，…，96×105共20個值，分析傳感節(jié)點隨機均勻分布下的算法參數(shù)，并以100個傳感節(jié)點的仿真結(jié)果以例說明參數(shù)Fth對MPSA算法的影響。

如圖6所示，F(xiàn)th對算法性能的影響與規(guī)定的最大數(shù)據(jù)傳輸時延有關。當最大數(shù)據(jù)傳輸時延較小，F(xiàn)th取較小值，甚至是0時，算法的仿真結(jié)果值較大。當最大數(shù)據(jù)傳輸時延較大，F(xiàn)th取中間值時，算法的仿真結(jié)果值較大，且最大仿真結(jié)果值的出現(xiàn)概率也較大。但是當Fth取較小值時，算法的仿真結(jié)果值之間相差不大。因此，F(xiàn)th取較小值時，算法性能較好。

圖6　最大數(shù)據(jù)傳輸時延和Fth對MPSA算法的影響

3.2.2最大數(shù)據(jù)傳輸時延和跳數(shù)對算法性能的影響

最大數(shù)據(jù)傳輸跳數(shù)2跳，判斷閾值Fth=2×105，x1=104，x2=103和表1中參數(shù)，分別選擇最大數(shù)據(jù)傳輸時延 20dgird/v，30dgird/v，…，90dgird/v共 8個值。生成傳感節(jié)點隨機均勻分布的10個拓撲結(jié)構(gòu)，分別計算算法的一輪數(shù)據(jù)收集量和節(jié)點覆蓋率，取其平均值作為算法仿真結(jié)果值，并以100個傳感節(jié)的仿真結(jié)果以例，說明最大數(shù)據(jù)傳輸時延和跳數(shù)對MPSA算法的影響。

如圖6和7所示，在MPSA算法中，當規(guī)定的最大數(shù)據(jù)傳輸時延變大時，Sink節(jié)點可移動的距離增大，從而提高了Sink節(jié)點的數(shù)據(jù)收集范圍，因此一輪數(shù)據(jù)收集總量和節(jié)點覆蓋率都變大。但是這導致在Sink節(jié)點數(shù)據(jù)收集范圍內(nèi)的傳感節(jié)點與Sink節(jié)點的通信周期變大，覆蓋節(jié)點的丟棄數(shù)據(jù)量變大。

圖7　最大數(shù)據(jù)傳輸時延對MPSA算法的影響

選擇最大數(shù)據(jù)傳輸跳數(shù)1，2，…，5，選擇最大數(shù)據(jù)傳輸時延30dgird/v，其它參數(shù)和上述相同。如圖8所示，當規(guī)定的最大數(shù)據(jù)傳輸跳數(shù)變大時，Sink節(jié)點的數(shù)據(jù)通信范圍變大。在同一個網(wǎng)格中心停留相同的時間，Sink節(jié)點可與更多的傳感節(jié)點通信，收集更多的傳感節(jié)點數(shù)據(jù)。因此一輪數(shù)據(jù)收集量和節(jié)點覆蓋率都變大。但是，在實際無線傳感網(wǎng)系統(tǒng)中，如果規(guī)定的最大數(shù)據(jù)傳輸跳數(shù)設置過大，很容易造成處于Sink節(jié)點的數(shù)據(jù)通信范圍邊緣的傳感節(jié)點數(shù)據(jù)傳輸不到Sink節(jié)點，其丟包率變大。

圖8　最大數(shù)據(jù)傳輸跳數(shù)對MPSA算法的影響

總之，當最大數(shù)據(jù)傳輸時延和跳數(shù)取較大值時，能提高MPSA算法的節(jié)點覆蓋率和一輪數(shù)據(jù)收集量，但是受到實際硬件設備的限制，不能無限增大，需要根據(jù)實際應用需求設定這兩個參數(shù)。

3.2.3算法比較和分析

選擇節(jié)點數(shù)量40、60、80、100、120、140、160、180、200，最大數(shù)據(jù)傳輸跳數(shù)2跳，最大數(shù)據(jù)傳輸時延30dgird/v，判斷閾值Fth=2×105，xb=104，x2=103和表1中參數(shù)，分別生成傳感節(jié)點隨機均勻分布的10個拓撲結(jié)構(gòu)，計算MPSA算法、RAND算法、GMRE算法［10］和EASR算法［12］的一輪數(shù)據(jù)收集量、節(jié)點覆蓋率、平均節(jié)點丟棄數(shù)據(jù)量和平均節(jié)點能耗，取其平均值作為算法仿真結(jié)果值。其中，RAND算法和GMRE算法的數(shù)據(jù)收集算法和MPSA算法一致，RAND算法隨機選擇當前停留網(wǎng)格中心的鄰居網(wǎng)格中心作為下一個停留位置。而且以100個傳感節(jié)點下的Sink節(jié)點移動路徑為例，說明Sink節(jié)點在均勻隨機分布、泊松隨機分布等多個情況下移動路徑選擇的特點。

3.2.3.1當不存在障礙物和空洞區(qū)域時的算法比較

如圖9所示，圓形表示傳感節(jié)點，五角星表示Sink節(jié)點的停留網(wǎng)格中心。當不存在障礙物和空洞區(qū)域且傳感節(jié)點均勻分布時，Sink節(jié)點根據(jù)停留次數(shù)，虛擬合力大小和方向，找到一條由30個網(wǎng)格中心組成且圍繞初始位置的移動路徑，盡可能擴大其移動范圍。

圖9　不存在障礙物和空洞區(qū)域的Sink節(jié)點移動路徑

圖10比較了各算法的Sink節(jié)點一輪數(shù)據(jù)收集量。如圖10所示，在MPSA算法中，Sink節(jié)點往周圍第k+1跳未覆蓋傳感節(jié)點多的位置移動，且采用邊界虛擬斥力避免Sink節(jié)點在邊界周圍采集數(shù)據(jù)而導致的采集效率不高和移動路徑選擇時的自循環(huán)，擴大了Sink節(jié)點的數(shù)據(jù)采集范圍，因此MPSA算法的一輪數(shù)據(jù)收集量最多，RAND算法次之，GMRE和EASR算法的一輪數(shù)據(jù)收集量較小。

圖10　一輪數(shù)據(jù)收集量比較圖

圖11比較了各算法的能與Sink節(jié)點通信的傳感節(jié)點率。如圖11所示，在規(guī)定的最大數(shù)據(jù)傳輸時延內(nèi)，MPSA算法采用虛擬力理論擴大了Sink節(jié)點的通信范圍，讓更多的傳感節(jié)點與Sink節(jié)點通信，提高了節(jié)點覆蓋率。而EASR算法往往只是在某一個局部區(qū)域移動，節(jié)點覆蓋率低。因此，MPSA算法的節(jié)點覆蓋率最大，RAND和GMRE算法次之，EASR算法的節(jié)點覆蓋率最小。圖12比較在規(guī)定的最大數(shù)據(jù)傳輸時延內(nèi)各算法的平均節(jié)點丟棄數(shù)據(jù)量。如圖12所示，由于傳感節(jié)點的數(shù)據(jù)緩沖空間有限，MPSA算法讓更多的傳感節(jié)點與Sink節(jié)點通信，降低了這些傳感節(jié)點的數(shù)據(jù)存儲壓力，因此MPSA算法的平均節(jié)點丟棄數(shù)據(jù)量最低，RAND算法次之，GMRE和EASR算法的平均節(jié)點丟棄數(shù)據(jù)量較高。

圖11　節(jié)點覆蓋率比較圖

圖12　平均節(jié)點丟棄數(shù)據(jù)量比較圖

圖13比較了從網(wǎng)絡開始到某一個傳感節(jié)點能耗耗盡為止各算法的平均節(jié)點能耗。如圖13所示，在MPSA算法中，Sink節(jié)點為了擴大節(jié)點覆蓋率，有時需要停留在一些通信能耗較大的過渡網(wǎng)格中心，而且由于節(jié)點覆蓋率較大，導致較多的傳感節(jié)點參與數(shù)據(jù)通信，消耗能量。因此MPSA算法的平均節(jié)點能耗最大。在GMRE和EASR算法中，Sink節(jié)點往往停留在節(jié)點能耗較小的網(wǎng)格中心且參與數(shù)據(jù)通信的傳感節(jié)點數(shù)量較少，因此這兩個算法的平均節(jié)點能耗較小。由于Sink節(jié)點移動的隨機性，RAND算法的平均節(jié)點能耗起伏較大。

圖13　平均節(jié)點能耗比較圖

總之，當不存在障礙物和空洞區(qū)域且傳感節(jié)點均勻分布時，MPSA算法根據(jù)傳感節(jié)點的位置、剩余能量等信息，尋找到一條較優(yōu)的路徑，從而提高一輪數(shù)據(jù)傳輸量和節(jié)點覆蓋率，降低平均節(jié)點丟棄數(shù)據(jù)量。

3.2.3.2當存在障礙物時的算法比較

假設在網(wǎng)格中心（4，4）、（4，5）、（4，6）和（4，7）上存在障礙物。選擇障礙物斥力系數(shù)xz為1010，其它參數(shù)和節(jié)3.1中參數(shù)一樣。如圖14所示，MPSA算法引入障礙物斥力，從而避開存在障礙物的網(wǎng)格中心，尋找到一條適合當前傳感節(jié)點位置分布的路徑。由于存在障礙物時的傳感節(jié)點分布、參數(shù)設置與節(jié)3.2.3.1中基本相同，兩者仿真結(jié)果也類似，因此本文不過多闡述，可參考節(jié)3.2.3.1中相關內(nèi)容。

圖14　當存在障礙物時Sink節(jié)點移動路徑

3.2.3.3當存在空洞時的算法比較

如圖15所示，假設在監(jiān)測區(qū)域中以坐標（600，0），（600，400），（1000，0）和（1000，400）為頂點的矩形區(qū)域內(nèi)不存在傳感節(jié)點。選擇空洞斥力系數(shù)xk為1010，最大數(shù)據(jù)傳輸時延25dgird/v，其它參數(shù)和節(jié)3.1中參數(shù)一樣。在MPSA算法中，Sink節(jié)點分析傳感節(jié)點的位置分布，計算空洞區(qū)域，避開選擇該區(qū)域的網(wǎng)格中心作為停留網(wǎng)格中心，從而尋找到一條避開空洞區(qū)域的較優(yōu)路徑。由于MPSA算法的一輪數(shù)據(jù)收集量、節(jié)點覆蓋率、平均節(jié)點丟棄數(shù)據(jù)量和平均節(jié)點能耗的仿真結(jié)果值與節(jié)3.2.3.1中的仿真結(jié)果值相差不大，因此本文不過多闡述，可參考節(jié)3.2.3.1中相關內(nèi)容。

圖15　當存在空洞時Sink節(jié)點移動路徑

3.2.3.4當傳感節(jié)點泊松隨機分布時的算法比較

在點（450 450）周圍泊松隨機分布了100個傳感節(jié)點。選擇數(shù)據(jù)傳輸時延20dgird/v，其它參數(shù)和節(jié)3.1中參數(shù)一樣，獲得Sink節(jié)點的移動路徑。如圖16所示，Sink節(jié)點的移動路徑集中在節(jié)點密集分布的區(qū)域，沒有向無傳感節(jié)點分布的區(qū)域移動。由于傳感節(jié)點密集分布，節(jié)點通信能耗少，因此當節(jié)點數(shù)量相同時，傳感節(jié)點泊松分布時MPSA算法的算法性能會略高于傳感節(jié)點均勻分布的MPSA算法，但是兩者的仿真結(jié)果值相差不大，因此本文不過多闡述，可參考節(jié)3.2.3.1中相關內(nèi)容。

圖16　當傳感節(jié)點泊松隨機分布時Sink節(jié)點移動路徑

4　總結(jié)

本文首先考慮實際無線傳感網(wǎng)系統(tǒng)中數(shù)據(jù)傳輸時延和跳數(shù)受限情況，提出了算法的假設。其次，提出數(shù)據(jù)收集算法，解決在Sink節(jié)點的移動過程中，其k跳通信范圍內(nèi)傳感節(jié)點相關信息和感知數(shù)據(jù)的收集問題。提出虛擬力的計算方法，計算Sink節(jié)點的當前網(wǎng)格中心的停留時間和下一個停留網(wǎng)格中心。接著，提出Sink節(jié)點和傳感節(jié)點各自的算法實現(xiàn)步驟。最后給出算法的仿真參數(shù)，仿真分析關鍵參數(shù)對算法的影響，比較和分析MPSA算法、RAND算法、GMRE算法和EASR算法的性能。

仿真結(jié)果表明:當傳感節(jié)點隨機均勻分布、存在障礙物和空洞區(qū)域、傳感節(jié)點隨機泊松分布等情況下，MPSA算法都能根據(jù)傳感節(jié)點的位置、剩余能量等信息，尋找到一條較優(yōu)的路徑，從而提高一輪數(shù)據(jù)傳輸量和節(jié)點覆蓋率，降低平均節(jié)點丟棄數(shù)據(jù)量。但是在MPSA算法中，xb、xz、xk、x2、Fth等關鍵參數(shù)選擇固定值。因此下一階段目標是考慮這些關鍵參數(shù)的動態(tài)變化，尋找自適應選擇方法，進一步提高算法的性能和適用范圍。

［1］ Zhu C，Shu L，Hara T，et al.A Survey on Communication and Data Management Issues in Mobile Sensor Networks［J］.Wireless Communications and Mobile Computing，2014，14（1）:19-36.

［2］ 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.

［3］ Rao J，Biswas S.Data Harvesting in Sensor Networks Using Mobile Sinks［J］.IEEE Wireless Communications，2008，15（6）:63-70.

［4］ Keskin M E，Altinel I K，Aras N，et al.Lifetime Maximization in Wireless Sensor Networks Using a Mobile Sink with Nonzero Traveling Time［J］.The Computer Journal，2011，54（12）:1987-1999.

［5］ 郭劍，孫力娟，許文君，等.基于移動Sink的無線傳感器網(wǎng)絡數(shù)據(jù)采集方案［J］.通信學報，2012，33（9）:176-184.

［6］ Liu W，Lu K，Wang Ji，et al.Performance Analysis of Wireless Sensor Networks with Mobile Sinks［J］.IEEE Transactions on Vehicular Technology，2012，61（6）:2777-2789.

［7］ Kumar A K，Sivalingam K M，Kumar A，et al.On Reducing Delay in Mobile Data Collection Based Wireless Sensor Networks［J］. Wireless Network，2013，19（3）:285-299.

［8］ 王章權(quán)，陳友榮，尉理哲，等.優(yōu)化網(wǎng)絡生存時間的Sink節(jié)點移動路徑選擇算法［J］.傳感技術學報，2014，27（3）:80-87.

［9］ Salarian H，Chin K W，Naghdy F，et al.An Energy-Efficient Mobile-Sink Path Selection Strategy for Wireless Sensor Networks ［J］.IEEE Transactions on Vehicular Technology，2014，63（5）: 2407-2419.

［10］Lee K，Kim Y H，Kim H J，et al.A Myopic Mobile Sink Migration Strategy for Maximizing Lifetime of Wireless Sensor Networks［J］. Wireless Networks，2014，20（2）:303-318.

［11］Basagni S，Carosi A，Melachrinoudis E，et al.Controlled Sink Mobility for Prolonging Wireless Sensor Networks Lifetime［J］. Wireless Networks，2008，14（6）:831-858.

［12］Wang C F，Shih J D，Pan B H，et al.A Network Lifetime Enhancement Method for Sink Relocation and Its Analysis in Wireless Sensor Networks［J］.IEEE Sensors Journal，2014，14（6）:1932-1943.

［13］劉惠，柴志杰，杜軍朝，等.基于組合虛擬力的傳感器網(wǎng)絡三維空間重部署算法研究［J］.自動化學報，2011，36（6）:713-723.

［14］范興剛，王恒，張兆娟，等.一種基于虛擬力導向微粒群的有向傳感器網(wǎng)絡覆蓋增強策略［J］.傳感技術學報，2015，28（11）: 1720-1726.

王章權(quán)（1969-），男，碩士，浙江諸暨人，教授，浙江樹人大學信息科技學院，主要研究方向為無線傳感網(wǎng)、控制技術；

陳友榮（1982-），男，博士，浙江蒼南人，副教授，浙江樹人大學信息科技學院，主要研究方向為無線傳感網(wǎng)、物聯(lián)網(wǎng)，Jack_chenyr@163.com；

任條娟（1965-），女，碩士，浙江杭州人，教授，浙江樹人大學信息科技學院，主要研究方向為無線傳感網(wǎng)、車聯(lián)網(wǎng)。

Sink Node Moving Path Selection Algorithm Limited by Data Transmission Delay and Hops*

WANG Zhangquan，CHEN Yourong*，REN Tiaojuan，LIU Yaolin
（College of Information Science and Technology，Zhejiang Shuren University，Hangzhou 310015，China）

Considering that data transmission delay and hops are limited in actual system，and to reduce the time complexity of algorithm，sink node moving path selection algorithm（MPSA）in mobile wireless sensor networks is proposed.In MPSA algorithm，sink node uses distributed shortest path tree algorithm to gather relevant information and data of sensor nodes in k+1-hop communication range.It uses virtual force theory to calculate the virtual repulsive forces of boundaries，obstacles and void regions，virtual gravitational forces of non-covered k+1-hop sensor nodes and resultant force of all virtual forces.It calculates residence time at present grid center and next residence grid center based on the information such as number of residence，size and direction of the resultant force.Simulation results show that according to the information such as node position and residual energy，MPSA algorithm can find an appropriate moving path of sink node，improve the gathering data amount and node coverage rate of sink node，and reduce the drop amount of sensor nodes'sensed data.In short，when data transmission delay and hops are limited，MPSA algorithm outperforms RAND algorithm，GMRE algorithm and EASR algorithm.

mobile wireless sensor networks；path selection；virtual force；data transmission delay；data transmission hop

TP393

A

1004-1699（2016）04-0583-10

項目來源:浙江省自然科學基金項目（LY14F030006，LY15F030004）；國家自然科學基金項目（61501403）；浙江省公益性技術應用研究計劃項目（2015C33028）；浙江省教育廳項目（Y201432498）

2015-10-04修改日期:2016-01-06