基于室內(nèi)WiFi環(huán)境的用戶自激發(fā)式弱定位方法研究中文摘要

室內(nèi)定位技術(shù)的研究發(fā)展近年來(lái)呈現(xiàn)出“定位更精準(zhǔn)”與“部署更簡(jiǎn)單”的趨勢(shì)。從“定位更精準(zhǔn)”角度進(jìn)行的技術(shù)研究已經(jīng)較為成熟；而從“部署更簡(jiǎn)單”角度進(jìn)行的技術(shù)研究才剛剛起步?，F(xiàn)有室內(nèi)定位技術(shù)往往對(duì)定位精準(zhǔn)度給予了足夠的關(guān)注，然而僅有部分近期的工作研究如何降低系統(tǒng)開(kāi)銷，更鮮有工作能夠系統(tǒng)性地在兩者間進(jìn)行權(quán)衡。在很多現(xiàn)實(shí)生活的應(yīng)用場(chǎng)景，現(xiàn)有室內(nèi)定位系統(tǒng)的部署代價(jià)仍然過(guò)高而難以適用。.本項(xiàng)目以低代價(jià)為目標(biāo)，研究基于室內(nèi)WiFi環(huán)境的用戶自激發(fā)式弱定位方法，以權(quán)衡定位的精準(zhǔn)度與開(kāi)銷。該方法使用室內(nèi)環(huán)境現(xiàn)有的WiFi信號(hào)，無(wú)需部署額外的基礎(chǔ)設(shè)施，只基于少量接收信號(hào)強(qiáng)度（RSS）等普通用戶可輕易獲取的信息，即可完成定位系統(tǒng)部署。本項(xiàng)目擬解決由RSS信息少量高噪導(dǎo)致的維度不匹配問(wèn)題與過(guò)擬合問(wèn)題，并結(jié)合用戶智能手機(jī)集成的傳感器，對(duì)定位結(jié)果進(jìn)行優(yōu)化。該方法可應(yīng)用于如場(chǎng)館導(dǎo)航、商場(chǎng)購(gòu)物、醫(yī)院就診、商務(wù)辦公等場(chǎng)景。

室內(nèi)定位技術(shù)的研究發(fā)展近年來(lái)呈現(xiàn)出“定位更精準(zhǔn)”與“部署更簡(jiǎn)單”的趨勢(shì)。從“定位更精準(zhǔn)”角度進(jìn)行的技術(shù)研究已經(jīng)較為成熟；而從“部署更簡(jiǎn)單”角度進(jìn)行的技術(shù)研究才剛剛起步?，F(xiàn)有室內(nèi)定位技術(shù)往往對(duì)定位精準(zhǔn)度給予了足夠的關(guān)注，然而僅有部分近期的工作研究如何降低系統(tǒng)開(kāi)銷，更鮮有工作能夠系統(tǒng)性地在兩者間進(jìn)行權(quán)衡。在很多現(xiàn)實(shí)生活的應(yīng)用場(chǎng)景，現(xiàn)有室內(nèi)定位系統(tǒng)的部署代價(jià)仍然過(guò)高而難以適用。本項(xiàng)目針對(duì)低代價(jià)的室內(nèi)定位該較新的研究領(lǐng)域中亟需解決的理論和關(guān)鍵技術(shù)問(wèn)題，研究基于WiFi 環(huán)境的用戶自激發(fā)式弱定位方法、與結(jié)合傳感器信息的用戶自激發(fā)式若定位優(yōu)化方法?，F(xiàn)有的室內(nèi)定位指紋技術(shù)，為現(xiàn)有的WLAN基礎(chǔ)設(shè)施提供了增值的本地化服務(wù)，而不需要任何專門(mén)的硬件?；谥讣y定位系統(tǒng)的部署需要對(duì)接收到的信號(hào)強(qiáng)度信息進(jìn)行大量的測(cè)量，以生成位置指紋數(shù)據(jù)庫(kù)。然而，這一要求在大多數(shù)室內(nèi)環(huán)境中很少能得到滿足。在這個(gè)項(xiàng)目中，我們針對(duì)上述普遍存在的問(wèn)題，即當(dāng)收集到的測(cè)量信號(hào)強(qiáng)度信息不足時(shí)，論證了現(xiàn)有的位置指紋方法在處理不足的位置指紋的局限性。本項(xiàng)目研究了一種基于最大似然估計(jì)的接收信號(hào)強(qiáng)度測(cè)量中降低噪聲的新方法，并利用隨機(jī)梯度下降算法計(jì)算位置指紋不足的位置。實(shí)驗(yàn)結(jié)果表明，即使只有少量的RSS測(cè)量數(shù)據(jù)，該方法也能獲得較好的定位性能。特別是當(dāng)每個(gè)位置的觀測(cè)值較少時(shí)，該方法在定位精度上具有明顯的優(yōu)越性?，F(xiàn)有的室內(nèi)導(dǎo)航系統(tǒng)，大部分依賴于足夠的無(wú)線信號(hào)和信號(hào)源。盡管如此，部署這樣一個(gè)系統(tǒng)需要定期進(jìn)行現(xiàn)場(chǎng)調(diào)查，這是一項(xiàng)耗時(shí)和勞動(dòng)密集的工作。為了解決這個(gè)問(wèn)題，在這個(gè)項(xiàng)目中，我們提出了“獨(dú)木舟”（Canoe），一個(gè)考慮購(gòu)物中心場(chǎng)景的室內(nèi)導(dǎo)航系統(tǒng)。在Canoe系統(tǒng)中，我們不假設(shè)任何先驗(yàn)知識(shí)，例如樓層平面圖或店鋪位置、接入點(diǎn)位置或電源設(shè)置、歷史RSS測(cè)量或指紋等，Canoe只要求店主在其店鋪的入口處收集并發(fā)布RSS值，并且可以通過(guò)比較觀察到的RSS值將消費(fèi)者引導(dǎo)到這些店鋪中的任何一個(gè)。消費(fèi)者和商店的位置估計(jì)最大似然估計(jì)。這樣，可以精確計(jì)算目標(biāo)商店相對(duì)于消費(fèi)者當(dāng)前方向的方向，從而確定消費(fèi)者應(yīng)該移動(dòng)的方向。我們使用真實(shí)世界的數(shù)據(jù)集進(jìn)行了廣泛的模擬。我們?cè)谝粋€(gè)真實(shí)的購(gòu)物中心進(jìn)行的實(shí)驗(yàn)表明，如果50%的商店發(fā)布RSS值，Canoe可以在30秒內(nèi)精確地導(dǎo)航消費(fèi)者，錯(cuò)誤率低于9%。 2100433B

隨著VLSI芯片功能越來(lái)越復(fù)雜，大量的時(shí)間消耗在功能驗(yàn)證上，而目前錯(cuò)誤定位仍主要依賴于手工勞動(dòng)，效率低下且易于引入新的錯(cuò)誤，因此錯(cuò)誤自動(dòng)定位方法成為新的研究熱點(diǎn)。但是現(xiàn)有方法存在抽象層次低、運(yùn)算復(fù)雜度高、處理電路規(guī)模有限等問(wèn)題。.針對(duì)這些問(wèn)題，研究基于字級(jí)求解的電路錯(cuò)誤自動(dòng)定位理論與方法；研究基于約束依賴圖的高層HDL程序切片算法，以抽取有效電路；研究基于等價(jià)約簡(jiǎn)與蘊(yùn)含消除的斷言精化方法，以減小斷言規(guī)模；研究融合字級(jí)不可滿足子式與Craig插值的錯(cuò)誤蹤跡優(yōu)化方法，以提高定位精度；研究基于否證分析與增量式求解的錯(cuò)誤敏感向量壓縮方法，以剔除冗余輸入；面向RTL級(jí)和行為級(jí)電路描述，設(shè)計(jì)實(shí)現(xiàn)錯(cuò)誤自動(dòng)定位的原型系統(tǒng)。.本項(xiàng)目的研究成果，能夠顯著提高VLSI芯片驗(yàn)證的效率，有助于縮短設(shè)計(jì)周期，突破制約芯片驗(yàn)證的瓶頸，具有重要理論意義與實(shí)際應(yīng)用價(jià)值。

針對(duì)VLSI芯片的設(shè)計(jì)與驗(yàn)證流程中，診斷與定位錯(cuò)誤依賴于手工勞動(dòng)且效率低下的問(wèn)題，項(xiàng)目重點(diǎn)研究如何自動(dòng)、高效地定位RTL級(jí)和行為級(jí)電路描述中的錯(cuò)誤，通過(guò)設(shè)計(jì)與實(shí)現(xiàn)一系列形式化方法與技術(shù)，大大提高錯(cuò)誤定位的效率與精度，從而加速芯片的設(shè)計(jì)與驗(yàn)證流程。項(xiàng)目的主要研究成果包括： （1）針對(duì)近年來(lái)出現(xiàn)的許多電路錯(cuò)誤定位方法，深入研究與分析了基于位級(jí)與字級(jí)的錯(cuò)誤定位方法的基本原理，并對(duì)各種算法進(jìn)行了評(píng)估與分析；并針對(duì)不可滿足子式能夠顯著提高錯(cuò)誤定位效率與精度進(jìn)行了深入分析。 （2）針對(duì)求解不可滿足子式可以顯著提高電路定位錯(cuò)誤的效率，提出了悖論證明與悖論解析樹(shù)的概念，并提出一種啟發(fā)式局部搜索算法，從布爾公式的悖論證明中求解不可滿足子式?；趯?shí)際測(cè)試集進(jìn)行了實(shí)驗(yàn)對(duì)比，結(jié)果表明該算法優(yōu)于同類最優(yōu)算法。 （3）針對(duì)布爾不可滿足子式能夠幫助自動(dòng)化工具迅速定位電路錯(cuò)誤，提出了求解布爾不可滿足子式的消解悖論算法。它屬于一種非完全算法，對(duì)于業(yè)界常見(jiàn)的3-SAT和2-SAT問(wèn)題非常高效?；陔S機(jī)測(cè)試集進(jìn)行了實(shí)驗(yàn)對(duì)比，結(jié)果表明消解悖論算法優(yōu)于其他同類算法。 （4）隨著硬件設(shè)計(jì)與驗(yàn)證的抽象層次越來(lái)越高，基于一階邏輯的可滿足性模逐漸成為研究熱點(diǎn)。針對(duì)極小可滿足性模的不可滿足子式的求解問(wèn)題，提出了基于深度優(yōu)先搜索與增量式求解的算法。與目前最優(yōu)算法對(duì)比，該算法能夠有效地求解極小不可滿足子式，并且隨著公式的規(guī)模增大，算法更加高效。 （5）高速緩沖存儲(chǔ)器（Cache）的錯(cuò)誤定位是驗(yàn)證領(lǐng)域的研究熱點(diǎn)與難點(diǎn)，對(duì)此提出了一種面向Cache的可綜合偽隨機(jī)驗(yàn)證與錯(cuò)誤定位方法。與業(yè)界常用的方法對(duì)比，該方法的處理速度快約3個(gè)數(shù)量級(jí)，并且能夠精確地定位更多的功能錯(cuò)誤。 （6）謂詞抽象技術(shù)是解決錯(cuò)誤定位中狀態(tài)空間組合爆炸問(wèn)題的重要途徑，而不可滿足子式能夠減少謂詞抽象過(guò)程中精化迭代的次數(shù)。因此將兩種最小不可滿足子式的求解算法進(jìn)行了集成與對(duì)比，并深入分析了不可滿足子式在硬件謂詞抽象中的作用，以及如何加速電路的錯(cuò)誤定位過(guò)程。