收發分置雷達容錯柵欄覆蓋的優化部署

姜子琛　徐向華

摘 要： 針對收發分置雷達柵欄覆蓋的部署位置容錯問題，研究了雷達節點在有部署位置誤差情況下的最大間隔部署策略。分析發現當雷達節點有位置誤差時的最大間隔部署是一個非線性規劃問題，通過限制相關條件得到了最大間隔部署問題的次優解；設計了貪心搜索算法實現了兩個發送器之間的任意個數接收器的最優部署，最終找到了收發分置雷達的最優部署序列實現容錯柵欄覆蓋的最優部署，使得柵欄的探測性能最優。

關鍵詞： 收發分置雷達； 位置容錯； 柵欄覆蓋； 最優部署序列

中圖分類號：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