• 學位論文

雲端運算下的節能負載平衡

雲端運算是近年來熱門的議題，透過虛擬化的機制讓虛擬機器共享同一台實體機器上的硬體資源進而提高實體機器上的資源利用度。然而，雲端資料中心需要負載平衡來避免系統中因為某些實體機器上的負擔過重，導致執行效率降低、硬體錯誤甚至當機的情形發生。我們在這篇論文中提出一個將雲端系統中的負載平衡問題轉換成一個權重雙分圖，再透過Hungarian演算法求解其上之最小權重的一組配對，依照得到的配對，平行的將虛擬機器遷移到負擔較低的機器上。一次的配對可以處理系統中多個負擔過重的實體機器來減低系統達到平衡的時間，降低虛擬機器間競爭資源的情形，進而提升系統的產能。我們利用CloudSim這個模擬器來測試我們演算法的效能，實驗的結果顯示我們在各種資源負載平衡的狀態之下，不論是系統達到平衡的時間以及各個虛擬機器上應用程式的執行完成時間皆大幅的下降。我們更利用XCP 雲端平台來搭建我們自己的小型雲端環境來證明我們的演算法在實際的雲端平台上也可以使用。此外，雲端的資料中心為了提供大量運算環境而需要許多伺服器，這些伺服器同時運行造成了大量的能源消耗和碳的排放量。所以我們改良我們的負載平衡演算法，當系統中的工作量降低時，去評估目前需要的伺服器數目，並將多餘的伺服器關閉，在負載平衡的同時達到節能的效果。

• 學位論文

應用動態樁技術於合作式網頁應用程式測試

現今，在網際網路上大量的免費人力資源通常被運用來減少測試成本與驗證軟體，如：線上遊戲與開放原始碼軟體。然而，傳統的合作測試方法在不考慮大眾測試者有共同的測試偏好與測試者素質參差不齊的情況下，往往會有測試時間難以收斂與測試報告的可信度不高等議題。為了加速收斂網站測試，有必要應用細顆粒的網頁應用程式模型來平行化測試工作。在這篇研究中，首先我們提出狀態轉換圖來為使用者的執行行為建模以達到分解網頁應用程式測試問題的目的。更進一步為了達到加速測試速度與改善測試報告的品質，並且減少合作測試的總成本，我們提出了一個動態樁技術來引導使用者進行測試。動態樁技術結合所提出的細顆粒的網頁應用程式模型可以在大眾測試者沒有察覺的情況下改變測試環境來導引他們解決子問題。實驗結果顯示我們所提出的方法可以減少50﹪的測試成本與增加30﹪的偵測效能。

• 學位論文

資料探勘技術於病人疼痛自控裝置之應用與分析

病患在接受手術後通常會發生疼痛的現象，嚴重的疼痛可能會影響到傷口的癒合。因此，如何有效地減緩術後疼痛現象是相當重要的。病人疼痛自控止痛法(Patient-Controlled Analgesia ,PCA)相較於傳統肌肉注射止痛法(Intramuscular Injection ,IM)更能有效且快速地減緩疼痛現象。本研究應用資料探勘技術，用以預測病患短期未來之內使用PCA裝置之情況。分析的資料來源為彰化基督教醫院，透過麻醉醫師的協助，我們收集了1099筆病患在術後使用PCA裝置的記錄。我們做了以下的預測分析：(1) 麻醉藥劑量預測，(2) PCA裝置參數設定調整預測。將預測及屬性分析結果提供給麻醉醫師參考，藉此更了解病患使用PCA裝置之情況，而能更有效地為病患減輕術後疼痛。

• 學位論文

適用於ETC多車道環境下的執法演算法

在電子收費（Electronic toll collection, ETC）系統中，利用車上機（On-Board Unit, OBU）與路邊節點(Roadside Unit, RSU)快速的資料交換，可降低收費處理時間，進而提升車流量。ETC系統由四個模組構成：自動車輛辨識模組、自動車輛分類模組、扣款模組、影像執法模組。其中影像執法模組將每張車牌影像透過自動化車牌辨識 (Automatic License Plate Recognition, ALPR) 產生牌照號碼，再利用牌照號碼與車輛扣款資料比對找出未繳費與交易未成功之車輛。然而大量的車牌辨識會造成ETC系統的瓶頸。此外牌照號碼與車輛扣款資料比對之運算，多車道(Multi-Lane Free Flow, MLFF)比單車道(Single-Lane Free Flow, SLFF)來的複雜。在本篇論文中，我們提出一個適用於ETC多車道環境下之模組，將車牌影像資料和扣款資訊匹配關係轉換成雙分圖(Bipartite Graph)。針對雙分圖提出演算法以找出未繳費與交易未成功之車輛。模擬的結果顯示出，我們提出的演算法可大幅的降低影像辨識的次數並提高執法系統的成功率。

• 學位論文

一個對時序工作流程管理系統進行分析的研究

現代化企業利用工作流程管理系統統整文件、資訊系統以及人事組織以遂行其企業目的，而針對工作流程進行分析，有助於尋找企業程序中所隱藏的問題，避免工作流程執行時重複發生的錯誤，進而增進企業整體的效率；由於大部分具有良好行為之工作流程皆可轉換為結構化工作流程，因此結構化工作流程模型是在進行工作流程結構健全性分析時不可或缺的工具，此外，時序為進行工作流程正確性檢查、驗證以及工作流程效率分析上必須考量之因素，在此博士論文中，我們將時序因素與結構化工作流程模型結合統整而成一結構化時序工作流程模型，並且針對三種不同的領域，提出各自的分析方法；在組織分析領域，針對使用任務與角色為基存取控制模型的工作流程管理系統，我們建立了一個可以進行工作代理的執行框架，在此框架下，代理行為受到責任分擔以及企業政策的制約，使用者可以手動進行工作代理授權，而系統也可以自動將緊急的工作授權給適合的代理人；在資料分析領域，我們建立了一個從結構化時序工作流程中偵測異常文件使用的方法，藉由這個方法對工作流程定義進行靜態分析，可以有效避免由於異常資料操作所造成的系統意外行為；最後，針對資源領域，我們提出了一個可以在結構化時序工作流程建構的過程中，進行資源一致性與時序條件分析的遞增性分析方法，藉由我們的方法，工作流程設計者可以瞭解他所做的每一個設計決定對於整體工作流程定義的影響，並且修正由於錯誤的設計邏輯所造成的潛在資源衝突。

• 學位論文

當機器導盲犬用之有視覺自動車在人行道上導航之研究

本研究提出了一個利用有視覺的自動車在戶外人行道上作機器導盲犬應用的系統，該系統利用一部搭載雙鏡面環場攝影機的自動車當作實驗平台，能在環場影像中直接求出實際物體的立體資訊。首先，利用環境學習的技術建立導航地圖，此地圖包含自動車導航路徑、沿途路標的位置，以及相關的導航參數。接著，利用人行道上特定的路標(人行道路緣、消防栓和電線杆)作定位來輔助導航，本研究整合上述兩項技術提出一個擁有自動定位和自動導航功能的自動車系統。 此外，本研究亦利用空間映射的方法提出新的直線偵測技術，能夠在環場影像上直接偵測出直線特徵，並計算出人行道上垂直形狀路標的位置，進而提出偵測以及定位消防栓和電線杆的方法。最後利用已定位的路標位置，來校正機械誤差，並算出正確的自動車位置。接著，本研究也提出自動跟隨人行道路緣線的技術，以及一項新的動態障礙物偵測技術，利用一「地板配對表」定出障礙物位置，讓自動車穩定且不間斷地完成導航，並在導航路徑中閃避障礙物。此外，本研究亦提出動態調整曝光值以及動態調整門檻值的技術，讓系統適應戶外環境的各種光影變化。實驗結果顯示本研究所提方法完整可行。

• 學位論文

利用架設在視訊監控車上成對的全方位攝影裝置作週遭環境監控之研究

本研究利用架設在一視訊監控車頂上的兩組全方位攝影裝置來達到視訊監控的功能，主要應用於監控行車視角的盲點和周遭的車輛。 在本研究中，此二全方位攝影機裝置可用以監看車輛周遭任何角度的影像畫面。此外，本研究利用光流分析法直接套用在連續擷取的影像上，並利用影像的移動向量分析目前車輛的行走方向，產生對應方位的透視影像(perspective-view image)，方便駕駛觀看。另一方面，本研究亦提出一種「透視對應表」(perspective mapping table)，可以快速地將全方位影像轉成透視影像，提供駕駛觀看行車紀錄。 同時，本研究利用全方位攝影系統所拍攝的影像，可靜態監控周遭靜止的車輛並求得立體資訊。另利用影像處理技術取出影像中的車體區域，並偵測車窗底緣的對應點，計算車輛位置，進而產生監控車週遭環境的俯視圖。 除了偵測靜態的車輛，本研究也提出了行駛當中的視訊監控車偵測到停止或移動的周遭車輛的方法。另亦使用光流分析法，配合全方位攝影機所擷取到的連續影像，利用有高度的物體會產生較大移動向量的性質，將車體給大致分割出來，進而使用「k均值分群法」(k-means clustering)去偵測出車體，接著透過區域增長法去找出較完整的車體，最後再利用預先造好的車輛模型去做比對，藉以取得周遭車輛的位置資訊，劃出車輛周遭的俯視圖，供車輛駕駛觀看。 上述方法的實驗結果皆甚良好，顯示所提視訊監控系統確實可行。

• 學位論文

應用於車載隨意網路環境下以移動式閘道器為基礎之路由協定

近幾年來車載隨意網路(Vehicular Ad Hoc NETwork, VANET)的相關研究越來越受重視，已成為炙手可熱的研究議題。在設計車間(vehicle-to-vehicle, V2V)通訊的路由協定上，必須考量到有時因車輛移動的速度變化太快，而造成通訊中斷的狀況。然而利用車輛對基礎建設網路(vehicle-to-infrastructure, V2I)的溝通可以大幅改善以上的問題。在此篇論文中，我們提出一個路由協定名為MGRP(Mobile-Gateway Routing Protocol)協定，MGRP協定結合了V2V和V2I兩者的通訊方式，在系統中，所有的車輛都具備有802.11的通訊介面，此外，部分的車輛另具備3G的介面，這些車輛稱為移動式閘道器。而移動式閘道器可透過IEEE 802.11介面接收一般車輛的封包，再利用3G介面將封包經由基地台送至閘道器控制中心。而閘道器控制中心會依據目的地車輛的位置，尋找目的地周邊的移動式閘道器，並將封包轉送給這些移動式閘道器，透過移動式閘道器以廣播的方式將封包送至目的地車輛。實驗結果顯示，我們提出的MGRP比起傳統的GPSR(Greedy Perimeter Stateless Routing for Wireless Networks)協定明顯提升封包傳送率以及縮短整體路徑。

• 學位論文

網路拓樸的遞移性:以流行性傳染病的潛在感染風險為例

分析網路拓樸動態產生的遞移性現象，儼然已成為研究網路拓樸亟需解決也不可或缺的需求。經由分析遞移性現象找出網路各節點在動態傳播過程中的影響力及重要性，就能控制核心節點來達到影響群體、主宰網路訊息傳遞的效果，對於網路拓樸所反映的現實實體層面即可提供有價值的參考資訊。本研究中，將過往探討遞移性現象的理論模型延伸擴充，依據網路拓樸架構及連結所呈現的權重值，分析動態傳播過程中每個節點的重要性。透過重要性的排序比較，得以找出關鍵的核心節點，解決現今研究網路拓樸的需求。 在本文以實際流行病傳播動態為案例研究來驗證演算法的正確性，並使用基因演算法優選在流行病傳播現象中，最貼近實際傳播動態的網路拓樸結構。實驗結果顯示經本模型分析，病原體遞移傳播對各節點的重要性造成的影響與案例研究比對呈現正相關性，證實本研究方法能夠有效處理遞移概念並分析各節點重要性。此外透過基因演算法搜尋結果也可顯示出實際流行病的傳播動態以及造成傳播的影響因素。

• 學位論文

實況與移時影音串流系統的實作與效能評估

點對點式網路架構目前廣泛應用於多媒體影音串流服務中，用以解決過去主從式網路架構所無法負荷的龐大流量。然而在點對點影音串流的蓬勃發展中，移時影音串流服務，也就是提供使用者觀看任意過去時間點上的影音串流服務的相關研究並不多。 於此篇論文中，我們提出了一個數學模型來評估移時影音串流服務的可行性，並且實作了一支援移時服務的點對點實況串流系統。此系統提出針對移時串流影音資料的分散式快取管理解決策略，並加強移時影音用戶的合作關係以分散對於整體系統的負擔。最後我們在PlanetLab平台上進行實驗，分析整體系統的效能以及特性。在我們實驗中全部移時用戶錯過少於0.5%的影音片段，並且只有造成影音伺服器少於全部移時影音服務流量的3%的負擔。而移時串流訂閱機制使移時用戶直接分享正在觀看的影音內容，其中有30%的移時串流流量來自此種方式，並且降低了15%原本需由實況用戶提供的移時串流流量。我們相信這將提供此類系統的一般性了解，幫助我們進一步的發展多媒體串流服務。