徐 英,周尚武,丁 鋒

(1.國防科技大學(xué)電子對抗學(xué)院,合肥 230037;2.安徽新華學(xué)院,合肥 230088)

無線電監(jiān)測往往需要多個監(jiān)測傳感器(以下簡稱監(jiān)測站)組成監(jiān)測網(wǎng)絡(luò)[1],以實現(xiàn)對監(jiān)測區(qū)域或目標(biāo)的最大化覆蓋。用最少的監(jiān)測站實現(xiàn)最大的監(jiān)測覆蓋率,即,實現(xiàn)監(jiān)測站部署的最優(yōu)化規(guī)劃,是提高節(jié)點(diǎn)部署效率和延長網(wǎng)絡(luò)生命周期的前提。對監(jiān)測站部署優(yōu)化需要解決兩個方面的問題,一是優(yōu)化算法,二是部署效率評估。傳統(tǒng)的無線電監(jiān)測網(wǎng)絡(luò)規(guī)劃[2-3]主要從選址原則、標(biāo)準(zhǔn)、周邊環(huán)境等方面考慮[4],沒有考慮監(jiān)測站部署效率優(yōu)化問題。陳升來、劉旭、胡進(jìn)輝等分別通過遺傳算法[5-10]、遺傳編程[11]、模擬退火遺傳[12]等算法解決無線電監(jiān)測網(wǎng)絡(luò)規(guī)劃的監(jiān)測站優(yōu)化部署問題,利用適應(yīng)度函數(shù)評估種群中每個個體解決目標(biāo)問題的能力,得到的優(yōu)化部署結(jié)果與染色體數(shù)目和循環(huán)次數(shù)有較大關(guān)系,運(yùn)算量大,且單純以覆蓋率作為指標(biāo)容易出現(xiàn)重復(fù)率過大的問題。

針對無線電監(jiān)測站分布式部署優(yōu)化存在的不足,構(gòu)建對無線電監(jiān)測網(wǎng)絡(luò)協(xié)同監(jiān)測部署效率評估指標(biāo)體系,基于空間二次聚類算法進(jìn)行優(yōu)化部署,實現(xiàn)部署效率的量化評估和最優(yōu)化部署,并通過仿真實驗驗證了算法的有效性和實用性。

1 監(jiān)測傳感器網(wǎng)絡(luò)部署效率指標(biāo)體系

對監(jiān)測站部署效率的評估是對多個監(jiān)測站協(xié)同監(jiān)測[13-14]的部署效率進(jìn)行綜合評估[15],需要考慮監(jiān)測覆蓋率、傳感器數(shù)量、監(jiān)測重復(fù)率等多方面的影響因素,評估指標(biāo)體系可分解為如圖1所示。

圖1 監(jiān)測傳感器網(wǎng)絡(luò)監(jiān)測效率評估指標(biāo)體系分解圖

①協(xié)同監(jiān)測覆蓋率

監(jiān)測站部署優(yōu)化的目的是用最少的監(jiān)測站實現(xiàn)最大的監(jiān)測覆蓋率。對于區(qū)域監(jiān)測[16],假設(shè)已知單個監(jiān)測站的監(jiān)測覆蓋范圍,對應(yīng)的監(jiān)測區(qū)域為Mi,由于不同監(jiān)測站的監(jiān)測區(qū)域可能會有重合,多個監(jiān)測站協(xié)同監(jiān)測區(qū)域定義為所有監(jiān)測站可監(jiān)測區(qū)域的并集集合,則協(xié)同監(jiān)測覆蓋率H由下式確定:

(1)

式中:i=1,2,…,k,k為部署的監(jiān)測站個數(shù),X為監(jiān)測任務(wù)區(qū)域,Area(·)為區(qū)域面積。

對于點(diǎn)目標(biāo)監(jiān)測,假設(shè)第i個監(jiān)測站的可監(jiān)測目標(biāo)集Pi={p1,p2,……,pNi},共有目標(biāo)Ni個,不同監(jiān)測站可以監(jiān)測的目標(biāo)可能會有重合,因此多個監(jiān)測站協(xié)同監(jiān)測目標(biāo)集定義為所有監(jiān)測站可監(jiān)測目標(biāo)集的并集集合,則協(xié)同監(jiān)測覆蓋率H由下式確定:

(2)

式中:i=1,2,…,k,k為部署的監(jiān)測站個數(shù),W為監(jiān)測任務(wù)目標(biāo)集合,Count(·)為目標(biāo)集合中的目標(biāo)數(shù)。

②協(xié)同監(jiān)測重復(fù)率

為了提高監(jiān)測站的利用率,應(yīng)盡量避免不同監(jiān)測站的監(jiān)測區(qū)域或監(jiān)測目標(biāo)之間有較大的重合,即要求協(xié)同監(jiān)測的重復(fù)率較小。對于區(qū)域監(jiān)測,多個監(jiān)測站協(xié)同監(jiān)測重復(fù)區(qū)域為所有監(jiān)測站可監(jiān)測區(qū)域的交集集合,則定義協(xié)同監(jiān)測的重復(fù)率為協(xié)同監(jiān)測重復(fù)區(qū)域和協(xié)同監(jiān)測區(qū)域的比值,由下式計算得到:

(3)

對于點(diǎn)目標(biāo)檢測,多個監(jiān)測站協(xié)同監(jiān)測重復(fù)目標(biāo)集為所有監(jiān)測站可監(jiān)測目標(biāo)集的交集集合,則定義協(xié)同監(jiān)測重復(fù)率為協(xié)同監(jiān)測重復(fù)目標(biāo)數(shù)和協(xié)同監(jiān)測目標(biāo)數(shù)的比值:

(4)

2 基于空間二次聚類的監(jiān)測站優(yōu)化部署算法

無線電監(jiān)測站部署優(yōu)化的根本思想是求出一組最優(yōu)的監(jiān)測站站址分布方案,用最小的成本(即最少的監(jiān)測站)來實現(xiàn)設(shè)定的協(xié)同監(jiān)測覆蓋率,達(dá)成監(jiān)測站的最優(yōu)化部署。

設(shè)有空間要素集合F={f1(x1,y1),f2(x2,y2),…,fn(xn,yn)}(n≥2),其中fi(xi,yi)表示發(fā)射站i的空間位置二維坐標(biāo)向量,fi到fj(1≤i,j≤n)的空間距離為Disfij,定義為:

(5)

假設(shè)監(jiān)測站在各個方向的監(jiān)測距離相同,取監(jiān)測距離R作為閾值。當(dāng)若干個空間要素的空間距離接近,且分布在同一個半徑為R的圓內(nèi)時,可劃分為同一類簇。取簇內(nèi)所有空間要素的外接矩形的中心作為圓心,獲得一次聚類中心。

經(jīng)過一次聚類后,不同簇內(nèi)的點(diǎn)仍有可能在同一個半徑為R的圓內(nèi),此時,依據(jù)簇中心與外接矩形點(diǎn)的位置關(guān)系,對一次聚類結(jié)果進(jìn)行二次聚類,即取一次聚類的簇中心作為二次聚類的空間要素,閾值取為2R,簇中心滿足聚類條件且兩簇的最遠(yuǎn)點(diǎn)距離小于2R的相鄰簇,則合并為一個簇。

設(shè)一次聚類獲得m個類簇,各簇中心分別為(X1,Y1),(X2,Y2),…,(Xm,Ym),第k個簇中所有空間要素的外接矩形的4個頂點(diǎn)坐標(biāo)分別為(minxk,minyk)、(maxxk,minyk)、(minxk,maxyk)和(maxxk,maxyk),則將第k個簇和第p個簇二次聚類為同一類簇的約束條件如下:

條件1:

Dis[(Xk,Yk),(Xp,Yp)]<2R
Dis[(minxk,minyk),(maxxp,maxyp)]<2R
Dis[(maxxk,maxyk),(minxp,minyp)]<2R

(6)

條件2:

Dis[(minxk,minyk),(Xp,Yp)]<2R
Dis[(minxk,maxyk),(Xp,Yp)]<2R

(7)

條件3:

Dis[(maxxk,maxyk),(Xp,Yp)<2R]
Dis[(maxxk,minyk),(Xp,Yp)]<2R

(8)

條件4:

Dis[(Xk,Yk),(minxp,minyp)]<2R
Dis[(Xk,Yk),(minxp,maxyp)]<2R

(9)

條件5:

Dis[(Xk,Yk),(maxxp,maxyp)]<2R
Dis[(Xk,Yk),(maxxp,minyp)]<2R

(10)

當(dāng)上述條件1～5同時滿足時,將兩個簇聚類為一個簇。以二次聚類中心為監(jiān)測站站址,可以實現(xiàn)對發(fā)射站目標(biāo)的全覆蓋監(jiān)測。

二次聚類結(jié)果可能出現(xiàn)監(jiān)測目標(biāo)集合重復(fù)或包含的情況,可根據(jù)需要設(shè)置重復(fù)率約束條件,并對存在空間點(diǎn)集重合包含關(guān)系的簇進(jìn)行合并。

3 試驗仿真

選取文獻(xiàn)[11]中的實驗數(shù)據(jù)進(jìn)行仿真試驗,參數(shù)設(shè)置如下:

覆蓋范圍:(x,y)∈(0≤x≤127,0≤y≤127);

發(fā)射站坐標(biāo):(1,10),(25,106),(10,45),(78,83),(65,44),(111,90),(78,23),(96,39),(77,102),(36,43)共10個發(fā)射站;

監(jiān)測站覆蓋半徑:25。

圖2 文獻(xiàn)[11]中的結(jié)果

文獻(xiàn)[11]采用遺傳編程算法進(jìn)行優(yōu)化部署,條件是用最少的監(jiān)測站實現(xiàn)針對發(fā)射站90%以上的覆蓋率,即用最少的監(jiān)測站覆蓋9個或者9個以上發(fā)射站。通過二進(jìn)制編碼、選擇復(fù)制、交換和變異等操作,循環(huán)若干次后得到最佳監(jiān)測站坐標(biāo)列表。其仿真結(jié)果顯示,循環(huán)21次后得到的最佳方案中監(jiān)測站數(shù)目為6個,如圖1[11],監(jiān)測目標(biāo)覆蓋率為90%,重復(fù)率為10%。然而,通過對此例的進(jìn)一步仿真實驗發(fā)現(xiàn),采用遺傳算法的優(yōu)化部署結(jié)果與染色體數(shù)目和循環(huán)次數(shù)有較大關(guān)系,且單純以覆蓋率作為指標(biāo)容易出現(xiàn)重復(fù)率過大的問題,如果要獲得較為優(yōu)化的方案,需要增加染色體數(shù)目和循環(huán)次數(shù)。比如,在本例中,通過增加隨機(jī)染色體數(shù)目和循環(huán)次數(shù),并設(shè)置重復(fù)率約束條件,可以進(jìn)一步得到更少監(jiān)測站、更高覆蓋率的更優(yōu)化部署,圖2中所示的最佳監(jiān)測站數(shù)目為4個,監(jiān)測目標(biāo)覆蓋率為100%,重復(fù)率為0。但是,增加隨機(jī)染色體數(shù)目和循環(huán)次數(shù)會極大地增加算法運(yùn)算時間,限制了這種方法的實用性和可行性。圖1和圖2中“+”為監(jiān)測站部署位置,“·”為發(fā)射站站址,圓周范圍為監(jiān)測站可覆蓋監(jiān)測的范圍。

以監(jiān)測目標(biāo)全覆蓋(發(fā)射站覆蓋率為100%)為條件,利用本文方法進(jìn)行監(jiān)測站優(yōu)化部署的步驟如下:

①對發(fā)射站進(jìn)行一次空間聚類,得到聚類結(jié)果,如圖3,圖中“·”表示發(fā)射站位置,圓周范圍為以一次聚類中心為圓心、監(jiān)測距離R為半徑的監(jiān)測范圍,此時的監(jiān)測目標(biāo)覆蓋率為100%,但是監(jiān)測目標(biāo)重復(fù)率為10%,監(jiān)測站數(shù)目為8個,且監(jiān)測站的監(jiān)測區(qū)域有較多重疊,存在監(jiān)測站冗余;

圖3 增加循環(huán)次數(shù)和重復(fù)率約束條件得到的結(jié)果

②對步驟①的結(jié)果進(jìn)行二次聚類,當(dāng)兩個簇同時滿足二次聚類約束條件1～5時,將這兩個簇二次聚類為一個簇,結(jié)果如圖4,圖中”+”為二次聚類中心,圓周為以二次聚類中心為圓心、監(jiān)測距離R為半徑的圓,此時的監(jiān)測目標(biāo)覆蓋率為100%,重復(fù)率為0,監(jiān)測站數(shù)目為4個;

圖4 一次聚類結(jié)果

圖5 二次聚類結(jié)果

③對存在空間點(diǎn)集重合或包含關(guān)系的簇進(jìn)行合并。

為了驗證算法的有效性和適用性,進(jìn)一步增加發(fā)射站點(diǎn)數(shù),進(jìn)行監(jiān)測站部署方案優(yōu)化。增加發(fā)射站坐標(biāo)分別為:(50,80),(105,72),(44,66),(8,60),(88,10),優(yōu)化部署結(jié)果如圖5所示。

圖6 增加發(fā)射站點(diǎn)后的優(yōu)化部署結(jié)果

4 結(jié)論

對無線電監(jiān)測傳感器網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行部署優(yōu)化可以有效提高監(jiān)測效率?；诒O(jiān)測傳感器網(wǎng)絡(luò)部署效率指標(biāo)評估和空間二次聚類方法的監(jiān)測站部署優(yōu)化算法,綜合考慮了監(jiān)測站數(shù)量和監(jiān)測覆蓋率、重復(fù)率等相關(guān)指標(biāo),通過約束條件的設(shè)置,兼顧監(jiān)測覆蓋效果和部署效率,與遺傳算法相比,運(yùn)算量大大降低,且用更少數(shù)量的監(jiān)測站和更小的監(jiān)測重復(fù)率實現(xiàn)了更大的監(jiān)測覆蓋率,即獲得的部署方案效率更高、更優(yōu)化。