全國也就數(shù)學建模競賽C題

1、2016年全國也就數(shù)學建模競賽C題基于無線通信基站的室內(nèi)三維定位問題1 背景介紹隨著無線通信網(wǎng)絡和移動互聯(lián)網(wǎng)的蓬勃發(fā)展，提供基于地理位置信息的服務（Location Based Service，簡稱LBS）已經(jīng)成為最具市場前景和發(fā)展?jié)摿Φ臉I(yè)務之一。從傳統(tǒng)的GPS導航，到大眾點評、微信等基于地理位置的消費信息服務和社交軟件，實現(xiàn)其功能的基礎就是要通過手機、導航儀等終端設備收發(fā)信號，來獲得距離、角度等測量信息，并利用定位算法將這些測量信息轉(zhuǎn)換成坐標信息?；跓o線移動通信網(wǎng)絡的定位是以獲取用戶手持終端（包括手機或者平板等設備）的位置為目標。而達成這一目標的手段是通過測量無線電信號的強度、傳播時間、到

2、達角等物理指標，并將其轉(zhuǎn)化成終端與基站之間的距離、角度等信息，最終利用定位算法將距離、角度等信息轉(zhuǎn)化成終端的坐標信息。雖然商用GPS已經(jīng)隨著智能手機的發(fā)展而得到了廣泛的應用，但是，在諸如室內(nèi)、地下、高樓林立的市區(qū)等諸多場景中，GPS定位性能較差。由于在覆蓋廣度和深度上，基于無線網(wǎng)絡基站的定位系統(tǒng)相比GPS存在優(yōu)勢，因此，越來越得到運營商和新興創(chuàng)業(yè)公司的重視。此外，對于大數(shù)據(jù)感興趣的IT公司，通過統(tǒng)計大規(guī)模匿名用戶的連續(xù)地理位置信息，可以獲得用戶的移動軌跡，以及在相應軌跡上的APP流量使用情況，甚至在特殊位置搜索和關(guān)注的關(guān)鍵詞等信息。因此，諸如Google、百度等搜索引擎公司也開始提供室內(nèi)定位和

3、室內(nèi)地圖導航的服務。這類服務，一方面可以彌補傳統(tǒng)的GPS在室內(nèi)定位性能較差，且不能分辨用戶所在樓層等問題，另一方面，也為商場、博物館等應用場景提供了為用戶提供基于室內(nèi)實時地理位置信息服務的可能。目前從事室內(nèi)定位和導航服務的方法，大多基于室內(nèi)密集分布的WiFi設備與手機之間的通信方式。這類方法存在兩個明顯的劣勢：首先，從技術(shù)上，WiFi設備的覆蓋范圍有限，并且WiFi設備收發(fā)信號所在的頻段容易受到干擾；其次，從業(yè)務模型上看，用戶對于接入陌生WiFi設備的戒備心理，以及WiFi設備的投資如何回收等，都存在較大的商業(yè)模式上的不確定性。與之相對的，使用基于運營商無線通信基站的方式對手機進行定位，則可以

4、規(guī)避上述問題。商用基站的覆蓋范圍、信號質(zhì)量均優(yōu)于WiFi，而且，用戶也期望自己的手持終端能夠隨時保持對基站設備的接入。同時，運營商推進定位服務的盈利模式清晰，在基礎的數(shù)據(jù)服務之外，還可以通過為用戶提供增值服務而促進運營商的業(yè)務發(fā)展?？傊跓o線通信基站的定位技術(shù)有著廣闊的應用前景和巨大的商業(yè)價值。手持終端設備如何基于基站的測量信息，計算或確定終端在三維空間中的位置坐標，也就是三維定位問題，被認為是現(xiàn)代商用通信網(wǎng)絡中對于定位系統(tǒng)真正具有技術(shù)難度的挑戰(zhàn)。而高精度三維定位也預期能為客戶提供更大的價值，在智能倉儲、智能工廠、固定資產(chǎn)追蹤等對于三維坐標信息敏感的垂直行業(yè)，以及傳統(tǒng)運營商感興趣的商場、辦

5、公樓中基于位置信息的室內(nèi)導航、人群流量分析，以及基于精確三維地理位置信息的業(yè)務推送等服務提供基礎性技術(shù)。從技術(shù)角度來看，現(xiàn)代商用通信網(wǎng)絡對于三維定位的需求，是使用盡可能少的基站完成對終端設備的定位、算法收斂速度快、對于干擾和噪聲具有魯棒性等優(yōu)點。相比于GPS等商用衛(wèi)星定位系統(tǒng)，基于通信基站的定位問題，具有如下特殊性：首先，通信基站的目標區(qū)域是GPS等衛(wèi)星定位系統(tǒng)無法實現(xiàn)定位的場景。在高樓林立的城區(qū)，建筑物內(nèi)部、地下停車場等區(qū)域，GPS等系統(tǒng)是無法滿足定位需求的。而這些應用場景基站、終端密集，是基站定位可以實現(xiàn)突破的地方。其次，通信基站所處的電磁信號環(huán)境較之GPS等系統(tǒng)更加復雜。以室內(nèi)環(huán)境為例，

6、無線電信號的傳播過程中會經(jīng)過墻面的多次反射、室內(nèi)物體的折射和吸收等。這些物理因素會導致通信基站測量得到的諸如距離、角度等信息存在噪聲。如何基于這些有噪聲的測量，得到對于位置信息的準確估計，也是通信基站實現(xiàn)對終端定位需要解決的問題?；谕ㄐ呕镜亩ㄎ粏栴}研究，在科研和工業(yè)界都吸引了極高的關(guān)注。一方面，定位問題與統(tǒng)計信號處理、最優(yōu)估計理論、優(yōu)化算法等諸多領(lǐng)域都有密切的聯(lián)系，諸如數(shù)據(jù)擬合、最小二乘估計、半正定規(guī)劃、流形學習等諸多數(shù)學工具都能夠被用于求解上述問題。另一方面，工業(yè)界對于如何高精度地在現(xiàn)有通信設備上完成上述功能也表現(xiàn)出了濃厚的興趣，我國除了業(yè)已廣泛部署商用的北斗導航系統(tǒng)之外，也在積極推進基

7、于室內(nèi)室外融合定位的羲和導航系統(tǒng)。我們相信，基于通信基站的定位系統(tǒng)，將會成為羲和導航系統(tǒng)有力的技術(shù)手段。求解分析基站定位相關(guān)問題的有創(chuàng)新性和可實現(xiàn)性強的算法，都將有可能被快速部署到現(xiàn)代商業(yè)通信網(wǎng)絡中，帶來巨大的社會和經(jīng)濟效益。2 基礎知識2.1 無線電信號的視距（LOS）與非視距（NLOS）傳播無線電信號在大氣中從A點向B點傳播時，如果傳播過程中存在一個沒有遮擋的直達路徑，那么，這種傳播環(huán)境被稱為視距傳播環(huán)境（Line Of Sight propagation，簡稱LOS）。這種傳播環(huán)境如圖 1中的左圖所示。如果在傳播過程中，由于建筑物或樹木的遮擋、反射、折射等物理現(xiàn)象，使得從A點到B點之間存

8、在多條無線電信號的傳播路徑，這種環(huán)境被稱為非視距傳播環(huán)境（Non-Line Of Sight，簡稱NLOS）。需要注意的是，在NLOS傳播環(huán)境中，仍然可能存在著無線電波的直達路徑，只不過相比于LOS傳播環(huán)境，在NLOS環(huán)境下因為遮擋、反射和吸收等損耗，信號強度會在傳播過程中變得較弱。圖 1 LOS徑與非LOS徑示意圖圖片來源2.2 無線電信號的到達時間（TOA）測量當無線電信號在基站與用戶手持終端之間互相傳播時，就可以計算基站與手持終端之間的距離，一種常用的測量方式是記錄無線電信號從手持終端發(fā)出，直到基站接收到信號為止的無線電信號傳播時間，將時間乘以無線電信號的傳播速度，即得到基站與終端之間沿

9、某條路徑的距離。其中，信號在基站與終端之間的傳播時間，被稱為無線電信號的到達時間（Time Of Arrival，簡稱TOA）。圖 2 TOA示意圖準確測量TOA所需的前提條件是基站計時與終端計時所使用的時鐘是同步的。以圖 2為例，當基站與終端在同一個 “時間坐標系”里，真實TOA等于接收時刻t1減去發(fā)送時刻t0。由于電子器件的工藝原因，基站與終端的時鐘可能是不同步的?？梢詫⒔K端與基站想象成分別使用北京時間和倫敦時間，那么TOA就會在信號真實傳播時間上疊加了時區(qū)之差。2.3 影響測量精度的可能因素基站測量得到的時間或者距離信息往往存在誤差，在建模的過程中，工業(yè)上一般會著重考慮如下兩個因素的影響

10、：l 使用基站測量的終端信號時，需要考慮的一個很重要因素就是基站側(cè)接收到的信號干擾比值（SINR），定義為：SINR=有用信號強度干擾信號強度+噪聲信號強度l 室內(nèi)環(huán)境下，由于反射頻繁發(fā)生，會形成無線電波的多徑傳播（multi-path propagation），從而導致雖然距離很近接收到的信號強度卻波動劇烈。3 賽題要求在本題中，需要解決如下四個方面的問題：1， 給定10組LOS或NLOS傳播環(huán)境下從手持終端到基站的TOA測量數(shù)據(jù)和所有基站的三維坐標（對應附錄中編號為case001_input.txt到case010_input.txt的文件），請根據(jù)這些測量數(shù)據(jù)計算出終端的三維坐標。（請給

11、出詳細的建模分析，建模過程中建議考慮測量模型、誤差分析等內(nèi)容。）2， 給定10組TOA測量數(shù)據(jù)和所有基站的三維坐標（對應附錄中編號為case011_input.txt到case020_input.txt的文件），請設計算法，使用盡可能少的基站數(shù)目，實現(xiàn)近似最優(yōu)的三維定位精度。3， 給定5組對處于移動過程中的終端采集到的TOA數(shù)據(jù)（對應附錄中編號為case021_input.txt到case025_input.txt的文件），請設計算法計算出終端的運動軌跡。（此時，編號為case021_input.txt到case025_input.txt的文件中，只記錄一個終端的TOA數(shù)據(jù)，并且是這一個終端在

12、運動軌跡中多個位置上的TOA數(shù)據(jù)。）4， 在前述3問中，都是假設給定區(qū)域內(nèi)終端到每一個基站的距離都是可知的，但事實上，基站的通信半徑是有限的，因此，只有在基站通信半徑覆蓋范圍內(nèi)的終端才有可能測到自身到基站的距離。而一個終端只有獲得它與足夠數(shù)目的基站之間的距離測量值，才能完成定位。假設每個基站的通信半徑為200米（超過范圍雖然有測量數(shù)據(jù)，但無效）。請根據(jù)給定的5組測量信息數(shù)據(jù)集（對應附錄中編號為case026_input.txt到case030_input.txt的文件），設計算法尋找出可以被基站定位的所有終端。進一步，回答如下問題：每一個場景中（對應著case026_input.txt到cas

13、e030_input.txt五個文件中的一個），定義終端的平均“連接度數(shù)”為=所有可以被定位終端到基站之間的連接數(shù)終端數(shù)，請建立模型分析連接度數(shù)與定位精度之間的關(guān)系。4 數(shù)據(jù)集描述4.1 基本數(shù)據(jù)輸入：l 每一個基站的三維（某些場景下會退化為二維，在文件中通過標識位給出）坐標，其中，第j個基站Aj的三維坐標記為(xj,yj,zj)。l 矩陣=TOAui,AjM×N。矩陣中i行j列元素表示標號為i的終端（記為ui）到標號為j的基站（記為Aj）之間的TOA測量值，記為TOAui,Aj。假設網(wǎng)絡中有M個終端，N個基站，則矩陣的維度為M×N。l 輸入文件的格式為txt。l 請?zhí)貏e注

14、意輸入文件的具體物理意義：第1行為基站個數(shù)N，第2行為終端個數(shù)M，第3行為標識位，（2表示二維場景，3表示三維場景），第4到第(N+3)行為基站坐標，第(N+4)行到第(N+M+3)行為TOA矩陣。輸出：M×3維矩陣，第i行表示第i個終端的三維坐標（部分場景下是M×2維矩陣），存放在txt文件中。4.2 補充說明4.2.1 關(guān)于TOA數(shù)據(jù)的說明在實際場景中，受帶寬、信噪比、時鐘同步以及NLOS傳播環(huán)境的影響，TOA測量會產(chǎn)生不同的誤差。給定的TOA數(shù)據(jù)也不例外。由于時鐘不同步問題引起的誤差在200ns以內(nèi)，由于NLOS導致的時延最高可能超過400ns。4.2.2 關(guān)于無線電

15、信號測量的說明當無線電波沿直線傳播時，估計無線電波從發(fā)送點到接收點之間真實傳播時間，從數(shù)學形式上，即如下等式中對于x的估計問題：                                     x=x+    &

16、#160;    (*)(*)式中，x表示真實的傳播時間，表示測量噪聲， x表示對于傳播時間的觀測。這時，測距問題就等價于根據(jù)觀測值x來獲?。ㄔ谀骋粋€指標意義下）盡可能準確的x。而如果無線電波傳播環(huán)境比較復雜時，觀測值可以表示為                             &#

17、160;       x=fx,    (*)此時的觀測量x中包含一些依賴于x以及函數(shù)f的因素。這時需要解決的仍然是如何依據(jù)觀測值x在某個恰當?shù)闹笜艘饬x下估計x的問題。一般而言，場景不同，函數(shù)f不同，算法思想可以相同也可以有所不同，我們的目標就是要能夠在任意的場景下，自適應地選擇與場景匹配的模型預算法，并且根據(jù)測量數(shù)據(jù)迅速對終端進行準確定位。從物理意義上說，根據(jù)式(*)中描述的情況，對于x的估計相對式(*)來說會變得困難，但是數(shù)值解通常是容易得到的。4.2.3 關(guān)于物理常數(shù)的說明無線電信號的傳播速度統(tǒng)一取3×108m/s。4.2.4 關(guān)于輸出格式的說明1， 賽題最終輸出文件格式應命名為output_case_xyz.txt。其中xyz與賽題給定的input case編號一致，比如input case 1的輸出文件格式應為output_case_001.txt。2， 輸出文件中的第i行對應著標號為i的終端的2維或者3