基于RRT 算法的障礙物移動模型研究*

湯小芳 楊余旺 郭利強 謝勇盛 趙啟超 李 操

（南京理工大學計算機科學與工程學院 南京 210000）

1 引言

MANET 網絡由若干自由移動的無線節點構成，節點之間的通信無需基礎設備的支持，每個節點不僅是通訊終端，還能作為中繼節點負責轉發數據［1］，其組網方式靈活，網絡拓撲變化頻繁。目前，關于移動自組網的相關研究大多在仿真軟件中進行，而如何根據特定的仿真場景來選取與之相匹配的移動模型成為研究的基礎和關鍵，越是接近現實場景的移動模型才越具有研究和使用價值。基于現實需求，人們在現有的傳統移動模型（例如RDM、RWPM、RWM 等）上進行了各種優化，但是，這些移動模型大多是采用簡單的、隨機的直線運動機制［2］，節點通過隨機函數生成一個隨機的目的位置或運動方向，以特定的速率前進到目的位置［3］。這些移動模型往往設計簡單，更適用于空曠、無障礙的環境。然而，現實中各種障礙物（如樹木、建筑物、人群等）隨處可見，實物很難始終保持直線運動狀態。所以，當存在障礙物時，這些傳統的移動模型已經不再適用。

本文選取隨機路點移動模型（Random Waypoint Model，RWPM）為研究對象，引入快速擴展隨機樹（RRT）算法，在起始點和終點之間快速尋找到一條能避開障礙物的有效路徑。RRT 算法作為一種新穎的隨機節點采樣算法，具有建模快、搜索能力強、易于擴展等優點，將其應用在多障礙環境下的移動模型中，不僅能增強模型的現實性，還能使模型具有更優的概率分布。

2 經典節點移動模型

2.1 隨機路點移動模型

隨機路點移動模型，是由CMU（Carnegie-Mellon University，卡內基—梅隆大學）提出的，它運行機制簡單，適用性強，已經成為研究MANET路由協議的標志性移動模型［4～5］。在NS2 中，RWPM 的實現過程大致如下：首先，每個節點nk在活動區域內隨機生成一個目的位置Pi；然后，它在區間［Vmin，Vmax］中隨機選取一個速度vi，接著，以速度vi向著Pi前進；到達Pi后，ni暫停一段時間Tpause，該過程稱為一個step；Tpause結束以后，nk繼續在活動區域內隨機選取一個新的目的位置Pi+1和速度vi+1并向著Pi+1前進。整個過程周而復始，直到仿真時間結束［6］。

2.2 存在的問題

雖然RWPM 一直被大多數網絡仿真軟件采用，但是如果要仿真障礙物存在的場景時，RWPM卻不是最優的選擇。在現實場景中，障礙物的存在是一種十分普遍的現象，行進路線經常會受到障礙物的干擾［7～8］。在RWPM 模型中，節點在選定的起點和終點間沿直線前進，因此，若想在仿真中規避障礙物，必須保證起點和終點的連線不觸碰任何障礙物，尤其當仿真區域內存在數量較多、規模較大的障礙物時，這會大大限制每一次終點的選擇范圍，這與現實場景相背離。

3 RRTMM模型

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

RRT算法將某一初始點作為根節點，在每一輪的生長中，根據隨機生成的采樣點來逐步擴展葉子節點，從而生成一個隨機擴展樹，直到樹中的某個葉子節點觸及目標點或抵達目標區域，就認為搜索到了一條由起點到終點的有效路徑［11～12］。RRT 算法的描述如圖1所示。

圖1 RRT算法描述

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

4 RRTMM評估

在MANET的仿真實驗中，移動節點（MN）的軌跡通常取決于節點的動態特性，往往表現為在仿真期間節點軌跡覆蓋仿真區域Ω的情況，即Ω內的節點概率分布。本文假設所有的MNs 在二維仿真區域Ω內獨立運動，互不干擾，所有的MNs 都具有相同的移動屬性。因此，可以通過研究某一個MN nj在不同場景下的概率分布，因為它的漸近空間分布與其他的MNs相同［13～15］。

如圖2 所示，假設將Ω平均分成50 × 50 份，用grid（s，t）表示Ω內的任一網格，其中（s，t）∈（1，2，…，50）。假設每個grid（s，t）都裝有計數器，只要當MN經過該處時，其計數器自動加1。用Ni（s，t，k）表示nk當前已經過grid（s，t）的次數，nk從當前位置Pi（x，y）移動到下一個位置Pi+1（x′，y′）所穿過grid（s，t）的次數用Ni+1（s，t，k）來表示。若nk在移動的過程中經過了grid（s，t），則有

圖2 節點nk穿過網格grid（s，t）的情形

如果用α（s，t）來表示節點nk在網格grid（s，t）上的概率，則有

利用上式，可以很方便地計算出所有節點位置在Ω內的不同子區域上的概率分布。

5 仿真實驗結果及分析

5.1 仿真環境設置

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

表1 仿真參數

在場景1 中，設置一個半徑為10m 的圓形障礙物，圓心位于仿真區域Ω內的中心。在場景2中，設置五個同等大小的的圓形障礙物，每個障礙物的半徑也均為10m。

5.2 仿真結果及其分析

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

圖3、4 和圖5、6 分別為RRTMM 模型和RWPM模型在兩種不同障礙物場景下的節點概率分布圖像。

圖3 RRTMM模型在場景1中的節點概率分布圖

圖4 RWPM模型在場景1中的節點概率分布圖

圖5 RRTMM模型在場景2中的節點概率分布圖

圖6 RWPM模型在場景2中的節點概率分布圖

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

從圖5、6 可以看出，當Ω內的障礙物數量增加時，五個障礙區內的概率均為0；從整體看來，RRTMM 仍然體現出較優的概率分布，這體現在障礙物周圍區域的分布比RWPM 更加均勻，曲線過渡也更加平穩。這說明RRTMM 模型能夠適應多障礙物場景。

6 結語

本文針對多障礙物場景，首次提出了一種基于RRT算法的移動模型，該模型能在復雜的障礙物場景中快速搜索到一條可行路徑。通過仿真對比實驗，在同等障礙物約束的條件下，該MM 比傳統的RWPM具有更優的節點概率分布，障礙物周圍區域的分布更加均勻，曲線過渡更加平滑。本MM 更加真實地模擬了現實場景中節點的運動情況，這為后續相關路由協議的仿真提供了可靠的基礎。