姜子琛　徐向華

摘 要： 針對(duì)收發(fā)分置雷達(dá)柵欄覆蓋的部署位置容錯(cuò)問(wèn)題，研究了雷達(dá)節(jié)點(diǎn)在有部署位置誤差情況下的最大間隔部署策略。分析發(fā)現(xiàn)當(dāng)雷達(dá)節(jié)點(diǎn)有位置誤差時(shí)的最大間隔部署是一個(gè)非線性規(guī)劃問(wèn)題，通過(guò)限制相關(guān)條件得到了最大間隔部署問(wèn)題的次優(yōu)解；設(shè)計(jì)了貪心搜索算法實(shí)現(xiàn)了兩個(gè)發(fā)送器之間的任意個(gè)數(shù)接收器的最優(yōu)部署，最終找到了收發(fā)分置雷達(dá)的最優(yōu)部署序列實(shí)現(xiàn)容錯(cuò)柵欄覆蓋的最優(yōu)部署，使得柵欄的探測(cè)性能最優(yōu)。

關(guān)鍵詞： 收發(fā)分置雷達(dá)； 位置容錯(cuò)； 柵欄覆蓋； 最優(yōu)部署序列

中圖分類號(hào)：TP393.0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

收發(fā)分置雷達(dá)是近年來(lái)的研究熱點(diǎn)，它的感知監(jiān)測(cè)范圍是一個(gè)卵形曲線包圍區(qū)域[1]，與傳統(tǒng)全向[2-3]、定向[4-5]的被動(dòng)監(jiān)測(cè)傳感器的圓盤感知模型不同，它的這種特殊模型給收發(fā)分置雷達(dá)的柵欄覆蓋部署問(wèn)題研究帶來(lái)了很大挑戰(zhàn)。Gong[6]首次研究了基于收發(fā)分置雷達(dá)傳感器網(wǎng)絡(luò)的柵欄覆蓋優(yōu)化部署問(wèn)題，他假定所有部署的雷達(dá)節(jié)點(diǎn)的位置都是精確且固定不變的，然而在現(xiàn)實(shí)場(chǎng)景中，所部署的雷達(dá)傳感器通常會(huì)有一定的位置誤差[7]，這一點(diǎn)在戰(zhàn)場(chǎng)監(jiān)測(cè)、邊境安防等領(lǐng)域尤為重要。本文中我們首次研究了收發(fā)分置雷達(dá)柵欄覆蓋的位置容錯(cuò)問(wèn)題：構(gòu)建了單個(gè)發(fā)送器的最大部署間隔；研究了在兩個(gè)發(fā)送器之間的最優(yōu)部署問(wèn)題；通過(guò)貪心算法解決了任意兩個(gè)發(fā)送器之間的接收器個(gè)數(shù)問(wèn)題，最終得到了最優(yōu)部署序列使得柵欄的探測(cè)性能最優(yōu)。

1 傳感器模型和相關(guān)定義

1.1 收發(fā)分置雷達(dá)模型

收發(fā)分置雷達(dá)分別由發(fā)送器和接收器構(gòu)成，一個(gè)發(fā)送器和一個(gè)接收器構(gòu)成一個(gè)雷達(dá)組，且發(fā)送器和接收器不在同一個(gè)位置。發(fā)送器通過(guò)發(fā)送信號(hào)，碰到目標(biāo)后由接收器來(lái)接收信號(hào)，一個(gè)目標(biāo)能否被一個(gè)雷達(dá)組探測(cè)到取決于這個(gè)目標(biāo)接收到的信噪比大小。

其中星號(hào)代表發(fā)送器，圓形代表接收器。為了后面描述方便，我們給出以下相關(guān)概念的定義。

定義3：部署序列

我們把若干個(gè)發(fā)送器和接收器在一條直線上的一次排列稱為一個(gè)部署序列，因此部署序列包含了兩層含義：①雷達(dá)節(jié)點(diǎn)（發(fā)送器和接收器）的排列順序；②各個(gè)相鄰雷達(dá)節(jié)點(diǎn)之間的間距。

定義4：點(diǎn)的信噪比

對(duì)于柵欄上的任意一點(diǎn)x，它可能獲得多對(duì)雷達(dá)組的對(duì)于改點(diǎn)的探測(cè)，因此我們把改點(diǎn)x獲得的最大信噪比作為它的信噪比。

定義5：柵欄弱點(diǎn)

我們把柵欄I上所有的點(diǎn)中信噪比最小的點(diǎn)定義為這條柵欄的弱點(diǎn)。

收發(fā)分置雷達(dá)容錯(cuò)柵欄的優(yōu)化部署問(wèn)題：基于上述描述，我們給出本章研究的問(wèn)題，具體描述如下。

問(wèn)題1 假定圖3中要部署的傳感器的柵欄長(zhǎng)度為L(zhǎng)，現(xiàn)在給定M個(gè)發(fā)送器和N個(gè)接收器，我們的目標(biāo)是如何確定最優(yōu)部署序列才能使得柵欄的弱點(diǎn)信噪比最大，即所部署柵欄具有最優(yōu)的入侵探測(cè)性能。其中每個(gè)部署的雷達(dá)節(jié)點(diǎn)有半徑不大于δ的誤差范圍。

問(wèn)題2 用式⑸描述，在柵欄的弱點(diǎn)信噪比不小于r的情況下，如何確定部署序列使得形成的柵欄長(zhǎng)度最長(zhǎng)。如果式⑸可解，那么我們可以用二分搜索算法求得問(wèn)題1的解，得到最優(yōu)柵欄部署方案。

2 柵欄優(yōu)化部署模型

2.1 單個(gè)發(fā)送器的最大部署間隔

問(wèn)題3 在T的一端部署n個(gè)接收器，如何確定部署序列，在其上任何一點(diǎn)的探測(cè)值不大于閾值C的情況下，使得部署序列覆蓋的長(zhǎng)度最長(zhǎng)？

通過(guò)分析發(fā)現(xiàn)：只要保證任意兩個(gè)相鄰節(jié)點(diǎn)之間的弱點(diǎn)的探測(cè)值小于C，那么這兩個(gè)節(jié)點(diǎn)之間的任意一點(diǎn)的探測(cè)值都會(huì)小于C。下面討論當(dāng)部署的雷達(dá)節(jié)點(diǎn)有誤差時(shí)，如何解決問(wèn)題3。

圖4中虛線圓為雷達(dá)節(jié)點(diǎn)的誤差范圍。當(dāng)雷達(dá)節(jié)點(diǎn)沒(méi)有誤差時(shí)，之間的弱點(diǎn)出現(xiàn)在中點(diǎn)O處。當(dāng)雷達(dá)節(jié)點(diǎn)的位置出現(xiàn)誤差時(shí)，T和T的位置分別變?yōu)門'和R'，弱點(diǎn)有可能變?yōu)镺'。假設(shè)，容易發(fā)現(xiàn)，當(dāng)發(fā)送器和接收器分別向兩邊偏移時(shí)，弱點(diǎn)探測(cè)值達(dá)到最大，因此即令，時(shí)，能保證TR之間任何一點(diǎn)都能被探測(cè)到。

當(dāng)n=2時(shí)，如圖5所示。

為計(jì)算方便，先建立一個(gè)坐標(biāo)系。假設(shè)T點(diǎn)坐標(biāo)為（0，0），偏差后坐標(biāo)為T*（p，q），R1的坐標(biāo)為（a，0），偏差后坐標(biāo)為，R2的坐標(biāo)為（b，0），偏差后坐標(biāo)為，我們的目標(biāo)是保證R1R2上的弱點(diǎn)的探測(cè)值小于C，而R1R2發(fā)生偏移后的弱點(diǎn)一定出現(xiàn)在的中點(diǎn)O。

接下來(lái)我們求點(diǎn)O最大可能的探測(cè)值，點(diǎn)O的坐標(biāo)為，的最大距離為，因此點(diǎn)O的最大探測(cè)值可以表示為：

我們得到了在雷達(dá)節(jié)點(diǎn)的誤差為δ情況下的最大間隔數(shù)組：。即只要按照此間隔數(shù)組在發(fā)送器的一端部署接收器，即使雷達(dá)節(jié)點(diǎn)有誤差，依然能保證柵欄上所有點(diǎn)的信噪比不小于閾值。

2.2 兩個(gè)發(fā)送器間的最優(yōu)部署

在前一章中，我們?cè)谟姓`差情況下，獲得了在單個(gè)發(fā)送器一端部署接收器時(shí)的最大間隔數(shù)組。接下來(lái)我們考慮在有誤差情況下，在兩個(gè)發(fā)送器之間部署n個(gè)接收器時(shí)的最優(yōu)間隔問(wèn)題。

當(dāng)n=1時(shí)，如圖6（a）所示：我們把左邊那個(gè)T記為Tleft，把右邊那個(gè)T記為Tright。容易得到，當(dāng)時(shí)，覆蓋的范圍最大，這里的就是上節(jié)中得到的關(guān)于T的最大間隔數(shù)組中的。

當(dāng)n=2時(shí)，如圖6（b）所示：當(dāng)，時(shí)，覆蓋的范圍最大。

依次類推，可以得到關(guān)于在TT之間部署n個(gè)接收器時(shí)的最大間隔部署的計(jì)算方法：

當(dāng)n為奇數(shù)時(shí)：

當(dāng)n為偶數(shù)時(shí)：

3 最優(yōu)部署算法

3.1 貪心搜索算法

接下來(lái)我們需要確定任意兩個(gè)相鄰發(fā)送器之間的接收器個(gè)數(shù)，發(fā)送器之間的接收器部署按照2.2的方法進(jìn)行，這樣我們就得到了最終的最優(yōu)部署序列。

為了描述方便，我們把任意兩個(gè)發(fā)送器之間，或者發(fā)送器與邊界之間的部分稱為一個(gè)分段，因此M個(gè)發(fā)送器把整個(gè)柵欄分隔成M+1個(gè)分段。在下面的偽代碼中，我們用part[i]代表分段i上已有的接收器個(gè)數(shù)，cover[i]代表在分段i上再部署一個(gè)接收器所能增加的覆蓋范圍。

4 模擬實(shí)驗(yàn)結(jié)果

在VS2013平臺(tái)上我們對(duì)本文的方法進(jìn)行了編碼實(shí)現(xiàn)，該方法標(biāo)注為OPT。為了驗(yàn)證算法的有效性，我們提出另外兩種經(jīng)驗(yàn)性的部署方法method1和method2。method1方法的思想：將所有的接收器等間隔部署在L上，然后分別將發(fā)送器等間隔部署在L上。method2方法的思想：將長(zhǎng)度為L(zhǎng)的直線M等分，每個(gè)發(fā)送器負(fù)責(zé)覆蓋長(zhǎng)為L(zhǎng)/M的區(qū)域，同樣將所有接收器等分給每個(gè)發(fā)送器。對(duì)于每個(gè)發(fā)送器Ti，假設(shè)它對(duì)應(yīng)有Ni個(gè)接收器以及所覆蓋的范圍Li，我們通過(guò)如下方式確定每個(gè)節(jié)點(diǎn)的位置：將Ti部署在Li的中點(diǎn)處，Ti左右兩側(cè)分布部署Ni/2個(gè)接收器，部署的間隔分別為前一個(gè)間隔的1/2。

下面通過(guò)實(shí)驗(yàn)對(duì)這幾種方法進(jìn)行對(duì)比，假設(shè)柵欄長(zhǎng)度為L(zhǎng)=1000m，誤差范圍error=2m，其中圖7（a）展示了在發(fā)送器個(gè)數(shù)為M=30的情況下，柵欄的弱點(diǎn)信噪比隨著接收器個(gè)數(shù)的增加的變化情況，圖7（b）展示了在接收器個(gè)數(shù)N=100的情況下，柵欄弱點(diǎn)信噪比隨著發(fā)送器個(gè)數(shù)的增加的變化情況。實(shí)驗(yàn)結(jié)果很好地表明了本文OPT方法的有效性。

5 結(jié)束語(yǔ)

本文研究了收發(fā)分置雷達(dá)的容錯(cuò)柵欄覆蓋問(wèn)題。具體研究了單個(gè)發(fā)送器無(wú)誤差情況下的最大部署間隔；分析了在有誤差情況下的最大間隔部署；利用最大間隔數(shù)組解決了如何在兩個(gè)發(fā)送器之間部署接收器的最優(yōu)部署方法；通過(guò)貪心搜索算法解決了每個(gè)分段的接收器個(gè)數(shù)問(wèn)題從而找到了最優(yōu)部署序列；通過(guò)模擬實(shí)驗(yàn)驗(yàn)證了最優(yōu)部署方法的有效性。

在本文中，我們假定所有的發(fā)送器都是同構(gòu)的，即它們擁有相同的物理參數(shù)。未來(lái)也可以考慮異構(gòu)的收發(fā)分置雷達(dá)部署問(wèn)題，毫無(wú)疑問(wèn)，這將大大增加問(wèn)題的復(fù)雜性。當(dāng)然也可以把收發(fā)分置雷達(dá)和其他問(wèn)題結(jié)合，比如多普勒效應(yīng)、能耗問(wèn)題等等，相信會(huì)有更大的收獲。

參考文獻(xiàn)（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