一种改进的无线传感器网络协议的模拟退火算法

一种改进的无线传感器网络协议的模拟退火算法

0letch-c协议的基本算法无线通信和数字电子的发展和进步，使云传感器节点能够降低和提升成本，降低成本，多功能，体积小，短距离。在无线传感器网络中,路由协议的研究是当前的研究热点。作为典型的无线传感器网络协议,LEACH-C协议是一种集中式的分簇路由协议,该协议通过基站的计算选举簇头节点。这种方式能够减少选举簇头时因通信而消耗的能量,从而有更多的剩余能量用于传输数据。在LEACH-C协议中,模拟退火算法被用来进行簇头节点的选择。其中,目标函数定义为所有节点到对应簇头的距离的平方之和。目标函数的值越小,说明整个网络在传输数据时的消耗越小。本文在模拟退火算法的基础上,对实现的具体过程进行了改进。在一次迭代过程中,首先产生一个新的簇头节点集合,然后设计新的方法,在较短时间内收敛到一个使目标函数更小的簇头节点集合。最后在这个收敛的集合基础上产生新的集合。试验证明,这种搜索较好的解的方式比原来的方法在执行效率上有很大提高。1相关研究1.1打造网络带的平台,使节点区分原理,并在控制具体的节点数时将自己作为另一个节点的一个簇头在LEACH-C协议每个周期的开始阶段,所有节点把自己的位置信息和剩余能量值发往基站。基站在收到这些信息后,首先计算所有节点的平均能量值,把能量不低于平均能量值的节点作为候选节点。然后使用模拟退火算法从中选举出使目标函数较小的簇头集合。最后把这个簇头集合广播到网络中。如果节点收到的簇头集合中有自己的ID,则把自己作为其中的一个簇头;如果没有,则与相应的簇头建立联系,并等待相应的TDMA时隙到来后向簇头传输数据。在模拟退火算法过程中,LEACH-C协议通过控制最大的迭代次数使算法结束,最后得到一个较好的解。当节点数较小时(例如100或者200个节点),搜索需要的迭代次数较少,因此可以在算法结束前得到一个较好的解;当节点数增大时,由于存在更多的局部最优解,算法需要较多的迭代次数从一个局部最优解跳出,然后寻找可能存在的更好的解。因此,在算法结束前搜索到一个较差解的可能性增大,最终使网络的传输代价增大,导致网络的生命周期缩短。1.2节点之间的问题描述模拟退火算法是一种理论上的全局最优算法,得到较好的解的质量取决于迭代次数和退火方式的选择。在目前的优化算法研究中,还包括遗传算法,粒子群算法等智能优化算法。模拟退火算法的研究热点是将并行计算引入该算法或者与遗传算法等配合使用。在LEACH-C协议中,模拟退火算法的执行流程如图1所示。设节点均匀分布在一个100m×100m的矩形区域内,当前迭代次数为。则图1中产生随机扰动的过程为:首先对当前解中的每个坐标产生一个新的随机坐标。设原来的坐标为,,则新的坐标为其中rand表示该区间内的某个随机数。然后在所有节点中搜索距离这个新坐标最近的节点。如果最后搜索到的每个节点都不相同,则把这个节点集合作为新解。在退火过程中,为使开始时有较大的概率接受新解,本文对图中步骤9的“指定概率”的值做了修改。设m=10000×exp(k/20),则指定概率为p=exp(-△/Em),其中E表示新解对应的目标函数与当前解对应的目标函数的差值。算法结束的条件为达到最大的迭代次数。在一次迭代过程中,算法执行从步骤4开始,直到步骤11为止。算法通过在当前解的基础上进行随机扰动来产生新解,然后计算对应的目标函数,最后通过步骤6到步骤10决定是否接收新解。新解是在当前解的邻域内搜索得到的。如果当前解在空间上距离较好的解很远,那么跳出当前解所在的较差区域需要经过很多迭代次数。尤其当节点数量增多时,节点之间的空间结构复杂,往往陷入一个很差的区域进行搜索而无法跳出。针对以上问题,本文提出了新的方法对步骤5进行改进。首先按照产生的新解对网络分簇,然后在各分簇内产生新的簇头,用形成的簇头集合代替原来的新解,然后重新分簇。如此循环,直到某次循环后簇头集合没有变化为止。最后计算这个簇头集合对应的目标函数值。实验证明,这个过程的收敛速度是相当快的。与原来算法的平均性能相比,该算法能够在很少的迭代次数内获得较好的解。2最优条件可选择比新解原来的模拟退火算法在每次迭代中直接计算新解的目标函数值。如果在计算之前能够找到比新解更好的解,将会使搜索速度获得很大提高。本文通过一个新的方法在不需要计算目标函数值的情况下,首先将新解收敛到一个局部最优解,然后用这个解产生新的随机扰动。2.1缺少一个簇头节点对于一个簇,目标函数为簇内节点到簇头的距离的平方和。假设在一个平面内随机均匀分布了N个节点,最佳的簇头数为。设属于i第个簇的节点标记为Sij,坐标为(xij,yij,其中j表示该簇中的第j个节点。该簇中的节点个数为n,则有1≤j≤n。该簇的簇头节点表示为Si0,坐标为(xi0,yi0)。很显然,有Si0∈{Sij,1≤j≤ni,ni∈N*}。则模拟退火算法的目标为寻找使假设最佳的簇头个数为1,那么整个网络被划分为一个簇。式(1)表示为式中:,(xj,yi)——任意节=1点的坐标,(x0,x0)——簇头的坐标。通过计算可得使式(2)最小的解为于是,得到如下结论:定理1一个簇内,使目标函数最小的簇头的位置为该簇中距离几何中心点最近的节点。证明:令则簇内的任意一个节点的坐标表示为把任意一个节点作为簇头,则目标函数的值为上式可以进一步化简为N﹒△x2+△y2。显然,只要△x2+△y2最小,上式的值将最小。而该式为任一节点到几何中心点的距离的平方。因此对于任一节点,只要到几何中心点的距离最小,该节点作为簇头时对应的目标函数值就最小。命题得证。2.2局部最优解的迭代当簇头集合确定后,为使整个网络对应的目标函数值最小,任一节点必须从簇头集合中选择距离最近的节点作为簇头。这是根据voronoi图划分的,如图2所示,大一些的点代表簇头,小一些的点表示普通节点,簇之间的边界在两个簇头连线的中垂线上。但是在网络完成分簇后,使一个簇对应的目标函数最小的节点并不一定是簇头节点。在图2中,箭头所指的簇头比较靠近该簇所在区域的边缘;而箭头所指该簇内的另外一个节点则更靠近几何中心点。如果节点作为簇头,将使该簇对应的目标函数值更小;如果所有分簇内都重新选择距离几何中心点最近的节点作为簇头,那么整个网络对应的目标函数值会更小。根据上节的结果,对于一个新产生的解(簇头集合),可以通过图3的过程得到一个局部最优解。在图3中,从步骤1到步骤4每进行一轮作为一次迭代,每次迭代都要经过“分簇—重新选举簇头”的过程。直到某次重新选举簇头后与选举前没有变化为止。这样将达到一个稳定状态,因为继续迭代不会使结果发生变化。本文把通过这样的一个过程得到的解称为一个局部最优解。在图3的迭代过程中,步骤1使得在簇头集合确定后,整个网络对应的目标函数最小;而步骤3能够使每个簇对应的目标函数减小,从而使整个网络对应的目标函数减小。如此循环,每进行一次步骤1或者步骤3都能使整个网络的目标函数值更小,最后得到一个局部最优解;如果某个新解在收敛后比其它解收敛后对应的目标函数都小,那么这个收敛后的解就是全局最优解。图4所示的是若干个随机产生的初始解收敛到的局部最优解对应的目标函数值。图中的虚线表示的是全局最优解对应的目标函数值。从图中可以看出,其中的某些解收敛到了接近于全局最优解;最后得到的局部最优解与选取的初始解有很大关系。图5是相应的每个初始解收敛所需的迭代次数。可以看出,收敛所需的迭代次数与初始解没有必然联系,与收敛后的局部最优解也没有必然联系。试验表明,即使节点数量很大,该过程的收敛也是相当快的。假设在一个100m×100m的矩形区域内随机均匀分布了若干节点。通过研究得到,最佳簇头数与节点的数目的平方根成正比;当=100时,取5为最佳。因此可得式中:round——取最近的整数。对于图3所示算法,每次运行时随机给定一个初始簇头集合,取1000次结果的平均值,结果如图6所示。从图6中可以看出,当节点数为100时,最多只需要5次左右迭代就能收敛。当节点数从100增加到2000时,收敛所需的平均迭代次数从5次左右增加到不到12次。因此,可以用图3所示过程代替图1中的步骤5,在跳出循环后计算局部最优解对应的目标函数值,并用收敛后的局部最优解(簇头集合)代替初始解。2.3多次迭代的计算复杂度假设在u个节点的网络中选举k个簇头。从图3的一次迭代过程可以看到,步骤1的计算复杂度为O(u×k);步骤2和步骤3的复杂度是O(u),而步骤4的复杂度只有O(k)。由于远小于u,因此可以只考虑步骤1到步骤3的计算复杂度。在经过多次迭代后,最后计算目标函数值(也是图1中步骤5的操作)的复杂度为O(u×k)。因为图3中的过程需要多次迭代,而每次迭代的计算复杂度至少为O(u×k),所以可以不用考虑计算目标函数的影响。从表1中可以看出,如果把改进后图3中一次迭代的计算复杂度和改进前图1中步骤5的复杂度相比,改进后增加了两个O(u)的计算复杂度。因此可以认为,如果把改进后图3中的一次迭代认为是整个算法的一次迭代,并且要求改进前后算法执行的迭代次数一样,那么改进前后计算量是没有变化的。3改进前后算法的迭代次数本文通过MATLAB试验比较图1中的模拟退火算法和改进后算法的执行效率。假设每个节点的当前能量相同,因此所有的节点都可以成为候选节点(如果节点能量不相同,只是造成候选的簇头集合有所变化,不影响算法的执行过程),取1000次运行结果的平均值。其中改进后的算法以图3中进行的迭代次数进行计算。当达到最大迭代次数,或者当前解对应的目标函数值与预先得到的最小目标函数值相比,减小到一个固定的差值范围内时,算法结束。试验结果如表2、表3所示。在表3中,当节点数为200时,改进后算法的平均迭代次数比节点数为300时要多。这是由于选取的某些初始解位于一个很差的区域,即使经过多次随机扰动都不能从这个区域跳出,甚至在达到最大迭代次数时还不能跳出,从而使平均的迭代次数剧增。在实验中发现,这种情况所占比例很小(当节点数为200时,平均只有3%左右),而改进前的算法不存在这种情况。针对上面问题,本文在改进后算法的基础上,设置一个迭代次数的最大累加值。即在经过图3所示过程后,判断在初始解的基础上已经进行的迭代次数;如果迭代次数已经超过这个值,则重新执行一遍图1中步骤1到步骤3的过程,得到一个新的初始解,然后继续循环,直到得到符合要求的解。改进后算法的最终试验结果如表4所示。实验中,当节点数为100,200和300时设置的迭代次数的最大累加值分别为100,200和300。这是通过多次试验后统计得到的结果。通过表4与表2试验结果的对比可以发现:节点数为100时,改进前算法所需的平均迭代次数是改进后算法的将近20倍,而改进后算法获得的目标函数的平均值更接近于最佳的目标函数值;当节点数为200时,这个比例扩大到了将近80倍。当节点数为300时,对于改进前算法设置的差值为3000,也就是说,只要当前计算得到的目标函数值与最佳的目标函数值的差值在3000以内,算法就可以结束;而改进后的算法的差值需要达到1000以内。因此对改进后算法的要求更高。从表中可以看到,改进后的算法平均只需要197.3次迭代,仍然只有改进前算法的0.0165倍。但是最后得到的目标函数的平均值仍然要比改进前的算法更接近于最佳值。4无线传感器网络上算法的改进本文通过对LEACH-C协议中模拟退火算法的改进,使选举簇头时能够有更高的执行效率,缩短了