耐延遲網路中基於人類移動模式之路由機制

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：45

、訪客IP：3.138.141.202

姓名

邱品淳(Pin-chun Chiu) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

耐延遲網路中基於人類移動模式之路由機制
(A Routing Scheme Based on Human Mobility Patterns in Delay-Tolerant Networks)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

在耐延遲網路中，節點與節點沒有一條端點到端點(end-to-end)之間的傳輸路徑，因為網路中節點的快速移動與傳輸距離限制使得節點分布不均及各種限制。因此節點必須要依靠節點機會性的相遇以儲存、攜帶與轉送的方式將訊息送達至目的地端。由於近年來無線與行動裝置的發展，人類擁有的行動裝置能夠儲存與攜帶訊息，藉由移動接觸其他人類轉送資料。當人類的行為相似於行動節點時，這種人類移動與相遇的情境符合以社群為基底的耐延遲網路。因此在耐延遲網路的環境中研究人類的移動特性有助於新式社群耐延遲網路路由演算法的設計。
本論文探討大量的相關研究，包含耐延遲網路路由與社群路由方法，回顧過去的文獻發現幾項人類的移動性質及社群互相接觸的特性。進而本論文以這些特性設計Leverage機制，在這個機制之中藉由節點與節點過往的接觸時間來判斷這個訊息是否要轉送。並以實驗佐證演算法的效能，使用訊息抵達率、訊息傳遞費用與成功傳遞比例進行量測。實驗結果顯示本論文提出的演算法不僅有較佳的訊息抵達率而且傳遞訊息的次數較少，能有效的降低傳輸費用。

摘要(英)

In delay-tolerant networks, it is hardly possible to sustain any end-to-end data delivery paths between any two nodes because the networks suffer from various restrictions by non-uniform node distribution, high node mobility as well as limited transmission ranges. Nodes thus take a store-carry-and-forwarding method to send messages to destinations when they have any opportunistic contacts with other nodes in a network. Considering the recent advance of wireless and mobile networking systems, human beings possessing mobile devices are able to store data in such devices, carry the data along with them, and forward the data to encountered devices as encountering people during movement. As human beings appear like mobile nodes in a network context, the scenarios of human movement and contact may fall into the application domain of social-based delay-tolerant networks. Therefore, the research study of human mobility characteristics will contribute to the design of new social-based routing schemes in delay-tolerant network environments.
The study in this thesis investigates lots of related works, including not only delay-tolerant routing but also social-based routing methods for delay-tolerant networks. This literature review finds out several behavior characteristics about human mobility patterns and contacts by social communities. Accordingly, the study exploits these characteristics to design a leverage routing scheme. In this scheme, message forwarding decision is made by referring to the information of contacts between two nodes in the past. To examine the proposed scheme, simulations are conducted to the performance in terms of message delivery probability, overhead ratio, and successful relay ratio. Performance results indicate that the leverage routing scheme not only has better delivery probability but also results in lower amounts of message transmissions in the network.

關鍵字(中)

★ 耐延遲網路
★ 路由協定
★ 訊息傳遞

關鍵字(英)

★ Delay-Tolerant Networks
★ Routing protocol
★ Message delivery

論文目次

1 簡介 1
2 相關文獻探討 4
2.1 複製訊息演算法 4
2.2 效用值演算法 5
2.2.1 節點接觸資訊 5
2.2.2 地點區域資訊 6
2.2.3 混合演算法6
2.3 社群效用值定義6
2.4 社群耐延遲網路演算法9
2.4.1 社群路由演算法9
2.4.2 移動模型10
2.4.3 社群分析11
2.5 社群效用值比較表12
3 從移動模型發現人類行為特性 14
3.1 移動模型介紹 (TVC Model) 14
3.2 模型之環境建置15
3.3 網路環境建置及實驗數據分析17
3.4 時變對於節點連結情形的影響18
3.5 觀察與評析22
4 週期性路由機制演算法 24
4.1 相遇時間統計24
4.2 前置點時間設計25
4.3 演算法流程26
5 模擬與實驗分析 27
5.1 模擬環境設置27
5.2 移動模型設置27
5.2.1 真實軌跡檔27
5.2.2 模擬軌跡檔28
5.3 路由演算法介紹30
5.4 模擬結果與分析討論31
5.4.1 Infocom05 軌跡檔之效能檢測31
5.4.2 Infocom06 軌跡檔之效能檢測31
5.4.3 Cambridge 軌跡檔之效能檢測35
5.4.4 TVCM 軌跡檔之效能檢測35
5.5 實驗結果總結38
6 結論及未來研究工作 39
參考文獻 40

參考文獻

[1] K. Fall, “A delay-tolerant network architecture for challenged internets,” in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, ser. SIGCOMM ’03. Karlsruhe, Germany: ACM, Aug. 25–29, 2003, pp. 27–34.
[2] P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot, “Pocket switched networks and human mobility in conference environments,” in Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, ser. WDTN ’05, Philadelphia, USA, Mar. 19–23, 2005, pp. 244–251.
[3] T. Spyropoulos, K. Psounis, and C. Raghavendra, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” in Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, Philadelphia, PA, Aug. 22–26, 2005, pp. 252–259.
[4] W.-J. Hsu, T. Spyropoulos, K. Psounis, and A. Helmy, “Modeling spatial and temporal dependencies of user mobility in wireless mobile networks,” IEEE/ACM Transactions on Networking, vol. 17, no. 5, pp. 1564 –1577, Oct. 2009.
[5] A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hoc networks,” Department of Computer Science, Duke University, Tech. Rep. CS-2000-06, Apr. 2000.
[6] Y.-F. Hsu and C.-L. Hu, “Erasure coding-based routing for message multicasting in delay-tolerant networks,” in Proceedings of the 2012 IET International Conference on Frontier Computing - Theory, Technologies and Applications (IET FC’12), Xining,China, Aug. 16–18, 2012.
[7] T. Spyropoulos, R. N. R. T. Turletti, K. Obraczka, and A. Vasilakos, “Routing for disruption tolerant networks: taxonomy and design,” Wireless Networks,vol. 16, no. 8, pp. 2349–2370, Nov. 2010.
[8] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott, “Impact of human mobility on opportunistic forwarding algorithms,” IEEE Transactions on Mobile Computing, vol. 6, no. 6, pp. 606–620, Jun. 2007.
[9] T. Karagiannis, J.-Y. L. Boudec, and M. Vojnović, “Power law and exponential decay of intercontact times between mobile devices,” IEEE Transactions on Mobile Computing, vol. 9, no. 10, pp. 1377–1390, Oct. 2010.
[10] A. Lindgren, A. Doria, and O. Schelén, “Probabilistic routing in intermittently connected networks,” SIGMOBILE Mob. Comput. Commun. Rev., vol. 7, no. 3,pp. 19–20, Jul. 2003.
[11] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility,” in Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, New York, USA, Mar. 19–23, 2007, pp.79–85.
[12] E. Daly and M. Haahr, “Social network analysis for information flow in disconnected delay-tolerant manets,” IEEE Transactions on Mobile Computing,vol. 8, no. 5, pp. 606 –621, May 2009.
[13] J. Wu and Y. Wang, “Social feature-based multi-path routing in delay tolerant networks,” in Proceedings of IEEE INFOCOM, Florida,USA, Mar. 25–30, 2012,pp. 1368 –1376.
[14] A.-K. Pietilänen and C. Diot, “Dissemination in opportunistic social networks: The role of temporal communities,” in Proceedings of the Thirteenth ACM Tnternational Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc’12), Hilton Head Island, South Carolina, Jun. 11–14, 2012, pp.165–174.
[15] J. Tang, M. Musolesi, C. Mascolo, and V. Latora, “Characterising temporal distance and reachability in mobile and online social networks,” ACM SIGCOMM Computer Communication Review (CCR), vol. 40, no. 1, pp. 118–124,Jan. 2010.
[16] M. E. J. Newman, “Modularity and community structure in networks,” Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577–8582,Jun. 2006.
[17] P. Hui, J. Crowcroft, and E. Yoneki, “Bubble rap: Social-based forwarding in delay-tolerant networks,” IEEE Transactions on Mobile Computing, vol. 10,no. 11, pp. 1576 –1589, Nov. 2011.
[18] G. Palla, I. Dere´nyi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, vol.435, no. 7043, pp. 814–818, Apr. 2005.
[19] P. Hui and J. Crowcroft, “How small labels create big improvements,” in Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops(PerCom Workshops ’07), New York, USA, Mar. 19–23, 2007, pp. 65–70.
[20] W. Gao, G. Cao, T. L. Porta, and J. Han, “On exploiting transient social contact patterns for data forwarding in delay-tolerant networks,” IEEE Transactions on Mobile Computing, vol. 12, no. 1, pp. 151 –165, Jan. 2013.
[21] K. Lee, S. Hong, S. J. Kim, I. Rhee, and S. Chong, “Slaw: Self-similar least action human walk,” IEEE/ACM Transactions on Networking, vol. 20, no. 2,pp. 515 –529, Apr. 2012.
[22] I. Rhee, M. Shin, S. Hong, K. Lee, S. J. Kim, and S. Chong, “On the levy-walk nature of human mobility,” IEEE/ACM Transactions on Networking, vol. 19,no. 3, pp. 630–643, Jun. 2011.
[23] M. C. Gonza´lez, C. A. Hidalgo, and A.-L. Baraba´si, “Understanding individual human mobility patterns,” Nature, vol. 453, no. 7196, pp. 779–782, Jun.2008.
[24] D. Brockmann, L. Hufnagel, and T. Geisel, “The scaling laws of human travel,”Nature, vol. 439, no. 7075, pp. 462–465, Jan. 2006.
[25] C. Boldrini and A. Passarella, “Hcmm: Modelling spatial and temporal properties of human mobility driven by users’ social relationships,” Computer Communications, vol. 33, no. 9, pp. 1056 – 1074, Jun. 2010.
[26] M. Musolesi and C. Mascolo, “Designing mobility models based on social network theory,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 11, no. 3, pp. 59–70, Jul. 2007.
[27] Frans, Ekman, A. Keränen, J. Karvo, and J. Ott, “Working day movement
model,” in Proceedings of the 1st ACM SIGMOBILE workshop on Mobility models, ser. MobilityModels ’08. Hong Kong SAR, China: ACM, May 27–30, 2008, pp. 33–40.
[28] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, p. P10008, Oct. 2008.
[29] T. Hossmann, T. Spyropoulos, and F. Legendre, “Putting contacts into context: Mobility modeling beyond inter-contact times,” in Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc’11), Paris, France, May 16–20, 2011, pp. 18:1–18:11.
[30] N. P. Nguyen, T. N. Dinh, Y. Xuan, and M. T. Thai, “Adaptive algorithms for detecting community structure in dynamic social networks,” in Proceedings of IEEE INFOCOM, Shanghai, China, Apr. 10–15, 2011, pp. 2282 –2290.
[31] W. jen Hsu and A. Helmy, “On modeling user associations in wireless lan traces on university campuses,” in Proceedings of the 2nd International Workshop On Wireless Network Measurement, Boston,USA, Apr. 3, 2006.
[32] A. Keränen, J. Ott, and T. Kärkkäinen, “The one simulator for dtn protocol evaluation,” in Proceedings of the 2nd International Conference on Simulation Tools and Techniques, Rome, Italy, Mar. 2-6, 2009, pp. 55:1–55:10.
[33] J. Ellson, E. Gansner, E. Koutsofios, S. North, and G. Woodhull, “Graphviz and dynagraph – static and dynamic graph drawing tools,” in Graph Drawing Software, M. Junger and P. Mutzel, Eds. Springer-Verlag, 2003, pp. 127–148.
[34] M. Bastian, S. Heymann, and M. Jacomy, “Gephi: An open source software for exploring and manipulating networks,” 2009.

指導教授

胡誌麟

審核日期

2013-8-27

推文