無線感測網路在應用上相當的廣泛, 而感測節點的位置資訊, 是大多數應用的基礎,
也是重要的議題。 有些研究方法是使用全球定位系統 (Global Positioning System) 裝
置在某些特定的感測節點上, 利用 GPS 所得之的位置和節點之間的關係, 推算其它感測
節點的位置。 由於此種方法會增加感測節點的成本, 且違反感測節點需具備體積小的特
性要求, 因此並非是一個很好的方法。 所以, 如何在符合無線感測網路特性的條件下, 找
出感測節點位置, 已經成為一個重要的議題。
由於在大多數的情形之下, 感測節點僅需知道彼此之間的相關位置, 即可進行感測網
路定位的相關應用。 在本篇論文中, 我們提出一個簡單的演算法, 可以求得感測節點之間
的相對位置, 並實用於感測網路中, 如此既可避免受到環境的不確定性的干擾, 亦可兼顧
到實用價值。 這也是無已知座標節點存在的定位演算法漸受注目的原因。
相對於一般具有已知座標節點存在的定位演算法, 無已知座標節點存在的定位方式
可以說是還在起步階段。 目前所存在的相關演算法皆是以量測距離為主, 藉以估測出感
測節點的相關位置。 在本篇論文中,我們進一步提出一種使用節點之間通訊關係以及Re-
ceived Signal Strength Indicator(RSSI) 距離估測機制的技術, 藉由這兩種方式的整
合, 最後推估出感測節點之間的相對位置關係, 以企圖得到更理想的結果, 再利用一些實
驗的數據說明演算法所得到的效能。

It is often useful to know the geographic positions of nodes in a commu-
nications network, but adding GPS receivers or other sophisticated sensors to
every node can be expensive. We present an algorithm that uses connectivity
information: who is within communications range of whom, to derive the rel-
ative relation of the nodes in the network. The method can take advantage of
additional information, such relative neighbourhood graph, if it is available.
Di?erent fromordinary position algorithmwith nodes of known coordinates,
the position method without sensors of known nodal coordinates is just in its
beginning status. So far as we know, the existed related algorithms all focus on
measuring distance to estimate relative relation of sensors. In this thesis, we
propose a technique that uses RSS and Voronoi diagram to derive the relative
relation of the nodes in the network. The integration of these two methods is to
estimate connectivity between sensor nodes. We try to get a more ideal result.
All details are explained on following pages.

[1] 王友群、 胡君琪、 曾煜棋. 感測網路將走入人類日常生活, volume 116. 通訊雜誌,
September 2003.
[2] CHEE-YEE CHONG and SRIKANTA P. KUMAR. Sensor Networks: Evo-
lution, Opportunities, and Challenges. Proceedings of the IEEE, 91(8):1247–
1256, August 2003.
[3] Tian He, Chengdu Huang, Brian M. Blum, John A. Stankovic, and Tarek
Abdelzaher. Range-Free Localization Schemes for Large Scale Sensor Net-
works. Proceedings of the ninth Annual International Conference on Mobile
Computing and Networking (MbilCom 2003), pages 81–95, September 2003.
[4] Andreas Savvides, Chih-Chieh Han, and Mani B. Strivastava. Dynamic
Fine-Grained Localization in ad-HocNetworks of Sensors. in the Proceeding
of the 7th IEEE/ACM Annual Conference on Mobile Computing and Networking
(MbilCom 2001), July 2001.
[5] Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine, and Seth Teller.
Anchor-Free Distributed Localization in Sensor Networks. ACM Interna-
tional Conference on Embedded Networked Sensor Systems (SenSys 2003), pages
340–341, April 2003.
[6] D. Niculescu and B. Nath. Ad hoc positioning system (APS). in Proceedings
of GLOBECOM, San Antonio, 2001.
[7] D. Niculescu and B. Nath. DV Based Positioning in Ad hoc Networks.
Journal of Telecommunication Systems, 2003.
[8] D. Niculescu and B. Nath. Ad Hoc Positioning System (APS) using AoA.
In Proceedings of INFOCOM 2003, San Francisco, CA., 2003.
[9] N. Patwari, J. Ash, S. Kyperountas, R. Moses, and N. Correal. Locating the
nodes: Cooperative localization in wireless sensor networks. IEEE Signal
Processing Magazine, 22(4):54–69, July 2005.
[10] Xiang Ji and Hongyuan Zha. Sensor Positioning inWireless Ad-hoc Sensor
Networks usingMultidimensional Scaling. Proceedings of 23rd Annual Joint
Conference of the IEEE Computer and Communications Societies (INFOCOM
2004), March 2004.
[11] Andreas Willig Holger Karl. Protocols and Architectures for Wireless Sensor
Networks. John Wiley & Sons, 2005.
[12] Jagoba Arias, Aitzol Zuloaga, Jesus Lazaro, Jon Andreu, and Armando
Astarloa.Malguki: anRSSI based ad hoc location algorithm.Microprocessors
and Microsystems, 28(8):403–409, 2004.
[13] Anxiao (Andrew) Jiang Jehoshua Bruck, Jie Gao. Localization and Routing
in SensorNetworks by Local Angle Information. Proceedings of the 6th ACM
international symposium on Mobile ad hoc networking and computing MobiHoc,
pages 181–192, May 2005.
[14] I. Borg and P. Groenen. Modern Multidimensional Scaling, Theory and
Applications. 1997.
[15] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz. Localization From Mere
Connectivity. IEEE Transactions on Parallel and Distributed Systems, 15, June
2004.
[16] Yi Shang,Wheeler Ruml, Ying Zhang, andMarkus Fromherz. Localization
from Connectivity in Sensor Networks. IEEE Transactions on Parallel and
Distributed Systems, 15:961 – 974, November 2004.
[17] Yi Shang and Wheeler Ruml. Improved MDS-based localization. In: Pro-
ceedings of the 23rd Conference of the IEEE Communications Society (Infocom
2004), 4:2640 – 2651, March 2004.
[18] Yi Shanga,Wheeler Rumlb, andMarkus P.J. Fromherzb. Positioning Using
Local Maps. Ad Hoc Networks, 4:240–253, March 2006.
[19] C. Savarese, J. Rabay, and K. Langendoen. Robust Positioning Algorithms
for Distributed Ad-Hoc Wireless Sensor Networks. USENIX Technical An-
nual Conference, June 2002.
[20] K.-F. Simon Wong, Ivor W. Tsang, Victor Cheung, S.-H. Gary Chan, and
James T. Kwok. Position Estimation for Wireless Sensor Networks. IEEE
Global Telecommunications Conference, 5, December 2005.
[21] Liang Zhao, Xiang Hong, and Qiliam Liang. Energy-efficient self-
organization for wireless sensor networks: a fully distributed approach.
IEEE Global Telecommunications Conference, 5:2728–2732, December 2004.
[22] Wendi B. Heinzelman, Anantha P. Chandrakasan, and Hari Balakrishnan.
An Application-Specific Protocol Architecture for Wireless Microsensor
Networks. IEEE Transactions on Wireless Communications, 1:660–670, Oc-
tober 2002.
[23] Mark de Berg, M. van Krefeld, M. Overmars, and O. Schwarzkopf. Com-
putational Geometry: Algorithms and Applications, Second Edition. Springer,
2000.
[24] Xiaoli Li, Hongchi Shi, and Yi Shang. A sorted RSSI quantization based
algorithm for sensor network localization. Proceedings of 11th International
Conference on Parallel and Distributed Systems, 1(20-22):557–563, July 2005.