雖然類似GPSR的地理繞徑(Geographic routing)在無線感測以及隨意網路中效能很好，但是在網路中的感測節點必須要知道他們自己的地理位置。另外，若網路中存在有洞時，使用GPSR橫越洞的繞徑會導致在洞邊界的感測節點負載過重。在本篇論文中，我們提出一個分散式的協定僅以感測節點間的跳步計數(hop count)來建立一個虛擬座標系統稱之HVC。每個感測節點最多紀錄跳步計數到七個最近的地標來當他的虛擬座標，而這些地標座落在一個六角形的頂點跟它的中心點。在HVC建立之後，在網路中的感測節點可以透過HVC航海圖來得知地標間的相對座標。然後起始點可以找到一條輔助的繞徑路徑來指引從起始點到目的地旅程之方向。最後，我們可以透過輔助繞徑節點的支援找到一條繞徑路徑到目的地去。我們的模擬結果呈現這個由我們的協定產生的虛擬座標系統可以有效率地支援地理繞徑，而且即時在這個網路中存在有一些洞在裡面，這些透過我們的協定找出來的地標仍然可以均勻地座落在網路中的每個地方。另外，我們的協定可以適用在各式各樣的網路形狀而且不論這條路徑是否會橫越洞他仍然可以找到一條均勻負載的繞徑路徑到目的地。 Although geographic routing like GPSR is efficient to ad hoc and wireless sensor networks, it requires that nodes be aware of their physical positions. In addition, if there are holes in the network, routing across holes in GPSR will lead to a lot of overloaded nodes in the boundaries of holes. In this thesis, we proposed a distributed protocol to construct a virtual coordinate system named HVC merely based on hop counts among nodes. Each node records hop counts to seven nearest landmarks at most to be its virtual coordinate, and the landmarks are located in the vertices of a hexagon and its center. After the HVC is constructed, the nodes in the network are aware of the relative coordinates among the landmarks through the HVC chart. Then source node can find an Auxiliary Routing Path (ARP) to indicate the direction in the journey from source to destination. Finally, we can find a routing path to destination with the ARP support. Simulation results show that our protocol can support geographic routing efficiently, and the landmarks found by our protocol are located everywhere in the network uniformly even if there exist some holes within it. In addition, our protocol is resilient to various network shapes and it can find a load balancing routing path to destination even this path will across holes in the network.
