交通大學資訊科學與工程研究所學位論文
國立交通大學,正常發行
選擇卷期
- 學位論文
Pawlewicz和Hayward於2013年成功證明出全部9x9 Hex開局盤面，以及一個特定的10x10開局盤面，其用來證明的程式只能使用單台機器的運算資源，因此無法更進一步並行化。在此研究中我們嘗試將該程式套用到工作層級UCT演算法上從而使其可以利用更多運算資源提高其並行度。在將其套用到工作層級系統之後，我們通過使用共享記憶體和資料庫技術使不同工作間的資訊可以被共享以提高搜尋效率。實驗結果顯示工作層級演算法可以提高並行度，而通過我們提出的這些技術，在單台機器上套用到工作層級框架上的程式可以比原本的程式證明同樣4個開局盤面中的3個花費更少的時間。當使用6台機器時，證明同樣的4個盤面，使用工作層級框架的程式效率是原本只能使用單台機器程式的1.6， 1.9， 1.8和2.6倍。
- 學位論文
在電腦遊戲的領域中，有許多平行化運算的方法被提出，其中的工作層級演算法已被成功用來建構開局庫以及解出部分六子棋的開局。目前已被提出的工作層級應用有工作層級證明數搜尋演算法用於六子棋、工作層級上界信賴樹演算法用於六子棋、Hex及工作層級alpha-beta搜尋演算法用於象棋，這些應用被獨立開發，卻有許多行為相似可以被共享，例如和工作層級系統的溝通以及最佳優先搜尋演算法(BFS)的通用行為等等。在本論文中，我們提出了一個工作層級應用的軟體開發框架，該框架實作了底層的溝通行為，並開放介面讓開發人員發展其應用，我們的框架更進一步提供BFS的基本模組，並成功分離出演算法相關部分及遊戲相關部分，讓不同的開發者得以獨立實作其演算法或遊戲。在案例研究中，我們的框架撰寫了一萬多行的程式碼，透過充分的共享，讓開發者只需要數百行的程式碼便能輕易開發出新的工作層級應用，由此可見透過我們的框架可以讓工作層級應用的開發更有效率。
- 學位論文
快閃記憶體儲存裝置因為高效能、抗震性、低功耗等特性，固態硬碟逐漸取代傳統硬碟作為主要儲存裝置。然而，為了進一步提升效能與容量，廠商傾向於採用多通道架構，雖然增加了整體平行度，但也使得裝置耗電提高，若不小心處理，固態硬碟峰值電流將超越傳統硬碟，低功耗將不再是快閃記憶體的優勢，除此之外，當峰值電流超越儲存裝置介面提供之功率預算，會使得裝置無法全速運作，造成效能損失。本研究我們提出動態控制峰值電流之排程演算法，首先透過實際量測建立出各種快閃記憶體操作之功耗，接著根據數學定理提出能有效控制峰值電流的排程演算法。相較於過去研究提出之基於個數之排程演算法，我們的演算法能達到更高的吞吐量。此外，現今快閃記憶體採用多階層儲存單元(Multi-layer cell)快閃記憶體，其成對頁(paired pages)彼此寫入速度以及功耗不相同，我們利用此特性提出減少裝置反應時間之寫入策略。
- 學位論文
近年來，由於以所在位置為基礎，所提供的地理位置服務的需求持續上升，使得行動定位技術近期內被深入且廣泛的研究。不像室外定位已經以全球定位系統(GPS)為大宗， 室內的解決方案必須考慮不同的傳感器輸入，各種環境的觀察，並透過融合技術將這些資訊相結合，來產生較為精確的位置結果。隨著移動/可穿戴技術漸趨成熟，合作式定位已經被提出並試著突破傳統定位的限制。在本文中，我們觀察到當多台裝置彼此碰面，我們稱之為“M2M相遇”，此時我們可以透過裝置間的即時數據交流，合作並完善彼此的位置資訊。利用可能在開放式空間常常發生的M2M相遇的機率性事件，我們可以頻繁的校準那些參與M2M相遇事件的裝置的粒子機率分佈。因此，通常用於融合單一裝置的環境觀察的粒子濾波器技術(稱為intra-PF)，被延伸到跨裝置的融合粒子濾波器的狀態的技術(稱為inter-PF)。此外，我們考慮了計算的複雜度，進一步的分割出近似的解決方案(稱為approximated inter-PF)。我們運用電腦模擬，以及利用智慧型平板的系統原型，在建有藍芽低能耗(BLE)基礎設施的辦公室環境中實地測試，來驗證了我們的intra-PF和inter-PF演算法。最後，我們證實透過額外的M2M相遇事件，具有較少的傳感器或更低的計算能力的裝 置，仍然可以享受能夠與那些擁有更豐富的感測信息的裝置相匹敵的良好定位品質。
- 學位論文
隨著科技日新月異，資料的數量也有著爆炸性的成長，因此資料的分群問題也逐漸變得重要。我們無法再透過人工的方式處理如此龐大數量的資料，所以必需利用電腦自動化完成人力所無法達成的，如此既快速、經濟又節省人力。本論文提出一個貝氏無母數非監督式學習法（Bayesian Non-parametric unsupervised Learning）。貝氏無母數方法在分群時不必事先決定資料群數，而是在分群的過程中讓資料自行決定需要分的群數。並且引用統計學裡的切比雪夫不等式 (Chebyshev's inequality) 的概念來調整先驗分布 (Prior) 的參數，使分群效果更佳。因此本論文延伸中國餐廳過程（Chinese Restaurant Process, CRP）進一步加入一個以統計觀點為基礎的計算方法，使分群的效果更為提升。此外，本論文在調整群數方面，提出了一個不同於原始 CRP 的方法，在決定資料點屬於哪一群時，若現有的資料群皆不適合該資料點時，則該資料點自成一群。最後實驗結果顯示本論文提出的方法表現優於其他非監督式學習法。
- 學位論文
監視攝影機目前被廣泛地使用來監控生活中各式各樣的事件，長時間以及大量的監視影片紀錄使得後續的瀏覽以及異常事件追蹤變得十分耗時。過去在此領域的研究為了提升瀏覽影片的效率，提出將影片中沒有事件發生的時空區塊移除並以同影片中其他事件填補，然而這樣將畫面呈現最大化的利用反而容易分散使用者的注意力。在注意力的相關文獻中顯示，當使用者必須同時追蹤影片中不同區塊的多重事件時較容易出錯，反而需要更多時間來消化影片中的資訊。因此本研究提出一種同調性的影像縮時方法來解決上述的缺點，採用事件發生的軌跡來做為同調性的依據，具有以下三個優點：(1)將相似的軌跡事件同時呈現使畫面簡潔而易於檢視與追蹤；(2)異常事件的軌跡篩選能夠簡化每個軌跡分群的內容，同時能夠分辨出可能需要警告的異常目標；(3)分群後的結果能夠有效率地搜尋特定目標。 本研究提出一套創新的分群系統，對輸入影片做背景去除演算法以及物件追蹤得到前景及其軌跡後，將所有軌跡的起點和終點做分組以得到此環境中的主要出入口位置，根據此結果配合各個軌跡的移動路徑進行分群計算，再對各個群的成員透過改良後的最長共同子序列演算法(DLCS)計算軌跡間的相似程度以篩選出群中可能存在的異常路徑。DLCS演算法保留了原始共同子序列演算法(LCS)中抗雜訊以及能夠比對伸縮軌跡的優點，同時改善了LCS演算法中無法計算兩軌跡間相異程度的缺點。得到最終的分群結果後將各個軌跡還原為影像，並計算彼此間的遮蔽率以做軌跡排程並產出壓縮影片。 本研究的實驗測試了不同場景、時間，長度的測試資料，並且在壓縮效率得到了平均73%的良好結果。在軌跡分群準確率有92%的良好結果，最後本研究提供了使用者參數調整實驗以探討不同遮蔽率下使用者個影片觀看效率比較。
- 學位論文
由於虛擬網路功能(Virtual Network Function , VNF)能夠把特殊的網路功能(如:防火牆、DNS)以軟體的方式呈現，並不需要專屬的硬體設備配合，這個特性能夠讓資料中心的設備需求變的簡單。也就是說，更新或增加任何的網路功能不用另外更動硬體。 同樣為了使雲端服務更靈活方便，在Openstack的發展中，也逐漸支援或提供愈來愈多的VNF。雲端平台上能提供的VNF數量會持續上升。放在雲端的服務，不管是雲端平台提供的，還是使用者自己放上雲端的，其服務的系統架構會愈來愈複雜。 於是一旦整個服務的其中一個環節出現問題，則會使整個系統不能正確提供服務。要改善這個問題，就要為我們的服務提供High Availability高可用性(HA)，使系統即使出現問題但仍能繼續正常運作。 在我們的論文中，我們著重探討在Openstack上之VNF的HA。我們提出了一個利用與HA相關的各種open software，並且配合shell script在虛擬機器(Virtual Machine, VM)上實現VNF的系統架構，此方法能運用在各種VNF上。然而因為VNF有太多種類，因此在我們的論文中挑選在實現HA上最為繁瑣的防火牆(Firewall ,FW)為討論對象，從Active Passive模式的防火牆到Active Active模式的防火牆皆在本論文的討論範圍內。 為了要達到防火牆的HA，我們至少需要做到三件事。首先，能夠讓網路封包能在原本負責的防火牆不能提供服務時，送到其他正常的防火牆提供服務。再來，就是要能夠把原本提供服務的防火牆設定的防火牆規則，與其他有可能接替服務的防火牆同步防火牆規則。最後，在將網路封包從不能提供服務之防火牆轉移到給其他正常的防火牆處理時，要能夠繼續維持原本的連線session，使得原本正在使用的網路連線繼續保持，不需要再重新連線。