移动自组网中路由协议的分析与研究

吴 院

(深圳清华大学研究院 EDA重点实验室，深圳 518057)



移动自组网中路由协议的分析与研究

吴 院

(深圳清华大学研究院 EDA重点实验室，深圳 518057)

移动自组网是一种由具有自配置功能的移动设备通过无线连接方式组成的网络。近几年来，对无线自组网各方面的研究十分突出，尤其是在灾难救援和执法等领域。一个自然而然的想法就是，将基于位置的操作引进到无线自组网中。在各种应用中，节点的身份认证事实上往往不如节点的位置有用。在可疑的无线自组网中，节点之间甚至不能信任彼此，因此它们的身份必须隐藏。本文将对移动自组网中的路由协议进行研究和对比。

位置；移动自组网；路由；安全

引 言

移动自组网(MANET)是由移动无线设备组成的自配置动态网络。网络中的节点能够独立地向各个方向移动。节点之间的拓扑结构和链路经常发生变化。移动自组网允许用户交换信息而不用考虑它们变动的基础设施。移动自组网在灾难救援、商业和个人局域网等领域有大量的应用。

路由就是指数据包从一个网络传送到另一个网络或从网络中的一个主机节点传送到另一个主机节点的过程。路由功能主要由专门配置的路由器节点承担，常常与桥接技术相混淆。基于网络结构，路由策略可分为平面路由、层次路由和基于地理位置的路由(地理位置辅助路由)[1]。先验式(表驱动路由)和反应式(按需路由)协议属于平面路由，在表驱动路由下每个节点都拥有网络中所有其他节点的路由信息，并且当网络拓扑结构发生变化时更新路由信息。每个节点将路由信息存储在路由表中。反应式协议只有当节点之间需要路由请求和应答时才会建立路由。混合协议就是为了融合先验式和反应式协议的优缺点。

本文将从基本的、基于地理位置的和基于安全的路由协议的分类出发，对移动自组网的路由协议进行一个粗略的研究，主要侧重于各协议优缺点的分析。

1 移动自组网路由协议的研究

1.1 基本的路由协议

(1) 链路状态路由协议(LSR)

LSR[2]是一个基本的先验式路由协议，根据当前条件发现路由，由Dijkstra提出的最短路径优先算法发展而来，其中每个节点都拥有整个网络的拓扑结构图。网络中的所有节点定期更新网络拓扑图，建立一个直连链路状态数据包，并广播给邻居节点。网络中的每个节点广播从它的邻居节点接收到的链路状态数据包，直到每个节点都有相同的路由信息。节点记录下从其他节点收到的链路状态信息，由此建立拓扑结构图，从而找到其他节点的最佳路径。

LSR收敛速度较快，并且能让节点拥有整个网络的拓扑结构图。但是它对存储、CPU处理速度和网络带宽的需求较高。

(2) 目标序列距离矢量路由协议(DSDV)

DSDV是一种先验式路由协议，它通过在路由表项里增加序列号，解决了距离矢量路由中的回路问题。与链路状态协议不同的是，它不能获得整个网络的拓扑图，然而它能容忍网络内部或网络之间拓扑结构的快速变化。每个节点维护着到所有已知的目标节点的路由信息，并定期更新。在路由选择时，通常选取拥有最高序列号的路径，在具有相同序列号的情况下，选择具有最高度量值的路径。DSDV[3]开销很大，即使网络拓扑没有发生变化，也要存储那些不再使用的路径信息。

DSDV对拓扑结构的改变反应迅速，并能确保没有路由回路。它的主要缺点是，大部分的路由信息从不使用，从而开销很大。

(3) 按需平面距离矢量路由协议(AODV)

AVOD是一种反应式路由协议，它仅在需要时才去发现到某个特定目标的路由，并维护这一路由信息。AVOD[4]优于DSR，它能减少在网络中传送的数据包报头的大小，并且拥有路由表。AVOD效仿路由发现和路由维护阶段通过路由请求和路由回复消息。源节点大量发出路由请求消息，网络中的其他节点转播这个请求，从而形成反过来指向这一源节点的路径，当预期的目标节点收到此消息时，它就会回复一条路由回复消息给源节点。

AVOD协议减少了控制信息的开销，并且对网络拓扑的改变反应迅速。其主要缺点是，只有在低拥塞和高密度的网络环境中，才能达到它的最佳性能。

1.2 基于地理位置的路由协议

(1) 最优链路状态路由协议(OLSR)

OLSR[5]是根据MANET的要求，在传统的LS(Link state)协议的基础上优化的。OLSR中的关键概念是多点转播(MPRs)，MPRs是在广播洪泛的过程中挑选的转发广播的节点。传统的链路状态协议每个节点都转发它收到信息的第一份拷贝，同它相比，OLSR很大程度上减少了转发的信息。在OLSR协议中，链路状态信息都是由被挑选为MPRs的节点产生的，这样减少了在网络中洪泛的控制信息，实现了第二步优化。第三步优化是MPR节点只选择在MPR或者MPR选择者之间传递链接状态信息。因此，同传统LS协议相比，在网络中分布着部分链路状态信息，这些信息将用于路由计算。OLSR以路由跳数提供最优路径。这种协议尤其适合大而密集型的网络。

(2)位置辅助路由协议(LAR)

此协议利用位置信息来改进移动自组网中路由协议的性能[6]。通过全球定位系统来获得位置信息。网络中的路由计算仅局限于一个较小的请求区域。此协议与洪泛十分相似，唯一的不同就是只有在请求区域的节点才能发送路由请求。

LAR减少了路由发现的开销，缩小了路由请求洪泛的范围。其主要缺点是，网络中的节点必须知道它们确切的物理位置。

(3) 基于网格的地域群播路由协议(GeoGRID)

GeoGRID依赖于单播协议GRID，其主要用于地域群播。它可以克服基于地址的路由协议的缺点，用来提供位置感知服务。该协议减少了网络拥塞，能够获得最佳的数据到达率。地域群播[7]就是从源节点传递消息到一给定地理区域内的所有节点，它基于位置而不是地址。位置信息只能通过全球定位系统获得。GeoGRID将地理区域分为许多个d×d大小的正方形网格。在每一个网格中，只有一个移动节点被指定为网格的首节点或网关，地域群播就是将消息经由这些首节点从一个网格传到另一个网格。非首节点不用于传播数据包，除非它是源节点。地域群播路由协议可分为两类，基于洪泛的和基于簇的。网关的选择是使用一种选举协议进行。

此协议在因洪泛引起冲突的拥塞网络中能表现出极佳的性能，提供高准确性和低传输成本。

1.3 基于安全的路由协议

(1) 安全感知路由协议(SAR)

该协议是第一个具有QoS意识的路由协议。该协议以基于路由表驱动的多路径方式满足网络低能耗和鲁棒性的要求。它的特点是路由决策不仅要考虑到每条路径的能源，还要涉及端到端的延迟需求和待发送数据包的优先级。为了在每个源节点和汇聚节点之间生成多条路径。需要维护多个树结构。每个树落在汇聚点有效传输半径内的节点为根向外生长，枝干的选择需要满足一定QoS要求，并要有一定的能源储备。这一处理使大多数传感器节点可能同时属于多个树。可以根据没条路径的能源、附加的QoS度量和包的优先级选择某棵树将信息返回给汇聚节点。

它与只考虑路径能量消耗的最小能量消耗度量协议相比，消耗更少；但是，它并不适合大型和拓扑频繁变化的网络[8]。

(2) 安全位置辅助路由协议(SPAAR)

SPAAR的目的就是为了减少路由开销，但是它不能在高风险的网络环境中使用。该协议利用位置统计来提高网络的性能和安全，然而只需要维护未经授权节点的详细位置信息[9]。节点仅接收从它们的一跳邻居节点传过来的路由信息。为了参与到路由中来，每个节点都要有一个公钥/私钥对，一种将它的身份加入到自己和受信任的证书服务器的公钥中的证书。节点只允许接收从它的邻居表中的节点传来的路由消息。捏造的路由信息不能够通过恶意节点插入到网络中，它们也不能造成路由回路。未经授权的节点必须被驱逐出路由计算和发现。此协议的缺点是，处理非对称加密会产生一些开销。

(3) 基于地理位置的隐私保护按需路由协议(PRISM)

PRISM是一种基于地理位置的反应式路由协议。此协议是用来保护网络的隐私和安全不受外部和内部的攻击[10]。PRISM基于AVOD协议，并保留了匿名性。

该协议实现了跟踪性的行为，不传播拓扑信息。协议中，路由请求消息以洪泛方式在目标地理区域中传播，只有在指定区域中的节点才能转发路由应答消息。它使用路由请求和应答的哈希值作为路由标识，用群签名进行认证。相比其它先验式的协议，该协议的路由开销较小，通信选择不依赖于当前网络的拓扑结构。它只会暴露一小部分的网络拓扑，但此协议限制了路由的即时可用性。

(4) 匿名的位置辅助路由协议(ALARM)

ALARM[11]是一种通过满意的匿名性实现安全和隐私的先验式路由协议。它可以抵御外部和内部攻击带来的安全威胁。此协议由群管理节点指定群签名方案，将所有合理的移动节点组成一个群。协议中，每个节点都会创建一个不向其他节点透露的私钥和一个只透露给群管理节点的公钥。然后，每个节点就会得到一个用来验证群签名的公共密钥。

网络中每个节点转发位置公告消息给所有其他节点，其中包含位置，时间戳，公钥和群签名信息。一旦收到位置公告消息，节点就会检查它是否准备好了，如果没有它就会记录下来或是丢弃掉。这样每个节点就能知道其他节点的确切位置和网络的拓扑。节点将消息用会话密钥加密后转发给位置信息已知的目的节点。会话密钥也是用公钥加密。ALARM协议致力于抵御跟踪和Sybil攻击。

2 对照表

通过相关文献的参考和研究，表1对无线自组网中的路由协议做个比较。表中协议被分为先验式和反应式，并对它们路由的基本性质进行了详细说明。同时表中也列出了那些包含安全属性的协议。最后两栏对它们的主要优缺点进行了说明。

表1 路由协议的对比

结 语

[1] Krishna Gorantala. Routing Protocols in Mobile Ad hoc Networks[D]. Umea: Umea University, 2006.

[2] C Adjih, E Baccelli, P Jacquet. Link State Routing In Wireless Adhoc Networks[C]//Proceedings of the 2003 IEEE conference on Military communications-Volume II: 1274-1279.

[3] Guoyou He. Destination-sequenced distance vector (DSDV) protocol[D]. Helsinki: Helsinki University of Technology,2012.

[4] C E Perkins, E M Royer. Ad-hoc on-demand distance vector routing[C]// Proc. of 2nd IEEE Workshop on Mobile Computing Systems and Applications, 1999: 90-100.

[5] Jacquet P, P Muhlethaler, T Clausen, et al. Optimized link state routing protocol for ad hoc networks, 2001: 62-68.

[6] Y B Ko, N H Vaidya. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks[J]. Wireless Networks, 2000, 6(4): 307-321.

[7] Wen-Hwa Liao1, Yu-Chee Tseng, Kuo-Lun Lo,et al. GeoGRID: A Geocasting Protocol for Mobile Ad Hoc Networks Based on GRID[J]. Journal of Internet Technology, 2000,1(2):23-32.

[8] Seung Yi, Prasad Naldurg, Robin Kravets. Security - Aware Ad hoc Routing for Wireless Networks[C]// Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing: 299-302.

[9] S Carter, A Yasinsac. Secure Position Aided Ad Hoc Routing[C]// Proc. IASTED Int'l Conf. Comm. and Computer Networks (CCN '02),2002:329-334.

[10] Karim El Defrawy, Gene Tsudik. Privacy-Preserving Location-Based On-Demand Routing in MANETs[J]. IEEE Journal on Selected Areas in Communications 2011, 29(10).

[11] Karim El Defrawy, Gene Tsudik. ALARM: Anonymous Location-Aided Routing in Suspicious MANETs[J].IEEE Transactions on Mobile Computing, 2011, 10(9):1345 - 1358.

吴院(硕士研究生)，研究方向为计算机网络与信息系统、智能协同通信技术、物联网技术等。

Analysis and Research of Routing Protocols in MANET

Wu Yuan

(Key Laboratory of EDA, Research Institute of Tsinghua University in Shenzhen, Shenzhen 518057, China)

The Mobile Ad-hoc Networks (MANET) are networks with self-configuring capacity of mobile devices interconnected by wireless links. During the last few years, research in various aspects of MANET has been prominent, prompted mainly by military, disaster relief, and law enforcement scenarios. An instinctive footstep is to take up such location-based operation to MANET. In various applications, including military and law enforcement, node identities are not virtually as helpful as node locations. In suspicious MANET, nodes do not even trust each other; hence identities must be concealed. This paper attempts to contribute a study and comparison on routing protocols in mobile Ad-hoc networks.

location; MANET; routing; security

TN929.5

A

珍

2013-07-22)