4 HFRR:高频反应路由协议 不同于一般的路由协议选取跳数最少的路径作为路由，CONEX协议的路由表通过选取路径质量矩阵中质量最佳的中继节点而形成（这是因为在短波通信中首要考虑的是信道条件而非路由跳数），体现了跨层(cross-layer)[46-47]设计协议的思想。文章旨在保留CONEX依据路径质量选取路由这一优点的前提下提出低开销的具体算法——HFRR（HF Reactive Routing）。
按需驱动路由的开销只发生在需要通信的节点之间，源节点只有在不存在到达目的节点的路由时才启动路由发现过程，适宜短波组网。路由维护则监控网络拓扑的变化，并在当前路由变更后启动路由发现过程重新寻径。
4.1节和4.2节分别描述了HFRR协议路由发现和路由维护的基本过程，4.3节则描述了一些相关的高级主题，4.4节则用Petri网模型对HFRR协议的可达性、不变性等进行了验证，4.5节对HFRR的适用范围进行了分析。
4.1路由发现在HFRR协议中，当源节点S的路由表中不存在达到目标节点D的路由时，它发出路由请求包Preq。如图4.1所示，Preq中包含：Preq 的ID、源节点S、目的节点D、允许的最大年龄MAXage、实际的路径年龄Fage、允许的最大中继数MAXre、实际的中继数Fre、允许广播Preq包的最大跳数MAX
br和一个路由记录域。路由记录域中存放的是中继节点的ID序列。
ID
S
D
MAXage
Fage
MAXre
Fre
MAXbr
R1
R2
…
Rn
…
路由记录域
图4.1 路由请求包Preq
在源节点最初发送的Preq包中，ID为上一次发送的Preq包ID加1，Fage = 0，Fre = 0，路由记录域为空。MAXre、MAXage、MAX
br三个字段的设置则会在4.3节的高级主题中阐述。
假设节点Rn收到了Preq，它将做如下处理：
1.如果节点Rn的Preq缓存中存在新收到Preq 的<S, ID>对，则忽略该Preq；否则将新的<S, ID> 写入Preq缓存，并执行2；
2.节点Rn解析Preq的包头，获得MAXage、MAXre、MAX
br，并分析路由记录域，得到已经记录的中继数NUMre，作如下判断：
（1）如果节点的路径质量矩阵中存在满足式(4.1)、(4.2)的到达目标节点的路径，则该节点将自身的节点ID写入路由记录域的最后，并向上一个中继节点Rn－1发送路由应答包Pres。
age ≤ MAXage (4.1)
n + NUMre ≤ MAXre (4.2)
如图4.2所示，路由应答包中包含Fage、Fre和到达目标节点的数据业务质量qdata，其中Fage为收到Preq包头中的Fage和路径质量矩阵中age的较大者，Fre则依据式(4.3)求得；
Fre = NUMre + n (4.3)
ID
S
D
Fage
Fre
Qdata
R1
R2
…
Rn
…
路由记录域
图4.2 路由应答包Pres
（2）如果节点本身就是目标节点，则将自身ID写入路由应答包Pres路由记录域的最后，并置Fage=0，qdata=14，并向上一个中继节点发送路由应答包Pres；
（3）如果节点的路径质量矩阵不存在满足式(4.1)、(4.2)的路径，也不是目标节点，则该节点需判断是否要将Preq包进一步广播：
①如果不满足式(4.4)（即超过寻径的广播范围），则节点不再广播Preq；
②如果满足式(4.4)，则节点将自身ID写入Preq的路由记录域末尾，并继续向周围邻居节点广播新的Preq；
NUMre ≤ MAX
br (4.4)
显然，只有路由记录域中记录的中继节点才可能收到路由应答包Pres。假设节点Rn收到了来自节点Rn+1的Pres，该节点需完成下列过程：
1.如果本节点不是源节点，则执行：
（1）依据美军标所描述的路径质量计算方法计算出通过Rn+1中继到目标节点D的qdata，统计收到的Pres包路由记录域中还剩余的中继节点数NUMre，依据式(4.5)计算其到达目标节点的中继数n。将qdata、n和Pres包中的Fage写入自身的路径质量矩阵并更新路由表；
n = Fre – NUMre (4.5)
（2）在Pres中写入ⅰ)中计算所得qdata，去掉路由记录域中本节点的ID，继续向路由记录域中记录的上一跳节点发送新的Pres；
2. 如果本节点是源节点，则其依据美军标所描述的路径质量计算方法计算出通过Rn+1中继到达目标节点D的qdata，并将计算所得的qdata和Pres包中记录的Fre、Fage写入自身的路径质量矩阵。源节点依据路径质量矩阵选取质量最佳路径更新路由表，这样就完成了一个路由发现的全过程。
4.2路由维护传统的主动路由协议靠周期性的广播将路由发现和路由维护融为一体，当原先的路由失效后，其后周期性的信息交换可以跟踪到路由的变更。但是，在按需驱动的路由协议中，没有这种心跳交换，故路由的变更只能依靠明确的路由维护过程来捕获。
可利用数据链路层跳到跳（hop-by-hop）的确认来追踪当前路由的状态，当源节点S在往目标节点D经过中继节点序列“R1->R2->…->Rn->…”传送数据的过程中，如果节点Rn的数据链路层超时未收到Rn＋1某一帧的确认，则它认为Rn到Rn+1的路径失效，并发送路由错误包Perror给上一跳节点Rn-1，上一跳节点收到Perror后继续将其发给Rn-2直到将Perror被发送到源节点。源节点收到Perror后，重新启动路由发现过程寻找新的路由。在路由维护过程中，所有收到Perror的节点应删除到达目标节点D的这一路径信息（即置路径质量为0）。
4.3高级主题4.3.1避免寻径洪泛HFRR协议的路由请求包Preq中包含了允许的最大广播跳数MAX
br这一字段，其目的在于限制Preq被广播的范围。在最初的Preq中，令MAX
br＝1，即Preq只向源节点的邻居节点广播。这时，邻居节点虽然没有到达目的节点的路由，但是由于不满足式(4.4)，它也不进一步向周围广播Preq。经过这一轮的寻径，如果源节点还没有找到合适的路由，则令MAX
br＝2*MAX
br，再次向周围广播Preq，这次的广播范围会增加一倍。如果在Preq中不设置MAXre这个字段，则无论如何，Preq会被在全网范围内广播（洪泛），这显然是不可取的。
4.3.2寻径约束路由请求包Preq中的MAXage、MAXre字段则可以根据用户的需求来人为设置。实际上，MAXage、MAXre字段的设置也限制了Pres的数量，对减小HFRR协议的带宽开销是有利的。如果用户需求MAXage为0，则路由发现过程将是不达目的节点D不停止，中间节点记录的路由信息不被采纳，即中继节点不能回复Pres，因为它们记录的路径必然不是age=0的最新路径（路径质量矩阵中记录的路径age会随着时间的推移由节点修改）。
4.3.3局部重新寻径在4.2节所描述的路由维护过程中，节点Rn在得知经过Rn+1到达目标节点D的路径失效后会发送路由错误包Perror给源节点告知源节点重新启动路由发现过程。另一种可行的方案是节点Rn不发送Perror通知源节点，而是启动本节点到达目的节点D的路由发现过程，将重新寻径的规模限制在较小范围之内。这就是反向链路算法，该算法适合于网络拓扑结构快速变化的网络，具有很好的自适应能力。反向链路算法的核心是将由于拓扑结构变化而引起的连锁反映限制在局部区域内。这与链路状态协议的设计思想完全相反。链路状态协议追求的是以最快的速度将链路变化通知到全网。
4.3.4避免路由环路在HFRR前面的论述中，没有考虑避免路由环路的产生问题，实际上此问题不容忽视。假设由三个无线节点组成的短波自组网如图4.3所示，节点A已知一条经过节点B到达节点C的路径，此时节点B到节点C的链路中断。如果不使用目的序列号技术，由于从B到C的链路中断，B需要寻找到达C的路由信息而发出一个路由请求报文。当A收到该请求时由于还保存着原来的路由信息，A会立即把这个旧的路由信息发送到B。节点B收到A发来的路由响应后创建一条以A为下一跳节点的到达C的路由表项。这时问题便产生了，因为此时A中保存的到达C的路由是以B为下一跳节点的。这样，当有目的节点为C的报文发送到B时，B会根据其路由表将该报文发送到A，而A又会根据自己的路由表把该报文又发送到B，从而形成了一个路由环路。
图4.3 三节点组成的自组网
故在HFRR协议中需借鉴DSDV、AODV协议所采用的目的序列号技术。假设节点A所知通过B转发到C的路由的序列号为N，B、C间链路断开后，节点B为了寻找到节点C的路由而发出一个路由请求报文。但此时与上面情况不同的是B在发送请求之前先把请求报文中的目的序列号加1（此时目的序列号为N+1）。当节点A收到该路由请求时，发现本地对应节点C的路由的序列号为N，小于N+1，因此节点A判定自身保存的路由已过时，只作继续转发该路由请求报文的操作，避免产生路由环路。
目的序列号技术的采用是为了保证路由协议的收敛性。给每一个路由信息设置一个序列号可以标识该信息是否为最新路由，每当一条路由发生改变时，它的序列号就会增大，网路在选择路由时总是选择具有最大序列号的路由，也即是最新的路由，保证了所选路由能够跟上网络拓扑的变化。
4.4 HFRR协议的验证4.4.1 HFRR协议的Petri网描述网络协议中任何错误和缺陷都将给系统带来巨大的危害，需要以形式化技术对HFRR协议进行验证。Petri网具有坚实的数学基础和丰富的分析技术，与物理系统极其相近，具有异步并发特性，适于网络体系结构和协议的分析。故本文选用Petri网对HFRR协议进行描述。由于引入高级主题后的HFRR协议过程很复杂，状态甚多，故在验证过程中，只保留了其主干。
HFRR协议所对应的Petri网描述如图4.4所示。
库所：
P1：节点处于初始等待状态；
P2：查找路由表，判断是否存在可用路由；
P3：发送数据包等待状态；
P4：发送寻址包Preq等待状态；
P5：判断收到包的类型；
P6：判断是否路由应答包Pres的源节点；
P7：发送路由应答包Pres等待状态；
P8：等待更新路径质量矩阵和路由表；
P9：收到寻址包Preq判断是否目标节点；
P10：检查是否有到目标节点的路由；
P11：检查是否满足跳数条件；
P12：等待发送寻址包Preq；
P13：等待发送路由应答包Pres；
P14：等待发送路由应答包Pres；
P15：等待释放链路；
P16：收到数据包判断路由；
P17：接收数据报等待；
P18：转发数据报等待；
变迁：
t1：欲发送数据包；
t2：存在可用路由；
t3：发送数据包；
t4：不存在可用路由；
t5：发送寻址包Preq；
t6：收到数据包；
t7：判断是路由应答包Pres；
t8：判断是路由应答包Pres的源节点；
t9：判断是路由应答包Pres的中继节点；
t10：修改路径质量矩阵和路由表；
t11：修改路径质量矩阵和路由表并向上级中继节点发送路由应答包Pres；
t12：收到寻址包Preq；
t13：判断是寻址中继节点；
t14：判断没有到达目标节点的路由；
t15：判断满足跳数条件；
t16：广播寻址包Preq；
t17：判断是目标节点；
t18：判断有到目标节点的路由；
t19：判断不满足跳数条件；
t20：发送路由应答包Pres；
t21：释放链路；
t22：判断是数据包；
t23：判断是目标节点；
t24：判断不是目标节点；
t25：转发数据包；
t26：接收数据包并释放链路；
t27：发送路由应答包Preq并释放链路；
图4.4 HFRR的Petri网模型
4.4.2 HFRR协议的Petri网可达性分析可达性分析是指生成Petri网的全部可达状态，以检查是否符合协议所要求出现的状态以及期望的行为特征。可达性分析从初始全局标识开始，根据每一个点火变迁或并发变迁集同时具备点火条件的变迁的集合生成分支节点，总体上形成可达树（图4.5）。
图4.5 HFRR的可达树
通过对可达树的分析，可对协议的各种性质得出结论：
(1)有界性
可达树中的每个节点中，每个位置中的标记数量都是有限的，所以此网是有界的。
(2)活性
从可达树中可以看出，每个变迁至少被点火一次，不会出现死锁。
(3)完整性
在描述中所说的状态都能达到。
(4)前进性
可达树中不存在无用的循环。
4.4.3 HFRR协议的Petri网不变量分析不变量分析是要求网在特定执行模式下不变量的特性。Petri研究最广泛且理论上最完备的两种不变量是S-不变量和T-不变量。S-不变量对应于Petri网中标记总数保持不变的库所子集，它反映协议的守恒性。T-不变量是指保持网标识不变的变迁序列，它反映协议运作的循环或重复特性。
(1)S-不变量分析利用CT·X=θT(θT是分量全为零的T-向量)，其中C为HFRR协议的Petri网描述的关联矩阵(图4.6)，从而得到两个S-不变量。两个库所不变量表明协议的可靠性不依赖于初始标识，代表接收和发送请求在协议运行过程中的库所总量没有发生变化，体现了协议的守恒性。
(2)T-不变量分析利用C·X=θS(θS是分量全为零的S-向量)，从而得到T-不变量。通过对其的分析可以反映出该协议系统的循环特性。
图4.6 HFRR的Petri模型关联矩阵
4.5 HFRR协议的适用范围 在小规模的高频网络内部，可以才用HFRR协议。在一个节点数据众多，地理范围分布很广的高频网络内，若完全采用HFRR协议，则路由发现的过程需要在非常广的范围内寻径。而寻径成功后，网络拓朴的变更也可能导致中继节点离开当前路径，此时也将付出很大的路由维护开销。所以在大规模的高频网络中，应采用分层结构，簇内可以适用HFRR协议，而簇头之间也可以采用HFRR维护骨干网的路由更新。
4.6小结一个合适的短波组网路由协议应该：
1)采用按需驱动的思想；
2)不能以传统路由协议的跳数最少作为选径的标准，应结合LQA机制，选择链路质量最佳的路由。
HFRR正是基于以上两点思考而提出，它综合了按需驱动路由协议和美军标CONEX协议依据链路质量选取路由的优点。HFRR分为路由发现和路由维护两个过程。在路由发现部分，为避免寻径洪泛采用了寻径约束机制；为减小路由维护开销，在路由维护部分，可采用局部重寻径的思想。
HFRR路由协议经过了Petri网的验证，适用于小规模范围内的短波组网。对于一个地理分布很广的大规模HF网络而言，可采用分层结构，簇内或簇头之间可采用HFRR路由协议。
本文版权：月影孤鸿（21cnbao@sohu.com）华中科技大学计算机学院研究生
