基于Grover路由策略的无线传感网络剩余容量构造与研究*

2015-05-10孟利民华惊宇

传感技术学报 2015年2期

关键词：无线网络路由容量

周凯,孟利民*,华惊宇

(1.浙江工业大学,信息工程学院,杭州 310023;2.浙江省通信网技术应用研究重点实验室,杭州 310023)

基于Grover路由策略的无线传感网络剩余容量构造与研究*

周凯1,2,孟利民1,2*,华惊宇1,2

(1.浙江工业大学,信息工程学院,杭州 310023;2.浙江省通信网技术应用研究重点实验室,杭州 310023)

网络容量计算问题是无线网络研究的热点领域之一,也是构建网络的重要评价指标。在前人的基础上,本文认为网络能耗和路由均衡技术是网络容量计算过程中两个重要因素,定义网络生存时间内所能传输的信息总量为网络总容量,网络剩余能量是随时间而变化的函数。首先,本文介绍信息传输信噪比和网络生存时间的数学模型;然后,建立整数规划数学模型,给出网络传输总容量和剩余容量的数学表达式;最后,仿真对比基于能量均衡的Grover路由策略和AODV路由策略下,网络总容量和剩余容量的变化情况。得到结论:节点移动性和能量均衡路由策略有助于提高网络总容量。

剩余容量;网络生存时间;能耗均衡;路由策略

由大量传感器节点以多跳自组织方式构成的无线传感网络俱有组网灵活、不受有线设备约束等优势,被广泛应用于紧急搜救、军事演习和医疗救治等实际应用中,已经引起产业界的高度重视,并逐渐发展成为21世纪最有前景的技术[1]。其中,如何计算无线传感网络整体信道特性和传输协议下所能够支持的最大信息流,便是无线网络容量问题,属于无线网络研究和设计的热点领域[2]。由于无线传感网络的特殊性(拓扑结构多变、多路径衰落效应等)使得网络吞吐量远小于有线网络,并不能直接应用香农公式计算无线传感网络容量。因此,针对无线传感网络的特点,设计算法计算网络容量并采取措施提高网络容量成为一个非常关键的课题。

1 相关研究

近年来,国内外学者针对无线网络容量进行了广泛地研究,主要体现在以下3个方面。

针对不同的应用环境,学者们提出了各种不同关于无线网络容量的定义。如文献[3]中作者定义了网络运输容量,即网络传输的所有信息量和传输距离乘积之和;文献[4]中作者定义了网络吞吐容量,即指单位时间内从源节点传送到目的节点的信息比特数;文献[5]中作者定义了网络传输容量,即网络中最大节点密度与成功传输的比特速率的乘积。这3种容量定义各具不同的物理含义。其中,Gupta和Kumar提出的传输容量被认定为无线网络容量研究的里程碑。

在无线网络容量定义的理论建立之后,学者们开始研究如何有效地计算网络容量。如文献[6]中基于链路信噪比的信息传输方式,作者提出通过建立混合整数规划模型来解决网络传输容量计算问题,并指出信息传输策略和路由协议都会对容量产生较大的影响。文献[7]中基于信息流分布模型,作者研究了多信道无线网络容量计算问题。在给定网络拓扑结构和信息流分布后,通过建立线性规划模型计算网络容量,并提出信息流优化分布方案可以提高无线网络的容量。由于无线网络拓扑结构的时变特性,学者们还探讨了随机网络容量上界和下界问题。如文献[8]中Gupta等人在协议模型和节点随机分布的情况下,利用地理几何的分析方法,得到网络每节点的吞吐容量为O[W/(nlog2n)1/3]bit/s。文献[9]中作者以随机点过程分析为基础,对跳频Ad Hoc网络的信息传输能力进行分析,推导了无线容量的上界和下界,讨论了可用频率数对网络容量的影响。文献[10]中作者讨论了由基站和Ad Hoc节点组成的异构网络容量上下界问题,推导得到网络容量界为O[log(n)]。其中,n表示网路中节点数量,W表示网络带宽。

在上述的研究中,无线网络容量的计算过程仅与链路信噪比有关,具有一定的局限性,且他们都没有明确地指出网络容量与网络生存时间之间的关系,而且认为网络容量是一个常量。但是,当网络能量耗尽殆尽时,网络信息也无法正常传输,网络容量也失去了原有的意义。作为创新点,本文中提出了网络传输总容量和网路剩余容量两个概念。网络传输总容量是受到网络生存时间约束的最优化模型,网络剩余容量是一个时变的函数,描述可用容量在传输进程中的消耗情况。对于网络信息传输而言,研究网络剩余容量具有非常重要的意义,它可以有效地指导信息传输。

2 网络传输总容量和剩余容量的数学模型

本文将网络生存时间内所能传输的信息总量定义为网络传输总容量,将某时刻网络的可用容量定义为网络剩余容量,剩余容量是一个时变函数。本文假设每次源节点与目的节点之间只发送1bit的数据信息;且在信息传送过程中,节点不发生移动。在一个S×S的矩形网络中随机散布着N个节点。以0-1矩阵Y(t)=(yij(t))N×N表示t时刻网络信息传输状况。元素yij(t)的含义如下:

因此,生存时间T内所能传输的信息总量即网络传输总容量C计算方式表达如下:

(1)

将网络中第1个节点因能量消耗殆尽退出网络的时间定义为无线网络生存时间。引入网络一阶能耗模型[15],网络中节点发送信息耗能包括发射电路耗能和放大电路耗能两个部分;节点接收信息耗能仅考虑接收电路耗能。以Ek(t)表示节点k在t的剩余能量,生存时间T可以由以下优化模型得到:

(2)

时刻t源节点s到目的节点d之间正常通信,即ysd(t)=1需要满足以下两个条件:

①信息发送过程是从源节点s到目的节点d形成的一条通路。为了描述这一约束,引入0-1变量xij(t):

xij(t)=

(3)

(4)

其中,χ表示发送节点和接收节点间正常通信时所需的信噪比阈值,η表示网络中的环境噪声功率。如果仅考虑大尺度路径损耗[17],信道增益可以表示如下:

γij(t)=‖Xi(t)-Xj(t)‖-μ

(5)

其中,2≤μ≤4,Xi(t)和Xj(t)分别表示t时刻发送节点和接收节点的位置坐标。

综上所述,可以得到无线传感网络总容量的整数规划模型。其中,式(1)是模型的优化目标,式(3)、(4)是模型的约束条件。无线网络剩余容量Rc(t)是衡量当前时刻网络有效容量的重要指标,可以通过如下式(6)计算得到。可见,网络总容量一个优化常量,而剩余容量是一个时变函数。

(6)

3 基于Grover算法的能量感知路由策略

上述的整数规划模型中,关于通路的约束方程组(3)与具体路由协议无关,是任何路由协议必须满足的基本要求。但在不同路由协议下,通过最优化模型计算得到的网络传输总容量各不相同。因此,只有在给定网络节点分布和路由策略后,才能够通过整数规划模型计算网络传输总容量以及网络中的剩余容量。

文献[17]指出能量均衡算法和能量感知路由协议有助于提高网络容量。为了印证这一点,本文提出基于Grover算法的能量感知路由策略,并计算在此策略下网络传输总容量和剩余容量。2009年,学者提出可以采用Grover量子搜索的方式实现在无线自组织网络中的QoS路由信息传输,并在文中详细介绍了Grover算法的操作矩阵和扩散矩阵构造方法[18]。在文献[18]的基础上,本文将介绍能量感知路由策略中Grover操作矩阵和扩散矩阵的构造方式。

首先介绍操作矩阵U的构造方式,每个节点i都维护着一个操作矩阵U=(uimn)N×N。

(7)

扩散矩阵的作用在于放大正确的解径[19],在Grover搜索过程中扩散矩阵恒定不变,构造方式如下:

(8)

在Grover搜索过程中,每个节点初始化振幅都相等,表达如下:

(9)

在第k跳链路选择时,网络节点的振幅为Γk;在第k+1跳链路选择时,网络节点的振幅为Γk+1。它们之间的迭代计算公式如下:

(10)

综上所述,基于Grover算法的路由均衡策略可以简单地描述如下:

Step 1:源节点s发起向目的节点d的路由建立请求信息。

Step 3:中间节点i收到来自上一节点的路由建立请求信息后,搜索其一跳通信范围的节点。如果中间节点i一跳范围内没有节点,则通信失败,转到Step 5;否则,按照式(7)、式(8)构造操作矩阵和扩散矩阵。然后通过式(9),迭代计算得到中间节点i一跳通信范围内,且信噪比大于阈值的节点被选择概率。

Step 4:按照概率从高到低,选择前50%的节点作为信息转发的中间节点。转到Step 3。

Step 5:通信失败。

Step 6:路由建立请求发送成功,建立路由进行信息传输。

为了印证能量感知的路由策略对于网络传输总容量和剩余容量的影响,本文选取AODV路由策略进行对比。AODV是无线网络中较早提出的一类路由策略,是一种源驱动路由协议。当一个节点需要给网络中的其他节点传送信息时,如果没有到达目标节点的路由,则必须先以多播的形式发出路由请求报文。路由请求报文中记录着发起节点和目标节点的网络层地址,邻近节点收到路由请求报文,首先判断目标节点是否为自己。如果是,则向发起节点发送路由回应;如果不是,则首先在路由表中查找是否有到达目标节点的路由,如果有,则向源节点单播路由回应,否则继续转发路由请求报文进行查找。

图1 两种策略下网络传输总量的变化图

4 数值仿真

为了验证算法的性能,本文采用MATLAB软件进行仿真分析。在一个300 m×300 m的矩形网络中,随机散布若干个节点,节点位置服从均匀分布。假设网路中每个节点的通信范围为50 m;信道信噪比阈值χ=1.3,信道衰落因子μ=2,噪声功率。

由于不同的路由策略,网络中节点能耗变化不同,造成网络生存时间不同,网络传输总量也会不同。本文对比了AODV路由策略与基于Grover算法的能量感知路由策略在网络传输总容量上的表现,如图1所示。在一个30个节点组成的无线网络中,两种路由策略在网络剩余容量上的表现,如图2所示。

图2 两种策略下网路剩余容量变化仿真图

从图1中可以发现:网络路由策略会影响网络传输总量,本文提出的基于Grover算法的能量感知路由策略比AODV路由策略更加有利于提高传输总量。从图2中可以发现:网络剩余容量随时间的变化而变化,是一个动态时变函数,而且随着网络能耗增加逐渐趋向于零。得到能量感知路由策略有助于提高网络动态容量的结论。

图4 两种网络下剩余容量的变化仿真图

网络节点移动可以改变网络拓扑结构,对链路信噪比造成影响。节点的移动性可以改变网络传输总容量和剩余容量。本节仿真移动性网络与非移动网络在传输总容量方面的表现。

在移动性网络中,本文定义网络中的每个节点速度随机分布在[0,2 m/s]的区间内,干扰节点移动方向朝远离发送节点的方向移动,遇到边界时便反向移动,采用基于Grover能量感知的路由策略传输信息,得到仿真结果如图3、图4所示。从图中可以发现:节点的移动性可以有效地提高网络传输总容量。

图3 两种网络下传输总容量的变化仿真图

5 结束语

本文在前人的基础上,将网络生存时间内所能传输的信息总量定义为网络传输总容量,将某时刻网络的可用容量定义为网络剩余容量,剩余容量是一个时变函数。通过建立整数规划数学模型,得到网络传输总容量和剩余容量的数学表达式。最后,本文进一步提出基于Grover算法的能量感知路由策略,通过仿真分析能量感知路由策略和节点的移动性可以提高网络传输总容量与网络剩余容量。

[1] 刘志,裘正定.基于分环多跳的无线传感网分簇路由算法[J].通信学报,2008,29(3):104-113.

[2]杨娟,李颖,张志军,等.移动Ad hoc网络容量非合作规划博弈模型的稳定性[J].电子与信息学报,2012,34(1):75-81.

[3]Renato M,de Moraes,Hamid R,et al.Garcia-Luna-Aceves.Mobility-Capacity-Delay Trade-Off in Wireless Ad Hoc Networks[J].Ad Hoc Networks,2006,4(5):607-620.

[4]Jae Young Seol,Seong Lyun Kim.Node Mobility and Capacity in Wireless Controllable Ad Hoc Networks[J].Computer Communications,2012,35(11):1345-1354.

[5]Gupta P,Kumar E R.The Capacity of Wireless Networks[J].IEEE Transactions on Information Theory,2000,46(2):388-404.

[6]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.

[7]刘永靖.多跳无线网络容量与资源优化技术研究[D].电子科技大学,2011.

[8]涂来,王芙蓉,张剑,等.基于多跳蜂窝网的合群网络模型网络容量效能分析[J].通信学报,2008,29(2):45-51.

[9]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.

[10]Song Guo,Oliver Yang.QoS-Aware Minimum Energy Multicast Tree Construction in Wireless Ad Hoc Networks[J].Ad Hoc Networks,2004,2(3):217-229.

[11]Meng Limin,Zhou Kai,Shen Xinyu,et al.Research on Qos Routing Protocol Based on Grover Algorithm for MANET[C]//Proceedings of the IASTED International Conference on Computational Intelligence,2009:138-142.

[12]杨汝涛,张绍谦,窦万春.一种基于QoS剪枝的Top-k自动服务组合方法[J].电子学报,2012,40(7):1489-1491.

[13]郝晓辰,窦晶晶,刘彬.基于路径损耗的无线传感器网络分布式拓扑控制算法[J].软件学报,2009,20(12):3213-3222.

[14]姜向远,张焕水,王伟.一种基于非完全数据的路径损耗模型选择算法[J].电子与信息学报,2012,34(6):1438-1344.

[15]Zhu Junhua,Hung Ka-Lok,Brahim Bensaou,et al.Rate-Lifetime Tradeoff for Reliable Communication in Wireless Sensor Networks[J].Computer Networks.2008,52(1):25-43.

[16]王维,杨明,罗军舟,等.多射频无线Mesh网络组播端到端时延建模与优化[J].计算机学报,2012,35(7):1358-1369.

[17]李辉,张安,徐琦,等.多径衰落信道中的一种定想多用户检测算法[J].传感技术学报,2006,19(1):238-240.

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

[19]Geetha V,Kallapur P V,Sushma Tellajeera.Clustering in Wireless Sensor Networks:Performance Comparison of LEACH and LEACH-C Protocols Using NS2[J].Procedia Technology,2012,4:163-170.

Residual Capacity Algorithm of Wireless Sensor Network Using Grover Routing Strategy*

ZHOUKai1,2,MENGLimin1,2*,HUAJingyu1,2

(1.College of Information Engineering,Zhejiang University of Technology,Hangzhou 310032,China;2.Zhejiang Provincial Key Laboratory of Communication Networks and Application,Hangzhou 310023,China)

Capacity estimation is the hotspot in the research of wireless sensor networks.This paper investigates capacity algorithms based on the physics SINR model by using the integer linear programming to formulate the routing problem.This paper proposes the residual capacity algorithm and total traffic algorithm based on the lifetime of network.The numerical results show the capacity will be improved with the increase of the nodes in networks and the dynamic capacity is a time-varied function which will decrease with time.Finally,this paper points out that routing strategies and mobility will improve the capacity.

residual capacity of networks;lifetime of network;energy model;routing protocol