一种节点混合运动的有向传感器网络强栅栏构建方法*

何文秀，王宇翔，张 拓，徐瑞吉，方 丁

(1.浙江工业大学之江学院，浙江 绍兴 312030；2.浙江工业大学计算机科学与技术学院，浙江 杭州 310023)

无线传感器网络(Wireless Sensor Networks，WSN)简单来说，就是一种使用无线通信技术将若干各种种类的传感器节点以一定的网络结构构建起来的技术手段，能够有效检测穿越节点感知覆盖区域的目标。 这种技术可能应用到的传感器种类繁多，比如气体传感器、光敏传感器、激光扫描仪、毫米波雷达以及立体视觉摄像机等，多种多样的传感器不仅是实现网络构建的前提条件，也使得这种技术的应用领域十分广泛[1-2]。 无线传感器网络中有一种重要的技术，是将传感器节点沿着部署线部署，所有节点的感知覆盖区域就像栅栏一样划分一块区域，因而被形象地称为栅栏覆盖技术。 当有目标从一块区域越过栅栏进入到另一块区域时，这道由传感器节点构成的栅栏就能感知到并且将该信息上传[3-5]。 栅栏覆盖技术被广泛应用于环境保护、生态检测以及军事保护等方面[6]。 而如何利用有限的有向传感器节点实现无间隙的强栅栏构建是目前栅栏覆盖技术研究的难点和热点[7-9]。

得益于众多科研工作者对于该难点的持续研究，目前在栅栏覆盖技术方面已有许多效果良好的解决方法供后来者参考。 在应用全向传感器节点实现栅栏覆盖的研究中，Kumar 等[10]对弱k-栅栏覆盖与强k-栅栏覆盖两个新名词做出了定义，并且设计了一种用以判定节点覆盖区域是否符合k-栅栏覆盖的方法，还推导出在某种临界情形下会出现弱k-栅栏覆盖并给出了该情形的条件。 班冬松等[11]定义了1-BCMS 和1-GBMS 两个最小移动和问题，并且设计出了一种网络划分模型，通过使用这种模型可以使1-BCMS 向1-GBMS 近似转化，还设计了一种针对k-栅栏覆盖问题的方法，该方法基于分治策略，极大地减少了在计算和通信方面的耗费。Chen 等[12]设计了目标栅栏覆盖方法，由于这种方法可以同时检测外部目标向内入侵栅栏和内部目标向外突破栅栏，因而适用于比较特殊的场景，比如监狱等，降低了被入侵或突破的风险，有较高的实用价值。

在无线传感器网络的实际应用中，有些种类的传感器节点只能够感知周围某个角度范围内的目标，这些节点被统称为有向传感器节点，其感知范围取决于感知角和感知半径的大小。 事实上在一些特定的情形下，为了取得更好的栅栏构建效果往往会选择使用有向传感器节点。 针对此类情况，也有许多科研工作者提出了自己的解决方案，Tao 等[13]利用有向传感器节点能够通过旋转来调节方向的能力，设计了一种构建强栅栏的方法，首先利用DBG方向栅栏图获取传感器节点的最小需求数，然后根据尽可能减少旋转角度总和的原则，就能够以最低的旋转能耗完成强栅栏的构建。 由于有向传感器节点的应用给连接覆盖(Connection Coverage，CoCo)问题带来了新的挑战，因此Han 等[14]对最小能量连接覆盖问题进行了研究，他们实验的网络场景中既有有向特征又有全向特征，这两种特征共有四种不同的组合，经研究后给出了四种组合情况下的问题均为非确定性多项式难题的结论，同时提出了一种近似算法，旨在最小化传感和连接的总能量耗费。Khanjary 等[15]研究出了一种基于分布式自主学习方法在DBG 中获取栅栏部署区域的部署线，然后在保证不重叠的前提下旋转节点以改变其感知方向的方法，该方法的优势在于利用相同数量节点可以实现更高的栅栏构建率。 范兴刚等[16]从移动和转动能耗相结合的角度来考虑有向栅栏的构建问题，设计了一种称为DBCNA 的分布式方法，主要改进是可以控制相邻有向传感器节点的移动，使用该方法构建栅栏，可以降低需要的传感器节点数量和消耗的能量，虽然移动邻居节点的方法较为简单，无法做到最小化栅栏构建的总能耗，但仍有非常大的参考价值。 Zhao 等[17]解决了具有节点移动能力的有向传感器网络的节能栅栏覆盖问题，首先推导出了在二维矩形区域中遵循泊松点随机放置的有向传感器节点产生栅栏间隙的临界条件，然后设计了一种节能栅栏修复算法，该算法的特点是通过最小化传感器节点的移动距离来在一定程度上降低能耗，但无法最小化。 Chen 等[18]提出了一种CRA 强栅栏构建方法，该方法通过对节点进行旋转操作以修复栅栏间隙，然而该方法忽略了节点的移动特性，因此部署时节点的利用率不能达到最大。 赵小敏等[19]提出的OMBR 栅栏间隙修复方法，则是一种通过Hungarian 算法移动节点来修复栅栏间隙的方法，该方法只使用了节点的移动特性，同样不能最大化利用节点。

上述科研工作者留下了许多针对无线传感器网络中的栅栏覆盖问题行之有效的解决方案，但仍普遍存在节点利用率较低、栅栏构建率不高等缺陷。针对这些问题，本文提出一种节点混合运动的有向传感器网络强栅栏构建方法(A strong barrier construction method for directional sensor networks with node hybrid movement，BCNHM)，该方法通过将传感器节点分类为子栅栏节点和冗余节点，再利用冗余节点修复子栅栏节点之间的栅栏间隙，就可以使被部署节点得到更大程度的利用，同时在派遣冗余节点时加入了Hungarian 算法[20]对节点的派遣方式完成优化，最小化冗余节点在移动中产生的能耗。 该方法在完成栅栏构建工作的基础上，在提升节点利用率和栅栏构建率方面有良好的性能。

1 相关模型与假设

1.1 相关模型

有向传感器通常采用的是〈P，R，α，β〉组成的四元组感知模型。

在图1 所示的模型示意图中，P(x，y)代表的是一个节点在平面直角坐标系上的相对坐标；由于节点的感知覆盖范围通常为扇形区域，因此用R代表覆盖区域的半径；α代表该节点感知方向与坐标轴的夹角大小，取值范围在0 与2π 之间；β表示的是该节点感知角的大小，β越大则该节点的感知范围越广，而当β＝2π 时，该有向传感器就变成了全向传感器；MN代表的是扇形区域里最长的弦。

图1 有向传感器感知模型

1.2 相关假设

①传感器网络的所有节点均为同一种类且内部构造相同，都能够进行任意方向的位移和旋转；

②所有节点都知道自己的坐标P(x，y)和感知方向夹角α；

③所有节点每移动1 m 能耗均为Jm＝3.6 J，每转动π 角度能耗均为Jr＝1.8 J[21-22]；

④所有节点在能量充足的情况下移动距离和旋转角度不受限制；

⑤当检测目标出现在节点感知区域之外时，无法检测到；反之则必定能够检测到目标。

2 子栅栏构建

2.1 子栅栏查找

栅栏构建首先需要沿着目标栅栏的部署线，在长为L宽为W的矩形区域内(通常L远大于W)部署传感器节点，在这一过程中往往会出现节点受风力、地形等环境因素影响而位置偏离的情况。 假设节点的个数为N，定义i、j为任意两个不同节点的编号(0

一般当两个节点的感知区域存在交集时，认为它们共同形成了一段子栅栏。 具体的判断方法如下:首先计算两个节点ni和nj感知区域边界之间的欧式距离，然后获取其中的最小值dis(ni，nj)作为感知区域间的距离。 若dis(ni，nj)＝0，认为两个区域存在交集；若dis(ni，nj)＞0，则认为两个区域不存在交集，即出现了栅栏间隙[23]。 这种子栅栏的判断方法是后续步骤能够实现的基础。

以x轴为横坐标，y轴为纵坐标在部署区域建立平面坐标系，然后将传感器节点沿着目标部署线放置，由于受到外界环境的影响，节点位置会如图2所示情形偏离x轴，这时将这些节点根据横坐标从小到大排列，获得所有节点集合Set ＝{n1，n2，…，nN}，同样用dis(ni，nj)代表任意两个节点感知区域间的距离。 在完成上述的准备工作后，就有了一种子栅栏的查找算法:从横坐标最小的两节点n1和n2开始，先计算dis(n1，n2)，若dis(n1，n2)＝0，即两个节点共同构建了子栅栏，把这两个节点添加到第一个子栅栏的集合B1内(B1为Set 类型的集合，能自动丢弃重复元素)。 随后对节点n2、n3和n4计算dis(n2，n3)和dis(n2，n4)，若dis(n2，n3)＞0 并且dis(n2，n4)＝0，则说明n2与n4共同构建了子栅栏而n3则没有参与构建。 类似n3的节点被称作冗余节点，需要添加到冗余节点集合Rs中，而节点n4则添加到集合B1内；若dis(n2，n3)＝0 则仅需把n3添加到B1内。 根据这样的规则重复进行距离计算与节点归类，直到遇见图2 中n4和n5对应的情况，子栅栏无法继续延长说明已经完成了一条子栅栏的查找，即子栅栏B1＝{n1，n2，n4}，冗余节点集合Rs＝{n3}；接着从节点n5开始重复上述过程，开始下一条子栅栏B2的构建，一直到区域内的所有节点都被归类到某个集合中，则算法结束。 表1 中介绍了算法的详细步骤以及伪代码。

图2 子栅栏分段构建图

表1 子栅栏构建算法表

7: Rs.add(ni+1，…，nmax(j)-1)；8: i←max(j)；9: else 10: t++；11: end if 12: i++；13:end for

2.2 子栅栏间隙修复

如图2 中的G1所示，在子栅栏初步构建后，两个子栅栏间通常会存在间隙，这时候就需要考虑移动或转动有向传感器节点来拼接它们，而由1.2 小节中的假设③可知:节点移动单位距离所消耗的能量要远高于转动单位角度消耗的能量。 因此在实际应用中，为了减少在拼接过程中产生的能耗，就要优先考虑通过转动节点的方式实现拼接。 假设存在间隙的两个节点编号分别为w、v，可以按照下述的流程完成拼接:

Step 1:(a)单独在子栅栏间隙左侧进行转动操作。 以图3(a)中nw为例，对它进行转动直至与nv的感知区域出现重叠，在两个节点的感知区域有相交的情况下，可以得到nw的角度为θ＝[](θ指的是节点感知区域的下边界PM 与x轴正方向形成的夹角)，又在和nw-1的感知区域相交的情况下，可以得到角度φ＝[]，则θ与φ的重叠区域的交角为ψ＝[]。 在交角ψ≠0 的情况下，只需依照式(2)所得的度数转动，就能够完成子栅栏的拼接，Δ＞0 时nw应当转动至，否则转动至x处。 若出现ψ＝0 的情况则跳转至Step 1(b)。

在式(2)中，节点未转动时感知区域的下边界PM 与x轴正方向形成的夹角为(由图1 可以得出)；其中代表θ和φ相交角度的上界；代表θ和φ相交角度的下界。

(b)单独在子栅栏间隙右侧进行转动操作。 以图3(b)中nv为例，对它进行转动直至与nw的感知区域出现重叠，在两个节点的感知区域有相交的情况下，可以得到nv的角度为θ＝[]，又在和nv+1的感知区域相交的情况下，可以得到角度φ＝[]，则θ与φ的重叠区域的交角为ψ＝[]。 在交角ψ≠0 的情况下，只需依照式(2)所得的度数进行转动，就实现了子栅栏的拼接，Δ＞0 时nv应当转动至，否则转动至处。 如果出现ψ＝0 的情况则算法转到Step 2。

图3 单个节点拼接子栅栏图

Step 2:同时在子栅栏间隙两侧进行转动操作。在Step 1 中，为了拼接子栅栏，算法对节点nw进行旋转操作，使其旋转至处(Δ＞0)。 完成Step 1能够有效缩短子栅栏的间隙长度，但不一定能完全消除间隙，此时将出现如图4(b)所示的新栅栏间隙NewGi。 出现这种情况时，需要再次调用Step 1(b)，转动NewGi右侧的nv来尝试完成拼接，若能达到如图4(c)所示的情况，则拼接成功。 否则重新使nw转动到，同时重复Step 1(b)中的方法再次尝试，如仍不能完全消除栅栏间隙，则拼接失败，算法转到Step 3。

图4 两节点同时拼接子栅栏图

Step 3:对间隙左侧节点和右侧子栅栏进行转动操作。 首先，对间隙左侧的节点调用Step 1(a)转动，完成转动有效减小了nw右侧的间隙，形成了较短的新栅栏间隙。 然后，对间隙右侧的节点调用Step 1(b)转动。 经过这一步，nv右侧也与节点nw一样形成了新的栅栏间隙，并且接下来的节点的情况均类似，所以逐个对nv与nv+1间以及所有后续节点间的新栅栏间隙调用Step 1(b)中的方法，如此重复至出现旋转后节点右侧没有出现新栅栏间隙的情况，算法结束。 如果完成所有节点的遍历，且节点右侧仍存在栅栏间隙，则说明子栅栏无法完全拼接，此时需要回滚操作，使初始状态时位于该间隙右侧的所有节点的朝向均复原，最后调用Step 1(b)使右侧第一个节点nv转动到处，以达到无法完全拼接的情况下最小化栅栏间隙长度的目的。

Step 4:对栅栏两端与边界的间隙进行修复。 在经过前面的步骤后，算法已经完成了子栅栏之间的拼接，这一步需要修复如图2 中Gt所示的间隙(t表示边界间隙的编号)，由于边界节点的感知方向发生了改变，导致与部署区域的边界之间出现了间隙。这种间隙的修复方法也比较简单，首先观察栅栏第一个节点n1的感知区域有没有触及左边界，若触及说明并未出现边界间隙，不作处理，若未触及则调用Step 1(b)转动节点以修补间隙。 接着同样观察栅栏最后一个节点nN的感知区域有没有触及右边界，若触及则不作处理，若未触及则调用Step 1(a)转动节点以修补。

3 栅栏间隙修复

子栅栏拼接有时会出现只靠旋转节点无法完全拼接的情况，此时栅栏间仍存在间隙，为解决该问题，同时提高节点利用率，选择对冗余节点进行旋转及移动操作对待修复位置进行修复。 然而怎样确定待修复位置，以及如何派遣冗余节点至修复位置，这些问题有待解决。

3.1 寻找待修复位置

待修复位置指的是冗余节点需要派遣到的位置。 由1.2 小节中的假设③可知:有向传感器节点的移动能耗比转动能耗高。 因此要降低修复栅栏间隙能耗，就需要尽量降低冗余节点在移动上的能耗，优先考虑旋转节点进行修复。 在整个栅栏间隙修复的过程中，感知角β 能影响节点的感知范围，栅栏间隙长度dG则决定了需要修复的距离，两者均会使待修复位置的寻找过程发生改变，而各种情形下β和dG均存在差异，下面将分别说明在各种情形下查找待修复位置的方式:

首先根据栅栏间隙长度dG的大小可以将寻找待修复位置的情形分为两大类，0

(1)在0

①在0<β<2arcsin(dG/2R)的情形下，使用边覆盖的方式查找待修复位置。 如图5(a)所示，边覆盖需要对待修复的栅栏间隙进行建模，首先找到栅栏间隙两侧节点感知区域的最短连线ST，可知ST 的长度就是dG，然后设连线中点为圆心O，以半径r＝R-dG/2 作圆C，此时延长连线ST可以得到与圆C的两个交点P1、P2，这两个点就是要找的待修复位置，可以根据实际情况派遣冗余节点至其中一个位置进行栅栏间隙修复。 下面选择P1证明冗余节点在该点可以实现修复:已知冗余节点的感知区域半径为R，而P1与间隙右侧节点的最短欧式距离d(P1，T)也为R，显然R≥dG，因此当冗余节点被派遣到P1处，且进行旋转操作必定能实现对栅栏间隙G的边覆盖，达到修复的效果。

②在2arcsin(dG/2R)≤β<2π 的情形下，可以使用边覆盖或弧覆盖的方式查找待修复位置。 如图5(b)所示，同样对栅栏间隙进行建模，首先找到栅栏间隙两侧节点感知区域的最短连线ST，然后分别以连线端点S、T为圆心，R为半径作圆，可以得到两个圆的交点P3、P4，这两个点就是要找的待修复位置。 下面选择P3证明冗余节点在该点可以实现修复:根据冗余节点感知区域的扇形模型，可以得出其中弦的长度最大值MN＝2Rsin(β/2)，由前提条件2arcsin(dG/2R)≤β变形可得2Rsin(β/2)≥dG，即MN≥dG，这正是实现弧覆盖需要满足的条件。 因此当冗余节点被派遣到P3处，且进行旋转操作必定能实现对栅栏间隙G的弧覆盖。 除了弧覆盖，情形①的边覆盖也同样适用于这种情形，所以可以根据情形①同样得到P1和P2，共计四个待修复位置可以达到修复的效果。

图5 待修复位置图

(2)在R

①在0<β<π/3 的情形下，仅靠移动一个冗余节点无法完成修复。 在这种条件下，可知栅栏间隙的长度dG大于冗余节点感知区域半径R，因此单个冗余节点的感知区域无法覆盖栅栏间隙。

②在π/3≤β<π 的情形下，若dG＞2Rsin(β/2)，则与①同理，同样无法依靠移动一个冗余节点完成修复。 若dG≤2Rsin(β/2)，则可如图5(c)所示的方式实现对栅栏间隙的弧覆盖，首先使用弧覆盖的方法可以查找到待修复位置P1、P2，同样举P1为例:通过条件dG≤2Rsin(β/2)计算可得弦MN的长度，显然此时MN长于栅栏间隙ST，而且MN的长度会随着β的增大而增大，所以必定能实现对栅栏间隙的弧覆盖，达到修复的效果。

③在π≤β<2π 的情形下，同样可以派遣单个冗余节点实现弧覆盖。 在π≤β<2π 的条件下，冗余节点感知区域的最大弦显然是直径，即MN＝2R，而已知dG≤2R，因此可以通过弧覆盖的方法查找到待修复位置P1、P2来实现栅栏间隙的修复。

由上述各类情形可以看出，在单个冗余节点能够实现栅栏间隙修复的情形中，可以查找到的待修复位置往往有多个，在图5(b)的情形中能够查找到四个待修复位置均可以用来修复栅栏间隙。 然而待派遣的冗余节点的位置到每个待修复位置的距离各不相同，导致派遣到不同待修复位置消耗的能量也有差异，因此还需要做出选择。 为了降低所有冗余节点在完成移动派遣后最终消耗的能量总值，应当选取与待派遣的冗余节点距离最短的待修复位置。

3.2 Hungarian 算法派遣冗余节点

在完成待修复位置的定位之后，就要进行冗余节点的派遣，为了在提高传感器节点利用率的同时尽可能减少派遣过程中产生的能耗代价，本文在派遣冗余节点时使用了Hungarian 算法，力求消耗最少的能量实现移动派遣。 Hungarian 算法的核心思想是以派遣冗余节点的距离代价为元素来构建代价矩阵，最终实现冗余节点和待修复位置的最佳匹配。

在使用Hungarian 算法前首先要对冗余节点的个数进行判断，若冗余节点的个数m少于栅栏间隙的数量n，则认为无法完成栅栏间隙的修复任务；若m＝n，则可以直接构建式(3)中的代价矩阵，其中dij(0≤i≤m，0≤j≤n)代表第i个冗余节点Rsi到第j个栅栏间隙的待修复位置Pj的最短距离；当m＞n时比较特殊，由于Hungarian 算法要求匹配双方数目一致，为了将其用在这种情形下，就需要将待修复位置的数量补足，具体操作为增设m-n个到冗余节点距离为0 的虚拟待修复位置，然后可以构建代价矩阵。

完成代价矩阵构建后需要使用Hungarian 算法对其进行优化处理，最终得到的最低Cost 就对应着最佳的派遣方式，可以使冗余节点在派遣过程中的移动能耗最小。 具体处理步骤以图6 情形为例进行说明:

图6 Hungarian 算法派遣冗余节点修复间隙图

①由于栅栏间隙的数量n＝1，因此最终的待修复位置为Pi(Pi∈{})，其中i为该栅栏间隙的编号；又因冗余节点的个数m＝2，所以需要增设1个虚拟的待修复位置。 根据式(3)最终得到式(4)所示的代价矩阵，因为虚拟待修复位置与冗余节点距离为0，因此代价矩阵第二列均为0。

②每一行的所有矩阵元素减去该行的最小值，每一列的所有矩阵元素也减去该列的最小值，得到式(5)所示代价矩阵。

③用最少的行列覆盖代价矩阵中所有的0，此处使用第二行与第二列即可覆盖所有的0，因此行列数为2，与矩阵大小相等，达到最佳匹配，算法停止。

④根据代价矩阵(5)中0 的位置为第一行第二列与第二行第一列可知(每列只选择一个0)，应当将Rs1派遣至虚拟待修复位置，Rs2派遣至，对应的最佳匹配的代价为d2i。

由于派遣冗余节点只是将节点移动到了待修复位置，不改变节点的感知方向，因此派遣后节点并不一定成功修复了栅栏间隙。 这时还需要对节点进行旋转操作以达到修复的目的。

4 仿真实验

为了验证算法的有效性，在i7 处理器，8G 内存的PC 机上利用MATLAB R2013a 软件进行仿真实验。 仿真实验中的部署区域为长1 000 m，宽200 m的矩形区域，将有向传感器节点在部署区域内沿着目标栅栏部署线进行部署，其中节点的感知区域半径R＝45m，感知角β＝π/3，部署时节点感知方向随机。 将32 个节点以0 为均值，25 为方差的高斯分布部署于目标区域内，如图7 所示。 部署后使用子栅栏构建方法将初期随机部署的节点进行子栅栏的构建及拼接，如图8 所示。 子栅栏完成拼接后仍存在间隙，则进行栅栏间隙修复，如图9 所示。

图7 节点随机部署图

图8 子栅栏拼接图

图9 栅栏间隙修复图

仿真实验将以栅栏间隙数量、节点利用率、栅栏构建率以及网络总能耗四个方面为性能指标对本文所述的BCNHM 栅栏构建方法进行性能验证与评价。 仿真实验还与CRA 强栅栏构建方法以及OMBR 栅栏间隙修复方法进行了对比实验，其中CRA 是一种通过转动节点感知方向来完成栅栏构建的方法，而OMBR 则是一种通过Hungarian 算法移动节点来修复栅栏间隙的方法，这两种方法均可以提高栅栏的构建率，并且在一定程度上代表了有向传感器节点的两类栅栏构建方法，因此选作对比方法。

4.1 节点部署数量影响

理论上来说，部署区域内有向传感器节点的数量大小是栅栏构建率的关键影响因素之一。 在有限的部署区域内，部署的节点个数越多，栅栏的构建率也就越高，而构建率的提高使耗费在移动和旋转上的能量减少，从而使网络的总能耗降低。 由于节点在实际部署过程中产生偏移的标准差通常为5，因此设置σx＝σy＝5，同时在实际场景中常见的有向传感器节点的感知角为π/3，故选其作为仿真节点的感知角进行仿真实验，在保证独立性的前提下进行100 次同样的实验，然后取结果均值绘制成如图10、11 的折线图，便于后续的实验分析。

图10(a)反映的是栅栏间隙个数随着部署区域内节点数量变化的关系。 实验结果表明随着节点数量的增加，构建栅栏时出现的间隙将减少。 当部署的节点数量相同时，本文的BCNHM 算法形成的间隙数量最少，随后是OMBR 算法与CRA 算法，最多的是没有对节点进行转动和移动操作的原始栅栏(Original)。 这是因为OMBR 算法和CRA 分别只利用了节点的移动能力和转动能力，因此在构建栅栏时仍然有间隙存在，而BCNHM 算法同时对节点的两种能力加以利用。 当仅依靠节点旋转无法将栅栏间隙完全修复时，算法就会派遣最近的冗余节点至待修复位置对栅栏进行修复。 因此完成相同的栅栏构建工作，BCNHM 算法需要使用的有向传感器节点个数更少。

图10(b)反映的是节点利用率随着节点数量变化的关系。 当节点数量在区间[30，35)时，BCNHM的节点利用率为100%，因为此时的节点数量少于或者刚好达到构建一条栅栏所需的节点数量，而BCNHM 算法充分利用了部署区域内的冗余节点。当节点数量在区间[35，50]时，节点的利用率随着节点数量的增多而缓慢降低，由于构建栅栏所需的节点数量只在一定的范围内波动，因此随着节点增多冗余节点也会相应增多，从而出现节点利用率逐渐降低的情况。 当节点数量相同时，BCNHM 的节点利用率最高，OMBR 次之，CRA 和Original 的利用率相同且较低。

图10 节点数量对栅栏构建影响图

图10(c)反映的是栅栏构建率随节点数量变化的关系。 四种算法的栅栏构建率都会随着节点数量的增多而逐渐提高，不过提高的速率有所差异。 其中BCNHM 的栅栏构建率提高得最快，OMBR 算法次之，随后是CRA 算法，Original 算法提高得最慢。并且，在相同节点数量的前提下，BCNHM 的栅栏构建率要远高于其余几种算法。 OMBR 算法与CRA算法通过对节点进行移动或旋转操作来进行栅栏构建，所以效果要好于Original，而BCNHM 算法充分利用节点的转动和移动能力进行栅栏构建，所以构建效果是最好的，达成百分百的栅栏构建率，即构建一道强栅栏只需要部署35 个传感器节点。

图10(d)反映的是网络总能耗随着节点数量变化的关系。 由于CRA 没有考虑节点的移动能力，作为实验对比没有意义，因此选用被广泛用于节点派遣问题的Greedy 算法[24]进行对比实验；由于节点通信消耗的能量远低于节点转动或者移动时的能耗，本实验忽略节点通信时的能耗，其中能耗模型如假设③所示。 通过实验结果可以看出，在相同节点数量的前提下，BCNHM 与OMBR 的节点能耗比Greedy 算法低，这是因为Greedy 通过派遣距离间隙最近的节点进行间隙修复，会陷入局部最优，而BCNHM和OMBR 均采用Hungarian 算法派遣冗余节点，对全局最优进行考虑，此时节点的移动距离总和更短，因此消耗的能量更低；而BCNHM 相对于OMBR 将一部分移动操作转化为了能耗更低的转动操作，耗能更少；Original 没有对节点进行操作，因此没有能量消耗。

4.2 节点感知角影响

分析节点感知角对栅栏构建的影响，同样设置σx＝σy＝5，同时设置节点数量N＝40(经实验验证该节点数量下便于分析不同算法的差异)。 实验结果如图11 所示。

图11 节点感知角对栅栏构建影响图

图11(a)反映的是栅栏间隙数量随着节点感知角变化的关系。 实验结果表明，随着节点感知角的增大，间隙数量逐渐减少，因为当感知角增大时节点感知范围增大，有较多间隙随着节点感知范围增大而被覆盖，因此间隙数量减少。 当感知角相同时，由于BCNHM 算法充分利用冗余节点进行间隙修复，构建的栅栏间隙数量少于其他几种算法。

图11(b)反映的是节点利用率随着节点感知角变化的关系。 从实验数据可以看出，节点利用率随着节点感知角变大而降低，这是由于感知角增大使感知区域变大，降低了构建栅栏需求的节点数量，从而增加了冗余节点的数量，降低了节点利用率。 当节点的感知角在区间[20°，40°]时，仅靠N＝40 的节点数量无法通过单一操作完成子栅栏的拼接，仅有BCNHM 算法可以派遣所有的冗余节点进行间隙的修复，因此节点的利用率可达100%。 在感知角相同时，BCNHM 利用率最高，OMBR 对冗余节点的利用不充分，节点利用率次之，CRA 未利用冗余节点，因此节点利用率与Original 相同且最低。

图11(c)反映的是栅栏构建率随着节点感知角变化的关系。 实验结果表明，四种算法的栅栏构建率均与节点感知角成正相关关系。 而在相同节点感知角的前提下，BCNHM 算法的栅栏构建率和栅栏构建率的提升速率均高于其余几种算法，OMBR 与CRA 算法分别需要感知角增大到140°与160°时，栅栏构建率才能提升至100%，而BCNHM 算法只需要节点感知角增大到60°左右，就可以实现100%的构建率。

图11(d)反映的是网络总能耗随着节点感知角变化的关系。 当感知角在[20°，68°)时网络总能耗随着角度增大迅速下降，而当感知角在[68°，180°]区间内，网络总能耗缓慢降低。 这是因为节点感知角小于68°时仅通过旋转节点不能完成栅栏构建，此时派遣冗余节点进行修复需要消耗大量能量，且随着感知角增大，此时栅栏出现的间隙迅速减少，因此出现了网络总能耗快速下降的趋势。 当感知角大于68°时此时只需转动节点即可完成栅栏拼接，因此耗能低。

5 总结

现有的有向传感器网络栅栏构建方法普遍存在着节点利用率不高，栅栏构建率低的问题，本文针对这些问题，设计了一种节点混合运动的有向传感器网络强栅栏构建方法BCNHM。 BCNHM 利用转动有向传感器节点的方法初步形成子栅栏，同时较好地利用了冗余节点的移动和转动来完成栅栏间隙的修复，从而达到构建强栅栏的目的。 将该方法与目前性能较好的强栅栏构建方法CRA 和栅栏间隙修复方法OMBR 进行仿真对比实验，证明了BCNHM 在提高节点利用率和栅栏构建率方面拥有更好的性能。 在未来的研究中，准备继续对强栅栏的构建方法进行探究，比如有向传感器的K-栅栏覆盖方法。 未来也考虑将该算法实际应用于化工厂等高危场所的环境安全监测与报警系统中，进行实地的实验验证。