无线自组织网络中基于位置的数据包转发方法

摘要

一种无线网络技术领域的无线自组织网络中基于位置的数据包转发方法，本发明通过当源节点收到数据包文后，解封装查看节点的目的节点址和目的节点的位置信息；然后进行传输数据的路径选择及优化。在节点以70m/s速度移动时，采用本发明的传输方法丢包率明显好于现有的GPSR技术。

说明书

技术领域

本发明涉及的是一种无线网络技术领域的方法，具体是一种无线自组织网络中基于位置的数据包转发方法。

背景技术

无线自组织网络作为一种新型的移动多跳无线网络，与传统的无线网络有许多不同的特点：1.网络的自组性——自组网相最大的特点就是可以在任何时刻、任何地点不需要现基础网络设施(如基站)的支持，快速构建起一个移动通信网络；2.动态变化的网络拓扑结构——在自组网中，通信结点可以任意的加入和消失，以任意速度和任意方式在网中移动，通信结点之间通过无线信道形成的网络拓扑结构随时可能发生变化；3.有限的无线传输带宽——由于自组网采用无线传输技术作为底层通信手段，而由于无线信道本身的物理特性，它所能提供的网络带宽相对有线信道要低得多；4.分布式控制网络——自组网中的通信结点都兼备独立路由和主机功能，不存在一个网络中心控制点，通信结点之间的地位是平等的，网络路由协议通常采用分布式控制方式，因而具有很强的鲁棒性和抗毁性。

需要指出的是，针对自组网网络的带宽有限，网络的拓扑动态变化等特点，如何使众多通信结点合理高效地占用无线资源以及源结点和目的结点间建立有效的路由成为无线自组织网络的核心问题。特别是在战场环境下，结点的移动速度增加，网络的拓扑变化频繁时，如何保证路由的有效性更是挑战性的课题。传统基于拓扑的无线自组网路由协议已经无法满足快速拓扑变化的需求。

经对现有技术的文献检索发现，Brad Karp在2000年MobiCom中发表的论文“GPSR：Greedy Perimeter Stateless Routing for Wireless Networks”(无线自组织网络贪婪周边无状态路由)，该文中提出了一个基于通信结点位置信息的贪婪周边转发策略GPSR，在现实中网络通信结点可以通过GPS等获得自身的位置信息，为此算法提供了可行性。结点可以通过位置服务获得网络中其他结点的位置信息，从而使用基于位置的无线自组网路由算法。GPSR是典型的基于位置的路由协议，故GPSR是一种无状态的路由协议，既没有定期交换路由信息，也没有通过广播洪泛进行路由请求，也没有存储路由信息，故减少了网络中协议带宽的消耗，也降低了对结点处理能力的要求，这是基于位置路由的一般性优点。GPSR的报文转发主要有贪婪转发和周边转发这两种转发模式：

贪婪转发，在任何可以使用的时候使用；边缘转发，在贪婪转发不可用的区域使用。所谓贪婪转发就是在运行GPSR的结点的邻居表项中都记录有邻居结点的位置信息。故当结点转发报文时它会选择距离目的结点最近的邻居结点作为下一跳结点。这样在理想情况下，数据报文最终会以最少的跳数转发到目的结点。但是当没有比源结点距离目的结点更近的邻居结点，贪婪转发将失败，GPSR的作者提出了当失败时进行周边遍历转发。所谓周边遍历转发就是构建一个平面图，然后使用右手法则进行周边遍历，这样就会形成一条到目的结点的路径。通过研究发现，GPSR协议有如下局限性：首先GPSR协议贪婪转发的思想是选择尽可能“远”的下一跳，这样就有可能导致在下一时刻邻居结点已经不在通信范围内而使转发失败；当采用周边遍历转发的时候，因为采用的是平坦图遍历方法，所以使得GPSR协议将不适用于三维空间的情况；并且使用平坦图的右手法则遍历势必引入了更多的跳数，从而增加了端到端的时延。

发明内容

本发明针对现有技术存在的上述不足，提供一种无线自组织网络中基于位置的数据包转发方法，在节点以70m/s速度移动时，采用本发明的传输方法丢包率明显好于现有的GPSR技术。

本发明是通过以下技术方案实现的，本发明包括以下步骤：

第一步、信息获取的路径发现过程：当源节点收到数据包文后，解封装查看节点的目的节点址和目的节点的位置信息，具体包括：目的位置信息通过统一的位置服务获得邻居节点的位置信息，并通过邻居的Hello报文一跳广播获取并存储到邻居节点表中，通过周期性的Hello更新来持续维护邻居的实时有效信息且通过邻居节点信息的维护获得通往目的节点的路径。

第二步、传输数据的路径选择：在第一步邻居信息维护的基础上，当源节点收到报文后根据目的节点的网络地址和位置信息采用水平分割原则选择如何到达目的节点的下一跳节点并获得最优路径；

所述的水平分割是指：当源节点不再是接收数据包的下一跳节点时，则发送出的数据将不再转发回该源节点；则在无环路的基础上优选源节点的所有邻居节点中距离目的节点最近的节点作为下一跳，当所有邻居节点距离目的节点的距离都大于源节点距离目的节点的距离时，选择目的方向角最小的邻居节点作为下一跳节点转发数据。

所述的目的方向是指：源结点到目的结点的射线方称为此源结点的目的方向；所述的目的方向角是指：目的方向旋转到邻居方向所旋转的角度的最小值的绝对值。

第三步、路径不可达处理过程：将两个可行后续节点都存储到拓扑表中，当节点选择下一跳时判断最优下一跳是否违背了水平分割原则，当违背水平分割原则时则将该节点的上一跳节点标识为不可达并且重新选择可行后续节点；当仅有一个可行后续节点并且不违背水平分割原则，将此节点作为下一跳节点转发数据包；当违背则将自身标记为路由毒药返回给上一跳节点，即节点收到带有路由毒药的Hello包则不向该节点发送数据，再由上一跳节点查看是否有其他可行后续节点，当没有其他可行后续节点时则向源节点返回目的节点不可达消息。

所述的路由毒药即将路由跳数标记为最大或者不可达；所述的Hello包是两个节点之间交换路由信息的报文。

附图说明

图1是本发明中用到的定义的示意图；

图中：目的方向，邻居方向，目的方向正向夹角，目的方向负向夹角，邻居方向负向夹角。节点为无线自组网中的网路节点，虚线箭头为节点运动方向，实体黑线为转发数据路径。

图2是数据包转发选路过程的示意图；

图中：S节点为源节点，D节点为目的节点。圆圈为S节点的转发半径，虚线箭头为节点运动方向，实体黑线为转发数据路径。

图3环路过程描述的示意图；

图中：S节点为源节点，D节点为目的节点。箭头所指方向为路径选择方向。

图4是GPSR周边遍历转发结果的示意图；

图中：S节点为源节点，D节点为目的节点，箭头所指方向为路径选择方向。

图5是根据本发明改进后转发结果的示意图；

图中：S节点为源节点，D节点为目的节点，箭头所指方向为路径选择方向。

图6为本发明和现有GPSR技术在NS-2模拟实验丢包率的对比图；

图中：横纵方向为节点的最大移动速度，单位m/s，纵轴方向为丢包率。

具体实施方式

下面结合附图对本发明的实施例作详细说明下面结合附图对本发明的实施例作详细说明：本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

本实施例包括如下步骤：

第一步、路径发现过程：

节点本身通过定位系统(如GPS)获得自身的位置信息，由全局位置服务进行统一管理。节点要发往某个目的节点数据时，首先根据目的节点的网络地址请求全局位置服务获得目的节点的位置信息，然后封装数据。有了这个目的节点的物理位置，源节点会结合自己的物理位置计算出本节点到目的节点的距离和目的方向。通过邻居间周期的交换Hello报文获得邻居节点的位置和速度信息，每个节点都要维护一张邻居信息表，如下表：

表1

各个节点通过维护邻居信息表，来获得通往其他多跳目的节点的可行路径。

邻居节点信息定义如图1所示。

目的方向：源节点到目的节点的射线方称为此源节点的目的方向。例如S-＞D。

邻居方向：一个节点到其邻居节点的射线方向称为该节点的邻居方向。例如S-＞A，S-＞F。

目的方向正(负)向夹角：邻居方向通过顺(逆)时针旋转到目的方向所旋转的角度称为目的方向正(负)向夹角(0°≤α≤180°)。正向夹角为正值，负向夹角为负值。

目的方向角：目的方向正(负)向夹角的绝对值称为目的方向角。

邻居节点位置(X，Y，Z)：三维空间坐标值。

邻居节点距离：两个节点之间直线距离。

邻居方向夹角：节点的运动速度是个矢量，节点运动速度已知。邻居方向通过顺(逆)时针旋转到邻居节点速度方向所旋转的角度称为邻居方向正(负)向夹角。正向夹角为正值，负向夹角为负值。其绝对值称为邻居方向角。

如图1所示，SD射线方向为目的方向，SA射线方向为邻居节点A的邻居方向，∠β为邻居节点A的目的方向正向夹角，-∠α为邻居节点F的目的方向负向夹角，-∠γ为节点A的邻居方向负向夹角，-∠ε为节点F的邻居方向负向夹角。

第二步、路径选择过程：

当一个源节点需要发送一个数据报文到目的节点时，源节点会按照步骤一根据目的节点的网络地址和位置服务查找目的节点的物理位置。源节点判断在满足邻居条件的邻居节点中是否有满足贪婪转发条件的节点，有则转发；当贪婪转发失败，则查找邻居表中目的方向夹角，选择绝对值较小的两个节点作为可行后续节点存储在后续节点表中。之后在两个节点中选择目的方向角最小的作为下一跳转发数据包。当目的方向角相同，接下来判断邻居方向夹角和目的方向夹角相“与”后结果是否相同，当运动方向判断结果不一样，则优选邻居方向夹角和目的方向夹角同向的邻居节点作为下一跳；当通过两个节点的运动方向判断结果一样(同为正或者同为负)则随机选取一个作为下一跳转发报文。然后将上层数据报文封装成网络层路由方向报文转发给该邻居节点，并在报头中添加目的节点址的网络地址信息。当一个中间节点收到一个需要转发的方向报文后，它会根据报头中目的节点的物理位置计算出本地的目的方向距离，接下来的工作就和源节点的一样遍历邻居表看是否有满足贪婪算法的邻居节点，没有的话则选出目的方向最优的邻居节点并将报文转发到该节点，直至最终将报文投递至目的节点。

具体实例如图2所示，S节点为源节点，D节点为目的节点，∠α＝∠β，节点速度方向如图所示。S节点选择下一跳时，由于没有满足贪婪转发的邻居节点，因此比较邻居节点的目的方向角大小，∠α＝∠β为所有邻居中目的方向角最小的，因此两个节点存储到可行后续节点表中；进一步根据节点运行的速度方向判断邻居方向角和目的方向角是否同向，由于节点A邻居方向角与目的方向角同向，而F邻居方向角与目的方向角反向，所以节点A成为下一跳节点。节点A继续选择下一跳节点，有满足贪婪转发的节点B成为下一跳节点(此时即便节点S距离目标节点更近由于水平分割也不会选择S作为下一跳)。依次选择下一跳到节点C，节点C根据贪婪算法选择节点N作为下一跳转发数据，但是由于节点N再无其他邻居节点，因此将自己标记为路由毒药通过Hello包通知节点C，节点C将不会向节点N转发数据包。节点C继续选择节点M作为下一跳转发数据，直至到达目的节点D。最终路径为S-＞A-＞B-＞C-＞M-＞L-＞D

在选择下一跳路径的时候，应该保证无环路发生，当源节点S只有一个邻居节点A，将数据转发给A后，A节点按照步骤一选择节点S作为最优下一跳来继续转发数据，这样就形成了环路，直到TTL变为0将数据丢弃。解决方法在封装上层数据时将本节点的网络层信息跟目的节点一样也添加在报文头部中，下一跳节点接收此报文后采用水平分割的思想将源节点置为不可达。水平分割思想是由某节点转发过来的数据将不再转发回去。具体环路避免实例说明如图3所示，图3中详细的描述了工程中可能遇到的环路实例，节点A收到报文后按照第一步的路由策略应该选择节点S作为下一跳，但是根据本步骤中环路避免过程的要求，将源节点S标记为不可达，优选B作为下一跳而不会再选择S节点作为下一跳，从而避免了环路。

第三步、路径不可达处理过程：

在步骤二中最初设计了选择两个可行后续节点，并最终选择目的方向最优的节点作为下一跳。此时将两个可行后续节点都存储到拓扑表中，当节点选择下一跳时判断最优下一跳是否违背了水平分割原则，当没有违背则按照步骤二中叙述的过程转发数据；当违背则将上一跳节点标识为不可达并且重新选择可行后续节点。当仅有一个可行后续节点并且不违背水平分割原则，将此节点作为下一跳节点转发数据包；当违背则将自身标记为路由毒药返回给上一跳节点(节点收到带有路由毒药的Hello包，不向该节点发送数据)，再由上一跳节点查看是否有其他可行后续节点，当有则继续转发，当没有则向源节点返回目的节点不可达消息。

与现有技术对比本发明有如下有益效果：

1.更优的路径选择，本发明在贪婪距离转发失败后采用贪婪的方向转发，整个向目的节点转发数据的过程都是基于贪婪的思想，这样达到了路径最优化的程度。通过以下实例来加以说明：如图4所示，S结点为源结点，D结点为目的结点。根据贪婪算法转发策略将失败，因为S的邻居结点中没有比S结点本身距离D更近的结点了。因此退避到按照周边遍历转发，转发结果如图3所示，这样会产生更多的跳数，增加了端到端的时延。采取基于方向性的目标转发策略，根据目标的方向确定可行后续结点是R和K，之后判断目的方向角最小的是R(此处假设结点R和节点K在平面内的速度分量都是靠近SD目的方向运动的)，转发策略是局部做出的，节点R重复此过程。本例依次选取下路径为S-＞R-＞Q-＞P-D，如图5所示。

2.数据包成功的传送率，本发明的数据包传送率在节点高速移动的情况下，远好于现有的周边遍历转发。为了验证本发明的有益效果，采用伯克利大学开发的NS2.31[17]进行仿真验证。在NS2.31的基础上实现了现有的GPSR和本发明中所述的路由转发过程，仿真的基本设置如下：网络中的节点数为30；MAC协议是802.11；链路带宽为1Mbps；节点传输范围为250m；节点最大的移动速度是20m-70m/s；场景范围是800m＊800m；对于节点的通信模型，流量类型为CBR(Constant Bit Rate)；包大小为64byte；在N个仿真节点中选取20个作为恒定码流节点CBR，每个CBR节点随机选择一个目的节点，然后以恒定的发包率2Hz向这个目的节点发送数据报文。HELLO包发送周期1Hz；邻居过期2S；每次仿真时间为200s。如图6中所示，节点移动最大速度不同的情况下，每个速度10次仿真实验丢包率的平均值。可以看出当节点以70m/s速度移动时，本发明的丢包率明显好于现有的GPSR技术。