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

（浙江樹(shù)人大學(xué)信息科技學(xué)院，杭州310015）

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

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

（浙江樹(shù)人大學(xué)信息科技學(xué)院，杭州310015）

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

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

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

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

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

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

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

1　算法原理

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

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

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

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

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

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

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

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

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

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

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

1.2虛擬力計(jì)算

圖2　3個(gè)斥力的分析

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

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

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

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

最終計(jì)算所有虛擬力的合力F為

1.3停留時(shí)間和下一個(gè)停留位置計(jì)算

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

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

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

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

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

2　算法實(shí)現(xiàn)

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

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

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

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

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

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

步驟5經(jīng)過(guò)Sink節(jié)點(diǎn)在當(dāng)前停留網(wǎng)格中心的停留時(shí)間tg后，Sink節(jié)點(diǎn)移動(dòng)到下一個(gè)停留網(wǎng)格中心。

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

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

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

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

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

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

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

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

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

3.1仿真參數(shù)

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

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

表1　仿真參數(shù)表

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

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

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

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

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

圖5　x1和x2對(duì)MPSA算法的影響

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

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

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

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

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

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

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

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

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

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

總之，當(dāng)最大數(shù)據(jù)傳輸時(shí)延和跳數(shù)取較大值時(shí)，能提高M(jìn)PSA算法的節(jié)點(diǎn)覆蓋率和一輪數(shù)據(jù)收集量，但是受到實(shí)際硬件設(shè)備的限制，不能無(wú)限增大，需要根據(jù)實(shí)際應(yīng)用需求設(shè)定這兩個(gè)參數(shù)。

3.2.3算法比較和分析

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

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

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

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

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

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

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

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

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

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

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

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

3.2.3.2當(dāng)存在障礙物時(shí)的算法比較

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

圖14　當(dāng)存在障礙物時(shí)Sink節(jié)點(diǎn)移動(dòng)路徑

3.2.3.3當(dāng)存在空洞時(shí)的算法比較

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

圖15　當(dāng)存在空洞時(shí)Sink節(jié)點(diǎn)移動(dòng)路徑

3.2.3.4當(dāng)傳感節(jié)點(diǎn)泊松隨機(jī)分布時(shí)的算法比較

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

圖16　當(dāng)傳感節(jié)點(diǎn)泊松隨機(jī)分布時(shí)Sink節(jié)點(diǎn)移動(dòng)路徑

4　總結(jié)

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

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

［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］ 郭劍，孫力娟，許文君，等.基于移動(dòng)Sink的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集方案［J］.通信學(xué)報(bào)，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)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)路徑選擇算法［J］.傳感技術(shù)學(xué)報(bào)，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)絡(luò)三維空間重部署算法研究［J］.自動(dòng)化學(xué)報(bào)，2011，36（6）:713-723.

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

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

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

任條娟（1965-），女，碩士，浙江杭州人，教授，浙江樹(shù)人大學(xué)信息科技學(xué)院，主要研究方向?yàn)闊o(wú)線傳感網(wǎng)、車(chē)聯(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

項(xiàng)目來(lái)源:浙江省自然科學(xué)基金項(xiàng)目（LY14F030006，LY15F030004）；國(guó)家自然科學(xué)基金項(xiàng)目（61501403）；浙江省公益性技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目（2015C33028）；浙江省教育廳項(xiàng)目（Y201432498）

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