CN1642144A

CN1642144A - 用于移动无线自组网的高效轻量信息传播方法和系统

Info

Publication number: CN1642144A
Application number: CNA2005100047600A
Authority: CN
Inventors: T·A·埃尔巴特; T·D·安德森
Original assignee: Motors Liquidation Co
Current assignee: Motors Liquidation Co
Priority date: 2004-01-13
Filing date: 2005-01-13
Publication date: 2005-07-20
Anticipated expiration: 2025-01-13
Also published as: US7420954B2; DE102005001267B4; CN1642144B; US20050152318A1; DE102005001267A1

Abstract

用于无线移动自组网中的信息传播的系统和方法。该方法描述：接收把消息从源节点传递到目的地的请求；标识自组网的各相邻节点；当目的地为相邻节点且其中到目的地的跳数小于预定跳数时，在源节点上调用主动式边界节点广播协议；当从源节点到目的地的跳数超过预定数量时，在源节点上调用请求式边界节点广播协议；以及根据所调用的广播协议从源节点传递该消息。还提供一种计算机可读媒体，其中包含用于无线移动自组网中的信息传播的计算机程序。最后描述了一种用于无线移动自组网中的信息传播的系统。

Description

用于移动无线自组网的高效轻量信息传播方法和系统

技术领域

本发明涉及无线网络，更具体来说，涉及在无线移动自组网内用于高效信息传播的方法和系统。

背景技术

许多客车现在加入了集成通信系统。与广域网(WAN)、如蜂窝电话网或卫星通信系统结合使用的车辆通信单元(VCU)允许在移动环境中提供各种收费的预订服务。VCU通常为车辆远程信息处理装置，包括蜂窝无线电、卫星收发信机、符合IEEE 802.11或类似无线通信标准的无线接入点收发信机以及全球定位功能。通过载波服务的通信可在VCU上在接通时发起或者通过手动或语音命令电话号码输入发起。在VCU与VCU附近的无线LAN或WAN的节点之间建立无线电通信链路，从而通过无线移动自组网(MANET)提供附加的通信信道。

无线移动自组网通过由相互的无线电传输范围内的无线接入点节点组成的动态网络提供通信。移动无线接入点节点相互之间交换信息(例如位置、速度等)，以便在自组网内路由信息、如数据包。信息传播算法提供用于MANET内信息交换的通信协议。设法向另一个无线接入点节点传播信息(例如位置信息)的无线接入点节点调用信息传播算法以便于这些节点之间的通信。

一般有两种用于移动自组网的路由选择范例：基于拓扑的和基于位置的。基于拓扑的路由协议采用与形成网络(连通性)以便把数据包从源节点转发到目的地节点的链路有关的信息。基于拓扑的路由协议还可进一步分为主动式和请求式。请求式路由协议因其与主动式(表驱动的)协议相比有较低开销而在MANET中受欢迎，因为仅在需要时才必须发现和维护多跳路由。这个优点是以初始路由建立(发现)阶段中导致的等待时间为代价而取得的。

基于拓扑的请求式协议的操作从路由发现阶段开始，其中源节点在整个自组网中发送路由请求(RR)消息，以便建立到目的地节点的路由。一旦目的地节点接收到RR，它采用路由确认(RC)消息通过已发现路由进行应答。大部分请求式路由协议建议依靠泛搜索算法用于RR传播。自组网中的泛搜索包括向始发节点附近的每个节点广播通信。此后，成功收到广播数据包的各节点将该数据包向其相应的相邻节点重播。这个过程重复进行，直到覆盖整个网络。

相反，基于位置的路由协议仅依靠参与节点的物理位置，它减轻了基于拓扑的路由的一部分限制。基于位置的路由协议指示节点向最接近目的地的相邻节点转发数据包，而没有定义到目的地的完整路径，即逐跳地进行路由判定。主要优点在于，消除了路由发现阶段导致的任何延迟，因为数据包转发判定仅基于位置信息。另外，极大地减少了由中间节点的移动性所产生的对路由判定的任何影响，因为路由判定不依靠拓扑，并且以逐跳方式进行。但是，这个优点是以用作网络中所有节点之间分发位置信息的基础设施的分离信息传播算法为代价得到的。以上论述说明，信息传播是MANET中的两大类路由协议的基本元素，即请求式的基于拓扑和基于位置的路由选择。

在MANET中，我们引入称作“可达性”的信息传播性能的量度，它被定义为受关注节点成功地位于自组网内的次数的百分比。另一个MANET性能量度是延迟，它被定义为定位节点所产生的时间。其它性能量度包括通信开销(完成传播任务所需的传输总数)以及存储开销(每个接入点节点的表条目的平均数)。

以上所述的信息传播的一个实例为泛搜索。泛搜索极为简单，但它因所谓的“广播风暴问题”而获得极低的可达性。当给定节点、例如A的所有相邻节点重播由A发送的数据包时，出现广播风暴问题。这又在多址控制(MAC)层引起过多冲突。另外，基于泛搜索的算法是极为低效的，因为它们不必要地浪费系统带宽和能量资源。文献中所介绍的用于移动自组网的目前已知的信息传播算法主要基于泛搜索。泛搜索的实例包括如E.Royer和C-K Toh所述的自组网请求式矢量(AODV)和动态源路由(DSR)技术(“自组移动无线网络所用的当前路由协议的评论”，IEEE Personal Communication Magazine，第46-55页，1999年4月)以及M.Mauve、J.Widmer和H.Hartenstein所述的其它协议(“移动自组网中基于位置的路由选择的综述”，IEEENetwork，第30-39页，2001年11月/12月)。如前面所述，泛搜索因广播风暴问题而极为低效，如J.Broch等人报导(“多跳无线自组连网路由协议的性能比较”，ACM MOBICOM，1998年10月)。另外，泛搜索还不必要地浪费系统带宽及能量资源，例如，所谓的“DREAM”系统为信息传播采用基于表的泛搜索(S.Basagni等人的“关于移动性的距离路由选择效应算法(DREAM)”，ACM MOBICOM1998)。因此，在DREAM系统建议中，各节点必须保持网络中其它每个节点的信息(例如位置)。显然，这种方法不可缩放，而且在嵌入式系统环境中因大的表数据存储要求而不可行。

在Z.Haas和B.Liang的另一个建议(“采用一致定额系统的自组移动性管理”，IEEE/ACM Transactions on Networking，Vol.7，No.2，第228-240页，1999年4月)中，作者提出自组网的基于定额的定位服务。在这个建议下，选择移动节点的子集(构成“虚拟主干”)来保持其它所有节点的位置信息。虽然这个协议建议可能会减少传播开销，但在移动性条件下创建和维护虚拟主干时会产生大量控制开销。

J.Li等人的另一篇文章(“地理自组路由选择的可缩放定位服务”，ACM MOBICOM 2000)提出分级网格定位服务。但是，它对于车对车网络环境的适用性因嵌入式系统实现强加的有限的处理和存储约束而令人怀疑。

M.Sun等人的一篇文章(“用于车辆间通信的基于GPS的消息广播”，IEEE International Conference on Parallel Processing，2000)描述了边界节点(选择性)泛搜索的构思。所建议的算法的本质是根据相邻者相对发送方的位置选择多个相邻者来重播消息。但是，M.Sun等人提出的算法具有两个主要限制。首先，它不可缩放，因为对于大网络，各车辆必须保持携带其它所有车辆的位置信息的巨大表格；第二，它没有针对具有多个交叉道路的任意路标进行优化。这些限制构成了对于M.Sun等人提出的算法在车对车网络环境中的实用性和可行性的主要障碍。

目前已知的和建议的信息传播算法对于动态改变节点密度缺乏可缩放性，例如当节点密度在给定时间周期中在许多节点与少数节点之间循环时。此外，已知的算法没有针对任意节点位置进行优化，并且耗用超过许多嵌入式系统设计的实际限制的存储资源。因此，希望提供一种克服了这些及其它缺点的、用于自组移动网中信息传播的系统和方法。

发明内容

本发明针对用于无线移动自组网中的信息传播的方法。该方法描述：接收把消息从源节点传递到目的地的请求；标识自组网的各相邻节点；当目的地为相邻节点并且其中到目的地的跳数小于预定跳数时，在源节点上调用主动式边界节点广播协议；当从源节点到目的地的跳数超过预定数量时，在源节点上调用请求式边界节点广播协议；以及根据所调用的广播协议从源节点传递消息。

根据本发明的另一方面，提供一种用于无线移动自组网中的信息传播的系统。该系统描述：用于确定把消息从源节点传递到目的地节点的请求的部件；用于标识自组网的各相邻节点的部件；用于在目的地为相邻节点且其中到目的地的跳数小于预定跳数时、在源节点上调用主动式边界节点广播协议的部件；用于在从源节点到目的地的跳数超过预定数量时在源节点上调用请求式边界节点广播协议的部件；以及用于根据所调用的广播协议从源节点传递消息的部件。

根据本发明的又一个方面，提供一种计算机可读媒体。该计算机可读媒体包括：用于确定在源节点与目的地之间传递消息的请求的计算机可读代码；用于标识自组网的各相邻节点的计算机可读代码；用于在目的地为相邻节点并且其中到目的地的跳数小于预定跳数时、在源节点上调用主动式边界节点广播协议的计算机可读代码；用于在从源节点到目的地的跳数超过预定数量时、在源节点上调用请求式边界节点广播协议的计算机可读代码；以及用于根据所调用的广播协议指导消息从源节点传递的计算机可读代码。

通过结合附图阅读以下对目前优选实施例的详细描述，本发明的上述及其它特征和优点将变得更加明显。详细说明和附图对于本发明只是说明性而不是限制性的，本发明的范围由所附权利要求及其等效物来定义。

附图说明

图1说明根据本发明的移动车辆通信系统的一个实施例。

图2说明根据本发明的移动车辆通信系统的第二实施例。

图3说明根据本发明、用于确定移动自组网边界节点的几何选择标准。

图4是根据本发明的一个实施例、用于无线移动自组网中的信息传播的方法的流程图。

具体实施方式

图1说明总体表示为100的移动车辆通信系统(MVCS)的一个实施例。移动车辆通信系统100包括移动车辆110、车辆通信总线112、车辆通信单元(VCU)120、一个或多个无线载波系统140、一个或多个通信网络142、一个或多个陆地网144、一个或多个客户机、个人或用户计算机150、一个或多个网站托管入口160以及一个或多个呼叫中心170。在一个实施例中，移动车辆110实现为配备了用于发送和接收语音及数据通信的适当硬件和软件的移动车辆。

在一个实施例中，车辆通信单元120为远程信息处理单元，其中包括数字信号处理器(DSP)122，它连接到无线调制解调器124、全球定位系统(GPS)单元126、车载存储器128、话筒130、一个或多个喇叭132、嵌入式或车载移动电话134以及无线接入点节点136。在一个实施例中，DSP 122为微控制器、控制器、主处理器或车辆通信处理器。在一个实例中，DSP 122实现为专用集成电路(ASIC)。GPS单元126提供车辆的经度和纬度坐标以及速度大小和方向。车载移动电话系统134为蜂窝电话，例如模拟、数字、双模、双频带、多模或多频带蜂窝电话。在另一个实例中，移动电话系统是在标称为800MHz的指定频带上工作的模拟移动电话系统。移动电话系统是在标称为800MHz、900MHz、1900MHz的指定频带或者能够承载移动通信的任何适当频带上工作的数字移动电话系统。

DSP 122执行各种计算机程序以及通信控制和协议算法，它们控制移动车辆110内电子和机械系统的通信、编程及工作模式。在一个实施例中，DSP 122为嵌入式系统控制器。在另一个实施例中，DSP122控制远程信息处理单元120、无线载波系统140和呼叫中心170之间的通信。在另一个实施例中，DSP 122控制无线接入点节点136与移动自组网的节点之间的通信。DSP 122产生和接收在远程信息处理单元120与连接到车辆110中各种电子模块的车辆通信总线112之间传送的数字信号。在一个实施例中，数字信号激活编程模式和工作模式，以及提供数据传输。

移动车辆110经由车辆通信总线112向移动车辆110内设备和系统的各种单元发送信号，从而执行各种功能，例如开门、打开行李箱、设置个人喜欢的设定以及从远程信息处理单元120发出呼叫。在实现各种通信和电子模块之间交互时，车辆通信总线112利用总线接口，例如控制器区域网(CAN)、国际标准化组织(ISO)标准9141、用于高速应用的ISO标准11898、用于低速应用的ISO标准11519以及用于高速和低速应用的汽车工程师学会(SAE)标准J1850。在一个实施例中，车辆通信总线112为所连接装置之间的直接连接。

移动车辆110经由远程信息处理单元120从无线载波系统140发送和接收无线电传输。无线载波系统140实现为用于从移动车辆110向通信网络142传送信号的任何适当系统。无线载波系统140结合其中电磁波通过部分或整个通信通路传送信号的任何类型的远程通信。在一个实施例中，无线载波系统140传送模拟音频和/或视频信号。在一个实例中，无线载波系统140传送例如从AM和FM无线电台和发射机发送的那些模拟音频和/或视频信号、或者S频带(批准在美国使用)以及L频带(用于欧洲和加拿大)的数字音频信号。在一个实施例中，无线载波系统140为在已经由美国联邦通信委员会(FCC)分配用于基于卫星的数字音频无线电服务(DARS)的全国广播的“S”频带(2.3GHz)中的频谱上广播的卫星广播系统。在一个实例中，无线载波系统140实现为XM卫星无线电。

通信网络142包括来自一个或多个移动电话交换局和无线网络的业务。通信网络142把无线载波系统140连接到陆地网144。通信网络142实现为把无线载波系统140连接到移动车辆110和陆地网144的任何适当的系统或者系统集合。在一个实例中，无线载波系统140包括仿照诸如IS-637 SMS标准、SMS的IS-136空中接口标准以及GSM 03.40和09.02标准等已建立协议的短消息业务。与寻呼相似，SMS通信可向许多区域接收者广播。在另一个实例中，载波采用符合例如IEEE 802.11顺从系统和蓝牙系统等其它标准的业务。

陆地网144为公共交换电话网。在一个实施例中，陆地网144实现为因特网协议(IP)网络。在其它实施例中，陆地网144实现为有线网络、光网络、光纤网络、另一个无线网络或者它们的任何组合。陆地网144连接到一个或多个陆线电话。陆地网144把通信网络142连接到用户计算机150、网站托管入口160和呼叫中心170。通信网络142和陆地网144把无线载波系统140连接到网站托管入口160和呼叫中心170。

客户机、个人或用户计算机150包括计算机可用媒体，以便运行因特网浏览器和因特网访问计算机程序，用于通过陆地网144以及可选的有线或无线通信网络142向网站托管入口160发送或从其中接收数据。个人或用户计算机150利用诸如超文本传输协议(HTTP)和传输控制协议因特网协议(TCP/IP)等通信标准通过网页界面向网站托管入口发送驾驶员首选项。在一个实施例中，数据包括改变移动车辆110内电子和机械系统的某些编程和工作模式的指示。在工作中，驾驶员利用用户计算机150设置或重置移动车辆110的用户首选项。来自客户机端软件的用户首选项数据被传送给网站托管入口160的服务器端软件。用户首选项数据存储在网站托管入口160。

网站托管入口160包括一个或多个数据调制解调器162、一个或多个万维网服务器164、一个或多个数据库166以及总线系统168。网站托管入口160通过线路直接连接到呼叫中心170，或者通过电话线路连接到与呼叫中心170连接的陆地网144。网站托管入口160通过一个或多个数据调制解调器162连接到陆地网144。陆地网144与调制解调器162相互发送数字数据；数据随后被传递给万维网服务器164。在一个实现中，调制解调器162驻留在万维网服务器164中。陆地网144在网站托管入口160与呼叫中心170之间传送数据通信。

万维网服务器164经由陆地网144从用户计算机150接收数据。在备选实施例中，用户计算机150包括无线调制解调器，用以通过无线网络142和陆地网144向网站托管入口160发送数据。数据由调制解调器162接收，并被发送到一个或多个万维网服务器164。在一个实施例中，万维网服务器164实现为能够提供万维网服务以便发送和接收从用户计算机150到移动车辆110中的远程信息处理单元120的数据的任何适当的硬件和软件。万维网服务器164经由总线系统168向一个或多个数据库166发送以及从其中接收数据传输。万维网服务器164包括用于管理车辆数据的计算机应用程序和文件。

在一个实施例中，一个或多个万维网服务器164经由总线系统168连网，从而在其网络组件、如数据库166之中分配用户首选项数据。在一个实例中，数据库166为独立于万维网服务器164的计算机的组成部分。万维网服务器164经由调制解调器162以及通过陆地网144向呼叫中心170发送具有用户首选项的数据传输。

呼叫中心170为这样一个位置，在这个位置，同时接收许多呼叫并同时为它们提供服务，或者同时发送许多呼叫。在一个实施例中，呼叫中心是远程信息处理呼叫中心，规定与移动车辆110中的远程信息处理单元120的通信。在一个实例中，呼叫中心为语音呼叫中心，提供呼叫中心的顾问与移动车辆的用户之间的语言交流。在另一个实例中，呼叫中心包含这些功能中的每一个。在其它实施例中，呼叫中心170和网站托管入口160位于相同或不同的设施中。

呼叫中心170包含一个或多个语音和数据交换机172、一个或多个通信服务管理器174、一个或多个通信服务数据库176、一个或多个通信服务顾问178以及一个或多个总线系统180。

呼叫中心170的交换机172连接到陆地网144。交换机172从呼叫中心170发送语音或数据传输，以及通过无线载波系统140和/或无线接入点节点136、通信网络142和陆地网144从移动车辆110中的远程信息处理单元120接收语音或数据传输。交换机172从一个或多个网站托管入口160接收以及向其发送数据传输。交换机172经由一个或多个总线系统180从一个或多个通信服务管理器174接收以及向其中发送数据传输。

通信服务管理器174是能够向移动车辆110中的远程信息处理单元120提供通信服务的任何适当的硬件和软件。通信服务管理器174经由总线系统180向一个或多个通信服务数据库176发送以及从其接收数据传输。通信服务管理器174经由总线系统180向一个或多个通信服务顾问178发送以及从其接收数据传输。通信服务数据库176经由总线系统180向通信服务顾问178发送以及从其接收数据传输。通信服务顾问178从交换机172接收或向其发送语音或数据传输。

通信服务管理器174有助于一个或多个服务，例如但不限于登记服务、导航帮助、查号服务、路边帮助、商业或住宅帮助、信息服务帮助、紧急援助以及通信帮助和车辆数据管理服务。通信服务管理器174经由用户计算机150、网站托管入口160和陆地网144接收用户对服务的服务请求。通信服务管理器174通过无线载波系统140、通信网络142、陆地网144、无线接入点节点136、语音和数据交换机172以及总线系统180向移动车辆110中的远程信息处理单元120发送以及从其中接收用户首选项和其它类型的车辆数据。通信服务管理器174存储或检索来自通信服务数据库176的车辆数据和信息。通信服务管理器174向通信服务顾问178提供所请求的信息。

在一个实施例中，通信服务顾问178为实际的顾问。在另一个实施例中，通信服务顾问178实现为虚拟顾问。在一个实例中，实际的顾问为处于服务提供商服务中心、经由远程信息处理单元120与移动车辆110中的服务用户进行语言交流的人。在另一个实例中，虚拟顾问实现为响应来自移动车辆110中的远程信息处理单元120的请求的合成语音界面。

通信服务顾问178向移动车辆110中的远程信息处理单元120提供服务。通信服务顾问178提供的服务包括登记服务、导航帮助、实时通信量咨询、查号服务、路边帮助、商业或住宅帮助、信息服务帮助、紧急援助以及通信帮助。通信服务顾问178通过无线载波系统140、通信网络142以及陆地网144利用语音传输或通过通信服务管理器174和交换机172利用数据传输与移动车辆110中的远程信息处理单元120进行通信。交换机172在语音传输和数据传输之间进行选择。

移动车辆110通过向远程信息处理单元120发送语音或数字信号命令，远程信息处理单元120又通过无线调制解调器124、无线载波系统140、通信网络142以及陆地网144向呼叫中心170发送指示信号或语音呼叫，从而向呼叫中心170发起服务请求。在另一个实施例中，服务请求是针对车辆数据上载，如本领域已知的那样。在另一个实施例中，移动车辆110从呼叫中心170接收请求，以便通过远程信息处理单元120经由无线调制解调器124、无线接入点节点136、无线载波系统140、通信网络142和陆地网144向呼叫中心170发送来自移动车辆110的各种车辆数据。

图2是本发明的一个实施例的第二示范操作环境的框图。图2表示无线移动自组网200的一个实施例。图2说明五个移动车辆210、220、230、240和250，其中的每个能够通过例如图1的VCU 120的车辆通信单元(VCU)进行无线通信。在一个实施例中，各车辆包含无线接入点节点，例如符合IEEE 802.11的无线收发信机单元、全球定位系统(GPS)收发信机、数字无线电单元和蜂窝电话。在另一个实施例中，为来自远程信息处理服务提供商的用户服务注册各车辆的VCU。

在工作中，车辆210、220、230、240和250是移动的，并且当各车辆通过道路和高速公路时改变相对彼此的位置。在一个实施例中，移动自组网200的各车辆能够向符合IEEE 802.11的装置发送以及从其接收消息。在另一个实施例中，为无线移动自组网200实现不同于IEEE 802.11标准的多址控制层(MAC)。在一个无线移动自组网中，源节点的无线电范围内的所有无线接入点装置组成该源节点的相邻者或相邻节点的集合。

在图2中，各车辆是无线自组网200的节点。在一个实施例中，只要自组网车辆中的至少一个与固定节点进行无线电联系，则固定无线装置(未示出)为相邻节点。各相邻节点有权访问来自网络中其它每个节点的传输，通过直接地从单元到单元或者间接地通过到中间相邻节点的跳。例如，在图2中，车辆210表示为与车辆220进行无线电通信。车辆220还表示为与车辆250通信。车辆240表示为与车辆210通信。因此，车辆240能够通过车辆210与车辆250通信，因为车辆250能够通过车辆220与车辆210通信。

通过移动自组网中的中间相邻节点进行通信的能力允许网络中的节点之间的更大的物理距离，同时仍然为所有节点提供对网络的访问。消息通过移动自组网200中的多跳路由的路由选择取决于网络中各节点的资源。例如，在移动车辆环境中，系统资源往往不允许支持容纳与网络中的所有路由或节点有关的信息的极大路由表的奢侈。这种节点表要求随机存取存储器形式的昂贵存储开销，它在车辆的嵌入式系统中通常非常宝贵。但是，如果这些表存储关于相邻节点(例如达到某个跳数以外)的信息，则随着开销存储减少，车辆系统资源变得不太重要。明智地选择相邻车辆(边界节点)作为转发器来传送消息消除了对于向网络中每个节点发送消息的需要。在源节点的无线电范围内的车辆和可能节点的数量将取决于通信量密度和用户数量。

对于车辆间通信环境中的移动无线自组网200存在许多实际应用。一个实施例包括估计给定地理区域中的通信量及其流速率。在另一个实施例中，移动无线自组网200用于检索来自服务提供商的信息。在另一个实施例中，实现移动车辆自组网200，以便通过由共同配合向蜂窝基站转发其相应请求的车辆组成的自组网来扩展蜂窝基础设施的覆盖范围。在又一个实施例中，依次排列的车辆共同合作，作为共享探险地图或路线的车队。在又一个实施例中，监测停车场的固定节点在其存储器提供可用的停车空间信息或者可兑换即时优惠券。另一个实施例包括使驾驶员能够在类似电话会议环境(例如使用基于IP的语音)与有共同兴趣的附近其它驾驶员聊天。具体来说，设想车对车移动自组网用于两个重要目的：首先，它们考虑其中系统达到过负荷的闹市区中的现有蜂窝系统，并且最好让汽车在达到基站方面相互帮助而不是争用同一个基站。第二，它们扩展基于蜂窝的预订服务基础设施的覆盖范围。

一种选择中间相邻节点以便在移动车辆自组网内重播信息的方法是把标识符包含在用于特定节点的消息中。以这种方式，消息被广泛地广播，但被除所选标识节点之外的所有节点忽略。首先，源节点要求与其无线电范围内的相邻节点有关的信息。这是利用“hello”数据包或定期信标得到的信息，本领域的技术人员会知道。相邻节点信息包括但不限于各响应节点的唯一地址或标识(ID)。

根据本发明的一个实施例，选择性泛搜索算法调用边界节点广播协议来选择用于信息传播的边界节点以及得到关于其它节点的信息。在一个实施例中，该算法由以下伪代码表示：

边界_广播(车辆i)

{

1.车辆‘i’发送请求其相邻者的位置信息的消息。

2.For(j＝1；j≤#目邻者(i)；j++)

车辆‘j’通过向车辆‘i’发送[pos(j)]来应答。

3.车辆‘i’选择多个‘B’边界相邻者用于重播其消息。

4.对于‘i’希望广播或重播的各消息x，车辆i向其相邻者广播该消息以及所选边界车辆的ID。

5.For(j＝1；j≤#相邻者(i)；j++)

If(j＝{边界车辆的ID})

边界_广播(j)

}

前面的伪代码适用于传播诸如通过请求式路由协议所产生的路由请求(RR)消息之类的各种信息以及诸如描述节点在网络所覆盖的地理区域中所处位置的GPS数据之类的位置信息。

在另一个实施例中，对网络中的所有节点以循环方式定期调用上述伪代码算法，以便通过由以下伪代码表示的过程实现主动式边界节点传播协议(其中各节点轮流传播其信息)：

Main()

{

For(i＝1；i≤#车辆；i++)

边界_广播(i)

}

此外，消息“x”携带各车辆的位置信息。因此，对于基于位置的路由算法，大表格必须存储在各车辆上，这在嵌入式系统环境中是不实际的。

在请求式实现中，每当源车辆(节点)希望定位或建立到目标车辆(节点)的通信路由时，均调用边界_广播(i)算法。在这种情况下，消息“x”包含关于目的地信息的查询，这减轻了存储大的相邻节点表的要求。如果消息“x”包含RR消息，则这个算法将直接适用于请求式路由协议(例如AODV和DSR)中的路由发现阶段。

对于基于位置的路由协议实现，上述请求式信息传播方法涉及两个阶段(一旦发现目的地，它把其信息回送给源)。这经由从源到目的地的广播阶段中建立的路由来进行(正象请求式路由协议中的路由发现阶段)。

在另一个实施例中，混合信息传播协议包括离源一直到预定跳数调用主动式边界节点传播算法。在预定跳数之外，调用请求式边界节点算法。当源车辆(节点)要求目标车辆(节点)的位置信息时，它搜索其相邻节点表(由主动式边界车辆广播创建)。如果没有发现目的地，则启动请求式边界车辆广播算法。在一个实施例中，在交换到请求式边界节点传播协议之前允许的跳数是可选的，取决于动态网络参数、如相邻节点的数量。在另一个实施例中，在交换到请求式边界节点传播协议之前允许的跳数处于两跳与十跳之间，最好小于五跳。在一个实施例中，源和目的地之间的各中间“跳”节点(边界节点)被视为源节点到目的地，以及建立广播协议以用于从“跳”节点广播信息。

选择性泛搜索边界节点选择的另一个重要元素是在自组网中提供均匀覆盖的几何规则。

图3说明根据本发明、用于确定移动自组网边界节点的几何选择标准。图3表示源节点邻域300的示意图，包括九个无线节点301、302、303、304、305、306、307、308、309，其中包含源节点309和罗盘方向指示符310。所选的边界节点车辆的数量是可被改变以便在效率与性能之间权衡的设计参数。它由下式给出：

B＝f*N， (1)

其中N＝相邻者数量，以及f为分数0.1、0.2、…、1。f＝1的情况是简单泛搜索算法，其中所有相邻者重播发送方的消息。在一个实施例中，根据确定最接近北、南、东和西方向的罗经点的最远相邻节点来选择边界节点车辆，从而保证传播算法对于任何任意道路图的最大覆盖。对于单一道路的特例，沿道路的正、反方向选择至少一个边界车辆。

各种相邻节点相对发送方的方向由相邻节点的坐标来计算，假定参考方向为“东”。相对从参考轴开始的源节点(发送方)确定各相邻节点的角坐标(Φ)。相邻节点根据以下几何规则分类：

最接近“东”向的最远车辆应当满足：

max.d_i cos|Φ_i| (2)

最接近“北”向的最远车辆应当满足：

max.d_i cos|Φ_i-90°| (3)

最接近“西”向的最远车辆应当满足：

max.d_i cos|Φ_i-180°| (4)

最接近“南”向的最远车辆应当满足：

max.d_i cos|Φ_i-270°| (5)

其中d_i＝发送方309与相邻节点“i”之间的距离。

对于图3所示的实例，假定B＝4，运行边界选择算法的源节点309将指定以下各项作为边界车辆，以及把其ID包含在广播消息中：

最接近东向的车辆为306

最接近北向的车辆为306

最接近西向的车辆为302

最接近南向的车辆为307

在一个实施例中，根据参数“B”选择各罗经点方向的一个以上边界车辆，以便增加传播算法的可达性，它被定义为成功定位车辆的尝试的百分比。在另一个实施例中，选取八个边界节点。在又一个实施例中，对于每个象限选择至少两个节点。

图4是根据本发明的一个实施例、用于无线移动自组网中的信息传播的方法400的流程图。方法400以步骤410开始。在一个实施例中，当计算机程序由处理器执行时，使存储计算机程序的计算机可读媒体能够实现方法400的一个或多个步骤。

在步骤410，收到把信息从源节点传递到目的地的请求。在一个实施例中，接收传递信息的请求包括从源节点或者连接到源节点的远程信息处理装置中发出新的消息。在另一个实施例中，接收传递信息的请求包括从移动自组网的另一个节点接收信息请求。

在步骤420，自组网的各相邻节点被标识。在已经接收到传递信息的请求之后的任何时间可发生步骤420。在一个实施例中，标识各相邻者包括轮询各相邻节点以便得到位置信息，从响应轮询的各相邻节点接收位置信息，以及产生标识各相邻节点的位置的相邻节点表。

在步骤430，当信息目的地为相邻节点并且到目的地的跳数小于预定跳数时，在源节点调用主动式边界节点广播协议。在一个实施例中，计算机可读媒体存储计算机程序，其中具有用于在消息目的地为相邻节点并且到目的地的跳数小于预定跳数时在源节点调用主动式边界节点广播协议的计算机可读代码。在另一个实施例中，在由参照图2和图3所述的伪代码所表示的过程中，用于选择性边界节点泛搜索的算法选择用于信息传播的边界节点，并得到与源节点的无线电范围内的相邻节点有关的信息。

在步骤440，当从源节点到目的地的跳数超过预定数量时，在源节点调用请求式广播协议。在已经接收到传递信息的请求之后的任何时间可发生步骤440。在一个实施例中，计算机可读媒体存储计算机程序，其中具有用于在从源节点到目的地的跳数超过预定数目时在源节点调用请求式边界节点广播协议的计算机可读代码。在另一个实施例中，在由参照图2和图3所述的伪代码所表示的过程中，用于选择性泛搜索的算法选择用于信息传播的边界节点，以及得到与源节点的无线电范围内的相邻节点有关的信息。

在步骤450，根据所调用的广播协议从源节点传递信息。在一个实施例中，根据边界节点广播协议传递信息的步骤包括：根据相邻节点的地理位置以及几何标准，选择至少一个相邻节点作为边界节点；以及从源节点广播信息，其中从源节点广播的信息标识各个选取的一个边界节点，用作“跳”节点和通信目的地。

在一个实施例中，根据边界节点广播协议传递信息的步骤还包括在所选边界节点接收广播信息，在边界节点调用边界节点广播协议，以及根据所调用的边界节点广播协议从边界节点向目的地重播已接收信息。

在另一个实施例中，预定跳数是可选的。在又一个实施例中，根据相邻节点的地理位置以及几何标准选择至少一个相邻节点作为边界节点的步骤包括确定至少一个相邻节点，它具有与源节点的最大距离以及到罗经点方向北、南、东和西其中之一的最小距离。在一个实施例中，对于各罗经点方向北、南、东和西，选择至少一个边界节点。

在另一个实施例中，根据请求式边界节点广播协议传递消息的步骤包括：产生目的地查询消息；根据相邻节点的地理位置以及几何标准，选择相邻节点作为边界节点；以及从源节点进行广播，其中该消息标识各所选边界节点以及目的地查询消息。

在又一个实施例中，查询消息为请求式路由协议(例如AODV和DSR)的类别中的路由请求。在另一个实施例中，根据相邻节点的地理位置以及几何标准选择边界节点的步骤包括确定至少一个相邻节点，它具有与源节点的最大距离以及到罗经点方向北、南、东和西之一的最小距离。在又一个实施例中，对于各罗经点方向北、南、东和西，选择至少一个边界节点。当已经根据所调用的边界节点广播协议传递了消息时，方法400结束。

可以预计，本发明还将以没有背离其实质或基本特征的、没有描述的其它具体形式来实施。所述实施例在所有方面应看作仅仅是说明性的而非限制性的。

Claims

1.一种用于无线移动自组网中的信息传播的方法，包括：

接收把信息从源节点传递到目的地的请求；

标识自组网的各相邻节点；

当所述目的地为相邻节点以及其中到所述目的地的跳数小于预定跳数时，在所述源节点调用主动式边界节点广播协议；

当从所述源节点到所述目的地的跳数超过所述预定数量时，在所述源节点调用请求式边界节点广播协议；以及

根据所调用的广播协议从所述源节点传递所述信息。

2.如权利要求1所述的方法，其特征在于，标识各本地节点的步骤包括：

轮询各相邻节点以便得到位置信息；

从响应所述轮询的各相邻节点接收位置信息；以及

产生标识各相邻节点的位置的相邻节点表。

3.如权利要求1所述的方法，其特征在于，根据所述调用的边界节点广播协议传递所述信息的步骤包括：

根据所述相邻节点的地理位置以及几何标准，选择至少一个相邻节点作为边界节点；

从所述源节点广播所述信息；以及

其中所述广播信息标识所选择的至少一个边界节点和通信目的地。

4.如权利要求3所述的方法，其特征在于还包括：

在所述选择的边界节点接收所述广播信息；

在所述边界节点调用边界节点广播协议；以及

根据所述调用的边界节点广播协议从所述边界节点向所述目的地重播所述接收的信息。

5.如权利要求1所述的方法，其特征在于，所述预定跳数是可选的。

6.如权利要求3所述的方法，其特征在于，根据所述相邻节点的地理位置以及几何标准选择至少一个相邻节点作为边界节点的步骤包括：

确定至少一个相邻节点，所述相邻节点具有与所述源节点之间的最大距离以及到罗经点方向北、南、东和西其中之一的最小距离。

7.如权利要求6所述的方法，其特征在于，对于各罗经点方向北、南、东和西选择至少一个边界节点。

8.如权利要求1所述的方法，其特征在于，根据所述请求式边界节点广播协议传递所述信息的步骤包括：

产生目的地查询消息；

根据所述相邻节点的地理位置以及几何标准，选择至少一个相邻节点作为边界节点；以及

从所述源节点广播所述信息；

其中所述信息标识所述至少一个所选相邻节点和所述目的地查询消息。

9.如权利要求8所述的方法，其特征在于，所述目的地查询消息是用于请求式的基于拓扑的路由协议的路由请求消息。

10.如权利要求8所述的方法，其特征在于，根据所述相邻节点的地理位置以及几何标准选择至少一个相邻节点作为边界节点的步骤包括：

确定至少一个相邻节点，所述相邻节点具有与所述源节点之间的最大距离以及到所述罗经点方向北、南、东和西其中之一的最小距离。

11.如权利要求10所述的方法，其特征在于，对于各罗经点方向北、南、东和西选择至少一个边界节点。

12.一种存储计算机程序的计算机可读媒体，包括：

用于确定在源节点和目的地之间传递信息的请求的计算机可读代码；

用于标识自组网的各相邻节点的计算机可读代码；

用于在所述目的地为相邻节点并且其中到所述目的地的跳数小于预定跳数时在所述源节点调用主动式边界节点广播协议的计算机可读代码；

用于在从所述源节点到所述目的地的跳数超过所述预定数量时在所述源节点调用请求式边界节点广播协议的计算机可读代码；以及

用于根据所述调用的广播协议指导从所述源节点传递所述消息的计算机可读代码。

13.如权利要求12所述的计算机可读媒体，其特征在于，用于标识自组网的各相邻节点的计算机可读代码包括：

用于轮询本地区域以便得到各相邻节点的位置信息的计算机可读代码；以及

用于根据从响应所述轮询的各相邻节点接收的位置数据产生标识各相邻节点的位置的相邻节点表的计算机可读代码。

14.如权利要求12所述的计算机可读代码，其特征在于，用于根据所述边界节点广播协议指导从所述源节点传递信息的代码包括：

用于根据所述相邻节点的地理位置以及几何标准来选择至少一个相邻节点作为边界节点的计算机可读代码；

指示从所述源节点广播所述信息的计算机可读代码；以及

其中所述信息标识所选的至少一个边界节点和通信目的地。

15.如权利要求14所述的计算机可读媒体，其特征在于还包括：

用于在所述所选边界节点接收所述广播信息的计算机可读代码；

用于在所述边界节点调用边界节点广播协议的计算机可读代码；以及

用于根据所述调用的边界节点广播协议从所述边界节点向所述目的地重播所接收信息的计算机可读代码。

16.如权利要求12所述的计算机可读媒体，其特征在于，用于选择至少一个边界节点的代码包括：

用于确定至少一个相邻节点的计算机可读代码，所述相邻节点具有与所述源节点之间的最大距离以及到罗经点方向北、南、东和西其中之一的最小距离。

17.如权利要求12所述的计算机可读媒体，其特征在于，用于在从所述源节点到所述目的地的跳数超过所述预定数量时在所述源节点调用请求式边界节点广播协议的计算机可读代码包括：

用于产生目的地查询消息的计算机可读代码；

用于根据所述相邻节点的地理位置以及几何标准来选择至少一个相邻节点作为边界节点的计算机可读代码；以及

指示从所述源节点广播所述信息的计算机可读代码，其中所述信息标识所述至少一个所选相邻节点和所述目的地查询消息。

18.如权利要求17所述的计算机可读媒体，其特征在于，用于选择至少一个边界节点的代码包括：

19.如权利要求18所述的计算机可读媒体，其特征在于还包括用于对各个罗经点方向北、南、东和西选择至少一个边界节点的代码。

20.一种用于无线移动自组网中的信息传播的系统，包括：

用于确定把消息从源节点传递到目的地节点的请求的部件；

用于标识自组网的各相邻节点的部件；

用于在所述目的地为相邻节点并且其中到所述目的地的跳数小于预定跳数时在所述源节点调用主动式边界节点广播协议的部件；

用于在从所述源节点到所述目的地的跳数超过所述预定数量时在所述源节点调用请求式边界节点广播协议的部件；以及

用于根据所述调用的广播协议从所述源节点传递所述消息的部件。