在無線感測器網路當中，會因為感測器使用不同的傳輸功率或是隱藏節點問題，造成網路中出現單向連結。在本篇論文中，我們針對存在單向連結的無線感測器網路，提出一個建構虛擬座標的方法，來幫助每個感測器指定相對應的虛擬座標。此方法不需要實際的地理位置資訊就可以進行虛擬座標的建構，此外我們也根據所建構的虛擬座標，提出一個相對應的路由協定。我們所提出的路由協定不需要花費大量的訊息，來獲知整個網路的拓樸資訊而且能夠保證傳輸。在實驗結果方面，我們將本論文所提出的方法 ABVCAp_Uni 與 GLDR + VLM 和 Euclidean 作比較，根據實驗顯示本論文所提出的方法，針對存在單向連結的無線感測器網路有較優良的結果。

A wireless sensor network has unidirectional links because sensors can have different transmission ranges, sensors have unstable transmission ranges, and a hidden terminal problem exists. In this thesis, we introduce a virtual coordinate assignment protocol (ABVCap_Uni) to assign virtual coordinates to nodes that have no geographic information in wireless sensor networks with unidirectional links, and we propose a routing protocol based on the ABVCap_Uni virtual coordinates. Our routing protocol guarantees packet delivery without computation and storage of global topology features in a discrete domain. Using
simulation, we evaluate the performance of the proposed routing protocol (ABVCap_Uni routing), the greedy landmark-descent routing protocol (GLDR+VLM routing), and the greedy routing protocol based on physical coordinates (Euclidean routing). The simulations demonstrate that our routing protocol ensures moderate routing path length cost overhead.

Abstract
Contents
List of Figures
Introduction
Preliminaries
ABVCap
ABVCAP_Uni
Construction of Cluster
Establishment of Rings
Neighborhood in Extended Node Graph
Assignment of Virtual Coordinates
ABVCAP_Uni Routing Protocol
ExteriorRouting
InteriorRouting
RoutingProtocol
Delivery-Guaranteed of ABVCAP_Uni
PerformanceEvaluation
Delivery Rate
Routing Path Length
Number of Virtual Coordinates
Hop Distance froma Visible Neighbor
Number of Broadcasts
Conclusion
Bibliography

[1]B.Karp and H.T.Kung, "GPSR: greedy perimeter stateless routing for wireless networks," in IEEE/ACMMOBICOM, 2000.
[2]J.Gao, L.J.Guibas, J.Hershberger, L.Zhang, and A.Zhu, "Geometric spanners for routing in mobile networks," IEEEJournal on Selected Areas in Communications, vol.23, pp. 174-185, 2005.
[3]H.Frey and I.Stojmenovic, "On delivery guarantees of face and combined greedy-face routing in adhoc and sensor networks, in IEEE/ACM MOBICOM, 2006.
[4]S.Funke and N.Milosavljevic, "Guaranteed-delivery geographic routing under uncertain location information," in IEEE INFOCOM, 2007.
[5]Q.Fang, J.Gao, L.J.Guibas, V.D.Silva, and L.Zhang, "GLIDER: gradien landmark-based distributed routing for sensor networks, in IEEE INFOCOM 2005.
[6]J.Bruck, J.Gao, and A.Jiang, "MAP: medial axis based geometric routing in sensor networks, in IEEE/ACM MOBICOM, 2005.
[7]A.Nguyen, N.Milosavljevic, Q.Fang, J.Gao, and L.J.Guibas, "Landmark selection and greedy landmark-descent routing for sensor networks," in IEEE INFOCOM,2007.
[8]A.Caruso, S.Chessa, S.De, and A.Urpi, "GPS free coordinate assignment and routing in wireless sensor networks," in IEEE INFOCOM, 2005.
[9]Y.Liu, L.M.Ni, and M.Li, "A geography-free routing protocol for wireles sensor networks, in IEEE HPSR, 2005.
[10]M.J.Tsai, H.Y.Yang, and W.Q.Huang, "Axis based virtual coordinate assignment protocol and delivery guaranteed routing protocol in wireless sensor networks," in IEEE INFOCOM, 2007
[11]M.Gerla, Y.Z.Lee, J.S.Park, and Y.Yi, "On demand multicast routing with unidirectional links," in IEEE WCNC, 2005.
[12]N.Li and J.C.Hou, "Localized topology control algorithms for heterogeneous wireless networks," IEEE/ACM Transactions on Networking, vol.13, pp.1313-1324, 2005.
[13]V.Ramasubramanian, R.Chandra, and D.Mosse, "Providing a bidirectional abstraction for unidirectional ad hoc networks," in IEEE INFOCOM, 2002.
[14]J.Wu, "Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links," IEEE Transactions on Parallel and Distributed Systems vol.13, pp.866-881, 2002.
[15]L.Barriere, P.Fraigniaud, and L.Narayanan, "Robust position-based routing in wireless ad hoc networks with unstable transmission ranges," in ACM DIAL-M 2001.
[16]J.Chen, A.Jiang, I.A.Kanj, G.Xia, and F.Zhang, "Separability and topolog control of quasi unit disk graphs," in IEEE INFOCOM, 2007.
[17]F.Kuhn, T.Moscibroda, and R.Wattenhofer, "Initializing newly deployed ad hoc and sensor networks," in IEEE/ACM MOBICOM, 2004.
[18]F.Kuhn, R.Wattenhofer, and A.Zollinger, "Ad-hoc networks beyond unit disk graphs," in ACM DIALM-POMC, 2003.
[19]S.Choi and K.G.Shin, "A unified wireless LAN architecture for real-time and non-real-time communication services," IEEE/ACM Transactions on Networking, vol.8, pp.44-59, 2000.
[20]F.Tobagi and L.Kleinrock, "Packet switching in radio channels : PartII The hidden terminal problem in carrier sense multiple access and the busy tone solution," IEEE Transactions on Communications, vol.23, pp.1417-1433, 1975.
[21]V.Bhargavan, A.Demers, S.Shenker, and L.Zhang, "MACAW : a media acces protocol for wireless LANs," in ACM SIGCOMM, 1994.
[22]J.Li, J.Jannotti, D.DeCouto, D.Karger, and R.Morris, "A scalable location service for geographic ad-hoc routing," in IEEE/ACM MOBICOM, 2000.