趙 青, 夏 娜, 束 強(qiáng), 伊 君

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230009)

Voronoi-BFO水面移動基站路徑規(guī)劃算法

趙 青, 夏 娜, 束 強(qiáng), 伊 君

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230009)

在水面無線傳感器網(wǎng)絡(luò)(surface wireless sensor networks,SWSNs)中,傳感器節(jié)點(diǎn)布置稀疏,節(jié)點(diǎn)間距離大于節(jié)點(diǎn)通信距離,移動基站需有效收集節(jié)點(diǎn)數(shù)據(jù)信息。完整收集節(jié)點(diǎn)數(shù)據(jù),使基站移動路徑最短或近似最短是一個關(guān)鍵問題。文章在節(jié)點(diǎn)間距離大于節(jié)點(diǎn)通信距離的前提下,利用Voronoi圖理論生成基站移動候選子路徑,并使用細(xì)菌覓食優(yōu)化(bacterial foraging optimization，BFO)算法求解,以使規(guī)劃路徑最短或近似最短,網(wǎng)絡(luò)通信能耗降低。結(jié)果表明,該方法在不同網(wǎng)絡(luò)規(guī)模情況下均具有最短或近似最短的路徑長度,且網(wǎng)絡(luò)通信能耗低。

水面無線傳感器網(wǎng)絡(luò);Voronoi圖;細(xì)菌覓食優(yōu)化算法;移動基站;路徑規(guī)劃

水面無線傳感器網(wǎng)絡(luò)(surface wireless sensor networks,SWSNs)是由分布在水面環(huán)境中的多個浮標(biāo)式傳感器節(jié)點(diǎn)組成的無線傳感器網(wǎng)絡(luò)[1]。該網(wǎng)絡(luò)中的節(jié)點(diǎn)配以多種傳感器采集水面或水下數(shù)據(jù)信息,并以射頻通信方式傳輸信息和采集數(shù)據(jù),可用于海洋、河流及湖泊等環(huán)境監(jiān)測領(lǐng)域,具有重要的應(yīng)用價(jià)值[2]。

SWSNs的組成結(jié)構(gòu)如圖1所示。其中水面?zhèn)鞲衅鞴?jié)點(diǎn)(surface sensor node,SSN)用于收集水面或水下數(shù)據(jù),并通過無線射頻通信傳輸數(shù)據(jù);移動基站 (mobile base station,MBS)負(fù)責(zé)采集整個網(wǎng)絡(luò)中SSN信息。SWSNs與節(jié)點(diǎn)密集部署的陸地?zé)o線傳感器網(wǎng)絡(luò)相比,通常有著傳感器節(jié)點(diǎn)布置稀疏的特點(diǎn),即節(jié)點(diǎn)通信半徑小于節(jié)點(diǎn)間距離,導(dǎo)致無法采用節(jié)點(diǎn)間的多跳路由方法進(jìn)行數(shù)據(jù)的匯聚,而采用MBS遍歷各個SSN進(jìn)行數(shù)據(jù)采集是當(dāng)前主要的數(shù)據(jù)匯聚方法。在監(jiān)測水域中規(guī)劃出一條基站移動路徑,不僅可以收集到所有SSN的數(shù)據(jù),而且可以達(dá)到路徑最短和網(wǎng)絡(luò)節(jié)能。

圖1 水面無線傳感器網(wǎng)絡(luò)組成結(jié)構(gòu)

近年來,學(xué)者們針對無線傳感器網(wǎng)絡(luò)提出了多種基站移動方法。按數(shù)據(jù)收集方式不同,可分為基于節(jié)點(diǎn)單跳通信的基站移動方法[3-5]和基于節(jié)點(diǎn)多跳路由的基站移動方法[6-8]兩類。以單跳通信的方式,傳感器節(jié)點(diǎn)的數(shù)據(jù)信息直接發(fā)送至基站,不需要其他節(jié)點(diǎn)轉(zhuǎn)發(fā)。這種方式有效降低了節(jié)點(diǎn)的通信能耗,且容易實(shí)現(xiàn)。但文獻(xiàn)[3-4]中單基站是隨機(jī)移動的,其隨機(jī)性無法保障完整收集數(shù)據(jù),同時也無法預(yù)估完整數(shù)據(jù)收集的路徑長度和耗時。文獻(xiàn)[5]采用多基站收集數(shù)據(jù)，存在著資源浪費(fèi)、不易統(tǒng)籌等問題。而文獻(xiàn)[6-8]中基于多跳路由的移動方法,在節(jié)點(diǎn)布置稀疏的SWSNs中,因?yàn)楣?jié)點(diǎn)間難以直接通信,不易構(gòu)建節(jié)點(diǎn)間的通信路由,所以多跳路由在實(shí)際SWSNs中難以使用。

本文研究了基于節(jié)點(diǎn)單跳通信的基站移動方法,提出了一種Voronoi圖(維諾圖)構(gòu)造細(xì)菌覓食優(yōu)化 (bacteria foraging optimization,BFO)算法的水面移動基站路徑規(guī)劃方法。首先利用Voronoi圖理論生成基站移動的候選子路徑,然后采用BFO算法求解最優(yōu)路徑。算法中設(shè)計(jì)的合法解判別方法同時具有將非法解改造成合法解的功能。仿真結(jié)果證明了該方法具有生成路徑短和網(wǎng)絡(luò)通信能耗低的優(yōu)點(diǎn)。

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

水面上傳感器節(jié)點(diǎn)隨機(jī)分布,位置固定且已知。MBS根據(jù)規(guī)劃路徑在該二維平面內(nèi)移動并進(jìn)行節(jié)點(diǎn)的數(shù)據(jù)信息采集。假設(shè)滿足下列條件:

(1) 節(jié)點(diǎn)布置稀疏,即節(jié)點(diǎn)間的距離大于節(jié)點(diǎn)的通信半徑,節(jié)點(diǎn)間不能直接通信。

(2) MBS和傳感器節(jié)點(diǎn)的通信以請求-應(yīng)答方式為主。MBS到達(dá)某位置,廣播數(shù)據(jù)請求消息,收到請求的節(jié)點(diǎn)由休眠模式切換至工作模式,并將自身的數(shù)據(jù)發(fā)送給MBS,完成數(shù)據(jù)傳輸即刻切換至休眠模式。短時間內(nèi)節(jié)點(diǎn)不再響應(yīng)基站的數(shù)據(jù)請求消息。

(3) 傳感器節(jié)點(diǎn)的能耗主要由處理器、傳感器和無線通信模塊3個部分的能耗組成,其中無線通信的能耗占據(jù)絕大部分,故傳感器節(jié)點(diǎn)的能耗可近似等于其通信能耗。本文采用典型的自由空間通信能耗模型[9],如圖2所示,傳感器節(jié)點(diǎn)的能耗為:

(1)

其中,k1、k2分別為節(jié)點(diǎn)收發(fā)的數(shù)據(jù)量;cs為傳感器節(jié)點(diǎn)收發(fā)電路的能耗系數(shù);εs為傳感器節(jié)點(diǎn)發(fā)射功率的放大系數(shù);d為通信距離。

圖2 傳感器節(jié)點(diǎn)的能耗模型

(4) MBS能耗主要包括移動能耗和通信能耗，其中移動能耗主要由移動距離決定，通信能耗與傳感器節(jié)點(diǎn)通信能耗模型相同，則MBS在整個移動和數(shù)據(jù)收集過程中的能耗為:

(2)

其中,P為移動基站航行功率;l為移動路徑長度;v為航行速度;n為傳感器節(jié)點(diǎn)個數(shù);q為移動基站廣播次數(shù);k1為移動基站一次廣播消息的數(shù)據(jù)量;k2為單個傳感器節(jié)點(diǎn)發(fā)送來的數(shù)據(jù)量;cB為基站發(fā)射或接收電路的能耗系數(shù);εB為基站發(fā)射功率放大系數(shù);R為基站廣播的通信半徑,R足夠大。

2 水面移動基站路徑規(guī)劃方法設(shè)計(jì)

2.1 Voronoi圖理論生成基站移動候選子路徑

通過Voronoi圖理論劃分SWSNs結(jié)構(gòu),得到一系列基站移動的候選子路徑。Voronoi圖又叫泰森多邊形或Dirichlet圖,是計(jì)算幾何中重要的幾何結(jié)構(gòu),具有很高的應(yīng)用價(jià)值[10]。它是由許多連接兩鄰點(diǎn)線段的垂直平分線段構(gòu)成的連續(xù)多邊形所組成。n個在二維平面上位置不一的點(diǎn),根據(jù)最鄰近原則劃分平面結(jié)構(gòu),每個點(diǎn)其最鄰近區(qū)域相關(guān)聯(lián)。

依據(jù)SWSNs中n個節(jié)點(diǎn)的位置,按照Voronoi圖劃分平面的方法,將整個二維區(qū)域劃分為n個子區(qū)域,且形成一系列的Voronoi邊。

在監(jiān)測區(qū)域A中有4個傳感器節(jié)點(diǎn)s1、s2、s3、s4,它們的位置如圖3所示。按照Voronoi圖劃分區(qū)域的方法,可以將監(jiān)測區(qū)域A劃分為4個子區(qū)域,并形成5條Voronoi邊e1、e2、e3、e4、e5,如圖3所示。

圖3 基于傳感器節(jié)點(diǎn)位置生成的Voronoi圖

定理1 基站在Voronoi邊上收集相鄰傳感器節(jié)點(diǎn)(距離該Voronoi邊最近的傳感器節(jié)點(diǎn))數(shù)據(jù),可以達(dá)到傳感器節(jié)點(diǎn)通信能耗最小。

證明 假設(shè)一條Voronoi邊ek,其相鄰傳感器節(jié)點(diǎn)為si和sj,如圖4a所示。由Voronoi圖理論可知,ek是si和sj的垂直平分線,即si和sj距離o點(diǎn)的距離相等,表示為d。當(dāng)基站沿著Voronoi邊移動到o點(diǎn)時,廣播數(shù)據(jù)請求消息。si和sj收到消息,并將自身的數(shù)據(jù)發(fā)送給移動基站。

節(jié)點(diǎn)si接收消息并發(fā)送數(shù)據(jù)的能耗為:

其中,k1為節(jié)點(diǎn)si接收消息的數(shù)據(jù)量;k2為節(jié)點(diǎn)si發(fā)送的數(shù)據(jù)量。

節(jié)點(diǎn)si和sj總的通信能耗為:

節(jié)點(diǎn)si和sj總的通信能耗為:

圖4 基站沿Voronoi邊和任意邊收集傳感器節(jié)點(diǎn)數(shù)據(jù)

將上述2種情況下的通信能耗進(jìn)行比較，計(jì)算可得:

因?yàn)閐i+dj=2d,所以有:

即E′≥E?？梢?基站在Voronoi邊上收集相鄰傳感器節(jié)點(diǎn)數(shù)據(jù),可以達(dá)到傳感器節(jié)點(diǎn)通信能耗最小。證畢。

條件3 路徑長度最短。

2.2 基于BFO算法求解最優(yōu)的候選子路徑集合

BFO算法是模擬大腸桿菌(E.coli)覓食行為的一種新型仿生啟發(fā)式優(yōu)化算法[11]。由于其在求解優(yōu)化問題過程中對初值不敏感,無需優(yōu)化對象的梯度信息,且具有分布并行搜索和全局尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)。BFO算法的離散化形式非常適合于求解本文的組合優(yōu)化問題。

2.2.1 細(xì)菌的一維二進(jìn)制編碼

BFO算法作為一種群智能優(yōu)化算法,通過細(xì)菌種群的進(jìn)化過程(趨化、復(fù)制和遷徙)完成對最優(yōu)解的搜索。種群由若干細(xì)菌組成,細(xì)菌通常以數(shù)值編碼的形式表達(dá)。對于本文優(yōu)化問題,設(shè)計(jì)的細(xì)菌一維二進(jìn)制編碼為x=(x1x2… xm),其中x1,x2,…,xm分別對應(yīng)了m條候選子路徑,即m條Voronoi邊,xi=1(1≤i≤m)表示第i條Voronoi邊被選擇,xi=0表示該Voronoi邊未被選擇。

2.2.2 細(xì)菌的初始化

隨機(jī)產(chǎn)生m個二進(jìn)制數(shù),構(gòu)成一個細(xì)菌編碼x=(x1x2… xm)。但是該編碼很可能不滿足上述條件1和條件2,即所選出的Voronoi邊不一定能顧及到所有傳感器節(jié)點(diǎn),或不能構(gòu)成一條連續(xù)路徑?？梢酝ㄟ^以下方法判斷編碼x=(x1x2… xm)能否滿足條件1和條件2。

定義1 Voronoi邊-節(jié)點(diǎn)關(guān)系矩陣。將監(jiān)測區(qū)域中所有Voronoi邊及其顧及到的傳感器節(jié)點(diǎn)用關(guān)系矩陣O加以描述。具體形式如圖5所示。

圖5 Voronoi邊-節(jié)點(diǎn)關(guān)系矩陣O

Voronoi邊-節(jié)點(diǎn)關(guān)系矩陣O=[oij],其中，i=1,2,…,n；j=1,2,…,m。oij=1表示Voronoi邊ej可以顧及到節(jié)點(diǎn)si；oij=0則表示Voronoi邊ej未顧及到節(jié)點(diǎn)si。

若x·O≥(k1k2k3…kn)T,k1,k2,k3,…,kn均為大于等于1的整數(shù),則滿足條件1。

現(xiàn)使用深度優(yōu)先搜索算法[12]將細(xì)菌編碼所對應(yīng)的Voronoi邊的端點(diǎn)遍歷以判斷其組成的路徑是否連續(xù)。若連續(xù),則滿足條件2。

定義2 在非連續(xù)的路徑圖中,選擇最近的端點(diǎn)相連,形成的邊稱為虛擬Voronoi邊。

算法步驟為:

步驟1 將選中子路徑頂點(diǎn)(vi,…,vs,bj,…,bt)初始化,visited[vi]=false。

步驟2 從某條選中子路徑的頂點(diǎn)vi出發(fā),并將visited[vi]=true。

步驟3 若vi的鄰接點(diǎn)vk存在,判斷其訪問狀態(tài),若visited[vk]=false,則設(shè)置visited[vk]=true。依次檢驗(yàn)vk的鄰接點(diǎn)是否存在；若存在，則判斷其訪問狀態(tài),若為false，則置其狀態(tài)為true。重復(fù)此步驟。

步驟4 檢驗(yàn)是否所有點(diǎn)滿足visited[vk]=true；若是，則路徑連續(xù)。

步驟5 若仍有頂點(diǎn)未被訪問到,則建立虛擬Voronoi邊使路徑連續(xù),使非可行解變?yōu)榭尚薪狻?/p>

條件3即為求

(3)

其中，ci為Voronoi邊ei的長度；i=1,2,…,m。

2.2.3 改進(jìn)BFO算法

本文將BFO算法應(yīng)用于MBS路徑規(guī)劃模型的組合優(yōu)化問題中并作出如下改進(jìn):

(1) 路徑規(guī)劃模型的組合優(yōu)化是一個多約束條件的整數(shù)規(guī)劃問題。一般情況下細(xì)菌的取值變量是變量取值范圍內(nèi)的任意實(shí)數(shù),但本文將所有Voronoi邊的選擇情況作為細(xì)菌變量,使用BFO算法應(yīng)注意所有變量取值應(yīng)為0或1,以解集選中情況x([x1x2… xm])組成的空間矢量θ([θ1θ2… θm]T)作為一個細(xì)菌,采用 (3) 式的值對應(yīng)搜索空間中細(xì)菌的健康狀態(tài)，即適應(yīng)度函數(shù)J(θ),即在滿足條件1和條件2的情況下，路徑長度越短，則適應(yīng)度函數(shù)值越小。

在BFO算法中使用Sigmoid函數(shù),將其各維如下離散成0～1的二元數(shù)值。BFO算法在趨向性操作中細(xì)菌i的位置更新描述如下:

(4)

(5)

(2) 判斷每個細(xì)菌生成的解中每一維是否滿足條件2,若不滿足,則繼續(xù)游動,直到滿足條件2或達(dá)到額定游動次數(shù)Ns，完成一次趨化操作。若滿足約束條件,則根據(jù)(3)式計(jì)算細(xì)菌的適應(yīng)度函數(shù)值。

改進(jìn)BFO算法步驟為:

步驟1 給定Voronoi邊-節(jié)點(diǎn)關(guān)系矩陣O,確定細(xì)菌種群規(guī)模S和細(xì)菌向量長度m。

步驟2 設(shè)置趨化、復(fù)制和遷徙操作的次數(shù)Nc、Nre、Ned,按照本文方法初始化細(xì)菌種群和遷徙概率Ped。

步驟4 細(xì)菌種群進(jìn)行復(fù)制操作。細(xì)菌執(zhí)行完趨化操作后,根據(jù)適應(yīng)度函數(shù)計(jì)算出所有細(xì)菌的健康度函數(shù)值并按從大到小的順序進(jìn)行排列,保留較大的Sr個并進(jìn)行復(fù)制,淘汰較小的Sr個。

步驟5 細(xì)菌種群執(zhí)行遷徙操作。復(fù)制操作

完成后,生成一個隨機(jī)概率并將其與Ped比較,若小于Ped，則執(zhí)行細(xì)菌的遷徙操作,并重新執(zhí)行趨化操作。

步驟6 判斷循環(huán)結(jié)束條件,若滿足,則結(jié)束,并輸出結(jié)果。

3 仿真實(shí)驗(yàn)分析

為了驗(yàn)證本文Voronoi-BFO水面移動基站路徑規(guī)劃方法的正確性和有效性,在Matlab7.0平臺上進(jìn)行了3組規(guī)模不同的實(shí)驗(yàn),并將該方法與其他文獻(xiàn)中的具有代表性的路徑規(guī)劃方法相比較。

實(shí)驗(yàn)1 100 m×100 m 監(jiān)測水域,50個水面?zhèn)鞲衅鞴?jié)點(diǎn){s1,s2,…,s50}。

實(shí)驗(yàn)2 100 m×100 m監(jiān)測水域,75個水面?zhèn)鞲衅鞴?jié)點(diǎn){s1,s2,…,s75}。

實(shí)驗(yàn)3 100 m×100 m監(jiān)測水域,100個水面?zhèn)鞲衅鞴?jié)點(diǎn){s1,s2,…,s100}。

本文采用通信能耗模型,其中參數(shù)分別為cs=50 nJ/bit,cB=200 nJ/bit,εs=100 pJ/(bit·m2),εB=500 pJ/(bit·m2),k1=50 bit,k2=1 000 bit,P=10 W,v=1 m/s。其中,cs和εs的取值參考文獻(xiàn)[9]。

3.1 可行性分析

在3組實(shí)驗(yàn)中,采用本文方法規(guī)劃的基站移動路徑如圖6所示。

圖6 不同點(diǎn)路徑規(guī)劃圖

由圖6可以看出,采用本文提出的Voronoi-BFO水面移動基站路徑規(guī)劃算法,可以求解并優(yōu)選出基站移動路徑。基站按照該路徑進(jìn)行移動,可以收集所有傳感器節(jié)點(diǎn)的數(shù)據(jù),并保證路徑連續(xù),且路徑長度分別為507.354、563.496、610.63 m。

3.2 與相關(guān)方法的性能比較

文獻(xiàn)[3]的方法是一種隨機(jī)的基站移動方法,且當(dāng)基站靠近傳感器節(jié)點(diǎn)時收集節(jié)點(diǎn)數(shù)據(jù)。文獻(xiàn)[5]研究無線傳感器網(wǎng)絡(luò)中移動基站遍歷固定位置的傳感器節(jié)點(diǎn),將路徑規(guī)劃直接轉(zhuǎn)化為旅行商問題(travelling salesperson problem,TSP)求解。

3.2.1 路徑長度比較

在3組實(shí)驗(yàn)中,本文方法、文獻(xiàn)[3]方法和文獻(xiàn)[5]方法分別規(guī)劃出的基站的移動路徑見表1所列。由表1可知,本文方法所規(guī)劃的路徑長度明顯小于文獻(xiàn)[3]和文獻(xiàn)[5]的方法。在基站移動速度一定的情況下,采用本文方法移動基站可以用較短的時間完成對監(jiān)測區(qū)域中傳感器數(shù)據(jù)的收集,以至基站移動路徑長度短、能耗更低。

表1 3種方法所規(guī)劃的路徑長度 m

3.2.2 網(wǎng)絡(luò)總能耗比較

在3組實(shí)驗(yàn)中,MBS分別按照本文方法、文

獻(xiàn)[3]方法和文獻(xiàn)[5]方法規(guī)劃出的路徑收集傳感器節(jié)點(diǎn)數(shù)據(jù),基站能耗包括移動能耗和通信能耗，具體見表2所列。

由表2可見,在3組實(shí)驗(yàn)中本文方法的網(wǎng)絡(luò)總能耗均是最小的,這主要得益于本文方法規(guī)劃出了最短的基站移動路徑,從而有效減小了基站的移動能耗。

因?yàn)樵谖墨I(xiàn)[3]方法和文獻(xiàn)[5]方法中,基站均移動至傳感器節(jié)點(diǎn)處收集數(shù)據(jù),所以節(jié)點(diǎn)通信能耗較低；而本文方法在一定程度上發(fā)揮了節(jié)點(diǎn)的通信能力,大幅度減小了基站移動路徑長度和能耗,使網(wǎng)絡(luò)總能耗達(dá)到了最低。

表2 3種方法網(wǎng)絡(luò)總能耗比較

4 結(jié) 論

本文將Voronoi圖理論引入到MBS路徑規(guī)劃的研究中,完善了相關(guān)理論方法，并將矩陣問題與節(jié)點(diǎn)數(shù)據(jù)收集完整相結(jié)合,將該問題具象化,采用BFO算法可有效解決該問題模型。大量仿真實(shí)驗(yàn)結(jié)果表明，本文方法在不同網(wǎng)絡(luò)規(guī)模下均能求出最短或近似最短路徑,因此可作為SWSNs路徑規(guī)劃的有效方法。下一步工作是在實(shí)際水面環(huán)境中進(jìn)行理論的方法測試,并拓展其綜合應(yīng)用。

[1] GKIKOPOULI A,NIKOLAKOPOULOS G,MANESIS S.A survey on underwater wireless sensor networks and applications[C]//Proceedings of the 20th Mediterranean Conference on Control & Automation.[S.l.]:IEEE,2012：1147-1154.

[2] DAVIS A,CHANG H.Underwater wireless sensor networks [J].Oceans,2012,4(Ⅶ)：1-5.

[3] SHAH R C,ROY S,JAIN S,et al.Data MULEs：modeling and analysis of three-tier architecture for sparse sensor networks [J].Ad Hoc Networks,2003,1(2/3)：215-233.

[4] 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.

[5] LIANG W F,SCHWEITZER P,XU Z C,et al.Approximation algorithms for capacitated minimum forest problems in wireless sensor networks with a mobile sink[J].IEEE Transactions on Computers,2013,62(10):1932-1944.

[6] 張建軍,萬磊,翟琰,等.基于能量區(qū)域代理機(jī)制的移動Sink 路由算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,38(1)：34-39.

[7] 陳濤,郭得科,羅雪山,等.一種基于移動基站的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集方法[J].國防科技大學(xué)學(xué)報(bào),2011,33(2):49-53.

[8] WANG Z M,BASAGNI S,MELACHRINOUDIS E,et al.Exploiting sink mobility for maximizing sensor networks lifetime.[C]//Proceedings of the 38th Hawaii International Conference on System Sciences.[S.l.:s.n.],2005：1-9.

[9] HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks [C]//Proceedings of the 33rd Hawaii International Conference on System Sciences.[S.l.:s.n.],2000：10-20.

[10] 夏娜,倪成春,徐朝農(nóng),等.逆向捕獲時間差的Voronoi聲源定位機(jī)制[J].通信學(xué)報(bào),2013,34(11)：140-152.

[11] PASSINO K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems,2002,22(3)：52-67.[12] TARJAN R.Depth-first search and linear graph algorithms[J].SIAM Journal on Computing,1972,1(2)：146-160.

(責(zé)任編輯 閆杏麗)

A path planning algorithm for water surface mobile base station based on Voronoi diagram and bacterial foraging optimization algorithm

ZHAO Qing, XIA Na, SHU Qiang, YI Jun

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

In surface wireless sensor networks(SWSNs), the sensor nodes are arranged sparsely, the distance between nodes is greater than the communication distance of the nodes, and the mobile base station needs to collect data of the nodes effectively. So the way to collect data completely so that the path is the shortest or the shortest approximately is a key problem. On the premise that the distance between nodes is greater than communication distance of the nodes, the base station moving candidate sub-path is generated by using the Voronoi diagram theory, and the bacterial foraging optimization(BFO) algorithm is proposed to solve the problem, so as to achieve a shortest path or approximate shortest path with lower energy consumption of network communication. The effectiveness of the proposed approach at different network scales is validated through extensive simulations.

surface wireless sensor networks(SWSNs); Voronoi diagram; bacterial foraging optimization(BFO) algorithm; mobile base station(MBS); path planning

2015-11-16；

2016-01-05

國家自然科學(xué)基金資助項(xiàng)目(61100211；61003307)；教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃資助項(xiàng)目(NCET-13-0768)和安徽省杰出青年科學(xué)基金資助項(xiàng)目(1408085J05)

趙 青(1990-),女,湖北荊州人,合肥工業(yè)大學(xué)碩士生; 夏 娜(1979-)，男，安徽蕪湖人，博士，合肥工業(yè)大學(xué)教授，碩士生導(dǎo)師.

10.3969/j.issn.1003-5060.2016.12.009

TP393.09

A

1003-5060(2016)12-1633-06