【作者】 赵传强；

【导师】 刘元安；

【作者基本信息】 北京邮电大学 ， 电磁场与微波技术， 2010， 博士

【摘要】 无线Mesh网络(Wireless Mesh Networks, WMN)的核心功能是路由功能,然而无线传输具有不稳定、不可靠、误码率高、投递率易受干扰等缺点,在多跳无线Mesh网络中进行路由变得非常困难。不同于传统的无线Ad hoc网络,无线Mesh网络的路由设计侧重于静态场景、高网络容量与高可靠性,因此对无线Mesh网络中路由机制的研究面临新的挑战。近年来,一些新的路由思想与路由技术不断被提出,包括基于机会转发的路由策略、基于多路径方案的路由策略等,相应的兼容性与优化问题也应运而生。本论文对机会路由与多路径路由的若干关键技术,包括机会路由的机会转发机制、路由度量设计、多速率控制等,以及表驱动模式的多路径路由等几个方面进行了深入研究,主要的工作和创新点包括：第一,提出了一种基于吞吐量效率的机会路由算法,建立了路由度量与吞吐量和有效转发节点数量的直接关系。通过基于随机过程理论的数学模型,推导出一种基于吞吐量效率的路由度量EAT(Expected Anypath Throughput),从理论上证明了EAT对转发节点数量的约束能力。同时,改进了传统机会路由的ACK应答机制与机会转发机制,提高了应答成功率,降低了由于应答无效造成数据重传的概率。使用动态规划法设计出基于EAT的转发节点选择与排序算法,仿真结果表明,该算法获得了更好的性能表现,EAT的吞吐量相对于ETX提高最高达到48.91%,相对于EN提高达到11.04%。第二,提出了两种多速率机会路由算法：基于端到端时延的多速率机会路由算法与基于最小丢包率的多速率机会路由算法。前者通过引入机会转发时间推导出多速率机会路由度量EEED (Expected End-to-End Delay),在此基础上提出的多速率转发节点选择与排序算法(STMOR算法)能够获得时延最小的转发列表及其对应的传输速率。后者侧重于减小丢包率的目的,结合包成功传输率提出多速率路由度量ETR (Effective Transmission Rate)。给出并证明了基于ETR的节点排序定理,基于ETR的转发节点选择与排序算法(MLA算法),能够选择有效传输速率最大化的转发列表。STMOR侧重于从时延的角度提高转发效率,MLA侧重于减少传输过程中的丢包率进而减少数据包的平均传输数量。仿真结果显示本文提出的两种多速率机会路由算法在同类型的路由方案中获得更好的性能表现。第三,提出了一种基于地理位置信息的机会路由算法。针对传统地理机会路由只考虑源节点到转发节点的链路质量的缺点,结合转发节点的欧氏前进度与转发节点到目的节点的链路质量信息,提出包成功前进度(PSA)的概念。通过分析研究该尺度的性质特点,做出进一步的优化策略：数据包前进效率(PAE)作为路由度量,将包成功前进度与机会转发时间进行了折中。最后的仿真结果表明,本文提出的基于地理位置的机会路由能取得更好的性能表现。最后,第一个提出了基于扩散更新算法的多路径无线Mesh网络路由算法。对经典的扩散更新算法进行了改进,对其中的扩散算法的可行性条件进行了调整,大大减少了扩散更新的数量,并且证明了改进后的扩散更新算法仍然能够保持网路无环。在改进的扩散更新算法的基础上设计了一种表驱动模式的多路径路由算法,阐述了邻居发现、路由建立及路由维护等几个环节的操作流程。通过仿真实验,将本方案与经典的多路径算法及单路径算法进行比较,本方案的性能能够与现有多路径方案相当,优于单路径算法。更多还原

【Abstract】 The kernel function of Wireless Mesh Networks(WMNs) is the routing ability. However, it is very difficult to perform routing in WMNs for the instability, unreliability, high BER, and interference-sensitivity of wireless transmission. Design of routing in WMNs emphasize on static scenario, high capacity and high reliability, which is very different from Wireless Ad Hoc networks. As a result, some new challenges appear when it comes to research of routing in WMNs. In recent years, many novel ideas and technologies of routing have been proposed, such as opportunistic routing(OR) and multi-path routing, followed with some compatibility and optimization issues.A series of key technologies of opportunistic routing and multi-path routing for wireless mesh networks are investigated in depth, including forwarding model, metric design, multi-rate control of OR, and proactive multi-path routing. The main innovative works of the dissertation can be summarized as follows:Firstly, a throughput efficiency based OR mechanism is proposed in order to overcome the problem that the metrics used by current OR protocols can not reflect the throughput capacity directly and restrict the number of forwarders effectively. An analysis model of OR is designed and a metric named Expected Anypath Throughput(EAT) based on the model is proposed. The saction of EAT on forwarders is proved theoretically. The traditional ACK reply mechanism is improved, as a result the PRR of ACK is heightened and retransmissions caused by invalid ACK are reduced. A forwarder selection and prioritizing algorithm is proposed by dynamic programming. Simulation results show that the throughput gain of proposed algorithm is up to 48.91% over ETX and 11.04% over EN.Secondly, two Multi-rate OR algorithm are proposed:an end-to-end delay based Multi-rate OR algorithm and an minimum packet loss based Multi-rate OR algorithm. In the first one, a novel multi-rate routing metric (EEED) is designed by introducing opportunistic forwarding time and a forwarder selection mechanism (STMOR) is designed which can select optimal transmission rate and get a forwarder list with minimum delay. The second one aims at reducing Loss rate, and a multi-rate metric ETR (Effective Transmission Rate) is proposed associated with the propability of successful transmission. The author proves the priority rule of forwarders based on ETR, and designs a forwarders selection algorithm which can obtain a forwarder list with maximum ETR. STMOR emphasizes on heighten forwarding efficiency by optimizing delay, while MLA prefers to reduce loss rate and avoid duplicate transmission. Extensive simulations show that the proposed multi-rate OR’s can achieve better performance compared to others..thirdly, a geographic OR in WMNs is proposed. Metrics using by traditional geographic OR only consider link quality between source and forwarders without considering links between forwarders and destination. In order to solve this question, a concept named Packet Successful Advancement(PSA) is proposed which introduces link quality between forwarders and destination. A further balance policy (PAE) is proposed after analysing the characteristics of PSA, which makes a tradeoff between packet advancement and forwarding time. Simulation results show that the proposed geographic OR performs better and the analysis of PSA and PAE are proved.Finally, a multi-path routing algorithm based on diffusing update algorithm(DUAL) is proposed for the first time. A improvement on traditional DUAL is accomplished, which greatly depress the number of diffusing. And at the same time routing is kept loop free. Then, a proactive multi-path routing based on modified DUAL is proposed and the routing steps including neighbor discovery, route discovery and maintain are particularly expounded. Simulation results show that the proposed multi-path routing can achieve a performance almost equal to current multi-path routing and much better than single-path routing.更多还原