臺灣博碩士論文加值系統

在無線網路下決定節點的座標位置是一個很有挑戰性的問題。這個問題十分的重要，尤其是對於體積很小的節點，如感測節點。因此，有很多的研究都在探討無線網路下的定位問題。節點定位的問題大致可分成兩大類：集中式及分散式定位方法。集中式定位方法需要有中央控管的伺服器，其功能是負責接收節點所偵測資料及其定位的要求，並根據此資訊執行定位演算法以決定節點位置資訊並回傳給發出詢問的節點。此方法的優點是系統架構簡單且節點負擔較輕。但缺點為伺服器與節點間的通訊成本大，且伺服器的運算負載重。另一方面分散式的定位方法，讓節點可以自行完成定位而不需依靠伺服器的協助。本篇論文針對規則及不規則的網路架構下，提出一個利用訊號涵蓋範圍區域重疊的特性來讓節點自行估計目前的位置。節點只需接收來自參考節點的訊框資訊，並根據收集的資訊來執行簡單的運算即可獲得位置資訊。我們討論所提方法的定位能力及對於不同環境下，評估系統的效能。另外，為了進一步提升定位系統的準確度，我們將具單一訊號強度的參考節點改採用具有多重訊號強度的參考節點。將此改進方法應用於各種嚴苛的狀況，如參考節點損壞、訊號不穩定、訊框封包遺失等，所提出的方法均能維持良好的運作。對於這樣的結果，我們相信將有助於提供一個簡單、準確且低成本的定位系統。

One challenging issue in wireless networks is to determine where a given node is physical located. This problem is especially crucial for very small nodes such as sensor nodes. Therefore, many researchers have given much attention to positioning problem of wireless networks. This problem can be solved by centralized or distributed positioning methods. The centralized positioning methods need a central server to receive the sensed data, accept positioning queries, perform positioning algorithm and reply the coordinate back to the querying node. The advantages of centralized methods are that their system architecture is simple and the computing load of querying node is light. However, both of the communication overhead between central server and querying node and computational load of central server are very heavy. Therefore, the distributed positioning methods are presented to provide a self-positioning mechanism to reduce these defects. This dissertation develops a distributed positioning method using transmission signal overlapping region that called as cell-based positioning method in regular and irregular network structures. The node receives beacon frames from reference node(s) and performs simple operation to estimate its position. We discuss the characteristics of the proposed method and evaluate the performance in different environment. To improve the positioning accuracy, the radio model with multiple power-levels is applied in the proposed positioning method. In critical situations such as reference node failure, unstable radio transmission range and beacon collision, the proposed method still performs well. We believe that the results are useful for designing a simple, accurate, and low cost positioning system for wireless networks.

Abstract(in Chinese) i
Abstract(in English) iii
Acknowledgements iv
Contents v
List of Tables vii
List of Figures viii
1 Introduction 1
2 Related Works 5
2.1 Centralized positioning systems . . . . . . 5
2.2 Distributed positioning systems . . . . . . 7
3 Cell-based positioning method with single power-level of RNs 9
3.1 Positioning accuracy analysis in regular network structure . . . . . 14
3.1.1 Positioning accuracy for perfect reference nodes . . . . . . . 14
3.1.2 Positioning accuracy for unstable radiomodel . . . . . . . . 20
3.1.3 Positioning accuracy for imperfect reference nodes . . . . . . 21
3.1.4 Positioning accuracy for backup reference nodes . . . . . . . 22
3.2 Positioning accuracy analysis in irregular network structure . . . . . 29
3.2.1 Region-finding algorithm . . . . . . 31
3.2.2 Improving accuracy with power adjustment . . . . . . 33
3.3 Hardware implementation . . . . . . 39
4 Cell-based positioning method with multiple power-levels of RNs 45
4.1 Setting up the optimal power levels . . . . . . 47
4.2 Node Localization . . . . . . 50
4.3 Positioning accuracy formultiple power-levels of RNs . . . . . . 58
4.3.1 Reference nodes failure . . . . . . 59
4.3.2 Beacon frame loss . . . . . . 60
4.3.3 Unstable radio propagation model . . . . . . 62
4.3.4 Randomplacement of reference nodes . . . . . . 64
4.3.5 Comparison with other positioning methods . . . . . . 65
5 Conclusion 68
Bibliography 70
Vita 74
Publication List 75

[1] N. Davies, K. Cheverst, K. Mitchell, and A. Efrat, ”Using and determining location in a context-sensitive tour guide,” IEEE Computer Magazine, vol. 34, Aug. 2001 pp. 35-41.
[2] D. Cotroneo, S. Russo, F. Cornevilli, M. Ficco, and V. Vecchio, ”Implementing positioning services over an ubiquitous infrastructure,” Proceedings of the Second IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems, May 2004, pp. 14-18.
[3] I. F. Akyildiz,W. Su, Y. Sankarasubramaniam, and E. Cayirci, ”Wireless sensor networks: A survey,” Computer Network, vol. 38, pp. 393-422, 2002.
[4] M.Voddiek, L. Wiebking, P. Gulden, J. Wieghardt, C. Hoffmann, and P. Heide, ”Wireless local positioning,” IEEE Microwave Magazine, vol. 4, pp. 77-86, Dec. 2004.
[5] J. Hightower and G. Borriello, ”Location Systems for Ubiquitous Computing,” IEEE Computer, vol. 34, no. 8, pp. 57-66, Aug. 2001.
[6] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, ”Global Positioning System: Theory and Practice”, fifth edition , Springer Verlag, 2001.
[7] R. Want, A. Hopper, V. Falcao and J. Gibbons, ”The Active Badge Location System,” ACM Trans. on Information Systems, Jan. 1992, pp. 91-102.
[8] A. Harter, A. Hopper, P. Steggles, A. Ward, P. Webster, ”The Anatomy of a Context-Aware Application,” Proc. 5th Ann. Intl Conf. Mobile Computing and Networking (Mobicom 99), ACM Press, New York, 1999, pp. 59-68.
[9] N.B. Priyantha, A. Chakraborty, and H. Balakrishnan, ”The Cricket Location-Support System,” Proc. 6th Ann. Intl Conf. Mobile Computing and Networking (Mobicom 00), ACM Press, New York, 2000, pp. 32-43.
[10] P. Bahl and V. N. Padmanabhan, ”RADAR: An in-building RF-based user location and tracking system,” in Proc. IEEE Annu. Joint Conf. IEEE Computer and Communications Societies (INFOCOM’00), 2000, pp. 775-784.
[11] J. Hightower, R. Want, and G. Borriello, SpotON: An Indoor 3d Location Sensing Technology Based on RF Signal Strength, UWCSE 2000-02-02, Univ. Washington, Seattle, Feb. 2000.
[12] G. M. Djuknic, and R. E. Richton, ”Geolocation and assisted GPS,” IEEE Computer Magazine, vol. 34, pp. 123-125, Feb. 2001.
[13] L. Doherty, K. S. J. Pister, and L. E. Ghaoui, ”Convex position estimation in wireless sensor networks,” In Proc. of INFOCOM, vol. 3, pp. 1655-1663, 2001.
[14] H.-C. Chu and R.-H. Jan, ”A Cell-Based location-sensing method for wireless networks”, Wireless Communication and Mobile Computing, vol. 3, pp. 455- 463, 2003.
[15] S. Capkun, M. Hamdi, and J. P. Hubaux, ”GPS-free positioning in mobile ad hoc networks,” in Proc. 34th Annu. Hawaii Int. Conf. System Sciences, 2001, pp. 3481-3490.
[16] 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. Oct., 2000.
[17] T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher, ”Range-free localization schemes in large scale sensor networks,” in Proc ACM/IEEE 9th Annu. Int. Conf. Mobile Computing and Networking (MobiCom’03), 2003, pp. 81-95.
[18] F. Mondinelli and Z.M. Kovacs-Vajna, ”Self localizing sensor network architectures,” PIEEE Transactions on Instrumentation and Measurement, vol. 53, Apr. 2004, pp.277-283.
[19] Chong Liu, KuiWu, and Tian He, ”Sensor localization with Ring Overlapping based on Comparison of Received Signal Strength Indicator,” IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), Oct. 2004, pp. 516-518.
[20] D. Niculescu and B. Nath, ”Localized positioning in ad hoc networks,” Ad hoc Networks, vol. 1, Sep. 2003, pp. 2476-259.
[21] D. Niculescu and B. Nath, ”Ad hoc positioning system (APS) using AoA,” in Proc. IEEE Joint Conf. IEEE Computer Communications Societies (INFOCOM), Mar. 2003, pp. 1734-1743.
[22] W. Ruml, Y. Shang, and Y. Zhang, ”Location from mere connectivity,” in Proc. 4th ACMInt. Symp. Mobile Ad Hoc Networking and Computing (MobiHOC’ 03), 2003, pp. 201-212.
[23] K.-F. Ssu, C.-H. Ou, and H. C. Jiau, ”Localization with mobile anchor points in wireless sensor networks,” IEEE transactions on Vehicular Technology, vol. 54, no. 3, pp. 1187-1197, May 2005.
[24] H.-C. Chu and R.-H. Jan, ”A GPS-less, outdoor, self-positioning method for wireless sensor networks”, accepted and to appear in Journal of Ad Hoc Networks, 2006.
[25] T. S. Rappaport, ”Wireless communications, principles and practice,” 2nd edition, Prentice Hall, 2002.
[26] Network Simulator ns-2: Documentation, Chapter 18 Radio propagation models, http://www.isi.edu/nsnam/ns/ns-documentation.html, Nov. 2005.
[27] P. J. M. van Laarhoven and E. H. L. Aarts, ”Simulated annealing: theory and applications”, Dordrecht, D. Reidel, 1987.
[28] T.M. Mote, http://www.xbow.com/Products/productsdetails.aspx?sid=72.
[29] R.-H. Jan, H.-C. Chu, and Y.-F. Lee, ”Improving the accuracy of cell-based positioning for wireless networks”, Computer network, vol. 46, pp. 817-827, Dec. 20, 2004.