一种大规模传感网络理论路由优化算法

一种大规模传感网络理论路由优化算法

基于时延约束的最小能耗路由优化问题在无线通信网络中，通信的能量消耗与距离的n（n通常为3）成正比。因此，从网络节能的角度来看，应尽量采用多段短距离通信模式。但这种短距离多跳路由方式同时又会增加网络时延,影响了业务的实时性。因此,在满足业务时延要求的约束条件下,如何选择最小能耗的路由是无线传感网络中需要研究的一个重要问题。当路由选择包含两个或两个以上的可加性参数,或者包括可加性参数和/或可乘性参数的组合时,该路由选择将是NP-完全问题。路由能耗和时延都属于可加性计算参数,因此基于时延约束的最小能耗路由优化问题是一个NP完全问题。目前求解优化问题的方法有许多种,除了割平面法、分支定界法等一般方法外,还有递推函数法、近似方法等。这些方法都存在计算量大、迭代时间长等问题,不能适应大规模网络要求。人工神经网络是由许多非线性处理单元构成的并行系统,通过适当的构造,神经网络能得到问题的满意解甚至全局最优解。文献主要讨论了两种神经网络(JEB和Hopfield网络)在路由优化中的应用,文献中应用人工神经网络研究了不可靠部件的通信路由问题,文献中构造了一个Hopfield神经网络,用于解决计算机网络中的最短路问题。这些神经网络能较好地弥补传统路由算法的缺陷,但神经网络结构复杂。从节能的角度来考虑,网络中节点结构应尽量简单。文献中构造了一种缩减的Hopfield神经网络算法,但能量函数参数的选择非常敏感,没有理论支持,对能量函数参数的选择采用实验法、经验法确定,算法的局限性大。本文主要考虑在能量受限的大规模无线传感网络中,在满足时延要求的条件下,选择能耗最小的路由优化问题。文中选取路由时延为约束条件,选择路由能耗作为优化目标,提出了一种新的基于Hopfield神经网络的路由优化算法。1节点期最大时延和能耗目前大规模的无线传感网络多采用分簇方式的层次化拓扑结构,图1所示模型为分簇结构的无线传感网络模型,其中首、末节点分别代表源传感器节点到目的接收节点(sink),其他节点则代表网络中的各簇的簇首节点。相邻簇首节点间可能存在多条通路,每条通路由一个或若干个簇内节点构成。每条通路的时延和能耗参数由簇首节点通过相应的路由协议收集完成。将网络抽象成一个加权图G(V,E*)。集合V的元素称为节点,集合E*的元素称为边。用Eij表示节点i到节点i+1的第j条边,其权值序列〈tij,pij〉表示从节点i经过第j条边到节点i+1的时延和能耗。引入变量xij={1节点i到节点i+1的第j条边被选为到目的点的路由0其他(i=1,2,⋯,n-1;j=1,2,⋯,ni)xij=⎧⎩⎨⎪⎪10节点i到节点i+1的第j条边被选为到目的点的路由其他(i=1,2,⋯,n−1;j=1,2,⋯,ni)定义1路由path=1→2→…n-1→n的时延delay和能耗power分别定义如下delay(path)=n-1∑i=1ni∑j=1∑i=1n−1∑j=1nitijxijpower(path)=n-1∑i=1ni∑j=1pijxij设T0是业务所能接受的最大网络时延。满足时延要求的最小能耗的路由选择模型可归结于如下的线性整数规划问题(LIP)minn-1∑i=1ni∑j=1pijxij(1)s.t.n-1∑i=1ni∑j=1tijxij≤Τ0(2)ni∑j=1xij=1(i=1,2,⋯,n-1)(3)xij∈{0,1}(i=1,2,⋯,n-1;j=1,2,⋯,ni)(4)式(1)表示从节点1到节点n的最小能耗路由问题。式(2)保证所选择路由满足最大时延约束。式(3)则保证任意两相邻节点间仅有一条边被选中。2基于混合动力网络的路径算法2.1网络状态空间微织构设计基于Hopfield神经网络的路由算法的基本思想是通过构造合适的能量函数,把求解的优化问题转化为能量函数的最小值问题。因此能量函数是设计Hopfield神经网络的关键,它反映了求解问题的目标,并且是构造网络动态过程的基础。Hopfield神经网络能量函数的一般形式为:E=-12∑i∑jwijxixj-∑ihixi,第i个神经元表示的动态特性为:dyidt=∑jwijxj+hi(wij=wji),xi=12(1+tanh(yiΤ)),其中yi,xi∈{0,1},hi分别表示第i个神经元的输入、输出和偏差,wij是从神经元j到神经元i的连接权值(wij=wji)。Hopfield神经网络的微分方程dyidt=-∂E∂xi(5)Τdxidt=-2xi(1-xi)∂E∂xi(6)根据上述公式,有dEdt=∑i∂E∂xi⋅dxidt=-∑i2xi(1-xi)Τ(∂E∂xi)2≤0,这就使得Hopfield神经网络的能量函数E逐渐趋于稳定状态。称N维空间{0,1}N为网络状态超空间,称x∈{0,1}N为空间顶点。根据无线传感网络的特点,构造一个新的Hopfield神经网络,用于解决满足时延约束条件下的最小能耗路由问题。其能量函数如下E=A2n-1∑i=1(ni∑j=1xij-1)2+B4{(Τ0-n-1∑i=1ni∑j=1tijxij)×[(Τ0-n-1∑i=1ni∑j=1tijxij)-|Τ0-n-1∑i=1ni∑j=1tijxij|]}+C2n-1∑i=1ni∑j=1xij(1-xij)+D2(n-1∑i=1ni∑j=1pijxij)(7)E的前两项分别表示约束条件(3)和(2),第三项表示变量的整型约束,迫使神经元趋于0或1,最后一项则表示优化目标能耗函数。Hopfield神经网络不仅要考虑计算的收敛速度,同时也要确保网络的稳定性,即保证网络的可行解都是渐进稳定的。如果能量函数的参数选择不当,往往会造成迭代次数的增加。而传统神经网络路由算法中对能量函数参数的选择一般采用实验法或经验法确定,算法局限性大。本文通过以下的定理来保证通过适当地选取能量函数的参数,网络状态空间顶点的可行解都是稳定的。令PM=max{pij},TM=max{tij}分别表示边中最大的能耗值和时延值。引理1对于任何神经元i如果满足条件∂E∂vi(V){>0Vi=0<0Vi=1(8)则网络状态超空间的顶点V=(Vi)是渐进稳定的;如果某些神经元i满足条件∂E∂vi(V){<0Vi=0>0Vi=1(9)则顶点V=(Vi)是不稳定的。定理1如果Hopfield网络能量函数E的参数A,B满足条件:A>C/2+D/2·PM,B>(C-D)/2,则所有的非可行解都是不稳定的。证明:称在以下任一情况下求得的解是非可行解x=(xij)∈{0,1}N(1)对于某个s,ns∑j=1xsj-1≥1;(2)对于某个s,ns∑j=1xsj-1≤-1;(3)n-1∑i=1ni∑j=1xij·tij-T0≥1。对于情况(1),当xsj=1时,ns∑j=1xsj-1≥0,有下式成立∂E∂xsj=A(ns∑k=1xsk-1)+Btsj(n-1∑p=1np∑q=1tpqxpq-Τ0)++C2(1-2xsj)+D2⋅psj≥A-C2+D2psj>A-C2当A>C/2时,∂E∂xsj>0,由式(9)可知该非可行解是不稳定的。对于情况(2),当xsj=0时,假设情况(3)不成立,即n-1∑i=1ni∑j=1xij·tij-T0<0,有∂E∂xsj≤-A+C2+D2⋅ΡΜ,即当A>C/2+D/2·PM时,∂E∂xsj<0。根据式(9)可知该非可行解是不稳定的。对于情况(3),当xsj=1时,ns∑j=1xsj-1≥0,有∂E∂xsj≥B⋅tsj-C2+psj⋅D2成立,即当B>(C-D)/2时,∂E∂xsj>0,由式(9)可知该非可行解是不稳定的。综合以上情况可以得到当A>C/2+D/2·PM,B>(C-D)/2时,非可行解是不稳定的。定理2如果Hopfield网络能量函数E的参数C,D满足条件:C>D·PM,则可行解是渐进稳定的,反之则是不稳定的。证明:对于任意的s,由于n-1∑i=1ni∑j=1xij·tij-T0<0,ns∑j=1xsj-1=0,因此∂E∂xsj=C2(1-2xsj)+D2⋅psj={C/2+psj⋅D/2xsj=0-C/2+psj⋅D/2xsj=1,显然当xij=0时,∂E∂xsj>0,由式(8)可知此时可行解是稳定的;当xij=1时,只有当C>D·psj时,或者当C>D·PM时,∂E∂xsj<0,可行解是稳定的。定理3当Hopfield神经网络能量函数E的参数满足条件:A>C/2+D/2·PM,B>(C-D)/2,C>D·PM时,其可行解是渐进稳定的。证明:根据定理1和定理2即可得。根据Hopfield神经网络的微分方程dxijdt=-∂E∂xij,应用梯度下降法,得到如下微分方程表示的动态系统:对1≤j≤ni,1≤i≤n,dxijdt=-{A(ni∑k=1xik-1)+Btij(n-1∑p=1np∑q=1tpqxpq-Τ0)++C2(1-2xij)+D2pij}(10)其中,(s)+=max{0,s}。根据dxijdt=xij(n)-xij(n-1)Δt|t=n-1,由式(10)可得xij(n)=xij(n-1)-{A(ni∑k=1xik(n-1)-1)+Btij(n-1∑p=1np∑q=1tpqxpq(n-1)-Τ0)++C2(1-2xij(n-1))+D2pij}⋅Δt(11)其中,xij(n)表示第n次迭代计算结果。为了加快算法收敛速度,当每个节点都有一条边对应的xij大于0.5时,算法结束。此时取xij={0xij<0.51xij>0.5(1≤i≤n,1≤j≤ni)。与启发式算法相比较,Hopfield神经网络具有并行结构,易于硬件实现。根据神经网络的动态方程(10),给出了本路由优化算法的硬件结构,如图2所示。能量函数E确定的神经网络由n-1∑i=1ni个神经元通过简单的加法器、乘法器互联而成。该神经网络共需执行n-1∑i=1ni+5次乘法和n-1∑i=1ni+max{ni|i=1,2,…,n-1}+7次加法。2.2算法时间复杂度步骤1根据定理3选择能量函数的系数A,B,C,D。同时xij(0)全部为0,n=1。步骤2据式(11)计算各xij(n),当每个节点都有一条边对应的xij大于0.5时,算法结束;否则n=n+1,重新进行步骤2迭代计算。设M=n-1∑i=1ni,迭代次数为N。算法时间复杂度为每次迭代计算时间乘以迭代次数,每次迭代计算时间复杂度为O(M),算法总时间复杂度为O(N·M)。通常网络中接收节点(Sink)配置较高,能量充足。算法计算主要集中在Sink节点完成,源节点和中间节点基本不参与路由计算,因此,算法的计算对网络中间节点的能耗影响较小,可忽略不计。3神经网络路由仿真通过下面的一个实例来验证算法的可行性。一个分簇结构的无线传感网络的模型如图3所示(每条边包括若干节点)。要求寻找一条从节点1到节点5的满足时延不超过21ms的最小能耗路由。根据定理3的要求,设置网络参数A=2000,B=400000,C=400,D=10,xij初始值全部为0。运算最终结果如表1,图4为能量函数的变化图。从表1中可以看出满足时延要求的最小能耗路由为x11=1,x21=1,x32=1,x41=1,其余xij=0,此时的能耗为11μJ,时延为17ms。从图4中可以看出神经网络收敛速度很快。通过计算机仿真来检验在不同网络规模下,本文提出的神经网络路由算法的迭代次数变化情况。模拟产生每个分簇包含10个传感器节点,分簇数分别为10,20,30,…,100的10种规模的网络(即网络节点数从100到1000)。簇内各边的时延和能耗参数随机产生。当每个簇内都有一条边对应的xij大于0.5时,迭代计算结束。仿真结果如图5所示,随着网络规模的增大,算法的迭代次数没有明显的增长趋势,基本稳定在25到35次之间。因此,本文提出的神经网络路由优化算法可用于大规模的传感器网络。与文献提出的蚁群算法(平均迭代次数为134次)和文献提出的遗传算法(平均迭代次数为152次