基于随机路径点移动模型的MANET容量及延迟分析

第36卷第10期 北京科技大学学报 Vol.36 No.10 2014年10月 Journal of University of Science and Technology Beijing 0ct.2014 基于随机路径点移动模型的MANET容量及延迟分析 王晓菲”，蔡英2四，范艳芳12 1)北京信息科技大学网络文化与数字传播北京市重点实验室，北京100101 2)中国科学院信息工程研究所信息安全国家重点实验室，北京100093 ☒通信作者，E-mail:ycai@bist.cdu.cn 摘要针对已有移动自组网容量、延迟闭解分析在移动模型方面的局限性，提出了新的概率理论框架，将无记忆的独立同 分布移动模型推广至更为真实的满足特定记忆条件的随机路径点移动模型，解决了局部移动方式带来的一系列复杂概率描 述问题.对多副本两跳中继算法进行了研究，得出该中继模式下基于随机路径点移动模型的移动自组网的容量、延迟上限的 精确闭解表达式.仿真实验结果证明了该概率理论框架的有效性及闭解表达式的准确性. 关键词移动自组网：容量：延迟：闭解表达式 分类号TN929.5 Capacity and delay in MANET under a random waypoint mobility model WANG Xiao fei,CAl Ying,FAN Yan-fang) 1)Beijing Key Laboratory of Internet Culture and Digital Dissemination Research,Beijing Information Science Technology University,Beijing 100101, China 2)State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China Corresponding author,E-mail:ycai@bistu.edu.cn ABSTRACT To overcome the limitation of mobility models for the closed-form analysis of capacity and delay in mobile ad hoc networks,the paper introduces a new probability theoretical framework in order to extend a memory-less independent and identically distributed mobility model to a more realistic random waypoint mobility model with certain memory,which solves a series of complex probabilistic problems caused by the way of local move in the random waypoint mobility model.The two-hop relay algorithm with packet redundancy is also investigated and then the accurate closed-form expressions of capacity and delay are obtained.Simulation results demonstrate the efficiency of the proposed probability theoretical framework and prove the accuracy of the closed-form theoretical expressions. KEY WORDS mobile ad hoc networks;capacity:delay:closed-form expression 移动自组网（mobile ad hoc networks,简称 可为网络协议的优化改进提供依据，因而得到学术 MANETs)是由一群兼具终端及路由功能的可移动 界的广泛关注.Grossglauser和Tse于2002年分析 设备通过无线链路形成的无中心、多跳和临时性的 得到单副本传输模式下移动自组网容量⊙(1)，证 自治系统皿，在目前的通讯领域具有极其重要的地 明与包含n节点的静态无线网的容量O(1/n2)相 位和较为广泛的应用. 比，若节点具备移动性，网络容量将从不可扩展变为 移动自组网容量、延迟的分析一方面可用于评 可扩展 估网络协议的传输性能，另一方面通过相关反馈，也 随后众多学者针对不同移动模型开展了大量研 收稿日期：2013-08-28 基金项目：北京市教委科技发展计划面上项目(KM201311232014)：北京信息科技大学网络文化与数字传播北京市重点实验室开放课题 (ICDD201408):中国科学院信息工程研究所信息安全国家重点实验室开放课题(2014-16) DOI:10.13374/j.issn1001-053x.2014.10.018:http://journals.ustb.edu.cn

第 36 卷 第 10 期 2014 年 10 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 10 Oct． 2014 基于随机路径点移动模型的 MANET 容量及延迟分析 王晓菲1) ，蔡 英1，2) ，范艳芳1，2) 1) 北京信息科技大学网络文化与数字传播北京市重点实验室，北京 100101 2) 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093  通信作者，E-mail: ycai@ bistu． edu． cn 摘 要 针对已有移动自组网容量、延迟闭解分析在移动模型方面的局限性，提出了新的概率理论框架，将无记忆的独立同 分布移动模型推广至更为真实的满足特定记忆条件的随机路径点移动模型，解决了局部移动方式带来的一系列复杂概率描 述问题． 对多副本两跳中继算法进行了研究，得出该中继模式下基于随机路径点移动模型的移动自组网的容量、延迟上限的 精确闭解表达式． 仿真实验结果证明了该概率理论框架的有效性及闭解表达式的准确性． 关键词 移动自组网; 容量; 延迟; 闭解表达式 分类号 TN 929. 5 Capacity and delay in MANET under a random waypoint mobility model WANG Xiao-fei1) ，CAI Ying1，2)  ，FAN Yan-fang1，2) 1) Beijing Key Laboratory of Internet Culture and Digital Dissemination Ｒesearch，Beijing Information Science ＆ Technology University，Beijing 100101， China 2) State Key Laboratory of Information Security，Institute of Information Engineering，Chinese Academy of Sciences，Beijing 100093，China  Corresponding author，E-mail: ycai@ bistu． edu． cn ABSTＲACT To overcome the limitation of mobility models for the closed-form analysis of capacity and delay in mobile ad hoc networks，the paper introduces a new probability theoretical framework in order to extend a memory-less independent and identically distributed mobility model to a more realistic random waypoint mobility model with certain memory，which solves a series of complex probabilistic problems caused by the way of local move in the random waypoint mobility model． The two-hop relay algorithm with packet redundancy is also investigated and then the accurate closed-form expressions of capacity and delay are obtained． Simulation results demonstrate the efficiency of the proposed probability theoretical framework and prove the accuracy of the closed-form theoretical expressions． KEY WOＲDS mobile ad hoc networks; capacity; delay; closed-form expression 收稿日期: 2013--08--28 基金项目: 北京市教委科技发展计划面上项目( KM201311232014) ; 北京信息科技大学网络文化与数字传播北京市重点实验室开放课题 ( ICDD201408) ; 中国科学院信息工程研究所信息安全国家重点实验室开放课题( 2014--16) DOI: 10． 13374 /j． issn1001--053x． 2014． 10． 018; http: / /journals． ustb． edu． cn 移 动 自 组 网 ( mobile ad hoc networks，简 称 MANETs) 是由一群兼具终端及路由功能的可移动 设备通过无线链路形成的无中心、多跳和临时性的 自治系统［1］，在目前的通讯领域具有极其重要的地 位和较为广泛的应用． 移动自组网容量、延迟的分析一方面可用于评 估网络协议的传输性能，另一方面通过相关反馈，也 可为网络协议的优化改进提供依据，因而得到学术 界的广泛关注． Grossglauser 和 Tse［2］于2002 年分析 得到单副本传输模式下移动自组网容量 Θ( 1) ，证 明与包含 n 节点的静态无线网的容量 O( 1 / n1 /2 ) 相 比，若节点具备移动性，网络容量将从不可扩展变为 可扩展． 随后众多学者针对不同移动模型开展了大量研

第10期 王晓菲等：基于随机路径点移动模型的MANET容量及延迟分析 ·1401· 究.Sharma等同将整体网络范围划分为n“×n“,研 传输调度机制乃至整体通信效率，主要表现为因移 究发现对于随机方向移动模型(random direction 动方式改变而亟需应对的离散型高维概率分布、对 model,简称RDM),当0≤a<0.5时两跳中继延迟 未来状态的有效预测和通信双方动态关联捕捉等 为0(n),当a=0.5时为0(nlogn).2010年，Li 难题 等0进一步细分该网络模型，设计更为实用的受限 近年来，对局部移动模型的研究主要涵盖以下 随机移动模型，得到多跳中继方案下网络容量与延 几个方面.其一，在特定移动模型和路由协议下具 迟的渐近关系式，研究如何通过调控节点移动方式 体分析节点速度、方向等因素在路由协议的能量消 以获取更大的网络容量.此外，相关工作针对一 耗方面起到的不同作用.其二，为路由节点的真 维与二维独立同分布移动模型(i.i.d mobility mod- 实移动行为建模.例如，Bhandari等考虑以吸引 )回中的快速与慢速移动场景，权衡出给定延迟条 点来表现真实用户的聚集行为，使移动节点沿着预 件下的最佳多播或单播容量.在使用高斯信道模型 先定义的路径接近其目标位置.该移动模型以降低 时，Wang等围绕混合随机漫步移动模型(hybrid 分组投递率为代价，有效缩小了端到端延迟.其三， random walk model))分析出平均网络容量及延迟. 鉴于移动模型在网络仿真中的重要地位，需对其稳 2010年，Huang等网为移动自组网引入通信基站来 定性进行分析.相关研究的指出逐点遍历性定理 提升网络容量，与慢速移动的单节点吞吐量相比，在 是移动模型具有稳定性的充要条件.诸如此类，关 快速移动的通用模型下该吞吐量可以得到提升. 于局部移动模型的研究虽较为丰富，但始终关注于 然而，上述工作均是围绕渐近性结果进行分析， 单个节点在某一模型下的自有属性，较少涉及节点 只能从宏观上描述延迟时间的变化趋势，而确切的 间相互关系的描述或具体中继算法下网络性能的分 延迟描述方法更能引发网络设计者的强烈兴趣，通 析.特别地，针对连续性系统模型，己有工作曾 常借助封闭式求解方法加以解决.Neely和Modiano 多次指出两个节点间的相遇间隔时间（即两次接连 在其2005年的工作回中讨论i.i.d.模型下的两跳 相遇的时间间隔)近似服从于指数分布，但在分析 中继算法，同时以各数据包的平均服务时间和输入 封闭式传输延迟时所考虑的网络场景往往相对简 泊松流的到达率为参数，构造出端到端延迟的封闭 单，一般仅包含一对源节点与目的节点，且只传送单 形式精确解需满足的上限表达式.2011年，Liu 个数据包，实用性受限. 等o为方便灵活操控延迟，设计∫副本两跳中继算 关于常见随机移动模型，分析其各自的移动方 法以支持冗余包传输，并由此在充分讨论源节点和 式和概率特征，可发现最初用来模拟粒子布朗运动 目的节点的平均服务时间的基础上，完整指出了基 的随机漫步移动模型本质上是一种完全不可预测的 于i.i.d.移动模型的网络容量与端到端延迟的封闭 运动方式，且节点的移动速度与其运动方向无关，该 形式上限.闭解表达式往往以函数形式表现各类网 模型的随机性导致其现实应用价值受限.而与之相 络控制参数与容量延迟之间的对应关系，在度量网 对的随机方向移动模型因其节点移动行为的简易性 络性能方面具有显著优势. 及相似性早期常见于理论研究中，后被证明仿真过 在移动自组网闭解容量延迟的相关分析工作 程存在严重的边界聚集现象.直至随机路径点移动 中，由于i.i.d.移动模型是一种全局移动形式，导致 模型被提出，该缺陷才最终得以改进.然而，该模型 目前己有结论在随机路径点移动模型（random 下的节点概率分布m多数依旧围绕孤立节点展开 waypoint mobility model,简称RWPM)、随机漫步 讨论，分析出单个运动节点在某一区间的一维与二 移动模型(random walk model,简称RWM)等局 维空间概率密度函数，有助于提高自组网的仿真精 部移动方式下并不适用. 度，但仍难以描述节点移动行为对网络性能造成的 一般认为，与i.i.d.等全局移动模型相比，局部 影响. 移动模型相对更为准确地描述了人类、物体等的运 因此，本文将重点讨论多方节点在移动过程中 动规律.这是由于前者的无约束大范围移动及均匀 的位置分布关系，充分分析随机路径点移动模型下 概率分布仅存在理论可行性，而后者却如实刻画了 节点记忆条件与相遇行为对网络传输质量的影响形 短期内小范围移动这一节点现实特征.但是，网络 式，并为之建模.具体来说，我们提出一套概率理论 对各节点移动方式的细节（特别是其概率分布）极 框架，研究关键点在于通过计算任意时刻任意节点 其敏感，由此引发了局部移动模型下的一系列复杂 在特定小区范围内的相遇概率，推导出网络各传输 概率描述问题，直接影响移动自组网中继转发机制、 阶段的成功完成概率，结合资源竞争和无线干扰的

第 10 期 王晓菲等: 基于随机路径点移动模型的 MANET 容量及延迟分析 究． Sharma 等［3］将整体网络范围划分为 nα × nα ，研 究发现对于随机方向移动模型 ( random direction model，简称 ＲDM) ，当 0≤α ＜ 0. 5 时两跳中继延迟 为 Θ( n) ，当 α = 0. 5 时为 Θ( nlogn) ． 2010 年，Li 等［4］进一步细分该网络模型，设计更为实用的受限 随机移动模型，得到多跳中继方案下网络容量与延 迟的渐近关系式，研究如何通过调控节点移动方式 以获取更大的网络容量． 此外，相关工作［5］针对一 维与二维独立同分布移动模型( i． i． d mobility mod￾el) ［2］中的快速与慢速移动场景，权衡出给定延迟条 件下的最佳多播或单播容量． 在使用高斯信道模型 时，Wang 等［6］围绕混合随机漫步移动模型( hybrid random walk model) ［7］分析出平均网络容量及延迟． 2010 年，Huang 等［8］为移动自组网引入通信基站来 提升网络容量，与慢速移动的单节点吞吐量相比，在 快速移动的通用模型下该吞吐量可以得到提升． 然而，上述工作均是围绕渐近性结果进行分析， 只能从宏观上描述延迟时间的变化趋势，而确切的 延迟描述方法更能引发网络设计者的强烈兴趣，通 常借助封闭式求解方法加以解决． Neely 和 Modiano 在其 2005 年的工作［9］中讨论 i． i． d． 模型下的两跳 中继算法，同时以各数据包的平均服务时间和输入 泊松流的到达率为参数，构造出端到端延迟的封闭 形式精确解需满足的上限表达式． 2011 年，Liu 等［10］为方便灵活操控延迟，设计 f 副本两跳中继算 法以支持冗余包传输，并由此在充分讨论源节点和 目的节点的平均服务时间的基础上，完整指出了基 于 i． i． d． 移动模型的网络容量与端到端延迟的封闭 形式上限． 闭解表达式往往以函数形式表现各类网 络控制参数与容量延迟之间的对应关系，在度量网 络性能方面具有显著优势． 在移动自组网闭解容量延迟的相关分析工作 中，由于 i． i． d． 移动模型是一种全局移动形式，导致 目前 已 有 结 论 在 随 机 路 径 点 移 动 模 型 ( random waypoint mobility model，简称 ＲWPM) ［11］、随机漫步 移动模型( random walk model，简称 ＲWM) ［12］等局 部移动方式下并不适用． 一般认为，与 i． i． d． 等全局移动模型相比，局部 移动模型相对更为准确地描述了人类、物体等的运 动规律． 这是由于前者的无约束大范围移动及均匀 概率分布仅存在理论可行性，而后者却如实刻画了 短期内小范围移动这一节点现实特征． 但是，网络 对各节点移动方式的细节( 特别是其概率分布) 极 其敏感，由此引发了局部移动模型下的一系列复杂 概率描述问题，直接影响移动自组网中继转发机制、 传输调度机制乃至整体通信效率，主要表现为因移 动方式改变而亟需应对的离散型高维概率分布、对 未来状态的有效预测和通信双方动态关联捕捉等 难题． 近年来，对局部移动模型的研究主要涵盖以下 几个方面． 其一，在特定移动模型和路由协议下具 体分析节点速度、方向等因素在路由协议的能量消 耗方面起到的不同作用［13］． 其二，为路由节点的真 实移动行为建模． 例如，Bhandari 等［14］考虑以吸引 点来表现真实用户的聚集行为，使移动节点沿着预 先定义的路径接近其目标位置． 该移动模型以降低 分组投递率为代价，有效缩小了端到端延迟． 其三， 鉴于移动模型在网络仿真中的重要地位，需对其稳 定性进行分析． 相关研究［15］指出逐点遍历性定理 是移动模型具有稳定性的充要条件． 诸如此类，关 于局部移动模型的研究虽较为丰富，但始终关注于 单个节点在某一模型下的自有属性，较少涉及节点 间相互关系的描述或具体中继算法下网络性能的分 析． 特别地，针对连续性系统模型，已有工作［16］曾 多次指出两个节点间的相遇间隔时间( 即两次接连 相遇的时间间隔) 近似服从于指数分布，但在分析 封闭式传输延迟时所考虑的网络场景往往相对简 单，一般仅包含一对源节点与目的节点，且只传送单 个数据包，实用性受限． 关于常见随机移动模型，分析其各自的移动方 式和概率特征，可发现最初用来模拟粒子布朗运动 的随机漫步移动模型本质上是一种完全不可预测的 运动方式，且节点的移动速度与其运动方向无关，该 模型的随机性导致其现实应用价值受限． 而与之相 对的随机方向移动模型因其节点移动行为的简易性 及相似性早期常见于理论研究中，后被证明仿真过 程存在严重的边界聚集现象． 直至随机路径点移动 模型被提出，该缺陷才最终得以改进． 然而，该模型 下的节点概率分布［17］多数依旧围绕孤立节点展开 讨论，分析出单个运动节点在某一区间的一维与二 维空间概率密度函数，有助于提高自组网的仿真精 度，但仍难以描述节点移动行为对网络性能造成的 影响． 因此，本文将重点讨论多方节点在移动过程中 的位置分布关系，充分分析随机路径点移动模型下 节点记忆条件与相遇行为对网络传输质量的影响形 式，并为之建模． 具体来说，我们提出一套概率理论 框架，研究关键点在于通过计算任意时刻任意节点 在特定小区范围内的相遇概率，推导出网络各传输 阶段的成功完成概率，结合资源竞争和无线干扰的 · 1041 ·

·1402 北京科技大学学报 第36卷 要求，构造马尔科夫链描述源节点与目的节点的服 端，目的节点总是按序请求并按序接收 务过程.此后，将i.i.d.移动模型下的容量、延迟分 1.2干扰模型和调度模型 析方法推广至更为真实的、满足特定记忆条件的随 对于广义的无线网络而言，利用传输范围，构 机路径点移动模型.针对移动自组网中广泛应用的 建通用干扰模型，以防止节点同时传输时的干扰现 多剧本两跳中继算法，分析网络容量、延迟上限的闭 象.假定某一时隙t,节点i试图与节点j通信，而节 解表达式.通过仿真实验，证明性能分析结果的准 点k恰好同时发起传输，则干扰模型指出i与j间无 确性及所提出分析方法的有效性. 干扰通信需满足的两项条件：(1)i与j的欧式距离 1系统模型与中继算法 不大于r;(2)k与j的欧式距离不小于(1+△)r,其 中△为保护因子. 本节依次详述了本文中所使用的网络模型、流 具体到移动自组网中继算法的局部传输场景， 量模型、干扰模型与调度模型.随后对随机路径点 调度模型规定位于某小区中的节点仅能向其一跳传 移动模型与多副本两跳中继算法进行了简要介绍. 输范围中的邻居（位于相同小区或其8个邻接小区 1.1网络模型和流量模型 中的节点)传送包，即可得传输范围如下 n个移动节点分布于一个有限平方单位中，该 r=8/m. 平方单位被视作一个边界互通的球面且被平均划分 为有效避免无线传输资源竞争，可引入传输组 为m×m个小区(cell).其中的每个节点既是源节 概念@，使得位于相同传输组中的节点可以同时传 点，又是某些数据包的目的节点，同时也充当其余 输而不会发生相互干扰.图1中α取值为3，共划分 n-2条数据流的中继节点.网络模型如图1所示，3 出9个传输组，所有标号为1的阴影小区被视作一 个移动节点随机分布于9×9的小区范围内. 个传输组，即任意两个水平且垂直距离均为α整数 倍的小区属于相同传输组，因而α的取值十分 关键0： 9 a=min{「(1+A)√⑧+2，m}. (1) 网络中共有α2个传输组，每个小区属于一个独 立的传输组.本文进一步规定每个传输组（每个小 区)每隔α2个时隙将成为活动的，即得到传输机会 1S. 随后从中随机选择一个节点作为发送者，并依照两 跳中继算法开始进行包传输 1.3随机路径点移动模型 图1网络模型、调度模型示例图 移动模型用来处理节点位置、速度、方向和加速 Fig.I Illustration of the network model and the scheduling model 度的变化.总体上讲，在每个时隙的开始，每个节点 在该网络环境下，本文选用一种基于时隙且快 独立且均匀地按照某种移动模型方案的要求选择一 速移动的网络场景圆，即假设在每个时隙(ime 个目的小区，并于整个时隙保持在该小区中.此外， slot)仅支持进行一跳传输：每个时隙传输的比特数 1.1节中网络模型描述的无边界球面通信空间使得 是固定的且被视作一个包：每个节点在一个时隙期 节点在有限平方单位实现边界互通性移动，因而移 间位于且仅位于唯一的一个小区中.在此，时隙长 动模型复杂的边界效应可被忽略，即移动节点不存 度定义为节点相遇过程中传送单个数据包的时间消 在中心聚集现象 耗，不包含节点移动时间和包的产生时间. 对于基于时隙且快速移动的有限网络环境，随 为单播通信方式设计如下流量模型吗：将从源 机路径点移动模型定义如下：每个节点随机产生 节点向目的节点的通信视作一个流：因网络中的每 一个向量v=(,,),用来代表目的小区相对于当 个移动节点均可作为发送者，且其目的节点随机选 前所处位置的二维位移增量，其中)，和v的取值范 取，故任意时刻网络中最多共有n个不同的流：源于 围为1/m,3/m].换言之，每步移动共覆盖了36 每个节点的通信是一个参数为入（包·时隙-)的泊 个可能的目的小区，即每个小区被选中的概率为1/ 松流.换言之，每个源节点生成包的速率为入，且包 36,如图2所示.同时，在每次移动结束后，各节点 的到达过程独立于其移动过程.对于每个流的目的 的暂停时间均为一个单位时隙

北 京 科 技 大 学 学 报 第 36 卷 要求，构造马尔科夫链描述源节点与目的节点的服 务过程． 此后，将 i． i． d． 移动模型下的容量、延迟分 析方法推广至更为真实的、满足特定记忆条件的随 机路径点移动模型． 针对移动自组网中广泛应用的 多副本两跳中继算法，分析网络容量、延迟上限的闭 解表达式． 通过仿真实验，证明性能分析结果的准 确性及所提出分析方法的有效性． 1 系统模型与中继算法 本节依次详述了本文中所使用的网络模型、流 量模型、干扰模型与调度模型． 随后对随机路径点 移动模型与多副本两跳中继算法进行了简要介绍． 1. 1 网络模型和流量模型 n 个移动节点分布于一个有限平方单位中，该 平方单位被视作一个边界互通的球面且被平均划分 为 m × m 个小区( cell) ． 其中的每个节点既是源节 点，又是某些数据包的目的节点，同时也充当其余 n － 2条数据流的中继节点． 网络模型如图 1 所示，3 个移动节点随机分布于 9 × 9 的小区范围内． 图 1 网络模型、调度模型示例图 Fig． 1 Illustration of the network model and the scheduling model 在该网络环境下，本文选用一种基于时隙且快 速移动 的 网 络 场 景［18］，即假设在每个时隙 ( time slot) 仅支持进行一跳传输; 每个时隙传输的比特数 是固定的且被视作一个包; 每个节点在一个时隙期 间位于且仅位于唯一的一个小区中． 在此，时隙长 度定义为节点相遇过程中传送单个数据包的时间消 耗，不包含节点移动时间和包的产生时间． 为单播通信方式设计如下流量模型［19］: 将从源 节点向目的节点的通信视作一个流; 因网络中的每 个移动节点均可作为发送者，且其目的节点随机选 取，故任意时刻网络中最多共有 n 个不同的流; 源于 每个节点的通信是一个参数为 λ ( 包·时隙 － 1 ) 的泊 松流． 换言之，每个源节点生成包的速率为 λ，且包 的到达过程独立于其移动过程． 对于每个流的目的 端，目的节点总是按序请求并按序接收． 1. 2 干扰模型和调度模型 对于广义的无线网络而言，利用传输范围 r 构 建通用干扰模型，以防止节点同时传输时的干扰现 象． 假定某一时隙 t，节点 i 试图与节点 j 通信，而节 点 k 恰好同时发起传输，则干扰模型指出 i 与 j 间无 干扰通信需满足的两项条件: ( 1) i 与 j 的欧式距离 不大于 r; ( 2) k 与 j 的欧式距离不小于( 1 + Δ) r，其 中 Δ 为保护因子． 具体到移动自组网中继算法的局部传输场景， 调度模型规定位于某小区中的节点仅能向其一跳传 输范围中的邻居( 位于相同小区或其 8 个邻接小区 中的节点) 传送包，即可得传输范围如下 r = 8槡 /m． 为有效避免无线传输资源竞争，可引入传输组 概念［10］，使得位于相同传输组中的节点可以同时传 输而不会发生相互干扰． 图 1 中 α 取值为 3，共划分 出 9 个传输组，所有标号为 1 的阴影小区被视作一 个传输组，即任意两个水平且垂直距离均为 α 整数 倍的小区属于相同传输组，因 而 α 的 取 值 十 分 关键［10］: α = min{ 「( 1 + Δ) 槡8? + 2，m} ． ( 1) 网络中共有 α2 个传输组，每个小区属于一个独 立的传输组． 本文进一步规定每个传输组( 每个小 区) 每隔 α2 个时隙将成为活动的，即得到传输机会． 随后从中随机选择一个节点作为发送者，并依照两 跳中继算法开始进行包传输． 1. 3 随机路径点移动模型 移动模型用来处理节点位置、速度、方向和加速 度的变化． 总体上讲，在每个时隙的开始，每个节点 独立且均匀地按照某种移动模型方案的要求选择一 个目的小区，并于整个时隙保持在该小区中． 此外， 1. 1 节中网络模型描述的无边界球面通信空间使得 节点在有限平方单位实现边界互通性移动，因而移 动模型复杂的边界效应可被忽略，即移动节点不存 在中心聚集现象． 对于基于时隙且快速移动的有限网络环境，随 机路径点移动模型定义如下［11］: 每个节点随机产生 一个向量 v = ( vx，vy ) ，用来代表目的小区相对于当 前所处位置的二维位移增量，其中 vx和 vy的取值范 围为［1 /m，3 /m］． 换言之，每步移动共覆盖了 36 个可能的目的小区，即每个小区被选中的概率为 1 / 36，如图 2 所示． 同时，在每次移动结束后，各节点 的暂停时间均为一个单位时隙． · 2041 ·

第10期 王晓菲等：基于随机路径点移动模型的MANET容量及延迟分析 ·1403· 概率上.本文用S,和D(k≥0)分别代表节点S和 节点D在时隙k的即时位置. Liu针对无记忆i.i.d.移动模型所设计的容量 延迟理论模型无法直接应用于满足特定记忆条件的 随机路径点移动模型.首先定义节点S和节点D间 的记忆条件和相遇事件. 记忆条件在时隙k-1,若D-1属于S-1(k≥ 1)的36个一跳小区（节点S一次移动的可达范 围)，且经过一次移动后，当且仅当下述三类事件至 图2随机路径点移动模型（其中S,代表节点S在时隙k所处位 少发生其一时，则称节点S和节点D在时隙k相遇. 置) 事件X:S和D,属于相同小区； Fig.2 Random waypoint mobility model,where S represents the lo 事件Y:D.属于S的8个邻接小区： cation of Node S at time slot k 事件Z:D属于S的9个一跳小区 相应地，用Px、P,和Pz分别代表上述事件发生 1.4多副本两跳中继算法 的概率，容易得出Pz=P、+P 为简便起见，本文余下内容分别用标记S、D和 注1Cai等的研究m己经证明，在严格基于 R依次代表源节点、目的节点和中继节点. 多副本两跳中继算法0一般规定源自S的每 时隙且快速移动的网络模型下，若各节点初始位置 均匀分布，各时隙移动方式一致且独立，则采用随机 个包在到达D之前将经历最多两跳传输，且每个包 路径点移动模型的节点在任意时隙的位置概率分布 的副本至多被发送给∫个不同的中继节点，简称为 呈现出均匀性.因此，从任意时隙起移动一步的相 2HRf图1描述了一条可能的传输路径，从中可观 遇事件近似等价于从初始状态起移动一步的相遇事 察出S正在R的转发协作下向D传送包 件，可以仅通过对一步移动情景的讨论来描述移动 因此，网络中每时每刻仅存在三类传输形式，即 模型的总体相遇行为.此时通常将位置D视作节 一跳传输范围内的S-D传输、S-R传输和R-D 点S与节点D的目标相遇小区（对于事件X而言， 传输.只要满足传输条件，S-D传输就会立即优先 即假设时隙k节点S和节点D在D,处相遇) 进行，S-R传输和R-D传输将会以等概率的形式 2.2概率理论框架 随机发生.活动小区中的发送者(S或R)及其一跳 现开始推导各类相遇事件概率.在边界互通的 范围内的接收者(R或D)均按照均匀概率分布进行 网络范围内，利用节点目的小区位置分布的平面对 选择 称性，将相遇问题的多种可能情况分类处理，得到各 2概率理论框架 个目标状态下满足随机路径点移动模型记忆条件的 相遇概率特征，并按照一定的比例进行整合计算 本节针对随机路径点移动模型的节点位置分布 在后续定理的证明过程中，将举例分析各类典型 特征，提出一套概率理论框架，对满足特定记忆条件 状态 的三类节点相遇行为进行建模，从而计算出任意时 首先，由于在初始时刻每个节点均随机地从 刻移动节点在指定小区范围内发生相遇的概率。此 m×m个小区中选择初始位置，故有 后利用该结论分析网络传输机会与接收机会的竞争 1 8 9 情况，以及各种传输形式的成功发生概率，可作为后 Px=2,Py=2,Pz=2k=0. m m m 续容量与延迟推导的基础. 对于k≥1的情况，有以下分析结论 2.1移动模型假设 定理1S,和D,属于相同小区的概率为 根据随机路径点移动模型的定义，可知任意两 1 (2) 个节点在时隙t的相对位置与其在时隙1-1的特定 P4mm≥13. 位置有着十分密切的联系，且此类记忆现象可从图 证明：相遇事件的记忆条件如图3所示，此时 2中得到印证.此外，在一跳传输范围内，由于节点 D-1的所有可能位置均属于Sk-1的36个一跳小区， 相遇是发生传输的先决条件，可知不同移动模型对 即仅此36个D-1位置满足节点S的记忆要求.同 网络性能的唯一可能影响表现在每对节点间的相遇 时以S-1为原点构建二维坐标系，由图形对称性可

第 10 期 王晓菲等: 基于随机路径点移动模型的 MANET 容量及延迟分析 图 2 随机路径点移动模型( 其中 Sk代表节点 S 在时隙 k 所处位 置) Fig． 2 Ｒandom waypoint mobility model，where Sk represents the lo￾cation of Node S at time slot k 1. 4 多副本两跳中继算法 为简便起见，本文余下内容分别用标记 S、D 和 Ｒ 依次代表源节点、目的节点和中继节点． 多副本两跳中继算法［10］一般规定源自 S 的每 个包在到达 D 之前将经历最多两跳传输，且每个包 的副本至多被发送给 f 个不同的中继节点，简称为 2HＲ-f． 图 1 描述了一条可能的传输路径，从中可观 察出 S 正在 Ｒ 的转发协作下向 D 传送包． 因此，网络中每时每刻仅存在三类传输形式，即 一跳传输范围内的 S － D 传输、S － Ｒ 传输和 Ｒ － D 传输． 只要满足传输条件，S － D 传输就会立即优先 进行，S － Ｒ 传输和 Ｒ － D 传输将会以等概率的形式 随机发生． 活动小区中的发送者( S 或 Ｒ) 及其一跳 范围内的接收者( Ｒ 或 D) 均按照均匀概率分布进行 选择． 2 概率理论框架 本节针对随机路径点移动模型的节点位置分布 特征，提出一套概率理论框架，对满足特定记忆条件 的三类节点相遇行为进行建模，从而计算出任意时 刻移动节点在指定小区范围内发生相遇的概率． 此 后利用该结论分析网络传输机会与接收机会的竞争 情况，以及各种传输形式的成功发生概率，可作为后 续容量与延迟推导的基础． 2. 1 移动模型假设 根据随机路径点移动模型的定义，可知任意两 个节点在时隙 t 的相对位置与其在时隙 t － 1 的特定 位置有着十分密切的联系，且此类记忆现象可从图 2 中得到印证． 此外，在一跳传输范围内，由于节点 相遇是发生传输的先决条件，可知不同移动模型对 网络性能的唯一可能影响表现在每对节点间的相遇 概率上． 本文用 Sk和 Dk ( k≥0) 分别代表节点 S 和 节点 D 在时隙 k 的即时位置． Liu 针对无记忆 i． i． d． 移动模型所设计的容量 延迟理论模型无法直接应用于满足特定记忆条件的 随机路径点移动模型． 首先定义节点 S 和节点 D 间 的记忆条件和相遇事件． 记忆条件 在时隙 k － 1，若 Dk － 1属于 Sk － 1 ( k≥ 1) 的 36 个一跳小区( 节点 S 一次移动的可达范 围) ，且经过一次移动后，当且仅当下述三类事件至 少发生其一时，则称节点 S 和节点 D 在时隙 k 相遇． 事件 X: Sk和 Dk属于相同小区; 事件 Y: Dk属于 Sk的 8 个邻接小区; 事件 Z: Dk属于 Sk的 9 个一跳小区． 相应地，用 PX、PY和 PZ分别代表上述事件发生 的概率，容易得出 PZ = PX + PY ． 注 1 Cai 等的研究［20］已经证明，在严格基于 时隙且快速移动的网络模型下，若各节点初始位置 均匀分布，各时隙移动方式一致且独立，则采用随机 路径点移动模型的节点在任意时隙的位置概率分布 呈现出均匀性． 因此，从任意时隙起移动一步的相 遇事件近似等价于从初始状态起移动一步的相遇事 件，可以仅通过对一步移动情景的讨论来描述移动 模型的总体相遇行为． 此时通常将位置 Dk视作节 点 S 与节点 D 的目标相遇小区( 对于事件 X 而言， 即假设时隙 k 节点 S 和节点 D 在 Dk处相遇) ． 2. 2 概率理论框架 现开始推导各类相遇事件概率． 在边界互通的 网络范围内，利用节点目的小区位置分布的平面对 称性，将相遇问题的多种可能情况分类处理，得到各 个目标状态下满足随机路径点移动模型记忆条件的 相遇概率特征，并按照一定的比例进行整合计算． 在后续定理的证明过程中，将举例分析各类典型 状态． 首先，由于在初始时刻每个节点均随机地从 m × m个小区中选择初始位置，故有 PX = 1 m2，PY = 8 m2，PZ = 9 m2，k = 0． 对于 k≥1 的情况，有以下分析结论． 定理 1 Sk和 Dk属于相同小区的概率为 PX = 1 4m2，m≥13． ( 2) 证明: 相遇事件的记忆条件如图 3 所示，此时 Dk － 1的所有可能位置均属于 Sk － 1的 36 个一跳小区， 即仅此 36 个 Dk － 1位置满足节点 S 的记忆要求． 同 时以 Sk － 1为原点构建二维坐标系，由图形对称性可 · 3041 ·

·1404 北京科技大学学报 第36卷 将S,的所有可能位置依照等比例划分为四部分，因 移动的状态总数为m2×36,而其中仅有8×1个状 每个一跳小区成为S的概率为1/36，故划分各部分 态满足事件X的要求，故此移动场景相应的发生概 的概率均为936.下文证明以第I象限为例. 率为(8×1)/(m2×36).余下情况同理可证. 由此，综合图3与图4中的场景，有 D D D D D Px=..8×1 +6×1+4×1 m49`（m2x36+m2×36+m2×36+ DDD D D D 12×1,9×1 +6×116×1 DDD. m2×36m2×36m2×36m2×36 12×18×1) m2×36m2×36/ m24=1 4m2 D.DD DDD. 则公式(2)得证 D D D. 定理2D:属于S的8个邻接小区的概率为 DDD D D.D. Py 91 36m2,m≥13. (3) 图3时隙k-1节点S与节点D位置分布 Fig.3 Location distribution of Node S and Node D at time slot -1 证明：以①号小区位置为例，所有可能的位置 D-1及其移动路径（从D-1移动到①号S的8个邻 对于图3中编号为①至⑨的每个S小区位置， 接小区)如图5所示，可知节点D一次移动过程中 所有可能的位置D-1及其移动路径（从D-1移动到 满足事件Y要求的状态总数为 S)分别如图4(a)至图4(i)所示.图中乘式的第一 1×1+5×2+5×3+4×4+ 个数字代表满足记忆条件且使得下一时隙节点D 4×5+3×6+2×8=96. 能够与节点S相遇的Dk-,的个数，而第二个数字代 表经过一次移动后二者实际发生相遇的小区个数 (对于事件X,该项显然为1).图5和附录A中图 A-1同. 若以图4(a)描述的情况为例，可知节点D一次 X b5×2 ◆● ●● ●1 ●● (a8x1 b)6x1 (c4x1 ●● ● (c)5x3 (d4x4 ●● ● 恋● (d)12×1 (e)9xI f)6×1 ●●● ● ●● ●● ● (e)4x5 (f)3×6 (g)2×8 ●● ● ● 秀● 图5D1到D移动过程示例（其中黑点代表可能的D位置， 阴影区域代表与①号$，邻接且D一步可达的小区，箭头举例说 (g)16x1 h)12x1 )8x1 明了相应的移动路径) 图4D-1到D移动过程示例（其中黑点代表可能的D-!位置， Fig.5 Illustration of all possible movement processes from D to 阴影区域代表S,箭头举例说明了相应的移动路径) D,where the blackspots represent possible D,the shaded areas represent adjacent cells of the first S that D can reach by one-hop and Fig.4 Illustration of all possible movement process from D to D the arrows take examples for corresponding moving paths where the blackspots represent possible D,the shaded areas repre- sent S and the arrows take examples for corresponding moving paths 有关余下的8个S:小区位置及相应的状态总

北 京 科 技 大 学 学 报 第 36 卷 将 Sk的所有可能位置依照等比例划分为四部分，因 每个一跳小区成为 Sk的概率为 1 /36，故划分各部分 的概率均为 9 /36． 下文证明以第 I 象限为例． 图 3 时隙 k － 1 节点 S 与节点 D 位置分布 Fig． 3 Location distribution of Node S and Node D at time slot k － 1 图 4 Dk － 1到 Dk移动过程示例( 其中黑点代表可能的 Dk － 1 位置， 阴影区域代表 Sk，箭头举例说明了相应的移动路径) Fig． 4 Illustration of all possible movement process from Dk － 1 to Dk， where the blackspots represent possible Dk － 1，the shaded areas repre￾sent Sk and the arrows take examples for corresponding moving paths 对于图 3 中编号为①至⑨的每个 Sk小区位置， 所有可能的位置 Dk － 1及其移动路径( 从 Dk － 1移动到 Sk ) 分别如图 4( a) 至图 4( i) 所示． 图中乘式的第一 个数字代表满足记忆条件且使得下一时隙节点 D 能够与节点 S 相遇的 Dk － 1的个数，而第二个数字代 表经过一次移动后二者实际发生相遇的小区个数 ( 对于事件 X，该项显然为 1) ． 图 5 和附录 A 中图 A － 1同． 若以图 4( a) 描述的情况为例，可知节点 D 一次 移动的状态总数为 m2 × 36，而其中仅有 8 × 1 个状 态满足事件 X 的要求，故此移动场景相应的发生概 率为( 8 × 1) / ( m2 × 36) ． 余下情况同理可证． 由此，综合图 3 与图 4 中的场景，有 PX = 1 m2 ·1 4 ·1 9 ·( 8 × 1 m2 × 36 + 6 × 1 m2 × 36 + 4 × 1 m2 × 36 + 12 × 1 m2 × 36 + 9 × 1 m2 × 36 + 6 × 1 m2 × 36 + 16 × 1 m2 × 36 + 12 × 1 m2 × 36 + 8 × 1 m2 ) × 36 ·m2 ·4 = 1 4m2 ． 则公式( 2) 得证． 定理 2 Dk属于 Sk的 8 个邻接小区的概率为 PY = 91 36m2，m≥13． ( 3) 证明: 以①号小区位置为例，所有可能的位置 Dk － 1及其移动路径( 从 Dk － 1移动到①号 Sk的 8 个邻 接小区) 如图 5 所示，可知节点 D 一次移动过程中 满足事件 Y 要求的状态总数为 1 × 1 + 5 × 2 + 5 × 3 + 4 × 4 + 4 × 5 + 3 × 6 + 2 × 8 = 96． 图 5 Dk － 1到 Dk移动过程示例( 其中黑点代表可能的 Dk － 1 位置， 阴影区域代表与①号 Sk 邻接且 D 一步可达的小区，箭头举例说 明了相应的移动路径) Fig． 5 Illustration of all possible movement processes from Dk － 1 to Dk，where the blackspots represent possible Dk － 1，the shaded areas represent adjacent cells of the first Sk that D can reach by one-hop and the arrows take examples for corresponding moving paths 有关余下的 8 个 Sk小区位置及相应的状态总 · 4041 ·