一种移动自组网基于距离稳定的路由协议

白 媛，栗晨亮，宋 焱，张会兵

（1.天津理工大学 电气电子工程学院，天津 300384；2.桂林电子科技大学 广西可信软件重点实验室，广西 桂林 541004；3.天津理工大学 光电器件与通信技术教育部工程研究中心，天津 300384）

移动自组网络（mobile ad hoc networks，MANET）是一种小规模、无统一管理、网络节点具备路由功能的动态无线移动网络。节点的移动方向和速度具有随机性，拓扑变化频繁［1］。此类网络适用于多跳路径的特殊环境，常用于临时组网应用场景，随着D2D［2］及IoT［3］的提出与发展，MANET将发挥更重要的作用。

路由协议的选择将直接决定无线网络数据传输的效率和性能，根据不同的需求，大量路由方案不断出现［4，5］。AODV［6］基于移动自组织网络特点设计，能够很好地适用于不断变化的拓扑环境。AODV的选路依据是路由条目的新旧和跳数，未考虑所建路由的稳定性，重路由概率较高。选择高稳定性路由是提高网络性能的有效措施［7-10］，能够有效地降低重路由频率及其带来的负面影响。针对该问题，大量提高所建链路稳定性的路由协议被陆续提出［8-15］。

文献［11］对接收到的邻节点功率进行采样并设计链路稳定预测度量函数，在传统协议基础上增加链路稳定预测值选路依据，重新设计路由过程，网络性能提高明显。该方法为组播方法，不适用于单播。文献［12］通过识别不安全节点来提高链路稳定性的组播方法，未考虑邻节点间关系。

根据节点之间的距离，文献［13］将邻居关系分为远离和靠近的相对状态，利用不同状态及节点间的距离估计链路生存时长。文献［14］根据节点自身和邻节点的历史位置信息，计算节点间距离、相对运动速度及运动角度，考虑多种因素预测邻节点之间的运动状态，该方法认为在一次节点停留前，节点的运动状态不变，与实际环境有差异。文献［15］根据节点的距离、速度和运动方向对节点的状态和运动过程进行预测，计算网络断裂或切换时间，提高了链路稳定性。文献［16］在AODV基础上进行改进，该方法考虑距离、开销和节点能量的消耗，对路由生存时间进行估计。协议使用参量较多，方法复杂性较高。

考虑节点的移动速度，文献［17］提出了2种速度感知概率模型，即简单速度感知概率模型和高级速度感知概率模型。目标是改变AODV协议的路由请求方式，模型的设计减少了链路中断的次数。文献［18］提出了一种车联网环境下的路由策略，节点不断获取邻节点的速度信息并记录，根据所邻节点的平均速度与本地速度比较，若本地速度较小，则参与转发。协议适用于有固定速度方向的车联网环境，普通移动自组网速度方向的随机性和速度值的瞬时性，不再适用。

根据上述方法中存在的问题，本文提出一种移动自组网基于距离稳定路由协议。协议考虑节点运动随机性特点，适用于一般移动自组网单播路由协议。利用节点之间一段时间内相对运动关系来预测路径稳定性强弱，相对运动关系由节点之间的距离变化计算得出。同时考虑邻居保持时间、路由跳数及相对运动关系设计距离稳定度量值改善网络性能。邻居关系保持时间长，相邻节点收集信息充分，路径稳定性预测更加准确。

1 基于距离的链路稳定性度量

距离稳定路由协议（distance-stability routing protocol，DSRP）是在按需距离矢量路由协议（AODV）的基础上进行改进。目的节点获取多条不交叉路由，选择路由跳数最少且距离稳定值较好的一条路由作为终选路由。路由距离稳定值由两节点之间的单跳距离稳定值确定。两相邻节点之间增加单跳距离稳定值作为改进路由协议的选路标准，单跳距离稳定值由相对稳定值和绝对稳定值确定。相对距离稳定值考虑数据传输两节点的相互移动性，表明两节点一段时间内的相对运动性。绝对稳定值表示接收节点自身在邻居拓扑中的相对运动性。

DSRP改进了参考文献［11］的组播协议，使其适用于单播路由协议。引入基于地理位置路由方法，根据连续多次获取的到达邻节点距离值，设计距离稳定度量值函数，重新设计路由流程，选择更加稳定高效的路径。协议设计和实验仿真在自由空间模型基础上完成，节点间的距离根据设备的GPS定位信息计算得到。

1.1 最大接收距离阈值

网络场景构建：节点总数为N，其中存在任意两相邻节点为Ni，Nj，i≠j，且i，j≤N。其中发送节点Ni，接收节点Nj，使用式（1）计算欧式距离，即

式中：（xNi，yNi）和分别为两邻居节点的位置；R为节点的传输距离。为节点Nj第n次接收到邻节点的位置并由式（1）计算得出的距离，其中n＝［1，2，…，K］，表示记录邻节点距离信息的次数，K为允许记录的最大数目，仿真实验中取K＝5。当n＞K时，记录表去除最早的一项，并记录新的一项。

在实际应用中，移动网络中各节点的网络环境存在差异，各节点能够正确接收到邻节点数据分组的距离值有差异。根据数据正确接收时的距离信息，各节点维护本地最大接收距离阈值Nk是网络中任意的节点。使用每次Nk与其任意邻节点Nl之间邻居链路断裂前最后一次距离信息更新节点的最大接收阈值为：

任意节点Nk维护取值，若邻节点Nl距离大于该值，认为该邻节点Nl有链路断裂风险，当前节点Nk不再参与该节点转发的路由建立过程。

1.2 距离稳定度量

1.2.1 相对距离稳定值

式中，n表示稳定值的次序。

对Nj与Ni的距离稳定度量值集做方差，定义距离稳定值为：

D_stabNiNj用来衡量两邻节点之间的距离变化剧烈程度。越小则表明两节点距离变化小，相对运动性弱。相邻两节点须连续保持一段时间的邻居关系才能计算该值，邻居关系断裂将清除相应的距离记录条目。

1.2.2 绝对距离稳定值

假定Nj有多个邻居节点，其中第k个表示为Njk。Nj计 算 与 多 个Njk的 稳 定 度 量 值 集：｛SNj（Nj1），SNj（Nj2），SNj（Nj3），…，SNj（Njk）｝，其中各项计算方法为：

对稳定度量值集求方差，得出绝对距离稳定值为：

I_stabNj表明Nj在拓扑区域内与邻节点之间的相对运动程度。

1.3 单跳距离稳定值

将2种稳定值以一定权重合成，得到某两相邻中间节点的单跳稳定值，该值由接收节点Nj计算得到，定义为：

考虑两相邻节点以及接收节点在邻居拓扑中的运动关系，得出上述结果。DSNiNj作为单跳距离稳定值。DSNiNj越小，认为Ni和Nj间的链路越稳定。

2 距离稳定路由协议

AODV协议仅以跳数作为度量值，路由建立由第一条传递到目的节点的路由请求（RREQ）报文决定，该方式易选择处于网络边缘的节点作为中间转发节点，路径断裂可能性高。DSRP增加路由稳定度量，重新设计路由流程。

2.1 路由策略

当RREQ报文从源节点传递到目的节点，并回复路由回复（RREP）报文，源节点接收到RREP时，源节点激活路由，一条路由得以建立。在此路由历经的节点序列中，若有2个相邻节点之间的单跳距离稳定值较高，则表明该对节点之间的链路不稳定，会增加整条路由断裂的概率。目的节点在接收到的多条跳数最少的路由中，选择路径上所有相邻节点间最大单跳稳定值最小的路由为终选路由，以增加路由稳定度。

定义路由距离稳定值为：

式中：节点Nx和Ny是路径path上任意一对邻节点，Ny为Nx的下一跳；Ny计算得到DSNxNy。源目节点间形成多条路由时，将使用Spath最小的路由。

DSRP未改变AODV协议中间节点通过RREQ广播ID和源节点ID确定同一个广播报文的判定机制。同一RREQ能够建立多条不交叉的路由。路由选择如图1所示。

路由过程如图1所示，根据DSRP路由策略，S→A→B→E的路由距离稳定值为0.2，而S→C→D→E路由距离稳定值为0.3，第一条路由将被选择并建立反向路由。协议同时考虑跳数和路由稳定性，跳数最少且路由稳定值较小的将被作为终选路由。

2.2 路由流程

DSRP数据包结构和路由表项与AODV协议相似，协议总流程见图2，DSPR主要针对图2中路由请求部分和路由建立部分做出改进。根据对邻节点信息收集及稳定路径选择流程需求，对数据包格式及路由流程作以下修改。

2.2.1 报文格式及本地信息

1）在HELLO报文中增加本地当前位置信息Location字段。路由请求RREQ报文及RREP报文在原有跳数度量值基础上，增加Path_stab字段用于更新及传递路由稳定值。

2）邻居表增加接收到某邻居HELLO报文的次序n和与之对应的记录邻居的距离值项。路由表项增加路由稳定值选项，用于记录RREQ到达当前节点路由稳定值。

2.2.2 协议流程

根据图2所示的总流程框图，协议流程步骤如下。

步骤1初始化。

1）网络初始化流程如图3所示。网络建立后，网络中任意节点Ni每HELLO_INTERVAL时长，获取自身定位并更新至其HELLO报文中Location字段，并广播HELLO报文。

2）Ni的邻节点Nj收到HELLO报文，根据报文中Location字段和自身位置信息，计算节点间距离并记录到邻居表，记录次数n初始值为1，每次连续接收Ni的HELLO报文更新n+1。每个节点根据与邻节点之的历史距离信息记录，利用式（2）维护本地最大接收阈值。

3）Nj判断次数n是否等于5，如果等于5，记录新到达的距离值，并将最早n＝1对应的距离值删除，保证连续接收到邻节点距离值最新且不超过5次。

步骤2路由请求。

1）路由请求流程如图4所示。若有源节点Ns需要和某一目的节点Nd交换数据，Ns首先查找路由表，若有已建立的路由条目，则根据条目单播传输数据；否则转入下一步。

2）源节点Ns构建RREQ报文，其中Path_stab＝0，广播RREQ报文。

3）邻居Ny接收到RREQ，解析RREQ并确定自身是否为目的节点，若是，则转8）；否则转入下一步。

4）Ny判断是否接收过该报文，若是，则直接丢弃；否则转入下一步。

5）Ny提取RREQ报文中携带的Nd信息并搜索本地路由表，若存在最新的到达Nd路由条目，记录到达Ns的路由条目并单播回复RREP，转入步骤3；否则转入下一步。

6）节点不参与路由建立的条件是：Ny未记录5次上跳节点Nx的距离或Nx处于自身最大接收距离阈值外，节点不参与路由建立，丢弃该RREQ报文；否则转入下一步。

7）Ny根据式（7），利用邻居表中记录的邻节点的距离信息，计算单跳距离稳定值DSNxNy，取DSNxNy和RREQ中Path_stab较大值，更新RREQ的Path_stab字段并转发RREQ，转入3），路由路径上所有节点转发RREQ时均做以上判断。

8）若RREQ到达Nd，不再丢弃已接收过的相同RREQ报文，Nd等待一定时间，根据路由更新规则，收敛后会生成一条跳数最少路由稳定值较好的路由条目，路由回复转步骤3。

当有RREQ到达时，路由表更新规则为：查找到达Ns路由条目，若不存在，则更新路由表，记录RREQ中的Sequence、Hops和Path_stab等相关信息。若存在路由条目，则更新到达Ns路由的优先级顺序为：Sequence、Hops、Path_stab。即保证路由最新和跳数最少条件下，判定路由稳定值大小。

步骤3路由建立。

1）路由建立流程如图5所示，RREQ转发过程中，路由上各节点已经建立到达Ns的路由，根据路由请求、路由更新规则更新路由表。

2）若RREQ到达Nd，Nd不再根据广播ID和源节点ID丢弃RREQ报文，等待0.1 s，等待时间不断更新路由表。等待结束后，根据路由表记录，单播回复RREP，各中间节点根据本地路由表转发。

3）若某中间节点存在最新到达Nd的路由条目，直接单播回复RREP。

4）RREP到达Ns，各中间节点反向路由条目成功建立，激活路由并开始转发数据。

分析上述路由过程可知，DSRP每个节点增加最大接收距离阈值的判定，节点根据自身最大接收距离阈值和与上跳节点之间的距离信息，距离超出阈值的节点不再转发接收到的RREQ报文，即不再参与该次路由建立过程，可以有效减少处于通信边缘节点转发RREQ的次数，减少RREQ报文的广播，提高路由稳定性的同时减少参与选路的中间节点的个数。

在DSRP中仅与RREQ发送节点保持一定时长邻居关系的节点参与选路，即两邻节点须保持5次连续HELLO间隔的邻居关系时间才参与RREQ报文的转发，否则直接丢弃RREQ报文，不再接收和转发，避免部分移动相对频繁的节点参与路由的建立。进一步降低协议对网络的开销并提高路由的稳定性。

根据式（8），DSPR路由选择过程中增加路由稳定值参数Spath，该参数在RREQ报文传递过程中被选择出来，代表多条不交叉路由中一条路由的路由稳定值，该值越小，认为该条路由的稳定性越好。某条路由建立成功后，路由上任意两相邻节点之间链路断裂，将导致整条路由的断裂，该值为整条路由中各中间相邻节点单跳稳点值最大值，即认为路由上相邻节点单跳稳定值最大的一段决定整条路径的稳定性。该值可预测邻节点之间的运动关系，选择相对移动性较小的路由，减少路由断裂次数。下文通过仿真实验分析其网络性能。

3 仿真分析

为验证DSRP与AODV性能，使用NS-2（2.35版本）仿真平台并使用Matlab分析数据。节点移动模型选择Randem Way-point。由于仿真过程需要使用HELLO报文实现位置信息交换，使用AODV-WITH-HELLO模式，开启NS-2中AODV协议的链路层探测功能。仿真场景参数见表1。

表1 仿真场景参数

3.1 网络性能评价

无线协议性能度量存在多种标准［19］。对以下参数进行仿真比较。

1）分组投递率：网络中所有节点实际接收到的数据分组数量与节点发送的数据分组数量之比，分组投递率的大小代表网络可靠性高低。

2）吞吐量：所有已建立连接的所有目的节点交换数据分组总量与仿真时间的比值。

3）控制分组发送量：网络存在期间，所有节点路由控制分组交换总数量，仿真实验时长设置为600 s。

4）归一化路由开销［20］：网络中所有节点发送和转发路由请求总数量与总接收数据分组的数量比值。表示路由协议的开销。

5）路由发起频率：整个网络发起路由过程的频率，表示链路断裂概率。

3.2 仿真实验设置

主要对DSRP和AODV进行仿真实验。仿真实验场景参数见表1，有关参数见表2，仿真图每点结果均为20次仿真实验所得数据平均值。

表2 仿真实验参数

3.3 仿真实验结果分析

3.3.1 仿真实验一

仿真实验结果如图6所示。

图6（a）显示了数据包投递率与节点移动最大速度关系。由图6（a）可知，随着节点移动最大速度的提高，2种协议的分组投递率都降低。AODV协议下降速度较快，DSRP大于AODV。DSRP能够有效减少拓扑变化对网络传输的影响。分析可得，当节点移动最大速度为20 m／s时，DSRP数据包投递率相比AODV提高了2%～3%。

图6（b）描述了节点移动最大速度与路由发起频率的变化关系。路由发起频率直观地反映了路由路径断裂与网络拓扑变化剧烈程度的关系。根据AODV和DSRP协议描述可知，只有在路由初建和路由断裂时才会发起路由建立过程，路由请求的次数越少，路由发起频率越低，路由断裂次数越少，路由生存时间越长，所选路由越稳定。分析可知，随着最大移动速度增加，AODV和DSRP的路由发起频率都逐渐增高，其中AODV增长速度更快。DSRP建立的路由具有更好的防路由断裂能力，节点最大移动速度为20m／s时，DSRP路由发起频率比AODV降低了约20%。

图6（c）显示了吞吐量随节点移动最大速度的变化关系。与图6（a）对比，更高的数据包投递率意味着更高的吞吐量。与AODV相比，最大移动速度为20 m／s时，DSRP在相同网络环境下提高2%～3%。

图6（d）描述了2种协议的归一化路由开销与节点移动最大速度的关系。归一化路由开销表明路由协议寻路过程对网络资源的消耗大小。随着网络拓扑变化，DSRP和AODV的归一化开销随之增加，AODV协议增长较快。节点移动最大速度为20 m／s时，DSRP比AODV下降约20%，性能提升明显。DSRP由于加入了距离阈值和5次HELLO转发的限制，减少了中间节点转发RREQ次数，降低了RREQ泛洪对网络资源的浪费。另外距离稳定值的加入，减少了因路径断裂而造成的路径修复带来的额外开销。

图6（e）是网络控制包发送总量与节点最大移动速度之间的关系，控制分组主要包括路由协议相关控制分组及数据包头部。归一化路由开销表明了路由请求次数与接收数据分组数量之间的关系。控制包总量则显示路由协议整体的开销数据，而不只是路由请求过程。随着节点移动性的增强，2种协议的控制包总量增大，DSRP比AODV需要更少的控制包，降低了节点处理路由协议需要的控制包的数量，有利于降低拥塞和节点能量消耗。

仿真结果表明，DSRP-1比DSRP-2具有更好的性能，ω＝0.8比ω＝0.5时性能更好，绝对距离稳定值所起作用更具优势。

3.3.2 仿真实验二

实验二仿真结果如图7所示，改变网络中节点数目，DSRP 5种性能指标均比AODV更好。节点个数增加时，路由可选择节点增加，路由建立成功的概率提高，分组投递率和吞吐量上升。但增加的节点数目将会增加路由过程控制包处理数量，归一化路由开销和控制包总量提高。更多的路径节点将会增加路由断裂的概率，路由发现频率也有所提升。

根据上述结果分析，DSRP实现了对AODV性能的提升，DSPR具有高效性。降低路由开销的同时，能够提高数据分组投递率，降低路由发起频率。提升了所选路径的稳定性。

4 结论

基于现有的选路方式，对传统AODV进行改进。根据定位信息计算节点间距离信息并设计路由距离稳定值评估路径的稳定性。仿真实验结果显示，相比AODV，新协议能够更好地适应移动自组网络拓扑的变化，实现性能的提升。本文在节点移动完全随机的场景下进行仿真实验，未考虑车辆网络、传感器网络等特殊网络场景，在不同网络场景下，权重值ω对网络的影响仍需验证。