26-Mesh网络中可靠路由的研究.pptVIP

Mesh网络中可靠路由的研究 学生：张宏 导师：张连芳教授 2006年10月 报告提纲 简要介绍mesh网络。 ETX算法 ETT算法 WCETT算法 什么是无线mesh网络 无线Mesh网络（WMN）是由一些固定和移动节点通过无线链路连接而组成的多跳ad hoc网络。WMN具有自组织，自配置的特点，网络中的节点自动的建立一个ad hoc网络并且维护网络的连通性。无线Mesh网络由mesh router和mesh clients这两种类型的节点组成。在无线Mesh网络中，节点既是一个终端，又是一个路由器。当源，目节点超出直接传输范围的时候，其他节点可以作为中继转发数据。 无线Mesh网络的主要的优势 快速部署，易于安装，降低安装成本 多跳无线传输：非视距传输（NLOS）覆盖范围大 网络的健壮性：提供了更大的冗余机制 结构灵活：通信负载平衡功能 能够提供高带宽 ETX（Expected Transmission Count)算法 每个节点周期性发广播包。 每个节点对于它的邻居节点维护一个统计信息，记录在过去 n秒内收到的邻居节点的广播包个数。 在发送广播包时将这些统计信息包含在广播包中一起发送。 802.11的MAC层重传机制 802.11的MAC层重传机制基于简单的停等ARQ机制，即发送了一个无线帧后，只有收到对端的肯定确认后，才能够进行下一个无线帧的发送。 ETX原理 根据统计数据可以得到x到y的发送成功的概率pf和相反方向发送成功的概率pr。 定义p为从x到y一次传输不成功的概率。 P=1-pf*pr 定义s(k) 为从x到y用k次才能成功传送一个包的次数。 s(k)=pk-1（1-p） 从x到y成功传输一个包所需次数定义为ETX ETX=∑k*s(k)=1／1-p=1/pf*pr ETT（estimated transmission time）算法 802.11b可以根据情况的变化，在11Mbps、5.5Mbps、2Mbps、1Mbps的不同速率之间自动切换。 问题的提出： 5.5M速率，丢包率50% 2M速率，丢包率5% 哪个更好？ 高速率即使有50%的丢包率也会比比它更低的速率好。 ETT算法的实现 每个节点周期性地以不同速率发1500-byte广播包。 每个节点周期性的以1Mb/s的速率广播60-byte广播包。 每个节点对于它的邻居节点维护一个统计信息，记录在过去 n秒内收到的邻居节点的广播包个数。 在发送广播包时将这些统计信息包含在广播包中一起发送。 ETT算法的计算 取带宽与其所对应的投递率的乘积，选择其中最大者，ti。 一条路径的端到端的吞吐率为 t=1/∑i1/ ti 原理 ETX=S/B/ETT ETT=S/ETX*B 其中S为包的大小，B为对应的带宽。 一条链路传送一个包的ETT为 ∑iETT= ∑iS/ ti t=S/ ∑iS/ ti= 1/∑i1/ ti 多radio，多跳的mesh网络 优势： 使用了多个天线允许节点收发同时进行，与无线节点只配备一个无线接口相比，理论上数据的转发速率应该有一定的提高。 节点处的多个天线可以分别设置在互不干扰的多个无线频段(IEEE 802.11b/g标准工作频率为2400-2483.5MHZ,并且1,6,11这三个信道互不干扰)或者天线采用不同的802.11标准（802.11a,802.11b/g）。 适应于多radio mesh网络路由算法的要求 应该同时考虑一跳链路的带宽和丢包率。 一条链路增加一跳时，估计整个链路的质量的数值应该增大，即这条链路质量变差。 原因： 1，增加一跳耗费更多的资源。 2，每增加一跳，就增加了传送一个包所需的时间。 应当明确的说明工作在同一频段上的链路之间的互相影响而造成的吞吐率下降。 WCETT 0≦β≦1 我们可以从两个方面来解释这个公式。 把它看成是自己利益和整个网络利益的平衡。 把它看成带宽和延迟的平衡。 参考文献 Richard Draves, Jitendra padhye, and Brian Zill, “Routing in Multi- Radio, Multi-Hop Wireless Mesh Networks”, in ACM Mobicom, 2004 John Bicket,daniel Aguayo,Sanjit Biswas,Robert Morris, “Architecture and Evaluation of an Unplanned 802.11b mesh Network”,M.I.T Computer Science and Articial Intelli