多點對一點網路上媒介存取控制的最佳化競爭範圍分配方法
申請人姓名：林盈達，尹維銘，林永松 先生

中文發明摘要：
一種多點對一點網路媒介存取控制的最佳測距方法， 尤其是一種求取最佳競爭範圍以使競爭範圍的使用效率極 佳化的方法，其利用建置最佳化表格查詢以達到本發明在 多點對一點之網路媒介存取的競爭範圍(contention region)內最佳化分配以減少碰撞的目的,因而在本發明 簡單快速的特性下，獲得最佳化流通率以降低頻寬之浪 費。本方法係將一個競爭週期(contention cycle)分成初 始競爭階段(initial contention phase)與碰撞解決階段 (collision resolution phase)，在初始競爭中失敗的要 求，會透過碰撞解決以成功地送出要求。本方法之執行步 驟如下：首先，利用電腦模擬實際競爭狀況而得最有可能 要求數表格MLR(d,S,c)及最佳化表格OPT(n,d)﹔其次，在 初始競爭階段，採用時間等比例方法，估測要參加初始競 爭之要求數，利用此要求數查詢依據機率法則所預置之最 佳化表格OPT(n,d)，其中，n為估測之要求數，d為對應n 的最佳競爭範圍,用以決定最佳初始競爭範圍;接著，在 碰撞解決階段，根據每次競爭輪迴(contetion round)的 結果,查詢根據程式模擬實際競爭狀況所建構之最有可能 要求數表格MLR(d,s,c)其中，d為配置的競爭範圍，s為 成功的要求數，c為碰撞群數量，利用此表格估測尚未成 功解決碰撞的要求數n;最後，根據此要求數n查詢與在初 始競爭階段預置之最佳化表格OPT(n,d)，用以決定各競爭 範圍的最佳值d，使得要求的流通率最大。

申請專利範圍
1.一種求取多點對一點網路媒介存取控制之最佳競爭範圍配置方法，係用於複數要求競爭動態指定時槽群，在進行競爭程序中，每個競爭輪迴定義至少一個最佳競爭範圍，且複數競爭輪迴形成一個競爭週期，包括下列步驟：

  • 建立一最可能要求數表格MLR(d,s,c)，其中，d係為競爭範圍，s係為成功送出的要求數，c係為碰撞群數；
  • 建立一最佳化表格OPT(n, d)，其中，n係為估測之待競爭要求數，d係為相對之最佳競爭範圍；
  • 估測下一競爭週期中待兢爭的要求數ni, l，其中，i係為下一競爭週期，ni, l係開始競爭週期i時的初始要求數；
  • 估測下一競爭輪迴j中待競爭的要求數ni, j，其中，j>1，ni, j係為該競爭週期i中第j個競爭輪迴時的要求數，該估測方法是根據前一兢爭輪迴的競爭結果，查詢該最可能要求數表格MLR(d, s, c)，來估測一要求數ni, j的值；
  • 利用該要求數ni, j做為索引，從該最佳化表格OPT(n, d)中尋找相對於該要求數ni, j的d值，該d值即為週期i之第j個競爭輪迴的最佳競爭範圍；
    分配給週期i之下一競爭輪迴j該d值作為定義之最佳競爭範圍。

    2.如申請專利範圍第1項之方法，其中，該最可能要求數表格MLR(d, s, c)可利用電腦模擬實際競爭狀況而得，包括下列步驟：
  • 決定一競爭範圍及參加競爭的要求數；
  • 利用電腦模擬各要求數實際競爭狀況t次，其中t 103，出現成功要求成功s，要求碰撞群c；
  • 指定出現組合(s, c)次數最多之要求數作為MLR(d, s, c)的值。

    3.如申請專利範圍第1項之方法，其中，該競爭程序是阻斷模式。

    4.如申請專利範圍第2項之方法，其中，根據該團體模式，在要求數與時間呈等比例分佈時，該競爭週期i中待競爭的要求數ni, l可由下列公式估測之：
  • ni, l / ni-1, l＝(週期i-1的長度)/(週期i-2的長度)其中，ni-1, l，為開始競爭週期i-1時的初始要求數
  • 週期i-l為週期i的前一週期
  • 週期i-2為週期i-1的前一週期。

    5.如申請專利範圍第1項之方法，其中，該最佳化表格OPT(n, d)用於已同步系統的競爭範圍分配時，di, j = ni, j。

    6.如申請專利範圍第1項之方法，其中，該最佳化表格OPT(n, d)用於未同步系統的競爭範圍分配時，OPT(n, d)可由p(n, m, d)求得，p(n, m, d)代表在要求數n競爭d個時槽時，其中m個要求成功的機率，利用p(n, m, d)建立表格OPT(n, d)的方法包括下列步驟：
  • 定義opt_d_n為n個待競爭要求數所對應的最佳競爭範圍，其中，n>1；
  • 判斷要求數n是否介於定義之大於1且小於極大值k的範圍內；
  • 測試各要求數n之最佳競爭範圍opt_d_n從1開始至給予之極大值max_d並從中計算花費之時間；
  • 選取各要求數所對應之受測試最佳競爭範圍中，花費時間最小者做為該要求數之最佳競爭範圍opt_d_n。