基于节点度的移动自组网络Grover路由算法研究*

卢 军，邬学军，周 凯

(1.浙江工业大学之江学院理学系，杭州 310024;2.浙江工业大学理学院，杭州 310023)

移动自组织网络(Mobile ad hoc networks，MANET)是一种具有全新的信息获取、信息处理与传输技术的通信网络，通常包含大量的可自组织成多跳无线网络的分布式节点［1］。MANET具有组网快捷、灵活、不受有线网络约束等优点，可用于紧急搜索、灾难救助、军事、医疗等环境中，具有广泛的应用前景。MANET已经引起了学术界和工业界的高度重视，被称为是21世纪最有发展前景的技术之一［2］。作为网络层的核心技术，如何设计MANET路由协议一直是近几年专家学者致力研究的热点问题。对于MANET这种特殊类型的移动通信网络而言，节点通常为笔记本电脑和无线电台等便携式通信设备。这些装置虽然重量轻、移动性好，但主要靠电池供电，由于电池的能量有限，因此节点的发射功率、传输距离和处理数据的能力都受到限制［3］。因此，在进行网络路由协议设计过程中必须要考虑到节电问题，以提高网络的生存时间。

移动自组织网络环境下，节点间的无线链路及由此而形成的网络拓扑结构随节点的位置分布和移动、信道的变化等因素呈现出动态变化的特性，移动自组网络的路由技术面临挑战。国内研究无线传感网络最早从1999年开始，研究内容包括:无线传感网络多跳路由协议、广播和组播协议、MAC协议改进、无线传感网络的性能分析、网络安全和QoS问题等等。QoS是指网络为用户提供的一组可以测量的预定义的服务参数，包括时延、带宽、分组丢失率、能耗和服务覆盖范围等。基于以上这些路由协议的分析和比较，发现现有无线传感网络路由协议主要缺点是:分布式节点计算能力弱，无法保证在任何时候都能胜任服务器角色，节点计算不收敛;网络延时大，节点计算和存储量大。因此，研究一种新的、快速收敛的、实时性强的、网络开销少的、计算量小的路由算法一直是无线传感网络路由技术研究的热点。

1 相关研究

MANET路由协议多是由传统的距离矢量协议和链路状态路由协议发展而来。为了适应网络拓扑的变化，首先出现的是周期更新的路由协议。在这种路由协议中，每个节点维护一张包含到达其它节点的路由信息的路由表。当检测到网络拓扑结构发生变化时，节点在网络中发送更新消息，收到更新消息的节点将更新自己的路由表，以维护一致的、及时的、准确的路由信息，所以路由表可以准确地反映网络的拓扑结构。源节点一旦要发送报文，可以立即获得到达目的节点的路由。因此这种路由协议的时延较小，但是路由协议的开销较大，占用无线信道时间长。基于此，出现了按需更新的路由协议，它是一种当需要发送数据时才查找路由的路由算法。在这种路由协议中，节点不需要维护及时准确的路由信息，当需要向目的节点发送报文时，源节点才在网络中发起路由查找过程，找到相应的路由。与周期式路由协议相比，按需更新路由协议的开销较小，但是数据报传送的时延较大。因此在MANET中单纯采用周期更新或按需更新路由协议都不能完全解决路由问题，特别是在网络规模不断扩大的时候这两种类型的路由协议就显的力不从心了。

动态源路由协议(Dynamic Source Routing Protocol，DSR)，是一种典型的按需更新反应式路由协议，它使用源路由而不是逐跳路由的算法，数据分组头部携带了到达目的节点的完整路由，收到分组的移动节点根据分组携带的路由信息转发分组。协议运作包括两个部分:路由发现和路由维持。路由发现使网络内的任一节点能够动态地找到到达网络内其节点的路由;路由维持负责实时监测正在使用的路由是否有效。DSR协议是基于最小跳数的路由协议。基于最小跳数意味着同样转发一个分组占用最少的移动节点资源和处理时间，使得分组转发更具效率。但有时候必须考虑这样的问题:在某些区域内移动节点比较稀少，由于节点之间距离较远，节点之间容易移动出彼此的无线覆盖范围，基于最小跳数的DSR路由更容易失效。另一方面，移动节点转发数据分组时，都以跳数最小的路由为优先，在区域节点比较稀少的情况下，会同时有很多节点向同一节点转发分组，这将造成冲突。

本文在动态源路由协议的基础上，提出了基于网络节点度值计算的路由协议。在路由建立过程中，计算网络中各个节点的度值和节点能量，通过操作矩阵与概率扩散矩阵计算网络中节点的选择概率。保留高概率的节点、使得路由搜索过程可以尽快地收敛到高性能的路由信息上。

2 网络节点度值模型

MANET是一种由移动节点组成的动态网络，本节首先描述网络节点的运动状态。节点i在时刻t的位置、速率和运动方向可以依次表示为(xi(t)，yi(t))、vi(t)、θi(t)。因此节点运动模型可以描述如下［4］:

因此在MANET网络中，在时刻t节点i和节点j之间的距离可以表示如下:

MANET中的节点均处于一个自由空间的传播模型中，信号的强度只与其传播距离有关，当两个相邻节点间的距离大到一定程度时，发送端的信号将不能被接收端正确地接收，两个节点间的路由链路断开，此时两个节点间的距离即为最大有效距离R［5］。由N个节点组成的MAENT可以构成一个N×N的邻接矩阵A=(aij(t))N×N，其元素应满足如下关系式:

每个节点都可以通过一个度值用于衡量该节点的连通状况，节点i的度值定义如下所示。节点的度值越高，也说明网络中与该节点相连接的节点也就越多。由于Ad Hoc网络中节点状态随时间动态变化，因此网络中每个节点的度值也在动态变化。

3 Grover网络搜索模型

Grover量子搜索算法是Grover在1966年提出的。依靠量子并行计算的优势，在遍历搜索问题中运用该算法可以大大减少搜索成功的运算次数。量子算法面临的主要问题是解集的振幅太小，因此量子搜索算法策略的核心是:如何迅速地使振幅向解集集中，同时考虑变换的实现复杂性和鲁棒性。也就是说，传统搜索算法考虑的是如何避免在无效路径上进行搜索，而对量子算法来说，搜索所有路径不是困难所在。量子算法寻求的是如何减少、消除非解路径上的振幅，并把它转移到解路径上来［6－7］。

Grover算法的基本思想是通过对系统量子态进行一系列幺正变换，使得各量子基态原先相等的概率幅发生变化，最终使所求解对应量子基态的概率幅达到最大，这就保证了对变化后的量子态进行测量可以以较大的概率获得正确的解［8］。正是这种思想，可以被借鉴到MANET网络的路由搜索中，用于降低网络的计算量。每一次Grover迭代过程可以等价为两次变换:首先使所需要查找的态相位旋转π弧度，这样可以用于标注目标解路径。然后使用通过概率扩散变换矩阵重新分配各个概率的大小。在之前将解路径的振幅标注以后，通过该扩散变换矩阵D可以将其概率放大，同时将其余非解路径的振幅缩小。

Grover搜索思想的特点在于利用矩阵运算，对各种解径的概率进行变换，从而达到放大正确解径概率的目的。通过选择高概率的正确解径，使得搜解过程快速收敛。需要借鉴Grover的思想，最重要的就是构造操作矩阵和概率扩散矩阵。本节首先提出了一种适合MANET网络的扩散矩阵和操作矩阵的构造方式，然后定义了适合MANET网络的Grover运算，建立基于概率计算的路由模型［9］。

根据联通矩阵可以构建N×N的操作矩阵U，对于网络中任一本地节点i，都维护矩阵U=(uimn)N×N。构建方法如下:

uimn为负数表示节点m和本地节点i相邻，是下一跳搜索的解径之一。需要注意的是:为了避免出现路由环路，本地节点i与上一跳节点j的关系，反映在操作矩阵中为uijj=1，说明节点j不是下一跳搜索的解径。扩散矩阵的作用在于放大正确的解径，使得路由搜索快速收敛。在将解径的振幅标注以后，通过该扩散变换矩阵D可以将其概率放大，同时将其余非解路径的振幅缩小。可以证明该矩阵满足幺正矩阵的条件，该概率重分布变换也是幺正变换。构建N×N的概率扩散矩阵D，矩阵在整个路由搜索过程中保持恒定不变［10］:

构建扩散矩阵D和操作矩阵U后，如何定义矩阵运算使得正确解径的概率得以放大，是将Grover搜索思想应用于MANET的另一个难题［11－12］。在路由搜索过程中，定义N×1的节点振幅矩阵γ，用于记录各个节点的概率。每个节点的初始振幅都相等表示如下:

当本地节点i需要确定后续节点发送数据报时，首先通过邻接矩阵构造操作矩阵和扩散矩阵。在上一跳时，节点的振幅矢量为γk，本地节点运算后，每个节点的振幅γk+1。

因为操作矩阵不是单位矩阵，所以得到的概率矢量需要进行归一化处理。本地节点的归一化概率计算公式如下:

算法首先将解路径的相位取反，并在此基础上，对初始节点矢量矩阵进行幺正变换，该变换的作用就是将解路径的振幅放大，同时缩小非解路径的振幅，相应的增大了解路径的被测概率。如此循环迭代直到找到目的节点，此时目的节点维护的概率矢量中，解路径的振幅扩大，非解路径的振幅缩小，将以最大概率可能性得到我们所需要的路由。

4 网络仿真

为了进一步分析提出的基于网路节点态矢量思想的路由协议的性能，本节建立了网络仿真模型对协议进行分析。通过前面的分析可以发现路由搜索过程按照图1进行。

图1 算法流程框图

在一个1 200 m×1 200 m的无线传感网络中，散落着90个节点，这些节点在网络中随机移动。初始时刻节点位置分布如图2所示。移动的速度在［0，5 m/s］之间变化，运动角度在［0，2π］之间随机变化，变化概率服从均匀分布。当节点在下一时刻将要运动至边界时，进行反向运动，在网络中假设每个节点的一跳通信范围是80 m。

图2 某时刻网络节点位置分布图

网络数据传送的成功率可以定义如下:当两个节点需要通信时，如果不能找到合适的路由进行传输，那么就认为数据传输是不成功的。考虑由于不同的节点选择概率对于网络节点成功率所造成的影响，对基于网络节点度值计算思想的路由协议进行仿真分析，得到仿真图如图3所示。

图3 网络数据传输的成功率仿真图

从图3可以发现，选择概率ρ越大，网络数据成功率也就越大，但是同时也伴随着网络计算量的提高。减少计算量使得路由搜索算法尽快收敛，是基于网络节点度值计算思想的路由协议的一个显著优点，本节将对网络的业务计算量进行仿真。对网络计算量进行定义:路由搜索时，每一次乘除运算都认为是一次计算量。对于不同的节点选择概率，针对网络中3160次网络通信业务进行仿真，统计网络平均计算量如图4所示。可见网络计算量随着节点选择概率的增加而增加，因此网络需要在网络通信成功率和网络计算量之间做一个均衡。

对比节点度值计算路由协议与DSR路由协议，虽然DSR可以获得较高的数据传输成功率，得到仿真如图5所示。但是网络计算量是非常庞大的。为了说明这一点，对于基于节点度值计算思想的路由协议与DSR协议在网络计算量上做了比较，得到仿真如图6所示。

图4 网络计算量仿真图

图5 两种路由协议在成功率上的差异仿真图

图6 两种路由协议在计算量上的差异仿真图

5 结束语

本文结合动态源路由协议的特点，提出了一种基于节点度值计算的Grover路由算法。本文利用Grover搜索算法构造操作矩阵和概率扩散矩阵计算得到网络中各节点选择概率，进而进行路由选择。仿真结果表明:本文提出的路由算法可以快速收敛、提供服务质量保障等特点，弥补了已有算法的不足。

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］.清华大学出版社，2005.

［2］郑四海，李腊元.Ad Hoc网络QoS多径路由协议的研究［J］，武汉理工大学学报(交通科学与工程版)，2008，32(3):450－453.

［3］郑祖全.无线自组网技术实用教程［M］.北京:清华大学出版社，2004.

［4］于宏毅.无线移动自组织网［M］.北京:人民邮电出版社，2005.

［5］Garcia-Luna-Aceves J，Roy S.On-Demand Loop-Free Routing with Link Vectors(OLIVE)［J］.IEEE Journal on Selected Areas in Communications，2005，23(3):533－546.

［6］孟利民，周凯，沈鑫宇，等.基于Grover搜索思想的无线自组网络路由算法研究［J］.传感技术学报，2010，23(2):251－255.

［7］Wu Xiaoxin，Bhargava B.AO2P:Ad Hoc on-Demand Position-Based Private Routing Protocol［J］.IEEE Transactions on Mobile Computing，2005，4(4):335－348.

［8］Anastasi G，Conti M，Gregori E，et al.An Energy-Aware Multimedia Streaming Protocol for Mobile Users［J］.Journal of Pervasive Computing and Communications，2006，1(4):42－50.

［9］薛小平，李欣，张思东.基于路由生存时间的Ad Hoc Qos路由［J］.北京交通大学学报(自然科学版)，2007，31(2):23－28.

［10］邬学军，孟利民，华惊宇，等.基于能量控制的无线传感网络最优化算法研究［J］.传感技术学报，2011，24(3):436－439.

［11］袁培燕，李腊元.移动模型对Ad hoc网络路由协议能耗的影响［J］.计算机工程，2007，33(11):123－125.

［12］王敏强，郑宝玉.一种新的应用于Ad Hoc网络的能量感知路由协议［J］.南京邮电学院学报，2005，25(1):13－17.