臺灣博碩士論文加值系統

在臨機人際網路上之以機率方式增進
資料之傳輸機制

中文摘要

隨著無線網路的應用越來越普及，適當地處理網路間因為服務範圍限制所造成的暫時網路中斷的議題日趨重要。透過利用攜帶者本身的移動性讓不同使用者移動裝置的無線裝置有“機會”(opportunities) 可互相傳輸資料或交換訊息的網路，我們稱之為“臨機網路”(opportunistic networks) 或是 “臨機人際網路”(opportunistic people networks)。針對這類網路特別設計資料傳輸演算法是十分重要的。在這篇論文中我們針對兩種在臨機人際網路裡常見的應用類型做研究，包括一般的資料檔案傳輸以及專門針對網頁資料的傳輸做研究。根據 H-EC [12] 的方法，我們提出了一個改良的機率式傳輸演算法 HEC-PF (H-EC with Probabilistic Forwarding)。這個改良的機制改善了 H-EC 的侵略式傳輸(aggressive forwarding)階段，在這個階段新增實作了機率式傳輸，也就是根據所遇到節點的傳輸機率(delivery probability)來決定是否要傳輸訊息。除此之外，為了針對網頁資料傳輸做處理，我們利用階層式多重描述編碼(Layered Multiple Description Coding)的概念，讓使用者可以透過階層式編碼法(Layer Coding)，漸進式地得到較高品質的網頁。透過使用實際網路資料的紀錄(trace)和情境來做模擬實驗，針對我們提出的方法採用延遲(latency)、 傳達率(delivery ratio)和實際收到的網頁品質，根據收到的階層(layer)數和相對接收品質(relative quality )等指標來做評估。結果顯示了我們所提出的 HEC-PF 方法在所有的情境中都比 EC 和 H-EC 方法的傳輸效果來得好，並且在網路狀況極不佳時仍能有相對良好的效能。透過調整 HEC-PF 的參數，我們發現增加最大傳輸距離(maximum forwarding hop distance)和傳輸機率的計算深度(hops count)，可以提高訊息的傳達率。除此之外，透過運用階層式多重描述編碼的概念，讓使用者可以在沒收到完整的網頁資料前，就可以根據目前已收到的階層(layer)作網頁的“預先瀏覽”(preview)。並且隨著收到階層(layer)數的累積，能漸進式地得到較高品質的網頁，進而增進整體網頁瀏覽的用戶體驗(user experience)。我們所提出的方法在強韌性和效率性上都是在臨機人際網路上一個有效的資料傳輸和內容散佈方式。

On Using Probabilistic Forwarding to Improve Data Transfer in Opportunistic People Networks

Abstract

With wireless networking technologies extending into every part of our working and living environments, proper handling of intermittent wireless connectivity and network disruptions is important. We use the term “opportunistic networks”or“opportunistic people networks”to refer to data exchanges based on the connection opportunities that arise whenever mobile devices happen to come into wireless range due to the mobility of their users. Propose proper strategies for dealing with communication in such opportunistic network environments are of significance and remained desirable. In this study, we investigated two applications in opportunistic people networks, namely file transfer and Web surfing applications. We propose the HEC-PF scheme, an enhancement of our previous H-EC [12] scheme for effective data forwarding in opportunistic networks. The enhanced scheme modifies the aggressive forwarding phase of the H-EC scheme by implementing a new Probabilistic Forwarding feature, which decides whether to forward a message to a newly encountered node based on the delivery probability. Moreover, targeting Web surfing applications, we designed LMDC (Layered Multiple Description Coding) based techniques that immensely improve the perceived Web quality for end users. Using simulations as well as realistic network scenarios, we evaluate the proposed schemes in terms of latency, and completion ratio. The results show that the HEC-PF scheme outperforms the EC and H-EC schemes in all test cases, and the performance gain is even more substantial when network connectivity is extremely poor. By varying the parameters of the HEC-PF scheme, we show that its completion ratio improves as the maximum forwarding distance or the hop distance considered when calculating the delivery probability increases. Furthermore, we show that using Layered MDC-based techniques leads to higher user perceived quality, since the end user is allowed to “preview” web content, even before the data has been completely transferred. The effectiveness and robustness of our proposed algorithm and their corresponding content dissemination techniques make them ideal solutions that can go a long way toward effective data dissemination in opportunistic people networks.

目 錄
第一章 緒論(INTRODUCTION) 1
1.1 研究背景(RESEARCH BACKGROUND) 1
1.1.1人類移動性(Human mobility) 1
1.1.2臨機網路(Opportunistic networking) 2
1.1.3個人可攜裝置(Personal device) 2
1.2問題及貢獻(PROBLEM DESCRIPTION AND CONTRIBUTIONS) 3
1.3 章節概述(THESIS ORGANIZATION) 4
第二章 相關研究(RELATED WORK) 6
2.1 臨機網路資料路由相關研究(OPPORTUNISTIC NETWORKS ROUTING) 6
2.1.1以資料複製為基礎的路由方法(Replication based routing): 7
2.1.2 以編碼技巧為基礎的路由方法(Coding based routing): 7
2.1.3以知識為基礎的路由方法(Knowledge based routing): 8
2.2 耐延遲網路上的HTTP協定相關研究(HTTP OVER DTN) 8
第三章 H-EC機率式傳輸改良版 10
(H-EC WITH PROBABILISTIC FORWARDING) 10
3.1 H-EC方法概觀(H-EC: AN OVERVIEW) 10
3.2 傳遞機率計算(DELIVERY PROBABILITY) 13
3.3 機率式傳輸(PROBABILISTIC FORWARDING) 15
第四章 針對網頁傳輸設計的階層式多重描述編碼 17
(LMDC FOR WEB SURFING) 17
4.1階層式多重描述編碼概觀(LMDC OVERVIEW) 17
4.2針對網頁傳輸設計的階層式多重描述編碼 20
(LMDC FOR WEB SURFING) 20
第五章 實驗評估(EVALUATION) 23
5.1 實驗情境(SIMULATION SCENARIOS) 23
5.2 評估ㄧ: 資料檔案傳輸 (EVALUATION I: DATA FILE TRANSFER) 25
5.2.1資料檔案傳輸評估I: Two-hop Scenario 25
5.2.2資料檔案傳輸評估II: 改變 H 的影響(Variable H Scenarios) 28
5.2.3資料檔案傳輸評估III: 改變 k 的影響(Variable k Scenarios) 29
5.3評估二: 網頁資料傳輸(EVALUATION II: WEB SURFING) 31
第六章 結論和將來工作項目 37
(CONCLUSIONS AND FUTURE WORK) 37
6.1結論(CONCLUSIONS) 37
6.2將來工作項目(FUTURE WORK) 38
附錄一、程式說明 39
參考文獻(REFERENCES) 42

[1]Crawdad project. http://crawdad.cs.dartmouth.edu/.
[2]Delay tolerant network simulator http://www.dtnrg.org/code/dtnsim.tgz
[3]The disruption tolerant networking project at umass. http://prisms.cs.umass.edu/diesel
[4]Jpeg 2000. http://www.jpeg.org/jpeg2000/
[5]UCSD wireless topology discovery project. http://sysnet.ucsd.edu/wtd/
[6]The zebranet wildlife tracker. http://www.princeton.edu/ mrm/zebranet.html
[7]N. Borenstein and N. Freed. Mime (multipurpose internet mail extensions) part one: Mechanisms for specifying and describing the format of internet message bodies. Technical report, IETF RFC 1521, September 1993.
[8]J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. Maxprop: Routing for vehicle-based disruption-tolerant networking. In IEEE Infocom, 2006.
[9]T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless Communication and Mobile Computing Journal, 2(5):483–502, 2002
[10]A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Pocket switched networks: Real-world mobility and its consequences for opportunistic forwarding. Technical Report UCAM-CL-TR-617, University of Cambridge, Computer Laboratory, February 2005.
[11]A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of human mobility on the design of opportunistic forwarding algorithms. In IEEE Infocom, 2006.
[12]L.-J. Chen, C.-H. Yu, T. Sun, Y.-C. Chen, and H. hua Chu. A hybrid routing approach for Opportunistic Networks. In ACM SIGCOMM Workshop on Challenged Networks, 2006.
[13]P. A. Chou and K. Ramchandran. Clustering source/channel rate allocations for receiver-drivenmulticast under a limited number of streams. In IEEE ICME, 2000.
[14]P. A. Chou, H. J. Wang, and V. N. Padmanabhan. Layered multiple description coding. In IEEE Packet Video Workshop, 2003
[15]J.-H. Cui, J. Kong, M. Gerla, and S. Zhou. Challenges: Building scalable mobile underwater wireless sensor networks for aquatic applications. IEEE Network, Special Issue on Wireless Sensor Networking, May 2006
[16]V. K. Goyal. Multiple description coding: Compression meets the network. IEEE Signal Processing Magazine, pages 74–93, September 2001.
[17]M. Grossglauser and D. Tse. Mobility increases the capacity of ad-hoc wireless networks. In IEEE Infocom, 2001.
[18]K. A. Harras, K. C. Almeroth, and E. M. Belding-Royer. Delay tolerant mobile networks (dtmns): Controlled flooding in sparse mobile networks. In IFIP Networking, 2005.
[19]X. Hong, M. Gerla, R. Bagrodia, and G. Pei. A group mobility model for ad hoc wireless networks. In ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 1999.
[20]J.-H. Huang, S. Amjad, and S. Mishra. Cenwits: A sensorbased loosely coupled search and rescue system using witnesses. In ACM SenSys, 2005.
[21]P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot. Pocket switched networks and human mobility in conference environments. In ACM SIGCOMM Workshop on DTN, 2005.
[22]S. Jain, K. Fall, and R. Patra. Routing in a delay tolerant network. In ACM SIGCOMM, 2004.
[23]J. LeBrun, C.-N. Chuah, and D. Ghosal. Knowledge based opportunistic forwarding in vehicular wireless ad hoc networks. In IEEE VTC Spring, 2005.
[24]J. Leguay, T. Friedman, and V. Conan. Dtn routing in a mobility pattern space. In ACM SIGCOMM Workshop on Delay Tolerant Networks, 2005.
[25]J. Leguay, T. Friedman, and V. Conan. Evaluating mobility pattern space routing for dtns. In IEEE Infocom, 2006.
[26]Y. Liao, K. Tan, Z. Zhang, and L. Gao. Estimation based erasure-coding routing in delay tolerant networks. In International Wireless Communications and Mobile Computing Conference, 2006.
[27]A. Lindgren and A. Doria. Probabilistic routing protocol for intermittently connected networks. Technical report, draft-lindgren-dtnrg-prophet-01.txt, IETF Internet draft, July 2005.
[28]A. Lindgren, A. Doria, and O. Schelen. Probabilistic routing in intermittently connected networks. ACM SIGMOBILE Mobile Computing and Communications Review, 7(3):19–20, July 2003.
[29]M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman. Efficient erasure correcting codes. IEEE Transactions on Information Theory, 47(2):569–584, February 2001.
[30]S. R. McCanne. Scalable Compression and Transmission of Internet Multicast Video. PhD thesis, University of California, Berkeley, 1996.
[31]J. Ott and D. Kutscher. Bundling the web: Http over dtn. In WNEPT, 2006.
[32]V. N. Padmanabhan, H. J. Wang, and P. A. Chou. Resilient peer-to-peer streaming. In IEEE ICNP, 2003.
[33]V. N. Padmanabhan, H. J. Wang, P. A. Chou, and K. Sripanidkulchai. Distributing streaming media content using cooperative networking. In IEEE NOSSDAV, 2002.
[34]J. Palme, A. Hopmann, and N. Shelness. Mime encapsulation of aggregate documents, such as html (mhtml). Technical report, IETF RFC 2557, March 1999.
[35]J. S. Plank and M. G. Thomason. A practical analysis of low-density parity-check erasure codes for wide-area storage applications. In The International Conference on Dependable Systems and Networks, 2004.
[36]D. Snowdon, N. Glance, and J.-L. Meunier. Pollen: using people as a communication medium. Elsevier Computer Networks, 35(4):429–442, February 2001.
[37]A. Vahdat and D. Becker. Epidemic routing for partially-connected ad hoc networks. Technical Report CS-2000-06, Duke University, 2000.
[38]R. Y. Wang, S. Sobti, N. Garg, E. Ziskind, J. Lai, and A. Krishnamurthy. Turning the postal system into a generic digital communication mechanism. In ACM SIGCOMM, 2004.
[39]Y. Wang, S. Jain, M. Martonosi, and K. Fall. Erasure coding based routing for Opportunistic Networks. In ACM SIGCOMM Workshop on Delay Tolerant Networks, 2005.
[40]Y. Wang and H. Wu. Dft-msn: The delay fault tolerant mobile sensor network for pervasive information gathering. In IEEE Infocom, 2006.
[41]H. Weatherspoon and J. D. Kubiatowicz. Erasure coding vs. replication: A quantitative comparison. In The 1st International Workshop on Peer-to-Peer Systems, March 2002.
[42]J. Widmer and J.-Y. L. Boudec. Network coding for efficient communication in extreme networks. In ACM SIGCOMM Workshop on Delay Tolerant Networks, 2005.
[43]Vikram Srinivasan, Mehul Motani, Wei Tsang Ooi. Analysis and Implications of Student Contact Patterns Derived from Campus Schedules, ACM MOBICOM 06.