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

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

1 引言

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

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

2 經典節(jié)點移動模型

2.1 隨機路點移動模型

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

2.2 存在的問題

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

3 RRTMM模型

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

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

圖1 RRT算法描述

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

4 RRTMM評估

在MANET的仿真實驗中，移動節(jié)點（MN）的軌跡通常取決于節(jié)點的動態(tài)特性，往往表現(xiàn)為在仿真期間節(jié)點軌跡覆蓋仿真區(qū)域Ω的情況，即Ω內的節(jié)點概率分布。本文假設所有的MNs 在二維仿真區(qū)域Ω內獨立運動，互不干擾，所有的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 節(jié)點nk穿過網格grid（s，t）的情形

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

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

5 仿真實驗結果及分析

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

為了驗證RRTMM 模型，分別在RWPM 和RRTMM 的仿真區(qū)域Ω內設置兩組相同的障礙物｛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 的圓形障礙物，圓心位于仿真區(qū)域Ω內的中心。在場景2中，設置五個同等大小的的圓形障礙物，每個障礙物的半徑也均為10m。

5.2 仿真結果及其分析

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

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

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

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

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

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

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

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

6 結語

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