何琦敏,王 堅,敖佳敏，余 航,徐 博，楊海潮

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

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

何琦敏1,2,王 堅1,2,敖佳敏3，余 航1,2,徐 博1,2，楊海潮1,2

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

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

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

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

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

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

1.1 測距定位算法

1.1.1 時間差定位(TDOA)算法

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

c(t0-ti)

(1)

以災區(qū)點的空間位置作為未知量，對式(1)進行一階泰勒級數(shù)展開，TDOA測量可以寫為

(2)

寫成矩陣形式有

y=Bx-f

(3)

(4)

1.1.2 精度評定

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

(5)

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

(6)

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

(7)

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

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

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

dij

(8)

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

(9)

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

DOP

(10)

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

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

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

(11)

式中，m為分區(qū)域的類型數(shù)目；ni為對應的區(qū)中特征點個數(shù)；ki為區(qū)域DOP加權值；num(DOPi>FDOP)表示區(qū)域i中特征點DOP值超越FDOP的個數(shù)；wi為區(qū)域中DOP越值的加權值，即目標函數(shù)越小，個體的適應度越大。

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

2.1 編碼方式

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

圖1 遺傳編碼解析

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

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

2.3 基于Logistic的隨機交叉操作

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

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

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

numb=PmN

(12)

與交叉操作方式類似，在實際操作時，通過產生一個服從(0,1)均勻分布的隨機數(shù)，若該值小于變異概率Pm，則在相應個體的Logistic點位上進行變異操作。

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

對交叉概率和變異概率進行自適應修正，使得變異和交叉操作隨著子代適應度自適應調整[15]，其表達式如下

(13)

(14)

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

2.6 算法流程

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

3 模擬與仿真

假定布設區(qū)域為100 m×100 m×20 m的長方體空間，3類不同的等級定位區(qū)域。定位系統(tǒng)共由4個基站組成，其中1個固定基站、3個可移動基站。3類不同等級定位區(qū)域的高度不同，分別為2.5～7.5 m、7.5～12.5 m、12.5～17.5 m。基站最大感應半徑為200 m，其中固定站坐標為(150，150，20)，3個移動站分布于空間外側。

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

表1 改進的自適應遺傳算法運算結果

圖2 IAGA算法流程

圖3為經(jīng)過算法優(yōu)化之后的組網(wǎng)效果圖，其中“+”形狀圖樣為固定基站，“*”形狀圖樣為移動基站，深灰色區(qū)域為較安全區(qū)域(高度2.5～7.5 m)，黑色區(qū)域為一般定位區(qū)域(高度7.5～12.5 m)，淺灰色區(qū)域為重點定位區(qū)域(高度12.5～17.5 m)。

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

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

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

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

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

4 結 語

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

圖4 改進的自適應遺傳算法的區(qū)域PDOP值分布

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

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

區(qū)域PDOP改進自適應遺傳算法蟻群算法傳統(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)部署的過程中，災害環(huán)境等自然環(huán)境因素不同，對于信號傳輸?shù)姆且暰鄦栴}、信號干擾等因素，本文未考慮，只對其進行了簡化。對于地形復雜、條件煩瑣的情況還需要進一步考慮遺傳模型中的參數(shù)設置、適應度函數(shù)的確定等問題。

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

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

[3] 侯全武，王堅，胡洪，等. 傳感器位置對狹長空間定位精度的影響[J]. 大地測量與地球動力學報，2013，33(1)：117-122.

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

[5] 錢鐿，陸明泉，馮振明.基于TDOA原理的地面定位系統(tǒng)中HDOP的研究[J].電訊技術，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] 邢文訓，謝金星. 現(xiàn)代優(yōu)化算法[M]. 北京: 清華大學出版社，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] 劉大杰，施一民，過靜珺.全球定位系統(tǒng)GPS的原理與數(shù)據(jù)處理[M].上海：同濟大學出版社，2003.

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

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

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

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

[14] 高虎，俞志強. 基于四站時差定位原理的星型布站分析[J]. 軍雷達學院學報，2004，18(3)：22-24.

[15] 于光帥，于憲.一種改進的自適應遺傳算法[J].數(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

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

10.13474/j.cnki.11-2246.2017.0245.

2016-12-19；

2017-02-17

國家重點研發(fā)計劃(2016YFC0803103)

何琦敏(1994—)，男，碩士，主要研究方向為室內外定位。E-mail:1006184846@qq.com

P228

A

0494-0911(2017)08-0007-06