請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46995
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張時中 | |
dc.contributor.author | Chia-Ching Lin | en |
dc.contributor.author | 林佳慶 | zh_TW |
dc.date.accessioned | 2021-06-15T05:44:52Z | - |
dc.date.available | 2010-10-19 | |
dc.date.copyright | 2010-08-20 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-08-19 | |
dc.identifier.citation | [Lyu08] Wun-Yan Lyu, “Research on Coverage Connection Establishment and Maintenance for Mobile Video Surveillance over Ad Hoc Networks”, Master Thesis, NTU EE, June 2008.
[Lin08] Jer-Wei Lin, “Design and Implementation of Energy Balance Routing for Mobile Video Surveillance over Ad Hoc Networks,” Master thesis, NTU EE, July 2008. [Cha07] Chia-Wei Chang, “Design and Implementation of Neighbor Information-based Mobile Video Surveillance Routing over Ad Hoc Networks”, Master Thesis, NTU EE, July 2007. [Lia06] Yu-Kai Liao, “Architecture Design of a Peer-to-Peer Mobile Video Surveillance Service on Wireless Network,” Master thesis, NTU EE, July 2006. [IEE99] IEEE Std. 802.11-1999, Parr 11: Wire/-s U N Medium Access Control (MAC) and Physical Layer (PHY) specifications, Reference number ISO/IEC 8802-11:1999(E), IEEE Std 802.11, 1999. [MAE08] http://mae.pennnet.com/articles/article_display.cfm?article_id=243563,“Networking tomorrow’s battlefields”. [CHI08] http://www.chip123.com/phpBB/archiver/?tid-12260.html, '災害現場WiMAX通訊指揮系統'. [RFC1189] U. Warrier and L. Besaw, “RTP: A Transport Protocol for Real-Time Applications,” IETF RFC 1889, October 1990. [RFC1190] CIP Working Group, “RTP Profile for Audio and Video Conferences with Minimal Control,” IETF RFC 1890, October 1990. [RFC2501] S. Corson and J. Macker, “Mobile Ad Hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,” IETF RFC 2501, January 1999. [PeR99] C.E. Perkins and E. M. Royer,' Ad Hoc On-Demand Distance Vector Routing,' Proceeding of IEEE Workshop on Mobile Computing February 1999.System and Applications 1999, pp.90-100. [OtL08] Akkaphop Otakahn, Mayuree Lertwatechakul, 'An Improvement of Ad Hoc Route Maintenance', 2008 International Symposium on Communications and Information Technologies (ISCIT 2008), pp. 95-99. [FFB08] Tullio Facchinetti, Gianluca Franchino, Giorgio Buttazzo, “A Distributed Coordination Protocol for the Connectivity Maintenance in a Network of Mobile Units” , 2008 IEEE Second International Conference on Sensor Technologies and Applications, pp. 764-769. [Zha96] Weixiong Zhang, “Branch-and-Bound Search Algorithms and Their Computational Complexity”, USC/Information Sciences Institute. May 1996. [SMR08] S. Sutor, F. Matusek and R. Reda,” WSSU: High Performance Wireless Self-Contained, Surveillance Unit; an Ad Hoc Video Surveillance System”. [LeP06] Jin Lee, Sin-Chong Park, “Area Efficient Pipelined VLSI Implementation of List Sphere Decoder”, 2006 IEEE Asia-Pacific Conference on • Communications(APCC), pp. 1-5. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46995 | - |
dc.description.abstract | 本論文發展一個更快速並且適合實作於晶片的演算法來求解行動視訊偵搜服務網路視訊涵蓋連結建立的問題,當目標物在網路取像涵蓋範圍外時,可快速的建立一條視訊連結來涵蓋目標物,以便將目標物的影像傳送給影像需求端。本論文利用呂文彥2008對於行動視訊偵搜服務網路所建構的初始涵蓋視訊連結數學模型(Initial Coverage and Connection Problem, ICCP)為基礎,以設計快速、質佳、且有潛力實作於晶片上為目標,發展一套ICCP問題的求解方法。
此外無線網路傳輸通道品質不穩定的情形,在呂文彥的研究中僅假設無線網路環境中沒有干擾且任務節點的電池能量階可以應付任務的需求。但實際在執行任務中,或因節點的能量會下降導致封包訊號的傳輸強度減弱,或因傳輸頻道環敬因素而影響視訊影像傳輸的品質。因此發展一套機制當傳輸通道品質不穩定時保持視訊連結完整也是一個重要的問題。 對於ICCP涵蓋視訊連結問題求解的方法,本論文以貪婪法則(Greedy Heuristic)和分支界定法(Branch-and-Bound)為基礎建立二階段貪婪分之界定法(Two Stage Greedy Branch-and-bound Solution Algorithm, TSGBA)來求解。首先透過貪婪式的步驟建構一條取向傳輸路徑,將此路徑指派節點移動的距離作為一個上限值,以減少後續分支界定法所需搜尋的路徑組合。接著再以深度優先搜尋(Depth first search)分支界定法搜尋其他可能的路徑組合。在搜尋的過程當中若某部分的任務節點移動距離已經超過了所設定的上限,便不再往下繼續搜尋以減少求解所花費的時間。分析TSGBA演算法得知其平均複雜度雖仍為指數型成長,但透過一開始所設定的上限,在大多數情況可以有效排除掉許多不可能的路徑組合,進而降低整體求解的時間。透過隨機產生30組網路節點的測試顯示,TSGBA在CPU 為Intel E8400@3.00GHz、記憶體2G的電腦上可在短時間內(10秒/10個網路節點)得到一組品質佳(平均與最佳解誤差5%)的指派結果。故雖然此演算法的複雜度為指數成長,但透過啟發式步驟定義出的上限可以有效縮短實際的計算時間,因此此演算法仍然具有製作於晶片上的潛力。 另外針對傳輸通道品質不穩定的情形,本論文也提出一套保持連線機制,包括: (1)週期性的感測任務節點剩餘能量以及封包接收訊號強度、(2)針對節點電池能量與接收封包強度兩項指標分別定義兩層臨界點以決定機制啟動時機、(3)利用TSGBA求解演算法重新求解涵蓋視訊連結問題找尋替代路徑。透過此機制可減少連線因傳輸通道品質不佳而中斷的機率。 本論文且將TSGBA進行實作。實作的環境延用了呂文彥2008在應用層中使用VB.NET 2003TM 所實作的視訊偵蒐系統 (包括自身廣播系統以及指揮機制) ,接著以Visual Basic程式語言將TSGBA求解演算法實作成模組並且整合到視訊偵蒐系統軟體架構的應用層中,來實現自動化求解規劃節點移動位置建立涵蓋視訊連結的功能。 | zh_TW |
dc.description.abstract | This thesis develops a rapid and suitable for VLSI implementation algorithm to solve the connection establishment problem of a mobile video surveillance system. When the target is out of the coverage, this algorithm can establish a video connection to cover the target quickly and stream the target’s image to the requesting node. Base on the mathematical model, Initial and Coverage Connection Problem (ICCP), established by Wun-Yan Lyu 2008, we design a solution algorithm to solve this problem for the purpose of fast, good quality and has the potential to implement.
For the unstable transmission quality in wireless networks, the research of 呂文彥 does not address much. He assumes that there is no interference within the network and battery energy of each node can meet requirements of missions. Nevertheless, the real situation is that the energy of the node would decrease continuously to attenuate the transmission strength of packets and then affect qualities of videos. Thus, to develop the mechanism to maintain the completeness of video connection when the quality of transmission channel is not great is also an vital issue. Based on the Greedy Heuristic and the Branch-and-Bound methodology, this thesis first, by the heuristic step, sets the upper bound of the moving distance of the assigned node to reduce the path combinations that the second part of the algorithm needs to search. Next, the thesis utilizes the Depth First Search of the Branch and Bound methodology to find the shortest path and then designs the Two Stage Greedy Branch and bound Algorithm (TSGBA), which is adapted to be embedded in chips, for solving the ICCP. TSGBA can obtain an assignment result with good quality (averagely 5% inaccuracy to optimal solutions) in a short time period (10seconds/ 10 nodes within networks.) This thesis also addresses the mechanism for maintaining connections for the issues of unstable transmission channel quality. The main concepts are: (1) the periodic inspection of residual energy in mission nodes and packet receiving strength (2) the definitions of the critical points in two layers for battery energies of nodes and packet receiving strength to identify the activation time (3) The exploitation of the TSGBA to re-solve ICCP for finding substitutive paths. This mechanism would re-assign the locations of nodes to avoid the break off of connections, when the transmission quality is lower than some level in the mission. As for the implementation, this thesis inherits the interfaces of Wun-Yan Lyu 2008 (the self broadcast system and the commanding mechanism) that were developed via VB.NET 2003TM in the application layer. Using Visual Basic programming language to implement TSGBA as an object and integrate it in the interfaces, this thesis can achieve the automatic solution findings of node location assignments for establishing video coverage connections without optimization tool suites. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T05:44:52Z (GMT). No. of bitstreams: 1 ntu-99-R97921015-1.pdf: 2023481 bytes, checksum: 4e77a06612ba33c196c967e25fad7361 (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | 口試委員會審定書
誌謝 中文摘要-----------------------------------i 英文摘要---------------------------------iii 第一章 行動視訊偵搜隨意網路服務簡介------------1 1.1 行動視訊偵搜服務的研究動機-------------1 1.2 文獻摘要----------------------------2 1.3 研究範疇----------------------------4 1.4 論文組織架構-------------------------7 第二章 行動視訊偵搜服務節點位置指派與連線保持的問題與挑戰---------9 2.1 以Ad Hoc無線隨意網路實現行動視訊偵搜服務系統-----------11 2.1.1 IEEE 802.11b/g協定架構簡介------------------------11 2.1.2 行動無線隨意網路(Mobile Ad Hoc Network, MANET)簡介--14 2.2 現有行動視訊偵搜網路整體架構-------------------------16 2.3 ICCP問題模型建立與TSSA演算法介紹---------------------20 2.3.1 ICCP涵蓋視訊連結問題模型[Lyu08]---------------------20 2.3.2 TSSA求解演算法[Lyu08]-----------------------------25 2.4 行動視訊偵搜服務連結建立與保持的問題與挑戰--------------26 2.4.1 行動視訊偵搜任務節點指派與保持連線之問題----------------26 2.4.2 行動視訊偵搜任務節點指派與保持連線之挑戰----------------28 第三章 ICCP問題求解演算法設計-------------------------------29 3.1 二階段貪婪分支定介求解演算法--------------------------30 3.2 求解演算法複雜度分析---------------------------------36 3.2.1 求解演算法複雜度分析---------------------------------36 3.2.2 求解演算法最佳性分析---------------------------------37 3.3 求解演算法例子測試與統計分析---------------------------42 3.3.1 求解演算法例子測試-----------------------------------42 3.3.2 TSGBA求解演算法統計分析------------------------------49 第四章 涵蓋並建立視訊連結簡易模擬與實作-------------------------55 4.1 行動視訊偵搜網路實作架設------------------------------56 4.2 自動化求解涵蓋並建立視訊連結實作展示--------------------58 第五章 保持連線機制系統設計----------------------------------63 5.1 動態調整節點以保持連線的問題描述-----------------------64 5.2 保持連線機制系統機制設計------------------------------65 5.2.1 保持連線機制系統流程圖--------------------------------65 5.2.2 保持連線機制系統啟動臨界點定義-------------------------67 5.2.3 替代路徑建立----------------------------------------69 第六章 結論與未來研究方向------------------------------------71 6.1 結論----------------------------------------------71 6.2 未來研究方向----------------------------------------74 參考文獻---------------------------------------------------75 | |
dc.language.iso | zh-TW | |
dc.title | 行動視訊偵搜網路服務中節點指派及保持連線演算法之設計 | zh_TW |
dc.title | Effective Node Location Assignment and Connectivity Maintenance for Mobile Video Surveillance Service on Wireless Ad Hoc Networks | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 蔡志宏,林宗男,孫雅麗 | |
dc.subject.keyword | 無線隨意網路,行動視訊偵搜,涵蓋範圍,指揮移動,視訊連結,分支介界定法, | zh_TW |
dc.subject.keyword | mobile video surveillance,coverage,command to move,connection,establishment,maintenance, | en |
dc.relation.page | 76 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2010-08-19 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 1.98 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。