分类： 系统运维
2010-07-19 09:56:36
AODV Ad-Hoc On-Demand Distance Vector Algorithm （1）
AODV最初提出的目的是为了建立一个纯粹的按需路由的系统。网络中的节点完全不依赖活动路径，既不维护任何路由信息，也不参与任何定期的路由表交换。节点不需要发现和维护到其他节点的路由，除非两个节点需要通讯或者节点是作为中间转发节点提供特定的服务来维护另外两个节点的连接性。
每个移动节点可以通过某些技术来感知邻近的节点，如本地广播hello消息。节点保留有到达其邻近节点的路由表，路由表的组织方式必须有利于优化针对本地活动的响应时间，并提供对建立新路由请求的快速响应。算法的主要目标是：一，仅当需要时才广播路由发现包。二，需要区分本地连接管理和一般的拓扑维护。本地连接管理指与邻近节点相关的连接管理。三，当本地的连接发生变化时，要把这些相关的信息传播到邻近的移动节点。
AODV使用了一个称为“广播路由发现”的机制，该机制在动态源路由协议DSR中也被使用，但做了一定的修改。与源路由不同，AODV依赖于中间节点对路由表项目的动态建立。需要知道的是，若在每个数据包中都携带源路由参数，会导致比较严重的过载。为了使节点间维护的是最新的路由信息，AODV借用了DSDV的目标节点顺序编码的概念。与DSDV不同的是,每个ad hoc节点都维护有一个单调递增的序号计数器，该计数器用于替换路由缓冲内旧的路由项目。所有的这些技术都只是为了能够更有效的利用带宽，并随时对拓扑的变化作出响应，以确保不会发生路由回路。
路径的发现
无论何时，当源节点需要和其他节点通讯，但在其路由表内又没有相关节点的路由信息，源节点就会初始化一个路径发现进程。每个节点都会维护两个独立的计数器。一个是节点序号计数器，一个是广播ID计数器。源节点通过广播一个路由请求包RREQ到其所有邻近节点来初始化路径发现进程。RREQ包含如下域：
参数对
反向路径的设置
除了广播ID外，RREQ中还有两个序号。源节点序号和源节点所知道的最新的目标节点序号。源节点序号用于到达源节点的反向路由，该序号用于表明反向路由的新旧程度。目标节点序号则说明了到达目标节点的路由的新旧程度。显然，一个目标节点的序号若在源节点的缓存内能被找到，则说明到达该目标节点的路由之前曾被源节使用过。
当RREQ从源节点出发到达不同的目标节点时，路径上的所有节点都会自动设置回到源节点的反向路径。为了建立反向路径，节点必须记录来自于它的邻节点的，收到的第一份RREQ的邻节点地址。反向路径路由项目需要维护足够长的时间以便RREQ经过网络期间，能产生一个路由响应包RREP，并通过反向路径回到源节点。
转发路径的设置
最终，RREQ会到达一个节点。该节点可能是目标节点，也可能不是。但该节点已经能够知道如何到达目标节点。接收到RREQ的节点首先要检查RREQ到达路径上的双向链路。若一个中间节点的路由表中有到达目标节点的路由项目，该中间节点就要决定该路由项目是否是当前可用的。通过将其路由表中目标节点的序号与它收到的RREQ中目标节点的序号相比较，若RREQ中的目标节点序号大于它路由表中目标节点的序号，则该中间节点就不能使用它所记录的到达目标节点的路由来响应RREQ，该中间节点还需要重新广播该RREQ。仅当中间节点的路由表中的关于目标节点的序号大于或等于RREQ中目标节点的序号，中间节点才可以对RREQ作出响应。若中间节点没有到达目标节点的当前可用路由，或者它收到的RREQ之前没有被该中间节点处理过，则该节点要通过单播方式发出一个路由响应RREP，该响应包是发送到它收到RREQ的那个邻节点的，而不是发到源节点的。这个RREP包含下列域：
直到一个广播包到达一个能够提供到达目标节点路由的节点时，一个为该RREQ建立的到达源节点的反向路径已经被建立。当RREP返回到源节点，沿着RREP前进路径上的所有节点都将设置一个转发指针，指向RREP所来的方向，并更新从源节点到目标节点的路由项目的超时时间，且要记录目标节点的最新序号。那些不在RREP路径上的节点在超时计数到期后，将删除反向指针。因为并非所有节点都会在前往目标接点的路径上，而这些节点都会建立反向指针，若这些节点最终发现他们无法到达目标节点，这些反向指针必须被释放。AODV中设置的超时时间为3000msec。
收到RREP的节点将会传播它收到的第一个RREP到源节点。若节点继续收到RREP，仅当新收到的RREP中目标节点的序号大于先前收到的RREP中目标节点的序号，或到达同样目标节点的跳计数小于先前收到的RREP中的跳计数，它才更新它的路由信息并再次传播RREP。否则，该节点禁止传播它收到的其他RREP。这个方案有效的降低了RREP传播的数量，并能确保有最新的路由信息。源节点一旦收到第一个RREP就可以开始数据转发，并在数据传输过程中不断更新路由信息，以确保能随时获得更好的路由。
路由表的管理
路由表中除了源节点和目标节点序号外，还存储了另一些有用的信息，这些信息被称为路由项目的软状态(soft-state)。与反向路径路由项目相关联的有个计时器，称为路由请求过期计时器(route request expiration timer)。该计时器的任务是为了清除反向路径路由项目，所有不在源节点到目标节点路径上的节点所维护的这些反向路径路由条目都会在超时后被删除。过期的时间与ad hoc网络的规模有很大的关系。另一个与路由条目相关联的重要参数称为“路由缓存超时(route caching timeout)”，它定义了一个时间段，在该时间段后的路由会被认为是无效的。
在每个路由条目里，那些会接收去往目标节点数据包的活动邻节点的地址也要被维护。一个邻节点在最近的“活动超时(active_timeout)”时间段内至少会产生一个数据包或转发一个数据包到目标节点的邻节点被定义为活动邻节点。维护这个邻节点地址信息的目的是为了当前往目标节点路径上的一个链路断开时，所有活动源节点会得到通告。若节点的一个路由条目被一个活动邻节点所使用，则该路由条目被认为是活动的。从源节点到目标节点的活动路由条目所确定的路径上若有数据包在传输，则该条路径被称为“活动路径(active path)”。需要注意的是，在DSDV中，路由表中的所有路由都被加上了目标节点序号标签，即使在极度无序的数据传输情况下，或者节点具备高速移动性的情况下，这样的做法也能确保不出现路由循环。
一个移动为每个目标节点维护一个路由表条目是有益的。每个路由表条目都包含下列信息。1.目标节点。2.下一跳。3.跳计数（这是一个路由参数）。4.目标节点序号。5.本条路由上的活动邻节点。6.路由表条目过期时间。
每一次当一个路由表条目被用于传输数据包，该条目的超时计数就或被重新设置为当前时间加上“活动路由超时（active_route_timeout）”的时间段.
若给一个移动节点提供了一个新的路由，该移动节点就会把当前使用的路由中的目标节点序号与新的路由中的目标节点序号进行比较。具有较大目标节点序号的路由会被选中。若目标节点序号一样，具有较小参数（跳数）的路由会被选中。
路径的维护
若一个节点没有沿着一条活动路径移动，它就不会影响到去往这条路径目标节点的路由。若源节点在在一个活动会话期间发生了移动，它就要重新初始化一个路由发现进程来建立到目标节点的新的路由。当目标节点或某些中间节点发生了移动，一个特殊的RREP就会被发送到受到影响的目标节点。定期的hello消息可以被用于确保对称链路，同样也可以用于检测链路失效。当然，为了能够大幅度的降低延迟，也可以用链路层的确认包来检测链路失效。如果往下一跳转发一个数据包失败了，也同样可以说明链路失效了。
一旦下一跳不可达，节点就要从断开处的上行链路开始来传播一个RREP，并伴随有一个新的序号，该序号大于先前已知的序号。同时跳计数变成无穷大，并发送到所有活动的上行邻节点。这些活动的邻节点随后就转发该消息到他们各自的邻节点。这个过程一直要持续到所有活动源节点得到关于该断链的通告才结束。这个过程一定是会终止的，因为AODV维护的是没有循环的路由且ad hoc网内节点数量是有限的。
一旦接收到断链的通告，源节点就重新开始路由发现进程。如何确定一个路由是否仍然需要呢？节点可能需要检查该路由是否在近期被使用过，除此之外，还要检查上层协议控制块，看是否还有到指定目标节点的连接仍然处于打开状态。如果源节点或其他在先前路由路径上的节点决定它应该重新建立一个到目标节点的路由，它就需要送出一个RREQ，并附有一个目标节点的序号，该序号大于先前目标节点的序号，以确保建立一个新的，变化过了的路由。若那些节点认为先前的路由仍有效，则这些节点不会回复。
本地连接性管理
无论什么时候，一个节点收到来自邻节点的广播后，都会更新它的本地连接信息，以确保在它的所有邻节点内有包含了这个邻节点。有一种情况，即在一个hello消息的间隔期间内，一个节点没有发送任何数据包到它的所有活动下行邻节点，这个节点就需要给它的邻节点广播一个hello消息，这是一个特殊的主动RREP消息，包含了它自己的ID和序号。节点的序号在hello消息传输时不会发生变化。hello消息在发送该hello消息的节点的邻节点以外是无法被广播的，因为hello消息包的TTL(Time to Live)值是1。所有接受到hello消息的邻节点都会更新它们和发送该hello消息节点的连接信息。收到一个广播；收到一个来自新的邻节点的hello消息或者没有收到来自原有邻节点的allowed_hello_loss的连续hello消息，这就说明本地连接性发生了变化。但从不活动的节点处接收到hello消息失败不会出发任何协议的反应。如果没有从沿着活动路径的下一跳节点收到hello消息，则这个下一跳节点的活动邻节点就需要被通告一个链路失效。
发表于 @ 2007年07月25日 8:22 PM | 评论 (0)
与网格网相关的无线网络相关协议标准
无线局域网IEEE 802.11 WLAN标准
802.11标准最早于1997年提出，它是所有后续802.11系列协议的基础。802.11提供了三种物理信道：红外方式、跳频方式和直接序列扩频方式，数据传输速率为1Mbps和2Mbps，工作在2.4GHz频段。在1999年追加了新的物理规格，相继推出802.11b和802.11a。802.11b规范也称为Wi-Fi，工作在2.45 GHz频段，最大的位速率为11 Mbps，使用直接序列扩频（DSSS）传输技术，并提供3个非重叠信道。802.11a工作在5GHz频段，最大位速率为54Mbps，使用OFDM技术，提供12个非重叠信道。但802.11a和802.11b不兼容。在2003年，一个兼容802.11b的标准802.11g出现了，同样工作在2.4GHz频段，使用OFDM技术，速率达到与802.11a相同的54Mbps，802.11g提供3个非重叠信道。802.11及802.11 a/b/g使用相同的MAC协议，不同的物理层标准。随后出现的802.11i/e/f分别在MAC层上对安全性，QoS和漫游进行完善。其他如802.11h是欧洲版的802.11a；802.11j是日本版的802.11a；802.11k是为方便WLAN网络管理而设；802.11m用于对802.11各标准进行维护；802.11p主要应用于智能交通领域的无线连接；802.11r对802.11的快速漫游进行了改进，将能保证热点间连接的无缝性。802.11n旨在提高效率，增加物理层数据信道的使用，提高速度，以满足高清晰度视频传输、家庭影院等全新应用对数据速率的更高的要求。
2004年的TGs任务组开始征集草案建立802.11s，正式在无线局域网内增加对mesh网的支持。据报道，802.11s在2007年年初已基本达成共识，新标准将于2008年正式推出。
无线个域网IEEE 802.15 WPAN标准
1999年，802.15工作组开始指定WPAN标准。蓝牙是802.15.1标准的基础，即蓝牙1.1标准，运行在2.4 GHz 波段并且传输链路范围从10厘米到10米左右，提供面向连接的和非连接的，即电路交换和分组交换两种连接方式。随后的802.15.1a包括了一些QoS功能，称为蓝牙1.2标准。由于WPAN与WLAN的802.11b/g同样工作在2.4GHz频段，为了避免干扰又制定了802.15.2标准。其后又推出两种通用802.15标准，即TG3制定的802.15.3，也称为WiMedia，使用基于802.11但不兼容的物理层，支持20Mbps以上高速传输，用于多媒体应用。2004年2月，802.15工作组的UWB标准化工作陷入僵局，这是由于intel和motolora在UWB标准的制定上出现了分歧。最终Intel成立了多频段OFDM联盟MBOA，802.15.3a即使用了Intel的MBOA物理层，速率高达480Mbps，MBOA提出了一个新的MAC协议，增加了对网格网和移动性的支持。TG4制定的802.15.4则是低速率，低功耗的标准，俗称ZigBee，在2.4Ghz的16个信道上达到250Kbps，在915MHz的10信道上达到40Kbps，在868MHz的1个信道上达到20Kbps。主要用于传感器网络。ZigBee网络层支持多种网络拓扑，也包括mesh。在mesh拓扑下，一个特殊的称为协调节点的节点专门负责网络的启动和选择关键的网络参数。路由算法使用请求-响应协议来消除优化不足路由。802.15.5正在制定中，其目的在于确定物理层和MAC层机制对网格网的有效性，最终定位于网格网的MAC协议，且不需要ZigBee或IP路由支持。802.15.6也在制定中，但目前还是非官方标准，据报道，该标准将提供G级速率。
无线城域网 IEEE 802.16 WMAN标准
802.16又称为WiMAX，最初的802.16标准运行在10-66GHz频率上，且在视距以内传输。802.16a扩展使用较低的频率，运行在2-11GHz频率，支持非视距传输，服务半径50公里，用于将802.11热点连接到互连网，可作为有线接入和DSL的无线扩展，即常说的最后一英里宽带接入的解决方案。802.16a的载波可以连接更多的客户到单个信号塔，充分的减低了服务成本。802.16d是对802.16和802.16a的修正，分别制定了2-11GHz和10-66GHz的固定宽带无线接入空中接口的物理层和MAC层，针对不同的QoS需求定义不同的MAC层和相应物理层。为了允许在行车速度下连接到Internet，在802.16d的基础上定义了802.16e，并与802.16d相兼容，802.11e运行在2-6GHz频段上，支持漫游和切换。目前认为，802.16标准族主要包含两个主要的空中接口标准。一个是以802.16d为代表的固定宽带无线接入空中接口标准，另一个是以802.16e为代表的同时支持固定无线接入和移动无线接入的空中接口标准。802.16支持时分双工TDD和频分双工FDD两种无线双工方式。根据使用频段的不同，对应不同的物理层技术，即单载波（Single Carrier，SC），OFDM（Orthogonal Frequency Division Multiplexing），OFDMA（Orthogonal Frequency Division Multiple Access）。单载波主要用于10-66GHz频率上，2-11GHz频率上主要采用OFDM和OFDMA。802.16e的物理层实现方式与802.16d基本一致，主要差别是对OFDMA进行了扩展。802.16支持两种网络拓扑，即点对多点和网格网。
移动宽带无线接入 IEEE 802.20 MBWA标准
802.20最初由802.16工作组于2002年3月提出，目的在于实现高速移动环境下的高速率数据传输。该标准运行在3.5GHz以下频段，为以250公里时速移动的客户提供1Mbps以上的数据传输速度。802.20物理层以FLASH-OFDM和MIMO技术为核心，其数据是基于纯IP的分组数据。802.20支持与802.16，802.11的无缝切换。802.11n提供了峰值为100Mbps的速率，但不支持快速移动。802.16e在支持每小时150公里的移动状态下，提供最高达70Mbps的速率。因而在802.11n和802.16e之间，802.20提供了一定的补充。
发表于 @ 2007年07月25日 2:20 AM | 评论 (0)
关于wireless mesh network的一般问题
如何定义无线网格网？它的独特属性是什么？它和无线局域网，ad hoc网有什么不同？当前和未来期望的应用有些什么？WMN的主要问题是什么？
模型和容量
模型一般是由连接性图和干涉图构造的，尽管还有一些限制，很多特性也不易获取，包括MAC的广播特性和断断续续的连接性。目前关于容量有很多种计算方式，包括Gupta和Kumar的理论容量分析，层次模型（Clique Model）和冲突域模型。后两种是目前关注比较多的，因为这两种是模型是单凭经验预估网络容量最现实的办法。路由协议及其参数也是研究的热点，这是因为现实的网络容量非常依赖于路由及其参数的选择。
Multi-Radio和Multi-Channel系统
单信道网络在网络容量和延迟上受到了极大的限制。多信道系统则能提供更大的容量，但只有multi-radio,multi-channel系统才能降低延迟。multi-radio系统方案有多种，必须清楚的了解它们的优势和限制。但是现实的问题必须通过实验来了解，可惜我没有这个条件。了解多信道系统的难点，如干涉问题，路由和信道指派。
拥塞控制，负载平衡，QoS公平性问题
WMN在拥塞控制和公平性方面遭遇了巨大的问题。过大的负载使吞吐量降低。短跳数路由使较长跳数路由发生“饥饿”。更严重的是，当大多数增强的WMN有多重网关时，它们的运行更类似与多个单网关网络。QoS也及其缺乏。要了解拥塞的原因和WMN独特的公平性问题。
部署问题
现实的部署经验告诉我们，部署的模型越简单，使用时遇到的错误更多。这有些不合常理，但现实就是这样。路由参数的确定必须考量在特定的网络测量手段下，希望得到的吞吐量是什么。自组织特性一向被认为是WMN的优点之一，但遗憾的是到目前为止，该特性仍然很缺乏。WMN的部署到底需要考虑些什么？到底如何在实际的系统中实施？
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/zhoujunyi/archive/2007/10/09/1816818.aspx
