基于RRT 算法的障礙物移動(dòng)模型研究*

湯小芳 楊余旺 郭利強(qiáng) 謝勇盛 趙啟超 李 操

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210000）

1 引言

MANET 網(wǎng)絡(luò)由若干自由移動(dòng)的無(wú)線節(jié)點(diǎn)構(gòu)成，節(jié)點(diǎn)之間的通信無(wú)需基礎(chǔ)設(shè)備的支持，每個(gè)節(jié)點(diǎn)不僅是通訊終端，還能作為中繼節(jié)點(diǎn)負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)［1］，其組網(wǎng)方式靈活，網(wǎng)絡(luò)拓?fù)渥兓l繁。目前，關(guān)于移動(dòng)自組網(wǎng)的相關(guān)研究大多在仿真軟件中進(jìn)行，而如何根據(jù)特定的仿真場(chǎng)景來(lái)選取與之相匹配的移動(dòng)模型成為研究的基礎(chǔ)和關(guān)鍵，越是接近現(xiàn)實(shí)場(chǎng)景的移動(dòng)模型才越具有研究和使用價(jià)值?；诂F(xiàn)實(shí)需求，人們?cè)诂F(xiàn)有的傳統(tǒng)移動(dòng)模型（例如RDM、RWPM、RWM 等）上進(jìn)行了各種優(yōu)化，但是，這些移動(dòng)模型大多是采用簡(jiǎn)單的、隨機(jī)的直線運(yùn)動(dòng)機(jī)制［2］，節(jié)點(diǎn)通過(guò)隨機(jī)函數(shù)生成一個(gè)隨機(jī)的目的位置或運(yùn)動(dòng)方向，以特定的速率前進(jìn)到目的位置［3］。這些移動(dòng)模型往往設(shè)計(jì)簡(jiǎn)單，更適用于空曠、無(wú)障礙的環(huán)境。然而，現(xiàn)實(shí)中各種障礙物（如樹木、建筑物、人群等）隨處可見，實(shí)物很難始終保持直線運(yùn)動(dòng)狀態(tài)。所以，當(dāng)存在障礙物時(shí)，這些傳統(tǒng)的移動(dòng)模型已經(jīng)不再適用。

本文選取隨機(jī)路點(diǎn)移動(dòng)模型（Random Waypoint Model，RWPM）為研究對(duì)象，引入快速擴(kuò)展隨機(jī)樹（RRT）算法，在起始點(diǎn)和終點(diǎn)之間快速尋找到一條能避開障礙物的有效路徑。RRT 算法作為一種新穎的隨機(jī)節(jié)點(diǎn)采樣算法，具有建?？臁⑺阉髂芰?qiáng)、易于擴(kuò)展等優(yōu)點(diǎn)，將其應(yīng)用在多障礙環(huán)境下的移動(dòng)模型中，不僅能增強(qiáng)模型的現(xiàn)實(shí)性，還能使模型具有更優(yōu)的概率分布。

2 經(jīng)典節(jié)點(diǎn)移動(dòng)模型

2.1 隨機(jī)路點(diǎn)移動(dòng)模型

隨機(jī)路點(diǎn)移動(dòng)模型，是由CMU（Carnegie-Mellon University，卡內(nèi)基—梅隆大學(xué)）提出的，它運(yùn)行機(jī)制簡(jiǎn)單，適用性強(qiáng)，已經(jīng)成為研究MANET路由協(xié)議的標(biāo)志性移動(dòng)模型［4～5］。在NS2 中，RWPM 的實(shí)現(xiàn)過(guò)程大致如下：首先，每個(gè)節(jié)點(diǎn)nk在活動(dòng)區(qū)域內(nèi)隨機(jī)生成一個(gè)目的位置Pi；然后，它在區(qū)間［Vmin，Vmax］中隨機(jī)選取一個(gè)速度vi，接著，以速度vi向著Pi前進(jìn)；到達(dá)Pi后，ni暫停一段時(shí)間Tpause，該過(guò)程稱為一個(gè)step；Tpause結(jié)束以后，nk繼續(xù)在活動(dòng)區(qū)域內(nèi)隨機(jī)選取一個(gè)新的目的位置Pi+1和速度vi+1并向著Pi+1前進(jìn)。整個(gè)過(guò)程周而復(fù)始，直到仿真時(shí)間結(jié)束［6］。

2.2 存在的問題

雖然RWPM 一直被大多數(shù)網(wǎng)絡(luò)仿真軟件采用，但是如果要仿真障礙物存在的場(chǎng)景時(shí)，RWPM卻不是最優(yōu)的選擇。在現(xiàn)實(shí)場(chǎng)景中，障礙物的存在是一種十分普遍的現(xiàn)象，行進(jìn)路線經(jīng)常會(huì)受到障礙物的干擾［7～8］。在RWPM 模型中，節(jié)點(diǎn)在選定的起點(diǎn)和終點(diǎn)間沿直線前進(jìn)，因此，若想在仿真中規(guī)避障礙物，必須保證起點(diǎn)和終點(diǎn)的連線不觸碰任何障礙物，尤其當(dāng)仿真區(qū)域內(nèi)存在數(shù)量較多、規(guī)模較大的障礙物時(shí)，這會(huì)大大限制每一次終點(diǎn)的選擇范圍，這與現(xiàn)實(shí)場(chǎng)景相背離。

3 RRTMM模型

快速搜索隨機(jī)樹算法（Rapidly-exploring Random Tree，RRT）是一種增量式隨機(jī)采樣算法，其優(yōu)點(diǎn)是無(wú)需對(duì)搜索區(qū)域做幾何劃分和空間建模，就能有效解決有代數(shù)約束和微分約束的復(fù)雜空間路徑規(guī)劃問題［9～10］。該算法搜索空間覆蓋率高，搜索范圍廣，盡可能地探索未知區(qū)域，能夠在復(fù)雜的多維空間有效規(guī)劃出一條合理路徑。

RRT算法將某一初始點(diǎn)作為根節(jié)點(diǎn)，在每一輪的生長(zhǎng)中，根據(jù)隨機(jī)生成的采樣點(diǎn)來(lái)逐步擴(kuò)展葉子節(jié)點(diǎn)，從而生成一個(gè)隨機(jī)擴(kuò)展樹，直到樹中的某個(gè)葉子節(jié)點(diǎn)觸及目標(biāo)點(diǎn)或抵達(dá)目標(biāo)區(qū)域，就認(rèn)為搜索到了一條由起點(diǎn)到終點(diǎn)的有效路徑［11～12］。RRT 算法的描述如圖1所示。

圖1 RRT算法描述

在隨機(jī)樹的生成過(guò)程中（1～10 行），假設(shè)初始點(diǎn)為qinit，目標(biāo)點(diǎn)為qgoal，最初的隨機(jī)樹僅由qinit這一個(gè)根節(jié)點(diǎn)構(gòu)成；在規(guī)定的循環(huán)次數(shù)范圍內(nèi)，首先，SetTarget 函數(shù)的作用是在空間內(nèi)隨機(jī)產(chǎn)生一個(gè)采樣點(diǎn)qtarget（3行）；然后，Nearest函數(shù)找到該隨機(jī)樹上與qtarget距離最近的節(jié)點(diǎn)qnearest（4 行）；最后，由Extend函數(shù)在qnearest節(jié)點(diǎn)上沿qtarget方向生成一個(gè)新的葉子節(jié)點(diǎn)qnew。若qnew觸碰到障礙物，則返回NULL，表示本輪葉子節(jié)點(diǎn)擴(kuò)展失敗，進(jìn)行下一輪擴(kuò)展；否則，qnew被添加到隨機(jī)樹中（7～9 行）。循環(huán)執(zhí)行上述步驟，當(dāng)qnearest和qgoal的距離小于某個(gè)閾值，則表示尋找到了一條從初始點(diǎn)為qinit到目標(biāo)點(diǎn)為qgoal的有效路徑，搜索成功（5～6行）。

4 RRTMM評(píng)估

在MANET的仿真實(shí)驗(yàn)中，移動(dòng)節(jié)點(diǎn)（MN）的軌跡通常取決于節(jié)點(diǎn)的動(dòng)態(tài)特性，往往表現(xiàn)為在仿真期間節(jié)點(diǎn)軌跡覆蓋仿真區(qū)域Ω的情況，即Ω內(nèi)的節(jié)點(diǎn)概率分布。本文假設(shè)所有的MNs 在二維仿真區(qū)域Ω內(nèi)獨(dú)立運(yùn)動(dòng)，互不干擾，所有的MNs 都具有相同的移動(dòng)屬性。因此，可以通過(guò)研究某一個(gè)MN nj在不同場(chǎng)景下的概率分布，因?yàn)樗臐u近空間分布與其他的MNs相同［13～15］。

如圖2 所示，假設(shè)將Ω平均分成50 × 50 份，用grid（s，t）表示Ω內(nèi)的任一網(wǎng)格，其中（s，t）∈（1，2，…，50）。假設(shè)每個(gè)grid（s，t）都裝有計(jì)數(shù)器，只要當(dāng)MN經(jīng)過(guò)該處時(shí)，其計(jì)數(shù)器自動(dòng)加1。用Ni（s，t，k）表示nk當(dāng)前已經(jīng)過(guò)grid（s，t）的次數(shù)，nk從當(dāng)前位置Pi（x，y）移動(dòng)到下一個(gè)位置Pi+1（x′，y′）所穿過(guò)grid（s，t）的次數(shù)用Ni+1（s，t，k）來(lái)表示。若nk在移動(dòng)的過(guò)程中經(jīng)過(guò)了grid（s，t），則有

圖2 節(jié)點(diǎn)nk穿過(guò)網(wǎng)格grid（s，t）的情形

如果用α（s，t）來(lái)表示節(jié)點(diǎn)nk在網(wǎng)格grid（s，t）上的概率，則有

利用上式，可以很方便地計(jì)算出所有節(jié)點(diǎn)位置在Ω內(nèi)的不同子區(qū)域上的概率分布。

5 仿真實(shí)驗(yàn)結(jié)果及分析

5.1 仿真環(huán)境設(shè)置

為了驗(yàn)證RRTMM 模型，分別在RWPM 和RRTMM 的仿真區(qū)域Ω內(nèi)設(shè)置兩組相同的障礙物｛Oi|i=1，2，…，n｝，當(dāng)MN隨機(jī)選定的目的位置Pi+1與當(dāng)前位置Pi的幾何連線穿過(guò)Ω內(nèi)的障礙物Oi時(shí)，RWPM放棄當(dāng)前選定的目的位置，重新選擇新的目的位置Pi+1，直到Pi和Pi+1的幾何連線與Oi無(wú)交點(diǎn)。與RWPM 的不同之處在于，當(dāng)MN 運(yùn)動(dòng)到目的位置Pi+1會(huì)觸碰到障礙物時(shí)，RRTMM會(huì)利用RRT算法在目的位置Pi+1和當(dāng)前位置Pi之間快速尋找到一條繞過(guò)障礙物Oi的可行路徑，當(dāng)起、終點(diǎn)連線未觸碰到障礙物，則直線前進(jìn)。本實(shí)驗(yàn)利用Matlab 仿真工具，并設(shè)計(jì)兩種不同的障礙物場(chǎng)景來(lái)進(jìn)行仿真實(shí)驗(yàn)。本實(shí)驗(yàn)所涉及的仿真參數(shù)如表1所示。

表1 仿真參數(shù)

在場(chǎng)景1 中，設(shè)置一個(gè)半徑為10m 的圓形障礙物，圓心位于仿真區(qū)域Ω內(nèi)的中心。在場(chǎng)景2中，設(shè)置五個(gè)同等大小的的圓形障礙物，每個(gè)障礙物的半徑也均為10m。

5.2 仿真結(jié)果及其分析

為了驗(yàn)證RRTMM 模型，仿真過(guò)程和評(píng)估方法如下：首先在除障礙物之外的Ω內(nèi)指定任意起始位置Pi和目的位置Pi+1，當(dāng)Pi和Pi+1之間的幾何連線穿過(guò)障礙物Oi時(shí)，RRTMM 根據(jù)RRT 算法尋找到一條最近的可行路徑；在MN 運(yùn)動(dòng)的過(guò)程中，每當(dāng)MN 的軌跡經(jīng)過(guò)一個(gè)網(wǎng)格grid（s，t）時(shí)，該網(wǎng)格的計(jì)數(shù)器自動(dòng)加1，經(jīng)過(guò)1×104個(gè)step 后，得到所有網(wǎng)格的計(jì)數(shù)器值；最后畫出該MN在Ω內(nèi)的節(jié)點(diǎn)概率分布圖像。

圖3、4 和圖5、6 分別為RRTMM 模型和RWPM模型在兩種不同障礙物場(chǎng)景下的節(jié)點(diǎn)概率分布圖像。

圖3 RRTMM模型在場(chǎng)景1中的節(jié)點(diǎn)概率分布圖

圖4 RWPM模型在場(chǎng)景1中的節(jié)點(diǎn)概率分布圖

圖5 RRTMM模型在場(chǎng)景2中的節(jié)點(diǎn)概率分布圖

圖6 RWPM模型在場(chǎng)景2中的節(jié)點(diǎn)概率分布圖

如圖3 和圖4 所示，在場(chǎng)景1 中，這兩種MM 在概率分布上有一定的相似之處：在障礙物區(qū)Oi中，即圖像中間凹陷下去的部分，MN 出現(xiàn)的概率均為0，并且整體概率分布呈現(xiàn)中心密集四周稀疏的狀態(tài)，這符合已有研究發(fā)現(xiàn)的泊松分布。而不同之處在于：RWPM 的節(jié)點(diǎn)概率分布在中心區(qū)域更加密集，而RRTMM 在障礙物周圍的區(qū)域分布明顯更加均勻，曲線過(guò)渡也較為平滑。這是因?yàn)?，RWPM 模型雖然設(shè)計(jì)簡(jiǎn)單，但其節(jié)點(diǎn)的非均勻分布會(huì)隨著仿真時(shí)間的延長(zhǎng)而更加嚴(yán)重；RRTMM 模型在節(jié)點(diǎn)運(yùn)動(dòng)需要繞過(guò)障礙物的情況下，調(diào)用RRT 算法來(lái)搜尋一條最短的可行路徑，RRT算法本身具有很強(qiáng)的隨機(jī)性，這有助于緩解MN 向中心聚攏的趨勢(shì)，所以MN分布更加均勻。

從圖5、6 可以看出，當(dāng)Ω內(nèi)的障礙物數(shù)量增加時(shí)，五個(gè)障礙區(qū)內(nèi)的概率均為0；從整體看來(lái)，RRTMM 仍然體現(xiàn)出較優(yōu)的概率分布，這體現(xiàn)在障礙物周圍區(qū)域的分布比RWPM 更加均勻，曲線過(guò)渡也更加平穩(wěn)。這說(shuō)明RRTMM 模型能夠適應(yīng)多障礙物場(chǎng)景。

6 結(jié)語(yǔ)

本文針對(duì)多障礙物場(chǎng)景，首次提出了一種基于RRT算法的移動(dòng)模型，該模型能在復(fù)雜的障礙物場(chǎng)景中快速搜索到一條可行路徑。通過(guò)仿真對(duì)比實(shí)驗(yàn)，在同等障礙物約束的條件下，該MM 比傳統(tǒng)的RWPM具有更優(yōu)的節(jié)點(diǎn)概率分布，障礙物周圍區(qū)域的分布更加均勻，曲線過(guò)渡更加平滑。本MM 更加真實(shí)地模擬了現(xiàn)實(shí)場(chǎng)景中節(jié)點(diǎn)的運(yùn)動(dòng)情況，這為后續(xù)相關(guān)路由協(xié)議的仿真提供了可靠的基礎(chǔ)。