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

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

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

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

一、實(shí)體運(yùn)動(dòng)模型

1.1隨機(jī)行走移動(dòng)模型（Random walk）[1]

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

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

1.2隨機(jī)路點(diǎn)移動(dòng)模型（Random WayPoint Mobility Model）

文獻(xiàn)[1]中描述此移動(dòng)模型為：節(jié)點(diǎn)首先在當(dāng)前位置停留一段隨機(jī)時(shí)間Tp∈[Tmin，Tmax]，然后在場(chǎng)景內(nèi)隨機(jī)選取一個(gè)位置作為目標(biāo)位置，并以隨機(jī)選定的速度v∈[Vmin，Vmax ]向該目標(biāo)位置移動(dòng)。節(jié)點(diǎn)到達(dá)目的地后再隨機(jī)停留一段時(shí)間Tp，然后重復(fù)上述過(guò)程。

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

1.3隨機(jī)方向移動(dòng)模型（Random Direction Model）

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

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

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

1.4Gauss Markov Model（GMM）

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

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

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

二、群組移動(dòng)模型

在實(shí)際生活中很多運(yùn)動(dòng)形式只能用群組移動(dòng)模型來(lái)描述，如行進(jìn)的士兵隊(duì)列，圍捕罪犯等。常用的群組移動(dòng)模型有：

2.1追逐移動(dòng)模型（Pursue Mobility Model）[9]

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

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

2.2參考點(diǎn)組移動(dòng)模型（Reference Point Group mobility Vector model，RPGM）[6]

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

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

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

2.4隊(duì)列移動(dòng)模型[8]

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

2.5隊(duì)列移動(dòng)模型[10]

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

如圖8所示，在初始時(shí)給定一個(gè)運(yùn)動(dòng)的參考坐標(biāo)線，每個(gè)移動(dòng)節(jié)點(diǎn)置于坐標(biāo)線上的參考點(diǎn)（圖中的小圓點(diǎn)）附近，節(jié)點(diǎn)允許在參考點(diǎn)周圍以一種隨機(jī)的方式運(yùn)動(dòng)。每個(gè)節(jié)點(diǎn)新的參考點(diǎn)由下式給出：

式中old_refrence_point是移動(dòng)節(jié)點(diǎn)以前的參考位置，advance_vector是預(yù)先定義的步進(jìn)量，它用來(lái)描述參考坐標(biāo)線的運(yùn)動(dòng)量。

參考文獻(xiàn)

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

[2]王兵，朱翠濤.機(jī)會(huì)式網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)模型的研究與實(shí)現(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ò)中基于運(yùn)動(dòng)狀態(tài)的簇路由協(xié)議[J].計(jì)算機(jī)工程，2013，39（3）；87-92

[7]時(shí)銳，楊孝宗.自組網(wǎng)Random Direction移動(dòng)模型點(diǎn)空間概率分布的研究.計(jì)算機(jī)研究與發(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ā)的機(jī)會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)模型[J].計(jì)算機(jī)工程與應(yīng)用，2013，776（01）：102-104

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