论文-动态频谱网络路由选择算法

1、一动态频谱网络的路由算法国外发展现状：1针对小规模动态网络的路由协议目前，MANETWG已经公布了一系列的有关基于动态路由的草案，如动态 源路山算法(DSR)、基于反向路径转发的拓扑分发协议(TBRPF)、优化链路状态 路山算法(OLSR)、按需距离矢量路山算法(AODV)、临时按序路山算法(TORA)、 区域路山算法(ZRP)；此外，研究还提出了许多可应用于Ad hoc网络的路山协议, 如LI的序列距离矢量路山算法(DSDV)、无线路山协议(WRP)、陆标路山协议 (LANMAR).位置辅助路曲(LAR)、鱼眼状态路山算法(FSR)。这些路山协议根据所采用的基本路山机制的不同，可分为基于链路

2、状态的路 山协议、基于距离矢量的路山协议、源路山协议及反向链路协议：按照网络逻辑 结构的不同，可分为平面结构的路山协议和分层结构的路山协议；按照路山发现 策略的不同，可分为表驱动路由协议、按需路由协议以及混合路由协议。2大规模动态网络选路算法的进展对于中小规模(通常为儿十个节点)动态网络路由协议的研究已取得了重要 进展，而大规模动态网络的路山技术是该类网络研究的一个难点，它是指可以支 持数白到数千个网络节点的路山算法。国际上早期的一些初步研究结果，如 Santivanez等人提出的基于链路状态法的模糊链路状态(FSLS)算法，研究了节点 数为100400时的部分性能；Woo和Singh提出了一

3、个基于位置修正的SLURP算 法，研究了节点数为501000时的算法性能；JinyingLi等提出了基于区域的网格 (Grid)系统，研究了 100600个节点时的算法性能；Rahul Jain等人提出了基于地 理位置的路由算法，研究101000个节点的算法性能。现有的路山协议或者利用全网泛洪(Global flooding)或者利用分层的方法完 成路山的发现。但是，前者山于开销太大并不适合大规模的网络：后者在分层的 过程中需要交互大量信息，而且可能山于节点的移动和可用频谱资源发生变化造 成性能的急剧恶化。为了克服这些缺陷Nitin Nahata等人提出了一种基于连接 (Contact)点的适

4、用于大规模动态网络的髙效的路山发现策略。它基于“小世界 (Smallworld)W概念，釆用了一种混合的方式：在节点的R跳(通常是35跳)围 采用先验式的路山算法，如DSDV,而在R跳以外通过Contact点进行反应式的路 曲发现。Contact点是一些捷径点，它通过减小分割度来把网络划分成为一些“小 世界”。3基于协同通信的路由协议Beres E, Xie Fang, Khandani A等人在各自的论文中提出利用节点间的相互 协作进行数据通信。它充分利用了无线电波的全向传播特性，使无线网络中的节 点相互协作形成了虚拟的天线阵列来获得传统多输入多输岀天线技术的空间分 集增益，当前协同通信的主

5、要方式有：编码协同，放大中继，解码中继等方式。 相对于其他协同方式，编码协同方式将协同通信技术和信道编码技术相结合，在 不消耗更多系统资源(带宽等)的前提下获得完全的分集增益。U前，基于协同技术的路山可大致分为两类，分别是基于能量的路山策略 和基于带宽的路山策略。基于能量的路山策略主要针对单个源和LI的节点的应用 环境，在保证源节点发射信号在接收节点处能达到接收信噪比门限的基础上，通 过为协同节点最优化地分配功率，从而达到降低网络总能量开销的H的。基于带 宽的路山策略主要是通过引入协同通信技术，以最大化源节点到LI的节点间路径 的带宽为LI标完成路山决策。协同技术在该种路山机制中主要有两种应用

6、方式。 一种是在选择好一条源到H的节点路山的基础上，通过在每一跳节点间根据对带 宽的改善程度有选择地进行协同，达到提升路山传输能力的U的。这种方式可称 为基于协同的路山。另一种方式是在路山选择的同时就考虑到协同技术对每跳传 输带宽的影响，从而决定每跳传输是否采用协同通信技术，并选择该情况下带宽 最大的路山进行数据传输。该方式称为动态协同路山。二现有动态网络路由协议的介绍和特点分析几种类型的路由协议1 先验式(proactive)和反应式(reactive)2平面型(flat)和层次型(hierarchical)3单路径型(single path )和多路径型(multipath)4 GPS辅助

7、型(GPS Assisted)和非GPS辅助(Non GPS Assisted)型路山协议先验式路由协议网络中的主机通过周期性的交互路山信息得到所有其它主机的路由，而不管 需不需要该路由进行通信。1 DSDV(Highly Dynamic Destination Sequenced Distance Vector Routing)DSDV是先验式距离向量路山协议，基于经典的Bellman-Ford路山机制，其 所做的主要改进是在路山表项中包含了山U的节点指定的序列号，以区分新旧路 山，并避免路山循环。其路山更新既是时间驱动的(周期性更新，可让新加入的节 点及时了解网络拓扑)，乂是事件驱动的(可

8、及时反应拓扑变化)。在具体环境下， 需要在及时性和减少开销之间取得平衡,尤其是在不可黑环境，拓扑频繁变化的 网络中，可考虑只依黑周期性更新。将更新信息分为两类：“完整”信息,包含路由表中所有信息；“增量”信息, 只包含自上一次广播“完整”信息之后的更新容。DSDV不适应快速变化的自组网，不支持单向信道。2 WRP(The Wireless Routing Protocol)WRP (the wireless routing protocol)也是先验式距离向量路由协议。WRP 是在路径发现算法PFA基础上改进设计的，以减少出现环路的次数。WRP的改进之 处在于当节点i监视到与邻居节点j的链路发

9、生变化时，i会检测所有邻居节点 关于倒数第二跳节点信息的一致性，而PFA只检察节点j关于倒数第二跳节点信 息的一致性。在WPR中,每一个节点需要维护4个表：距离表、路由表、链路代价表、消息 中继列表(MRL )。移动节点使用更新消息通知每一条链路的变化,更新消息仅在 邻节点间传递。节点通过接收应答和其它消息来感知其邻节点的存在。如果一个 节点没有更新消息需要发送，它必须定期发送消息以声明其存在。3 FSR(fisheye state routing)FSR是先验式链路状态(LS)路山协议，其U的是通过鱼眼(fisheye)效应对 于较近的节点用较短间隔交换链路状态信息,对于较远的节点用较长的间

10、隔交换 状态信息)，以减少路由信息流量。4 FSLS(Fuzzy Sighted Link State)FSLS和FSR相似，使用了一种叫HSLS(HazySighted Link State)的最优化算 法。即每2k*T时间向2k围的节点发送一个链路状态信息。K表示跳数,T表示链 路状态更新的最小时间间隔。5 OLSR(optimized link state routing)OLSR是一种优化的LS协议，这个协议的一个关键概念是多点中继站(MPR), 仅山被选举为MPR的节点产生LS信息和转播控制信息，而且MPR只需要维护MPR和 以自己做为MPR的节点(MPR SELECTOR)之间的L

11、S更新。OLSR适用于密集型网络，对于稀疏型网络，每个邻节点都成了MPR，则OLSR 就变成了纯LS。6 TBRPF(Topology Broadcast on Reverse Path Forwarding)TBRPF也是一种LS协议。它包括两个模块:邻节点发现模块，路由模块。每 个节点通过拓扑表中的部分拓扑信息计算出一个源树(RT),提供了到所有可达节 点的最短路径。每个节点只向其邻节点通告部分源树，以减少开销。也可有选择 的通告完整拓扑，以提高快速移动网络的健壮性。HELLO消息只报告邻节点状态 的变化，也可减少开销7 STARA(system and traffic dependent

12、 adaptive routing algorithm)STARA协议采用了最短路径算法计算路径，但“最短”路由度量采用了平均 时延，考虑了无线链路的容量和排队时延等因素。其采用的平均时延估测机制不 需要双向信道和节点间的时钟同步的支持。反应式路由协议网络中的每个节点在需要进行通信时才发送路由分组，以减少路由开销。一 般分成两个阶段：路由发现和路由维护。路山发现:当一个节点需要向某个H标节点发送数据时，首先查询其路山表， 如果不存在所需路血就启动一个路山发现过程,通常是广播一个路山请求(RREQ) 分组，当合适的路山被找到，返回一个请求响应(RREP),该过程就终止。或所有可 能的路由排列都已

13、检查过，该过程也终止。路山维护：路山建立后，它就山某种路山维护程序进行维护,直到该路山不 再需要，或通过任何路径都无法访问目标节点。1泛洪路由(1) DSR(Dynamic Source Routing)DSR是一种简单有效的路山协议。数据分组头部包含了完整的路由信息，可 以避免环路。中间节点使用了路山缓存技术以减少了路山发现的耗费，但过期路 由会影响路由选择的准确性。DSR支持单向链路，支持主动应答和被动应答两种链路状态监测方法，不需 要周期性的广播链路状态信息，可减少开销。但因分组头部包含了完整的路山信 息,所以链路利用率低。(2) AODV(Ad Hoc On-demand Distan

14、ce Vector Routing)AODV是基于DSDV的，使用LI的序列号防止环路和计数到无穷大等问题。在 路山发现阶段，当节点需要发送信息而乂没有LJ的节点的有效路山时，启动一个 路山发现过程：向网络广播一个RREQ分组。AODV允许中间节点响应RREQ。发现 路由后，中间节点或H的节点以单播的方式向源节点发送一个RREP分组。AODV 支持单向链路。AODV路山开销小，但要周期性地广播HELLO报文来监视链路状态，要消耗一 定的电池能源和网络带宽。(3) TORA(Temporally Ordered Routing Algorithm)是基于链路反转的路山算法，提供到LI的节点的多条

15、路山，可以传输更高速 的数据。其关键的设计概念是将控制信息局限在发生拓扑变化的区域的少量节点 中。可以处理高密度网络，适应高度动态的移动网络环境，但不支持单向信道，且 TORA算法是基于同步时钟的，所以时钟不同可导致路由故障。(4) ABR(Associativity Based Routing)ABR有两个独特之处:一是依据路曲的持久性和质量来选择路山，二是当路山 失效时，通过路由重组来快速查找路由。(5) SSR(signal stability based adaptive routing)SSR是基于信号强度自适应路由协议。该协议旨在选择连接性最强的路山。SSA山两个互相合作的协议构成

16、：动态路山协议(DRP)和静态路山协议(SRP) c DRP 负责维护信号稳定度表(SST)和路山表(RT) o SST记录邻节点的信号强度。在选择 路山时，将信号强度作为选择依据，以得到稳定性最好的路山。SSR不支持单向链 路。平面受限路由平面受限路山和平面泛洪路III类似,不同的是在路由查找过程中，对请求报 文的传播围进行了限制，以减少路由开销，且速度快，网络可扩展性好。1 LAR(Location-Aided Routing)LAR通过GPS获得移动主机的位置信息来控制路由查询用。提供了两种控制 路山查找的策略：区域策略和距离策略。在区域策略中，只有在限定的路山请求传 播圉的主机才参与路

17、山查找;在距离策略中，通过比较源节点到U的节点的距离 和中间节点到目的节点的距离来决定中间节点是否转发路由请求。2 RDMAR(Relative Distance Miero-discovery Ad hoc Routing)RDMAR山路III查找和路山维护两部分组成。在路III查找时，利用源宿主机间 的网段数来限制路山查找围。在路山维护时，依据主机间的空间关系来确定维护 策略。使用主动应答来监测链路状态。层次型路由协议在分层路山协议中，最常用的方法是将地理上紧密相联的节点组成一个显式 的簇,每个簇选举一个簇头，簇部节点与簇头直接通信，是单跳的,这种方式称为 物理分层。列一种方法是隐式地分层

18、，每个节点属于一个本地围，围外使用不同的 路由策略。围中的节点要进行选路，这种方式称为逻辑分层。1 CGSR(Cluster head Gateway Switch Routing)CGSR是典型的基于簇的DV路由协议，用LCC(Least Cluster head Change) 算法分簇，选簇头,属于两个或多个簇的节点作为网关。网络由三种节点:簇头， 网关,部节点组成。每个节点维护两表：簇成员表,DV路由表。簇成员表记录了 到每个节点的簇头信息，并周期性地广播，表的大小取决于网络中簇的个数。路山 表只维护了到每个簇的簇头的一条路由。2 HSR(Hierarchical State Routing)HSR是基于簇的LS路山协议,通过递归使用簇方法来维护一个逻辑分层结构。 也由三种节点：簇头，网关，部节点组成。节点地址格式为HID(物理节点的 Hierarchical ID),显示了该节点的分层拓扑信息，HID足以将分组传到网络中的 任何目