26车载A_oc网络中基于位置的路由协议研究硕士学位论文免费在线阅读

位置服务位置服务是类位置信息发布与查询机制，节点通过位置服务把自身位置信息按照定的方式发布到网络中，其它节点通过位置服务可随时查询该节点的位置。

位置服务为基于位置的路由协议提供网络中目的节点位置的查询服务，基于位置的路由协议又为位置服务提供路由方式。

因此，从网络层整体上来看，其协议开销是基于位置的路由协议和位置服务开销之和。

有关位置服务机制的相关内容将在第四章进行详述。

基于位置的路由协议工作机制∞图结构二〇年五月二十二日星期日图工作流程图接收到上层数据开始转发切换到下个平面使用右手定则计算下跳转发节点使用右手定二〇年五月二十二日星期日，二〇年五月二十二日星期日含在阴影内，这个虚线圆符合的定义，可见，如果它定同时属于反之，则不定。

定理表明是图的个子集。

和相比，这与中寻找其它节点的区域致。

文献给出了在网络仿真场景为区域中随机部署个节点的完全图如图所示，网络中每个节点的覆盖范围为，图同时还给出了该完全图通过移除不同数量的非和边得到的子图和子图，和图提供了不同密度的连通性。

图从构造完全图图相对邻接图图完全图中相对邻接图和图中的边二〇年五月二十二日星期日如图所示，结构的定义为，当时，为线段当时，为垂直于的带当时，是以为半径并过，两点的圆的相交部分当时，是以为半径，以，两点为圆心的圆之相交部分。

当等于，时，与都是结构的特例。

位置服务位置服务是类位置信息发布与查询机制，节点通过位置服务把自身位置信息按照定的方式发布到网络中，其它节点通过位置服务可随时查询该节点的位置。

位置服务为基于位置的路由协议提供网络中目的节点位置的查询服务，基于位置的路由协议又为位置服务提供路由方式。

因此，从网络层整体上来看，其协议开销是基于位置的路由协议和位置服务开销之和。

有关位置服务机制的相关内容将在第四章进行详述。

基于位置的路由协议工作机制∞图结构二〇年五月二十二日星期日图工作流程图接收到上层数据开始转发切换到下个平面使用右手定则计算下跳转发节点使用右手定则进行边界转发使用左手定则进行边界转发至层丢弃分组下跳节点处于右手法则区是否可返回贪婪模式是否是是否否否是下跳有效贪婪转发边界转发达到本地最优否是经过边经过边二〇年五月二十二日星期日规定网络中的节点使用贪婪算法和边界算法来转发数据分组，在平面图的映射边界上，只要节点未达到本地最优，使用贪婪算法转发数据分组，否则使用边界算法转发，协议工作流程图如图所示。

网络中的所有节点都维护张邻居节点信息表，用来存储其邻居节点的地址和位置信息，该表提供了进行转发决策所需要的所有状态信息。

在边界转发模式下所使用的分组首部的部分字段如表所示，其中分组首部有个字段用来记录分组处于贪婪转发模式还是边界转发模式，所有新产生的数据分组初始时都被标记为贪婪转发模式，并设置目的节点的为信息，以便转发节点用其计算下跳转发节点。

当网络中的节点收到个标记为贪婪转发模式的分组时，转发节点首先查找其邻居节点表，从中找出地理上最接近分组目的地址的邻居节点，然后转发分组至该邻居节点。

如果没有邻居节点比转发节点更接近目的节点时，就将该分组标记为边界转发模式。

在边界转发模式下，首先根据网络拓扑结构构建张图，然后将其简化成张平面图。

以节点为例，节点从张包含全部邻居节点的表开始，采用如下算法移除非和非边算法伪代码分别见表和表。

域功能目的节点位置分组进入边界转发模式时的位置当前面边上分组的位置进入当前面的第边数据分组模式表边界模式下使用的首部字段二〇年五月二十二日星期日算法移除非边算法伪代码，算法移除非边算法伪代码，在边界转发模式下转发分组时，遍历张网络平面图来进行分组转发。

平面图的边将整个图划分成许多小的互不重叠的有界多边形和些无界区域，这些有界多边形和无界区域统称为面。

平面图中的这些面分为内面和外面两表移除非边算法伪代码表移除非边算法伪代码二〇年五月二十二日星期日种，内面指由图的边所构成的密闭多边形区域，外面指由无界区域构成的面。

在这两类面中如图所示，首先使用右手定则先遍历图找到与直线交叉的边，然后转移到相邻的被直线横切的面。

当目的节点标识为的分组在节点处进入边界转发模式时，转发该分组到平面图上最接近目的节点且分布在的连线上的面。

在图中，每个遍历的面被直线贯穿，前两个和最后的个面是内面，第三个是外面。

边界转发是指数据分组依次沿着这些面的边界转发，在每个面中，依据右手定则选择下边。

当数据分组进入边界转发模式时，在分组中记录下贪婪转发失败的节点位置，该位置在之后的每跳中用来确定数据分组能否返回到贪婪转发模式。

每次转发分组到个新的面，就在中记录下旧面和新面与直线的交点，同时记录分组在新的面中进入第次进入的边。

当收到个标记为边界转发模式分组时，首先比较与当前转发节点的位置进行比较，如果当前转发节点的位置到目的节点的距离比到目的节点的距离更近，就将该分组标记为贪婪转发模式，并重新返回到贪婪转发模式进行转发。

因此，边界转发只是本地最优化的种优化策略，旦分组到达个比之前贪婪转发失败的位置更接近目的节点的位置，数据分组就能够继续贪婪转发过程，而不会返回到之前本地最优化的情况。

当数据分组在节点处进入边界转发模式，沿着横切直线的面转发图边界转发二〇年五月二十二日星期日该数据分组，节点转发数据分组到相对直线作逆时针旋转所遇到的第条边，即使用右手定则决定转发节点的第个边。

此后，使用右手定则绕着该面转发数据分组。

当绕着个面转发分组时，需要状态信息来判断并选择那条边会与直线相交，数据分组中记录了贪婪转发失败的节点位置和节点相关信息，并且转发节点存储了其自身和邻居节点的位置信息。

如果个节点所在边与直线相交于点，设置分组的的值为，并将分组沿着下个被直线横切的面转发。

首先使用右手定则找到相对作逆时针旋转所遇到的第条边，并记录新的面中的第条边到分组首部的域。

此过程在逐渐靠近的面中不断重复，直到分组返回到贪婪转发模式或路由到目的节点。

节点和目的节点在图中是连通或者不连通两种情况。

当节点和目的节点在图中是连通时，不管节点位于内面还是外面，以任方向遍历面的边必定会引起面远端的边与直线相交，设交点为。

在交点与分组进入边界转发模式的节点相比，当前转发节点越来越靠近目的节点。

分组如果不能到达目的节点，可能存在以下两种情况，第种情况是导致链路中断的节点在内面，另