OLDM Ad-Hoc 路由协议简介.docx

Eric WangOLDM Ad-Hoc 路由协议简介2009年8月19日Email: eric8136 | Tel: 13366662606 | 王海军Eric WangOLDM Ad-Hoc 路由协议简介OLDM Ad-Hoc 路由协议简介摘要：OLDM (On-demand Light-weight Dynamic Multipath Routing Protocol) 路由协议是针对硬件资源条件苛刻的移动自组网（MANET Mobile Ad-Hoc Network）设计的一种Ad Hoc路由协议。并且适用于移动速度、拓扑结构变化很快的无线网络。OLDM协议创新性地解决了目前流行的路由协议在反复重建路由过程中带来路由效率低下的难题。 OLDM是目前少有的能够支持“多径（multipath）”的路由协议，具有“单径（uniquepath）”路由协议如AODV、OLSR等所不具备的优势。其最主要的特点有：每个节点同时维护尽可能多的到其他节点的路由；路由稳定性好、延时小、更新速度快；路由的维护开销少；路由的选择算法多种多样可以是距离矢量、信号的能量、链路质量以及电源的电量等等；能够根据网络拓扑结构的变化，路由动态地达到最优；没有路由回路；网络吞吐量高；支持的网络的规模大；可扩展性好；所占资源极少（可以运行在只有几十字节内存、4K代码空间的MCU上）。OLDM路由协议可以应用在无线抄表（AMR/AMI）、智能楼宇、智能家居、工业控制、安防、传感器网络数据采集等领域，给用户带来前所未有的新体验。Ad-hoc网络简介Ad Hoc网络是一种没有特定组织结构的自我组织、自我配置、自我控制的无线网络。移动Ad hoc网络也被称作MANET（mobile ad hoc network）是由无线连接的移动设备组网的自制域网络，所有组网的无线设备可以独立的向各个方向移动，因此网络拓扑结构是时刻变化的。MANET网内的每个设备都兼作路由器的功能，担负着寻找路由和转发报文的工作。如何在不停变化的拓扑下维护正确的路由信息是设计移动自组网路由协议的主要挑战。Ad Hoc网络的特点：1. 网络的独立性 Ad Hoc网络相对常规通信网络而言，最大的区别就是可以在任何时刻、任何地点能够快速构建起一个移动通信网络。它的建立不依赖于现有的网络通信设施，具有一定的独立性。Ad Hoc网络的这种特点很适合灾难救助、偏远地区通信等应用。目前，Ad Hoc网络的应用领域日趋广泛，在无线抄表AMR/AMI、智能楼宇、智能家居、工业控制、安防等领域都有着广泛的应用。 2. 动态变化的网络拓扑结构 在Ad Hoc网络中，节点可以在网中随意移动。节点的移动会导致节点间的链路消失和增加，节点之间的物理链路不断发生变化，而且变化的方式和速度都是不可预测的。对于常规网络而言，网络拓扑结构则相对较为稳定。 3. 有限的无线通信带宽 在Ad Hoc网络中节点之间的通信均通过无线传输来完成。由于无线信道本身的物理特性，它提供的网络带宽相对有线信道要低得多。除此以外，考虑到竞争共享无线信道产生的碰撞、信号衰减、噪音干扰等多种因素，移动终端可得到的实际带宽远远小于理论中的最大带宽值。 特别是对于类似无线传感器网络WSN（Wireless sensor networks）来说，由于成本和功耗的原因节点的无线通信带宽一般只有几十kbps甚至几个kbps，而且射频发射功率十分低，一般小于10dBm。4. 电源有限在Ad Hoc网络中，节点均是移动设备。由于节点可能处在不停的移动状态下，节点的能源主要由电池提供，因此Ad Hoc网络有能源十分有限。为了提到节点电池的续航能力，每个节点在待机的情况下需要尽可能的进入睡眠状态。5. 硬件资源有限Ad Hoc网络中的节点数目可能很庞大，可能是成千上万个节点。因此单个节点的成本控制显得尤为重要。一些无线芯片集成的MCU只有不到1K 字节内存，8K Flash空间，硬件资源非常苛刻。6. 分布式网络的特性 Ad Hoc网络可以没有中心控制节点，每个节点的地位均等，节点之前通过协作完成工作。一旦网络的某个或某些节点发生故障，其余的节点仍然能够正常工作。 OLDM路由协议人们对Ad Hoc路由协议和拓扑控制算法的研究已经有20多年的时间，提出了超过100种的路由协议。可以按照不同的特性分成不同的种类：自适应/非自适应；主动（路由表驱动）/被动（按需）/混合；距离矢量/链路状态；平面/分级/分簇；基于地理位置/基于方向；统一（节点地位均等）/非统一（有特殊的节点）；全连接/部分连接；基于历史/基于预测；单播/广播；反向链路（link-reversal routing）/源路由（source-routing）；单径（uniquepath）/多径（multipath）。路由的选择方式也有很多种：电源的电量/信号的能量/链路的稳定性/最短路径/链路状态/距离矢量/反向链路/多径/方向/地理位置等。请参考:http:/en.wikipedia.org/wiki/List_of_ad-hoc_routing_protocols；http:/wiki.uni.lu/secan-lab/Ad-Hoc+Protocols+%28$28%29Classification%28$29%29.html。OLDM是根据移动无线自组网的特点为由硬件资源匮乏的无线节点组成的超大规模网路精心设计的轻量型、高性能、低开销、高可靠性的路由协议。该协议能够在不停变化的网络拓扑结构中选择最佳的路由，路由的选择方式（算法）可以根据实际需要灵活配置如：距离矢量、信号的能量、链路质量以及电源的电量等等。OLDM路由协议的特点：1. 多径（multipath）OLDM中的每个节点同时维护尽可能多的到其它节点的路由。“多径”会大大提高路由的稳定性，将路由的重建开销降低到最低。如下图所示的网络拓扑结构：上图中的连线代表两节点之间有直接的无线链路，如果节点A向节点H发送报文，则可能的路径会有9种：A-B-E-H, A-B-F-H, A-B-G-H, A-C-E-H, A-C-F-H, A-C-G-H, A-D-E-H, A-D-F-H, A-D-G-H。如果B, C和E, F四个节点同时移动位置或者出现意外断电，A和H之间仍然有稳定的路由A-D-G-H，而不需要进行路由重建。并且可以在A和H按照路由A-D-G-H进行数据传输的同时寻找A-H的其它新的可能路由，使得当A-D-G-H这条链路失效后A-H之间仍然可达路由。这样以来A和H之间的数量传输就会是连续和可靠的。另外，对于“多径”路由协议，可以在多条路径之间动态选择，多条路径并行发送报文，使网络的吞吐量最大化。如果A-H的某条链路或者某个节点发生拥塞，则会旁路发生拥塞的路由，将链路拥塞带来的问题降到最低。我们现在来看单径（unique path）路由协议的情况：网络拓扑结构与多径相同，A向H发送消息，“单径”路由协议会根据某种算法选择A到H的一条最佳路由A-C-F-H，而对别的额外可能的路由视而不见。如果中间节点C或者F任何一个改变位置或者掉电，则会导致A-H的链路不可达。这时必须被动地重新寻找A-H之间的路由。路由的重新建立过程会占用网路的带宽并且在重建路由的期间A-H的链路是不可达的，因此会带来A-H传输的时延。“单径”路由协议由于对潜在的可能链路视而不见，因此不能很好的利用网络的有效带宽。同时在应对链路拥塞、QOS等问题的解决也远远不及“多径”路由协议。 “单径”路由协议相对“多径”路由协议有占用资源少、实现算法简单等特点受到广泛的应用，几乎常见的路由协议都是“单径”路由协议。比如比较流行的AODV、DSDV、OLSR等路由协议。总结：“单径”路由协议的优点：1. 路由表结构简单，所需要的内存开销少2. 代码实现、维护起来比较容易3. 容易处理路由回路（loop）的问题，用报文序号（sequence）等方法 “单径”路由协议的缺点：1. 需要消耗网络带宽和时间去重新建立路由。如果网路的拓扑结构变化的速度很快，需要不停地路由重建，带来不能接受的时延并消耗大量的网络带宽，甚至导致全网瘫痪。2. 不能充分利用无线资源，由于只有一条链路，容易产生链路拥塞，很难保证QOS等特性3. 不适合拓扑结构变化快的移动网络“多径”路由协议的优点：1. 吞吐量高，充分利用无线资源，使用尽可能多的链路并行发送报文，最大程度避免拥塞的发生。2. 路由的建立和维护所消耗有效网络带宽很小、延时少。3. 新的路由会在现有链路失效之前便可以被发现并且建立，能够轻松应对路由的频繁变化。4. 很适合拓扑结构变化快的移动网络“多径”路由协议的缺点：1. 设计复杂度增加，需要实时动态感知网络拓扑结构的变化，动态发现和建立尽可能多的路由2. 怎样处理路由回路（loop）的问题3. 路由表结构复杂度、内存开销增加“多径”路由协议在目前流行的Ad Hoc路由协议中十分罕见，几乎找不到能参考的成熟路由协议的前例。OLDM路由协议采用“多径”路由方式是一种创新性的挑战。综上所述“多径”路由协议的优点，OLDM路由协议比采用“单径”路由协议的AODV等更适合应用在拓扑结构变化快的移动自组网系统中。2. 路由的维护无线资源开销少OLDM在设计上尽可能的减少在路由的搜索、维护等算法对有限的无线资源的消耗。OLDM作为路由协议可以与链路层（LLD）和MAC层紧密结合，并且利用无线信号生来具有的广播特性可以在节点之间进行数据传输的同时进行路由的更新维护。由于OLDM的路由报文很短，可以作为报文头附加在数据报文之前，实现在数据传输的同时对路由的更新维护。进一步减少OLDM路由协议对无线资源的消耗。3. 路由的选择方法多样OLDM的路由选择方式可以多种多样，也可以多种方法配合使用。由于不同的无线自组网的应用场景是可能完全不同。有些网路可能需要最稳定的链路以确保报文的延时抖动小；而有些网路需要考虑节点的电池电量，尽可能的使每个节点的电池消耗达到平衡；有些网络则需要达到最大的吞吐量，需要选择最近和信号强度最佳的路由。OLDM在每发出一个数据报文前都根据需要实时计算出那一时刻的最佳路由。路由的计算方法可以是距离矢量、信号的能量、链路质量以及电源的电量等等。4. 路由动态最优由于移动无线自组网系统的节点之间的位置关系是动态变化的，也许之前建立好的最佳路由可能变得不是最佳、甚至变成无效路由。OLDM可以实时跟踪网路拓扑结构的变化，动态的选择最优的路由，在当前的路由失效之前完成新路由的寻找和建立工作。而不是像常见路由协议如AODV等在链路遭到破坏时才去进行路由的重建工作。因此，OLDM的路由维护是主动、超前的，动态地达到最优。这是OLDM 能够同时维护多条路由的能力带来的结果。5. 没有路由回路避免路由回路的问题是Ad Hoc路由协议需要解决的难题，比如AODV路由协议是不能完全避免路由回路的产生。不同的路由协议为了解决该问题用的方法千差万别，有的使路由协议变得很复杂，占用很多无线带宽。OLDM是一种多径的路由协议，每个节点维护着尽可能多的到其它节点的路由，这些路由往往错综复杂。并且OLDM同时支持多种路由的选择方法，一些路由选择算法本身并不能避免路由回路的产生。解决路由回路问题是OLDM路由协议设计的关键。不但OLDM路由协议能够完美的解决路由回路这个难题，而且OLDM路由协议是对路由回路完全免疫的，在任何时间点网络中都不会产生路由回路。这是也是OLDM路由协议除了采用了“多径”技术之外优于广泛流行的AODV等路由协议地方。6. 路由稳定性好、延时小、更新速度快由于OLDM路由协议采用了“多径”技术，每个节点维护着到达目的节点的尽可能多的路由。并且新路由的发现是在原有路由仍然有效的情况下进行的，具有超前的意识，使得新旧路由的更迭平滑顺畅。相对诸如AODV等路由协议，OLDM的路由算法具有路由稳定性好、延时小以及更新速度快的优势。7. 实现简单所需资源极少OLDM路由协议可以运行在只有几十个字节的内存的MCU上，简单的OLDM的现实仅需要4K字节的代码空间。这样低的硬件资源的要求，可以使OLDM运行在目前几乎所有的嵌入式设备上，在市场上提供最具有价格优势的移动无线自组网的解决方案。8. 网络吞吐量高由于OLDM路由协议采用了“多径”技术，可以同时使用尽可能多的链路发送节点间的数据报文，最大程度避免网络中出现的拥塞情况提高网络的吞吐量。9. 支持超大规模的网络由于OLDM路由协议具有占用资源少、路由算法延时小、可靠性高、网络吞吐量高等优点，因此OLDM路由协议支持超大规模的网络。比如：65535+个节点；255+级路或更大的网络。10. 扩展性好基于OLDM路由协议，可以对路由协议报文进行扩展，容易实现QOS、信道选择、自适应波特率等特性。总结：OLDM路由协议是针对硬件资源条件苛刻的移动自组网嵌入式设备设计的Ad Hoc路由协议，并且适用于移动速度、拓扑结构变化很快的无线网络。该协议具有路由稳定性好、网络吞吐量高、代码尺寸小、无线带宽开销小、支持超大规模网络等特点，具有很多流行Ad Hoc路由协议如AODV、DSDV等不具备的优势。OLDM路由协议能够充分利用移动自组网的特点，解决了很多路由算法设计上的难题。OLDM路由协议可以应用在无线抄表（AMR/AMI）、智能楼宇、智能家居、工业控制、传感器网络数据采集等领域。 10