| 摘要: | 雖然 Greedy Perimeter Stateless Routing (GPSR) 的地理繞徑貪婪演算法在無線隨意網路中有傳輸效能很好以及封包的負載較小等特性，但是在網路中的節點必須要知道他們自己的地理位置。另外，若網路中存在有缺口時，使用GPSR 橫越缺口的繞徑會導致在缺口邊界的節點負載過重，以及造成一些不必要的多餘繞徑。在本篇論文中，我們提出一個分散式的演算法以建構各點的區域性voronoi diagram的方式，先偵測出可能會造成封包傳送發生dead end的區域，並利用場論的概念，由發送端傳輸至目的端的路徑必定沿著兩點間的最短路徑，若路徑中的中繼點具有面臨缺口造成傳輸失敗的疑慮，則需使位於缺口邊界附近的節點在虛擬座標系統上向缺口的反方向靠攏，以降低其被選為中繼點的機率，如同於缺口方向存在一個帶有正電的電荷，而節點亦是一個帶正電的電荷，所以缺口方向會給予節點一股反向的推力，使其遠離缺口，藉此降低缺口邊界附近的節點被選為中繼節點的機率。我們的模擬結果呈現這個由我們的協定產生的虛擬座標系統可以有效率地支援地理繞徑，而且即時在這個網路中存在有一些缺口在裡面，這些透過我們的協定確實有效降低節點傳輸間遇到缺口的機率，尤其是在稀疏的網路環境及U型管般的網路拓墣中。 Geographic routing algorithms are an attractive alternative to traditional ad hoc routing algorithms. Although geographic routing like Greedy Perimeter Stateless Routing (GPSR) is efficient to mobile ad hoc wireless networks, it requires that nodes be aware of their physical positions to inform their neighbors. In addition, if there are exist geometric holes within the network topology, which is called “dead end”, routing across dead ends in GPSR [5] will lead to a lot of redundant routing paths during data transmission and overloaded nodes in the boundaries of dead ends. In this thesis, we proposed an approach, according to virtual coordinate system based on detecting possible dead ends among nodes to improve the routing performance of existing geographic routing algorithms. When exchanging beacon message among nodes, each node will construct a local Voronoi diagram on the basis of the message information which receives from its neighbors simultaneously, each node draws perpendicular bisectors with all of its neighbors and then it checks if any segments on its transmission circle are not covered, which is called “dead end area”. Encountering those nodes which is existed the dead end area when data packets were greedily forwarded. It may cause transmission end up. In order to reduce this kind of situation, we assume every mobile node within network was a positive electron and destination node is a negative electron. In accordance with field theory [25] the packet forwarding among the shortest path from source node to destination node is inevitable, if the node exist one or more dead end area within its broadcast range, there was existed an pseudo positive electron which locate out of node's broadcast range, the pseudo electron’s location was sum of two vectors, one is mobile node to the start point of dead end area, and the other is mobile node to the end of dead end area. And pseudo electron will give a repulsive force to mobile node which will force virtual coordinate of nodes moving away from the dead end area. For the purpose of reducing the risk of encountering dead end situation. After the mention above, the nodes in the network are aware of the relative virtual coordinates and each of them was notified to the neighbors by exchanging beacon message. In the final of this study, results of the simulation show that our approach can improve geographic routing more efficient, In addition, our approach is resilient to various network shapes especially for U-shaped-like topology within the sparse network. In this thesis, some programming effort was implemented for comparison using the NS2 simulator platform[17]. The simulation results show that the average number of dead end occurrences was significantly reduced about 5 to 10 times of packet to encounter the dead end situation. When our dead end avoidance enhanced mechanism was applied. The packet delivery ratio was improved also. |
