全國(guó)也就數(shù)學(xué)建模競(jìng)賽C題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、信號(hào)測(cè)量的說(shuō)明當(dāng)無(wú)線電波沿直線傳播時(shí)，估計(jì)無(wú)線電波從發(fā)送點(diǎn)到接收點(diǎn)之間真實(shí)傳播時(shí)間，從數(shù)學(xué)形式上，即如下等式中對(duì)于x的估計(jì)問(wèn)題：                                     x=x+    &

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

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