臺灣博碩士論文加值系統

近來科學技術的進展已經使得發展能透過短距離的無線鏈結之低廉、低耗能且多重功能的大量感測器之分散式感測網路計畫變得可行，同時這樣的網路也已被廣泛發展到各種應用中；其應用的領域諸如健康照護監視、居家安全及軍事戰場的應用。但對於廣闊無線感測網路而言，位置仍然是真實生活應用中一項實質的挑戰。即使現今很多的解決方案都已相繼提出，但往往卻因設備和額外硬體的需求致費用太高或是無法因應實際環境要求而致較差的準確性或不可行性，因此一般說來，極少數的解決方案是可真正落實於實際應用中的。
一般來說，測距法(ranging estimation)在很多無線感測網路的位置演算法中是可行且常用的。依據他們運算結構的方式，位置演算法可大略分為兩類:一為集中式的演算法，而另一為分散式的演算法。在本篇論文中，我們只專注於分散式演算法中的一群名為邊界盒(bounding box algorithm)演算法，且以其中的CPE演算法(14)為比較的參照演算法，並提出改良其感測器位置估測準確性的策略。在邊界盒(bounding box algorithm)演算法中，假設每一個感測器都位於他所有beacon node 的 邊界盒 (bounding box)相交集合中，則感測器的位置就以此相交集合的最後邊界盒 (bounding box)的中心點位置作為估測值。如此隨便取值的結果，往往導致誤差太大，效能較低。有鑑於此，本研究針對此隨便取值的缺點提出改良方案，以數學上平面幾何的觀點出發，利用平面上一點到三定點的最短距離和為最小的點即為此三定點所構成的三角形的費馬點(Fermat point)且經證明此點即為三角形的重心位置的特性，我們提出了FPDLE algorithm的策略研究，經模擬結果顯示，FPDLE algorithm在影響效能因素的分析下(感測器的密度、beacon node 的比率及查詢的回覆率)有三項重要的結果 (1)當感測器數量低於150個時，平均誤差確實可隨著感測器數量增加而快速減少，但當數量超過170 時，平均誤差保持在1%範圍內，因此數量增加對平均誤差的影響，就不太明顯 。(2)當beacon node的數量低於60時，增加beacon node數，確實可降低平均誤差。但其數超過60後，這個因素的影響又變得不太明顯。(3)在回覆率比較上，當beacon node數超過55後，位置估測的準確度將近可達90%。就演算法的角度看來，FPDLE演算法的數學算式簡單是不需藉由套裝軟體像MATLAB、Maple V等的使用協助,模擬結果確實也證明了較CPE演算法在位置的估測上執行得準確性更高且效能更好。
由於本篇論文的模擬環境，我們做了一些較理想的設定，要在真正Tinyos platform上執行，仍有些因素要克服，這也是我們後續要努力的方向。但本篇論文最主要的目地—就是從數學平面幾何費馬點的觀點，提供另一種相較於bounding box algorithm準確性較高且效能較好的Ranged-based algorithm—FPDLE algorithm 來估測感測器的位置。

Recent technological advances have made it possible to develop distributed sensor networks consisting of a large number of low-cost, low -power, and multi-functional sensor nodes that communicate in short distances through wireless links. Such sensor networks have been proposed for various applications such as health monitoring, home and military operations. But localization for wide area wireless sensor networks has been still a practical challenge for real applications. Although today many solutions have been proposed, few of them can be used in real applications due to their high cost (requirements on extra hardware), low accuracy or infeasibility due to practical issues.

Generally speaking, range estimation is essential in many sensor network localization algorithms. Based on their computational organization, localization algorithms are divided into two classes: centralized localization algorithms and distributed localization algorithms. In this paper, we focus on one of groups of distributed localizations algorithms: beacon-based distributed algorithms (bounding box algorithm named CPE algorithm) and make some improvements on the accuracy of location estimation of a sensor node. In bounding box algorithm each node assumes that it lies within the intersection of its beacons’ bounding boxes. And the initial position estimate of a sensor node is taken to be as the center of the bounding box. It results in much large errors and bad performances because of a random guess. Just for these reasons, we make some improvements on these drawbacks. In the sight of the shortest path problem in the plane geometric, we take the characteristic of Fermat point：Fermat point is that the point which minimizes the sum of the distances from the three vertices inside a triangle ,and this point is indeed the triangle's center of gravity. We propose a connectivity based RF localization, called Fermat-point distributed location estimation algorithm (FPDLE) utilizing the Fermat point of the triangle for an irregular wireless sensor network. After simulation operation, we obtain three results: (1) when the number of total nodes is below 150, the mean error decreases fast as the node density increases, up to the number of total nodes exceeds 170, the mean error keep below 1% besides the impact of the node density on the mean error is not broad.(2) When the number of beacon nodes is below 60,normal nodes do not have enough accurate beacon nodes to help them estimate their location, so the mean error could be reduced by means of increasing the number of beacon nodes. But the number of beacon nodes exceeds 60, the mean error only vary a little such that the impact on the number of beacon nodes is not broad.(3) our FPDLE algorithm has an acceptable performance when the number of beacon node exceeds 55.Therefore FPDLE algorithm performs more accuracy and efficiency that improves on bounding box of the connectivity based RF localization.

In this thesis, for simplicity, we make some assumptions such as the network is static and all the sensor nodes have the same transmission range which are assumed to be round-shaped with a uniform radius within the sensing area. But it is nonconformity with the real world. So there are a lot of existed challenges to overcome when we perform on real Tinyos platform. We will make researches on this theme in future works. This thesis bears a novel thinking from the aspect based on Fermat-point of plane geometry and proposes a named FPDLE algorithm which is more accuracy and efficiency that improves on bounding box algorithm(CPE ) related to location estimation of a sensor node. This conclusion is also a chief contribution for this thesis.

摘要..... ..........................................I
Abstract...........................................III
Table of Contents..................................V
List of Figures....................................VII
List of Tables............................ ........VIII
Chapter 1 Introduction................................1
1.1 Sensor Networks Overviews....... .................1
1.2 Sensor Networks Characteristics...................3
1.2.1 Design Factors....... .......................... 5
1.2.2 Challenges......................................8
1.3 Sensor Networks Applications......................9
1.4 Organization of the Thesis........................10
Chapter 2 Related Work................................12
2.1 Range-Based Schemes...............................13
2.1.1 Receiver Signal Strength Indicator (RSSI).......13
2.1.2 Time Difference of Arrival (TDoA)...............14
2.1.3 Angle of Arrival (AoA)..........................15
2.2 Range-Free Schemes................................16
Chapter 3 Fermat Point Distributed Location Estimation Algorithm .............................................17
3.1 Fermat-Point Distributed Location Estimation Algorithm .............................................18
3.2 Related to Mathematical Computation...............20
3.2.1 The Coordinate of the Intersection Points of Two Circles on a Plane ....................................20
3.2.2 A Survey on the Fermat Point....................21
3.3 Decide the Vertices Composed a Triangle...........26
3.4 Reduce the Size of the Triangle...................28
3.5 Errors............................................30
Chapter 4 Simulation Results.........................31
4.1 Impact on the Density of Sensor Nodes.............34
4.2 Impact on the Ratio of Beacon Nodes...............35
4.3 Response Rate.....................................37
Chapter 5 Conclusion and Future Work..................38
References............................................41

[1] X. Ji and H. Zha, ”Sensor Positioning inWireless Ad- hoc Sensor Networks using Multidimensional Scaling,” Proceedings of 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004),pp 33March 2004.
[2] D. N. and B. Nath, ”Ad Hoc Positioning System (APS),” Proceeding of IEEE Global Telecommunications Conference(Globecom 2001), pp. 34 2926-2931, vol. 1,November 2001.
[3] D. N. and B. N., ”Localized positioning in ad hoc networks Ad Hoc Networks,” Proceedings of 1st IEEE International Workshop on Sensor Network Protocols and Applications (SNPA 2003),pp. 247-259, May 2003.
[4] T. Adebutu, L. Sacks, and Ian Marshall, ”Simple Position Estimation for Wireless Sensor Networks,” Proceedings of London Communications Symposium (LCS 2003),September 2003.
[5] F. M.i and Z. M. Kovacs Vajna, ”Self Localizing Sensor Network Architectures,”Proceedings of the 19th IEEE Instrumentation and Measurement TechnologyConference, vol. 1, pp. 823-828, May 2002.
[6] Neal Patwari, Robert J. O’Dea, and YanweiWang, ”Relative Location inWireless Networks,”Proceedings of IEEE Vehicular Technology Conference (VTC), pp. 1149-1153, Rhodes, Greece, May 2001.
[7] Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, and Kristofer Pister, ”System architecture directions for networked sensors,” Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), pp. 93-104, Cambridge, MA, November 2000.
[8] Seapahn M. and Sasha S. and Vahag Karayan and MiodragPotkonjak, ”Localized Algorithms in Wireless Ad-Hoc Networks: Location Discovery and Sensor Exposure,” Proceedings of MobiHoc01, pp. 106-116, October 2001.
[9] Nissanka B. Priyantha, Anit Chakraborty, and Hari Balakrishnan, ”The CricketLocation-Support System,” Proceedings of 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), pp. 32-43, Boston, MA,August 2000.
[10] Joe Albowicz, Alvin Chen, and Lixia Zhang, ”Recursive Position Estimation in SensorNetworks,” Proceedings of Ninth IEEE International Conference on Network Protocols(ICNP 2001), pp. 35-41, November 2001.
[11] Jeffrey Hightower and Gaetano Borriello, ”Location Systems for Ubiquitous Computing, in IEEE Computer, vol. 34, pp. 57-66, August 2001.
[12] Nirupama Bulusu, John Heidemann, and Deborah Estrin, ”GPS-less Low Cost Outdoor Localization For Very Small Devices,” Proceedings of the IEEE Personal Communications Magazine, vol. 7, no. 5, pp. 28-34, October 2000.
[13] Srdan Capkun, Maher Hamdi, and Jean-Pierre HubauxInstitute, ”GPS-free positioning in mobile ad-hoc networks,” Proceedings of the 34th Annual Hawaii International Conference on System Science (HICSS’01), pp. 3481-3490, January 2001.
[14] Lance Doherty, Kristofer S. J. Pister, Laurent El Ghaoui, ”Convex Position Estimation in Wireless Sensor Networks,” Proceedings of 20th Annual Joint Conference of the IEEE 32 Computer and Communications Societies (INFOCOM 2001), vol. 3, pp. 1655-1663, April 2001.
[15] Aram Galstyan, Bhaskar Krishnamachari, Sundeep Pattem, and Kristina Lerman, ”Distributed Online Localization in Sensor Networks Using a Moving Target,” Proceedings of IEEE/ACM 3rd International Symposium on Information Processing in Sensor Networks (IPSN 2004), pp. 61-70, Berkeley, CA, April 2004.
[16] Tian He, Chengdu Huang, Brian M. Blum, John A. Stankovic, and Tarek abdelzher,
”Range-Free Localization Schemes for Large Scale Sensor Networks,” Proceedings of 9th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2003), pp. 81-95, September 2003.
[17] P. Bahl and V. N. Padmanabhan, ”RADAR: An In-Building RF-based User Location and Tracking System,” Proceedings of 19th Annual Joint Conference of theIEEE Computer and Communications Societies (INFOCOM 2000), vol. 2, pp. 775-784, Tel Aviv, Israel, March 2000.
[18] Yi Shang, W. Ruml, Ying Zhang, and Markus P. J. Fromherz, ”Localization from Mere Connectivity,” Proceedings of 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2003), pp. 201-212, June 2003.
[19] Jeffrey Hightower, RoyWant, and Gaetano Borriello, ”SpotON: An Indoor 3D Location Sensing Technology Based on RF Signal Strength,” University of Washington, Department of Computer Science and Engineering, Seattle, WA February 2000.
[20] Dragos Niculescu and Badri Nath, ”Ad hoc positioning system (APS) using AOA,”
Proceedings of 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003) , pp. 1734-1743, vol. 22, Mar 2003.
[21] Krishna Kant Chintalapudi, Amit Dhariwal, Ramesh Govindan, and Gaurav Sukhatme, ”Ad-Hoc Localization Using Ranging and Sectoring,” Proceedings of 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), March 2004.
[22] Teng Li, Anthony Ekpenyong, Yih-Fang Huang, ”A Location System Using Asynchronous Distributed Sensors,” Proceedings of 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), March 2004.
[23] Asis Nasipuri and Kai Li, ”A Directionality based Location Discovery Scheme for
Wireless Sensor Networks,” Proceedings of the first ACM international conference onWireless sensor networks and applications(WSNA 2002), pp. 105-111, September 2002.
[24] Dragos Niculescu and Badri Nath, ”DV Based Positioning in Ad Hoc Networks,” Journal of Telecommunication Systems, pp. 267-280, vol. 22, January-April 2003.
[25] Neal Patwari and Alfred O. Hero III, ”Location Estimation Accuracy in Wireless Sensor Networks,” Proceedings of IEEE Asilomar Conference on Signals and Systems 2002, Pacific Grove, California, November 2002.
[26] Dragan Petrovic, Rahul C. Shah, Kannan Ramchandran, and Jan Rabaey, ”Data Funneling: Routing with aggregation and compression for wireless sensor networks,” IEEE Sensor Network Protocols and Applications (SNPA), pp. 156-162, Anchorage, May 2003.
[27] Ananth Rao, Sylvia Ratnasamy, Christos Papadimitriou, Scott Shenker, and Ion Stoica,”Geographic Routing without Location Information, ” Proceedings of 9th Annual35 ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2003), pp. 96-108, September 2003.
[28] Saikat Ray, Rachanee Ungrangsi, Francesco De Pellegrini, Ari Trachtenberg, and David Starobinski, ”Robust Location Detection in Emergency Sensor Networks,” Proceedings of 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), vol. 2, pp. 1044-1053, March-April 2003.
[29] Yi Shang and Wheeler Ruml, ”Improved MDS-Based Localization,” Proceedings of
23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), March 2004.
[30] D.Steere, A. Baptista, Dylan McNamee, Calton Pu, and Jonathan Walpole,”Research challenges in environmental observation and forecasting systems,” Proceedings of 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), pages 292-299, Boston, MA, August 2000.
[31] Yi Zou and K. C., ”Sensor Deployment and Target Localization Based on Virtual Forces,” Proceedings of 22nd Annual Joint Conference of the IEEE Computerand Communications Societies (INFOCOM2003), pp. 1293-1303, March-April 2003.
[32] Philip L., Nelson L., MattWelsh, and David Culler, ”TOSSIM: Accurate and Scalable Simulation of Entire TinyOS Applications”, Proceedings of the First ACM Conference on Embeedded Networked Sensor Syatems (SenSys 2003), Los Angeles, CA, Noverber 2003.
[33] ”TinyOS Community Forum”, http://webs.cs.berkeley.edu/tos/36.
[34] D. Krivitski, Assaf Schuster and Ran Wolff,” A Local Facility Location Algorithm for Sensor Networks”, International Conference on Distributed Computing in Sensor Systems, June 2005.
[35] Wang, G.; Cao, G.; Porta, T.L.and Zhang, W., “Sensor relocation in mobile sensor networks”, IEEE Infocom, March 2005.
[36] K.W., A. W., C. K., F. J and D. C., ‘”The Effects of Ranging Noise on Multi-hop Localization: An Empirical Study”, Fourth International Conference on Information Processing in Sensor Networks (IPSN '05), April 2005.
[37] D. Liu, P. N and W. D., “Attack-Resistant Location Estimation in Sensor Networks”, Fourth International Conference on Information Processing in Sensor Networks (IPSN '05), April 2005.
[38] J. B., J. G., and A. J.,” Localization and Routing in Sensor Networks by Local angle Information”, ACM Mobihoc, May 2005.
[39] K. Y., B. K., S. R and B.S., “Ecolocation: A Technique for RF Based Localization in Wireless Sensor Networks” Fourth International Conference on Information Processing in Sensor Networks (IPSN '05), April 2005.
[40] L. L., S. C. and R. P.” ROPE: Robust Position Estimation in Wireless Sensor Networks”, Fourth International Conference on Information Processing in Sensor Networks (IPSN '05), April 2005.
[41] H. L.; H. and J.C., “Localization for anisotropic sensor networks”, IEEE Infocom, March 2005.
[42] C., A.; C., S.; De, S. “and Urpi, A, “GPS free coordinate assignment and routing in wireless sensor networks,” IEEE Infocom, March 2005.
[43] L. F, W. Du and P. N, “A beacon-less location discovery scheme for wireless sensor networks,” IEEE Infocom, March 2005.
[44] P., N.B.; B., H.; D and E.D, “Teller, S., Mobile-assisted localization in wireless sensor networks,” IEEE Infocom, March 2005.
[45] R and S., “Precise Localization in Coarse-Grained Localization Algorithms Through Local Learning,” September 2005.
[46] Caruso, A.; Chessa, S.; De, S.; Urpi, A., GPS free coordinate assignment and routing in wireless sensor networks, IEEE Infocom, March 2005.
[47] S., S., V., and M., Localized Algorithms In Wireless Ad-Hoc Networks: Location Discovery adn Sensor Exposure, MobiHoc, October 2001 S. Meguerdichian, S. Slijepcevic, V. Karayan, and M. Potkonjak, Localized Algorithms In Wireless Ad-Hoc Networks: Location Discovery adn Sensor Exposure, MobiHoc, October 2001.