基于蜂窝网格的变步长移动节点部署算法
作者：朱明，金仁成，车志平，李应琛 大连理工大学 辽宁省微纳米技术及系统工程重点实验室
摘要: 针对无线传感器网络节点部署问题，提出了一种基于蜂窝网格的变步长节点部署算法。将监测区域进行正六边形网格划分，利用网格中心位置信息，以及随机散布的节点的位置信息，每个节点会找到自己的目标网格，目标网格中心即为该节点部署位置。根据待部署节点与相应目标网格顶点之间的距离信息，控制节点的移动距离。仿真结果表明，该算法收敛速度快，能以较小的节点平均移动距离获得98%以上的覆盖率。
引言
无线传感器网络(WSN)节点部署，是在指定的监测区域内，适当布置传感器节点以满足特定需求，传感器节点布置的好坏直接影响WSN所能提供的“感知”服务质量[1]。
一种能够有效控制节点的移动策略是借助虚拟力原理导向控制节点移动[24]。节点受监测区域内其他节点的虚拟引力和斥力的作用而移动，合力为0时，停止移动。基于虚拟力的算法能够有效提高监测区域覆盖率，但因为节点没有移动目标，容易形成监测空洞。
另一种就是借助网格划分的策略，从节点的覆盖效率出发，实现监测区域的节点部署。参考文献[5]首次提出当且仅当3个半径为1的圆交于一点，且三个圆心连成边长为3的等边三角形时，可以获得最大的覆盖效率。参考文献[6]在最大覆盖效率的基础上，提出了基于蜂窝网格的传感器节点静态部署算法，将无线传感器网络节点部署在组成蜂窝网格的各个六边形的中心。参考文献[7]将网格划分与虚拟力算法有机结合，提出了一种基于网格划分的虚拟力部署算法，但是，该算法没有在全局上从最短距离开始寻找，会出现能耗过多的情况。参考文献[8]利用满足全覆盖条件的正六边形蜂窝网络拓扑模型，将监测区域划分成正六边形的网格结构，在正六边形的中心设置虚拟锚节点，结合传统的虚拟力算法，考虑虚拟锚节点的引力作用，同时兼顾不同移动节点间的斥力影响，在满足一定覆盖率要求的前提下,建立节点在合力作用下的移动到虚拟锚节点的运动模型。
针对传统基于虚拟力的移动策略移动目标不明确、能耗过大，以及容易出现监测漏洞等缺点，提出了一种基于蜂窝网格的变步长节点部署算法。利用监测区域的正六边形网格划分信息，以及随机散布的节点位置信息，每个节点会找到自己的目标网格。根据待部署节点与相应目标网格中心之间的距离信息，控制节点的移动距离和方向。
1问题陈述
1.1相关假设
针对本文的研究，做出以下假设：
① 所有的传感器节点具有相同的感知、通信、计算以及移动能力；
② 所有的传感器节点的感知范围和通信范围都是理想的圆形；
③ 所有节点都能通过GPS等方法获取自身位置信息，另外，当监测区域划分为蜂窝网状结构时，每个正六边形网格的中心坐标信息是可以获取的；
④ 节点的初始部署是随机的；
⑤ 传感器节点的通信半径Rc是其感知半径Rs的2倍，此时，覆盖可保证连通[9]；
⑥数据传输过程中的延时等误差忽略不计。
1.2感知模型
假设传感器节点si部署在点xi,yi，对于任意一点P，其坐标为x,y，则si与P之间的欧式距离为：
为简化问题研究，选择传感器节点的模型为二元感知模型。当点si与P之间的距离在节点的感知范围内时，节点能采集到P点信息的概率为1；当点si与P之间的距离在节点的感知范围外时，节点能采集到P点信息的概率为0，如下所示：
1.3评价方法
为了评价算法的优劣，引入3个评价机制：覆盖率、平均移动距离、部署时间。
(1) 覆盖率
覆盖率是评价一个部署策略最重要的指标,它从直观上表达了一个部署策略的好坏。对一些特殊的监测区，需要很高的覆盖率，同时还要避免出现监测空洞。覆盖率越大，节点对监测区域的监测效果越明显，部署策略的优越性越强。在数学上，覆盖率是所有节点覆盖区域面积的并集与监测区域面积的比值，如下所示：
式中，Ai是每个节点的覆盖面积，A是监测区域的面积，Coverage(%)是监测区域的覆盖率。
（2) 平均移动距离
平均移动距离体现了每个节点在部署过程中移动距离的多少。由于节点在移动过程中需要消耗能量，平均移动距离也间接反映节点在部署过程中消耗能量的平均水平。平均移动距离越小，节点的平均能耗越低。当节点部署策略实施完成，可以利用式(4)来计算节点的平均移动距离。
(3) 部署时间
在对时间要求严格的场合,部署时间是非常重要的指标。在本文中，部署时间定义为从初始节点随机散布到所有节点部署完成的这段时间。部署时间的长短与部署策略的关系很大，它能反映一个部署策略的好坏。
2本文算法
2.1基本网格划分结构
利用参考文献[5-6]中提到的部署模型，对监测区域进行网格划分，得到如图1所示的蜂窝网络结构，这样就很容易得到蜂窝网络中每个正六边形网格的中心坐标。图中正六边形网格的边长为节点的感知半径，当节点处于各个网格的中心时，即为参考文献[6]所述的静态网络结构，传感器节点的覆盖效率最高，达到82.7%。
图1 监测区域的基本网格结构
2.2基于蜂窝网格的变步长部署策略
按照图1所示的基本网状结构，将各个正六边形网格的中心作为随机散布的移动传感器节点的移动目标。当节点随机散布后，根据最小距离原则在全局上分配每个传感器节点的目标网格，当所有节点选择目标网格点之后，节点移动开始。
(1) 节点移动目标选择
当传感器节点随机散布后，利用节点位置信息、正六边形网格中心坐标信息，可以计算出每个传感器节点与图1中任意一个正六边形网格中心之间的距离信息，将其记作一个m×n的矩阵Dm,n，如下所示：
式中，m是随机散布的传感器节点的个数，n是监测区域划分得到的正六边形网格的个数，矩阵中的每一行元素代表传感器节点i到n个正六边形网格之间的距离。对矩阵中的元素进行查找，确定每个传感器节点的目标网格，处理过程如下：
① 对距离矩阵中的所有元素进行第一轮查找，找到其中最小的元素dij，由此确定第i个节点的目标网格为网格j，并标记节点i已确定为目标网格，第i行和第j列的所有元素不参与下次查找;
② 如果i③ 节点的移动目标选择完成，查找过程结束。
(2) 确定节点移动方向α及每次移动距离Mov_D
当所有传感器节点找到自己的目标网格后，节点的移动策略开始执行。由节点与目标网格中心之间的位置关系,可以确定节点移动的方向。假设节点si的坐标为xi,yi，其目标网格中心的坐标为xc,yc，如图2所示。
图2 节点与其目标网格坐标方位图
显然，由二者的坐标信息可以计算出节点的移动方向角α，如下所示：
为了得到比较完善的部署控制策略，需要研究传感器节点在部署过程中移动距离的选择。如图3所示，方格代表的是正六边形的顶点，方格内部的数字是顶点的编号，圆圈代表的是传感器网络节点。显然，传感器节点与目标网格的位置关系不确定，既可在网格内部，也可在网格外部。若节点与目标网格中心的距离大于最大移动步长，则需要先对节点以最大步长进行移动，直到节点与目标网格中心的距离小于最大移动步长，则以当前距离为移动步长；若节点与目标网格中心的距离小于最大移动步长时，以当前距离作为节点的移动步长。以d表示节点与其目标网格点之间的距离，Max_Step为最大移动步长，Mov_D为每次移动距离，则每次移动距离的选择如下所示：
图3 节点与其目标网格之间的包含关系
(3) 考虑避障问题的部署策略研究
在节点的部署过程中，节点之间相互碰撞的可能性不可忽略,特别在基于移动机器人的节点部署场合，当初始部署阶段具有很高的速度时，节点间的相互碰撞会造成节点不可修复的损坏。因此，对节点避障策略的研究是非常有必要的。
针对节点之间会产生碰撞的问题，提出了一种基于接替移动法的避障策略。为了更好地说明该避障策略，先对节点与其目标网格之间的距离进行数学统计，如图4所示。
图4 对节点与其目标网格中心距离的数学统计
经过统计发现，67%的传感器网络节点的移动距离小于或等于4，即位于其目标网格内部。显然，由于是从全局上进行目标网格查找，该节点与相应的目标网格中心之间不会再有其他的传感器节点，否则该网格并不是该节点对应的目标网格。
经过以上分析，可以得到以下的部署策略：
① 部署处于其目标网格内的节点，一次移动到达相应的目标网格中心，这类节点部署完毕。
② 部署节点处于其目标网格外部的节点，如图5所示，首先查找节点S与其目标网格G之间的一系列已经部署的节点A、B、C…，以这些节点为基础，优先选择之前移动距离较小的节点建立移动路径，将节点S向目标网格G的移动转化为C→G，B→C，A→B，S→A的移动过程，在整个移动过程中，节点的每次移动先以最大移动步长Mov_Step移动，直到与目标网格中心的距离小于最大移动步长时，再以当前距离作为节点的移动步长。
图5 部署处于其目标网格点外部节点的路径选择
3仿真结果
为了验证算法的优越性，借助Matlab对上述算法进行仿真试验。在试验中，设定传感器节点的相关参数如表1所列。
在基于蜂窝网格的节点部署策略的仿真试验中，首先开始移动的是处于目标网格内部的节点，一次移动达到目标网格中心；接着运用考虑避障的部署策略移动处于目标网格外部的传感器节点。从图6可以看出，基于蜂窝网格的部署算法获得的覆盖率，在第一次部署得到的覆盖率低于虚拟力算法得到的覆盖率，但是在第4次循环迭代以后有明显增加的趋势，在第7次循环迭代后覆盖率达到95%以上，明显高于虚拟力算法获得的最高90%左右的覆盖率。更重要的是，从图7中可以看出，基于蜂窝网格策略的部署算法中，节点的最大平均移动距离为6 m，相比虚拟力算法中的8 m有所减小。
图6 监测区域在不同算法下得到的覆盖率
图7 节点的平均移动距离
结语
本文实现了基于蜂窝网格的无线传感器网络节点部署策略，相比传统的虚拟力算法，在提高覆盖率的同时，降低了节点的平均能耗。Matlab仿真实验表明，本文提出的算法能使覆盖率提高12%，节点平均移动距离减小25%，这从直观上反映出基于蜂窝网格策略的部署算法能节省能量。
编辑：admin 最后修改时间：2017-09-05
