何琦敏,王 堅(jiān),敖佳敏，余 航,徐 博，楊海潮

(1. 中國(guó)礦業(yè)大學(xué)國(guó)土環(huán)境與災(zāi)害監(jiān)測(cè)國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，江蘇 徐州 221116；2. 中國(guó)礦業(yè)大學(xué)環(huán)境與測(cè)繪學(xué)院，江蘇 徐州 221116；3. 華東交通大學(xué)理工學(xué)院經(jīng)濟(jì)管理分院，江西 南昌 330100)

IAGA模型支持下的災(zāi)區(qū)基站組網(wǎng)優(yōu)化

何琦敏1,2,王 堅(jiān)1,2,敖佳敏3，余 航1,2,徐 博1,2，楊海潮1,2

(1. 中國(guó)礦業(yè)大學(xué)國(guó)土環(huán)境與災(zāi)害監(jiān)測(cè)國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，江蘇 徐州 221116；2. 中國(guó)礦業(yè)大學(xué)環(huán)境與測(cè)繪學(xué)院，江蘇 徐州 221116；3. 華東交通大學(xué)理工學(xué)院經(jīng)濟(jì)管理分院，江西 南昌 330100)

根據(jù)礦井、失火辦公大樓等災(zāi)區(qū)自然環(huán)境特征，結(jié)合基站信號(hào)多重覆蓋的特點(diǎn)，提出了一種改進(jìn)自適應(yīng)遺傳算法(IAGA)，對(duì)基站組網(wǎng)部署進(jìn)行優(yōu)化。首先介紹災(zāi)害環(huán)境下的時(shí)間到達(dá)差算法(TDOA)，用精度因子(DOP)刻畫(huà)精度指標(biāo)，提出了基站組網(wǎng)部署原則，以定位綜合性能作為目標(biāo)函數(shù)求解基站坐標(biāo)。仿真試驗(yàn)表明，IAGA模型能夠較好地應(yīng)用于應(yīng)急組網(wǎng)優(yōu)化的部署，該算法基本能夠達(dá)到最優(yōu)解或次優(yōu)解。

改進(jìn)自適應(yīng)遺傳算法；基站組網(wǎng)優(yōu)化；時(shí)間到達(dá)差算法；精度因子；定位綜合性能

近年來(lái)，針對(duì)建筑物倒塌、城鎮(zhèn)火災(zāi)、地震等災(zāi)害場(chǎng)景應(yīng)急定位難題，基于傳統(tǒng)定位精度因子的單因子靜態(tài)基站組網(wǎng)方式已難以兼顧災(zāi)害場(chǎng)景和環(huán)境信息的自組網(wǎng)體系[1]。然而災(zāi)情空間分布情況及不同災(zāi)情程度的發(fā)生位置，是搜救人員實(shí)施任務(wù)的主導(dǎo)環(huán)節(jié)，因此導(dǎo)航定位技術(shù)在災(zāi)害狀況分布圖的制作和救援決策中具有不可替代的作用[2]?；趥鞲衅鞯氖覂?nèi)定位原理與全球定位系統(tǒng)偽距定位原理相似，終端至少需要接收4個(gè)基站傳輸?shù)男盘?hào)才能完成定位[3]。在礦井、失火大樓等災(zāi)害環(huán)境中，由于該方式定位涉及信號(hào)多重覆蓋、區(qū)域信號(hào)的連續(xù)性、信號(hào)延遲等問(wèn)題[4]，基站位置的確定將直接影響區(qū)域內(nèi)的定位效果。因?yàn)槭苌鲜鲆蛩氐挠绊?，基站坐?biāo)確定問(wèn)題屬于優(yōu)化問(wèn)題中的組合優(yōu)化問(wèn)題。當(dāng)前主要組網(wǎng)方式有星型布設(shè)、方形布設(shè)和菱形布設(shè)[5]，但其設(shè)計(jì)方案過(guò)于理想化，沒(méi)有考慮定位區(qū)域的空間特征，在實(shí)際應(yīng)用中難以滿足實(shí)際需求，一般不是最佳布站方案。

曾有學(xué)者提出，將生物學(xué)中的遺傳模型應(yīng)用于雷達(dá)網(wǎng)的優(yōu)化布設(shè)[6]。遺傳算法(genetic algorithm，GA)作為現(xiàn)代智能優(yōu)化算法，最大特點(diǎn)是可以針對(duì)非線性優(yōu)化問(wèn)題快速挑出局部最優(yōu)解[7]。由于GA算法容易發(fā)生過(guò)早收斂現(xiàn)象，算法的最優(yōu)解依賴于初始種群現(xiàn)象較嚴(yán)重，使得算法需經(jīng)過(guò)長(zhǎng)時(shí)間才能得到最優(yōu)解[8]。應(yīng)急組網(wǎng)屬于動(dòng)態(tài)組網(wǎng)，目前還沒(méi)有一套綜合的組網(wǎng)理論。鑒于此，本文提出應(yīng)急組網(wǎng)遵循的基本原則，并結(jié)合IAGA模型將其應(yīng)用到基站組網(wǎng)優(yōu)化部署中，該模型從種群的選取，到遺傳過(guò)程操作中均有改良。試驗(yàn)證明，該算法能夠較大提高組網(wǎng)效率，為實(shí)施決策提供一定的參考價(jià)值。

1 優(yōu)化組網(wǎng)的數(shù)學(xué)模型

1.1 測(cè)距定位算法

1.1.1 時(shí)間差定位(TDOA)算法

假定災(zāi)區(qū)中一點(diǎn)的空間三維坐標(biāo)為(X，Y，Z)，它到第一個(gè)固定基站(X0，Y0，Z0)與移動(dòng)站(Xi，Yi，Zi)的傳播時(shí)間和距離差分別為t0、ti和ΔRi(i=1，2，3)，則有如下關(guān)系方程組成立，以ΔRi作為觀測(cè)值得到觀測(cè)方程

c(t0-ti)

(1)

以災(zāi)區(qū)點(diǎn)的空間位置作為未知量，對(duì)式(1)進(jìn)行一階泰勒級(jí)數(shù)展開(kāi)，TDOA測(cè)量可以寫(xiě)為

(2)

寫(xiě)成矩陣形式有

y=Bx-f

(3)

(4)

1.1.2 精度評(píng)定

(1) 定義平面位置精度因子[3]

(5)

(2) 高程精度因子[3]

(6)

(3) 空間位置精度因子[3]

(7)

1.2 組網(wǎng)部署原則

一個(gè)具體的現(xiàn)場(chǎng)組網(wǎng)部署任務(wù)，事故現(xiàn)場(chǎng)的自然條件(地物、地貌)已經(jīng)確定。如多層式的辦公樓可以將受災(zāi)區(qū)域分為重點(diǎn)定位區(qū)域、一般定位區(qū)域和較安全區(qū)域?；饎?shì)較重、人口密集的危險(xiǎn)樓層可設(shè)置為重點(diǎn)定位區(qū)域；受災(zāi)程度較輕、人口稀少的樓層可設(shè)置為一般定位區(qū)域；暫時(shí)安全、無(wú)人區(qū)的樓層可以設(shè)置為較安全區(qū)域。基站優(yōu)化部署應(yīng)該遵循連續(xù)性、區(qū)域重疊性、可靠性、探測(cè)區(qū)域最大化原則[10]。優(yōu)化部署基站原則量化如下[11]：

(1) 連續(xù)性：終端處于目的基站接發(fā)射信號(hào)的有效半徑內(nèi)，才能保證數(shù)據(jù)的可靠性。假設(shè)每個(gè)基站的通信半徑為Ri，終端位置點(diǎn)j至基站i的距離為dij，則有

dij

(8)

(2) 區(qū)域重疊性：終端只有獲得其與足夠數(shù)目的基站之間的距離測(cè)量值，才能完成定位，實(shí)現(xiàn)應(yīng)急組網(wǎng)的功能，即有

(9)

(3) 可靠性：為了提高終端定位跟蹤進(jìn)度，要求區(qū)域中任一點(diǎn)DOP值小于相應(yīng)閾值，即有

DOP

(10)

式中，DOP可以是HDOP(平面精度因子)、VDOP(高程精度因子)或PDOP(空間位置精度因子)，對(duì)應(yīng)FDOP分別為FHDOP(平面精度因子閾值)、FVDOP(高程精度因子閾值)或FPDOP(空間位置精度因子閾值)。

(4) 探測(cè)區(qū)域最大化：基站組網(wǎng)對(duì)責(zé)任區(qū)的覆蓋范圍也盡可能大，整體覆蓋層數(shù)盡可能多。

覆蓋區(qū)網(wǎng)絡(luò)由N部基站組成，改變基站放置位置，網(wǎng)絡(luò)的性能將會(huì)發(fā)生較大程度的變化，尋求一組合適的基站坐標(biāo)對(duì)網(wǎng)絡(luò)進(jìn)行優(yōu)化，使得在該區(qū)域中加權(quán)DOP值達(dá)到最小，以最差DOP值點(diǎn)位個(gè)數(shù)最少為目標(biāo)，使其達(dá)到定位設(shè)計(jì)要求。目標(biāo)函數(shù)可表示為

(11)

式中，m為分區(qū)域的類(lèi)型數(shù)目；ni為對(duì)應(yīng)的區(qū)中特征點(diǎn)個(gè)數(shù)；ki為區(qū)域DOP加權(quán)值；num(DOPi>FDOP)表示區(qū)域i中特征點(diǎn)DOP值超越FDOP的個(gè)數(shù)；wi為區(qū)域中DOP越值的加權(quán)值，即目標(biāo)函數(shù)越小，個(gè)體的適應(yīng)度越大。

2 改進(jìn)的自適應(yīng)遺傳算法組網(wǎng)優(yōu)化部署

2.1 編碼方式

一般來(lái)說(shuō)，染色體編碼方式有浮點(diǎn)編碼、二進(jìn)制編碼、格雷碼編碼、符號(hào)編碼法[12]。鑒于浮點(diǎn)數(shù)編碼可表示的數(shù)值較大、精度高且便于較大空間的遺傳搜索，可以較好地應(yīng)用于本問(wèn)題，依次將基站的空間坐標(biāo)設(shè)置為染色體，采用浮點(diǎn)編碼方式[13]，各基站的三維坐標(biāo)分別由nx、ny和nz位的十進(jìn)制編碼表示，多基站組成的染色體編碼表示如圖1所示。

圖1 遺傳編碼解析

2.2 用Hamilton優(yōu)化初始種群

初始種群規(guī)模應(yīng)足夠大，以增加取得最優(yōu)解的概率，但規(guī)模過(guò)大易造成搜索范圍過(guò)大，遺傳過(guò)程時(shí)間變長(zhǎng)。文獻(xiàn)[14]提出一種基于星型布站方式實(shí)現(xiàn)三維定位的方法，其基站組網(wǎng)方式可以作為初始種群的預(yù)選值，并結(jié)合Hamilton算法獲得一個(gè)較合適的初始種群。

2.3 基于Logistic的隨機(jī)交叉操作

這里的交叉操作采取“門(mén)當(dāng)戶對(duì)”的形式，即適應(yīng)度接近的父代個(gè)體相互配對(duì)。交叉點(diǎn)位置通過(guò)Logistic序列確定，對(duì)需要配對(duì)的父代進(jìn)行交叉操作。在實(shí)際操作時(shí)，是通過(guò)產(chǎn)生一個(gè)服從(0,1)均勻分布的隨機(jī)數(shù)，如果該值大于交叉概率Pc，則在相應(yīng)個(gè)體的Logistic點(diǎn)位上進(jìn)行交叉配對(duì)。

2.4 基于種群規(guī)模的變異操作

在進(jìn)行交叉過(guò)程之后，從新個(gè)體中選擇變異個(gè)體，變異個(gè)體和個(gè)體基因位置采取隨機(jī)的方式進(jìn)行。變異數(shù)量由群體中的群體個(gè)數(shù)N和變異概率Pm決定，并有

numb=PmN

(12)

與交叉操作方式類(lèi)似，在實(shí)際操作時(shí)，通過(guò)產(chǎn)生一個(gè)服從(0,1)均勻分布的隨機(jī)數(shù)，若該值小于變異概率Pm，則在相應(yīng)個(gè)體的Logistic點(diǎn)位上進(jìn)行變異操作。

2.5 交叉概率和變異概率的自適應(yīng)優(yōu)化

對(duì)交叉概率和變異概率進(jìn)行自適應(yīng)修正，使得變異和交叉操作隨著子代適應(yīng)度自適應(yīng)調(diào)整[15]，其表達(dá)式如下

(13)

(14)

式中，pc0和pm0為常數(shù)，分別表示初始交叉概率和初始變異概率；α和β為區(qū)間[0，1]的常量；fc為交叉?zhèn)€體適應(yīng)度大的個(gè)體適應(yīng)度；fm表示變異個(gè)體的適應(yīng)度；faver表示所有個(gè)體中的平均適應(yīng)度；fmax表示所有個(gè)體中的最大適應(yīng)度。

2.6 算法流程

災(zāi)害優(yōu)化組網(wǎng)布設(shè)的改進(jìn)自適應(yīng)遺傳算法的主要步驟流程如圖2所示。

3 模擬與仿真

假定布設(shè)區(qū)域?yàn)?00 m×100 m×20 m的長(zhǎng)方體空間，3類(lèi)不同的等級(jí)定位區(qū)域。定位系統(tǒng)共由4個(gè)基站組成，其中1個(gè)固定基站、3個(gè)可移動(dòng)基站。3類(lèi)不同等級(jí)定位區(qū)域的高度不同，分別為2.5～7.5 m、7.5～12.5 m、12.5～17.5 m。基站最大感應(yīng)半徑為200 m，其中固定站坐標(biāo)為(150，150，20)，3個(gè)移動(dòng)站分布于空間外側(cè)。

改進(jìn)自適應(yīng)遺傳算法參數(shù)設(shè)置如下：染色體長(zhǎng)度L=30，種群規(guī)模值取N=50，初始交叉概率值pc0為0.95，初始變異系數(shù)值pm0取為0.1，在適應(yīng)度函數(shù)中，F(xiàn)PDOP取為12，區(qū)域DOP加權(quán)值k={1,2,3}，區(qū)域DOP越值的加權(quán)值w={1,2,3}。通過(guò)改進(jìn)自適應(yīng)遺傳算法對(duì)移動(dòng)基站坐標(biāo)進(jìn)行優(yōu)化計(jì)算，運(yùn)算結(jié)果見(jiàn)表1。

表1 改進(jìn)的自適應(yīng)遺傳算法運(yùn)算結(jié)果

圖2 IAGA算法流程

圖3為經(jīng)過(guò)算法優(yōu)化之后的組網(wǎng)效果圖，其中“+”形狀圖樣為固定基站，“*”形狀圖樣為移動(dòng)基站，深灰色區(qū)域?yàn)檩^安全區(qū)域(高度2.5～7.5 m)，黑色區(qū)域?yàn)橐话愣ㄎ粎^(qū)域(高度7.5～12.5 m)，淺灰色區(qū)域?yàn)橹攸c(diǎn)定位區(qū)域(高度12.5～17.5 m)。

同時(shí)，將表1迭代30次結(jié)果與蟻群算法迭代60次及傳統(tǒng)遺傳算法迭代30次得到的結(jié)果進(jìn)行比較。蟻群算法的優(yōu)化結(jié)果為：移動(dòng)基站1位置(48.5，105.8，0.9)，移動(dòng)基站2位置(197.2，234.9，2.0)，移動(dòng)基站3位置(211.2，45.6，0.5)，目標(biāo)函數(shù)值fp為4.703。傳統(tǒng)遺傳算法的優(yōu)化結(jié)果為：移動(dòng)基站1位置(54.4，140.9，1.4)，移動(dòng)基站2位置(159.2，239.9，2.3)，移動(dòng)基站3位置(224，86.8，0.80)，目標(biāo)函數(shù)值fp為5.602。

圖3 基站組網(wǎng)示意圖

分別選取區(qū)域中的高度為5、10和15 m的區(qū)域面作為3類(lèi)不同等級(jí)區(qū)域特征面，經(jīng)過(guò)改進(jìn)的自適應(yīng)遺傳算法迭代30次運(yùn)算得到基站坐標(biāo)，組成的基站網(wǎng)在不同類(lèi)型等級(jí)定位區(qū)域的PDOP值分布如圖4所示。使用蟻群算法和傳統(tǒng)遺傳算法得到的在不同類(lèi)型等級(jí)定位區(qū)域的PDOP值分布，如圖5和圖6所示。

表2為3種算法在3個(gè)特征面上的平均PODP值(aver)、最小PDOP值(min)和最大PDOP值(max)3個(gè)指標(biāo)的比較。

由圖4—圖6和表2可知，改進(jìn)的自適應(yīng)遺傳算法相較于蟻群算法從效率上有較大程度的提升，性能也有所提高。相較于傳統(tǒng)的遺傳算法，由于初始種群的改良、交叉變異的改進(jìn)，使得搜索速率加快，大大節(jié)省了尋求最優(yōu)解的運(yùn)算時(shí)間，提高了應(yīng)急網(wǎng)絡(luò)綜合性能。

4 結(jié) 語(yǔ)

本文提出了一種改進(jìn)的自適應(yīng)遺傳算法，并將其應(yīng)用于應(yīng)急定位組網(wǎng)的基站優(yōu)化部署。根據(jù)應(yīng)急定位的特殊性，結(jié)合基站組網(wǎng)的特點(diǎn)，總結(jié)出優(yōu)化組網(wǎng)的概念、遵循的原則及組網(wǎng)的評(píng)價(jià)指標(biāo)。試驗(yàn)結(jié)果表明，該算法能夠達(dá)到應(yīng)急定位精度的要求，滿足災(zāi)害環(huán)境下的定位要求，符合組網(wǎng)基本原則。為了加快算法收斂速度，提高組網(wǎng)強(qiáng)度，通過(guò)改良圈算法和Logistic混沌序列改良父代種群，以及遺傳操作中的變異與交叉自適應(yīng)調(diào)整，其效果優(yōu)于蟻群算法和傳統(tǒng)遺傳算法。

圖4 改進(jìn)的自適應(yīng)遺傳算法的區(qū)域PDOP值分布

圖5 蟻群算法的區(qū)域PDOP分布

圖6 傳統(tǒng)遺傳算法的區(qū)域PDOP分布

區(qū)域PDOP改進(jìn)自適應(yīng)遺傳算法蟻群算法傳統(tǒng)遺傳算法averminmaxaverminmaxaverminmax5m2.71751.33514.70232.71651.33794.71343.36621.72106.786110m3.38991.32947.63153.39171.33227.55664.15311.71339.174915m5.96401.32369.98025.99091.342610.03116.85291.706016.2577

然而，在組網(wǎng)部署的過(guò)程中，災(zāi)害環(huán)境等自然環(huán)境因素不同，對(duì)于信號(hào)傳輸?shù)姆且暰鄦?wèn)題、信號(hào)干擾等因素，本文未考慮，只對(duì)其進(jìn)行了簡(jiǎn)化。對(duì)于地形復(fù)雜、條件煩瑣的情況還需要進(jìn)一步考慮遺傳模型中的參數(shù)設(shè)置、適應(yīng)度函數(shù)的確定等問(wèn)題。

[1] 蔡紅.基于UWB的定位方法研究[M].北京：北京郵電大學(xué)出版社，2014.

[2] 曲國(guó)勝，賴俊彥，寧寶坤. 衛(wèi)星定位導(dǎo)航系統(tǒng)在地震應(yīng)急救援中的應(yīng)用[J].震災(zāi)防御技術(shù)，2007，2(4)：409-415.

[3] 侯全武，王堅(jiān)，胡洪，等. 傳感器位置對(duì)狹長(zhǎng)空間定位精度的影響[J]. 大地測(cè)量與地球動(dòng)力學(xué)報(bào)，2013，33(1)：117-122.

[4] 景博.智能網(wǎng)絡(luò)傳感器與無(wú)線傳感器網(wǎng)絡(luò)[M].北京：國(guó)防工業(yè)出版社，2011.

[5] 錢(qián)鐿，陸明泉，馮振明.基于TDOA原理的地面定位系統(tǒng)中HDOP的研究[J].電訊技術(shù)，2005(4):135-138.

[6] YU H F.Designing an Accelerated Degradation Experiment with a Reciprocal Weibull Degradation Rate[J].Journal of Statistical Planning and Inference，2006，136(1): 282-297．

[7] 邢文訓(xùn)，謝金星. 現(xiàn)代優(yōu)化算法[M]. 北京: 清華大學(xué)出版社，1999.

[8] NELSON W B.Graphical Analysis of Accelerated Test with a Mix of Failure Modes[J].IEEE Transactions on Reliability，1975， 23(3): 230-237．

[9] 劉大杰，施一民，過(guò)靜珺.全球定位系統(tǒng)GPS的原理與數(shù)據(jù)處理[M].上海：同濟(jì)大學(xué)出版社，2003.

[10] 張遠(yuǎn)，方青，曲成華. 基于遺傳算法的組網(wǎng)雷達(dá)優(yōu)化部署[J].雷達(dá)科學(xué)與技術(shù)，2014，12(1)：76-80.

[11] 陳亮，鄒鵬，郝利云，等.基于改進(jìn)蜂群算法的雷達(dá)組網(wǎng)優(yōu)化布站研究[C]∥Proceeding of Asia-Pacific Youth Conference on Communication.[S.l.]：[s.n.]，2011.

[12] 曹博，劉文評(píng)，李承尚，等.自適應(yīng)遺傳算法在ADS_S優(yōu)化布站中的應(yīng)用[J].電光與控制，2015，22(6)：81-85.

[13] 楊仕明，柯炳清，薛正輝. 基于遺傳算法的區(qū)域雷達(dá)網(wǎng)優(yōu)化布站方法[J]. 北京理工大學(xué)學(xué)報(bào)，2005，25(6)：534-537.

[14] 高虎，俞志強(qiáng). 基于四站時(shí)差定位原理的星型布站分析[J]. 軍雷達(dá)學(xué)院學(xué)報(bào)，2004，18(3)：22-24.

[15] 于光帥，于憲.一種改進(jìn)的自適應(yīng)遺傳算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí).2015,45(19)：259-264.

Optimization of Disaster Base Station Network Based on IAGA Model

HE Qimin1,2,WANG Jian1,2,AO Jiamin3,YU Hang1,2,XU Bo1,2，YANG Haichao1,2

(1. NASG Key Laboratory of Land Environment and Disaster Monitoring, CUMT, Xuzhou 221116, China; 2. School of Environment and Spatial Mapping, CUMT, Xuzhou 221116, China; 3. Economic Management Branch, ECJTUIT, Nanchang 330100, China)

According to the natural environment characteristics of the mine, office buildings and other disaster areas, combined with the characteristics of multiple signal coverage, an improved adaptive genetic algorithm is proposed to optimize the deployment of base station network. Firstly, the time difference of arrival algorithm in disaster environment is introduced, using DOP to evaluate the positioning accuracy and put forward the principle of network deployment. The base station coordinates are solved by using the integrated performance as the objective function. The simulation results show that the IAGA model can be applied to the optimization of emergency network, and the algorithm can achieve the optimal or suboptimal solution.

improved adaptive genetic algorithm；optimization of base station network；time difference of arrival algorithm；DOP；positioning comprehensive performance

何琦敏,王堅(jiān),敖佳敏,等.IAGA模型支持下的災(zāi)區(qū)基站組網(wǎng)優(yōu)化[J].測(cè)繪通報(bào)，2017(8)：7-12.

10.13474/j.cnki.11-2246.2017.0245.

2016-12-19；

2017-02-17

國(guó)家重點(diǎn)研發(fā)計(jì)劃(2016YFC0803103)

何琦敏(1994—)，男，碩士，主要研究方向?yàn)槭覂?nèi)外定位。E-mail:1006184846@qq.com

P228

A

0494-0911(2017)08-0007-06