基于定位辅助的超宽带自组网路由算法
1.1 算法设计思想
算法主要利用节点的位置信息将路由查找的范围限制在一定的区间内，以减小算法的开销，并基于节点的位置信息产生网络拓扑和路由表，完成分组的路由选择和转发过程。算法由位置信息的交换获取和路由表的形成阶段、路由选择和分组转发阶段、路由维护阶段共三部分构成。在节点频繁移动的情况下，节点的位置频繁变化，导致链路断开时常发生。算法利用周期更新的距离位置交换分组(DAP)信息获得网络的拓扑信息，在得到节点位置的同时维护本地网络拓扑表，并根据拓扑表计算到达全网其他节点的最短路由。分组的转发首先基于本地路由表中的路由信息，使用源路由转发的模式。当链路变化太快，使得通过DAP实现网络拓扑更新的速度跟不上链路的变化速度或其他原因导致分组中的源路由断开时，算法基于已有位置信息采用按需方式重新进行限制搜索范围的路由发现，以减少算法开销。由于使用UWB技术得到的是节点之间的距离信息，将其转换为位置信息所需要进行的计算和控制消息发布会引入一定的控制开销。
1.2 网络拓扑和路由表信息更新
节点定位信息可以采用文献[3]中所述方法获得，包括本地路由表、网络拓扑表和节点位置信息表三种信息表，分别如图1、图2和图3所示。每个节点都周期广播一张包含网络中每个节点到其他邻居节点的距离信息集的截短表－DAP表，以实现位置信息的交换和更新，如图4所示。图4中，分组长度以字节为单位；“N_邻居1”为第1个目的节点的邻居数；邻居地址N_邻居1为第一个目的节点的第N个邻居节点。
周期性主动广播的过程如下：(1) 网络初始化时，节点间通过不断与邻节点交换彼此的信息以得到周围的链路状态信息。当获得全网节点的拓扑连接关系以及所有相邻节点之间的距离后，使用最小距离算法计算本地路由表。计算本节点全局坐标系坐标时，以ID号最小的节点为网络的中心参考节点。(2) 节点首先将拓扑更新信息中每一项的目的节点序列号加1，节点将本节点已知的最新距离和拓扑信息广播到邻居节点。(3) 节点收到来自一跳邻居节点的DAP信息后，根据分组中携带的距离信息和拓扑信息更新自己的本地位置信息表。若DAP信息中的目的节点序列号大于本地拓扑表中的目的节点序列号，则使用DAP信息中的相应表项更新本地拓扑表中的相应表项；否则，不更新。之后，该邻居节点再将所知道的最新网络拓扑连接和节点位置信息向其邻居节点广播。通过充分的信息交换后，所有节点就能够获得全网的拓扑连接和节点间的距离。节点本地拓扑表每次更新后都将重新计算本地路由表，以保证路由表中信息对拓扑变化的收敛。
1.3 路由选择和分组转发
对节点距离信息和网络拓扑信息定期更新时，节点利用本地链路状态信息计算去往网络中其他节点的路由表，路由表中的每个表项都保存了到达其他节点的整条路径信息。当节点有分组要发送到目的节点时，将本地路由表中到达目的节点的所有中转节点的地址信息封装在数据分组，采用源路由的方式将分组发送到下一跳邻居节点。中转节点接收到该数据分组时，首先检查分组中封装的下一跳邻居节点地址是否为本节点地址，如果是，记录本节点信息并向目的节点继续发送该分组。由于当前网络拓扑结构发生变化或其他原因导致从源节点到目的节点的路由不可达时，使用源路由维护机制维护到目的节点的路由。
1.4 位置信息对算法的优化
在全网节点位置信息计算的基础上，算法使用位置信息限制请求分组的发送范围以降低控制开销。本算法只允许在源节点所定义的容许转发区域内（请求区）的中间节点对路由请求分组进行转发，减少了路由请求分组洪泛的区域。请求区的定义需要在两方面进行权衡：(1) 较小的请求区导致较低的路由开销，因为较少数量的节点被容许转发路由请求分组；(2) 较大的请求区会增加到达目的节点的路径，特别是在网络节点稀疏的情况下。本文采用了锥形和圆形两种请求区。(1) 锥形请求区定义为一个以源节点位置为定点、大到足够可以包含路由请求分组应该到达的网络区域(期望区)的锥形区域，该定义减小了请求区，因此减小了路由发现开销，如图5所示。(2) 圆形请求区定义为一种基于距离信息的区域。在路由请求分组中，包含源节点S和目标节点D之间的距离dSD以及目标节点的位置(XD,Y)。收到路由请求分组的节点I检查dDID≤dSD+δ这个条件是否被满足。设dID是节点I与D之间的距离；δ是一个给定的常数，如果dID≤dSD+δ，节点I就转发路由请求分组；否则分组被丢弃。对于δ=0，只有离目标节点的距离比源节点离目标节点的距离还小的节点容许转发路由分组，请求区是一个以(XD,YD)为圆心、d为半径的圆形区域；当δ>0，请求区增大为以(XSDD,YD)为圆心、dSD+δ为半径的圆形区域，如图6所示。
图5 锥形请求区示意图 图6 圆形请求区示意图
路由查找过程中，虽然使用位置信息进行了路由期望区的限制，但如果本地节点的路由表中保存有到目的节点的路径，则不需要进行位置判断；只有当本地节点路由表中没有到目的节点的路由的情况下，才会发起按需路由维护的过程，中转节点接收到请求分组后判断本节点是否位于期望区域内，如果在期望区域内，则转发分组请求。另外，本算法将路由查找限制在5跳以内，有利于减少路由发现的时间。