反應曲面法Response surface methodology,簡寫RSM)為結合數學與統計而延生出的方法,為最適實驗設計或作業條件的有利工具,於1951年,Box 和 Wilson 共同進行數學模式的建立與推導,而後普遍應用於電子、機械、農業、化學工業、生物科技、材料科學、食品科學及工業製程改善等各項研究領域中。

說明

編輯

反應曲面法在協助研究人員對科學系統或工業製程中最佳產品設計、製程改善、系統最佳化等問題提供一套分析、求解程序,大部分應用時機均屬工業性研究,尤其是當系統特性受大量變數影響狀況下最為適當。

歷史

編輯
1920 R.A. Fisher 從基本的實驗設計技術的改進開始發展反應曲面法,並將農業及生命科學的實驗設計技術引進工業界。
1951 Box 和 Wilson 共同進行數學模式的建立與推導開始。
1966 Hill 和 Hunter 等相關研究下,其理論模式的建立與應用已趨於完整。
1966~1988 相關延伸的研究包含了探討模式的穩健性、可旋轉性、直交性、最佳化設計與自變數高度相關等因子實驗或混和實驗中常見問題,以及反應曲面法分析中之正規分析、脊線分析與雙反應曲面系統等。
1980 由於電腦模擬技巧應用於決策科學上漸受歡迎,反應曲面法亦成為分析複雜系統中重要影響變數的一項工具
2000至今 多反應值最佳化設計與多反應值共同最佳化問題成為反應曲面法研究的主流。

概念

編輯

反應曲面法之研究問題,一般假設問題為限制性之最佳化問題,目標函數的確切型式是未知的    為誤差,反應曲面法一般在此前提的假設與應用系統的限制下,可有效地求得最佳實驗或作業變數值。 一般來說,執行反應曲面法大致分為兩階段:

反應曲面設計

編輯

為探討獨立變數與反應變數之間的數學模式關係,因此欲對於反應和獨立變數之間找出一個適當的近似函數。通常利用獨立變數在一些範圍裏的低階多項式近似,即為一階迴歸模型 (first-order model),

 

如果系統中有曲率,則必須利用較高階的多項式,如二階模型(second-order model)。

 

獲得最適化實務模型便是本階段最重要的議題。收集資料後以最小平方法 (least squares estimation, LSE) 配適,以尋找出一個適當近似的函數,採用迴歸分析的顯著性檢定 (general linear test approach) 來瞭解獨立變數與反應變數間的關係強弱,並檢定配適的模式是否恰當 (statistical adequacy)。當實驗區域接近最佳反應值附近時,真實反應曲面的曲率 (curvature) 會增加,則考慮二階模型,同樣的,我們需要檢定二階模式的適當性。當這個二階迴歸模式配適良好時,便可以利用這二階模式求得最適操作點及特徵化反應曲面。

反應曲面最佳化

編輯
反應曲面法是一個逐次程序 (sequential procedure)。通常,當我們是在反應曲面的一個遠離最佳狀況的點時,系統只有少量的曲率而一階模型會是適當的,在此欲沿着改善路徑快速且有效地朝向最佳點 (optimum) 附近。
進而利用最陡上升(下降)法 (steepest ascent/descent method)。所配適一階模型的反應曲面,也就是   的等高線,沿着最大反應變數增加(減少)逐次移動程序,直到反應值無法再改善為止,其中,前進步伐的決定並非固定不變,可以根據實驗情況或經驗值決定,接着以此組操作水準為新的實驗中心點,並重複實驗步驟,往最佳反應曲面的方向逼近,並且執行線性模式之缺適性檢定,一旦發現一階迴歸模型不適合時,表示已接近最佳點,此時應採用更複雜的數學模式來進行分析。
 
最陡上升路徑
如果選擇二階模式配適實驗資料時,一般進行中央合成設計實驗英語central composite design (CCD)或是三水準因子設計 (three-level factorial design),在配適及檢定二階模型完成之後,就進行反應曲面分析,指在目前實驗區域中,以實際不同情況(或製程限制)針對反應曲面系統作深入探討。此時可利用正規分析或脊線分析等技術來進一步瞭解穩定點 (stationary point) 之數學特性,其發現為鞍點 (saddle point) 則需進行更進一步的脊線分析,並配合反應曲面圖(或輪廓圖)的協助,若二階模式配適時仍存在缺適性之問題,則可以求得局部最佳操作狀態或再進而配適更高之迴歸模式,如三次 (cubic) 或四次 (quartic) 模型。
 
反應曲面

優點

編輯
  1. 經濟性原則:反應曲面法可以使用部分因子設計或特殊反應曲面設計(如混種設計等 (hybrid design)),以較少的實驗成本及時間獲得不錯且有效的資訊。
  2. 深入探討因子間交互作用影響:反應曲面法可以經由分析與配適模式來研究因子間的交互作用,並且進而討論多因子對反應變數影響的程度。
  3. 獲得最適化的條件:根據數學理論求得最適的實驗情況,同時利用配適反應方程式繪出模式三度空間曲面圖與等高線圖,觀察並分析出最適的操作條件。
  4. 減少模擬時間:可獲得模擬獨立變數與響應變數關係之數學模型,藉此將實驗次數及時間降低。

限制

編輯

在應用上主要存在下列二項限制:

  1. 只適用於連續性的系統,是假設所有反應值與獨立變數的量測刻度是連續性的。
  2. 影響系統之獨立變數(可控制和不可控制變數)是屬於計量性。

應用

編輯
這裏以行動隨意網絡 (MANET) 為例。
網絡是由行動主機 (Mobile host, MH) 所組成,這些 MH 中有部分擔任群組管理者 (Cluster Manager, CM) 的工作。管理者身分的行動主機主要負責群聚的形成、維持,並維護網絡拓樸。行動主機會對群聚內的成員作資源分配及管理;另外一種 MH 就稱為一般節點。MANET架構環境下,每個MH不需經過基地台即可自我組織 (Self-organization) 形成動態網絡,每個 MH 之間可隨意移動藉由多跳躍無線鏈結 (multi-hop wireless links) 彼此溝通,每個 MH 也是像路由器一般擔負的封包傳送與轉送。

背景

編輯
行動隨意網絡不需無線基地台 (Base station, BS) 或無線網絡橋接器 (Access point, AP) 即可做點對點的傳輸,在應用上有很多好處。像是在災難發生導致主從式網絡架構毀壞時,提供救助或著是緊急運作;在不利或是不熟悉的地方進行軍事策略任務等。

因此大量的研究注重在最適化協定堆疊 (protocol stack) 中個體層的協議之執行。一些基本的參數如下:

問題與方法

編輯

而這裏主要探討的是行動式隨意網絡裏 IEEE 802.11 中的 媒體存取控制 (Medium access control, MAC) 協定和隨意隨選距離向量 (Ad hoc On demand Distance Vector, AODV) 路由協議間的通訊。 由於目前沒有一個通用的方法論來確認和最適化協定之間的通訊,這裏利用反應曲面法來解決這些問題。

考慮三個可能影響的因子:

A:Active route timeout
B:Max route request wait timeout
C:Max retransmissions

將三個因子分別設定成二個水準(利用 ns-2 模擬器中 AODV 軟件分配的預設值)

而網絡性能上考慮以下二個變數做為反應變數:

Average throughput:目的地節點每秒收到的數量(bytes/sec)
Average packet delay:一個封包從來源送到目的節點所花的平均時間(sec)

因此我們將網絡分析的問題轉變為二水準三因子實驗設計(response surface design)

接下來利用反應曲面法尋求最佳化 (response surface optimization) ,使得 average throughput 最大,average packet delay 最小。 並且在某個限制式下,尋求最佳解,例如,延遲時間在 400ms 之內。

可利用 ns-2 模擬器來模擬出 20 次不同的流動情境,拿預設值和用 RSM 找出的最佳解做比較。

以下是利用蒙地卡羅 (Monte Carlo) 模擬下,一些比較的結果:

因子動態

編輯

在不同的網絡設定下,有可能導致不同因子對於反應變數的影響程度。因此對於因子在不同網絡環境下之表現行為的了解,對 RSM 是很重要的。 不僅可以決定超初的搜尋範圍,亦可決定最陡上升(下降)法的步伐大小。 某些應用中,平均網絡速度及節點密度是已知的條件,在自然世界的動態中可能會不合適,因此在分析時亦需將當下的網絡條件隨時做改變。 關於這個問題,可將因子配上一個權重表示,設定所有因子的權重起始值為1,而權重將隨着網絡設定的不同而改變;0表示對反應變數沒有影響。

下表為不同網絡設定下,各因子的影響程度比較:

相關工作

編輯

此例子為在 IEEE 802.11 中的媒體存取控制協定和隨意隨選距離向量路由協定中的通訊,其他的協定下的補充研究可參考

  • AODV:E.M. Royer and C.E. Perkins
  • DSR:Maltz, J. Broch, and D.B. Johnson
  • ODMRP:S.H. Bae, S.-J. Lee, and M. Gerla
  • ABR:C.K. Toh and M. Delawar

參考文獻

編輯
  • K.K. Vadde, V.R. Syrotiuk, D.C. Montgomery, 「Optimizing Protocol Interaction Using Response Surface Methodology,」IEEE Transations On Mobile Computing, Vol. 5, NO. 6, June 2006.
  • E.M. Royer and C.E. Perkins, 「An Implementation Study of the AODV Routing Protocol,」 Proc. IEEE Wireless Comm. and Networking Conf. (WCNC), vol. 3, pp. 23-28, Sept. 2000.
  • D.A. Maltz, J. Broch, and D.B. Johnson, 「Experiences Designing and Building a Multi-Hop Wireless Ad-Hoc Network Testbed,」 Technical Report CMU-CS-99-11, Carnegie Mellon Univ., Mar. 1999.
  • D.A. Maltz, J. Broch, and D.B. Johnson, 「Lessons from a Full-Scale Multihop Wireless Ad Hoc Network Testbed,」 IEEE Personal Comm. Magazine, vol. 8, no. 1, pp. 8-15, Feb. 2001.
  • S.H. Bae, S.-J. Lee, and M. Gerla, 「Unicast Performance Analysis of the ODMRP in a Mobile Ad-Hoc Network Testbed,」 Proc. IEEE Conf. Computer Comm. and Networks (ICCCN 』00), pp. 148-153, Oct. 2000.
  • C.K. Toh and M. Delawar, 「Implementation and Evaluation of an Adaptive Routing Protocol for Infra-Structureless Mobile Networks,」 Proc. IEEE Int』l Conf. Computer Comm. and Networks, pp. 16- 18, Oct. 2000.

外部連結

編輯