Ad hoc網(wǎng)絡(luò)節(jié)點移動模型綜述

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

【關(guān)鍵詞】Ad hoc網(wǎng)絡(luò)節(jié)點移動模型網(wǎng)絡(luò)仿真

在移動Ad hoc網(wǎng)絡(luò)中，節(jié)點的移動將會直接影響網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和鏈路狀態(tài)，而網(wǎng)絡(luò)的拓撲結(jié)構(gòu)是設(shè)計MAC協(xié)議和路由協(xié)議的基礎(chǔ)，基于合理的節(jié)點移動模型設(shè)計的網(wǎng)絡(luò)協(xié)議才是可信的。

現(xiàn)有的Ad hoc網(wǎng)絡(luò)節(jié)點運動模型主要有兩類：一類是實體運動模型（Entity Mobility Model）；另一類是群組運動模型（Group Mobility Model）。實體運動模型描述了單個節(jié)點獨立運動的情況；而組運動模型則描述一組運動相關(guān)的節(jié)點組的運動情況。下面對這兩類模型分別介紹。

一、實體運動模型

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

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

圖1是一個節(jié)點以隨機行走運動模型在1000×1000的區(qū)域內(nèi)運動，根據(jù)節(jié)點的運動數(shù)據(jù)用NS2軟件中的gnuplot工具畫出的運動軌跡。

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

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

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

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

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

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

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

1.4Gauss Markov Model（GMM）

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

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

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

二、群組移動模型

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

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

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

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

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

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

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

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

2.4隊列移動模型[8]

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

2.5隊列移動模型[10]

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

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

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

參考文獻

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

[2]王兵，朱翠濤.機會式網(wǎng)絡(luò)中節(jié)點移動模型的研究與實現(xiàn)[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，F(xiàn)inland，2001

[6]陳培菊，唐倫，陳前斌.車載自組織網(wǎng)絡(luò)中基于運動狀態(tài)的簇路由協(xié)議[J].計算機工程，2013，39（3）；87-92

[7]時銳，楊孝宗.自組網(wǎng)Random Direction移動模型點空間概率分布的研究.計算機研究與發(fā)展. 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]王繼良.狀態(tài)轉(zhuǎn)換和事件觸發(fā)的機會網(wǎng)絡(luò)節(jié)點移動模型[J].計算機工程與應用，2013，776（01）：102-104

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