基于二次Bezier曲線的無線傳感網避障路徑規劃研究*

張美燕,蔡文郁,周莉萍

(1.浙江水利水電學院 電氣工程系,杭州 310018;2.杭州電子科技大學電子信息學院,杭州 310018)

項目來源:浙江省自然科學基金項目(LY18F030006,LY15F030018,Y18F030025);國家自然科學基金項目(6170060208)

2017-03-27修改日期2017-06-09

基于二次Bezier曲線的無線傳感網避障路徑規劃研究*

張美燕1,蔡文郁2*,周莉萍1

(1.浙江水利水電學院 電氣工程系,杭州 310018;2.杭州電子科技大學電子信息學院,杭州 310018)

用固定Sink節點進行無線傳感網內數據采集的傳統方式會導致熱點區域(hot spot)問題,而采用移動Sink節點進行數據采集可以克服這個問題,從而達到均衡網絡能量分布與延長網絡生命周期的效果。本文針對類車型機器人作為無線傳感網中移動數據匯聚節點的應用場景,提出了一種基于Bezier連續曲線的移動Sink節點避障路徑規劃算法。本文構建了連續分段Bezier曲線為巡航軌跡,采用人工勢場中的斥力場理論實現對多個障礙物的智能躲避,動態調節二次Bezier曲線的內部控制點位置,將障礙物排斥在二次Bezier曲線之外。仿真結果驗證本文提出的算法可以實現移動Sink節點規劃路徑的避障功能,同時Bezier曲線規劃算法簡單,計算量較小。

無線傳感器網絡;Bezier曲線;路徑規劃;障礙避免

通過合理規劃移動Sink節點的運動路徑以實現無線傳感器網絡中多傳感器節點的數據收集是目前的一大研究熱點[1-2]。無線傳感器網絡的避障路徑規劃問題是指:在具有多個凸形障礙物的無線傳感器網絡配置空間(Configuration Space)中,按照設定的路徑優化目標,尋找一條能夠遍歷所有傳感器節點的無碰撞路徑[3]。傳統的避障路徑規劃中往往不考慮路徑的曲率連續性,只考慮了最小時間、最短巡航距離或最少能量消耗等原則,從而找到一條最優解或次優解,因此獲得的路徑是一連串由直線段構成的避障路線。由于非連續運動曲線對于車型機器人的運動方向造成突變,不利于機器人保持平穩的運動速度和能量消耗。為了使車輛型機器人行駛路線平滑,不存在拐點,整體軌跡應由分段連續曲線構成[4]。為滿足以上的幾個特征,Bezier曲線[5]利用了曲線的切矢量性,即Bezier曲線的起點和終點處的切線方向和控制點多邊形的第1條邊及最后一條邊的走向一致,這對于類車型機器人,通過Bezier曲線模型構造的運動軌跡,非常符合類車型機器人的動力學特征。

目前已有一些研究采用了Bezier和B-Spline等樣條曲線對避障路徑規劃問題和連續性路徑規劃問題進行了研究。文獻[6]提出了一種基于多段線方式的避障曲線,然后利用三次樣條曲線簡化實現;文獻[7-8]提出了一種基于有理三次樣條曲線的避障路徑規劃技術;文獻[9]提出了一種利用Bezier曲線描述路徑與改進粒子群優化算法相結合的路徑規劃方法;文獻[10]提出了一種既能使曲線規避所有障礙物,又能使曲線在整體上保持G2連續的低次避障代數樣條曲線;文獻[11]提出通過遺傳算法再結合B樣條曲線規劃出平滑的避障路徑的方法。除此之外,文獻[12-14]研究了存在多個移動機器人情況下如何實現路徑規劃與協作避障的方法。上述研究成果都對機器人移動路徑規劃問題的某些方面做了深入研究,但是有些文獻提出的曲線構造算法過于復雜,需要求解高次方程,有些研究采用了遺傳算法等啟發式優化算法,計算復雜度過高。

除此之外,在實際的無線傳感器網絡中,移動Sink節點進行數據收集往往需要一段時間,因此一般會在采集傳感器節點附近停留,完成數據采集后再按路徑向下一個傳感器節點行駛。但是行駛過程中運動方向突變對減速齒輪的傷害和會減速打滑而帶來的位置誤差,因此只需要在分段曲線內滿足較高連續性即可,這樣可以極大地降低路徑計算復雜度。

本文結合了分段連續二次Bezier曲線和人工勢場算法,實現了一種基于連續二次Bezier曲線的避障路徑規劃方法,從而避免由于障礙物存在導致移動失效的情況,為無線傳感器網絡中移動Sink節點的高效數據采集提供了保證。

1 問題描述

假設無線傳感器網絡區域內隨機分布了S個傳感器節點Ni(i=1,2,…,S),其坐標為(xi,yi)(i=1,2,…,S)和Q個凸形障礙物Oj(j=1,2,…,Q),其坐標為(xj,yj)(j=1,2,…,Q),1個移動Sink機器人沿著預定的軌跡移動,按序采集每個傳感器節點的傳感數據,如圖1所示。本文研究的優化問題如下:假設移動Sink節點沿著預定的路徑對各個傳感器節點進行數據采集,且該路徑具有避開障礙物的功能。優化目標為尋找一條巡航總距離最短的避障閉合曲線來遍歷所有的傳感器節點,該曲線滿足曲率連續的約束條件。數學模型如下所示:

(1)

(2)

(3)

圖1 避障路徑規劃示意圖

Bezier曲線的形狀由通過一組多邊折線(控制點多邊形)的各頂點定義,只有第1個頂點和最后一個頂點在曲線上,其余的頂點用于定義曲線的導數、階次和形狀,第1條邊和最后一條邊則表示了曲線在兩端點處的切線方向。其數學表達式由多項式混合函數推導,如下所示:

(4)

式中:Pi為曲線各個控制點的位置向量,順序連接從P0到Pn的折線被稱為Bezier曲線的控制多邊形,Bn,i(u)為伯恩斯坦基多項式,定義如下:

(5)

由于三次Bezier曲線計算量比二次Bezier更多更復雜,因此本文將只采用二次Bezier曲線作為相鄰傳感器節點之間巡航的路徑曲線。由于式(1)～(3)所提出的最優化模型需要多階曲線來規劃,計算復雜度較大,本文采用的Bezier曲線規劃較為簡單,屬于一種次優解。

由于Bezier曲線的長度計算公式如式(6)所示,無法直接進行積分運算,只能粗略獲取Bezier曲線長度的限值。文獻[15]提出了計算曲線長度的近似式(7),為了簡單起見,本文也以此作為Bezier曲線長度計算的公式,所以對于二次Bezier曲線而言,Bezier距離計算可以等價于首位控制點的歐式距離。

(6)

(7)

2 基于二次Bezier曲線的避障路徑規劃算法

對于一般類車型機器人,滿足C2連續的移動路徑已經足夠滿足巡航速度和動力性需求,關于Bezier曲線的連續性如下定義:

定義1C(u)滿足C2連續的充要條件,C″(u1)=C″(u2) (u1≠u2),即要求曲線二階導數連續。

Bezier曲線的導數定義為:

(8)

定義2f1和f2滿足G0連續的充要條件:f1(1)=f2(0)。即f1的終點與f2的起點重合,但是曲線在連接點處不能保證是光滑連接。

根據Bezier曲線的基本性質,可以推導出以下定理,這些定理可以用于本文的避障路徑規劃算法:

定理1當且僅當障礙物在控制點多邊形內部時,才需要調節內部控制點的位置實現避障。

證明由Bezier曲線的凸包性可知,Bezier曲線全段位于由控制點構成的閉合凸包內,因此,如果當障礙物在控制點多邊形外部時,Bezier曲線不會與障礙物發生碰撞。當且僅當障礙物在控制點多邊形內部時,才需要調節Bezier曲線形態,實現避障。

定理2障礙物是否處于控制點多邊形內部的判斷條件必須滿足:

證明控制點三角形ΔP0P1P2內部的任意一點P(α,β)都可以表示如下:

選取慢性心力衰竭合并2型糖尿病患者74例作為研究對象，將其隨機分為替米沙坦組和雷米普利組，各37例，比較兩組慢性心力衰竭治療效果、空腹血糖水平、胰島素水平及不良反應發生率。入院時，患者均符合美國心臟病協會制定的關于慢性心力衰竭的診斷標準，1999年WHO制定的關于2型糖尿病的診斷標準，空腹血清C肽平均指數為（2.61±0.21）nmol/L，排除免疫系統疾病者、血液系統疾病者、精神疾病者等，其中，替米沙坦組女12例，男25例，平均年齡（36.92±2.14）歲；雷米普利組女11例，男26例，平均年齡（37.16±2.09）歲。兩組患者一般資料比較，差異無統計學意義（P＞0.05）。

P(α,β)=P1+α(P0-P1)+β(P2-P1)
(α+β<1,α>0,β>0)

(9)

當α+β=1時,P(α,β)在P0P2線段上;當α=0時,P(α,β)在P1P2線段上;β=0,P(α,β)在P0P1線段上。由上式可得如下方程組,通過求解方程組可得α和β的值,通過α和β的條件判斷,從而得知障礙物是否在控制點三角形ΔP0P1P2內部。

(10)

(11)

C′(1/2)=P2-P0

(12)

圖2 二次Bezier避障曲線示意

基于人工勢場的方法是機器人運動規劃中一種常用方法,通過對障礙物建立排斥勢場,對目標點建立引力勢場,綜合目標對機器人的吸引力以及障礙物對機器人的排斥力,使機器人繞開障礙物向目標點移動而形成運動規劃。但是人工勢場法也有其內在的局限性,而且也有較為復雜的計算量。本文利用人工勢場方法中的斥力勢場理論對Bezier避障曲線的內部控制點進行調整,但是本文的避障算法只引入了人工勢場中的斥力場來分析障礙物排斥范圍,即規劃曲線路徑要避開障礙物的斥力場區域,其計算公式如下:

(13)

式中:ρi表示物體和障礙物之間的距離,η表示斥力尺度因子,ρ0表示每個障礙物的斥力場半徑。根據上述定義,本文假設只要Sink節點巡航路徑不通過障礙物的斥力場區域,那么就是安全的;如果Sink節點巡航路徑通過了障礙物的斥力場區域,那么就認為與障礙物發生了碰撞。障礙物斥力場強度與斥力尺度因子之間的關系如圖3所示。

圖3 障礙物斥力場強度曲線

定理4二次Bezier曲線f1和f2滿足G1連續的條件是前后兩條Bezier曲線的兩個內部控制點與兩條曲線交點成同一直線,并以兩條曲線交點為中點。

圖4 G1分段連續二次Bezier曲線示意

圖5 仿真場景示意圖

3 仿真結果

本文采用MATLAB R2010a仿真平臺對所提出的算法進行驗證。仿真環境的主要參數為:區域半徑為100×100×100的立方體型三維空間內隨機分布分布著S個傳感器節點和Q個凸形障礙物,斥力尺度因子η=10,障礙物的斥力場半徑ρ0=1,算法參數ν=1/η=0.1,仿真場景示意如圖5所示,其中圖5(a)為傳感器節點和障礙物的空間分布,圖5(b)為障礙物的斥力場分布。仿真采用的AUV能量模型簡化為距離模型,AUV消耗能量與其所巡航的距離成正比。在本文仿真中,傳感器節點的數量從5、10、20變化,即S=5/10/20,凸形障礙物數量從5、10變化,即Q=5/10。如圖6所示,如果采用最小距離旅行商問題的直線方法進行Sink節點的路徑規劃,該曲線與5個障礙物中的2個障礙點發生了碰撞。因此,雖然采用該方法可以獲得最小的總巡航距離,但是最短直線路徑肯定無法避免全部的障礙物。

圖6 無避障功能最短路徑規劃圖

本文采用的二次Bezier曲線避障,只有一個內部控制點需要調節,控制量較少,算法簡單。如果采用現有研究中的更高階數樣條曲線作為規劃路徑,實施避障路徑規劃可能達到更優的路徑長度,但是要滿足路徑的C2連續,需要調整更多的參數,不適合于計算能力較低的移動Sink節點。因此本文仿真過程只比較了不同數量障礙物和待訪問傳感器節點下的避障性能。

由式(7)可知,本文假設Bezier曲線長度可簡單等價于首位控制點的歐式距離。因此本文提出的基于二次Bezier曲線的避障礙路徑規劃算法中,可以借鑒圖6無避障功能最短路徑規劃圖所用的最小總距離旅行商問題的求解方法。首先根據最小總距離旅行商問題求解出移動Sink巡航的傳感器節點次序,以此獲取最小距離路徑規劃的求解。然后利用本文提出的Bezier避障曲線算法,對兩兩傳感器節點之間的滿足C2連續路徑進行計算,最終得到整個無線傳感網移動數據收集總路徑曲線。

在5個傳感器節點和5個障礙物,10個傳感器節點和5個障礙物,20個傳感器節點和10個障礙物情況下,有無避障功能的曲線對比分別如圖7、圖8和圖9所示。圖中粉紅色方塊為障礙物,紅色圓圈為傳感器節點,綠色折線表示控制點多邊形,藍色曲線表示規劃路徑。從圖7可以發現,只有右下方兩個障礙物存在于控制點三角形內,所以Bezier曲線的內部控制點進行了下移,并且縮短了曲線距離,其余部分曲線與無故障避免曲線相同。從圖8可以發現,本文提出的障礙避免規劃路徑已經避開了所有障礙物。從圖9可以發現,當障礙物數量較多時,Bezier曲線避障規劃路徑也能避開障礙物。因此,通過多次仿真曲線可知,應用本文提出的基于二次Bezier曲線的避障路徑規劃算法,可以實現多個障礙物的有效避免。

圖9 Bezier曲線避障路徑(S=20,Q=10)

圖7 Bezier曲線避障路徑(S=5,Q=5)

圖8 Bezier曲線避障路徑(S=10,Q=5)

4 結語

本文綜合考慮了滿足C2連續二次Bezier曲線和人工勢場法中斥力場的分析方法,提出了一種滿足分段連續的二次Bezier避障曲線,保證無線傳感器網絡中的Sink節點對多個凸形障礙的有效避障。仿真結果驗證了本文提出的基于二次Bezier曲線的無線傳感網避障路徑規劃算法以較低的計算復雜度來實現高效率避障。后續工作將考慮無線傳感器網絡中存在有多個Sink節點時如何優化規劃路徑,使得多個Sink節點協同完成數據采集任務,同時避開障礙物以及避免自我碰撞。

[1] 張美燕,蔡文郁,周麗萍. 三維水下移動傳感網多目標有向路徑覆蓋增強研究[J]. 傳感技術學報,2014,27(1):100-106.

[2] 蔣富龍,劉昊. 面向批量數據采集的無線傳感器網絡雙路徑采集協議[J]. 傳感技術學報,2013,9(9):1270-1275.

[3] Latombe J C. Robot Motion Planning. Norwood[M]. Kluwer M A. Academic Publishers,1991.

[4] 胡誠,汪蕓,王輝. 無線可充電傳感器網絡中充電規劃研究進展[J]. 軟件學報,2016,27(1):72-95.

[5] 王家潤,趙南松,華文元,等. 分段連續三次Bezier曲線控制點的構造算法[J]. 計算機工程與應用,2010,46(22):190-193.

[6] Li Z,Meek D S,Walton D J. A Smooth,Obstacle-Avoiding Curve[J]. Computers and Graphics,2006,30(4):581-587.

[7] Meek D S,Ong B H,Walton D J. A Constrained GuidedG1Continuous Spline Curve[J]. Computer-Aided Design,2003,35(6):591-599.

[8] Meek D S,Ong B H,Walton D J. Constrained Interpolation With Rational Cubics[J]. Computer Aided Geometric Design,2003,20(5):253-275.

[9] 朱東偉,毛曉波,陳鐵軍. 基于改進粒子群三次Bezier曲線優化的路徑規劃[J]. 計算機應用研究,2012,29(5):1710-1712.

[10] 陳軍. 連續的低次避障代數樣條曲線[J]. 中國圖象圖形學報,2013,18(6):718-723.

[11] 王憲,盛巍,宋書林,等. 基于遺傳算法和B樣條曲線的平滑避障路徑規劃[J]. 計算機系統應用,2012,21(2):65-71.

[12] Florin S,Vlad-Mihai I,Ionela P. Obstacle Avoidance Via B-Spline Parameterizations of Flat Trajectories[C]//Proceedings of the 24th Mediterranean Conference on Control and Automation,June 21-24,2016,Athens,Greece.

[13] Igor S,Gregor K. Cooperative Collision Avoidance Between Multiple Robots Based on Bezier Curve[C]//Proceedings of the ITI 2007 29th Int. Conf. on Information Technology Interfaces,Cavtat,Croatia,June 25-28,2007:451-456.

[14] 楊冬梅. 基于無線傳感器網絡的多移動機器人避障方法研究[D]. 哈爾濱:哈爾濱工業大學,2013.

[15] Press W H,Teukolsky S A,Vetterling W T,et al. Numerical Recipes in C++[M]. 2nd ed. Cambridge,England:Cambridge University Press,2002.

ObstaclesAvoidanceBasedQuadraticBezierCurvePathPlanningforWirelessSensorNetworks*

ZHANGMeiyan1,CAIWenyu2*,ZHOULiping1

(1.School of Electrical Engineering,Zhejiang University of Water Resources and Electric Power,Hangzhou 310018,China; 2.School of Electronics and Information,Hangzhou Dianzi University,Hangzhou 310018,China)

The traditional sensory data collection method with fixed Sink node will lead to hot spot problem. To overcome this problem,mobile data collection by mobile Sink is proposed so as to balance network energy distribution and prolong network lifecycle. Aiming at the application scenario of the vehicle-like robot as a mobile data aggregation node in wireless sensor networks,this paper proposes a continuous quadratic Bezier curves based obstacle avoidance path planning algorithm for mobile Sink node. Firstly,some segmented continuous Bezier curves are constructed as a whole cruise trajectory. Secondly,the repulsive effect of multiple obstacles is analyzed by artificial potential field method. As a result,the position of internal control points of Bezier curve is dynamically adjusted with repulsive potential field,and adjacent obstacles can be excluded from delta-shaped region by quadratic Bezier curve. Simulation results verify that the proposed method can realize multiple obstacles avoidance in the planning path of mobile Sink node with smaller computational complexity.

wireless sensor networks;bezier curve;path planning;obstacles avoidance

TP393

A

1004-1699(2017)10-1596-06

10.3969/j.issn.1004-1699.2017.10.024

張美燕(1983-),女,副教授,從事無線傳感網絡、新型能源技術、物聯網技術等研究,主持和參與浙江省自然科學基金2項,浙江省公益性行業專項3項,浙江省水利廳科技項目2項,參與浙江省廳級項目多項。近年來發表論文20余篇,被三大索引收錄論文10余篇,申請發明專利和實用新型專利30余項;

蔡文郁(1979-),男,博士,副教授,主要從事物聯網、無線傳感網及嵌入式技術研究。主持和參與國家自然科學基金2項、浙江省自然科學基金3項、浙江省公益性行業專項3項,國家863計劃項目2項、國家海洋局行業專項1項、浙江省重大科技專項1項,橫向課題10余項。近年來發表論文40余篇,被SCI/EI收錄20余篇,申請專利及軟著40余項,授權30余項,dreampp2000@163.com。