Publications-Theses
Article View/Open
Publication Export
-
Google ScholarTM
NCCU Library
Citation Infomation
Related Publications in TAIR
題名 在機會網路上使用機率預測法搜尋行動代理人 之機制
Using probabilistic prediction method in the search of mobile agents over opportunistic network作者 游筱慈
You, Hsiao Tzu貢獻者 連耀南
Lien, Yao Nan
游筱慈
You, Hsiao Tzu關鍵詞 機率
預測
搜尋
機會網路
probability
prediction
search
opportunistic network日期 2012 上傳時間 3-Jun-2013 17:41:32 (UTC+8) 摘要 在機會網路上,訊息的遞送遠比一般網路來得困難許多,溝通交換資訊效率很低。本篇論文以山文誌資訊系統為背景,假設在山區中已佈建完成控制節點並組成控制網路,以及行動代理人機制已導入在控制網路上用來搜尋移動的目標節點。其中行動代理人附屬於登山客所攜帶的設備上,欲搜尋的目標節點會沿著登山路徑不斷移動造成搜尋上的困難,若搜尋失敗不只拉長延後了搜尋時間,也可能錯失黃金救難時間造成極大的損失,如何增進搜尋效率是機會網路上相當重要的議題。為此,本文提出一個搜尋方法,在任意的時間點計算目標行動節點落在每個控制節點之間路段的機率,預測目標代理人的位置,就可依機率高低逐次搜尋各路段,以提高搜尋效率。我們以山文誌登山資訊系統,作為參考的機會網路,提出兩個模型,使用機率預測搜尋法,預測行動節點可能所在位置優先搜尋此路段來降低整體搜尋時間,透過一連串的實驗驗證機率模型之準確度,並評估本法之搜尋效率以及當各路段花費時間的機率分佈假設有誤時,搜尋效率的受損程度。在我們的實驗中,機率模型之準確度極高,誤差不超過7.59%,搜尋效率都在44.44以上,即使機率分佈錯誤,搜尋效能仍高於二分搜尋法約2倍。
Since transmitting data on an opportunistic network is more difficult than that on a general network, information exchanging is less efficient. Based on “CenWits” system, we assume that control point has entirely construed all over the mountains and a control network has completed altogether; meanwhile, the mobile agent mechanism has applied in the searching of mobile target nodes. With mobile agent attached on the equipment of hikers, the target agent moving constantly along the hiking path grows the difficulties in searching. The failure in locating the mobile agent possibly not only prolongs the searching time, but also misses the golden time of life saving, and causes enormously damages eventually. Therefore, figuring that “improving the efficiency of searching” is a major issue in opportunistic network, in this thesis we develop a searching method which enables us to calculate the probability where a mobile target agent locates in every edge between control points in any arbitrary time point. Through forecasting the location of the target agent, we can start searching from the edge with the highest probability, thus enhance the efficiency of searching. Using “CenWits” system as reference opportunistic network, we designed two probability models as well as associated search methods. We conducted a series of experiments to evaluate the accuracy of probabilistic models and the performance of the proposed search methods. In our experiments, the error of probability models is no more than 7.59%. Our proposed methods out perform Basic Binary Search by 44.44 in average. Furthermore, assuming that there is a discrepancy between the probability assumptions and the real distribution of the traveling time spent on each edge, we evaluate the performance degradation too. The experimental results show that under such circumstance, our Probabilistic Prediction Method can even outperform Basic Binary Search by approximately 200%.參考文獻 [1] S. A. Tamhane, M. Kumar, A. Passarella, and M. Conti, "Service Composition in Opportunistic Networks," in Proc. of the 2012 IEEE International Conference on Green Computing and Communications, 2012, pp.285-292[2] L. Pelusi, A. Passarella, and M. Conti, "Opportunistic networking: data forwarding in disconnected mobile ad hoc networks," IEEE Communications Magazine, vol. 44, no. 11, pp. 134-141, Nov. 2006.[3] C.-M. Huang, K.-c. Lan, and C.-Z. Tsai, "A survey of opportunistic networks," in Proc. of the 22nd International Conference on Advanced Information Networking and Applications, 2008, pp. 1672-1677.[4] J. H. Huang, S. Amjad, and S. Mishra, "Cenwits: a sensor-based loosely coupled search and rescue system using witnesses," in Proc. of the 3rd International Conference on Embedded Networked Sensor Systems, 2005, pp. 180-191.[5] Y. T. Huang, Y. C. Chen, J. H. Huang, L. J. Chen, and P. Huang, "YushanNet: A delay-tolerant wireless sensor network for hiker tracking in Yushan national park," in Proc. of the 10th International Conference on Mobile Data Management: Systems, Services and Middleware, 2009, pp. 379-380.[6] Y. T. Huang, Y. C. Chen, J. H. Huang, L. J. Chen, and P. Huang, "YushanNet: A delay-tolerant wireless sensor network for hiker tracking in Yushan national park," in Proc. of the 10th International Conference on Mobile Data Management: Systems, Services and Middleware, 2009, pp. 379-380.[7] 陳伶志, 黃寶儀, and 黃致豪. "山文誌登山資訊系統." Internet: http://nrl.iis.sinica.edu.tw/YushanNet/tw_project.php, Retrieved on May. 1, 2013.[8] A. Fujihara, “ZebraNet and its theoretical analysis on distribution functions of datagathering times” in Proc. of the Second International Workshop on Mobile OpportunisticNetworking, 2010, pp. 205-206[9] M. Martonosi, “ZebraNet and beyond: applications and systems support for mobile, dynamic networks”, in Proc. of the 2008 International Conference on Compilers, architectures and synthesis for embedded systems, 2008, pp.21-21[10] S. Farrell, et al. "InterPlanetary Internet." Internet: http://www.ipnsig.org/, Retrieved on May. 1, 2013.[11] Y. Chen, and H. Wu “Communications and Architectures for Interplanetary Internet”, in Proc. of 2011First International Conference on Instrumentation, Measurement, Computer, Communication and Control, 2011, pp. 895-899 [12] E. Brewer, et al. "Technology and Infrastructure for Emerging Regions (TIER)." Internet: http://tier.cs.berkeley.edu/drupal/about, Retrieved on May. 1, 2013.[13] Z. Lu and J. Fan, "Delay/Disruption tolerant network and its application in military communications," in Proc. of the 2010 International Conference on Computer Design and Applications (ICCDA), 2010, pp. 231-234.[14] Y. Sasaki and Y. Shibata, "Distributed disaster information system in DTN based mobile communication environment," in Proc. of the 2010 International Conference on Broadband, Wireless Computing, Communication and Applications, 2010, pp. 274-277.[15] 陳禹銘, 祝鈞毅, 李雅萍, and 周子勤, "多工協調技術之應用與展望," 機械工業, no. 285, pp. 93-104, Dec. 2006.[16] D. S. Milojicic, F. Douglis, and R. Wheeler. Mobility: processes, computers, and agents. New York, NY: ACM Press/Addison-Wesley Publishing Co., 1999.[17] D. B. Lange and M. Oshima, "Seven good reasons for mobile agents," Communications of the ACM, vol. 42, no. 3, pp. 88-89, Mar. 1999.[18] L. T. Yang. Mobile Intelligence. Hoboken, NJ: John Wiley & Sons, Inc., 2010.[19] 楊柏華譯, "<<資訊新知>>:行動代理人技術(上)," 中央研究院計算中心通訊, vol. 18, no. 23, pp. 184-188, Nov. 2002.[20] 陳伶志, and 黃有德, "登山客的黑盒子," 中央研究院週報, no. 1376, pp. 4-6, June 2012.”[21] J. H. Huang, S. Amjad, and S. Mishra. "Cenwits Search and Rescue System." Internet: https://csel.cs.colorado.edu, Retrieved on May.1, 2013.[22] Y.N. Lien, Y.S. Lin, "Placement of control network for mobile agents overopportunistic networks," in Proc. of the 2012 IEEE International Conference on PervasiveComputing and Communications Workshops, 2012, pp.631-636 描述 碩士
國立政治大學
資訊科學學系
98753032
101資料來源 http://thesis.lib.nccu.edu.tw/record/#G0987530321 資料類型 thesis dc.contributor.advisor 連耀南 zh_TW dc.contributor.advisor Lien, Yao Nan en_US dc.contributor.author (Authors) 游筱慈 zh_TW dc.contributor.author (Authors) You, Hsiao Tzu en_US dc.creator (作者) 游筱慈 zh_TW dc.creator (作者) You, Hsiao Tzu en_US dc.date (日期) 2012 en_US dc.date.accessioned 3-Jun-2013 17:41:32 (UTC+8) - dc.date.available 3-Jun-2013 17:41:32 (UTC+8) - dc.date.issued (上傳時間) 3-Jun-2013 17:41:32 (UTC+8) - dc.identifier (Other Identifiers) G0987530321 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/58322 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 98753032 zh_TW dc.description (描述) 101 zh_TW dc.description.abstract (摘要) 在機會網路上,訊息的遞送遠比一般網路來得困難許多,溝通交換資訊效率很低。本篇論文以山文誌資訊系統為背景,假設在山區中已佈建完成控制節點並組成控制網路,以及行動代理人機制已導入在控制網路上用來搜尋移動的目標節點。其中行動代理人附屬於登山客所攜帶的設備上,欲搜尋的目標節點會沿著登山路徑不斷移動造成搜尋上的困難,若搜尋失敗不只拉長延後了搜尋時間,也可能錯失黃金救難時間造成極大的損失,如何增進搜尋效率是機會網路上相當重要的議題。為此,本文提出一個搜尋方法,在任意的時間點計算目標行動節點落在每個控制節點之間路段的機率,預測目標代理人的位置,就可依機率高低逐次搜尋各路段,以提高搜尋效率。我們以山文誌登山資訊系統,作為參考的機會網路,提出兩個模型,使用機率預測搜尋法,預測行動節點可能所在位置優先搜尋此路段來降低整體搜尋時間,透過一連串的實驗驗證機率模型之準確度,並評估本法之搜尋效率以及當各路段花費時間的機率分佈假設有誤時,搜尋效率的受損程度。在我們的實驗中,機率模型之準確度極高,誤差不超過7.59%,搜尋效率都在44.44以上,即使機率分佈錯誤,搜尋效能仍高於二分搜尋法約2倍。 zh_TW dc.description.abstract (摘要) Since transmitting data on an opportunistic network is more difficult than that on a general network, information exchanging is less efficient. Based on “CenWits” system, we assume that control point has entirely construed all over the mountains and a control network has completed altogether; meanwhile, the mobile agent mechanism has applied in the searching of mobile target nodes. With mobile agent attached on the equipment of hikers, the target agent moving constantly along the hiking path grows the difficulties in searching. The failure in locating the mobile agent possibly not only prolongs the searching time, but also misses the golden time of life saving, and causes enormously damages eventually. Therefore, figuring that “improving the efficiency of searching” is a major issue in opportunistic network, in this thesis we develop a searching method which enables us to calculate the probability where a mobile target agent locates in every edge between control points in any arbitrary time point. Through forecasting the location of the target agent, we can start searching from the edge with the highest probability, thus enhance the efficiency of searching. Using “CenWits” system as reference opportunistic network, we designed two probability models as well as associated search methods. We conducted a series of experiments to evaluate the accuracy of probabilistic models and the performance of the proposed search methods. In our experiments, the error of probability models is no more than 7.59%. Our proposed methods out perform Basic Binary Search by 44.44 in average. Furthermore, assuming that there is a discrepancy between the probability assumptions and the real distribution of the traveling time spent on each edge, we evaluate the performance degradation too. The experimental results show that under such circumstance, our Probabilistic Prediction Method can even outperform Basic Binary Search by approximately 200%. en_US dc.description.tableofcontents 第1章 1緒論 11.1 研究背景與目的 11.2 機會網路 21.2.1 機會網路的訊息交換機制 31.2.2 機會網路的研究議題 41.2.3 機會網路的應用 61.3 行動代理人 81.3.1 行動代理人的特點 91.3.2 行動代理人的優點 101.3.3 行動代理人的應用 111.4 運用行動代理人於機會網路 121.4.1 機會網路上的行動代理人運作 131.4.2 行動代理人平台的功能需求 131.5 論文組織架構 14第2章 相關研究與文獻探討 162.1 機會網路上搜尋行動代理人之挑戰 162.2 「山文誌登山資訊系統」簡介 162.3 機會網路上使用控制網路搜尋行動代理人 202.3.1 控制網路概念 212.3.2 利用控制網路的搜尋策略 222.4 控制網路上控制節點選擇問題之相關研究 232.4.1 控制網路的建置 232.4.2 環境假設 242.4.3 設計考量與目標 242.4.4 控制點選擇問題—最大總流量模型 252.4.5 控制點選擇問題—最大涵蓋率模型 252.4.6 控制點選擇問題—最大加權涵蓋率模型 26第3章 機會網路上行動代理人搜尋控制點選擇問題及解決方案 273.1 控制點選擇問題-最大複合加權涵蓋率模型 273.2 最大複合加權涵蓋率的數學模型 283.3 解決方案的演算法 293.3.1 控制點選擇問題的評估指標 303.3.2 CPSP-Coverage改進式解決方案- NPF2 演算法 323.3.3 CPSP-Utility改進式解決方案- NPF-U2 演算法 353.3.4 CPSP-Utility-Flow解決方案- NPF-PF 演算法 38第4章 機會網路上行動代理人位置之預測方法 404.1 預測方法設計理念與目標 404.2 問題定義 414.2.1 控制網路下搜尋名詞定義 414.2.2 問題模型 424.3 機率預測函數 444.3.1 Gamma分配 454.3.2 模型一使用計算機率預測法之搜尋程序 474.3.3 模型二使用計算機率預測法之搜尋程序 49第5章 效能評估 525.1 實驗設計 525.2 控制點選擇問題效能評估 545.2.1 小型問題效能評估 545.2.2 實驗1A環境參數設定 545.2.3 實驗1A結果與分析 555.2.4 大型問題效能評估 605.2.5 實驗1B環境參數設定 615.2.6 實驗1B結果與分析 615.2.7 實驗1C環境參數設定 645.2.8 實驗1C結果與分析 645.3 機率預測搜尋法效能評估 675.3.1 單一路徑機率預測準確度實驗 685.3.2 單一路徑機率預測搜尋法效能評估 745.3.3 單一路徑錯誤容忍度實驗 785.3.4 多重路徑機率預測準確度實驗 945.3.5 多重路徑機率預測搜尋法效能評估 975.3.6 多重路徑錯誤容忍度實驗 99第6章 結論與未來研究 107參考文獻 109 zh_TW dc.format.extent 2263935 bytes - dc.format.mimetype application/pdf - dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0987530321 en_US dc.subject (關鍵詞) 機率 zh_TW dc.subject (關鍵詞) 預測 zh_TW dc.subject (關鍵詞) 搜尋 zh_TW dc.subject (關鍵詞) 機會網路 zh_TW dc.subject (關鍵詞) probability en_US dc.subject (關鍵詞) prediction en_US dc.subject (關鍵詞) search en_US dc.subject (關鍵詞) opportunistic network en_US dc.title (題名) 在機會網路上使用機率預測法搜尋行動代理人 之機制 zh_TW dc.title (題名) Using probabilistic prediction method in the search of mobile agents over opportunistic network en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [1] S. A. Tamhane, M. Kumar, A. Passarella, and M. Conti, "Service Composition in Opportunistic Networks," in Proc. of the 2012 IEEE International Conference on Green Computing and Communications, 2012, pp.285-292[2] L. Pelusi, A. Passarella, and M. Conti, "Opportunistic networking: data forwarding in disconnected mobile ad hoc networks," IEEE Communications Magazine, vol. 44, no. 11, pp. 134-141, Nov. 2006.[3] C.-M. Huang, K.-c. Lan, and C.-Z. Tsai, "A survey of opportunistic networks," in Proc. of the 22nd International Conference on Advanced Information Networking and Applications, 2008, pp. 1672-1677.[4] J. H. Huang, S. Amjad, and S. Mishra, "Cenwits: a sensor-based loosely coupled search and rescue system using witnesses," in Proc. of the 3rd International Conference on Embedded Networked Sensor Systems, 2005, pp. 180-191.[5] Y. T. Huang, Y. C. Chen, J. H. Huang, L. J. Chen, and P. Huang, "YushanNet: A delay-tolerant wireless sensor network for hiker tracking in Yushan national park," in Proc. of the 10th International Conference on Mobile Data Management: Systems, Services and Middleware, 2009, pp. 379-380.[6] Y. T. Huang, Y. C. Chen, J. H. Huang, L. J. Chen, and P. Huang, "YushanNet: A delay-tolerant wireless sensor network for hiker tracking in Yushan national park," in Proc. of the 10th International Conference on Mobile Data Management: Systems, Services and Middleware, 2009, pp. 379-380.[7] 陳伶志, 黃寶儀, and 黃致豪. "山文誌登山資訊系統." Internet: http://nrl.iis.sinica.edu.tw/YushanNet/tw_project.php, Retrieved on May. 1, 2013.[8] A. Fujihara, “ZebraNet and its theoretical analysis on distribution functions of datagathering times” in Proc. of the Second International Workshop on Mobile OpportunisticNetworking, 2010, pp. 205-206[9] M. Martonosi, “ZebraNet and beyond: applications and systems support for mobile, dynamic networks”, in Proc. of the 2008 International Conference on Compilers, architectures and synthesis for embedded systems, 2008, pp.21-21[10] S. Farrell, et al. "InterPlanetary Internet." Internet: http://www.ipnsig.org/, Retrieved on May. 1, 2013.[11] Y. Chen, and H. Wu “Communications and Architectures for Interplanetary Internet”, in Proc. of 2011First International Conference on Instrumentation, Measurement, Computer, Communication and Control, 2011, pp. 895-899 [12] E. Brewer, et al. "Technology and Infrastructure for Emerging Regions (TIER)." Internet: http://tier.cs.berkeley.edu/drupal/about, Retrieved on May. 1, 2013.[13] Z. Lu and J. Fan, "Delay/Disruption tolerant network and its application in military communications," in Proc. of the 2010 International Conference on Computer Design and Applications (ICCDA), 2010, pp. 231-234.[14] Y. Sasaki and Y. Shibata, "Distributed disaster information system in DTN based mobile communication environment," in Proc. of the 2010 International Conference on Broadband, Wireless Computing, Communication and Applications, 2010, pp. 274-277.[15] 陳禹銘, 祝鈞毅, 李雅萍, and 周子勤, "多工協調技術之應用與展望," 機械工業, no. 285, pp. 93-104, Dec. 2006.[16] D. S. Milojicic, F. Douglis, and R. Wheeler. Mobility: processes, computers, and agents. New York, NY: ACM Press/Addison-Wesley Publishing Co., 1999.[17] D. B. Lange and M. Oshima, "Seven good reasons for mobile agents," Communications of the ACM, vol. 42, no. 3, pp. 88-89, Mar. 1999.[18] L. T. Yang. Mobile Intelligence. Hoboken, NJ: John Wiley & Sons, Inc., 2010.[19] 楊柏華譯, "<<資訊新知>>:行動代理人技術(上)," 中央研究院計算中心通訊, vol. 18, no. 23, pp. 184-188, Nov. 2002.[20] 陳伶志, and 黃有德, "登山客的黑盒子," 中央研究院週報, no. 1376, pp. 4-6, June 2012.”[21] J. H. Huang, S. Amjad, and S. Mishra. "Cenwits Search and Rescue System." Internet: https://csel.cs.colorado.edu, Retrieved on May.1, 2013.[22] Y.N. Lien, Y.S. Lin, "Placement of control network for mobile agents overopportunistic networks," in Proc. of the 2012 IEEE International Conference on PervasiveComputing and Communications Workshops, 2012, pp.631-636 zh_TW