基于随机路径点移动模型的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 ·

第10期 王晓菲等：基于随机路径点移动模型的MANET容量及延迟分析 ·1405· 数，详见表1.表中个乘式的第一个因子代表满足记 CCPP,(1-P2)-2-51-eia-263e -25/9 忆条件且使得下一时隙节点D能够与节点S相遇 288 的D-的个数，而第二个因子代表经过一次移动后 引理1与引理2的结果充分证明，随着网络规 二者实际发生相遇的小区个数，表4同. 模m(m2=n)无限增长并逐渐趋于无穷，基于随机 由此，依据图3的记忆条件，结合图5与表1中 路径点移动模型的移动自组网发生传输机会竞争或 所描述的场景，仿照定理1的证明过程，可得 接收机会竞争的概率无法收敛于0，故通过研究此 P,=31L.96 66 60 类资源竞争问题，可以提升网络性能分析结果的准 m49·(m2×36+mx36+m2x36 确性. 105+72+66 153 其次，对于一个给定时隙下的数据流，分别用 m2×36m2×36m2×36m2×36 PP2和P3依次代表其发生一次包传输的概率、发生 105,96 一次S-D传输的概率以及发生一次S-R传输或 m×36m2×36 小m4=器 R-D传输的概率，易知P1=P2+P3,具体如下. 则公式(3)得证 注2由Pz=Px+Py,可知D属于S的9个一 对于P2所描述的事件，当且仅当下述三个子事 跳小区的概率为 件同时发生：(1)S位于活动小区中；(2)D位于S 所在小区或S的8个邻接小区；(3)S被选作发 9125 P2-1三+36m=9m3 (4) 送者 使用相似方法对此结论进行验证，详见附录A 综上所述，有 表1不同S,位置下满足事件Y要求的状态总数 Table 1 Total number of the state that meets the requirement of Event Y under different S 含c1-)p= S编号 满足事件Y要求的状态总数 总计 ② 1×1+6×2+4×3+5×4+3×5+1×6 66 -1-1- ③ 1×1+4×2+3×3+3×4+2×5+2×6+1×8 60 ④ 1×1+7×2+8×3+6×4+6×5+2×6 105 0- 4m2-1)-191n+9-36m21 4m2/ 9n(n-1)J ⑤ 1×1+8×2+9×3+7×4 72 对于P3所描述的事件，当且仅当下述四个子事 1×1+6×2+4X3+5×4+3×5+1×6 66 ⊙ 件同时发生：(1)S位于活动小区中：(2)S一跳传 1×1+6×2+8×3+5×4+8×5+4×6+4×8 153 输范围内至少有一个除S外的节点：(3)S被选作 ⑧ 1×1+7×2+8×3+6×4+6×5+2×6 105 发送者：(4)D不在S的一跳传输范围内 ⑨1×1+5×2+5×3+4×4+4×5+3×6+2×8 96 2.3基础概率性质 =1-P以[宫c-p)+ 传输或接收机会竞争作为影响传输质量的重要 因素，在移动自组网性能分析工作中极易被忽视. 言c片u-月…x- 首先利用上述相遇事件的有关结论，为活动小区定 义下述两类机会竞争概率。 引理1传输机会竞争概率被定义为活动小区 中至少含有两个节点的概率，即 {--）]- 1-(1-Px)"-CPx(1-Px)-1= 1-1-(层-)-子 类似地，对于一个给定时隙下的数据流，假设当 引理2接收机会竞争概率被定义为除发送节 前网络中己有包P的j个副本，则以P)代表节点 点外，活动小区的一跳传输范围内至少含有两个其 D在下一时隙成功接收到包P的概率，其中1≤j≤ 他节点的概率，即 f+1:以P,(》代表节点S在下一时隙成功发出包P 1-(1-Px)"-∑CPx(1-Pz)-k- 的一个新副本的概率，其中1≤≤f根据充要条件， 可推出o

第 10 期 王晓菲等: 基于随机路径点移动模型的 MANET 容量及延迟分析 数，详见表 1． 表中个乘式的第一个因子代表满足记 忆条件且使得下一时隙节点 D 能够与节点 S 相遇 的 Dk － 1的个数，而第二个因子代表经过一次移动后 二者实际发生相遇的小区个数，表 4 同． 由此，依据图 3 的记忆条件，结合图 5 与表 1 中 所描述的场景，仿照定理 1 的证明过程，可得 PY = 1 m2 ·1 4 ·1 9 ·( 96 m2 × 36 + 66 m2 × 36 + 60 m2 × 36 + 105 m2 × 36 + 72 m2 × 36 + 66 m2 × 36 + 153 m2 × 36 + 105 m2 × 36 + 96 m2 ) × 36 ·m2 ·4 = 91 36m2 ． 则公式( 3) 得证． 注 2 由 PZ = PX + PY，可知 Dk属于 Sk的 9 个一 跳小区的概率为 PZ = 1 4m2 + 91 36m2 = 25 9m2，m≥13． ( 4) 使用相似方法对此结论进行验证，详见附录 A． 表 1 不同 Sk位置下满足事件 Y 要求的状态总数 Table 1 Total number of the state that meets the requirement of Event Y under different Sk Sk编号 满足事件 Y 要求的状态总数 总计 ② 1 × 1 + 6 × 2 + 4 × 3 + 5 × 4 + 3 × 5 + 1 × 6 66 ③ 1 × 1 + 4 × 2 + 3 × 3 + 3 × 4 + 2 × 5 + 2 × 6 + 1 × 8 60 ④ 1 × 1 + 7 × 2 + 8 × 3 + 6 × 4 + 6 × 5 + 2 × 6 105 ⑤ 1 × 1 + 8 × 2 + 9 × 3 + 7 × 4 72 ⑥ 1 × 1 + 6 × 2 + 4 × 3 + 5 × 4 + 3 × 5 + 1 × 6 66 ⑦ 1 × 1 + 6 × 2 + 8 × 3 + 5 × 4 + 8 × 5 + 4 × 6 + 4 × 8 153 ⑧ 1 × 1 + 7 × 2 + 8 × 3 + 6 × 4 + 6 × 5 + 2 × 6 105 ⑨ 1 × 1 + 5 × 2 + 5 × 3 + 4 × 4 + 4 × 5 + 3 × 6 + 2 × 8 96 2. 3 基础概率性质 传输或接收机会竞争作为影响传输质量的重要 因素，在移动自组网性能分析工作中极易被忽视． 首先利用上述相遇事件的有关结论，为活动小区定 义下述两类机会竞争概率． 引理 1 传输机会竞争概率被定义为活动小区 中至少含有两个节点的概率，即 1 － ( 1 － PX ) n － C1 nPX ( 1 － PX ) n － 1 = 1 － 1 － ( 1 4 ) n n ( － 1 5 4 － 1 4 ) n n→ → ∞ 1 － 5 4 e － 1 /4 ． 引理 2 接收机会竞争概率被定义为除发送节 点外，活动小区的一跳传输范围内至少含有两个其 他节点的概率，即 1 － ( 1 － PX ) n － ∑ 2 k = 1 Ck nPX ( 1 － PZ ) n － k － C2 nC1 2PX PY ( 1 － PZ ) n － 2 n→ → ∞ 1 － e － 1 /4 － 263 288e － 25 /9 ． 引理 1 与引理 2 的结果充分证明，随着网络规 模 m( m2 = n) 无限增长并逐渐趋于无穷，基于随机 路径点移动模型的移动自组网发生传输机会竞争或 接收机会竞争的概率无法收敛于 0，故通过研究此 类资源竞争问题，可以提升网络性能分析结果的准 确性． 其次，对于一个给定时隙下的数据流，分别用 p1、p2和 p3依次代表其发生一次包传输的概率、发生 一次 S － D 传输的概率以及发生一次 S － Ｒ 传输或 Ｒ － D 传输的概率，易知 p1 = p2 + p3，具体如下． 对于 p2所描述的事件，当且仅当下述三个子事 件同时发生: ( 1) S 位于活动小区中; ( 2) D 位于 S 所在小区或 S 的 8 个邻接小区; ( 3) S 被选作发 送者． 综上所述，有 p2 = 1 α2 [ ∑ n －2 k = 0 Ck n － 2Pk X ( 1 － PX ) n － 2 － k PX 1 k + 2 + ∑ n －2 k = 0 Ck n － 2Pk X ( 1 － Px ) n － 2 － k PY 1 k ] + 1 = 1 α2 [ nPY + nPX － 1 n( n － 1) PX － ( 1 － PX ) n － 1 nPY + PX － 1 n( n － 1) P ] X = 1 α2 [ 100n － 36m2 9n( n － 1) － ( 4m2 － 1 4m2 ) n － 191n + 9 － 36m2 9n( n － 1 ] ) ． 对于 p3所描述的事件，当且仅当下述四个子事 件同时发生: ( 1) S 位于活动小区中; ( 2) S 一跳传 输范围内至少有一个除 S 外的节点; ( 3) S 被选作 发送者; ( 4) D 不在 S 的一跳传输范围内． p3 = 1 α2 ( 1 － PZ [ ) ∑ n －2 k = 1 Ck n － 2Pk X ( 1 － PX ) n － 2 － k 1 k + 1 + ∑ n －2 k = 1 Ck n － 2Pk Y ( 1 － PZ ) n － 2 － k × 1 = ] 1 α2 ( 1 － PZ [ ) 1 － ( 1 － PX ) n － 1 ( n － 1) PX － ( 1 － PZ ) n ] － 2 = 1 α2 { 36m2 － 100 9( n － 1 [ ) 1 － ( 4m2 － 1 4m2 ) n ] － 1 ( － 9m2 － 25 9m2 ) n } － 1 ． 类似地，对于一个给定时隙下的数据流，假设当 前网络中已有包 P 的 j 个副本，则以 Pr( j) 代表节点 D 在下一时隙成功接收到包 P 的概率，其中1≤j≤ f + 1; 以 Pd ( j) 代表节点 S 在下一时隙成功发出包 P 的一个新副本的概率，其中1≤j≤f． 根据充要条件， 可推出［10］ · 5041 ·

·1406· 北京科技大学学报 第36卷 -1 P.》=P+2n-2P (5) 讨论. 4.1网络参数设置 -n-j-1 Pa)=2n-2P: (6) 在模拟仿真平台中，约定保护因子△=1，则公 式(1)相应地化简为a=min{8,m}.同时为方便数 3 网络容量延迟封闭表达式 据度量，引入系统负载量p=入，通常在稳定的网 络环境下，恒有p<1. 我们可以利用第2节中得到的理论结果推导出 仿真实验过程中所涉及的主要网络参数依次设 随机路径点移动模型下的网络容量和端到端延迟 定为n=550,m=24,f6=21,其中包副本数上限f取 上限. 值为12时，理论网络容量值4=2.036×10-4包时 推导过程首先将公式(5)和公式(6)视作马尔 隙1，当f取值为15时，u=2.385×10-4包· 科夫链的转移概率，并由此构建两条有限状态的一 时隙. 维吸收马尔科夫链@分别用来描述S端的发送过 关于使用多副本两跳中继算法的基于记忆条件 程和D端的接收过程.定义S端平均服务时间X 的随机路径点移动模型，通过计算可得不同负载下 为源节点S开始为某包发送副本到S结束为其发送 端到端延迟的理论上限，如表2所列. 副本的平均时间间隔，D端平均服务时间X,指目的 节点D开始请求接收某包到D成功收到该包的平 表2端到端延迟上限理论值(n=550,m=24) 均时间间隔。随后寻找二者间的数值关系，其中一 Table 2 Theoretical values of the upper bound of end-o-nd delay (n= 550,m=24) 个重要的性质指明存在区域上限f,使得当1≤f≤ E{T}f=12) E{T}f=15) f6时，总有 0.2 8201.379 7932.840 X、≤Xo (7) 0.3 9168.755 8866.235 最终由公式(7)推导出网络容量μ，即最大接收 0.4 10436.731 10076.407 速率，和端到端延迟上限T的期望值E{T},其中 0.5 12181.884 11719.589 T代表包从产生到被接收的平均时间间隔，分别如 下式o: 0.6 14756.412 14103.994 0.7 18980.501 17940.449 u=P+2(n-2)P (8) 0.75 22325.610 20932.353 E{X,(f+1)} E{X,(f+1)} 0.8 27311.609 25342.380 E(T.}≤1-AEX,+1)厅+-AEXf+1)刀 0.85 35575.723 32571.500 (9) 0.9 52028.986 46816.615 其中，Ex+1)}=22a-2》且EX,+ 台(n-i-1)P3 4.2理论结果准确性验证 2(n-2) 仿真实验运行总时间达到10000000时隙，并重 1)}=2(m-2)p+fP 分别为S与D的服务时间 复该模拟过程三次后，汇总不同副本数下仿真实验 函数 数值结果及其均值为表3.其中，端到端延迟的实验 值均严格低于其理论上界，验证了第2节中相遇事 4 仿真结果与分析 件概率理论框架的分析结论以及第3节中端到端延 依据系统模型的相关要求，在C++环境中构 迟闭解表达式的正确性.当f=12时，实验值与理论 造相应的网络模拟器，对随机路径点移动模型下的 上界比较接近，二者差距分布在0.87%与10.71% 多副本两跳中继算法进行了仿真.模拟程序包含随 之间：而当f=15时，源节点发出的副本总数增加， 机数生成模块、输入流控制模块、传输组管理模块、 使得网络端到端延迟略有改善，但理论延迟上界的 传输机会竞争模块、S-D传输模块、S-R传输模 约束条件变宽，造成实验数据与理论值之间的差距 块、R-D传输模块、总传输调度模块以及移动模 增大，大致分布在5.08%与16.72%之间.因此，从 型等 实验结果我们可以进一步推知，在网络参数n、m与 通过分析该仿真结果，验证了概率理论框架、容 固定的条件下，若降低包副本数上限，则端到端延 量延迟闭解表达式的正确性.同时，对i.i.d.移动 迟的闭解上界将更加接近于真实时延. 模型、随机路径点移动模型下网络性能的差异进行 图6描述在基于记忆条件的随机路径点移动模

北 京 科 技 大 学 学 报 第 36 卷 Pr( j) = p2 + j － 1 2( n － 2) p3， ( 5) Pd ( j) = n － j － 1 2( n － 2) p3 ． ( 6) 3 网络容量延迟封闭表达式 我们可以利用第 2 节中得到的理论结果推导出 随机路径点移动模型下的网络容量和端到端延迟 上限． 推导过程首先将公式( 5) 和公式( 6) 视作马尔 科夫链的转移概率，并由此构建两条有限状态的一 维吸收马尔科夫链［10］分别用来描述 S 端的发送过 程和 D 端的接收过程． 定义 S 端平均服务时间 XS 为源节点 S 开始为某包发送副本到 S 结束为其发送 副本的平均时间间隔，D 端平均服务时间 XD指目的 节点 D 开始请求接收某包到 D 成功收到该包的平 均时间间隔． 随后寻找二者间的数值关系，其中一 个重要的性质指明存在区域上限 f0，使得当 1≤f≤ f0时，总有 XS≤XD ( 7) 最终由公式( 7) 推导出网络容量 μ，即最大接收 速率，和端到端延迟上限 Te的期望值 E{ Te } ，其中 Te代表包从产生到被接收的平均时间间隔，分别如 下式［10］: μ = p2 + f 2( n － 2) p3 ( 8) E{ Te } ≤ E{ XS ( f + 1) } 1 － λE{ XS ( f + 1) } + E{ XD( f + 1) } 1 － λE{ XD( f + 1) } ( 9) 其中，E{ XS ( f + 1) } = ∑ f i = 1 2( n － 2) ( n － i － 1) p3 且 E{ XD( f + 1) } = 2( n － 2) 2( n － 2) p2 + f·p3 分别为 S 与 D 的服务时间 函数． 4 仿真结果与分析 依据系统模型的相关要求，在 C + + 环境中构 造相应的网络模拟器，对随机路径点移动模型下的 多副本两跳中继算法进行了仿真． 模拟程序包含随 机数生成模块、输入流控制模块、传输组管理模块、 传输机会竞争模块、S － D 传输模块、S － Ｒ 传输模 块、Ｒ － D 传输模块、总传输调度模块以及移动模 型等． 通过分析该仿真结果，验证了概率理论框架、容 量延迟闭解表达式的正确性． 同时，对 i． i． d． 移动 模型、随机路径点移动模型下网络性能的差异进行 讨论． 4. 1 网络参数设置 在模拟仿真平台中，约定保护因子 Δ = 1，则公 式( 1) 相应地化简为 α = min{ 8，m} ． 同时为方便数 据度量，引入系统负载量 ρ = λ /μ，通常在稳定的网 络环境下，恒有 ρ ＜ 1． 仿真实验过程中所涉及的主要网络参数依次设 定为 n = 550，m = 24，f0 = 21，其中包副本数上限 f 取 值为 12 时，理论网络容量值 μ = 2. 036 × 10 － 4包·时 隙 － 1，当 f 取 值 为 15 时，μ = 2. 385 × 10 － 4 包· 时隙 － 1 ． 关于使用多副本两跳中继算法的基于记忆条件 的随机路径点移动模型，通过计算可得不同负载下 端到端延迟的理论上限，如表 2 所列． 表 2 端到端延迟上限理论值( n = 550，m = 24) Table 2 Theoretical values of the upper bound of end-to-end delay ( n = 550，m = 24) ρ E{ Te } ( f = 12) E{ Te } ( f = 15) 0. 2 8201. 379 7932. 840 0. 3 9168. 755 8866. 235 0. 4 10436. 731 10076. 407 0. 5 12181. 884 11719. 589 0. 6 14756. 412 14103. 994 0. 7 18980. 501 17940. 449 0. 75 22325. 610 20932. 353 0. 8 27311. 609 25342. 380 0. 85 35575. 723 32571. 500 0. 9 52028. 986 46816. 615 4. 2 理论结果准确性验证 仿真实验运行总时间达到 10000000 时隙，并重 复该模拟过程三次后，汇总不同副本数下仿真实验 数值结果及其均值为表 3． 其中，端到端延迟的实验 值均严格低于其理论上界，验证了第 2 节中相遇事 件概率理论框架的分析结论以及第 3 节中端到端延 迟闭解表达式的正确性． 当 f = 12 时，实验值与理论 上界比较接近，二者差距分布在 0. 87% 与 10. 71% 之间; 而当 f = 15 时，源节点发出的副本总数增加， 使得网络端到端延迟略有改善，但理论延迟上界的 约束条件变宽，造成实验数据与理论值之间的差距 增大，大致分布在 5. 08% 与 16. 72% 之间． 因此，从 实验结果我们可以进一步推知，在网络参数 n、m 与 f0固定的条件下，若降低包副本数上限，则端到端延 迟的闭解上界将更加接近于真实时延． 图 6 描述在基于记忆条件的随机路径点移动模 · 6041 ·

第10期 王晓菲等：基于随机路径点移动模型的MANET容量及延迟分析 ·1407· 表3端到端延迟模拟仿真结果及平均值(95%置信区间) 7415.8~49157.1间连续变化，理论时延由8201.4 Table 3 Simulated results and their average values for end-to-end delay 增大到52029.0，表明实验数据与理论上界紧密匹 (95%confidence intervals) 配。此外，通过观察可知，当系统负载量逐渐向1逼 f 实验1 实验2 实验3 平均值 近（大于0.8）时，平均端到端延迟快速增长，网络输 12 0.2 7531.2 7225.0 7491.3 7415.8 入速率逐渐接近其最大吞吐量，从而初步验证了理 12 0.3 9017.1 8926.3 9001.2 8981.5 论网络容量.对于图6(b)中f取值为15的情况，同 0.4 10312.5 10056.3 10110.9 10159.9 样可以得到相似结论. 12 0.5 11434.4 11302.2 11701.5 11479.4 进一步对比可以发现，随机路径点移动模型的 12 0.6 14332.7 13567.9 13747.5 13882.7 记忆条件降低了移动节点的相遇概率，使得网络容 0.7 19128.4 18543.2 18777.1 18816.2 量小于i.i.d.移动模型，而平均时延在f=12时高 12 0.75 22254.120934.9 21023 21404.0 于i.i.d.移动模型（见图6(a)),却在f=15时低于 0.8 27510.4 25873.2 26035.1 26472.9 i.i.d.移动模型（见图6(b)).证明相遇概率不是影 12 0.85 32359.2 31419.8 31517.5 31765.5 响网络延迟的唯一因素，可以在随机路径点移动模 农 0.9 54697.5 45765.6 47008.2 49157.1 型下通过提高包副本数上限来降低端到端延迟，甚 15 0.2 6103.4 6674 7042.2 6606.5 至获得优于i.i.d.移动模型的时延性能指标，但要 s 0.3 7337.1 7489.7 7770.3 7532.4 以牺牲小部分网络容量为代价 15 0.4 10005.5 8664.7 9045.4 9238.5 此外，以P.(f+1)代表某个包在发完f个副本 0.5 11375.7 10204.6 10797.2 10792.5 后才被目的节点接收的概率.图7绘制出伴随系统 15 0.6 12048.3 12434.8 12696.2 12393.1 负载的提升概率P。(f+1)的增长曲线，p=0.9时 0.7 15647.8 16977.3 17640.8 16755.3 P.(f+1)的取值接近于1.当前传输中几乎全部的 15 0.75 20394.9 19287.6 19509.9 19730.8 数据包均是在源节点发出f个副本后才由目的节点 0.8 24144.7 23013.9 23885.0 23681.2 接收，即数据输入速率己无限接近网络能够提供的 15 0.85 31860.8 30079.1 30812.4 30917.4 最大吞吐能力，可以证明闭解容量理论分析结果的 15 0.9 42876.640940.5 41404.5 41740.5 准确性. 型下，随着系统负载量的不断增加，网络延迟理论值 4.3理论结果定量分析 与模拟仿真结果的变化趋势.以图6(a)为例，当p 针对移动自组网中基于记忆条件的随机路径点移 从0.2增大到0.9，即入值在0.407×10-4至 动模型，从容量延迟闭解表达式中可以分析出一些实 1.832×10-4间连续变化时，实验结果与理论上界两 用指标图8(a)指出f的最佳取值（即f。),以及在该 条曲线呈现出基本相同的变化规律.仿真时延在 值下可达的最大网络容量，如图8(b)所示 55000Ta i.d,移动模型理论上限 45000 ii.d.移动模型理论上限 (1=2.586x104包·时隙 4=2.858×10一包·时隙-) 45000 随机路径点移动模型理论上限 随机路径点移动模型理论上限 ···随机路径点移动模型仿真 ···随机路径点移动模型仿真 蓝35000 35000 25000 25000 15000 15000 5000 5000 0.1 0.3 0.5 0.7 0.9 .1 0.3 05 0.7 0.9 系统负载 系统负载 图6随机路径点模型下网络延迟理论值与仿真结果对比.(a)参数n=550,m=24,f=12,μ=2.036×104包·时隙：(b)参数n= 550,m=24,f=15,u=2.385×10-4包时隙1 Fig.6 Comparison between theoretical and simulated results for network delay validation under the random waypoint mobility model:(a)parameters n =550,m=24,f=12,u=2.036 x10-4 packets'slot-1:(b)parameters n =550,m=24,f=15,u=2.385 x10-4 packets'slot

第 10 期 王晓菲等: 基于随机路径点移动模型的 MANET 容量及延迟分析 表 3 端到端延迟模拟仿真结果及平均值( 95% 置信区间) Table 3 Simulated results and their average values for end-to-end delay ( 95% confidence intervals) f ρ 实验 1 实验 2 实验 3 平均值 12 0. 2 7531. 2 7225. 0 7491. 3 7415. 8 12 0. 3 9017. 1 8926. 3 9001. 2 8981. 5 12 0. 4 10312. 5 10056. 3 10110. 9 10159. 9 12 0. 5 11434. 4 11302. 2 11701. 5 11479. 4 12 0. 6 14332. 7 13567. 9 13747. 5 13882. 7 12 0. 7 19128. 4 18543. 2 18777. 1 18816. 2 12 0. 75 22254. 1 20934. 9 21023 21404. 0 12 0. 8 27510. 4 25873. 2 26035. 1 26472. 9 12 0. 85 32359. 2 31419. 8 31517. 5 31765. 5 12 0. 9 54697. 5 45765. 6 47008. 2 49157. 1 15 0. 2 6103. 4 6674 7042. 2 6606. 5 15 0. 3 7337. 1 7489. 7 7770. 3 7532. 4 15 0. 4 10005. 5 8664. 7 9045. 4 9238. 5 15 0. 5 11375. 7 10204. 6 10797. 2 10792. 5 15 0. 6 12048. 3 12434. 8 12696. 2 12393. 1 15 0. 7 15647. 8 16977. 3 17640. 8 16755. 3 15 0. 75 20394. 9 19287. 6 19509. 9 19730. 8 15 0. 8 24144. 7 23013. 9 23885. 0 23681. 2 15 0. 85 31860. 8 30079. 1 30812. 4 30917. 4 15 0. 9 42876. 6 40940. 5 41404. 5 41740. 5 图 6 随机路径点模型下网络延迟理论值与仿真结果对比． ( a) 参数 n = 550，m = 24，f = 12，μ = 2. 036 × 10 － 4 包·时隙 － 1 ; ( b) 参数 n = 550，m = 24，f = 15，μ = 2. 385 × 10 － 4包·时隙 － 1 Fig． 6 Comparison between theoretical and simulated results for network delay validation under the random waypoint mobility model: ( a) parameters n = 550，m = 24，f = 12，μ = 2. 036 × 10 － 4 packets·slot － 1 ; ( b) parameters n = 550，m = 24，f = 15，μ = 2. 385 × 10 － 4 packets·slot － 1 型下，随着系统负载量的不断增加，网络延迟理论值 与模拟仿真结果的变化趋势． 以图 6( a) 为例，当 ρ 从 0. 2 增 大 到 0. 9，即 λ 值 在 0. 407 × 10 － 4 至 1. 832 × 10 － 4间连续变化时，实验结果与理论上界两 条曲线呈现出基本相同的变化规律． 仿真时延在 7415. 8 ～ 49157. 1 间连续变化，理论时延由 8201. 4 增大到 52029. 0，表明实验数据与理论上界紧密匹 配． 此外，通过观察可知，当系统负载量逐渐向 1 逼 近( 大于 0. 8) 时，平均端到端延迟快速增长，网络输 入速率逐渐接近其最大吞吐量，从而初步验证了理 论网络容量． 对于图 6( b) 中 f 取值为 15 的情况，同 样可以得到相似结论． 进一步对比可以发现，随机路径点移动模型的 记忆条件降低了移动节点的相遇概率，使得网络容 量小于 i． i． d． 移动模型，而平均时延在 f = 12 时高 于 i． i． d． 移动模型( 见图 6( a) ) ，却在 f = 15 时低于 i． i． d． 移动模型( 见图 6( b) ) ． 证明相遇概率不是影 响网络延迟的唯一因素，可以在随机路径点移动模 型下通过提高包副本数上限来降低端到端延迟，甚 至获得优于 i． i． d． 移动模型的时延性能指标，但要 以牺牲小部分网络容量为代价． 此外，以 Pa ( f + 1) 代表某个包在发完 f 个副本 后才被目的节点接收的概率． 图 7 绘制出伴随系统 负载的提升概率 Pa ( f + 1) 的增长曲线，ρ = 0. 9 时 Pa ( f + 1) 的取值接近于 1． 当前传输中几乎全部的 数据包均是在源节点发出 f 个副本后才由目的节点 接收，即数据输入速率已无限接近网络能够提供的 最大吞吐能力，可以证明闭解容量理论分析结果的 准确性． 4. 3 理论结果定量分析 针对移动自组网中基于记忆条件的随机路径点移 动模型，从容量延迟闭解表达式中可以分析出一些实 用指标． 图 8( a) 指出 f 的最佳取值( 即 f0 ) ，以及在该 值下可达的最大网络容量 μ* ，如图8( b) 所示． · 7041 ·

·1408 北京科技大学学报 第36卷 0.98 0.96 0.88 0.92 084 0.90 .1 03 0.5 0.7 0.9 0.3 0.5 0.7 0.9 系统负截 系统负截 图7随机路径点移动模型概率值P.V+1)仿真结果.(a)参数n=550,m=24,∫=12,4=2.036×104包·时隙l:(b)参数n=550, m=24,f=15,4=2.385×10-4包时隙1 Fig.7 Simulated results for the probability value P (f+1)under the random waypoint mobility model:(a)parameters n =550,m=24,f=12, =2.036 x10-4 packets*slot":(b)parameters n=550,m=24.f=15,u=2.385 x10-4 packets"slot-! 在n=m的约束条件下，当m值从6逐渐增至 低.此外，图8(a)的分段函数表明副本数f的最佳 12,即n值在36至1024间连续变化时，图8(b)表 取值仅能在小范围的值区间内保持稳定，不存在 明随着n值的不断增加，u快速趋近于0.若n> 适用于任意通信场景的最优。值.且随着节点数目 250,则μ值将会低于5×10-4包·时隙-，相比n= 的增加，6取值的增长速度不断减小，即对于大规模 36的情况，最大网络容量缩小了5倍以上.此时，移 网络环境，单纯增加副本数上限不会为网络容量带 动节点传输资源竞争带来的负作用远远超过单个数 来明显提升 据流所能提供的通信能力，故其最大吞吐量急剧降 30- 30- a 25 35 20 15 15 10 10 200 400 600800 1000 200 400 600 800 1000 节点数，n 节点数 图8最大容量及f最佳值（其中m2=n且36≤n≤1024）.(a)不同n值下的最佳f值：(b)不同n值下的最大网络容量： Fig.8 Maximum capacity and optimal fvalue,where m2=n and 324:(a)optimal fvalue with different n:(b)maximum capacity with different n 5结论 i.i.d.移动模型推广至随机路径点移动模型； (3)通过仿真实验，证明了该概率理论框架的 本文研究了随机路径点移动模型下移动自组织 有效性及闭解表达式的准确性. 网的容量与延迟，针对广泛应用的多副本两跳中继 附录A 算法，推导出封闭的性能表达式 (1)提出了一套概率理论框架，为满足记忆条 概率P,证明：以①号小区位置为例，所有可能 件的相遇行为建模，并计算移动节点的相遇概率； 的位置D-1及其移动路径（从Dk-1移动到①号S的 (2)将移动自组网容量延迟的闭解分析方法从 9个一跳小区)如图A一1所示，可知节点D一次移

北 京 科 技 大 学 学 报 第 36 卷 图 7 随机路径点移动模型概率值 Pa ( f + 1) 仿真结果． ( a) 参数 n = 550，m = 24，f = 12，μ = 2. 036 × 10 － 4 包·时隙 － 1 ; ( b) 参数 n = 550， m = 24，f = 15，μ = 2. 385 × 10 － 4包·时隙 － 1 Fig． 7 Simulated results for the probability value Pa ( f + 1) under the random waypoint mobility model: ( a) parameters n = 550，m = 24，f = 12， μ = 2. 036 × 10 － 4 packets·slot － 1 ; ( b) parameters n = 550，m = 24，f = 15，μ = 2. 385 × 10 － 4 packets·slot － 1 在 n = m2 的约束条件下，当 m 值从 6 逐渐增至 12，即 n 值在 36 至 1024 间连续变化时，图 8( b) 表 明随着 n 值的不断增加，μ* 快速趋近于 0． 若 n ＞ 250，则 μ* 值将会低于 5 × 10 － 4包·时隙 － 1，相比 n = 36 的情况，最大网络容量缩小了 5 倍以上． 此时，移 动节点传输资源竞争带来的负作用远远超过单个数 据流所能提供的通信能力，故其最大吞吐量急剧降 低． 此外，图 8( a) 的分段函数表明副本数 f 的最佳 取值仅能在小范围的 n 值区间内保持稳定，不存在 适用于任意通信场景的最优 f0值． 且随着节点数目 的增加，f0取值的增长速度不断减小，即对于大规模 网络环境，单纯增加副本数上限不会为网络容量带 来明显提升． 图 8 最大容量及 f 最佳值( 其中 m2 = n 且 36≤n≤1024) ． ( a) 不同 n 值下的最佳 f 值; ( b) 不同 n 值下的最大网络容量 μ* Fig． 8 Maximum capacity and optimal f value，where m2 = n and 36≤n≤1024: ( a) optimal f value with different n; ( b) maximum capacity with different n 5 结论 本文研究了随机路径点移动模型下移动自组织 网的容量与延迟，针对广泛应用的多副本两跳中继 算法，推导出封闭的性能表达式． ( 1) 提出了一套概率理论框架，为满足记忆条 件的相遇行为建模，并计算移动节点的相遇概率; ( 2) 将移动自组网容量延迟的闭解分析方法从 i． i． d． 移动模型推广至随机路径点移动模型; ( 3) 通过仿真实验，证明了该概率理论框架的 有效性及闭解表达式的准确性． 附录 A 概率 PZ证明: 以①号小区位置为例，所有可能 的位置 Dk － 1及其移动路径( 从 Dk － 1移动到①号 Sk的 9 个一跳小区) 如图 A--1 所示，可知节点 D 一次移 · 8041 ·

第10期 王晓菲等：基于随机路径点移动模型的MANET容量及延迟分析 ·1409· 动过程中满足事件Z要求的状态总数为 附录B 1×1+5×2+3×3+6×4+7×6+2×9=104. 有关余下的8个S小区位置及相应的状态总数，详 现归纳本文使用符号及具体含义如表B一1 见表A-1. 所示 表A-H不同S,位置下满足事件Z要求的状态总数 表BH符号与参数汇总 Table A-1 Total number of the state that meets the requirement of Table B-1 Summary of notations and parameters Event Z under different S 符号 含义 S编号 满足事件Z要求的状态总数 总计 E(T.} 瑞到端延迟上限 ② 1×1+6×2+1×3+8×4+4×6 72 4 干扰模型保护因子 8 1×1+4×2+2×3+4×4+4×6+1×9 64 a 传输组小区间隔数 ④ 1×1+7×2+2×3+12×4+8×6 117 源节点生成包速率 ⑤ 1×1+8×2+16×4 81 Px S和D属于相同小区的概率 ⑥ 1×1+6×2+1×3+8×4+4×6 72 P D属于S的8个邻接小区的概率 ① 1×1+6×2+4×3+9×4+12×6+4×9 169 Pz D属于S的9个一跳小区的概率 ⑧ 1×1+7×2+2×3+12×4+8×6 117 P 发生一次包传输的概率 1×1+5×2+3×3+6×4+7×6+2×9 104 P2 发生一次S-D传输的概率 P3 发生一次S-R传输或R-D传输的概率 由此，依据图3的记忆条件，结合图A一1与表 P.》 D在下一时隙收到包P的概率 A一中所描述的场景，仿照定理1的证明过程，可得 Pa() S在下一时隙发出包P新副本的概率 P=.L.104 72 64 P.V+1) 包P发完f个副本后才被D接收的概率 m249m2×36m2×36m2×36 Xs S端平均屐务时间 11781+72-+169 网络容量 m2×36m2×36m2×36m2×36 m 网络规模 m×36tmx36m4=2点 117,1041 9m2 通信范围 则公式(4)得证. 源节点 R 中继节点 目的节点 fo f值上限 系统负载 n 移动节点总数 f 包副本数上限 a)1x1 )5x2 e)3x3 最大网络容量 S S在时隙k的位置 Du D在时隙k的位置 X。 D端平均服务时间 参考文献 (d)6x4 (e)7x6 )2x9 图A1D.1到Du移动过程示例（其中黑点代表可能的D4.1位 [Ma YZ,Jamalipour A.A cooperative cache-ased content deliv- 置，阴影区域代表在①号S,一跳范围且D一步可达的小区，箭头 ery framework for intermittently connected mobile ad hoc networks. 举例说明了相应的移动路径) IEEE Trans Wireless Commun,2010,9(1)366 Fig.A-1 Illustration of all possible movement processes from D 2] Grossglauser M,Tse D N.Mobility increases the capacity of ad hoc wireless networks.IEEE/ACM Trans Netcorking,2002,10 to D,where the blackspots represent possible D,the shaded are- (4):477 as represent one-hop cells of the first S that D can reach by one-hop B3]Sharma G.Mazumdar R.Shroff N.Delay and capacity tradeoffs and the arrows take examples for corresponding moving paths in mobile ad hoc networks:a global perspective.IEEE/ACM

第 10 期 王晓菲等: 基于随机路径点移动模型的 MANET 容量及延迟分析 动过程中满足事件 Z 要求的状态总数为 1 × 1 + 5 × 2 + 3 × 3 + 6 × 4 + 7 × 6 + 2 × 9 = 104． 有关余下的 8 个 Sk小区位置及相应的状态总数，详 见表 A--1． 表 A--1 不同 Sk位置下满足事件 Z 要求的状态总数 Table A--1 Total number of the state that meets the requirement of Event Z under different Sk Sk编号 满足事件 Z 要求的状态总数 总计 ② 1 × 1 + 6 × 2 + 1 × 3 + 8 × 4 + 4 × 6 72 ③ 1 × 1 + 4 × 2 + 2 × 3 + 4 × 4 + 4 × 6 + 1 × 9 64 ④ 1 × 1 + 7 × 2 + 2 × 3 + 12 × 4 + 8 × 6 117 ⑤ 1 × 1 + 8 × 2 + 16 × 4 81 ⑥ 1 × 1 + 6 × 2 + 1 × 3 + 8 × 4 + 4 × 6 72 ⑦ 1 × 1 + 6 × 2 + 4 × 3 + 9 × 4 + 12 × 6 + 4 × 9 169 ⑧ 1 × 1 + 7 × 2 + 2 × 3 + 12 × 4 + 8 × 6 117 ⑨ 1 × 1 + 5 × 2 + 3 × 3 + 6 × 4 + 7 × 6 + 2 × 9 104 由此，依据图 3 的记忆条件，结合图 A--1 与表 A--1 中所描述的场景，仿照定理 1 的证明过程，可得 图 A--1 Dk － 1到 Dk移动过程示例( 其中黑点代表可能的 Dk － 1 位 置，阴影区域代表在①号 Sk一跳范围且 D 一步可达的小区，箭头 举例说明了相应的移动路径) Fig． A--1 Illustration of all possible movement processes from Dk － 1 to Dk，where the blackspots represent possible Dk － 1，the shaded are￾as represent one-hop cells of the first Sk that D can reach by one-hop and the arrows take examples for corresponding moving paths Pz = 1 m2 ·1 4 ·1 9 ·( 104 m2 × 36 + 72 m2 × 36 + 64 m2 × 36 + 117 m2 × 36 + 81 m2 × 36 + 72 m2 × 36 + 169 m2 × 36 + 117 m2 × 36 + 104 m2 ) × 36 ·m2 ·4 = 25 9m2 ． 则公式( 4) 得证． 附录 B 现归纳本文使用符号及具体含义如表 B--1 所示． 表 B--1 符号与参数汇总 Table B--1 Summary of notations and parameters 符号 含义 E{ Te } 端到端延迟上限 Δ 干扰模型保护因子 α 传输组小区间隔数 λ 源节点生成包速率 PX S 和 D 属于相同小区的概率 PY D 属于 S 的 8 个邻接小区的概率 PZ D 属于 S 的 9 个一跳小区的概率 p1 发生一次包传输的概率 p2 发生一次 S － D 传输的概率 p3 发生一次 S － Ｒ 传输或 Ｒ － D 传输的概率 Pr ( j) D 在下一时隙收到包 P 的概率 Pd ( j) S 在下一时隙发出包 P 新副本的概率 Pa ( f + 1) 包 P 发完 f 个副本后才被 D 接收的概率 XS S 端平均服务时间 μ 网络容量 m 网络规模 r 通信范围 S 源节点 Ｒ 中继节点 D 目的节点 f0 f 值上限 ρ 系统负载 n 移动节点总数 f 包副本数上限 μ* 最大网络容量 Sk S 在时隙 k 的位置 Dk D 在时隙 k 的位置 XD D 端平均服务时间 参 考 文 献 ［1］ Ma Y Z，Jamalipour A． A cooperative cache-based content deliv￾ery framework for intermittently connected mobile ad hoc networks． IEEE Trans Wireless Commun，2010，9( 1) : 366 ［2］ Grossglauser M，Tse D N． Mobility increases the capacity of ad hoc wireless networks． IEEE /ACM Trans Networking，2002，10 ( 4) : 477 ［3］ Sharma G，Mazumdar Ｒ，Shroff N． Delay and capacity trade-offs in mobile ad hoc networks: a global perspective． IEEE /ACM · 9041 ·