Ad Hoc 网络中的区域划分和资源分配问题(正文).pdf

Ad Hoc 网络中的区域划分和资源分配问题 1 问题假设 本文根据 Ad Hoc 网络中的区域划分和资源分配问题的一些要求 为了达到 简化模型的目的 除问题中已给出的假设外 仅以可不作出以下假设 （1）本文考虑在指定区域 1000×1000 的范围内 假设均放置等大小的圆 并且使其在区域范围内对称 （仅对无湖的情况考虑对称）。 （2）假设两圆相切不相交时不属于相邻的情况 （3）假设在一个节点有多个信道的情况下 多信道可以同时工作。 （4）假设转发也可以看作是一次接收和一次发射。 注：部分问题涉及到的假设 在相应问题中给出。 2 参数说明 R：一跳覆盖区圆的半径;  ：相邻两圆公共面积所确定弦长对应的圆心角； W：单个节点的发射功率； h：单个节点的最大传输距离； n：正方形区域内的节点总数； M：整个网络通信中 数据包丢失的几率 3 问题分析 3.1 对于问题一的分析 (1) 对覆盖整个网络所用最少圆的问题分析 要考虑一个实际问题 即对称性。 通过分析 必须保证网络的覆盖对称 这样才能保证所用的圆的数量最少。还要 满足任意两个相交的圆的面积要大于 5% 通过后面的定量计算 使得任意一个 圆都和周围的六个圆相交 才能符合。 (2) 对信道选择的理解为 任意两个相邻的圆均要拥有不同的频率 并且要选择 最少的频率来填充。此问题类似于用最少的颜色来填充地图问题 属于离散数学 方面的问题。 (3) 对于网络抗毁性的理解 随机抽掉一定比例的节点后 只考虑剩余的节点是否任意两个都可以通信 即为连通即可。故当任意一个节点周围均匀分布的所有节点都被抽掉时 网络会 有一个节点无法与外界通信 这也就是网络抗毁性研究的临界情况。 3.2 对问题二的分析 由于半径是可变化的 可先考虑无湖情况下 采用什么样的一跳覆盖区可以 使得全部圆半径之和最小。在此基础上 考虑有湖情况下 改进现有方案。 3.3 对问题三的分析  采用基于节点的划分方式 可以将实际问题抽象为 在 1000 1000 的正方 形区域内 用半径为 75-100 的圆将节点全部覆盖 （允许在没有节点的区域内不 进行覆盖）。这样的模型要满足这样的条件 任意相交的两个圆的重叠部分的面 积要大于其中的大圆面积的 5% 并且使得这样的所有大小不等的圆的半径之和 最小。 3.4 对问题四的分析 基于问题三的模型 利用节点的划分方式以及概率的计算方法 进行定量的 计算并比较。考虑节点移动的时候 其所覆盖的区域的半径也在变化 （参考问题 三的模型与算法） 这样当其走出最大可能半径范围而又未进入其他覆盖区 则 此时其发生通信中断。计算这个最大半径的值与问题三的模型进行比较 得出结 1 Ad Hoc 网络中的区域划分和资源分配问题 果。 3.5 对问题五的分析 本问题所要解决的目标是节能 并使第一个退出网络的节点的时间尽量长。 则根据题设 半径越小 则越能节省能源 使得网络的周期延长。基于此思想 可以列出能量相等的公式 得出所要求的模型中圆的半径与题设中给的半径 100 的比值关系 这样就能确定最优答案。 电池的总能量是可看作固定常量 题中假设覆盖半径为 100 发送状态下的工 作总时间是 400 个时间单位