一种车载Ad Hoc网络的分布式位置服务路由方法

摘要

本发明公开了一种车载Ad Hoc网络的分布式位置服务路由方法，在路网中部署位置服务器，位置服务器接收并存储所辖区域内移动节点上报的位置信息，并且在位置服务器之间定期进行信息交互得到全网所有移动节点的位置信息，在节点需要通信时，源节点将数据发送至位置服务器，位置服务器通过全网节点信息列表得到目的节点所属的位置服务器，再建立位置服务器之间的路由进行数据转发，最后由目的节点所属的位置服务器向目的节点转发数据。采用本发明，可以显著减少网络中传播的位置信息数量，并且提高数据的投递成功率。

说明书

技术领域

本发明属于智能交通技术领域，更为具体地讲，涉及一种车载Ad Hoc网络的分布式位置服务路由方法。 

背景技术

在智能交通技术领域中，车载Ad Hoc（点对点）网络作为Ad Hoc网络的一个特殊子集，除了具有传统Ad Hoc网络无中心、自组织、多跳等特点外，还具有节点移动受道路拓扑以及驾驶员行为影响等特点。但是由于车载Ad Hoc网络中的车辆节点高速移动，从而导致网络拓扑变化迅速，容易造成通信链路中断等现象，使得原本为Ad Hoc网络设计的路由协议不再适用。考虑到车载Ad Hoc网络的特点，有科研工作者提出了基于位置的路由协议。基于位置的路由协议根据节点自身位置信息、邻居节点位置信息以及目的节点位置信息进行路由决策，不需要维护路由表，减少了路由开销，因此非常适用于网络拓扑变化迅速的车载Ad Hoc网络。在基于位置的路由协议中，位置信息的散布需要通过位置服务协议来实现，因此位置服务协议是实现基于位置的路由协议的前提。如何高效、准确地获取目的节点的位置信息并有效地与路由协议进行融合，用以提高数据的投递成功率是车载Ad Hoc网络的关键研究内容之一。 

在目前提出的位置服务协议中，按照实现方式可以大致分为两类：基于洪泛的位置服务协议和基于交会的位置服务协议。 

基于洪泛的位置服务协议可以分为主动式协议和被动式协议。在主动式协议中，路网中每个节点定期查询GPS定位系统获得自身位置信息，并将该信息洪泛给网络中的每个节点，网络中的每个节点维护一张位置信息表，用于记录网络中其他节点的位置信息。在需要通信时，源节点直接查询位置信息表获得目的节点的位置信息进行路由，其代表协议主要有SLS(Simple Location Service)，参见Basagni S,Chlamtac I,Syrotiuk V.R and Woodward B.A.A Distance Routing Effect Algorithm for Mobility[J].Proc of ACM MobiCom,2010.10,vol.18.在被动式协议中，当节点需要通信时，该节点在一定范围内洪泛一个查询信息来查询目 的节点的位置信息，其代表协议主要有RLS(Reactive Location Service)，参见Camp T,Boleng G and Wilcox L.Location Information Services in Mobile Ad Hoc Networks[J],Proc of the IEEE International Conference on Communications,2002. 

基于交会的位置服务协议又可以分为基于行列的协议和基于哈希函数的协议。在基于行列的协议中，网络中的每个节点选取南北方向上一定区域内的节点作为位置服务器来更新自己的位置信息，需要通信时，源节点沿东西方向发送查询分组来查询目的节点的位置信息，并通过查询分组与某一位置服务器节点的相遇来获得目的节点的位置信息，其代表协议主要有XYLS(Column-Row Location Service)，参见Haas Z.J and Liang B.Ad Hoc Mobility Management with Uniform Quorum System[S].IEEE/ACM Transactions on Networking,1999.4,vol.7.在基于哈希函数的协议中，网络被划分为网格，且位置服务器通过哈希函数来选择，每个节点选择一个或多个位置服务器来更新自己的位置信息，需要通信的节点通过查询这些位置服务器来获得目的节点的位置信息，其代表协议有GLS(Grid Location Service)。 

然而，基于洪泛的位置服务协议如SLS采用大规模洪泛机制散布位置信息，其负载开销较大。对于节点移动速度较快、网络规模较大的车载Ad Hoc网络，采用GLS等基于交会的位置服务协议需要花费大量的开销用于选取位置服务器，影响了协议的可扩展性。此外，SLS、RLS、XYLS、GLS等位置服务协议适用于节点随意改变移动方向且没有固定移动轨迹的移动场景，没有考虑实际路网中建筑物等障碍物对通信质量的影响。在车载Ad Hoc网络中，车辆节点的移动受道路拓扑和交通规则限制，且移动轨迹受驾驶员行为影响较大，因此上述位置服务协议不能很好的适用于车载Ad Hoc网络。 

发明内容

本发明的目的在于克服现有技术的不足，提供一种车载Ad Hoc网络的分布式位置服务路由方法，减少网络中传播的位置信息数量，提高数据的投递成功率。 

为实现上述发明目的，本发明车载Ad Hoc网络的分布式位置服务路由方法，包括以下步骤： 

S1：根据路网情况部署位置服务器，位置服务器遵循与移动节点相同的协 议； 

S2：在车载Ad Hoc网络初始化时，各个位置服务器将自身ID和自身位置信息在全网范围内洪泛，接收到该位置信息的其他位置服务器和移动节点将该位置服务器的ID和位置信息存储到本地的位置服务器列表；此后的新接入移动节点在第一次接入时广播一个查询消息，由接收到该查询消息的位置服务器将所有位置服务器的信息发送至该移动节点； 

S3：每个移动节点以固定周期T₁对自身位置进行定位，选择一个位置服务器将自身ID和位置信息使用基于位置的路由方法进行上报； 

S4：位置服务器将接收到的移动节点的ID和位置信息保存至本地的所辖节点位置列表，位置服务器以固定周期T₂进行所辖节点位置列表条目的更新与维护； 

S5：每个位置服务器使用基于位置的路由方法，以固定周期T₃交互所辖节点位置列表，使每个位置服务器都可以获得全网移动节点的ID和位置信息及其所属的位置服务器ID，保存至本地的全网节点位置列表； 

S6：有移动节点需要通信时，通信方法为： 

S6.1：源节点使用基于位置的路由方法将携带有目的节点ID的数据转发到其最近一次上报位置信息的位置服务器； 

S6.2：接收到数据的位置服务器根据目的节点ID查询所辖节点位置列表，如果存在目的节点，进入步骤S6.4，如果不存在，进入步骤S6.3； 

S6.3：在全网节点位置列表中查询该目的节点所属的位置服务器，使用基于位置的路由方法向该目的节点所属的位置服务器转发数据，返回步骤S6.2； 

S6.4：该位置服务器使用基于位置的路由方法向目的节点转发数据。 

进一步地，所述步骤S3中周期T₁采用以下公式计算： 

$>T_1=\frac{R_{\mathrm{Tr}}}{\alpha \times \bar{v}}$>

其中，R_Tr为该移动节点的传输范围，为该移动节点的平均移动速度，α为预设的比例因子。 

进一步地，步骤S3中位置服务器的选择方法为：移动节点在位置服务器列表中选择与其距离最近的位置服务器，如果存在多个距离最近的位置服务器， 则根据该移动节点的移动方向，选择靠近的位置服务器，如果仍然存在多个位置服务器，则任意选择一个。 

进一步地，步骤S4中周期T₂采用以下公式计算： 

$>T_2=\frac{R_{\mathrm{Tr}}^{*}}{\alpha \times \bar{V}}$>

$>\bar{V}=\left(\underset{k=1}{\overset{n}{\Sigma }}{\bar{v}}_k\right)/n$>

其中，为该位置服务器的传输范围，为该位置服务器所辖区域内所有移动节点的平均移动速度，n为所辖节点数量，为第k个节点的平均移动速度，α为预设的比例因子。 

进一步地，步骤S4中所辖节点位置列表条目的更新与维护的具体方法为： 

如果位置服务器在周期T₂内接收到所辖节点列表中已有节点的新的位置信息，则在期满时对该节点的位置信息进行更新； 

如果位置服务器在周期T₂内没有接收到所辖节点列表中已有节点的新的位置信息，则在期满时删除列表中该节点的相关条目； 

如果位置服务器在周期T₂内接收到所辖节点列表中未曾记录的新的节点的位置信息，则在期满时建立新的条目用于保存新加入节点的相关信息。 

进一步地，步骤S6.3中，在向目的节点所属的位置服务器转发数据时，在中继节点的选择时优先采用位置服务器。 

本发明车载Ad Hoc网络的分布式位置服务路由方法，在路网中部署位置服务器，位置服务器接收并存储所辖区域内移动节点上报的位置信息，并且在位置服务器之间定期进行信息交互得到全网所有移动节点的位置信息，在节点需要通信时，源节点将数据发送至位置服务器，位置服务器通过全网节点信息列表得到目的节点所属的位置服务器，再建立位置服务器之间的路由进行数据转发，最后由目的节点所属的位置服务器向目的节点转发数据。 

采用本发明，可以获得以下有益效果： 

（1）、各移动节点只需向位置服务器上报位置信息，位置服务器进行信息交互得到全网节点位置信息，可以显著减少网络中传播的位置信息数量，减少网络资源消耗； 

（2）、移动节点通信时，移动节点之间无需建立路由，只需要和所属的位 置服务器建立路由，再由两个固定的位置服务器进行路由和数据传输，可以降低路由难度，提高数据的投递成功率。 

附图说明

图1是本发明实施例的应用场景示意图； 

图2是本发明实施例中节点选择位置服务器的示意图； 

图3是本发明中节点通信时的一种具体实施方式流程图。 

具体实施方式

下面结合附图对本发明的具体实施方式进行描述，以便本领域的技术人员更好地理解本发明。需要特别提醒注意的是，在以下的描述中，当已知功能和设计的详细描述也许会淡化本发明的主要内容时，这些描述在这里将被忽略。 

实施例 

本发明车载Ad Hoc网络的分布式位置服务路由方法提出了一种位置信息服务方法，具体包括： 

S101：根据路网情况部署位置服务器，位置服务器遵循与移动节点相同的协议。在实际应用中，需要根据具体的路网情况和周围环境情况等因素来综合考虑位置服务器的部署，通常设置在路口处。图1是本发明实施例的应用场景示意图。如图1所示，本实施例在每个十字路口均部署了一个位置服务器，每个位置服务器与网络中的其他移动节点即车辆的地位平等，即遵循与移动节点相同的协议，也配置有定位系统，还需要配置一定的存储容量和计算能力，与移动节点一样，位置服务器也会分配固定ID用于标记身份。 

S102：在车载Ad Hoc网络初始化时，各个位置服务器将自身ID和自身位置信息在全网范围内洪泛，接收到该位置信息的其他位置服务器和移动节点将该位置服务器的ID和位置信息存储到本地的位置服务器列表；此后的新接入移动节点在第一次接入时广播一个查询消息，由接收到该查询消息的位置服务器将所有位置服务器的信息发送至该移动节点。表1是位置服务器列表。 

位置服务器ID 位置信息

表1 

通过本步骤，即完成了位置服务器的位置信息服务。如果之后有新的位置服务器加入网络，在加入时也应该将自身ID和自身位置信息在全网范围内进行洪泛。 

S103：每个移动节点以固定周期T₁对自身位置进行定位，选择一个位置服务器将自身ID和位置信息使用基于位置的路由方法进行上报。基于位置的路由方法采用现有技术即可，即根据距离远近选择发送节点与接收节点之间的节点作为中继节点，通过单跳或多跳的方式进行信息传输。 

周期T₁可以直接根据需要设置，也采用以下公式计算： 

$>T_1=\frac{R_{\mathrm{Tr}}}{\alpha \times \bar{v}}$>

其中，R_Tr为该移动节点的传输范围，为该移动节点的平均移动速度，α为设置的比例因子。 

在选择上报的位置服务器时，可以基于位置服务器的位置、信号强度、所辖节点数量等因素进行选择。本实施例中使用的方法为：移动节点在位置服务器列表中选择与其距离最近的位置服务器，如果出现多个距离最近的位置服务器，则根据该移动节点的移动方向，选择靠近的位置服务器，如果仍然出现多个位置服务器，则任意选择一个。 

图2是本发明实施例中节点选择位置服务器示意图。如图2所示，本实施例中位置服务器10和位置服务器20之间的某移动节点X需要上报位置信息，由于其目前刚好位于两个位置服务器的正中，即存在两个距离最近的位置服务器，由于移动节点X正在向位置服务器10的方向驶去，会靠近位置服务器10，因此选择位置服务器10上报。 

S104：位置服务器将接收到的移动节点的ID和位置信息保存至本地的所辖节点位置列表，位置服务器以固定周期T₂进行所辖节点位置列表条目的更新与维护。表2是所辖节点位置列表。 

所辖节点ID 位置信息

表2 

同样的，周期T₂可以直接根据需要设置，也可以采用以下公式计算： 

$>T_2=\frac{R_{\mathrm{Tr}}^{*}}{\alpha \times \bar{V}}$>

$>\bar{V}=\left(\underset{k=1}{\overset{n}{\Sigma }}{\bar{v}}_k\right)/n$>

其中，为该位置服务器的传输范围，为该位置服务器所辖区域内所有移动节点的平均移动速度，n为所辖节点数量，为第k个节点的平均移动速度，α为预设的比例因子。在采用这种方法计算周期T₂时，所辖区域内的所有移动节点需要向该位置服务器上报该移动节点的平均移动速度。 

在进行所辖节点位置列表条目的更新与维护时，以固定周期T₂进行更新与维护，即每隔T₂进行一次操作，其余时间仅接收并缓存移动节点上报的位置信息，具体方法为： 

如果位置服务器在周期T₂内接收到所辖节点列表中已有移动节点的新的位置信息，则在期满时对该节点的位置信息进行更新； 

如果位置服务器在周期T₂内没有接收到所辖节点列表中已有移动节点的新的位置信息，则在期满时删除列表中该节点的相关条目； 

如果位置服务器在周期T₂内接收到所辖节点列表中未曾记录的新的移动节点的位置信息，则在期满时建立新的条目用于保存新加入节点的相关信息。 

S105：每个位置服务器使用基于位置的路由方法，以固定周期T₃交互所辖节点位置列表，使每个位置服务器都可以获得全网移动节点的ID和位置信息，及其所属的位置服务器ID，保存至本地的全网节点位置列表。周期T₃根据实际需要进行设置。 

通过以上步骤，即实现了车载Ad Hoc网络中各节点位置信息的服务，即在各移动节点中均保存有各位置服务器的位置信息，各位置服务器中保存有全网中所有移动节点的位置信息。在本发明中，各移动节点只需要选择一个位置服务器上报位置信息，各位置服务器再通过信息交互获得全网的移动节点位置信息，从而减少网络中传播的位置信息数量，减少网络资源消耗。 

当有移动节点需要通信时，即可使用上述方法得到的位置信息进行通信。图3是本发明中节点通信时的一种具体实施方式流程图。如图3所示，本发明中节点通信方法为： 

S301：源节点上报位置信息：源节点使用基于位置的路由方法将携带有目 的节点ID的数据转发到其最近一次上报位置信息的位置服务器。 

本发明中，源节点不需要建立与目的节点的路由，只需要建立与所属位置服务器的路由，所属位置服务器即移动节点最近一次上报位置信息的位置服务器。以图1所示场景为例，假定图1中车辆S为源节点，目的节点为车辆D，车辆S最近一次上报位置信息的位置服务器为位置服务器10，则车辆S使用基于位置的路由方法将携带有目的节点ID的数据发送给位置服务器10。图1中的虚线圆表示各节点一跳范围，可见车辆S无法直接发送给位置服务器10，需要通过一个其他车辆，例如车辆M作为中继节点转发到位置服务器10。 

S302：接收到数据的位置服务器根据目的节点ID查询所辖节点位置列表。 

S303：接收到数据的位置服务器判断所辖节点位置列表是否存在目的节点，如果存在目的节点，进入步骤S305，如果不存在，进入步骤S304。 

位置服务器10在接收到数据后，在所辖节点位置列表中查找车辆D，根据图1所示本实施例中位置服务器10所辖节点位置列表中不存在车辆D，因此进入步骤S304。 

S304：转发数据至目的节点所属的位置服务器：该位置服务器在其全网节点位置列表中查询该目的节点所属的位置服务器，使用基于位置的路由方法向该目的节点所属的位置服务器转发数据，返回步骤S302。 

位置服务器10在全网节点位置列表中查询车辆D所属的位置服务器，假定此时查询得到的是位置服务器30，那么位置服务器10向位置服务器30转发数据。因为位置服务器是固定设置的，因此在转发过程中可以优先采用位置服务器作为中继节点，以保证较高的传输质量。 

位置服务器30接收到数据后，同样要在所辖节点位置列表中查找车辆D，由于在之前的数据传输过程中车辆D仍然在移动，假定此时车辆D已经不在位置服务器30所辖区域内，那么位置服务器30还需要继续转发数据。假定此时位置服务器30经过信息交互在全网节点位置列表中得到此时车辆D所属的位置服务器40，即向位置服务器40转发数据。位置服务器40接收到数据后，即可在所辖节点位置列表查询得到车辆D，进入步骤S305。 

S305：该位置服务器使用基于位置的路由方法向目的节点转发数据。本实施例中，位置服务器40根据车辆D的位置信息，采用基于位置的路由方法根据 距离远近通过单跳或多跳的方式将数据发送到目的节点D。从图1可以看出，车辆D在位置服务器40的一跳范围外，因此在本实施例中需要选择一个或多个车辆作为中继节点来转发。 

可见，本发明在移动节点通信时，采用的是一种将位置信息服务和基于位置的路由方法融合使用的分布式位置服务路由方法，位置服务器可以通过全网节点位置列表中存储的目的节点信息得到其目前所属的位置服务器，通过将数据转发至其所属的位置服务器之后再向目的节点转发，可以有效提高数据的投递成功率。 

尽管上面对本发明说明性的具体实施方式进行了描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。