(3.227.208.0) 您好!臺灣時間:2021/04/21 01:57
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:賴胤竹
研究生(外文):Lai, Yin-Chu
論文名稱:至多兩倍最短路徑的分散式緊湊路由方法
論文名稱(外文):Distributed Compact Routing Protocol with Stretch 2
指導教授:蔡明哲蔡明哲引用關係
指導教授(外文):Tsai, Ming-Jer
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:21
中文關鍵詞:緊湊路由拉伸路由表
外文關鍵詞:compact routingrouting stretchrouting state
相關次數:
  • 被引用被引用:0
  • 點閱點閱:102
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:12
  • 收藏至我的研究室書目清單書目收藏:0
緊湊路由問題主要探討的是路由表及拉伸之間的權衡。在此,拉伸代表實際選擇的路徑以及最短路徑的比值。至今的研究顯示,在 $N$ 個節點的網路中,使用 $O(N)$ 的大小來建構路由表可達到3倍拉伸的結果。在這篇論文中,我們提出了一個新的方法能夠達到2倍拉伸的效果。我們的實驗結果顯示,我們只用少量的空間來建構路由表,並-在平均拉伸以及標記點的附載平衡上有良好的效果。
Compact routing addresses the tradeoff between routing state and stretch, where stretch is the ratio between the hop counts of the selected path and that of the optimal path. Recent advances in compact routing protocol show that a stretch of 3 can be achieved while maintaining $O(\sqrt{N})$ routing state per node in an $N$-node network. In this thesis, we present a new routing protocol that achieves a worst-case stretch of 2. Simulations show that our algorithm only requires small amounts of routing state, and we have good performance in the average routing stretch and the load balance of landmarks.
Abstract ii
Contents iii
List of Figures v
1 Introduction 1
2 Related Works 3
3 Overview Our Technique 4
4 The Proposed Algorithm 6
4.1 Preprocessing . . . . . . . . . . . . . . . . . . . 7
4.2 Routing . . . . . . . . . . . . . . . . . . . . . 8
5 Analysis 11
6 Performance Evaluation 14
6.1 Routing Stretch . . . . . . . . . . . . . . . . . 15
6.2 Routing State . . . . . . . . . . . . . . . . . . . 15
6.3 Load Balance of Landmarks . . . . . . . . . . . . . 16
7 Conclusion 18
Bibliography 19
[1] M. Thorup and U. Zwick, "Approximate distance oracles," in Journal of the ACM, vol. 52, no. 1, pp. 1-24, january 2005.
[2] M. Thorup and U. Zwick, "Compact routing schemes," in Proc. ACM SPAA, july 2001.
[3] Y. Mao, F. Wang, L. Qiu, S. Lam, and J. Smith, "S4: Small state and small stretch compact routing protocol for large static wireless networks," in Proc. USENIX NSDI, april 2007
[4] R. Agarwal, P. B. Godfrey, and S. Har-Peled, "Appoximate distance queries and compact routing in sparse graphs," in Proc. IEEE Conference on Computer Communications (INFOCOM), 2011.
[5] D. Johnson, D. Maltz, and J. Broch, "DSR: The dynamic source routing protocol for multihop wireless ad hoc networks," in Ad Hoc Networking, Boston, MA: Addison-Wesley, 2001.
[6] C. E. Perkins and E. M. Royer, "Ad hoc on-demand distance vector routing," in Proc. 2nd IEEE Workshop Mobile Comput. Syst. Appl, february 1999, pp. 90-100.
[7] C. E. Perkins and P. Bhagwat, "Highly dynamic destinationi-sequenced distance-vector routing (DSDV) for mobile computers," in Proc. ACM SIGCOMM, 1994, pp. 234-244.
[8] L Cowen, "Compact routing with minimum stretch," in Journal of Algorithms, pp. 170-183, 2001.
[9] M. Gerla, X. Hong, and G. Pei, "Landmark routing for large ad hoc wireless networks," in Proc. IEEE Globecom, Nov. 2000, vol. 3, pp. 1702-1706.
[10] Z.J. Hass, M. R. Pearlman, and P. Samar, "The zone routing protocol (ZRP) for ad hoc networks," IETF MANET Working Group, Internet-Draft, july 2002.
[11] A. Post and D. johnson, "Self-organizing hierarchical routing for scalable ad hoc networking," Rice CS Tech. Rep. TR04-433, 2004.
[12] P. F. Tsuchiya, "The landmark hierarchy: A new hierarchy for routing in very large networks," in Proc. ACM SIGGCOM, 1988, pp. 35-42.
[13] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, "Routing with guaranteed delivery in ad hoc wireless networks," in Proc. 3rd ACM DIALM, augest 2004, pp. 121-132.
[14] B. Karp and H. Kung, "GPSR: Greedy perimeter stateless routing for wireless networks," in Proc. ACM MobiCom, augest 2000, pp. 243-254.
[15] F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger, "Geometric ad-hoc routing: Of theory and practice," in Proc. ACM PODC, 2003, pp. 63-72.
[16] B. Leong, S. Mitra, and B. Liskov, "Path vector face routing: Geographic routing with local face information," in Proc. IEEE ICNP, november 2005.
[17] K. Iwanicki, and M. V. Steen, "A case for hierarchical routing in low-power wireless embedded networks," in ACM Transaction on Sensor Networks, july 2012.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔