【導(dǎo)讀】間差、到達(dá)方向的測量和估計(jì)，來實(shí)現(xiàn)移動(dòng)用戶的定位。文對(duì)無線通信網(wǎng)絡(luò)中基于TDOA的無線定位技術(shù)進(jìn)行了研究。本文分析了國內(nèi)外相關(guān)研究現(xiàn)狀，給出了移動(dòng)臺(tái)定位的幾種基本方法，法、遺傳算法和差分演進(jìn)算法，并對(duì)其進(jìn)行了計(jì)算機(jī)仿真。果表明，三種算法各有優(yōu)缺點(diǎn)：Chan算法定位精度較低但運(yùn)算速度很快，GA算法和DE算法定位精度高但收斂時(shí)間較長。Chan-GA算法、Chan-DE算法和Chan-IDE算法。并在相同的仿真環(huán)境下進(jìn)。行比較，仿真結(jié)果表明，在保證種群數(shù)量的情況下，所提的算法性能穩(wěn)定，課題研究的目的和意義·········&#1

　　

【正文】 pz 的協(xié)方差矩陣 Φ 為： 110111T01T211)()c o v (41)c o v (????????????????????????BGBGBQBGBGBBzBzΦaaaaapc () 式中， ?????? ????? )(0 0)( 1010 YyXxB 4 個(gè)以上基站的 Chan 算法可歸納為：遠(yuǎn)距離 MS 的位置可通過式 ()、()和式 ()進(jìn)行估計(jì)，定位估計(jì)的協(xié)方差矩陣可由式 ()計(jì)算；定位 近距離 MS 時(shí)，由式 ()可計(jì)算出一近似 B 矩陣，再分別采用式 ()、 ()和式 ()計(jì)算出定位結(jié)果，定位估計(jì)的協(xié)方差矩陣可由式 ()計(jì)算。在TDOA 距離差誤差較小時(shí)該算法給出了能達(dá)到 CRLB 的表達(dá)式解，但也需要有關(guān) MS 位置的先驗(yàn)信息以解決式 ()中存在的不確定性。在文獻(xiàn)中該算法的推導(dǎo)過程都是基于 TDOA誤差較小且為理想的零均值高斯隨機(jī)變量這個(gè)前提，因此可以預(yù)計(jì)，對(duì)于實(shí)際信道環(huán)境中誤差較大的 TDOA 測量值，該算法的性能將受到較大影響。 定位準(zhǔn)確率的評(píng)價(jià)指標(biāo) 雙曲線定位的準(zhǔn)確率需要一系列指標(biāo)進(jìn)行評(píng)價(jià)，文中將定位解的平均估哈爾濱工程大學(xué)本科生畢業(yè)論文 21 計(jì)坐標(biāo) (MV)和均方誤差 (MSE)作為算法性能的評(píng)價(jià)標(biāo)準(zhǔn)。 在二維定位估計(jì)中計(jì)算 MV 和 MSE 的方法為： )],[(E yxMV ? () ])?()?[(E 22 yyxxM S E ???? () 其中， ),( yx 為 MS 實(shí)際位置， )?,?( yx 為 MS 估計(jì)位置。 本章小結(jié) 本章主要給出了 TDOA 定位的數(shù)學(xué)模型，研究了基于 TDOA 的常見算法—— Chan 算法。綜合分析可見， Chan 算法為非遞歸算法，其解為明確的解析表達(dá)式，但需要一些有關(guān) MS 位置的先驗(yàn)信息以解決其解存在的模糊性。在蜂窩網(wǎng)絡(luò)信道環(huán)境中， Chan 算法是定位性能很好的一種算法。因此， Chan算法是一種比較適合在蜂窩網(wǎng)絡(luò)環(huán)境中對(duì) MS 進(jìn)行定位估計(jì)的算法 [2]。在本章最后給出了定位準(zhǔn)確率的評(píng)價(jià)指標(biāo)：平均估計(jì)坐標(biāo)和均方誤差。平均估計(jì)坐標(biāo)與實(shí)際位置越接 近，均方誤差越小，定位準(zhǔn)確率越高，性能越好。 哈爾濱工程大學(xué)本科生畢業(yè)論文 22 第 4章 遺傳算法在 TDOA定位中的應(yīng)用 本章根據(jù)遺傳算法的基本優(yōu)化原理，研究了適用于 TDOA 定位的改進(jìn)的遺傳算法 [8]。該算法首先根據(jù)移動(dòng)臺(tái)所在服務(wù)區(qū)來確定移動(dòng)臺(tái)的坐標(biāo)范圍，然后采用似然函數(shù)的倒數(shù)作為個(gè)體適應(yīng)度值來選取優(yōu)良個(gè)體并進(jìn)行遺傳操作，在服務(wù)臺(tái)所確定的坐標(biāo)范圍內(nèi)搜索移動(dòng)臺(tái)位置。仿真結(jié)果說明，算法的性能穩(wěn)定，能得到較高精度的解。 遺傳算法簡介 遺傳算法的基本原理 遺傳算法 (Geic Algorithm， GA)是建立在自然選擇和群 體遺傳學(xué)基礎(chǔ)上的搜索方法，是由美國 Michigan 大學(xué)的 Holland 教授首先提出并發(fā)展起來的 [9]。 遺傳算法是從代表問題可能潛在解集的一個(gè)種群開始的，一個(gè)種群則由經(jīng)過基因編碼的一定數(shù)目的個(gè)體組成。每個(gè)個(gè)體實(shí)際上是染色體帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn) (即基因型 )是某種基因組合，它決定了個(gè)體形狀的外部表現(xiàn)。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射，即編碼工作。初始種群產(chǎn)生之后，按照“適者生存”和“優(yōu)勝劣汰”的原理，逐代演化產(chǎn)生出越來越好的近似解。在每一代中，根 據(jù)問題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合、交叉和變異，產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化的一樣，后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼，可以作為問題近似最優(yōu)解 [10]。 遺傳算法是自然遺傳學(xué)和計(jì)算機(jī)科學(xué)相互結(jié)合滲透的產(chǎn)物，借用了許多自然進(jìn)化的基礎(chǔ)術(shù)語。下面我們對(duì)一些術(shù)語進(jìn)行簡單的介紹： (1) 群體和個(gè)體 哈爾濱工程大學(xué)本科生畢業(yè)論文 23 遺傳算法處理的是染色體，或者叫基因型個(gè)體，通常以一維串結(jié)構(gòu)數(shù)據(jù)來表示；一定數(shù)量的個(gè)體組成群體。 (2) 適應(yīng)度函數(shù) 各個(gè)個(gè)體對(duì)環(huán)境 的適應(yīng)程度叫做適應(yīng)度。遺傳算法對(duì)適應(yīng)度函數(shù)并不要求可導(dǎo)等條件，只要求適應(yīng)度函數(shù)是非負(fù)函數(shù)，同時(shí)要求把待解優(yōu)化問題表達(dá)為最大化問題，即目標(biāo)函數(shù)的優(yōu)化方向?yàn)檫m應(yīng)度函數(shù)的增大方向，所以有廣泛的應(yīng)用。在解決 TDOA 問題中，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。 (3) 編碼和解碼 遺傳算法必須包含兩個(gè)必須的數(shù)據(jù)轉(zhuǎn)換操作，即把搜索空間中的參數(shù)或解轉(zhuǎn)換成遺傳空間中的染色體或個(gè)體，稱為編碼；反之，稱之為解碼。 (4) 遺傳操作 遺傳操作中包括三種主要操作，分別是選擇、交叉和變異操作 (詳細(xì)在 節(jié)介紹 )。 遺傳算法的 特點(diǎn) 遺傳算法的特點(diǎn) [11]可以從它和傳統(tǒng)搜索方法對(duì)比可以充分體現(xiàn)出來： 遺傳算法不是直接作用在參變量集上，而是利用參變量集的某種編碼 遺傳算法的處理對(duì)象不是參數(shù)本身，而是對(duì)參數(shù)集進(jìn)行了編碼的個(gè)體。此編碼操作，使遺傳算法可直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作。這一特點(diǎn)，使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。 遺傳算法不是從單個(gè)點(diǎn)，而是從多個(gè)點(diǎn)的群體開始搜索 傳統(tǒng)方法都是單點(diǎn)搜索，從一點(diǎn)移到另一點(diǎn)。這種點(diǎn)對(duì)點(diǎn)的搜索常常會(huì)陷入局部最優(yōu)解；而遺傳算法采用同時(shí)處理多個(gè)點(diǎn)的方法，對(duì)多個(gè)解進(jìn)行評(píng)估，具有全局搜索性能，同時(shí)也易于并行化。 遺 傳算法利用適應(yīng)值信息，無需導(dǎo)數(shù)和其他輔助信息 遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。對(duì)適應(yīng)度函數(shù)的唯一要求是，對(duì)于輸入可計(jì)算出正的函數(shù)值。這使哈爾濱工程大學(xué)本科生畢業(yè)論文 24 得該算法的應(yīng)用范圍大大擴(kuò)展。 遺傳算法利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則 遺傳算法采用概率作為一種工具來引導(dǎo)其搜索過程朝著搜索空間的更優(yōu)化的解移動(dòng)，因此具有明確的搜索方向。 上述特點(diǎn)，表明遺傳算法適于解決維數(shù)很高，總體很大的復(fù)雜的非線性問題。這使遺傳算法具有以下優(yōu)點(diǎn)： (1) 應(yīng)用廣泛性：易于寫出通用算法，求解不同優(yōu)化問題； (2) 非線 性性：其他多數(shù)算法都需與可導(dǎo)、線性、凸性等性質(zhì)相聯(lián)系，遺傳算法只需適應(yīng)度函數(shù)值非負(fù)，適合具有高度非線性問題的尋優(yōu)； (3) 易于修改性：遺傳算法只需少量改變算法，即可適用于不同問題； (4) 易于并行實(shí)現(xiàn)。 遺傳算法的基本流程圖和主要步驟 標(biāo)準(zhǔn)遺傳算法 (SGA)的基本流程 [7]如圖 所示： 哈爾濱工程大學(xué)本科生畢業(yè)論文 25 產(chǎn) 生 初 始 種 群計(jì) 算 適 應(yīng) 度 值是 否 滿 足優(yōu) 化 原 則選 擇交 叉變 異輸 出 最 佳 個(gè) 體結(jié) 束開 始是否 圖 遺傳算法的流程圖 算法主要步驟如下： 第 1 步：設(shè)置運(yùn)行參數(shù)：群體大小 N 、終止進(jìn)化代數(shù) T 、交叉概率 cP 、變異概率 mP ； 第 2 步：隨機(jī)產(chǎn)生初始群體； 第 3 步：計(jì)算個(gè)體的適應(yīng)度，并判斷是否符合優(yōu)化準(zhǔn)則。若符合，輸出最佳個(gè)體及其代表的最優(yōu)解，并結(jié)束計(jì)算；否則轉(zhuǎn)向第 3 步； 第 4 步：依據(jù)適應(yīng)度選擇個(gè)體，適應(yīng)度高的個(gè)體被選中的概率高，適應(yīng)度低的個(gè)體可能被淘汰； 第 5 步：按照一定的交叉概率和交叉方法，生成新的個(gè)體； 第 6 步：按照一定的變異概率和變異方法， 生成新的個(gè)體； 第 7 步：由交叉和變異產(chǎn)生新一代的種群，返回到第 3 步。 哈爾濱工程大學(xué)本科生畢業(yè)論文 26 遺傳算法的基本操作 編碼與解碼 應(yīng)用遺傳算法解決問題的關(guān)鍵步驟就是編碼。由問題空間向遺傳算法空間的映射稱為編碼，由遺傳算法空間向問題空間的映射稱為解碼 [10]。由于遺傳算法并不直接作用于待求變量本身，而是先將待求問題的變量進(jìn)行編碼，表示成適于遺傳算法求解的碼串形式，然后進(jìn)行遺傳操作，故相應(yīng)地應(yīng)該有解碼過程，也就是將編碼變回?cái)?shù)字變量，從而找到所求問題的最優(yōu)解。 編碼的方法有很多，比如有二進(jìn)制編碼法和浮點(diǎn)數(shù)編碼法。由于二進(jìn)制數(shù) 占用的位數(shù)較多，解碼時(shí)延增加，故本文中采用浮點(diǎn)數(shù)編碼。 種群初始化 在應(yīng)用遺傳算法之前，要對(duì)一定群體規(guī)模的個(gè)體進(jìn)行初始化，這些經(jīng)過初始化后的個(gè)體將作為遺傳進(jìn)化的祖先 (下一代的父代 )。作為祖先的初始群體，這些給定數(shù)量的個(gè)體是通過隨機(jī)方法生成的，以保證搜索空間中的每個(gè)可能解在初始群體中都有相同的出現(xiàn)機(jī)會(huì)。 個(gè)體適應(yīng)度的評(píng)價(jià) [5] 在遺傳算法中評(píng)價(jià)值被稱為個(gè)體適應(yīng)度值，定義一個(gè)適應(yīng)性函數(shù)是遺傳算法中評(píng)價(jià)個(gè)體優(yōu)劣的手段，評(píng)價(jià)的標(biāo)準(zhǔn)因所研究問題的不同而異，它通常由目標(biāo)函數(shù)轉(zhuǎn)化而來，并要求與目標(biāo)函數(shù)有相同的極值點(diǎn)和可行 解域，且值域非負(fù)，這樣就可以將目標(biāo)函數(shù)的極小值問題，轉(zhuǎn)化為求適應(yīng)函數(shù)的極大值問題，便于遺傳操作。本文將目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù) [12]。在評(píng)價(jià)中，取其倒數(shù)是因?yàn)榱?xí)慣上按從大到小的順序排列適應(yīng)值，計(jì)算出群體中每個(gè)解相應(yīng)的適應(yīng)度函數(shù)，適應(yīng)度函數(shù)值越大，表示該個(gè)體適應(yīng)度越高，亦即該個(gè)體的質(zhì)量較好，更適應(yīng)于目標(biāo)函數(shù)所定義的生存環(huán)境，因此也應(yīng)該較其它個(gè)體有更多的機(jī)會(huì)參與遺傳操作，并將其優(yōu)良性能遺傳給更多的子代，適應(yīng)函數(shù)為群體進(jìn)化的選擇提供了依據(jù)。 選擇 哈爾濱工程大學(xué)本科生畢業(yè)論文 27 選擇運(yùn)算是從群體中選擇優(yōu)良的個(gè)體、淘汰劣質(zhì)個(gè)體的操作，用于模 擬生物界去劣存優(yōu)的自然選擇現(xiàn)象。選擇的目的是把優(yōu)異的個(gè)體特性直接遺傳到下一代或通過配對(duì)交叉將其部分優(yōu)良特性遺傳給新的個(gè)體，再遺傳到下一代群體。 選擇方法有輪盤賭選擇法、隨機(jī)遍歷抽樣、錦標(biāo)賽選擇等，其中輪盤賭選擇法較為常用。首先計(jì)算所有個(gè)體的適應(yīng)度值總和和每個(gè)個(gè)體的適應(yīng)度值所占適應(yīng)度值總和的比重。它把種群中所有個(gè)體適應(yīng)度的總和看成一個(gè)輪子的圓周，每個(gè)個(gè)體按其適應(yīng)度值在總和中的比重占據(jù)輪子的一個(gè)扇區(qū)，每次個(gè)體的選擇可以看作輪子的一次隨機(jī)轉(zhuǎn)動(dòng)，它轉(zhuǎn)到哪個(gè)扇區(qū)停下來，那個(gè)扇區(qū)對(duì)應(yīng)的個(gè)體就被選中。比重越大，能參與繁殖 的概率越大，此概率與其個(gè)體適應(yīng)度的大小成正比。即適合于生存環(huán)境的優(yōu)良個(gè)體將有更多的繁殖后代的機(jī)會(huì)，從而使得優(yōu)良特性得以遺傳。選擇是遺傳算法的關(guān)鍵，它體現(xiàn)了自然界中“適者生存”的思想。本文中采用輪盤賭法進(jìn)行個(gè)體的選擇。 交叉 交叉操作利用了來自不同符號(hào)串的基因經(jīng)由交換而混合以產(chǎn)生新符號(hào)串的概念，它是根據(jù)交叉概率在種群中選取兩個(gè)個(gè)體做為父體和母體，再依交叉概率將兩個(gè)個(gè)體中位于交叉位后的符號(hào)串互換，保留交叉位前的各基因位符號(hào)不變，形成兩個(gè)下一代新個(gè)體的遺傳操作 [10]。由此可以看出，適應(yīng)度值大的個(gè)體參與交叉的 機(jī)率大，通過交叉把遺傳信息傳給了子代，使優(yōu)良的性狀更易繼承下去。根據(jù)交叉點(diǎn)的不同，交叉運(yùn)算有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉等多種不同的交叉方法。 變異 為了避免落入局部最優(yōu)，遺傳算法中引入了變異算子，變異是為了避免“近親繁殖”，它可以保持群體的多樣性，以避免局部收斂，同時(shí)還可以恢復(fù)丟失的或?qū)ふ椅凑业降膬?yōu)良信息，在當(dāng)前解的附近找到更好的解 [10]。變異操作可使適應(yīng)度值小的個(gè)體或群體素質(zhì)趨于一致的個(gè)體發(fā)生變化，同時(shí)防止適應(yīng)值大的個(gè)體變異，從而使每一代保持新鮮個(gè)體，避免進(jìn)化停滯，過早收斂，哈爾濱工程大學(xué)本科生畢業(yè)論文 28 確保群體能繼續(xù)優(yōu)化。 遺傳算法在 TDOA定位中的實(shí)現(xiàn) 遺傳算法在開發(fā)最好解和探求搜索空間兩方面同時(shí)努力，即在探究搜索空間的同時(shí)，維持一個(gè)潛在解的群體。這一特性對(duì)于尋找全局最優(yōu)點(diǎn)是非常有利的。下面我們將遺傳算法用于 TDOA 定位中。 TDOA 雙曲線定位模型 如圖 所示，假設(shè) M 個(gè)接收機(jī)隨機(jī)分布在二維平面上 ， ),( yx 為移動(dòng)臺(tái)MS 的待估計(jì)位置， ),Y(X ii 為第 i 個(gè)基 站 BS 的已知位置。 MS 到基站 i 的距離為 iR ，令 01,iR 表示 MS 與基站 i )1(?i 和基站 1(服務(wù)基站 )的實(shí)際距離差，測量值記作 1,iR ，則 MiRRRcdR iiiiii ,2,1,11,0 1,1,1, ???????? () 式中： c 為電波傳播速度； 1,id 是 TDOA 測量值； 1,in 是測量 TDOA 時(shí)引入的噪聲， 為方便起見 ， 可認(rèn)為是 獨(dú)立同分布的方差為 2? 的高斯白噪聲。 又因?yàn)? 22 )()( yYxXR iii ???? () ： 源 點(diǎn) 位 置 ， 坐 標(biāo) （ x ， y ）xy6 k m 圖 基站與源點(diǎn)位置示意圖 哈爾濱工程大學(xué)本科生畢業(yè)論文 29 所以有 MiyYxXyYxXR iiii ,3,2,)()()()( 1,2121221, ??????????? () 記作 T1)1(1,1,31,2T1)1(1111T1)1(32T1)1(1,1,31,2],[],[],[],[?????????????MMMMMMMnnnRRRRRRRRR????nRRR 可得 nnRRR cyYxXyYxXyYxXyYxXyYxXyYxXcMM?????????????????????????????????????????21212221212323212122221)()()()()()()()()()()()(? () 本文考慮 3?M 時(shí)的情況。為了充分利用統(tǒng)計(jì)信息，采用最大似然法估計(jì)源點(diǎn)坐標(biāo) ),( yx 。因?yàn)?1,iR 服從均值為 )( 1RRi ? ， 方差為 2? 的高斯分布 ， 又 因各測量值獨(dú)立 ， 則似然函數(shù) 211211 T112()1 e x p22( ) ( )1 e x p22MiiiMR R R?????????????? ? ??????????????? ? ? ? ? ??????????? ???R R R R R R () 求使似然函數(shù)最大的坐標(biāo)值 ， 相當(dāng)于求 T112( ) ( )( , ) a r g m a x e x p ( )2xy ?????? ? ? ? ? ?????????????R R R R R R () 也就是求 ? ?T11( , ) a r g m i n ( ) ( )xy ??? ? ? ? ? ? ?R R R R R R () 式 ()表明要求解出坐標(biāo)值，必須求非線性函數(shù)的最小值 [8]。用解析法求解式 ()的非線性函數(shù)的最小值是比較困難的?？蓪⑹?()的倒數(shù)用作適應(yīng)度函數(shù)，在這一章和下一章中應(yīng)用，用于評(píng)價(jià)遺傳算法和差分進(jìn)化算法中個(gè)體的適應(yīng)度。 哈爾濱工程大學(xué)本科生畢業(yè)論文 30 改進(jìn)的遺傳算法 的實(shí)現(xiàn) 本節(jié)對(duì)基本遺傳算法進(jìn)行了改進(jìn)，并根據(jù) 節(jié)的數(shù)學(xué)模型給出了具體的實(shí)現(xiàn)方法。 染色體編碼 由于我們解決的定位問題是二維的，并且采用浮點(diǎn)數(shù)編碼，所以我們考慮的染色體由兩個(gè)基因組成。首先根據(jù)移動(dòng)臺(tái)所處服務(wù)基站小區(qū)確定移動(dòng)臺(tái)的坐標(biāo)范圍： ??? ????maxminmaxmin yyy xxx () 式中， minx ， maxx 分別表示基站覆蓋區(qū)域的橫坐標(biāo)范圍的最小值和最大值，miny ， maxy 分別表示基站覆蓋區(qū)域的縱坐標(biāo)范圍的最小值和最大值。 將待優(yōu)化的 x 變量和 y 變量通過式 ()進(jìn)行歸一化處理： ??? ?????? ])[2( ])[1(m i nm a xm i nm i nm a xm i n yyvyy xxvxx () 將 x 和 y 轉(zhuǎn)換為 [0,1]區(qū)間上的實(shí)數(shù) 2,1),( ?iiv ，稱 )(iv 為基因， x ， y 變量對(duì)應(yīng)的基因 )1(v 和 )2(v 一起構(gòu)成該實(shí)數(shù)編碼的染色體，記 T)]2(),1([ vv?v 。 初始化種群 設(shè)群體規(guī)模為 N ，在 [0,1]區(qū)間上生成 N?2 維均勻隨機(jī)數(shù)矩陣 V ，},{ 21 NvvvV ?? ，作為初始群體的父代個(gè)體值。 個(gè)體適應(yīng)度值 根據(jù) 節(jié)的內(nèi)容，本文算法中我們?nèi)∵m應(yīng)度函數(shù) [8]為： i|)()(1)(1T1i zRRRRRRz ???????f () 式中， Ti ]y,x[ ii ?z ，其中 ix 和 iy 為染色體向量 v 所對(duì)應(yīng)的移動(dòng)臺(tái)的