无线自组网个体移动模型分析

刘宴涛，安建平，卢继华，刘珩

（1.渤海大学 信息科学与工程学院 计算机网络智能重点实验室，辽宁 锦州 121013；2.北京理工大学 电子工程系，北京 100081）

1 引言

移动模型是无线自组织(ad hoc)网络仿真研究的重要工具，用以规划节点的移动轨迹。根据移动方式的不同，ad hoc网络的移动模型一般可以分为2大类[1]。如果网络中节点彼此独立地选择自己的运动参数，如速度和方向等，则这种模型被称为个体移动模型；如果节点以某种合作的、相互依赖的方式移动，则称之为群组移动模型。个体移动模型以节点运动的随机性为特征，这类模型具有遍历性，即对某一个节点在多个时刻的采样和多个节点在同一时刻的采样具有相同的分布。

随机点模型、随机游走模型和随机方向模型是3种典型的个体移动模型，其中随机点模型应用最广泛。最近研究发现该模型具有非均匀节点分布[2,3]和速度衰减[4]等问题，这反映出使用该模型的仿真网络存在一段时期的瞬态过程，该过程可能持续很长时间，以至于在有限时间内收集到的结果不可信。由于准确的仿真应该工作在系统的稳态，所以深刻理解和准确把握移动模型的稳态特征对于规避模型的瞬态过程，有效设计一个无线自组网仿真来说是至关重要的。目前针对个体移动模型的稳态特征已经开展了一些研究，Bettstetter[3]分析了随机点模型的节点分布特征，得到了一维区间的精确解和二维区域的近似解。Lin[5]利用更新理论研究了随机点模型的节点速度分布，得到了节点平稳速度分布的概率密度函数的解析解，从而解释了随机点模型的速度衰减问题。Boudec[6]开创性地把 Palm积分引入到ad hoc网络移动模型的特性分析中，得到了随机点模型在平稳状态下速度分布和节点分布的精确解。Garetto[7]应用偏微分方程描述随机游走模型的特征，包括系统的瞬态行为和收敛速率。此外，还有大量的仿真工作对模型的稳态特征加以验证。

从随机过程的角度来看，各种模型的工作过程构成了随机点过程。Boudec[6]通过对随机点模型的分析证明，只要模型的速度下限Vmin大于0，点过程就存在平稳态，该结论对其他2个模型也成立。因此，可以把平稳点过程的方法和结论应用到个体移动模型的稳态速度分布和节点分布的分析中。本文以上述3种模型的平稳速度分布和节点分布为研究对象，采用理论分析和实验仿真相结合的方法加以分析，主要工作包括如下：

1) 应用Palm积分分析3种模型的平稳速度分布，证明距离型随机游走模型、随机点模型和随机方向模型节点速度的时间平均低于事件平均，从而具有速度衰减问题，并总结具有这种问题的移动模型的本质特征；

2) 应用几何概率分析随机方向模型的平稳节点分布，得到圆形区域下节点分布的闭式解；

3) 应用Palm积分分析一维区间随机点模型的平稳节点分布，得到概率密度函数的闭式解；

4) 应用中心极限定理推导随机游走模型在无边界区域的端点分布。

后续内容安排如下：第2节简要介绍了3种移动模型的工作方式；第3节简介本文采用的2个主要数学工具，即几何概率与 Palm积分的相关理论和结论；第4节对3种模型的速度衰减问题加以分析；第5节、第6节分别针对随机方向模型和随机点模型的平稳节点分布加以分析；第7节给出了无边界区域下随机游走模型的端点分布；第8节是结束语。

2 Ad hoc网络个体移动模型介绍

2.1 随机点模型(RWP,random waypoint model)

随机点模型采用分段移动轨迹，每一段轨迹被称为一个运动周期。仿真开始后，每个节点在仿真区域内部随机选择一个目的点，然后以速度v向目的点移动，v均匀产生于区间[Vmin,Vmax]。到达目的点后节点暂停，然后开始下一周期。

2.2 随机游走模型(RW,random walk model)

随机游走模型也采用分段的移动轨迹。但与随机点模型不同的是在随机游走模型中，节点从当前位置选择一个随机方向和随机速度，移动一段距离或一段时间后暂停，然后变换方向开始下一周期。在有边界区域，如果移动过程中节点撞到了区域边界，则它将被反射回区域内部。随机游走模型目前还没有一个标准的定义，本文把该模型分为2个子类型：

时间型(RW1)，在一个周期中节点的移动时间服从某种分布。

距离型(RW2)，在一个周期中节点的移动距离服从某种分布。

2.3 随机方向模型(RD,random direction model)

文献[7～9]也把随机游走模型称为随机方向模型。为避免混淆，本文中术语“随机方向”专指Royer模型，该模型由E.M.Royer[10]于2001年提出，曾被文献[1,2]所引用。该模型的移动特点是节点在区域内部不能停留，即一个周期只能开始并结束于区域的边界，所以节点的移动轨迹由区域的弦构成。

3 几何概率与积分

3.1 几何概率

几何概率源于2个世纪以前的Buffon针问题，该理论把概率的思想应用到随机几何对象上，如点、线等[11]。在几何概率中，平面上的一条直线由其到原点的距离p和其法线与x轴夹角θ所决定，直线方程定义为[11]

几何概率把dp dθ作为直线集合的密度，把∫Kdp dθ作为区域K中直线集合的测度，这是唯一满足刚体运动群不变性的密度和测度定义[11]。几何概率的一个结论是与闭凸集K相交的直线集合的测度满足[12]：

其中，M(·)表示集合的测度，L是K边界的周长。

3.2 Palm积分

对一个仿真系统的采样可以基于2种时钟：标准时钟和事件时钟[6,13]。标准时钟是均匀流逝的，具有无限精度的时钟；事件时钟的推进则依靠仿真事件的发生。根据参考时钟的不同，可以通过时间平均和事件平均2种方法来统计仿真结果，这2种结果往往是不一致的。

事件平均

时间平均

当满足速度下限非零的条件时，移动模型可以建模为平稳点过程[6]。图1给出了移动模型的点过程表示，假设经过一段仿真时间后，在观察的起始时刻（以0表示）仿真系统已经处于稳态，并令t0和t1分别是0时刻之前和之后的状态转移时刻，即t0≤0＜ t1。

图1 移动模型的点过程

Palm积分[13,14]是分析平稳点过程的重要工具，Palm期望和Palm概率定义为[13]

E0(X)=E(X |在 0时 刻有事件发生)P0(X ∈ W)=P(X ∈ W|在 0时 刻有事件发生)

用平稳更新过程的术语来说，Palm分布相当于在原点有更新事件发生的条件概率分布[14]。若X满足遍历性，则X的时间平均趋近于期望E(X)，事件平均0趋近于Palm期望E0(X)[13]。下面不加证明地给出与移动模型分析相关的2个Palm积分公式[13]：

其中，λ代表平稳点过程的点密度。本文的第4节和第6节采用的主要就是Palm积分的分析方法。

4 个体移动模型的速度衰减问题

4.1 RW1模型的平稳速度分布

下面的分析假设在观察的起始时刻(设为 0时刻)，系统已经处于稳态。在RW1模型中，节点每个周期的移动时间Ti服从某种分布(比如指数分布)。在每段轨迹的终点，节点选择下一次移动的速度Vi，Vi服从[Vmin，Vmax]区间的均匀分布，随机变量 Vi和 Ti相互独立，则其速度的时间均值和事件均值分别为

应用反演公式可得：

根据随机变量V1和T1的独立性，并利用密度公式 λ=1/E0(T1)，可得

可见，RW1模型处于稳态时，节点速度的时间均值和事件均值相等，不存在速度衰减问题。

4.2 RW2、RWP和RD模型的平稳速度分布

RW2模型要求节点在每一周期的移动距离服从某种分布，下面的分析假设周期移动距离为定值L，其速度的时间均值和事件均值分别为

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

以c表示随机变量V1和T1的协方差，即

则

仿真设置：速度范围是[0，5] m/s，所以速度的事件均值应为2.5m/s。第一个实验仿真RW1模型的时间平均速度，移动周期固定为10s，每秒采样一次取时间平均，如图2所示。第二个实验对RW2模型的节点速度在每个周期端点处采样，结果取事件平均，如图3所示；第三个实验对RW2模型的节点速度每秒采样一次，结果取时间平均，如图4所示。结果表明，RW1模型不存在速度衰减问题，而RW2模型则存在。

图2 RW1模型节点速度的时间平均仿真

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

图4 RW2模型速度的时间平均仿真

进一步，基于Boudec对RWP模型所做的工作可得RWP，RW2，RD模型平稳速度分布的概率密度函数形如其中E0(L)表示节点分段轨迹长度的事件平均。假设仿真区域是半径为 r的圆形区域，对于 RWP模型，E0(L)应该等于区域内2个随机点之间的平均距离，由几何概率[11]可知E0(L)＝128r/45π。对于RD模型，E0(L)应该等于区域边界上2个随机点之间的平均距离，由数学中随机弦问题[15]可知E0(L)＝4r/π。所以3种模型时间平均速度分布的概率密度函数为

可见，在RW2、RWP和RD模型中，节点平稳速度分布的概率密度函数与v成反比，如图5所示，这意味着对某一个节点来说，它会以很高的概率位于较低的速度区间，而以较低的概率位于较高的速度区间，这也验证了速度衰减现象。

图5 RW2模型的时间平均速度分布和Palm分布

4.3 速度衰减问题小结

比较式(5)、式(6)可见，在RW2、RWP以及RD模型中，每个运动周期的移动速度Vi和该周期持续时间Ti的相关性造成了速度的事件平均和时间平均不一致，从而导致速度衰减现象。对这个现象的直观解释是：在这3种模型中，节点在每个周期的移动距离服从相同分布，这就造成速度较低的周期持续时间较长，因此在对速度取时间平均时被分配了较大的权重，从而时间平均速度会向低速区间推移。

5 随机方向模型的平稳节点分布

因为RD模型的节点移动轨迹由仿真区域的弦构成，所以应用概率语言可以把RD模型的平稳节点分布问题等价地描述为：在区域K全部弦构成的集合中，随机选择一根弦G并在其上随机选择一点Q，如图6所示，则随机点Q与RD模型中节点的瞬时位置具有相同的概率分布。下面以圆形区域为例做出具体分析。在图6中，弦G表示节点在某个周期的移动轨迹。K是半径为R的圆形仿真区域，K1是半径为r

图6 随机弦G上的随机点Q的分布同于节点的时间平稳分布

的同心圆，Q是G上的一个随机点。根据圆形区域各向同性的特点，定义随机变量d表示随机点Q与圆心的距离。CDF(r)＝Pr(d≤r)是 d的累积分布函数，它等于Q落在K1内部的概率。以l(K)和l(K1)

分别表示G被K和K1所截得弦的长度，以M(K)表示区域K弦集的测度，根据式(2)，M(K)应等于K的周长，即 2πR。对于坐标为(p,θ)的弦 G，其上随机点Q位于K1内部的概率为

因此，累积分布函数CDF(r)为

把(r/R)替换为k，则k相当于R归一化时的r。把(p/R)替换为ksinφ，则上式可以化为

其中，F(φ，k)和 E(φ，k)分别被称为椭圆积分的第一和第二类Legendre标准范式[16]。特别地，F(π/2，k)=K(k)，E(π/2，k)=E(k) 又被称为完全椭圆积分，所以式(8)可以化简为

K(k)和E(k)的函数值可以查表求得[16]。图7画出了取 R=1(即仿真区域为单位圆)时 CDF(r)和 pdf(r)的曲线。为了比较，同时给出了均匀分布的累积分布函数(=r2/R2)和概率密度函数(=2r/R2)的曲线。图 8给出了RD模型概率密度函数的三维视图。可见，RD模型工作在圆形区域时，其平稳节点分布在靠近圆心的区域与均匀分布接近，但在靠近边界的区域明显高于均匀分布，这表明该模型节点趋于向边界发散。

图7 RD模型与均匀分布CDF(r)和pdf(r)的比较结果

图8 RD模型平稳节点分布的三维视图

仿真设置：一个节点按照RD模型的移动规则在单位圆内移动，速度设为1m/s，每0.1s记录一次节点位置，共收集20 000个位置数据，把[0,1]区间等分为10组，把样点位置按照与圆心的距离分配到各个子区间并统计每个子区间的样点数。为了比较，还产生了同样数目的均匀分布的节点位置，比较结果如图9所示。仿真结果与图7所示的理论结果相吻合，进一步验证了RD模型节点向边界发散的效果。

图9 RD模型圆形区域的仿真结果

6 随机点模型的平稳节点分布

6.1 一维区间随机点模型节点的时间平稳分布

一维情况下，RWP模型工作在区域[0，a]中。假设某个移动周期的起点为p，终点为n，则节点的瞬时位置x(t)应均匀分布于p和n之间，如图10所示。

图10 一维区间RWP模型节点分布分析

假设该周期的长度为T1，速度为V1，对于x(t)的一个有界函数f(x(t))应用反演公式可得：

替换t/T1为u，可得：

根据随机变量p、n和V1的相互独立性，上式化为

为了求解上述积分，不妨先假设 p＜n，并替换p+u(n-p)为x，则上式变为

所以x的概率密度函数为 3x(a-x)/a3，再考虑到p＞n的情况，可得 pd f(x)=6x(a-x)/a3，取a=1时计算结果如图11所示。

图11 一维区间RWP模型节点分布的理论结果

一维区间仿真设置：一个节点在[0，1]区间按照RWP模型规则移动，速度均匀分布于[0.01，0.05]，对其运动轨迹每秒采样一次，记录样点的位置。把[0，1]区间等分为10个子区间，统计每个子区间出现的样点的个数，该统计量正比于节点出现在该子区间的概率，图12为100个运动周期的仿真结果。

图12 一维区间RWP模型节点分布的仿真结果

6.2 二维区域随机点模型节点的时间平稳分布

Boudec[6]分析了二维区域 RWP模型的节点分布特征，给出二维凸区域中 RWP模型的时间平稳节点分布概率密度函数的通用表达式为

其中，E0(L)表示区域内部2个随机点的平均距离，Area(A)表示区域A的面积，aM(θ)表示点M沿着方向θ与边界的距离。应用此公式针对圆形区域做出具体分析，可得：

其三维视图如图13所示。

图13 二维圆形区域RWP模型节点分布的理论值

仿真设置：在 RWP模型中，令目的点均匀产生于单位圆区域内，速度均匀分布于[0.01，0.05]，对其运动轨迹每秒采样一次，记录样点的位置。把[-1，1]2区间等分为100×100个小格子，统计每个小格子出现的样点的个数，该统计量正比于节点出现在各个小格子的概率。图14所示为5 000个运动周期的仿真结果。

图14 二维圆形区域RWP模型节点分布的仿真结果

7 无边界区域RW模型的端点分布

RW模型与RWP和RD模型有所不同: 第一，RW 模型可以工作在无边界区域；第二，RW模型的端点分布不像RWP和RD模型那样简单直观。Garetto[7]和Boudec[17]对有边界区域RW模型的节点分布问题进行了深入研究，证明该模型在有边界区域采用反射效应或者环面效应时平稳节点分布为均匀分布。但目前对于RW模型工作在无边界区域时的节点分布问题还有待解决。由图15可见，RW1模型的每个运动周期由3个独立的随机变量T、V、φ所决定。其端点坐标为

图15 无边界区域的RW1模型

由图16可见，RW2模型的每个运动周期由2个独立的随机变量 L、φ所决定。各个移动周期的端点坐标为

图16 无边界区域的RW2模型

φ服从0到2π区间的均匀分布。由式(10)中随机变量T、V、φ的独立性和式(11)中随机变量L、φ的独立性可知，无论是RW1模型还是RW2模型，Xn（或Yn）都是n个独立同分布的随机变量之和，根据中心极限定理，当n很大时Xn（或Yn）应趋于正态分布。以式(11)为例，假设每个周期节点移动固定长度l，则：

因为lcosφj的期望和方差分别为

所以Xn的期望和方差为

因此，Xn的概率密度函数为

同理，Yn的概率密度函数为

此外，Hughes[18]应用随机矢量特征函数的方法对的分布加以分析。当移动次数在4步以内时，求出了Rn概率密度函数的精确闭式解，当移动次数很大时，求出了其近似表达式如下：

由式(12)～式(14)可见，从原点出发的某个随机游走节点经过很多步移动后，节点与原点的距离以及节点位置的横、纵坐标均服从正态分布。因此，如果仿真网络全部节点的初始分布是均匀分布，那么随着仿真时间的推进，网络将保持均匀分布不变。

8 结束语

由前面的分析可知，只有令移动模型在各个周期内移动速度和周期持续时间彼此独立，才能从根本上解决速度衰减问题，在本文研究的4种模型中，只有 RW1模型具有这样的特征。其次，从平稳节点分布看，RWP模型和RD模型都表现出非均匀分布特征，即处于稳态时节点会以很高的概率出现在某个子区域，这种节点位置的耦合关系与个体移动模型独立性和随机性原则是相悖的，必然降低仿真的准确度。RW模型由于能够保持节点的均匀分布，所以优于前两者。综上所述，时间型随机游走模型的平稳速度分布和节点分布性能要优于距离型随机游走模型、随机点模型和随机方向模型，是最理想的个体移动模型。

[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] 邓永录,梁之舜.随机点过程及其应用[M].北京: 科学出版社,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.