基于三維流函數(shù)的無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)Sink避障機(jī)制研究?

張美燕蔡文郁嚴(yán)求真

(1.浙江水利水電學(xué)院電氣工程學(xué)院，浙江 杭州310018；2.杭州電子科技大學(xué)電子信息學(xué)院，浙江 杭州310018)

基于移動(dòng)Sink節(jié)點(diǎn)的數(shù)據(jù)采集方式逐漸成為無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)重要研究方向[1－2]。隨著自動(dòng)化和智能化程度的不斷提高，無(wú)人小車、無(wú)人機(jī)、水下航行器等智能機(jī)器人系統(tǒng)逐漸應(yīng)用于各種傳感器網(wǎng)絡(luò)中[3－4]。在Sink節(jié)點(diǎn)進(jìn)行移動(dòng)數(shù)據(jù)采集過程中，計(jì)算的優(yōu)化路徑必須能夠規(guī)避無(wú)線傳感器網(wǎng)絡(luò)中可能存在的各種類障礙物。傳統(tǒng)的自主機(jī)器人避障是通過雷達(dá)、聲吶、激光等傳感器感知周圍的環(huán)境信息，確定當(dāng)前環(huán)境的障礙物分布，并根據(jù)各種傳感器采集到的感知數(shù)據(jù)進(jìn)行有效路徑避障。因此，避障路徑規(guī)劃已經(jīng)成為移動(dòng)機(jī)器人領(lǐng)域的重要研究課題，也是無(wú)線傳感器網(wǎng)絡(luò)中Sink節(jié)點(diǎn)移動(dòng)數(shù)據(jù)采集領(lǐng)域的一個(gè)技術(shù)難點(diǎn)。

目前關(guān)于無(wú)線傳感器網(wǎng)絡(luò)中移動(dòng)Sink節(jié)點(diǎn)路徑規(guī)劃的研究較多，但是考慮障礙物躲避特性的優(yōu)化路徑規(guī)劃研究相對(duì)較少[5]。1986年，Khatib提出了經(jīng)典的人工勢(shì)場(chǎng)法(Artificial Potential Fields，APF)[6]，雖然人工勢(shì)場(chǎng)避障算法非常簡(jiǎn)單，但是缺陷在于目標(biāo)點(diǎn)對(duì)移動(dòng)物體產(chǎn)生的引力與障礙物對(duì)移動(dòng)物體產(chǎn)生的斥力相混合，局部極值點(diǎn)導(dǎo)致避障失效。后續(xù)研究也對(duì)人工勢(shì)場(chǎng)避障方法進(jìn)行了改進(jìn)，Volpe等人提出基于超二次型(Super Quadric)的人工勢(shì)場(chǎng)結(jié)構(gòu)[7]代替?zhèn)鹘y(tǒng)二次型勢(shì)場(chǎng)，并對(duì)勢(shì)場(chǎng)函數(shù)加以修正。流函數(shù)法[8]作為一種新型的避障方法，借鑒流體力學(xué)的概念建立了勢(shì)場(chǎng)區(qū)域，通過模擬水流運(yùn)動(dòng)機(jī)理，規(guī)劃出的航線能夠像流水避開巖石一樣平滑繞過障礙物，還能避免局部最小問題。文獻(xiàn)[9]中引入流函數(shù)以解決障礙環(huán)境下單機(jī)器人的導(dǎo)航控制，從而產(chǎn)生光滑的無(wú)碰路徑，避免與障礙物發(fā)生碰撞。文獻(xiàn)[10]通過對(duì)單個(gè)障礙物流函數(shù)進(jìn)行加權(quán)求和，解決了兩個(gè)障礙物重疊情況下的路徑規(guī)劃問題。文獻(xiàn)[11]針對(duì)水下機(jī)器人在實(shí)際應(yīng)用中由于自身機(jī)動(dòng)性、探測(cè)性能約束而產(chǎn)生的問題，改進(jìn)了傳統(tǒng)的流函數(shù)法，結(jié)果驗(yàn)證了改進(jìn)算法能夠有效地規(guī)劃路徑。文獻(xiàn)[12]研究了流函數(shù)法在無(wú)人機(jī)航線規(guī)劃中的應(yīng)用，將地形障礙和雷達(dá)等威脅等效為圓柱體，推導(dǎo)了流體運(yùn)動(dòng)的復(fù)勢(shì)函數(shù)，將其應(yīng)用到多障礙物環(huán)境中。文獻(xiàn)[13]利用流函數(shù)解決單個(gè)移動(dòng)Sink節(jié)點(diǎn)的避障問題，提出了采用虛擬Leader和二叉樹結(jié)構(gòu)的多移動(dòng)Sink節(jié)點(diǎn)Swarming控制模型。文獻(xiàn)[14]提出改進(jìn)的流函數(shù)規(guī)劃無(wú)人機(jī)在復(fù)雜地形環(huán)境的航線。針對(duì)傳統(tǒng)流函數(shù)法面對(duì)多個(gè)障礙物時(shí)存在的問題，提出了一種基于虛擬動(dòng)態(tài)目標(biāo)的方法，解決了兩個(gè)障礙物重疊情況的航線規(guī)劃問題。圖1所示為單個(gè)和多個(gè)障礙物情況下的平面流場(chǎng)分布情況，可以發(fā)現(xiàn)移動(dòng)Sink節(jié)點(diǎn)沿著流線方向運(yùn)動(dòng)能夠?qū)崿F(xiàn)避障效果。

圖1 平面障礙物場(chǎng)景下流場(chǎng)分布

綜上所述，目前一些研究已將流函數(shù)方法應(yīng)用于無(wú)人機(jī)或無(wú)人航行器的避障路徑規(guī)劃領(lǐng)域，但是基本上都是針對(duì)二維平面應(yīng)用環(huán)境，缺乏三維環(huán)境下基于三維流函數(shù)的避障路徑研究。本文將流函數(shù)應(yīng)用到三維無(wú)線傳感器網(wǎng)絡(luò)環(huán)境中，利用球型障礙物在Z軸分層的方法實(shí)現(xiàn)三維流場(chǎng)計(jì)算，并且提出橢圓形路徑變形方法克服“滯點(diǎn)”問題，從而求取移動(dòng)Sink節(jié)點(diǎn)在三維無(wú)線傳感器網(wǎng)絡(luò)中的避障優(yōu)化路徑。

1 算法描述

無(wú)線傳感器網(wǎng)絡(luò)中分布的實(shí)際障礙物一般是不規(guī)則的，但是由于水流、風(fēng)沖刷、腐蝕等影響，長(zhǎng)時(shí)間作用下的障礙物一般都呈現(xiàn)了凸型多邊體形態(tài)[15]。為了簡(jiǎn)單起見，本文以障礙物的質(zhì)心位置為球心、安全半徑為R的規(guī)則球體來(lái)表示需要躲避的障礙物范圍。

基于凸球型障礙物的避障路徑規(guī)劃模型如圖2所示:在三維傳感器網(wǎng)絡(luò)空間內(nèi)隨機(jī)分布若干個(gè)球型障礙物，移動(dòng)Sink節(jié)點(diǎn)沿著預(yù)先設(shè)定的路徑進(jìn)行移動(dòng)數(shù)據(jù)采集。避障規(guī)劃的目標(biāo)是使移動(dòng)Sink節(jié)點(diǎn)所規(guī)劃路徑中的任何一點(diǎn)都不觸碰到障礙物范圍，而且規(guī)劃路徑要盡量保持連續(xù)和平滑?；谝陨蟽?yōu)化模型，本文借鑒流函數(shù)的思想并進(jìn)行三維擴(kuò)展，設(shè)計(jì)了適合三維傳感器網(wǎng)絡(luò)空間的有效避障路徑規(guī)劃方法。本文假設(shè)移動(dòng)Sink節(jié)點(diǎn)在移動(dòng)之前就已獲取了全局網(wǎng)絡(luò)空間內(nèi)障礙物的分布情況，因此可根據(jù)障礙物分布計(jì)算整個(gè)區(qū)域的三維流場(chǎng)分布。

圖2 基于球型障礙物的避障路徑規(guī)劃

流體力學(xué)中流體的繞流運(yùn)動(dòng)理想情況下可以看成是無(wú)旋運(yùn)動(dòng)，如果理想流體在某一源點(diǎn)是無(wú)旋流，則該流體在源點(diǎn)周圍也是無(wú)旋流[16]。對(duì)于任意的標(biāo)量函數(shù)?，存在?×??＝0，所以滿足無(wú)旋性的條件可以定義為:uf＝??，其中uf為速度勢(shì)，該無(wú)旋流定義為勢(shì)流場(chǎng)[17]。速度勢(shì)uf可表達(dá)為uf＝u＋iv，i指實(shí)數(shù)的虛部，因此有以下公式:

在直角坐標(biāo)系中，在二維不可壓縮流動(dòng)場(chǎng)中需要滿足質(zhì)量守恒方程:因此可引入一個(gè)新的函數(shù)定義如下[17]:

如果滿足上述條件，則上述函數(shù)被稱為流函數(shù)，流函數(shù)是表示流線的函數(shù)[18]。令球心位置為(Ox，Oy)，球體半徑為R，則在統(tǒng)一流場(chǎng)(洋流強(qiáng)度為U)作用下的流函數(shù)公式可以推導(dǎo)得到[18]:

由上述的推導(dǎo)過程可知，使用流函數(shù)的概念進(jìn)行避障路徑規(guī)劃，實(shí)質(zhì)上是將移動(dòng)Sink假設(shè)為水流體的一部分，利用虛擬的流線作為移動(dòng)Sink的運(yùn)動(dòng)軌跡。因此，可以按照上述的勢(shì)函數(shù)和流函數(shù)公式生成避障流線分布，讓移動(dòng)Sink節(jié)點(diǎn)根據(jù)起點(diǎn)位置選擇相應(yīng)的流線，并沿著該流線運(yùn)動(dòng)，就可以避開相應(yīng)的障礙物?；诹骱瘮?shù)的路徑規(guī)劃可以滿足躲避障礙物的需求，同時(shí)還可以保持運(yùn)動(dòng)路徑的連續(xù)性和平滑性。

下文主要推導(dǎo)三維流函數(shù)的存在條件和構(gòu)造方法。在不可壓縮的無(wú)旋場(chǎng)中，由于球體障礙物是立體對(duì)稱的，因此三維流函數(shù)可以通過將X－Y平面經(jīng)過Z軸擴(kuò)展到X－Y－Z三維坐標(biāo)系。三維空間球型障礙物環(huán)境下的流場(chǎng)計(jì)算方式如圖3所示:本文將球型障礙物用不同的Z值平面去切割，切割成一個(gè)個(gè)不同半徑R?的圓形障礙物，因此可以求出對(duì)應(yīng)不同Z坐標(biāo)的圓形障礙物的流函數(shù)分布，如圖4所示。按照不同Z坐標(biāo)下的流場(chǎng)曲線，移動(dòng)Sink根據(jù)自身的起點(diǎn)位置選擇合適流線進(jìn)行避障路徑規(guī)劃。

圖3 三維空間球型障礙物環(huán)境下流場(chǎng)計(jì)算模型

圖4 基于三維流函數(shù)的球型障礙物避障方法

為了克服傳統(tǒng)流函數(shù)避障曲線存在的“滯點(diǎn)”問題[10]，本文提出了一種新型的橢圓形路徑變形方法。當(dāng)根據(jù)起始位置所選擇的流線剛好處于“滯點(diǎn)”位置時(shí)，將圓形軌跡調(diào)整為橢圓形路徑，從而克服無(wú)法求解避障路徑的問題。

橢圓形路徑變形算法如圖5所示，圓形障礙物的半徑為r，令其等于橢圓形的寬b＝r，橢圓長(zhǎng)a設(shè)為a＝2r，即在距離障礙物球形等于兩倍障礙物半徑時(shí)就啟動(dòng)橢圓路徑變形算法。為了控制方便，將規(guī)劃路徑離散化成[(x0，y0)，(x1，y1)，…，(xn，yn)]，然后進(jìn)行各個(gè)計(jì)算路徑點(diǎn)的速度偏移。路徑點(diǎn)(x0，y0)到路徑點(diǎn)(x1，y1)的連線與X軸正向的夾角θ可以計(jì)算如下:

圖5 橢圓路徑變形方法

假設(shè)沿X正軸的洋流強(qiáng)度為U，移動(dòng)Sink節(jié)點(diǎn)在Y負(fù)軸方向的速度分量為V0，因此在路徑點(diǎn)(x0，y0)只要滿足式(4)所示的速度條件，就可以沿著曲線行進(jìn)到路徑點(diǎn)(x1，y1)，從而避免流函數(shù)的“滯點(diǎn)”問題。

橢圓路徑變形算法的仿真結(jié)果如圖6所示:

圖6 橢圓路徑變形方法仿真結(jié)果

2 仿真結(jié)果

基于流函數(shù)的三維避障算法采用MATLAB軟件進(jìn)行仿真，采用的方法如上文所述。仿真場(chǎng)景設(shè)置如下:三維無(wú)線傳感器網(wǎng)絡(luò)場(chǎng)景中分布多個(gè)不同半徑的球型障礙物，隨機(jī)選擇移動(dòng)Sink節(jié)點(diǎn)的起點(diǎn)位置計(jì)算整體空間的虛擬流場(chǎng)。本文的主要仿真參數(shù)選取如表1所示，單位均為基本單位(Unit)。

表1 仿真參數(shù)

二維平面流函數(shù)的分布情況如圖7所示。隨機(jī)分布如表2所示的多個(gè)障礙物時(shí)，利用流函數(shù)獲得的避障路徑如圖8所示，虛線加粗的流線為根據(jù)起點(diǎn)位置所確定的移動(dòng)Sink節(jié)點(diǎn)的運(yùn)動(dòng)路徑軌跡。立體空間內(nèi)不同Z軸位置的流線分布如圖9所示，可見不同Z軸對(duì)應(yīng)的障礙物在X－Y平面投影不一樣，利用本文提出的Z軸分層方法就可以獲取不同Z坐標(biāo)時(shí)的流線分布，從而獲取三維環(huán)境下的全局流線分布，移動(dòng)Sink節(jié)點(diǎn)可以根據(jù)目前自身所處的Z坐標(biāo)選擇合適的流線路徑進(jìn)行移動(dòng)。

圖7 平面流線仿真結(jié)果

圖9 三維空間內(nèi)不同Z位置的流線分布

表2 多障礙物位置分布

圖8 多障礙物平面避障路徑

下文從三維擴(kuò)展角度分析本文提出的三維流函數(shù)避障算法的性能。

三維傳感器網(wǎng)絡(luò)中存在單個(gè)球體障礙物情況下，移動(dòng)Sink節(jié)點(diǎn)的起點(diǎn)位置不同，得到的流函數(shù)避障路徑如圖10所示，根據(jù)流線分布獲取三維空間不同起點(diǎn)到終點(diǎn)的避障軌跡，從而驗(yàn)證了本文提出的三維流函數(shù)避障方法能夠有效躲避單個(gè)障礙物。

圖10 單障礙物三維避障路徑

當(dāng)三維傳感器網(wǎng)絡(luò)內(nèi)存在隨機(jī)2個(gè)球型障礙物情況下，移動(dòng)Sink節(jié)點(diǎn)的起點(diǎn)位置相同，獲得的流函數(shù)避障路徑如圖11所示。為了表現(xiàn)清晰，圖11展現(xiàn)了多障礙物情況下三維避障路徑的俯視圖。根據(jù)流線分布獲取三維空間不同起點(diǎn)到終點(diǎn)的連續(xù)避障軌跡，從而驗(yàn)證本文提出的三維流函數(shù)避障方法能有效躲避多個(gè)障礙物。

圖11 兩障礙物Sink節(jié)點(diǎn)三維避障路徑

在較大區(qū)域的三維傳感器網(wǎng)絡(luò)中隨機(jī)分布10個(gè)半徑不一的球型障礙物時(shí)，基于流函數(shù)避障的移動(dòng)Sink節(jié)點(diǎn)軌跡如圖12所示。從仿真結(jié)果可以發(fā)現(xiàn)，利用本文所提出的流函數(shù)避障方法，在障礙物較為密集的三維無(wú)線傳感器網(wǎng)絡(luò)可以搜索到優(yōu)化的避障路徑。從獲取的實(shí)際軌跡中也可以發(fā)現(xiàn)，利用流函數(shù)避障方法獲取的移動(dòng)Sink軌跡具有良好的連續(xù)性和平滑性。

圖12 多障礙物Sink節(jié)點(diǎn)三維避障路徑軌跡圖

3 結(jié)語(yǔ)

為了保證移動(dòng)Sink節(jié)點(diǎn)在三維無(wú)線傳感器網(wǎng)絡(luò)中路徑能夠有效躲避多個(gè)隨機(jī)分布的障礙物，本文提出一種利用三維流函數(shù)為移動(dòng)Sink節(jié)點(diǎn)選擇優(yōu)化避障路徑的方法。仿真結(jié)果表明，通過三維流函數(shù)所規(guī)劃出的避障路徑具有良好的連續(xù)性、平滑度和和高效的避障率，可以滿足移動(dòng)Sink節(jié)點(diǎn)在移動(dòng)運(yùn)動(dòng)中躲避障礙物的需求。后期的研究將集中于構(gòu)建更多種形狀障礙物情況下的三維流函數(shù)分布，同時(shí)分析比較均勻流函數(shù)和匯流函數(shù)的避障效果。