基于dijkstra算法的ad_hoc网络的动态仿真优化

基于dijkstra算法的ad_hoc网络的动态仿真优化内容摘要：

终端可直接建立端到端的通信链路；非相邻终端则可动态地搜索路由，数据包借助其他终端转发，以多跳方式传递至最终的目的终端。 网络中无 线信道环境的快速变化及终端的移动性造成了网络拓扑结构不断变化。 基于 Dijkstra 算法的 Ad Hoc 网络的动态仿真优化 9 （如图 “ Ad Hoc 网络的平面结构图 ” ）在此情况下，法国国立普瓦捷大学国家信号 图像 通信实验室 （ SIC） 设计并实际建立了一个 Ad Hoc 网络动态仿真测试平台 Ad NS(Ad ’hoc Network Simulator)。 通过设置相关的特性参数，我们可以完整地模拟 Ad Hoc 网络的通信；仿但是这个软件同时也有大多数仿真软件共有的不足之处，那就是运算速度不够快。 仿真软件的运算速度将直接影响许多科究工作的顺利开展。 同时也由于采用了迭代循环的最短路 径搜寻算法，这就造成了所有 Ad Hoc 网络仿真平台在计算速度上的一个绝对瓶颈。 本课题的优化思路就是针对 “ 仿真的速度 ” 来展开的 ,如图 14 图 14 Ad NS 仿真平台的微波传输界面 在任意的无线信道环境中，我们假设存在一个相对均匀的或者说稳定的空间区域，能够使我们在仿真微波通讯时，针对所有属于这个区域的移动终端，我们只需要做一次迭代仿真运算就相当于对它们全部进行了仿真运算。 这样一来，仿真的速度应该就能成倍甚至是更大程度地提高。 根据这个假设的思路去做优化，优化的就不再是算法本身。 应该说，这种优化 的实质只是一种近似估算；但对于 “ 优化 ” 而言，只要能真正提高 “ 速度 ”的优化方法，就是好方法。 信宿 信源 基于 Dijkstra 算法的 Ad Hoc 网络的动态仿真优化 10 当然，不论它如何富有创新意味，它仅仅只是一个假设。 任何科学的假设（设想）提出固然异常重要，但同样重要的还有针对它的实践论证。 在我们的实验过程中，为了进一步提高效率，我们选用了 Ad NS 平台的 2D模式的 升级 版本软件：微波通讯仿真软件 Impulse Response Simulator（简称IRS）。 这个软件能够根据对通信信道脉冲响应的研究而描绘出通信信道的稳定性特征曲线。 而我们要利用的，则是它在 做 完无线仿真计算后生 成的一个有关冲激响应的文件 （ 也是 .DR 文件 ） ，这个文件由一系列的坐标及其对应的延时抖动（ dispersion of the delay） 组成，我们要做的最简单的也是最主要的工作，就是从这个文件中提取出一组延时数据生成一个新的数组（ array），借用 MATLAB等软件读取之后，再对其进行一系列的统计和分析。 在实际的实验论证中，我们首先选用了普瓦捷大学校园作为应用模拟脚本。 先后设置了十个信号发射 (emission)点和 6 个目标 (destination)信号群 (待测区域 )，每次先固定一个发射点，然后分别对应 6 个 待测区域（正方形），并且将每个区域的面积分别从 4 平方米增加到 40平方米，一个信号能得到 6组数据。 这样我们就有了 60组数据进行对比分析。 所有的数据都是在统一的工作频率、统一的折射、衍射次数、统一的工作海拔高度，以及统一的目标终端排列密度等等的情况下获得的。 然后我们对它们进行群组统计。 不但确保了统计分析的涵盖性和科学性，更确保了我们最看重的精确性。 要平台上实现一次仿真，一般包括下面三个部分： 参数设置等前期准备： 包括以下参数：频率 f=()，场景（三维仿真图），衍射和反射 的有效次数，信源和信宿的坐标及（海拨）高度等； 完整地模拟网络： 结果分析 ：生成一个 .DR 文件，关于时间延迟的，实际是生成一个原始数据矩阵，可利用 MATLAB 对数据获取较便利的优势及其强大的矩阵数据处理能力来进行分析处理。 1． 5 Ad Hoc 网络相关参数 先介绍三个计算公式，分别是数学期望，方差（及标准方差）和标准基于 Dijkstra 算法的 Ad Hoc 网络的动态仿真优化 11 离差率。 1) 数学期望 若离散型随机变量  可能取值为 ( 1, 2,...)iai ，其分布列为 ),2,1( iPi则当 1||iii pa （ ） 时 ,称  存在数学期望 ,并且数学期望为 1iii paE  （ ） 离散型随机变量的一切可能的取值 ia 与对应的概率 P(= ix )之积的 和称为数学期望。 2) 方差 21()niiSSn （ ） 标准差为： （ ） 数学上一般用 E{[XE(X)]^2}来度量随机变量 X 与其均值 E(X)即期望的偏离程度，称为 X 的 方差。 方差是标准差的平方 3）标准离差率（离散系数） 标准离差率是以相对数来衡量待决策方案的风险。 标准离差率指标的适用范围较广，尤其适用于期望值不同的决策方案风险程度的比较。 标准离差率，是一个 相对指示，它表示某资产每单位预期收益中所包基于 Dijkstra 算法的 Ad Hoc 网络的动态仿真优化 12 含的风险的大小。 一般情况下，标准离差率越大，资产的相对风险越大；标准离差率越小，资产的相对风险越小。 标准离差率指标可以用来比较预期收益率不同的资产之间的风险大小。 标准离差率是一个相对指标。 标准离差率是标准离差与期望值之比。 其计算公式为： 标准离差率＝标准离差 /期望值 在课题当中，我们的原始数据是以大量的文件形式出现的，这是一种后缀为 “ DR” 的特殊文件，里面的内容其实就是一个矩阵。 1． 6 Ad Hoc 网络的动态仿真进行优化的思路 Ad Hoc 网络的优化主要是为 了提高软件的运算速度，但是由于 Ad Hoc 网络的本身具有的一些特点，例如，临时性，随机性，不确定性，可变性，无固定中心等。 而影响它的主要因素是路由算法。 所以在这里，我们采用 Dijkstra最短路径算法。 Dijkstra 算法是一种典型的最短路径算法，用于计算一个节点到其他所有节点的最短路径。 Dijkstra 算法是用于计算一个节点到其他所有节点的最短路径，其实质就是就是减少计算的次数。 其实在实际过程中我们要算成千上万次，这样是非常精确的。 那是否存在既减少运算次数又保证运算的准确率呢。 因此在该过程中，我们假设存 在一个相对均匀的或者说稳定的空间区域（即均稳空间），能够使我们在仿真微波通讯时，针对所有属于这个区域的移动终端，我们只需要做一次迭代仿真运算就相当于对它们全部进行了仿真运算。 这样一来，仿真的速度就成倍甚至是更大程度地提高了。 接下来我们需要验证的是这个均稳空间的存在。 从 DR 文件中调出矩阵第三列，求出平均延迟、方差以及均方差，进而求出离散系数， Ratio 比值 (离散系数 ) =均方差 /平均延迟。 假设，信源通过四次反射，一次衍射到达信宿的，接受区域面积 10m2,根据接受点分布密度为 个 / m2，对应的接受区域有 125 个点，用图表的形式表示出个范围所占的个数既信息还原率，通过信息还原率和离散系数确定这条曲线，来确定稳定区间的最大面积。 基于 Dijkstra 算法的 Ad Hoc 网络的动态仿真优化 13 第二章 标准简介 2． 1 WLAN的基本概念和技术要求 随着 Inter 应用的迅猛发展，便携机、 PDA(Personal Data Assistant)等移动智能终端的使用日益增长，给广大用户提供了诸多便利（随时随处自由接入Inter、能享受更多的业务、安全且有保障的网络），成为发展的必然。 在接入速率和适应环境上与 3G 技术互为补充的 WLAN(Wireless Local Area Network) 即无线局域网 迅猛发展，成为新一代告诉无线接入网络 WLAN 是 指应用无线通信技术将计算机设备互联起来，构成可以互相通信和 实现 资源共享的网络体系。 无线局域网本质的特点是不再使用通信电缆将计算机与网络连接起来，而是通过无线的方式连接，从而使网络的构建和终端的移动更加灵活。 由于无线局域网需要支持高速、突发的数据业务，在室内使用还需要解决多径衰落以及各子网间串扰等问题。 具体来说，无线局域网必须实现以下技术要求： （ 1）可靠性：无线局域网的系统分组 丢失率应该低于 105，误码率应该低于 108。 （ 2）兼容性：对于室内使用的无线局域网，应尽可能使其跟现有的有线局域网在网络操作系统和网络软件上相互兼容。 （ 3）数据速率：为了满足局域网业务量的需要，无线局域网的数据传输速率应该在 1Mbps 以上。 （ 4）通信保密：由于数据通过无线介质在空中传播，无线局域网必须在不同层次采取有效的措施以提高通信保密和数据安全性能。 （ 5）移动性：支持全移动网络或半移动网络。 （ 6）节能管理：当无数据收发时使站点机处于休眠状态，当有数据收发时再激活，从而达到节省电力 消耗的目的。 （ 7）小型化、低价格：这是无线局域网得以普及的关键。 （ 8）电磁环境：无线局域网应考虑电磁对人体和周边环境的影响问题。 基于 Dijkstra 算法的 Ad Hoc 网络的动态仿真优化 14 标准简介 是在 1997 年由大量的局域网以及计算机专家审定通过的标准。 规 定了无线局域网在 波段进行操作，这一波段被全球无线电法规定义为扩频使用波段。 1999 年 8 月， 标准得到了进一步的完善和修订，包括用一个基于SNMP 的 MIB 来取代原来基于 OSI 协议的 MIB。 另外还增加了两项内容： 一是，它扩充了标准的物理层，频带为 5GHz,采用 QFSK 调制方式，传输速率为 6Mb/s——54Mb/s。 它采用正交频分复用 （ OFDM） 的独特扩展扩频技术，可提供 25Mbps 的无线 ATM 街口和 10Mbps 的以太无线帧结构接口，并支持语音、数据、图像业务。 这样的速率完全能满足室内、室外的各种应用场合。 但是，采用该标准的产品目前还没有进入市场。 另一种是 标准，采用 频带和补偿编码键控 （ CCK） 调制方式。 该标准可提供 11Mb/s 的数据速率，大约是原有 IEEE 标准无线 LAN 速度的 5 倍，而且 可以根据情况的变化，在 11Mbps、 、 2 Mbps、 1 Mbps 的不同速率之间自动切换。 它从根本上改变 WLAN 设计和应用现状，扩大了 WLAN 的应用领域。 现在，大多数厂商生产的 WLAN 产品都基于 标准。 而本课题研究的 Ad Hoc 网络 正是属于 协议下的网络 ,它们 的工作频率都 是 ，故而在运用 Ad Hoc 网络时候，可以选择 作为标准协议来研究本次课题。 基于 Dijkstra 算法的 Ad Hoc 网络的动态仿真优化 15 第三章 MATLAB 的基本知识与应用 3． 1 MATLAB 的概 述 MATLAB 是一种用于算法开发、数据可视。