一种基于平面区域划分的Ad Hoc网络多径路由方法

技术领域

本发明涉及计算机网络技术领域的Ad Hoc网络多径路由方法，特别是一种基于平面区域划分的Ad Hoc网络多径路由方法。 

背景技术

Ad Hoc网络(自组织网络)是不依赖于任何固定基础设施的移动节点的动态联合体。由于具有无需基础设施支持、高动态性、无线通信以及多跳传输的高覆盖性等优点，Ad Hoc网络在军事应用、灾难援助等领域具有广泛的应用前景。然而，Ad Hoc网络本身具有的高动态性、多跳传输、能量有限性等特点使得保障可靠的数据传输成为一个关键而棘手的问题。 

相对于传统的单径路由，多径路由在实现负载均衡、提高路由可靠性和容错性方面具有很强的优势，已成为自组织网络路由研究中的热点。多径路由实现是Ad Hoc网络可靠运行的有效保证。多径路由利用多条链路的冗余，提高动态变化系统的可靠性。此外，在一次路由发现过程中找到多条路径，能够减少路由发现次数，并降低传统的差错控制开销与端到端延时，提高网络实时性。使用多径之后，将原本集中在一条路径上的负载分配到了几条不同的路径上，减少了该路径上中间节点的能量消耗，也有利于提高实时性。多径路由可以适应无线网络中节点易失效的特点，从而较好地利用网络拓扑信息。 

多径技术按照多径使用方式分成依次使用单条路径和并发使用多条路径模式，按照路径相互关系分成相交多径、链路不相交多径和节点不相交多径模型。节点不相交多径最能充分利用网络资源，达到负载均衡，但是也最难寻找。 

目前的多径路由一般是在单路径路由(如动态源路由协议DSR和自组织网络按需距离矢量路由协议AODV)的基础上进行扩展，如：分离多径路由(split multipath routing，SMR)，按需多径距离矢量路由(ad hoc on-demand multipath distance vector，AOMDV)，基于选票方式的路由协议(ticket based routing protocol，TBR)。这几种典型的多径路由协议在应用于大规模的网络环境中会存在广播风暴的问题，而且现有的大多数路由方法也没有充分地利用节点的地理位置信息来寻找多条路经。 

发明内容

本发明目的在于提供一种快速建立最大限度不相交多径的路由算法。 

实现本发明目的的技术解决方案为： 

1)源节点计算自身与目的节点之间的距离，将网络中所有节点所在的平面通过椭圆曲线划分成不相交的区域，根据需要的路径条数确定区域的个数以及相应的曲线条数，然后计算各个曲线方程的系数； 

2)源节点将自身与目的节点的地理位置信息，以及曲线方程系数写入数据包头部，并在数据包头部添加访问路径字段，用来存储局部的访问路径，然后根据路由转发策略向下一跳节点转发； 

3)转发节点收到数据包后，从包头部取出源节点与目的节点的地理位置信息，以及曲线方程系数，判断自身所在区域，并根据路由转发策略继续转发； 

4)后续转发节点按照步骤3所述方法继续转发，直至数据包到达目的节点。 

其中计算曲线方程系数的方法如下： 

1)计算源节点和目的节点之间的距离。源节点S通过位置服务(Location Service)获得目的节点D的地理位置坐标D(x_D，y_D)，源节点S的地理位置坐标是S(x_S，y_S)。通过两点之间的距离公式计算源节点和目的节点之间的距离 $d=\sqrt{(x_D-x_S{)}^2+(y_D-y_S{)}^2}.$

2)确定需要的曲线条数。当路径条数为k时，需要 条曲线，这里将直线y＝0和椭圆曲线 统称为曲线，当a，b等于0时，曲线方程为y＝0。 

3)计算曲线方程的系数。根据所需的路径条数k的奇偶性，选择不同的公式计算曲线的方程 中的系数。若k为奇数，则选择公式 $a_0=a_1=a_2=L{a}_{n-1}=\frac{d}{2},$$b_i=\frac{h}{2}+\mathrm{ih}(0\le i\le n-1,i\in N),$$h=\frac{\mathrm{Cd}}{k},$C为常数，计算n个曲线方程系数对(a_i，b_i)(0≤i≤n-1，i∈N)；若k为偶数，选择公式 b_i＝ih(1≤i≤n-1，i∈N)， 计算n-1个曲线方程系数对(a_i，b_i)(1≤i≤n-1，i∈N)，对于a₀，b₀，令a₀＝0，b₀＝0，即曲线方程为y＝0。 

其中判断节点所属区域的方法如下： 

由于节点通过GPS设备获得的地理位置是经纬度坐标系中的坐标，而曲线的 坐标系是以源节点作为原点，以源节点S到目的节点D的有向直线作为x轴的直角坐标系，两者是不同的坐标系，所以需要进行坐标变换。本发明将所有节点视为位于同一平面，于是可以将经纬度坐标系看作直角坐标系，且称其为坐标系Oxy，将以源节点作为原点，以源节点S到目的节点D的有向直线作为x轴建立的直角坐标系称为坐标系O′x′y′，坐标变换如公式(1)所示。 

$\left(\begin{array}{c}{x}^{\prime }\text{=}(x-x_0)\cos \theta +(y-y_0)\sin \theta \\ y^{\prime }=-(x-x_0)\sin \theta +(y-y_0)\cos \theta \end{array}\right)--\left(1\right)$

其中(x₀，y₀)就是源节点S在坐标系Oxy中的坐标(x_S，y_S)，θ为Ox轴与O′x′轴的夹角，即向量 

$\sin \theta =\left(\begin{array}{c}\sqrt{1-\mathrm{co}{s}^2\theta },y_D>y_S\\ -\sqrt{1-{\cos }^2\theta },y_D<y_S\end{array}\right)--\left(3\right)$

根据公式(4)和公式(5)分别计算路径条数k为奇数和偶数的情况下节点是否属于指定区域，其中M_i为划分区域在第一象限的区域编号，M_-i为划分区域在第四象限的区域编号。指定区域指的是从数据包头部取出的曲线系数对所决定的曲线围成的区域。 

具体判断节点是否属于指定区域的算法如下： 

1)节点收到数据包之后，从数据包头部中取出源节点坐标(x_S，y_S)、目的节点坐标(x_D，y_D)和指定区域两条边界曲线的系数a_i，b_i，a_i+1，b_i+1； 

2)使用公式(1)，(2)，(3)可计算出节点经过坐标变换之后的曲线坐标(x′，y′)； 

3)将曲线坐标(x′，y′)代入公式(4)或公式(5)，若不等式方程组成立，则说明节点在指定区域内；否则，说明节点在指定区域外。 

其中路由转发策略如下： 

所述路由转发策略结合区域内转发模式和边线转发模式实现。接收到数据包的节点判断自己是否落在指定区域内，若是，则按照区域内转发模式转发数据；否则，按照边线转发模式转发数据。本发明在数据包头部添加的访问路径字段，用来存储局部的访问路径，以防止环路的产生，并辅助判断所属的转发模式。具体添加方法是在数据包头部的尾部添加访问路径中的节点地址(32位)，并修改数据包长度字段。 

1)弱化贪婪转发策略 

本发明采用的转发策略与经典GPSR(Greedy Perimeter Stateless Routing)协 议中提到的转发策略不同，转发节点每次选择的下一跳节点不一定是比当前节点更靠近目的节点的节点，只要是邻居节点集合中最靠近目的节点的节点即可，我们称此贪婪转发为弱化贪婪转发。当前节点若能找到比自身更靠近目的节点的邻居节点，则处于正常情况，此时先将访问路径字段清空，再将自身写入其中，然后选择最靠近目的节点的邻居节点转发数据。若所有邻居节点都比当前节点更远离目的节点，则处于局部最优的情况，称当前节点为局部最优节点。发生局部最优情况之后，后续节点选择下一跳节点时都要先判断下一跳节点与局部最优节点的位置，若下一跳节点更靠近目的节点，说明可以跳出局部最优的情况，则先将访问路径字段清空，再将自身写入其中；否则直接将自身添加到访问路径字段中，以防止环路的产生。弱化贪婪转发策略在遇到局部最优的情况时，可以有效地绕过空洞区域。 

2)区域内转发模式 

当前节点在区域内寻找比自身更靠近目的节点的邻居节点，若找到则正常转发，否则按照弱化贪婪转发策略寻找邻居节点集合中最靠近目的节点的节点。此节点有可能在区域内，也有可能在区域外。若在指定区域内，则按照区域内转发模式继续转发；若在区域外，则切换到边线转发模式。 

3)边线转发模式 

把发送区域靠近x轴的曲线称为该区域的边线。节点收到数据包以后，先在指定区域内且比访问路径字段中的第一个节点更靠近目的节点的区域寻找，若有节点，则先将访问路径字段清空，再将自身写入其中，选择最靠近目的节点的节点进行转发，然后切换到区域内转发模式；若没有，就在指定区域外且更靠近目的节点的范围内选择最靠近指定区域边线的节点，使得数据转发能够尽快地回到原先的指定区域。此时为了防止环路的产生，直接将自身添加到访问路径字段中。若还是没有找到节点，就在指定区域外，按照弱化贪婪转发策略选择最靠近目的节点的节点作为下一跳。此时，也要将自身添加到访问路径字段中。边线转发模式下“优先考虑能够回到指定区域的节点作为下一跳”的目的是尽量避免路径相交，或在出现相交时尽快脱离相交。 

本发明与现有技术相比，其显著优点：本发明充分利用节点位置信息，在划 分的不相交区域内构造多条路径，既考虑了节点的不相交性，又避免了简单泛洪带来的路由发现开销，提高了路由寻找的效率。弱化贪婪转发策略不要求下一跳节点比当前节点更靠近目的节点，可以有效地绕过空洞区域。若在指定区域内找不到节点时，就从隔壁区域绕行，保证在节点稀疏的情况下也能成功找到路径。启用边线转发模式可以使数据转发尽快地回到原先的指定区域，尽量避免路径相交，或在出现相交时尽快脱离相交。 

附图说明

图1为偶数条路径区域划分示意图。 

图2为奇数条路径区域划分示意图。 

图3为本发明总体流程图。 

图4为计算划分区域曲线方程的流程图。 

图5(a)为区域内转发模式正常情况下转发策略示意图，图5(b)区域内转发模式局部最优情况下转发策略示意图。 

图6为边线转发模式下转发策略示意图。 

图7为区域内转发模式算法流程图。 

图8为边线转发模式算法流程图。 

具体实施方式

本发明构造多径路由是这样实现的：将网络中的所有节点视为位于同一平面区域上，利用GPS设备获取节点的地理位置信息，在该平面上通过椭圆曲线划分成不相交的区域，然后分别在各自区域中寻找一条路径。若在本区域找不到下一跳节点，就转发给相邻区域的节点，并在继续转发的过程中尽快的绕回本区域。本方法保证在节点密集的情况下，可以构造出节点不相交多径；在节点稀疏的情况下，也能找到相交尽可能少的多径，即相交路径条数尽可能少，相交节点个数尽可能少。 

下面结合附图对本发明作进一步详细描述。 

图1和图2是分别在奇数和偶数条路径的情况下，依据本发明提出的平面区域划分方法。以源节点作为原点，以源节点到目的节点的有向直线作为x轴建立直角坐标系，用此坐标系的坐标表示网络中节点的地理位置。过目的节点作一条垂直x轴的直线，把y轴到这条垂线之间的带状区域M进行划分。本发明采用椭 圆曲线进行区域划分。 

网络中节点分布相对均匀时，本发明设计划分出来的每块区域面积S_i一样大，这样可以使每块区域中分布的节点个数差不多，以保证每块区域都能找到路径。 

假设需要构造k条路径。若k为偶数，则需要 条椭圆曲线和一条直线，分别为 i＝1，2，...，n-1和y＝0。由于第四象限与第一象限轴对称，这里我们只讨论第一象限的情况。因为 且 为了使得S₁＝S₂＝L＝S_n-1，可以得出b₁＝b₂-b₁＝L＝b_n-1-b_n-2，令其等于一个常数h，即b_i＝ih(1≤i≤n-1，i∈N)。 

若k为奇数，需要 条椭圆曲线，分别为 i＝0，1，2，...，n-1且 其中，区域M₀为椭圆曲线 的内部区域，区域M_i(1≤i≤n-1)为第i-1条曲线和第i条曲线之间的区域。此时，$b_i=\frac{h}{2}+\mathrm{ih}(0\le i\le n-1,i\in N).$

令 其中，C为常数，d为源节点到目的节点之间的距离，k为需要构造的多径条数。 

结合图5和图6详细描述区域内转发模式和边线转发模式的运行机制。 

在图5的(a)图中，节点A是当前节点，节点B是存在数据包头部中访问路径字段中的唯一节点。区域M_in表示节点A通信半径内落在转发区域内的区域，区域M_out表示落在转发区域外的区域。区域M_in_c表示在区域M_in中比节点A更靠近目的节点的区域，区域M_in_f表示在区域M_in中比节点A离目的节点更远的区域。同理，区域M_out_c表示在区域M_out中比节点A更靠近目的节点的区域，区域M_out_f表示在区域M_out中比节点A离目的节点更远的区域。 

在图5的(b)图中，节点A是当前节点，节点B是存在数据包头部中访问路径字段中的第一个节点。区域M_in、M_out、M_out_f、M_out_c的含义与图(a)中表示的相同，区域M_in_f、M_in_c与图(a)不同，区域M_in_c表示在区域M_in中比节点B更靠近目的节点的区域，区域M_in_f表示在区域M_in中比节点B离目的节点更远的区域。 

图6中，节点A是当前节点，节点B是数据包头部中访问路径字段中的第一 个节点，区域M_in、M_out、M_out_f、M_out_c、M_in_f、M_in_c的划分与图5中的(b)图的划分相同。 

区域内转发模式算法如下： 

1)节点A判断访问路径字段中第一个节点是否属于指定区域，若是，说明上一跳节点处于区域内转发模式，转到2)；否则，说明上一跳节点处于边线转发模式，转到3)； 

2)节点A判断自身是否比访问路径中的第一个节点更靠近目的节点，若是，说明处于正常情况，转到3)；否则，处于局部最优情况，转到4)； 

3)判断图5的(a)图中的M_in_c区域内是否存在节点，若是转到5)；否则，转到6)； 

4)判断图5的(b)图中的M_in_c区域内是否存在节点，若是转到5)；否则，转到6)； 

5)清空访问路径字段，并将自身添加到访问路径字段中，然后选择M_in_c区域内最靠近目的节点的邻居节点作为下一跳节点进行转发，结束； 

6)节点A先不考虑访问路径中的节点，选择最靠近目的节点的邻居节点作为下一跳。然后判断访问路径字段中第一个节点是否属于指定区域，若是，转到7)；否则，转到8)； 

7)节点A判断自身是否比访问路径中的第一个节点更靠近目的节点，若是，转到8)；否则，直接将自身添加到访问路径中，并将数据包发送给下一跳，结束； 

8)先清空访问路径，再将自身添加到访问路径中，然后将数据包发送给下一跳，结束。 

边线转发模式算法如下： 

1)节点A判断图6中的M_in_c区域内是否存在节点，若是转到2)；否则，转到3)； 

2)清空访问路径字段，并将自身添加到访问路径字段中，然后选择M_in_c区域内最靠近目的节点的邻居节点作为下一跳节点进行转发，结束； 

3)节点A判断图6中的M_out_c区域内是否存在节点，若是转到4)；否则，转到5)； 

4)将自己添加到访问路径字段中，然后选择M_out_c区域内最靠近指定区域边线的节点作为下一跳节点进行转发，结束； 

5)判断图6中的M_out_f区域内，除去访问路径字段中的节点，是否还存在其他节点，若是转到6)；否则，数据转发失败，结束； 

6)将自身添加到访问路径字段中，然后在M_out_f区域内，不考虑访问路径中的节点，选择最靠近目的节点的节点作为下一跳节点进行转发，结束。