無線感測網路(Wireless Sensor Network, WSN)是由數個集感測、通訊與計算能力於一身的感測器組成，廣泛地應用在諸多領域中，然而大部分的應用皆需要配合感測器的位置，感測所得的資料才具有價值。本研究探討的感測網路定位(Sensor Network Localization, SNL)問題旨在利用軟體的計算能力降低實體的定位成本，亦即不在所有感測器裝備定位元件，而是僅使用少數位置已知的錨點(Anchor)感測器，透過感測器之間的距離資訊來自動定位其它位置未知的流點(Sensor)感測器，當大規模隨機佈署感測器時，如何快速且準確地定位感測器即是一大挑戰。文獻顯示當前SNL問題的兩大瓶頸為大規模WSN的定位以及使用帶誤差(Noise)的距離資訊來定位，又因感測器的訊號範圍有限且感測器間距離的量測通常不精準，在距離資訊不足且帶有誤差的情況下，當感測網路含有數百甚至數千個感測器時，其求解的困難度將大幅增加，而誤差也會在求解過程中被放大，以致求解時往往難以兼顧速度與準確度。
可定位程度(Localizability)是求解SNL的基礎，由於SNL的求解演算法通常僅能應用於可定位的WSN，可定位程度的檢驗有助於減少無謂的計算與資源消耗，並且可加強WSN的控制與管理，例如我們可針對不可定位的WSN加強感測器的佈署，提高其可定位程度。本研究首先探討文獻中可定位網路的條件與特性，發展一個檢驗可定位程度的演算法Loc_Idx，藉此演算法可判定一個WSN中可定位流點的比例，並將流點分為三類，依此分類能更有效的評比定位演算法的效能。
SNL問題可規劃成一個無限制式的非線性最佳化問題，為能在短時間內精確定位大規模的WSN，本研究提出的定位演算法Grad_MSA以梯度法(Gradient Method)為基礎，對較易定位的流點以幾何性質與感測器連結性(Connectivity)構成的多邊定位法(Multilateration)來快速地定位；而對於較難定位的流點，使用最短路徑補強未知的距離資訊，並利用感測器連結的合理性建構區域調整機制，將流點調整到合理的位置，在求解過程中將部分有可靠定位結果的流點當作錨點來輔助其它流點定位，如此重複這些步驟來收斂各流點的定位。
本研究亦進一步探討極少錨點或無錨點(Anchor-free)感測網路的定位問題，發展無錨點網路的定位演算法不但有助於解決極少錨點的SNL問題，同時也可延伸SNL的解法到其它領域，例如分子構形(Molecular Conformation)問題。本研究提出的無錨點定位演算法Grad_SS係以種子感測器充當WSN中的錨點，而後以Grad_MSA求解，其中種子感測器的選擇攸關無錨點定位的成效，本研究基於貪婪法的精神，提出最大度數法與最大體積法等二種方法來選取種子感測器。
實驗結果顯示，Grad_MSA中的迭代多邊定位法、最短路徑擴增人工節線與區域調整機制同時使用時能發揮綜效，並針對感測網路中各種不同定位難度的節點定位，其中尤以迭代多邊定位法的成效最顯著，當節線與錨點充足時能快速且準確地定位。與Kim et al. (2009)使用半正定規劃(Semidefinite Programming)的SFSDP演算法比較，對於任何可定位程度的網路，本研究的Grad_MSA演算法均能達到較快且較準確的定位，且對於同規模的網路，隨著網路的可定位程度愈高，運算時間就愈短；而定位無錨點的網路時，Grad_SS演算法也擁有較SFSDP良好的定位精準度，且運算時間隨著網路規模的增長速度也較慢，並能求解三維空間中的分子構形問題，對於含有一萬餘個節點的大規模網路，Grad_SS能在3分鐘內達到相當精準的定位效果。
本研究由SNL問題中發現更多仍待解決的問題，其中網路的定位程度檢驗仍處於萌芽階段，發展一個能檢驗節點可否定位的演算法，除了有上述的益處以外，還能用以開發可靠的標竿測試資料，並能輔助無錨點定位演算法選擇種子感測器。此外，SNL問題屬於歐氏距離幾何問題(Euclidean Distance Geometry Problems)中的一環，將SNL解法一般化將有助於應用於更多相似的問題，因此無錨點的定位演算法值得繼續發展。

A Wireless Sensor Network (WSN) consists of numerous sensors which monitor physical conditions and communicate in an ad-hoc fashion. The data collected by the sensors are usually meaningful when coupled with their locations. Since equipping GPS modules is not cost effective for localizing sensors, the Sensor Network Localization (SNL) problem is aroused to localize sensors based on few known-position anchors and internode distances, and can be formulated as an unconstrained nonlinear optimization problem. Related works show that current challenges in SNL problem are error propagation and low computational efficiency, caused by large scale network and localization failure due to noisy distances.
The localizability test, as a tool to measure the difficulty for a SNL problem, can help avoid unnecessary computation in sensor localization and improve the deployment and control of WSN. The localizability for a sensor network is closely related to its global rigidity, but is not well-defined. To test the network localizability, we propose algorithm Loc_Idx to determine the localizability of each sensor, and accordingly classify sensors into three types, depending on their difficulties to be localized. Next, we propose a novel localization algorithm named Grad_MSA to localize sensors of different types by different methods. In particular, we first apply an iterative multilateration mechanism to localize those easily localizable sensors efficiently with small errors, and then localize the rest of sensors by a gradient descent mechanism based on a nonlinear mathematical programming model. Heuristics that use shortest path and local adjustment mechanisms are also applied to refine solutions.
Moreover, an anchor-free SNL problem is studied, which is beneficial for solving WSN containing unhelpful anchors and can generalize SNL algorithms to solve related problems such as graph realization or molecular conformation. We propose algorithm Grad_SS to localize anchor-free WSN by firstly selecting seed sensors, which are regarded as anchors in the process, localizing the rest of sensors with respect to the seed sensors, and then conducting linear coordinate transformation to calculate their original coordinates.
Numerical experiments show each heuristics in Grad_MSA takes effect to improve the solution, and among them the iterative multilateration mechanism dominates high accuracy of localization. Compared with SFSDP (Kim et al. 2009) which solves a SNL problem by Semidefinite Programming, Grad_MSA performs better in both accuracy and running time of localization. For networks comprising the same number of nodes, the accuracy and speed of localization is positively related to its localizability. For solving an anchor-free SNL problem, several protein data are tested by Grad_SS and SFSDP with the results indicating the former performs much better than the other. It also reveals that Grad_MSA is able to localize large-scale network (containing more than 10,000 nodes) in 3D space within 3 minutes, and Grad_SS manages to solve the molecular conformation problem.
Several research topics are suggested for further investigation. The localizability test remains as an open problem since there is still no efficient method to identify all localizable sensors. With a robust algorithm of localizability test, we can generate SNL benchmark test cases of different localizabilities, so that SNL algorithms can be compared on a fair basis. Localizability tests can also help select optimal seed sensors for solving anchor-free SNL problems, which may be extended for solving other Euclidean distance geometry problems.

Alfakih, A. Y., A. Khandani & H. Wolkowicz (1999), "Solving Euclidean Distance Matrix Completion Problems Via Semidefinite Programming," Computational Optimization and Applications, 12 (1-3), pp.13-30.
Armijo, L. (1966), "Minimization of Functions Having Lipschitz Continuous First Partial Derivatives," Pacific Journal of Mathematics, 16 (1), pp.1-3.
Aspnes, J., D. Goldenberg & Y. R. Yang (2004), "On the Computational Complexity of Sensor Network Localization," Algorithmic Aspects of Wireless Sensor Networks, Berlin Heidelberg: Springer, 3121, pp.32-44.
Berg, A. R. & T. Jordán (2003), "Algorithms for Graph Rigidity and Scene Analysis," Algorithms - Esa 2003, Berlin Heidelberg: Springer, 2832, pp.78-89.
Berg, A. R. & T. Jordán (2003), "A Proof of Connelly's Conjecture on 3-Connected Circuits of the Rigidity Matroid," Journal of Combinatorial Theory Series B, 88 (1), pp.77-97.
Biswas, P., K.-C. Toh & Y. Ye (2008), "A Distributed Sdp Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation," SIAM Journal on Scientific Computing, 30 (3), pp.1251-1277.
Biswas, P. & Y. Ye (2004), "Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization," Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks, Berkeley, CA, ACM, pp.46-54.
Biswas, P. & Y. Ye (2006), "A Distributed Method for Solving Semidefinite Programs Arising from Ad Hoc Wireless Sensor Network Localization," Multiscale Optimization Methods and Applications, US: Springer, 82, pp.69-84.
Borg, I. & P. J. F. Groenen (2005), Modern Multidimensional Scaling, New York: Springer.
Clark, B. N., C. J. Colbourn & D. S. Johnson (1990), "Unit Disk Graphs," Discrete Mathematics, 86 (1–3), pp.165-177.
Connelly, R. (1991), "On Generic Global Rigidity," Applied Geometry and Discrete Mathematics, Providence, RI: American Mathematical Society, 4, pp.147-155.
Connelly, R. (2005), "Generic Global Rigidity," Discrete and Computational Geometry, 33 (4), pp.549-563.
Cota-Ruiz, J., J.-G. Rosiles, E. Sifuentes & P. Rivas-Perea (2012), "A Low-Complexity Geometric Bilateration Method for Localization in Wireless Sensor Networks and Its Comparison with Least-Squares Methods," Sensors, 12 (1), pp.839-862.
Ding, Y., L. Du, T. Yang & Y. Sun (2009), "Distributed Localization Algorithm for Wireless Sensor Network Based on Multidimensional Scaling and the Shortest Path Distance Correction," Transactions of Tianjin University, 15 (4), pp.237-244.
Ding, Y., N. Krislock, J. Qian & H. Wolkowicz (2010), "Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization," Optimization and Engineering, 11 (1), pp.45-66.
Doherty, L., K. S. J. Pister & L. El Ghaoui (2001), "Convex Position Estimation in Wireless Sensor Networks," INFOCOM 2001 Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, 3, Anchorage, AK, April 2001, pp.1655-1663.
Eren, T., D. K. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. O. Anderson & P. N. Belhumeur (2004), "Rigidity, Computation, and Randomization in Network Localization," INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, 4, March 2004, pp.2673-2684.
Hendrickson, B. (1992), "Conditions for Unique Graph Realizations," SIAM Journal on Computing, 21 (1), pp.65-84.
Jackson, B. & T. Jordán (2005), "Connected Rigidity Matroids and Unique Realizations of Graphs," Journal of Combinatorial Theory, Series B, 94 (1), pp.1-29.
Johnson, D. B. (1977), "Efficient Algorithms for Shortest Paths in Sparse Networks," Journal of the ACM, 24 (1), pp.1-13.
Kim, S., M. Kojima & H. Waki (2009), "Exploiting Sparsity in Sdp Relaxation for Sensor Network Localization," SIAM Journal on Optimization, 20 (1), pp.192-215.
Kim, S., M. Kojima & M. Yamashita (2012), "Parallel Implementation of Successive Sparse Sdp Relaxations for Large-Scale Euclidean Distance Geometry Problems," Department of Mathematical and Computing Sciences Tokyo Institute of Technology, B-470.
Laman, G. (1970), "On Graphs and Rigidity of Plane Skeletal Structures," Journal of Engineering Mathematics, 4 (4), pp.331-340.
Leung, N.-H. Z. & K.-C. Toh (2009), "An Sdp-Based Divide-and-Conquer Algorithm for Large-Scale Noisy Anchor-Free Graph Realization," SIAM Journal on Scientific Computing, 31 (6), pp.4351-4372.
Li, X., B. Hua, Y. Shang, Y. Guo & L. Yue (2007), "Bilateration: An Attack-Resistant Localization Algorithm of Wireless Sensor Network," Embedded and Ubiquitous Computing, Berlin Heidelberg: Springer, 4808, pp.321-332.
Liu, Y. & Z. Yang (2011), Location, Localization, and Localizability: Location-Awareness Technology for Wireless Networks, New York: Springer.
Locher, T., P. Rickenbach & R. Wattenhofer (2008), "Sensor Networks Continue to Puzzle: Selected Open Problems," Proceedings of the 9th International Conference on Distributed Computing and Networking, Kolkata, India, Springer-Verlag, pp.25-38.
Mao, G., B. Fidan & B. D. O. Anderson (2007), "Wireless Sensor Betwork Localization Techniques," Computer Networks, 51 (10), pp.2529-2553.
Moore, D., J. Leonard, D. Rus & S. Teller (2004), "Robust Distributed Network Localization with Noisy Range Measurements," Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, MD, USA, ACM, pp.50-61.
Niculescu, D. & B. Nath (2003), "DV Based Positioning in Ad Hoc Networks," Telecommunication Systems, 22 (1), pp.267-280.
Savarese, C., J. M. Rabaey & K. Langendoen (2002), "Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks," Proceedings of the General Track of the Annual Conference on USENIX Annual Technical Conference, USENIX Association, pp.317-327.
Savvides, A., C.-C. Han & M. B. Strivastava (2001), "Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors," Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, Rome, Italy, ACM, pp.166-179.
Shang , Y., W. Ruml, Y. Zhang & M. Fromherz (2004), "Localization from Connectivity in Sensor Networks," IEEE Transactions on Parallel and Distributed Systems, 15 (11), pp.961-974.
Yang, Z. (2010), Localization and Localizability in Sensor and Ad-Hoc Networks, Published Doctoral Dissertation, The Hong Kong University of Science and Technology, Computer Science and Engineering.
Zhu, Z., A. M.-C. So & Y. Ye (2010), "Universal Rigidity: Towards Accurate and Efficient Localization of Wireless Networks," INFOCOM 2010 Proceedings of the 29th Conference on Information Communications, San Diego, CA, March 2010, pp.1-9.