劉宴濤，安建平，盧繼華，劉珩

（1.渤海大學(xué) 信息科學(xué)與工程學(xué)院 計(jì)算機(jī)網(wǎng)絡(luò)智能重點(diǎn)實(shí)驗(yàn)室，遼寧 錦州 121013；2.北京理工大學(xué) 電子工程系，北京 100081）

1 引言

移動(dòng)模型是無(wú)線自組織(ad hoc)網(wǎng)絡(luò)仿真研究的重要工具，用以規(guī)劃節(jié)點(diǎn)的移動(dòng)軌跡。根據(jù)移動(dòng)方式的不同，ad hoc網(wǎng)絡(luò)的移動(dòng)模型一般可以分為2大類[1]。如果網(wǎng)絡(luò)中節(jié)點(diǎn)彼此獨(dú)立地選擇自己的運(yùn)動(dòng)參數(shù)，如速度和方向等，則這種模型被稱為個(gè)體移動(dòng)模型；如果節(jié)點(diǎn)以某種合作的、相互依賴的方式移動(dòng)，則稱之為群組移動(dòng)模型。個(gè)體移動(dòng)模型以節(jié)點(diǎn)運(yùn)動(dòng)的隨機(jī)性為特征，這類模型具有遍歷性，即對(duì)某一個(gè)節(jié)點(diǎn)在多個(gè)時(shí)刻的采樣和多個(gè)節(jié)點(diǎn)在同一時(shí)刻的采樣具有相同的分布。

隨機(jī)點(diǎn)模型、隨機(jī)游走模型和隨機(jī)方向模型是3種典型的個(gè)體移動(dòng)模型，其中隨機(jī)點(diǎn)模型應(yīng)用最廣泛。最近研究發(fā)現(xiàn)該模型具有非均勻節(jié)點(diǎn)分布[2,3]和速度衰減[4]等問(wèn)題，這反映出使用該模型的仿真網(wǎng)絡(luò)存在一段時(shí)期的瞬態(tài)過(guò)程，該過(guò)程可能持續(xù)很長(zhǎng)時(shí)間，以至于在有限時(shí)間內(nèi)收集到的結(jié)果不可信。由于準(zhǔn)確的仿真應(yīng)該工作在系統(tǒng)的穩(wěn)態(tài)，所以深刻理解和準(zhǔn)確把握移動(dòng)模型的穩(wěn)態(tài)特征對(duì)于規(guī)避模型的瞬態(tài)過(guò)程，有效設(shè)計(jì)一個(gè)無(wú)線自組網(wǎng)仿真來(lái)說(shuō)是至關(guān)重要的。目前針對(duì)個(gè)體移動(dòng)模型的穩(wěn)態(tài)特征已經(jīng)開展了一些研究，Bettstetter[3]分析了隨機(jī)點(diǎn)模型的節(jié)點(diǎn)分布特征，得到了一維區(qū)間的精確解和二維區(qū)域的近似解。Lin[5]利用更新理論研究了隨機(jī)點(diǎn)模型的節(jié)點(diǎn)速度分布，得到了節(jié)點(diǎn)平穩(wěn)速度分布的概率密度函數(shù)的解析解，從而解釋了隨機(jī)點(diǎn)模型的速度衰減問(wèn)題。Boudec[6]開創(chuàng)性地把 Palm積分引入到ad hoc網(wǎng)絡(luò)移動(dòng)模型的特性分析中，得到了隨機(jī)點(diǎn)模型在平穩(wěn)狀態(tài)下速度分布和節(jié)點(diǎn)分布的精確解。Garetto[7]應(yīng)用偏微分方程描述隨機(jī)游走模型的特征，包括系統(tǒng)的瞬態(tài)行為和收斂速率。此外，還有大量的仿真工作對(duì)模型的穩(wěn)態(tài)特征加以驗(yàn)證。

從隨機(jī)過(guò)程的角度來(lái)看，各種模型的工作過(guò)程構(gòu)成了隨機(jī)點(diǎn)過(guò)程。Boudec[6]通過(guò)對(duì)隨機(jī)點(diǎn)模型的分析證明，只要模型的速度下限Vmin大于0，點(diǎn)過(guò)程就存在平穩(wěn)態(tài)，該結(jié)論對(duì)其他2個(gè)模型也成立。因此，可以把平穩(wěn)點(diǎn)過(guò)程的方法和結(jié)論應(yīng)用到個(gè)體移動(dòng)模型的穩(wěn)態(tài)速度分布和節(jié)點(diǎn)分布的分析中。本文以上述3種模型的平穩(wěn)速度分布和節(jié)點(diǎn)分布為研究對(duì)象，采用理論分析和實(shí)驗(yàn)仿真相結(jié)合的方法加以分析，主要工作包括如下：

1) 應(yīng)用Palm積分分析3種模型的平穩(wěn)速度分布，證明距離型隨機(jī)游走模型、隨機(jī)點(diǎn)模型和隨機(jī)方向模型節(jié)點(diǎn)速度的時(shí)間平均低于事件平均，從而具有速度衰減問(wèn)題，并總結(jié)具有這種問(wèn)題的移動(dòng)模型的本質(zhì)特征；

2) 應(yīng)用幾何概率分析隨機(jī)方向模型的平穩(wěn)節(jié)點(diǎn)分布，得到圓形區(qū)域下節(jié)點(diǎn)分布的閉式解；

3) 應(yīng)用Palm積分分析一維區(qū)間隨機(jī)點(diǎn)模型的平穩(wěn)節(jié)點(diǎn)分布，得到概率密度函數(shù)的閉式解；

4) 應(yīng)用中心極限定理推導(dǎo)隨機(jī)游走模型在無(wú)邊界區(qū)域的端點(diǎn)分布。

后續(xù)內(nèi)容安排如下：第2節(jié)簡(jiǎn)要介紹了3種移動(dòng)模型的工作方式；第3節(jié)簡(jiǎn)介本文采用的2個(gè)主要數(shù)學(xué)工具，即幾何概率與 Palm積分的相關(guān)理論和結(jié)論；第4節(jié)對(duì)3種模型的速度衰減問(wèn)題加以分析；第5節(jié)、第6節(jié)分別針對(duì)隨機(jī)方向模型和隨機(jī)點(diǎn)模型的平穩(wěn)節(jié)點(diǎn)分布加以分析；第7節(jié)給出了無(wú)邊界區(qū)域下隨機(jī)游走模型的端點(diǎn)分布；第8節(jié)是結(jié)束語(yǔ)。

2 Ad hoc網(wǎng)絡(luò)個(gè)體移動(dòng)模型介紹

2.1 隨機(jī)點(diǎn)模型(RWP,random waypoint model)

隨機(jī)點(diǎn)模型采用分段移動(dòng)軌跡，每一段軌跡被稱為一個(gè)運(yùn)動(dòng)周期。仿真開始后，每個(gè)節(jié)點(diǎn)在仿真區(qū)域內(nèi)部隨機(jī)選擇一個(gè)目的點(diǎn)，然后以速度v向目的點(diǎn)移動(dòng)，v均勻產(chǎn)生于區(qū)間[Vmin,Vmax]。到達(dá)目的點(diǎn)后節(jié)點(diǎn)暫停，然后開始下一周期。

2.2 隨機(jī)游走模型(RW,random walk model)

隨機(jī)游走模型也采用分段的移動(dòng)軌跡。但與隨機(jī)點(diǎn)模型不同的是在隨機(jī)游走模型中，節(jié)點(diǎn)從當(dāng)前位置選擇一個(gè)隨機(jī)方向和隨機(jī)速度，移動(dòng)一段距離或一段時(shí)間后暫停，然后變換方向開始下一周期。在有邊界區(qū)域，如果移動(dòng)過(guò)程中節(jié)點(diǎn)撞到了區(qū)域邊界，則它將被反射回區(qū)域內(nèi)部。隨機(jī)游走模型目前還沒有一個(gè)標(biāo)準(zhǔn)的定義，本文把該模型分為2個(gè)子類型：

時(shí)間型(RW1)，在一個(gè)周期中節(jié)點(diǎn)的移動(dòng)時(shí)間服從某種分布。

距離型(RW2)，在一個(gè)周期中節(jié)點(diǎn)的移動(dòng)距離服從某種分布。

2.3 隨機(jī)方向模型(RD,random direction model)

文獻(xiàn)[7～9]也把隨機(jī)游走模型稱為隨機(jī)方向模型。為避免混淆，本文中術(shù)語(yǔ)“隨機(jī)方向”專指Royer模型，該模型由E.M.Royer[10]于2001年提出，曾被文獻(xiàn)[1,2]所引用。該模型的移動(dòng)特點(diǎn)是節(jié)點(diǎn)在區(qū)域內(nèi)部不能停留，即一個(gè)周期只能開始并結(jié)束于區(qū)域的邊界，所以節(jié)點(diǎn)的移動(dòng)軌跡由區(qū)域的弦構(gòu)成。

3 幾何概率與積分

3.1 幾何概率

幾何概率源于2個(gè)世紀(jì)以前的Buffon針問(wèn)題，該理論把概率的思想應(yīng)用到隨機(jī)幾何對(duì)象上，如點(diǎn)、線等[11]。在幾何概率中，平面上的一條直線由其到原點(diǎn)的距離p和其法線與x軸夾角θ所決定，直線方程定義為[11]

幾何概率把dp dθ作為直線集合的密度，把∫Kdp dθ作為區(qū)域K中直線集合的測(cè)度，這是唯一滿足剛體運(yùn)動(dòng)群不變性的密度和測(cè)度定義[11]。幾何概率的一個(gè)結(jié)論是與閉凸集K相交的直線集合的測(cè)度滿足[12]：

其中，M(·)表示集合的測(cè)度，L是K邊界的周長(zhǎng)。

3.2 Palm積分

對(duì)一個(gè)仿真系統(tǒng)的采樣可以基于2種時(shí)鐘：標(biāo)準(zhǔn)時(shí)鐘和事件時(shí)鐘[6,13]。標(biāo)準(zhǔn)時(shí)鐘是均勻流逝的，具有無(wú)限精度的時(shí)鐘；事件時(shí)鐘的推進(jìn)則依靠仿真事件的發(fā)生。根據(jù)參考時(shí)鐘的不同，可以通過(guò)時(shí)間平均和事件平均2種方法來(lái)統(tǒng)計(jì)仿真結(jié)果，這2種結(jié)果往往是不一致的。

事件平均

時(shí)間平均

當(dāng)滿足速度下限非零的條件時(shí)，移動(dòng)模型可以建模為平穩(wěn)點(diǎn)過(guò)程[6]。圖1給出了移動(dòng)模型的點(diǎn)過(guò)程表示，假設(shè)經(jīng)過(guò)一段仿真時(shí)間后，在觀察的起始時(shí)刻（以0表示）仿真系統(tǒng)已經(jīng)處于穩(wěn)態(tài)，并令t0和t1分別是0時(shí)刻之前和之后的狀態(tài)轉(zhuǎn)移時(shí)刻，即t0≤0＜ t1。

圖1 移動(dòng)模型的點(diǎn)過(guò)程

Palm積分[13,14]是分析平穩(wěn)點(diǎn)過(guò)程的重要工具，Palm期望和Palm概率定義為[13]

E0(X)=E(X |在 0時(shí) 刻有事件發(fā)生)P0(X ∈ W)=P(X ∈ W|在 0時(shí) 刻有事件發(fā)生)

用平穩(wěn)更新過(guò)程的術(shù)語(yǔ)來(lái)說(shuō)，Palm分布相當(dāng)于在原點(diǎn)有更新事件發(fā)生的條件概率分布[14]。若X滿足遍歷性，則X的時(shí)間平均趨近于期望E(X)，事件平均0趨近于Palm期望E0(X)[13]。下面不加證明地給出與移動(dòng)模型分析相關(guān)的2個(gè)Palm積分公式[13]：

其中，λ代表平穩(wěn)點(diǎn)過(guò)程的點(diǎn)密度。本文的第4節(jié)和第6節(jié)采用的主要就是Palm積分的分析方法。

4 個(gè)體移動(dòng)模型的速度衰減問(wèn)題

4.1 RW1模型的平穩(wěn)速度分布

下面的分析假設(shè)在觀察的起始時(shí)刻(設(shè)為 0時(shí)刻)，系統(tǒng)已經(jīng)處于穩(wěn)態(tài)。在RW1模型中，節(jié)點(diǎn)每個(gè)周期的移動(dòng)時(shí)間Ti服從某種分布(比如指數(shù)分布)。在每段軌跡的終點(diǎn)，節(jié)點(diǎn)選擇下一次移動(dòng)的速度Vi，Vi服從[Vmin，Vmax]區(qū)間的均勻分布，隨機(jī)變量 Vi和 Ti相互獨(dú)立，則其速度的時(shí)間均值和事件均值分別為

應(yīng)用反演公式可得：

根據(jù)隨機(jī)變量V1和T1的獨(dú)立性，并利用密度公式 λ=1/E0(T1)，可得

可見，RW1模型處于穩(wěn)態(tài)時(shí)，節(jié)點(diǎn)速度的時(shí)間均值和事件均值相等，不存在速度衰減問(wèn)題。

4.2 RW2、RWP和RD模型的平穩(wěn)速度分布

RW2模型要求節(jié)點(diǎn)在每一周期的移動(dòng)距離服從某種分布，下面的分析假設(shè)周期移動(dòng)距離為定值L，其速度的時(shí)間均值和事件均值分別為

由反演公式可得 E(V)=λE0(V1T1)

以c表示隨機(jī)變量V1和T1的協(xié)方差，即

則

仿真設(shè)置：速度范圍是[0，5] m/s，所以速度的事件均值應(yīng)為2.5m/s。第一個(gè)實(shí)驗(yàn)仿真RW1模型的時(shí)間平均速度，移動(dòng)周期固定為10s，每秒采樣一次取時(shí)間平均，如圖2所示。第二個(gè)實(shí)驗(yàn)對(duì)RW2模型的節(jié)點(diǎn)速度在每個(gè)周期端點(diǎn)處采樣，結(jié)果取事件平均，如圖3所示；第三個(gè)實(shí)驗(yàn)對(duì)RW2模型的節(jié)點(diǎn)速度每秒采樣一次，結(jié)果取時(shí)間平均，如圖4所示。結(jié)果表明，RW1模型不存在速度衰減問(wèn)題，而RW2模型則存在。

圖2 RW1模型節(jié)點(diǎn)速度的時(shí)間平均仿真

圖3 RW2模型速度的事件平均仿真

圖4 RW2模型速度的時(shí)間平均仿真

進(jìn)一步，基于Boudec對(duì)RWP模型所做的工作可得RWP，RW2，RD模型平穩(wěn)速度分布的概率密度函數(shù)形如其中E0(L)表示節(jié)點(diǎn)分段軌跡長(zhǎng)度的事件平均。假設(shè)仿真區(qū)域是半徑為 r的圓形區(qū)域，對(duì)于 RWP模型，E0(L)應(yīng)該等于區(qū)域內(nèi)2個(gè)隨機(jī)點(diǎn)之間的平均距離，由幾何概率[11]可知E0(L)＝128r/45π。對(duì)于RD模型，E0(L)應(yīng)該等于區(qū)域邊界上2個(gè)隨機(jī)點(diǎn)之間的平均距離，由數(shù)學(xué)中隨機(jī)弦問(wèn)題[15]可知E0(L)＝4r/π。所以3種模型時(shí)間平均速度分布的概率密度函數(shù)為

可見，在RW2、RWP和RD模型中，節(jié)點(diǎn)平穩(wěn)速度分布的概率密度函數(shù)與v成反比，如圖5所示，這意味著對(duì)某一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，它會(huì)以很高的概率位于較低的速度區(qū)間，而以較低的概率位于較高的速度區(qū)間，這也驗(yàn)證了速度衰減現(xiàn)象。

圖5 RW2模型的時(shí)間平均速度分布和Palm分布

4.3 速度衰減問(wèn)題小結(jié)

比較式(5)、式(6)可見，在RW2、RWP以及RD模型中，每個(gè)運(yùn)動(dòng)周期的移動(dòng)速度Vi和該周期持續(xù)時(shí)間Ti的相關(guān)性造成了速度的事件平均和時(shí)間平均不一致，從而導(dǎo)致速度衰減現(xiàn)象。對(duì)這個(gè)現(xiàn)象的直觀解釋是：在這3種模型中，節(jié)點(diǎn)在每個(gè)周期的移動(dòng)距離服從相同分布，這就造成速度較低的周期持續(xù)時(shí)間較長(zhǎng)，因此在對(duì)速度取時(shí)間平均時(shí)被分配了較大的權(quán)重，從而時(shí)間平均速度會(huì)向低速區(qū)間推移。

5 隨機(jī)方向模型的平穩(wěn)節(jié)點(diǎn)分布

因?yàn)镽D模型的節(jié)點(diǎn)移動(dòng)軌跡由仿真區(qū)域的弦構(gòu)成，所以應(yīng)用概率語(yǔ)言可以把RD模型的平穩(wěn)節(jié)點(diǎn)分布問(wèn)題等價(jià)地描述為：在區(qū)域K全部弦構(gòu)成的集合中，隨機(jī)選擇一根弦G并在其上隨機(jī)選擇一點(diǎn)Q，如圖6所示，則隨機(jī)點(diǎn)Q與RD模型中節(jié)點(diǎn)的瞬時(shí)位置具有相同的概率分布。下面以圓形區(qū)域?yàn)槔龀鼍唧w分析。在圖6中，弦G表示節(jié)點(diǎn)在某個(gè)周期的移動(dòng)軌跡。K是半徑為R的圓形仿真區(qū)域，K1是半徑為r

圖6 隨機(jī)弦G上的隨機(jī)點(diǎn)Q的分布同于節(jié)點(diǎn)的時(shí)間平穩(wěn)分布

的同心圓，Q是G上的一個(gè)隨機(jī)點(diǎn)。根據(jù)圓形區(qū)域各向同性的特點(diǎn)，定義隨機(jī)變量d表示隨機(jī)點(diǎn)Q與圓心的距離。CDF(r)＝Pr(d≤r)是 d的累積分布函數(shù)，它等于Q落在K1內(nèi)部的概率。以l(K)和l(K1)

分別表示G被K和K1所截得弦的長(zhǎng)度，以M(K)表示區(qū)域K弦集的測(cè)度，根據(jù)式(2)，M(K)應(yīng)等于K的周長(zhǎng)，即 2πR。對(duì)于坐標(biāo)為(p,θ)的弦 G，其上隨機(jī)點(diǎn)Q位于K1內(nèi)部的概率為

因此，累積分布函數(shù)CDF(r)為

把(r/R)替換為k，則k相當(dāng)于R歸一化時(shí)的r。把(p/R)替換為ksinφ，則上式可以化為

其中，F(xiàn)(φ，k)和 E(φ，k)分別被稱為橢圓積分的第一和第二類Legendre標(biāo)準(zhǔn)范式[16]。特別地，F(xiàn)(π/2，k)=K(k)，E(π/2，k)=E(k) 又被稱為完全橢圓積分，所以式(8)可以化簡(jiǎn)為

K(k)和E(k)的函數(shù)值可以查表求得[16]。圖7畫出了取 R=1(即仿真區(qū)域?yàn)閱挝粓A)時(shí) CDF(r)和 pdf(r)的曲線。為了比較，同時(shí)給出了均勻分布的累積分布函數(shù)(=r2/R2)和概率密度函數(shù)(=2r/R2)的曲線。圖 8給出了RD模型概率密度函數(shù)的三維視圖。可見，RD模型工作在圓形區(qū)域時(shí)，其平穩(wěn)節(jié)點(diǎn)分布在靠近圓心的區(qū)域與均勻分布接近，但在靠近邊界的區(qū)域明顯高于均勻分布，這表明該模型節(jié)點(diǎn)趨于向邊界發(fā)散。

圖7 RD模型與均勻分布CDF(r)和pdf(r)的比較結(jié)果

圖8 RD模型平穩(wěn)節(jié)點(diǎn)分布的三維視圖

仿真設(shè)置：一個(gè)節(jié)點(diǎn)按照RD模型的移動(dòng)規(guī)則在單位圓內(nèi)移動(dòng)，速度設(shè)為1m/s，每0.1s記錄一次節(jié)點(diǎn)位置，共收集20 000個(gè)位置數(shù)據(jù)，把[0,1]區(qū)間等分為10組，把樣點(diǎn)位置按照與圓心的距離分配到各個(gè)子區(qū)間并統(tǒng)計(jì)每個(gè)子區(qū)間的樣點(diǎn)數(shù)。為了比較，還產(chǎn)生了同樣數(shù)目的均勻分布的節(jié)點(diǎn)位置，比較結(jié)果如圖9所示。仿真結(jié)果與圖7所示的理論結(jié)果相吻合，進(jìn)一步驗(yàn)證了RD模型節(jié)點(diǎn)向邊界發(fā)散的效果。

圖9 RD模型圓形區(qū)域的仿真結(jié)果

6 隨機(jī)點(diǎn)模型的平穩(wěn)節(jié)點(diǎn)分布

6.1 一維區(qū)間隨機(jī)點(diǎn)模型節(jié)點(diǎn)的時(shí)間平穩(wěn)分布

一維情況下，RWP模型工作在區(qū)域[0，a]中。假設(shè)某個(gè)移動(dòng)周期的起點(diǎn)為p，終點(diǎn)為n，則節(jié)點(diǎn)的瞬時(shí)位置x(t)應(yīng)均勻分布于p和n之間，如圖10所示。

圖10 一維區(qū)間RWP模型節(jié)點(diǎn)分布分析

假設(shè)該周期的長(zhǎng)度為T1，速度為V1，對(duì)于x(t)的一個(gè)有界函數(shù)f(x(t))應(yīng)用反演公式可得：

替換t/T1為u，可得：

根據(jù)隨機(jī)變量p、n和V1的相互獨(dú)立性，上式化為

為了求解上述積分，不妨先假設(shè) p＜n，并替換p+u(n-p)為x，則上式變?yōu)?/p>

所以x的概率密度函數(shù)為 3x(a-x)/a3，再考慮到p＞n的情況，可得 pd f(x)=6x(a-x)/a3，取a=1時(shí)計(jì)算結(jié)果如圖11所示。

圖11 一維區(qū)間RWP模型節(jié)點(diǎn)分布的理論結(jié)果

一維區(qū)間仿真設(shè)置：一個(gè)節(jié)點(diǎn)在[0，1]區(qū)間按照RWP模型規(guī)則移動(dòng)，速度均勻分布于[0.01，0.05]，對(duì)其運(yùn)動(dòng)軌跡每秒采樣一次，記錄樣點(diǎn)的位置。把[0，1]區(qū)間等分為10個(gè)子區(qū)間，統(tǒng)計(jì)每個(gè)子區(qū)間出現(xiàn)的樣點(diǎn)的個(gè)數(shù)，該統(tǒng)計(jì)量正比于節(jié)點(diǎn)出現(xiàn)在該子區(qū)間的概率，圖12為100個(gè)運(yùn)動(dòng)周期的仿真結(jié)果。

圖12 一維區(qū)間RWP模型節(jié)點(diǎn)分布的仿真結(jié)果

6.2 二維區(qū)域隨機(jī)點(diǎn)模型節(jié)點(diǎn)的時(shí)間平穩(wěn)分布

Boudec[6]分析了二維區(qū)域 RWP模型的節(jié)點(diǎn)分布特征，給出二維凸區(qū)域中 RWP模型的時(shí)間平穩(wěn)節(jié)點(diǎn)分布概率密度函數(shù)的通用表達(dá)式為

其中，E0(L)表示區(qū)域內(nèi)部2個(gè)隨機(jī)點(diǎn)的平均距離，Area(A)表示區(qū)域A的面積，aM(θ)表示點(diǎn)M沿著方向θ與邊界的距離。應(yīng)用此公式針對(duì)圓形區(qū)域做出具體分析，可得：

其三維視圖如圖13所示。

圖13 二維圓形區(qū)域RWP模型節(jié)點(diǎn)分布的理論值

仿真設(shè)置：在 RWP模型中，令目的點(diǎn)均勻產(chǎn)生于單位圓區(qū)域內(nèi)，速度均勻分布于[0.01，0.05]，對(duì)其運(yùn)動(dòng)軌跡每秒采樣一次，記錄樣點(diǎn)的位置。把[-1，1]2區(qū)間等分為100×100個(gè)小格子，統(tǒng)計(jì)每個(gè)小格子出現(xiàn)的樣點(diǎn)的個(gè)數(shù)，該統(tǒng)計(jì)量正比于節(jié)點(diǎn)出現(xiàn)在各個(gè)小格子的概率。圖14所示為5 000個(gè)運(yùn)動(dòng)周期的仿真結(jié)果。

圖14 二維圓形區(qū)域RWP模型節(jié)點(diǎn)分布的仿真結(jié)果

7 無(wú)邊界區(qū)域RW模型的端點(diǎn)分布

RW模型與RWP和RD模型有所不同: 第一，RW 模型可以工作在無(wú)邊界區(qū)域；第二，RW模型的端點(diǎn)分布不像RWP和RD模型那樣簡(jiǎn)單直觀。Garetto[7]和Boudec[17]對(duì)有邊界區(qū)域RW模型的節(jié)點(diǎn)分布問(wèn)題進(jìn)行了深入研究，證明該模型在有邊界區(qū)域采用反射效應(yīng)或者環(huán)面效應(yīng)時(shí)平穩(wěn)節(jié)點(diǎn)分布為均勻分布。但目前對(duì)于RW模型工作在無(wú)邊界區(qū)域時(shí)的節(jié)點(diǎn)分布問(wèn)題還有待解決。由圖15可見，RW1模型的每個(gè)運(yùn)動(dòng)周期由3個(gè)獨(dú)立的隨機(jī)變量T、V、φ所決定。其端點(diǎn)坐標(biāo)為

圖15 無(wú)邊界區(qū)域的RW1模型

由圖16可見，RW2模型的每個(gè)運(yùn)動(dòng)周期由2個(gè)獨(dú)立的隨機(jī)變量 L、φ所決定。各個(gè)移動(dòng)周期的端點(diǎn)坐標(biāo)為

圖16 無(wú)邊界區(qū)域的RW2模型

φ服從0到2π區(qū)間的均勻分布。由式(10)中隨機(jī)變量T、V、φ的獨(dú)立性和式(11)中隨機(jī)變量L、φ的獨(dú)立性可知，無(wú)論是RW1模型還是RW2模型，Xn（或Yn）都是n個(gè)獨(dú)立同分布的隨機(jī)變量之和，根據(jù)中心極限定理，當(dāng)n很大時(shí)Xn（或Yn）應(yīng)趨于正態(tài)分布。以式(11)為例，假設(shè)每個(gè)周期節(jié)點(diǎn)移動(dòng)固定長(zhǎng)度l，則：

因?yàn)閘cosφj的期望和方差分別為

所以Xn的期望和方差為

因此，Xn的概率密度函數(shù)為

同理，Yn的概率密度函數(shù)為

此外，Hughes[18]應(yīng)用隨機(jī)矢量特征函數(shù)的方法對(duì)的分布加以分析。當(dāng)移動(dòng)次數(shù)在4步以內(nèi)時(shí)，求出了Rn概率密度函數(shù)的精確閉式解，當(dāng)移動(dòng)次數(shù)很大時(shí)，求出了其近似表達(dá)式如下：

由式(12)～式(14)可見，從原點(diǎn)出發(fā)的某個(gè)隨機(jī)游走節(jié)點(diǎn)經(jīng)過(guò)很多步移動(dòng)后，節(jié)點(diǎn)與原點(diǎn)的距離以及節(jié)點(diǎn)位置的橫、縱坐標(biāo)均服從正態(tài)分布。因此，如果仿真網(wǎng)絡(luò)全部節(jié)點(diǎn)的初始分布是均勻分布，那么隨著仿真時(shí)間的推進(jìn)，網(wǎng)絡(luò)將保持均勻分布不變。

8 結(jié)束語(yǔ)

由前面的分析可知，只有令移動(dòng)模型在各個(gè)周期內(nèi)移動(dòng)速度和周期持續(xù)時(shí)間彼此獨(dú)立，才能從根本上解決速度衰減問(wèn)題，在本文研究的4種模型中，只有 RW1模型具有這樣的特征。其次，從平穩(wěn)節(jié)點(diǎn)分布看，RWP模型和RD模型都表現(xiàn)出非均勻分布特征，即處于穩(wěn)態(tài)時(shí)節(jié)點(diǎn)會(huì)以很高的概率出現(xiàn)在某個(gè)子區(qū)域，這種節(jié)點(diǎn)位置的耦合關(guān)系與個(gè)體移動(dòng)模型獨(dú)立性和隨機(jī)性原則是相悖的，必然降低仿真的準(zhǔn)確度。RW模型由于能夠保持節(jié)點(diǎn)的均勻分布，所以優(yōu)于前兩者。綜上所述，時(shí)間型隨機(jī)游走模型的平穩(wěn)速度分布和節(jié)點(diǎn)分布性能要優(yōu)于距離型隨機(jī)游走模型、隨機(jī)點(diǎn)模型和隨機(jī)方向模型，是最理想的個(gè)體移動(dòng)模型。

[1] CAMP T,BOLENG J,DAVIES V.A survey of mobility models for ad-hoc network research[A].Wireless Communication & Mobile Computing(WCMC): Special Issue on Mobile Ad-Hoc Networking:Research,Trends and Applications[C].2002.483-502.

[2] YU D,LI H.Influence of mobility models on node distribution in ad-hoc networks[A].Proceedings of ICCT[C].Piscataway,NJ,USA:IEEE Press,2003.985- 989.

[3] BETTSTETTER C,RESTA G,SANTI P.The node distribution of the random waypoint mobility model for wireless ad-hoc networks[J].IEEE Transactions on Mobile Computing,2003,2(3): 257-269.

[4] YOON J,LIU M,NOBLE B.Random waypoint considered harmful[A].Proc IEEE Infocom[C].Piscataway,NJ,USA: IEEE Press,2003.1312-1321.

[5] LIN G,NOUBIR G,RAJARAMAN R.Mobility models for ad-hoc network simulation[A].Proc IEEE Infocom[C].2004.454-463.

[6] BOUDEC J L.Understanding the Simulation of Mobility Models with Palm Calculus[R].Technical Report,2005.

[7] GARETTO M,LEONARDI E.Analysis of random mobility models with partial differential equations[J].IEEE Trans Mobile Computing,2007,6(11): 1204-1217.

[8] BETTSTETTER C.Mobility modeling in wireless networks: categorization,smooth movement,and border effects[J].ACM Mobile Comp and Comm Rev,2001,5(3): 55-67.

[9] NAIN P,TOWSLEY D,LIU B.Properties of random direction models[A].Proc IEEE INFOCOM[C].2005.1897-1907.

[10] ROYER E M,MELLIAR P M,MOSER L.An analysis of the optimum node density for ad-hoc mobile networks[A].Proceeding of the IEEE International Conference on Communications(ICC)[C].Piscataway,NJ,USA: IEEE Press,2001.857-861.

[11] SANTALO L A.Integral Geometry and Geometric Probability[M].Cambridge: Cambridge University Press,2004.

[12] SOLOMAN H.Geometric Probability[M].Philadelphia: Society for Industrial and Applied Mathematics,1978.

[13] BOUDEC J L.Performance Evaluation of Computer and Communication Systems[EB/OL].http://perfeval.epfl.ch,2009.

[14] 鄧永錄,梁之舜.隨機(jī)點(diǎn)過(guò)程及其應(yīng)用[M].北京: 科學(xué)出版社,1992.DENG Y L,LIANG Z S.Random Point Process and Its Applications[M].Beijing: Science Press,1992.

[15] WEISSTEIN E W.Circle line picking[EB/OL].http://mathworld.wolfram.com/CircleLinePicking.html,2009.

[16] JAHNKE E,EMDE F.Tables of Functions with Formulae and Curves[M].New York: Dover Publications,1945.

[17] BOUDEC J L,VOJNOVIC M.The random trip model: stability,stationary regime,and perfect simulation[J].IEEE/ACM Trans on Networking,2006,14(6): 1153-1166

[18] HUGHES B.Random Walks and Random Environments[M].Oxford:Clarendon Press,1995.