關於MDCLAB

關於 MDCLAB

MDCLAB

行動暨分散式計算研究室(Mobile and Distributed Computing Laboratory)由蔡明哲教授成立於西元2003年秋。

聯絡我們

國立清華大學資電館834室

(03)571-5131 ext 33913

實驗室目標

訓練學生獨立與嚴謹的思考及研究能力,未來能帶領其團隊在學術界(或在業界)發表有影響力的頂尖論文(或高品質產品)。

目前已有多位研究生成果取得國際專利或發表在國際重要期刊或會議,分別敘述如下,其中TC (TMC,TWC)表示IEEE Transactions on Computers (Mobile Computing, Wireless Communications),TON表示IEEE/ACM Transactions on Networking,CN 表示Computer Networks,INFOCOM表示IEEE International Conference on Computer Communications,ICCCN表示IEEE International Conference on Computer Communications and Networks,ICC表示IEEE International Conference on Communications,ICDCS表示IEEE International Conference on Distributed Computing Systems,MobiHoc表示ACM International Symposium on Mobile Ad Hoc Networking and Computing:

  1. 劉炳宏(Bing-Hong Liu,2008年博士班畢):從事使用無線感測網路(Wireless Sensor Network)偵測移動物體的研究,任職高雄應用科技大學電子工程系;主要成果包括提出建立分散式資料庫來有效率更新及查詢移動物體的資訊(TC 2008)以及提出藉由網路節點傳遞少量固定資料量便可精準預測物體未來移動軌跡的方法,不同於文獻上的方法網路節點間需傳遞大量的物體歷史移動資訊,因此所提的方法是當時文獻上第一個可適用於節點有電力限制的無線感測網路(TC 2011)。
  2. 楊弘源(Hong-Yen Yang,2009年博士班畢):從事行動隨意網路(Mobile Ad Hoc Network)及無線感測網路繞徑方法的研究,任職聯發科技公司;在行動隨意網路的成果是提出建立連結性虛擬骨幹(用來增加繞徑效能)的方法,是當時文獻上第一個在網路節點可隨意移動下可保證虛擬骨幹連結性的方法(TMC 2008);在無線感測網路的成果是提出分配網路節點虛擬座標的方法及基於虛擬座標的繞徑方法,是當時文獻上第一個不需要整個網路拓墣資訊可保證封包送達的方法(INFOCOM 2007,TON 2009)。
  3. 林佳宏(Chia-Hung Lin,2009年博士班畢):從事無線感測網路及無線隨意網路(Wireless Ad Hoc Network)繞徑方法的研究,任職晨星半導體公司;在無線感測網路的成果包括提出在網路節點間具單向通道下分配節點虛擬座標的方法及基於虛擬座標的繞徑方法(INFOCOM 2008),以及提出分配網路節點虛擬座標及基於虛擬座標的資料存取系統(Information Brokerage Scheme),是當時文獻上第一個不需要節點地理座標可保證資料存取系統具有distance-sensitive的性質,也就是需求資料節點到具有需求資料中介節點的距離與提供資料節點到此資料中介節點的距離總和與需求資料節點到提供資料節點的距離在一個固定比例內(INFOCOM 2010,TC 2012);在無線隨意網路的成果是提出當時文獻上第一個決定FACE(最著名可將封包脫離死結區域的方法)有效率繞行方向(順時針或逆時針)的方法,此方法可提升各種採用FACE方法將封包脫離死結區域繞徑方法的效能(TC 2010 );除此之外,他也發現隨意感測網路的著名分群方法HEED一些新性質(TMC 2006)。
  4. 柯崴傑(Wei-Chieh Ke,2011年博士班畢):從事佈建無線感測網路的研究;主要成果是提出佈建具有連結性最小網路覆蓋關鍵區域問題是NP-complete,在當時文獻上是第一個提出證明具連結性解問題(佈建具有連結性最小網路覆蓋關鍵區域問題的解是具有連結性網路,所以其解具連結性)是NP-complete的方法(TC 2007,CN 2011),並且他也提出此問題的近似方法(TWC 2011)。
  5. 鄭元博(Yuan-Po Cheng,2012年博士班畢):從事無線感測網路及無線隨意網路繞徑方法的研究,任職工業技術研究院資訊與通訊研究所;在無線感測網路的成果是提出分配網路節點虛擬座標的方法及基於虛擬座標保證封包送達的繞徑方法,提出的分配網路節點虛擬座標方法是當時文獻上第一個當網路拓墣改變(由於移入或移出網路節點)只需非常少的訊息交換局部重新分配網路節點虛擬座標便可使其繞徑方法保證封包送達,因此可適用於節點有電力限制因而會發生網路拓墣改變的無線感測器網路(TWC 2014);在無線隨意網路的成果是突破了FACE(最著名可將封包脫離死結區域的方法)只能在平面圖才可將封包脫離死結區域的限制,提出可保證FACE可將封包脫離死結區域的充分條件,保證FACE在符合充分條件的非平面圖可將封包脫離死結區域(MobiHoc 2015);除此之外,他在三維無線隨意網路提出當時文獻上第一個具有distance-sensitive的資料存取系統(TC 2013)。
  6. 郭建志(Jian-Jhih Kuo,2014年博士班畢):從事雲端網路及軟體定義網路的研究,任職中央研究院資訊科學所;在雲端網路的成果是提出工作與分配機器間及任兩個分配機器間的最大距離的最小化問題是NP-complete及其近似方法,是當時文獻上第一個探討限制分配機器間距離的工作機器分配問題,適用於虛擬機器間需交換訊息來處理共同數據節點資料的雲端網路(INFOCOM 2014);在軟體定義網路的成果是提出分配服務鏈(Service Chain)需求路徑及伺服器(多個伺服器可共同執行服務鏈的虛擬化網路功能(Virtual Network Function))達到最大網路流量問題是NP-complete及其近似方法,是當時文獻上第一個在考慮伺服器具有處理網路流量限制下,分配服務鏈需求路徑及伺服器的問題(INFOCOM 2017);在軟體定義網路的另一個成果是提出建立最小成本服務鏈多播樹問題是NP-complete及其近似方法,是當時文獻上第一個在軟體定義網路上嘗試建立服務鏈多播樹的問題(ICDCS 2017)。
  7. 郭桐惟(Tung-Wei Kuo,2015年博士班畢):從事無線感測網路,無線隨意網路,及雲端網路的研究,任職政治大學資訊科學系;在無線感測網路的成果是提出建立資料聚合樹來達到最少傳輸能量消耗的問題是 NP-complete及其近似方法,適用於節點有電力限制的無線感測器網路(INFOCOM 2012,TC 2016);在無線隨意網路的成果是提出具連通性次模集函數(submodular function)最大化問題是 NP-complete及其近似方法,是當時文獻上第一個探討限制被選擇元素集合需具連通性的次模集函數最大化問題,適用於佈建具有最大覆蓋區域大小,覆蓋使用者數目,和頻寬吞吐量(及各種可以次模集函數表示的目標)網路節點需具連通性的無線隨意網路(INFOCOM 2013,TON 2015);在雲端網路的成果是提出分配需求的路徑及伺服器(用以執行服務鏈的虛擬化網路功能)達到最多服務鏈的問題是不存在近似方法,因而提出根據網路資源(包括伺服器及網路通道)使用情況及服務鏈虛擬化網路功能種類及數目計算服務鏈需求最佳路徑長度的方法,進而提出根據服務鏈最佳需求路徑長度分配服務鏈需求路徑及伺服器的方法(INFOCOM 2016);除此之外,他也提出一個考慮用戶通道特性及公平性來分配用戶允許傳輸資料的方法,使得系統能達到最大的資料傳輸吞吐量(TWC 2014)。
  8. 湯曜任(Yao-Jen Tang,2017年博士班畢):從事行動隨意網路的研究;成果是在行動隨意網路提出網路節點不具備地理座標下,當時文獻上第一個具有distance-sensitive的資料存取系統(ICCCN 2014,CN 2017),以及當時文獻上第一個考慮鄰近網路節點地理位置過時的繞路方法(ICC 2017)。
  9. 汪芳如(Fang-Ru Wang,2008年碩士班畢):從事無線感測網路繞徑方法的研究,任職聯發科技公司;成果是提出在網路節點不具備地理座標的網路可將封包脫離死結區域的方法,是當時文獻上第一個可結合各種基於虛擬座標的繞徑方法,使這些方法保證封包送達(INFOCOM 2009)。
  10. 謝雨岑(Yu-Tsen Hsieh,2012年碩士班畢):從事定位方法的研究,任職台灣積體電路公司;成果是與工業技術研究院合作提出使用路邊資料交換網路的方法,可應用在改善全球定位系統準確度,並且解決距離參考站遠的全球定位系統準確度較差的問題(US Patent 2014)。

研究

分散式演算法

研究由網路節點分散式執行的網路協定,研究主題包括:

  1. 路由協定 (Routing Protocol):路由協定是用來傳送網路上節點間的封包,我們探討理論上保證送達封包的方法。
  2. 資料存取系統 (Data Storage and Retrieval Scheme):資料存取系統可讓網路上的節點有效率的取得所要的資料,我們探討節點在限制距離內理論上保證取得所要資料的方法。

近似演算法

研究應用在網路上問題的困難度,探討網路上NP-complete問題的近似演算法,研究主題包括:

  1. 無線感測器/路由器部署 (Wireless Sensor/Router Deployment):我們探討的問題是尋求覆蓋最大範圍/最多使用者的無線感測器/路由器部署方式。
  2. 資料備份 (Data Backup Scheme):資料備份是網路中用來避免資料因各種因素遺失的必要方式,我們探討的問題是尋求建立花費最少資料傳輸能量的資料備份方式。
  3. 資料聚合 (Data Aggregation Scheme):資料聚合是網路中常見用來節省資料傳輸能量的方法,我們探討的問題是尋求建立花費最少資料傳輸能量的資料聚合路線。

成員

蔡明哲 教授

國立台灣大學博士

研究領域

行動隨意網路、無線感測器網路

聯絡

mjtsai[AT]cs.nthu.edu.tw

李宗韋

博士班

聯絡

chungweli[AT]hotmail.com

張子文

博士班

聯絡

g9962515[AT]cs.nthu.edu.tw

陳鈺書

博士班

聯絡

azyEagles[AT]gmail.com

康宏瑜

博士班

聯絡

andy082866[AT]gmail.com

羅惠琦

碩士班

聯絡

ritalo39[AT]gmail.com

朱翊文

碩士班

聯絡

darthvader627[AT]gmail.com

徐偉涵

碩士班

聯絡

cheatfinish123[AT]yahoo.com.tw

侯舒晏

碩士班

聯絡

bastgirlsusan[AT]gmail.com

林孟翰

碩士班

聯絡

lemontea1011[AT]yahoo.com.tw

已畢業成員

PhD

劉炳宏

楊弘源

林佳宏

柯崴傑

鄭元博

郭建志

郭桐惟

湯曜任

MS

洪浩翔

曾聿民

趙英欽

陳民倫

何承宜

黃炳欽

黃文謙

蔡志賢

簡志軒

高啟晏

汪芳如

柯品丞

袁孝安

溫健弘

吳佳怡

許書豪

邱士維

游振威

郇志翔

謝雨岑

徐玉蘋

邱文顥

賴胤竹

楊秀先

鄭如意

王思平

陳孟岑

王愷宏

吳孟桓

劉邦亨

張益銘

劉昇倫

許芳華

許景翔

朱書賢

李彥余

張家豪