在無線感測網路中，現存的繞徑協定、資料儲存技術及物件追蹤技術均假設Sensor Node具有精準的位置資訊，然而，就現今所提出之各種定位技術而言，仍無法使Static Sensor Node具有精準的位置資訊，近年來已有許多Bounding Box的定位技術被提出，其主要利用攜帶位置資訊的Mobile Anchor不斷移動，並定期發送其位置資訊，以協助其鄰近的Static Sensor Node定位，然而，由於Static Sensor Node所儲存的位置資訊為一矩形的模糊位置，這將造成Sensor Node無法區別其與鄰近Sensor Nodes在東西南北方位上的相對關係，相對位置的不確定將使目前廣為應用的具位置感知繞徑協定位置以及現存的物件追縱技術其效能顯著低落。本論文對Bounding Box定位技術所衍生的相對位置模糊關係詳加討論及分析，並在不改變發送Beacon之位置及數量的條件下，提出分散式的方法來協助Static Sensor Node改善其與鄰近Sensor Node相對位置的辨別度，此外，我們亦提出一繞徑協定以克服不精確位置所產生的繞徑問題。效能分析及實驗顯示，以本論文所提出定位技術的確可顯著改善鄰近Sensor Node間的相對位置辨別度，此技術與現有具位置感知之繞徑協定搭配使用將可大幅改善繞徑效能，而搭配本論文所提出之定位技術及具模糊位置感知之繞徑技術，將可再更進一步改善繞徑的效能。

Location information has been proven to be very useful in the design of sensor network infrastructures. First of all, a sensor network is “data-centric”. The data sensed by sensor networks are meaningless if we don’t know where the data are from. Location information can also help routing. However, it is still a big challenge to provide each sensor with accurate location information. Many localization mechanisms developed based on the bounding box concept have been proposed. Each sensor that receives the location beacons from mobile anchor can construct a rectangle box representing its possible location region. However, the bounding box approaches can not identify the relative locations for neighboring sensors based on the inaccurate location information. Furthermore, the well-known location-aware routing can only be applied in the network environment where each sensor has accurate location information. The performance of location-aware routing will be significantly dropped when it is applied in an inaccurate location environment. This paper aims to improve the location accuracy of each sensor and help the neighboring sensors to identify their relative locations by using the unused location beacons. In addition, a location-aware routing mechanism that is operated in an inaccurate location environment is proposed to improve the routing performance. Simulation study reveals that the proposed localization mechanisms improve the location accuracy and identify the relative location of sensors while the proposed location-aware routing mechanism reduces the average route length and hence prolongs the network lifetime.

目    錄	I
圖 目 錄	II
第一章、緒論	1
第二章、相關研究	5
第三章、網路環境與問題描述	10
第四章、改善位置精準度及區別度之定位技術	14
第五章、模糊位置資訊下之繞徑協定	24
第六章、模擬實驗	27
第七章、結論	36
參考文獻	37
附錄-英文版本	40
圖 目 錄
圖(一)  Bounding Box定位方法概念圖	3
圖(二)  (a)為兩個相鄰的Sensor S1與S2的位置資訊Bounding Box相互重疊。(b)Sensor S3與S4之間的位置資訊雖無重疊，但仍無法分辨相對關係。	7
圖(三)  以接收的每個Beacon所代表的方格取其交集，以此交集出的斜線方格為此感測器的位置資訊。	9
圖(四)  Sensor Node位置資訊之符號定義圖	11
圖(五)　黑點為Sensor Node實際所在位置，粗線條方框為每個Sensor Node所擁有的Bounding Box，三角形為一Beacon位置，虛線則代表此Beacon的通訊範圍與Beacon範圍。	16
圖(六)　位置資訊縮減程序示意圖	19
圖(七)　矩形化程序示意圖	20
圖(八)  (a)Sensor皆有各自的Bounding Box資訊，並且S1能與剩餘Sensor通訊 (b)八個象限示意圖 (c)八個象限得分分配圖	26
圖(九) 　Bounding Box定位方式之定位結果	30
圖(十)　以方格中心為Sensor座標執行Greedy 繞徑演算法	30
圖(十一)　以象限的概念執行Greedy繞徑演算法	31
圖(十二)　以傳統Bounding Box位置資訊定位法所得之結果。	31
圖(十三)　經由我們所提出的位置資訊修正法後所得之改善結果。	32
圖(十四)　在500×500的場景下，分別以Regular（蛇行）及Random行走方式廣播Beacon，並在六種點密度下分別求位置資訊之改善比例。	32
圖(十五)　在500×500的監控場景下，我們分別以三種點密度來分析Mobile Anchor行走的過程中，間隔不同的距離廣播Beacon對我們所提出的演算法之改善效能有何影響。	33
圖(十六)　在500×500的場景下，以傳統的Geographic Routing及我們所提出的Routing在Bounding Box及我們提出的位置資訊修正演算法下的繞徑平均步數。	34

[1]	A. Galstyan, Bhaskar Krishnamachari, Sundeep Pattem and Kristina Lerman, “Distributed Online Localization in Sensor Network Using a Moving Target,” in ACM/IEEE International Conference on Information Processing in Sensor Network (IPSN), California, USA, 2004, pp. 61-70.
[2]	G. J. Pottie and W. J. Kaiser, “Wireless Integrate Network Sensors,” Communications of the ACM, vol. 43, no. 5, pp. 551-558, 2002.
[3]	D. Estrin, L. Girod, G. Pottie and M. Strivastava, “Instrumenting the World With Wireless Sensor Networks,” in International Conference of Acoustics, Speech, and Signal Processing (ICASSP), vol. 4, 2001, pp. 2033-2036.
[4]	I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “A Survey on Sensor Networks,” IEEE Communication Magazine, vol. 40, pp. 102-114, 2002.
[5]	J. Hightower and G. Borriello, “Location Systems for Ubiquitous Computing,” IEEE Computer, vol. 34, pp. 57-66, 2001. 
[6]	B. H. Wellenhoff, H. Lichtenegger and J. Collins, “Global Positions System: Theory and Practice,” Fourth Edition. Springer Verlag, 1997. 
[7]	B. Parkinson and J. Spilker, “Global Positioning System: Theory and Application,” American Institute of Aeronautics and Astronautics, 1996. 
[8]	N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, “The Cricket Location- Support System,” in ACM International Conference on Mobile Computing and Networking, Boston, MA, 2000, pp. 32-43. 
[9]	D. Niculescu and B. Nath, “Ad-Hoc Positioning System (APS) Using AOA,” in IEEE Conference on Computer Communications (INFOCOM), San Francisco, CA, 2003. 
[10]	D. Niculescu and B. Nath, “Ad-Hoc Positioning System,” in IEEE Global Communications Conference (GLOBECOM), San Antonio, TX, Nov. 2001. 
[11]	A. Savvides, C. C. Han, and M. B. Srivastava, “Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors,” in ACM International Conference on Mobile Computing and Networking (MOBICOM), Rome, Italy, 2001, pp. 166–179. 
[12]	K. Chintalapudi, A. Dhariwal, R. Govindan, and G. Sukhatme, “Ad-Hoc Localization Using Ranging and Sectoring,” in IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 2004. 
[13]	Y. Shang, W. Ruml, and Y. Zhang, “Improved MDS-Based Localization,” in IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 2004. 
[14]	M. L. Sichitiu and V. Ramadurai, “Localization of Wireless Sensor Networks with A Mobile Beacon,” Technique Report, Center for Advances Computing Communications, North Carolina State University TR-03/06, July 2003. 
[15]	N. Bulusu, J. Heidemann, and D. Estrin, “GPS-Less Low Cost Outdoor Localization for Very Small Devices,” IEEE Personal Communications Magazine, vol. 7, no. 5, pp. 28-34, 2000.
[16]	D. Niculescu and B. Nath, “DV Based Positioning in Ad Hoc Networks,” Kluwer J. Telecommunication System, vol. 22, no. 1, pp. 267-280, 2003. 
[17]	T. He, C. Huang, B. Lum, J. Stankovic, and T. Adelzaher, “Range-Free Localization Schemes for Large Scale Sensor Networks,” in ACM International Conference on Mobile Computing and Networking (MOBICOM), San Diego, CA, 2003. 
[18]	C. Liu, K. Wu, and T. He, “Sensor Localization with Ring Overlapping Based on Comparison of Received Signal Strength Indicator,” in IEEE International Conference on Mobile Ad-hoc and Sensor Netwrok (MASS), Fort Lauderdate, Florida, 2004. 
[19]	V. Vivekanandan and V. Wong “Concentric Anchor-Beacons (CAB) Localization for Wireless Sensor Networks,“ in IEEE International Conference on Communications (ICC), Istanbul, Turkey, 2006. 
[20]	K. F. Ssu, C. H. Ou, and H. Jiau, “Localization with Mobile Anchor Points in Wireless Sensor Networks,” IEEE Transaction on Vehicular Technology, vol. 54, pp. 1186-1197, May 2005. 
[21]	T V Srinath, “Localization in Resource Constrained Sensor Networks Using a Mobile Beacon with In-Ranging”, in IEEE International Conference on Wireless and Optical Communication, 2006
[22]	J. P. Sheu, J. M. Li, and C. S. Hsu “A Distributed Location Estimating Algorithm for Wireless Sensor Networks”, in IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC), vol. 1, Taichung, Taiwan, 2006, pp. 218-225.
[23]	M. Wong and D. Aksoy “Relative Accuracy based Location Estimation in Wireless Ad Hoc Sensor Networks.”, in IEEE International Conference on Communications (ICC), Glasgow, Scotland, 2007, pp.3244-3250.