收发分置雷达容错栅栏覆盖的优化部署

姜子琛　徐向华

摘 要： 针对收发分置雷达栅栏覆盖的部署位置容错问题，研究了雷达节点在有部署位置误差情况下的最大间隔部署策略。分析发现当雷达节点有位置误差时的最大间隔部署是一个非线性规划问题，通过限制相关条件得到了最大间隔部署问题的次优解；设计了贪心搜索算法实现了两个发送器之间的任意个数接收器的最优部署，最终找到了收发分置雷达的最优部署序列实现容错栅栏覆盖的最优部署，使得栅栏的探测性能最优。

关键词： 收发分置雷达； 位置容错； 栅栏覆盖； 最优部署序列

中图分类号：TP393.0 文献标志码：A 文章编号：1006-8228（2016）06-08-05

Abstract： This paper focus on the position fault tolerant of barrier coverage in bistatic radar sensor networks， studied the maximum interval deployment strategy when there is position fault of sensor node. It is found that when the radar node has position fault， the maximum interval deployment is a nonlinear programming problem， and the second-best solution can be got through restricting some conditions. The greedy-search algorithm is proposed to get the optimal deployment strategy of any number of receivers in between two transmitters， and finally found the optimal placement strategy for fault tolerant barrier coverage in bistatic radar sensor networks， and bring the barrier the optimal detection performance.

Key words： bistatic radar； fault tolerant； barrier coverage； optimal placement order

0 引言

收发分置雷达是近年来的研究热点，它的感知监测范围是一个卵形曲线包围区域[1]，与传统全向[2-3]、定向[4-5]的被动监测传感器的圆盘感知模型不同，它的这种特殊模型给收发分置雷达的栅栏覆盖部署问题研究带来了很大挑战。Gong[6]首次研究了基于收发分置雷达传感器网络的栅栏覆盖优化部署问题，他假定所有部署的雷达节点的位置都是精确且固定不变的，然而在现实场景中，所部署的雷达传感器通常会有一定的位置误差[7]，这一点在战场监测、边境安防等领域尤为重要。本文中我们首次研究了收发分置雷达栅栏覆盖的位置容错问题：构建了单个发送器的最大部署间隔；研究了在两个发送器之间的最优部署问题；通过贪心算法解决了任意两个发送器之间的接收器个数问题，最终得到了最优部署序列使得栅栏的探测性能最优。

1 传感器模型和相关定义

1.1 收发分置雷达模型

收发分置雷达分别由发送器和接收器构成，一个发送器和一个接收器构成一个雷达组，且发送器和接收器不在同一个位置。发送器通过发送信号，碰到目标后由接收器来接收信号，一个目标能否被一个雷达组探测到取决于这个目标接收到的信噪比大小。

其中星号代表发送器，圆形代表接收器。为了后面描述方便，我们给出以下相关概念的定义。

定义3：部署序列

我们把若干个发送器和接收器在一条直线上的一次排列称为一个部署序列，因此部署序列包含了两层含义：①雷达节点（发送器和接收器）的排列顺序；②各个相邻雷达节点之间的间距。

定义4：点的信噪比

对于栅栏上的任意一点x，它可能获得多对雷达组的对于改点的探测，因此我们把改点x获得的最大信噪比作为它的信噪比。

定义5：栅栏弱点

我们把栅栏I上所有的点中信噪比最小的点定义为这条栅栏的弱点。

收发分置雷达容错栅栏的优化部署问题：基于上述描述，我们给出本章研究的问题，具体描述如下。

问题1 假定图3中要部署的传感器的栅栏长度为L，现在给定M个发送器和N个接收器，我们的目标是如何确定最优部署序列才能使得栅栏的弱点信噪比最大，即所部署栅栏具有最优的入侵探测性能。其中每个部署的雷达节点有半径不大于δ的误差范围。

问题2 用式⑸描述，在栅栏的弱点信噪比不小于r的情况下，如何确定部署序列使得形成的栅栏长度最长。如果式⑸可解，那么我们可以用二分搜索算法求得问题1的解，得到最优栅栏部署方案。

2 栅栏优化部署模型

2.1 单个发送器的最大部署间隔

问题3 在T的一端部署n个接收器，如何确定部署序列，在其上任何一点的探测值不大于阈值C的情况下，使得部署序列覆盖的长度最长？

通过分析发现：只要保证任意两个相邻节点之间的弱点的探测值小于C，那么这两个节点之间的任意一点的探测值都会小于C。下面讨论当部署的雷达节点有误差时，如何解决问题3。

图4中虚线圆为雷达节点的误差范围。当雷达节点没有误差时，之间的弱点出现在中点O处。当雷达节点的位置出现误差时，T和T的位置分别变为T'和R'，弱点有可能变为O'。假设，容易发现，当发送器和接收器分别向两边偏移时，弱点探测值达到最大，因此即令，时，能保证TR之间任何一点都能被探测到。

当n=2时，如图5所示。

为计算方便，先建立一个坐标系。假设T点坐标为（0，0），偏差后坐标为T*（p，q），R1的坐标为（a，0），偏差后坐标为，R2的坐标为（b，0），偏差后坐标为，我们的目标是保证R1R2上的弱点的探测值小于C，而R1R2发生偏移后的弱点一定出现在的中点O。

接下来我们求点O最大可能的探测值，点O的坐标为，的最大距离为，因此点O的最大探测值可以表示为：

我们得到了在雷达节点的误差为δ情况下的最大间隔数组：。即只要按照此间隔数组在发送器的一端部署接收器，即使雷达节点有误差，依然能保证栅栏上所有点的信噪比不小于阈值。

2.2 两个发送器间的最优部署

在前一章中，我们在有误差情况下，获得了在单个发送器一端部署接收器时的最大间隔数组。接下来我们考虑在有误差情况下，在两个发送器之间部署n个接收器时的最优间隔问题。

当n=1时，如图6（a）所示：我们把左边那个T记为Tleft，把右边那个T记为Tright。容易得到，当时，覆盖的范围最大，这里的就是上节中得到的关于T的最大间隔数组中的。

当n=2时，如图6（b）所示：当，时，覆盖的范围最大。

依次类推，可以得到关于在TT之间部署n个接收器时的最大间隔部署的计算方法：

当n为奇数时：

当n为偶数时：

3 最优部署算法

3.1 贪心搜索算法

接下来我们需要确定任意两个相邻发送器之间的接收器个数，发送器之间的接收器部署按照2.2的方法进行，这样我们就得到了最终的最优部署序列。

为了描述方便，我们把任意两个发送器之间，或者发送器与边界之间的部分称为一个分段，因此M个发送器把整个栅栏分隔成M+1个分段。在下面的伪代码中，我们用part[i]代表分段i上已有的接收器个数，cover[i]代表在分段i上再部署一个接收器所能增加的覆盖范围。

4 模拟实验结果

在VS2013平台上我们对本文的方法进行了编码实现，该方法标注为OPT。为了验证算法的有效性，我们提出另外两种经验性的部署方法method1和method2。method1方法的思想：将所有的接收器等间隔部署在L上，然后分别将发送器等间隔部署在L上。method2方法的思想：将长度为L的直线M等分，每个发送器负责覆盖长为L/M的区域，同样将所有接收器等分给每个发送器。对于每个发送器Ti，假设它对应有Ni个接收器以及所覆盖的范围Li，我们通过如下方式确定每个节点的位置：将Ti部署在Li的中点处，Ti左右两侧分布部署Ni/2个接收器，部署的间隔分别为前一个间隔的1/2。

下面通过实验对这几种方法进行对比，假设栅栏长度为L=1000m，误差范围error=2m，其中图7（a）展示了在发送器个数为M=30的情况下，栅栏的弱点信噪比随着接收器个数的增加的变化情况，图7（b）展示了在接收器个数N=100的情况下，栅栏弱点信噪比随着发送器个数的增加的变化情况。实验结果很好地表明了本文OPT方法的有效性。

5 结束语

本文研究了收发分置雷达的容错栅栏覆盖问题。具体研究了单个发送器无误差情况下的最大部署间隔；分析了在有误差情况下的最大间隔部署；利用最大间隔数组解决了如何在两个发送器之间部署接收器的最优部署方法；通过贪心搜索算法解决了每个分段的接收器个数问题从而找到了最优部署序列；通过模拟实验验证了最优部署方法的有效性。

在本文中，我们假定所有的发送器都是同构的，即它们拥有相同的物理参数。未来也可以考虑异构的收发分置雷达部署问题，毫无疑问，这将大大增加问题的复杂性。当然也可以把收发分置雷达和其他问题结合，比如多普勒效应、能耗问题等等，相信会有更大的收获。

参考文献（References）：

[1] Willis， N.J.， Bistatic Radar. IET Digital Library，2004：53-79

[2] Bar-Noy， A.， D. Rawitz and P. Terlecky， Maximizing

Barrier Coverage Lifetime with Mobile Sensors. Lecture Notes in Computer Science，2013.8125：97-108

[3] Cardei， M.， et al. Energy-efficient target coverage in

wireless sensor networks. in Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies，2005.3：1976-1984

[4] Tao， D.， H. Ma and L. Liu， Coverage-Enhancing

Algorithm for Directional Sensor Networks. Mobile Ad-hoc and Sensor Networks，2006：256-267

[5] Wu， M.C. and W. Lu. On Target Coverage Problem of

Angle Rotatable Directional Sensor Networks. in Proceedings of the 2013 Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing，2013：605-610

[6] Gong， X.， et al. Barrier coverage in bistatic radar sensor

networks： cassini oval sensing and optimal placement. in Proceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing，2013：49-58

[7] Wang， Z.， et al. Fault tolerant barrier coverage for wireless

sensor networks. in Proceedings of INFOCOM，2014：1869-1877