(3.238.235.155) 您好!臺灣時間:2021/05/11 04:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:王文揚
研究生(外文):Wen-Yang Wang
論文名稱:基於芙諾以圖之室內定位演算法
論文名稱(外文):A Voronoi-based Algorithm for Indoor Localization
指導教授:雷欽隆雷欽隆引用關係
指導教授(外文):Chin-Laung Lei
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:46
中文關鍵詞:定位芙諾以圖感測器網路
外文關鍵詞:localizatoin algorithmVoronoi diagramsensor networks
相關次數:
  • 被引用被引用:0
  • 點閱點閱:126
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
  定位對於感測網路而言,是個相當重要的問題。一些感測器所得的資訊,如果沒有其對應位置的話,很有可能不具有任何意義。因此,針對感測網路的定位這個問題,前人提出了不少方法可供使用;然而,在室內環境下的定位,仍舊需要相當高的硬體成本,以及繁瑣的事前準備工作。本篇論文針對室內定位提出了一套新的做法。這個方法主要根據芙諾以圖來進行定位,而且只需要為數不多的感測器,即可做到相當不錯的定位效果。除此之外,對於室內有障礙物的情況,本篇論文也提出一個延伸的芙諾以演算法用來計算芙諾以圖。原先的芙諾以圖利用兩點之間的直線距離來判斷這兩點的遠近關係,而這個新的演算法則可利用兩點之間最短路徑的長度來判斷。之後,為了了解本篇論文所提出的這個定位法的優劣,在文中對於數種不同的情況,也做了一些模擬來測試這個定位法的表現。
Location is one of the most important contexts for the sensor networks. In sensor networks, sensors have to know their locations in order to make the sensing data meaningful. Therefore, there are many previous localization algorithms and systems that can estimate the sensors’ locations. A Voronoi-based algorithm for indoor localization has been proposed to do the localization, too. Based on the Voronoi diagram, the proposed algorithm can localize a sensor by only several beacons needed, and the results of estimation accuracy are acceptable. Besides, to support the indoor environment, an extended Voronoi algorithm is used by defining the distance between the sensor and the beacon as the length of the shortest path. Simulations are also provided to justify the achieved accuracy of the proposed algorithm under different situations.
Chapter 1 Introduction 1
1.1 Sensor Networks 2
1.2 Voronoi Diagram 4
Chapter 2 Related Works 7
2.1 Proximity 7
2.2 Triangulation 8
2.3 Scene Analysis 12
2.4 Miscellaneous 13
Chapter 3 The Proposed Algorithm 17
3.1 Design Goals 18
3.2 Assumptions 19
3.3 Extended Voronoi Algorithm 21
3.4 The Proposed Algorithm 27
3.5 Case Study 30
Chapter 4 Simulation 35
4.1 The Original Voronoi Diagram 36
4.2 Number of Beacons 38
4.3 Number of Decrements 38
4.4 Communication Radius 39
4.5 Beacon Placements 40
4.6 The Error Bound 42
Chapter 5 Conclusion and Future Works 45
5.1 Conclusion 45
5.2 Future Works 46
Reference 47
[1]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey on Sensor Networks,” IEEE Communication Magazine, vol. 40, issue 8, p. 102-114, IEEE, August 2002.
[2]F. Aurenhammer, “Voronoi Diagrams: A Survey for a Fundamental Geometric Data Structure,” ACM Computing Survey, vol. 23, issue 3, p. 345-405, ACM, September 1991.
[3]P. Bahl and V. N. Padmanabhan, “RADAR: An In-building RF-based User Location and Tracking System,” Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2000), vol. 2, p. 775-784, IEEE, March 2000.
[4]N. Bulusu, J. Heidemann, and D. Estrin, “Density Adaptive Beacon Placement Algorithms for Localization in Ad Hoc Wireless Networks,” Technical Report UCLA-CS-TR-010013, University of California, Los Angeles, Computer Science Department, July 2001.
[5]N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less Low-cost Outdoor Localization for Very Small Devices,” IEEE Personal Communication, vol. 7, issue 5, p. 28-34, IEEE, October 2000.
[6]P. H. Dana, Global Positioning System Overview, the Geographer''s Craft Project, Department of Geography, the University of Colorado at Boulder, 1999.
[7]S. Fortune, “A Sweepline Algorithm for Voronoi Diagrams,” Proceedings of the 2nd Annual Symposium on Computational Geometry, p. 313-323, ACM, June 1986.
[8]A. Harter, A. Hopper, P. Steggles, A. Ward, and P. Webster, “The Anatomy of a Context-aware Application,” Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom’99), p. 59-68, August 1999.
[9]T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-Free Localization Schemes for Large Scale Sensor Networks,” Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom’03), p. 81-95, ACM, September 2003.
[10]J. HighTower and G. Borriello, “A Survey and Taxonomy of Location Systems for Ubiquitous Computing,” Technical Report UW CSE 01-08-03, University of Washington, Department of Computer Science and Engineering, August 2001.
[11]M. A. Mostafavi, C. Gold, and M. Dakowicz, “Delete and Insert Operations in Voronoi/Delaunay Methods and Applications,” Computers & Geosciences, vol. 29, issue 4, p. 523-530, May 2003.
[12]A. Nasipuri and K. Li, “A Directionality based Location Discovery Scheme for Wireless Sensor Networks,” Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA’02), p. 105-111, ACM, September 2002.
[13]D. Niculescu and B. Nath, “Ad hoc Positioning System (APS),” Proceedings of the 21st Annual Joint Conference of IEEE Computer and Communications Societies (INFOCOM 2003), vol. 3, p. 1734-1743, IEEE, March 2003.
[14]R. J. Orr and G. D. Abowd, “The Smart Floor: A Mechanism for Natural User Identification and Tracking,” Technical Report GIT-GVU-00-02, Georgia Institute of Technology, Graphics, Visualization, and Usability (GVU) Center, January 2000.
[15]N. B. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller, “Anchor-free Distributed Localization in Sensor Networks,” Technical Report MIT-LCS-TR-892, Massachusetts Institute of Technology, Laboratory of Computer Science, April 2003.
[16]N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, “The Cricket Location Support System,” Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom’00), p. 32-43, ACM, August 2000.
[17]N. B. Priyantha, A. K. L. Miu, H. Balakrishnan, and S. Teller, “The Cricket Compass for Context-aware Mobile Applications,” Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom’01), p. 1-14, ACM, July 2001.
[18]R. Want, A. Hopper, V. Falcao, and J. Gibbons, “The Active Badge Location System,” ACM Transactions on Information Systems (TOIS), vol. 10, issue 1, p. 91-102, ACM, January 1992.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔