在本篇論文中，我們主要探討在無線感測網路中的定位技術。近年來由於感測網路相關研究蓬勃的發展，許多應用與通訊協定紛紛被提出，像是：感測網路涵蓋範圍的計算、目標物的偵測追蹤或是地理式路由等等…各種服務；然而，在這種種應用或是通訊協定實行之前，皆必須先取得感測節點的位置資訊，而這些節點一般會透過隨機部署的方式散播在監測的區域範圍中。因此，如何定位出這些隨機部署在監測區域的感測節點即為本篇論文所要解決的問題。
定位問題的解決方案一般可以分為兩種策略模式:Range-Based和Range-Free。Range-Based主要的作法是藉由測量節點與節點之間的距離或角度，透過所得到的距離資訊來定位節點本身所在的位置；然而，由於Range-Based的作法需要在每個節點上皆裝備額外的硬體設備（像是:聲納或是 GPS）以進行距離的測量，使得在實行上需要較高的硬體成本與消耗較高的能量於訊息的溝通。因此，在感測網路中的定位問題一般採取Range-Free的策略模式：藉由在感測節點中，部署少許的錨點（Anchor node），這些錨點能透過某些設備裝置（例如：GPS）定位出自己的位置。而其餘未知節點透過錨點所傳送的資訊，以簡單的演算法達成定位的目的，不需進一步透過取得距離資訊的方式來實行定位。
在本篇論文中提出了兩種以Range-Free策略模式下的定位方法：Localization by Likelihood Evaluation（LLE）和Localization by Likelihood Evaluation with Radio Frequency（LLE_RF）。LLE主要會利用附近two-hop範圍內的錨點資訊，先找出感測器所在的可能範圍，再透過信號衰減模型（path loss model）的協助預測節點最有可能坐落的位置，並且考量在有效地控制通訊與計算成本下，提供一套較符合實際無線通訊環境的演算法；而LLE_RF則是進一步利用信號強度的資訊，將其導入所定義的信號傳遞模型中，實行更為精確的定位。在我們最後的實驗結果中，可以顯現LLE和LLE_RF能相較於目前其他的定位方法在較低的通訊成本下，提供更為精確的定位效能；並且考量在外在環境因素的影響下，能相較於其他方法有較好的定位結果。

Localization is a fundamental and important issue for wireless sensor networks (WSNs). Many applications and protocols in WSNs are based on the assumption that sensors are aware of their locations. For example, coverage calculation in a WSN, geographic-based routing, event detection or target tracking. Sensing nodes are usually randomly deployed in the monitored area without location information. This thesis focuses on developing effective and accurate localization methods for sensor nodes in a random deployment.
Conventionally, localization methods can be categorized into Range-Based and Range-Free approaches. Range-Based approaches calculate location based on absolute point-to-point distance estimates or angle estimates. However, to estimate the distance or angle between two sensors, sonar or GPS must be installed in each node and higher energy consumption is required for information exchange. The cost is too high and not scalable for large WSNs. In contrast, Range-Free localization is cost-effective alternative. In such approaches, unknown nodes estimate their location using information from anchor nodes without distance estimations.
In this paper, two novel Range-Free based localization algorithms namely Localization by Likelihood Evaluation (LLE) and Localization by Likelihood Evaluation with Radio Frequency (LLE_RF) are proposed. LLE estimates the potential location region using the information from anchors within two-hops. It then finds the optimal location of the sensor by evaluating likelihood over the potential region. LLE_RF further takes advantage of the received signal strength to find a sensor’s location with better accuracy. Through extensive simulations, we show that the proposed schemes outperform many state of the art approaches in terms of localization accuracy and communication cost, and can much apply to the real environment with noise effect.

[1] A. Baggio and K. Langendoen. Monte Carlo localization for mobile wireless sensor networks. Ad Hoc Networks, 6(5):718–733, 2008.
[2] N. Bulusu, J. Heidemann, and D. Estrin. GPS-less low-cost outdoor localization for very small devices. IEEE personal communications, page 29, 2000.
[3] C.M. Chao, J.P. Sheu, and I.C. Chou. An adaptive quorum-based energy conserving protocol for IEEE 802.11 ad hoc networks. IEEE transactions on mobile computing, pages 560–570, 2006.
[4] J. Chen, S. Kher, and A. Somani. Distributed fault detection of wireless sensor networks. In Proceedings of the 2006 workshop on Dependability issues in wireless ad hoc networks and sensor networks, page 72. ACM, 2006.
[5] T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, and K.K. Saluja.Sensor deployment strategy for target detection. In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, page 48. ACM, 2002.
[6] L. Doherty, K.S.J. Pister, and L. El Ghaoui. Convex position estimation in wireless sensor networks. In IEEE INFOCOM, volume 3, pages 1655–1663. Citeseer, 2001.
[7] T. He, C. Huang, B.M. Blum, J.A. Stankovic, and T. Abdelzaher. Range-free localization schemes for large scale sensor networks. In Proceedings of the 9th annual international conference on Mobile computing and networking, pages 81–95. ACM, 2003.
[8] J. Hightower and G. Borriello. Location systems for ubiquitous computing. Computer, 34(8):57–66, 2001.
[9] X. Hong, K. Xu, and M. Gerla. Scalable routing protocols for mobile ad hoc networks. IEEE network, 16(4):11–21, 2002.
[10] S. Lederer, Y. Wang, and J. Gao. Connectivity-based localization of large scale sensor networks with complex shape. In Proceedings of IEEE INFOCOM, pages 789–797. Citeseer, 2008.
[11] D. Niculescu and B. Nath. Ad hoc positioning system (APS). GLOBECOM-NEW YORK-, 5:2926–2931, 2001.
[12] G.J. Pottie and W.J. Kaiser. Wireless integrated network sensors. Communications of the ACM, 43(5):51–58, 2000.
[13] N.B. Priyantha, A. Chakraborty, and H. Balakrishnan. The cricket location-support system. In Proceedings of the 6th annual international conference on Mobile computing and networking, pages 32–43. ACM, 2000.
[14] T.S. Rappaport et al. Wireless communications: principles and practice. Prentice Hall PTR New Jersey, 1996.
[15] A. Ryan, J. Tisdale, M. Godwin, D. Coatta, D. Nguyen, S. Spry, R. Sengupta, and J.K. Hedrick. Decentralized control of unmanned aerial vehicle collaborative sensing missions. In American Control Conference, 2007. ACC'07, pages 4672–4677, 2007.
[16] A. Savvides, C.C. Han, and M.B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In Proceedings of the 7th annual international conference on Mobile computing and networking, page 179. ACM, 2001.
[17] J.P. Sheu, P.C. Chen, and C.S. Hsu. A distributed localization scheme for wireless sensor networks with improved grid-scan and vector-based refinement. IEEE transactions on mobile computing, pages 1110–1123, 2008.
[18] A. Uchiyama, S. Fujii, K. Maeda, T. Umedu, H. Yamaguchi, and T. Higashino. Ad-hoc localization in urban district. In IEEE INFOCOM 2007. 26th IEEE International Conference on Computer Communications, pages 2306–2310, 2007.
[19] K.C. Wang and P. Ramanathan. Collaborative sensing using sensors of uncoordinated mobility. Distributed Computing in Sensor Systems, pages 293–306, 2005.
[20] Y. Wang, S. Lederer, and J. Gao. Connectivity-based sensor network localization with incremental delaunay refinement method. In Proc. of the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09). Citeseer, 2009.
[21] Y. Xu, J. Heidemann, and D. Estrin. Geography-informed energy conservation for ad hoc routing. In Proceedings of the 7th annual international conference on Mobile computing and networking, page 84.ACM, 2001.
[22] T. Yan, T. He, and J.A. Stankovic. Differentiated surveillance for sensor networks. In Proceedings of the 1st international conference on Embedded networked sensor systems, page 62. ACM, 2003.
[23] W. Ye, J. Heidemann, and D. Estrin. An energy-efficient MAC protocol for wireless sensor networks. In IEEE INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, pages 1567–1576, 2002.
[24] K. Yedavalli, B. Krishnamachari, S. Ravula, and B. Srinivasan.Ecolocation: a sequence based technique for RF localization in wireless sensor networks. In Proceedings of the 4th international symposium on Information processing in sensor networks, page 38. IEEE Press, 2005.
[25] Z. Zhou, J.H. Cui, and A. Bagtzoglou. Scalable localization with mobility prediction for underwater sensor networks. In Proceedings of IEEE INFOCOM'08, Mini-Conference, pages 13–18. Citeseer.
[26] Y. Zou and K. Chakrabarty. Sensor deployment and target localization in distributed sensor networks. ACM Transactions on Embedded Computing Systems (TECS), 3(1):61–91, 2004.
[27] J.Antol, P. Calhoun, J. Flick, G.A. Hajos, R. Kolacinske, D. Minton, R. Owens and Jennifer Parker. Low Cost Mars Surface Exploration: The Mars Tumbleweed. NASA Langley Research. Center. NASA/TM-2003-212411, 2003.