第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 ·