分布式路由

分布式路由（共4篇）

分布式路由 篇1

0 引言

随着Internet应用和用户的快速增长, 网络需要承载的信息流量也越来越大, 对信息转发设备的性能要求也越来越高。支持大容量的新一代路由器是核心网络运营商的必然选择。新一代路由器需要达到Pbps的吞吐量, 这使得先阶段的单主控的集中式架构的路由器显然很难满足这个要求。基于主控与线卡之间的任务共享机制实现的分布式路由器是一种可行的解决方案。这种分布式路由器在具有满足现实应用要求的极强的扩展性外, 还具有较高的可靠性。

路由管理器是路由器的一个核心软件组件。它连接不同的路由协议模块。在核心路由器中, 路由管理器管理来自不同协议源头的优选路由。如来自OSPF、IS-IS、BGP等协议维护的动态路由及用户配置的静态路由。路由管理器从这些路由中决策出最佳的优选路由指导路由器转发平面的分组数据的转发。

随着路由器之间的连接数量的增加, 路由管理器模块需要管理的路由表的大小也增长迅速。这要求路由有更强的CPU处理能力和更大的存储空间。针对该问题, 以前主要的解决方案是周期性的升级路由器的主控卡或路由器本身。但通常CPU芯片的更新周期会长于互联网流量增长带来的CPU处理能力更新周期。一种有效的替代解决方案是采用分布式的路由器体系架构[1]。但其集中式路由管理器实现方案还不能有效解决路由器主控卡CPU处理能力增长压力需求。本文在分布式路由器体系结构的基础上, 提出一种分布式路由管理器架构, 充分利用线卡的CPU处理能力, 分散对主控CPU的处理能力要求的方式解决上述问题。

1 新一代路由器

第一代和第二代IP路由器基本上是采用单个集中处理器运行所有的路由协议模块, 并通过总线互联多个线卡。路由器的性能主要依赖共享总线的吞吐量和中心处理器的处理能力。因此, 这些路由器很难满足当前互联网的带宽要求。新一代的路由器的引入主要是为了解决上述互联网应用瓶颈[2]。其中, 用交换矩阵替代共享总线, 可以为线卡之间的数据交换提供足够的带宽。如图1所示, 新一代路由器体系架构一般由一组线卡、一组转发引擎和一个主控卡通过交换矩阵互联构成。

其中:

1) 线卡提供多个GE接口。入口网络处理器 (i NP:Ingress network processor) 是一个可编程处理器, 执行分组转发、包分类及流控策略等功能。在i NP中包含一个转发信息表 (FIT:Forward Information Table) , 指导数据分组的转发。同时提取接口输入数据中的信令分组转发到CPU进行下一步的处理。线卡中的入口流量管理 (i TM:ingress Traffic Manager) 将i NP传递过来的分组数据转发到交换矩阵, 利用流量接入控制、缓存区管理及分组调度等手段维护流量的负载均衡。数据分组通过交换矩阵转发到线卡的出口流量管理模块 (e TM:egress Traffic Manager) , 而信令则发送到主控卡。e TM接收到交换矩阵转发过来的数据分组后, 进行分组排序和拥塞控制处理后, 通过出口处理器 (e NP:egress Network Processor) 将分组发送出去。

2) 控制卡主要执行路由协议处理功能, 如BGP、OSPF等协议处理。控制卡接口与线卡结构比较类似, 只是处理器和内存容量的要求更高。

3) 控制卡和线卡通过可扩展交换矩阵互连。交换矩阵由矩阵卡组成, 提供数据交换功能。交换卡实现交换矩阵内的流调度、路径平衡及拥塞管理。每个线卡和控制卡都有一个入端口和出端口与交换矩阵互连。Benes拓扑[3]因其无阻塞的特性是最常用的一种交换矩阵互连拓扑组织方案。

路由器中最重要的一个组件是路由管理器组件 (RTM:Routing Table Manager) 。该组件依据从不同协议学习到的路由数据库构建分组转发信息表, 指导数据分组的转发。对于具有相同前缀的一组路由, 路由管理器按照协议优选级设置选择其中最优的一条路由作为转发信息表条目。路由管理器还需要将路由信息变化、直连链路接口状态变化通告给路由协议。为了实现路由过滤, 还需要与策略管理模块进行交互。

为了使路由器的控制平面具有更好的扩展性, 一些研究将路由协议的部分功能分布到线卡中执行, 将OSPF的会话维护功能分布到线卡中执行。不过, 目前还未见将路由管理器进行分布式实施的相关研究。

2 分布式路由管理器架构设计

2.1 分布式路由管理器组成

如图2所示, 我们建议的分布式路由管理器体系架构中, 路由管理器负责管理路由表和路由策略处理功能, 并向路由协议提供API接口, 以交换路由更新信息并执行路由转发路径的决策处理。

分布式路由管理器由两个部分组成:

1) 线卡中的路由管理器 (LC-RTM) 。LC-路由管理器从本地路由协议实例中获取路由信息, 并基于线卡端口进行局部转发路径决策计算处理。线卡可以根据网络区域的划分以集群的方式组成。服务于同一个网络区域的线卡构成一个线卡集群。

2) 主控卡中的主路由管理器 (G-RTM) 从LC-RTM收集的路由信息, 并进行路由表更新和转发表更新的处理。G-RTM也处理用户配置的静态路由, 以及基于路由的流量工程等功能。

2.2 分布式管理器的主要功能实现

RTM模块的功能主要涉及到链路状态通告、路由分布、转发路径计, Qo S及流量工程相关的处理过程。在本文建议的分布式路由管理器体系架构中, 上述路由管理器的主要功能的实现过程如下:

1) 链路状态通告:在分布式路由管理器架构下, 链路状态数据库存储在线卡中。在分布式架构下, 同一个网络域中的线卡中的链路状态数据库必须保持同步。这个可以在集群中选择一个线卡作为主线卡的方式实现。当一个线卡收到链路状态通告信息, 它将该信息转发到该线卡集群的主卡, 主卡进行链路状态数据的更新以及与集群中其他线卡同步。

2) 路由发布:当线卡检测到一个物理链路状态的改变, LC-RTM会向路由器中的所有线卡通告该变化。并进行路由的重新计算, 并将路由更新通告发送给邻居路由器。

3) 转发路径计算:转发路径的处理时基于路由协议, 对于链路状态路由协议 (如OSPF、IS-IS) , 路径计算可以在线卡集群中的主线卡中执行。而基于距离向量协议将路由更新信息发送给主控卡执行转发路径计算。具体路径计算过程是:路由协议模块从邻居接收到路由更新信息后, 相同线卡上的LC-RTM接收到该通告后, 根据协议类型的不同分别发送到主控G-RTM和线卡集群中的主线卡LC-RTM处理。G-RTM或主LC-RTM通过执行路由算法生成最优路由。该路由通过G-RTM或LC-RTM注入到转发表中。

3 可扩展性评估分析

为了比较分布式路由管理器架构和集中式路由管理器架构的扩展能力, 从以下几个方面进行了对比分析。

1) 交换矩阵中的消息数量:分布式架构和集中式架构中, 通过交换矩阵的消息数量基本相同。在集中式架构中, 所有线卡的链路状态通告消息都要通告给主控的G-RTM。在分布式架构中, 链路状态通告需要发送到主线卡, 只有最优路由会发送到G-RTM。因此, 建议分布式路由管理架构未增加交换矩阵中消息流量。

2) 在集中式架构中, 所有的可用路由都存储在主控卡的G-RTM中, 因此主控卡需要大量的存储空间。在分布式架构中, 可用路由存储在线卡集群中的主线卡LC-RTM中。通过这种分布式处理, 有效降低了主控卡的大存储容量要求。

3) 在集中式架构下, 路由管理器功能集中在主控卡上, 对主控卡的CPU要求极高。在分布式架构中, 一部分路由管理器处理功能分布到线卡集群中的主线卡执行。由于集群主线卡管理的路由容量与集中式主控卡管理的路由容量下, 对CPU的处理要求降低。当集群线卡数量增加后导致主线卡的CPU处理能力不能满足要求时, 可以通过进一步的按层次分布式实施, 降低主线卡的CPU处理能力要求。

4 结语

路由管理器是路由器软件体系架构中的核心关键组件。它对路由器的性能起着关键作用。在路由器中, 通过对该组件的分布式实施, 充分利用线卡的计算和存储资源, 提高路由器的可扩展能力。

参考文献

[1]O.Hagsand, M.Hidell, and P.Sjodin.Design and Implementation of a DistributedRouter[C].Proc.5th IEEE Int’l.Symp.Signal Processing and Info.Tech., 2005:227-232.

[2]A.Csaszar et al.Converging the Evolution of Router Architectures and IPNetworks[J].IEEE Network Mag., 2007, 21 (4) :731-736.

[3]H.J.Chao and B.Liu.High Performance Switches and Routers[J].Wiley-Interscience, 2007:453-460.

[4]M.Leelanivas, Y.Rekhter, and R.Aggarwal.Graceful Restart Mechanismfor Label Distribution Protocol[S].IETF RFC 3478, 2003.

分布式路由 篇2

1 分布式匿名路由的算法

在介绍该路由的算法时, 会牵扯到节点问题, 有源节点、目的节点和中间节点。所谓源节点是充当信源的, 它发送的是原始数据包。所谓目的节点是充当信宿的, 用来接收数据包的。所谓中间节点就是除了源节点和目的节点以外的其它参与数据传输的节点。在分布式匿名路由的算法中, 用目的节点的公钥对数据包实行加密, 这样以来, 目的节点具有了密钥, 其它的节点只能尝试解密, 这一算法在路径发现和路径反向阶段中有明显的体现。

1.1 路径发现阶段

源节点首先向周围的邻近节点发送路径发现数据包, 但是周围的邻近节点不能得知源节点的身份信息, 同时也不能得知目的节点的身份信息, 这也是路径发现阶段的一大特征。另外, 路径发现数据包主要包含以下几个方面:首先是开放性的部分, 主要指路径发现过程中存在着一次性公钥, 每个节点都可以利用一次性公钥进行加密, 这样以来, 该公钥也可以作为路径发现数据包的标识号, 而且具有唯一性;其次是源节点的标识号和目的节点的对称密钥, 它们的加密是通过目的节点的公钥进行的, 与此同时, 源节点可以通过相应的方法获取该公钥, 对称密钥主要针对TPK、PKS等内容进行加密, 对数据具有保护作用;再者是TPK、IDs、PKS等内容, 它们是通过Ps进行加密的, 也就是源节点产生的填充符, 它能够有效的防止外来入侵;最后就是参与路径发现阶段的中间节点信息, 当路径发现包传输到一个节点时, 会做出相应的处理。

1.2 路径反向阶段

路径反向阶段是按照路径发现数据包传送过来的路径进行反向传送, 将路径反向数据包传送到源节点。在目的节点接收到路径发现数据包以后, 会做出一系列的加密处理, 随后生成了路径反向数据包, 并且在路径反向数据包的传送过程中进行逆向依次加密。

2 分布式匿名路由协议的特点

1) 首先协议采用的是分布式路由。分布式匿名路由协议与标准的路由协议相比, 实行起来更加简单方便, 它不需要对网络中整体拓扑结构进行维护工作。它改变了原有的中心管理网络路由, 采用节点分布式进行数据包的传送, 并且进一步减少了变更信息的传送。分布式匿名路由协议收集路由信息的情况有两种:一种是会话开始的时候, 另一种是路径中断的时候;

2) 其次协议能够防止路径劫持。分布式匿名路由协议使路径劫持得到了有效的制止, 确保了信息的安全传输。在进入路径反向阶段之前, 要确保接收节点的有效性, 一定要选择可以信任的目的节点来进行路径发现数据包的接收工作, 只有这样才能确保路径反向阶段的顺利进行, 从而进入数据传送阶段。在数据传送阶段开始前, 要确保源节点成功接收到路径反向数据包。

如果出现了路径发现数据包在恶意节点之间进行传送的现象, 就会导致路径发现数据包无法达到有效的目的节点, 从而阻碍了路径反向阶段的进行, 进而无法进行数据传送, 整个过程无法进行。但是有两种情况可以使数据传送正常进行, 一种是有其它的有效节点的路径发现数据包传送到了目的节点, 使路径反向阶段正常进行, 从而完成整个过程。另一种是恶意节点之间的数据包传送被终止, 使路径发现数据包传送到了有效节点, 整个过程得以完成。从这一点上充分的体现了分布式匿名路由协议的优势, 即便是在数据传送过程中遇到恶意节点, 但是由于协议本身的特性, 保证了数据传输的安全性和匿名性;

3) 再者是协议的安全性。路径发现数据包里面包括的内容很多, 这在分布式匿名路由的算法中也讲过, 其中IDs和PKs使用对称密钥进行加密, 而目的节点的公钥也会对它们实行加密。这种情况之下, 只有目标节点拥有获取所有信息的权限, 从而阻碍了外来攻击行为, 使信息得到了保护;

4) 最后是协议的匿名性。协议的匿名性主要表现在路径发现阶段和路径法相阶段, 在路径发现阶段, 它的匿名性又分为以下几种情况:在源节点的相邻节点进行犯罪时, 它们会清楚的判断源节点的数据包, 但是不能知道目标节点;在目标节点相邻的节点进行犯罪时, 它们能够确定目标节点, 却不能够知道源节点;在中间节点进行犯罪时, 它们什么都不清楚。在路径反向阶段, 它的匿名性也分为多种情况, 情况与路径发现阶段类似, 就不进行详细说明了。

3 结论

随着科技的发展, 越来越多的人们通过互联网进行信息交流, 为此信息的安全性受到了高度重视。在数据传输过程中, 受到了恶意的阻挠和侵害, 传输信息得不到一定的保护, 降低了网络对用户的信誉。为此研究人员不断提高加密手段, 并且提出了分布式匿名路由协议, 这一协议能够有效的防止数据入侵, 为了保护信息不被窃取, 信息在路由器之间进行了加密, 这方便了用户进行信息传输, 提高了信息的安全性, 使网络机密管理进一步加强。

摘要：随着信息化时代的到来, 人们通过互联网交流越来越密切, 在数据传输过程中出现了窃取现象, 这就导致了信息往来的不安全性, 使得用户的隐私及重要机密文件对外泄露。针对这一问题, 我们通过对IP数据包进行加密, 但是仍然存在着信息泄露现象, 为此一些学者不断研究加密措施, 提出了分布式匿名路由协议进行网络机密管理。分布式匿名路由协议可以有效的防止路径劫持, 保护了网络机密, 具有较高的安全性, 在本文中会对它的相关内容进行探讨。

关键词：网络机密管理,分布式匿名路由协议,安全性

参考文献

[1]陈新.匿名通信系统关键技术研究[D].国防科学技术大学, 2010.

[2]孙一品.车载自组网隐私保护关键技术研究[D].国防科学技术大学, 2010.

分布式路由 篇3

车载自组网VANET(Vehicular ad Hoc Network）被认为是应用于未来智能交通系统的最有前景的技术，提供了多类的应用服务，实现了车间短距离通信。如图1所示，VANE中车辆装有车载单元OBU(On-Board Unit），实现了车间通信V2V(Vehicle to Vehicle）和车与基础设施通信V2I(Vehicle to Infrastructure）。有效的V2V通信能够增强车辆行驶安全、提高交通效率[1,2,3,4]。然而，由于动态的拓扑，变化的车速以及不均匀的车辆分布，维持不同簇内的V2V通信存在巨大的挑战。因此，多数路由机制采用广播传输，进而实现快速、实时地分享交通信息。但是，广播传输一方面提高了共享消息的速率，另一方面引发信道频繁的竞争以及数据包的碰撞，导致大量的冗余数据包，即广播风暴问题[5]。这直接影响了V2V通信效率。当车辆广播了一条消息，很有可能邻居车辆之前已经接收了此消息，这就导致消息传输冗余，降低信道资源利用率。

目前，已有较多针对传统的MANET环境下的广播风暴的处理方案的文献资料，但是针对VANET环境的文献较少[6]。多数研究工作是以VANET作为连通顺畅的网络为前提。在间歇式连接的VANET中，设计一个可靠、有效的路由协议仍是一个挑战。为此，提出基于分布式的分簇路由机制（Distributed Clustering-based Routing Mechanism,DCRM）。它充分利用车辆分布不均匀的特性，将邻近的车辆看成一簇，并为每个簇选择一个簇头，由簇头传输数据。DCRM采用源节点对其一跳邻居节点进行簇划分，这种分布式的簇划分有利用消息的快速传输，降低消息的传输时延、提高消息的传输效率。

1 相关工作

在VANET中，通常假定车间通信被分割成多个簇。簇内的车辆能够通过一跳或多跳方式与簇内其他车辆通信，但是，簇与簇之间不存在直接连接，这便形成了基于簇的路由协议[7]，如图2所示。

基于地理位置、移动方向以及其他信息，车辆形成不同的簇。簇提高了消息广播、转发效率，减少了不必要消息的复本的数目，降低了系统开销。Ni等认为每个簇内有三类节点（车辆）[8]：簇头、网关以及成员。网关车辆扮演着簇与簇间的连接角色。簇头车辆是指其通信范围能够遍历到簇内的任何一个节点的车辆。簇内成员就是非簇头、网关的簇内其他车辆。当网关车辆从其他车辆接收到消息，就立即向簇头传递，再通过簇头向簇内成员传输。但是，作者在文中并没有给出簇头的选择过程。Fasolo等提出了智能广播协议[9]。假定网络被分割成不同的分区（Sector）。每个车辆能够估计自己的位置，并且知道自己在哪个分区域。该协议利用竞争机制选择转发节点。尽管该协议看似有效，但是作者并没有证实其网络性能以及系统开销。此外，Luo等也考虑了车辆的位置信息，提出了基于簇的路由协议[10]。将地理区域划分为正方形网格（Foursquare gird）。簇头依据邻近的网格传输数据包。Sun等提出了基于RSU辅助的簇头选择机制[11]。通过部署RSU，并维持RSU与车辆间的连接，进而选择簇头。上述研究并没有考虑车辆的移动信息。实际上，车辆的移动影响了簇头的选择过程以及簇的稳定性。Benslimane等利用车辆的移动方向、车间距离以及信号强度RSS(Received Signal Strength）信息构建簇[12]。Gunter等在簇的碰撞阶段考虑了车辆移动，并且簇头具有最低的移动性以及离邻居车辆的距离最近的特性[13]。此外，Kayis等将车辆分为速度群[14]。在同一个速度群内的车辆在同一个簇内。Koyamparambil等提出了基于簇的MAC协议，形成稳定的簇[15]。利用车辆的位置、移动方向以及车道、速度信息划分簇。Hafeeze等利用相对速度、车间距离选择簇头[16]。据此，本文以分布式方式，并充分结合车辆位置，提出了DCRM。

2 系统场景及约束条件

考虑混合交通场景：车辆的行驶速度随机，车辆分布随机，以接收真实的交通场景。提出的DCRM，基于以下假设：假定有N个车辆，每个车辆标识为υi,i=1,2,⋅⋅⋅,N，其位置坐标为(xi,yi)，本文车辆与节点概念等同，可以互换；所有车辆都具备GPS定位功能和无线局域网络功能（WLAN capabilities）；每个车辆利用GPS系统获取自己的位置；每个车辆通过交互beacon消息，能够获取邻居数；仅当车辆υi与υj的距离dij小于通信范围R，车辆υi与υj的通信链路才被建立。

3 DCRM

提出DCRM有两个目的：避免重播消息，缓解广播风暴问题；快速、有效地进行簇划分。在DCRM中，仅选择部分车辆进行消息转发，降低消息被重传的次数。首先对网络进行簇划分，每个簇产生一个簇头。簇头承担着簇与簇之间的消息传递的任务。提出的DCRM主要分为四个阶段：RTB传输，CTB传输、簇划分以及簇头选择，如图3所示。图3(a）中，源节点（车辆）向一跳邻居节点传输RTB控制包。随后，邻居节点通过设置等待时间轮流回复CTB控制包，如图3(b）所示。源节点接收CTB控制包，从中提取邻居节点的位置信息，并计算邻近车辆间的距离，进行簇划分，并选择离自己最远的车辆作为簇头，如图3(c）所示。最后，源节点向簇头传输数据包，如图3(d）所示。

3.1 RTB传输

当源节点需要传输数据时，先向所有邻居节点传输请求广播RTB(Request-to-Broadcast）控制消息。RTB属于MAC广播包，包含了节点的地理位置信息，约7.5 B。

3.2 CTB传输

一旦接收到RTB消息，车辆就计算离源车辆的距离d,d能够用于计算退避时间tw:

式中：rtx为传输半径；CWmax,CWmin分别表示竞争窗口的最大、最小尺寸。

当退避时间tw计时完毕，车辆就向源节点回复CTB(Clear-to-Broadcast）数据包，其包含车辆ID以及离源车辆的距离，大小7.5 B。一旦收到有效了CTB数据包，车辆就退出竞争阶段。

3.3 簇划分

通过接收CTB数据包，源车辆获取了邻近车辆的位置以及距离信息，通过测量CTB消息的到达方向DOA(Direction of Arrival），源车辆计算邻近车辆间的距离。如果邻近区域的每两辆车辆的距离小于门限值Dmin，这两辆车辆将纳入同一个簇。Dmin的选择直接影响簇的数量。Dmin过大，每个簇内成员数就越多，若Dmin趋近于零，每车辆能够独立形成一个簇如图4所示。首先源节点对一跳邻居节点的所有车辆依据DOA按降序从“0”开始编号，假定有N个一跳邻居节点，对这些节点进行0至N的编号。设定N×N维零矩阵A，相应矩阵元素Aij的值为1，否则为0，如下所示：

在计算距离时，考虑距离的对称性，即dij=dji。因此，在构建矩阵A时，采用的伪代码如算法1所示。车辆υi与υj间的欧式距离为dij。

算法1：构建矩阵

(1）初始化：i=0;j=1;

(2)While(i<=j)do

(3)If dij<Dminthen

(4)Aij=1;j++

(5)Else

(6)i++;

(7)End if

(8)End while

依据算法1，源节点的一跳区域7个节点，节点间的距离如算法1所示。构建的矩阵A的过程如下：

依据矩阵A，算法2进行簇划分。矩阵A内每一行元素值表示该行所对应的节点离其他节点的距离是否小于门限值。检测连续出现“1”的行（假定i行），然后将该行元素A(i,:)与下一行元素A(i+1,:)值一一对应进行或运算，并进行相加，如式（4）所示。

其中：I表示一维数组。如果I(i)=m表示m个节点构成一个簇，这m个节点的编号分别为i,i+1，…，i+m-1。

以式（3）为例，共检查到有3行出现连续1，并且I(0)=4,I(4)=2,I(6)=1。因此，节点编号0,1,2,3为一簇；4,5为一簇，6为一簇，如下所示：

算法2：簇划分

(1）初始化：i=0;j=1;h=0;sum=0;temp=0;

(2)While(i<=j)do

(3)If A(i,j)=1 then

(4)j++;

(5)Else

(6)i++;

(7)End if

(8)End while

3.4 簇头选择

源节点对源节点进行簇划分后，就给每个簇选择一个簇头CH。每个簇内离源车辆最远的车辆作为该簇的簇头CH。随后，源节点就将数据包传输到簇头。数据包大小约1 526 B。一旦接收到了数据包，簇头就变成下一轮源节点，类似，重复此过程，直接将数据包传输至目的节点。

4 数值分析

4.1 仿真场景

考虑高速场景，其基于中国上海的方形地图，区域面积为15 km2。如图5所示，该地图来源于OSM(Open Street Map）网址，仿真时间为300 s，具体的仿真参数如表1所示。

为了分析提出的DCRM协议的有效性，选择传统的广播协议与基于竞争分布协议CDP[2011]进行比较。

选择数据包传输率PDR(Packet Delivery Ratio）、端到端传输时延EED(End-to-End Delay）以及吞吐量（Through）三个性能指标考察路由机制。数据包传输率PDR表示源节点发送的数据包与目的节点成功接收的比率，是衡量网络拓扑结构中信息包正确接收的性能参数。数据包传输率越大，路由机制的性能越好。端到端传输时延衡量传输效率，时延越短，表示传输效率越好。同时，与BBC[17],SRB[18]进行比较。仿真结果如图6～图8所示。

4.2 仿真结果分析

图6描述了数据包传输率随PDR随节点数的变化曲线。从图6可知，提出的DCRM的数据包传输率优于BBC和SBP方案，随着节点数的增加，优势随之增加。原因在于DCRM充分利用节点的移动特性，通过簇头转发数据，提高路由的稳定性，降低链路断裂的概率，提高数据包传输的效率。

图7显示了吞吐量随节点数的变化情况。从图7可知，DCRM,BBC,SBP的吞吐量随节点数的变化趋势相同。当车辆数少时，BBC的吞吐量略优于DCRM,SBP。这主要是因为车辆密度小，发生信道竞争概率小，采用直接广播的BBC存在优势。然而，随着车辆密度的增加，DCRM的优势突显出来，当节点数达到120时，吞吐量是BBC,SBP的3倍。

图8绘制了端到端传输时延EED随节点数的变化情况。与图7类似，DCRM,BBC,SBP的EED端到端传输时延随节点数的变化情况相同。在车辆密度较大时，DCRM的EED明显下降，比BBC下降约70%。

5 结语

针对车载自组网VANET的消息传输机制问题，展开分析，并提出了基于分布式的分簇路由机制DCRM。DCRM以分布式方式对网络节点进行簇划分。每个簇内邻近车辆间的距离小于门限值，并选择离源节点最远的节点作为簇头CH。簇头CH承担接连簇与簇间的通信，构建了通信的主线。仿真结果表明，提出的DCRM在吞吐量、数据包传输率以及端到端传输时延方面的性能良好。将进一步研究基于簇的路由机制，将其拓展至任何一个先应式路由协议，进而提高路由协议的性能。

摘要：车载自组网(VANET)是一种将高速移动车辆作为通信节点的自组网,动态的拓扑结构致使传统的自组网路由机制不再适用。为此,提出基于分布式的分簇路由机制(DCRM)。DCRM首先引用RTB/CTB握手策略,源节点利用RTB/CTB数据包,获取其一跳邻居的信息,然后源节点根据每两个邻近节点间的距离小于门限值的原则,以分布式方式对这些邻居节点进行簇划分。随后,将每个簇中选择一个离源节点最远的节点作为簇头,源节点将消息传输至簇头。接收消息后,簇头成了源节点,重复此过程直至消息传输至目的节点。仿真结果表明,提出的DCRM提高了消息传输效率、降低了消息传输时延。

分布式路由 篇4

无线传感器网络 (Wireless Sensor Network, WSN) 是部署在监测区域内大量的传感器节点以自组织方式构成的无线网络。WSN具有展开快速、抗毁性强、检测精度高、覆盖区域大等特点, 在军事、航空航天、环境监测等领域具有广阔的应用前景。但传感器节点在计算、通信能力及能量等方面都十分有限, 再加上部署环境多在人们不易到达的地方, 使得节点的更换和充电也较难实现。因此, 如何减少节点能耗、延长网络生存时间是目前研究的热点问题[1]。对此, 国内外学者提出了一系列的解决方案, LEACH (low-energy adaptive clustering hierarchy) 协议提出了分簇思想, 实现了载荷均衡[2];HCCM协议采用了正六边形分簇的方式, 实现了多跳传输[3]。这两种协议都是先确定好簇的划分, 再收集数据, 这样划分的灵活性不强, 可能造成不必要的资源浪费, 而且, 在大规模无线网络环境中, 簇头与基站之间的距离一般较远, LEACH采取簇头与基站单跳通信的方式将会造成因簇头能量不足, 无法与基站通信而产生“死亡簇”的情况[4]。虽然在HCCM中簇头与基站之间通信时采用多跳方式, 节省了能量, 延长了簇的生命力, 但这种做法会使得离基站近的节点因为转发大量数据而过早耗尽能量, 从而失去工作能力。

为了改善这些情况, 本文提出了基于事件触发的六边形分布式分簇多跳路由协议, 该协议采用6个点构成六边形, 这种方式增加了网络的容错性, 使簇内成员能够灵活地被簇外成员替换。HDCMET协议由事件触发节点, 只有当事件进入监测区域, 才能使位于监测范围内的节点被激活, 而其余节点仍处于休眠状态。此外, HDCMET协议使用编码分区的方式, 将信息从簇头向基站多跳传输。 Matlab仿真结果表明, 在大规模随机分布的无线网络中, HDCMET协议能增加节点使用率, 有效延长网络生存时间。

1分簇多跳路由协议

1.1网络模型

假设有大量传感器节点随机均匀分布在一个正方形区域内, 基站的位置位于正方形区域的一角上。在网络建立之初, 基站会根据各节点的位置, 设置一个标志 (用0、 1、2…表示, 数字越小表示距离越近, 基站标志为0) , 基站将与其距离相近的节点用统一的标志表示出来, 并通过广播的形式将标志发送给各个节点。

结合HDCMET协议的特点, 现对无线网络传感器作如下假设[5]:1网络中的全部节点是随机分布的, 初始能量相同, 节点的坐标由定位算法获得;2因为基站不靠电池供电, 这样就可以认为它的能量是无穷的;3节点的发射功率可根据通信双方之间的距离来动态调整;4各个节点的监测半径R0相同并已知, R0不随能量、温度等外界因素的变化而变化。

1.2基于事件触发的六边形分布式分簇算法

当事件进入监测区域后, 处于休眠状态的传感器被激活。此时, 被激活的传感器先将自己的剩余能量与Er (能量阈值) 进行比较, 当小于Er时不发送自身位置等信息, 当大于或等于Er时才广播自己的位置、ID号和剩余能量。当节点接收到其余节点发来的信息时, 先提取剩余能量, 将其和自身保存的最大能量Emax进行比较, 如果大于Emax, 则修改最大能量值, 并保存其位置信息;如果小于等于Emax, 则丢弃该信息[5]。被事件触发的传感器数目有限, 这样可以保证经过一轮比较后, 在所有被触发的节点中, 最大能量节点的信息是一致的。所以, 选取出来的簇头不用进行声明, 其余节点可以及时向簇头发送数据。而后, 簇头收集其余各节点发来的信息, 根据它们的距离、剩余能量和数据采集量选择出最接近正六边形的5个节点。 具体算法如下:

根据正六边形的几何特性, 构建的正六边形是以检测半径为边长。簇头先以自身为圆心, 以监测半径R0为半径, 选取在该范围内的节点, 再利用公式 (1) 对节点进行筛选。公式 (1) 的具体算法为:

设节点i的剩余能量为Ei, 数据采集量为Si,

其中, Pei= E0/E;Psi=Si/S0;.E0、S0分别为初始能量和假定最大数据传输量, α和β分别表示Pei、Psi的权重, 且α=0.6, β=0.4。

簇头选择距离最接近R0且Pi最大的两个节点, 作为与簇头相邻的节点, 而后这3个节点利用公式 (1) , 分别找与其距离为2 R0的节点。当完成筛选后, 与簇头相邻的两个节点把选择的结果发送给簇头。簇头接收到这些信息后, 将选择的结果广播出去, 未被选中的节点进入休眠状态。这样建立的六边形最接近正六边形, 其监测面积约为

当节点的剩余能量小于等于Emin (最低能量值) 时, 节点停止采集信息, 并唤醒最近的节点, 使其代替自己继续工作。新进入的节点先主动将自己的位置和ID号发送给簇头, 让簇头明白之前的节点已经失效, 而后, 新节点直接进行数据采集, 把数据发送给簇头。在替换过程中, 不必担心数据采集不完全, 因为6个节点采集的数据高达5.6%左右的冗余度, 可以允许部分节点的位置偏移。但如果簇头的能量小于或等于能量阈值Er, 则其会广播发送重新竞争簇头的信息, 簇内的5个节点接受到这个信息, 则停止数据采集。之前被事件激活的簇外节点再次激活, 进入下一轮的簇头选择。

1.3多跳路由选择算法

节点编码是一种新型节点位置标识方式, 融合了编码和路由选择的概念, 可以在数据传输中减小传输距离, 降低能耗, 减缓信号衰减的速度[6]。基于这一观点, 本文提出基于节点编码的多跳路由算法。

在网络成立之初, 基站会收集各个节点的位置信息, 并以自身为圆点, 以节点的监测半径R0的整数倍为半径, 依次编号。即半径为R0时编号为1, 半径处于R0与2R0之间编号为2, 以此类推。

已知基站对各节点的编号, 当某一标志的节点 (簇头) 要向基站发送数据而自身能量不足以将数据发送过去, 即Er

1.4能耗分析

节点的能量消耗主要在于数据的传输和处理。对于服从四次方衰减的无线电, 每100m距离上传输lkb数据所消耗的能量大致相当于在100MIPS/W的处理器上执行300万个指令, 即节点的数据处理能耗要远小于数据收发能耗, 因此, 本文主要考虑数据收发能耗。

结合HDCMET协议的分簇特点, 根据通信双方的位置, 可分为簇内通信和基站通信。在簇内通信中, 簇内成员会根据其与簇头的距离调整发射能量, 并以单跳的形式进行传输。在与基站通信时, 簇头采用多跳路由算法, 在其最远发射范围内选择合适的节点, 进行下一跳传输。

本网络采用无线通信方法, 通过设置传输距离门限d0, 分别采用自然空间模型和多径衰落模型, 假设节点发送k bit数据, 数据传输距离为dm, 此时消耗的能量Etx为[7]:

传感器节点接收k bit数据所需要的能量Erx为:

其中, Eelec是发送电路和接收电路的能量消耗;εfs和 εmp分别是自由空间模型和多径衰减模型中功率放大器的能量消耗, d0是传输距离门限, 为R0的两倍, 决定了衰减模式。

2仿真结果与数据分析

HDCMET协议利用Matlab进行仿真, 将HDCMET协议与LEACH协议进行比较, 结果见图3。其中, 相关参数定义为:正方形监测区域边长a=200m, 基站位于 (190, 190) , 节点数目为N=1000, 各个节点的监测半径R0=10m, 节点初始能量E0为2J, 数据包长度 (即最大传输量) S0=5000bit。

由图3 (a) 所示, 采用HDCMET协议传输数据明显多于LEACH协议。因为数据处理具有突发性, 不能事先预测数据传输的路径, HDCMET协议的数据采集是基于事件触发机制的, 能有效应对突发数据的采集和传输, 而LEACH协议是通过事先选择好的路径进行传输, 容易出现路径选择不合理的情况, 降低传输效率。

从图3 (b) 可以发现, 在相同节点数目内, 采用HDC- MET协议存活的节点数明显高于LEACH协议, 而且整体节点的存活时间也长于LEACH。这是由于HDCMET协议是根据事件触发节点进行信息监控和发送, 而不是像LEACH协议那样, 由基站按照时间轮进行统一分簇, 即使没有事件发生, 节点也要接受分簇信息, 避免了不必要的能量消耗。同时, HDCMET协议采用分散式算法, 由节点自身分析、计算并分簇, 增加了分簇的灵活性, 避免了大规模网络中因节点数目众多而造成的重复数据采集问题, 减少了整体节点的能耗, 而且, 数据的冗余性也使簇内节点能够灵活替换, 减少了重新建簇的机会, 节省了能量消耗, 延长了网络的寿命, 从而增加数据传输量, 提升网络性能。

3结语

HDCMET协议在大规模的随机均匀分布的无线传感器网络中, 能明显延长网络寿命, 而且该协议采用事件触发机制, 节省了大量节点。HDCMET是以六边形为基础的, 既保证了数据采集的完整性, 也为其容错性提供了一定的数据冗余[8]。虽然基于事件触发的六边形分布式分簇多跳路由协议对于大规模随机均匀分布的无线传感器网络有较好的适应性, 但是, 由于该协议中分簇划分是由簇头完成的, 这样容易造成单个节点负担较大, 对此还需要进一步深入研究。

参考文献

[1]GUAN XIN, WANG YONGXIN, LIU FANG.An energy-efficient clustering technique for WSN[C].International Conference on Networking, Architecture, and Storage, IEEE, 2008:248-252.

[2]陈静, 张晓敏.无线传感器网络簇头优化分簇算法及其性能仿真[J].计算机应用, 2006, 26 (11) .

[3]李桢, 陈健, 阔永红.WSN中六边形集中式分簇多跳路由协议[J].西安电子科技大学学报, 2012, 39 (3) .

[4]伍小平.传感器网络分簇路由协议的研究与仿真[D].武汉:武汉理工大学, 2005.

[5]YANG YINGTANG, GAO XIANG, CHAI CHANGCHUN, et al.Novel dynamic routing algorithm for energy optimization in WSN[J].Journal of Xidian University, 2010, 37 (5) .

[6]林力伟, 许力, 潘鹏贵.基于网络编码的分簇传感器网络链路容错策略[J].计算机应用, 2010, 30 (1) .

[7]裴晓黎, 刘志坤, 刘忠.事件触发的无线传感器网络动态分簇[J].舰船电子工程, 2012, 32 (2) .