徐 英,周尚武,丁 鋒

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

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

(3)

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

(4)

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

無(wú)線電監(jiān)測(cè)站部署優(yōu)化的根本思想是求出一組最優(yōu)的監(jiān)測(cè)站站址分布方案,用最小的成本(即最少的監(jiān)測(cè)站)來(lái)實(shí)現(xiàn)設(shè)定的協(xié)同監(jiān)測(cè)覆蓋率,達(dá)成監(jiān)測(cè)站的最優(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)測(cè)站在各個(gè)方向的監(jiān)測(cè)距離相同,取監(jiān)測(cè)距離R作為閾值。當(dāng)若干個(gè)空間要素的空間距離接近,且分布在同一個(gè)半徑為R的圓內(nèi)時(shí),可劃分為同一類簇。取簇內(nèi)所有空間要素的外接矩形的中心作為圓心,獲得一次聚類中心。

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

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

條件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同時(shí)滿足時(shí),將兩個(gè)簇聚類為一個(gè)簇。以二次聚類中心為監(jiān)測(cè)站站址,可以實(shí)現(xiàn)對(duì)發(fā)射站目標(biāo)的全覆蓋監(jiān)測(cè)。

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

3 試驗(yàn)仿真

選取文獻(xiàn)[11]中的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行仿真試驗(yà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個(gè)發(fā)射站;

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

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

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

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

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

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

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

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

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

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

為了驗(yàn)證算法的有效性和適用性,進(jìn)一步增加發(fā)射站點(diǎn)數(shù),進(jìn)行監(jiān)測(cè)站部署方案優(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é)論

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