1、計算機科學2007V0134No6 無線局域網(wǎng)中基于信號強度的室內定位*) 張明華張申生曹健 (上海交通大學計算機科學與工程系 上海200240) 摘要確定用戶的位置信息有利于向用戶提供方便高效的服務，基于接收信號強度的無線局域網(wǎng)室內定位是定位 領域的一個新的研究熱點。研究的難點在如何克服隨機因素對信號的干擾，使定位方法具有健壯性、適應性。本文基 于IEEE 8021lbg協(xié)議的無線局域網(wǎng)環(huán)境下定位問題的難點，分析了如何評價定位算法的性能問題，介紹目前定位方法的基本原理、優(yōu)缺點及其分類，詳細綜述利用接收信號強度的室內定位算法，最后指出未來定位算法研究的幾個 方向。 關鍵詞IEEE 80211，

2、無線局域網(wǎng)，室內定位，接收信號強度 Received-Signal-Strength-Based Indoor Location in Wireless LANs ZHANG Ming-Hua ZHANG Shen-Sheng CAO Jian (Department of Computer ScienceEngineering。Shanghai Jiao Tong University，Shanghai 200240) Abstract Locating userS physical position iS crucial of providing convenient and eftici

3、ent services for the useL Re- ceived-signalstrength based indoor location in WLAN iS a hot research topic in the field of 10cation estimationThe dif ficulties are how tO mitigate disturbance of random factors tO signals，and make location estimation methods more to- bust and adaptable After analyzing

4、 the difficulties of location estimation problem in IEEE 8021 1 bg WLAN，how tO evaluate the performance of location estimation algorithms，current principles of location methods，their advantages and disadvantages and classifications are introducedThen receive&signal-strength based indoor location alg

5、orithms are sur veyed in detailFuture research directions in indoor location estimation problem are pointed out at the end Keywords IEEE 80211，Wireless local area network，Indoor location estimation，Received signal strength 與基于信號到達時間(TOA)和信號到達角度(AOA)的 1 引言WLAN定位相比，它不需要添加額外的硬件設備來進行精確 隨著無線網(wǎng)絡、移動通信和普及計算技

6、術應用的不斷擴 的時間同步和角度測量，能充分利用現(xiàn)有的無線網(wǎng)設施，將定大和深入，位置感知計算1(Location-aware Computing)、基 位系統(tǒng)的應用范圍擴大到樓群和室內，降低成本，因此成為室于位置的服務(LBS，Location-based Services)顯得越來越重 內定位技術的研究熱點。國內在這方面的研究主要集中在軍要，典型的例子有資源查找、旅游導航、會議指南、尋找老人兒 隊的科研機構，中國 、 地區(qū)的高校有 科技大童等。如何確定用戶的位置是實現(xiàn)LBS的核心問題。全球 學8， 新竹大學。國外的高校和研究機構有微軟、IBM、定位系統(tǒng)(GPS，Global Position

7、ing System)是應用比較成功 Intel、CMU、匹茲堡大學、馬里蘭大學等。 的定位技術，它通過GPS 測量來自524個 信號 室內定位的難點在于如何克服隨機因素對信號的干擾， 的到達時間差估算位置，可以提供接近全球的定位覆蓋范圍。 對靜止和移動用戶進行準確、快速定位，使定位方法具有健壯但是，GPS在室內和高樓密布的城市由于感測不到 信號 性、適應性，因此對其研究涉及到隨機信號處理、跟蹤與導航、而無法定位。從20世紀90年代末期起，許多高校和研究機 人工智能、計算機技術等眾多交叉領域，目前國內外對定位算構開始了室內定位技術的研究，具有代表性的有AT&T 法的研究主要集中在提高算法的精度

8、和實用性。本文首先分Cambridge 主持的Active Badges項目2，之后進一步改進為 析基于IEEE 802 1lbg協(xié)議的無線局域網(wǎng)環(huán)境下定位問題Active Bats3|，cricket“，微軟的Easy Living項目5以及 的難點，如何評價定位算法的性能。在此基礎上，介紹目前定 Georgia Tech公司的Smart Floor項目61等。上述項目雖然 位方法的基本原理、優(yōu)缺點及其分類，然后詳細綜述利用接收取得了一定的效果，有的還可以達到毫米級的精度7，但這些 信號強度的室內定位算法，最后指出未來定位算法研究的幾定位系統(tǒng)需要添加新的硬件，系統(tǒng)部署復雜，維護成本高，可 個

9、方向。 擴展性差。 另一方面，基于8021lbg協(xié)議的無線局域網(wǎng)(WLAN) 2基于無線局域網(wǎng)室內定位的難點 已廣泛分布在校園、辦公大樓和家庭，PDA、筆記本等移動設 利用信號強度定位的重要前提是用戶收到的信號強度隨備中也都內置了無線網(wǎng)卡。基于接收信號強度的WLAN定 著與AP間距離的增大而減小。這一基本規(guī)律在RADAR系位是根據(jù)接收信號強度隨距離變化而變化的規(guī)律進行定位， 統(tǒng)伽的實驗中已經(jīng)得到了驗證，但是這種變化只是近似的線 *)本課題研究得國家自然科學基金項目(60503041)和上海市科委項目(03DZl9320)資助。張明華博士生，主要研究領域為普及計算、無線局域網(wǎng)定位；張申生教授，博

10、士生導師，主要研究領域為普及計算、分布式虛擬現(xiàn)實、分布計算與智能 等；曹健副教授，CCF會員，主要研究領域為協(xié)同信息系統(tǒng)、智能決策支持系統(tǒng)、網(wǎng)絡計算等。 性變化，在室內距離近、結構相對復雜的環(huán)境下，障礙物的影現(xiàn)有的研究中對定位速度的討論較少，一方面因為研究關響難以忽略。各種噪聲的干擾是室內定位的困難之一。干擾注的重點在定位精度，另一方面已有的定位方法還沒有復雜到 因素可以歸納為以下幾個方面：影響定位速度。但是當需要對移動用戶進行定位和跟蹤時，定(1)IEEE 8021lbg協(xié)議已成為無線局域網(wǎng)應用的主位速度將顯得非常重要。實驗發(fā)現(xiàn)，由于環(huán)境中各種干擾因素流，它們工作在24GHz的公共頻段上，這

11、使得信號在傳播過的存在，覆蓋某位置的AP信號的個數(shù)會隨著時間而變化1叩； 程中會受到其他使用該頻段的設備(如手機、微波爐、采用在不同的地點，網(wǎng)卡可感知到的接入點信號的個數(shù)也不同；在B1uetooth協(xié)議通訊的設備)的干擾。墻壁死角、拐彎等處，信號數(shù)量少而且微弱。定位范圍越大，說(2)人體90的成分是水，水的共振頻率為24GHz，因明定位算法的健壯性越好，應對干擾的能力越強。 此人體也是干擾無線信號的因素之一。BahlE9和Kaema 4基于信號強度定位算法的原理及其分類 rungsiEl3的實驗都說明，同一地點測量的信號強度會隨著用 戶站立方向的不同而發(fā)生顯著的變化。當用戶面朝AP時，近似法、

12、三角測量法和場景分析法是3種基本的位置感 AP的信號到達網(wǎng)卡為視距傳播(LOS，Line of Si。ght)，信號強知技術Iv。近似法即當物體靠近某一已知位置對，由該位置 度很強；而當用戶背朝AP時，用戶的身體遮擋了信號，信號來定位物體。三角測量法采用三角形的幾何特性計算物體的 強度下降，兩者之間的差別可達510dBm。位置。場景分析法則利用從某一優(yōu)勢位置觀察到的場景中的(3)由于室內建筑布局復雜，信號傳播中會受到家具、門特征信息，來估計觀測者的位置或者場景中某一物體的位置。窗、墻壁、天花板的阻擋，引起無線電信號的反射、折射、衍射在基于信號強度的室內定位方法中，相應的分別是最強基站現(xiàn)象，發(fā)射

13、信號往往經(jīng)過多條不同路徑，以不同的時間到達用法、傳播模型法和位置法，如圖1所示。 戶，造成傳播信號在時延擴展、信號幅度、頻率和相位的改變，基奎崖焦友造塞王筐曼堡度數(shù)室焦左整 從而導致多徑傳播(Multipath)效應。多徑傳播是基于到達 角度、信號強度、到達時間或時間差測量系統(tǒng)定位誤差的主要竺量+-+最強基站法模支的來豫力言羹麟萋萋 來源。三角測量法+一傳播模型法 在無線局域網(wǎng)中，基于接收信號強度定位的另外一個難場景分析法+一+位置法、位置的保存-確定性方法 點是如何使定位方法具有良好的環(huán)境可適應性。所謂可適應概率分布法 性是指當定位系統(tǒng)應用的環(huán)境發(fā)生改變后，定位算法也能利圖l室內定位方法分類

14、 用某種機制探測出來并自動地進行修正，以保證算法的正確在無線局域網(wǎng)中，最簡單的定位方法是將無線終端用于 性。環(huán)境中可能的變化有：數(shù)據(jù)通信的訪問點(AP)的位置，近似地作為估計的位置，稱 AP數(shù)量的變化。比如有的AP發(fā)生故障，部署新的為最強基站法。它不需要復雜的算法和任何的參數(shù)估計，也AP。不需要在客戶端添加新的軟件。但是該方法定位的精度局限室內布局的變化。如房間進行了新的裝修，布置了家在AP的信號覆蓋范圍，不能進行精確定位。 具，或者原有家具進行大范圍的調整。傳播模型法利用信號在室內的傳播衰減變化規(guī)律，將信可 以看出，上述兩個定位難點將直接影響定位算法的準號強度轉換成信號傳播的距離，根據(jù)已知的

15、AP位置和三角 確性和定位系統(tǒng)能否進入實際應用。測量原理計算出用戶的位置。這類方法簡單，計算效率高，但它的定位準確性主要依賴于傳播衰減模型是否正確，是否能3定位算法的性能度量 夠適合定位區(qū)域復雜的建筑和平面布局環(huán)境。根據(jù)傳播衰減為提高定位的準確度和定位算法的性能，研究者們提出 模型的來源又分為物理模型法和實驗模型法，即一種由信號了許多不同的方法并通過實驗加以驗證。但是，不同的實驗 傳播衰減的物理特性得到，另一種由大量實驗數(shù)據(jù)擬合出來。都是針對不同的定位環(huán)境，使用的硬件也有所不同。目前國 實驗模型法得到的傳播模型更適合待定位環(huán)境，但它普遍性際上在定位領域還沒有一套標準的測試數(shù)據(jù)，因此定位算法 不

16、好，使這類定位系統(tǒng)難以推廣。 的性能度量指標是比較和分析不同方法的重要依據(jù)。文30位置法完全在實驗的基礎上進行，分為離線勘測和給出了比較完整的無線定位系統(tǒng)的性能評價標準。無線環(huán)境在線定位兩個階段。離線勘測是在待定位區(qū)域里按照一定的下定位算法的性能度量可以分為4個方面：間隔距離確定若干采樣點，形成一個采樣點的網(wǎng)格，并將每個(1)定位準確性。即定位的誤差。點測得的信號強度連同其位置信息一同保存到數(shù)據(jù)庫里，這(2)定位 速度。即用戶發(fā)出定位請求與給出定位結果之些信息被稱為位置(Location Fingerprints)或射電天圖間的延時。(Radio Map)。在線定位時，將實時測量的信號強度信息

17、與數(shù)(3)接收定位請求的能力。即在單位時間內可以處理的據(jù)庫中的信息比較，取信號強度最接近的點的位置作為估計 定位請求數(shù)。的位置。換個角度，位置法也可以被看作是讓計算機先(4)定位范圍。即可定位的區(qū)域。學習信號強度與位置間的內在規(guī)律，然后再推理的過程，因此實際上，隨著LBS應用背景的不同，對定位精度的要求 神經(jīng)網(wǎng)絡、機器學習、統(tǒng)計學習理論也被越來越多地應用進也不同。如查找最近的打印機，定位到某個房間就可以滿足 來。根據(jù)位置 在數(shù)據(jù)庫中的保存形式，又可以分為確定要求。但對于走失兒童、老人的尋找，則需要盡可能的準確。 性方法和概率分布法。確定性方法保存一定采樣時間內接收對于定位準確度的表示目前還不太

18、統(tǒng)一，有的用精度和誤差 信號強度的平均值；概率分布法保存的是一定時間內信號強范圍共同表示，如Maryland大學研究的JC和IT系統(tǒng)10,123； 度的概率分布，如直方圖。相應地，在匹配時確定性方法多采還有的則給出結果的誤差累積分布函數(shù)(CDF)，如CIVI-O大 用歐式距離衡量兩個信號強度之間的相似性；概率分布法多實現(xiàn)更方便；而概率分布法對信號中噪聲的抗干擾性較好，因在RADAR9定位系統(tǒng)中。每個采樣點處的位置保存來此準確度較高。自AP的信號強度的平均值。通過采用歐幾里得幾何距離或目前位置法研究得較多，傳播模型法的瓶頸在于研其他距離(如曼哈頓距離)度量測量值與位置之間的差 究信號傳播模型。還

19、有的研究將傳播模型法和位置法結異，并取差異值最小的位置的位置作為估計的位置。用 合起 來。數(shù)學公式表示為 ，H 5典型的定位算法rain(D)，D一、(RSSi-RSSi)2 V t=1 基于對無線局域網(wǎng)中的室內定位技術的研究，下面針對其中行表示AP的個數(shù)，RSSi表示實時收到的來自第i個AP 每 種方法分別介紹一些具體的實例，并從性能上對比和分析的信號強度，RSSi表示數(shù)據(jù)庫中的信號強度平均值。RA 典型的定位算法。DAR稱為最近鄰居法。此外，考慮到相鄰采樣點的相似性，5.1 傳播模型法他們還提出了K個最近鄰居法和加權K個最近鄰居法，并分RADAR9是較早利用無線局域網(wǎng)中的接收信號強度開析了

20、它們適用的場合和效果。Kaemarungsi等人1釘提出了兩 發(fā)出的室內定位系統(tǒng)，其中為了減輕采樣的工作量，他們研究種選擇權值的方案，即分別以采樣點處樣本的個數(shù)和樣本的 了無線信號在室內的傳播衰減模型。通過對常用模型的適用標準偏差為權值。文21也采用了確定性的位置法，不 條件和優(yōu)缺點的比較，RADAR提出了考慮墻壁影響因素的同之處表現(xiàn)在他們根據(jù)接收信號強度的信息，首先確定可能室 內無線信號傳播衰減模型：所屬的位置集合，減少計算的次數(shù)。Battiti等人22貝0從神經(jīng)孑f 箍 W*wAF 咒WC網(wǎng)絡的角度考慮，以多個AP的信號強度為輸入，位置坐標為P(d)一P(而)一10扎109蓋一c；WAF

21、挖1咿c輸出，訓練多層感知機(MLP)，達到推理位置信息的目的，他其中 咒表示信號強度隨距離的衰減速度，P(d。)表示在參考 們的最終定位精度與K個最近鄰居法接近。在文23中，他距離 函處的信號強度，d表示信號發(fā)送方和接收方之間的距 們又將統(tǒng)計學習理論應用到無線局域網(wǎng)定位問題中，采用支離。 C表示衰減因子能夠分辨出的最大墻壁數(shù)，nW表示信 持向量機推理用戶所在的位置。 號 發(fā)送方和接收方之間的墻壁數(shù)，WAF指信號經(jīng)過墻壁的 基于概率分布的位置 法是目前研究定位算法的熱衰減 因子。他們研究的模型沒有直接用于估計用戶的位置， 點，是繼確定性方法之后由Petri Myllymaki等人241首先提只

22、是 用來生成定位區(qū)域的射電天圖(radio map)。出，他們將位置估計問題看作機器學習的問題，即基于在已知Robinson等人”在RADAR的基礎上提出了概率形式區(qū)域收集的樣本建立信號強度在不同地理區(qū)域上的分布模的室 內信號傳播衰減模型，以此計算AP與網(wǎng)卡間的距離。型，并提出了一個概率性的框架解決定位問題。Bayes規(guī)則 用 戶端網(wǎng)卡上的接收信號功率的概率分布函數(shù)表示為是基于概率分布法的理論基礎，其中的關鍵在于如何確定每f(Pi；mi，di)=g(Pl；PiL0107 log(di)一mk，2)個采樣點處信號強度分布的先驗概率。Myllymaki等人提出其 中函數(shù)g(z；p，礦)表示平均值為

23、P、方差為礦的高斯分布了核方法和直方圖方法。Youssef等人10的聯(lián)合聚類(JC，隨量的概率分布函數(shù)。Pr為用戶接收的來自第i個APJoint Clustering)定位系統(tǒng)同樣基于概率分布的方法，并提到 的接收功率，P。為第i個AP的發(fā)射功率，k表示距發(fā)射端了研究定位算法復雜性問題，使定位系統(tǒng)能夠適應用戶端資 lm處 的路徑損失，y代表路徑損耗系數(shù)，m為用戶與AP間源有限的移動設備。他們提出利用聯(lián)合聚類技術(Joint 的墻壁 個數(shù)，k表示一面墻對信號的衰減。利用該模型，Clustering Technique)1U以解決，即引入聚類技術，減小需要 Rob inson等人計算出用戶與AP間

24、的最大似然距離，結合AP匹配的樣本量，由各AP信號強度的聯(lián)合概率分布確定定位的位置 坐標，用三角測量推算用戶的位置。對定位誤差要求區(qū)域各點處的先驗概率。之后，他們又進一步從信號強度的 不高 的情況下，這種方法相對簡單、高效。時間253和空間26特性上著手，利用時間序列分析等技術提文17用信號傳播模型估計用戶與AP間的距離，然后高定位算法的性能。IBM研究院的ZXiang等人27為了減利用擴展卡爾曼濾波器(EKF)技術將距離的估計轉化為對用 輕收集樣本的工作量，設計了平滑過濾器和加尾過濾器，使得 戶位置的估計。在文18中，作者發(fā)現(xiàn)如果對定位精度要求 利用少量的樣本就可以構造信號強度長期變化的規(guī)律

25、。同 很高，開放空間里的信號傳播模型難以適用在室內的現(xiàn)實環(huán) 時，他們利用圖論技術表示出室內的拓撲結構，結合前一時刻 境中，因此不再考慮多徑傳播和干擾，而直接從試驗數(shù)據(jù)中求 出最佳的回歸模型，形式如下： 對用戶位置的估計，來大致判斷用戶下一時刻可能的位置，比如用戶不可能穿墻而過，必須沿走廊行走等。另外一種基于 d=O000198*S3一O025*S2+114*S一148概率分布的位置法是基于貝葉斯網(wǎng)絡技術，最早由其中 S表示信號強度，單位為dBm。d表示接收端與AP問 UCLA大學Castro等人提出，應用在Nibble組件中，以提供的距 離，單位為米。為提高系統(tǒng)定位的精度，降低環(huán)境對信號 Wi

26、Fi網(wǎng)絡環(huán)境下的房間內定位服務z8|。貝葉斯網(wǎng)絡是一個 的干擾，他們在文E20里進而提出兩種性能改進算法。通過 聯(lián)合概率分布的圖形化表示，可以清楚地說明分布中各隨機增加 基準參考測量點，用以校正測量信號同存在的系統(tǒng) 變量間的依賴關系。文29也基于貝葉斯網(wǎng)絡進行了相關的 誤差 ；同時，以5s為間隔，取其中最強的信號強度值為這段時 研究。 間的 信號強度，忽略微弱的干擾信號。以上從兩個大的方面對一些有代表性的定位系統(tǒng)或定位從目前的研究可以看出，傳播模型法主要使用在兩個方算法進行了分析和研究?？偟膩碚f，傳播模型法的精度稍差面 ：當用戶或應用對定位精度的要求不高時；與其他方一些，一般情況下為510m。

27、位置法因為獲取的樣本信法 、技術結合起來，提高定位的精度。息更多，更加結合實際環(huán)境，所以精度稍好一些，平均805.2 位置法90的情況下可以達到3m以內。表1對上述提到的典型的 確定性方法是一種比較簡單的位置法，它最早出現(xiàn)定位算法進行了對比。 70 實例表1典型定位算法的對比 對比項、 RADARRADARNibbleJC 對象靜止用戶、移動用戶靜止用戶移動用戶靜止用戶 方法確定性位置模型法+確定性位置貝葉斯網(wǎng)絡基于概率分布的位置范圍 三層樓的第二層，三層樓的第二層，Boelter大樓中的走廊和FX Palo 224英尺*851英尺， 43.5 米*225米435米*225米Alto實驗室22

28、4英尺*96英尺 計算機系大樓中四層的南翼 靜止用戶：75，469米除15的地點無法識別， 精度50，43米90，7英尺移動用戶：50，35米剩余的97的地點能識別 速度未討論未討論每2秒更新一次位置的概率未討論 環(huán)境可適應性未來的工作未考慮未考慮未考慮 總結與展望基于位置的服務實現(xiàn)的一個關鍵是如何準5 Microsoft ResearchEasy livingWebsite，2001http：www 確獲取用戶所在的位置，利用LBS可以為用戶提供更加方 researchmicrosoftcomeasyllying 6 0rr R J，Abowd G DThe smart floor：A me

29、chanism for natural 便、 高效的服務，進而預測用戶的行為。室內定位，特別是基 user identification and trackingIn：Proceedings of the 2000 Con于無線局域網(wǎng)的室內定位技術，已成為一個非?；钴S的研究 ference on Human Factors in Computing Systems(CHI 2000)， 領域，在普及計算、移動計算、無線局域網(wǎng)方面的重大國際會 The Hague，Netherlands。April 2000 7 Hightower J，Borriello GA Survey and Taxono

30、my of Location議， 如UbiComp、InfoCom和國際期刊，如IEEE PervasiveSensing Systems for Ubiquitous ComputingUW CSE 01-08-03 Computing上都有相關的研究內容發(fā)表。本文首先分析無線Seattle，WA：University of Washington，Department of Computer Science and Engineering，Aug2001 局域網(wǎng)中利用信號強度定位的難點，無線定位系統(tǒng)的性能評8 http：ihomeusthkyinjieindexhtml 價標準。在介紹定位方

31、法基本原理和優(yōu)缺點的基礎上，綜述9 Bahl P，Padmanabhan V NRADAR：An In-building RF-Based 和對比了典型的定位算法。User Location and Tracking SystemINR0M，20002775 784 目前許多定位算法的研究集中在如何減小環(huán)境里的各種10 Youssef M，Agrawala A，Shankar A U WLAN Location Deter干擾因素對定位誤差的影響，提高定位精度?？梢钥闯觯瑸槭筸ination via Clustering and Probability DistributionsIn：IEEE

32、 定位系統(tǒng)能較好的應用于實際，還需要進一步提高定位算法 International Conference on Pervasive Computing and Communi cations(PerCom)2003，F(xiàn)ort Worth，Texas，March，2003 的易用性，環(huán)境可適應性等性能。不僅能夠對靜止用戶定位， 1l Smailagic A，Siewiorek D P，Anhalt J，et a1Wang，YLocation 而且能對移動用戶位置做出及時的判斷?；诙ㄎ凰惴ǖ难?Sensing and Privacy in a Context Aware ComputingPer

33、vasive Computing，2001Environment 究現(xiàn)狀，本文提出未來的定位算法的研究重點將集中在： 12 Youssef M，Agrawala ASmall-scale Compensation for WLAN (1) 借鑒數(shù)據(jù)融合的思想，不僅使用用戶端的接收信號強Location Determination SystemsIn：IEEE Wireless Communica度，而且結合定位環(huán)境中的室內布局信息，用戶經(jīng)常的行動路tions and Networking Conference(WCNC)2003 New Orleans， 徑， 研究如何提高定位的準確性，同時減

34、少定位算法對前期環(huán)Louisiana，March，200313 Kaemarungsi K，Krishnamurthy PProperties of Indoor Received 境勘測工作的依賴D4As，使定位系統(tǒng)可以快速應用到不同的Signal Strength for WLAN Location FingerprintingMobiQ- 場合 。uitous，20041423 14 Yin J，Yang Q，Ni L M Adaptive Temporal Radio Maps for In (2) 提高定位算法的效率，使得占用的資源更少，定位速door Location Estima

35、tionIn：Proceedings of the Third Annual 度更 快。移動通信技術、嵌入式系統(tǒng)的發(fā)展使終端設備便攜IEEE International Conference on Pervasive Computing and COm- 性不 斷提高，體積越來越小，同時便攜式設備可用的存儲資munications(PerCom 05)，Kauai Island，Hawaii，March 2005 8594 源、 能量也很有限，研究和改善定位算法的運算時間復雜度， 15 Chai Xiaoyong，Yang QiangReducing the Calibration Effor

36、t for空間 復雜度也具有一定的現(xiàn)實意義。Location Estimation Using U11labeled SamplesPervasive Compu (3) 提高定位系統(tǒng)的適應性，使之能夠根據(jù)環(huán)境中網(wǎng)絡環(huán)ting and Communications，2005In：PerCom 2005Third IEEE International Conference on March 200595104 境的 變化，如AP的增加、減少、位置的變動或室內布局的調16 Robinson M 。 Psaromiligkos IReceived Signal Strength-based整。 文1

37、5E2031中都采用引入?yún)⒄瘴锏姆椒▽Σ杉臉覮ocation Estimation of a Wireless LAN ClientIEEE Communi 本或定位結果進行校正和調整。另外一種思路是結合機器入cations SocietyWCNC，2005 17 Kotanen A，Hannikainen M，Leppakoski H，et a1Positioning 學、 現(xiàn)代控制理論、卡爾曼濾波器，在移動用戶的定位中發(fā)現(xiàn) with IEEE 8021lb wireless lanIn：14th IEEE Proceedings on 環(huán)境 中可能的變化。對移動用戶的定位也是本文的重點工

38、作 Personal，Indoor and Mobile Radio Communications(PIMRC 之一。2003)，Sept200322182222 18 Wang Y，Jia X，Lee H K An Indoors Wireless Positioning Sys- 參考文獻 tern Based on Wireless Local Area Network InfrastructureIn： The 6th International Symposium on Satellite Navigation(SatNav 2003)，Melbourne，Australia，Ju2

39、l0y03 1 Hazas M，Scott J，KrUlTIITI JLocation-aware computing comes of ageComputer，2004，37(2)：9597 19 Prasithsangaree P，Krishnamurthy P，Chrysanthis P KOn In2r ant R，Hopper A，F(xiàn)aleao V，et a1The active badge location system ACM Transactions on offica Information Systems (TOIS)，1992，10(1)：91102 3 Wa rd AJ

40、ones A，Harper八A new 10cation technique for the door Position Location with Wireless LANsPIM喂C。2002 20 WANG Y，JIA X，Rizos e Two new algorithms for indoor WirelessPositioning System(WPS)Int 17 th Int Tech Meetingof the Satellite Division of the U S Institute of NavigationLong active officeIEEE Persona

41、l Communications，1997，4(5)：42Beach，California，September，200419881997 21 Jan Rong-Hong，Lee Yung RongAn indoor geolocation system 47 4 Pr iyantha N B，Chakraborty A 。 Balakrishnan HThe cricket 10 for wireless LANsIn：Proceedings of the International Confer cation-support systemIn：Proceedings ofjoBICoM 2

42、000，Bosence on Parallel Processing Workshops(ICPPW03)2003 ton，MA，ACM，ACM Press，August 20003243(下轉第75頁) 71 新。準確地說，更新的表項數(shù)是2241眥(17FM224)，可見 結論本文提出了一種新穎的基于最長前綴匹配的分段 更新的表項數(shù)最大值是128。相似地，SegH中一次性更新的 式IP查表方法。利用這種方法可以獲得高達25X108秒的表項數(shù)是216硼1(8FHl16)，更新的表項數(shù)最大值是256； 吞吐量，可滿足具有40Gbps高速光纖鏈路的骨干路由器的SegL中一次性更新的表項數(shù)是23z-

43、凡1(25FLl32)，更新 要求。此外，利用這種方法更新轉發(fā)表，可以使得更新時間最的表項數(shù)最大值是128。大多數(shù)情況下，需要更新的是對應 多不大于512 ns，能極大程度滿足骨干路由對更新時間的要于前綴長度介于16到24的表項，因此需要的時間只是一個 求。 DI)R II讀周期。最差的情況是一次需要更新256個表項，假4-8 J一DDRlI存聊對間=2 rl$【 設我們轉發(fā)表存儲在是讀寫周期為2ns的DDRII中，此時更 4o 新操作所需要的時間也僅僅是512ns，這個值大約是文3中 一36 獲得的平均更新時間的25。5 32 星28 f 翟2 一一一一一一一一一一一一 稷20 6 測1 2

44、 08 O鼻 OO 2 4 6 8 10 1216 18盈甜神湖越前綴長度 圖8不同前綴長度需要的搜索時間 參考文獻 1 砧一K11affaf B A，karuppiah E K，Abdulah R Efficient partitionbased6 lookup algorithm for packet forwardingIn：Proeof 圖7更新SegM中的表項the 9th Asia-Pacific Conference on Communications，Penang， Malaysia，V011，seD2003238242 2 Berger M IP 100kup with lo

45、w memory requirement and fast up 7性能dateIn：Workshop on High Performance Switching and Routing， 轉發(fā)表的邏輯框圖見圖2，假設該圖中的SegH、SegM以Torino，Italy，Jul2003287291 3 Jean S，Chung S H，et a1Sealable IP lookup scheme with small 及SegL采用的是讀寫周期為2 as的DDR II。根據(jù)前面的分 forwarding table for gigabit routersE1ectronics Letters，

46、2002，38析，當IP地址的前綴長度介于8到16時，相應的表項位于(6)：298230 SegH中，此時搜索下一跳只需要一個DDR II讀寫周期，即4 MAl_West routing databaseThe Internet performance Measure 2ns；當當前綴長度介于17到24時，可確定表項位于SegMment and Analysis(IPMA)Projecthttp：wwwmeriteduim- 中，此時搜索下一跳仍然只需要一個DDR II讀寫周期，2ns；parouting-table，Oct2002 5 Sundstron M，Larzon L A High-

47、peHormance longest prefix matc- 當前綴長度介于25到32時，可確定表項位于SegL中，這時 hing supporting high-speed incremental updates and guaranteed 需要分別讀取SegM和SegL，即搜索過程包括兩次DDR IIcompressionIn：Proc of 24th Annual Joint Conference of the讀周期，需要22 ns一4ns。將上述結果用搜索時間前綴IEEE Computer and Conmmnications Societies，Miami，F(xiàn)L， 長度的曲線來表

48、示，參見圖8。USA，2005。3：16411652 (上接第71頁)27 Xiang Z，Song S，Chen J，et a1A Wireless LANbased Indoor 22 Battiti R，Villani A，Le Nhat TNeural network model for intelPositioning TechnologyIBM Journal of Research and Develop- ligent networks：deriving the location from signal patternsIn：ment，2004，48(56)：617626 Pr

49、oceedings of The First Annual Symposium on Autonomous In28 Castro P，Chiu P，Kremenek T，et a1A Probabilistic Location telligent Networks and Systems UCLA，May，2002Se而ca for Wireless Network EnvironmentsIn：Proceedings of23 Brunato M，Battiti RStatistical Learning Theory for LocationUbicomp 2001，Spdnger V

50、ertag，September 20011824 Fingerprinting in Wireless LANsComputer Networks，2005，4729 Madigan D，Elnahrawy E，Martin R P，et a1Bayesian Indoor Po- (6)：825845sitioning SystemsIn：Proceedings of the 24 th Joint Conference 24 Roos T，Myllymaki P，Tirri H，et a1A Probabilistic Approachof the IEEE Computer and Co

51、mmunication Societies(INFOCOMto WLAN User Location EstimationInt Journal of Wireless In2005)，Miami，F(xiàn)L，March 2005 formation Networks，2002，9(3)：15516430 Tekinay S。Chao E，RichtonPerformance Benchrnarking for 25 Youssef M，Agrawala A KHandling Samplas Correlation in theWireless Location SystemsIEEE Commu

52、nications MagazineAHorus Systerm IEEE Infocom，Hong Kon_g，March 2004pril 1998 26 Y0ussef N ， Agrawala A On the Optimality of WLAN Location 31 Krishnan P ， Krishnakumar A S ， Ju Wen-Hua ， et a1 A System Determination SystemsIn：Communication Networks and Dis for LEASE：Location Estimation Assisted by St

53、ationary Emitters trihuted Systems Modeling and Simulation Conference，San Die for Indoor RF Wireless NetworksINF000M，2004 go，california，January 2004 75 無線局域網(wǎng)中基于信號強度的室內定位 計算機科學 作者：張明華， 張申生， 曹健， ZHANG Ming-Hua， ZHANG Shen-Sheng， CAO Jian 作者單位：上海交通大學,計算機科學與工程系,上海,200240 刊名： 英文刊名：COMPUTER SCIENCE 年，卷(期)

54、：2007,34(6) 被引用次數(shù)：5次 參考文獻(31條) 1.Youssef M;Agrawala A;Shankar A U WLAN Location Determination via Clustering and Probability Distributions外文會議 2003 2. Madigan D;Elnahrawy E;Martin R P Bayesian Indoor Positioning Systems 2005 3. Castro P;Chiu P;Kremenek T A Probabilistic Location Service for Wireless Network Environments 2001 4.Xiang Z;Song S;Chen J A Wireless LAN-based Indoor Positioning Technology 外 文 期 刊 2004(5-6) 5.Youssef M;Agrawala A Small-scale Compensation for WLAN Location Determination Systems外文會議 2003 6. Smailagic A;Siewior