高动态无线自组网路由协议设计

王文 弢，卿利

(中国西南电子技术研究所, 成都610036)

1 引 言

关于无线自组网的路由协议研究有很多,都是针对不同应用需求来设计不同的路由协议[1-3]。比如从路由发现策略出发,可分为先应式路由与反应式路由[4];从网络逻辑视图出发,可分为平面路由与分级路由;从是否使用GPS 系统出发,可分为地理定位辅助路由和无地理定位辅助路由[5]。

本文在充分研究现有各种路由协议的基础上,针对高动态运动节点在进行自组织组网运行过程中,直接采用现有路由协议时将产生网络建立时间较长、数据端到端传输时延无法得到可靠保障,并且由于维护动态网络连接性造成网络开销较大等方面的问题[6],提出一种基于分簇的路由协议,该协议综合借鉴了主动路由协议、被动路由协议和分级路由协议的优点,并能够适应网络节点高速运动、网络拓扑结构快速变化。

2 路由协议设计

高动态无线网络路由协议采用混合式路由协议,将主动式路由和被动式路由进行有机结合。在簇的内部,所有节点周期维护簇内的完整路由信息,保障在簇内通信的响应时间段,属于主动式的路由维护;在簇的外部,采用了按需路由协议,即当节点有数据包发送但没有该节点的路由时,由成员节点向簇首节点发送路由请求消息,簇首节点周期维护邻接簇表,减少簇间通信时的响应时间;簇间网关节点实现簇间通信。

2.1 网络运行过程

网络运行过程中,节点根据网络运行状态,分为以下4 种节点类型:

(1)未明确节点:节点初始入网时,没有明确身份的节点;

(2)成员节点:一般的网络节点;

(3)簇首节点:通过动态选择,簇首节点负责维护簇内路由表和邻接簇表;

(4)簇间网关节点:通过动态选择,选择原则是横跨邻接簇数目最多,为每个邻接簇都要动态选择一个簇间网关节点。

运行过程中,主要处理以下7 种类型消息:

(1)Hello 消息:节点发送hello 消息,用于邻居发现过程。Hello 消息包括本节点地址、本节点身份、本节点邻居节点数目;

(2)本地拓扑通告消息:通过本地拓扑通告消息在簇内部交互,用于创建簇内全网路由表,包括本节点地址、邻居数目、邻居节点地址列表、邻居节点身份、邻居节点状态等;

(3)簇拓扑通告消息:在簇首与簇首之间进行拓扑通告,包括簇首地址、中继簇首地址、簇成员数、簇成员地址等;

(4)路由请求消息:向未知路由的目的节点通信时,如果其节点类型是簇内成员节点,则向簇首发送路由请求消息;如果节点类型是簇首节点,则向簇间网关节点发送路由请求消息;

(5)路由应答消息:用于簇首节点或者簇间网关节点对路由请求进行的应答;

(6)路由错误:用于向使用中断路由的邻居发送错误通告,以防后续数据包的发送失败;

(7)应用数据:各类需要传输的用户数据。

在节点入网、拓扑维护等过程中,网络会自动根据一定原则选取簇首,其状态转移图如图1 所示。

图1 网络运行过程Fig.1 The process of network running

2.1.1 搜索网络

站点完成初始加电,搜索当前网络。如果收到网络成员发送的消息,则网络存在,建立簇首信息,获取通信密钥,完成成员入网。如果超时未收到网络成员发送的消息,则网络不存在,发起建立网络,自己成为簇首,产生通信密钥等安全参数。

2.1.2 入网运行

站点只要加入网络,则可与网络中成员进行通信,并维护路由和簇拓扑结构。

2.1.3 簇首维护拓扑

簇首进行以下拓扑维护处理:成员离开,即超时未收到成员消息或成员主动退网均视为离开本簇,簇首删除成员信息;成员加入,即收到新节点消息,则增加该成员信息;竞争簇首,即有相邻簇首存在,则根据簇首邻居数决定是否放弃簇首身份。

2.1.4 簇成员维护拓扑

簇成员进行以下拓扑维护处理:簇首离开,若超时未收到簇首消息或簇首主动退网均视为簇首离开本簇,簇成员选择新的簇首;取代簇首,当簇成员邻居数大于簇首邻居数一定门限,则自己成为簇首。

2.1.5 静默

成员静默定义为只能接收数据包且不能发送数据包。成员静默状态通知到全网,所有网络成员保留静默成员的路由信息,并正常转发目的地址为静默成员地址的数据包。成员静默超时未收到解除静默或继续静默通知,则删除静默成员路由信息。

2.1.6 退网

网络管理站收到成员发送的退网消息视为成员退网。网络管理站将成员退网消息传输到网络的所有网络成员。网络成员收到成员退网消息,则停止转发所有发往该成员的数据包。

2.2 簇首形成与维护

网络运行开始后,则进行簇形成,每个簇由若干节点构成,每个簇由一个簇首节点,簇首节点与簇内所有节点都是邻居节点。簇形成过程如图2 所示。

图2 簇首选择过程Fig.2 The process of election of cluster head

簇形成是指在网络建立时,网络形成多个簇的网络拓扑结构过程。主要步骤如下:

(1)节点发送hello 消息,初始状态为未确定;

(2)根据消息触发机制,发送hello 消息或者本地拓扑通告消息;

(3)节点接收到簇首发送的hello 消息后,将本节点状态更改为成员,并加入簇;

(4)本节点邻居数是最多的,则本节点为簇首节点;

(5)如果邻居数同样多,则节点ID 号偏小的为簇首节点;

(6)经过一段时间后,没有接收到簇首或者其他节点的hello 消息,则将本节点身份改为簇首。

簇维护是当网络拓扑结构发生变化时进行的簇结构维护过程,引起变化的原因包括有新节点加入簇、节点离开簇、簇首离开、成员节点取代簇首节点等情况。

2.3 全网簇拓扑

全网簇簇拓扑发现通过接收处理簇拓扑通告消息,获取一定跳数范围内簇首及其成员的可达信息,簇拓扑信息包含在簇拓扑表中。主要包括了对两个表的建立与维护。

(1)邻接簇表

簇首维护邻接簇表,记录邻接簇首信息,包括簇首地址、簇间网关地址、当前节点到邻接簇首的跳数。

(2)簇拓扑表

簇拓扑表由每个簇的簇首建立和维护,通过发送簇拓扑通告消息,互相通告每个簇的节点,簇间网关节点记录网络中的簇首和成员信息,包括目的簇首地址、下一跳簇首地址、当前簇首到目的簇首的簇跳数、下一跳簇间网关节点地址、簇内成员地址列表。

2.4 路由计算

通过建立并维护路由表来获得目的节点的路由信息。路由表中主要包括以下信息:目的地址、目的簇首地址、下一跳地址、下一跳簇首地址、流水号、跳数、有效时间。

簇首节点建立和维护簇内路由表的过程类似主动式路由协议;簇间路由表的建立与维护是簇间数据传输时延能够降低的关键,其主要过程如下:

(1)簇间网关节点接收到hello 消息后,将其纳入邻居节点表,如果该节点是成员节点,并通过簇间拓扑消息或者本地拓扑消息管理得知该成员节点对应的簇首节点,则将其与簇首对应,否则簇首为未知;如果该节点是簇首节点,并且是已知簇首节点则将其更新周期重置,如果是未知簇首则新增加簇表项;

(2)簇间网关节点接收到本地拓扑消息后,将本地簇首对应的成员地址全部更新,簇间网关节点会连接有多个簇首;

(3)簇间网关节点接收到簇拓扑消息后,将簇拓扑消息发送到簇首节点,并将本地维护的簇首和簇成员表进行更新。

3 仿真实验及结果分析

为了在实际网络中分析路由协议,采用OPNET进行了协议仿真,网络节点数设置为200 个,节点移动模型设置为随机移动,初始设置每个节点有3 ～7个邻居节点,保持较好的网络连通性,节点传输速率设置为2 Mbit/s,主要针对数据端到端传输时延和网络管理开销进行分析和评估。

应用层业务传输的端到端时延仿真结果如图3所示。

图3 端到端时延Fig.3 End-to-end delay

从图3 可以看出,簇内端到端时延比簇间端到端时延明显小很多,主要因为簇内路由协议采用主动式路由协议,采取周期维护簇内路由表,簇间路由表由簇间网关进行维护,端到端时延较大。

簇间端到端时延随着网络成员数增大变化较为明显,主要是由于网络成员变多以后,形成的簇较多,不同簇的节点之间跳数增加,簇间网关节点经常发生变化,造成端到端时延较大。

网络管理开销指网络中路由及管理信息占总数据量的比例。仿真工作针对包括200 个节点的网络控制开销进行分析,通过改变簇拓扑管理消息维护周期和邻居节点发现周期等参数,通过仿真得出各参数的最优值,实现网络管理开销满足网络设计要求。仿真结果如图4 所示。

图4 网络管理开销Fig.4 Network management overhead

从图4 可以看出,网络管理开销随着节点数的增加有增大的趋势,由于设计较为合理,节点数为200 个时,网络管理开销小于4%。并且当网络节点数为80 个左右时,网络管理开销最低,通过合理控制网络节点数目以及拓扑更新率,能够实现网络管理开销最小。

4 结 论

本文分析了无线自组织网络路由协议的基本分类,着重针对高动态无线网络中对于快速建立网络、数据低时延传输等需求进行分析,并在此基础上进行路由协议设计,提出了基于主动式和被动式相结合的路由协议算法,并针对端到端时延和网络管理开销这两个主要指标进行了仿真分析。通过仿真表明,设计的路由协议在一定范围内基本符合高动态无线自组网运行特点,其数据传输时延基本满足业务需求。下一步还将优化簇间路由协议,使其受到网络节点数的影响更小,同时还将对路由协议涉及到的其他指标进行更全面的仿真,完善路由协议设计。

[1] 史美林, 英春.自组网路由协议综述[ J] .通信学报,2001,22(11):93-103.

SH I Mei-lin, YING Chun.Routing protocols for ad hoc networks:a survey[ J] .Journal on Communications, 2001, 22(11):93-103.(in Chinese)

[2] 王海涛.Ad hoc 网络的体系结构及其设计[ J] .中国数据通信, 2003(8):70-76.

WANG Hai-tao.Architecture construction and design for ad hoc networks[ J] .China Data Communication, 2003(8):70-76.(in Chinese)

[3] Akkaya K, Younis M.A survey of routing protocols in wireless sensor networks[J] .Ad Hoc Networks,2005,3(3):325-349.

[4] IETF RFC 2328,OSPF Version 2[S] .

[5] Xu Kaixin, Hong Xiaoyan, Gerla M.Landmark Routing in Ad Hoc Networks with Mobile Backbones[ J] .Journal of Parallel and Distributed,2003, 63(2):110-122.

[6] Ghanadan R, Tufano P, Hsu J, et al.Flexible Access Secure Transfer(FAST)Tactical Communications Waveform for Airborne Networking[ C]//Proceedings of 2005 IEEE Military Communications Conference.Atlantic City, NJ:IEEE, 2005:1167-1173.