无线自组织网络GDSR的路由算法研

彭玉颜，陈春良，陈新

(福州大学 物理与信息工程学院，福州 350108)



彭玉颜，陈春良，陈新

(福州大学 物理与信息工程学院，福州 350108)

针对无线自组织网络(Ad-Hoc)中DSR路由算法在路由查询时产生的洪泛广播问题，介绍了网关动态源路由协议(Gateway Dynamic Source Routing，GDSR)，着重阐述了该算法的新节点入网路由查询机制、节点路径查询机制、基于优先级的对数函数退避算法等。本文实现了该路由算法，并在实际环境中测试验证了该路由协议。

Ad-Hoc；DSR；GDSR；CC1110

引　言

无线自组织网络(Ad-Hoc)主要用于不便使用现有网络或者通信基础设施的情况，比如临时会议、应急服务、灾难紧急通信、信息采集、军事通信等[1]。如今物联网已起步，无线自组织网络将能很好地运用于物联网中。无线自组织网络的路由协议很多，DSR是常见的一种协议[2]。使用路由协议的网络，系统收敛性效果好，但是容易引起不必要的退避和冲突，如果该网络非常庞大，还会导致网络堵塞、效率低。因此，研究以及优化该路由协议和相应冲突退避算法非常有必要。

1　DSR网络协议

DSR协议帧格式为：固定头部+帧类型+数据+固定尾部。帧类型有路由发现请求帧RREQ、路由应答帧RREP、路由维护帧RRER、应答请求帧ASKP、确认帧ASK、数据帧DATA。DSR的路由发现请求帧RREQ、路由应答帧RREP、路由维护帧RRER主要应用于路由发现维护阶段。

DSR路由协议主要包括路由发现、路由维护、退避策略3部分。其中，路由发现的过程主要是节点发现和寻找通信路径的过程[3]。网络中要通信的节点通过向网络广播路由请求帧RREQ，来寻找到目的节点的路由信息，把经过的中间节点写入自身地址并一跳一跳地广播出去，直至目的节点收到该分组为止，路由发现帧RREQ分组传播过程如图1所示。目的节点计算最佳路由之后，反馈路由应答帧RREP分组至源节点，源节点收到目的节点反馈回来的RREP分组之后，将路由信息保存在自身路由表中，然后就可以与目的节点进行通信[4]。

图1　路由发现帧RREQ分组传播过程

DSR路由协议的特点使其较为适用于移动性不强的网络，又由于DSR网络中不需要维护路由表，导致其路由表内容简单，其节点内存可以选择较小容量，所以可选用较为廉价的硬件实现，大大降低了在实际应用过程中的系统成本。DSR的不足在于会出现洪泛式广播、可能存在陈旧路由、重建路由，将增大系统响应时延、节点容易失去与网络的联系，并且DSR协议的网络规模不能过于庞大[5]。

2　GDSR路由算法

2.1GDSR路由协议的概述

网关动态源路由协议(Gateway Dynamic Source Routing，GDSR)是在DSR路由协议的基础上，增加网关节点、划分广播冲突区域，使得区域中广播只在网关内部转发，其他冲突区域的节点可以通过网关来访问目的节点所在区域的网关，进而获得前往目的节点的路径，同时网络还可以通过网关定时查询和维护节点。在GDSR网络中，节点维护的数据结构有两个表：入网路由表(表驱动路由协议)和通信路由表(按需路由协议)，这使得其拥有入网路由请求和通信路径发现请求两种路由请求方式，因此GDSR路由协议更加可靠。节点在入网时采用入网路由请求应答机制寻找最佳节点作为入网网关(上游节点)；节点在通信路由发现时，采用有限贪婪路径发现机制寻找路径，即通过入网网关节点以及邻居节点查找路径。

GDSR网络选择处于网络中心或者起始状况时的节点作为集中节点，也就是最初的网关节点，新节点通过上游节点或者网关节点进入网络，能在网关所在域进行广播。由于网关节点将网络划分成不同的冲突域，使DSR路由洪泛得到有效控制。图2为GDSR网络示意图。

图2　GDSR网络示意图

2.2GDSR网络的建立

GDSR属于分级式体系结构，适用于有集中节点的网络或者层级型网络，对于采集数据型、通信接口汇聚型、命令控制型网络非常实用。GDSR路由协议在网络建立之初为最初的一个节点，没有其他网络接入，于是选择为网络集中节点，也就是最初的网关节点。有了网络的核心，后续通过该节点接入网络的节点也称为网关节点。与集中节点相连的上游节点如果频度增加(其下游节点变多)，则升级为网关节点。图2中，网络最初的网关节点D为集中节点，网络最初只有B、E、G、F时无其他网关节点，当有A、C通过B加入网络时，B的频度增加，于是，D赋予B为网关节点，A、B、C为单独的一个域，整个网络从星状网变成2级层次星状网。其他新节点通过入网路由请求应答机制选择最佳路径接入网络，使得网络不断变大。当工程应用不同时，集中节点可以自动或者人工选择节点。

2.3GDSR入网路由请求应答机制

新节点加入网络时，根据GDSR入网路由请求应答机制，需要广播入网路由请求包RREQ,接收RREQ对象为上游节点，也就是已经通过的网关节点或者其他已加入网络的上游节点。路由应答时，接收到路由请求包RREQ的上游节点不再进行转发，而是发回路由反馈包RREP。

发送RREQ之后的新节点将接收到一条乃至多条路由反馈包RREP，将所有RREP包存入路由缓存表中；然后将根据各个RREP中的网络号、路由频度、时延等情况进行对比和计算最优路径，将该节点存入路由表中，并向该节点发送路由确认帧RREPP；接着把缓存表直接复制进入邻居节点表，最后新节点填充路由确认帧RREPP，发送给最佳路径。

由于新节点有计算最佳路径的过程，使得网络可以避免有两个冲突域的子网络之间同时产生最优节点，GDSR入网路由请求应答的示意图如图3所示。

图3　GDSR入网路由请求应答的示意图

2.4GDSR路由维护和节点退出机制

路由维护的目的是确定下游节点是否还在搜索网络，避免有限贪婪转发时浪费转发机会、集中节点失去其链接的下游节点等问题，同时，也可以及时了解到节点是否非主动退出网络。GDSR采用网关节点定期查询维护机制。网关节点对所在网络区域的节点进行定期轮询单播查询，如果有节点没有及时回复，那么需要再次广播该节点，在确认该节点已经退出网络时，及时通知客户端。

节点退出机制：当有终端节点主动退出(即需要报停或者某些原因需要拆除)时，如果没有退出机制，会造成所在路径失效，导致上下游节点链路问题，因此在该节点退出网络时，会发出广播退出帧。接收到退出帧的上游节点在收到退出请求后，将本地路由表中该请求节点的路由信息清空，并向路由节点汇报。

2.5GDSR有限贪婪路径发现机制

在DSR路由协议中，在和目的节点通信时，源节点需要知道数据包发往目的节点的路径，此时，源节点根据DSR路由协议的路由发现机制洪泛广播路径发现帧，每个节点收到转发广播之后，如果不是目标节点，则把自己的节点地址加入路径发现帧的路径中，TTL加1，然后转发该帧。采用洪泛广播转发机制的DSR路由协议在路径发现、网络收敛性方面效果较好，但由于接收到转发帧的节点会继续转发，造成洪泛的同时还可能引起路由环路。

在GDSR路由协议中，节点在通信路径发现时，采用有限贪婪路径发现机制寻找路径，即通过邻居节点或者网关节点发现路径。每次向上查询时，路径中就加入该节点地址，当查询完毕就有了完整路径。路径发现机制处理流程图如图4所示。

图4　GDSR有限贪婪路径发现机制流程图

2.6MAC协议退避策略

当网络比较大时，无线节点数量也会很大。由于采用的是同频传输，所以众多节点在路由建立、数据转发时会造成碰撞。利用CSMA/CA机制对信道检测往往会造成连续的退避，增加时延。同时，隐藏终端和暴露终端的存在也增加了冲突的概率[6]：

① 当一个节点重复收到一个分组k次后，若k>4再进行广播，则该报文所能覆盖新区域的期望值小于5%。随着k的值增大，转播分组后所能覆盖的区域就会迅速减小。设定一个门限值，在未转发帧之前若是收到超过门限值C的相同的广播分组，则取消转发,此处C设置为4。

② 当接收节点距离发射节点越近，进行广播转发时所能覆盖的额外范围越小，相反，距离越远，增加的额外范围就越大，能够到达新节点的概率就越大，通过以上观察，对中间节点的广播转发的随机退避时间进行了优先级划分，即距离发射节点近的退避时间长，距离越远退避的时间越短，这样就增加了距离远的终端节点的发送机会，减少了近处节点的发送机会。并且由于退避时间长，很可能在退避过程中收到C个重复的广播分组后而不再进行广播转发[7]。

对于同样的节点数，将退避时间进行分段不但不会增加碰撞的概率，反而使其减小[8]。广播退避流程如图5所示。

图5　节点转发退避流程

2.7GDSR数据中继转发

GDSR网络节点数据中转能力与DSR网络的节点类似[9]，故不赘述。只是在对比收到的数据帧时，会比较路由表项的源地址和网关地址是否是自己的地址，或者网关地址是否与自己的网关地址相同，以确认是否转发。

2.8负载均衡

网络可能会由于路由多跳建立导致节点负载不均衡，使某些节点比较优秀，频繁作为上游节点，在数据抄收、数据传输阶段这些节点频繁转发数据，会造成数据不准确、网络延迟甚至瘫痪，而有些却很少使用，造成资源浪费[10]。因此有必要加入负载均衡机制[11]。

根据网络中上游节点的使用频度Freque来间接衡量路径负载，每个节点维护一个使用频度Freque。在路由建立阶段，上游节点接收到新节点的路由请求包RREQ时，将自身的频度填充进入路由应答帧RREP，然后发送。新节点收到RREP之后，经过对比和计算，选择频度小或者跳数小的上游节点作为最佳路径，相对小的作为次佳路径，并向最佳路径发送RREPP。上游节点收到RREPP之后，将下游节点存入路由表中，并且自身频度Frequ加1，同时向自身上游节点通告增加了1节点，让其频度自加1。自动负载均衡选择最佳路径的步骤、跳数频度负载均衡示意图略——编者注。

3　GDSR路由协议实现

GDSR路由协议应用于CC1110组成的网络时，网络中的单个节点采用CC1110无线单片机。本系统CC1110中心频率设置为433.000 MHz，调制方式采用GFSK，串口数据传输速率设置为57 600 bps，数据速率为250 Kbps，发射功率设置为10 dBm[12-13]。

3.1GDSR路由协议帧结构

在使用GDSR路由协议并采用CC1110无线单片机收发数据时，需要统一的数据帧格式，如下所示：

同步字帧长度N目的地址源地址路由标识序列号数据CRC2字节1字节2字节2字节1字节1字节N字节2字节

网络中的节点在发送和接收信息时都需要填写或者读取通信帧内的信息。

3.2GDSR路由协议标识

新节点在填充路由请求包RREQ时，其帧中的路由标识为0x01，为广播标识；所得到的回应为RREP，路由标识为0x22，为单播标识；收到回复RREP之后发送的反馈RREPP为0x63，为广播标识。贪婪获取路径时，源节点填充路径查询帧CPRQ，其帧中的路由标识为0x60，为广播标识；收到的路径反馈帧CPRP为0x62，为单播标识。数据帧的路由标识DATA为0x88，为单播标识。

3.3GDSR路由表

GDSR是基于网关节点的分级式设计的路由协议，所以在节点的路由表中有网关地址与网络号。GDSR路由表中拥有两种类型，即入网路由表项和通信路径路由表项。信息数据记载了通信路径路由表项的路径。CC1110无线节点的路由表结构如下所示：

节点地址网络号网关地址跳数信息数组频度状态2字节2字节2字节1字节1字节1字节1字节

4　性能分析

采用9个CC1110无线单片机作为网络节点，分别建立DSR和GDSR网络，网络节点拓扑与跳数频度负载均衡示意图相同。实际网络测试容易受到环境、硬件节点的影响，导致统计时个别参数的数据会有偏差，故需要多次做两个网络的满负荷数据包投递实验。根据PC客户端收到的数据包的时间和数量作为参数统计数据，从以下3个参数来讨论GDSR路由协议在无线自组织网络中的性能[14]：

① 数据包传送成功率：当网络稳定后，GDSR网络的数据包发送成功率比DSR的高，这是由于GDSR建立的是有可靠网关、有效退避、双重路由表的网络；但是DSR路由协议的路由收敛能力比GDSR好，所以GDSR成功率不会比DSR高多少。两种协议的数据包传送成功率图略——编者注。

② 网络平均延迟：DSR网络中的节点要通信时，按需发送洪泛路由请求使得网络经常拥塞，造成网络延迟；如果退避策略不优秀，那么容易使得MAC层多次重发的延迟时间更长、网络更堵等。GDSR协议在网络的初期延迟高，但是当网络稳定后，延迟更低，这是由于新协议采用了“区域管理”限制洪泛滥、区分路由入网和路径查询、有效的退避策略的缘故。两种协议的网络平均延迟略——编者注。

③ 路由开销：GDSR网络由于修改了路由查询机制，使得路由开销明显降低。两种协议的网络路由开销略——编者注。

结　语

GDSR路由协议从修改路由选择机制、退避策略、路径查找机制等方面入手，明显改善了网络的拥堵情况，减小了路由开销，缩短了节点的传输延迟，提高了数据包传递的效率。

编者注：本文为期刊缩略版，全文见本刊网站www.mesnet.com.cn。

[1] 程伟明.无线移动自组网及其关键技术[J].数据通信,2002(3):56- 58．

[2] 陈林星,曾曦,曹毅.移动Ad Hoc网络[M].北京:电子工业出版社,2012:4- 11．

[3] 矣昕宝,全海燕,董会升.一种用于Ad-Hoc网络的精简路由协议设计与实现[J].科学技术与工程,2011,12 (11):35.

[4] 鲍传山.Ad Hoc网络DSR路由协议的研究与改进[D].南京:南京邮电大学,2011:1- 42.

[5] 王进,李克.无线Ad Hoc网络DSR协议的优化策略[J].湖南广播电视大学学报,2010(2):66- 57.

[6] 陈国先.PIC单片机原理与接口技术[M].北京:电子工业出版社,2004:109- 117.

[7] 雷占勃,陈新,徐艺文.无线电力抄表系统的传输中继站设计[J].单片机与嵌入式系统应用,2013(8).

[8] 徐磊,方红雨,李晓辉.基于对数函数的Ad Hoc网络MAC退避算法[J].计算机应用,2009,29(1).

[9] 蔡宜飞,陈新.无线抄表系统中继技术的研究与改进[J].通信技术,2013,46(2):45- 47.

[10] 李梅,周继鹏.基于负载均衡的DSR路由协议改进[J].计算机应用,2011,28(1).

[11] YANG Qin,WEN Y Y,ANG H Y.A routing protocol with energy and traffic balance awareness in wireless Ad hoc networks[C]//Proc of the 6th International Conference on Information,Communications&Signal Processing,2007:1- 5.

[12] Texas Instruments.CC1110f32 Data Sheet,2008.

[13] 王振宇,刘清.基于CC1110无线自动抄表方案[J].电脑知识与技术,2008(17).

[14] 王亮,朱秋萍,马丽霞.Ad-Hoc网络DSR路由协议的优化[J].武汉大学学报:理学版,2005,3(51):361- 364.

[15] 周敬祥,李腊元.Ad Hoc网络DSR路由协议的优化[J].计算机应用研究,2006(12):292- 293.

Peng Yuyan,Chen Chunliang,Chen Xin

(College of Physics and Information Engineering,Fuzhou University,Fuzhou 350108,China)

Aiming at the problem of DSR routing algorithm in Ad-Hoc that will generate the flood broadcast in the routing query,the gateway dynamic source routing protocol(GDSR) is introduced.The algorithm of the new node network routing query mechanism,the node path query mechanism and the backoff algorithm based on the priority of logarithmic function are introduced.In the real environment,the routing algorithm is verified.

Ad-Hoc;DSR;GDSR;CC1110

TN92

A

(责任编辑：薛士然2015-11-04)