一种无线自组织网络路由稳定性的度量系统及其方法

摘要

本发明提出一种无线自组织网络路由稳定性的度量系统及其方法，涉及的领域包括Ad hoc网络以及网络的稳定性度量。该系统由定位模块、获取模块和计算模块组成。首先由定位模块得到的节点移动速度矢量和位置矢量数据以及由获取模块得到的发送速率和信道容量数据被添加在路由协议的RREP包中发送给源节点，然后由源节点根据本发明所提供的度量计算方法对这些数据信息进行分析计算并得到该网络路由的动态稳定域。从而可以由得到的动态稳定域快速在线地判断路由稳定性。

说明书

技术领域

本发明涉及一种在无线自组织网络中路由稳定的评价体系，特别是提供了一种适用于节点移动性强的Ad hoc网络的自适应的路由稳定性度量系统。

背景技术

近年来，一种叫做无线自组织网络(也称Ad hoc网络)的移动通信网络发展很快，它是一组带有无线收发装置的移动节点(通常是指计算机)组成的临时性自组织的网络系统，具有无中心控制、节点移动、多跳无线连接的特点，可以广泛应用于如野战通信、紧急搜救、临时会议等，敌对和不易建设固定通信设施的环境中。在此网络中，每一移动节点能够作为其它移动节点的基站或路由器进行操作，从而消除了对固定的基站基础架构的需要。

当讨论Ad hoc网络时，基本上有两种网络用法；第一个用法是构建局域网而不用任何设备提供到外部网络(例如互联网)接入的外部网关。这个方案可以在有关灾区的安装、或在战场上的军事安装中找到。其它的和可能更通用的用法是当一个或几个网关向网络提供例如到基于IP的网络的外部连接。在这样的网络配置中，数据分组可以取不同的路由和使用不同的网关，这取决于例如数据业务类型、拥塞或路由花费。

基于分组的路由方案常常围绕分层模型构建通信网络系统，例如OSI参考模型(开发系统互连)。通信软件或硬件被划分成以分级方式工作的几个较小的子单元。信息和通信控制参数在本地向上和向下传递以及在发送和接受端之间、在相同的层之间被传递。每个这样的层负责通信命令中的不同任务。对于路由，按照OSI参考模型的头三层是最重要的。

层1负责数据的比特的物理传输；物理传输的例子例如可以是基于以太网的网络中的有线链路或无线局域网(WLAN)中的无线链路。

层2常称为链路层或MAC层，以及它负责传输大块数据、检错和网络资源协调。

层3称为网络层；它负责使网络中任何节点对之间的通信。这个例如看管路由计算和拥塞控制。为此目的，取决于网络类型而开发了不同的路由协议。

对于Ad hoc网络，基本上有两类现有的路由协议，这些路由协议是先验式(proactive)和反应式(reactive)路由协议。也有可以具有这些协议的组合的协议。

由于Ad hoc网络的特定节点是移动的，网络有必要维持与这些节点的连接性。每个节点都是一台计算机，都有存储、计算和在执行一定的协议下发送数据包和接收数据包的功能。数据包从移动设备“跳”到移动设备，创建传输路径，即路由。直到到达最终目的。然而，当设备移动时，移动设备之间的传输路径常常易于变化。并且，由于Ad hoc网络中无线链路的状态随时可能随周围环境的变化而变化，稀少的带宽资源很容易使网络发送拥塞，造成网络不稳定。鉴于以上分析，拥塞和节点的移动是造成路由不稳的主要原因。路由不稳会造成数据分组丢失。从而在Ad hoc网络的多条路径中，寻找一个路由稳定的评价系统来预测当前的路由状态是否是稳定的十分必要。

目前，对于度量路由稳定而选取最佳路由的技术，比如在NO.5,412,654的美国专利中，其度量就是跳数，即用每一节点其目的节点的跳数作为路由度量。序列号60/476,237的美国临时预决专利申请中，度量依赖于信号强度的“链路可靠性”计算。尽管上述引用的专利中描述的技术适宜于许多无线网络，包括无线Ad hoc网络。但其局限性显而易见。例如，在衰减信道的特定情形中，低成本宽带无线设备不能适宜地跟踪接受端遭遇的信号强度的变化。这部分是因为测量依赖于无线设备的敏感度，部分是因为接收器仅能进行零星的测量，这提供关于实际信号强度变化的不完全信息。

另外，在美国专利No.5,537,394中，为一种固定网络解决方案引入了一种状态预测功能。该方案牵涉到对来自状态监视功能的信息的大量统计计算。但是它不易对无线Ad hoc网络进行调节。

发明内容

为了解决现有评价无线自组织网络路由稳定性的技术的不足，本发明的目的在于提供一种评价无线自组织网络路由稳定性和指导选取稳定路由的方法和系统，具体是为了提高可用的网络资源的效率，这是通过链路状态测量和预测路由机制一起进行速率控制和路由选择的。

该度量系统包括以下几个部分：定位模块，用于对无线自组织网络中的移动设备进行准确定位；具体说每个节点配备GPS定位设备，从而可以为系统中的获取装置提供移动节点的位置、速度和方向；采集模块，用于获取在包括多个节点的网络中的基础结构节点之间的链路和路由状态信息，具体操作是将数据采集装置嵌入每个基础结构节点。目前通常使用的数据流采集装置的技术方案是在电路中设计芯片控制电路，控制各种大容量随机存储器芯片，利用通用控制芯片配合进行数据流采集。采集装置可以是通用的采集器或卡，比如TI公司的TLC5540嵌入式数据采集卡或者SDY2500型瞬态数据采集器等；由采集装置，对每个节点进行检测，获取通过(发送或接收)的数据流数量，单位是比特；计算模块，对于获取到的信息按照本发明的计算方法进行计算，具体来说是对采集到的数据比如：节点移动速度、源(发送)节点发送速率、信道容量等数据通过路由协议中的RREP包发送给发送节点，然后由源节点根据本发明所提供的计算方法对该数据进行分析计算；更新模块，由计算模块得到的分析数据来给路由单元更新链路状态信息；确定模块，用于相对于业务内容确定适当的路由。

所述的GPS定位模块通过蓝牙与配备它的移动设备相连，而配备它的移动设备将从GPS卫星定位模块获得的定位信息得到自己的位置信息和方向。

具体方法如下：在Ad hoc网络中的每个节点上配备GPS定位装置，因为每个节点都是一台计算机，都有存储、计算和分析的功能。把网络中移动设备的速度、方向和节点发送和接收到的数据包发送到路由的发起者即源节点。由定位装置得到的节点移动速度矢量和位置矢量以及由获取模块得到的发送速率和信道容量数据信息被添加到路由协议的RREP包中发送给源节点；每个源节点根据反馈到的数据信息采用动态稳定域计算方法进行计算，得到动态稳定域后在网络运行时对采集来的数据进行分析并做出路由选择；例如对某一条路由中数据进行判断，看这些数据是否位于该动态稳定域中，如果没有，则对该路由的源节点发出预警。提示其或降低发送数据包的数量或重新选取路由，在重新选路由时，给发送节点到目的节点提供最稳定的路由。计算动态稳定域的方法如下：

1)建立网络模型：因为每一个节点都是一台高性能计算机，可以根据网络的拓扑结构建立网络模型。针对的是Ad hoc网络，一般表示为赋权图G(N，L)，其中N＝{1，2，…N}为Ad hoc网络的节点集合，L＝{1，2，…L}为节点间能够相互通信的双向链路集合，并且是动态变化的。R＝{1，2，…R}是路由的集合，任意路由r是L的子集。

2)采集网络数据信息：由数据采集器从节点携带的数据库中获取以下信息：无线链路l∈L的传输容量记为C_l；源节点(发送节点)的发送速率x_s(t)。节点的位置坐标(x_s，y_s)、节点的移动速度v_s(t)和节点的覆盖半径R_s(这些可以通过在每个节点上安装GPS设备)。

3)由源节点把采集来的数据信息汇聚并根据公式进行计算。

我们用是链路l上的代价函数，包括由拥塞造成的数据包丢失概率即拥塞代价函数和非拥塞因素造成的数据包丢失的代价函数q_l(t)。其中为通过链路l的发送速率的和。计算步骤如下：

(i)首先计算拥塞代价函数p_l(y)，其中$y=\underset{s:l\in s}{\Sigma }{x}_s\left(t\right).$

其中计算拥塞代价函数的公式为$p_l\left(y\right)=\frac{{(y-c_l)}^{+}}{y},$其中(y-c_l)⁺＝max{y-c_l，0}。并且链路l上由拥塞造成的单位时间内丢失的数据包为其中x_r为源节点的发送速率。

(ii)然后计算非拥塞代价函数(这里指路由不稳定代价函数)：

为了计算非拥塞代价函数，我们首先计算下面几个公式。

(a)由定位装置(一般用GPS定位装置)获取节点的位置向量和速度向量，比如得到一条链路l的两个端点节点i和节点j在t时刻的速度失量分别为v(i，t)和v(j，t)，位置矢量分别为[x_i(t)，y_i(t)]和[x_j(t)，y_j(t)]，则由公式$d_l\left(t\right)=d(i,j,t)=\sqrt{{[x_i\left(t\right)-x_j\left(t\right)]}^2+{[y_j\left(t\right)-y_j\left(t\right)]}^2}$以及公式v(i，j，t)＝v(i，t)-v(j，t)计算它们的相对距离矢量和它们的相对速度矢量。

(b)计算相对移动性度量：我们用a_ij表示，计算公式：a_ij＝|v(i，j，t)|。

(c)计算链路l上的稳定熵：

$H_l\left(t\right)=\frac{-\underset{j\in F\left(i\right)}{\Sigma }{P}_j\left(t\right)\log P_j\left(t\right)}{\log \left|F\left(i\right)\right|}$

这里P_j(t)表示相对位置变化概率，由公式$P_j\left(t\right)=\frac{a_{\mathrm{ij}}}{\underset{l\in F\left(i\right)}{\Sigma }{a}_{\mathrm{il}}}$得到，其中F(i)表示节点i的邻居节点集。这里表示节点i在路由中前后两个邻居节点。所以|F(i)＝2|。

(d)计算路由r的稳定熵：公式为$H_r\left(t\right)=\underset{i\in N_r}{\Pi }\log H_i\left(t\right),$其中N_r表示路由r上中间节点集合。

(e)最后计算非拥塞代价函数。

为了表示非拥塞因素造成的数据包丢失代价，用由位置变化引起的不稳定代价函数q_l(t)＝(1-H_r(t))表示，即由节点移动造成的不稳定概率与链路l上到达的累计发送速率之和的乘积。

(iii)计算动态稳定域：

由上面两个步骤的计算，我们得到了拥塞代价函数和非拥塞代价函数在取值。然后把这些数据带入公式$\frac{{\mathrm{dx}}_r\left(t\right)}{\mathrm{dt}}=k_r[{\omega }_r\left(t\right)-x_r\left(t\right)\underset{l\in r}{\Sigma }{V}_l\left(\underset{s:l\in s}{\Sigma }{x}_s\left(t\right)\right)],$并由此公式编程计算稳定速率，结合公式d_l(t)≤min{R_i，R_j}，$\forall l\in r$来得出路由稳定时的动态稳定域(包括节点发送速率、节点移动速度、节点位置和节点接收半径的稳定范围)。在上面的微分方程式中k_r表示控制增益(范围为远小于1的一个非常小的正数)，ω_r(t)为目标值或承受能力(可根据网络的服务质量要求确定，如设置为发送速率与代价函数的乘积)，。是链路l上的代价函数，包括由拥塞造成的数据包丢失概率和非拥塞因素造成的数据包丢失的代价函数q_l(t)。

本度量系统的使用与所使用的Ad hoc网络的路由协议的类型无关。

该系统的特征在于，各节点之间的通信是一种基于电磁辐射的、具有在100kHz到100PHz范围内频率的传输系统。

该系统的特征还在于，传输系统是IEEE 802.11、IEEE 802.15、IEEE 802.16、蓝牙、3G、GPRS和EDGE的其中之一。

本发明的有益效果：能实时监控路由的运行状况，并在路由存在不稳定时对路由的源节点发出预警和指导。能确保路由的稳定性，使数据包的丢失率达到最低。并且不受Adhoc网络路由协议类别的限制。

参照以下的详细描述，将明白本发明的这个和其它目的、特点、功能和好处。

附图说明

图1是在本发明优选实施例的层间概念中的某些部件和它们的各自作用的示意图。L1为网络第一层，L2为网络第二层，L3为网络第三层；101为路路由单元，102为数据采集装置，103为网关，与外部网络相连，

图2是本发明链路稳定熵的示意图。A-G为网络节点，H_B、H_C、H_D、H_E、H_F、H_G分别为链路AB、BC、CD、AE、EF、FG的稳定熵。

图3无线Adhoc网络拓扑的示意图。其中301、302、303、304、…、30n为基础结构单元(如节点)，节点301为与标准固定网(如互联网)320相连的网关，310表示Ad hoc网络，320表示标准固定网(如互联网)。

图4用于度量无线Ad hoc网络路由稳定的处理过程示意图。

图5网络中节点的示意图。500为节点或基础结构单元，501为定位模块，502为存储模块，503为计算模块，504为路由模块，505为通信模块，506为连接器。

图6计算Adhoc网络路由的动态稳定域的流程图。

具体实施方式

在图1上，显示了在路由单元中的关键部件和它们的各自作用，以及在分层网络参考模型(例如OSI模型)内的数据和控制业务流。第一层(L1)负责数据比特的物理传输，在这一层用来测量和得到物理特性的状态和质量，例如信道的容量和状态，发送的数据包数量(发送速率)和队列大小，这些信息被传递到第三层(L3)给数据采集装置102。数据采集装置把得到的和分析的状态信息传输到路由单元101。该单元101执行路由计算来为目前待发送的数据分组确定路由，它也确定应当何时及如何更新路由表。路由单元101操控发送和接受数据业务和控制业务。它操控处理路由更新，以及按照预定的进度表或根据从数据采集装置102得到的状态信息来启动路由更新。

在图3上，显示了本发明的移动多跳无线Ad hoc网络的基本概念。多个节点或基础结构单元301、302、303、304、…、30n通过互相通信和互相转发数据业务与控制业务而一起构建无线Adhoc网络310，以便保持在通信的末端节点与中间节点之间的网络业务。其中节点301充当了网关，与互联网320进行通信。有时在无线Ad hoc网络310中存在一个或几个网关301。此网关充当310与标准固定网络之间的衔接。

图3上基础结构节点301、302、…、30n所表示的是可以互相通信的用户终端，可包括诸如台式计算机、便携式电脑、工作站或其它具有通信或联网装置的数据处理设备(在本例中选的是便携式电脑)。这些终端至少包括定位模块(GPS定位装置)(501)、存储模块(502)、计算模块(503)和通信模块(505)和路由模块(504)。通信装置505在本实施例中是无线的。路由装置常常使用软件程序以路由算法来实现，以及这些装置常常被嵌入在基础结构单元(节点)中，但它们也可以通过一个连接器506被连接到节点的外部设备中。这个外部设备操控路由或通信装置，以使这些装置能成为无线Ad hoc网络的一部分。我们的度量系统被嵌入到每个节点中。

参考图4，其图示了度量无线Ad hoc网络路由稳定的处理过程示意图，因为这个评价系统不局限于任何路由协议，我们的例子是一个反应式路由协议。由定位装置测量节点位置速度和方向和数据采集装置采集到的速率和信道容量被包括在正常路由回答(RREP)消息中被发回到源节点。源节点由储存装置把这些信息储存起来并利用这些信息，由计算装置根据动态稳定域的计算方法计算出稳定域，在路由装置中路由单元101可以根据所得到的有关当前活动的路由的信息来改变数据分组的路由。整个过程如图4所示。具体步骤如下：

1)无线Ad hoc网络中所有节点在一段时间内测量它们各自的信息和通向邻居节点的链路信息。

2)所以信息被集中到源节点，由源节点计算动态稳定域。

3)源节点根据动态稳定域在以后的时间内判断是否位于稳定域中。

4)如果位于，则可以继续使用该路由，并继续发送数据包。否则，可根据稳定熵的计算重新选取路由并发送数据包，或减小发送数据包的大小。

对于计算动态稳定域的过程可按图6进行。由图6，我们对每一条路由重复以下过程进行计算动态稳定域，步骤如下：

1)建立网络模型：因为每一个节点都是一台高性能计算机，可以根据网络的拓扑结构建立网络模型。针对的是Ad hoc网络，一般表示为赋权图G(N，L)，其中N＝{1，2，…N}为Ad hoc网络的节点集合，L＝{1，2，…L}为节点间能够相互通信的双向链路集合，并且是动态变化的。R＝{1，2，…R}是路由的集合，任意路由r是L的子集。

2)采集网络数据信息：由数据采集器从节点携带的数据库中获取以下信息：无线链路l∈L的传输容量记为C_l；源节点(发送节点)的发送速率x_s(t)。节点的位置坐标(x_s，y_s)、节点的移动速度v_s(t)和节点的覆盖半径R_s(这些可以通过在每个节点上安装GPS设备)。

3)由源节点把采集来的数据信息汇聚并根据公式进行计算。

我们用是链路l上的代价函数，包括由拥塞造成的数据包丢失概率即拥塞代价函数和非拥塞因素造成的数据包丢失的代价函数q_l(t)。其中为通过链路l的发送速率的和。计算步骤如下：

(i)首先计算拥塞代价函数p_l(y)，其中$y=\underset{s:l\in s}{\Sigma }{x}_s\left(t\right).$

其中计算拥塞代价函数的公式为$p_l\left(y\right)=\frac{{(y-c_l)}^{+}}{y},$其中(y-c_l)⁺＝max{y-c_l，0}。并且链路l上由拥塞造成的单位时间内丢失的数据包为其中x_r为源节点的发送速率。

(ii)然后计算非拥塞代价函数(这里指路由不稳定代价函数)：

为了计算非拥塞代价函数，我们首先计算下面几个公式。

(a)由定位装置(一般用GPS定位装置)获取节点的位置向量和速度向量，比如得到一条链路l的两个端点节点i和节点j在t时刻的速度失量分别为v(i，t)和v(j，t)，位置矢量分别为[x_i(t)，y_i(t)]和[x_j(t)，y_j(t)]，则由公式$d_l\left(t\right)=d(i,j,t)=\sqrt{{[x_i\left(t\right)-x_j\left(t\right)]}^2+{[y_j\left(t\right)-y_j\left(t\right)]}^2}$以及公式v(i，j，t)＝v(i，t)-v(j，t)计算它们的相对距离矢量和它们的相对速度矢量。

(b)计算相对移动性度量：我们用a_ij表示，计算公式：a_ij＝|v(i，j，t)|。

(c)计算链路l上的稳定熵：

$H_l\left(t\right)=\frac{-\underset{j\in F\left(i\right)}{\Sigma }{P}_j\left(t\right)\log P_j\left(t\right)}{\log \left|F\left(i\right)\right|}$

这里P_j(t)表示相对位置变化概率，由公式$P_j\left(t\right)=\frac{a_{\mathrm{ij}}}{\underset{l\in F\left(i\right)}{\Sigma }{a}_{\mathrm{il}}}$得到，其中F(i)表示节点i的邻居节点集。这里表示节点i在路由中前后两个邻居节点。所以|F(i)＝2|。

这里构造的熵函数不是信息论中严格意义下的熵，而只是借助与熵的意义和形式所构造的表示链路稳定性的尺度。如附图2，源节点为A，目的节点为D。从A到D有两条路由：分别为A→B→C→D和A→F→G→H→D。每条链路都有一个稳定熵，如链路AB的稳定熵为H_B。

(d)计算路由r的稳定熵：公式为$H_r\left(t\right)=\underset{i\in N_r}{\Pi }\log H_i\left(t\right),$其中N_r表示路由r上中间节点集合。

(e)最后计算非拥塞代价函数。

为了表示非拥塞因素造成的数据包丢失代价，我们用由位置变化引起的不稳定代价函数q_l(t)＝(1-H_r(t))表示，即由节点移动造成的不稳定概率与链路l上到达的累计发送速率之和的乘积。

(iii)计算动态稳定域。

由上面两个步骤的计算，我们得到了拥塞代价函数和非拥塞代价函数在取值。然后把这些数据带入公式$\frac{{\mathrm{dx}}_r\left(t\right)}{\mathrm{dt}}=k_r[{\omega }_r\left(t\right)-x_r\left(t\right)\underset{l\in r}{\Sigma }{V}_l\left(\underset{s:l\in s}{\Sigma }{x}_s\left(t\right)\right)],$并由此公式编程计算稳定速率，结合公式d_l(t)≤min{R_i，R_j}，$\forall l\in r$来得出路由稳定时的动态稳定域(包括节点发送速率、节点移动速度、节点位置和节点接收半径的稳定范围)。在上面的微分方程式中k_r表示控制增益(范围为远小于1的一个非常小的正数)，ω_r(t)为目标值或承受能力(可根据网络的服务质量要求确定)。是链路l上的代价函数，包括由拥塞造成的数据包丢失概率和非拥塞因素造成的数据包丢失的代价函数q_l(t)。

我们用该系统评价Ad hoc网络路由的稳定性：先在一定范围内(从开始到链路失效)由上述方法得到路由的动态稳定域，然后在网络运行时根据节点的信息(如节点的速率、移动速度和相对位置和接收半径)判断是否位于动态稳定域，若没有位于稳定域中，则可比较具体的数据：比如若速率偏大，表示可能会造成路由不稳采取减少数据包的发送的方法；若速率偏小，表示链路利用率不够可增加发送数据包以获取较高的网络效率；若节点相对移动速度过大或相对距离过大或接受半径偏小，表示此条路由可能已经失效，选取另外的路由进行发包。

对于Ad hoc网络，路由的稳定性显得至关紧要，因为节点移动频繁和带宽资源稀少，如果路由不稳定会造成数据包丢失。频繁重传数据包，则造成能量耗费甚至能量耗尽。而对于任意的Ad hoc网络协议来说，实时地评判路由的稳定性对指导选择路由有非常大的作用。如果源节点到目的节点的稳定路由有多条，则我们根据式$H_r\left(t\right)=\underset{i\in N_r}{\Pi }\log H_i\left(t\right)$来选择最稳定路由。