行動視訊偵搜網路服務中節點指派及保持連線演算法之設計

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求解演算法實作成模組並且整合到視訊偵蒐系統軟體架構的應用層中，來實現自動化求解規劃節點移動位置建立涵蓋視訊連結的功能。

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.