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

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

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

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

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

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

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

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

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

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

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

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

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

14、意輸入文件的具體物理意義：第1行為基站個數N，第2行為終端個數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 關于TOA數據的說明在實際場景中，受帶寬、信噪比、時鐘同步以及NLOS傳播環境的影響，TOA測量會產生不同的誤差。給定的TOA數據也不例外。由于時鐘不同步問題引起的誤差在200ns以內，由于NLOS導致的時延最高可能超過400ns。4.2.2 關于無線電

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

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

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