Ad hoc網絡節點移動模型綜述

【摘要】在移動Ad hoc網絡仿真研究中，節點移動模型直接決定了網絡的拓撲結構，進而影響網絡性能的評估，基于合理的節點移動模型的仿真結果才真實可靠。介紹了目前Ad hoc網絡仿真研究中所應用的移動節點模型。

【關鍵詞】Ad hoc網絡節點移動模型網絡仿真

在移動Ad hoc網絡中，節點的移動將會直接影響網絡的拓撲結構和鏈路狀態，而網絡的拓撲結構是設計MAC協議和路由協議的基礎，基于合理的節點移動模型設計的網絡協議才是可信的。

現有的Ad hoc網絡節點運動模型主要有兩類：一類是實體運動模型（Entity Mobility Model）；另一類是群組運動模型（Group Mobility Model）。實體運動模型描述了單個節點獨立運動的情況；而組運動模型則描述一組運動相關的節點組的運動情況。下面對這兩類模型分別介紹。

一、實體運動模型

1.1隨機行走移動模型（Random walk）[1]

這種模型反映的是一種完全不可預測、沒有規律的一種極限運動模式，它是一種類布朗運動。在這種模型中，節點從當前位置移動到下一個位置時，在[0，2π]的范圍內隨機選擇一個方向，在[Vmin，Vmax]內隨機的選擇一個速度，然后運動一個固定的時間或者一段固定的距離。在運動到仿真區域的邊界時，節點發生反彈，以和入射角大小相同的角度繼續運動。隨機走動模型是一種無記憶的運動方式，因為節點當前的移動速度和方向完全獨立于先前的移動速度和方向，因而會使網絡中的節點產生不現實的運動方式，如突然停止或急轉，不符合實際應用的情況，不利于網絡仿真。目前這種模型已經被淘汰。

圖1是一個節點以隨機行走運動模型在1000×1000的區域內運動，根據節點的運動數據用NS2軟件中的gnuplot工具畫出的運動軌跡。

1.2隨機路點移動模型（Random WayPoint Mobility Model）

文獻[1]中描述此移動模型為：節點首先在當前位置停留一段隨機時間Tp∈[Tmin，Tmax]，然后在場景內隨機選取一個位置作為目標位置，并以隨機選定的速度v∈[Vmin，Vmax ]向該目標位置移動。節點到達目的地后再隨機停留一段時間Tp，然后重復上述過程。

RWM移動模型比較真實的反映了人類的一種基本的運動規律，具有很好的現實性，且簡單易于實現，所以成為事實上基準移動模型，得到了最廣泛的應用。然而，RWP存在兩個問題：（1）平均速度逐漸降低。文獻[2]中通過仿真發現，若采用RWM模型，則節點平均速度隨著仿真的運行逐漸降低。（2）節點穩態分布不均勻。文獻[3]通過仿真發現，當Tp為0時，10m×10m方形場景內100個節點按RWM模型移動得到的穩態分布具有非均勻特性。當平均停留時間Tp變長時，節點的穩態分布趨于均勻。文獻[11]給出了一種防止節點速度衰減的方法。

1.3隨機方向移動模型（Random Direction Model）

RDM模型是一種在自組網的仿真中經常普遍采用的移動模型，在文獻[4]中為解決鄰節點個數波動而首次提出。該節點移動模型的定義是在運動區域內隨機找一個點S作為起始點，從（0，2π）隨機均勻選擇一個方向，按照預先定義的速度，一直走到該運動區域的邊界點D，然后保持靜Tpause時間，再以D作為新的起始點S重新選擇一個方向Y一直走到該運動區域新的邊界點D，然后保持靜止Tpause時間，如此反復。

在文獻[5]中，對Random Direction節點移動模型進行了深入研究，給出了Random Direction節點移動模型在一維和二維的空間概率分布函數的公式，認為運動節點空間的分布在二維坐標下出現中心概率密度小，邊緣概率密度大，且具有圓對稱的非均勻分布等特點。文獻[7]中推導出了RandomDirection節點移動模型在三維空間概率密度函數。

但是隨著研究的深入，其存在著固有的缺點就是：邊界現象。即由于節點都是碰到邊界才一變向，這樣會出現節點在邊界處聚集，其與現實中的一些情況不是很符合，尤其是并不是每個節點都碰到邊界才會變向，而是在運動中每個時刻有可能變向。近年來主要是考慮對這種模型的改進。

1.4Gauss Markov Model（GMM）

由于隨機路點移動模型和隨機方向移動模型等模型沒有記憶性，會導致急停、急轉彎等不合理的運動情形，高斯馬爾可夫模型（Gauss Markov Model）[6]中節點新的速度和新的位置都與此前的速度和位置有關，所以彌補了這方面不足。但是這種模型的實現比較復雜，所以應用不是很廣泛。

該模型通過一個可調的參數來適應隨機性程度不同的情況。起始時，每個移動節點被賦予一個速度和方向，每經過一個固定的時間間隙n，每個節點的速度和方向就會發生更新。節點在第n個時間間隙的速度和方向取決于第n-1個時間間隙的速度和方向和隨機變量，具體由下式給出：

其中，sn和dn是移動節點在第n個時間間隙新的速度和方向，α（0≤α≤1）是控制隨機程度的變量，s和d是速度和方向的平均值，sxn-1和dxn-1是服從高斯分布的隨機變量。當α=0時為完全隨機運動，α=1時為勻速直線運動。

二、群組移動模型

在實際生活中很多運動形式只能用群組移動模型來描述，如行進的士兵隊列，圍捕罪犯等。常用的群組移動模型有：

2.1追逐移動模型（Pursue Mobility Model）[9]

這種模型用于模擬現實生活中多個移動個體共同追逐目標節點的運動模式，例如警察追逐在逃的罪犯，士兵追擊敵人等。在追逐移動模型中，每組節點中都有一個特殊節點，它是組中其它節點追逐的目標。該目標節點按照RWP模型移動。在該模型中，節點位置的更新按照以下方程進行：

式中acceleration（target-old_position）是被追逐節點的運動信息，random_vector是每個節點的漂移量。如圖3所示，在該模型中，追逐節點的運動受到了限制。圖中，黑色節點是被追逐的節點，白色節點是追逐節點。

2.2參考點組移動模型（Reference Point Group mobility Vector model，RPGM）[6]

這種模型如圖4所示，每一個群都有一個群首作為參考點（RP，Reference Point），群內其它節點的運動以群首的運動為參考，在群首運動的速度和方向基礎上，疊加一個隨機的偏移量，作為自己的速度和方向，即

式中，0≤SDR、ADR≤1，SDR、ADR分別是速度、角度偏移率。它們用來控制群組成員的速度和方向與群首節點的偏移程度。max_speed和max_angle是群組成員能夠獲得的最大的偏移量。

如圖6所示，與隊列移動模型相比，在這種模型中所有的節點有一個共同的參考點，而在隊列移動模型中每個節點有一個參考點。因此，在游牧部落移動模型中節點運動所受的約束較小。

2.4隊列移動模型[8]

隊列移動模型在一些搜捕工作中是很有用的。節點的運動情況如圖7所示。在初始時給定一個運動的參考坐標線，每個移動的節點置于坐標線上的參考點（圖中的小圓點）附近，節點允許在參考點周圍以一種隨機的方式運動。該模式的具體應用情況：如一排士兵在搜索敵人的時候，往往是沿著一個方向進行的，但士兵在行進的過程中，又可以有一定的位置偏移。在地震或火災發生現場的救護工作也有類似的運動情況。

2.5隊列移動模型[10]

隊列移動模型（Column Mobility Model）描述的是一隊移動節點在一條線周圍運動的情形。如一排士兵在搜索敵人時，往往是沿著一個方向進行的，但士兵在行進的過程中，又可以有一定的位置偏移；在地震或火災發生現場的救護工作也有類似的運動情況。

如圖8所示，在初始時給定一個運動的參考坐標線，每個移動節點置于坐標線上的參考點（圖中的小圓點）附近，節點允許在參考點周圍以一種隨機的方式運動。每個節點新的參考點由下式給出：

式中old_refrence_point是移動節點以前的參考位置，advance_vector是預先定義的步進量，它用來描述參考坐標線的運動量。

參考文獻

[1] Vanessa Ann Davies. Evaluating Mobility Models Within an Ad Hoc Networks[z]. The Faculty and the Colorado School，2000.

[2]王兵，朱翠濤.機會式網絡中節點移動模型的研究與實現[J].光通信研究，2011，164（2）：57-59

[3] Yoon J K，LIU Min2yan，Noble B. Random waypoint considered harmful [C]. Proceedings of the 22nd Annual Joint Conference of theIEEE Computer and Communications Societies （ INFOCOM’03） ， SanFransisco，California，USA，Apr. 2003：1312-1321

[4] Blough D M，Resta G，Santi P. A statistical analysis of the long-run node spatial distribution in mobile ad hoc networks[J] . Wireless Net2works，Special Issue on‘Modeling Analysis of Mobile Networks，Sep. 2004，10（1）：543-554

[5] Elizabeth M Royer，P Michael Melliar-Smith，Louise E Moser.An analysis of the optimum node density for ad hoc mobile networks. IEEE Int’l Conf on Communications，Helsinki，Finland，2001

[6]陳培菊，唐倫，陳前斌.車載自組織網絡中基于運動狀態的簇路由協議[J].計算機工程，2013，39（3）；87-92

[7]時銳，楊孝宗.自組網Random Direction移動模型點空間概率分布的研究.計算機研究與發展. 2004，41（7）：1166-1173.

[8] Liang B，Haas Z J. Predictive distance2based mobility management for PCS networks[C]. Proceedings of IEEE Information Communication Conference（INFOCOM’99），New York，USA，Mar. 1999：1377-1384

[9] Camp T，Boleng J，Davies V. A survey of mobility models for ad hoc network research [J]. Wireless Communications and Mobile Computing（WCMC），Special Issue on Mobile Ad Hoc Networking：Research，Trends，and Applications，2002，2（4）：483-502

[10]王繼良.狀態轉換和事件觸發的機會網絡節點移動模型[J].計算機工程與應用，2013，776（01）：102-104

[11]孫國棟，廖明宏.一種避免Random Waypoint模型速度衰減的方法.小型微型計算機系統. 2006，27（4）