耐延遲網路中利用訊息編碼重組條件之資料傳播機制

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：12

、訪客IP：3.141.202.187

姓名

徐侑豐(Yu-feng Hsu) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

耐延遲網路中利用訊息編碼重組條件之資料傳播機制
(A Novel Remix Qualification Algorithm for Network Coding Based Data Dissemination in Delay-Tolerant Networks)

相關論文

★ 非結構同儕網路上以特徵相似度為基準之搜尋方法	★ 以階層式叢集聲譽為基礎之行動同儕網路拓撲架構
★ 線上RSS新聞資料流中主題性事件監測機制之設計與實作	★ 耐延遲網路下具密度感知的路由方法
★ 整合P2P與UPnP內容分享服務之家用多媒體閘道器：設計與實作	★ 家庭網路下簡易無縫式串流影音播放服務之設計與實作
★ 耐延遲網路下訊息傳遞時間分析與高效能路由演算法設計	★ BitTorrent P2P 檔案系統下載端網路資源之可調式配置方法與效能實測
★ 耐延遲網路中基於人類移動模式之路由機制	★ 車載網路中以資料匯集技術改善傳輸效能之封包傳送機制
★ 適用於交叉路口環境之車輛叢集方法	★ 車載網路下結合路側單元輔助之訊息廣播機制
★ 耐延遲網路下以靜態中繼節點（暫存盒）最佳化訊息傳遞效能之研究	★ 耐延遲網路下以動態叢集感知建構之訊息傳遞機制
★ 跨裝置影音匯流平台之設計與實作	★ 耐延遲網路下基於封包複製模式的路由機制之模擬及效能比較

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

由於耐延遲網路其節點間建立連線具有偶然性，無法保証來源端與目的端之間持續存在完整的點對點路由路徑，因此資料訊息的傳播有賴於節點移動間的相遇，在短暫的相遇期間訊速地傳送攜帶的資料訊息。而在群播的環境下，如果考量到必須多個目的端收到訊息之成功率(群播傳遞成功率)，整個群播目的端收到訊息的延遲時間即是最後收到訊息之目的端的延遲時間，那麼單一目的端的worst-case delay 即需要加以考量，而根據文獻顯示，訊息編碼機制即可減少worst-case delay 的問題。因此為了能夠改善耐延遲網路資訊傳播的效率和可靠性，本論文深入研究訊息編碼機制應用在耐延遲網路群播環境下的適用性，研究內容首先探討訊息編碼機制的基本型-來源編碼機制在訊息單播與群播環境下的特性，透過數學分析得到來源編碼隨著目的端數之增加，其延遲時間的效能比使用訊息複制機制還來得佳，並以實驗佐証此一性質。接著透過此性質，進一步研究訊息編碼機制中較複雜的網路編碼機制，雖然網路編碼機制可改善來源編碼機制的延遲時間效能，但同時亦因為執行編碼重組而需較多的傳輸花費，因此本論文亦提出利用訊息編碼重組條件之資料傳播機制，透過編碼重組條件減少傳輸花費的機制，使得不僅維持較佳的延遲時間效能，亦可降低傳輸訊息量。最後，本研究透過模擬來驗証不同參數對於網路編碼機制的影響，觀察其在延遲時間和傳輸花費這兩項效能指標上的表現，可以得到其在多目的端的環境下，有著較佳的延遲時間。雖然網路編碼機制其傳輸花費略高，但是所占用系統的儲存空間較小，使其在儲存空間有限的環境下，亦擁有較佳的效能表現。

摘要(英)

Delay tolerant networks (DTNs) are a type of challenged networks with property of intermittent connectivity because of nodes’occasional contacts during movement in networks. It is very difficult for DTN systems to guarantee any persistent end-to-end routing path between a source and a destination node. Thus the data dissemination in DTNs exploits the nodal mobility to assist the data transferring. In the multicasting scenario, as regards multicasting for many destination nodes, the delay is counted till the last destination gets the message. So it is necessary to consider the worst-case delay problem for last destination. According to the previous studies, the message coding scheme significantly improves the worst case delay. To improve the efficient data dissemination in DTNs, this study seeks to exploit the essence of the message coding scheme for multicasting in DTN environments. First, with the order statistic principle, this study derives the mathematic formulations of deliver delay distribution for message multicasting using the basic message coding approach-source coding. As the number of destination nodes increase, the performance gain can become better in terms of delivery delay. Second, this study investigates the functions of complex message coding approach-network coding for message delivery in DTN. Although network coding approach has better delivery latency than source coding approach, it cause more transmitting traffic by “remix” scheme. The remix scheme is used to overcome the dependence of code blocks. Then this study proposed a novel remix qualification algorithm to reduce the transmitting traffic when using the remix scheme. Finally, this study conducts simulations to evaluate the performance sensitivities to the metrics of message delivery latency and transmitting traffic under a variety of coding parameters. The results demonstrate that proposed network coding based data dissemination has lower delivery latency than message replication based in multicasting scenario. Although network coding based cause more transmitting traffic, it occupies little buffer than others. Therefore network coding based data dissemination has considerable improvement while the buffer is constrained.

關鍵字(中)

★ 耐延遲網路
★ 網路編碼
★ 資料傳播

關鍵字(英)

★ Delay-Tolerant Networks
★ Network Coding
★ Data Dissemination

論文目次

1 簡介1
2 相關文獻與探討5
2.1 訊息複製機制5
2.1.1 控制複製機制(Controlled replication)6
2.1.2 效益性複製機制(Utility-based replication)7
2.2 訊息編碼機制8
2.2.1 來源編碼機制Source coding9
2.2.2 網路編碼機制Network coding10
2.3 耐延遲網路群播作法之比較12
3 系統與環境14
3.1 系統模型14
3.2 來源編碼機制之群播方法16
3.3 網路編碼機制之群播方法18
3.3.1 基本架構18
3.3.2 編碼區塊相依性問題19
3.3.3 編碼重組機制(Remix)19
3.4 網路編碼與來源編碼之基本差異22
4 訊息編碼機制在群播環境下的性質25
4.1 訊息單播25
4.2 訊息群播27
4.2.1 群播下的延遲時間分佈27
4.2.2 抹除碼機制於群播下的延遲時間分佈28
4.3 模擬實驗及結果30
4.3.1 模擬模型30
4.3.2 目的端個數(N) 的影響31
4.3.3 訊息分割數(k) 的上限值之影響31
4.3.4 複製因子(r) 之影響31
4.3.5 節點密度之影響34
4.4 小結35
5 訊息編碼重組條件之設計36
5.1 編碼重組之多餘傳送問題36
5.2 編碼重組滿足條件(Remix Qualification)38
5.2.1 考慮RootIDSet 紀錄到的個數38
5.2.2 考慮編碼區塊被編碼重組的次數43
5.2.3 編碼重組滿足條件無效之特例45
5.3 編碼重組滿足條件的總結46
6 模擬結果與分析51
6.1 模擬環境51
6.2 目的端個數(N) 的影響52
6.3 複製因子(r) 和來源端散佈源頭區塊的個數(L) 之影響53
6.4 節點數的影響56
6.5 編碼重組有無之影響56
6.6 編碼重組條件的影響56
6.7 比較相同傳輸訊息量的表現60
6.8 儲存空間之影響65
6.9 實驗結果與總結67
7 結論及未來研究工作68
參考文獻69

參考文獻

[1] G. Zussman and A. Segall, “Energy efficient routing in ad hoc disaster recovery networks,”in Proc. of IEEE INFOCOM, vol. 1, 2003, pp. 682–691.
[2] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot, “Optimized link state routing protocol for ad hoc networks,” in Proc. of IEEE International Multitopic Conference, 2001, pp. 62–68.
[3] C. E. Perkins and E. M. Royer, “Ad-hoc on-demand distance vector routing,” in Proc. Of IEEE Workshop on Mobile Computing Systems and Applications, 1999, pp. 90–100.
[4] D. B. Johnson and D. A. Maltz, “Dynamic source routing in ad hoc wireless networks,” in Mobile Computing, ser. The Kluwer International Series in Engineering and Computer Science. Springer US, 1996, vol. 353, pp. 153–181.
[5] Z. Zhang, “Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges,” IEEE Communications Surveys Tutorials, vol. 8, no. 1, pp. 24–37, 2006.
[6] T. Spyropoulos, R. N. B. Rais, T. Turletti, K. Obraczka, and A. Vasilakos, “Routing for
disruption tolerant networks: Taxonomy and design,” Wireless Networks, vol. 16, no. 8, pp. 2349–2370, 2010.
[7] Y. Wang, S. Jain, M. Martonosi, and K. Fall, “Erasure-coding based routing for opportunistic networks,” in Proc. of ACM SIGCOMM Workshop on Delay-Tolerant Networking, 2005, pp. 229–236.
[8] W. Zhao, M. Ammar, and E. Zegura, “Multicasting in delay tolerant networks: semantic models and routing algorithms,” in Proc. of ACM SIGCOMM Workshop on Delay-Tolerant Networking, 2005, pp. 268–275.
[9] Y. Xi and M. C. Chuah, “An encounter-based multicast scheme for disruption tolerant networks,” Elsevier Comput. Commun., vol. 32, no. 16, pp. 1742–1756, 2009.
[10] Y. Wang, X. Li, and J. Wu, “Multicasting in delay tolerant networks: Delegation forwarding,” in Proc. of IEEE GLOBECOM, Dec. 2010.
[11] W. Gao, Q. Li, B. Zhao, and G. Cao, “Multicasting in delay tolerant networks: a social network perspective,” in Proc. of ACM MobiHoc, 2009, pp. 299–308.
[12] J. Santiago, A. Casaca, and P. R. Pereira, “Multicast in delay tolerant networks using probabilities and mobility information,” Ad Hoc & Sensor Wireless Networks, An International Journal, vol. 7, no. 1-2, pp. 51–68, 2009.
[13] M. Grossglauser and D. N. C. Tse, “Mobility increases the capacity of ad hoc wireless networks,” IEEE/ACM Transactions on Networking, vol. 10, no. 4, pp. 477–486, Aug.2002.
[14] A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hoc networks,” Duke University, Tech. Rep. CS-200006, 2000.
[15] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Spray and wait: An efficient routing scheme for intermittently connected mobile networks,” in Proc. of ACM SIGCOMM Workshop on Delay-Tolerant Networking, 2005, pp. 252–259.
[16] U. Lee, S. Y. Oh, K.-W. Lee, and M. Gerla, “Relaycast: Scalable multicast routing in delay tolerant networks,” in Proc. of IEEE ICNP, Oct. 2008, pp. 218–227.
[17] A. Lindgren, A. Doria, and O. Schelen, “Probabilistic routing in intermittently connected networks,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 7, no. 3, pp. 19–20, Jul. 2003.
[18] V. Erramilli, M. Crovella, A. Chaintreau, and C. Diot, “Delegation forwarding,” in Proc. of ACM MobiHoc, 2008, pp. 251–260.
[19] M. Ma, Z. Zhang, X. An, C. Li, and Y. Cao, “Probability and receiver list based multicast routing in dtns,” in Proc. of IEEE International Conference on Advanced Communication Technology, vol. 1, Feb. 2010, pp. 23–26.
[20] L.-J. Chen, C.-H. Yu, T. Sun, Y.-C. Chen, and H. hua Chu, “A hybrid routing approach for opportunistic networks,” in Proc. of ACM Workshop on Challenged Networks, 2006, pp. 213–220.
[21] S. Jain, M. Demmer, R. Patra, and K. Fall, “Using redundancy to cope with failures in a delay tolerant network,” in Proc. of ACM SIGCOMM, 2005, pp. 109–120.
[22] Y. Liao, K. Tan, Z. Zhang, and L. Gao, “Estimation based erasure-coding routing in delay tolerant networks,” in Proc. of ACM International Conference on Wireless Communications and Mobile Computing, 2006, pp. 557–562.
[23] Y. Liao, Z. Zhang, B. Ryu, and L. Gao, “Cooperative robust forwarding scheme in dtns using erasure coding,” in Proc. of IEEE Military Communications Conference, 2007.
[24] E. Bulut, Z. Wang, and B. K. Szymanski, “Cost efficient erasure coding based routing in delay tolerant networks,” in Proc. of IEEE ICC, 2010.
[25] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204–1216, Jul. 2000.
[26] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, “Xors in the air: Practical wireless network coding,” IEEE/ACM Transactions on Networking, vol. 16, no. 3, pp. 497–510, Jun. 2008.
[27] T. Ho, R. Koetter, M. Mkdard, D. R. Karger, and M. Effros, “The benefits of coding over routing in a randomized setting,” in Proc. of IEEE International Symposium on Information Theory, Jun. 2003, p. 442.
[28] J. Widmer and J.-Y. L. Boudec, “Network coding for efficient communication in extreme networks,” in Proc. of ACM SIGCOMM Workshop on Delay-Tolerant Networking, 2005, pp. 284–291.
[29] X. Zhang, G. N. J. Kurose, and D. Towsley, “On the benefits of random linear coding for unicast applications in disruption tolerant networks,” in Proc. of IEEE Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2006, pp. 1 – 7.
[30] Y. Lin, B. Liang, and B. Li, “Performance modeling of network coding in epidemic routing,” in Proc. of ACM international MobiSys workshop on Mobile opportunistic networking, 2007, pp. 67–74.
[31] Y. Lin, B. Li, and B. Liang, “Efficient network coded data transmissions in disruption tolerant networks,” in Proc. of IEEE INFOCOM, 2008, pp. 1508–1516.
[32] S. Ahmed and S. S. Kanhere, “Hubcode: message forwarding using hub-based network coding in delay tolerant networks,” in Proc. of ACM international conference on Modeling, analysis and simulation of wireless and mobile systems, 2009, pp. 288–296.
[33] Z. Narmawala and S. Srivastava, “Midtone: Multicast in delay tolerant networks,” in Proc. of IEEE International Conference on Communications and Networking in China, Aug. 2009, pp. 1 –8.
[34] A. Keranen, J. Ott, and T. Karkkainen, “The one simulator for dtn protocol evaluation,” in Proc. of International Conference on Simulation Tools and Techniques, 2009.
[35] K. Lee, S. Hong, S. J. Kim, I. Rhee, and S. Chong, “Slaw: A new mobility model for human walks,” in Proc. of IEEE INFOCOM, 2009, pp. 855–863.

指導教授

胡誌麟(Chih-lin Hu)

審核日期

2012-8-8

推文