基于Grover融合理论的无线传感网络路由算法研究*

2016-10-21丁伟杰周凯周国民王勋

传感技术学报 2016年9期

关键词：传感路由时延

丁伟杰，周凯，周国民，王勋

（1.浙江警察学院计算机与信息技术系，杭州310053；2.浙江工业大学信息工程学院，杭州310023；3.浙江工业大学理学院，杭州310023）

基于Grover融合理论的无线传感网络路由算法研究*

丁伟杰1，2，周凯3*，周国民1，王勋1

（1.浙江警察学院计算机与信息技术系，杭州310053；2.浙江工业大学信息工程学院，杭州310023；3.浙江工业大学理学院，杭州310023）

如何在各种网络资源受限制的情况，实现高质量的信息传输是无线传感网络研究领域的关键问题之一。首先，分析了网络传输中所需要考虑的受限制因素，并提出各种因素的计算办法；然后，针对确保服务质量的多目标规划算法存在计算量过大的缺陷，借鉴量子搜索算法中的Grover理论用以降低信息传输过程的搜索计算量；最后，通过Grover理论得到的各种资源路由选择方案，本文采用了计算机控制中的D-S信息融合理论，将多目标规划转化为单目标规划。为了验证本文所提出的Grover融合路由算法，文章建立MATLAB仿真环境，对比传统的DSR路由协议与多目标规划TOPSIS算法，可见本文所提出的算法在降低网络搜索计算量、延长网络生存时间、降低网络时延方面具有较大的改善。

路由协议；多目标规划；Grover算法；数据融合；TOPSIS

EEACC：7230doi：10.3969/j.issn.1004-1699.2016.09.022

无线传感器网络WSN（Wireless Sensor Net⁃work）是一种由大量可自组织形成多跳无线网络的传感节点构成，并实现信息处理与传输的新型网络。由于无线传感网络组网灵活，不受现有基础设备约束等优势，因而被广泛地应用于军事、医疗等领域中［1］，引起了国内外学者的广泛关注。其中，网络路由协议就是无线传感网络研究的热点领域之一。由于传统的分布式路由协议以网络节点为中心，造成网络节点计算量都较大，且无线传感网络的布网环境较有线网络更为恶劣，许多网络资源受到制约（如网络中节点的能量有限）［2］，因此传统的路由协议并不适用于无线传感网络。探索一种能够在资源受限的情况，确保高质量信息传输的路由协议显得尤为重要。

国内学者对于无线传感网络路由协议的研究起源于2001年，有大量关于多跳路由协议的论文相继被发表。相比有限网络路由协议，无线传感网络信息传输过程中，需要兼顾更多的影响因素（如网络节点能量消耗、网络传输时延、分组丢失率等等）。因此，如何在网络资源受限时，提供高质量的信息服务显得更为重要。有相关文献指出［3］：当路由选择时的约束条件包含两个或者两个以上参数组合时，该路由问题便是一个NP完全问题，即多项式复杂程度的非确定性问题，该问题无法使用传统的算法就行求解。国内外的专家也针对这个问题展开了一些研究。如文献［4］提出利用串联排队的方法，降低网络路由的搜索量，实现网络中信息传输的服务质量保障。文献［5］对最重要的几个因素Top-k服务组合进行建模，采用启发式算法（贪婪算法）缩小求解空间，从而实现网络中信息传输的服务质量保障。

由于无线传感网络中的节点计算能力弱，无法实现高质量的实时语音和图像的传输［6］。为了能够在网络中传输高质量的传输服务，同时又能降低网络节点的计算量，本文提出了一种Grover融合的新型无线传感网络路由算法。本文分析了网络传输中所需要考虑的受限制因素，并提出各种因素的计算办法；然后，针对确保服务质量的多目标规划算法存在计算量过大的缺陷，借鉴量子搜索算法中的Grover理论用以降低信息传输过程的搜索计算量；最后，通过Grover理论得到的各种资源路由选择方案，本文采用了计算机控制中的D-S信息融合理论，将多目标规划问题转化为单目标规划问题。

1　网络关键参数计算方法

在一个由N个节点组成的M×M正方形无线传感网络中，Xi（t）表示在时刻t节点i的位置。无线传感网络中，每一个节点都有一个受限的通信半径R。如果两个节点间的距离小于R，则说明节点间可以直接通信；否则节点间需要通过中间节点转发才可以进行通信。在时刻t，节点i和节点j之间的距离lij（t）可以表达如下：

当仅考虑网络时延进行信息传输时，优先考虑时延较少的链路，因此每一条路的被选择概率与该条链路的时延成反比，与该条链路的长度成反比。

无线传感网络中的节点间是靠无线电进行通信。为此，本文可以建立一阶能量消耗模型［9］，如图1所示。

图1　一阶能量消耗模型

发送数据包消耗能量包括发射电路耗能、放大电路耗能两部分，接收数据只有接收电路消耗能量。一阶能量消耗模型数学模型可以表示如式所示［10］：

其中，ETx表示发送者能量消耗，ERx表示接收者能量消耗，Eelec表示发射电路和接收电路的能耗，L表示发送数据包包含的比特数，l表示传输距离，εfs是常数。上述参数典型值为：Eelec=50 nJ/bit，εfs=10 pJ/（bit/m2）。

每条链路的剩余能量由组成该条链路的两端节点剩余能量决定。当两端节点中的任一节点剩余能量耗尽时，该条链路也便宣告失效。因此，链路→的剩余能量Egij（t）表达如下：

其中，Ei（t）表示节点i在当前时刻的剩余能量；Ej（t）表示节点j在当前时刻的剩余能量。

当仅考虑节点剩余能量进行路由选择时，优先选择剩余能量较高的链路进行信息转发。因此每一条路的被选择概率与该条链路的剩余能量成正比。

2　Grover融合多目标路由数学模型

Grover搜索思想的特点在于利用矩阵运算的优势，对各种存在的各种可能解径概率进行变换，从而达到放大正确解径概率，降低非正确解径概率的目的。通过分析可知：运用Grover算法进行搜索的关键就在于构造合适的操作矩阵和概率扩散矩阵［11］。与文献［11］中所构造的操作矩阵、扩散矩阵的方法所有不同：文献中构造的两种矩阵皆以网络分布式节点为主体进行链路的被选择概率计算，从而提高正确的节点被选择概率。而本文研究所针对的时延、剩余能量皆以网络中的链路为主体，从而提高能够确保高质量信息传输服务的链路被选择概率。因此，本文所构造的两个矩阵也是以链路为主体而进行展开。

对于一个N节点构成的无线传感网络将会形成N2条可能的链路。整个网络维护着两个N2×N2链路操作矩阵

扩散矩阵的作用在于放大正确的解径，使得路由搜索快速收敛，该矩阵在整个路由搜索过程中保持恒定不变［12］。可以证明该矩阵满足幺正矩阵的条件，构建N2×N2的概率扩散矩阵D=（dmn）N2×N2的方式如下所示：

在路由搜索过程中，定义1×N2链路振幅矩阵W=（ϖm）1×N2，用于记录各条链路的振幅，表示链路被选择的概率。每条链路的初始振幅都相等表示如下：

根据被测概率等于振幅的平方，满足振幅的平方和等于1的条件。因为操作矩阵不是单位矩阵，所以得到的概率矢量需要进行归一化处理。归一化以后，链路基于能量选择的概率和基于时延选择的概率表达如下：

通过Grover计算后的每条链路都会得到两个被选择概率，分别对应着剩余能量与时延，形成两个网络概率矩阵和这是一个多目标规划问题。本文引入人工智能领域中的D-S证据理论［13］，将链路能量信息和时延信息进行融合，得到每条链路选择概率计算公式如下：

3　网络仿真

为了进一步分析本文所提出Grover融合路由算法的性能，建立了网络仿真模型对协议进行分析。在一个300 m×300 m的矩形无线传感网络中，随机分布50个无线节点，两两之间产生1 225个业务通信请求，采用MATLAB软件进行仿真分析。

为了与本文提出的Grover融合路由算法进行性能比较，本文引入动态源路由协议DSR（Dynamic Source Routing Protocol）与理想状态多目标算法TOPSIS（Technique for Order Preference by Similarity to an Ideal Solution）。其中，DSR是一种专门为多跳无线传感网络而设计的简单、高效的路由协议，该协议动态地维护着网络中所有的路由信息，并进行适时、自动更新。当需要建立路由时，该路由协议可以提供快速反应服务。在DSR路由协议的基础上，考虑网络时延、能量消耗两个网络关键指标，运用TOPSIS算法进行多目标规划的路径选择。TOPSIS求解过程中先依次最优化各个分目标（网络能耗和网络时延），然后在某种意义下使向量目标函数与所考虑问题的理想点的偏差为极小。

在如上的无线传感网络环境中，进行1 225次的业务量仿真，对比两种算法在计算量上的性能差异，部分效果如图2所示。

图2　两种路由策略计算量对比图

从图2可以发现：对于相同的业务请求，两种协议在路由搜索过程中，Grover融合路由算法在网络计算量上普遍低于由DSR-TOPSIS路由协议所产生的计算量。可见，Grover算法的确可以有效地降低由多目标规划问题产生的高计算量问题。

为了评价路由算法在延长网络生存时间所产生的作用，将网络中第一个节点由于能量耗尽退出网络的时间定义为网络生存时间的指标。第一个节点退出网络的时间越迟，说明网络的生存时间越长。因此，也将网络中能量最低的节点称为瓶颈节点。定义网络中每个节点最初时的能量为“1”，运用两种路由协议分别对无线传感网络中的1 225个业务请求进行路由搜索，得到网络中瓶颈节点的能量变化情况如图3所示。从图3可以发现：Grover融合路由算法可以使得网络瓶颈节点能量降低较为缓慢，从而延长网络生存时间。可见，相比于DSR-TOPSIS路由协议，Grover融合路由算法更加有利于延长网络生存时间。

图3　两种算法下瓶颈节点的能量变化图

本文主要考察网络生存时间与网络时延两项网络关键参数。运用两种路由算法分别对无线传感网络中的1 225次业务请求进行路由搜索，并记录每次业务信息传输产生的时延，结果如图4所示。从图4可以发现：Grover融合路由算法的时延普遍低于DSR-TOPSIS路由协议。

图4　两种算法下网络业务传输时延变化图

4　结束语

为了确保高质量的网络信息传输，本文提出了一种基于Grover融合思想的无线传感网络路由算法。在该算法中，通过Grover量子搜索算法降低网络多目标规划的计算量，然后使用D-S融合理论将各指标下的链路概率进行融合得到每条链路的最终选择概率，解决多目标决策的难题。对比于其他的无线传感网络路由协议，本文提出的算法能够有效地降低计算量、延迟网络生存时间、降低网络传输的时延。

［1］Jae Young Seol，Seong Lyun Kim.Node Mobility and Capacity in Wireless Controllable Ad Hoc Networks［J］.Computer Communi⁃cations，2012，35（11）：1345-1354.

［2］Vishwanath Ramamurthi，Abu（Sayeem）Reaz，Dipak Ghosal，et al.Channel，Capacity，and Flow Assignment in Wireless Mesh Networks［J］.Computer Networks，2011，55（9）：2241-2258.

［3］Liu Min，Xu Shijun，Sun Siyi.An Agent-Assisted QoS-Based Routing Algorithm for Wireless Sensor Networks［J］.Journal of Network and Computer Applications，2012，35（1）：29-36.

［4］Song Guo，Oliver Yang.QoS-Aware Minimum Energy Multicast Tree Construction in Wireless Ad Hoc Networks［J］.Ad Hoc Net⁃works.2004，2（3）：217-229.

［5］杨汝涛，张绍谦，窦万春.一种基于QoS剪枝的Top-k自动服务组合方法［J］.电子学报，2012，40（7）：1489-1491.

［6］郝晓辰，窦晶晶，刘彬.基于路径损耗的无线传感器网络分布式拓扑控制算法［J］.软件学报.2009，20（12）：3213-3222.

［7］姜向远，张焕水，王伟.一种基于非完全数据的路径损耗模型选择算法［J］.电子与信息学报，2012，34（6）：1438-1344.

［8］Junhua Zhu，Ka-Lok Hung，Brahim Bensaou，et al.Rate-Lifetime Tradeoff for Reliable Communication in Wireless Sensor Networks［J］.Computer Networks，2008，52（1）：25-43.

［9］杨明，罗军舟，刘波.多射频无线Mesh网络组播端到端时延建模与优化［J］.计算机学报，2012，35（7）：1358-1369.

［10］Abbas Nayebi，Hamid Sarbazi-Azad.Performance Modeling of the LEACH Protocol for Mobile Wireless Sensor Networks［J］.Jour⁃nal of Parallel and Distributed Computing.2011，71（6）：812-821.

［11］Geetha V，Kallapur P V，Sushma Tellajeera.Clustering in Wire⁃less Sensor Networks：Performance Comparison of LEACH& LEACH-C Protocols Using NS2［J］.Procedia Technology，2012，4：163-170.

［12］Luan Linlin，Wang Zhijie，Liu Sanming.Progress of Grover Quan⁃tum Search Algorithm［J］.Energy Procedia，2012，6：1701-1706.

［13］Ai Lingmei，Wang Jue，Wang Xuelian.Multi-Features Fusion Di⁃agnosis of Tremor Based on Artificial Neural Network and D-S Ev⁃idence Theory［J］.Signal Processing，2008，88（12）：2927-2935.

丁伟杰（1980-）男，河南西平人，浙江警察学院计算机与信息技术系讲师，浙江工业大学信息工程学院博士研究生。主要研究方向为信号处理，计算机网络建模，图像处理等，dingwei212@163.com；

周凯（1985-），男，讲师，博士研究生，就读于浙江工业大学信息工程学院，主要研究方向为无线网网络建模、无线网络容量计算、无线网络路由设计，zhoukai@ zjut.edu.cn。

Research on Routing Algorithm in Wireless Sensor Network Based on Grover Fusion Theory*

DING Weijie1，2，ZHOU Kai3*，ZHOU Guomin1，WANG Xun1
（1.Department of Computer and Information Technology，Zhejiang Police College，Hangzhou 310053，2.College of Information and Engineering，Zhejiang University of Technology，Hangzhou 310023，China；3.College of Science，Zhejiang University of Technology，Hangzhou 310023，China）

How to guarantee high quality information transmission in the condition of resource-constrained is the fo⁃cus of current research on wireless sensor networks.Firstly，several key factors during transmission processing were discussed.To overcome the large calculation of the traditional multi-objects programming，Grover algorithm was ap⁃plied the routing selection to reduce amount of searching space.Finally，this paper proposed a D-S fusion algorithm to transform multi-factors into single object.This paper simulated the performance of this proposed algorithm.Com⁃pare with TOPSIS algorithm，this algorithm would prolong the life of the network and improve the time delay in the network effectively.

routing protocol；multi-objects programming；Grover algorithm；data fusion；TOPSIS