地理繞徑協定上改善Dead end的發生機率; Dead end avoidance enhanced Mechanism in GPSR

NCU Institutional Repository > 資訊電機學院 > 資訊工程學系碩士在職專班 > 博碩士論文 > Item 987654321/8812

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/8812

题名:	地理繞徑協定上改善Dead end的發生機率;Dead end avoidance enhanced Mechanism in GPSR
作者:	林浩偉;Hao-Wei Lin
贡献者:	資訊工程學系碩士在職專班
关键词:	無線隨意網路;地理繞徑;mobile ad hoc networks;virtual coordinate system;Geographic routing
日期:	2008-07-18
上传时间:	2009-09-22 11:35:14 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	雖然 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.
显示于类别:	[資訊工程學系碩士在職專班 ] 博碩士論文

文件中的档案:

档案	大小	格式	浏览次数

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....