大规模MANET路由协议SPDSR的仿真研究

郭一辰，陈 靖，罗 樵，陈桂茸

（空军工程大学 电讯工程学院，陕西 西安710077）

0 引 言

移动 Ad hoc网络（mobile Ad hoc network，MANET）由一组无线移动节点组成，是一种没有任何基础设施、自组织、自愈的网络［2］。及至目前，人们已经提出了多达10～20种Ad hoc网络路由协议，经典的路由协议有DSDV（destination－sequenced distance－vector routing）， AODV（Ad hoc on demand distance vector），DSR（dynamic source routing）等［3－4］。通过前期对这3种协议进行的大量仿真实验及对结果进行的观察分析可以看到，在小规模网络中，DSR的综合性能要优于另外两种协议，但当网络规模扩大即网络中的节点个数增加时，3种协议的性能均有明显下降，其中以AODV和DSDV性能变化最为明显。因此需要一种对大规模网络具有良好支持的新型Ad Hoc路由协议。

本文所讨论的一种新协议——SPDSR，是在 MANET路由协议领域，选择主流反应式路由协议之一的DSR作为研究对象建立起来的。这种新的路由模型在MANET物理拓扑基础上构建一层结构化P2P覆盖层网络，将运行在逻辑命名空间的P2P覆盖层网络协议功能与运行在物理命名空间的MANET路由协议无缝地结合起来，其目的是利用P2P计算模式对大规模网络具有良好支持这一优点，将其有效地应用到无限自组织网络路由技术中，从而实现了网络资源的充分利用。本文设计实现了这一算法，并通过仿真实验验证了该算法在大规模网络中的优越性能。

1 DSR协议和P2P技术

1.1 DSR协议

DSR协议是最早采用按需路由思想的路由协议［5］。其实现方式是中间节点不用维护去往全网所有节点的路由信息。当有分组需要发送并且本地路由表中没有到目的节点的路由时，协议将启动路由发现和路由维护算法，从而实现源节点和目的节点之间路径的发现和维护。

DSR的优点是中间节点不用维护去往全网所有节点的路由信息，而且可以避免出现路由环路。它的缺点是每个数据分组都携带了路径信息，造成协议开销较大。而且也不适合网络直径大的自组网，网络可扩展性不强［6］。

1.2 P2P技术和Chord算法

目前三代主流P2P路由模型为集中目录式P2P网络路由模型（第一代P2P路由模型），非结构化P2P网络路由模型（第二代P2P路由模型）以及结构化P2P网络路由模型（第三代P2P路由模型），其中研究最多应用最广的是结构化P2P网络路由模型［7］。其模型中的每个节点通过存储少量路由信息，实现源节点到目的节点间的消息路由功能。该模型取缔了泛洪算法，有效减少节点消息发送数量，使P2P网络的可扩展性得到了增强。

Chord是最为典型的非结构化P2P网络路由模型［8］。在Chord模型中，系统通过哈希算法给网络中每个节点和资源分别赋予一个标识符，这些标识符按照一定的规则排列形成一个环（如图1所示），环中每个节点具有其自己的路由表（在Chord中被称为Finger table），并通过查询该路由表进行消息的路由和转发。

图1 Chord路由表结构及消息转发过程

1.3 结构化P2P网络路由技术和 MANET路由技术的交叉研究

结构化P2P网络与无线移动自组织网络具有相似之处，见表1。

通过观察研究两种网络的相似性特征可以预测，根据P2P技术与MANET技术的切合点从而产生新的MANET路由协议是可行的研究方向。因此在两个技术领域分别选择Chord模型和DSR协议作为研究对象，为下文对新算法的研究实现提供了技术基础。

表1 结构化P2P网络与无线移动自组织网络相似性比较

2 基于P2P计算模式的MANET路由协议：SPDSR

本节介绍一种基于P2P计算模式的新型MANET路由模型，在主流反应式MANET路由协议DSR的基础上，通过引入基于DHT的分布式命名机制、新型路由表以及一系列优化策略，有效地建立起一个基于MANET架构的完全分布式自组网路由协议——SPDSR。新路由模型实现了DSR和Chord算法的结合，并继承了DSR所有动态特征和优点。

2.1 SPDSR模型基本设计

与DSR一样，SPDSR也是一个基于MANET的网络层路由算法，消息的源节点及目的节点采用IP地址。不同的是，SPDSR为每个节点分配了唯一的节点身份标识（Node Identifier，NID），这些NID都属于同一个连续的哈希环域空间，通过在这个空间上运行P2P网络路由算法，SPDSR有效实现了移动节点间的信息共享和消息通信。图2描述了SPDSR的节点命名机制，其中图2（a）描述了无线自组织网络的结构，图2（b）显示了图2（a）中无线自组织网络所对应逻辑命名空间的哈希环域空间结构。

2.2 SPDSR路由算法

2.2.1 SPDSR路由发现算法

SPDSR路由发现算法通过按需机制查找通往指定目标节点的源路由，路由发现过程一般均由移动节点启动的路由更新过程调用。不同于DSR的是［9］，SPDSR路由发现算法仅查询每个移动节点指定路由表项对应下一跳节点的源路由，并采用多跳路由的方式将路由消息经过多个节点转发至目的节点。SPDSR路由表（PRT，SPDSR Routing Table）的结构如表2所示。

图2 SPDSR节点命名机制

表2 SPDSR路由表结构

在SPDSR路由算法中，每个路由表项负责所有NID属于该路由表项对应环域空间范围（NRI）内目标节点的路由，无需像DSR一样针对每个不同目标节点的路由查询消息进行路由发现，因此SPDSR下广播机制造成的网络流量负担将大大减少。

2.2.2 SPDSR路由表查询算法

SPDSR的路由表查询算法是基于P2P计算模式的结构化覆盖层网络路由查询算法，其采用的路由表查询机制与Chord算法的路由发现机制原理类似。在SPDSR中，每个节点的IP地址通过哈希杂凑运算获得对应的NID和KID，这两个识别码具有严格的一一对应关系，因此只要目标节点存在于网络中，SPDSR就能通过消息在节点间的多跳转发定位目标节点。而这一多跳过程是通过每个节点的无线收发机在其信号传输范围内，与其它节点建立连接完成的。

2.2.3 SPDSR路由维护算法

（1）移动节点的加入（mobile node join）

在移动节点加入网络时，SPDSR不对移动节点的路由表进行初始化，而仅当有某种消息路由需求时，才按需启动路由表项发现机制，实时构建相应路由表项。

（2）移动节点的退出（mobile node departure）

在SPDSR中，节点的退出可分为正常退出和异常退出。对于移动节点异常退出，系统将不采取任何动作；对于移动节点正常退出，系统将进行以下动作：移动节点B首先向其后继节点C和前继节点A发送一个退出请求消息（QREQ），C和A接收到该消息后，将分别更新自己的前继和后继节点，从而使哈希环的完整性得到了保证。

2.3 SPDSR路由算法优化策略

2.3.1 侦听技术

DSR中一个重要的优化策略是侦听技术，即侦听通过本节点转发的数据分组和路由响应分组，从而获取通往网络中其他节点的路由信息。SPDSR继承了这一优化策略，但不同于DSR的是，SPDSR中的节点仅侦听并提取通往本节点路由表项所对应的下一跳节点的源路由信息，有效降低了路由更新和维护开销［10］。

2.3.2 源路由检测机制与phello协议

源路由检测机制和phello协议是为了解决SPDSR中的绕路问题而引入的两种优化机制。源路由检测机制的基本思想就是每个移动节点在发起一次路由查询请求或转发某个路由查询消息时，应首先通过判断目标节点是否存在于路由表项中某条源路由的中间节点之中，如果是，则从该源路由中提取通往目的节点的路由信息，并直接返回给路由查询发起节点。

phello协议采用按需发送机制，仅当某节点需要发起一次路由查询请求或者转发某个路由查询消息时，才向其无线信号范围内的相邻节点发送hello消息以获得相邻节点的列表信息，其目的是降低phello协议对网络造成的路由开销。

总之，通过一系列算法优化策略的引入，进一步提高了模型的路由性能，有效地建立起一个基于MANET架构的完全分布式自组网路由协议。

3 基于NS－2的SPDSR的仿真

3.1 SPDSR协议的设计和实现

SPDSR协议是在DSR协议的基础上，结合P2P计算模式建立起来的。其目的是通过Chord算法与DSR的结合，将P2P网络路由算法的优点有效移植到新型MANET路由协议之中。因此SPDSR在DSR中已有类的基础上，添加了新的类，如图3所示。

（1）用于存放运行时用到的常量的MyConst类；

（2）用于连续hash函数构造的哈希构造类Hash；

（3）用于维护全局Chord环节点的Chord环类Chord－Cycle；

（4）用于存放节点类信息的Chord环节点类Chord－Node；

图3 SPDSR中添加的类及类之间的关系

（5）用于节点路由表维护和管理的节点管理类NIDManager；

（6）算法路由表PRTTable；

（7）存储路由信息的路由表项类PRTEntry。

哈希构造类Hash将节点的地址通过哈希运算映射成一个哈希环域空间结构，有效实现了移动节点间的信息共享和消息通信；类ChordNode用于存储节点Id值和下一节点指针的信息，通过Chord环类ChordCycle对其信息的调用，实现了在Chord环中节点查询，插入，删除的功能，维护了全环节点的秩序；类NIDManager的功能是标识节点NID和定位目标节点NID，从而实现对节点路由表的维护和管理。

路由表项类PRTEntry包含NHID，路由表路径的实际长度等信息，用于查看NHSR中是否包含到destId的节点路径。一个节点的所有路由表项构成这个节点的算法路由表PRTTable，加入这个类可以实现初始化PRTEntry，更新PRTEntry中的路由表路径等功能。

3.2 NS－2分裂对象模型扩展［11－12］

NS－2支持有线和无线网络中的有关TCP、路由、多播等协议的模拟，且只支持4种主要自组网路由协议（DSDV、DSR、TORA和 AODV）。为了在NS－2中添加新协议，需要扩展NS－2分裂对象模型，其步骤为：添加tcl的新协议类；添加新协议支持；新协议初始化。

对新协议做仿真实验时，需要在仿真程序中添加对新协议支持。即在仿真程序中添加以下代码：

3.2.1 添加tcl的新协议类

针对新算法SPDSR，需要添加tcl类SPDSRNode，并初始化参数。在类SPDSRNode中主要是对SPDSRAgent类功能的tcl封装，具体包括：配置模拟环境参数、新算法的初始化方法、添加接口参数的设置、参数重置方法和初始化参数等过程。

3.2.2 ns－lib.tcl中添加新协议支持

ns－lib.tcl中定义的模拟器类Simulator在创建无线节点时调用了函数create－wireless－node，为了增加对新路由协议SPDSR的支持，需要增加SPDSR启动入口（MYMself at 0.0"MYMnode start－spdsr"）、对SPDSR节点参数进行设置和绑定SPDSR节点代理类。

3.2.3 新协议初始化

在tcl/lib/ns－default.tcl中 添 加 对 SPDSR 初 始 值 的 设置，代码如下：

4 实验结果及分析

本实验模拟在1000＊1000m，节点移动速度1m/s，数据流类型为cbr的单兵场景中，节点规模变化（节点个数分别为50，70，100，200，300，400，500个）对分组投递率，平均端到端延时，路由开销，吞吐量这4个性能指标的影响。通过对DSR和SPDSR这两种路由协议性能的比较，论证SPDSR在大规模无线网络中的优势。

4.1 分组投递率（packet delieve ratio，PDR）

如图4所示，两种协议的分组投递率在中小规模网络中性能差别不大；当节点个数增加即网络规模扩大时，性能均有所下降。其中DSR在节点个数超过200个之后，其分组投递率下降速度陡然加快，而SPDSR虽然也有下降趋势，但下降速度比较缓慢。在200个节点以后随着节点个数的继续增加，SPDSR对DSR的优势更加明显。因此在大规模网络中，SPDSR在分组投递率方面具有更为良好的表现。

图4 分组投递率性能比较

4.2 平均端到端延时（average end－to－end delay，AED）

图5显示随着节点个数的增加，端到端延时整体呈上升趋势。其中在中小规模网络环境里，两种协议的端到端延时较低且差别不大。当网络规模变大时，DSR的端到端延时陡然增加，而SPDSR的这一性能未发生很大波动，并且有下降的趋势。这是由于新算法引入了源路由检测机制、PHello协议以及邻居节点表，解决了结构化P2P覆盖层网络路由技术应用到无线移动自组织网络过程中带来的绕路问题，消息转发次数大大减少，从而降低了端到端延时［13］。

图5 端到端延时性能比较

4.3 路由开销（routload）

图6显示的是协议在路由开销方面的表现。从图中可以观察到，当网络规模变大时，SPDSR的路由开销明显低于DSR，这是由于新协议将每个移动节点必须保存和维护的路由表项数控制为O（log（N））（N为网络中节点总数），使它的路由存储开销，路由发现和维护开销大大低于其他协议［14］。

图6 路由开销性能比较

4.4 吞吐量（thoughout）

从图7中我们可以看到和前几幅图类似的情况，即在中小规模网络中，SPDSR的吞吐量与DSR协议差别不大，而随着节点个数增加，DSR的吞吐量明显低于SPDSR，这充分体现了SPDSR在大规模网络中良好的通信性能。

5 结束语

图7 吞吐量性能比较

本文介绍了一种基于P2P计算模式的新型MANET路由协议——SPDSR，并实现了其在NS2上的设计与仿真。通过观察DSDV，AODV，DSR这3种协议在分组投递率，端到端延时，第一个封包到达时间，路由开销，吞吐量这5个指标的表现，发现DSR的整体性能要优于另外两种协议［15］，这充分说明选择DSR作为研究对象并建立新的协议是具有实验依据的，是在考虑了多种因素的前提下作出的正确选择。通过大量实验我们可以得出结论，即SPDSR在大规模无线网络中的几个主要性能指标要明显优于另外3种协议，这与SPDSR的原理相一致。新协议的这一特点增强了网络的可扩展性，提升了网络的实用性能。总之，SPDSR是一种极具开发潜力的新的路由协议，相信在今后不断深入研究和实际应用中将得到更好的发展和完善。

［1］LI Zupeng.Study in MANET routing protocol base on P2P computing model ［D］.Beijing：Institute of Computing Technology，Chinese Academy of Science，2007：38－50（in Chinese）.［李祖鹏.基于P2P计算模式的MANTE路由协议研究［D］.北京：中国科学院计算机研究所，2007：38－50.］

［2］PAN Lili.Performance simulation for ZRP route protocols in Ad hoc network ［J］.Computer Engineering and Design，2010，30（12）：2948－2950（in Chinese）.［盘莉 莉.Ad hoc网络ZRP路由协议的性能仿真 ［J］.计算机工程与设计，2010，30（12）：2948－2950.］

［3］MENG Hao，ZHONG Zhangdui，AI Bo.Performance comparison and evaluation of the routing protocols in Ad Hoc Network ［J］.Information and Electronic Engineering，2009，7（2）：151－155（in Chinese）.［孟昊，钟章队，艾渤.Ad hoc网络路由协议研究及其性能比较 ［J］.信息与电子工程，2009，7（2）：151－155.］

［4］KE Zhiheng，CHENG Rongxiang，DENG Dejuan.NS2simulation experiment－multimedia and wireless network communication ［M］.Beijing：Electronics Industry Press，2009：15－17（in Chinese）.［柯志亨，程荣祥，邓德隽.NS2仿真实验－多媒体和无线网络通信 ［M］.北京：电子工业出版社，2009：15－17.］

［5］LUO Qiao，CHEN Jing，HUANG Chonghui，et al.Study of MANET routing evaluation model Based on Best－First ［C］.IEEE Internationan Conference on Wireless Communications，Networking and Information Security，2010：329－332.

［6］CHEN Jing，LUO Qiao，HUANG Conghui.The research on clustering algorithm of position forecast based on DSR ［J］.Journal of Air Force Engineering University，2011，12（1）：55－58（in Chinese）.［陈靖，罗樵，黄聪会，等.基于DSR的位置预测分簇算法研究 ［J］.空军工程大学学报（自然科学），2011，12（1）：55－58.］

［7］ZHANG Zhen，WANG Xiaoming.Research on Chord lookup algorithm for peer－to－peer network ［J］.Computer Engineering and Application，2006，42（11）：147－152（in Chinese）. ［张震，王晓明.对等网中Chord资源查找算法研究 ［J］.计算机工程与应用，2006，42（11）：147－152.］

［8］LUO Qiao，CHEN Jing，GUO Yichen，et al.The study of structured P2Prouting protocol based on DHT ［J］.China Science and Technology Information，2011，8（77）：127－128（in Chinese）.［罗樵，陈靖，郭一辰，等.基于DHT的结构化P2P路由协议研究 ［J］.中国科技信息，2011，8（77）：127－128.］

［9］ZHOU Jingxiang，LI Layuan.Optimized in DSR routing protocol of Ad hoc networks ［J］.Computer Application Research，2006，23（12）：292－294（in Chinese）.［周敬祥，李腊元.Ad hoc网络DSR路由协议的优化 ［J］.计算机应用研究，2006，23（12）：292－294.］

［10］Mohammad Shahidul Hasan，Christopher Harding，Hongnian Yu.Modeling delay and packet drop in network control system using network simulator NS2 ［J］.International Journal of Automation and Computing，2005：187－194.

［11］SONG Ling，LIU Bolan.Study and implementation of adding routing protocols in NS2 ［J］.Journal of Communication and Computer，2006，3（10）：33－37（in Chinese）. ［宋玲，刘勃兰.NS2中添加路由协议的研究与实现 ［J］.通信和计算机，2006，3（10）：33－37.］

［12］CHEN Yajun，XIAO Jianhua.Network simulation and protocol extension based on NS－2 ［J］.Computer Syetem Application，2005，14（5）：84－87（in Chinese）.［陈亚军，肖建华.基于NS－2的网络仿真与扩展 ［J］.计算机系统应用，2005，14（5）：84－87.］

［13］TAN Feng，FU Xuezheng，ZHANG Yanqing，et al.A genetic algorithm－based method for feature subset selection ［J］.Soft Computing，2007，12（2）：111－120.

［14］BAI Rujiang，WANG Xiaoyue，LIAO Junhua.Combination of rough sets and genetic algorithms for text classification ［C］.Proceedings of the 2nd International Conference on Autonomous Intelligent Systems：Agents and Data Mining，2007：256－268.

［15］CHEN Fujiang.Ad Hoc network routing protocol compare study and DSR optimizing ［D］.Nanjing University of Science，2008：50－55（in Chinese）.［陈复将.Ad Hoc网络路由协议的比较研究与DSR协议的优化 ［D］.南京：南京理工大学，2008：50－55.］